Re: [scheme-reports-wg1] eqv? on procedures

[John Cowan]

Taking this to the public list, as the discussion is now technical
and not merely procedural.

Alex Shinn scripsit:

> Kent Dybvig was the only one opposed to the change [to making
> eqv? possibly fail on procedures] and he points out in
> <http://www.r6rs.org/r6rs-editors/2007-May/002246.html>
> specifically that it breaks code, but his argument was not strong,
> and the other editors didn't seem to think procedures should be allowed
> to be put in hash tables.

He adds more detail in
<http://www.r6rs.org/r6rs-editors/2007-May/002248.html>:

I don't care as much about making eq?/eqv? work reliably on
procedures as for immutable pairs and records. In r5rs and
perhaps before, however, the intent was that eq?/eqv? would work
on procedures used to implement objects with state. Some people
(including me) felt this was useful, some did not. I've also
seen people use eq? to recognize specific merely procedures in the
interfaces for various procedures. (Common Lisp's hash-table
mechansism does this.)

> It's pretty easy to come up with a list of other things this breaks:

Excellent list!

Or as the R2RS abstract has it:

Data and procedures and the values they amass,
Higher-order functions to combine and mix and match,
Objects with their local state, the messages they pass,
A property, a package, the control point for a catch --
In the Lambda Order they are all first-class.

One Thing to name them all, One Thing to define them,
One Thing to place them in environments and bind them,
In the Lambda Order they are all first-class.

In R6RS, procedures are *not* first class, and they are not "objects
with their local state" any more. Arguably records do that better, but
should we really feel free to abandon one of the founding ideas of Scheme?
I think not.

--
Ambassador Trentino: I've said enough. I'm a man of few words.
Rufus T. Firefly: I'm a man of one word: scram!
--Duck Soup John Cowan <co...@ccil.org>

[John Cowan]

(Redirecting technical discussion to the public list.)

Alex Shinn scripsit:

> True. The point is the entire rationale for introducing #467 is bogus.

I don't see why. Alaric originally proposed that implementations be
allowed to say procedures were eqv? if their code objects were eq? and
their closed-over variables were eqv?. This is a pretty good extension
to the R5RS notion; however, it's potentially unbounded, and thus doesn't
work well as the definition used by eq?. With #467 in place, though,
eq? could be quick and dirty and eqv? more clever.

This whole idea falls down again, however, on the "objects and their
local state" criterion. Worse, it allows two closures to be eqv? at
one point and not so at another (because a closed-over variable has been
mutated), which is not very much like the usual definition of eqv?; if
objects are ever identical, they are always identical, because identity
implies sharing the same history and destiny.

So yes, I agree that #467 is useless if we overturn #125. It does no harm
in that case, though, and we may as well leave it in place. Allowing
eq? to fail for identical characters isn't useful in any Scheme I know
of, but there it is, and it would be silly to withdraw the permission now.

