[Haskell-cafe] Programming an Evaluation Context

Klaus Ostermann ostermann at informatik.tu-darmstadt.de
Wed Feb 14 19:31:58 EST 2007

Hi there,

in structural operational semantics, an evaluation context is often used to 
decompose an expression into a redex and its context. In a formal semantics on 
paper, an expression can just be "pattern matched" over the grammar of an 
evaluation context. If one wants to implement such a semantics in the form of an 
interpreter, I could not come up with a similarly nice solution. I have declared 
two separate data types (one for expressions, and one for evaluation contexts) 
and explicit functions to convert an expression into a (evaluation context, 
redex) pair.

For example, I could have

data Expr = Val Int | Plus Expr Expr


data Ctx = Hole | CPlusl Ctx Expr | CPlusr Int Expr

Are there any tricks to mimick more closely what is going on in the formal 


More information about the Haskell-Cafe mailing list