Improve and clarify transformation format definition.

diff --git a/Chapters/Normalization.tex b/Chapters/Normalization.tex
index a2ccfa4c9b6111f27acf6a23d486244d1d0c7b1b..78854ac586e8901bf730287417294e3479a8a094 100644 (file)
--- a/Chapters/Normalization.tex
+++ b/Chapters/Normalization.tex
@@ -377,44 +377,232 @@ available.
 In the following sections, we will be using a number of functions and
 notations, which we will define here.
 
 In the following sections, we will be using a number of functions and
 notations, which we will define here.
 

-\subsubsection{Transformations}
-The most important notation is the one for transformation, which looks like
-the following:
+\subsubsection{Transformation notation}
+To be able to concisely present transformations, we use a specific format to
+them. It is a simple format, similar to one used in logic reasoning.
+
+Such a transformation description looks like the following.

 
 \starttrans
 
 \starttrans

-context conditions
+<context conditions>

 ~
 ~

-from
-------------------------            expression conditions
-to
+<original expression>
+--------------------------          <expression conditions>
+<transformed expresssion>

 ~
 ~

-context additions
+<context additions>
+\stoptrans
+
+This format desribes a transformation that applies to \lam{original
+expresssion} and transforms it into \lam{transformed expression}, assuming
+that all conditions apply. In this format, there are a number of placeholders
+in pointy brackets, most of which should be rather obvious in their meaning.
+Nevertheless, we will more precisely specify their meaning below:
+
+  \startdesc{<original expression>} The expression pattern that will be matched
+  against (subexpressions of) the expression to be transformed. We call this a
+  pattern, because it can contain \emph{placeholders} (variables), which match
+  any expression or binder. Any such placeholder is said to be \emph{bound} to
+  the expression it matches. It is convention to use an uppercase latter (\eg
+  \lam{M} or \lam{E} to refer to any expression (including a simple variable
+  reference) and lowercase letters (\eg \lam{v} or \lam{b}) to refer to
+  (references to) binders.
+
+  For example, the pattern \lam{a + B} will match the expression 
+  \lam{v + (2 * w)} (and bind \lam{a} to \lam{v} and \lam{B} to 
+  \lam{(2 * 2)}), but not \lam{v + (2 * w)}.
+  \stopdesc
+
+  \startdesc{<expression conditions>}
+  These are extra conditions on the expression that is matched. These
+  conditions can be used to further limit the cases in which the
+  transformation applies, in particular to prevent a transformation from
+  causing a loop with itself or another transformation.
+
+  Only if these if these conditions are \emph{all} true, this transformation
+  applies.
+  \stopdesc
+
+  \startdesc{<context conditions>}
+  These are a number of extra conditions on the context of the function. In
+  particular, these conditions can require some other top level function to be
+  present, whose value matches the pattern given here. The format of each of
+  these conditions is: \lam{binder = <pattern>}.
+
+  Typically, the binder is some placeholder bound in the \lam{<original
+  expression>}, while the pattern contains some placeholders that are used in
+  the \lam{transformed expression}.
+  
+  Only if a top level binder exists that matches each binder and pattern, this
+  transformation applies.
+  \stopdesc
+
+  \startdesc{<transformed expression>}
+  This is the expression template that is the result of the transformation. If, looking
+  at the above three items, the transformation applies, the \lam{original
+  expression} is completely replaced with the \lam{<transformed expression>}.
+  We call this a template, because it can contain placeholders, referring to
+  any placeholder bound by the \lam{<original expression>} or the
+  \lam{<context conditions>}. The resulting expression will have those
+  placeholders replaced by the values bound to them.
+
+  Any binder (lowercase) placeholder that has no value bound to it yet will be
+  bound to (and replaced with) a fresh binder.
+  \stopdesc
+
+  \startdesc{<context additions>}
+  These are templates for new functions to add to the context. This is a way
+  to have a transformation create new top level functiosn.
+
+  Each addition has the form \lam{binder = template}. As above, any
+  placeholder in the addition is replaced with the value bound to it, and any
+  binder placeholder that has no value bound to it yet will be bound to (and
+  replaced with) a fresh binder.
+  \stopdesc
+
+  As an example, we'll look at η-abstraction:
+
+\starttrans
+E                 \lam{E :: a -> b}
+--------------    \lam{E} does not occur on a function position in an application
+λx.E x            \lam{E} is not a lambda abstraction.

 \stoptrans
 
 \stoptrans
 

-Here, we describe a transformation. The most import parts are \lam{from} and
-\lam{to}, which describe the Core expresssion that should be matched and the
-expression that it should be replaced with. This matching can occur anywhere
-in function that is being normalized, so it applies to any subexpression as
-well.
+  Consider the following function, which is a fairly obvious way to specify a
+  simple ALU (Note \at{example}[ex:AddSubAlu] is the normal form of this
+  function):

 
 

-The \lam{expression conditions} list a number of conditions on the \lam{from}
-expression that must hold for the transformation to apply.
+\startlambda 
+alu :: Bit -> Word -> Word -> Word
+alu = λopcode. case opcode of
+  Low -> (+)
+  High -> (-)
+\stoplambda

 
 

-Furthermore, there is some way to look into the environment (\eg, other top
-level bindings).  The \lam{context conditions} part specifies any number of
-top level bindings that must be present for the transformation to apply.
-Usually, this lists a top level binding that binds an identfier that is also
-used in the \lam{from} expression, allowing us to "access" the value of a top
-level binding in the \lam{to} expression (\eg, for inlining).
+  There are a few subexpressions in this function to which we could possibly
+  apply the transformation. Since the pattern of the transformation is only
+  the placeholder \lam{E}, any expression will match that. Whether the
+  transformation applies to an expression is thus solely decided by the
+  conditions to the right of the transformation.

 
 

-Finally, there is a way to influence the environment. The \lam{context
-additions} part lists any number of new top level bindings that should be
-added.
+  We will look at each expression in the function in a top down manner. The
+  first expression is the entire expression the function is bound to.

 
 

-If there are no \lam{context conditions} or \lam{context additions}, they can
-be left out alltogether, along with the separator \lam{~}.
+\startlambda
+λopcode. case opcode of
+  Low -> (+)
+  High -> (-)
+\stoplambda

 
 

-TODO: Example
+  As said, the expression pattern matches this. The type of this expression is
+  \lam{Bit -> Word -> Word -> Word}, which matches \lam{a -> b} (Note that in
+  this case \lam{a = Bit} and \lam{b = Word -> Word -> Word}).
+
+  Since this expression is at top level, it does not occur at a function
+  position of an application. However, The expression is a lambda abstraction,
+  so this transformation does not apply.
+
+  The next expression we could apply this transformation to, is the body of
+  the lambda abstraction:
+
+\startlambda
+case opcode of
+  Low -> (+)
+  High -> (-)
+\stoplambda
+
+  The type of this expression is \lam{Word -> Word -> Word}, which again
+  matches \lam{a -> b}. The expression is the body of a lambda expression, so
+  it does not occur at a function position of an application. Finally, the
+  expression is not a lambda abstraction but a case expression, so all the
+  conditions match. There are no context conditions to match, so the
+  transformation applies.
+
+  By now, the placeholder \lam{E} is bound to the entire expression. The
+  placeholder \lam{x}, which occurs in the replacement template, is not bound
+  yet, so we need to generate a fresh binder for that. Let's use the binder
+  \lam{a}. This results in the following replacement expression:
+
+\startlambda
+λa.(case opcode of
+  Low -> (+)
+  High -> (-)) a
+\stoplambda
+
+  Continuing with this expression, we see that the transformation does not
+  apply again (it is a lambda expression). Next we look at the body of this
+  labmda abstraction:
+
+\startlambda
+(case opcode of
+  Low -> (+)
+  High -> (-)) a
+\stoplambda
+  
+  Here, the transformation does apply, binding \lam{E} to the entire
+  expression and \lam{x} to the fresh binder \lam{b}, resulting in the
+  replacement:
+
+\startlambda
+λb.(case opcode of
+  Low -> (+)
+  High -> (-)) a b
+\stoplambda
+
+  Again, the transformation does not apply to this lambda abstraction, so we
+  look at its body. For brevity, we'll put the case statement on one line from
+  now on.
+
+\startlambda
+(case opcode of Low -> (+); High -> (-)) a b
+\stoplambda
+
+  The type of this expression is \lam{Word}, so it does not match \lam{a -> b}
+  and the transformation does not apply. Next, we have two options for the
+  next expression to look at: The function position and argument position of
+  the application. The expression in the argument position is \lam{b}, which
+  has type \lam{Word}, so the transformation does not apply. The expression in
+  the function position is:
+
+\startlambda
+(case opcode of Low -> (+); High -> (-)) a
+\stoplambda
+
+  Obviously, the transformation does not apply here, since it occurs in
+  function position. In the same way the transformation does not apply to both
+  components of this expression (\lam{case opcode of Low -> (+); High -> (-)}
+  and \lam{a}), so we'll skip to the components of the case expression: The
+  scrutinee and both alternatives. Since the opcode is not a function, it does
+  not apply here, and we'll leave both alternatives as an exercise to the
+  reader. The final function, after all these transformations becomes:
+
+\startlambda 
+alu :: Bit -> Word -> Word -> Word
+alu = λopcode.λa.b. (case opcode of
+  Low -> λa1.λb1 (+) a1 b1
+  High -> λa2.λb2 (-) a2 b2) a b
+\stoplambda
+
+  In this case, the transformation does not apply anymore, though this might
+  not always be the case (e.g., the application of a transformation on a
+  subexpression might open up possibilities to apply the transformation
+  further up in the expression).
+
+\subsubsection{Transformation application}
+In this chapter we define a number of transformations, but how will we apply
+these? As stated before, our normal form is reached as soon as no
+transformation applies anymore. This means our application strategy is to
+simply apply any transformation that applies, and continuing to do that with
+the result of each transformation.
+
+In particular, we define no particular order of transformations. Since
+transformation order should not influence the resulting normal form (see TODO
+ref), this leaves the implementation free to choose any application order that
+results in an efficient implementation.
+
+When applying a single transformation, we try to apply it to every (sub)expression
+in a function, not just the top level function. This allows us to keep the
+transformation descriptions concise and powerful.

 
 \subsubsection{Other concepts}
 A \emph{global variable} is any variable that is bound at the
 
 \subsubsection{Other concepts}
 A \emph{global variable} is any variable that is bound at the


@@ -566,7 +754,7 @@ expression are named, by introducing lambda expressions. When combined with
 be lambda abstractions or global identifiers.
 
 \starttrans
 be lambda abstractions or global identifiers.
 
 \starttrans

-E                 \lam{E :: * -> *}
+E                 \lam{E :: a -> b}

 --------------    \lam{E} is not the first argument of an application.
 λx.E x            \lam{E} is not a lambda abstraction.
                   \lam{x} is a variable that does not occur free in \lam{E}.
 --------------    \lam{E} is not the first argument of an application.
 λx.E x            \lam{E} is not a lambda abstraction.
                   \lam{x} is a variable that does not occur free in \lam{E}.