Logic programming: AMALOG is a basic Prolog-ish interpreter in Snap!

From a different topic

Sounds interesting. Any specific ideas yet? Would it support optimization through integer linear programming?

hmm thats really cool cant wait to see them add it!

Well, if I do it, it'll just barely work, never mind optimization, because I'm totally ignorant, other than having read SICP 4.4. I'm sorta hoping that if I hold my breath long enough @toontalk, who actually speaks Prolog, will do it. :~)

I think someone should implement the worlds tiniest Prolog interpreter in Snap!

Here it is
Google Photos

and here's an example of using it
Google Photos

From
Nilsson, Martin. "The world's shortest Prolog interpreter?." (1984): 87-92. Implementations of Prolog, edited by J.A. Campbell

Click on the images to see the entire thing.

Oh, this is nice, I want to play with it! Thanks, Ken, for sharing this.

Seriously, is the (Lisp?) code on this single page a fully operational core Prolog interpreter?
Do all of the functions the interpreter utilizes have Snap! equivalents?
Do those five basic functions suffice to gradually build a full Prolog interpreter upon?
(if 3x yes: wow!)

Yes it is MacLisp and everything should be easily translated to Snap! It is a real Prolog (no cut or assert). In Snap! one can replace the var predicate with something that checks if it starts with a question mark.

Here's the first page which I should have included since it explains how the selectors and constructors have simple Lisp definitions.

I’m trying to write a Snap! implementation but don’t understand (MAC) Lisp.
What is … ?

  • (goals)
  • (list goals)
  • ‘((bottom-of-env))
  • top-level
  • (null)
  • atom
  • apply
  • loop with …
  • for ( head . tail) in database do
  • setq
  • caar
  • cadr
  • cdar

Things in parentheses, except for a few exceptions, are procedure calls.

(goals) -> call the procedure GOALS.

