Tom Moertel's Blog

def my_while(cond)
  break unless cond
  yield
  retry
end

i = 0
my_while i < 10 do
  print i
  i += 1
end

# output: 0123456789

{-# OPTIONS -fglasgow-exts #-}

-- Tom Moertel <tom@moertel.com>
-- 2005-03-26

module MiniRuby where

import Control.Monad.Cont
import Control.Monad.Reader
import Control.Monad.State
import Data.List
import Data.Maybe

-- ========================================================
-- DATA TYPES

-- To keep things simple, there is only value type: string.

type Identifier = String
type Value = String

-- Evaluation occurs with in the continuation monad (which is used to
-- handle control flow), wrapped around a reader monad (which keeps
-- track of the calling context), wrapped around a state monad (which
-- keeps track of the evaluator's variables.)

type Env = [(Identifier, Value)] -- identifiers => values (strings)
type RubyEvalCxt a = ContT a (ReaderT FcallCxt (State Env)) a
data FcallCxt = FC { retryCall :: Exp
                   , blockCont :: Value -> Exp }

-- An expression is just something that can be evaluated to a value
-- within a ruby evaluation context.

type Exp = RubyEvalCxt Value

-- ========================================================
-- EVALUATOR

-- The following function evaluates an expression within a given
-- evaluation context.   The result is a value.

eval :: Env -> FcallCxt -> Exp -> Value
eval env fc =
    (`evalState` env) . (`runReaderT` fc) . (`runContT` return)

-- This version evaluates an expression at the "top level."

evalTop = eval [] $
    FC { retryCall = return "TOPLEVEL RETRY"
       , blockCont = const $ return "TOPLEVEL BLOCK" }

-- A function call takes a function, a list of variable bindings, and
-- corresponding block.  It then creates a new execution context,
-- binds the variables, and evaluates the function body.

fcall :: Exp -> [(Identifier, Exp)] -> Exp -> Exp
fcall fn args blk = callCC evalFn
  where
    evalFn fnCont = (`local` do { bindArgs; fn }) $ \fc ->
        fc { retryCall = evalFn fnCont >>= fnCont
           , blockCont = const blk }
    bindArgs = mapM_ (uncurry (=:=)) args

-- Yield remembers the current continuation and passes control to the
-- associated block (which we get from the calling context).  For
-- extra spice, this version differs from Ruby's in that upon yielding
-- it makes the yielding function seem like a block to the block to
-- which it yields.  This lets the function and block yield back and
-- forth to each other, passing values along the way.

yield_ = yield "YIELD" -- yield w/o value

yield :: Value -> Exp
yield value = callCC $ \k -> do
    bc <- asks blockCont
    local (\fc -> fc { blockCont = k }) (bc value)

-- Retry restarts the current computation w/in the calling context's
-- continuation.

retry :: Exp
retry = do
    k <- asks retryCall
    k

-- ========================================================
-- VARIABLES

-- Bind associates a value with an identifier

bind :: Identifier -> Value -> Exp
bind i v = do
    modify ((i,v) :)
    return v

-- More convenient syntax (=:=) for binding

infixr 1 =:=
class Bindable v where (=:=) :: Identifier -> v -> Exp
instance Bindable Value where (=:=) = bind
instance Bindable Exp where i =:= e = bind i =<< e

-- Lookup the value associated with an identifier

val :: Identifier -> Exp
val i = gets $ fromMaybe (i ++ "=UNDEFINED") . lookup i

-- ========================================================
-- SAMPLE CODE

-- This code shows how "retry" works.  It is equivalent
-- to the following Ruby code:
--
--   def my_while(cond)
--     if cond
--       yield
--       retry
--     end
--   end
--
--   i = 0
--   my_while i < 10 do
--     i += 1
--   end
--
--   i

test1 = do
    "i" =:= "0"
    my_while [("cond", condExp)] $
        "i" += 1 -- block, passed to my_while
    val "i"
  where
    my_while = fcall $ do
        cond <- val "cond"
        if cond == "true"
           then do { yield_; retry }
           else return cond

    -- Ruby's += operator
    a += b = a =:= (liftM $ show . (b+) . read) (val a)

    -- the expression "i < 10"
    condExp = do
        i <- val "i"
        return $ if (read i) < 10 then "true" else "false"

-- This example tests out yield.  It is equivalent to the following
-- Ruby code:
--
--   def f
--     @i = "I"
--     @k = "K"
--     yield
--   end
--
--   f do
--     @j = "J"
--     @l = "L"
--   end
--
--   [@i,@j,@k,@l].join(" ")

test2 = do
    f [] $ do
        "j" =:= "J"
        "l" =:= "L"
    mapM val (words "i j k l") >>= return . unwords
  where
    f = fcall $ do
        "i" =:= "I"
        "k" =:= "K"
        yield_

-- This sample is somewhat trickier.  It uses the evaluator's
-- extended yield semantics to do what this Ruby code would
-- do if it were legal:
--
-- def f
--   @i = "I"
--   @j = yield
--   @k = "K"
--   @l = yield "Right-back-atcha!"
--   @m = yield
-- end
--
-- f do
--   rba = yield "J-via-yield"  # not Ruby: yields *back* to f's body
--   yield rba
--   yield "M-via-yield"
-- end
--
-- [@i,@j,@k,@l,@m].join(" ")

test3 = do
    f [] $ do
        rba <- yield "J-via-yield"
        yield rba
        yield "M-via-yield"
    mapM val (words "i j k l m") >>= return . unwords
  where
    f = fcall $ do
        "i" =:= "I"
        "j" =:= yield_
        "k" =:= "K"
        "l" =:= yield "Right-back-atcha!"
        "m" =:= yield_

> evalTop test1
"10"

> evalTop test2
"I J K L"

> evalTop test3
"I J-via-yield K Right-back-atcha! M-via-yield"