Re: [Scheme-reports] Procedural equivalence: the last debate

[Ray Dillinger <bear@x>]

On 06/01/2013 09:03 PM, John Cowan wrote:

: clip:

> proposal
> is to reverse one of the changes to R5RS, namely the rules for `eqv?`
> and `eq?` when applied to procedures.

To summarize, there are three classes of procedures of interest.

On procedures that behave differently these predicates are required
to return #f in both cases.

On procedures that behave identically but which were created at
different times (by different invocations of lambda), these
predicates may return #t or #f in both cases.

On procedures that were created by the same invocation of lambda
(which will definitely behave identically) the R6RS allows returning
#t or #f, and the R5RS semantics (which this proposes returning to)
requires the predicates to return #t.

In favor of the R6RS semantics, a procedure-call optimization is
easier to implement and can be applied in more cases, so under these
semantics it's fairly easy to make a scheme system run faster.

In favor of the R5RS semantics, there is a long list of things that
can use procedure identity as keys or for comparison, which do not
work otherwise. Among these are TinyCLOS generics, which are IMO the
premier example of generic procedures done well for Scheme, and hash
tables on procedures as keys, which I find myself using more and more 
extensively the more I get used to them. They are central to some OO 
techniques I've been using.

I'm very much in favor of the R5RS semantics; I regarded the R6RS
changes to procedure equivalence predicates as a mistake at the time,
and still do.

Inlining and call optimizations are still possible with the R5RS
semantics; it becomes only slightly more difficult to implement
(some scope and position checks have to be made and escape analysis
must be done) and covers 95%+ of the cases allowed by the R6RS 
semantics.  Therefore, In my opinion, preferring R6RS semantics for 
performance reasons is not a compelling argument.

By comparison, I find the issues listed below *VERY* compelling. 
Additionally, the model of computation expressed by the R5RS semantics
is aesthetically superior to me as a nearer approximation to the
"right thing."  I find the R6RS semantics on this point inconsistent
and counterintuitive. I imagine someone asking "why is this obviously
true thing not treated as true?" and having no good answer to give them.

				Bear


: clip :


  == Advantages of the R5RS semantics ==
>
> In Scheme, procedures have always had identity, and a large body of code
> stretching from the original Lambda: the Ultimate papers up to the present
> day depends on it.  Unfortunately, breaking the first-class status of
> procedures as objects causes a number of techniques previously possible
> to become unreliable.  (The following list was prepared by Alex Shinn.)
>
>    - Using procedures as lightweight objects or actors
>    - SRFI-17 (generalized set! needs to lookup procedure setter)
>    - TinyCLOS generics (needs to understand method identity)
>    - Elisp `add-hook' equivalents (needs to avoid duplicates)
>    - Fast paths such as SRFI-1 lset-* optimized for eq?,
>      or SRFI-95 sort optimized for<.  See
>      https://wiki.call-cc.org/eggref/4/special-case for the
>      general case of special cases.
>    - Caching with procedures as (part of) the key.  Given
>      a large enough cost and high enough cache hit ratio,
>      caching is an arbitrarily large speedup.
>    - Memoization.  The (chibi parse) parser combinator
>      library memoizes combinators to achieve packrat
>      parser-like performance.  The test case at
>      https://code.google.com/p/chibi-scheme/source/browse/tests/parse-tests.scm#121
>      runs in exponential time with memoization disabled,
>      and linear time otherwise.




_______________________________________________
Scheme-reports mailing list
Scheme-reports@x
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports