Globals/Locals: Mini-LISP C implementation - a-list behavior

[OfirMarkowitz1]

@DorYeheskel @yossigil
Though I can't run the C implementation, I picked up a few possible errors regarding the binding process of actuals to formals, when calling a lambda expression.

1. The restoring of the a-list after executing the lambda to it's state before execution isn't done, leading me to believe that when there's intersecting formals between a caller and a callee lambdas, after the callee's execution ended, the binding of the callee's actuals will still exist in the a-list, and will precede the binding of the caller, e.g. after during the caller's execution, after callee's execution ended, the a-list state will be false and will mislead the lookup.
   There's no test in the project which checks this scenario, and I think at least one should be added.

2. The aforementioned issue with the binding also means that the a-list won't be restored correctly when lambdas are involved, and an error occurs. That's because the "bind" function doesn't call "set" nor increment "count_sets" directly, so the "count_sets will be smaller than needed when an error occurs and "restore_alist" is called, e.g., not all the "sets" done during the process (with set/defun/ndefun) will be cleared.

[yossigil]

Few comments.

• I am not sure what is the correct behaviour re side effects, I.e., setting variables when executing something that aborts. I now think the variables should be saved; I think this is what I always thought, but I am not sure.

• The solution with the counters seems like a hack to me. Cannot explain why, but it looks so unnatural. We work with lists, so what are the number doing here?

3. It is clear that binding should be removed, both in normal and in aborting execution

[OfirMarkowitz1]

After encountering a few bugs in my JS implementation, I arrived at the conclusion that there has to be 2 different a-lists, one for the bindings of the actuals to the formals, and one for set/defun/ndefun.
It has to be this way because the formals' bindings must always take precedence over set bindings. For example:

(set 'x 'a) ; => A
(defun foo (x) (cons (set 'x 'c) (eval 'x))) ; => (LAMBDA (X) ...)
(foo 'y) ; => (C . Y)
(eval 'x) ; => C

When evaluating (foo 'y), if the binding of the formal X to the actual Y wouldn't take precedence over the binding of X to C, after the evaluation of (set 'x 'c), upon the evaluation if (eval 'x), the result would be wrong - (C . C) instead of (C . Y). It doesn't make since that sets would override formals passed to a lambda. Of course, after the call to foo is over, X should be bound to C.
Also, my solution supports restoring the state of the a-list and formals' a-list when an exception is thrown (e.g. error is invoked).

For more information about my solution, please review safot/Mini-LISP.JS/Engine.js

[OfirMarkowitz1]

Another thing: When applying a lambda, after the binding of the formals, and the execution of the lambda, the formals should always be unbound. It can either be done by telling the environment how many pairs to unbind, or by keeping an a-lists stack, for the formals' bindings. I used the former because it seems much simpler to me - more readable and understandable, consumes less memory, etc. I can quickly change it to the latter if you want.

[yossigil]

Neither way. The function that does the invocation, defines a local variable, called last-a-list. It restores this variable when the invoked function in lisp terminates. It is possible to make this more abstract, i.e., a save and restore methods of the a-list. Did you check the C implementation? @OfirMarkowitz1

[OfirMarkowitz1]

I did. Anyway, I implemented it as you said - get the a-list to save the current state, then after the evaluation of the lambda's body (whether it was successful or an error occurred), setting the a-list back. If we don't want to expose the a-list to the Environment's user, the Environment should maintain a stack of a-list pointers, that is pushed before any bind and popped to back to the a-list after the evaluation of the body (the stack can be implemented as an S expression as well). Not sure if it qualifies as the most simple solution :)

[yossigil]

Not yet; not sure why I cannot explain this. Let me try again; I will use the square bracket notation, [A.B] for dotted pairs.
Initially, the a-list is
[t.t][nil.nil]
After the command

(setq a b)
The list is
[a.b][t.t][nil.nil]
After a no parameters function definition:
(defun f() (set x x))
the a-list is
[f.(lambda () (set x x)][a.b][t.t][nil.nil]
Now, let’s write a function that invokes f and aborts, regardless of the value of x;
(defun g(y) (cond (f) ((car ‘a) (t t)))
the a-list is now
[g.(...)] [f.(lambda () (set x x)][a.b][t.t][nil.nil]
Now, invoke g, on some argument;
(g a)
The evaluation starts by marking two pointers, into the A list. These pointers will be marked as * and @. * denotes the stack of binding, while @ denotes the stack of variables; both stacks are represented by the a list.
Initially, the pointers are identical, and they proceed together as long as functions are not invoked.
The binding prior to the invocation above makes the a list like so:

• [y.b] @ [g.(...)] [f.(lambda () (set x x)][a.b][t.t][nil.nil]
  In each deeper function application the previous binding pointer is saved, it is restored upon successful completion of the invocation. In each set operation, the globals pointer, @, is advanced. If there is an error; all binding are erased by setting the * pointer to the current value of the @ pointer.

[yossigil]

@DorYeheskel , what’s up with this one? See also text in

[DorYeheskel]

@yossigil

1. Done a month ago here.
2. Binding are also removed from the alist each time we returned from a function.
3. The solution with the counters is just the same as pointer - we just tell the alist pointer how much steps ("cdr steps") we need to travel over the alist as described here.

[yossigil]

You are right; there were too many issues that revolved around the same thing. I tried to merge them somewhat and close as many as possible.