X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Freport.git;a=blobdiff_plain;f=Chapters%2FNormalization.tex;h=b74333ae103c15d51b08fa37cc708cc7c3f1503b;hp=fd0e2cb294a074dd2a101a62fdb68f47a2ea057d;hb=4a7110a98633822b54a94f2333e6713b27aa9710;hpb=a9c202b10658a4993aae80b8fc986da14c6fe19e

diff --git a/Chapters/Normalization.tex b/Chapters/Normalization.tex
index fd0e2cb..b74333a 100644
--- a/Chapters/Normalization.tex
+++ b/Chapters/Normalization.tex
@@ -15,10 +15,6 @@
 }
 
 
-% A transformation example
-\definefloat[example][examples]
-\setupcaption[example][location=top] % Put captions on top
-
 \define[3]\transexample{
   \placeexample[here]{#1}
   \startcombination[2*1]
@@ -784,21 +780,66 @@ foo = λa.λx.(case a of
 
 \transexample{η-abstraction}{from}{to}
 
-\subsection{Extended β-reduction}
+\subsection{β-reduction}
+β-reduction is a well known transformation from lambda calculus, where it is
+the main reduction step. It reduces applications of labmda abstractions,
+removing both the lambda abstraction and the application.
+
+In our transformation system, this step helps to remove unwanted lambda
+abstractions (basically all but the ones at the top level). Other
+transformations (application propagation, non-representable inlining) make
+sure that most lambda abstractions will eventually be reducable by
+β-reduction.
+
+TODO: Define substitution syntax
+
+\starttrans
+(λx.E) M
+-----------------
+E[M/x]
+\stoptrans
+
+% And an example
+\startbuffer[from]
+(λa. 2 * a) (2 * b)
+\stopbuffer
+
+\startbuffer[to]
+2 * (2 * b)
+\stopbuffer
+
+\transexample{β-reduction}{from}{to}
+
+\subsection{Application propagation}
 This transformation is meant to propagate application expressions downwards
-into expressions as far as possible. In lambda calculus, this reduction
-is known as β-reduction, but it is of course only defined for
-applications of lambda abstractions. We extend this reduction to also
-work for the rest of core (case and let expressions).
+into expressions as far as possible. This allows partial applications inside
+expressions to become fully applied and exposes new transformation
+possibilities for other transformations (like β-reduction).
 
-For let expressions:
 \starttrans
 let binds in E) M
 -----------------
 let binds in E M
 \stoptrans
 
-For case statements:
+% And an example
+\startbuffer[from]
+( let 
+    val = 1
+  in 
+    add val
+) 3
+\stopbuffer
+
+\startbuffer[to]
+let 
+  val = 1
+in 
+  add val 3
+\stopbuffer
+
+\transexample{Application propagation for a let expression}{from}{to}
+
 \starttrans
 (case x of
   p1 -> E1
@@ -811,35 +852,21 @@ case x of
   pn -> En M
 \stoptrans
 
-For lambda expressions:
-\starttrans
-(λx.E) M
------------------
-E[M/x]
-\stoptrans
-
 % And an example
 \startbuffer[from]
-( let a = (case x of 
-            True -> id
-            False -> neg
-          ) 1
-      b = (let y = 3 in add y) 2
-  in
-    (λz.add 1 z)
-) 3
+( case x of 
+    True -> id
+    False -> neg
+) 1
 \stopbuffer
 
 \startbuffer[to]
-let a = case x of 
-           True -> id 1
-           False -> neg 1
-    b = let y = 3 in add y 2
-in
-  add 1 3
+case x of 
+  True -> id 1
+  False -> neg 1
 \stopbuffer
 
-\transexample{Extended β-reduction}{from}{to}
+\transexample{Application propagation for a case expression}{from}{to}
 
 \subsection{Let derecursification}
 This transformation is meant to make lets non-recursive whenever possible.
@@ -855,7 +882,7 @@ in scope for the function return value).
 Note that this transformation does not try to be smart when faced with
 recursive lets, it will just leave the lets recursive (possibly joining a
 recursive and non-recursive let into a single recursive let). The let
-rederursification transformation will do this instead.
+rederecursification transformation will do this instead.
 
 \starttrans
 letnonrec x = (let bindings in M) in N