scheme in prolog

[mike%acorn@oak.lcs.mit.edu]

    Date: Sun, 5 Apr 87 01:42:37 EST
    From: tim@linc.cis.upenn.edu (Tim Finin)
    
    What I found most interesting about the exercise has more to do with
    Prolog than with Scheme - It is very difficult to implement an
    efficient interpreter for a language which has side-effects in prolog.

No more difficult, I think, than interpreting a language with
side-effects in a language without side effects. Consider writing a
scheme interpreter in Pure Scheme or in ML (not using the side
effects). In either case, the technique you end up using makes the
interpreter look alot like a denotational semantics (Pure Scheme or ML
case) or a Plotkin-Style operational semantics (Prolog Case).  

    I basically considered two alternatives for representing the environment:
    
      o represent an environment as a term which contains a sequence of
        variable-name/variable-value pairs.  This achieves (1) in most prologs
        but must give up on either (2) or (3).

      o represent an environment as a set of assertions in the clausal
        database of the form: bound(Symbol,Value,EnvironmentID).  This wins on
        (2) and (3) but loses on (1).

I think you should build an abstract data type for this rather than 
expecting terms and pattern matching or the interpreter to do it for you. 
The best you'll be able to do in prolog is a tree like representation,
requiring logarithmic access time and update time (as well as logarithmic
space for copying on updates.)    

lookup (X, Env, Value) :- ....given X find value V in environment E.

update (X, V, Env1, Env2) :- update X to value V in environment Env1 to get
				environment Env2.

    This makes me think that a side-effect predicate like RPLACARG
    (discussed in PROLOG-DIGEST about a year ago) is not such a bad idea.

Yup. The difficulty is that it is hard to use side effects in a language
with automatic control structures. You basically can't get the level
of operational control you need, but the declarative model also breaks down.
In any case I'd say RPLACARG will be infinitely MORE useful than 
assert and retract ever were. Consider for example the UPDATE predicate
above. This, written using RPLACARG would destructively update the environment
Env1 to make Env2, which is exactly what you need.

    It also reinforces the notion that Lisp is either a (i) more general
    or (ii) lower level language than Prolog, depending, of course, on
    your point of view.

Both I'd say. Prolog is a very high level language, and is less expressive
than languages with side effects. What I mean by expressive here is not
the usual formal definition, since Prolog is clearly complete in that
all computable functions can be computed, but rather a pragmatic 
view. Any language without side effects is restricted in that it
cannot describe changes of state over time without having representations
of those states separately.

Try writing code for hash-tables in prolog or pure scheme and you'll
see what I mean. Hashing (like most side effect oriented code) requires
side effects in its essence since it has to reason about whether buckets
in the table are in use "yet". They also lack any notion of EQ-ness
as in Lisp or Scheme for the same reason. 


...mike beckerle
Gold Hill Computers