% portableTracer.tex

% Author: Olaf Chitil
% Created: 14.8.2000
% Last Update: 
  
\documentclass[12pt]{article}
\usepackage{pst-node}
\usepackage[a4paper]{geometry}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{alltt}
\usepackage{url}

%------------------------------------------------------------------------------

\begin{document}
\thispagestyle{empty}

\title{ART Memo 9 (Version 2)\\Towards a Portable Tracer} 
\author{Olaf Chitil}
\date{\today}
\maketitle


%------------------------------------------------------------------------------

\tableofcontents

%------------------------------------------------------------------------------

\section{Introduction}

The Hat viewers are separate programs, but
the Hat transformation is still integrated into nhc.
Here we collect some ideas about how a separate transformation can yield Haskell programs that can be compiled with other Haskell compilers.
Advantages are:

\begin{itemize}
\item More users $\Rightarrow$ more permanence.
\item An optimising Haskell compiler such as ghc can produce better (especially faster) code.
\item The obtained modularity may improve the understanding of tracing further. The trace generating program is a complete and standard Haskell program. The transformation relates it to the original Haskell program and its semantics relates it to the ART trace.
\end{itemize}

Note that the separate transformation will not lead to supporting Haskell extensions implemented by various Haskell compilers. It might facilitate such extensions, because only the transformation but not the back end of nhc need to be modified for any such extension.

The transformed Haskell modules will use a library of support functions, which include C-functions accessed via the FFI. The library should be implementation independent.


%------------------------------------------------------------------------------

\section{Details of Issues}

Here we enumerate how the Hat transformation and nhc are currently intertwined and the problems we have to solve for separating the two. 


\subsection{An Example for the Current State}

For the program

\begin{alltt}
insert :: Ord a => a -> [a] -> [a]

insert x [] = [x]
insert x (y:ys)
  | x > y = x : insert x ys
  | otherwise = x : y : ys

sort xs = foldr insert [] xs

main = print (sort [3,2,1])
\end{alltt}

we can obtain with the options \texttt{-tracefns} \texttt{-noshowqualified} the following result:

\begin{alltt}
insert ::
  Ord t1 =>
  SR -> Trace -> R (Trace -> (R t1) -> R (Trace -> (R [t1]) -> R [t1]))

