Any objections to restoring R5RS rules of procedure equivalence?

[John Cowan]

I'm going to file a formal objection with the SC about reverting
the R7RS-small semantics of procedure equivalence to the R5RS rules.
This means that closures have identity. If they don't, Alex has provided
the following list of what will break:

- 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.

Alex and John Boyle have debunked the argument from compiler performance to
my satisfaction, at least, and I have noted that a procedure with settable
variables is a mutable object and should have identity like other mutable
objects.

But I can't do this in the name of the WG if someone on the WG objects,
so I'm giving you all a chance to object. At least Cowan, Shinn, Hsu,
Sussman, Gleckler, and Snell-Pym are on board, and Ganz and Radul already
voted for R5RS semantics on ballot 6.

So I'd like to hear specifically from Bradley Lucier, Emmanuel Medernach,
and Jeffrey Read, all of whom voted for R6RS semantics last time.
Any objections to changing this decision?

--
Real FORTRAN programmers can program FORTRAN John Cowan
in any language. --Ed Post co...@ccil.org

[Bradley Lucier]

On May 4, 2013, at 4:31 PM, John Cowan wrote:

>
> So I'd like to hear specifically from Bradley Lucier, Emmanuel Medernach,
> and Jeffrey Read, all of whom voted for R6RS semantics last time.
> Any objections to changing this decision?

No.

[Jeff Read]

On May 4, 2013 4:31 PM, "John Cowan" <co...@mercury.ccil.org> wrote:

> So I'd like to hear specifically from Bradley Lucier, Emmanuel Medernach,
> and Jeffrey Read, all of whom voted for R6RS semantics last time.
> Any objections to changing this decision?
>

No objections from me. I don't know what I was thinking tbh.

[Alaric Snell-Pym]

On 04/05/13 21:40, Jeff Read wrote:
>
> On May 4, 2013 4:31 PM, "John Cowan" <co...@mercury.ccil.org

> <mailto:co...@mercury.ccil.org>> wrote:
>
> > So I'd like to hear specifically from Bradley Lucier, Emmanuel Medernach,
> > and Jeffrey Read, all of whom voted for R6RS semantics last time.
> > Any objections to changing this decision?
> >
>
> No objections from me. I don't know what I was thinking tbh.

I know the feeling too! I think we had a few different things conflated
at the time...

ABS

--
Alaric Snell-Pym
http://www.snell-pym.org.uk/alaric/

[Alexey Radul]

For the record, I continue to fully support restoring R5RS rules of
procedure equivalence.

~Alexey Radul

> --
> You received this message because you are subscribed to the Google Groups
> "scheme-reports-wg1" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to scheme-reports-...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Emmanuel Medernach]

After some dig up, I repeat my POV from July 2012 mails : 

  I am inclined to think that (eqv?  x x), (let* ((x ...)

  (y x)) (eqv?  x y)) and ((lambda (y) (eqv?  x y)) x)

  should always return #t.

  

  The controversial point is the following statement from

  R5RS about eqv? : "obj1 and obj2 are procedures whose

  location tags are equal" because it implies that all

  lambdas have location tags, which (stricly speaking)

  prevents compiler to use inlining.

So I think we don't have to break procedures equivalence and

that is is enough to remove only this sentence above from R5RS.

Sorry for the delay.

[John Cowan]

Emmanuel Medernach scripsit:

> After some dig up, I repeat my POV from July 2012 mails :
>
> I am inclined to think that (eqv? x x), (let* ((x ...) (y x))
> (eqv? x y)) and ((lambda (y) (eqv? x y)) x) should always return #t.
>
> The controversial point is the following statement from R5RS about
> eqv? : "obj1 and obj2 are procedures whose location tags are equal"
> because it implies that all lambdas have location tags, which
> (stricly speaking) prevents compiler to use inlining.

Well, inlining is not possible in any case if the procedure object can
escape its context. But a lambda such as the one in ((lambda (x y)
(+ x y)) 3 4), to take a completely trivial example, cannot possibly
escape, and so the value of its location tag is irrelevant. The essence
of traditional Scheme compiling is figuring out just which lambdas can
and cannot have their location tags merged or stripped without affecting
the correctness of the program.

