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