How lambda works

I'll explain how does lambda work in MY-BASIC in this page.

MY-BASIC deals with lambda creation during runtime than parsing time according to its interpretation mechanism. The implementation is simple. There are five key points:

1. Create a lambda. And its own scope, mark parameter list and upvalues (values in outer scope referenced in a lambda)
2. Prepare scope information. Store lambda information into its outer scopes which its upvalues refer to. This is a preparation for the 3rd step
3. Maintain the scope. Iterate through and check lambda information marked in step 2 when the scope went out of use, generate a new hanged scope and duplicate upvalues into it. Note different lambdas referencing the same outer scope should share a same new generated scope; so the hanged scope is also managed by Reference Counting and GC, lambdas should reference hanged scopes instead of its original ones
4. Invoke a lambda. Similar to ordinary sub routines, the only difference is that we have to link the hanged scope chain properly before invoking to let a lambda know where to lookup values, and unlink them after invoking
5. Release a lambda. Unreference a lambda and each node of its hanged scope chain because both lambda and hanged scope are referenced type

I’ve written another wiki page to describe the usage of lambda in MY-BASIC. Now I’d like to talk some detail of the implementation. For example assuming we have a piece of code:

global_factor = 2

def multiplier(n)
	l = lambda (a) (return a * n * global_factor) ' Step a

	return l
enddef ' Step b

multiply_by_2 = multiplier(2) ' Step c
multiply_by_3 = multiplier(3) ' Step d

print multiply_by_2(3); ' Step e
print multiply_by_3(4); ' Step f

Here we got a routine multiplier which returns a lambda, we called it twice to create the two multiply_by_2 and multiply_by_3 lambdas with passing 2 and 3 to the lambda creator routine. When we were calling multiplier at Step a, we got a scope layout as follow:

After returning from multiplier at Step b, the “multiplier” scope goes to out of use:

Wait a moment, the lambda expression captured an outer n and another global_factor, what we need to do when the "multiplier" scope went out is duplicating the scope, and put all values which were referenced by lambda into the new generated scope:

The variable l holds the lambda, but it’s not referenced by the lambda; it doesn’t need to duplicate non-referenced value to new generated scope. Now we get four scopes after Step c and Step d as follow:

That’s all what we need to deal with, before invoking a lambda. MY-BASIC will link the scopes as follow when we are going to invoke a lambda:

And it will do a bottom-up lookup for values as the figure shows. Note that the two variables holding lambdas are in the global scope as follow:

As you can see, multiply_by_2 and multiply_by_3 refer to values of the same name n in different scopes, but they share the only one global_factor in the global scope. Generally speaking, implementing a facility of lambda is mostly about taking care of scopes; it would be a disaster without automatic memory management.

But what will happen if the global scope went out of use too? That is a good question; let’s modify the code:

class super_outer
	var global_factor = 2

	def multiplier(n)
		l = lambda (a) (return a * n * global_factor)

		return l
	enddef
endclass

inst = new(super_outer)

multiply_by_2 = inst.multiplier(2)
multiply_by_3 = inst.multiplier(3)

inst = nil

print multiply_by_2(3);
print multiply_by_3(4);

In the line inst = nil, the scope which holds global_factor goes out of use. MY-BASIC creates a new scope as well for this case; and both of the two multiply_by_2 and multiply_by_3 share this scope as follow:

There are only three important points that need to be cared about when I was intending to write good quality code:

1. Defining metastatement in different detailed programming aspect levels
2. Assigning responsibility and authority of state reading and writing among metastatements in a same detailed programming aspect level
3. Join up metastatements naturally

Dismissing a problem is better than solve a problem. Functional programming may dismiss lots of problems elegantly, that we can only solve it more tediously in pure OOP languages. If I can't write code naturally, then I'd go back to step 1 and step 2 for refactoring.