\documentclass[a4paper]{article}

\setlength{\textwidth}{162mm}
\setlength{\textheight}{254mm}
\setlength{\oddsidemargin}{1cm}
\setlength{\evensidemargin}{1cm}

\title{{\em ART memo 4 (version 0)} \\
            Problems with numerics in tracing with nhc98}
\author{Malcolm Wallace \\ University of York, UK}
\date{15th June 2000}

\begin{document}
\maketitle

\section{The Float/Double problem}

The tracing Prelude/Libraries do not support any operations on {\tt
Float}s or {\tt Double}s.  (The appropriate classes ({\tt Real},
{\tt Floating}\ldots) are defined, but all instances have null
implementations.)

It follows that literal {\tt Float}s and {\tt Double}s are also
poorly supported for tracing.  Remember however that non-integral
literals are defined as being sugar for {\tt (fromRational (n\%d))},
where the chosen rational number preserves full precision of the
value as a {\tt Ratio Integer}.  Thus, provided that {\tt Integer}s
and the {\tt fromRational} method are supported, literal rationals
are straightforwardly also supported - provided only that you can't
do anything useful with them yet.

See the Proposals section for how the situation might be rectified.


\section{The literal Integer problem}

At present the nhc98comp tracing compiler treats {\tt Integer}s specially,
not in full accordance with the language specification.  This section
is an investigation of the current situation, identifying problems
and proposing solutions.

When the tracing compiler was first written, integral numbers defaulted
to fixed-width {\tt Int}s in the absence of any further type information.
Since then, the newer Haskell'98 Report mandates that integral numbers
should default to multi-precision {\tt Integer}s.  This means that where
previously most programs using integral numbers worked, most now fail.

There are two parts to the problem -- one is the runtime representation
of {\tt Integer}s and the implementation of primitive operations on
{\tt Integer}s;  the other is the treatment of literal {\tt Integer}s
as they appear in the user's source code.


\subsection{Compiler}

The compiler source files relevant to this investigation are
\begin{itemize}
\item    STGBuild.hs
\item    STGGcode.hs
\item    FixSyntax.hs
\end{itemize}
These are easily identified from the Makefile as being the only files
which differ (via CPP magic) between the tracing compiler and the normal
compiler.

\subsection*{STGBuild.hs}

\begin{verbatim}
  #ifdef DBGTRANS
  buildExp pu (PosInteger pos i) = oneHeap True pu (HEAP_INT (fromInteger i))
  #else
  buildExp pu (PosInteger pos i) = oneHeap True pu (HEAP_INTEGER i)
  #endif
\end{verbatim}

We can see that literal {\tt Integer}s are down-cast to fixed-width
{\tt Int}s before code generation.

\subsection*{STGGcode.hs}

\begin{verbatim}
 #ifdef DBGTRANS
 gAtom (PosInteger pos i) = incDepth >>> unitS [PUSH_INT (fromInteger i)]
 #else
 gAtom (PosInteger pos i) = incDepth >>> unitS [PUSH_INTEGER i]
 #endif
\end{verbatim}

Likewise here.

\subsection*{FixSyntax.hs}

The following section of code is part of the normal compiler.
It finds an expression of the form {\tt (fromInteger \{dict\} x)}
for a literal {\tt x} and, depending on the context and type of the
argument {\tt x}, simplifies the whole expression to a simple literal
of the correct type.  If that is not possible, it passes the expression
on (almost) unchanged.

