author Matthijs Kooijman Mon, 12 Oct 2009 11:15:45 +0000 (13:15 +0200) committer Matthijs Kooijman Mon, 12 Oct 2009 11:15:45 +0000 (13:15 +0200)

index fd0e2cb..7c6b469 100644 (file)
@@ -784,21 +784,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
+) 3
+\stopbuffer
+
+\startbuffer[to]
+let
+  val = 1
+in
+\stopbuffer
+
+\transexample{Application propagation for a let expression}{from}{to}
+
\starttrans
(case x of
p1 -> E1
@@ -811,35 +856,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
-) 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