guile and elisp

guile and elisp

[Andy Wingo]

Hi all,

For 2.0 I have a very short list of things to do, mostly documentation
and compatibility work, but there is at least one feature: finishing
Mark Weaver's integration of nil into Guile.

If you're just catching up, Elisp has "nil", which is both false and the
end-of-list. Nil works fine in Elisp, but we would like to tightly
integrate Scheme and Elisp, allowing procedures and data to be passed
back and forth -- so we need a way for Scheme to see nil as false.

So! Here's a table of how various functions respond to various inputs.
To make the table more readable, a result of #t is written as T, and a
result of #f as F, and nil as NIL.


                 #t    #f   '()  nil   otherwise
Scheme:
  boolean?       T     T    F    T     F
  not            F     T    F    T     F
  null?          F     F    T    T     F
Elisp:
  booleanp       T     T    T    T     NIL
  not (elisp)    NIL   T    T    T     NIL


I guess I was assuming from the get-go that elisp's T would be Scheme's
#t; one could decide otherwise, but that would be pain for no gain. So
already we see how practical considerations are creeping in :)

Currently in Guile, things are as the table describes; though it could
be that the elisp functions return F instead of NIL. But the whole point
here is to allow Elisp to see #f as nil, so I'm not particularly worried
about this. (I'll be writing test cases according to these tables).

One can see however that introducing a value to which e.g. BOOLEAN? or
NOT respond differently than the "otherwise" case can break code that
assumes that, for example, `(not foo)'` implies that `foo' is #f
(whereas in the future it can be nil also). We don't see these cases
now, because we aren't mixing Scheme and elisp much. But I would argue
that that code is broken; that it should test for /properties/ via the
NULL?, NOT, etc instead of testing for values.


More tricky is what should happen with equality predicates, and the
fallout thereafter. We could make any decision here; but here's one set
of decisions:

     EQ?  #t   #f   '()  nil
     #t   T    F    F    F
     #f        T    F    F
     '()            T    F
     nil                 T

This table shows the result of calling `eq?' between these four values,
specifically that #t is only eq? to #t, #f to #f, and so on. The missing
half of the table is redundant.

EQV? could be like EQ? or like EQUAL?; I am inclined to make it like
EQ?. So, same considerations for EQV?.

But what about this one:

  EQUAL?  #t   #f   '()  nil
     #t   T    F    F    F
     #f        T    F    T
     '()            T    T
     nil                 T

If we disregard #t, because it's not interesting, and cut out the
identity cases, we get the following three rules:

   (equal? #f  '()) => #f    ; required by scheme
   (equal? #f  nil) => #t    ; interop
   (equal? nil '()) => #t    ; interop

But then you break the transitive property of equality!

[An aside: This equal? behavior would require `hash' (not `hashq' or
`hashv') to hash #f, nil, and '() to the same value, then to be
distinguished via `equal?' while traversing the bucket. I don't think
`hash' presents more problems than that.]


                             ***

What to do?

In a perfect world, we want '(a b c . #%nil) to be EQUAL? to '(a b c .
()). But as I showed above, we can't do that without breaking some
corner cases.

It's of course an option to just make `(equal? #f nil) => #f'. But this
would limit the interoperability of Scheme and Elisp. I was telling this
to our fringe languages group last night, and Andrew Bagdanov remarked
that it would be amusing if opaque types like buffers were more
interoperable than pairs.

It would also be an option to translate data from Elisp to Scheme and
back, when going across the language barrier, but this pains me on many
levels; it destroys EQ? semantics, and it changes algorithmic space/time
complexities.

Another option would be to present an abstraction above pairs, or
sequences in general, as Clojure has done. (Incidentally, this decision,
combined with support for lazy sequencies, led Hickey to remove the
concept of nil-as-singleton from his language.)


These are the four options that I see. For myself, the interoperability
benefits of considering '() as equal? to nil are quite compelling, and
outweigh the practical implications of the transitive equal? wart. But,
I wanted to mention this analysis and these options so that interested
people can give feedback, and we can document our decision.

(Actually, thinking on it a little more, maybe it would be the right
thing to do to just keep nil not equal? to #f. But it's a complicated
question, and my brain is tired :))

Thoughts?

Happy hacking,

Andy
-- 
http://wingolog.org/

Re: guile and elisp

[Mark H Weaver]

Hello all,

I still haven't found the time to fully evaluate all of these thorny
issues regarding nil, nor to present my perspectives as persuasively
as I'd like to.  Nonetheless I've thought about this issue a great
deal, and here are my thoughts:

First of all, we need to distinguish the equality predicates from the
values themselves.  It is very important to unify the values from lisp
and scheme, but the equality predicates needn't be unified, and imho
shouldn't be.

In my view, the best way to think of "nil" in guile is: "either #f or
'(), but we don't know which one", rather than as a distinct value in
its own right.  Almost every other language treats those two concepts
as distinct, and needs to be able to tell the difference between them
in order to implement its semantics properly.  In other words, every
"nil" is ambiguous from the point of view of other languages.

I think it's very important that we choose a path which can
potentially lead to clean semantics somewhere down the road in a
future guile-emacs universe with finely intermixed scheme and lisp
code (and other languages for that matter).

So what is the path to clean semantics that I'd like to make available
to future generations of guile-emacs?  I'd like it to be possible to
gradually convert instances of nil to either #f or '(), with the goal
of eventually deprecating nil altogether.  We can think of this
process as "annotating" otherwise ambiguous values, so that non-lisp
languages know how to treat them.  To enable that, we must be able
convert any instance of nil to #f or '() without breaking existing
lisp code.  The way to accomplish this is to have different equality
predicates.

The Lisp equality predicates, and the associated hash tables, alists,
etc, should not distinguish boolean-false and end-of-list (and here's
the important point) regardless of where the values being
compared/hashed came from.  The hacks involving intransitive equality
predicates only work when nil is used; they won't work reliably when
there is non-lisp code involved, nor if any of the aforementioned
annotation has been done.

The Scheme equality predicates should probably treat nil as Andy
proposes.  There is no clean way to handle "nil" in a language which
distinguishes the two concepts that lisp conflates, but Andy's
proposal is the best one I've heard.  Other non-lisp languages should
probably use similiar heuristics to deal with nil.

In addition, we might want to consider some kind of hacks to
automatically annotate data in various places.  We could provide
procedures such as "canonicalize-boolean" which converts nil to #f,
and "canonicalize-list" which converts nil to '() and mutates any nil
in the CDRs to '().

These procedures could be safely called on values which are known to
be of the corresponding types, because semantically, they are only
adding information to what would otherwise be an ambiguous value.
This is only possible if Lisp treats #f, '() and nil as the same
value.

What do you think?

    Mark

Re: guile and elisp

[Andy Wingo]

Hi Mark,

Thanks for the mail. A couple of brief reactions:

On Sat 27 Mar 2010 14:07, Mark H Weaver <mhw@netris.org> writes:

> I think it's very important that we choose a path which can
> potentially lead to clean semantics somewhere down the road in a
> future guile-emacs universe with finely intermixed scheme and lisp
> code (and other languages for that matter).

Yes. And I would put this even stronger, that if Scheme and Elisp were
mixed now, that our solution should have clean semantics, without the
need to migrate elisp.

> So what is the path to clean semantics that I'd like to make available
> to future generations of guile-emacs?  I'd like it to be possible to
> gradually convert instances of nil to either #f or '(), with the goal
> of eventually deprecating nil altogether.  We can think of this
> process as "annotating" otherwise ambiguous values, so that non-lisp
> languages know how to treat them.  To enable that, we must be able
> convert any instance of nil to #f or '() without breaking existing
> lisp code.

Hm, not sure if I follow; and in any case I'm not sure that modifying
existing Elisp code should really be on the table. But your next point
is interesting:

> The [E]Lisp equality predicates, and the associated hash tables,
> alists, etc, should not distinguish boolean-false and end-of-list (and
> here's the important point) regardless of where the values being
> compared/hashed came from.

Good point, that Scheme's equal? (and assoc, and hash-ref) can treat #f
and nil as distinct, but Elisp's equalp can treat them as equivalent.
Thus we don't introduce any intransitivity into the language.

> In addition, we might want to consider some kind of hacks to
> automatically annotate data in various places.  We could provide
> procedures such as "canonicalize-boolean" which converts nil to #f,
> and "canonicalize-list" which converts nil to '() and mutates any nil
> in the CDRs to '().

We could, but I'm not sure I see the need: if Scheme's equal? treats
nil, #f, and '() as distinct, why bother? (As in: what inconsistencies
or problems does this approach create?)

I'm not sure (I keep saying "not sure", and I'm really not :) that
*value* or *identity* is the way to solve this problem. To me the
question is more of *property* -- is this value false, is it equal? to
another, is it a boolean, etc.

Thoughts?

Andy
-- 
http://wingolog.org/

Re: guile and elisp

[Mark H Weaver]

(BTW, I'm deliberately writing "lisp" instead of "elisp" because these
discussions should be relevant to any lisp dialect that uses nil for
both false and eol, and in the future guile might support other lisps).

On Sat, Mar 27, 2010 at 05:54:24PM +0100, Andy Wingo wrote:
> I'm not sure (I keep saying "not sure", and I'm really not :) that
> *value* or *identity* is the way to solve this problem. To me the
> question is more of *property* -- is this value false, is it equal? to
> another, is it a boolean, etc.

Well, if we can assume that all non-lisp code in the guile system will
robustly handle nil by using the appropriate predicates, then yes,
that's a fine solution with clear semantics.  I just don't think
we can safely assume that.

Someday there may be significant libraries and other complex software
developed elsewhere being used in guile-emacs.  Most code outside of
the lisp world has never had to cope with an ambiguous "maybe boolean
false or maybe the empty list" value.  When that code meets the lisp
world, I guarantee you'll start seeing obscure bugs crop up.  The
system as a whole will not be as robust as it could be.

A lot of code outside of lisp uses equality to test boolean values.
If nil is distinct from #f, then that code will fail.

A lot of code assumes that if a value is boolean, then it cannot be a
list, and vice versa.

Some code looks up booleans and/or lists in hash tables or other
structures.  That code won't deal gracefully with list structures
containing nil.

Some object-oriented languages may overload an operation depending on
whether a parameter is a boolean or a list.  I don't see how such code
can deal with nil gracefully without being significantly rewritten.

Using your proposed intransitive equality predicates would handle many
of the common cases properly, but not all of them.

I see no way to handle these kinds of problems robustly without
gradually deprecating nil.  My proposal allows instances of nil to be
incrementally "annotated" by changing them to #f or '().

Lisp code treats all three values the same, so from lisp's point of
view these annotations are harmless and effectively no-ops.  But each
annotation has the potential to prevent some obscure nil-related bugs
from breaking non-lisp code which wasn't designed to handle nil.

These annotations could be done in response to the discovery of a
nil-related bug, or they could be done preemptively to reduce the
probability of such bugs before they occur.

They could be done either in the lisp sources, or elsewhere using my
proposed "canonicalize-*" procedures, perhaps where values are passed
from lisp to non-lisp code, or upon entry to code which is known not
to handle nil gracefully.

So, I guess I should have been more broad when I said that I want
"clear semantics".  More than that, I want to be able to robustly mix
lisp code with other code that was never designed to interface well
with lisp, with a minimum of obscure bugs cropping up.  The gradual
deprecation of nil (or at least the option of eventually doing so) is
the only path I see to toward that end.

   Regards,
     Mark

Re: guile and elisp

[Andy Wingo]

Hey Mark,

Thanks for the thoughts.

On Sat 27 Mar 2010 19:01, Mark H Weaver <mhw@netris.org> writes:

> (BTW, I'm deliberately writing "lisp" instead of "elisp" because these
> discussions should be relevant to any lisp dialect that uses nil for
> both false and eol, and in the future guile might support other
> lisps).

Sure, good point. Scheme is still a lisp, so it helps me to write
"elisp", but I'll try to parse your statements appropriately :)

> On Sat, Mar 27, 2010 at 05:54:24PM +0100, Andy Wingo wrote:
>> I'm not sure (I keep saying "not sure", and I'm really not :) that
>> *value* or *identity* is the way to solve this problem. To me the
>> question is more of *property* -- is this value false, is it equal? to
>> another, is it a boolean, etc.
>
> Well, if we can assume that all non-lisp code in the guile system will
> robustly handle nil by using the appropriate predicates, then yes,
> that's a fine solution with clear semantics.  I just don't think
> we can safely assume that.

Note that we have the same problem on the Scheme side, for code that
assumes that (not x) implies that x is eq? to #f. I don't want to change
eq?, so this hole will exist. But, at least it's a documentable hole,
and we can fix up any code that needs it without e.g. introducing the
concept of #f-but-not-end-of-list into elisp itself, likewise avoiding
introducing the concept of #f-or-end-of-list into Guile.

Which reminds me: another breakage point would be the canonical:

  (cond
    ((null? x) ...)
    ((not x) ...)
    ...)

The result if x is nil depends on the ordering of the null? and not
clauses.

> Someday there may be significant libraries and other complex software
> developed elsewhere being used in guile-emacs.  Most code outside of
> the lisp world has never had to cope with an ambiguous "maybe boolean
      ^^^^ Scheme?

> false or maybe the empty list" value.  When that code meets the lisp
> world, I guarantee you'll start seeing obscure bugs crop up.  The
> system as a whole will not be as robust as it could be.

Of course you're right. I've just been thinking that all solutions will
have this characteristic to greater or lesser degrees.

> A lot of code outside of lisp uses equality to test boolean values.
> If nil is distinct from #f, then that code will fail.

Such code is in poor style IMO; changing it to use the predicates would
make it cleaner and more correct. Not sure how much code would fall
under this case.

> A lot of code assumes that if a value is boolean, then it cannot be a
> list, and vice versa.

Yes. But what can you do? Not all nil values are actually one or the
other.

> Some code looks up booleans and/or lists in hash tables or other
> structures.  That code won't deal gracefully with list structures
> containing nil.

Ah, but it will! There are three cases here, sets with eq?, eqv?, and
equal?. Eq? sets, and to an extent eqv? sets, are designed to return a
value if the key is the actual value that was passed in.

So the key is an opaque value, and it doesn't really matter what it is,
because e.g. (memq x set) won't inspect what x is. X must actually *be*
the object that was inserted into the set; it doesn't matter what type
it is.

A similar argument applies to equal? maps/sets. If you inserted X into a
set, and call (member x set), then the call succeeds, as with eq? sets.

This only leaves the case in which you put X in, then construct a new Y
that should be equal? to X, and call (memq y set). Here's the kicker: if
X was constructed in elisp and contains a nil, and Y was constructed in
Scheme out of Scheme data and thus does not contain a nil, *they aren't
the same*. Not to Scheme anyway!

Of course elisp's equal? sets might operate differently, as I mentioned.

> Some object-oriented languages may overload an operation depending on
> whether a parameter is a boolean or a list.  I don't see how such code
> can deal with nil gracefully without being significantly rewritten.

Well, specifying on lists involves an O(N) calculation at method
dispatch time, so it's not a good idea; but with '() versus #f, GOOPS
can specify one is more specific than the other, but also provide a
protocol to override that default.

> Using your proposed intransitive equality predicates would handle many
> of the common cases properly, but not all of them.

I probably was unclear, but I've decided that intranstive equality is a
worse idea than (equal? '() nil) => #f. (For elisp though, (equalp '()
#f) => t, so equalp can be permissive and transitive.) I would suggest
making equal? in Scheme behave as eq? for booleans.

I don't think that deprecating nil is really an option, because some
nils really are lists and booleans. But I could be wrong on this point,
as on many others!

(More thoughts? :)

Andy
-- 
http://wingolog.org/

Re: guile and elisp

[Ludovic Courtès]

Hello Guilemacsers!  :-)

Not sure about the fine technical points, but I think the general
philosophy should consider these points:

  - There’s currently no Scheme code that interacts with Elisp.  Thus,
    code that will be written specifically to interact with Elisp code
    can adjust to do the right thing, e.g., make explicit calls to
    ‘canonicalize-boolean’, etc., as Mark suggested.

  - Scheme’s #f/() are more expressive that elisp’s nil.  They can be
    easily mapped to nil, whereas it seems hard to automatically choose
    whether to map nil to #f or to ().  This also supports the idea of
    requiring Scheme code to make explicit conversions.

  - Elisp should be considered “legacy”.  Whenever something can’t be
    made transparent, I’d consider Scheme first-class and Elisp
    second-class.

Thanks,
Ludo’.

Re: guile and elisp

[Andy Wingo]

Hi!

On Mon 29 Mar 2010 10:42, ludo@gnu.org (Ludovic Courtès) writes:

>   - There’s currently no Scheme code that interacts with Elisp.  Thus,
>     code that will be written specifically to interact with Elisp code
>     can adjust to do the right thing, e.g., make explicit calls to
>     ‘canonicalize-boolean’, etc., as Mark suggested.

This is certainly an option on the table. However it would be nice if we
could avoid it, if Scheme code were "nil-safe" by default.

>   - Scheme’s #f/() are more expressive that elisp’s nil.  They can be
>     easily mapped to nil, whereas it seems hard to automatically choose
>     whether to map nil to #f or to ().  This also supports the idea of
>     requiring Scheme code to make explicit conversions.

Sure, though it's easy to map all three values to "not", "null?", and
"boolean?", in those predicates' incarnations in both languages. For
that reason I think we can avoid conversion of values.

>   - Elisp should be considered “legacy”.  Whenever something can’t be
>     made transparent, I’d consider Scheme first-class and Elisp
>     second-class.

Hoo, that's a really broad definition of legacy. Even if all elisp
hackers were to stop hacking elisp today, we'd probably still have elisp
code 10 years from now. Hopefully we don't have to make a
"first-class"/"second-class" distinction, besides the obvious one that
Scheme is first-class to Scheme, and Elisp to Elisp, and so on.

Cheers,

Andy
-- 
http://wingolog.org/

Re: guile and elisp

[Ludovic Courtès]

Hello!

Andy Wingo <wingo@pobox.com> writes:

> On Mon 29 Mar 2010 10:42, ludo@gnu.org (Ludovic Courtès) writes:

[...]

>>   - Scheme’s #f/() are more expressive that elisp’s nil.  They can be
>>     easily mapped to nil, whereas it seems hard to automatically choose
>>     whether to map nil to #f or to ().  This also supports the idea of
>>     requiring Scheme code to make explicit conversions.
>
> Sure, though it's easy to map all three values to "not", "null?", and
> "boolean?", in those predicates' incarnations in both languages. For
> that reason I think we can avoid conversion of values.

Well, yes, conversions can be avoided in many but not all situations, as
the corner cases you described illustrate (notably equality predicates
and hash functions).  Maybe it’s a good middle ground, though.  I’m
wondering to what extent such a semi-transparent solution could
“surprise” programmers.

>>   - Elisp should be considered “legacy”.  Whenever something can’t be
>>     made transparent, I’d consider Scheme first-class and Elisp
>>     second-class.
>
> Hoo, that's a really broad definition of legacy.

Yes.  :-)

> Even if all elisp hackers were to stop hacking elisp today, we'd
> probably still have elisp code 10 years from now. Hopefully we don't
> have to make a "first-class"/"second-class" distinction, besides the
> obvious one that Scheme is first-class to Scheme, and Elisp to Elisp,
> and so on.

Sure.

What I meant is that Scheme’s disjoint boolean type should be considered
the Right Thing.  I’d rather keep it really disjoint, at the cost of
weaker/less trivial interop, than going the elisp road too far.

Thanks,
Ludo’.

Re: guile and elisp

[Grant Rettke]

On Mon, Mar 29, 2010 at 7:01 AM, Ludovic Courtès <ludo@gnu.org> wrote:
> What I meant is that Scheme’s disjoint boolean type should be considered
> the Right Thing.  I’d rather keep it really disjoint, at the cost of
> weaker/less trivial interop, than going the elisp road too far.

Are you guys discussing something like a foreign function interface
for Scheme to Elisp and vice versa?

Sorry for the dense question as from what I have read it started very
technical, and I am wondering what is the overarching vision.