1 \documentstyle[11pt,literate,a4wide]{article}
7 %\newcommand{\folks}[1]{$\spadesuit$ {\em #1} $\spadesuit$}
8 %\newcommand{\ToDo}[1]{$\spadesuit$ {\bf ToDo:} {\em #1} $\spadesuit$}
10 % to avoid src-location marginpars, comment in/out this defn.
11 %\newcommand{\srcloc}[1]{{\tt #1}}
12 %\newcommand{\srclocnote}[1]{}
13 %\newcommand{\srclocnote}[1]{\marginpar{\small\srcloc{#1}}}
15 \setcounter{secnumdepth}{6}
16 \setcounter{tocdepth}{6}
21 \title{Basic types and the standard Prelude: OBSOLETE}
22 \author{The AQUA team}
23 \date{November 1992 (obsolete February 1994)}
30 % added to keep DPH stuff happy:
32 \def\DPHaskell{DPHaskell}
36 This document describes how we deal with Haskell's standard prelude,
37 notably what the compiler itself ``knows'' about it. There's nothing
38 intellectually difficult here---it's just vast and occasionally
41 First, some introduction, mostly terminology. Second, the actual
42 compiler source code which defines what the compiler knows about the
43 prelude. Finally, something about how we compile the prelude code
44 (with GHC, of course) to produce the executable bits for the prelude.
46 %************************************************************************
48 \section{Introduction and terminology}
50 %************************************************************************
52 The standard prelude is made of many, many pieces. The GHC system
53 must deal with these pieces in different ways. For example, the
54 compiler must obviously do different things for primitive operations
55 (e.g., addition on machine-level @Ints@) and for plain
56 written-in-Haskell functions (e.g., @tail@).
58 In this section, the main thing we do is explain the various ways that
59 we categorise prelude thingies, most notably types.
61 %************************************************************************
63 \subsection{Background information}
65 %************************************************************************
67 %************************************************************************
69 \subsubsection{Background terms: Heap objects}
71 %************************************************************************
73 A {\em heap object} (equivalently {\em closure}) is always a
74 contiguous block of memory, starting with an info pointer. {\em
75 Dynamic} heap objects are allocated by a sequence of instructions in
78 In contrast, {\em static heap objects} are statically allocated at
79 fixed, labelled locations outside the dynamic heap --- but we still
80 call them heap objects! Their GC code does not evacuate them, and
81 they are never scavenged since they never appear in to-space. Note:
82 the ``staticness'' does {\em not} mean they are read-only; they may be
85 (Much) more on this stuff in the STG paper.
87 %************************************************************************
89 \subsection{Categorising the prelude bits}
91 %************************************************************************
93 Here are four different ways in which we might categorise prelude
94 things generally. Note, also, the {\em simplifying assumptions} that
95 we make so that we can have a ``Prelude onion,'' in which each
96 ``layer'' includes the preceding ones.
99 %------------------------------------------------------------------
100 \item[Primitive vs Haskell-able:]
102 Some parts of the prelude cannot be expressed in Haskell ({\em
103 primitive}), whereas most of it can be ({\em Haskell-able}).
105 BIG NOTE: Because of our non-standard support for unboxed numbers and
106 operations thereon, some of the things in @PreludeBuiltin@ in the
107 report {\em are} Haskell-able. For example, the @negate@ operation on
112 = case i of MkInt i# -> case (negateInt# i#) of j# -> MkInt j#
115 Of course, this just moves the goalposts: @negateInt#@ is now the
116 primitive, non-Haskell-able thingy...
118 So: something is ``primitive'' if we cannot define it in our
119 GHC-extended Haskell.
121 For more information, please see \sectionref{prelude-more-on-types}
122 for further discussion about types in the Prelude.
124 %------------------------------------------------------------------
125 \item[From (exported by) PreludeCore or not:]
126 The module @PreludeCore@ exports all the types, classes, and instances
127 in the prelude. These entities are ``immutable;'' they can't be
128 hidden, renamed, or really fiddled in any way.
130 (NB: The entities {\em exported by} @PreludeCore@ may {\em originally}
131 be from another module. For example, the @Complex@ datatype is
132 defined in @PreludeComplex@; nonetheless, it is exported by
133 @PreludeCore@ and falls into the category under discussion here.)
135 {\em Simplifying assumption:} We take everything primitive (see
136 previous classification) to be ``from PreludeCore''.
138 {\em Simplifying assumption:} We take all {\em values} from
139 @PreludeBuiltin@ to be ``from PreludeCore.'' This includes @error@
140 and the various \tr{prim*} functions (which may or may not be
141 ``primitive'' in our system [because of our extensions for unboxery]).
142 It shouldn't be hard to believe that something from @PreludeBuiltin@
143 is (at least) slightly magic and not just another value...
145 {\em Simplifying assumption:} The GHC compiler has ``wired in''
146 information about {\em all} @fromPreludeCore@ things. The fact that
147 they are ``immutable'' means we don't have to worry about ``unwiring''
148 them in the face of renaming, etc., (which would be pretty bizarre,
151 Not-exported-by-PreludeCore things (non-@PreludeBuiltin@ values) can
152 be renamed, hidden, etc.
154 %------------------------------------------------------------------
155 \item[Compiler-must-know vs compiler-chooses-to-know vs compiler-unknown:]
157 There are some prelude things that the compiler has to ``know about.''
158 For example, it must know about the @Bool@ data type, because (for one
159 reason) it needs it to typecheck guards.
161 {\em Simplifying assumption:} By decree, the compiler ``must know''
162 about everything exported from @PreludeCore@ (see previous
163 classification). This is only slight overkill: there are a few types
164 (e.g., @Request@), classes (e.g., @RealFrac@), and instances (e.g.,
165 anything for @RealFrac@)---all @fromPreludeCore@---that the compiler
166 could, strictly speaking, get away with not knowing about. However,
167 it is a {\em pain} to maintain the distinction...
169 On the other hand, the compiler really {\em doesn't} need to know
170 about the non-@fromPreludeCore@ stuff (as defined above). It can read
171 the relevant information out of a \tr{.hi} interface file, just as it
172 would for a user-defined module (and, indeed, that's what it does).
173 An example of something the compiler doesn't need to know about is the
174 @tail@ function, defined in @PreludeList@, exported by @Prelude@.
176 There are some non-@fromPreludeCore@ things that the compiler may {\em
177 choose} to clutch to its bosom: this is so it can do unfolding on the
178 use of a function. For example, we always want to unfold uses of @&&@
179 and @||@, so we wire info about them into the compiler. (We won't
180 need this when we are able to pass unfolding info via interface
183 %------------------------------------------------------------------
184 \item[Per-report vs Glasgow-extension:]
185 Some of our prelude stuff is not strictly as per the Haskell report,
186 notably the support for monadic I/O, and our different notion of what
187 is truly primitive in Haskell (c.f. @PreludeBuiltin@'s ideas).
189 In this document, ``Haskell'' always means ``Glasgow-extended
193 %************************************************************************
195 \subsection[prelude-more-on-types]{More about the Prelude datatypes}
197 %************************************************************************
199 The previous section explained how we categorise the prelude as a
200 whole. In this section, we home in on prelude datatypes.
202 %************************************************************************
204 \subsubsection{Boxed vs unboxed types}
206 %************************************************************************
208 Objects of a particular type are all represented the same way.
209 We recognise two kinds of types:
213 The domain of a boxed type includes bottom. Values of boxed type are
214 always represented by a pointer to a heap object, which may or may not
215 be evaluated. Anyone needing to scrutinise a value of boxed type must
216 evaluate it first by entering it. Value of boxed type can be passed
217 to polymorphic functions.
219 \item[Unboxed types.]
220 The domain of an unboxed type does not include bottom, so values of
221 unboxed type do not need a representation which accommodates the
222 possibility that it is not yet evaluated.
224 Unboxed values are represented by one or more words. At present, if
225 it is represented by more than one word then none of the words are
226 pointers, but we plan to lift this restriction eventually.
227 (At present, the only multi-word values are @Double#@s.)
229 An unboxed value may be represented by a pointer to a heap object:
230 primitive strings and arbitrary-precision integers are examples (see
231 Section~\ref{sect-primitive}).
234 %************************************************************************
236 \subsubsection{Primitive vs algebraic types}
238 %************************************************************************
240 There is a second classification of types, which is not quite orthogonal:
243 \item[Primitive types.]
244 A type is called {\em primitive} if it cannot be defined in
245 (Glasgow-extended) Haskell, and the only operations which manipulate its
246 representation are primitive ones. It follows that the domain
247 corresponding to a primitive type has no bottom element; that is, all
248 primitive data types are unboxed.
250 By convention, the names of all primitive types end with @#@.
252 \item[Algebraic data types.]
253 These are built with Haskell's @data@ declaration. Currently, @data@
254 declarations can {\em only} build boxed types (and hence {\em all
255 unboxed types are also primitive}), but we plan to lift this
256 restriction in due course.
259 %************************************************************************
261 \subsection[prelude-onion]{Summary of the ``Prelude onion''}
263 %************************************************************************
268 {\em Primitive} types, and operations thereon (@PrimitiveOps@), are at
269 the core of the onion.
272 Everything exported @fromPreludeCore@ (w/ all noted provisos) makes up
273 the next layer of the onion; and, by decree, the compiler has built-in
274 knowledge of all of it. All the primitive stuff is included in this
278 The compiler {\em chooses to know} about a few of the
279 non-@fromPreludeCore@ values in the @Prelude@. This is (exclusively)
280 for access to their unfoldings.
283 The rest of the @Prelude@ is ``unknown'' to the compiler itself; it
284 gets its information from a \tr{Prelude.hi} file, exactly as it does
285 for user-defined modules.
288 %************************************************************************
290 \section{What the compiler knows about the prelude}
292 %************************************************************************
294 This is essentially the stuff in the directory \tr{ghc/compiler/prelude}.
296 %************************************************************************
298 \subsection{What the compiler knows about prelude types (and ops thereon)}
300 %************************************************************************
302 The compiler has wired into it knowledge of all the types in the
303 standard prelude, all of which are exported by @PreludeCore@.
304 Strictly speaking, it needn't know about some types (e.g., the
305 @Request@ and @Response@ datatypes), but it's tidier in the end to
308 Primitive types, and related stuff, are covered first. Then the more
309 ordinary prelude types. The more turgid parts may be arranged
315 %************************************************************************
317 \section{Primitive types (and ``kinds'') {\em and} operations thereon}
318 \label{sect-primitive}
320 %************************************************************************
322 There are the following primitive types.
323 %partain:\begin{center}
324 \begin{tabular}{|llll|}
326 Type & Represents & Size (32|64-bit words) & Pointer? \\
328 @Void#@ & zero-element type & 1 & No \\
329 @Char#@ & characters & 1 & No \\
330 @Int#@ & 32|64-bit integers & 1 & No \\
331 @Float#@ & 32|64-bit floats & 1 & No \\
332 @Double#@ & 64|128-bit floats & 2 & No \\
333 @Arr#@ & array of pointers & ? & Yes \\
334 @Arr# Char#@ & array of @Char#@s & ? & No \\
335 @Arr# Int#@ & array of @Int#@s & ? & No \\
336 @Arr# Float#@ & array of @Float#@s & ? & No \\
337 @Arr# Double#@ & array of @Double#@s & ? & No \\
338 @Integer#@ & arbitrary-precision integers & 1 & Yes \\
339 @LitString#@ & literal C-style strings & 1 & No \\
342 %partain:\end{center}
344 Notes: (a)~@Integer#s@ have a pointer in them, to a @Arr# Int#@; see
345 the discussion in @TyInteger@. (b)~@LitString#@ is a magical type
346 used {\em only} to handle literal C-strings; this is a convenience; we
347 could use an @Arr# Char#@ instead.
349 What the compiler knows about these primitive types is either
350 (a)~given with the corresponding algebraic type (e.g., @Int#@ stuff is
351 with @Int@ stuff), or (b)~in a module of its own (e.g., @Void#@).
356 \section{Details about ``Glasgow-special'' types}
367 %************************************************************************
369 \section{Details (mostly) about non-primitive Prelude types}
370 \label{sect-nonprim-tys}
372 %************************************************************************
375 \input{TysWiredIn.lhs}
378 %************************************************************************
380 %\subsection{What the compiler knows about prelude values}
382 %************************************************************************
387 %************************************************************************
389 \subsection{Uniquifiers and utility bits for this prelude stuff}
391 %************************************************************************
398 %************************************************************************
400 %\subsection{The @AbsPrel@ interface to the compiler's prelude knowledge}
402 %************************************************************************
407 %************************************************************************
409 \section{The executable code for prelude bits}
411 %************************************************************************
413 This essentially describes what happens in the directories
414 \tr{ghc/lib/{io,prelude}}; the former is to support the (non-std)
415 Glasgow I/O; the latter is regular prelude things.