content: \section{Recap of syntax trees with variables, |Env| and |lookup|}
  
  % removed this because it's already covered in similar ways before and after, several times.
  % Alternatively: convert to exercise.
  
  \jp{reformulate in book form (or move earlier, or remove)}
  
  This was frequently a source of confusion already the first week so
  there is already a question + answers earlier in this text.
  %
  But here is an additional example to help clarify the matter.
  %
  \begin{code}
  data Rat v = RV v | FromI Integer | RPlus (Rat v) (Rat v) | RDiv (Rat v) (Rat v)
    deriving (Eq, Show)
  
  newtype RatSem = RSem (Integer, Integer)
  \end{code}
  %
  We have a type |Rat v| for the syntax trees of rational number
  expressions (with variables of type |v|) and a type |RatSem| for the
  semantics of those rational number expressions as pairs of integers.
  %
  The constructor |RV :: v -> Rat v| is used to embed variables with
  names of type |v| in |Rat v|.
  %
  We could use |String| instead of |v| but with a type parameter |v| we
  get more flexibility at the same time as we get better feedback from
  the type-checker.
  %
  Note that this type parameter serves a different purpose from the type
  parameter in~\cref{sec:toComplexSyn}.
  
  %
  To evaluate some |e :: Rat v| we need to know how to evaluate the
  variables we encounter.
  %
  What does ``evaluate'' mean for a variable?
  %
  Well, it just means that we must be able to translate a variable name
  (of type |v|) to a semantic value (a rational number in this case).
  %
  To ``translate a name to a value'' we can use a function (of type |v
  -> RatSem|) so we can give the following implementation of the
  evaluator:
  %
  \begin{code}
  evalRat1 ::  (v -> RatSem) -> (Rat v -> RatSem)
  evalRat1 ev (RV v)       = ev v
  evalRat1 ev (FromI i)    = fromISem i
  evalRat1 ev (RPlus l r)  = plusSem  (evalRat1 ev l) (evalRat1 ev r)
  evalRat1 ev (RDiv  l r)  = divSem   (evalRat1 ev l) (evalRat1 ev r)
  \end{code}
  Notice that we simply added a parameter |ev| for ``evaluate variable''
  to the evaluator.
  %
  The rest of the definition follows a common pattern: recursively
  translate each subexpression and apply the corresponding semantic
  operation to combine the results: |RPlus| is replaced by |plusSem|,
  etc.
  %
  \begin{code}
  fromISem :: Integer -> RatSem
  fromISem i = RSem (i, 1)
  
  plusSem :: RatSem -> RatSem -> RatSem
  plusSem = undefined -- TODO: exercise
  
  -- Division of rational numbers
  divSem :: RatSem -> RatSem -> RatSem
  divSem (RSem (a, b)) (RSem (c, d)) = RSem (a*d, b*c)
  \end{code}
  
  Often the first argument |ev| to the eval function is constructed from
  a list of pairs:
  %
  \begin{code}
  type Env v s = [(v, s)]
  
  envToFun :: (Show v, Eq v) => Env v s -> (v -> s)
  envToFun [] v = error ("envToFun: variable "++ show v ++" not found")
  envToFun ((w,s):env) v
    | w == v     = s
    | otherwise  = envToFun env v
  \end{code}
  %
  Thus, |Env v s| can be seen as an implementation of a ``lookup
  table''.
  %
  It could also be implemented using hash tables or binary search trees,
  but efficiency is not the point here.
  %
  Finally, with |envToFun| in our hands we can implement a second
  version of the evaluator:
  %
  \begin{code}
  evalRat2 :: (Show v, Eq v) => (Env v RatSem) -> (Rat v -> RatSem)
  evalRat2 env e = evalRat1 (envToFun env) e
  \end{code}
  