Lambda abstraction

Why and how

A lambda abstraction (aka. anonymous function or function literal) is a function definition that is not bound to an identifier. Lambda functions are often:

1. Arguments being passed to higher order functions, or
2. Used for constructing the result of a higher order function that needs to return a function

A lambda becomes a closure after it captured some values in outer scope.

MY-BASIC offers full support for lambda, including invokable as a value, higher order function, closure and currying, etc.

The syntax of lambda in MY-BASIC is:

    LAMBDA ::= lambda "(" PARAMETERS ")" "(" BODY ")"
PARAMETERS ::= variable { "," PARAMETERS }
      BODY ::= STATEMENTS
STATEMENTS ::= statement \n STATEMENTS

It begins with a LAMBDA keyword, and follows by a parameter list (with none or multiple parameter identifiers), then the lambda body. It's possible to write multiple line statements in a lambda body, use the RETURN statement to return a value from a lambda body.

Short identifier

The LAMBDA keyword is too long to type? Then try defining another short alias name for it by adding an MB_LAMBDA_ALIAS macro. For instance defining it with a single character ~, then ~ () () will be equivalent to lambda () ().

#ifndef MB_LAMBDA_ALIAS
#	define MB_LAMBDA_ALIAS "~"
#endif /* MB_LAMBDA_ALIAS */

Or even unicode alias.

#ifndef MB_LAMBDA_ALIAS
#	define MB_LAMBDA_ALIAS "\xce\xbb"
#endif /* MB_LAMBDA_ALIAS */

The hex symbol represents for the λ symbol.

l = λ (a, b) (return a + b)
print l(1, 2);

"Hold on. Where's a λ key?" Well, I hope there was one :)

Samples

Let's have a look at some short samples as follow.

Simple invoke:

f = lambda (x, y) (return x * x + y * y)
print f(3, 4);

Returning as a value:

def counter()
	c = 0

	return lambda (n)
	(
		c = c + n
		print c;
	)
enddef

acc = counter()

acc(1)
acc(2)

Higher order function:

def foo()
	y = 1

	return lambda (x, z) (return x + y + z)
enddef

l = foo()

print l(2, 3);

Closure:

s = 0

def create_lambda()
	v = 0

	return lambda ()
	(
		v = v + 1
		s = s + 1
		print v;
		print s;
	)
enddef

a = create_lambda()
b = create_lambda()

a()
b()

Currying:

def divide(x, y)
	return x / y
enddef

def divisor(d)
	return lambda (x) (return divide(x, d))
enddef

half = divisor(2)
third = divisor(3)

print half(32); third(32);

Folding:

def fold(lst, func, seed)
	r = seed
	l = clone(lst)
	while len(l) <> 0
		r = func(r, l(0))
		remove(l, 0)
	wend

	return r
enddef

lst = list(2, 3, 4)
func = lambda (l, r) (return l + r)
ret = fold(lst, func, 0)
print ret;

Lazy evaluation:

def fib(n)
	t0 = 0
	t1 = 0
	i = 0

	return lambda ()
	(
		if i = 0 then
			t = 1
		else
			t = t0 + t1
		endif
		t0 = t1
		t1 = t
		i = i + 1
		if i > n then
			return 0
		endif

		return t
	)
enddef

f = fib(20)
do
	n = f()
	if n then
		print n;
	endif
until not n

It's neat to implement a foreach loop with lambda:

def foreach(c, f)
	it = iterator(c)
	while move_next(it)
		item = get(it)
		f(item)
	wend
enddef

f = lambda (i) (print i;)

l = list(1, 2, 3, 4)

foreach(l, f)

It's also possible to implement a list iterator in another way by using a lambda to memorize states:

class my_list
	var l = list()

	var tail = "__TAIL__"

	def push_back(i)
		push(l, i)
	enddef

	def pop_back()
		return pop(l)
	enddef

	def get_iterator()
		it = iterator(l)

		return lambda ()
		(
			if not move_next(it) then
				return tail
			endif

			return get(it)
		)
	enddef
endclass

lst = new(my_list)
lst.push_back(1)
lst.push_back(2)
lst.push_back(3)
lst.push_back(4)

iter = lst.get_iterator()
do
	item = iter()
	if item <> lst.tail then
		print item;
	endif
until item = lst.tail