On Fri, 1 Feb 2002, Anthony Hannan wrote:

Scott A Crosby crosby@qwes.math.cmu.edu wrote:

...

BTW, what about tailcall out of a block?

foo: ^[^self bar]

Is that a different bytecode?

Tail call out of a block would be harder because the caller's receiver (the block) (which we are replacing) holds the return context and callee's (#bar) localReturns would have to be changed to a remoteReturns. So a new method would have to be made on the fly and the receiver would have to be wrapped in a new block closure with the return context.

I don't know the intricities and terminology of the method context and invocation mechanism; I'm not following this.

Ah. Ha.. It took me two hours hours, but I think we're confusing two distinct things....

[ foo foo foo. ^self someMessage] AND [ bar bar bar. self someMessage]

Which are *very very* different things.

What it means to 'tailcall' for the first seems messy. I don't know? Punt? Define some sort of new semantics for it? Use a normal method call? What do you think?

What it means to tailcall for the second is clear. A block returns the value of the last thing in the block, whether that is a value or a message send. If its a messagesend, it may be tailcalled, furthermore, there are no 'which context does it return into' issues. Finally, since we only care about the last method call, we're already done with using any variables in the context, We'll have popped any that we'll pass to the function we're invoking by this point, before we call out, so we can nuke the context (the one inside of [^^self bar]) safetly?

Is tail recursion required for continuations? I really don't understand continuations, can you give me some pointers?

Tail recursion is not needed for continuations. You only need closures, but without tail recursions, continuations-style programming can overflow the stack much easier.

Continuations are basically when you have a 'what do I do next' argument. Normally, thats implicit, but not always. A stack of frames is a continuation.. Or, an error handler is a continuation.

You can think of each method in squeak currently getting 2 extra arguments, a return continuation (invoked on your return value), and an error continuation. (which is invoked on an error)

Sometimes having them passed explicitly is also good. For example, assume I have a bunch of functions trying to do a proof search (solve a problem).. But, they can fail, and changes may need to be unwound, so handle this with a failure continuation.

Sorta like:

Foo>>match: aStream ifFailure: failCont pos _ stream position .... stream pop. .... " Used to restore the state if things fail " ^^subproblem2 match: aStream ifFailure: [aStream position: pos. ^^failCont value] -- Or, you want to try something, but also maybe try something else if the first fails.

-- Bar>>match: aStream ifFailure: failCont pos _ stream position .... subproblem1 match: aStream ifFailure: failCont. ... stream pop. ... " Used to try an alternative. " ^^subproblem2 match: aStream ifFailure: [aStream position: pos. ... the stuff for the alternative ...]

--

Note that in the first example, without tail recursion, you pay one stack frame for each element on the stream.

You can think of continuations as being the abstract represntation of the flow of control, 'what to do next'. In many cases, existing implicit flow-control continuations may be coopted as continuations. The first example, for example, could be done by throwing exceptions. (and using the implicit error continuation.)

In fact, anytime you have a stack of stuff to keep track of 'what to do next', you're dealing with (a concrete representation of) continuations without even realizing it. That applies to the function-call stack, the error handler stack.

Here's some code, written in SML-NJ that implements a complete regexp matcher. It defines the regular expressions at the top, and the engine at the bottom. This language uses short-circuting boolean connectives and pattern-match on arguments. 'head::tail' is used to patternmatch the head&tail of a list.

--

datatype regexp = Char of char | Times of regexp * regexp | One | Plus of regexp * regexp | Zero | Star of regexp | Underscore | And of regexp * regexp | Top | Not of regexp;

(* val acc : regExp -> char list -> (char list -> bool) -> bool *) fun acc (Char(a)) (a1::s) k = if (a = a1) then k s else false | acc (Char(a)) (nil) k = false | acc (Times(r1,r2)) s k = acc r1 s (fn s' => acc r2 s' k) | acc (One) s k = k s | acc (Plus(r1,r2)) s k = acc r1 s k orelse acc r2 s k | acc (Zero) s k = false | acc (r as Star(r1)) s k = k s orelse acc r1 s (fn s' => if s = s' then false else acc r s' k)

| acc (Underscore) (a1::s) k = k s | acc (Underscore) (nil) k = false

| acc (And(r1,r2)) s k = acc r1 s k andalso acc r2 s k | acc (Top) (nil) k = k nil | acc (Top) (a1::rest) k = k (a1::rest) orelse acc Top rest k | acc (Not(r)) s k = if (acc r s k) then false else true;

-- You can think of the regexp engine as getting 3 arguments: The 'self' indicating the type of regexp node. A stream of characters. A continuation (block) that, when given a stream it returns a boolean indicating if there is a match on the 'rest' of the regular expression. The continuation is used to 'thread' the regular expression through the string.

The matcher and continuation indicates true/false on whether the string is matched. Note that in several of the rules (Times, Star), the continuation is actually a closure over parts of the regular expression.

The control flow is roughly: If you consume no input and match, just invoke the continuation on the input and return that; you match if the 'rest' matches. If you are simple and match, invoke the continuation on the rest of the input and return that value; the regexp is matched if the rest of the string is accepted by the continuation (Char, One, Underscore) If you are simple and don't match, return false. (Char, Zero, Underscrore) If you might match based on whether one or more regular expression match, you try to accept on one regular expression, and set up a new continuation which will be invoked only if that other regular exp matches. (Times, Star)

Anyways, with tail recursion, this matcher consumes stack space proprortional to the complexity of the regexp, not the size of the input string. If it weren't tail recursive, it wouldn't have this property. (It consumes one methodcontext per charater in the input string)

Continuations, are one of those things (like pointers or closures) that seems wierd and confusing until you get it, but when you do, its a revelation. You never view programming quite the same way again.

With BC, the regexp example could be coded up in smalltalk. Adding on a way to extract matching substrings is trivial, and you'd have a extremly featureful regexp library in about 25 lines of code.

In fact, I suggest everyone try it, just get an idea of continuations, then try running it and seeing the beauty of the algorithm. :)

And with tailcall, you won't exhaust all RAM trying to match a megabyte string. Finally, bonus points if anyone can tell me the difference between Times and And.

Scott