ghc/compiler/prelude/prelude.lit

   1 \documentstyle[11pt,literate,a4wide]{article}
   2
   3 %--------------------
   4 \begin{rawlatex}
   5 %\input{transfig}
   6
   7 %\newcommand{\folks}[1]{$\spadesuit$ {\em #1} $\spadesuit$}
   8 %\newcommand{\ToDo}[1]{$\spadesuit$ {\bf ToDo:} {\em #1} $\spadesuit$}
   9
  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}}}
  14
  15 \setcounter{secnumdepth}{6}
  16 \setcounter{tocdepth}{6}
  17 \end{rawlatex}
  18 %--------------------
  19
  20 \begin{document}
  21 \title{Basic types and the standard Prelude: OBSOLETE}
  22 \author{The AQUA team}
  23 \date{November 1992 (obsolete February 1994)}
  24 \maketitle
  25 \begin{rawlatex}
  26 \tableofcontents
  27 \pagebreak
  28 \end{rawlatex}
  29
  30 % added to keep DPH stuff happy:
  31 \begin{rawlatex}
  32 \def\DPHaskell{DPHaskell}
  33 \def\POD{POD}
  34 \end{rawlatex}
  35
  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
  39 delicate.
  40
  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.
  45
  46 %************************************************************************
  47 %*                                                                      *
  48 \section{Introduction and terminology}
  49 %*                                                                      *
  50 %************************************************************************
  51
  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@).
  57
  58 In this section, the main thing we do is explain the various ways that
  59 we categorise prelude thingies, most notably types.
  60
  61 %************************************************************************
  62 %*                                                                      *
  63 \subsection{Background information}
  64 %*                                                                      *
  65 %************************************************************************
  66
  67 %************************************************************************
  68 %*                                                                      *
  69 \subsubsection{Background terms: Heap objects}
  70 %*                                                                      *
  71 %************************************************************************
  72
  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
  76 the usual way.
  77
  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
  83 updatable.
  84
  85 (Much) more on this stuff in the STG paper.
  86
  87 %************************************************************************
  88 %*                                                                      *
  89 \subsection{Categorising the prelude bits}
  90 %*                                                                      *
  91 %************************************************************************
  92
  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.
  97
  98 \begin{description}
  99 %------------------------------------------------------------------
 100 \item[Primitive vs Haskell-able:]
 101
 102 Some parts of the prelude cannot be expressed in Haskell ({\em
 103 primitive}), whereas most of it can be ({\em Haskell-able}).
 104
 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
 108 an @Int@ is just:
 109
 110 \begin{verbatim}
 111 negateInt i
 112   = case i of MkInt i# -> case (negateInt# i#) of j# -> MkInt j#
 113 \end{verbatim}
 114
 115 Of course, this just moves the goalposts: @negateInt#@ is now the
 116 primitive, non-Haskell-able thingy...
 117
 118 So: something is ``primitive'' if we cannot define it in our
 119 GHC-extended Haskell.
 120
 121 For more information, please see \sectionref{prelude-more-on-types}
 122 for further discussion about types in the Prelude.
 123
 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.
 129
 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.)
 134
 135 {\em Simplifying assumption:} We take everything primitive (see
 136 previous classification) to be ``from PreludeCore''.
 137
 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...
 144
 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,
 149 anyway).
 150
 151 Not-exported-by-PreludeCore things (non-@PreludeBuiltin@ values) can
 152 be renamed, hidden, etc.
 153
 154 %------------------------------------------------------------------
 155 \item[Compiler-must-know vs compiler-chooses-to-know vs compiler-unknown:]
 156
 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.
 160
 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...
 168
 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@.
 175
 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
 181 files.)
 182
 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).
 188
 189 In this document, ``Haskell'' always means ``Glasgow-extended
 190 Haskell.''
 191 \end{description}
 192
 193 %************************************************************************
 194 %*                                                                      *
 195 \subsection[prelude-more-on-types]{More about the Prelude datatypes}
 196 %*                                                                      *
 197 %************************************************************************
 198
 199 The previous section explained how we categorise the prelude as a
 200 whole.  In this section, we home in on prelude datatypes.
 201
 202 %************************************************************************
 203 %*                                                                      *
 204 \subsubsection{Boxed vs unboxed types}
 205 %*                                                                      *
 206 %************************************************************************
 207
 208 Objects of a particular type are all represented the same way.
 209 We recognise two kinds of types:
 210 \begin{description}
 211
 212 \item[Boxed 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.
 218
 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.
 223
 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.)
 228
 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}).
 232 \end{description}
 233
 234 %************************************************************************
 235 %*                                                                      *
 236 \subsubsection{Primitive vs algebraic types}
 237 %*                                                                      *
 238 %************************************************************************
 239
 240 There is a second classification of types, which is not quite orthogonal:
 241 \begin{description}
 242
 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.
 249
 250 By convention, the names of all primitive types end with @#@.
 251
 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.
 257 \end{description}
 258
 259 %************************************************************************
 260 %*                                                                      *
 261 \subsection[prelude-onion]{Summary of the ``Prelude onion''}
 262 %*                                                                      *
 263 %************************************************************************
 264
 265 Summarizing:
 266 \begin{enumerate}
 267 \item
 268 {\em Primitive} types, and operations thereon (@PrimitiveOps@), are at
 269 the core of the onion.
 270
 271 \item
 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
 275 category.
 276
 277 \item
 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.
 281
 282 \item
 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.
 286 \end{enumerate}
 287
 288 %************************************************************************
 289 %*                                                                      *
 290 \section{What the compiler knows about the prelude}
 291 %*                                                                      *
 292 %************************************************************************
 293
 294 This is essentially the stuff in the directory \tr{ghc/compiler/prelude}.
 295
 296 %************************************************************************
 297 %*                                                                      *
 298 \subsection{What the compiler knows about prelude types (and ops thereon)}
 299 %*                                                                      *
 300 %************************************************************************
 301
 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
 306 wire in everything.
 307
 308 Primitive types, and related stuff, are covered first.  Then the more
 309 ordinary prelude types.  The more turgid parts may be arranged
 310 alphabetically...
 311
 312 \downsection
 313 \downsection
 314 % pretty ugly, no?
 315 %************************************************************************
 316 %*                                                                      *
 317 \section{Primitive types (and ``kinds'') {\em and} operations thereon}
 318 \label{sect-primitive}
 319 %*                                                                      *
 320 %************************************************************************
 321
 322 There are the following primitive types.
 323 %partain:\begin{center}
 324 \begin{tabular}{|llll|}
 325 \hline
 326 Type & Represents & Size (32|64-bit words) & Pointer? \\
 327 \hline
 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 \\
 340 \hline
 341 \end{tabular}
 342 %partain:\end{center}
 343
 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.
 348
 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#@).
 352
 353 \downsection
 354 \input{PrimKind.lhs}
 355
 356 \section{Details about ``Glasgow-special'' types}
 357
 358 \downsection
 359 \input{TysPrim.lhs}
 360 \input{TyPod.lhs}
 361 \input{TyProcs.lhs}
 362 \upsection
 363
 364 \input{PrimOps.lhs}
 365 \upsection
 366
 367 %************************************************************************
 368 %*                                                                      *
 369 \section{Details (mostly) about non-primitive Prelude types}
 370 \label{sect-nonprim-tys}
 371 %*                                                                      *
 372 %************************************************************************
 373
 374 \downsection
 375 \input{TysWiredIn.lhs}
 376 \upsection
 377
 378 %************************************************************************
 379 %*                                                                      *
 380 %\subsection{What the compiler knows about prelude values}
 381 %*                                                                      *
 382 %************************************************************************
 383 \downsection
 384 \input{PrelVals.lhs}
 385 \upsection
 386
 387 %************************************************************************
 388 %*                                                                      *
 389 \subsection{Uniquifiers and utility bits for this prelude stuff}
 390 %*                                                                      *
 391 %************************************************************************
 392 \downsection
 393 \downsection
 394 \input{PrelFuns.lhs}
 395 \upsection
 396 \upsection
 397
 398 %************************************************************************
 399 %*                                                                      *
 400 %\subsection{The @AbsPrel@ interface to the compiler's prelude knowledge}
 401 %*                                                                      *
 402 %************************************************************************
 403 \downsection
 404 \input{AbsPrel.lhs}
 405 \upsection
 406
 407 %************************************************************************
 408 %*                                                                      *
 409 \section{The executable code for prelude bits}
 410 %*                                                                      *
 411 %************************************************************************
 412
 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.
 416
 417 ToDo: more.
 418
 419 \printindex
 420 \end{document}