Tony Finch – blog

Recently I've read about Lua. It's a nice simple language, with a syntax that's quite close to my ideal for a dynamically-typed imperative language. One of the things it omits for simplicity's sake is first-class continuations. I've been wondering how one might specify a similar syntax if you have a Schemeish infrastructure, so that the usual control structures can be desugared into functions, conditionals, and tail-calls. I also have in mind Modula-3's definition of some control structures in terms of exceptions. In the following I'm not going to talk about the whole syntax; I'll omit things which don't involve blocks.

The basic form of a block expression is:

	name(arguments): do
		statements
	end

The value of this expression is a function which takes some arguments and which when called executes the statements. The scope of its name is just within the block itself; it is used in inner scopes to refer to shadowed variables in outer scopes.

To execute the block immediately, the arguments can be omitted:

	name: do statements; end

is equivalent to

	name(): do statements; end()

that is, it specifies a function that has no arguments and which is called immediately.

The name can also be omitted. Doing so just means there's no way to refer to this block's variables if they are shadowed in an inner scope. For example, an anonymous function (lambda expression) is typically

	(args): do statements; end

You might also want to allow a shorter version of

	(args): do return(values); end

for use in expressions, perhaps

	(args): return (values)

A minimal block like the following is just like a Lua block:

	do statements; end

Just before the end of each block there's an implicit return(nil). You can return from a block early with whatever value or list of values you want.

Instead of do...end you can write a conditional:

	if expression then
		true statements
	else
		false statements
	end

If the else part is omitted then the false statements are implicitly return(nil). You can also add elsif expression then alternate statements parts in the usual way.

The basic form of a loop is

	name: do
		statements
	loop

which is equivalent to

	name: do
		statements
		return(name())
	end

that is, loops are implemented using tail recursion. (Loops do not have to be named, but I've written the desugaring in terms of a named block to avoid having to talk about hypothetical unique names.)

	name: while expression do
		statements
	loop

is equivalent to

	name: if expression then
		statements
		return(name())
	end

and

	name: do
		statements
	while expression loop

is equivalent to

	name: do
		statements
		if expression then
			return(name())
		end
	end

You can use until expression instead of while not(expression).

Given the above, you can see that return inside a loop is similar to break in C. It's often nice to be able to break out of more than one nested loop at a time, or return from a function inside a loop. This is where a block's name comes into play. To return from a named outer block, call name.return. For example:

	def bsearch(arr, val): do
		def lo, hi := 1, #arr
		while lo <= hi do
			def mid := math.floor((lo + hi) / 2);
			if arr[mid] == val then
				bsearch.return(mid)
			elsif arr[mid] < val then
				lo := mid + 1
			else
				hi := mid - 1
			end
		loop
	end

A bare return in the above would specify the value of the if block, not the function.

This kind of return makes it easy to write call-with-current-continuation:

	def callcc(f): do
		def cont(...): do
			callcc.return(...)
		end
		return(f(cont))
	end

However this is unnecessary because return is already an expression whose value is the current continuation. It's just like other function arguments, except that it's implicit (a bit like the self argument in Lua's methods) and can't be assigned to (so that the compiler can do tail-call optimisation). (Actually, what if you *could* assign to return? Eeeeevil!)

There are three forms of statement within a block: definitions, assignments, and function calls. Since a block without arguments is equivalent to a function expression that is immediately called, non-function blocks can be statements. A function definition

	def name(arguments): do ...

is equivalent to

	def name := name(arguments): do ...

For bigger code, it's useful to allow a block's name to be repeated after its end or loop, for example:

	def long_function(arguments): do
		code
		code
		code
	end long_function

You can further desugar definitions, since

	old_name: do
		before statements
		def variables := values
		after statements
	end

is equivalent to

	outer_name: do
		before statements
		inner_name(variables): do
			after statements
		end(values)
	end

except that you need to fix up the after statements so that unqualified returns are qualified with the outer_name, and variables qualified with the old_name are qualified with the outer_name or inner_name as necessary.

Some things are still missing from this description. A for loop is necessary, probably based on some kind of iterator concept, but that's too far away from the topic of this post to be worth pursuing in detail now. Also, we would probably like a standard exception mechanism; this is not trivial to implement in terms of continuations because the code that handles an exception is determined dynamically (like Perl local) whereas continuations are lexical (like Perl my). Finally, the combination of continuations and concurrency is utterly filthy: imagine what happens if one thread calls a continuation created by another...