Script interpreter bug?

[l0mars01]

I was trying to write some useful code when I found a problem. Some testing revealed a pattern:

Code: Select all

(setq test (lambda (a b)
				(block Nil
					(dbgOutput a)
					(dbgOutput b)
					(a b))))
(setq zero (lambda (a) 0))

(test zero 1) -> 0
debug displays: [lambda expression] 1

(test add 1) -> 0
debug displays: add 1

(add 1) -> 1

The red expression should evaluate to 1 but evaluates to 0 like function 'zero' is still operator. This happens whenever a lambda expression uses a parameter as an operator--like

Code: Select all

(lambda (parameter ...) 
	(parameter operand ...))

. The lambda expression evaluates correctly on its first application, but on subsequent applications it still uses the operator's first value and not the parameter's actual value.

Is the interpreter supposed to do that?

[alterecco]

Interesting. I played around with it a bit and think the problem is that just doing (a b) does not let the wrapper function catch the return value. Try:

Code: Select all

(setq test (lambda (a b)
    (dbgOutput (a b))
))
(test add 1)
1
True

Furthermore, try:

Code: Select all

(setq test (lambda (a b)
    (eval (a b))
))
(test add 1) -> 1

So, i think the problem is that just doing (a b) does not catch the return value, but some status code or the like. (dbgOutput ..) and (eval ..) however seem to be able to catch the correct value. Not sure if this made things clearer though...

.]

[l0mars01]

I try this, but my results do not confirm:

Code: Select all

(setq test (lambda (a b)
				(dbgOutput (a b))))

(test add 1)
1
True

(test zero 1)
1
True

(setq test (lambda (a b)
				(eval (a b))))
(test add 1) -> 1
(test zero 1) -> 1
(test zero 123) -> 123

Do you repeat applying the same operator (eg, test) on different operands? The problem only shows up on repeated use of an operator.

[george moromisato]

Nice debugging, l0mars01. Thanks!

This is definitely a bug. You are right that the variable "a" is being bound to the first function that you pass in. I've fixed this in the next version.

Thanks again!

[l0mars01]

Excellent! Finding it surprised me.

I've noticed some more surprises. These may be bugs or be simply language design.

1. Dynamic Extent
   The local variable bindings appear to have dynamic extent. For example, code

   Code: Select all

   ((block (a)
   	(setq a True)
   	(lambda Nil a)))

   raises error

   No binding for symbol: a ### ((block (a) (setq a True) (lambda Nil a))) ###

   . A local binding ceases existing when the form that creates it finishes executing. Is this true?
2. Closures
   The above example requires a closure evaluation and raises an error. Another possibility is proper closures fail evaluation. The deceptively similar looking code

   Code: Select all

   (block (a)
   	(setq a True)
   	((lambda Nil a)))

   raises error

   a ### ((lambda Nil a)) ###

   . Here, the closure's referenced variable a is in extent. Is the interpreter supposed to support closures?

The code I've been testing

Code: Select all

(setq foldl (lambda (op initial list)
					(block Nil
						(enum list var
							(setq initial (op initial var)))
						initial)))
(setq map (lambda (map list)
				(foldl (lambda (a b) (lnkAppend a (map b)))
					Nil
					list)))

led me to notice these features. Should these functions work?

[Betelgeuse]

Code: Select all

((block (a)
   (setq a True)
   (lambda Nil a)))

Err yes that does give you that error but why is there an extra parens around it? Removing the extra pair of parens makes it work as expected.

Your second example has more of the same. Why are you adding random parens in places? I agree the errors are not clear what is going on.

As for fold and map I would have too look more closely at them to see what is going on will get back to you.

edit: I just had a thought maybe you are using some advanced lisp features. This language while lisp like isn't lisp.

[Betelgeuse]

can you give us some expected inputs and outputs? So we can test your functions out for ourselves.

Question why do you have a temp variable the same name as your function? See the map function. Do you want it to be a different function?

[l0mars01]

That was fast! I'll explain. The expressions employ only familiar rules:

Procedure application: (operator operand ...)
The operator and operands are expressions.
Application applies the value of operator (a procedure) to the values of operands (arguments).
It evaluates to the value of the procedure applied on its arguments.

and special forms:

Local binding: (block (variable ...) body)
body = expression ...
Binds each variable to Nil. Their scope is body.
Evaluates to the value of body's last expression if it has any expressions. Otherwise, it evaluates to Nil.

Assignment: (setq variable expression)
Binds the value of expression to variable.
Evaluates to this value.

Anonymous function: (lambda (variable ...) expression)
Creates a procedure with parameters as the variables and body as the expression.
Evaluates to the created procedure.

The extra parentheses are there to evaluate block's body's last expression value (the value of a lambda expression with no parameters). This equivalent body might clarify:

Code: Select all

(setq procedure (block (a)
						(setq a True)
						(lambda Nil a)))
(procedure)

The other code is equivalent to

Code: Select all

(block (a)
	(setq a True)
	(setq procedure (lambda Nil a))
	(procedure))

Their difference is they create global variable procedure.

foldl and map don't work, but these expressions are equivalent in a language that handles them:
(foldl op initial (list l0 ... ln)) equivalent to (op ... (op initial l0) ... ln)
(map f (list l0 ... ln)) equivalent to (list (f l0) ... (f ln))

The lambda expression parameter map shadows the global variable map on procedure application. They are different variables and the code executes the same if you give them distinct names.

