[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
scheme in prolog
A while back there was a discussion on the SCHEME newsgroup concerning
implementations of logic programming languages in Scheme. David Moon
wondered if anyone had implemented Prolog in Scheme. His query
stimulated me to give it a try. I wrote two interpreters for a subset
of Scheme, one with and one without continuation semantics. I'm happy
to share these with anyone who is interested.
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.
I could not find a way to represent environments which had what I
consider to be the neccessary features:
1 - unreferenced enviroments should be automatically GCed.
2 - looking up the value of a variable should be cheap and,
in particular, should not depend on the the number of values it
has received in the past.
3 - variable assignment should be cheap and, in particular should not
require copying abritrary portions of an environment.
4 - The interpreter should not require an infinite stack nor
should the host prolog be required to detect and optimize
for tail recursion.
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).
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.
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.