/* NOTES: * Our "semantic language" is a variant of Prolog that does not support backtracking. This "limitation" makes it handy for describing the semantics of other languages. You don't have to write "cuts" all over the place, which makes programs much easier to write/understand than real Prolog. * We've built in support for guards on the left-hand side of the rules (like in Concurrent Prolog). These guards are written as boolean expressions in JavaScript, e.g., ev(S, Env, V), S instanceof Sym :- lookup(S, Env, V). So far we've only needed this kind of guard, but we may end up supporting the use of arbitrary predicates in guards. (But we should keep in mind that our language---and its implementation---should be kept as small as possible.) * The expression a:b:c:nil is shorthand for pair(a, pair(b, pair(c, nil))). There's nothing special about the "pair" clause, except that the language provides a special syntax for it. TODO: * Improve the syntax of the "semantic language". For example, it would be much nicer to write eval(X) = Y instead of the very Prologgy eval(X, Y) * Right now a rule can only have one guard; we will probably want to add support for multiple guards. * Provide an "is" clause as a way to access all of JS, e.g., add(X, Y, Z) :- is(`X+Y`, Z). Having access to the underlying "unfelicitous" language will make it easy for us to extend our lisp with proper support for numbers, strings, etc. * Think about in/out annotations; will they make implementation easier? */ include("Prolog_Library2") ometa PrologTranslator <: Parser { variable = spaces firstAndRest(`upper, `letterOrDigit):name -> new Var(name.join('')), symbol = spaces firstAndRest(`lower, `letterOrDigit):name -> new Sym(name.join('')), string = "`" (~'`' char)*:xs '`' -> xs.join(''), number = spaces digit+:ds -> parseInt(ds.join('')), pairs = expr:x ":" pairs:xs -> new Clause(new Sym('pair'), [x, xs]) | expr, head = symbol | variable, clause = head:hd "(" listOf(`pairs, ','):args ")" "=" pairs:arg -> new Clause(hd, args.concat(arg)) | head:hd "(" listOf(`pairs, ','):args ")" -> new Clause(hd, args), expr = clause | variable | symbol | number, clauses = listOf(#clause, ','), guard = "`" (~'`' char)+:xs '`' -> xs.join('') | clause, rule = clause:head "," guard:g ":-" clauses:body "." -> new Rule(head, body, g) | clause:head "." -> new Rule(head, []), rules = rule*:rs spaces end -> rs, query = clause:c spaces end -> c } PrologTranslator.answer = function(query, rules) { return solve(this.matchAll(query, "query"), this.matchAll(rules, "rules")) } /* #X for sym $X for list %X for num (_, :-, ...) (foo X = Y) :- (bar X = Y, baz X = Y) (_, when, _, :-, ...) (foo X = Y) when (bar X = Z, baz X = W) :- ... ev(cons(X, Y), Env) = cell(X1, Y1) :- ev(X, Env) = X1, ... if Cond then Tb else Fb -> [if, Cond, then, Tb, else, Fb] use ()s for grouping? if (x > y) then ... Syntax for Decomposing Terms ---------------------------- a(b, c) -> a:b:c:nil (a, b, c) -> a:b:c:nil ==> conclusion: clauses should probably be built out of pairs ==> should use my new ST-72-like syntax experiment! that would be much more flexible. What about "views", kinda? I could enable foo(bar, baz) to unify with foo:bar:baz:nil, which would make it possible for all kinds of interesting things to happen. But then I would also have to make, e.g., pair(A, pair(B, nil)) unify with A(B). (It must go both ways.) ev(Hd:Args, Env) = Hd:Args1 Syntactic Sugar for Lists ------------------------- [A, B, C] -> A:B:C:nil -> pair(A, pair(B, pair(C, nil))) [A, B, C | Rest] -> A:B:C:Rest -> pair(A, pair(B, pair(C, Rest))) [] -> nil -> nil */ lispRules = """ ev(cons(X, Y), Env) = cell(X1, Y1) :- ev(X, Env) = X1, ev(Y, Env) = Y1. ev(car(X), Env) = HeadX :- ev(X, Env) = cell(HeadX, TailX). ev(cdr(X), Env) = TailX :- ev(X, Env) = cell(HeadX, TailX). ev(quote(X), Env) = X. lookup(N, nil) = N. lookup(N, binding(N, V):EnvRest) = V. lookup(N, binding(OtherN, OtherV):EnvRest) = V :- lookup(N, EnvRest) = V. ev(S, Env) = V, `S instanceof Sym` :- lookup(S, Env) = V. ev(if(Cond, X, Y), Env) = Ans :- ev(Cond, Env) = Cond1, s(Cond1, X, Y, Env) = Ans. s(true, X, Y, Env) = Ans :- ev(X, Env) = Ans. s(false, X, Y, Env) = Ans :- ev(Y, Env) = Ans. ev(eq(X, Y), Env) = Ans :- ev(X, Env) = X1, ev(Y, Env) = Y1, sel(X1, Y1) = Ans. sel(X, X) = true. sel(X, Y) = false. ev(closure(Formals, Body, ClosEnv), Env) = closure(Formals, Body, ClosEnv). ev(lambda(Fs, B), Env) = closure(Fs, B, Env). ev(apply(Fn, As), Env) = Ans :- ev(Fn, Env) = closure(Fs, B, CEnv), evList(As, Env) = As1, addToEnv(CEnv, Fs, As1) = NewEnv, ev(B, NewEnv) = Ans. addToEnv(Env, nil, nil) = Env. addToEnv(Env, F:Fs, A:As) = binding(F, A):Rest :- addToEnv(Env, Fs, As) = Rest. evList(nil, Env) = nil. evList(X:Xs, Env) = X1:X1s :- ev(X, Env) = X1, evList(Xs, Env) = X1s. eval(X) = Y :- ev(X, nil) = Y. """ doIt = function(x) { return PrologTranslator.answer(x, lispRules) } doIt("ev(x, binding(z, asdf):binding(x, y):nil, Ans)") doIt("ev(cdr(cons(quote(a), quote(b))), Env, Ans)") doIt("ev(cons(quote(a), cons(quote(b), quote(c))), Env, Ans)") doIt("evList(x:y:nil, binding(x, 1):binding(y, 2):nil, Ans)") doIt("addToEnv(binding(z, 3):nil, x:y:nil, 1:2:nil, Env)") doIt("ev(apply(lambda(nil, cons(a,b)), nil), nil, Ans)") doIt("eval(apply(lambda(x:y:nil, cons(x,y)), foo:bar:nil), Ans)") prog = """ apply( apply( lambda(x:nil, lambda(y:nil, cons(x, y))), a:nil ), b:nil ) """ doIt("eval(" + prog + ", Ans)")