Re: compatibility/elegance & *theory*

[mcvax!ukc!its63b!aiva!jeff@uunet.uu.net (Jeff Dalton)]

The frist 4 paragraphs or so are a review of the story so far...

The original question was whether it is possible to write a correct
(and complete) automatic conversion program from Prolog (or Lisp) to
assembler.  It was pointed out (by OK and perhaps others) that this
was not possible because call/1 (in Prolog) or EVAL (in Lisp) could
use arbitrary data ("source code representations") as code and so
would require that the "conversion" include an interpreter for the
language -- the conversion wouldn't be complete for further
conversions might be required.

I then suggested that Lisp's APPLY was less troublesome in this regard
that call/1 or EVAL because it just called a function (which is a kind
of data objetc in Lisp) rather than process some source representation
that might turn out to do anything whatsoever.

Richard replied that call/1 was just APPLY, not EVAL.

[Aside: it isn't always implemented that way.  Sometimes call/1 is
an interpreter rather than having the "interpretation" put off into
"fexprs" such as ','/2.]

I replied that call/1 takes (and in Prolog must take) the name of a
procedure while APPLY can take the actual procedure and that this
causes problems for some kinds of Prolog module systems.  It turns
out that this name vs. procedure point isn't quite the right one
though: see below.

In article <922@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes:
>There are two differences between EVAL and APPLY
>(1) EVAL evaluates the arguments of its argument, APPLY does not.
>    In this respect, call/1 resembles APPLY, not EVAL.  call/1 as such
>    does not do any interpretation other than to locate the predicate
>    which is to be called.
>(2) EVAL is given (a form in which there occurs) the _name_ of a function,
>    not the function itself, APPLY is given a function pointer/closure &c.
>    In this respect call/1 resembles EVAL, not APPLY.  There is no Prolog
>    object which "directly" represents a predicate.
>
>I have always regarded the essential feature of EVAL as being (1), and
>have regarded (2) as a detail of implementation, so I understood "is
>basically an EVAL" to mean "is like an interpreter which is responsible
>for evaluating sub-forms".  That is what is false.

The question of whether APPLY accepts procedures or (also) procedure
names is one of the key differences between Scheme and other Lisps
such as Franz and CL.  It is one way in which Scheme makes a clearer
distinction between procedures and source representations.

By saying call/1 is basically an EVAL, I meant that it brings in the
problems that EVAL does while APPLY does not.  One of these problems
is that procedure names can be passed around rather than procedures.
Then you may have do decide at call time which module to dereference
the name in unless (as in Common Lisp packages) the module information
is part of the name.  So this is a problem.  But it's not the right
problem, or at least not all of it.

The right problem is that EVAL means you can never completely
translate Lisp without supplying an EVAL on the object side too.
Call/1 shares this problem.

APPLY, defined as in Scheme, does not because
  (a) You can call procedures but not, say, lists like (LAMBDA (X) ...).
      So you can't build an arbitrary expression as a list and then
      call APPLY to get that list evaluated.
  (b) You can't call fexprs, only functions of the normal sort.
      So you can't say

        (apply if '(t <arbitrary expression as a list>))

      Richard's explanation of call/1 shows that it can do this.

>Jeff Dalton is quite right about (2), and as he points out, you _do_
>have to work a bit to make a module system and call/1 work together.

By the way, Richard, are you still opposed to the so-called atom-based
module schemes?  I suppose it should be a separate topic...

>If Prolog were typed, with the void/N type constructor as Alan
>Mycroft suggested, it would be possible to have a version of call/1
>which resembled APPLY in both respects.

Tell me more.

Jeff Dalton,                      JANET: J.Dalton@uk.ac.ed             
AI Applications Institute,        ARPA:  J.Dalton%uk.ac.ed@nss.cs.ucl.ac.uk
Edinburgh University.             UUCP:  ...!ukc!ed.ac.uk!J.Dalton