Path: utzoo!mnetor!uunet!mcvax!ukc!its63b!aiva!jeff
From: jeff@aiva.ed.ac.uk (Jeff Dalton)
Newsgroups: comp.lang.prolog
Subject: Re: compatibility/elegance & *theory*
Message-ID: <385@aiva.ed.ac.uk>
Date: 28 Apr 88 13:47:00 GMT
References: <136@vor.esosun.UUCP> <841@cresswell.quintus.UUCP> <365@aiva.ed.ac.uk> <903@cresswell.quintus.UUCP>
Reply-To: jeff@uk.ac.ed.aiva (Jeff Dalton)
Organization: Dept. of AI, Univ. of Edinburgh, UK
Lines: 88


In article <365@aiva.ed.ac.uk>, jeff@aiva.ed.ac.uk (Jeff Dalton) writes:
- It's interesting that call/1 in Prolog is basically an EVAL, while
- Lisp has EVAL but also a less troublesome notion in APPLY.  

In article <903@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A.
O'Keefe) writes:
> Actually, call/1 in Prolog is a pretty straightforward APPLY.  (There is
> a family of call/N things each adding N-1 extra arguments.)  The problem
> is that ','/2 and so on are FEXPRs.  (Is everyone nicely confused now?)

I don't think I'm confused (yet).  You're saying call/1 is a normal
procedure byt ','/2 and friends are not.  So call/1, in itself,
is like APPLY, but you can apply things like ','/2, which actually
implement any unusual behavior.

> The point is that call(','(write(a)), write(b)) ends up calling write(a)
> and write(b), not because call/2 does anything special, but because (A,B)
> calls A and B.  It is as if you did
>	(APPLY #'(LAMBDA (X Y) (AND (EVAL X) (EVAL Y)))
>	    '(PRINT 'a) '(PRINT 'b) '())
> in Lisp.

I could put my point like this: in the Lisp "as if" you end up having
to call EVAL in order to convert "source code representations" to code.
Without EVAL, you couldn't make that kind of conversion.  (There might
be other ways, such as COMPILE in Common Lisp, but the basic point
still holds.  Note too that CL's APPLY does make such conversions,
but Scheme's doesn't.  Nor can Scheme apply fexprs.)

The difference between Prolog and Lisp is that in Prolog just saying

     call(X).

takes some "source code representation" (the value of X) and
interprets it as code while in Scheme-like Lisps

     (apply f ...)

doesn't.  The value of F is a procedure, not the name of one.  That
is why call/1 makes problems for Prolog module systems (you have a
procedure name whose reference has not yet been resolved with respect
to modules) while APPLY doesn't make analogous problems in Lisp.
(Actually, there are other factors involved as well; and some Prolog
module proposals get around the problem one way or another, but
anyway...)

In article <841@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. 
O'Keefe) writes:
+ Yes, it *is* theoretically impossible to write a correct automatic
+ conversion program from Lisp to assembler.  You have to have an
+ interpreter as well.  Why?  Because you can construct code on the fly
+ and execute it.

Bear in mind the "construct code on the fly and execute it".  This is
just what's difficult in Scheme.  To do it, you need something like
EVAL (or LOAD, it turns out).  APPLY won't do *unless* you think in
terms of Common Lisp's "auto-coercion" idea of APPLY, where you can
say (APPLY (CONS 'LAMBDA ...) ...).  That won't work in (R3RS) Scheme.

+ Unfortunately, because Lisp has EVAL and Prolog has call/1, whether a
+ particular instance of some term will be called or used as data is not
+ a simple syntactic property.  It's at least as hard as solving the
+ halting problem.  (In fact, a term may be used as BOTH code and data.)

- Scheme (which is after all a dialect of Lisp) doesn't have EVAL in
- the R3 Scheme Report in part because they want to prevent arbitrary
- data being turned into code. 

So, while EVAL and call/1 bring in the problem of whether or not
some term will be called, APPLY needn't do so.

Something trivial...

- I take your point, Richard, but it's worth pointing out that you don't
- need an interpreter per se: you can just keep the translator around.

> I regard keeping the translator around as just another way of 
> implementing an interpreter.  The point is that you need a
> non-trivial chunk of code which in some sense defines the
> semantics of the _OLD_ language.

We're not disagreeing.  I said I took your point, and by the "per se"
I meant to indicate that I meant an interpreter in a narrow sense.

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