Re: [Kawa-commonlisp-dev] Switching to Guile's #nil

[Per Bothner]

On 06/18/2013 08:18 AM, John Cowan wrote:
> (Note:  In this post, by "Lisp" I mean Common Lisp or Elisp or ISLisp
> or any other traditional Lisp, but not Scheme.)
>
> FWIU, in Kawa the the Scheme equivalent of Lisp's NIL is the empty list.
> I wanted to explore the possibility of adopting Guile's convention of
> using a separate object notated #nil in Scheme.

We're concerned with multiple dimensions of "compatibility":

Interoperability with standards and other implementations:
I1a: Kawa-Scheme and "standard" Scheme (RnRS, IEEE, other Schemes).
I1b: Kawa-Lisp and "standard" Lisp (Common Lisp standard, etc).

Interoperability with Java:
I2a: Kawa-Scheme and Java.
I2b: Kawa-Lisp and Java.
This is the reason I switched Kawa-Scheme so that immutable
Scheme strings are java.lang.String instances.

Interoperability with other Kawa languages.
I3: Kawa-Scheme and Kawa-Lisp (and Kawa-XQuery ...).

I suspect that I1 and I2 are more important than I3.
However, I3 makes it easier for (say) a Kawa-Lisp user
(or language implementor) to re-use Kawa-Scheme code.

Nil is of course a nasty problem - there is no good
interoperability answer.  Currently, Kawa-Lisp uses
LList.Empty for nil.  My rationale was that if we need
to pass data between Scheme and Lisp, it is harder to
convert lists if we used a different representation of
the empty list, while "atoms" (symbols and booleans)
are easier to translate.  Of course this doesn't help
with lists (or vectors) that contains symbols or booleans.

I'm beginning to think that a Kawa-Lisp programmer
would prioritize interoperability with Java over
with Kawa-Scheme.  That suggests we use Java null
for Lisp nil.  But that still raises a number of questions.

Note Kawa-Scheme uses #!null for Java null, so I don't think
we need a #nil syntax (unless for Guile compatibility).

I'll assume #nil for Java null.

> The way #nil behaves is this:
>
> 1) In both Scheme and Lisp, it is false.
>
> 2) Both Scheme `null?` and Lisp `null` return true on it.
>
> 3) It is a symbol in Lisp but not in Scheme.
>
> The advantages of this is promoting interoprerability between predicates.
> As things stand, Scheme has to know that when it calls a Lisp predicate
> it may get the empty list back, and lisp has to know that when it calls a
> Scheme predicate it may get back some Scheme object that isn't even part
> of the Lisp system (the value of scheme:false, or something like that).
>
> The problem, of course, is the increased run-time cost.  In Guile, #t and
> #f and #nil are all immediates, so a simple mask test works.  In Kawa
> it would require two chained tests for both `null?` and (worse) truth
> value, unless something clever can be done with classes and `instanceof`
> (I don't know how slow that is).

(3) is easy - I agree #nil (java null) should be a symbol in Lisp
but not Scheme.  However, note we  need a "shadow symbol"
for nil that is gnu.mapping.Symbol.  This is used for property
lists, for example.

When it comes to (1), I'm concerned about complicating these tests -
it comes the byte bigger and slower.  Selfishly, it also makes
disassembled bytecode harder to read.

It is worth pointing out that Java allows multiple java.lang.Boolean
objects whose booleanValue is false, but Kawa only considers the
canonical Boolean bound to the static field java.lang.Boolean:FALSE
to be false.  This causes some strange behavior:

#|kawa:1|# (define b1 ::java.lang.Boolean (make java.lang.Boolean #f))
#|kawa:2|# b1
#f
#|kawa:3|# (b1:booleanValue)
#f
#|kawa:4|# (if b1 1 0)
1
#|kawa:6|# (if (b1:booleanValue) 1 0)
0

So perhaps we might re-think this.

One option is to change Scheme false value to be #!null.
I.e. (eq? #f #!null)
This can improve both performance and Java compatibility.
Testing against #!null is faster (and more compact) than
testing against java.lang.Boolean:FALSE.  Scheme traditionally
uses #f for missing or default values (similar to Common Lisp's
use of nil); this would be cheaper.  If a Scheme type ST is
implemented by a Java type JT, then the common case of (ST or #f)
still has the Java type JT, which is cleaner.

So this argues for changing the canonical false value to #!null
for both Scheme and Lisp.  If we allow non-canonical false
values, we should probably also consider as false all
java.lang.Boolean objects whose booleanValue is false:

public static final boolean isTrue(Object value) {
   return value != null
      && (! (value instanceof Boolean)
          || ((Boolean) value).booleanValue()));
}

This is clearly going to be slower and bloat the bytecode.
If we went this route, I think we'd want the Kawa compiler
to emit a call to the isTrue method, rather try to inline it.
(However, the JVM JIT could inline it.)

The cost of truth-checking is reduced when the Kawa compiler
can infer the type of a variable or expression to be
boolean (through type specifiers or date-flow).  In that case
the generated code uses a primitive (immediate) boolean, and
so we don't get the overhead of calling isTrue.

However, if we make the canonical false value be #!null,
then (2) above becomes difficult: We can't have (null? #f).

So I end up with two tempting options.  In both cases we have:
- Lisp nil is represented by Java null - aka Scheme #!null.
- Testing a value for truth uses the isTrue method above.
- Hence #!null is considered false in both Scheme and Kawa.

In addition:
Option 1:
- #!null becomes the canonical Scheme false value - i.e. (eq? #f #!null).
This has some advantages as mentioned above.
- Hence #!null cannot be recognized as end-of-list in Scheme.

Option 2:
- #!null is recognized as false, but not the canonical false value.
I.e. (not (eq? #f #!null)) but (if #!null 1 0) yields 0 (rather than
1 as is currently the case.

Sub-option 2a:
- #!null is the canonical end-of-list - i.e. (eq? #!null '()).

Sub-option 2b:
- #!null is handled as end-of-list, but not (eq? #!null '()).

Sub-option 2c:
- Don't change-end-of-list handling in Scheme.
I.e. (null? #!null) remains false.  This causes Lisp-Scheme
interoperability problems, so it doesn't seem a good long-term solution.

I'm not sure which of 2a or 2b would be better.  Both might be
a pain to implement - lots of changes lots of places.  At least
as a transition 2b seems easier.  Perhaps start by replacing
(xx == LList.Empty) by (LList.isEmpty(xx)) lots of places.
--
        --Per Bothner
address@hidden   http://per.bothner.com/