1 \documentstyle[11pt]{article}
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
11 % and some of my own personal preferences
12 \parindent=0in
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
21 \newcommand{\tva}{$\alpha$} % type variables
22 \newcommand{\tvb}{$\beta$}
23 \newcommand{\tvc}{$\gamma$}
25 \newcommand{\arrow}{$\enspace\to\enspace$} % type constructors
27 \newcommand{\Hugs}{{\bf Hugs\/}}
28 \newcommand{\GHC}{{\bf GHC\/}}
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)
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 }
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 }
67 \newcommand{\Portability}[1]{\par{{\bf Portability Note:} \sl #1}\par}
68 \newcommand{\Warning}[1]{\par{{\bf Warning:} \sl #1}\par}
70 % These are used for reminders, communication between authors, etc.
71 % There should be no calls to these guys in the final document.
73 %\newcommand{\ToDo}[1]{\par{{\bf ToDo:} \sl #1}\par}
74 \newcommand{\ToDo}[1]{{{\bf ToDo:} \sl #1}}
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 }
90 % Here's how you create figures
91 %
92 % \begin{figure*}
93 % \centerline{
94 % Foo
95 % }
96 % \caption{...}
97 % \label{...}
98 % \end{figure*}
100 \begin{document}
102 \title{%
103 Architecture of the Haskell Execution Platform (HEP)\\
104 Version 6
105 }
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
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.
122 Those wishing to go directly to the all-important HEP
123 interface will find it in section 6.1.
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:
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}
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}
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.
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.
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}
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.
190 \item Symbol table (names, classes, values, instances, modules) management
192 arbitrary mixtures of compiled and interpreted code in arbitrary
193 orders. It needs redoing.
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}
201 \section{Issues}
202 Here are the major architectural difficulties which have been encountered.
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}
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?
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}
256 Some less troublesome issues are
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
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.
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
278 Hugs is fairly platform independent, except
279 for its need to load object files. We can
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.
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.
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.
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}
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
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.
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
382 for execution. Responsible for arranging
383 evaluation of Haskell expressions passed from the user interfaces.
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}.
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
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.
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.
410 \item
412 manufactures symbol table entries in SSym for the specified module.
414 Analogously to BC, has a submode for finding just the dependencies
415 of an interface file.
417 When called upon to load an interface, RdIF must engage Object
419 responsibility to relocate and link this file, since that's platform
421 object code to this module's SSym entry, namely the address of the
422 \cfun{\_closure} entry points.
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.
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.
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.
442 \item
443 Object Symbol Table (OSym): global object-level symbol table.
444 Contains a binding for every symbol in every object currently
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
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?).
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
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
471 OSym with these symbols at Hugs startup time.
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).
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}
498 \item
499 Underlying everything is the compile-time storage manager.
500 Details currently hazy.
501 \end{itemize}
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
519 |
520 StorMgr
521 & Eval
522 \end{verbatim}
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.
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.
540 \section{The component interfaces}
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.
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 {
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?}
565 \subsubsection{Servers}
566 \begin{verbatim}
567 getServer :: HsServer
569 interface HsServer : IUnknown {
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.
581 A client can ask a \verb@HsServer@ object whether it is
583 HEPs hosted on non-GHC-supporting platforms will return
584 \verb@False@ here. The HEP will still work but must
585 interpret everything.
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.
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.
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.
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.
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,
630 \begin{verbatim}
631 interface LoadHooks : IUnknown {
632 findModule :: String
633 -> (Maybe InStream, Maybe (InStream, InStream))
634 -- .hs file, (.hi file, .o file)
636 setProgress :: String -> Float -> Bool
637 -- True <=> abandon compilation please
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.
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}
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.
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.
686 \begin{verbatim}
687 interface Showable : IUnknown {
688 show :: String
689 }
691 interface Error : Showable {
692 source :: InStream
693 line, col :: Int
694 }
695 \end{verbatim}
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
708 idVal :: String -> Maybe HsVal
709 -- The name of a top-level value in
710 -- scope in the module
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]
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.
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.
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.
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.
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}
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@.
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}.
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
786 apply :: [HsVal] -> Maybe HsVal
787 -- can fail because of type error
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
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
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?}
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.
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
838 \subsubsection{Threading issues for the HEP}
840 managed and scheduled by the RTS's scheduler, and operating-system
844 starts a single main'' thread, and that can create new
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.
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.
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.
869 \subsection{Haskell to STG compiler (Hs2Stg)}
870 \begin{verbatim}
871 -- look at text of module and get import list
872 getImportList :: ModuleName -> [ModuleName]
874 -- convert .hs to stg trees
875 compileModule :: ModuleName -> [STG]
876 \end{verbatim}
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]
890 -- load a group of modules, resolving references between them
891 -- update OSym and SSym
892 loadObjectGroup :: [ModuleName] -> ()
893 \end{verbatim}
897 \subsection{Source symbol table (SSym)}
898 \begin{verbatim}
899 -- create/delete entries for a new module
900 newModule :: ModuleName -> ()
901 delModule :: ModuleName -> ()
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}
910 \subsection{Object symbol table (OSym)}
911 \begin{verbatim}
912 -- add, delete module-level entries
913 addOMod :: ModuleName -> ()
914 delOMod :: ModuleName -> ()
916 addOSym :: ModuleName -> Name -> Pointer -> ()
917 findOSym :: ModuleName -> Name -> Pointer
918 \end{verbatim}
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}
935 \subsection{Storage manager and evaluator (RTS)}
936 \begin{verbatim}
937 -- eval this ptr to WHNF
938 enter :: Pointer -> ()
939 \end{verbatim}
943 \subsection{Code generators, STG to bytecode (Stg2BC) and STG to OTHER
944 (Stg2Com)}
945 \begin{verbatim}
946 stg2BC, stg2OTHER :: [STG] -> ()
947 \end{verbatim}
950 \subsection{The user interfaces}
951 ... don't have a programmatic interface.
956 \section{Tentative design details looking for a home}
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.
962 \subsection{Compile-time storage management}
963 {\bf ToDo}: draw some pictures of how the tables interrelate.
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}
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).
1001 Let's call these values compile-time pointers''.
1003 GHC's storage manager would need to be modified to
1004 deal with fields which might or not might be pointers.
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.
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.
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.
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.
1039 When a module is deleted, all its name table entries are put back on
1040 the free list.
1042 The tycon, instance and class tables function in exactly the same way.
1043 The module table is different.
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.
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.
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.
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.
1073 Tycons, classes and instances use exactly the same scheme.
1076 \subsubsection*{The module table}
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.
1090 \subsubsection*{The text table}
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
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.
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.
1106 \subsubsection*{The object symbol table}
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.
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.
1121 \subsubsection*{Dividing up the compile-time-pointer space}
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.
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.
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.
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.
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).
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@.
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.
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.
1206 I'm going to call these entities \verb@HugsPtr@ in pseudocode bits.
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.
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.
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.
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.
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.
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.
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.
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.
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?
1282 In the second pass, the unresolved refs are fixed.
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.
1293 \end{itemize}
1295 \section{\ToDo{}}
1296 Clarify how mutually recursive object modules are loaded.
1299 \end{document}