\begin{verbatim}
  --- fromInteger {Int Integer Float Double} constant
  fsExp exp@(ExpApplication pos [v@(ExpVar _ qfromInteger)
                                ,(ExpDict v2@(Exp2 _ qNum qType))
                                ,l@(ExpLit pl (LitInteger b i))]) =
    fsState >>>= \ state ->
    if tidIS state qfromInteger == tfromInteger && tidIS state qNum == tNum 
    then
      let id       = tidIS state qType
          return x = unitS (ExpLit pl x)
      in   if id == tInt        then return (LitInt b (fromInteger i))
      else if id == tIntHash    then return (LitInt UnBoxed (fromInteger i))
      else if id == tInteger    then unitS l
      else if id == tFloat      then return (litFloat Integer b i)
      else if id == tFloatHash  then return (litFloat Integer UnBoxed i)
      else if id == tDouble     then return (LitDouble b (fromInteger i))
      else if id == tDoubleHash then return (LitDouble UnBoxed (fromInteger i))
      else if id == tRational   then return (LitRational b (fromInteger i))
      else fsExp (ExpApplication pos [v,ExpDict (ExpApplication pos [v2]),l])
    -- Match (sel (class.type dicts) args)
    else fsExp (ExpApplication pos [v,ExpDict (ExpApplication pos [v2]),l])
\end{verbatim}

Because the tracing compiler transforms the types of all expressions so
that they calculate a trace in addition to a value, this piece of code
is partially overridden by a preceding clause which is present only when
tracing.

\begin{verbatim}
  #ifdef DBGTRANS
  fsExp exp@(ExpApplication p [ExpVar _ fci
                              ,ExpDict dict@(Exp2 _ qNum qType)
                              ,sr
                              ,t
                              ,l@(ExpLit p2 (LitInteger b i))]) =
    fsState >>>= \state ->
    if tidIS state fci == t_fromConInteger && tidIS state qNum == tNum then
        fsTidFun >>>= \tidFun -> 
        if tidIS state qType == tInt then
            unitS (ExpApplication p [ExpVar p (tidFun (t_conInt, Var)), sr, t,
                                     ExpLit p (LitInt b (fromInteger i))])
        else if tidIS state qType == tInteger then
            unitS (ExpApplication p [ExpVar p (tidFun (t_conInteger, Var))
                                    , sr, t, l])
        else error ("fsExp: strange expr(1) at "++ strPos p)
    else if tidIS state fci == t_patFromConInteger then
        fsTidFun >>>= \tidFun -> 
        if tidIS state qType == tInt then
            unitS (ExpApplication p [ExpCon p (tidFun (tR, Con)), 
                                     ExpLit p (LitInt b (fromInteger i)), t])
        else if tidIS state qType == tInteger then
            unitS (ExpApplication p [ExpCon p (tidFun (tR, Con)), l, t])
        else error ("fsExp: strange expr(5) at "++ strPos p)
    else error ("fsExp: strange expr(2) at " ++ strPos p ++
                "\nfci=" ++ show t_fromConInteger ++
                "\npfci=" ++ show t_patFromConInteger ++
                "\n?=" ++ show(tidIS state fci))
  fsExp exp@(ExpApplication p [ExpVar _ fci
                              ,ExpDict dict@(ExpVar _ _)
                              ,sr
                              ,t
                              ,l@(ExpLit p2 (LitInteger b i))]) =
    fsState >>>= \state ->
    if tidIS state fci == t_fromConInteger then
        fsTidFun >>>= \tidFun -> 
        unitS (ExpApplication p [ExpVar p (tidFun (t_ap 1, Var)),
                                 sr, t, ExpApplication p [ExpVar p (tidFun (tfromInteger, Var)),
                                                          dict, sr, t],
                                 ExpApplication p [ExpVar p (tidFun (t_conInteger, Var)), 
                                                   sr, t, l]])
    else if tidIS state fci == t_patFromConInteger then error ("fsExp: strange expr(4) at "++strPos p)
    else error ("fsExp: strange expr(3) at "++ strPos p)
  #endif
\end{verbatim}

Comparing this with the normal code, it now matters whether we
are looking at a {\em constructive} expression of the form {\tt
(fromConInteger \{dict\} SR T x)} or a {\em pattern} expression of the
form {\tt (patFromConInteger \{dict\} SR T x)}.

In the constructive case, provided the context is {\tt Num} and the
type of the literal is either {\tt Integer} or {\tt Int}, a translation
to a direct expression is given.

In the pattern case, the context is ignored and once again if the type
is either {\tt Int} or {\tt Integer} a translation is given.