--
Some people open all the Windows; John Cowan
wise wives welcome the spring co...@ccil.org
by moving the Unix. http://www.ccil.org/~cowan
--ad for Unix Book Units (U.K.)
(see http://cm.bell-labs.com/cm/cs/who/dmr/unix3image.gif)

[Alex Shinn]

On Sat, May 4, 2013 at 3:49 PM, John Cowan <co...@mercury.ccil.org> wrote:

(Redirecting technical discussion to the public list.)

Alex Shinn scripsit:

> True.  The point is the entire rationale for introducing #467 is bogus.

I don't see why.  Alaric originally proposed that implementations be
allowed to say procedures were eqv? if their code objects were eq? and
their closed-over variables were eqv?.  This is a pretty good extension
to the R5RS notion; however, it's potentially unbounded, and thus doesn't
work well as the definition used by eq?.  With #467 in place, though,
eq? could be quick and dirty and eqv? more clever.

My understanding was this was proposed as a compromise

to allow eqv? to preserve locations but eq? to be locationless.

This argument is bogus because if there is any procedure in

the language that can discriminate locations the optimizations

being argued for can't be applied.

If I'm misremembering and this _wasn't_ the motivation, the

question remains, what _is_ the motivation?  You're describing

a new semantics, but no compiler writers have asked for

this semantics, nor have any users, nor does this change have

any history in Scheme.

We should not be in the business of making semantic changes

without a good reason, even ones that seem "harmless."

Furthermore, the comparison you suggest is a structured

comparison, isomorphically comparing the compiled code and

the closed cells.  If anything this is something that should be

done by equal? (and I think if any implementors wanted to do

this they already would have).

So I think this change was proposed on false premises and

is poorly thought out, and so should be removed along with

the eqv? change.

-- 

Alex

[John Cowan]

Alex Shinn scripsit:

> My understanding was this was proposed as a compromise to allow eqv? to
> preserve locations but eq? to be locationless.

No, it potentially widens eqv? rather than narrowing it. For example:

(let* ((x 1)
(f (lambda (y) (+ x y))
(g (lambda (y) (+ x y)))
(eqv? f g))

is allowed to return #t if the compiler notices that the code-vectors are
identical and merges them, thus allowing the closures to be merged too.
However, f and g cannot be eq?.

> If I'm misremembering and this _wasn't_ the motivation, the question
> remains, what _is_ the motivation? You're describing a new semantics,
> but no compiler writers have asked for this semantics, nor have any
> users, nor does this change have any history in Scheme.

Well, you're right about that. But as far as I know, the
eq?/eqv? distinction for characters and fixnums is something else that
no Schemer has ever wanted, and no Common Lisper either; it goes back
to Maclisp, which allocated both characters and fixnums on the heap.

> Furthermore, the comparison you suggest is a structured
> comparison, isomorphically comparing the compiled code and
> the closed cells. If anything this is something that should be
> done by equal? (and I think if any implementors wanted to do
> this they already would have).

The eqv? comparison of bignums is isomorphic too (though admittedly bigits
are handled under the radar, so bignums aren't really the same case).

> So I think this change was proposed on false premises and is poorly
> thought out, and so should be removed along with the eqv? change.

We're on the semifinal report, and there has been no groundswell of
objection to #467. Ignoring undecided votes, only Ganz actually opposed
it in ballot 6. I say, leave it alone.

--
John Cowan http://www.ccil.org/~cowan co...@ccil.org
Uneasy lies the head that wears the Editor's hat! --Eddie Foirbeis Climo

[Alex Shinn]

On Sun, May 5, 2013 at 11:47 AM, John Cowan <co...@mercury.ccil.org> wrote:

> Furthermore, the comparison you suggest is a structured
> comparison, isomorphically comparing the compiled code and
> the closed cells.  If anything this is something that should be
> done by equal? (and I think if any implementors wanted to do
> this they already would have).

The eqv? comparison of bignums is isomorphic too (though admittedly bigits
are handled under the radar, so bignums aren't really the same case).

Indeed, bignums are a very different story, a workaround for the fact that

not everything fits in a fixnum.  Closures actually have state and reference

objects.

 

> So I think this change was proposed on false premises and is poorly
> thought out, and so should be removed along with the eqv? change.

We're on the semifinal report, and there has been no groundswell of
objection to #467.  Ignoring undecided votes, only Ganz actually opposed
it in ballot 6.  I say, leave it alone.

Fine.

-- 

Alex

[Steven Ganz]

For the record, this is the basis of my objection -- that procedures (code + free values) should be treated analogously to vectors.  'equal?' is the procedure that digs in and compares based on the values.

Steve

---

From: "Alex Shinn" <alex...@gmail.com>
To: scheme-re...@googlegroups.com
Sent: Saturday, May 4, 2013 7:07:37 PM
Subject: Re: [scheme-reports-wg1] eqv? on procedures

-- 

Alex

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

[Alexey Radul]

I am of the opinion that Henry Baker [1] was right about object
identity -- the only true identity comparison compares immutable
(portions of) objects structurally, and mutable ones by location.
Since, technically, all "compound" Scheme objects (procedures, pairs,
strings, vectors, and records [2]) are mutable, eqv? is the closest modern
Scheme can get. I am therefore very happy with the course this thread
has taken so far, namely to restoration of the requirement that eqv?
behave correctly on procedures (interpreted as mutable objects).

The existence of equal? is justified by the fact that, though Scheme's
compound objects are all mutable, many of them (notably pairs and
vectors) are often used immutably, so structural comparison is an
extremely valuable operation.

But why does Scheme have eq? ? The only possible justification for
eq? is that sometimes (e.g., bignums) structural comparison is too
expensive, so the programmer is willing to sacrifice accurate
identification of immutable objects in order to guarantee efficient
execution.

However, the essence of the opposition to #125 is that Scheme
procedures really are mutable objects, and their identity as such
really is important both aesthetically and in practice. This means
that overturning #125 constitutes restoring the R5RS constraints upon
the semantics of both eq? and eqv? applied to procedures; whereas
upholding #467 grants (novel) permission for eq? and eqv? to have
different semantics within those constraints (for example, permitting
eqv? to perform structural comparison on free variables that provably
cannot be assigned (from anywhere, not just the body of that
procedure)). As an editorial suggestion, this can be implemented
without duplication of words by defining that eqv? on procedures is
required to return #t if eq? does, and spelling out the minimum
requirements of procedure identity in the specification of eq?.

Best,
~Alexey

[John Cowan]

Alexey Radul scripsit:

> I am of the opinion that Henry Baker [1] was right about object identity
> -- the only true identity comparison compares immutable (portions of)
> objects structurally, and mutable ones by location.

I agree entirely. Unfortunately, history places its own demands
on what a standard Scheme can provide.

> The existence of equal? is justified by the fact that, though Scheme's
> compound objects are all mutable, many of them (notably pairs and
> vectors) are often used immutably, so structural comparison is an
> extremely valuable operation.

In addition, if two ordered mutable containers contingently contain the
same values at a particular moment in their evolution, equal? can test
for that situation as well. However, equal? is limited in what it can
handle by the weight of tradition: it descends into pairs, vectors,
and strings (to which R6RS and R7RS add bytevectors), but reports
the same as eqv? for all other objects, including user-defined or
implementation-specified ones.

I am therefore proposing generalized-equal? for R7RS-large, which
accepts two objects and an arbitrary number of comparators, which are
procedures that are called in sequence, returning #t if their arguments
are generalized-equal?, #f if they are not, and 'pass if the procedure
cannot tell. Each comparator is also passed the full current list of
comparators, to allow it to invoke generalized-equal? recursively.
By using comparators for numeric, char-ci, string-ci, and hashtable
equality, for example, we get the equivalent of CL equalp.

> But why does Scheme have eq? ? The only possible justification for
> eq? is that sometimes (e.g., bignums) structural comparison is too
> expensive, so the programmer is willing to sacrifice accurate
> identification of immutable objects in order to guarantee efficient
> execution.

Just so.

> As an editorial suggestion, this can be implemented
> without duplication of words by defining that eqv? on procedures is
> required to return #t if eq? does, and spelling out the minimum
> requirements of procedure identity in the specification of eq?.

Editorially, Scheme has always defined eq? by its difference from eqv?
rather than vice versa.

--
John Cowan http://www.ccil.org/~cowan co...@ccil.org

To say that Bilbo's breath was taken away is no description at all. There are
no words left to express his staggerment, since Men changed the language that
they learned of elves in the days when all the world was wonderful. --The Hobbit

[Alexey Radul]

On Sun, May 5, 2013 at 10:43 PM, John Cowan <co...@mercury.ccil.org> wrote:
>> As an editorial suggestion, this can be implemented
>> without duplication of words by defining that eqv? on procedures is
>> required to return #t if eq? does, and spelling out the minimum
>> requirements of procedure identity in the specification of eq?.
>
> Editorially, Scheme has always defined eq? by its difference from eqv?
> rather than vice versa.

I merely brought the option up because I could think of no non-awkward
way to do otherwise. The minimum required coarseness (to wit,
maintaining the identity of procedures) applies to eq? and eqv?
equally, but furthermore, eqv? must be no finer than eq?. If we
define the lower bound in eq?, then eqv? will inherit it from their
relationship; but if we define it in eqv?, then eq? will need to
either repeat or reference the definition of the lower bound on eqv?'s
behavior (as opposed to eqv?'s actual behavior in the implementation,
which is what the definition of eq? referenced in R5RS).

~Alexey

[John Cowan]

Alexey Radul scripsit:

> The minimum required coarseness (to wit, maintaining the identity
> of procedures) applies to eq? and eqv? equally, but furthermore,
> eqv? must be no finer than eq?.

That is already so generically. After saying that on most datatypes
eq? and eqv? behave identically, R5RS says:

On numbers and characters [and procedures -- R7RS], eq?'s behavior
is implementation-dependent, but it will always return either
true or false, and will return true only when eqv? will also
return true.

So eqv? can never make finer distinctions than eq?.

--
My corporate data's a mess! John Cowan
It's all semi-structured, no less. http://www.ccil.org/~cowan
But I'll be carefree co...@ccil.org
Using XSLT
On an XML DBMS.

[Alexey Radul]

On Sun, May 5, 2013 at 11:23 PM, John Cowan <co...@mercury.ccil.org> wrote:
> Alexey Radul scripsit:
>
>> The minimum required coarseness (to wit, maintaining the identity
>> of procedures) applies to eq? and eqv? equally, but furthermore,
>> eqv? must be no finer than eq?.
>
> That is already so generically. After saying that on most datatypes
> eq? and eqv? behave identically, R5RS says:
>
> On numbers and characters [and procedures -- R7RS], eq?'s behavior
> is implementation-dependent, but it will always return either
> true or false, and will return true only when eqv? will also
> return true.
>
> So eqv? can never make finer distinctions than eq?.

Yes, of course. But you will note that the quoted passage places no
lower bound on eq?'s coarseness on numbers and characters -- R5RS
allows eq? to always return #f when either argument is a number or a
character. If #125 is overturned and #467 is not, the result will be
that eq? is permitted to differ from eqv? on procedures, but must
still obey the lower bound that placing a procedure into a
data structure and taking it out again produces an eq? object. This is
the state that I find it somewhat awkward to implement, even though it
is the right state (unless we overturn #467 also, which would be fine
by me).

~Alexey

[John Cowan]

Alexey Radul scripsit:

> Yes, of course. But you will note that the quoted passage places no
> lower bound on eq?'s coarseness on numbers and characters -- R5RS
> allows eq? to always return #f when either argument is a number or a
> character.

Indeed. See FixnumInfo for what various Schemes actually do: there are
a few Schemes that appear to box every exact integer.

> eq? is permitted to differ from eqv? on procedures, but must still
> obey the lower bound that placing a procedure into a data structure
> and taking it out again produces an eq? object.

There is no such guarantee in general: when ou put something into a
container and take it out again the result is merely eqv?, not eq?, to
the original.

> unless we overturn #467 also, which would be fine by me.

That appears to be what Our Fearless Leader is going to do.

--
John Cowan co...@ccil.org http://ccil.org/~cowan
The present impossibility of giving a scientific explanation is no proof
that there is no scientific explanation. The unexplained is not to be
identified with the unexplainable, and the strange and extraordinary
nature of a fact is not a justification for attributing it to powers
above nature. --The Catholic Encyclopedia, s.v. "telepathy" (1913)

[Steven Ganz]

As an alternative, equality could be built into the record infrastructure. If record type definitions allowed for a customized equality predicate, then plain old equal? could use them.

----- Original Message -----
From: "John Cowan" <co...@mercury.ccil.org>
To: scheme-re...@googlegroups.com
Sent: Sunday, May 5, 2013 7:43:12 PM
Subject: Re: [scheme-reports-wg1] eqv? on procedures

Alexey Radul scripsit: