/*
Posted to comp.lang.prolog
Date: Sun, 5 Apr 87 01:42:37 EST
From: Tim Finin <t...@linc.cis.upenn.edu>
Subject: Scheme
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.
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: t_l: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.
-- Tim
-----------------------------------------------------------------
-----------------------------------------------------------------
To: tim@linc.cis.upenn.edu (Tim Finin)
Subject: scheme in prolog
From: mike%acorn@oak.lcs.mit.edu
Date: Tue ,7 Apr 87 20:38:00 EDT
Cc: scheme@mc.lcs.mit.edu, prolog-request@sushi.stanford.edu
Reply-to: 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: t_l: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
-----------------------------------------------------------------
-----------------------------------------------------------------
To: mike%acorn@LIVE-OAK.LCS.MIT.EDU
Subject: Re: scheme in prolog
From: Kahn.pa@Xerox.COM
Date: Wed ,8 Apr 87 13:20:31 EDT
Cc: scheme@mc.lcs.mit.edu, prolog-request@sushi.stanford.edu
In-reply-to: "mike%acorn@LIVE-OAK.LCS.MIT.EDU's message of Tue, 7 Apr 87 19:38:00 EST"
Tim Finin says "It is very difficult to implement an efficient
interpreter for a language which has side-effects in prolog," while mike
beckerle says "No more difficult, I think, than interpreting a language
with side-effects in a language without side effects."
Notice that Tim says "efficient" and mike doesn't. I think that much of
the argument hinges on this point. Just to muddy the waters I want to
bring up a paper in the 2nd international logic programming conference
(1984) called "Mutable arrays in Prolog" (or some such). The paper
essentially presents a naive implementation of arrays in Pure Prolog
where every write copies and a read entails a linear search. It then
goes on to describe a primitive implementation of the predicates for
creating and accessing arrays. The primitive implementation in some
cases actually had the same computational complexity as array primitives
in conventional languages. Is there any specification of Prolog which
would rule out a compiler that did such optimizations?
The point is that something is wrong with the question of whether one
language can EFFICIENTLY implement another. One can ask whether a
particular implementation of a language can efficiently implement
another. A more interesting question I think is whether one language
can EASILY and NATURALLY implement another.
- ken kahn
References
mike%acorn@LIVE-OAK.LCS.MIT.EDU's message of Tue, 7 Apr 87 19:38:00 EST
-- scheme in prolog
-----------------------------------------------------------------
-----------------------------------------------------------------
To: scheme@mc.lcs.mit.edu, prolog-request@sushi.stanford.edu
Subject: Re: scheme in prolog
From: Paul Hudak <hudak-paul@YALE.ARPA>
Date: Wed ,8 Apr 87 17:17:56 EDT
Cc: mike%acorn@oak.lcs.mit.edu, tim@linc.cis.upenn.edu, Kahn.pa@Xerox.COM
Full-name: Paul Hudak
I was about to respond to the Tim Finin / Mike Beckerle discussion
in much the same way that Ken Kahn did, so I won't bother now, except
to point out that the efficiency issue, in particular the "aggregate
update" or "copy avoidance" issue, has also been addressed by the
functional programming community. This includes work in
semantics-directed compilation as well as more general work by Alan
Mycroft (in his dissertation), David Schmidt (see a recent TOPLAS
paper about detecting "singlethreaded stores") and me (see POPL 85,
Lisp and FP 86).
The nice thing about doing all this in the functional programming
paradigm is that the implementation of an interpreter for a language
looks VERY MUCH (if not identical) to the formal semantics of the
language. At Yale we have been experimenting a bit with such "truly
direct" semantics-directed compilation/interpretation with very
encouraging results. Thus, assuming one believes in denotational
semantics (and I realize that some people don't...), then the answer
to Ken Kahn's question:
A more interesting question I think is whether one language
can EASILY and NATURALLY implement another.
would have to be in the affirmative.
-Paul Hudak
-----------------------------------------------------------------
-----------------------------------------------------------------
To: Kahn.pa@xerox.com, mike%acorn@live-oak.lcs.mit.edu, hudak-paul@yale-arpa
Subject: scheme in prolog
From: tim@linc.cis.upenn.edu (Tim Finin)
Date: Wed ,8 Apr 87 23:31:29 EDT
Cc: scheme@mc.lcs.mit.edu, prolog-request@sushi.stanford.edu
Posted-date: Wed, 8 Apr 87 23:31:29 AST
The points that Ken, Mike and Paul make are quite valid and very
interesting. Implementing an interpreter for a language with side
effects in a language without them is bit of a problem and leads to
some known tradeoffs. The mutable array example is a case in point.
However, Prolog, as opposed to a purer and more abstact logic
programming language does have side effects. One is free, if one
chooses, to dynamically assert and retract clauses in the database. I
was, in general, pleased with the way my scheme-in-prolog interpreter
turned out, except when it came to implementing SET!. I was surprised
that Prolog's side-effecting operations did not enable handle this in
what I considered a good way.
Tim
-----------------------------------------------------------------
-----------------------------------------------------------------
-----------------------------------------------------------------
-----------------------------------------------------------------
-----------------------------------------------------------------
-----------------------------------------------------------------
SIP, Tim Finin (tim@cis.upenn.edu), University of Pennsylvania, April 1987.
SIP (Scheme in Prolog) is a partial interpreter for a subset of
Scheme. There are two versions: one with (sip2) and one without
(sip1) continuation semantics. The relevant files are:
sip1 - interpreter w/o continuations.
sip2 - interpreter with continuations
sipcore - base file for both, defines primitive variables, etc.
siptest - examples
Start SIP by loading either "sip1" or "sip2" and issuing the query:
?- sip.
This should create an initial environment (by loading the file
"sipcore") and then enter a read-eval-print loop. You can re-start the
read-eval-print loop w/o recreating the initial environment by issuing
the prolog query:
?- sipREP.
A few notes:
The bad news: the syntax is unLispy, due to the prolog reader. Instead
of (foo a 1) you must say foo(a,1). Look at the file "siptest" to see
some samples of simple expressions. Similarly, you must type a "."
after every input. The usual prolog special characters (e.g.
operators) may cause the reader to complain. There is no way to call
a function with no arguments! The good news: infix operators are
allowed, to some degree. In particular "S == E" means (define S E).
More syntax kludges: Cal a no-argument function FOO like [FOO]. Call
a lambda-form like: [lambda([n],n+2),3]. BEGIN only takes two
arguments - you can embed them, of course.
evaling prolog(P) invokes prolog on query P and returns #!t if it
succeeded and #!F otherwise.
The character '`' acts like '`' in normal Scheme in that it quotes the
next expression in the input.
evaling prolog('`' abort) is the (dirty) way to exit the read-eval-print
loop. In fact, evaling prolog('`' abort) is the only way to exit the
read-eval-print loop.
Just to make my job easier, I added a macro like facility. Evaling S1
==> S2 defines a rewriting type macro that transforms S1 into S2. For
example, we could (and do) do:
tail(X) ==> force(cdr(X)).
*/
:-module(moo_ext_scheme_sip,[proccessInSip/1,eval/1,sip/0,ssip/0]).
%:-ensure_loaded(moo_ext_lisp_triska).
%% SIPC - Scheme In Prolog with Continuation Semantics
%% a simple implementation of Scheme in Prolog (w. continuation semantics)
%% Tim Finin, University of Pennsylvania, Mon Oct 6 10:11:18 1986
%% note: in order to handle side effects in a reasonable way,
%% environments are stored in the database. The result is that old
%% environments never die. They don't even fade away!
% operators
:- set_prolog_flag(backquoted_string,false).
:- dynamic(((( ==> ))/2)).
:- op( 900,xfy, user:(==>)). % used for macros.
:- op(1100,xfx, (==)).
:- op(200,fx,'`'). % '`'(x) = quote(x).
:- thread_local(t_l:bound/3).
:- use_module(library(sexpr_reader)).
% sip - creates a virgin initial environment and enters a
% read-eval-print loop for SIP. Exit by typing "prolog('`' abort)."
:- meta_predicate moo_ext_scheme_sip:sip_when(0,0).
% :- meta_predicate moo_ext_scheme_sip:goal_truth(0,*,*,*).
:- meta_predicate moo_ext_scheme_sip:applyPrim(*,*,0).
sip :- create0Env, sipREP.
ssip :- create0Env, ssipREP.
% sipREP - enters a read-eval-print loop for SIP.
sipREP :-
repeat,
writeln('SIP> '),
sip_read(curent_input,E),
once(eval3(print(E),0,k(nil))),
fail.
sip_read(In,P):- lisp_read(In,E),sexpr_sterm_to_pterm(E,P).
% sipREP - enters a read-eval-print loop for SSIP.
ssipREP :-
repeat,
writeln('SSIP> '),
%readCycL(E),
read(E),
once(eval3(print(E),0,k(nil))),
fail.
% create0Env sets up E as the inital Scheme environment.
create0Env :-
% flush all old environments.
retractall(t_l:bound(_,_,_)),
% (re)set the environment counter.
%abolish(envNum,1),
%assert(envNum(1)),
flag(envNum,_,1),
% define the initial variables.
load('sipcore.pl').
% abbreviations for eval/3.
eval(E) :- eval3(E,0,k(nil)),!.
eval(E,_V) :- eval3(E,0,k(nil)),!.
eval(E,Env,C) :- eval3(E,Env,C),!.
sip_when(Test,Then) :- Test->Then;true.
% like eval3, but "returns" its value to caller.
evalReturn(Exp,Env,Val) :- eval3(Exp,Env,k(return(Val))).
% eval3(expression,environment,continuation)
eval3(X,_,C) :- number(X),applyC(C,X).
eval3(X,E,C) :- atomic(X),!,lookUp(X,V,E),applyC(C,V).
% syntax kludge - call a fn F of no arguments as [F].
% bug - doen't check for special forms!!!
eval3([F|Args],_E,C) :- !,eval3(F,Env,k(evalArgs(Args,[]),Env,C)).
% special forms ...
eval3(quote(E),_,C) :- !,applyC(C,E).
eval3(lambda(Vars,Body),E,C) :- !, applyC(C,closure(Vars,Body,E)).
eval3(set(Sym,Val),E,C) :- !, eval3(Val,E,k(set(Sym),E,C)).
eval3(define(Sym,Exp),Env,C) :- !, eval3(Exp,Env,k(define(Sym),Env,C)).
eval3(if(E1,E2,E3),Env,C) :- !, eval3(E1,Env,k(if(E2,E3),Env,C)).
eval3(and(X,Y),Env,C) :- !, eval3(X,Env,k(and(Y),Env,C)).
eval3(or(X,Y),Env,C) :- !, eval3(X,Env,k(or(Y),Env,C)).
eval3(delay(X),Env,C) :- applyC(C,promise(X,Env,_)).
eval3(F1==>F2,_,C) :- !, assert(F1==>F2), applyC(C,F2).
% this should be done via apply.
eval3(eval(X),Env,C) :- !, eval3(X,Env,k(eval,Env,C)).
% check for a "macro" application.
eval3(X,E,C) :- (X==>NewX), !, eval3(NewX,E,C).
% non-special form...
eval3(E,Env,C) :-
!,
E =.. [F|Args],
eval3(F,Env,k(evalArgs(Args,[]),Env,C)).
% applyC(continuation,value) ...
% a continuation has one of the forms:
% k(operation,expression,next continuation)
% k(nil)
% k(return(Value))
applyC(k(if(_Then,Else),E,C),false) :- !,eval3(Else,E,C).
applyC(k(if(Then,_Else),E,C),_) :- eval3(Then,E,C).
applyC(k(set(Sym),E,C),V) :- set(Sym,V,E,OldV),applyC(C,OldV).
applyC(k(define(Sym),E,C),V) :- define(Sym,V,E),applyC(C,Sym).
applyC(k(and(X),E,C),V) :- V=false->applyC(C,false);eval3(X,E,C).
applyC(k(or(X),E,C),V) :- V=false->eval3(X,E,C);applyC(C,V).
applyC(k(eval,E,C),V) :- eval3(V,E,C).
applyC(k(evalArgs([In1|InRest],Out),E,C),V) :-
eval3(In1,E,k(evalArgs(InRest,[V|Out]),E,C)).
applyC(k(evalArgs([],RCall),_E,C),V) :-
reverse([V|RCall],Call),
Call = [F|Args],
apply(F,Args,C).
% we're done
applyC(k(return(V)),V) :- !.
applyC(k(nil),_V) :- !.
% apply(Function,Args,COntinuation) - apply a prmitive function.
apply(pf(callCC),[F],C) :- !, apply(F,[C],C).
apply(pf(X),Args,C) :-
!,
applyPrim(X,Args,V),
applyC(C,V).
% apply a compound function.
apply(closure(Parameters,Body,Env),Args,C) :- !,
makeEnv(Parameters,Args,New/Env),
eval3(Body,New/Env,C),
!.
% this should never happen.
apply(X,Args,_) :- err('I dont know how to apply:', [X|Args]).
% applyPrim(function,arguments,value)
applyPrim('+',[A1,A2],V) :- V is A1+A2.
applyPrim('-',[A1,A2],V) :- V is A1-A2.
applyPrim('*',[A1,A2],V) :- V is A1*A2.
applyPrim('=',[A1,A2],V) :- A1=A2->V=true;V=false.
applyPrim(cons,[A1,A2],[A1|A2]).
applyPrim(car,[LIST],H):-LIST=[H|_]->true;H=[].
applyPrim(cdr,[LIST],T):-LIST=[_|T]->true;T=[].
applyPrim(begin,[_A1,A2],A2).
applyPrim(force,[promise(B,E,V)],V) :- var(V)->evalReturn(B,E,V);true.
applyPrim(load,[File],File) :- !,load(File).
applyPrim(prolog,[X],V) :- !,call(X) -> V=X;V=false.
applyPrim(print,[X],true) :- !,writeln(X).
applyPrim(F,Args,error) :-
Call =.. [F|Args],
err('bad call to a primitive function',Call).
% makeEnv(+Parameters,+Arguments,-Environment) - creates a new environment
% in which the variables in the 1st arg are t_l:bound to the values in the
% 2nd. The new envitronment is returned in the 3rd.
makeEnv(Ps,As,New/Old) :-
% determine the next environment number to use.
retract(envNum(N)),
New is N+1,
assert(envNum(New)),
!,
% add the binding to the new environment.
addBindings(Ps,As,New/Old).
% addBindings(Variables,Values,Environment) binds variables to
% corresponding values in the specified Environment.
addBindings([],[],_) :- !.
addBindings([P|Ps],[V|Vs],Env) :-
!,
define(P,V,Env),
addBindings(Ps,Vs,Env).
addBindings([_|_],[],_) :- !, err('too few arguments').
addBindings([],[_|_],_) :- !, err('too many arguments').
% looks up the values associated with a symbol in an environment. It's
% an error if there is no binding.
lookUp(Symbol,Value,Env) :- value(Symbol,Value,Env,_),!.
lookUp(S,_,Env) :- trace, err('unbound symbol: ',S/Env).
% value(+symbol,-value,+frameSought,-frameFound) like lookUp but also
% returns the frame in which the variable was t_l:bound.
value(S,V,Env,Env) :- t_l:bound(S,V,Env).
value(S,V,E1/E2,E) :-
\+ (t_l:bound(S,V,E1/E2)),
value(S,V,E2,E).
% change the value associated with symbol S to V, returning the old value.
set(S,V,Env,OldV) :-
value(S,OldV,Env,BindingEnv),
!,
retract(t_l:bound(S,OldV,BindingEnv)),
assert(t_l:bound(S,V,BindingEnv)).
set(S,_,E,_) :- err('symbol not bound in environment:',(S/E)).
% add an initial binding for symbol S to value V in environment Env.
define(S,V,Env) :-
sip_when(retract(t_l:bound(S,_,Env)),
warn('symbol already defined in environment: ',(S,Env))),
assert(t_l:bound(S,V,Env)).
% load(F) reads and evals all expressions in file F.
load(File):- see(File),
repeat,
call_cleanup((read(X), ((X = end_if_file ) -> true;((once(loadProcess(X)),fail)))),seen),!.
:-thread_local(schemePExpansion/1).
loadProcess(end_of_file):- ignore(retract(schemePExpansion)),!.
loadProcess(X) :- eval(X).
%%% misc. utilities ...
err(Msg) :- warn(Msg),!,fail.
err(Msg1,Msg2) :- warn(Msg1,Msg2),!,fail.
warn(Msg) :- writeln(Msg).
warn(Msg1,Msg2) :-writeln(Msg1),write(' '),write(Msg2).
proccessInSip(H):- \+ compound(H),!,fail.
proccessInSip(M:H):-atom(M),!,proccessInSip(H).
proccessInSip(H):-functor(H,==,2).
proccessInSip(H):-functor(H,==>,2).
term_exp_process((H:-B),S):-B==true,!, term_exp_process(H,S).
term_exp_process(H,H):- proccessInSip(H),!,ignore(loadProcess(H)).
%% [tim.prolog]SIPCORE,
%% Tim Finin, University of Pennsylvania, Mon Oct 27 10:40:00 1986
%% this file specifies the initial environment for SIP.
user:term_expansion( T ,evaluated_term(S)):- source_location(F,_), schemePExpansion(F),term_exp_process(T,S).
user:goal_expansion( T ,eval(T)):- source_location(F,_),schemePExpansion(F),proccessInSip(T),!.
:- source_location(F,_),asserta(schemePExpansion(F)).
% PRIMITIVE "MACROS"
(X==Y) ==> define(X,Y).
'`'(X) ==> quote(X).
consStream(X,Y) ==> cons(X,delay(Y)).
head(X) ==> car(X).
tail(X) ==> force(cdr(X)).
theEmptyStream ==> nil.
'emptyStream?' ==> 'null?'.
%% PRIMITIVE VARIABLES.
:-eval((true == quote(true))).
false == quote(false).
nil == quote([]).
% :-debug.
%% PRIMITIVE FUNCTIONS
:-eval((car == '`'(pf(car)))).
:-eval((cdr == '`'(pf(cdr)))).
cons == '`' pf(cons).
'eq?' == '`' pf(=).
'=' == '`' pf('=').
('+') == '`' pf('+').
('-') == '`' pf('-').
'*' == '`' pf('*').
'/' == '`' pf('/').
begin == '`' pf(begin).
force == '`' pf(force).
load == '`' pf(load).
==> == '`' pf(==>).
prolog == '`' pf(prolog).
print == '`' pf(print).
callCC == '`' pf(callCC).
null == lambda([x], 'eq?'(x,nil)).
end_of_file. % <-- why mankind will always dominate machines?
% once(X) executes X only once.
once(X) :- X,!.
writeln(X) :- nl,write(X).
append([],X,X).
append([U|L],X,[U|M]) :- append(L,X,M).
reverse([],[]).
reverse([Head|Tail],L) :-
reverse(Tail,TailReversed),
append(TailReversed,[Head],L).
%% [tim.prolog]siptest.
%% Tim Finin, University of Pennsylvania, Mon Oct 27 10:39:27 1986
%% this file contains samples for SIP.
fact == lambda([n], if(=(n,0),1,n*fact(sub1(n)))).
add1 == lambda([n], n+1).
sub1 == lambda([n], n-1).
% higher order functions
mapcar ==
lambda([f,l],
if(null(l),
nil,
cons(f(car(l)),mapcar(f,cdr(l))))).
% simple list manipulation functions.
length == lambda([l], if(null(l),0,add1(length(cdr(l))))).
append == lambda([l1,l2],if(null(l1),l2,cons(car(l1),append(cdr(l1),l2)))).
reverse ==
lambda([l],
if(null(l),
l,
append(reverse(cdr(l)),(cons(car(l),nil))))).
% stuff for streams.
filter ==
lambda([f,s],
if('emptyStream?'(s),
s,
if(f(head(s)),
consStream(head(s),filter(f,tail(s))),
filter(f,tail(s))))).
from == lambda([n],consStream(n,from(n+1))).
nthStream == lambda([s,n],if(n=1,head(s),nthStream(tail(s),n-1))).
integers == from(1).
% environments
makeCounter ==
lambda([],
begin(counter == 0,
lambda([],set(counter,1+counter)))).
:- source_location(F,_),retract(schemePExpansion(F)).