X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Freport.git;a=blobdiff_plain;f=Chapters%2FNormalization.tex;h=f9a10157970ad68d646a6d5948f697f516af8f23;hp=78b7a1d2e2352662fd759c495af3904b7fdd163b;hb=4b177f0eea59d8cc3e9da21a078583260d9f79c9;hpb=e1d6411fce1aecea50e986f4002c7241b88f4342

diff --git a/Chapters/Normalization.tex b/Chapters/Normalization.tex
index 78b7a1d..f9a1015 100644
--- a/Chapters/Normalization.tex
+++ b/Chapters/Normalization.tex
@@ -28,11 +28,7 @@
   core can describe expressions that do not have a direct hardware
   interpretation.
 
-  \todo{Describe core properties not supported in \VHDL, and describe how the
-  \VHDL we want to generate should look like.}
-
   \section{Normal form}
-    \todo{Refresh or refer to distinct hardware per application principle}
     The transformations described here have a well-defined goal: To bring the
     program in a well-defined form that is directly translatable to hardware,
     while fully preserving the semantics of the program. We refer to this form as
@@ -629,9 +625,11 @@
 
       In particular, we define no particular order of transformations. Since
       transformation order should not influence the resulting normal form,
-      \todo{This is not really true, but would like it to be...} this leaves
-      the implementation free to choose any application order that results in
-      an efficient implementation.
+      this leaves the implementation free to choose any application order that
+      results in an efficient implementation. Unfortunately this is not
+      entirely true for the current set of transformations. See
+      \in{section}[sec:normalization:non-determinism] for a discussion of this
+      problem.
 
       When applying a single transformation, we try to apply it to every (sub)expression
       in a function, not just the top level function body. This allows us to
@@ -641,8 +639,6 @@
       In the following sections, we will be using a number of functions and
       notations, which we will define here.
 
-      \todo{Define substitution (notation)}
-
       \subsubsection{Concepts}
         A \emph{global variable} is any variable (binder) that is bound at the
         top level of a program, or an external module. A \emph{local variable} is any
@@ -799,8 +795,34 @@
        optimizations, but they are required to get our program into intended
        normal form.
 
+        \placeintermezzo{}{
+          \defref{substitution notation}
+          \startframedtext[width=8cm,background=box,frame=no]
+          \startalignment[center]
+            {\tfa Substitution notation}
+          \stopalignment
+          \blank[medium]
+
+          In some of the transformations in this chapter, we need to perform
+          substitution on an expression. Substitution means replacing every
+          occurence of some expression (usually a variable reference) with
+          another expression.
+
+          There have been a lot of different notations used in literature for
+          specifying substitution. The notation that will be used in this report
+          is the following:
+
+          \startlambda
+            E[A=>B]
+          \stoplambda
+
+          This means expression \lam{E} with all occurences of \lam{A} replaced
+          with \lam{B}.
+          \stopframedtext
+        }
+
+      \defref{beta-reduction}
       \subsubsection[sec:normalization:beta]{β-reduction}
-        \defref{beta-reduction}
         β-reduction is a well known transformation from lambda calculus, where it is
         the main reduction step. It reduces applications of lambda abstractions,
         removing both the lambda abstraction and the application.
@@ -867,7 +889,8 @@
         This transformation is not needed to get an expression into intended
         normal form (since these bindings are part of the intended normal
         form), but makes the resulting \small{VHDL} a lot shorter.
-        
+       
+        \refdef{substitution notation}
         \starttrans
         letrec
           a0 = E0
@@ -1624,7 +1647,7 @@
         
         This propagation makes higher order values become applied (in
         particular both of the alternatives of the case now have a
-        representable type. Completely applied top level functions (like the
+        representable type). Completely applied top level functions (like the
         first alternative) are now no longer invalid (they fall under
         \in{item}[item:completeapp] above). (Completely) applied lambda
         abstractions can be removed by β-abstraction. For our example,
@@ -1799,6 +1822,7 @@
         solves (part of) the polymorphism, higher order values and
         unrepresentable literals in an expression.
 
+        \refdef{substitution notation}
         \starttrans
         letrec 
           a0 = E0
@@ -1921,7 +1945,6 @@
 
         \todo{Examples. Perhaps reference the previous sections}
 
-
   \section{Unsolved problems}
     The above system of transformations has been implemented in the prototype
     and seems to work well to compile simple and more complex examples of
@@ -1990,7 +2013,7 @@
         let y = (a * b) in y + y
         \stoplambda
 
-      \subsection{Non-determinism}
+      \subsection[sec:normalization:non-determinism]{Non-determinism}
         As an example, again consider the following expression:
 
         \startlambda