insert v346 v345 =
  fun2 (mkNTId' 337) Main.insert_347 v346 v345
  where
  
  Main.insert_347 v348 v340 (R ([]) v351) =
    con2 (mkSR' 2) v348 (:) (mkNTConstr' 311) v340
      (con0 (mkSR' 2) v348 ([]) (mkNTConstr' 310))
  Main.insert_347 v348 v341 (R (v342 : v343) v352) =
    case ap2 (mkSR' 7) v348 ((mkSR' 7) > v348) v341 v342 of
      R v357 v358 ->
        let
          v353 =
            mkTAp2 v348 (mkTNm v348 mkNTGuard (mkSR' 10)) v358 v348 (mkSR' 10)
          in
          (myseq v353
            (if v357
              then con2 (mkSR' 9) v353 (:) (mkNTConstr' 311) v341
                (ap2 (mkSR' 8) v353 (insert (mkSR' 8) v353) v341 v343)
              else case otherwise (mkSR' 3) v353 of
                R v355 v356 ->
                  let
                    v354 =
                      mkTAp2 v353 (mkTNm v353 mkNTGuard (mkSR' 6)) v356 v353
                        (mkSR' 6) in
                    (myseq v354
                      (if v355
                        then con2 (mkSR' 5) v354 (:) (mkNTConstr' 311) v341
                          (con2 (mkSR' 4) v354 (:) (mkNTConstr' 311) v342 v343)
                        else fatal v354))))
  Main.insert_347 v348 _ _ =
    fatal v348
  

sort v360 v359 =
  fun1 (mkNTId' 338) Main.sort_361 v360 v359
  where
  
  Main.sort_361 v362 v344 =
    rap3 (mkSR' 11) v362 (foldr (mkSR' 11) v362) (insert (mkSR' 12) v362)
      (con0 (mkSR' 13) v362 ([]) (mkNTConstr' 310)) v344
  Main.sort_361 v362 _ =
    fatal v362
  

main _ _ =
  Main.main_365

Main.main_365 =
  lazySat
    (rap1 (mkSR' 14) nt_364 (print (mkSR' 14) nt_364)
      (ap1 (mkSR' 15) nt_364 (sort (mkSR' 15) nt_364)
        (con2 (mkSR' 19) nt_364 (:) (mkNTConstr' 311)
          (fromConInteger (mkSR' 16) nt_364 3L)
          (con2 (mkSR' 19) nt_364 (:) (mkNTConstr' 311)
            (fromConInteger (mkSR' 17) nt_364 2L)
            (con2 (mkSR' 19) nt_364 (:) (mkNTConstr' 311)
              (fromConInteger (mkSR' 18) nt_364 1L)
              (con0 (mkSR' 19) nt_364 ([]) (mkNTConstr' 310))))))) nt_364
  where
  
  nt_364 =
    mkTNm mkTRoot (mkNTId' 339) (mkSR' 20)
\end{alltt}


\subsection{Pretty Printing the Syntax Tree as a Haskell Module}

Besides the subsequently listed points, the pretty printer also makes a number of small mistakes (especially parenthesis) which have to be corrected to obtain a well-formed Haskell program.


\subsubsection{The Module Header: Imports \& Exports}

The module name, the export list and various imports have to be added to the output. This information is not part of the declaration list but should be available. However, for reasons discussed elsewhere the information might need to be modified with respect to the original program.


\subsubsection{Qualified Names}

The pretty printer either always uses qualified names or always unqualified names. The latter leads to ambiguities, the former make the output unreadable for a human and the qualification refers to the definition module, not the module from which the named entity is imported. The name originally used in the program (qualified or unqualified) is lost during renaming.


\subsubsection{Missing Declarations}

Several kind of declarations containing types are missing from the output, for example definitions of types and type synonyms, types in expressions and type declarations introduced by the transformation (which may sometimes be necessary to enable type inference). This is because there exist two kinds of representations of types in nhc. \texttt{Context} and \texttt{Type} values are produced by the parser. The renamer transforms them into \texttt{NewType} and \texttt{NT} values. For the latter there is currently no suitable pretty printer.


\subsubsection{Pragmas}

Comments delimited by \verb?{-#? and \verb?#-}? contain pragmas for the compiler. Unfortunately the parser already dismisses these pragmas, they are not part of the syntax tree. Hence the question arises of how to get them into the tracing program.

For some pragmas simple copying of their content into the tracing program may not suffice, they have to be transformed as well. The most obvious example for such a pragma is the RULES pragma. It contains a rewriting rule that is to be used by the compiler, mostly for optimisations. It consists of terms and types and would need to be transformed similar to a variable definition. Because of the modified types an untransformed rule does not make any sense in the tracing program. Possibly we do not want rules at all, because we may not want to trace optimised programs. However, many optimisations of ghc are now based on rules and without them ghc will produce rather inefficient code, especially for the prelude and standard libraries (so rules are connected with the problem of how to handle the prelude).

The pragmatic solution is to ignore all pragmas. There may be a way to introduce pragmas especially for the tracing program.


\subsection{The Source Reference and Identifier Tables}\label{sridtable}

For each Haskell module exists a table with information about source references and a table with information about identifiers. The tables are used for sharing the information, entries are usually referred to several times in the transformed Haskell code. These tables are currently generated by the code generator.

Earlier generation at the Haskell level is possible. However, whereas source reference entries are only referred to in the same module, references to identifier table entries may be to tables of other modules.


\subsection{The Prelude}

Because the definitions of the prelude are not fixed, just the semantics, it is not sensible to trace the prelude. However, even a trusted prelude requires transformation.

Writing the whole tracing prelude by hand would probably be rather error-prone and hard work. Most of the tracing prelude needs to be created by the tracing transformation from nhc's normal prelude. However, for some primitive parts hand-written wrappers are still required (~20 functions?). 

The final aim will be that the traced trusted prelude is produced automatically from the identifiers and types of the original prelude and consists of wrappers that call the original prelude. For this a type based analysis might be necessary.


\subsubsection{Unchanged Prelude}

A Haskell system knows the semantics of all prelude functions and is free to use them internally in the compiler. For example, pattern matching of numeric constants and $n+k$ patterns is translated into the use of overloaded \texttt{==} and \texttt{-}. The tracing transformation removes such syntactic sugar itself, but in principal a Haskell system may make use of its knowledge of prelude functions for any kind of purposes, especially optimisation.

Hence a traced program has to import both the original, unchanged prelude (as qualified) and a trusted traced prelude (which needs a new name). All explicit imports of the prelude have to be changed to imports of the traced prelude. 


\subsubsection{Primitive Functions (Wrapping)}

Some prelude functions are defined as primitive (should be FFI).
Some have magic implementations as byte code.
For the latter wrappers have to be provided that call the magic implementations.


\subsubsection{Primitive Types (Naming)}

We need tracing counterparts of primitive types like numbers, \texttt{Char}, tuples and list. For most of them no new definition is necessary, but either the transformation has to handle them differently to refer to the original prelude or type synonyms have to be introduced. Because new data type definitions need to be normal Haskell definitions, special syntax such as \texttt{[]} is not admissible for them. Hence the transformation also has to replace constructors appropriately.





\subsubsection{Traced Trusted Prelude as Valid Haskell Modules}

Nhc's prelude consists of numerous files, all with the same module header. The traced trusted prelude needs to consist of normal Haskell modules.
However, a single module would probably lead to always linking the whole prelude.


\subsubsection{Interface Files for Bootstrapping}

Currently the transformation needs the interface files of the transformed prelude. They are written by hand. 

For the portable version these interface files may change. How can they be generated automatically to avoid bootstrapping problems?


\subsubsection{IO (more wrappers)}

To write a computation's output to file and to connect it to the trace, some nhc internal IO functions are implemented specially.

For portability, the traced prelude IO functions must be defined in terms of the untraced prelude IO functions.


\subsection{Other Issues}

\subsubsection{Primitive Functions Used by Tracing Combinators}

The combinator library contains several C-functions which are used via nhc's primitive mechanism: \texttt{fatal}, \texttt{cPointerEquality} (still used?), \texttt{cEnter}, \texttt{cInitializeDebugger}, \texttt{\_tprim\_setOutputContext},  The purpose of each of these functions has to be determined. For several of them just using them via the FFI or from another C-function may suffice. Some are addressed in the following.

\subsubsection{Abortion of a Traced Computation with Error Message}

The transformation introduces calls of the C-function \texttt{fatal} with
a parent as argument.
It aborts the computation with the message ``pattern match failure''.

Somehow calls of \texttt{error} also abort the computation.


\subsubsection{Interruption of a Traced Computation}

An important feature of Hat is that any traced computation can be interrupted by pressing Control-C. The C-function \texttt{cEnter} is called every time a closure is entered. It tests if Control-C is pressed and if that is the case then terminates the computation. Some other C-function must set up a handler for Control-C. Both functions should be used via the FFI and their definitions should be portable. They should not conflict with the exception handling mechanism of GHC. (Maybe polling for Control-C can be avoided altogether; cleaning up at termination probably only requires access to C-variables which should be in a consistent state.)

\subsubsection{Initialisation of Trace Generation (wrapping)}

The C-function \texttt{cInitializeDebugger} seems to perform some initialisation for trace generation. It is currently called from some nhc internal module \texttt{\_Driver} which calls \texttt{main}. For portability all initialisation should be performed by \texttt{main}.


\subsubsection{\texttt{main} (wrapping)}

The function \texttt{Main.main} needs to have type \texttt{IO ()}, but all transformed functions have a different more complex types. The transformed version of \texttt{Main.main} should have a different name, to enable calls to it (currently impossible).

So a fixed module \texttt{Main} should call \texttt{Main\_T.omain}.

\subsubsection{Numeric Patterns}

Numeric patterns, that is, numeric constants and $n+k$ patterns, are currently handled specially in various parts of the compiler, also in code generation.

They have to be handled by the transformation. A simple method would be to ignore the involved reduction steps in the trace and rely on numeric patterns of the compiler (which must use the untransformed prelude functions). Otherwise a transformation has to be defined, which probably needs untransformed prelude functions.

\subsubsection{\texttt{fromInteger}/\texttt{fromRational}}

Where are these implicit conversion functions for numeric literals introduced explicitly? Probably they are currently traced specially.

There is nothing to do about them, if nhc introduces them after the transformation and they refer to the original prelude.


\subsection{Current order of compiler phases in nhc}

Currently the transformation takes place rather late in the front end of nhc, just before type inference.

\begin{enumerate}
\item processArgs
\item nhcLexParse (+ desugar)
\item nhcNeed (what imported entities are required?)
\item nhcImport (parse interface files for imported modules)
\item nhcRename (+ fixity adjust)
\item nhcFFItrans (introduces wrappers for IO type FFI funs)
\item nhcDerive
\item nhcDbgDataTrans
\item nhcExtract (add types from declarations to symbol table)
\item nhcDbgTrans
\item nhcRemove (create selectors for record fields; remove type definitions)
\item nhcScc (flatten instance defs and str. con. component analysis)
\item nhcType (also desugar do and records)
\item nhcInterface (build interface file for this module and write it)
\end{enumerate}

%------------------------------------------------------------------------------

\section{Design Decisions}

To minimise the development effort we intend to obtain the separate transformation by modifying the current integrated transformation.

\subsection{Extended Module Names}

The name of the transformed module gets a prefix or suffix, e.g. \texttt{Module\_T}. The new name must be a valid Haskell name but name collision should be avoided.
\begin{itemize}
\item A tracing module does not overwrite its original module and can live in the same directory.
\item The tracing prelude needs a new name anyway.
\item A wrapper scheme will need importing of original and transformed modules.
\item A fixed module \texttt{Main} is a tracing wrapper that calls \texttt{Main\_T.omain}. 
\end{itemize}


\subsection{Mangling of Identifier and Operator Names}

The transformation prefixes each original name by a character, e.g. \texttt{o} for identifiers and \texttt{*} for operators.

\begin{itemize}
\item We obtain a name space for identifiers introduced by the transformation.
\item Using different prefixes we can associate several new identifiers with an old one (e.g. transformed identifier and identifier table entry).
\item Using different prefixes we can associate new identifiers with data constructors.
\end{itemize}


\subsection{Remaining Integration with nhc}

The separate transformation can be built as a separate program, or nhc obtains a new option to perform the transformation, generating a Haskell module, without generating code. We choose the latter option because of the following advantages:

\begin{itemize}
\item A natural result of stepwise development of the transformation.
\item For compiling with nhc no second parsing of transformed Haskell program necessary.
\item Nhc and the transformation keep consistent during further development.
\item (The transformation can use any information available in nhc's front end (e.g. types); hence future changes may be easier to implement.)
\end{itemize}
The latter option also has a few disadvantages that we need to address:

\begin{itemize}
\item Tracing transformation can be more efficient, because it does not need to perform any superfluous work needed by nhc.

Having the transformation at a very early stage should avoid superfluous work.
\item A user only has to install the transformation, not full nhc.

A distribution of portable Hat still does not need to include the full nhc distribution and a wrapper shell script \texttt{hat-trans} can hide the presence of nhc.
\item Easier to support Haskell extensions that nhc does not support.

We do not intend to support extensions but nonetheless supporting some should not be that difficult.
\end{itemize}


\subsection{Position of the Transformation}

We move the transformation to just after the parser for the following reasons:

\begin{itemize}
\item At that point the dependency of the transformation on nhc will be minimal, which leads to a cleaner implementation.
\item Transforming code for another compiler requires only a minimal amount of time.
\end{itemize}

There are some problems addressed in the following:

\subsubsection{Interface Files}

The transformation needs the following information for names of imported modules.

\begin{itemize}
\item The fixity of imported operators is required for parsing.
\item The arity of data constructors is used for producing better code.
\item The arity of functions might be used in the future for producing better code.
\end{itemize}
The name mangling scheme will already handle cross-module references to identifier tables.

Except for the arity of functions the information can be gained from nhc's interface files, as is currently done. However, for reasons given in the next section, it is desirable to have the transformation at the very beginning of the compiler.

The transformation reads and writes its own interface files \texttt{*.hx}.
This requires some duplication of the nhcNeed, nhcImport and nhcRename phases, which can, however, be kept to a minimum, assuming that the input is a valid Haskell program.

For generating wrappers for a trusted module, the names and types of the defined functions and the occurring data type definitions *of this module* are needed. These should be obtained from the normal Haskell interface file of the original module. The original module has to be compiled anyway.

For generating wrapping and unwrapping functions for a data type, the data type definition is needed. It seems reasonable to produce these functions for any data type definition in a trusted module. Then naming conventions suffice to access these functions from any module.


\subsubsection{Derived Instances}

With the transformation at the beginning of the compiler, derivation of class instances is performed after the transformation. This is possible, considering that derived instances should be trusted. The transformation should introduce wrappers. The instances are still derived for the untransformed data types. It is, however, unclear, if transformed and untransformed instances and types shall exist in one module, or if using deriving will force importing the original module.

\subsubsection{The Architecture}

\begin{itemize}
\item[] ...
\item[] nhcLexParse
\item[] \quad readHxs
\item[] \quad augementNames
\item[] \quad traceTrans
\item[] \quad writeHx
\item[] \quad prettyPrint
\item[] need
\item[] ...
\end{itemize}

The trace interface file can be small and easy to parse. It may be a binary file. For each exported name it may contain its arity and fixity (no arity for class methods; no fixity in case of default fixity). \texttt{readHxs} can completely read the interface files of all imported modules and transform the import list into a filter function. \texttt{augmentNames} traverses the syntax tree and augments names by arity, fixity, and the information if it is let or lambda defined. If nhc shall compile the transformed program, \texttt{prettyPrint} is skipped.


%------------------------------------------------------------------------------

\end{document}