[project @ 1997-11-13 17:09:40 by simonm]

[ghc-hetmet.git] / docs / rts / rts.verb

diff --git a/docs/rts/rts.verb b/docs/rts/rts.verb
index 7a5a62e..2c2f983 100644 (file)
--- a/docs/rts/rts.verb
+++ b/docs/rts/rts.verb
@@ -49,6 +49,7 @@
 
 \title{The STG runtime system (revised)}
 \author{Simon Peyton Jones \\ Glasgow University and Oregon Graduate Institute \and
 
 \title{The STG runtime system (revised)}
 \author{Simon Peyton Jones \\ Glasgow University and Oregon Graduate Institute \and

+Simon Marlow \\ Glasgow University \and

 Alastair Reid \\ Yale University} 
 
 \maketitle
 Alastair Reid \\ Yale University} 
 
 \maketitle

@@ -82,6 +83,13 @@ Using one stack instead of two reduces register pressure, reduces the
 size of update frames, and eliminates
 ``stack-stubbing'' instructions.)
 
 size of update frames, and eliminates
 ``stack-stubbing'' instructions.)
 

+\item The ``return in registers'' return convention has been dropped
+because it was complicated and doesn't work well on register-poor
+architectures.  It has been partly replaced by unboxed
+tuples~\ref{sect:unboxed-tuples} which allow the programmer to
+explicitly state where results should be returned in registers (or on
+the stack) instead of on the heap.
+

 \end{itemize} 
 
 \subsection{Wish list}
 \end{itemize} 
 
 \subsection{Wish list}

@@ -140,7 +148,11 @@ Which garbage collector to use.  At the moment we
 only anticipate one, however.
 \end{itemize}
 
 only anticipate one, however.
 \end{itemize}
 

-\subsection{Terminology}
+\subsection{Glossary}
+
+\ToDo{This terminology is not used consistently within the document.
+If you find soemthing which disagrees with this terminology, fix the
+usage.}

 
 \begin{itemize}
 
 
 \begin{itemize}
 

@@ -150,12 +162,29 @@ or an unsigned int.
 \item A {\em pointer} is (at least) 32 bits and big enough to hold a
 function pointer or a data pointer.  
 
 \item A {\em pointer} is (at least) 32 bits and big enough to hold a
 function pointer or a data pointer.  
 

