Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

autrijus (1505)

autrijus
  (email not shown publicly)
http://pugs.blogs.com/

Journal of autrijus (1505)

Sunday February 13, 2005
02:27 PM

Day 13: Continuations

[ #23175 ]
First, a heads-up: the source tree in the repository is broken right now, due to the newly introduced "Eval" monad. I'll fix it tomorrow when I wake up.

Some random things I've done today:

  • Separates the one() junction into two sets, the none() set and the one() set, unified on autothreading.
  • Division by zero is caught. (viirya)
  • Lexical pads.
  • Parsec now maintains a Env state, so it can serve as a compiler as well.
  • Compile-time evaluation of runtime code is now possible, which nicely complements eval"".

Today is by far the most challenging day, because I started tackle the control flow as specified in Synopsis 4 (Blocks and Statements) and Synopsis 6 (Subroutines). Perl6 is extremely flexible in this regard, with following features:

  • Access to outer lexical contexts via $OUTER::
  • Access to outer dynamic contexts via $CALLER::
  • Skipping dynamic contexts via leave()
  • Selective exception handling via closure traits, eg. CATCH and CONTROL
  • Tail-recursive Y combinator, via &?SUB and &?BLOCK

Also, although Larry didn't say if Perl6 will have a multiple-entrant call_cc(), because it comes for free with Haskell, I decided to throw it in as a primitive.

To that end, I surveyed various literature on this subject; among the most helpful ones are Ken Shan's "Shift to Control" and "A Monadic Framework for Subcontinuations" from Dybvig, Jones and Sabry. After several hours of tweaking and prototyping, I settled on this definition of Eval monad and the associated Env data type:

type Eval x = ContT Val (ReaderT Env IO) x
data Env = Env { envContext :: Cxt
               , envPad     :: Pad
               , envClasses :: ClassTree
               , envEval    :: Exp -> Eval Val
               , envCC      :: Val -> Eval Val
               , envBody    :: Exp
               , envDepth   :: Int
               , envID      :: Unique
               }

That is, each ongoing evaluation keeps an unique ID of the current dynamic context, its current continuation, body of expression, recursion depth, a lexical pad of symbols, and its caller's evaluation environment (and it's caller's caller's, etc...)

The "envEval" field is the current evaluator, which is responsible to turning an expression into a value. Normally it just points to the "evaluate" function in Eval.hs; however, once we start dealing with sublanguages inside Perl6 (grammar and rules, for example), it may come handy as we can freely swap evaluation engines for any (dynamic and/or lexical) contexts.

The "ReaderT" means that it can freely enter a lexical scope by "shadowing" the pad with some new symbols; direct modification of the pad contents is disallowed. (At least in FP6; in full Perl6 I'll do it with IORefs.)

The "ContT" part provides us with "shiftT" and "resetT" primitives. Together they represent the sort of delimited continuation we need for calling and returning from subroutines. To enter a scope, we do this:

\f -> do
    uniq <- liftIO $ newUnique
    rv <- callCC $ \cc -> resetT $ do
        local (\e -> e
            { envCaller = Just e
            , envCC = cc
            , envDepth = 1 + envDepth e
            , envID = uniq } ) f

That is, we populate the inner environment context with relevant information from the outer one, and run the inner evaluation (represented by "f") using an unique identifier. The upshot of this is one can freely leave() any of its parent's contexts, by passing an abnormal return value to "shiftT".

The abnormal return value contains a predicate, and we apply it to each upward context's environment, shifting past each intermediate resetT delimiters. Once it matches a context (usually by testing against its unique ID), it returns on its behalf, which is exactly what we want.

Proper use of shiftT and resetT is "safe", because they won't return from a function more than once.

On the other hand, one can "return" on behalf of any outer context by calling its "envCC", which will run until its destined end (usually end of program or eval "" -- but who knows), and then the original context is resumed again, "return"ing normally this time, resulting in one function returned twice. That is admittedly highly bizzare, but that also means we can implement our own delimited continuations in Pugs, without the constraint of shiftT/resetT above.

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.