5/30/2011

A more serious online partial evaluator

Admittedly, the illustrative partial evaluator of the previous blog post was quite limited. Consider, for example, the following attempts of partially evaluating different applications of the exponentiation function; the last attempt diverges:


> peval (lib, (Apply "exp" [Const 2, Const 3]))
Const 8

> peval (lib, (Apply "exp" [Var "x", Const 3]))
Binary Times (Var "x") (Binary Times (Var "x") (Binary Times (Var "x")(Const 1)))

> peval (lib, (Apply "exp" [Const 2, Var "n"]))
IfZero (Var "n") (Const 1) (Binary Times (Const 2) (IfZero (Binary Plus (Var "n") (Const (-1))) (Const 1) (Binary Times (Const 2) (IfZero (Binary Plus (Binary Plus (Var "n") (Const (-1))) (Const (-1))) (Const 1) (Binary Times (Const 2) (IfZero (Binary Plus (Binary Plus (Binary Plus (Var "n") (Const (-1))) (Const (-1))) (Const (-1))) (Const 1) (Binary Times (Const 2) (IfZero (Binary Plus (Binary Plus (Binary Plus (Binary Plus (Var "n") (Const (-1))) (Const (-1))) (Const (-1))) (Const (-1))) (Const 1) (Binary Times (Const 2) (IfZero ...


In the first attempt, we partially evaluate a ground term, which is as if we were using the regular interpreter. In the second attempt, we leave the base parametric, but we fix the exponent. In the third attempt, it is the other way around: we fix the base, but we leave the exponent parametric. The divergence for the third attempt is clearly undesirable. Ideally, partial evaluation of a non-ground term t should terminate whenever there is an ground instance t' of t such that regular evaluation terminates for t'. Otherwise, we could never be sure whether we can safely decompose a computation into partial evaluation followed by evaluation of the residual program.

So let us develop a more advanced partial evaluator:


peval :: Prog -> (Expr, FEnv)


The result type has changed. In addition to a transformed main expression, we also expect to obtain specialized function definitions as they are encountered by partial evaluation. That is, function definitions are specialized by statically known argument values. A demo helps:


> peval (lib, (Apply "exp" [Var "x", Const 3]))
( Apply "exp_[(n,3)]" [Var "x"],
[("exp_[(n,3)]", (["x"], Apply "times" [Var "x",Apply "exp_[(n,2)]" [Var "x"]])),
("exp_[(n,2)]", (["x"], Apply "times" [Var "x",Apply "exp_[(n,1)]" [Var "x"]])),
("exp_[(n,1)]", (["x"], Apply "times" [Var "x",Apply "exp_[(n,0)]" [Var "x"]])),
("exp_[(n,0)]", (["x"], Const 1))])


Thus, specialized function definitions were inferred for all the inductively encountered values for the exponent. Subject to a simple inlining optimization (which is not shown here for brevity but included into the open-source repository), we obtain the familiar expression for "x" to the power 3:


Apply "times" [Var "x",Apply "times" [Var "x",Apply "times" [Var "x",Const 1]]]


The partial evaluator commences as follows:


peval :: Prog -> (Expr, FEnv)
peval (fe,m) = runState (peval' m []) []
where
peval' :: Expr -> VEnv -> State FEnv Expr


That is, the expression-level partial evaluation function starts from the empty variable environment and it uses the state monad to aggregate specialized function definitions, starting also from the empty list. The type of variable environments is the same as in the original interpreter:


type VEnv = [(String,Int)]


The cases for all constructs but function application can be adopted from the simpler partial evaluator--except that we need to convert to monadic style:


peval' :: Expr -> VEnv -> State FEnv Expr
peval' (Const i) ve = return (Const i)
peval' (Var x) ve
= return (case lookup x ve of
Just v -> Const v
Nothing -> Var x)
peval' (Binary op e1 e2) ve
= do
e1' <- peval' e1 ve
e2' <- peval' e2 ve
return (case (e1', e2') of
(Const v1, Const v2) -> Const (op2f op v1 v2)
_ -> Binary op e1' e2')
peval' (IfZero e1 e2 e3) ve
= do
e1' <- peval' e1 ve
case e1' of
(Const v1) -> if (v1==0) then r2 else r3
_ -> r2 >>= \e2' -> r3 >>= \e3' -> return (IfZero e1' e2' e3')
where
r2 = peval' e2 ve
r3 = peval' e3 ve


The deviating and complicated and interesting case is the one for function application. We prepare this development by an informal specification. (Thanks again to William Cook for teaching me on this part.) The following specification relies on two important terms used in partial evaluation. That is, when partial evaluation encounters a function application with a value (say, a constant---as opposed to an expression) for a given argument position, then this position (or the associated variable) is called static; otherwise, it is called dynamic. The specification follows.

1. The applied function is looked up. 2. The arguments of the function application are partially evaluated. 3. The arguments are partitioned into static and dynamic ones. 4. The specialized function name consists of the original function name qualified by the static arguments. 5. The body of the specialized funtion is obtained by partially evaluating the original body in the variable envrironment of the static variables. 6. An application of the specialized function is constructed from the dynamic arguments. This is the result of partial evaluation.

The following function definition clarifies the step of partitioning the partially evaluated arguments (see 3. above). One list of
expressions is partioned into two lists of static versus dynamic arguments qualified by the formal argument names. Static arguments are Const expressions. Dynamic arguments are all other expressions. Thus:


partition [] [] = ([],[])
partition (n:ns) (Const i:es)
= ((n,i):ss,ds) where (ss,ds) = partition ns es
partition (n:ns) (e:es)
= (ss,(n,e):ds) where (ss,ds) = partition ns es


The following equation for function applications implements the afore-mentioned steps 1.-6., but additional details
arise. In order to deal with recursion, it is important that the specialized function is already added to the state before its body is
obtained. To this end, an undefined body is preliminarily associated with the new name, which is replaced later; see get, put, get, put. Furher, we need to distunguish function applications that are fully static from those that involve dynamic arguments because fully static function applications should not be specialized; instead, they should be evaluated.

Here are the glory details:


peval' (Apply n es) ve
= do
-- Look up function
let (ns,e) = fromJust (lookup n fe)

-- Partially evaluate arguments
es' <- mapM (flip peval' ve) es

-- Partition arguments into static and dynamic ones
let (ss,ds) = partition ns es'

case (null ss, null ds) of

-- A constant application
(True, True) -> peval' e []

-- A fully static application
(False, True) -> peval' e ss

-- A fully dynamic application
(True, False) -> return (Apply n es')

-- A mixed static application
(False, False) -> (do

-- The name that encodes the static values
let n' = n ++ "_" ++ myshowl ss

-- Construct application of specialized function
let e' = Apply n' (map snd ds)

-- See whether the specialization exists already
fe <- get
case lookup n' fe of
Just _ -> return e'
Nothing -> (do

-- Memo before possible recursion
put (fe++[(n',undefined)])

-- Partial evaluation of function body
e'' <- peval' e ss

-- Record definition of specialized function
fe' <- get
put (update (const (map fst ds,e'')) n' fe')

-- Return application of specialized function
return e'))


So much for partial evaluation.

Regards,
PF

PS: The source code of this blog post is available through the repository of the Software Language Processing Suite; see here.

5/27/2011

An illustrative online partial evaluator

Let's understand the basic mechanics of a (too?) simple online partial evaluator. (I am grateful to William Cook for encouraging the following Haskell exercise, and for sharing with me some stimulating slides and notes on the subject.) I recommend John Hatcliff's excellent and detailed course material on "Foundations of Partial Evaluation and Program Specialization"---available online. For those in a hurry, try Wikipedia. Anyway, partial evaluation, macro systems, and multi-stage programming is a lot of fun. Here is also a paper (draft) by William Cook that I can warmly recommend.

Consider the following syntax of a simple, pure, first-order, functional programming language:


type Prog = (FEnv,Expr)
type FEnv = [FDef]
type FDef = (String,([String],Expr))

data Expr
= Const Int
| Var String
| Binary Op Expr Expr
| IfZero Expr Expr Expr
| Apply String [Expr]
deriving (Show)

data Op = Plus | Times
deriving (Show)


Thus, a program consists of a main expression and bindings for functions (i.e., a "function environment" FEnv is a list of "function definitions" FDef each of them being of term form (s,(ss,e)) with s as the function name, ss the formal parameters and e the body). Evaluation of an expression is supposed to return an integer (or to diverge or to fail in reply to a dynamic type error). The functions are supposed to be of first-order: functions are neither passed as arguments, nor returned as results.

Here are some function definitions---including those for factorial and exponentiation:


lib :: FEnv
lib
= [ ("neg", (["x"], Binary Times (Var "x") (Const (-1)))),
("add", (["x", "y"], Binary Plus (Var "x") (Var "y"))),
("minus", (["x", "y"], Binary Plus (Var "x") (Apply "neg" [Var "y"]))),
("times", (["x", "y"], Binary Times (Var "x") (Var "y"))),
("inc", (["x"], Binary Plus (Var "x") (Const 1))),
("dec", (["x"], Binary Plus (Var "x") (Const (-1)))),

("fac",
( ["x"]
, IfZero (Var "x")
(Const 1)
(Apply "times" [Var "x", Apply "fac" [Apply "dec" [Var "x"]]]))),

("exp",
( ["x","n"]
, IfZero (Var "n")
(Const 1)
(Apply "times" [Var "x", Apply "exp" [Var "x", Apply "dec" [Var "n"]]])))]


Let's first develop a straightforward interpreter.

We expect interpretation to behave as follows:


> eval (lib, Apply "fac" [Const 5])
120
> eval (lib, Apply "exp" [Const 2, Const 3])
8


Here is the complete interpreter:


type VEnv = [(String,Int)]

eval :: Prog -> Int
eval (fe,m) = eval' m []
where
eval' :: Expr -> VEnv -> Int
eval' (Const i) ve = i
eval' (Var x) ve = fromJust (lookup x ve)
eval' (Binary op e1 e2) ve = f v1 v2
where
f = op2f op
v1 = eval' e1 ve
v2 = eval' e2 ve
eval' (IfZero e1 e2 e3) ve = if (v1==0) then v2 else v3
where
v1 = eval' e1 ve
v2 = eval' e2 ve
v3 = eval' e3 ve
eval' (Apply n es) ve = eval' e ve'
where
(ns,e) = fromJust (lookup n fe)
vs = map (\e -> eval' e ve) es
ve' = zip ns vs

op2f :: Op -> (Int -> Int -> Int)
op2f Plus = (+)
op2f Times = (*)


It must be emphasized that this interpreter is in no way special, unusual, or targeted at partial evaluation. One gets this interpreter naturally when using denotational semantics (i.e., compositional functional semantics) as the guiding principle. Now the key "challenge" of our effort here is to modify the interpreter so that it effectively serves as a partial evaluator. That is, the partial evaluator should produce the same result as the interpreter when faced with a ground main expression, but it should compute a residual expression otherwise. Let's think of the residual expression as the "rest of the program" that needs to be evaluated once the free variables are bound to values. For instance:


> peval (lib, Apply "exp" [Var "x", Const 3])
Binary Times (Var "x") (Binary Times (Var "x") (Binary Times (Var "x") (Const 1)))


Thus, the function "exp" is applied to a specific exponent 3, but the base remains a variable "x", and the result of partial evaluation essentially represents the code to compute "x" to the power 3: "x*x*x*1".

Our design of a partial evaluator starts from the insight that the type of the top-level function must be changed so that expressions are returned instead of integers. (A more general design would also return any number of bindings for specialized functions that were encountered along partial evaluation.) Please note that integers are trivially embedded into expressions through the constant form of expressions. Thus:


-- Interpreter
eval :: Prog -> Int
eval (fe,m) = eval' m []
where
...

-- Partial evaluator
peval :: Prog -> Expr
peval (fe,m) = peval' m []
where
...


In the chosen style of partial evaluator design, we also propagate the type change into the definition of variable environments. (This leads to a simple development, but implies some issues as we will discuss towards the end of the blog post.) Thus, variables may be bound to (free) variables:


-- Interpreter
type VEnv = [(String,Int)]

-- Partial evaluator
type VEnv = [(String,Expr)]


The cases for constant expressions differ trivially only as follows:


-- Interpreter
eval' :: Expr -> VEnv -> Int
eval' (Const i) ve = i

-- Partial evaluator
peval' :: Expr -> VEnv -> Expr
peval' (Const i) ve = Const i


Variables are to be treated in a special manner. The interpreter can only deal with ground main expressions, and---subject to other reasonable assumptions about well-typedness of programs---variables would always be bound throughout interpretation. In contrast, the partial evaluator faithfully deals with free variables: a free variable is partially evaluated to itself.


-- Interpreter
eval' (Var x) ve = fromJust (lookup x ve)

-- Partial evaluator
peval' (Var x) ve
= case lookup x ve of
Just e -> e
Nothing -> Var x


Compound expression forms are also affected non-trivially but systematically. The general idea is that an expression form may be evaluated if some or all operands can be, in turn, partially evaluated to values, or the expression form may need to be re-generated in the result otherwise. Consider the following cases for binary expressions:


-- Interpreter
eval' (Binary op e1 e2) ve = f v1 v2
where
f = op2f op
v1 = eval' e1 ve
v2 = eval' e2 ve

-- Partial evaluator
peval' (Binary op e1 e2) ve
= case (e1', e2') of
(Const v1, Const v2) -> Const (f v1 v2)
_ -> Binary op e1' e2'
where
f = op2f op
e1' = peval' e1 ve
e2' = peval' e2 ve


Thus, in the interpreter, subexpressions are recursively evaluated, and the corresponding operator is applied to the intermediate results. Subexpressions are also recursively evaluated in the partial evaluator, but the intermediate results are to be checked this time such that the operator is applied for the case of value results (constants). Otherwise, a binary expression is generated which incorporates partially evaluated operands as opposed to the original operand expressions.

The same idea is applied to the IsZero construct:


-- Interpreter
eval' (IfZero e1 e2 e3) ve = if (v1==0) then v2 else v3
where
v1 = eval' e1 ve
v2 = eval' e2 ve
v3 = eval' e3 ve

-- Partial evaluator
peval' (IfZero e1 e2 e3) ve
= case e1' of
(Const v1) -> if (v1==0) then e2' else e3'
_ -> IfZero e1' e2' e3'
where
e1' = peval' e1 ve
e2' = peval' e2 ve
e3' = peval' e3 ve


The pleasant status of IfZero is that it is enough to partially evaluate the condition to a value in order to be able to eliminate the conditional form.

Perhaps surprisingly, the cases for function application can be identical (modulo renaming):


-- Interpreter
eval' (Apply n es) ve = eval' e ve'
where
(ns,e) = fromJust (lookup n fe)
vs = map (\e -> eval' e ve) es
ve' = zip ns vs

-- Partial evaluator
peval' (Apply n es) ve = peval' e ve'
where
(ns,e) = fromJust (lookup n fe)
es' = map (\e -> peval' e ve) es
ve' = zip ns es'


In both cases, we look up the function from the function environment, we bind (partially) evaluated actual parameters to the formal parameter variables, and we proceed with the (partial) evaluation of the function's body relative to the local environment.

Exercise: Is there any issue of variable capture with the partial evaluator at hand? Can you demonstrate a problem? How would you generally rule out variable capture? Further, can you think of situations where the partial evaluator clones too much code or where it even loops, even though a non-cloning and non-looping partial evaluator would be desirable and feasible, perhaps subject to some form of memoization?

The source code of this blog post is available in the repository for the Software Language Processing Suite; see here. You would also find a not so simple partial evaluator discussed in the next blog post.

Regards,
PF

5/14/2011

Empirical studies of software languages

Dear language researchers and engineers,

if you were interested in empirical studies of software languages, what journals and conferences come to your mind as potential publication venues for such studies? In different terms, what do you think what quality journals and conferences would be popping up if you were googling (binging) intelligently for empirical studies of programming languages, modeling languages, domain-specific languages, and other software languages you can think of?

Please send your ideas by email to rlaemmel@acm.org by 19 May.

The results of this inquiry will be published while preserving anonymity of all participants.

Thanks!
Professor Fish

PS1: The reason for asking is that we are into a meta-empirical effort, continuing our SLE 2010 paper "Empirical language analysis in software linguistics" (Jean-Marie Favre and Dragan Gasevic and Ralf Lämmel and Ekaterina Pek). We are going to use content analysis, where we aim for automation for data mining to the extent possible, but substantial manual efforts remain. Therefore, scalability is limited, and we would like to narrow down the search space for relevant publications by using a short list of journals and conferences, but, at the same time, remaining transparent about what we use. So please, in the interest of science, send your journal and conference acronyms.

PS2: Please understand that I do not include any journals and conferences that are already on our mind. I do not want to bias you in any way. This is also the reason for disabling comments on this post.

5/08/2011

Language processing for dummies

I enjoyed reading recently "Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages" by Terence Parr (the ANTLR guy) as available from The Pragmatic Bookshelf. The book uses a design pattern style to present techniques for language processing. Eventually the book gets to leverage ANTLR for many problems, but it also explains language processing in terms of patterns that require regular programming effort without the help of a program generator. This is a clever way of teaching some basics of grammars, parsing, tree walking and other concepts that can be explained all too easily (elsewhere) in a too complicated manner, or in a manner requiring substantial background.

In my (very) advanced Bachelor's course Programming techniques and technologies, I face students who don't know much yet about formal languages and certainly nothing about compiler construction; they are aware though of context-free grammars (EBNFs) for the purpose of syntax definition. The course covers many programming techniques and technologies, and I am willing to dedicate two lectures to language processing. Hence, I designed patterns that are really simple and that allow me to discuss a number of language processors for 101companies in a systematic manner.

"Manual" patterns
  • The Chopper Pattern: Chop input into pieces for classification and iterator-based processing.
  • The Lexer Pattern: Transform character stream into token stream for iterator-based processing.
  • The Copy/Replace Pattern: Implement text transformation by copying tokens from input to output while replacing tokens of interest.
  • The Acceptor Pattern: Implement a context-free grammar with procedures for parsing input and signaling acceptance or rejection.
  • The Parser Pattern: Advance the Acceptor Pattern such that semantic actions are to be executed along with parsing input.

"Generative" patterns
  • The Lexer Generation Pattern: Use a lexer/parser generator to derive a character-to-token stream conversion from a grammar generatively.
  • The Acceptor Generation Pattern: Use a parser generator to derive an acceptor from a grammar generatively.
  • The Parser Generation Pattern: Use a parser generator to derive an parser from a grammar with associated semantic actions generatively.
  • The Text-to-object Pattern: Instantiate the Parser (Generation) Pattern such that the semantic actions construct objects that resemble the syntactical structure of the input.
  • The Object-to-text Pattern: Implement an operation on an object model that writes out the object graph in the underlying textual notation.

Associated 101companies implementations

Slide decks (.pdf): [1]. [2]

Lecture videos (.mov): [1]. [2]

Regards,
PF

5/05/2011

A tiny attribute grammar exercise

(C) 2011, Ralf Laemmel

Let's map Knuth' attribute grammar example to Haskell. This has been done many times. In fact, there is a long track of excellent research on the relation between attribute grammars and functional programming. For instance, see the work by Doaitse Swierstra and team over many years. Our development here is meant to just illustrate the basic mapping in an as simple and self-contained manner as possible.

One should notice that the chosen example (due to Knuth) requires laziness for the straightforward encoding that is leveraged
below. Hence, C programmers are encouraged to try to transcribe this Haskell program to their favorite language.

The following context-free grammar is assumed:


digit : '0'
digit : '1'
digits : digit
digits : digits digit
number : digits
number : digits '.' digits


That is, we deal with binary numbers---both integer and fractional numbers.

We use the following algebraic datatypes to model the grammar:


data Digit = Zero | One
data Digits = Single Digit | Several Digits Digit
data Number = Int Digits | Frac Digits Digits


Let us now associate attributes with the nonterminals:


* digit:
- inh. p -- position of digit
- syn. v -- value of digit
* digits:
- inh. p -- position of digits
- syn. v -- value of digits
- syn. l -- length of digits
* number:
- syn. v -- value of number


In Haskell, we can introduce designated type aliases to capture the names of the attributes, and the association of nonterminals with attributes is modeled with the signatures for functions that are expected to model the semantic equations. (We could also use record types, but Haskell's record system is not quite convenient in this context.) Here, the assumption is that those functions carry one argument for the syntactial part, another argument for (the tuple of) the inherited attributes, and the result corresponds to (the tuple of) the synthesized attributes. Thus:


-- Type synonyms for attributes
type Val = Float
type Pos = Int
type Len = Int

-- Functions for semantic equations
digit :: Digit -> Pos -> Val
digits :: Digits -> Pos -> (Val,Len)
number :: Number -> Val


Here are the semantic equations for the example:


digit : '0'
v.digit = 0

digit : '1'
v.digit = 2^^p.digit

digits : digit
v.digits = v.digit
l.digits = 1
p.digit = p.digits

digits : digits' digit
v.digits = v.digits' + v.digit
p.digit = p.digits
p.digits' = p.digits + 1
l.digits = l.digits' + 1

number : digits
v.number = v.digits
p.digits = 0

number : digits '.' digits'
v.number = v.digits + v.digits'
p.digits = 0
p.digits' = -l.digits'


We implement these semantic equations as equations defining the functions from syntax times inherited attributes to synthesized attributes.


digit Zero _ = 0
digit One p = 2^^p

digits (Single d) p = (digit d p,1)
digits (Several ds d) p = (v,l)
where
v = v' + v''
l = l' + 1
(v',l') = digits ds (p+1)
v'' = digit d p

number (Int ds) = fst (digits ds 0)
number (Frac ds1 ds2) = v1+v2
where
(v1,l1) = digits ds1 0
(v2,l2) = digits ds2 (-l2)


Let us evaluate 10.01.


main = do print (number n)
where
n = Frac ds ds'
ds = Several (Single One) Zero
ds' = Several (Single Zero) One

> main
2.25


Regards,
Prof. Fisch