How lambda works

Wang Renxin edited this page Nov 19, 2017 · 4 revisions

This page shows how lambda works in MY-BASIC.

MY-BASIC deals with lambda processing during runtime other than parsing time according to its interpretation mechanism. There are some key points:

  1. Creating a lambda. And its own scope, marks parameter list and upvalues (values in outer scope referenced in a lambda)
  2. Preparing scope information. Stores lambda information into its outer scopes which its upvalues refer to. This is a preparation for the 3rd step
  3. Maintaining the scope. Iterates through and checks lambda information marked in step 2 when the scope went out of use, generates a new danling scope and duplicates upvalues into it. Note different lambdas referencing the same outer scope should share same generated scopes; so the danling scope is also managed by Reference Counting and GC, lambdas should reference danling scopes instead of its original ones
  4. Invoking a lambda. Similar to ordinary routines, the only difference is that we have to link the danling scope chain properly before invoking to let a lambda know where to lookup values, and unlink them after invoking
  5. Releasing a lambda. Unreferences a lambda and each layer of its danling scope chain because both lambda and danling scope are referenced type

I’ve written another wiki page to show the usage of lambda in MY-BASIC. For the implementation part, for example assuming got following 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 got a routine multiplier which returns a lambda, it is called twice to create the two multiply_by_2 and multiply_by_3 lambdas with passing 2 and 3 to the lambda creator routine. When calling multiplier at Step a, it gets 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 generated scope:

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

That’s all what we need, before invoking a lambda. MY-BASIC links the scopes as follow when invokes a lambda:

And it does 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 may 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 dealing with scopes; and it's possible to manage everything properly with automatic memory management.

But what whould happen if the global scope went out of use too? As the following code:

class super_outer
	var global_factor = 2

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

		return l

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:

Lambda is not one-fits-all, but it simplifies something.

Clone this wiki locally
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.