> So I think we don't have to break procedures equivalence and
> that is is enough to remove only this sentence above from R5RS.

That *does* break procedural equivalence, because location tags are the
*only* way of knowing if procedures are equivalent. In languages like
ML that don't have tags, procedures cannot be compared for identity.
(You cannot, of course, tell procedures apart by their behavior because
of the halting problem.)

--
John Cowan co...@ccil.org http://ccil.org/~cowan
It's the old, old story. Droid meets droid. Droid becomes chameleon.
Droid loses chameleon, chameleon becomes blob, droid gets blob back
again. It's a classic tale. --Kryten, Red Dwarf

[Emmanuel Medernach]

On Sun, May 12, 2013 at 2:25 AM, John Cowan <co...@mercury.ccil.org> wrote:

Emmanuel Medernach scripsit:

> > After some dig up, I repeat my POV from July 2012 mails :

> >

> >   I am inclined to think that (eqv?  x x), (let* ((x ...)  (y x))

> >   (eqv?  x y)) and ((lambda (y) (eqv?  x y)) x) should always return #t.

> >

> >   The controversial point is the following statement from R5RS about

> >   eqv? : "obj1 and obj2 are procedures whose location tags are equal"

> >   because it implies that all lambdas have location tags, which

> >   (stricly speaking) prevents compiler to use inlining.

> 

> Well, inlining is not possible in any case if the procedure object can

> escape its context.  But a lambda such as the one in ((lambda (x y)

> (+ x y)) 3 4), to take a completely trivial example, cannot possibly

> escape, and so the value of its location tag is irrelevant.  The essence

> of traditional Scheme compiling is figuring out just which lambdas can

> and cannot have their location tags merged or stripped without affecting

> the correctness of the program.

> 

Exactly, you said it: in some  case it could be removed ! My

whole point  is to  notice it in  the standard and  to allow

implementors not  allocating a (unique)  tag when it  is not

absolutely  needed.  It  is  not about  forbiding to  always

provide a tag, of course.

Also about  the second  part, I expect  closures to  have an

identity per  se, as noticed  before this is  so fundamental

that we cannot afford losing this feature.

But I already talked about this, you could read my rationale

about this vote item here:

http://trac.sacrideo.us/wg/wiki/WG1BallotMedernach6#a125AllowproceduresnottobelocationsmakingEQVunspecifiedinsomeadditionalcases

Hope it is clearer this time :-I

> > So I think we don't have to break procedures equivalence and

> > that is is enough to remove only this sentence above from R5RS.

> 

> That *does* break procedural equivalence, because location tags are the

> *only* way of knowing if procedures are equivalent.  

Let me illustrate, for instance do we allow Alaric's

definition of eqv? on closures ?

    If a procedure is reified  as a closure object, I gather

    we can easily answer (eqv? x y) as #t if the closure has

    the  same code  vector and  the same  closed-over values

    (identical, not just same-valued, to allow for mutation,

    which  is  trivially  #t  if there  are  no  closed-over

    values), and "maybe, can't tell" (spelt #f) if not.

This seems perfectly sound to me.

Well  Ok,  let's summarize.   I  don't  want  to reopen  the

Pandora box:  I agree to  remove and get  back to R5RS  if a

consensus is needed, but really  I would prefer the "(eqv? p

p)"  paragraph removed  and  would like  the allocation  tag

sentence to be removed as well. Am I the only one ?

--

Emmanuel

[Alex Shinn]

On Tue, May 14, 2013 at 3:55 AM, Emmanuel Medernach <emmanuel....@gmail.com> wrote:

Exactly, you said it: in some  case it could be removed ! My

whole point  is to  notice it in  the standard and  to allow

implementors not  allocating a (unique)  tag when it  is not

absolutely  needed.  It  is  not about  forbiding to  always

provide a tag, of course.

Compiler writers are free to do whatever they want so long

as it doesn't change the observable semantics.  Just because

we say procedures have locations doesn't prevent inlining

and other optimizations in the common cases.

-- 

Alex