+\item A {\em boxed} type is one whose elements are heap allocated.
+
+\item An {\em unboxed} type is one whose elements are {\em not} heap allocated.
+
+\item A {\em pointed} type is one that contains $\bot$.  Variables with
+pointed types are the only things which can be lazily evaluated.  In
+the STG machine, this means that they are the only things that can be 
+{\em entered} or {\em updated} and it requires that they be boxed.
+
+\item An {\em unpointed} type is one that does not contains $\bot$.
+Variables with unpointed types are never delayed --- they are always
+evaluated when they are constructed.  In the STG machine, this means
+that they cannot be {\em entered} or {\em updated}.  Unpointed objects
+may be boxed (like @Array#@) or unboxed (like @Int#@).
+

 \item A {\em closure} is a (representation of) a value of a {\em pointed}
 \item A {\em closure} is a (representation of) a value of a {\em pointed}

- type.  It may be in HNF or it may be unevaluated --- in either case, you can
- try to evaluate it again.
+type.  It may be in HNF or it may be unevaluated --- in either case, you can
+try to evaluate it again.

 
 \item A {\em thunk} is a (representation of) a value of a {\em pointed}
 
 \item A {\em thunk} is a (representation of) a value of a {\em pointed}

- type which is {\em not} in HNF.
+type which is {\em not} in HNF.
+
+\item A {\em value} is an object in HNF.  It can be pointed or unpointed.

 
 \end{itemize}
 
 
 \end{itemize}
 

@@ -167,8 +196,10 @@ words and pointers are the same size.
 % More terminology to mention.
 % unboxed, unpointed
 
 % More terminology to mention.
 % unboxed, unpointed
 

-There are a few other system invariants which need to be mentioned ---
-though not necessarily here:
+\subsection{Invariants}
+
+There are a few system invariants which need to be mentioned ---
+though this is probably the wrong place for them.

 
 \begin{itemize}
 
 
 \begin{itemize}
 

@@ -179,6 +210,56 @@ the old generation is no bigger than the current new generation.
 
 \end{itemize}
 
 
 \end{itemize}
 

+\section{Source Language}
+
+\subsection{Unboxed tuples}\label{sect:unboxed-tuples}
+
+Functions can take multiple arguments as easily as they can take one
+argument: there's no cost for adding another argument.  But functions
+can only return one result: the cost of adding a second ``result'' is
+that the function must construct a tuple of ``results'' on the heap.
+The assymetry is rather galling and can make certain programming
+styles quite expensive.  For example, consider a simple state transformer
+monad:
+@
+> type S a = State -> (a,State)
+> bindS m k s0 = case m s0 of { (a,s1) -> k a s1 }
+> returnS a s  = (a,s)
+> getS s       = (s,s)
+> setS s _     = ((),s)
+@
+Here, every use of @returnS@, @getS@ or @setS@ constructs a new tuple
+in the heap which is instantly taken apart (and becomes garbage) by
+the case analysis in @bind@.  Even a short state-transformer program
+will construct a lot of these temporary tuples.
+
+Unboxed tuples provide a way for the programmer to indicate that they
+do not expect a tuple to be shared and that they do not expect it to
+be allocated in the heap.  Syntactically, unboxed tuples are just like
+single constructor datatypes except for the annotation @unboxed@.
+@
+> data unboxed AAndState# a = AnS a State
+> type S a = State -> AAndState# a
+> bindS m k s0 = case m s0 of { AnS a s1 -> k a s1 }
+> returnS a s  = AnS a s
+> getS s       = AnS s s
+> setS s _     = AnS () s
+@
+Semantically, unboxed tuples are just unlifted tuples and are subject
+to the same restrictions as other unpointed types.
+
+Operationally, unboxed tuples are never built on the heap.  When
+unboxed tuples are returned, they are returned in multiple registers
+or multiple stack slots.  At first sight, this seems a little strange
+but it's no different from passing double precision floats in two
+registers.
+
+Note that unboxed tuples can only have one constructor and that
+thunks never have unboxed types --- so we'll never try to update an
+unboxed constructor.  The restriction to a single constructor is
+largely to avoid garbage collection complications.
+
+

 %-----------------------------------------------------------------------------
 \part{Evaluation Model}
 \section{Compiled Execution}
 %-----------------------------------------------------------------------------
 \part{Evaluation Model}
 \section{Compiled Execution}

@@ -309,7 +390,7 @@ and either builds a PAP or pops the arguments off the stack into
 \Arg{2} \ldots \Arg{m+1} and jumps to the fast entry point.
 
 
 \Arg{2} \ldots \Arg{m+1} and jumps to the fast entry point.
 
 

-\item {\em Unknown function closure or thunk.}
+\item {\em Unknown function closure, thunk or constructor.}

 
 Sometimes, the function being called is not statically identifiable.
 Consider, for example, the @compose@ function:
 
 Sometimes, the function being called is not statically identifiable.
 Consider, for example, the @compose@ function:

@@ -387,35 +468,18 @@ stack contains a valid activation record
 (section~\ref{sect:activation-records}) --- should a garbage collection
 be required.
 
 (section~\ref{sect:activation-records}) --- should a garbage collection
 be required.
 

-\item If @x@ has a pointed type (e.g.~a data constructor or a function),
+\item If @x@ has a boxed type (e.g.~a data constructor or a function),

 a pointer to @x@ is returned in \Arg{1}.
 
 \ToDo{Warn that components of E should be extracted as soon as
 possible to avoid a space leak.}
 
 a pointer to @x@ is returned in \Arg{1}.
 
 \ToDo{Warn that components of E should be extracted as soon as
 possible to avoid a space leak.}
 

-\item If @x@ is an unpointed type (e.g.~@Int#@ or @Float#@), @x@ is
+\item If @x@ is an unboxed type (e.g.~@Int#@ or @Float#@), @x@ is

 returned in \Arg{1}
 
 returned in \Arg{1}
 

-\item If @x@ is an unpointed tuple constructor, the components of @x@
+\item If @x@ is an unboxed tuple constructor, the components of @x@

 are returned in \Arg{1} \ldots \Arg{n} but no object is constructed in
 are returned in \Arg{1} \ldots \Arg{n} but no object is constructed in

-the heap.  Unboxed tuple constructors are useful for functions which
-want to return multiple values such as those used in an (explicitly
-encoded) state monad:
-
-\ToDo{Move stuff about unboxed tuples to a separate section}
-
-@
-data unpointed AAndState a = AnS a State
-type S a = State -> AAndState a
-
-bindS m k s0 = case m s0 of { AnS s1 a -> k s1 a }
-returnS a s  = AnS a s
-@
-
-Note that unboxed datatypes can only have one constructor and that
-thunks never have unboxed types --- so we'll never try to update an
-unboxed constructor.  Unboxed tuples are \emph{never} built on the
-heap.
+the heap.  

 
 When passing an unboxed tuple to a function, the components are
 flattened out and passed in \Arg{1} \ldots \Arg{n} as usual.
 
 When passing an unboxed tuple to a function, the components are
 flattened out and passed in \Arg{1} \ldots \Arg{n} as usual.

@@ -497,7 +561,7 @@ that case there is no need to return a tag in \Arg{2}.
 \subsection{Updates}
 \label{sect:data-updates}
 
 \subsection{Updates}
 \label{sect:data-updates}
 

-The entry code for an updatable thunk (which must also be of arity 0):
+The entry code for an updatable thunk (which must be of arity 0):

 
 \begin{itemize}
 \item copies the free variables out of the thunk into registers or
 
 \begin{itemize}
 \item copies the free variables out of the thunk into registers or

@@ -589,8 +653,10 @@ of the scrutinee, and (c) returning by an indirect jump through the
 return address on the stack.
 
 If we knew that the scrutinee was already evaluated we could generate
 return address on the stack.
 
 If we knew that the scrutinee was already evaluated we could generate

-(better) code which simply jumps to the appropriate branch of the @case@
-with a pointer to the scrutinee in \Arg{1}.
+(better) code which simply jumps to the appropriate branch of the
+@case@ with a pointer to the scrutinee in \Arg{1}.  (For direct
+returns to multiconstructor datatypes, we might also load the tag into
+\Arg{2}).

 
 An obvious idea, therefore, is to test dynamically whether the heap
 closure is a value (using the tag in the info table).  If not, we
 
 An obvious idea, therefore, is to test dynamically whether the heap
 closure is a value (using the tag in the info table).  If not, we

@@ -660,9 +726,16 @@ entering the garbage collector.
 
 \note{I reckon these deserve a subsection of their own}
 
 
 \note{I reckon these deserve a subsection of their own}
 

-Don't move heap pointer before success occurs.
+The storage manager detects that it needs to garbage collect the old
+generation when the evaluator requests a garbage collection without
+having moved the heap pointer since the last garbage collection.  It
+is therefore important that the GC routines {\em not} move the heap
+pointer unless the heap check fails.  This is different from what
+happens in the current STG implementation.
+

 Talk about how stack check looks ahead into the branches of case expressions.
 
 Talk about how stack check looks ahead into the branches of case expressions.
 

+

 \subsection{Handling interrupts/signals}
 
 @
 \subsection{Handling interrupts/signals}
 
 @

@@ -716,56 +789,90 @@ closure; a BCO can be entered just like any other closure.  Hugs
 performs lambda-lifting during compilation to byte-code, and each
 top-level combinator becomes a BCO in the heap.
 
 performs lambda-lifting during compilation to byte-code, and each
 top-level combinator becomes a BCO in the heap.
 

-\subsubsection{Thunks}
+\subsubsection{Thunks and partial applications}

 
 A thunk consists of a code pointer, and values for the free variables
 of that code.  Since Hugs byte-code is lambda-lifted, free variables
 become arguments and are expected to be on the stack by the called
 function.
 
 
 A thunk consists of a code pointer, and values for the free variables
 of that code.  Since Hugs byte-code is lambda-lifted, free variables
 become arguments and are expected to be on the stack by the called
 function.
 

-Hugs represents thunks with an AP object.  The AP object contains one
-or more pointers to other heap objects.  When it is entered, it pushes
-an update frame followed by its payload on the stack, and enters the
-first word (which will be a pointer to a BCO).  The layout of AP
-objects is described in more detail in Section \ref{sect:AP}.
+Hugs represents thunks with an @HUGS_AP@ object.  The @HUGS_AP@ object
+contains one or more pointers to other heap objects.  When it is
+entered, it pushes an update frame followed by its payload on the
+stack, and enters the first word (which will be a pointer to a BCO).
+The layout of @HUGS_AP@ objects is described in more detail in Section
+\ref{sect:HUGS-AP}.

 
 

-\subsubsection{Partial Applications}
+Partial applications are represented by @HUGS_PAP@ objects, which are
+identical to @HUGS_AP@s except that they are non-updatable.

 
 

-Partial applications are represented by PAP objects.  A PAP object is
-exactly the same as an AP object, except that it is non-updatable.
-The layout of PAP objects is described in Section \ref{sect:PAP}.
+\ToDo{Hugs Constructors}.

 
 \subsection{Calling conventions}
 \label{sect:hugs-calling-conventions}
 
 The calling convention for any byte-code function is straightforward:
 
 \subsection{Calling conventions}
 \label{sect:hugs-calling-conventions}
 
 The calling convention for any byte-code function is straightforward:

-

 \begin{itemize}
 \item Push any arguments on the stack.
 \item Push a pointer to the BCO.
 \item Begin interpreting the byte code.
 \end{itemize}
 
 \begin{itemize}
 \item Push any arguments on the stack.
 \item Push a pointer to the BCO.
 \item Begin interpreting the byte code.
 \end{itemize}
 

-The @ENTER@ byte-code instruction decides how to enter its argument.
-The object being entered must be either
+But it isn't enough for the bytecode interpreter to handle just
+byte-code functions specially.  At a minimum, it must also be able to
+enter constructors too because of the way that GHC returns to
+Hugs-compiled return addresses (Section~\ref{sect:ghc-to-hugs-return}).
+
+In principle, all other closure types could be handled by switching to
+the compiled world (as described in
+Section~\ref{sect:hugs-to-ghc-closure}) and entering the closure
+there.  This would work but it would obviously be very inefficient if
+we entered a @HUGS_AP@ by switching worlds, entering the @HUGS_AP@,
+pushing the arguments and function onto the stack, and entering the
+function which, likely as not, will be a byte-code object which we
+will enter by \emph{returning} to the byte-code interpreter.  To avoid
+such gratuitious world switching, we choose to recognise certain
+closure types as being ``standard'' --- and duplicate the entry code
+for the ``standard closures'' in the bytecode interpreter.
+
+A closure is said to be ``standard'' if its entry code is entirely
+determined by its info table.  \emph{Standard Closures} have the
+desirable property that the byte-code interpreter can enter
+the closure by simply ``interpreting'' the info table instead of
+switching to the compiled world.  The standard closures include:

 
 

-\begin{itemize}
-\item A BCO,
-\item An AP,
-\item A PAP,
-\item A constructor,
-\item A GHC-built closure, or
-\item An indirection.
-\end{itemize}
+\begin{description}
+\item[@HUGS_AP@] 
+To enter a @HUGS_AP@ we push an update frame, push the values from the
+@HUGS_AP@ on the stack, and enter its associated object.
+
+\item[@HUGS_PAP@]
+To enter a @HUGS_PAP@, we push its values on the stack and enter the
+first one.
+
+\item[@PAP@]
+Same as @HUGS_PAP@.
+
+\item[Constructor]
+To enter a constructor, we simply return (see Section
+\ref{sect:hugs-return-convention}).
+
+\item[Indirection]
+To enter an indirection, we simply enter the object it points to
+after possibly adjusting the current cost centre.
+
+\item[Selector] 
+To enter a selector, we test whether the selectee is a value.  If so,
+we simply select the appropriate component; if not, it's simplest to
+treat it as a GHC-built closure --- though we could interpret it if we
+wanted.
+
+\end{description}
+
+The most obvious omissions from the above list are @BCO@s (which we
+dealt with above) and GHC-built closures (which are covered in Section
+\ref{sect:hugs-to-ghc-closure}).

 
 

-If @ENTER@ is applied to a BCO, we just begin interpreting the
-byte-code contained therein.  If the object is an AP, we push an
-update frame, push the values from the AP on the stack, and enter its
-associated object.  If the object is a PAP, we push its values on the
-stack and enter the first one.  If the object is a constructor, we
-simply return (see Section \ref{sect:hugs-return-convention}).  The
-fourth case is convered in Section \ref{sect:hugs-to-ghc-closure}.  If
-the object is an indirection, we simply enter the object it points to.

 
 \subsection{Return convention}
 \label{sect:hugs-return-convention}
 
 \subsection{Return convention}
 \label{sect:hugs-return-convention}

@@ -773,13 +880,13 @@ the object is an indirection, we simply enter the object it points to.
 When Hugs pushes a return address, it pushes both a pointer to the BCO
 to return to, and a pointer to a static code fragment @HUGS_RET@ (this
 will be described in Section \ref{sect:ghc-to-hugs-return}).  The
 When Hugs pushes a return address, it pushes both a pointer to the BCO
 to return to, and a pointer to a static code fragment @HUGS_RET@ (this
 will be described in Section \ref{sect:ghc-to-hugs-return}).  The

-stack layout is shown in Figure \ref{fig:hugs-return-fig}.
+stack layout is shown in Figure \ref{fig:hugs-return-stack}.

 
 \begin{figure}
 \begin{center}
 \input{hugs_ret.pstex_t}
 \end{center}
 
 \begin{figure}
 \begin{center}
 \input{hugs_ret.pstex_t}
 \end{center}

-\caption{Stack layout for a hugs return address}
+\caption{Stack layout for a Hugs return address}

 \label{fig:hugs-return-stack}
 \end{figure}
 
 \label{fig:hugs-return-stack}
 \end{figure}
 

@@ -787,7 +894,7 @@ stack layout is shown in Figure \ref{fig:hugs-return-fig}.
 \begin{center}
 \input{hugs_ret2.pstex_t}
 \end{center}
 \begin{center}
 \input{hugs_ret2.pstex_t}
 \end{center}

-\caption{Stack layout on enterings a hugs return address}
+\caption{Stack layout on enterings a Hugs return address}

 \label{fig:hugs-return2}
 \end{figure}
 
 \label{fig:hugs-return2}
 \end{figure}
 

@@ -799,7 +906,7 @@ the second word on the stack):
 
 \item If the return address is @HUGS_RET@, rearrange the stack so that
 it has the returned object followed by the pointer to the BCO at the
 
 \item If the return address is @HUGS_RET@, rearrange the stack so that
 it has the returned object followed by the pointer to the BCO at the

-top, then enter the BCO (Figure \ref{fig:hugsreturn2}).
+top, then enter the BCO (Figure \ref{fig:hugs-return2}).

 
 \item If the top of the stack is not @HUGS_RET@, we need to do a world
 switch as described in Section \ref{sect:hugs-to-ghc-return}.
 
 \item If the top of the stack is not @HUGS_RET@, we need to do a world
 switch as described in Section \ref{sect:hugs-to-ghc-return}.

@@ -851,8 +958,8 @@ while (threads_exist) {
   pick a runnable thread;
   do {
     switch (thread->whatNext) {
   pick a runnable thread;
   do {
     switch (thread->whatNext) {

-      case (RunGHC  pc): status=runGHC(pc);  break;
-      case (RunHugs bc): status=runHugs(bc); break;
+      case (EnterGHC  pc): status=runGHC(pc);  break;
+      case (EnterHugs bc): status=runHugs(bc); break;

     }
     switch (status) {  // handle local problems
       case (StackOverflow): enlargeStack; break;
     }
     switch (status) {  // handle local problems
       case (StackOverflow): enlargeStack; break;

@@ -915,13 +1022,14 @@ switch happens in each situation.
 \subsection{A GHC thread enters a Hugs-built closure}
 \label{sect:ghc-to-hugs-closure}
 
 \subsection{A GHC thread enters a Hugs-built closure}
 \label{sect:ghc-to-hugs-closure}
 

-There are two possibilities: GHC has entered the BCO directly (for a
-top-level function closure), or it has entered an AP.
+There are three possibilities: GHC has entered the BCO directly (for a
+top-level function closure), it has entered a @HUGS_AP@, or it has
+entered a @HUGS_PAP@.

 
 

-The code for both objects is the same:
+The code for all three objects is the same:

 
 \begin{itemize}
 
 \begin{itemize}

-\item Push the address of the BCO on the stack.
+\item Push the address of the object entered on the stack.

 \item Save the current state of the thread in its TSO.
 \item Return to the scheduler, setting @whatNext@ to @EnterHugs@.
 \end{itemize}
 \item Save the current state of the thread in its TSO.
 \item Return to the scheduler, setting @whatNext@ to @EnterHugs@.
 \end{itemize}

@@ -952,8 +1060,10 @@ Hugs can recognise a GHC-built closure as not being one of the
 following types of object:
 
 \begin{itemize}
 following types of object:
 
 \begin{itemize}

-\item A BCO.
-\item An AP.
+\item A @BCO@,
+\item A @HUGS_AP@,
+\item A @HUGS_PAP@,
+\item An indirection, or

 \item A constructor.
 \end{itemize}
 
 \item A constructor.
 \end{itemize}
 

@@ -998,11 +1108,16 @@ return itself to the return address using the GHC return convention.
 \label{fig:closure}
 \end{figure}
 
 \label{fig:closure}
 \end{figure}
 

-Every {\em heap object}, or {\em closure} is a contiguous block
+Every {\em heap object} is a contiguous block

 of memory, consisting of a fixed-format {\em header} followed
 by zero or more {\em data words}.
 of memory, consisting of a fixed-format {\em header} followed
 by zero or more {\em data words}.

-The header consists of
-the following fields:
+
+\ToDo{I absolutely do not believe that every heap object has a header
+like this - ADR.  I believe that they all have an info pointer but I
+see no readon why stack objects and unpointed heap objects would have
+an entry count since this will always be zero.}
+
+The header consists of the following fields:

 \begin{itemize}
 \item A one-word {\em info pointer}, which points to
 the object's static {\em info table}.
 \begin{itemize}
 \item A one-word {\em info pointer}, which points to
 the object's static {\em info table}.

@@ -1016,19 +1131,18 @@ though GUM keeps a separate hash table).
 \item Statistics (e.g. a word to track how many times a thunk is entered.).
 
 We add a Ticky word to the fixed-header part of closures.  This is
 \item Statistics (e.g. a word to track how many times a thunk is entered.).
 
 We add a Ticky word to the fixed-header part of closures.  This is

-used to record indicate if a closure has been updated but not yet
-entered. It is set when the closure is updated and cleared when
-subsequently entered.
+used to indicate if a closure has been updated but not yet entered. It
+is set when the closure is updated and cleared when subsequently
+entered.

 
 NB: It is {\em not} an ``entry count'', it is an
 ``entries-after-update count.''  The commoning up of @CONST@,
 @CHARLIKE@ and @INTLIKE@ closures is turned off(?) if this is
 required. This has only been done for 2s collection.
 
 
 NB: It is {\em not} an ``entry count'', it is an
 ``entries-after-update count.''  The commoning up of @CONST@,
 @CHARLIKE@ and @INTLIKE@ closures is turned off(?) if this is
 required. This has only been done for 2s collection.
 

-
-

 \end{itemize}
 \end{itemize}
 \end{itemize}
 \end{itemize}

+

 Most of the RTS is completely insensitive to the number of admin words.
 The total size of the fixed header is @FIXED_HS@.
 
 Most of the RTS is completely insensitive to the number of admin words.
 The total size of the fixed header is @FIXED_HS@.
 

@@ -1082,12 +1196,11 @@ successive decreasing memory addresses.
    \hline Parallelism Info 
 \\ \hline Profile Info 
 \\ \hline Debug Info 
    \hline Parallelism Info 
 \\ \hline Profile Info 
 \\ \hline Debug Info 

-\\ \hline Tag/bytecode pointer
-\\ \hline Static reference table 
+\\ \hline Tag / Static reference table

 \\ \hline Storage manager layout info
 \\ \hline Closure type 
 \\ \hline Storage manager layout info
 \\ \hline Closure type 

-\\ \hline entry code \ldots
-\\ \hline
+\\ \hline entry code
+\\       \vdots

 \end{tabular}
 \end{center}
 An info table has the following contents (working backwards in memory
 \end{tabular}
 \end{center}
 An info table has the following contents (working backwards in memory

@@ -1110,24 +1223,12 @@ are represented as high-order bits so they can be tested quickly.
 precise layout, for the benefit of the garbage collector and the code
 that stuffs graph into packets for transmission over the network.
 
 precise layout, for the benefit of the garbage collector and the code
 that stuffs graph into packets for transmission over the network.
 

-\item A one-pointer {\em Static Reference Table (SRT) pointer}, @INFO_SRT@, points to
-a table which enables the garbage collector to identify all accessible
-code and CAFs.  They are fully described in Section~\ref{sect:srt}.
-
-\item A one-pointer {\em tag/bytecode-pointer} field, @INFO_TAG@ or @INFO_BC@.  
-For data constructors this field contains the constructor tag, in the
-range $0..n-1$ where $n$ is the number of constructors.
-
-For other objects that can be entered this field points to the byte
-codes for the object.  For the constructor case you can think of the
-tag as the name of a a suitable bytecode sequence but it can also be used to
-implement semi-tagging (section~\ref{sect:semi-tagging}).
-
-One awkward question (which may not belong here) is ``how does the
-bytecode interpreter know whether to do a vectored return?''  The
-answer is it examines the @INFO_TYPE@ field of the return address:
-@RET_VEC_@$sz$ requires a vectored return and @RET_@$sz$ requires a
-direct return.
+\item A one-word {\em Tag/Static Reference Table} field, @INFO_SRT@.
+For data constructors, this field contains the constructor tag, in the
+range $0..n-1$ where $n$ is the number of constructors.  For all other
+objects it contains a pointer to a table which enables the garbage
+collector to identify all accessible code and CAFs.  They are fully
+described in Section~\ref{sect:srt}.

 
 \item {\em Profiling info\/}
 
 
 \item {\em Profiling info\/}
 

@@ -1228,8 +1329,8 @@ Something internal to the runtime system.
 \end{itemize}
 
 
 \end{itemize}
 
 

-
-\section{Kinds of Heap Object}
+%-----------------------------------------------------------------------------
+\subsection{Kinds of Heap Object}

 \label{sect:closures}
 
 Heap objects can be classified in several ways, but one useful one is
 \label{sect:closures}
 
 Heap objects can be classified in several ways, but one useful one is

@@ -1252,9 +1353,9 @@ Section~\ref{sect:stacks}.
 A second useful classification is this:
 \begin{itemize}
 \item 
 A second useful classification is this:
 \begin{itemize}
 \item 

-{\em Executive closures}, such as thunks and data constructors,
+{\em Executive objects}, such as thunks and data constructors,

 participate directly in a program's execution.  They can be subdivided into
 participate directly in a program's execution.  They can be subdivided into

-two kinds of objects according to their type:
+three kinds of objects according to their type:

 \begin{itemize}
 \item 
 {\em Pointed objects}, represent values of a {\em pointed} type
 \begin{itemize}
 \item 
 {\em Pointed objects}, represent values of a {\em pointed} type

@@ -1269,7 +1370,7 @@ once we support speculative evaluation.}
 
 \end{itemize}
 
 
 \end{itemize}
 

-\item {\em Administrative closures}, such as stack objects and thread
+\item {\em Administrative objects}, such as stack objects and thread

 state objects, do not represent values in the original program.
 \end{itemize}
 
 state objects, do not represent values in the original program.
 \end{itemize}
 

@@ -1293,42 +1394,48 @@ closure kind          & HNF & UPD & NS & STA & THU & MUT & UPT & BH & IND & Sect
 {\em Pointed} \\ 
 \hline 
 
 {\em Pointed} \\ 
 \hline 
 

-@CONSTR@              & 1   &     & 1  &     &     &     &     &    &     & \ref{sect:CONSTR}    \\
-@CONSTR_STATIC@       & 1   &     & 1  & 1   &     &     &     &    &     & \ref{sect:CONSTR}    \\
-@CONSTR_STATIC_NOCAF@ & 1   &     & 1  & 1   &     &     &     &    &     & \ref{sect:CONSTR}    \\
-                                                                                                
-@FUN@                 & 1   &     & ?  &     &     &     &     &    &     & \ref{sect:FUN}       \\
-@FUN_STATIC@          & 1   &     & ?  & 1   &     &     &     &    &     & \ref{sect:FUN}       \\
-                                                                                                
-@THUNK@               & 1   & 1   &    &     & 1   &     &     &    &     & \ref{sect:THUNK}     \\
-@THUNK_STATIC@        & 1   & 1   &    & 1   & 1   &     &     &    &     & \ref{sect:THUNK}     \\
-@THUNK_SELECTOR@      & 1   & 1   & 1  &     & 1   &     &     &    &     & \ref{sect:THUNK_SEL}     \\
-                                                                                                
-@PAP@                 & 1   &     & ?  &     &     &     &     &    &     & \ref{sect:PAP}       \\
-                                                                                                
-@IND@                 &     &     & 1  &     & ?   &     &     &    & 1   & \ref{sect:IND}       \\
-@IND_OLDGEN@          & 1   &     & 1  &     & ?   &     &     &    & 1   & \ref{sect:IND}       \\
-@IND_PERM@            &     &     & 1  &     & ?   &     &     &    & 1   & \ref{sect:IND}       \\
-@IND_OLDGEN_PERM@     & 1   &     & 1  &     & ?   &     &     &    & 1   & \ref{sect:IND}       \\
-@IND_STATIC@          & ?   &     & 1  & 1   & ?   &     &     &    & 1   & \ref{sect:IND}       \\
-
-\hline
-{\em Unpointed} \\ 
-\hline
-
-
-@ARR_WORDS@           & 1   &     & 1  &     &     & 1   & 1   &    &     & \ref{sect:ARR_WORDS1},\ref{sect:ARR_WORDS2} \\
-@ARR_PTRS@            & 1   &     & 1  &     &     & 1   & 1   &    &     & \ref{sect:ARR_PTRS}  \\
-@MUTVAR@              & 1   &     & 1  &     &     & 1   & 1   &    &     & \ref{sect:MUTVAR}    \\
-@MUTARR_PTRS@         & 1   &     & 1  &     &     & 1   & 1   &    &     & \ref{sect:MUTARR_PTRS} \\
-@MUTARR_PTRS_FROZEN@  & 1   &     & 1  &     &     & 1   & 1   &    &     & \ref{sect:MUTARR_PTRS_FROZEN} \\
-
-@FOREIGN@             & 1   &     & 1  &     &     &     & 1   &    &     & \ref{sect:FOREIGN}   \\
-
-@BH@                  & ?   & 0/1 & 1  &     & ?   & ?   &     & 1  & ?   & \ref{sect:BH}        \\
-@MVAR@                       &     &     &    &     &     &     &     &    &     & \ref{sect:MVAR}      \\
-@IVAR@                       &     &     &    &     &     &     &     &    &     & \ref{sect:IVAR}      \\
-@FETCHME@             &     &     &    &     &     &     &     &    &     & \ref{sect:FETCHME}   \\
+@CONSTR@              & 1 &   & 1 &   &   &   &   &   &   & \ref{sect:CONSTR}    \\
+@CONSTR_STATIC@       & 1 &   & 1 & 1 &   &   &   &   &   & \ref{sect:CONSTR}    \\
+@CONSTR_STATIC_NOCAF@ & 1 &   & 1 & 1 &   &   &   &   &   & \ref{sect:CONSTR}    \\
+
+@FUN@                 & 1 &   & ? &   &   &   &   &   &   & \ref{sect:FUN}       \\
+@FUN_STATIC@          & 1 &   & ? & 1 &   &   &   &   &   & \ref{sect:FUN}       \\
+
+@THUNK@               &   & 1 &   &   & 1 &   &   &   &   & \ref{sect:THUNK}     \\
+@THUNK_STATIC@        &   & 1 &   & 1 & 1 &   &   &   &   & \ref{sect:THUNK}     \\
+@THUNK_SELECTOR@      &   & 1 & 1 &   & 1 &   &   &   &   & \ref{sect:THUNK_SEL} \\
+
+@BCO@                & 1 &   & 1 &   &   &   &   &   &   & \ref{sect:BCO}       \\
+@BCO_CAF@            &   & 1 &   &   & 1 &   &   &   &   & \ref{sect:BCO}       \\
+
+@HUGS_AP@            &   & 1 &   &   & 1 &   &   &   &   & \ref{sect:HUGS-AP}   \\
+@HUGS_PAP@           & 1 &   & 1 &   &   &   &   &   &   & \ref{sect:HUGS-AP}   \\
+
+@PAP@                 & 1 &   & 1 &   &   &   &   &   &   & \ref{sect:PAP}       \\
+
+@IND@                 & ? &   & ? &   & ? &   &   &   & 1 & \ref{sect:IND}       \\
+@IND_OLDGEN@          & ? &   & ? &   & ? &   &   &   & 1 & \ref{sect:IND}       \\
+@IND_PERM@            & ? &   & ? &   & ? &   &   &   & 1 & \ref{sect:IND}       \\
+@IND_OLDGEN_PERM@     & ? &   & ? &   & ? &   &   &   & 1 & \ref{sect:IND}       \\
+@IND_STATIC@          & ? &   & ? & 1 & ? &   &   &   & 1 & \ref{sect:IND}       \\
+                                                        
+\hline                                                  
+{\em Unpointed} \\                                      
+\hline                                                  
+                                                        
+                                                        
+@ARR_WORDS@           & 1 &   & 1 &   &   &   & 1 &   &   & \ref{sect:ARR_WORDS1},\ref{sect:ARR_WORDS2} \\
+@ARR_PTRS@            & 1 &   & 1 &   &   &   & 1 &   &   & \ref{sect:ARR_PTRS}  \\
+@MUTVAR@              & 1 &   & 1 &   &   & 1 & 1 &   &   & \ref{sect:MUTVAR}    \\
+@MUTARR_PTRS@         & 1 &   & 1 &   &   & 1 & 1 &   &   & \ref{sect:MUTARR_PTRS} \\
+@MUTARR_PTRS_FROZEN@  & 1 &   & 1 &   &   & 1 & 1 &   &   & \ref{sect:MUTARR_PTRS_FROZEN} \\
+                                                        
+@FOREIGN@             & 1 &   & 1 &   &   &   & 1 &   &   & \ref{sect:FOREIGN}   \\
+                                                        
+@BH@                  &   & 1 & 1 &   & ? & ? &   & 1 & ? & \ref{sect:BH}        \\
+@MVAR@                       & 1 &   & 1 &   &   &   &   &   &   & \ref{sect:MVAR}      \\
+@IVAR@                       & 1 &   & 1 &   &   &   &   &   &   & \ref{sect:IVAR}      \\
+@FETCHME@             & 1 &   & 1 &   &   &   &   &   &   & \ref{sect:FETCHME}   \\

 \hline
 \end{tabular}
 
 \hline
 \end{tabular}
 

@@ -1467,8 +1574,14 @@ under evaluation (BH), or by now an HNF.  Thus, indirections get NoSpark flag.
 \label{sect:BCO}
 
 A Byte-Code Object (BCO) is a container for a a chunk of byte-code,
 \label{sect:BCO}
 
 A Byte-Code Object (BCO) is a container for a a chunk of byte-code,

-which can be executed by Hugs.  For a top-level function, the BCO also
-serves as the closure for the function.
+which can be executed by Hugs.  The byte-code represents a
+supercombinator in the program: when hugs compiles a module, it
+performs lambda lifting and each resulting supercombinator becomes a
+byte-code object in the heap.
+
+There are two kinds of BCO: a standard @BCO@ which has an arity of one
+or more, and a @BCO_CAF@ which takes no arguments and can be updated.
+When a @BCO_CAF@ is updated, the code is thrown away!

 
 The semantics of BCOs are described in Section
 \ref{sect:hugs-heap-objects}.  A BCO has the following structure:
 
 The semantics of BCOs are described in Section
 \ref{sect:hugs-heap-objects}.  A BCO has the following structure:

@@ -1476,7 +1589,7 @@ The semantics of BCOs are described in Section
 \begin{center}
 \begin{tabular}{|l|l|l|l|l|l|}
 \hline 
 \begin{center}
 \begin{tabular}{|l|l|l|l|l|l|}
 \hline 

-\emph{BCO} & \emph{Layout} & \emph{Offset} & \emph{Size} &
+\emph{Fixed Header} & \emph{Layout} & \emph{Offset} & \emph{Size} &

 \emph{Literals} & \emph{Byte code} \\
 \hline
 \end{tabular}
 \emph{Literals} & \emph{Byte code} \\
 \hline
 \end{tabular}

@@ -1484,7 +1597,7 @@ The semantics of BCOs are described in Section
 
 \noindent where:
 \begin{itemize}
 
 \noindent where:
 \begin{itemize}

-\item \emph{BCO} is a pointer to a static code fragment/info table that
+\item The entry code is a static code fragment/info table that

 returns to the scheduler to invoke Hugs (Section
 \ref{sect:ghc-to-hugs-closure}).
 \item \emph{Layout} contains the number of pointer literals in the
 returns to the scheduler to invoke Hugs (Section
 \ref{sect:ghc-to-hugs-closure}).
 \item \emph{Layout} contains the number of pointer literals in the

@@ -1498,16 +1611,18 @@ the byte-codes (including jump addresses), pointers first.
 code.
 \end{itemize}
 
 code.
 \end{itemize}
 

-\subsubsection{AP objects}
-\label{sect:AP}
+\subsubsection{@HUGS_AP@ objects}
+\label{sect:HUGS-AP}

 
 

-Hugs uses a standard object called an AP for thunks and partial
-applications.  The layout of an AP is
+There are two kinds of @HUGS_AP@ objects: a standard @HUGS_AP@, used
+to represent thunks buit by Hugs, and a @HUGS_PAP@, used for partial
+applications.  The only difference between the two is that a
+@HUGS_PAP@ is non-updatable.

 
 \begin{center}
 \begin{tabular}{|l|l|l|l|}
 \hline
 
 \begin{center}
 \begin{tabular}{|l|l|l|l|}
 \hline

-\emph{AP} & \emph{BCO} & \emph{Layout} & \emph{Free Variables} \\
+\emph{Fixed Header} & \emph{BCO} & \emph{Layout} & \emph{Free Variables} \\

 \hline
 \end{tabular}
 \end{center}
 \hline
 \end{tabular}
 \end{center}

@@ -1515,14 +1630,19 @@ applications.  The layout of an AP is
 \noindent where:
 
 \begin{itemize}
 \noindent where:
 
 \begin{itemize}

-\item \emph{AP} is a pointer to a statically-compiled code
-fragment/info table that returns to the scheduler to invoke Hugs
-(Sections \ref{sect:ghc-to-hugs-closure}, \ref{sect:ghc-to-hugs-return}).
+
+\item The entry code is a statically-compiled code fragment/info table
+that returns to the scheduler to invoke Hugs (Sections
+\ref{sect:ghc-to-hugs-closure}, \ref{sect:ghc-to-hugs-return}).
+

 \item \emph{BCO} is a pointer to the BCO for the thunk.
 \item \emph{BCO} is a pointer to the BCO for the thunk.

+

 \item \emph{Layout} contains the number of pointers and the size of
 the \emph{Free Variables} field.
 \item \emph{Layout} contains the number of pointers and the size of
 the \emph{Free Variables} field.

+

 \item \emph{Free Variables} contains the free variables of the
 thunk/partial application/return address, pointers first.
 \item \emph{Free Variables} contains the free variables of the
 thunk/partial application/return address, pointers first.

+

 \end{itemize}
 
 \subsection{Pointed Objects}
 \end{itemize}
 
 \subsection{Pointed Objects}

@@ -1569,7 +1689,7 @@ layout than dynamic ones:
 {\em Fixed header}  & {\em Static object link} \\ \hline
 \end{tabular}
 \end{center}
 {\em Fixed header}  & {\em Static object link} \\ \hline
 \end{tabular}
 \end{center}

-Static function closurs have no free variables.  (However they may refer to other 
+Static function closures have no free variables.  (However they may refer to other 

 static closures; these references are recorded in the function closure's SRT.)
 They have one field that is not present in dynamic closures, the {\em static object
 link} field.  This is used by the garbage collector in the same way that to-space
 static closures; these references are recorded in the function closure's SRT.)
 They have one field that is not present in dynamic closures, the {\em static object
 link} field.  This is used by the garbage collector in the same way that to-space

@@ -1603,9 +1723,8 @@ closures.  That is
 \end{tabular}
 \end{center}
 
 \end{tabular}
 \end{center}
 

-The SRT pointer in a data constructor's info table is never used --- the
-code for a constructor does not make any static references.
-\note{Use it for something else??  E.g. tag?}
+The SRT pointer in a data constructor's info table is used for the
+constructor tag, since a constructor never has any static references.

 
 There are several different sorts of constructor:
 \begin{itemize}
 
 There are several different sorts of constructor:
 \begin{itemize}

@@ -1746,7 +1865,7 @@ check failure.  A PAP has the following shape:
 {\em Fixed header}  & {\em No of arg words} & {\em Function closure} & {\em Arg stack} \\ \hline
 \end{tabular}
 \end{center}
 {\em Fixed header}  & {\em No of arg words} & {\em Function closure} & {\em Arg stack} \\ \hline
 \end{tabular}
 \end{center}

-The ``arg stack'' is a copy of of the chunk of stack above the update
+The ``arg stack'' is a copy of the chunk of stack above the update

 frame; ``no of arg words'' tells how many words it consists of.  The
 function closure is (a pointer to) the closure for the function whose
 argument-satisfaction check failed.
 frame; ``no of arg words'' tells how many words it consists of.  The
 function closure is (a pointer to) the closure for the function whose
 argument-satisfaction check failed.

@@ -2636,7 +2755,7 @@ a case in point, as <.jones jfp leak.> points out.  Consider a thunk for
 the expression
 @
   let xs = [1..1000] in last xs
 the expression
 @
   let xs = [1..1000] in last xs

-@ 
+@

 where @last@ is a function that returns the last element of its
 argument list.  When the thunk is entered it will call @last@, which
 will consume @xs@ until it finds the last element.  Since the list
 where @last@ is a function that returns the last element of its
 argument list.  When the thunk is entered it will call @last@, which
 will consume @xs@ until it finds the last element.  Since the list

@@ -2825,7 +2944,7 @@ some of these update targets are garbage they will be collected right away.
 
 \fi
 
 
 \fi
 

-\subsection{Space leaks and selectors}
+\subsection{Space leaks and selectors}\label{sect:space-leaks-and-selectors}

 
 \iffalse
 
 
 \iffalse
 

@@ -2886,6 +3005,8 @@ garbage collection.   We have not (yet) implemented this idea.
 A very similar idea, dubbed ``stingy evaluation'', is described 
 by <.stingy.>.
 
 A very similar idea, dubbed ``stingy evaluation'', is described 
 by <.stingy.>.
 

+\ToDo{Simple generalisation: handle all the ``standard closures'' this way.}
+

 <.sparud lazy pattern matching.> describes another solution to the
 lazy-pattern-matching
 problem.  His solution involves adding code to the two thunks for
 <.sparud lazy pattern matching.> describes another solution to the
 lazy-pattern-matching
 problem.  His solution involves adding code to the two thunks for