Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Rewriting code with continuations

I have some code that evaluates primitive programs. Program is a list of statements (expression, block, return statement). Result of evaluation is last evaluated expression. Also evaluator should properly treat return statement (i.e. stop evaluation after first occurrence of return).

To implement this logic I pass special callback function (NextStep) which make next evaluating step after current statement. I don't call next step when handling return statement:

data Statement = 
      Expr Int
    | Block [Statement]
    | Return Int
    deriving (Show, Eq)

data Value = 
      Undefined
    | Value Int
    deriving (Show, Eq)

type NextStep = Value -> Value

evalStmt :: Statement -> NextStep -> Value
evalStmt (Expr val) next = 
    let res = Value val
    in next res
evalStmt (Block stmts) next = evalBlock stmts next
evalStmt (Return val) next = Value val

evalBlock :: [Statement] -> NextStep -> Value
evalBlock [] next = next Undefined
evalBlock [st] next = evalStmt st next
evalBlock (st:rest) next = evalStmt st $ \ _ -> evalBlock rest next

evalProgram stmts = evalBlock stmts id

prog1 = [Expr 1, Block [Return 3, Expr 2], Expr 4] 
evalProg1 = evalProgram prog1 -- result will be Value 3

The question is how can I rewrite this code with continuation monad? I want to get rid of explicitly passed NextStep callback in evalStmt and evalBlock functions. Is it possible?

like image 428
sergeyz Avatar asked May 11 '14 14:05

sergeyz


People also ask

What is a continuation functional programming?

A continuation is a callback function k that represents the current state of the program's execution. More precisely, the continuation k is a function of one argument, namely the value that has been computed so far, that returns the final value of the computation after the rest of the program has run to completion.

Why use continuation passing style?

Continuation passing style makes the control flow of programs more explicit as every procedure has the power to change the execution of the remainder of the program, contrast this to the traditional model in which procedures have no control over the behavior of the program once they return to their caller.

What is a continuation CS?

In computer science, a continuation is an abstract representation of the control state of a computer program.

What does continuation passing style give you that tail recursion does not?

Continuation-Passing-Style, Tail Recursion, and Efficiency is not tail recursive, because the recursive call fact(n-1) is not the last thing the function does before returning. Instead, the function waits for the result of the recursive call, then multiples that by the value of n.


1 Answers

The translation is fairly mechanical.

Keep in mind that in the continuation monad, return feeds the value into the continuation.

evalStmt :: Statement -> Cont Value Value
evalStmt (Expr val) = 
    let res = Value val
    in return res
evalStmt (Block stmts) = evalBlock stmts
evalStmt (Return val) = cont $ \_ -> Value val

evalBlock :: [Statement] -> Cont Value Value
evalBlock [] = return Undefined
evalBlock [st] = evalStmt st
evalBlock (st:rest) = evalStmt st >> evalBlock rest

evalProgram :: [Statement] -> Value
evalProgram stmts = runCont (evalBlock stmts) id

And to simulate early returns, we just ignore the continuation given to Return val and just return the value we have.

like image 196
Daniel Gratzer Avatar answered Oct 20 '22 00:10

Daniel Gratzer