(list goals) -> call the procedure LIST, with GOALS as an input. (GOALS itself, not the result of calling GOALS, which would be
(list (goals))

(@toontalk, I forget, is MacLisp a Lisp-1 or a Lisp-2?)

'((bottom-of-env)) -> the one-item list containing the one-item list containing the value of bottom-of-env. Parentheses after a single-quote a/k/a an apostrophe indicate a list, with its items separated by spaces.

top-level -> the context of interacting with the user, not inside a procedure call

(null) -> where did you find this? It's calling a procedure NULL, but I would expect it to take an input, and return True if the input is the empty list. I dunno what it means with no input.

atom -> An atom is either an empty list or something that isn't a list.

apply -> To apply a function to arguments means to call it, to invoke it. There's a procedure APPLY that takes two inputs: a function and a list of inputs to call it with. (Input values, not input expressions).

loop with -> ?? What's the context?

(head . tail) -> A list is stored as a linked chain of pairs. Pairs are basically arrays of length two. The notation (a . b) means a pair whose first element is A and whose second element is B. A list is either the empty list, a distinguished object not equal to anything else, or a pair whose second element is (recursively) a list. The first elements of the pairs are the items of the list. So the notation (x y z) for a list is equivalent to (x . (y . (z . ()))).

In the context of FOR, "head" and "tail" are variable names, which are given values (locally) by matching elements of DATABASE.

setq -> The assignment operator. The Q stands for "quote," to remind you that in the expression (setq var val) the VAR part is not evaluated, but is the actual variable name, literally in the expression. Because of the special rule about not evaluating the variable name, SETQ is one of those exceptions I mentioned when talking about parentheses meaning function calls.

caar, cadr, etc. -> For historical reasons (which I'll explain if you insist, although you can search the forum for the last dozen times I've done so), the first item of a pair is called its "car," and the second item is called its "cdr." CAR and CDR are functions that take a pair as input and select one of the two elements. Things that match the regular expression c[ad]+r are names of functions made by composing CAR and CDR. So (caar x) means (car (car x)); (cadr x) means (car (cdr x)) (Be careful about the order: evaluated right to left!); etc. All combinations up to four As and/or Ds are standardly provided as primitives in most Lisp dialects.

Functions and variables are in separate name spaces in MacLisp. To call a function bound to a variable named F on argument A you used (funcall F A) - I think it was faster than (apply F (list A))

OK, so (list goals) isn't a list containing the procedure; it's a list containing something else. :~/

I finally found an online source of the tiny Prolog in Lisp both the readable longer version and the incredibly short hard-to-understand version (the current topic).
http://elvira.stacken.kth.se/~mz/sp/stackpointer-1982-2.pdf

Starting on page 12. The introductory half-page is in Swedish. Here's Google Translate:

I get it, he's drinking out of a Can (line 9 of the body) but it's not Coke (line 5). He's drunk.

I guess it was meant to be a parody of Wolfman Jack, or a similar radio dj of the time.
WJ's shows were broadcast in Europe by AFN (American Forces Network).

From the pictures @toontalk attached earlier it is unclear (to me) where this value is initialized. My guess is that bottom-of-env would be either the first or the last item of env (is that a built-in component of MacLisp?).

A mistake on my part: NULL, indeed, doesn't come without argument. Snap!: untitled script pic (43).
BTW does Lisp, like Snap! discern between "empty list" (nil) and "nothing"?

    ((loop with goalmolec = (molec (car nlist) (caar to-prove)) and
      rest = (but-first-goal to-prove) and env2 = nil and tmp = nil
      for (head . tail) in *database* do
      (and (setq env2 (unify goalmolec (molec n head) env))
           (setq tmp (seek (cons tail rest) (cons n nlist) env2 (add1 n)))
           (return (and (null (equal tmp n)) tmp)))))

(((((((I can only hope the parenthesis balance is 0))))))) :wink:

My guess is that loop [...] for (head . tail) in *database* do [...] is the actual loop construct, encompassing a few let -s, followed by (Snap!): untitled script pic (44) and then (still inside the c-shape) the body which returns either true or false (?).

No. For one thing, the environments in question are Prolog environments, not Lisp environments. (And Prolog environments are different, because variables can be bound to patterns—to other variables, for example.)

No, there's no such value as "nothing," although a variable can be unbound, which has a related but different meaning. I think that in Snap! the thing you are calling "nothing" is the empty string.

https://www.maclisp.info/pitmanual/contro.html:

LOOP is a programmable iteration facility used in Maclisp, NIL and Lisp Machine Lisp which was inspired by, but is not compatible with,the “FOR” facility in Interlisp's CLISP.

The general approach is that a LOOP form macroexpands into a single program loop, into which a variety of features can be incorporated. The loop consists of some initialization (prologue) code, a body which might be executed any number of times, and some exit (epilogue) code. The loop can have local variables. The kinds of features offered are, for example, initialization and stepping of local variables, deciding when to end the iteration, putting user written code into the body, stepping variables through “paths” in data structures (not described in this draft), accumulating quantities in local variables, and returning a value from the LOOP.

Internally, LOOP constructs a PROG which includes variable bindings, pre-iteration (initialization) code, post-iteration (exit) code, the body of the iteration, and the stepping of the variables of iteration to their next value (which happens on every iteration after executing the body).

A clause consists of a keyword symbol and any keywords which it deals with. For example,

(LOOP FOR X IN L DO (PRINT X))

contains two clauses, “FOR X IN L” and “DO (PRINT X).” Certain of the parts of the clause will be described as being expressions. For example, (PRINT X) in the above. An expression can be a single Lisp form or a series of forms implicitly collected by a PROGN. An expression is terminated by the next atom (which is taken as a keyword) or by the end of the LOOP body. This syntax allows only the first expression to be atomic, but makes misspelled keywords more easily detectable.

...

The discussion of LOOP in the next several pages is only a summary of LOOP's features. Descriptions of certain features have been omitted and descriptions of others have been shortened for this draft; a later draft may contain a more full description. For more complete information in the meantime, see MIT Laboratory for Computer Science TM-169, “LOOP Iteration Macro.”

Multics users must (%include loop) to get LOOP.

The FOR keyword takes a variety of syntaxes. Each has a slightly different meaning; read their descriptions carefully. AS is a synonym for FOR.

FOR var [datatype] IN expr1 [BY expr2]

This iterates over each of the elements in the list expr1. If the BY subclause is present, expr2 is evaluated once on entry to the loop to supply the function used to fetch sublists instead of CDR.

FOR var [datatype] ON expr1 [BY expr2]

This is like the previous FOR format, except that var is set to successive sublists of the list instead of successive elements. Note that since var will always be a list, it is not meaningful to specify a datatype unless var is a destructuring pattern (beyond the scope of this draft). Note also that LOOP uses a NULL rather than an ATOM test to implement both this and the preceding clause.

FOR var [datatype] = expr

On each iteration, expr is evaluated and var is set to the result.

FOR var [datatype] = expr1 THEN expr2

var is bound to expr1 when the loop is entered, and set to expr2 (re-evaluated) at all but the first iteration. Since expr1 is evaluated during the binding phase, it cannot reference other iteration variables set before it; for that, use the following:

FOR var [datatype] FIRST expr1 THEN expr2

This sets var to expr1 on the first iteration, and to expr2 (re-evaluated) on each succeeding iteration. The evaluation of both expressions is performed inside of the LOOP binding environment, before the LOOP body. This allows the first value of var to come from the first value of some other iteration variable, allowing such constructs as

(LOOP FOR TERM IN POLY FOR ANS FIRST (CAR TERM) THEN (GCD ANS (CAR TERM)) FINALLY (RETURN ANS))

FOR var [datatype] FROM expr1 [TO expr2] [BY expr3]

This performs numeric iteration. var is initialized to expr1, and on each succeeding iteration is incremented by expr3 (default 1). If the TO phrase is given, the iteration terminates when var becomes greater than expr2. Each of the expressions is evaluated only once, and the TO and BY phrases may be written in either order. DOWNTO may be used instead of TO, in which case var is decremented by the step value, and the endtest is adjusted accordingly. If BELOW is used instead of TO, or ABOVE instead of DOWNTO, the iteration will be terminated before expr2 is reached, rather than after. Note that the TO variant appropriate for the direction of stepping must be used for the endtest to be formed correctly; i.e. the code will not work if expr3 is negative or zero. If no limit-specifying clause is given, then the direction of the stepping may be specified as being decreasing by using DOWNFROM instead of FROM. UPFROM may also be used instead of FROM; it forces the stepping direction to be increasing. The datatype defaults to FIXNUM.

The WITH keyword may be used to establish initial bindings, that is, variables which are local to the loop but are only set once, rather than on each iteration. The WITH clause looks like:

WITH var1 [datatype] [= expr1]
[AND var2 [datatype] [= expr2]]...

If no expr is given, the variable is initialized to the appropriate value for its data type, usually NIL. WITH bindings linked by AND are performed in parallel (as in a LET); those not linked are performed sequentially (as in a LET*). That is,

(LOOP WITH A = (FOO) AND B = (BAR) ...)

does its bindings like

... (LET ((A (FOO)) (B (BAR))) ...) ...

whereas

(LOOP WITH A = (FOO) WITH B = (BAR) ...)

does its bindings like

... (LET* ((A (FOO)) (B (BAR))) ...) ...

...

LOOP forms are intended to look like stylized English rather than Lisp code. There is a notably low density of parentheses, and there are several synonyms for many of the keywords to allow writing of more euphonious and grammatical “English.” Some feel that this notation is verbose, inappropriate or distasteful, or misleading; others find it flexible, convenient, and expressive. Users of DO are frequently as baffled by the complexity of some LOOP forms as users of LOOP are irritated by the verbosity of the equivalent DO forms.

A controversy exists. I have strong opinions on the issue, but others whom I greatly respect have strong opposing opinions. In the interest of fairness, since there is no universally accepted “conservative position,” I do not here offer any style advice about whether to choose DO or LOOP for any particular application or as a general-purpose tool for use day-to-day. I mean only to point out that there is an issue of style here, and that there are good and bad reasons for choosing either.

...

Yeah, that recording is actually from a Dutch pop music TV show from my youth.

I see.

I did mean the empty string in Snap!.

Thanks for the explanation!

I really tried to convert the example Lisp code to Snap!, but found it too difficult. So I wrote my own very basic Prolog-ish interpreter from scratch (no pun intended). I probably did not comply fully with any of the existing Prolog syntax varieties, but so what? Please try it, anyone … I’m looking forward to your comments and suggestions!

Here it is.

There is at least one bug in the code: I tried to allow the functor (1st element of a goal) to be variable too (I’m not even sure if it’s supposed to be, in Prolog), but somehow this doesn’t work (yet).(solved)
Also, the code is a bit clumsy, and hardly documented yet.

Below is an example of logic rules entered in a database. It does not execute - to experiment with the interpreter, please follow the above link.

To do:

  • prevent improve mechanism preventing infinite loops;
  • improve runtime efficiency;
  • implement some example problems (see if they can be expressed, and solved).

You realize you can't do a perfect job of this, right?

The way real Prolog deals with this is to let the user indicate explicitly where to break a potentially infinite loop. Look up "cut" in a Prolog manual/textbook.

P.S. I can't look at this right now, but I will. Honest!