🚀 go-pugleaf

> In article <2181@munnari.oz.au> ok@cs.mu.oz.au I claimed that
> (defun app (A Z) (if (endp A) Z (cons (car A) (app (cdr A) Z))))    
would check three times that A is a list.

In article <979@skye.ed.ac.uk>, jeff@aiai.ed.ac.uk (Jeff Dalton) writes:
> Richard, I've seen this claim before (in Warren's paper, for example),
> and I've always been a bit puzzled by it.

Why be puzzled by it?  David Warren and I were both used to Lisp systems
(in my case Interlisp-D) that do in fact make the check that many times.
Admittedly, Interlisp-D does the check in microcode, but then the Prolog
equivalent is in microcode on the Xerox Lisp machines too.  People at
RMIT in Melbourne use Common Lisp on MacIvory, and I would be surprised
if that Lisp system didn't repeat the check three times as part of the
three instructions involved.  The Lisp system I use here from time to
time definitely has the check repeated in CAR and CDR -- I just checked.
(ok, ok, so it's a Scheme, not a Lisp, big deal.)

> I would expect compiled Lisp code to make only one check, not three.

I'll get back to this shortly.

> However, in many Lisps there's only one check because the compiled
> code for a car or cdr never includes a check.  It's fair to flame Lisp,
> or at least some Lisp implementations, for being less safe.

Now that is a serious mistake.  Consider those broken Lisp implementations
(but not the ones I've used or the one David Warren used) duly flamed.

> But I don't think it's fair to say Lisp makes three checks,
> because it doesn't.

It _was_ fair for me to say that, because every Lisp I'd personally checked
DOES make the three checks.

Back to the question of what compiled Lisp code would do.  A good Lisp
compiler would exploit any type information it could pick up along the way.
Now (endp A) succeeds if A is NIL, fails if A is a CONS, and is supposed to
signal an error otherwise, so when we have (if (endp A) #|foo|# #|baz|#)
a smart compiler would know in #|foo|# that A was NIL and it would know in
#|baz|# that A was a CONS, so when it saw (car A) and (cdr A) it would know
that it didn't need to repeat the checks.  My own good habit of using (endp -)
rather than (null -) defeated my own argument here!  However, if I had
written (if (null A) #|foo|# #|baz|#) then the compiler would only have
been entitled to rely on A being different from NIL in the #|baz|# branch,
so the (car A) would have to perform the check, and the (cdr A) would then
be able to omit it.
					  "
So what I *should* have said is that "a naive Lisp compiler which makes
the checks which are necessary for safety will do more checking than a
  "
naive Prolog compiler which makes the checks which are necessary for safety".