X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Freport.git;a=blobdiff_plain;f=Core2Core.tex;h=66612e12aac7933f782bf0e219266b6ed90821d7;hp=d62807715c21bd530530fd2077cb5a285136a9f9;hb=7dad1bb3af2b675be75987956f248ceceda60a3e;hpb=aab3b545f16f854e01b60caf483093ed30749892

diff --git a/Core2Core.tex b/Core2Core.tex
index d628077..66612e1 100644
--- a/Core2Core.tex
+++ b/Core2Core.tex
@@ -1,9 +1,20 @@
 \mainlanguage [en]
 \setuppapersize[A4][A4]
 
-\setupbodyfont[10pt]
-%\usetypescript [lbr][ec]
-%\switchtotypeface [lbr] [10pt]
+% Define a custom typescript. We could also have put the \definetypeface's
+% directly in the script, without a typescript, but I guess this is more
+% elegant...
+\starttypescript[Custom]
+% This is a sans font that supports greek symbols
+\definetypeface [Custom] [ss] [sans]  [iwona]                [default]
+\definetypeface [Custom] [rm] [serif] [antykwa-torunska]     [default]
+\definetypeface [Custom] [tt] [mono]  [modern]               [default]
+\definetypeface [Custom] [mm] [math]  [modern]               [default]
+\stoptypescript
+\usetypescript [Custom]
+
+% Use our custom typeface
+\switchtotypeface [Custom] [10pt]
 
 % The function application operator, which expands to a space in math mode
 \define[1]\expr{|#1|}
@@ -25,6 +36,36 @@
   \stopframedtext
 }
 
