Copy the right ghc-pkg.bin into bindists

[ghc-hetmet.git] / docs / hep / hep.tex

\documentstyle[11pt]{article}

% copied from the Haskore tutorial
\textheight=8.5in
\textwidth=6.5in
\topmargin=-.3in
\oddsidemargin=0in
\evensidemargin=0in
\parskip=6pt plus2pt minus2pt

% and some of my own personal preferences
\parindent=0in

\newcommand{\var}[1]{{\tt #1\/}}    % variables
\newcommand{\fun}[1]{{\tt #1\/}}    % functions
\newcommand{\expr}[1]{{\tt #1\/}}   % expressions
\newcommand{\type}[1]{{\tt #1\/}}   % types
\newcommand{\class}[1]{{\tt #1\/}}  % classes
\newcommand{\module}[1]{{\tt #1\/}} % modules

\newcommand{\tva}{$\alpha$} % type variables
\newcommand{\tvb}{$\beta $}
\newcommand{\tvc}{$\gamma$}

\newcommand{\arrow}{$\enspace\to\enspace$} % type constructors

\newcommand{\Hugs}{{\bf Hugs\/}}
\newcommand{\GHC}{{\bf GHC\/}}
\newcommand{\Haskell}{{\bf Haskell\/}}

\newcommand{\cexpr}[1]{{\tt #1\/}}   % C expressions
\newcommand{\ctype}[1]{{\tt #1\/}}   % C types
\newcommand{\cvar}[1]{{\tt #1\/}}    % C variables
\newcommand{\cfun}[1]{{\tt #1\/}}    % C functions
\newcommand{\cfile}[1]{{\tt #1\/}}   % C files (.c, .h, etc)

\newenvironment{aside}{%
  \medbreak
  \noindent
  {\bf Aside: }
  \begingroup
    \sl
    \begin{indent}  % why doesn't this do what I expect?
}{%
    \end{indent}
  \endgroup
  \par
  {\bf End aside.}
  \medbreak
}

\newenvironment{note}{%
  \medbreak
  \noindent
  {\bf Note: }
  \begingroup
    \sl
    \begin{indent}  % why doesn't this do what I expect?
}{%
    \end{indent}
  \endgroup
  \par
  {\bf End note.}
  \medbreak
}

\newcommand{\Portability}[1]{\par{{\bf Portability Note:} \sl #1}\par}
\newcommand{\Warning}[1]{\par{{\bf Warning:} \sl #1}\par}

% These are used for reminders, communication between authors, etc.
% There should be no calls to these guys in the final document.

%\newcommand{\ToDo}[1]{\par{{\bf ToDo:} \sl #1}\par}
\newcommand{\ToDo}[1]{{{\bf ToDo:} \sl #1}}

\newenvironment{outline}{%
  \medbreak
  \noindent
  {\bf Outline: }
  \begingroup
    \nobreak
    \sl
}{%
  \endgroup
  \nobreak
  {\bf End outline.}
  \medbreak
}

% Here's how you create figures
%
% \begin{figure*}
% \centerline{
% Foo
% }
% \caption{...}
% \label{...}
% \end{figure*}

\begin{document}

\title{%
  Architecture of the Haskell Execution Platform (HEP)\\
  Version 6
}

\author{Julian Seward, Simon Marlow, Andy Gill, Sigbjorn Finne, Simon
  Peyton Jones \\
Microsoft Research, Cambridge, UK\\
{\tt \{v-julsew,simonmar,v-sfinne,simonpj\}@microsoft.com}, {\tt andy@cse.ogi.edu}}
\date{29 July 1999}
\maketitle



\section{What this document is for}
As the combined GHC--Hugs system comes ever closer to running compiled
code, it becomes clearer than an architectural overhaul is
needed.  We at MSRC, together with Andy Gill, have been discussing
this at length.

Those wishing to go directly to the all-important HEP
interface will find it in section 6.1.

\section{Names}
One frequent point of confusion in our discussions so far has
been what the names mean.  Here's some defns:

\begin{itemize}
\item ``GHC'' is the standalone native-code compiler.
\item ``Hugs''
  denotes the version built from sources in the Glasgow tree,
  using an STG back end and GHC runtime support.  On supported
  architectures, Hugs will be able to load binaries compiled by GHC.
\item ``Hugs98'' is the current public distribution.  This document is not
  concerned with it.  Further changes to
  Hugs98 will be bugfixes/maintenance, and we expect that Hugs will
  supercede Hugs98 at some point.
\end{itemize}


\section{Rationale and motivation}
As of 10 June, Hugs is able to load and run
extremely simple functions compiled by GHC.  To get to this stage has
required drastic changes to the original Hugs98 from which it was
derived:
\begin{itemize}
\item dumping the original back end and runtime support, and using
  an STG-based code generator and GHC's RTS instead.
\item adding a new parser to read GHC's interface files (easy) and
  a significant amount of code to manufacture appropriate
  symbol table entries (not so easy).
\item modifying the import chasing mechanism to follow dependencies
  through both source and interface files.
\end{itemize}

These changes, particularly the latter two, are inelegantly integrated
into the original structure.  It is clear that whatever Hugs
emerges as a result of my current hackery will be more a
proof-of-concept vehicle than as something which we can carry
forwards.  Some of the design decisions I made on the way are, in
hindsight,  bad.  A decent system will need a cleaned-up
architecture.

Hugs is becoming more complex as more parties modify it for their own
diverse purposes.  There are now various user interfaces (WinHugs, the
``standard'' text UI, the HaskellScript stuff, and RunHugs).  Not far
ahead will come the further complexity of supporting multiple code
generators.  We already have the original and STG codegens, and 
further codegens are proposed for Hugs and GHC.

A powerful motivating factor for redoing the architecture is to try
and modularise Hugs so that
\begin{itemize}
\item supporting these various extensions is simpler.
\item supporting different platforms is simpler.  Hugs is not too
  bad, but GHC is very Unix oriented.
\item new extensions don't involve grappling with so many
  parts of the system.
\item building customised variants is simpler.
\end{itemize}

Finally, it would be nice to at least review, and possibly redo, some
aspects of the existing code base:
\begin{itemize}
\item The conservative garbage collector (now reduced to compile-time only
  duty in Hugs) has been much discussed.  Perhaps we could
  do away with it and use the GHC heap instead.

\item Symbol table (names, classes, values, instances, modules) management
  in Hugs is too inflexible to support loading and unloading of
  arbitrary mixtures of compiled and interpreted code in arbitrary
  orders.  It needs redoing.

\item The import chasing mechanism is hard to understand, and has proven
  difficult to adapt for use in Hugs.  Redesign is unavoidable.
\end{itemize}



\section{Issues}
Here are the major architectural difficulties which have been encountered.

\begin{itemize}
\item 
  What mixtures of compiled and interpreted code should be supported?
  Currently there are at three proposals, in increasing order of
  complexity to implement:
  \begin{itemize}
  \item ``Downward closure'': if module M is compiled, then all modules
     reachable from M, including Prelude, must be too.
  \item ``Prelude + any'': arbitrary mixtures are allowed, with the proviso
     that if any module is compiled, then the Prelude must be compiled
     too.
  \item ``Any'': any mixture at all.
  \end{itemize}
  Underlying problems are:
  \begin{itemize}
  \item 
     Run-time linking of object files.  Use of the Unix \cfun{dlopen}
     facility mandates a downward closure approach, since there is
     no way to resolve references to interpreted code from compiled
     code.  How the windows DLL loaders would behave I don't know.
     To be more flexible seems to require writing one's own linkers.
  \item
     Primops.  Operations on, and assumptions about representation of
     primops have to be compatible in compiled and interpreted code.
     One possibility is to ensure that Hugs's and GHC's primops
     exactly correspond.  That seems wasteful, and difficult and
     bug-prone to maintain.  Another approach it to route all
     primop calls to GHC, probably by routing them all via a
     GHC-compiled Prelude.
  \item
     Interface files.  All but the downward closure option require
     Hugs to generate interface files for interpreted modules
     so GHC can compile against them.
  \end{itemize}

\item
  When the user asks ``:reload'', how should Hugs go about bringing
  the execution environment up-to-date?  How intelligent should it be?
  (how accurately do we track changes in the module dependencies?)
  Where do we put the intelligence?  Is Hugs allowed to invoke GHC,
  or must the user do it?  Do the different user interfaces require
  different levels of sophistication?

\item
  For platforms on which GHC is not supported, 
  we still desire to build a standalone Hugs without object loading
  facilities.
  The main trickyness is that a standalone Hugs will have to supply 
  its own implementation of primops, since it can't rely on use of
  primop facilities in a GHC-compiled prelude.
\end{itemize}

Some less troublesome issues are

\begin{itemize}
\item
  We might want a form of BCO which can be dumped
  into a file and reloaded/linked later.  One use would be to 
  give an architecture-neutral way to distribute libraries
  in binary form.  Another is for shipping code across a network.
  Finally, for platforms on which GHC is not supported, it offers
  the possibility of fast startup, by loading \cfun{Prelude.bco} and
  reading \cfun{Prelude.hi}.  One consequence of doing dumpable
  BCOs is that Hugs would need to create interface files.
\item
  Multiple code generators.  If Hugs is to acquire other code
  generators, it may be desirable to create an interface at the
  boundary between STGland and the code generators.

  Since GHC may also want to target new platforms, work on new
  code generators should aim to maximise compatibility between
  Hugs and GHC.
\item
  Loading object files.  
  Hugs is fairly platform independent, except
  for its need to load object files.  We can
  create an object file loading/linking generic API, and hook
  specific loaders, for example ELF and Win32 DLL, under that. 
  However, as mentioned above, use of the native facilities may be
  too inflexible, and so necessitate writing our own linkers.
\item
  Object vs source-level symbol tables.
  For each function \cfun{f} that GHC compiles, a whole
  bunch of symbols are spewed into the object code: \cfun{f\_closure},
  \cfun{f\_entry}, \cfun{f\_info} and \cfun{f\_fastk}, at the very
  least.

  On the one hand, you need to remember all these names because other
  object modules will reference them.  On the other hand, the bytecode
  compiler is only interested in source-level facts about \cfun{f}, such as
  its type, and not about the addresses of its derivative symbols.
  We propose to have a
  separate symbol table for object code symbols, with only minimal
  connection to the source-level symbol table (a pointer to
  \cfun{f\_closure} ?)
\item
  Replacement of the conservative garbage collector.  It doesn't
  make much sense to have two heaps, allocators and GCs in the new Hugs.
  Either we can move compile-time allocation into the
  execution heap, or move to an arena-based allocator.  Hugs allocates
  heap when compiling so slowly that the latter possibility is quite
  practical.  Either way, the main criteria is to reimplement the \cfun{fst},
  \cfun{snd}, \cfun{pair}, \&c, macros, so that client code doesn't have to be
  changed.

  Changing the heap representation would require a new scheme
  for dealing with Hugs' symbol tables, since pointers to places
  outside the (Hugs) heap are interpreted in various ways, including
  as symbol table references.

  It's also unclear what the consequences would be of any client
  code which dynamically changes the type of a (eg) pair field
  from pointer to non-pointer, or vice versa.
\item 
  Dictionary layouts.  Hugs and GHC need to agree on the order
  in which dictionary arguments are passed, and on the order of
  methods within a dictionary.  We also need to make GHC regard
  selector functions as possibly overloaded, if necessary,
  and pass dictionaries appropriately.
\item
  Currently GHC, and therefore Hugs, is very Unix oriented.  This
  is not acceptable for a standalone Hugs.  The main blocking points for
  development on WinNT are the GHC driver (Perl) and the
  build environment (GNU Make).
\item
  Profiling.  If Hugs is to be able to do profiling,
  it needs to be able to handle scc annotations and probably implement
  auto-sccification.  Will it be difficult to make sure the
  implemented cost semantics are the same as that of GHC ?
\item 
  Type system extensions.  If Hugs is to implement them, Hugs and
  GHC must agree on them.  Currently: multiparam type classes, 
  local universal quantification, existential quantification.
\item 
  Issues to do with startup and loading the Prelude, so as
  to minimise code duplication and complexity in Hugs.
  Interacts with the primops issue.
\item
  Andy is interested in looking into some hooks for debugging.
\end{itemize}


\section{Proposed structure}
\begin{verbatim}
              TextUI    WinUI  HaskellScript  etcUI    VisualStudio
                 |        |         |          |           |
                 +--------+----+----+----------+ ..........+
                               |
                             ..... HEP interface
      /~                       |
      |                    Session                     ((Compile-time
      |                    Manager                       storage mgr))
      |                        |
 HEP -+        +----------+----+----+----------+---------+
      |        |          |    |    |          |         |
      |    Bytecode    Source  |  Object     Object    IFace
      |    Compiler    SymTab  |  Loader     SymTab    Reader
      \_                       |
                            StorMgr
                            & Eval
\end{verbatim}
This crude picture depicts the main blocks, with lines indicating flow
of control, not data.  Underlying all components is the compile-time
storage manager.  The session manager is central to the design, so
I'll start there.

The parts from the Session Manager on downwards, including the 
compile-time storage manager, are collectively known as the
Haskell Execution Platform (HEP).  HEP has to support a diversity
of clients, both those which offer human user interfaces (TextUI,
WinUI, etc) or those offering higher level programmatic interfaces
(HaskellScript, VisualStudio).  Because of this, the HEP interface
is critical.  It is described in detail in Section 6.1.
\begin{itemize}
\item
  Session manager (SM): Responsible for building an up-to-date
  executable image (mixture of byte and native code) when the user
  interfaces request a particular Haskell module to be made available
  for execution.  Responsible for arranging
  evaluation of Haskell expressions passed from the user interfaces.

  To build an up-to-date image, SM needs to keep track of module
  dependencies and source/object in-or-out-of-dateness, so as to
  determine when to reload/recompile modules.
  It's fair to say that SM will have to
  incorporate the functionality of (\cfun{hbc|nhc|}$\epsilon$)\cfun{make}.

  The RTS can support multiple Haskell threads running concurrently,
  so SM offers that service too.  This might be useful for a GUI based
  Hugs in which there are multiple read-eval windows.  Further, SM
  needs to offer GUIs a way to check their own event queues whilst the
  evaluator or compiler is running.  We have devised what we hope is a
  flexible scheme to support this.  The same mechanism allows UIs to
  interrupt compilation or evaluation in a portable manner.
\item
  Bytecode Compiler (BC): the previous core of Hugs.  Reads Haskell
  source and translates it via STG code to bytecode, which it places
  in the (runtime) heap.  Updates the Source SymTab (SSym) entry for
  this module and references SSym entries for other modules.
  Optionally emits a simple, GHC-readable interface file for the
  module.

  In order that SM can determine the dependencies of a given source
  file without attempting full compilation, BC has a facility to parse
  a file and return the import list, but do nothing more.

\item
  IFace Reader (RdIF): reads GHC created interface files and
  manufactures symbol table entries in SSym for the specified module.

  Analogously to BC, has a submode for finding just the dependencies
  of an interface file.

  When called upon to load an interface, RdIF must engage Object
  Loader (OLoad) to load the corresponding object file.  It is OLoad's
  responsibility to relocate and link this file, since that's platform
  dependent.  However, RdIF must add some minimal info about the
  object code to this module's SSym entry, namely the address of the
  \cfun{\_closure} entry points.

\item
  Source Symbol Table (SSym): is the global source-level symbol
  table, containing info on modules (imports, exports), classes
  (types, members, etc), instances, tycons and functions.  This is
  what BC will have to consult and update in order to static-check and
  typecheck source files.  SSym only contains enough info about object
  files to be able to create calls to GHC compiled functions.  At the
  moment this would appear to be the \cfun{f\_closure} addresses.

  SSym must be designed so that modules can be thrown out of the
  system in any order, rather than just the stack-like order in the
  current Hugs.  Fixed limits on table sizes should also be avoided.

  SSym must be designed so client code doesn't have to change.
  I think most accesses go via the \cfun{name}, \cfun{isName},
  \cfun{findName}, \cfun{newName} macros (ditto \cfun{module},
  \cfun{cclass}, \cfun{inst}, \cfun{tycon}), so it's ok.

\item
  Object Symbol Table (OSym): global object-level symbol table.
  Contains a binding for every symbol in every object currently
  loaded.  New objects can be linked merely by querying OSym;
  no reference to SSym is needed.  As motivation, GHC compiled 
  functions have dozens of symbols not referred to at the source
  level but which are referred to from other objects, and also 
  internally between code and data sections, so we need
  to record their addresses.


\item
  Object Loader (OLoad) has two duties: (1) bring an object file into
  memory and create OSym entries for it.  (2) resolve references in an
  object file in memory by consulting OSym (and possibly SSym?).

  OLoad is obviously object-format dependent.  It should be structured
  so that it has a 
  format independent interface, and implementations of (1) and (2) for
  each format (ELF, DLL, COFF, etc).  The ELF implementation is
  already done and takes only about 300 lines of C.

  Extra complication: object files can refer to symbols in the RTS,
  and to symbols like \cfun{printf}.  These symbols will be bound into the
  executable Hugs image at the time that is built.   So we need a
  way to find the addresses of symbols ``in this process image''.  On
  one hand, logically it is up to OSym to supply these addresses.  But
  this is also object/executable format dependent, so OLoad needs to
  be involved.  Blargh.  Possibly have an OLoad call to preload 
  OSym with these symbols at Hugs startup time.


\item
  Storage Manager and Evaluator (RTS): This is the GHC RTS,
  along with the bytecode interpreter already in StgHugs.  Executes the
  native/bytecode mixture.  (Not sure what else to say.  This is
  what Simon and Alastair created.  It works and is more or less in
  the required form).


\item
  The user interfaces, TextUI, WinUI, RunHugsUI, etc.  These wrap up
  the services of SM and present them to the end-user, either human
  or programmatic, in some
  appropriate way.  The pictures show multiple interfaces built into
  the system, but in practice we expect only one to be linked in to
  any particular system.  The requests that they can pass to SM are:
  \begin{itemize}
  \item Initialise system, shut down.
  \item Change system settings (implements :set in Hugs)
  \item Prepare a module for use, returning a module handle.
  \item Translate expressions in the context of a given module.
  \item Evaluate a translated expression.
  \item Query SSym (so that :info, :type, etc can be implemented)
  \end{itemize}

\item
  Underlying everything is the compile-time storage manager.
  Details currently hazy.
\end{itemize}

\subsubsection*{Possible variant 1: multiple code generators}
Chop up BC, so it becomes a single source-to-STGcode converter
plus some number of STGcode-to-whatever code generators.
Hopefully the code generators would all have the same interface.
\begin{verbatim}
  TextUI    WinUI   RunHugsUI  etcUI    VisualStudio
     |        |         |        |           |
     +--------+----+----+--------+ ..........+
                   |
                Session                     ((Compile-time
                Manager                       storage mgr))
                   |
   +----------+----+----+----------+---------+--------+----------+
   |          |    |    |          |         |        |          |
 Haskell   Source  |  Object     Object    IFace    STG to     STG to
 to STG    SymTab  |  Loader     SymTab    Reader   Bytecode   OTHER
                   |
                StorMgr
                & Eval
\end{verbatim}

\subsubsection*{Possible variant 2: dumpable BCOs}
If BCOs are dumpable to file, they can be regarded as just another
flavour of object format.  Then the Haskell to BCO (BC) component can
be factored off into another process.  Loading of BCOs would be done
via OLoad, with RdIF reading the interface files which would have
to be created by BC.  It also means BC would have to read
interface files.

This scheme has overheads in both compile speed and
implementational complexity.  The point of mentioning it is to
emphasise the idea that there's no particularly fundamental reason why
the BC component should be compiled into SystemC whilst GHC remains a
separate entity.  If we need to do this, it's not difficult.
However, nor is it at present of the highest priority.


\section{The component interfaces}

Many of the calls can fail.  It would be good to think about a
consistent error-recovery strategy.  I've ignored any error cases
in the signatures below.  I'm working with Variant 1 (multiple code
generators) above.



\subsection{Session manager (SM)}
These interfaces are presented in IDLishly, with
Haskell types.  Regard the return types as really being \verb@IO@
types.
\begin{verbatim}
interface IUnknown {
   addRef, release :: ()
}
\end{verbatim}
All interfaces inherit reference counting methods in \verb@IUnknown@.
When a client copies a pointer, it should \verb@addRef@ it, and
conversely \verb@release@ it when done.
Once a pointer is \verb@release@d, the thing it points at may or
may not still be alive, but in any case the owner of the
pointer must assume it is dead.  \ToDo{Are these the COM semantics?}

\subsubsection{Servers}
\begin{verbatim}
getServer :: HsServer

interface HsServer : IUnknown {
   loadModule   :: LoadHooks -> String -> Maybe HsModule

   setOptions   :: [(String,String)] -> ()
   getOptions   :: [(String,String)]
   canUseObject :: Bool
}
\end{verbatim}
For simplicity, we assume there is only one server, obtained
via \verb@getServer@.  In practice they might be manufactured 
by a class factory (???), but that's too COM specific here.

A client can ask a \verb@HsServer@ object whether it is 
capable of loading object code with \verb@canUseObject@.
HEPs hosted on non-GHC-supporting platforms will return
\verb@False@ here.  The HEP will still work but must
interpret everything.

Clients can query and set options for this server using
\verb@getOptions@ and \verb@setOptions@.  \verb@getOptions@
returns all the available options and their current values.
\verb@setOptions@ can supply new values for any subset, or all, of
them.

\verb@HsServer@'s main purpose is to supply \verb@loadModule@.
Clients supply a string such as ``\verb@List@'', indicating a
module name, with no filename extension or directory.  
HEP tries to return a \verb@HsModule@ handle reflecting
the current state of the source/object code base.  In doing so,
it may need to load and/or compile arbitrary numbers of 
subsidiary modules.  This operation may fail, hence the \verb@Maybe@
return type.

Once a \verb@HsModule@ handle has been successfully acquired,
that handle remains valid until the client calls \verb@release@
on it.  What the handle refers to is the state of the object/source
code base at the time the handle was created.  Subsequent changes
to the code base have no effect on the handle; the executable images
to which it refers are unchanged.

For example, assuming \verb@s :: HsServer@ and \verb@h :: LoadHooks@,
then given the following sequence of events
\begin{enumerate}
\item \verb@m1 = s.loadModule("M", h)@, and this call succeeds
\item The source/object for \verb@M@ changes
\item \verb@m2 = s.loadModule("M", h)@
\end{enumerate}
\verb@m1@ will continue to be valid and will refer to the original
version of \verb@M@, whilst \verb@m2@ refers to the new version.
Furthermore, if \verb@M@ depends on some other
modules, \verb@m1@ will still be based on the
original version of those modules, even if their sources/objects
change.  In short, once a \verb@HsModule@ comes into existence,
its meaning never changes.

\subsubsection{Load-time hooks}

HEP decides for itself what modules it needs to load, when, and
in what order.  It is up to the client to supply the
actual source/object code for modules.  To facilitate this, 
clients must pass a \verb@LoadHooks@ object to \verb@loadModule@:
\begin{verbatim}
interface LoadHooks : IUnknown {
   findModule :: String
         -> (Maybe InStream, Maybe (InStream, InStream))
      -- .hs file, (.hi file, .o file)

   setProgress :: String -> Float -> Bool   
      -- True <=> abandon compilation please

   error :: Error -> ()
}
\end{verbatim}
When HEP needs a module, it calls \verb@findModule@, passing it
the unadorned module name, unadorned in the same way as names 
passed to \verb@loadModule@.  The client should attempt to locate
source, interface and object streams for the module in any way
it pleases.  The returned pair is a possible stream for the
source text, and a possible pair of streams for the interface
and object text.  This latter pairing exists because there's
no point in producing an object stream without the corresponding
interface stream, or vice versa.

An \verb@InStream@ is an abstract handle with which to read a finite stream.
\verb@getChar@ reads the next character or returns an end-of-file
marker.  \verb@fprint@ returns a fingerprint, perhaps a checksum,
or a file timestamp,
which characterises the stream's contents.  \verb@eqFPrint@ compares
this stream's fingerprint against a supplied one.  The fingerprinting
semantics requires that two identical streams have identical
fingerprints. \ToDo{Do we care that this isn't implementable,
strictly speaking?}  The intention is to provide HEP with a 
way to determine to whether a given stream has changed since it was
last looked at.  \verb@FPrint@ is regarded as an abstract type
supplied by the client.
\begin{verbatim}
interface InStream : IUnknown {
   getChar  :: Int
   fprint   :: FPrint
   eqFPrint :: FPrint -> Bool
}
\end{verbatim}

HEP notifies the client of compilation/loading progress by calling
\verb@setProgress@, giving the name of a goal, eg ``Typechecking'',
and a value, increasing monotonically over a sequence of such calls,
from $0.0$ to $1.0$, indicating progress towards that goal.
If the client returns \verb@True@ to such a call, HEP abandons 
compilation as soon as possible.  In this way, clients can
interrupt compilation in a portable manner.

If a compilation error occurs, HEP creates a \verb@Error@ object
and passes it to the client with \verb@error@.  For the moment,
the error object only contains the source coordinates of the
error, the \verb@InStream@ from which the source originated,
and a method \verb@show@ which produces the text of the error message.
Later versions may contain more information.
\begin{verbatim}
interface Showable : IUnknown { 
   show :: String
}

interface Error : Showable {
   source    :: InStream
   line, col :: Int
}
\end{verbatim}

\subsubsection{Modules}
Once a client has obtained a \verb@HsModule@ handle, it can
translate and run expressions in the context of that module.
Translated values are \verb@HsVal@ objects.
\begin{verbatim}
interface HsModule : IUnknown {
   exprVal :: String -> Bool -> Maybe HsVal
      -- A Haskell expression, treated as if
      -- it was written in the module
      -- Bool==True <=> wrap in `print' if not :: IO t

   idVal :: String -> Maybe HsVal
      -- The name of a top-level value in
      -- scope in the module

   -- takes a regexp, gives list of things
   -- defined in (Bool==True) or in scope in (Bool==False) this mod
   getNames     :: Bool -> String -> [Name]
   getTypes     :: Bool -> String -> [Type]
   getTycons    :: Bool -> String -> [Tycon]
   getClasses   :: Bool -> String -> [Class]
   getInstances :: Bool -> String -> [Instance]

   -- query a specific thing.  String is a name.  Bool as above.
   findName     :: Bool -> String -> Maybe Name
   findType     :: Bool -> String -> Maybe Type
   findTycon    :: Bool -> String -> Maybe Tycon
   findClass    :: Bool -> String -> Maybe Class
   findInstance :: Bool -> String -> String -> Maybe Instance
}
\end{verbatim}
The two important methods are \verb@exprVal@ and
\verb@idVal@.  \verb@exprVal@ takes an arbitrary Haskell
expression and tries to return a translation of it in the
context of that module.  The caller can optionally ask to
have the value wrapped in \verb@print@, since that is often
convenient.

\verb@idVal@ is simpler.  It simply regards the supplied string
as the name of a top-level function in scope in the module, and
returns a \verb@HsVal@ referring to that name.  It's conceivable
that a skeletal HEP which just loaded object files could implement
\verb@idVal@ but not \verb@exprVal@.  Such a HEP would not need
a bytecode compiler or interpreter.

The \verb@get*@ and \verb@find*@ methods allow clients to consult
the HEP's symbol tables.  In all cases, the \verb@Bool@
parameter facilitates choosing between ``defined in this module''
and ``in scope in this module'' interpretation of queries.

\verb@getNames@ returns the names of all top-level values
matching the wildcard in the supplied string, defined in or
in scope in this module.  \verb@findName@ returns the 
corresponding information for a specific name; the supplied
string must be a real name and not a wildcard.  The \verb@Type@,
\verb@Tycon@, \verb@Class@ and \verb@Instance@ calls function
analogously for types, type constructors, classes and instances.

As with error messages, currently the only possible action with 
a name, type, tycon, class or instance is to print it.  This
may change later.
\begin{verbatim}
interface Class    : Showable { }
interface Type     : Showable { }
interface Instance : Showable { }
interface Tycon    : Showable { }
interface Name     : Showable { }
\end{verbatim}

\subsubsection{Values}
A Haskell value is represented by a \verb@HsVal@ object.
\verb@HsVal@s carry their type, which is obtained with
\verb@type@.  

New values can be created by application of
a value to a list of argument values; \verb@apply@ does this.
The application is typechecked, and will fail if it is type-incorrect.
\ToDo{Say more about the rules and extent of this}.

For convenience, new values can be manufactured from integers,
using \verb@mkIntValue@.  The inverse operation is \verb@intValueOf@,
which will fail if the type is wrong.  Such mistakes can be avoided
by first testing with \verb@isIntValue@.  \ToDo{What does
\verb@intValueOf@ do if the arg is not in whnf?}  Similar functions
exist for other primitive types.
\begin{verbatim}
interface HsVal : IUnknown {
   type  :: Type

   apply :: [HsVal] -> Maybe HsVal
      -- can fail because of type error
      
   eval   :: RunHooks -> WhyIStopped   
      -- To WHNF
   evalIO :: RunHooks -> Maybe WhyIStopped
      -- Runs a value of type IO t, returning the t
      -- the result may or may not be evaluated

   mkIntValue :: Int -> HsVal
   isIntValue :: Bool
   intValueOf :: Maybe Int
      -- ditto Bool Char Word Float Double
}
\end{verbatim}
The main purpose of \verb@HsVal@ is to supply \verb@eval@ and
\verb@evalIO@.  \verb@eval@ evaluates a value, which may be of 
any type, to WHNF.  The client must supply a \verb@RunHooks@ object
to be used during evaluation.  \verb@evalIO@ is similar, except
that the supplied value must have type \verb@IO t@.   The 
possibly unevaluated \verb@t@ is then returned.
\begin{verbatim}
data WhyIStopped = Done
                 | DoneIO HsVal 
                 | YouAskedMeToStop 
                 | NoThreadsToRun

interface RunHooks : IUnknown {
   continue       :: Bool
   stdout, stderr :: Char -> ()
   stdin          :: Char
   -- if the last three block, the entire HEP does
}
\end{verbatim}
A \verb@RunHooks@ object allows the client to capture \verb@stdout@
and \verb@stderr@ from the evaluated expression, and supply a
\verb@stdin@ stream for it.  If any of these calls blocks, the
entire HEP will too.  \ToDo{Are we sure?}

When running an expression, HEP will call \verb@continue@ on a
fairly regular basis, to find out if the client wants to interrupt
evaluation.  If the client returns \verb@True@,
\verb@eval@/\verb@evalIO@ then will return with the value
\verb@YouAskedMeToStop@.  The client can resume execution later
by calling \verb@eval@/\verb@evalIO@ again on that value.

\verb@eval@/\verb@evalIO@ may also return bearing \verb@Done@
or \verb@DoneIO@ respectively, indicating that the value has
reached WHNF.  Lastly, a return value of \verb@NoThreadsToRun@
indicates that the RTS's scheduler could not find any Haskell
threads to run.  This could indicate deadlock.

\subsubsection{Threading issues for the HEP}
There are two kinds of threads to consider: Haskell threads,
managed and scheduled by the RTS's scheduler, and operating-system
threads.

Haskell threads are easy.  An \verb@eval@/\verb@evalIO@ call
starts a single ``main'' thread, and that can create new
threads using the Haskell primitive \verb@forkIO@.

The complication lies in OS threads.  Rather than attempt
to design a multithreaded HEP, we place a mutex around the
entire HEP, and allow only one OS thread in at a time.
To try and create some fairness, the HEP can, at times convenient
to it, check whether any other OS threads are waiting to enter,
in which case it may yield, so as to let others enter.

Unfortunately this will cause deadlocks for Haskell programs
using callbacks.  Typically, a callback function will be 
supplied to some other subsystem (eg, graphics) using a 
\verb@ccall@ to that subsystem, bearing the \verb@HsVal@ of the
callback.  To run the callback, the subsystem will later
call \verb@eval@ on the callback.  But if the same OS thread is
still ``inside'' the HEP, this call will block.

A solution is to release the lock when an OS thread \verb@ccall@s 
out of the HEP.  This allows other threads, or callbacks in the
same thread, to successfully enter the HEP -- not necessarily 
immediately, but eventually, assume the OSs thread scheduling
is fair.


\subsection{Haskell to STG compiler (Hs2Stg)}
\begin{verbatim}
-- look at text of module and get import list
getImportList :: ModuleName -> [ModuleName]

-- convert .hs to stg trees
compileModule :: ModuleName -> [STG]
\end{verbatim}



\subsection{Interface reader (RdIF)}
Loading of mutually recursive groups of objects is allowed even
though Hugs can't handle that at the source level.  Internally,
\cfun{loadObjectGroup} has to make two passes through the 
interface files, the first to create partially-filled entries in SSym, and the 
second to complete those entries.
\begin{verbatim}
-- look at interface file for module and get import list
getImportList   :: ModuleName -> [ModuleName]

-- load a group of modules, resolving references between them
-- update OSym and SSym
loadObjectGroup :: [ModuleName] -> ()
\end{verbatim}



\subsection{Source symbol table (SSym)}
\begin{verbatim}
-- create/delete entries for a new module
newModule :: ModuleName -> ()
delModule :: ModuleName -> ()

-- various functions for adding/querying vars, tycons, classes, instances
-- and in particular
setClosureOf :: Name -> Pointer -> ()
getClosureOf :: Name -> Pointer
\end{verbatim}


\subsection{Object symbol table (OSym)}
\begin{verbatim}
-- add, delete module-level entries
addOMod  :: ModuleName -> ()
delOMod  :: ModuleName -> ()
-- add, find symbols
addOSym  :: ModuleName -> Name -> Pointer -> ()
findOSym :: ModuleName -> Name -> Pointer
\end{verbatim}



\subsection{Object loader (OLoad)}
\begin{verbatim}
-- check object for correct format, etc
validateObject :: ModuleName -> Bool
-- get object into memory and update OSym, but don't link it
loadObject :: ModuleName -> ()
-- resolve refs in previously loaded object
linkObject :: ModuleName -> ()
-- remove object from memory
delObject :: ModuleName -> ()
\end{verbatim}


\subsection{Storage manager and evaluator (RTS)}
\begin{verbatim}
-- eval this ptr to WHNF
enter :: Pointer -> ()
\end{verbatim}



\subsection{Code generators, STG to bytecode (Stg2BC) and STG to OTHER
      (Stg2Com)}
\begin{verbatim}
stg2BC, stg2OTHER :: [STG] -> ()
\end{verbatim}


\subsection{The user interfaces}
... don't have a programmatic interface.




\section{Tentative design details looking for a home}

These sections record how the various bits of the new system
should work.  In may places it merely records what the existing
system does.

\subsection{Compile-time storage management}
{\bf ToDo}: draw some pictures of how the tables interrelate.

Relevant structures are
\begin{itemize}
\item compile-time heap
\item Source symbol table, comprising: name table, tycon table,
class table, instance table, module table
\item Text table (not sure where this logically belongs)
\item Object symbol table
\end{itemize}
Needs to be redone.  Design goals are:
\begin{itemize}
\item Should be able to delete an arbitrary module from the system
      and scrub all references to it.  The current Hugs scheme only
      allows deleting of modules in a LIFO fashion.
\item No fixed table sizes for anything!
      Everything to by dynamically resizable on-the-go.
      This is a long-overdue change.
\item No changes to the client code.  No way do we want to rewrite
      the typechecker, static analyser, etc.  That means that
      any reimplementation will have to supply suitable versions
      of the many macros used to access storage in current Hugs.
      Indeed, the viability of this enterprise depends on
      the observation that the current Hugs consistently uses these 
      macros/functions and does not go directly to the structures.
\end{itemize}

For the time being, it seems best not to mix the compile-time
and run-time heaps.  It might be possible, but there are a bunch
of unknown factors, and fixing them seems to have a low 
brownie-points/effort ratio:
\begin{itemize}
\item Hugs assumes the existence of a ``generic'' pointer-ish entity.
      This might point into the heap, but if it doesn't, then it can
      be a reference to a symbol table, an integer, a piece of text,
      or various other things.  This simplifies the typechecker and
      static analysis.  (I guess you could say it's a union type).

      Let's call these values ``compile-time pointers''.

      GHC's storage manager would need to be modified to
      deal with fields which might or not might be pointers.

\item Assignment.  Hugs frequently (?) mutates heap objects.  I'm
      unsure what effect this would have on the RTS if a pointer field
      is changed to a non-pointer one, or vice versa.

      Also, when doing assignments, the old-to-new pointer tables
      would need to be checked and updated.  Changes to
      client code at assignment points seem unavoidable.
\end{itemize}
\subsubsection*{Name, tycon, class and instance tables}
Each name table entry describes a top-level value in a Haskell module.
It holds a pointer to the textual name, the type, pointers to the
STG trees and compiled bytecode, and various other things.  A
compile-time pointer can point directly at a name table entry.

Like existing Hugs, we continue to organise the name table as an
array of name table entries.  Unlike existing Hugs, the name 
entries for a given module do not occupy a contiguous range
of the name table.  To do so makes it impossible to delete 
modules, since deletion of a module would create a large hole
in the table.  To fill this hole, we'd have to slide other entries
around, but then we'd need to find and change all
compile-time pointers to the moved entries (viz, the usual
compacting-GC problem).  The latter could be
very difficult.

Instead, each name table entry has a link field, which is used to 
chain together all entries for a given module.  For unused entries,
the link fields implement a standard freelist.  Allocation of new
entries consults the freelist.  If that's empty, the table is 
expanded as follows: a bigger array, perhaps twice the size, is
malloc'd.  The existing name table is copied into it, and the
new entries are put on the free list.  

When a module is deleted, all its name table entries are put back on
the free list.

The tycon, instance and class tables function in exactly the same way.
The module table is different.

\subsubsection*{Notion of the ``current module's scope''}
When translating a module, Hugs needs to have a way, given the text
of a symbol, to (a) find out if it is in scope in this module, and 
(b) if so, what value/type it is bound to.  Because a module can
import symbols from other modules, the current scope is not just
the contents of the current module.

To support this, name table entries have a second link field.
This field is used to chain together all entries in the current
scope.  Unlike the module-link fields, this chain necessarily
visits entries from many different modules.

Because each name table only has one scope-link field, only
one current scope can be supported at any time.  When Hugs
starts processing a new module, the current scope chain has to
be rebuilt for that module, by processing its import declarations,
and recursing down through other modules as necessary.  This operation
is expensive and should be done infrequently.

Having a single chain for the current scope makes
name lookup terribly inefficient.   The current Hugs uses a small
256 entry hash table to help.  Each hash table entry points to a
chain of name-table entries with the same hash value, chained as
described above through the current-scope field.  In other words,
there are 256 current-scope chains, not just one, and they all 
begin at the hash table.  So, when changing current module,
Hugs has to rebuild the hash table as well as the chains.

Tycons, classes and instances use exactly the same scheme.


\subsubsection*{The module table}

Unlike the name, tycon, class and instance table, this one 
has exactly one entry per module.  Each entry contains 
pointers to: the textual name of the module,
an import list, an export list,
the start of the name-table chain
for this module, ditto for tycons, classes and instances, 
and perhaps a pointer to a list of STG trees denoting the
code generated for the module.  When a module is deleted,
its module table entry is marked as unused.  This table can
be resized by copying it into a larger array if needed, in the
usual way.

\subsubsection*{The text table}

This remains pretty much the same as before, with the proviso
that entries in it cannot be ejected when a module is deleted.  
If it gets full, we expand it by copying it onto a bigger
array in the usual way.  In practice this is unlikely to be
a problem, since loading a revised version of a recently-deleted
module is very likely to present almost the same set of strings
as the old version, thereby not increasing the size of the
table very much.

One final detail: the current hashing scheme to find stuff in
the table will need to be carefully revised so that it can
still work when the table size is, say, doubled.  Apparently
\verb@rts/Hash.c@ contains a suitable algorithm.

\subsubsection*{The object symbol table}

We may as well make the object symbol table work in the same way as
the name, tycon, class and instance tables.  That is, an array of 
symbol records, with each record having a link field to chain together
entries in the same module, and another field linking together entries
with the same hash values.  The table can expand dynamically, and
modules can be thrown out of the table in any order.  There is a
top-level hash table holding the start point of the hash chains.

Unlike the name, class, tycon and instance tables, the hash table
and chains for the object symbol table reflects all the available
symbols, not just those regarded as in scope for the current module
being translated.

\subsubsection*{Dividing up the compile-time-pointer space}

Hugs has always had the notion of a pointer which {\em might}
point into the compile-time heap, or it might not, denoting a 
name, piece of text, etc.  This is a great idea, but needs redoing.

Problem is that the address spaces for the various kinds of
entities are arranged contiguously, with no gaps in between.  This
make it impossible to expand the address range for some particular
kind of entity without disturbing the other address ranges.

We propose instead to use a tag-and-value scheme.  A
compile-time-pointer
is still a 32-bit integer, but divided up thusly:
\begin{verbatim}
   <-1-> <--7--> <--24-->
       0     tag    value
\end{verbatim}
The tag space is arranged like this (pretty arbitrary; requires a
trawl through existing storage.h to pick up all stuff):
\begin{verbatim}
   000 0000    is an illegal tag
   0xx xxxx    denotes a heap number.  value field is address in that heap.
   100 0000    Text
   100 0001    Name
   100 0010    Class
   100 0011    Instance
   100 0100    an integer; 24-bit value field gives value
   100 0101    Object symbol table entry
   100 0110    Tuple constructor; value field gives tuple number
   100 0111    Offset; value in value field
   ........
   101 0000    ``Box cell tag'' (TAGMIN .. BCSTAG); 
               actual value is in value & 0xff
   101 0001    ``Constructor tag'' (LETREC .. SPECMIN-1); 
               value is in value & 0xff
   101 0010    ``Special tag'' (SPECMIN .. PREDEFINED);
               value is in value & 0xff
\end{verbatim}
\verb@000 0000@ is an illegal tag so that we can continue the
convention
that a 32-bit zero word means NIL.  We could have redefined NIL, but
it is frequently tested for, and tests against zero are fast on most
(RISC) architectures.

There are up to 63 possible heaps, each with up to 16 M entries.
This facilitates a dynamically expanding heap.  The idea is to start
off with a single small heap of say 20000 cells.  When this fills,
a new lump of memory can be malloc'd and used as a second heap, of
perhaps 40000 cells, giving 60000 in total.  Hugs needs to know the
size of each heap for GC purposes, but there are no required size
relationships between them.  

In principle, if Hugs can guarantee that there are no references
to a given heap, it can return that memory to the operating system
(or at least \verb@free@ it).

This is a tradeoff.  The \verb@fst@ and \verb@snd@ macros 
take more instructions:
\begin{verbatim}
   #define fst(p)    heap[p >> 24][p & 0xffffff].fst
   #define snd(p)    heap[p >> 24][p & 0xffffff].snd
\end{verbatim}
Each of these translate to 5 Intel x86 insns; I have measured it.
In the current Hugs, \verb@fst@ and \verb@snd@ are just array
references, possibly just 1 x86 insn.
On the other hand, if \verb@fst(p)@ is referenced close in time
to \verb@snd(p)@, for the same \verb@p@, it's likely that the
second reference will still be in the CPU's data cache.  The original
Hugs has separate arrays for \verb@fst@ and \verb@snd@.

Further compensation is that the ubiquitous \verb@whatIs@ call
is a lot cheaper this way, since we just shift out the tag:
\begin{verbatim}
   #define whatIs(x)     ((x) >> 24)
\end{verbatim}
which is just a single instruction, instead of a whole sequence 
implementing a binary search tree, as at present.

Texts, names, classes, and other entities with only one tag value,
can have up to 16 M entries, since the value field is 24 bits long.
After some discussion, we feel that (eg) 16 M names is enough for
programs at least ten times the size of GHC, around half a million
lines of code.

I'm going to call these entities \verb@HugsPtr@ in pseudocode bits.

\subsection{The code generator interface}
More details on how this hangs together.
\begin{verbatim}
stg2BC, stg2OTHER :: [(Name, STG_TREE)] -> ()
markRTSobjects_BC,
markRTSobjects_OTHER :: Name -> ()
\end{verbatim}
The result of translating a Haskell module to STG trees is a
{\em code list}: a list of pairs \verb@(Name, STG_TREE)@.
Each tree represents a function or CAF, either written by 
the programmer in the source module, or generated automatically,
by desugaring, \verb@deriving@ clauses, or lambda lifting.

The \verb@Name@ component of the pairs points to a name 
table entry for the tree.  And that name table entry points
back at the pair.  In previous hacking, I often needed to 
get a name table entry from a tree, and vice versa.  Without a
bidirectional link, this requires a search of all the name tables
or all the trees, which is inefficient.

So each tree has a name table entry, even if it isn't part of
the source given by the user.  That makes life simpler and more
uniform, even if it wastes a little space in the name table.

When the bytecode compiler translates source to trees, it 
generates a code list, and sets up the links from the code
list to the name table and back.

To generate bytecode objects in the GHC-RTS- or OTHER-managed
heap, \verb@stg2BC@ or \verb@stg2OTHER@ is passed the code list.
A simple interface, but what goes on inside could be quite complex.
\begin{itemize}
\item For one thing, each STG tree can turn into multiple 
      BCOs (I guess I should be more general and say ``code blocks''),
      because of the STG way of translating \verb@case@ expressions.
      At GC time, all of these need to be found and kept alive.
      
      I propose that each name table entry include the following
      fields:
      \begin{verbatim}
         code_list_entry :: HugsPtr
         rts_primary     :: HugsPtr
         rts_secondaries :: [HugsPtr]
      \end{verbatim}
      \verb@code_list_entry@ is a pointer to the relevant 
      code list pair.  The STG tree lives, of course, in the
      compile-time heap.

      After code generation, \verb@rts_primary@ and
      \verb@rts_secondaries@ hold pointers into the code blocks
      in the {\em runtime} heap.  (NB -- these pointers are
      \verb@HugsPtr@s pointing to boxed pointers in the compile-time
      heap, as at present.)  \verb@rts_primary@ holds the address
      of the code-block (or whatever one enters) generated from
      the tree as a whole.  \verb@rts_secondaries@ is a list of
      pointers to subsidiary code blocks, such as \verb@case@ 
      return continuations.

      Only the specific code generators needs to understand the
      precise meaning and layout of what \verb@rts_primary@ and
      \verb@rts_secondaries@ point at.  Each code generator
      must also supply a \verb@markRTSobjects@ function, which
      examines and marks the \verb@rts_@ entries in the specified
      name table entry.

\item Linking.  
      Code generators will have to traverse the code list twice,
      once to generate code, and once to fix inter-tree
      references.  ((Blargh -- unresolved details ahead))
      The first pass translates each tree into a collection 
      of BCOs.  Each BCO has unresolved references to other
      BCOs, but how are they recorded?  Erk.  But I don't 
      think this is v. important?
  
      In the second pass, the unresolved refs are fixed.

      It seems that the BCOs can't be constructed directly in the
      heap, because the intermediate BCOs need a fixup table which
      the final ones don't.  Current StgHugs has \verb@AsmBCO@s for
      the intermediaries, living in mallocville, and \verb@StgBCOs@
      for the Real Thing in the RTS heap.  The \verb@AsmBCO@s are
      freed at the end of code generation for a module.  Because
      Hugs doesn't support mutually recursive modules, the entire
      codegen-resolve cycle can happen on a per-module basis.

\end{itemize}

\section{\ToDo{}}
Clarify how mutually recursive object modules are loaded.


\end{document}