Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uwm.edu!gem.mps.ohio-state.edu!ginosko!uunet!munnari.oz.au!cs.mu.oz.au!ok
From: ok@cs.mu.oz.au (Richard O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: logic programs -> procedural lang?
Summary: f
Keywords: Prolog, typing, compiler efficiency
Message-ID: <2367@munnari.oz.au>
Date: 10 Oct 89 02:57:44 GMT
References: <27335@shemp.CS.UCLA.EDU> <869@gamera.cs.utexas.edu> <979@skye.ed.ac.uk>
Sender: news@cs.mu.oz.au
Lines: 52

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