+% Install the lambda calculus pretty-printer, as defined in pret-lam.lua.
+\installprettytype [LAM] [LAM]
+
+% An (invisible) frame to hold a lambda expression
+\define[1]\lamframe{
+        % Put a frame around lambda expressions, so they can have multiple
+        % lines and still appear inline.
+        % The align=right option really does left-alignment, but without the
+        % program will end up on a single line. The strut=no option prevents a
+        % bunch of empty space at the start of the frame.
+        \framed[offset=0mm,location=middle,strut=no,align=right,frame=off]{#1}
+}
+
+\define[2]\trans{
+        % Make \typebuffer uses the LAM pretty printer and a sans-serif font
+        % Also prevent any extra spacing above and below caused by the default
+        % before=\blank and after=\blank.
+        \setuptyping[option=LAM,style=sans,before=,after=]
+        % Prevent the arrow from ending up below the first frame (a \framed
+        % at the start of a line defaults to using vmode).
+        \dontleavehmode
+        % Put the elements in frames, so they can have multiple lines and be
+        % middle-aligned
+        \lamframe{\typebuffer[#1]}
+        \lamframe{\Rightarrow}
+        \lamframe{\typebuffer[#2]}
+        % Reset the typing settings to their defaults
+        \setuptyping[option=none,style=\tttf]
+}
+
 % A helper to print a single example in the half the page width. The example
 % text should be in a buffer whose name is given in an argument.
 %
@@ -63,7 +104,7 @@ Matthijs Kooijman
 \section{Introduction}
 As a new approach to translating Core to VHDL, we investigate a number of
 transformations on our Core program, which should bring the program into a
-well-defined "canonical" state, which is subsequently trivial to translate to
+well-defined "canonical" form, which is subsequently trivial to translate to
 VHDL.
 
 The transformations as presented here are far from complete, but are meant as
@@ -73,16 +114,16 @@ apparent from the end result, there will be additional transformations needed
 to fully reach our goal, and some transformations must be applied more than
 once. How exactly to (efficiently) do this, has not been investigated.
 
-Lastly, I hope to be able to state a number of pre- and postconditinos for
+Lastly, I hope to be able to state a number of pre- and postconditions for
 each transformation. If these can be proven for each transformation, and it
-can be shown that ther exists some ordering of transformations for which the
+can be shown that there exists some ordering of transformations for which the
 postcondition implies the canonical form, we can show that the transformations
 do indeed transform any program (probably satisfying a number of
 preconditions) to the canonical form.
 
 \section{Goal}
 The transformations described here have a well-defined goal: To bring the
-program in a well-defined program that is directly translatable to hardware,
+program in a well-defined form that is directly translatable to hardware,
 while fully preserving the semantics of the program.
 
 This {\em canonical form} is again a Core program, but with a very specific
@@ -214,14 +255,14 @@ canonical form.
     in
       case s of
         (a, b) ->
-          r = case a of
-                High -> add
-                Low -> let
-                  op' = case b of
-                    High -> sub
-                    Low  -> \c d -> c
-                  in
-                    \c d -> op' d c
+          case a of
+            High -> add
+            Low -> let
+              op' = case b of
+                High -> sub
+                Low  -> \c d -> c
+              in
+                \c d -> op' d c
 \stoptyping
 
 \subsection{Argument extraction}
@@ -422,4 +463,249 @@ non-polymorph functions can be a lot faster than generic ones).
 \item More builtin expressions should be added and these should be evaluated
 by the compiler. For example, map, fold, +.
 \stopitemize
+
+Initial example
+
+\starttyping
+  \x -> 
+    let s = foo x
+    in
+      case s of
+        (a, b) ->
+          case a of
+            High -> add
+            Low -> let
+              op' = case b of
+                High -> sub
+                Low  -> \c d -> c
+              in
+                \c d -> op' d c
+\stoptyping
+
+After top-level η-abstraction:
+
+\starttyping
+  \x c d -> 
+    (let s = foo x
+    in
+      case s of
+        (a, b) ->
+          case a of
+            High -> add
+            Low -> let
+              op' = case b of
+                High -> sub
+                Low  -> \c d -> c
+              in
+                \c d -> op' d c
+    ) c d
+\stoptyping
+
+After (extended) β-reduction:
+
+\starttyping
+  \x c d -> 
+    let s = foo x
+    in
+      case s of
+        (a, b) ->
+          case a of
+            High -> add c d
+            Low -> let
+              op' = case b of
+                High -> sub
+                Low  -> \c d -> c
+              in
+                op' d c
+\stoptyping
+
+After return value extraction:
+
+\starttyping
+  \x c d -> 
+    let s = foo x
+        r = case s of
+              (a, b) ->
+                case a of
+                  High -> add c d
+                  Low -> let
+                    op' = case b of
+                      High -> sub
+                      Low  -> \c d -> c
+                    in
+                      op' d c
+    in
+      r
+\stoptyping
+
+Scrutinee simplification does not apply.
+
+After case binder wildening:
+
+\starttyping
+  \x c d -> 
+    let s = foo x
+        a = case s of (a, _) -> a
+        b = case s of (_, b) -> b
+        r = case s of
+              (_, _) ->
+                case a of
+                  High -> add c d
+                  Low -> let
+                    op' = case b of
+                      High -> sub
+                      Low  -> \c d -> c
+                    in
+                      op' d c
+    in
+      r
+\stoptyping
+
+After case value simplification
+
+\starttyping
+  \x c d -> 
+    let s = foo x
+        a = case s of (a, _) -> a
+        b = case s of (_, b) -> b
+        r = case s of
+              (_, _) -> r'
+        rh = add c d
+        rl = let
+               rll = \c d -> c
+               op' = case b of
+                 High -> sub
+                 Low  -> rll
+               in
+                 op' d c
+        r' = case a of
+               High -> rh
+               Low -> rl
+    in
+      r
+\stoptyping
+
+After let flattening:
+
+\starttyping
+  \x c d -> 
+    let s = foo x
+        a = case s of (a, _) -> a
+        b = case s of (_, b) -> b
+        r = case s of
+              (_, _) -> r'
+        rh = add c d
+        rl = op' d c
+        rll = \c d -> c
+        op' = case b of
+          High -> sub
+          Low  -> rll
+        r' = case a of
+               High -> rh
+               Low -> rl
+    in
+      r
+\stoptyping
+
+After function inlining:
+
+\starttyping
+  \x c d -> 
+    let s = foo x
+        a = case s of (a, _) -> a
+        b = case s of (_, b) -> b
+        r = case s of
+              (_, _) -> r'
+        rh = add c d
+        rl = (case b of
+          High -> sub
+          Low  -> \c d -> c) d c
+        r' = case a of
+               High -> rh
+               Low -> rl
+    in
+      r
+\stoptyping
+
+After (extended) β-reduction again:
+
+\starttyping
+  \x c d -> 
+    let s = foo x
+        a = case s of (a, _) -> a
+        b = case s of (_, b) -> b
+        r = case s of
+              (_, _) -> r'
+        rh = add c d
+        rl = case b of
+          High -> sub d c
+          Low  -> d
+        r' = case a of
+               High -> rh
+               Low -> rl
+    in
+      r
+\stoptyping
+
+After case value simplification again:
+
+\starttyping
+  \x c d -> 
+    let s = foo x
+        a = case s of (a, _) -> a
+        b = case s of (_, b) -> b
+        r = case s of
+              (_, _) -> r'
+        rh = add c d
+        rlh = sub d c
+        rl = case b of
+          High -> rlh
+          Low  -> d
+        r' = case a of
+               High -> rh
+               Low -> rl
+    in
+      r
+\stoptyping
+
+After case removal:
+
+\starttyping
+  \x c d -> 
+    let s = foo x
+        a = case s of (a, _) -> a
+        b = case s of (_, b) -> b
+        r = r'
+        rh = add c d
+        rlh = sub d c
+        rl = case b of
+          High -> rlh
+          Low  -> d
+        r' = case a of
+               High -> rh
+               Low -> rl
+    in
+      r
+\stoptyping
+
+After let bind removal:
+
+\starttyping
+  \x c d -> 
+    let s = foo x
+        a = case s of (a, _) -> a
+        b = case s of (_, b) -> b
+        rh = add c d
+        rlh = sub d c
+        rl = case b of
+          High -> rlh
+          Low  -> d
+        r' = case a of
+               High -> rh
+               Low -> rl
+    in
+      r'
+\stoptyping
+
+Application simplification is not applicable.
 \stoptext