In the case of a constructive pattern with a definite (i.e. not
variable) but non-{\tt Num} context, we end up with an error rather than
keeping the original expression (as one might have expected from the
non-tracing case).

Looking at the second clause, when the context is non-definite, i.e.
variable, it seems that we can translate constructive expressions
to an application of the {\tt t\_ap1} tracing combinator, but we cannot
deal with pattern expressions.


\subsection{Runtime system}

In the normal runtime system, numeric operations on almost all types
are implemented as bytecode instructions in the virtual machine.
There is special magic inside the compiler to recognise certain function
applications and emit the appropriate bytecode instruction.

However for tracing it is not possible to take advantage of this
mechanism because we want to use the standard virtual machine, yet
the traced numeric ops have totally different types.

So, in the tracing runtime system, the file
\begin{itemize}
\item    getconstr.c
\end{itemize}
holds extra tracing versions of most of the numeric primitives.
These are written by hand.  Here we see that

\begin{verbatim}
  /* Num Integer -- Not correct!!! */
  PRIM_INT_OP2(_tprim_IntegerLt,<,mkBool,mkNmBool)
  PRIM_INT_OP2(_tprim_IntegerPlus,+,mkInt,mkNmInt)
  PRIM_INT_OP2(_tprim_IntegerMinus,-,mkInt,mkNmInt)
  PRIM_INT_OP2(_tprim_IntegerTimes,*,mkInt,mkNmInt)
\end{verbatim}

etc.  The macro {\tt PRIM\_INT\_OP2} defines the primitive Haskell
operations by application of the C operator to two fixed-width
{\tt Int}s.  Clearly the comment is accurate in recognising that
this is not adequate for multi-precision {\tt Integer}s.  We also
note the following code:

\begin{verbatim}
  C_HEADER(_tprim_FromInteger)
  {
    fprintf(stderr, "_fromInteger not yet implemented.\n");
    exit(1);
  }
\end{verbatim}

which indicates that a runtime conversion of an {\tt Integer} to another
Integral type won't work in the general case, although it is possible
that a more specific conversion function might be applied instead.
As an example of the latter,

\begin{verbatim}
  C_HEADER(_tprim_IntFromInteger)
\end{verbatim}

implements the down-casting (truncation) of multi-precision {\tt
Integer}s to fixed-width {\tt Int}s.  However,

\begin{verbatim}
  PRIM_NOT_IMPLEMENTED(DoubleFromInteger)
  PRIM_NOT_IMPLEMENTED(FloatFromInteger)
\end{verbatim}

shows that there are other numeric conversions still lacking.


\section{Proposed solution}

We pre-suppose that there exists a correct scheme for transforming
primitive FFI functions to tracing variants thereof.  (See separate memo.)

\subsection*{Floats and Doubles}
\begin{itemize}
\item
  Whereas {\tt Float} and {\tt Double} operations are currently not defined
  at all in the tracing runtime system,
\item
  we propose to use the primitive FFI as an interface to the
  standard C Float and Double operations.
\end{itemize}

\subsection*{Integers}
\begin{itemize}
\item
  Whereas {\tt Integer} operations are currently defined by hand,
  in C, in part of the tracing runtime system,
\item
  and whereas such definitions actually implement fixed-width {\tt Int}s not
  multiple-precision {\tt Integer}s,
\item
  we propose to convert to using the primitive FFI as an interface to the
  standard m-p {\tt Integer} library.
\end{itemize}

\subsection*{Integers}
\begin{itemize}
\item
  Whereas the FixSyntax phase currently has an incomplete set of conditions
  for patching literal {\tt Integer}s in expressions to the actual type used,
\item
  and whereas the default action here, in the absence of a matching
  simplification, is to fail rather than to continue without simplification,
\item
  we propose to fill out the remaining useful conditions under which
  a simplification is possible,
\item
  and to default to continuing with an unsimplified expression where
  simplification was not possible.
\end{itemize}

\end{document}
