Copy the right ghc-pkg.bin into bindists
[ghc-hetmet.git] / docs / hep / hep.tex
1 \documentstyle[11pt]{article}
2
3 % copied from the Haskore tutorial
4 \textheight=8.5in
5 \textwidth=6.5in
6 \topmargin=-.3in
7 \oddsidemargin=0in
8 \evensidemargin=0in
9 \parskip=6pt plus2pt minus2pt
10
11 % and some of my own personal preferences
12 \parindent=0in
13
14 \newcommand{\var}[1]{{\tt #1\/}}    % variables
15 \newcommand{\fun}[1]{{\tt #1\/}}    % functions
16 \newcommand{\expr}[1]{{\tt #1\/}}   % expressions
17 \newcommand{\type}[1]{{\tt #1\/}}   % types
18 \newcommand{\class}[1]{{\tt #1\/}}  % classes
19 \newcommand{\module}[1]{{\tt #1\/}} % modules
20
21 \newcommand{\tva}{$\alpha$} % type variables
22 \newcommand{\tvb}{$\beta $}
23 \newcommand{\tvc}{$\gamma$}
24
25 \newcommand{\arrow}{$\enspace\to\enspace$} % type constructors
26
27 \newcommand{\Hugs}{{\bf Hugs\/}}
28 \newcommand{\GHC}{{\bf GHC\/}}
29 \newcommand{\Haskell}{{\bf Haskell\/}}
30
31 \newcommand{\cexpr}[1]{{\tt #1\/}}   % C expressions
32 \newcommand{\ctype}[1]{{\tt #1\/}}   % C types
33 \newcommand{\cvar}[1]{{\tt #1\/}}    % C variables
34 \newcommand{\cfun}[1]{{\tt #1\/}}    % C functions
35 \newcommand{\cfile}[1]{{\tt #1\/}}   % C files (.c, .h, etc)
36
37 \newenvironment{aside}{%
38   \medbreak
39   \noindent
40   {\bf Aside: }
41   \begingroup
42     \sl
43     \begin{indent}  % why doesn't this do what I expect?
44 }{%
45     \end{indent}
46   \endgroup
47   \par
48   {\bf End aside.}
49   \medbreak
50 }
51
52 \newenvironment{note}{%
53   \medbreak
54   \noindent
55   {\bf Note: }
56   \begingroup
57     \sl
58     \begin{indent}  % why doesn't this do what I expect?
59 }{%
60     \end{indent}
61   \endgroup
62   \par
63   {\bf End note.}
64   \medbreak
65 }
66
67 \newcommand{\Portability}[1]{\par{{\bf Portability Note:} \sl #1}\par}
68 \newcommand{\Warning}[1]{\par{{\bf Warning:} \sl #1}\par}
69
70 % These are used for reminders, communication between authors, etc.
71 % There should be no calls to these guys in the final document.
72
73 %\newcommand{\ToDo}[1]{\par{{\bf ToDo:} \sl #1}\par}
74 \newcommand{\ToDo}[1]{{{\bf ToDo:} \sl #1}}
75
76 \newenvironment{outline}{%
77   \medbreak
78   \noindent
79   {\bf Outline: }
80   \begingroup
81     \nobreak
82     \sl
83 }{%
84   \endgroup
85   \nobreak
86   {\bf End outline.}
87   \medbreak
88 }
89
90 % Here's how you create figures
91 %
92 % \begin{figure*}
93 % \centerline{
94 % Foo
95 % }
96 % \caption{...}
97 % \label{...}
98 % \end{figure*}
99
100 \begin{document}
101
102 \title{%
103   Architecture of the Haskell Execution Platform (HEP)\\
104   Version 6
105 }
106
107 \author{Julian Seward, Simon Marlow, Andy Gill, Sigbjorn Finne, Simon
108   Peyton Jones \\
109 Microsoft Research, Cambridge, UK\\
110 {\tt \{v-julsew,simonmar,v-sfinne,simonpj\}@microsoft.com}, {\tt andy@cse.ogi.edu}}
111 \date{29 July 1999}
112 \maketitle
113
114
115
116 \section{What this document is for}
117 As the combined GHC--Hugs system comes ever closer to running compiled
118 code, it becomes clearer than an architectural overhaul is
119 needed.  We at MSRC, together with Andy Gill, have been discussing
120 this at length.
121
122 Those wishing to go directly to the all-important HEP
123 interface will find it in section 6.1.
124
125 \section{Names}
126 One frequent point of confusion in our discussions so far has
127 been what the names mean.  Here's some defns:
128
129 \begin{itemize}
130 \item ``GHC'' is the standalone native-code compiler.
131 \item ``Hugs''
132   denotes the version built from sources in the Glasgow tree,
133   using an STG back end and GHC runtime support.  On supported
134   architectures, Hugs will be able to load binaries compiled by GHC.
135 \item ``Hugs98'' is the current public distribution.  This document is not
136   concerned with it.  Further changes to
137   Hugs98 will be bugfixes/maintenance, and we expect that Hugs will
138   supercede Hugs98 at some point.
139 \end{itemize}
140
141
142 \section{Rationale and motivation}
143 As of 10 June, Hugs is able to load and run
144 extremely simple functions compiled by GHC.  To get to this stage has
145 required drastic changes to the original Hugs98 from which it was
146 derived:
147 \begin{itemize}
148 \item dumping the original back end and runtime support, and using
149   an STG-based code generator and GHC's RTS instead.
150 \item adding a new parser to read GHC's interface files (easy) and
151   a significant amount of code to manufacture appropriate
152   symbol table entries (not so easy).
153 \item modifying the import chasing mechanism to follow dependencies
154   through both source and interface files.
155 \end{itemize}
156
157 These changes, particularly the latter two, are inelegantly integrated
158 into the original structure.  It is clear that whatever Hugs
159 emerges as a result of my current hackery will be more a
160 proof-of-concept vehicle than as something which we can carry
161 forwards.  Some of the design decisions I made on the way are, in
162 hindsight,  bad.  A decent system will need a cleaned-up
163 architecture.
164
165 Hugs is becoming more complex as more parties modify it for their own
166 diverse purposes.  There are now various user interfaces (WinHugs, the
167 ``standard'' text UI, the HaskellScript stuff, and RunHugs).  Not far
168 ahead will come the further complexity of supporting multiple code
169 generators.  We already have the original and STG codegens, and 
170 further codegens are proposed for Hugs and GHC.
171
172 A powerful motivating factor for redoing the architecture is to try
173 and modularise Hugs so that
174 \begin{itemize}
175 \item supporting these various extensions is simpler.
176 \item supporting different platforms is simpler.  Hugs is not too
177   bad, but GHC is very Unix oriented.
178 \item new extensions don't involve grappling with so many
179   parts of the system.
180 \item building customised variants is simpler.
181 \end{itemize}
182
183 Finally, it would be nice to at least review, and possibly redo, some
184 aspects of the existing code base:
185 \begin{itemize}
186 \item The conservative garbage collector (now reduced to compile-time only
187   duty in Hugs) has been much discussed.  Perhaps we could
188   do away with it and use the GHC heap instead.
189
190 \item Symbol table (names, classes, values, instances, modules) management
191   in Hugs is too inflexible to support loading and unloading of
192   arbitrary mixtures of compiled and interpreted code in arbitrary
193   orders.  It needs redoing.
194
195 \item The import chasing mechanism is hard to understand, and has proven
196   difficult to adapt for use in Hugs.  Redesign is unavoidable.
197 \end{itemize}
198
199
200
201 \section{Issues}
202 Here are the major architectural difficulties which have been encountered.
203
204 \begin{itemize}
205 \item 
206   What mixtures of compiled and interpreted code should be supported?
207   Currently there are at three proposals, in increasing order of
208   complexity to implement:
209   \begin{itemize}
210   \item ``Downward closure'': if module M is compiled, then all modules
211      reachable from M, including Prelude, must be too.
212   \item ``Prelude + any'': arbitrary mixtures are allowed, with the proviso
213      that if any module is compiled, then the Prelude must be compiled
214      too.
215   \item ``Any'': any mixture at all.
216   \end{itemize}
217   Underlying problems are:
218   \begin{itemize}
219   \item 
220      Run-time linking of object files.  Use of the Unix \cfun{dlopen}
221      facility mandates a downward closure approach, since there is
222      no way to resolve references to interpreted code from compiled
223      code.  How the windows DLL loaders would behave I don't know.
224      To be more flexible seems to require writing one's own linkers.
225   \item
226      Primops.  Operations on, and assumptions about representation of
227      primops have to be compatible in compiled and interpreted code.
228      One possibility is to ensure that Hugs's and GHC's primops
229      exactly correspond.  That seems wasteful, and difficult and
230      bug-prone to maintain.  Another approach it to route all
231      primop calls to GHC, probably by routing them all via a
232      GHC-compiled Prelude.
233   \item
234      Interface files.  All but the downward closure option require
235      Hugs to generate interface files for interpreted modules
236      so GHC can compile against them.
237   \end{itemize}
238
239 \item
240   When the user asks ``:reload'', how should Hugs go about bringing
241   the execution environment up-to-date?  How intelligent should it be?
242   (how accurately do we track changes in the module dependencies?)
243   Where do we put the intelligence?  Is Hugs allowed to invoke GHC,
244   or must the user do it?  Do the different user interfaces require
245   different levels of sophistication?
246
247 \item
248   For platforms on which GHC is not supported, 
249   we still desire to build a standalone Hugs without object loading
250   facilities.
251   The main trickyness is that a standalone Hugs will have to supply 
252   its own implementation of primops, since it can't rely on use of
253   primop facilities in a GHC-compiled prelude.
254 \end{itemize}
255
256 Some less troublesome issues are
257
258 \begin{itemize}
259 \item
260   We might want a form of BCO which can be dumped
261   into a file and reloaded/linked later.  One use would be to 
262   give an architecture-neutral way to distribute libraries
263   in binary form.  Another is for shipping code across a network.
264   Finally, for platforms on which GHC is not supported, it offers
265   the possibility of fast startup, by loading \cfun{Prelude.bco} and
266   reading \cfun{Prelude.hi}.  One consequence of doing dumpable
267   BCOs is that Hugs would need to create interface files.
268 \item
269   Multiple code generators.  If Hugs is to acquire other code
270   generators, it may be desirable to create an interface at the
271   boundary between STGland and the code generators.
272
273   Since GHC may also want to target new platforms, work on new
274   code generators should aim to maximise compatibility between
275   Hugs and GHC.
276 \item
277   Loading object files.  
278   Hugs is fairly platform independent, except
279   for its need to load object files.  We can
280   create an object file loading/linking generic API, and hook
281   specific loaders, for example ELF and Win32 DLL, under that. 
282   However, as mentioned above, use of the native facilities may be
283   too inflexible, and so necessitate writing our own linkers.
284 \item
285   Object vs source-level symbol tables.
286   For each function \cfun{f} that GHC compiles, a whole
287   bunch of symbols are spewed into the object code: \cfun{f\_closure},
288   \cfun{f\_entry}, \cfun{f\_info} and \cfun{f\_fastk}, at the very
289   least.
290
291   On the one hand, you need to remember all these names because other
292   object modules will reference them.  On the other hand, the bytecode
293   compiler is only interested in source-level facts about \cfun{f}, such as
294   its type, and not about the addresses of its derivative symbols.
295   We propose to have a
296   separate symbol table for object code symbols, with only minimal
297   connection to the source-level symbol table (a pointer to
298   \cfun{f\_closure} ?)
299 \item
300   Replacement of the conservative garbage collector.  It doesn't
301   make much sense to have two heaps, allocators and GCs in the new Hugs.
302   Either we can move compile-time allocation into the
303   execution heap, or move to an arena-based allocator.  Hugs allocates
304   heap when compiling so slowly that the latter possibility is quite
305   practical.  Either way, the main criteria is to reimplement the \cfun{fst},
306   \cfun{snd}, \cfun{pair}, \&c, macros, so that client code doesn't have to be
307   changed.
308
309   Changing the heap representation would require a new scheme
310   for dealing with Hugs' symbol tables, since pointers to places
311   outside the (Hugs) heap are interpreted in various ways, including
312   as symbol table references.
313
314   It's also unclear what the consequences would be of any client
315   code which dynamically changes the type of a (eg) pair field
316   from pointer to non-pointer, or vice versa.
317 \item 
318   Dictionary layouts.  Hugs and GHC need to agree on the order
319   in which dictionary arguments are passed, and on the order of
320   methods within a dictionary.  We also need to make GHC regard
321   selector functions as possibly overloaded, if necessary,
322   and pass dictionaries appropriately.
323 \item
324   Currently GHC, and therefore Hugs, is very Unix oriented.  This
325   is not acceptable for a standalone Hugs.  The main blocking points for
326   development on WinNT are the GHC driver (Perl) and the
327   build environment (GNU Make).
328 \item
329   Profiling.  If Hugs is to be able to do profiling,
330   it needs to be able to handle scc annotations and probably implement
331   auto-sccification.  Will it be difficult to make sure the
332   implemented cost semantics are the same as that of GHC ?
333 \item 
334   Type system extensions.  If Hugs is to implement them, Hugs and
335   GHC must agree on them.  Currently: multiparam type classes, 
336   local universal quantification, existential quantification.
337 \item 
338   Issues to do with startup and loading the Prelude, so as
339   to minimise code duplication and complexity in Hugs.
340   Interacts with the primops issue.
341 \item
342   Andy is interested in looking into some hooks for debugging.
343 \end{itemize}
344
345
346 \section{Proposed structure}
347 \begin{verbatim}
348               TextUI    WinUI  HaskellScript  etcUI    VisualStudio
349                  |        |         |          |           |
350                  +--------+----+----+----------+ ..........+
351                                |
352                              ..... HEP interface
353       /~                       |
354       |                    Session                     ((Compile-time
355       |                    Manager                       storage mgr))
356       |                        |
357  HEP -+        +----------+----+----+----------+---------+
358       |        |          |    |    |          |         |
359       |    Bytecode    Source  |  Object     Object    IFace
360       |    Compiler    SymTab  |  Loader     SymTab    Reader
361       \_                       |
362                             StorMgr
363                             & Eval
364 \end{verbatim}
365 This crude picture depicts the main blocks, with lines indicating flow
366 of control, not data.  Underlying all components is the compile-time
367 storage manager.  The session manager is central to the design, so
368 I'll start there.
369
370 The parts from the Session Manager on downwards, including the 
371 compile-time storage manager, are collectively known as the
372 Haskell Execution Platform (HEP).  HEP has to support a diversity
373 of clients, both those which offer human user interfaces (TextUI,
374 WinUI, etc) or those offering higher level programmatic interfaces
375 (HaskellScript, VisualStudio).  Because of this, the HEP interface
376 is critical.  It is described in detail in Section 6.1.
377 \begin{itemize}
378 \item
379   Session manager (SM): Responsible for building an up-to-date
380   executable image (mixture of byte and native code) when the user
381   interfaces request a particular Haskell module to be made available
382   for execution.  Responsible for arranging
383   evaluation of Haskell expressions passed from the user interfaces.
384
385   To build an up-to-date image, SM needs to keep track of module
386   dependencies and source/object in-or-out-of-dateness, so as to
387   determine when to reload/recompile modules.
388   It's fair to say that SM will have to
389   incorporate the functionality of (\cfun{hbc|nhc|}$\epsilon$)\cfun{make}.
390
391   The RTS can support multiple Haskell threads running concurrently,
392   so SM offers that service too.  This might be useful for a GUI based
393   Hugs in which there are multiple read-eval windows.  Further, SM
394   needs to offer GUIs a way to check their own event queues whilst the
395   evaluator or compiler is running.  We have devised what we hope is a
396   flexible scheme to support this.  The same mechanism allows UIs to
397   interrupt compilation or evaluation in a portable manner.
398 \item
399   Bytecode Compiler (BC): the previous core of Hugs.  Reads Haskell
400   source and translates it via STG code to bytecode, which it places
401   in the (runtime) heap.  Updates the Source SymTab (SSym) entry for
402   this module and references SSym entries for other modules.
403   Optionally emits a simple, GHC-readable interface file for the
404   module.
405
406   In order that SM can determine the dependencies of a given source
407   file without attempting full compilation, BC has a facility to parse
408   a file and return the import list, but do nothing more.
409
410 \item
411   IFace Reader (RdIF): reads GHC created interface files and
412   manufactures symbol table entries in SSym for the specified module.
413
414   Analogously to BC, has a submode for finding just the dependencies
415   of an interface file.
416
417   When called upon to load an interface, RdIF must engage Object
418   Loader (OLoad) to load the corresponding object file.  It is OLoad's
419   responsibility to relocate and link this file, since that's platform
420   dependent.  However, RdIF must add some minimal info about the
421   object code to this module's SSym entry, namely the address of the
422   \cfun{\_closure} entry points.
423
424 \item
425   Source Symbol Table (SSym): is the global source-level symbol
426   table, containing info on modules (imports, exports), classes
427   (types, members, etc), instances, tycons and functions.  This is
428   what BC will have to consult and update in order to static-check and
429   typecheck source files.  SSym only contains enough info about object
430   files to be able to create calls to GHC compiled functions.  At the
431   moment this would appear to be the \cfun{f\_closure} addresses.
432
433   SSym must be designed so that modules can be thrown out of the
434   system in any order, rather than just the stack-like order in the
435   current Hugs.  Fixed limits on table sizes should also be avoided.
436
437   SSym must be designed so client code doesn't have to change.
438   I think most accesses go via the \cfun{name}, \cfun{isName},
439   \cfun{findName}, \cfun{newName} macros (ditto \cfun{module},
440   \cfun{cclass}, \cfun{inst}, \cfun{tycon}), so it's ok.
441
442 \item
443   Object Symbol Table (OSym): global object-level symbol table.
444   Contains a binding for every symbol in every object currently
445   loaded.  New objects can be linked merely by querying OSym;
446   no reference to SSym is needed.  As motivation, GHC compiled 
447   functions have dozens of symbols not referred to at the source
448   level but which are referred to from other objects, and also 
449   internally between code and data sections, so we need
450   to record their addresses.
451
452
453 \item
454   Object Loader (OLoad) has two duties: (1) bring an object file into
455   memory and create OSym entries for it.  (2) resolve references in an
456   object file in memory by consulting OSym (and possibly SSym?).
457
458   OLoad is obviously object-format dependent.  It should be structured
459   so that it has a 
460   format independent interface, and implementations of (1) and (2) for
461   each format (ELF, DLL, COFF, etc).  The ELF implementation is
462   already done and takes only about 300 lines of C.
463
464   Extra complication: object files can refer to symbols in the RTS,
465   and to symbols like \cfun{printf}.  These symbols will be bound into the
466   executable Hugs image at the time that is built.   So we need a
467   way to find the addresses of symbols ``in this process image''.  On
468   one hand, logically it is up to OSym to supply these addresses.  But
469   this is also object/executable format dependent, so OLoad needs to
470   be involved.  Blargh.  Possibly have an OLoad call to preload 
471   OSym with these symbols at Hugs startup time.
472
473
474 \item
475   Storage Manager and Evaluator (RTS): This is the GHC RTS,
476   along with the bytecode interpreter already in StgHugs.  Executes the
477   native/bytecode mixture.  (Not sure what else to say.  This is
478   what Simon and Alastair created.  It works and is more or less in
479   the required form).
480
481
482 \item
483   The user interfaces, TextUI, WinUI, RunHugsUI, etc.  These wrap up
484   the services of SM and present them to the end-user, either human
485   or programmatic, in some
486   appropriate way.  The pictures show multiple interfaces built into
487   the system, but in practice we expect only one to be linked in to
488   any particular system.  The requests that they can pass to SM are:
489   \begin{itemize}
490   \item Initialise system, shut down.
491   \item Change system settings (implements :set in Hugs)
492   \item Prepare a module for use, returning a module handle.
493   \item Translate expressions in the context of a given module.
494   \item Evaluate a translated expression.
495   \item Query SSym (so that :info, :type, etc can be implemented)
496   \end{itemize}
497
498 \item
499   Underlying everything is the compile-time storage manager.
500   Details currently hazy.
501 \end{itemize}
502
503 \subsubsection*{Possible variant 1: multiple code generators}
504 Chop up BC, so it becomes a single source-to-STGcode converter
505 plus some number of STGcode-to-whatever code generators.
506 Hopefully the code generators would all have the same interface.
507 \begin{verbatim}
508   TextUI    WinUI   RunHugsUI  etcUI    VisualStudio
509      |        |         |        |           |
510      +--------+----+----+--------+ ..........+
511                    |
512                 Session                     ((Compile-time
513                 Manager                       storage mgr))
514                    |
515    +----------+----+----+----------+---------+--------+----------+
516    |          |    |    |          |         |        |          |
517  Haskell   Source  |  Object     Object    IFace    STG to     STG to
518  to STG    SymTab  |  Loader     SymTab    Reader   Bytecode   OTHER
519                    |
520                 StorMgr
521                 & Eval
522 \end{verbatim}
523
524 \subsubsection*{Possible variant 2: dumpable BCOs}
525 If BCOs are dumpable to file, they can be regarded as just another
526 flavour of object format.  Then the Haskell to BCO (BC) component can
527 be factored off into another process.  Loading of BCOs would be done
528 via OLoad, with RdIF reading the interface files which would have
529 to be created by BC.  It also means BC would have to read
530 interface files.
531
532 This scheme has overheads in both compile speed and
533 implementational complexity.  The point of mentioning it is to
534 emphasise the idea that there's no particularly fundamental reason why
535 the BC component should be compiled into SystemC whilst GHC remains a
536 separate entity.  If we need to do this, it's not difficult.
537 However, nor is it at present of the highest priority.
538
539
540 \section{The component interfaces}
541
542 Many of the calls can fail.  It would be good to think about a
543 consistent error-recovery strategy.  I've ignored any error cases
544 in the signatures below.  I'm working with Variant 1 (multiple code
545 generators) above.
546
547
548
549 \subsection{Session manager (SM)}
550 These interfaces are presented in IDLishly, with
551 Haskell types.  Regard the return types as really being \verb@IO@
552 types.
553 \begin{verbatim}
554 interface IUnknown {
555    addRef, release :: ()
556 }
557 \end{verbatim}
558 All interfaces inherit reference counting methods in \verb@IUnknown@.
559 When a client copies a pointer, it should \verb@addRef@ it, and
560 conversely \verb@release@ it when done.
561 Once a pointer is \verb@release@d, the thing it points at may or
562 may not still be alive, but in any case the owner of the
563 pointer must assume it is dead.  \ToDo{Are these the COM semantics?}
564
565 \subsubsection{Servers}
566 \begin{verbatim}
567 getServer :: HsServer
568
569 interface HsServer : IUnknown {
570    loadModule   :: LoadHooks -> String -> Maybe HsModule
571
572    setOptions   :: [(String,String)] -> ()
573    getOptions   :: [(String,String)]
574    canUseObject :: Bool
575 }
576 \end{verbatim}
577 For simplicity, we assume there is only one server, obtained
578 via \verb@getServer@.  In practice they might be manufactured 
579 by a class factory (???), but that's too COM specific here.
580
581 A client can ask a \verb@HsServer@ object whether it is 
582 capable of loading object code with \verb@canUseObject@.
583 HEPs hosted on non-GHC-supporting platforms will return
584 \verb@False@ here.  The HEP will still work but must
585 interpret everything.
586
587 Clients can query and set options for this server using
588 \verb@getOptions@ and \verb@setOptions@.  \verb@getOptions@
589 returns all the available options and their current values.
590 \verb@setOptions@ can supply new values for any subset, or all, of
591 them.
592
593 \verb@HsServer@'s main purpose is to supply \verb@loadModule@.
594 Clients supply a string such as ``\verb@List@'', indicating a
595 module name, with no filename extension or directory.  
596 HEP tries to return a \verb@HsModule@ handle reflecting
597 the current state of the source/object code base.  In doing so,
598 it may need to load and/or compile arbitrary numbers of 
599 subsidiary modules.  This operation may fail, hence the \verb@Maybe@
600 return type.
601
602 Once a \verb@HsModule@ handle has been successfully acquired,
603 that handle remains valid until the client calls \verb@release@
604 on it.  What the handle refers to is the state of the object/source
605 code base at the time the handle was created.  Subsequent changes
606 to the code base have no effect on the handle; the executable images
607 to which it refers are unchanged.
608
609 For example, assuming \verb@s :: HsServer@ and \verb@h :: LoadHooks@,
610 then given the following sequence of events
611 \begin{enumerate}
612 \item \verb@m1 = s.loadModule("M", h)@, and this call succeeds
613 \item The source/object for \verb@M@ changes
614 \item \verb@m2 = s.loadModule("M", h)@
615 \end{enumerate}
616 \verb@m1@ will continue to be valid and will refer to the original
617 version of \verb@M@, whilst \verb@m2@ refers to the new version.
618 Furthermore, if \verb@M@ depends on some other
619 modules, \verb@m1@ will still be based on the
620 original version of those modules, even if their sources/objects
621 change.  In short, once a \verb@HsModule@ comes into existence,
622 its meaning never changes.
623
624 \subsubsection{Load-time hooks}
625
626 HEP decides for itself what modules it needs to load, when, and
627 in what order.  It is up to the client to supply the
628 actual source/object code for modules.  To facilitate this, 
629 clients must pass a \verb@LoadHooks@ object to \verb@loadModule@:
630 \begin{verbatim}
631 interface LoadHooks : IUnknown {
632    findModule :: String
633          -> (Maybe InStream, Maybe (InStream, InStream))
634       -- .hs file, (.hi file, .o file)
635
636    setProgress :: String -> Float -> Bool   
637       -- True <=> abandon compilation please
638
639    error :: Error -> ()
640 }
641 \end{verbatim}
642 When HEP needs a module, it calls \verb@findModule@, passing it
643 the unadorned module name, unadorned in the same way as names 
644 passed to \verb@loadModule@.  The client should attempt to locate
645 source, interface and object streams for the module in any way
646 it pleases.  The returned pair is a possible stream for the
647 source text, and a possible pair of streams for the interface
648 and object text.  This latter pairing exists because there's
649 no point in producing an object stream without the corresponding
650 interface stream, or vice versa.
651
652 An \verb@InStream@ is an abstract handle with which to read a finite stream.
653 \verb@getChar@ reads the next character or returns an end-of-file
654 marker.  \verb@fprint@ returns a fingerprint, perhaps a checksum,
655 or a file timestamp,
656 which characterises the stream's contents.  \verb@eqFPrint@ compares
657 this stream's fingerprint against a supplied one.  The fingerprinting
658 semantics requires that two identical streams have identical
659 fingerprints. \ToDo{Do we care that this isn't implementable,
660 strictly speaking?}  The intention is to provide HEP with a 
661 way to determine to whether a given stream has changed since it was
662 last looked at.  \verb@FPrint@ is regarded as an abstract type
663 supplied by the client.
664 \begin{verbatim}
665 interface InStream : IUnknown {
666    getChar  :: Int
667    fprint   :: FPrint
668    eqFPrint :: FPrint -> Bool
669 }
670 \end{verbatim}
671
672 HEP notifies the client of compilation/loading progress by calling
673 \verb@setProgress@, giving the name of a goal, eg ``Typechecking'',
674 and a value, increasing monotonically over a sequence of such calls,
675 from $0.0$ to $1.0$, indicating progress towards that goal.
676 If the client returns \verb@True@ to such a call, HEP abandons 
677 compilation as soon as possible.  In this way, clients can
678 interrupt compilation in a portable manner.
679
680 If a compilation error occurs, HEP creates a \verb@Error@ object
681 and passes it to the client with \verb@error@.  For the moment,
682 the error object only contains the source coordinates of the
683 error, the \verb@InStream@ from which the source originated,
684 and a method \verb@show@ which produces the text of the error message.
685 Later versions may contain more information.
686 \begin{verbatim}
687 interface Showable : IUnknown { 
688    show :: String
689 }
690
691 interface Error : Showable {
692    source    :: InStream
693    line, col :: Int
694 }
695 \end{verbatim}
696
697 \subsubsection{Modules}
698 Once a client has obtained a \verb@HsModule@ handle, it can
699 translate and run expressions in the context of that module.
700 Translated values are \verb@HsVal@ objects.
701 \begin{verbatim}
702 interface HsModule : IUnknown {
703    exprVal :: String -> Bool -> Maybe HsVal
704       -- A Haskell expression, treated as if
705       -- it was written in the module
706       -- Bool==True <=> wrap in `print' if not :: IO t
707
708    idVal :: String -> Maybe HsVal
709       -- The name of a top-level value in
710       -- scope in the module
711
712    -- takes a regexp, gives list of things
713    -- defined in (Bool==True) or in scope in (Bool==False) this mod
714    getNames     :: Bool -> String -> [Name]
715    getTypes     :: Bool -> String -> [Type]
716    getTycons    :: Bool -> String -> [Tycon]
717    getClasses   :: Bool -> String -> [Class]
718    getInstances :: Bool -> String -> [Instance]
719
720    -- query a specific thing.  String is a name.  Bool as above.
721    findName     :: Bool -> String -> Maybe Name
722    findType     :: Bool -> String -> Maybe Type
723    findTycon    :: Bool -> String -> Maybe Tycon
724    findClass    :: Bool -> String -> Maybe Class
725    findInstance :: Bool -> String -> String -> Maybe Instance
726 }
727 \end{verbatim}
728 The two important methods are \verb@exprVal@ and
729 \verb@idVal@.  \verb@exprVal@ takes an arbitrary Haskell
730 expression and tries to return a translation of it in the
731 context of that module.  The caller can optionally ask to
732 have the value wrapped in \verb@print@, since that is often
733 convenient.
734
735 \verb@idVal@ is simpler.  It simply regards the supplied string
736 as the name of a top-level function in scope in the module, and
737 returns a \verb@HsVal@ referring to that name.  It's conceivable
738 that a skeletal HEP which just loaded object files could implement
739 \verb@idVal@ but not \verb@exprVal@.  Such a HEP would not need
740 a bytecode compiler or interpreter.
741
742 The \verb@get*@ and \verb@find*@ methods allow clients to consult
743 the HEP's symbol tables.  In all cases, the \verb@Bool@
744 parameter facilitates choosing between ``defined in this module''
745 and ``in scope in this module'' interpretation of queries.
746
747 \verb@getNames@ returns the names of all top-level values
748 matching the wildcard in the supplied string, defined in or
749 in scope in this module.  \verb@findName@ returns the 
750 corresponding information for a specific name; the supplied
751 string must be a real name and not a wildcard.  The \verb@Type@,
752 \verb@Tycon@, \verb@Class@ and \verb@Instance@ calls function
753 analogously for types, type constructors, classes and instances.
754
755 As with error messages, currently the only possible action with 
756 a name, type, tycon, class or instance is to print it.  This
757 may change later.
758 \begin{verbatim}
759 interface Class    : Showable { }
760 interface Type     : Showable { }
761 interface Instance : Showable { }
762 interface Tycon    : Showable { }
763 interface Name     : Showable { }
764 \end{verbatim}
765
766 \subsubsection{Values}
767 A Haskell value is represented by a \verb@HsVal@ object.
768 \verb@HsVal@s carry their type, which is obtained with
769 \verb@type@.  
770
771 New values can be created by application of
772 a value to a list of argument values; \verb@apply@ does this.
773 The application is typechecked, and will fail if it is type-incorrect.
774 \ToDo{Say more about the rules and extent of this}.
775
776 For convenience, new values can be manufactured from integers,
777 using \verb@mkIntValue@.  The inverse operation is \verb@intValueOf@,
778 which will fail if the type is wrong.  Such mistakes can be avoided
779 by first testing with \verb@isIntValue@.  \ToDo{What does
780 \verb@intValueOf@ do if the arg is not in whnf?}  Similar functions
781 exist for other primitive types.
782 \begin{verbatim}
783 interface HsVal : IUnknown {
784    type  :: Type
785
786    apply :: [HsVal] -> Maybe HsVal
787       -- can fail because of type error
788       
789    eval   :: RunHooks -> WhyIStopped   
790       -- To WHNF
791    evalIO :: RunHooks -> Maybe WhyIStopped
792       -- Runs a value of type IO t, returning the t
793       -- the result may or may not be evaluated
794
795    mkIntValue :: Int -> HsVal
796    isIntValue :: Bool
797    intValueOf :: Maybe Int
798       -- ditto Bool Char Word Float Double
799 }
800 \end{verbatim}
801 The main purpose of \verb@HsVal@ is to supply \verb@eval@ and
802 \verb@evalIO@.  \verb@eval@ evaluates a value, which may be of 
803 any type, to WHNF.  The client must supply a \verb@RunHooks@ object
804 to be used during evaluation.  \verb@evalIO@ is similar, except
805 that the supplied value must have type \verb@IO t@.   The 
806 possibly unevaluated \verb@t@ is then returned.
807 \begin{verbatim}
808 data WhyIStopped = Done
809                  | DoneIO HsVal 
810                  | YouAskedMeToStop 
811                  | NoThreadsToRun
812
813 interface RunHooks : IUnknown {
814    continue       :: Bool
815    stdout, stderr :: Char -> ()
816    stdin          :: Char
817    -- if the last three block, the entire HEP does
818 }
819 \end{verbatim}
820 A \verb@RunHooks@ object allows the client to capture \verb@stdout@
821 and \verb@stderr@ from the evaluated expression, and supply a
822 \verb@stdin@ stream for it.  If any of these calls blocks, the
823 entire HEP will too.  \ToDo{Are we sure?}
824
825 When running an expression, HEP will call \verb@continue@ on a
826 fairly regular basis, to find out if the client wants to interrupt
827 evaluation.  If the client returns \verb@True@,
828 \verb@eval@/\verb@evalIO@ then will return with the value
829 \verb@YouAskedMeToStop@.  The client can resume execution later
830 by calling \verb@eval@/\verb@evalIO@ again on that value.
831
832 \verb@eval@/\verb@evalIO@ may also return bearing \verb@Done@
833 or \verb@DoneIO@ respectively, indicating that the value has
834 reached WHNF.  Lastly, a return value of \verb@NoThreadsToRun@
835 indicates that the RTS's scheduler could not find any Haskell
836 threads to run.  This could indicate deadlock.
837
838 \subsubsection{Threading issues for the HEP}
839 There are two kinds of threads to consider: Haskell threads,
840 managed and scheduled by the RTS's scheduler, and operating-system
841 threads.
842
843 Haskell threads are easy.  An \verb@eval@/\verb@evalIO@ call
844 starts a single ``main'' thread, and that can create new
845 threads using the Haskell primitive \verb@forkIO@.
846
847 The complication lies in OS threads.  Rather than attempt
848 to design a multithreaded HEP, we place a mutex around the
849 entire HEP, and allow only one OS thread in at a time.
850 To try and create some fairness, the HEP can, at times convenient
851 to it, check whether any other OS threads are waiting to enter,
852 in which case it may yield, so as to let others enter.
853
854 Unfortunately this will cause deadlocks for Haskell programs
855 using callbacks.  Typically, a callback function will be 
856 supplied to some other subsystem (eg, graphics) using a 
857 \verb@ccall@ to that subsystem, bearing the \verb@HsVal@ of the
858 callback.  To run the callback, the subsystem will later
859 call \verb@eval@ on the callback.  But if the same OS thread is
860 still ``inside'' the HEP, this call will block.
861
862 A solution is to release the lock when an OS thread \verb@ccall@s 
863 out of the HEP.  This allows other threads, or callbacks in the
864 same thread, to successfully enter the HEP -- not necessarily 
865 immediately, but eventually, assume the OSs thread scheduling
866 is fair.
867
868
869 \subsection{Haskell to STG compiler (Hs2Stg)}
870 \begin{verbatim}
871 -- look at text of module and get import list
872 getImportList :: ModuleName -> [ModuleName]
873
874 -- convert .hs to stg trees
875 compileModule :: ModuleName -> [STG]
876 \end{verbatim}
877
878
879
880 \subsection{Interface reader (RdIF)}
881 Loading of mutually recursive groups of objects is allowed even
882 though Hugs can't handle that at the source level.  Internally,
883 \cfun{loadObjectGroup} has to make two passes through the 
884 interface files, the first to create partially-filled entries in SSym, and the 
885 second to complete those entries.
886 \begin{verbatim}
887 -- look at interface file for module and get import list
888 getImportList   :: ModuleName -> [ModuleName]
889
890 -- load a group of modules, resolving references between them
891 -- update OSym and SSym
892 loadObjectGroup :: [ModuleName] -> ()
893 \end{verbatim}
894
895
896
897 \subsection{Source symbol table (SSym)}
898 \begin{verbatim}
899 -- create/delete entries for a new module
900 newModule :: ModuleName -> ()
901 delModule :: ModuleName -> ()
902
903 -- various functions for adding/querying vars, tycons, classes, instances
904 -- and in particular
905 setClosureOf :: Name -> Pointer -> ()
906 getClosureOf :: Name -> Pointer
907 \end{verbatim}
908
909
910 \subsection{Object symbol table (OSym)}
911 \begin{verbatim}
912 -- add, delete module-level entries
913 addOMod  :: ModuleName -> ()
914 delOMod  :: ModuleName -> ()
915 -- add, find symbols
916 addOSym  :: ModuleName -> Name -> Pointer -> ()
917 findOSym :: ModuleName -> Name -> Pointer
918 \end{verbatim}
919
920
921
922 \subsection{Object loader (OLoad)}
923 \begin{verbatim}
924 -- check object for correct format, etc
925 validateObject :: ModuleName -> Bool
926 -- get object into memory and update OSym, but don't link it
927 loadObject :: ModuleName -> ()
928 -- resolve refs in previously loaded object
929 linkObject :: ModuleName -> ()
930 -- remove object from memory
931 delObject :: ModuleName -> ()
932 \end{verbatim}
933
934
935 \subsection{Storage manager and evaluator (RTS)}
936 \begin{verbatim}
937 -- eval this ptr to WHNF
938 enter :: Pointer -> ()
939 \end{verbatim}
940
941
942
943 \subsection{Code generators, STG to bytecode (Stg2BC) and STG to OTHER
944       (Stg2Com)}
945 \begin{verbatim}
946 stg2BC, stg2OTHER :: [STG] -> ()
947 \end{verbatim}
948
949
950 \subsection{The user interfaces}
951 ... don't have a programmatic interface.
952
953
954
955
956 \section{Tentative design details looking for a home}
957
958 These sections record how the various bits of the new system
959 should work.  In may places it merely records what the existing
960 system does.
961
962 \subsection{Compile-time storage management}
963 {\bf ToDo}: draw some pictures of how the tables interrelate.
964
965 Relevant structures are
966 \begin{itemize}
967 \item compile-time heap
968 \item Source symbol table, comprising: name table, tycon table,
969 class table, instance table, module table
970 \item Text table (not sure where this logically belongs)
971 \item Object symbol table
972 \end{itemize}
973 Needs to be redone.  Design goals are:
974 \begin{itemize}
975 \item Should be able to delete an arbitrary module from the system
976       and scrub all references to it.  The current Hugs scheme only
977       allows deleting of modules in a LIFO fashion.
978 \item No fixed table sizes for anything!
979       Everything to by dynamically resizable on-the-go.
980       This is a long-overdue change.
981 \item No changes to the client code.  No way do we want to rewrite
982       the typechecker, static analyser, etc.  That means that
983       any reimplementation will have to supply suitable versions
984       of the many macros used to access storage in current Hugs.
985       Indeed, the viability of this enterprise depends on
986       the observation that the current Hugs consistently uses these 
987       macros/functions and does not go directly to the structures.
988 \end{itemize}
989
990 For the time being, it seems best not to mix the compile-time
991 and run-time heaps.  It might be possible, but there are a bunch
992 of unknown factors, and fixing them seems to have a low 
993 brownie-points/effort ratio:
994 \begin{itemize}
995 \item Hugs assumes the existence of a ``generic'' pointer-ish entity.
996       This might point into the heap, but if it doesn't, then it can
997       be a reference to a symbol table, an integer, a piece of text,
998       or various other things.  This simplifies the typechecker and
999       static analysis.  (I guess you could say it's a union type).
1000
1001       Let's call these values ``compile-time pointers''.
1002
1003       GHC's storage manager would need to be modified to
1004       deal with fields which might or not might be pointers.
1005
1006 \item Assignment.  Hugs frequently (?) mutates heap objects.  I'm
1007       unsure what effect this would have on the RTS if a pointer field
1008       is changed to a non-pointer one, or vice versa.
1009
1010       Also, when doing assignments, the old-to-new pointer tables
1011       would need to be checked and updated.  Changes to
1012       client code at assignment points seem unavoidable.
1013 \end{itemize}
1014 \subsubsection*{Name, tycon, class and instance tables}
1015 Each name table entry describes a top-level value in a Haskell module.
1016 It holds a pointer to the textual name, the type, pointers to the
1017 STG trees and compiled bytecode, and various other things.  A
1018 compile-time pointer can point directly at a name table entry.
1019
1020 Like existing Hugs, we continue to organise the name table as an
1021 array of name table entries.  Unlike existing Hugs, the name 
1022 entries for a given module do not occupy a contiguous range
1023 of the name table.  To do so makes it impossible to delete 
1024 modules, since deletion of a module would create a large hole
1025 in the table.  To fill this hole, we'd have to slide other entries
1026 around, but then we'd need to find and change all
1027 compile-time pointers to the moved entries (viz, the usual
1028 compacting-GC problem).  The latter could be
1029 very difficult.
1030
1031 Instead, each name table entry has a link field, which is used to 
1032 chain together all entries for a given module.  For unused entries,
1033 the link fields implement a standard freelist.  Allocation of new
1034 entries consults the freelist.  If that's empty, the table is 
1035 expanded as follows: a bigger array, perhaps twice the size, is
1036 malloc'd.  The existing name table is copied into it, and the
1037 new entries are put on the free list.  
1038
1039 When a module is deleted, all its name table entries are put back on
1040 the free list.
1041
1042 The tycon, instance and class tables function in exactly the same way.
1043 The module table is different.
1044
1045 \subsubsection*{Notion of the ``current module's scope''}
1046 When translating a module, Hugs needs to have a way, given the text
1047 of a symbol, to (a) find out if it is in scope in this module, and 
1048 (b) if so, what value/type it is bound to.  Because a module can
1049 import symbols from other modules, the current scope is not just
1050 the contents of the current module.
1051
1052 To support this, name table entries have a second link field.
1053 This field is used to chain together all entries in the current
1054 scope.  Unlike the module-link fields, this chain necessarily
1055 visits entries from many different modules.
1056
1057 Because each name table only has one scope-link field, only
1058 one current scope can be supported at any time.  When Hugs
1059 starts processing a new module, the current scope chain has to
1060 be rebuilt for that module, by processing its import declarations,
1061 and recursing down through other modules as necessary.  This operation
1062 is expensive and should be done infrequently.
1063
1064 Having a single chain for the current scope makes
1065 name lookup terribly inefficient.   The current Hugs uses a small
1066 256 entry hash table to help.  Each hash table entry points to a
1067 chain of name-table entries with the same hash value, chained as
1068 described above through the current-scope field.  In other words,
1069 there are 256 current-scope chains, not just one, and they all 
1070 begin at the hash table.  So, when changing current module,
1071 Hugs has to rebuild the hash table as well as the chains.
1072
1073 Tycons, classes and instances use exactly the same scheme.
1074
1075
1076 \subsubsection*{The module table}
1077
1078 Unlike the name, tycon, class and instance table, this one 
1079 has exactly one entry per module.  Each entry contains 
1080 pointers to: the textual name of the module,
1081 an import list, an export list,
1082 the start of the name-table chain
1083 for this module, ditto for tycons, classes and instances, 
1084 and perhaps a pointer to a list of STG trees denoting the
1085 code generated for the module.  When a module is deleted,
1086 its module table entry is marked as unused.  This table can
1087 be resized by copying it into a larger array if needed, in the
1088 usual way.
1089
1090 \subsubsection*{The text table}
1091
1092 This remains pretty much the same as before, with the proviso
1093 that entries in it cannot be ejected when a module is deleted.  
1094 If it gets full, we expand it by copying it onto a bigger
1095 array in the usual way.  In practice this is unlikely to be
1096 a problem, since loading a revised version of a recently-deleted
1097 module is very likely to present almost the same set of strings
1098 as the old version, thereby not increasing the size of the
1099 table very much.
1100
1101 One final detail: the current hashing scheme to find stuff in
1102 the table will need to be carefully revised so that it can
1103 still work when the table size is, say, doubled.  Apparently
1104 \verb@rts/Hash.c@ contains a suitable algorithm.
1105
1106 \subsubsection*{The object symbol table}
1107
1108 We may as well make the object symbol table work in the same way as
1109 the name, tycon, class and instance tables.  That is, an array of 
1110 symbol records, with each record having a link field to chain together
1111 entries in the same module, and another field linking together entries
1112 with the same hash values.  The table can expand dynamically, and
1113 modules can be thrown out of the table in any order.  There is a
1114 top-level hash table holding the start point of the hash chains.
1115
1116 Unlike the name, class, tycon and instance tables, the hash table
1117 and chains for the object symbol table reflects all the available
1118 symbols, not just those regarded as in scope for the current module
1119 being translated.
1120
1121 \subsubsection*{Dividing up the compile-time-pointer space}
1122
1123 Hugs has always had the notion of a pointer which {\em might}
1124 point into the compile-time heap, or it might not, denoting a 
1125 name, piece of text, etc.  This is a great idea, but needs redoing.
1126
1127 Problem is that the address spaces for the various kinds of
1128 entities are arranged contiguously, with no gaps in between.  This
1129 make it impossible to expand the address range for some particular
1130 kind of entity without disturbing the other address ranges.
1131
1132 We propose instead to use a tag-and-value scheme.  A
1133 compile-time-pointer
1134 is still a 32-bit integer, but divided up thusly:
1135 \begin{verbatim}
1136    <-1-> <--7--> <--24-->
1137        0     tag    value
1138 \end{verbatim}
1139 The tag space is arranged like this (pretty arbitrary; requires a
1140 trawl through existing storage.h to pick up all stuff):
1141 \begin{verbatim}
1142    000 0000    is an illegal tag
1143    0xx xxxx    denotes a heap number.  value field is address in that heap.
1144    100 0000    Text
1145    100 0001    Name
1146    100 0010    Class
1147    100 0011    Instance
1148    100 0100    an integer; 24-bit value field gives value
1149    100 0101    Object symbol table entry
1150    100 0110    Tuple constructor; value field gives tuple number
1151    100 0111    Offset; value in value field
1152    ........
1153    101 0000    ``Box cell tag'' (TAGMIN .. BCSTAG); 
1154                actual value is in value & 0xff
1155    101 0001    ``Constructor tag'' (LETREC .. SPECMIN-1); 
1156                value is in value & 0xff
1157    101 0010    ``Special tag'' (SPECMIN .. PREDEFINED);
1158                value is in value & 0xff
1159 \end{verbatim}
1160 \verb@000 0000@ is an illegal tag so that we can continue the
1161 convention
1162 that a 32-bit zero word means NIL.  We could have redefined NIL, but
1163 it is frequently tested for, and tests against zero are fast on most
1164 (RISC) architectures.
1165
1166 There are up to 63 possible heaps, each with up to 16 M entries.
1167 This facilitates a dynamically expanding heap.  The idea is to start
1168 off with a single small heap of say 20000 cells.  When this fills,
1169 a new lump of memory can be malloc'd and used as a second heap, of
1170 perhaps 40000 cells, giving 60000 in total.  Hugs needs to know the
1171 size of each heap for GC purposes, but there are no required size
1172 relationships between them.  
1173
1174 In principle, if Hugs can guarantee that there are no references
1175 to a given heap, it can return that memory to the operating system
1176 (or at least \verb@free@ it).
1177
1178 This is a tradeoff.  The \verb@fst@ and \verb@snd@ macros 
1179 take more instructions:
1180 \begin{verbatim}
1181    #define fst(p)    heap[p >> 24][p & 0xffffff].fst
1182    #define snd(p)    heap[p >> 24][p & 0xffffff].snd
1183 \end{verbatim}
1184 Each of these translate to 5 Intel x86 insns; I have measured it.
1185 In the current Hugs, \verb@fst@ and \verb@snd@ are just array
1186 references, possibly just 1 x86 insn.
1187 On the other hand, if \verb@fst(p)@ is referenced close in time
1188 to \verb@snd(p)@, for the same \verb@p@, it's likely that the
1189 second reference will still be in the CPU's data cache.  The original
1190 Hugs has separate arrays for \verb@fst@ and \verb@snd@.
1191
1192 Further compensation is that the ubiquitous \verb@whatIs@ call
1193 is a lot cheaper this way, since we just shift out the tag:
1194 \begin{verbatim}
1195    #define whatIs(x)     ((x) >> 24)
1196 \end{verbatim}
1197 which is just a single instruction, instead of a whole sequence 
1198 implementing a binary search tree, as at present.
1199
1200 Texts, names, classes, and other entities with only one tag value,
1201 can have up to 16 M entries, since the value field is 24 bits long.
1202 After some discussion, we feel that (eg) 16 M names is enough for
1203 programs at least ten times the size of GHC, around half a million
1204 lines of code.
1205
1206 I'm going to call these entities \verb@HugsPtr@ in pseudocode bits.
1207
1208 \subsection{The code generator interface}
1209 More details on how this hangs together.
1210 \begin{verbatim}
1211 stg2BC, stg2OTHER :: [(Name, STG_TREE)] -> ()
1212 markRTSobjects_BC,
1213 markRTSobjects_OTHER :: Name -> ()
1214 \end{verbatim}
1215 The result of translating a Haskell module to STG trees is a
1216 {\em code list}: a list of pairs \verb@(Name, STG_TREE)@.
1217 Each tree represents a function or CAF, either written by 
1218 the programmer in the source module, or generated automatically,
1219 by desugaring, \verb@deriving@ clauses, or lambda lifting.
1220
1221 The \verb@Name@ component of the pairs points to a name 
1222 table entry for the tree.  And that name table entry points
1223 back at the pair.  In previous hacking, I often needed to 
1224 get a name table entry from a tree, and vice versa.  Without a
1225 bidirectional link, this requires a search of all the name tables
1226 or all the trees, which is inefficient.
1227
1228 So each tree has a name table entry, even if it isn't part of
1229 the source given by the user.  That makes life simpler and more
1230 uniform, even if it wastes a little space in the name table.
1231
1232 When the bytecode compiler translates source to trees, it 
1233 generates a code list, and sets up the links from the code
1234 list to the name table and back.
1235
1236 To generate bytecode objects in the GHC-RTS- or OTHER-managed
1237 heap, \verb@stg2BC@ or \verb@stg2OTHER@ is passed the code list.
1238 A simple interface, but what goes on inside could be quite complex.
1239 \begin{itemize}
1240 \item For one thing, each STG tree can turn into multiple 
1241       BCOs (I guess I should be more general and say ``code blocks''),
1242       because of the STG way of translating \verb@case@ expressions.
1243       At GC time, all of these need to be found and kept alive.
1244       
1245       I propose that each name table entry include the following
1246       fields:
1247       \begin{verbatim}
1248          code_list_entry :: HugsPtr
1249          rts_primary     :: HugsPtr
1250          rts_secondaries :: [HugsPtr]
1251       \end{verbatim}
1252       \verb@code_list_entry@ is a pointer to the relevant 
1253       code list pair.  The STG tree lives, of course, in the
1254       compile-time heap.
1255
1256       After code generation, \verb@rts_primary@ and
1257       \verb@rts_secondaries@ hold pointers into the code blocks
1258       in the {\em runtime} heap.  (NB -- these pointers are
1259       \verb@HugsPtr@s pointing to boxed pointers in the compile-time
1260       heap, as at present.)  \verb@rts_primary@ holds the address
1261       of the code-block (or whatever one enters) generated from
1262       the tree as a whole.  \verb@rts_secondaries@ is a list of
1263       pointers to subsidiary code blocks, such as \verb@case@ 
1264       return continuations.
1265
1266       Only the specific code generators needs to understand the
1267       precise meaning and layout of what \verb@rts_primary@ and
1268       \verb@rts_secondaries@ point at.  Each code generator
1269       must also supply a \verb@markRTSobjects@ function, which
1270       examines and marks the \verb@rts_@ entries in the specified
1271       name table entry.
1272
1273 \item Linking.  
1274       Code generators will have to traverse the code list twice,
1275       once to generate code, and once to fix inter-tree
1276       references.  ((Blargh -- unresolved details ahead))
1277       The first pass translates each tree into a collection 
1278       of BCOs.  Each BCO has unresolved references to other
1279       BCOs, but how are they recorded?  Erk.  But I don't 
1280       think this is v. important?
1281   
1282       In the second pass, the unresolved refs are fixed.
1283
1284       It seems that the BCOs can't be constructed directly in the
1285       heap, because the intermediate BCOs need a fixup table which
1286       the final ones don't.  Current StgHugs has \verb@AsmBCO@s for
1287       the intermediaries, living in mallocville, and \verb@StgBCOs@
1288       for the Real Thing in the RTS heap.  The \verb@AsmBCO@s are
1289       freed at the end of code generation for a module.  Because
1290       Hugs doesn't support mutually recursive modules, the entire
1291       codegen-resolve cycle can happen on a per-module basis.
1292
1293 \end{itemize}
1294
1295 \section{\ToDo{}}
1296 Clarify how mutually recursive object modules are loaded.
1297
1298
1299 \end{document}