Add some more transformations.
[matthijs/master-project/report.git] / Core2Core.tex
index 17d0ee2..ae9c189 100644 (file)
   \stopframedtext
 }
 
-% A shortcut for italicized e.g.
+% A shortcut for italicized e.g. and i.e.
 \define[0]\eg{{\em e.g.}}
+\define[0]\ie{{\em i.e.}}
+
+\definedescription 
+  [desc]
+  [location=hanging,hang=20,width=broad]
+   %command=\hskip-1cm,margin=1cm]
 
 % Install the lambda calculus pretty-printer, as defined in pret-lam.lua.
 \installprettytype [LAM] [LAM]
@@ -403,23 +409,111 @@ arguments into normal form. The goal here is to:
    \stopitemize
 \stopitemize
 
-\subsubsection{User-defined functions}
-We can divide the arguments of a user-defined function into two
-categories:
+When looking at the arguments of a user-defined function, we can
+divide them into two categories:
 \startitemize
-  \item Runtime representable typed arguments (\eg bits or vectors).
+  \item Arguments with a runtime representable type (\eg bits or vectors).
+
+        These arguments can be preserved in the program, since they can
+        be translated to input ports later on.  However, since we can
+        only connect signals to input ports, these arguments must be
+        reduced to simple variables (for which signals will be
+        produced). This is taken care of by the argument extraction
+        transform.
   \item Non-runtime representable typed arguments.
+        
+        These arguments cannot be preserved in the program, since we
+        cannot represent them as input or output ports in the resulting
+        VHDL. To remove them, we create a specialized version of the
+        called function with these arguments filled in. This is done by
+        the argument propagation transform.
 \stopitemize
 
-The next two transformations will deal with each of these two kinds of argument respectively.
+When looking at the arguments of a builtin function, we can divide them
+into categories: 
+
+\startitemize
+  \item Arguments with a runtime representable type.
+        
+        As we have seen with user-defined functions, these arguments can
+        always be reduced to a simple variable reference, by the
+        argument extraction transform. Performing this transform for
+        builtin functions as well, means that the translation of builtin
+        functions can be limited to signal references, instead of
+        needing to support all possible expressions.
+
+  \item Arguments with a function type.
+        
+        These arguments are functions passed to higher order builtins,
+        like \lam{map} and \lam{foldl}. Since implementing these
+        functions for arbitrary function-typed expressions (\eg, lambda
+        expressions) is rather comlex, we reduce these arguments to
+        (partial applications of) global functions.
+        
+        We can still support arbitrary expressions from the user code,
+        by creating a new global function containing that expression.
+        This way, we can simply replace the argument with a reference to
+        that new function. However, since the expression can contain any
+        number of free variables we also have to include partial
+        applications in our normal form.
+
+        This category of arguments is handled by the function extraction
+        transform.
+  \item Other unrepresentable arguments.
+        
+        These arguments can take a few different forms:
+        \startdesc{Type arguments}
+          In the core language, type arguments can only take a single
+          form: A type wrapped in the Type constructor. Also, there is
+          nothing that can be done with type expressions, except for
+          applying functions to them, so we can simply leave type
+          arguments as they are.
+        \stopdesc
+        \startdesc{Dictionary arguments}
+          In the core language, dictionary arguments are used to find
+          operations operating on one of the type arguments (mostly for
+          finding class methods). Since we will not actually evaluatie
+          the function body for builtin functions and can generate
+          code for builtin functions by just looking at the type
+          arguments, these arguments can be ignored and left as they
+          are.
+        \stopdesc
+        \startdesc{Type level arguments}
+          Sometimes, we want to pass a value to a builtin function, but
+          we need to know the value at compile time. Additionally, the
+          value has an impact on the type of the function. This is
+          encoded using type-level values, where the actual value of the
+          argument is not important, but the type encodes some integer,
+          for example. Since the value is not important, the actual form
+          of the expression does not matter either and we can leave
+          these arguments as they are.
+        \stopdesc
+        \startdesc{Other arguments}
+          Technically, there is still a wide array of arguments that can
+          be passed, but does not fall into any of the above categories.
+          However, none of the supported builtin functions requires such
+          an argument. This leaves use with passing unsupported types to
+          a function, such as calling \lam{head} on a list of functions.
+
+          In these cases, it would be impossible to generate hardware
+          for such a function call anyway, so we can ignore these
+          arguments.
+
+          The only way to generate hardware for builtin functions with
+          arguments like these, is to expand the function call into an
+          equivalent core expression (\eg, expand map into a series of
+          function applications). But for now, we choose to simply not
+          support expressions like these.
+        \stopdesc
+
+        From the above, we can conclude that we can simply ignore these
+        other unrepresentable arguments and focus on the first two
+        categories instead.
+\stopitemize
 
-\subsubsubsection{Argument extraction}
-This transform deals with arguments to user-defined functions that
-are of a runtime representable type. These arguments can be preserved in
-the program, since they can be translated to input ports later on.
-However, since we can only connect signals to input ports, these
-arguments must be reduced to simple variables (for which signals will be
-produced).
+\subsubsection{Argument extraction}
+This transform deals with arguments to functions that
+are of a runtime representable type. 
 
 TODO: It seems we can map an expression to a port, not only a signal.
 Perhaps this makes this transformation not needed?
@@ -434,8 +528,6 @@ this variable.
 
 \transform{Argument extract}
 {
-\lam{X} is a (partial application of) a user-defined function
-
 \lam{Y} is of a hardware representable type
 
 \lam{Y} is not a variable referene
@@ -444,7 +536,37 @@ this variable.
 
 \trans{X Y}{let z = Y in X z}
 }
-\subsubsubsection{Argument propagation}
+
+\subsubsection{Function extraction}
+This transform deals with function-typed arguments to builtin functions.
+Since these arguments cannot be propagated, we choose to extract them
+into a new global function instead.
+
+Any free variables occuring in the extracted arguments will become
+parameters to the new global function. The original argument is replaced
+with a reference to the new function, applied to any free variables from
+the original argument.
+
+\transform{Function extraction}
+{
+\lam{X} is a (partial application of) a builtin function
+
+\lam{Y} is not an application
+
+\lam{Y} is not a variable reference
+
+\conclusion
+
+\lam{f0 ... fm} = free local vars of \lam{Y}
+
+\lam{y} is a new global variable
+
+\lam{y = λf0 ... fn.Y}
+
+\trans{X Y}{X (y f0 ... fn)}
+}
+
+\subsubsection{Argument propagation}
 This transform deals with arguments to user-defined functions that are
 not representable at runtime. This means these arguments cannot be
 preserved in the final form and most be {\em propagated}.
@@ -520,18 +642,6 @@ translatable. A user-defined function is any other function.
 TODO: The above definition looks too complicated... Can we find
 something more concise?
 
-\subsubsection{Builtin functions}
-
-argument categories:
-
-function typed
-
-type / dictionary / other
-
-hardware representable
-
-TODO
-
 \subsection{Introducing main scope}
 This transformation is meant to introduce a single let expression that will be
 the "main scope". This is the let expression as described under requirement