[Betelgeuse]

cool now that I understand what you are asking for I can answer

Code: Select all

(setq procedure (block (a)
                  (setq a True)
                  (lambda Nil a)))
(procedure)

Well yes you are not in the scope that a is valid anymore so even if you have a different variable named a it would still be in error. What are you expecting to happen? Do you expect different scoping rules?

The lambda expression parameter map shadows the global variable map on procedure application. They are different variables and the code executes the same if you give them distinct names.

Do note that the script supports recursion that is why I was confused when you named it the same thing. (you got around that because local variables come first)

[george moromisato]

In the next version, the interpreter will support closures. E.g.,:

Let's define a global function that takes another function as a parameter.

Code: Select all

(block Nil
   (setq times2 (lambda (f1)
      (block (a)
         (setq a 2)
         (multiply a (f1))
         )
      ))
   )

A "closure" means that we can define a function within a local scope and pass it as a parameter to a global function. The local function can access its own local variables within the global function.

For example:

Code: Select all

(block (a)
   (setq a 7)
   (times2 (lambda Nil a))   ; This will return 14. When we
                      ; pass in the local function,
                      ; (lambda Nil a), the value of a is 
                      ; bound to the function before it is
                      ; passed in.
                      ; That is, when the local function 
                      ; executes inside of the global
                      ; function (times2), the local 
                      ; function has access to its local
                      ; variables (and does not have
                      ; access to the local variables
                      ; of the global function).
   )

[george moromisato]

BTW, I tested:

Code: Select all

((block (a) (setq a 7) (lambda Nil a)))

In the new version, the code above returns 7 (as it should).

[Betelgeuse]

(sorry for the offtopic but want to ask a couple questions about this)

Code: Select all

((block (a b)
		(setq a True)
		(setq b (lambda nil a))
		(setq a 7)
		b
))

With this change would that return a True or a 7?

Code: Select all

(block (c)
	(setq c (block (a b)
		(setq a True)
		(setq b (lambda nil (if a (setq a nil) (setq a True))))
		(setq a nil)
		b
	))
	(dbgOutput (c))
	(dbgOutput (c))
	(dbgOutput (c))
)

What will this output?

[Betelgeuse]

new example

Code: Select all

((block (a)
		(setq a nil)
		(lambda nil 
			(block nil (setq a True) (if a 7 11))
		)
))

[george moromisato]

Betel,

For the first example, the code returns True. [Which, I believe, is consistent with how closures should work.]

For the second example, the code returns:

Nil
True
Nil

[In other words, the changed value of "a" persists across invocations.]

I don't know enough about closures to know if the second behavior is standard for closures or not. I suspect not, but probably not worth fixing.

[l0mars01]

In the next version, the interpreter will support closures.

Cool! 8)

Further testing showed me I was wrong about dynamic extent:

Code: Select all

(setq a True) -> True
(block (a) a) -> Nil
(block (a) ((lambda Nil a))) -> True

The lambda expression simply matches free variables to global bindings. When no global binding exists (like my previous examples), it raises error on application.

Betelgeuse, a closure is an anonymous procedure that (1) captures the environment in which it's created and (2) uses an extension of this environment to evaluate its body. It can be modeled this way

procedure = (parameters body environment)
parameters = (variable ...)

where an environment is a stack of frames based off the global environment, ie

environment = global-environment | (frame . environment)

and a frame is a collection of bindings

frame = (binding ...)

and a binding associates a variable to a value

binding = (variable value)

For procedure = ((variable-1 ... variable-n) body captured-environment), expression (procedure value-1 ... value-n) evaluates to the evaluation of body in environment (parameter-bindings . captured-environment) where frame parameter-bindings is ((variable-1 value-1) ... (variable-n value-n)).

Variables in a scope match its environment's top bindings (to evaluate expressions). To illustrate environments

Code: Select all

(setq a 'global-a)
(setq b 'global-b)
;mark 0
(block (b c)
       (setq b 'b)
       (setq c 'c)
       ;mark 1
       (block (b)
       	      (setq a 'new-a)
       	      (setq b 'new-b)
	      (setq c 'new-c)
	      ;mark 2
	      )
       ;mark 3
       )
;mark 4

Mark 0 and 4 are in the same scope and use the global environment to evaluate expressions there (though the binding for a has changed).
Mark 0
Environment: global-environment
Top bindings: (a 'global-a) (b 'global-b)
Mark 4
Environment: global-environment
Top bindings: (a 'new-a) (b 'global-b)

Mark 1 and 3 (same scope) use an extension of the global environment as their environment. The enclosing block form extends the global environment with local-bindings for b and c.
Mark 1
Environment: (frame0 . global-environment)
Top frame: frame0 = ((b 'b) (c 'c))
Top bindings: (a 'global-a) (b 'b) (c 'c)
Mark 3
Environment: (frame0 . global-environment)
Top frame: frame0 = ((b 'b) (c 'new-c))
Top bindings: (a 'new-a) (b 'b) (c 'new-c)

Mark 2 uses a further extension as its environment. The enclosing block extends the enclosing enviroment with a local binding for b. The block's body changes bindings for a and c.
Mark 2
Enviroment: (frame1 frame0 . global-environment)
Top frame: frame1 = ((b 'new-b))
Top bindings: (a 'new-a) (b 'new-b) (c 'new-c)

While this can be convenient, I'm beginning to see careful use of some global variables can allow me to write the code I was after.