posts: Add "Bootstrapping Haskell: part 1"
authorRicardo Wurmus <rekado@elephly.net>
Mon, 9 Jan 2017 12:45:26 +0000 (13:45 +0100)
committerRicardo Wurmus <rekado@elephly.net>
Mon, 9 Jan 2017 12:45:58 +0000 (13:45 +0100)
* posts/2017-01-09-bootstrapping-haskell-part-1.html: New file.
* 2017-01-09-bootstrapping-haskell-part-1.org: New file.

2017-01-09-bootstrapping-haskell-part-1.org [new file with mode: 0644]
posts/2017-01-09-bootstrapping-haskell-part-1.html [new file with mode: 0644]

diff --git a/2017-01-09-bootstrapping-haskell-part-1.org b/2017-01-09-bootstrapping-haskell-part-1.org
new file mode 100644 (file)
index 0000000..22cabc3
--- /dev/null
@@ -0,0 +1,483 @@
+#+TITLE: Bootstrapping Haskell: part 1
+#+AUTHOR: Ricardo Wurmus
+#+DATE: <2017-01-08 Sun>
+
+Haskell is a formally specified language with potentially many alternative implementations, but in early 2017 the reality is that Haskell is whatever the Glasgow Haskell Compiler (GHC) implements.  Unfortunately, to build GHC one needs a previous version of GHC.  This is true for all public releases of GHC all the way back to version 0.29, which was released in 1996 and which implements Haskell 1.2.  Some GHC releases include files containing generated ANSI C code, which require only a C compiler to build.  For most purposes, generated code does not qualify as source code.
+
+So I wondered: /is it possible to construct a procedure to build a modern release of GHC from source without depending on any generated code or pre-built binaries of an older variant of GHC?/  The answer to this question depends on the answers to a number of related questions.  One of them is: are there any alternative Haskell implementations that are still usable today and that can be built without GHC?
+
+* A short survey of Haskell implementations
+
+Although nowadays hardly anyone uses any other Haskell compiler but GHC in production there are some alternative Haskell implementations that were protected from bit rot and thus can still be built from source with today’s common toolchains.
+
+One of the oldest implementations is [[http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/syntax/haskell/0.html][Yale Haskell]], a Haskell system embedded in Common Lisp.  The last release of Yale Haskell was version 2.0.5 in the early 1990s.[fn::It is unclear when exactly the release was made, but any time between 1991 and 1993 seems likely.]  Yale Haskell runs on top of CMU Common Lisp, Lucid Common Lisp, Allegro Common Lisp, or Harlequin LispWorks, but since I do not have access to any of these proprietary Common Lisp implementations, I ported the Yale Haskell system to GNU CLISP.  The [[http://git.elephly.net/software/yale-haskell.git][code for the port is available here]].  Yale Haskell is not a compiler, it can only be used as an interpreter.
+
+Another Haskell interpreter with a more recent release is [[https://haskell.org/hugs][Hugs]].  Hugs is written in C and implements almost all of the Haskell 98 standard.  It also comes with a number of [[https://www.haskell.org/hugs/pages/users_guide/hugs-ghc.htm][useful language extensions]] that GHC and other Haskell systems depend on.  Unfortunately, it cannot deal with mutually recursive module dependencies, which is a feature that even the earliest versions of GHC rely on.  This means that running a variant of GHC inside of Hugs is not going to work without major changes.
+
+An alternative Haskell compiler that does not need to be built with GHC is [[https://www.haskell.org/nhc98][nhc98]].  Its latest release was in 2010, which is much more recent than any of the other Haskell implementations mentioned so far.  nhc98 is written in Haskell, so a Haskell compiler or interpreter is required to build it.  Like GHC the release of nhc98 comes with files containing generated C code, but depending on them for a clean bootstrap is almost as bad as depending on a third-party binary.  Sadly, nhc98 has another shortcoming: it is restricted to 32-bit machine architectures.
+
+* An early bootstrapping idea
+
+Since nhc98 is written in C (the runtime) and standard Haskell 98, we can run the Haskell parts of the compiler inside of a Haskell 98 interpreter.  Luckily, we have an interpreter that fits the bill: Hugs!  If we can interpret and run enough parts of nhc98 with Hugs we might be able to use nhc98 on Hugs to build a native version of nhc98 and related tools (such as cpphs, hmake, and cabal).  Using the native compiler we can build a complete toolchain and just /maybe/ that’s enough to build an early version of GHC.  Once we have an early version of GHC we can go ahead and build later versions with ease.  (Building GHC directly using nhc98 on Hugs might also work, but due to complexity in GHC modules it seems better to avoid depending on Hugs at runtime.)
+
+At this point I have verified that (with minor modifications) nhc98 can indeed be run on top of Hugs and that (with enough care to pre-processing and dependency ordering) it can build a native library from the Haskell source files of the nhc98 prelude.  It is not clear whether nhc98 would be capable of building a version of GHC and how close to a modern version GHC we can get with just nhc98.  There are also problems with the nhc98 runtime on modern x86_64 systems (more on that at the end).
+
+* Setting up the environment
+
+Before we can start let’s prepare a suitable environment.  Since nhc98 can only be used on 32-bit architectures we need a GCC toolchain for i686.  With [[https://gnu.org/software/guix][GNU Guix]] it’s easy to set up a temporary environment containing just the right tools: the GCC toolchain, make, and Hugs.
+
+#+BEGIN_SRC sh
+guix environment --system=i686-linux \
+                 --ad-hoc gcc-toolchain@4 make hugs
+#+END_SRC
+
+* Building the runtime
+
+Now we can configure nhc98 and build the C runtime, which is needed to link the binary objects that nhc98 and GCC produce when compiling Haskell sources.  Configuration is easy:
+
+#+BEGIN_SRC sh
+cd /path/to/nhc98-1.22
+export NHCDIR=$PWD
+./configure
+#+END_SRC
+
+Next, we build the C runtime:
+
+#+BEGIN_SRC sh
+cd src/runtime
+make
+#+END_SRC
+
+This produces binary objects in an architecture-specific directory.  In my case this is =targets/x86_64-Linux=.
+
+* Building the prelude?
+
+The standard library in Haskell is called the prelude.  Most source files of nhc98 depend on the prelude in one way or another.  Although Hugs comes with its own prelude it is of little use for our purposes as components of nhc98 must be linked with a static prelude library object.  Hugs does not provide a suitable object that we could link to.
+
+To build the prelude we need a Haskell compiler that has the same call interface as nhc98.  Interestingly, much of the nhc98 compiler’s user interface is implemented as a shell script, which after extensive argument processing calls =nhc98comp= to translate Haskell source files into C code, and then runs GCC over the C files to create binary objects.  Since we do not have =nhc98comp= at this point, we need to fake it with Hugs (more on that later).
+
+* Detour: cpphs and GreenCard
+
+Unfortunately, this is not the only problem.  Some of the prelude’s source files require pre-processing by a tool called GreenCard, which generates boilerplate FFI code.  Of course, GreenCard is written in Haskell.  Since we cannot build a native GreenCard binary without the native nhc98 prelude library, we need to make GreenCard run on Hugs.  Some of the GreenCard sources require pre-processing with =cpphs=.  Luckily, that’s just a really simple Haskell script, so running it in Hugs is trivial.  We will need =cpphs= later again, so it makes sense to write a script for it.  Let’s call it =hugs-cpphs= and drop it in =${NHCDIR}=.
+
+#+BEGIN_SRC sh
+#!/bin/bash
+
+runhugs ${NHCDIR}/src/cpphs/cpphs.hs --noline -D__HASKELL98__ "$@"
+#+END_SRC
+
+Make it executable:
+
+#+BEGIN_SRC sh
+chmod +x hugs-cpphs
+#+END_SRC
+
+Okay, let’s first pre-process the GreenCard sources with =cpphs=.  To do that I ran the following commands:
+
+#+BEGIN_SRC sh
+cd ${NHCDIR}/src/greencard
+
+CPPPRE="${NHCDIR}/hugs-cpphs -D__NHC__"
+
+FILES="DIS.lhs \
+ HandLex.hs \
+ ParseLib.hs \
+ HandParse.hs \
+ FillIn.lhs \
+ Proc.lhs \
+ NHCBackend.hs \
+ NameSupply.lhs \
+ Process.lhs"
+
+for file in $FILES; do
+    cp $file $file.original && $CPPPRE $file.original > $file && rm $file.original
+done
+#+END_SRC
+
+The result is a bunch of GreenCard source files without these pesky CPP pre-processor directives.  Hugs can pre-process sources on the fly, but this makes evaluation orders of magnitude slower.  Pre-processing the sources once before using them repeatedly seems like a better choice.
+
+There is still a minor problem with GreenCard on Hugs.  The GreenCard sources import the module =NonStdTrace=, which depends on built-in prelude functions from nhc98.  Obviously, they are not available when running on Hugs (it has its own prelude implementation), so we need to provide an alternative using just the regular Hugs prelude.  The following snippet creates a file named =src/prelude/NonStd/NonStdTraceBootstrap.hs= with the necessary changes.
+
+#+BEGIN_SRC sh
+cd ${NHCDIR}/src/prelude/NonStd/
+sed -e 's|NonStdTrace|NonStdTraceBootstrap|' \
+    -e 's|import PreludeBuiltin||' \
+    -e 's|_||g' NonStdTrace.hs > NonStdTraceBootstrap.hs
+#+END_SRC
+
+Then we change a single line in  =src/greencard/NHCBackend.hs= to make it import =NonStdTraceBootstrap= instead of =NonStdTrace=.
+
+#+BEGIN_SRC sh
+cd ${NHCDIR}/src/greencard
+sed -i -e 's|NonStdTrace|NonStdTraceBootstrap|' NHCBackend.hs
+#+END_SRC
+
+To run GreenCard we still need a driver script.  Let’s call this =hugs-greencard= and place it in =${NHCDIR}=:
+
+#+BEGIN_SRC sh
+#!/bin/bash
+
+HUGSDIR="$(dirname $(readlink -f $(which runhugs)))/../"
+SEARCH_HUGS=$(printf "${NHCDIR}/src/%s/*:" compiler prelude libraries)
+
+runhugs -98 \
+        -P${HUGSDIR}/lib/hugs/packages/*:${NHCDIR}/include/*:${SEARCH_HUGS} \
+        ${NHCDIR}/src/greencard/GreenCard.lhs \
+        $@
+#+END_SRC
+
+Make it executable:
+
+#+BEGIN_SRC sh
+cd ${NHCDIR}
+chmod +x hugs-greencard
+#+END_SRC
+
+* Building the prelude!
+
+Where were we?  Ah, the prelude.  As stated earlier, we need a working replacement for =nhc98comp=, which will be called by the driver script =script/nhc98= (created by the configure script).  Let’s call the replacement =hugs-nhc=, and again we’ll dump it in =${NHCDIR}=.  Here it is in all its glory:
+
+#+BEGIN_SRC sh
+#!/bin/bash
+
+# Root directory of Hugs installation
+HUGSDIR="$(dirname $(readlink -f $(which runhugs)))/../"
+
+# TODO: "libraries" alone may be sufficient
+SEARCH_HUGS=$(printf "${NHCDIR}/src/%s/*:" compiler prelude libraries)
+
+# Filter everything from "+RTS" to "-RTS" from $@ because MainNhc98.hs
+# does not know what to do with these flags.
+ARGS=""
+SKIP="false"
+for arg in "$@"; do
+    if [[ $arg == "+RTS" ]]; then
+        SKIP="true"
+    elif [[ $arg == "-RTS" ]]; then
+        SKIP="false"
+    elif [[ $SKIP == "false" ]]; then
+        ARGS="${ARGS} $arg"
+    fi
+done
+
+runhugs -98 \
+        -P${HUGSDIR}/lib/hugs/packages/*:${SEARCH_HUGS} \
+        ${NHCDIR}/src/compiler98/MainNhc98.hs \
+        $ARGS
+#+END_SRC
+
+All this does is run Hugs (=runhugs=) with language extensions (=-98=),  ensures that Hugs knows where to look for Hugs and nhc98 modules (=-P=), loads up the compiler’s =main= function, and then passes any arguments other than RTS flags (=$ARGS=) to it.
+
+Let’s also make this executable:
+
+#+BEGIN_SRC sh
+cd ${NHCDIR}
+chmod +x hugs-nhc
+#+END_SRC
+
+The compiler sources contain pre-processor directives, which need to be removed before running =hugs-nhc=.  It would be foolish to let Hugs pre-process the sources at runtime with =-F=.  In my tests it made =hugs-nhc= run slower by an order of magnitude.  Let’s pre-process the sources of the compiler and the libraries it depends on with =hugs-cpphs= (see above):
+
+#+BEGIN_SRC sh
+cd ${NHCDIR}
+CPPPRE="${NHCDIR}/hugs-cpphs -D__HUGS__"
+
+FILES="src/compiler98/GcodeLowC.hs \
+ src/libraries/filepath/System/FilePath.hs \
+ src/libraries/filepath/System/FilePath/Posix.hs"
+
+for file in $FILES; do
+    cp $file $file.original && $CPPPRE $file.original > $file && rm $file.original
+done
+#+END_SRC
+
+The compiler’s driver script =script/nhc98= expects to find the executables of =hmake-PRAGMA=, =greencard-nhc98=, and =cpphs= in the architecture-specific lib directory (in my case that’s =${NHCDIR}/lib/x86_64-Linux/=).  They do not exist, obviously, but for two of them we already have scripts to run them on top of Hugs.  =hmake-PRAGMA= does not seem to be very important; replacing it with =cat= appears to be fine.  To pacify the compiler script it’s easiest to just replace a few definitions:
+
+#+BEGIN_SRC sh
+cd ${NHCDIR}
+sed -i \
+  -e '0,/^GREENCARD=.*$/s||GREENCARD="$NHC98BINDIR/../hugs-greencard"|' \
+  -e '0,/^CPPHS=.*$/s||CPPHS="$NHC98BINDIR/../hugs-cpphs -D__NHC__"|' \
+  -e '0,/^PRAGMA=.*$/s||PRAGMA=cat|' \
+  script/nhc98
+#+END_SRC
+
+Initially, this looked like it would be enough, but half-way through building the prelude Hugs choked when interpreting nhc98 to build a certain module.  After some experimentation it turned out that the =NHC.FFI= module in =src/prelude/FFI/CTypes.hs= is too big for Hugs.  Running nhc98 on that module causes Hugs to abort with an overflow in the control stack.  The fix here is to break up the module to make it easier for nhc98 to build it, which in turn prevents Hugs from doing too much work at once.
+
+Apply this patch:
+
+#+BEGIN_EXAMPLE
+From 9eb2a2066eb9f93e60e447aab28479af6c8b9759 Mon Sep 17 00:00:00 2001
+From: Ricardo Wurmus <rekado@elephly.net>
+Date: Sat, 7 Jan 2017 22:31:41 +0100
+Subject: [PATCH] Split up CTypes
+
+This is necessary to avoid a control stack overflow in Hugs when
+building the FFI library with nhc98 running on Hugs.
+---
+ src/prelude/FFI/CStrings.hs     |  2 ++
+ src/prelude/FFI/CTypes.hs       | 14 --------------
+ src/prelude/FFI/CTypes1.hs      | 20 ++++++++++++++++++++
+ src/prelude/FFI/CTypes2.hs      | 22 ++++++++++++++++++++++
+ src/prelude/FFI/CTypesExtra.hs  |  2 ++
+ src/prelude/FFI/FFI.hs          |  2 ++
+ src/prelude/FFI/Makefile        |  8 ++++----
+ src/prelude/FFI/MarshalAlloc.hs |  2 ++
+ src/prelude/FFI/MarshalUtils.hs |  2 ++
+ 9 files changed, 56 insertions(+), 18 deletions(-)
+ create mode 100644 src/prelude/FFI/CTypes1.hs
+ create mode 100644 src/prelude/FFI/CTypes2.hs
+
+diff --git a/src/prelude/FFI/CStrings.hs b/src/prelude/FFI/CStrings.hs
+index 18fdfa9..f1373cf 100644
+--- a/src/prelude/FFI/CStrings.hs
++++ b/src/prelude/FFI/CStrings.hs
+@@ -23,6 +23,8 @@ module NHC.FFI (
+ import MarshalArray
+ import CTypes
++import CTypes1
++import CTypes2
+ import Ptr
+ import Word
+ import Char
+diff --git a/src/prelude/FFI/CTypes.hs b/src/prelude/FFI/CTypes.hs
+index 18e9d60..942e7a1 100644
+--- a/src/prelude/FFI/CTypes.hs
++++ b/src/prelude/FFI/CTypes.hs
+@@ -4,11 +4,6 @@ module NHC.FFI
+         -- Typeable, Storable, Bounded, Real, Integral, Bits
+         CChar(..),    CSChar(..),  CUChar(..)
+       , CShort(..),   CUShort(..), CInt(..),    CUInt(..)
+-      , CLong(..),    CULong(..),  CLLong(..),  CULLong(..)
+-
+-        -- Floating types, instances of: Eq, Ord, Num, Read, Show, Enum,
+-        -- Typeable, Storable, Real, Fractional, Floating, RealFrac, RealFloat
+-      , CFloat(..),   CDouble(..), CLDouble(..)
+       ) where
+ import NonStdUnsafeCoerce
+@@ -29,12 +24,3 @@ INTEGRAL_TYPE(CShort,Int16)
+ INTEGRAL_TYPE(CUShort,Word16)
+ INTEGRAL_TYPE(CInt,Int)
+ INTEGRAL_TYPE(CUInt,Word32)
+-INTEGRAL_TYPE(CLong,Int32)
+-INTEGRAL_TYPE(CULong,Word32)
+-INTEGRAL_TYPE(CLLong,Int64)
+-INTEGRAL_TYPE(CULLong,Word64)
+-
+-FLOATING_TYPE(CFloat,Float)
+-FLOATING_TYPE(CDouble,Double)
+--- HACK: Currently no long double in the FFI, so we simply re-use double
+-FLOATING_TYPE(CLDouble,Double)
+diff --git a/src/prelude/FFI/CTypes1.hs b/src/prelude/FFI/CTypes1.hs
+new file mode 100644
+index 0000000..81ba0f5
+--- /dev/null
++++ b/src/prelude/FFI/CTypes1.hs
+@@ -0,0 +1,20 @@
++{-# OPTIONS_COMPILE -cpp #-}
++module NHC.FFI
++      ( CLong(..),    CULong(..),  CLLong(..),  CULLong(..)
++      ) where
++
++import NonStdUnsafeCoerce
++import Int    ( Int8,  Int16,  Int32,  Int64  )
++import Word   ( Word8, Word16, Word32, Word64 )
++import Storable       ( Storable(..) )
++-- import Data.Bits( Bits(..) )
++-- import NHC.SizedTypes
++import Monad  ( liftM )
++import Ptr    ( castPtr )
++
++#include "CTypes.h"
++
++INTEGRAL_TYPE(CLong,Int32)
++INTEGRAL_TYPE(CULong,Word32)
++INTEGRAL_TYPE(CLLong,Int64)
++INTEGRAL_TYPE(CULLong,Word64)
+diff --git a/src/prelude/FFI/CTypes2.hs b/src/prelude/FFI/CTypes2.hs
+new file mode 100644
+index 0000000..7d66242
+--- /dev/null
++++ b/src/prelude/FFI/CTypes2.hs
+@@ -0,0 +1,22 @@
++{-# OPTIONS_COMPILE -cpp #-}
++module NHC.FFI
++      ( -- Floating types, instances of: Eq, Ord, Num, Read, Show, Enum,
++        -- Typeable, Storable, Real, Fractional, Floating, RealFrac, RealFloat
++      CFloat(..), CDouble(..), CLDouble(..)
++      ) where
++
++import NonStdUnsafeCoerce
++import Int    ( Int8,  Int16,  Int32,  Int64  )
++import Word   ( Word8, Word16, Word32, Word64 )
++import Storable       ( Storable(..) )
++-- import Data.Bits( Bits(..) )
++-- import NHC.SizedTypes
++import Monad  ( liftM )
++import Ptr    ( castPtr )
++
++#include "CTypes.h"
++
++FLOATING_TYPE(CFloat,Float)
++FLOATING_TYPE(CDouble,Double)
++-- HACK: Currently no long double in the FFI, so we simply re-use double
++FLOATING_TYPE(CLDouble,Double)
+diff --git a/src/prelude/FFI/CTypesExtra.hs b/src/prelude/FFI/CTypesExtra.hs
+index ba3f15b..7cbdcbb 100644
+--- a/src/prelude/FFI/CTypesExtra.hs
++++ b/src/prelude/FFI/CTypesExtra.hs
+@@ -20,6 +20,8 @@ import Storable      ( Storable(..) )
+ import Monad  ( liftM )
+ import Ptr    ( castPtr )
+ import CTypes
++import CTypes1
++import CTypes2
+ #include "CTypes.h"
+diff --git a/src/prelude/FFI/FFI.hs b/src/prelude/FFI/FFI.hs
+index 9d91e57..0c29394 100644
+--- a/src/prelude/FFI/FFI.hs
++++ b/src/prelude/FFI/FFI.hs
+@@ -217,6 +217,8 @@ import MarshalUtils        -- routines for basic marshalling
+ import MarshalError   -- routines for basic error-handling
+ import CTypes         -- newtypes for various C basic types
++import CTypes1
++import CTypes2
+ import CTypesExtra    -- types for various extra C types
+ import CStrings               -- C pointer to array of char
+ import CString                -- nhc98-only
+diff --git a/src/prelude/FFI/Makefile b/src/prelude/FFI/Makefile
+index 99065f8..e229672 100644
+--- a/src/prelude/FFI/Makefile
++++ b/src/prelude/FFI/Makefile
+@@ -18,7 +18,7 @@ EXTRA_C_FLAGS        =
+ SRCS = \
+       Addr.hs Ptr.hs FunPtr.hs Storable.hs \
+       ForeignObj.hs ForeignPtr.hs Int.hs Word.hs \
+-      CError.hs CTypes.hs CTypesExtra.hs CStrings.hs \
++      CError.hs CTypes.hs CTypes1.hs CTypes2.hs CTypesExtra.hs CStrings.hs \
+       MarshalAlloc.hs MarshalArray.hs MarshalError.hs MarshalUtils.hs \
+       StablePtr.hs
+@@ -38,12 +38,12 @@ Word.hs: Word.hs.cpp
+ # dependencies generated by hmake -Md: (and hacked by MW)
+ ${OBJDIR}/MarshalError.$O: ${OBJDIR}/Ptr.$O 
+ ${OBJDIR}/MarshalUtils.$O: ${OBJDIR}/Ptr.$O ${OBJDIR}/Storable.$O \
+-      ${OBJDIR}/MarshalAlloc.$O ${OBJDIR}/CTypes.$O ${OBJDIR}/CTypesExtra.$O 
++      ${OBJDIR}/MarshalAlloc.$O ${OBJDIR}/CTypes.$O ${OBJDIR}/CTypes1.$O ${OBJDIR}/CTypes2.$O ${OBJDIR}/CTypesExtra.$O
+ ${OBJDIR}/MarshalArray.$O: ${OBJDIR}/Ptr.$O ${OBJDIR}/Storable.$O \
+       ${OBJDIR}/MarshalAlloc.$O ${OBJDIR}/MarshalUtils.$O 
+-${OBJDIR}/CTypesExtra.$O: ${OBJDIR}/Int.$O ${OBJDIR}/Word.$O ${OBJDIR}/CTypes.$O
++${OBJDIR}/CTypesExtra.$O: ${OBJDIR}/Int.$O ${OBJDIR}/Word.$O ${OBJDIR}/CTypes.$O ${OBJDIR}/CTypes1.$O ${OBJDIR}/CTypes2.$O
+ ${OBJDIR}/CTypes.$O: ${OBJDIR}/Int.$O ${OBJDIR}/Word.$O ${OBJDIR}/Storable.$O \
+-      ${OBJDIR}/Ptr.$O 
++      ${OBJDIR}/Ptr.$O ${OBJDIR}/CTypes1.$O ${OBJDIR}/CTypes2.$O
+ ${OBJDIR}/CStrings.$O: ${OBJDIR}/MarshalArray.$O ${OBJDIR}/CTypes.$O \
+       ${OBJDIR}/Ptr.$O ${OBJDIR}/Word.$O
+ ${OBJDIR}/MarshalAlloc.$O: ${OBJDIR}/Ptr.$O ${OBJDIR}/Storable.$O \
+diff --git a/src/prelude/FFI/MarshalAlloc.hs b/src/prelude/FFI/MarshalAlloc.hs
+index 34ac7b3..5b43554 100644
+--- a/src/prelude/FFI/MarshalAlloc.hs
++++ b/src/prelude/FFI/MarshalAlloc.hs
+@@ -14,6 +14,8 @@ import ForeignPtr (FinalizerPtr(..))
+ import Storable
+ import CError
+ import CTypes
++import CTypes1
++import CTypes2
+ import CTypesExtra (CSize)
+ import NHC.DErrNo
+diff --git a/src/prelude/FFI/MarshalUtils.hs b/src/prelude/FFI/MarshalUtils.hs
+index 312719b..bd9d149 100644
+--- a/src/prelude/FFI/MarshalUtils.hs
++++ b/src/prelude/FFI/MarshalUtils.hs
+@@ -29,6 +29,8 @@ import Ptr
+ import Storable
+ import MarshalAlloc
+ import CTypes
++import CTypes1
++import CTypes2
+ import CTypesExtra
+ -- combined allocation and marshalling
+-- 
+2.11.0
+#+END_EXAMPLE
+
+After all this it’s time for a break.  Run the following commands for a long break:
+
+#+BEGIN_SRC sh
+cd ${NHCDIR}/src/prelude
+time make NHC98COMP=$NHCDIR/hugs-nhc
+#+END_SRC
+
+After the break—it took more than two hours on my laptop—you should see output like this:
+
+#+BEGIN_EXAMPLE
+ranlib /path/to/nhc98-1.22/lib/x86_64-Linux/Prelude.a
+#+END_EXAMPLE
+
+Congratulations!  You now have a native nhc98 prelude library!
+
+* Building hmake
+
+The compiler and additional Haskell libraries all require a tool called “hmake” to automatically order dependencies, so we’ll try to build it next.  There’s just a small problem with one of the source files: =src/hmake/FileName.hs= contains the name “Niklas Röjemo” and the compiler really does not like the umlaut.  With apologies to Niklas we change the copyright line to appease the compiler.
+
+#+BEGIN_SRC sh
+cd $NHCDIR/src/hmake
+mv FileName.hs{,.broken}
+tr '\366' 'o' < FileName.hs.broken > FileName.hs
+rm FileName.hs.broken
+NHC98COMP=$NHCDIR/hugs-nhc make HC=$NHCDIR/script/nhc98
+#+END_SRC
+
+* To be continued
+
+Unfortunately, the hmake tools are not working.  All of the tools (e.g. =MkConfig=) fail with an early segmentation fault.  There must be an error in the runtime, likely in =src/runtime/Kernel/mutator.c= where bytecode for heap and stack operations is interpreted.  One thing that looks like a problem is statements like this:
+
+#+BEGIN_EXAMPLE
+*--sp = (NodePtr) constptr[-HEAPOFFSET(ip[0])];
+#+END_EXAMPLE
+
+=constptr= is =NULL=, so this seems to be just pointer arithmetic expressed in array notation.  These errors can be fixed by rewriting the statement to use explicit pointer arithmetic:
+
+#+BEGIN_EXAMPLE
+*--sp = (NodePtr) (constptr + (-HEAPOFFSET(ip[0])));
+#+END_EXAMPLE
+
+Unfortunately, this doesn’t seem to be enough as there is another segfault in the handling of the =EvalTOS= label.  =IND_REMOVE= is applied to the contents of the stack pointer, which turns out to be =0x10=, which just doesn’t seem right.  =IND_REMOVE= removes indirection by following pointer addresses until the value stored at the given address does not look like an address.  This fails because =0x10= does look like an address—it’s just invalid.  I have enabled a bunch of tracing and debugging features, but I don’t fully understand how the nhc98 runtime is /supposed/ to work.
+
+Judging from mails on the nhc-bugs and nhc-users lists I see that I’m not the only one experiencing segfaults.  [[https://mail.haskell.org/pipermail/nhc-bugs/2005-October/000529.html][This email]] suggests that segfaults are “associated with changes in the way gcc lays out static arrays of bytecodes, e.g. by putting extra padding space between arrays that are supposed to be adjacent.”  I may have to try different compiler flags or an older version of GCC; I only tried with GCC 4.9.4 but the [[http://sources.debian.net/src/nhc98/1.16-15/debian/rules/][Debian package for nhc98]] used version 2.95 or 3.3.
+
+For completeness sake here’s the trace of the failing execution of MkProg:
+
+#+BEGIN_EXAMPLE
+(gdb) run
+Starting program: /path/to/nhc98-1.22/lib/x86_64-Linux/MkProg 
+ZAP_ARG_I1             hp=0x80c5010 sp=0x8136a10 fp=0x8136a10 ip=0x8085140
+NEEDHEAP_I32   hp=0x80c5010 sp=0x8136a10 fp=0x8136a10 ip=0x8085141
+HEAP_CVAL_N1   hp=0x80c5010 sp=0x8136a10 fp=0x8136a10 ip=0x8085142
+HEAP_CVAL_I3   hp=0x80c5014 sp=0x8136a10 fp=0x8136a10 ip=0x8085144
+HEAP_OFF_N1            hp=0x80c5018 sp=0x8136a10 fp=0x8136a10 ip=0x8085145
+PUSH_HEAP              hp=0x80c501c sp=0x8136a10 fp=0x8136a10 ip=0x8085147
+HEAP_CVAL_I4   hp=0x80c501c sp=0x8136a0c fp=0x8136a10 ip=0x8085148
+HEAP_CVAL_I5   hp=0x80c5020 sp=0x8136a0c fp=0x8136a10 ip=0x8085149
+HEAP_OFF_N1            hp=0x80c5024 sp=0x8136a0c fp=0x8136a10 ip=0x808514a
+PUSH_CVAL_P1   hp=0x80c5028 sp=0x8136a0c fp=0x8136a10 ip=0x808514c
+PUSH_I1                    hp=0x80c5028 sp=0x8136a08 fp=0x8136a10 ip=0x808514e
+ZAP_STACK_P1   hp=0x80c5028 sp=0x8136a04 fp=0x8136a10 ip=0x808514f
+EVAL               hp=0x80c5028 sp=0x8136a04 fp=0x8136a10 ip=0x8085151
+eval: evalToS
+
+Program received signal SIGSEGV, Segmentation fault.
+0x0804ac27 in run (toplevel=0x80c5008) at mutator.c:425
+425            IND_REMOVE(nodeptr);
+#+END_EXAMPLE
+
+=ip= is the instruction pointer, which points at the current element in the bytecode stream.  =fp= is probably the frame pointer, =sp= the stack pointer, and =hp= the heap pointer.  The [[https://www.haskell.org/nhc98/implementation-notes/index.html][implementation notes for nhc98]] will probably be helpful in solving this problem.
+
+Anyway, that’s where I’m at so far.   If you are interested in these kinds of problems or other bootstrapping projects, consider joining the efforts of the [[http://bootstrappable.org][Bootstrappable Builds project]]!
diff --git a/posts/2017-01-09-bootstrapping-haskell-part-1.html b/posts/2017-01-09-bootstrapping-haskell-part-1.html
new file mode 100644 (file)
index 0000000..ffd38bf
--- /dev/null
@@ -0,0 +1,634 @@
+title: Bootstrapping Haskell: part 1
+date: 2017-01-09 00:00
+tags: bootstrapping, haskell, planet-fsfe-en, free software
+---
+
+<div>
+<div id="table-of-contents">
+<h2>Table of Contents</h2>
+<div id="text-table-of-contents">
+<ul>
+<li><a href="#org2d8c41c">1. A short survey of Haskell implementations</a></li>
+<li><a href="#orgb07f4d3">2. An early bootstrapping idea</a></li>
+<li><a href="#org9ee479e">3. Setting up the environment</a></li>
+<li><a href="#org9e4c0ac">4. Building the runtime</a></li>
+<li><a href="#org655c609">5. Building the prelude?</a></li>
+<li><a href="#org360295f">6. Detour: cpphs and GreenCard</a></li>
+<li><a href="#org9519691">7. Building the prelude!</a></li>
+<li><a href="#orgace25de">8. Building hmake</a></li>
+<li><a href="#org83aa24b">9. To be continued</a></li>
+</ul>
+</div>
+</div>
+<p>
+Haskell is a formally specified language with potentially many alternative implementations, but in early 2017 the reality is that Haskell is whatever the Glasgow Haskell Compiler (GHC) implements.  Unfortunately, to build GHC one needs a previous version of GHC.  This is true for all public releases of GHC all the way back to version 0.29, which was released in 1996 and which implements Haskell 1.2.  Some GHC releases include files containing generated ANSI C code, which require only a C compiler to build.  For most purposes, generated code does not qualify as source code.
+</p>
+
+<p>
+So I wondered: <i>is it possible to construct a procedure to build a modern release of GHC from source without depending on any generated code or pre-built binaries of an older variant of GHC?</i>  The answer to this question depends on the answers to a number of related questions.  One of them is: are there any alternative Haskell implementations that are still usable today and that can be built without GHC?
+</p>
+
+<div id="outline-container-org2d8c41c" class="outline-2">
+<h2 id="org2d8c41c">A short survey of Haskell implementations</h2>
+<div class="outline-text-2" id="text-1">
+<p>
+Although nowadays hardly anyone uses any other Haskell compiler but GHC in production there are some alternative Haskell implementations that were protected from bit rot and thus can still be built from source with today’s common toolchains.
+</p>
+
+<p>
+One of the oldest implementations is <a href="http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/syntax/haskell/0.html">Yale Haskell</a>, a Haskell system embedded in Common Lisp.  The last release of Yale Haskell was version 2.0.5 in the early 1990s.<sup><a id="fnr.1" class="footref" href="#fn.1">1</a></sup>  Yale Haskell runs on top of CMU Common Lisp, Lucid Common Lisp, Allegro Common Lisp, or Harlequin LispWorks, but since I do not have access to any of these proprietary Common Lisp implementations, I ported the Yale Haskell system to GNU CLISP.  The <a href="http://git.elephly.net/software/yale-haskell.git">code for the port is available here</a>.  Yale Haskell is not a compiler, it can only be used as an interpreter.
+</p>
+
+<p>
+Another Haskell interpreter with a more recent release is <a href="https://haskell.org/hugs">Hugs</a>.  Hugs is written in C and implements almost all of the Haskell 98 standard.  It also comes with a number of <a href="https://www.haskell.org/hugs/pages/users_guide/hugs-ghc.htm">useful language extensions</a> that GHC and other Haskell systems depend on.  Unfortunately, it cannot deal with mutually recursive module dependencies, which is a feature that even the earliest versions of GHC rely on.  This means that running a variant of GHC inside of Hugs is not going to work without major changes.
+</p>
+
+<p>
+An alternative Haskell compiler that does not need to be built with GHC is <a href="https://www.haskell.org/nhc98">nhc98</a>.  Its latest release was in 2010, which is much more recent than any of the other Haskell implementations mentioned so far.  nhc98 is written in Haskell, so a Haskell compiler or interpreter is required to build it.  Like GHC the release of nhc98 comes with files containing generated C code, but depending on them for a clean bootstrap is almost as bad as depending on a third-party binary.  Sadly, nhc98 has another shortcoming: it is restricted to 32-bit machine architectures.
+</p>
+</div>
+</div>
+
+<div id="outline-container-orgb07f4d3" class="outline-2">
+<h2 id="orgb07f4d3">An early bootstrapping idea</h2>
+<div class="outline-text-2" id="text-2">
+<p>
+Since nhc98 is written in C (the runtime) and standard Haskell 98, we can run the Haskell parts of the compiler inside of a Haskell 98 interpreter.  Luckily, we have an interpreter that fits the bill: Hugs!  If we can interpret and run enough parts of nhc98 with Hugs we might be able to use nhc98 on Hugs to build a native version of nhc98 and related tools (such as cpphs, hmake, and cabal).  Using the native compiler we can build a complete toolchain and just <i>maybe</i> that’s enough to build an early version of GHC.  Once we have an early version of GHC we can go ahead and build later versions with ease.  (Building GHC directly using nhc98 on Hugs might also work, but due to complexity in GHC modules it seems better to avoid depending on Hugs at runtime.)
+</p>
+
+<p>
+At this point I have verified that (with minor modifications) nhc98 can indeed be run on top of Hugs and that (with enough care to pre-processing and dependency ordering) it can build a native library from the Haskell source files of the nhc98 prelude.  It is not clear whether nhc98 would be capable of building a version of GHC and how close to a modern version GHC we can get with just nhc98.  There are also problems with the nhc98 runtime on modern x86<sub>64</sub> systems (more on that at the end).
+</p>
+</div>
+</div>
+
+<div id="outline-container-org9ee479e" class="outline-2">
+<h2 id="org9ee479e">Setting up the environment</h2>
+<div class="outline-text-2" id="text-3">
+<p>
+Before we can start let’s prepare a suitable environment.  Since nhc98 can only be used on 32-bit architectures we need a GCC toolchain for i686.  With <a href="https://gnu.org/software/guix">GNU Guix</a> it’s easy to set up a temporary environment containing just the right tools: the GCC toolchain, make, and Hugs.
+</p>
+
+<div class="org-src-container">
+<pre class="src src-sh">guix environment --system=i686-linux \
+                 --ad-hoc gcc-toolchain@4 make hugs
+</pre>
+</div>
+</div>
+</div>
+
+<div id="outline-container-org9e4c0ac" class="outline-2">
+<h2 id="org9e4c0ac">Building the runtime</h2>
+<div class="outline-text-2" id="text-4">
+<p>
+Now we can configure nhc98 and build the C runtime, which is needed to link the binary objects that nhc98 and GCC produce when compiling Haskell sources.  Configuration is easy:
+</p>
+
+<div class="org-src-container">
+<pre class="src src-sh">cd /path/to/nhc98-1.22
+export NHCDIR=$PWD
+./configure
+</pre>
+</div>
+
+<p>
+Next, we build the C runtime:
+</p>
+
+<div class="org-src-container">
+<pre class="src src-sh">cd src/runtime
+make
+</pre>
+</div>
+
+<p>
+This produces binary objects in an architecture-specific directory.  In my case this is <code>targets/x86_64-Linux</code>.
+</p>
+</div>
+</div>
+
+<div id="outline-container-org655c609" class="outline-2">
+<h2 id="org655c609">Building the prelude?</h2>
+<div class="outline-text-2" id="text-5">
+<p>
+The standard library in Haskell is called the prelude.  Most source files of nhc98 depend on the prelude in one way or another.  Although Hugs comes with its own prelude it is of little use for our purposes as components of nhc98 must be linked with a static prelude library object.  Hugs does not provide a suitable object that we could link to.
+</p>
+
+<p>
+To build the prelude we need a Haskell compiler that has the same call interface as nhc98.  Interestingly, much of the nhc98 compiler’s user interface is implemented as a shell script, which after extensive argument processing calls <code>nhc98comp</code> to translate Haskell source files into C code, and then runs GCC over the C files to create binary objects.  Since we do not have <code>nhc98comp</code> at this point, we need to fake it with Hugs (more on that later).
+</p>
+</div>
+</div>
+
+<div id="outline-container-org360295f" class="outline-2">
+<h2 id="org360295f">Detour: cpphs and GreenCard</h2>
+<div class="outline-text-2" id="text-6">
+<p>
+Unfortunately, this is not the only problem.  Some of the prelude’s source files require pre-processing by a tool called GreenCard, which generates boilerplate FFI code.  Of course, GreenCard is written in Haskell.  Since we cannot build a native GreenCard binary without the native nhc98 prelude library, we need to make GreenCard run on Hugs.  Some of the GreenCard sources require pre-processing with <code>cpphs</code>.  Luckily, that’s just a really simple Haskell script, so running it in Hugs is trivial.  We will need <code>cpphs</code> later again, so it makes sense to write a script for it.  Let’s call it <code>hugs-cpphs</code> and drop it in <code>${NHCDIR}</code>.
+</p>
+
+<div class="org-src-container">
+<pre class="src src-sh">#!/bin/bash
+
+runhugs ${NHCDIR}/src/cpphs/cpphs.hs --noline -D__HASKELL98__ "$@"
+</pre>
+</div>
+
+<p>
+Make it executable:
+</p>
+
+<div class="org-src-container">
+<pre class="src src-sh">chmod +x hugs-cpphs
+</pre>
+</div>
+
+<p>
+Okay, let’s first pre-process the GreenCard sources with <code>cpphs</code>.  To do that I ran the following commands:
+</p>
+
+<div class="org-src-container">
+<pre class="src src-sh">cd ${NHCDIR}/src/greencard
+
+CPPPRE="${NHCDIR}/hugs-cpphs -D__NHC__"
+
+FILES="DIS.lhs \
+ HandLex.hs \
+ ParseLib.hs \
+ HandParse.hs \
+ FillIn.lhs \
+ Proc.lhs \
+ NHCBackend.hs \
+ NameSupply.lhs \
+ Process.lhs"
+
+for file in $FILES; do
+    cp $file $file.original &amp;&amp; $CPPPRE $file.original &gt; $file &amp;&amp; rm $file.original
+done
+</pre>
+</div>
+
+<p>
+The result is a bunch of GreenCard source files without these pesky CPP pre-processor directives.  Hugs can pre-process sources on the fly, but this makes evaluation orders of magnitude slower.  Pre-processing the sources once before using them repeatedly seems like a better choice.
+</p>
+
+<p>
+There is still a minor problem with GreenCard on Hugs.  The GreenCard sources import the module <code>NonStdTrace</code>, which depends on built-in prelude functions from nhc98.  Obviously, they are not available when running on Hugs (it has its own prelude implementation), so we need to provide an alternative using just the regular Hugs prelude.  The following snippet creates a file named <code>src/prelude/NonStd/NonStdTraceBootstrap.hs</code> with the necessary changes.
+</p>
+
+<div class="org-src-container">
+<pre class="src src-sh">cd ${NHCDIR}/src/prelude/NonStd/
+sed -e 's|NonStdTrace|NonStdTraceBootstrap|' \
+    -e 's|import PreludeBuiltin||' \
+    -e 's|_||g' NonStdTrace.hs &gt; NonStdTraceBootstrap.hs
+</pre>
+</div>
+
+<p>
+Then we change a single line in  <code>src/greencard/NHCBackend.hs</code> to make it import <code>NonStdTraceBootstrap</code> instead of <code>NonStdTrace</code>.
+</p>
+
+<div class="org-src-container">
+<pre class="src src-sh">cd ${NHCDIR}/src/greencard
+sed -i -e 's|NonStdTrace|NonStdTraceBootstrap|' NHCBackend.hs
+</pre>
+</div>
+
+<p>
+To run GreenCard we still need a driver script.  Let’s call this <code>hugs-greencard</code> and place it in <code>${NHCDIR}</code>:
+</p>
+
+<div class="org-src-container">
+<pre class="src src-sh">#!/bin/bash
+
+HUGSDIR="$(dirname $(readlink -f $(which runhugs)))/../"
+SEARCH_HUGS=$(printf "${NHCDIR}/src/%s/*:" compiler prelude libraries)
+
+runhugs -98 \
+        -P${HUGSDIR}/lib/hugs/packages/*:${NHCDIR}/include/*:${SEARCH_HUGS} \
+        ${NHCDIR}/src/greencard/GreenCard.lhs \
+        $@
+</pre>
+</div>
+
+<p>
+Make it executable:
+</p>
+
+<div class="org-src-container">
+<pre class="src src-sh">cd ${NHCDIR}
+chmod +x hugs-greencard
+</pre>
+</div>
+</div>
+</div>
+
+<div id="outline-container-org9519691" class="outline-2">
+<h2 id="org9519691">Building the prelude!</h2>
+<div class="outline-text-2" id="text-7">
+<p>
+Where were we?  Ah, the prelude.  As stated earlier, we need a working replacement for <code>nhc98comp</code>, which will be called by the driver script <code>script/nhc98</code> (created by the configure script).  Let’s call the replacement <code>hugs-nhc</code>, and again we’ll dump it in <code>${NHCDIR}</code>.  Here it is in all its glory:
+</p>
+
+<div class="org-src-container">
+<pre class="src src-sh">#!/bin/bash
+
+# Root directory of Hugs installation
+HUGSDIR="$(dirname $(readlink -f $(which runhugs)))/../"
+
+# TODO: "libraries" alone may be sufficient
+SEARCH_HUGS=$(printf "${NHCDIR}/src/%s/*:" compiler prelude libraries)
+
+# Filter everything from "+RTS" to "-RTS" from $@ because MainNhc98.hs
+# does not know what to do with these flags.
+ARGS=""
+SKIP="false"
+for arg in "$@"; do
+    if [[ $arg == "+RTS" ]]; then
+        SKIP="true"
+    elif [[ $arg == "-RTS" ]]; then
+        SKIP="false"
+    elif [[ $SKIP == "false" ]]; then
+        ARGS="${ARGS} $arg"
+    fi
+done
+
+runhugs -98 \
+        -P${HUGSDIR}/lib/hugs/packages/*:${SEARCH_HUGS} \
+        ${NHCDIR}/src/compiler98/MainNhc98.hs \
+        $ARGS
+</pre>
+</div>
+
+<p>
+All this does is run Hugs (<code>runhugs</code>) with language extensions (<code>-98</code>),  ensures that Hugs knows where to look for Hugs and nhc98 modules (<code>-P</code>), loads up the compiler’s <code>main</code> function, and then passes any arguments other than RTS flags (<code>$ARGS</code>) to it.
+</p>
+
+<p>
+Let’s also make this executable:
+</p>
+
+<div class="org-src-container">
+<pre class="src src-sh">cd ${NHCDIR}
+chmod +x hugs-nhc
+</pre>
+</div>
+
+<p>
+The compiler sources contain pre-processor directives, which need to be removed before running <code>hugs-nhc</code>.  It would be foolish to let Hugs pre-process the sources at runtime with <code>-F</code>.  In my tests it made <code>hugs-nhc</code> run slower by an order of magnitude.  Let’s pre-process the sources of the compiler and the libraries it depends on with <code>hugs-cpphs</code> (see above):
+</p>
+
+<div class="org-src-container">
+<pre class="src src-sh">cd ${NHCDIR}
+CPPPRE="${NHCDIR}/hugs-cpphs -D__HUGS__"
+
+FILES="src/compiler98/GcodeLowC.hs \
+ src/libraries/filepath/System/FilePath.hs \
+ src/libraries/filepath/System/FilePath/Posix.hs"
+
+for file in $FILES; do
+    cp $file $file.original &amp;&amp; $CPPPRE $file.original &gt; $file &amp;&amp; rm $file.original
+done
+</pre>
+</div>
+
+<p>
+The compiler’s driver script <code>script/nhc98</code> expects to find the executables of <code>hmake-PRAGMA</code>, <code>greencard-nhc98</code>, and <code>cpphs</code> in the architecture-specific lib directory (in my case that’s <code>${NHCDIR}/lib/x86_64-Linux/</code>).  They do not exist, obviously, but for two of them we already have scripts to run them on top of Hugs.  <code>hmake-PRAGMA</code> does not seem to be very important; replacing it with <code>cat</code> appears to be fine.  To pacify the compiler script it’s easiest to just replace a few definitions:
+</p>
+
+<div class="org-src-container">
+<pre class="src src-sh">cd ${NHCDIR}
+sed -i \
+  -e '0,/^GREENCARD=.*$/s||GREENCARD="$NHC98BINDIR/../hugs-greencard"|' \
+  -e '0,/^CPPHS=.*$/s||CPPHS="$NHC98BINDIR/../hugs-cpphs -D__NHC__"|' \
+  -e '0,/^PRAGMA=.*$/s||PRAGMA=cat|' \
+  script/nhc98
+</pre>
+</div>
+
+<p>
+Initially, this looked like it would be enough, but half-way through building the prelude Hugs choked when interpreting nhc98 to build a certain module.  After some experimentation it turned out that the <code>NHC.FFI</code> module in <code>src/prelude/FFI/CTypes.hs</code> is too big for Hugs.  Running nhc98 on that module causes Hugs to abort with an overflow in the control stack.  The fix here is to break up the module to make it easier for nhc98 to build it, which in turn prevents Hugs from doing too much work at once.
+</p>
+
+<p>
+Apply this patch:
+</p>
+
+<pre class="example">
+From 9eb2a2066eb9f93e60e447aab28479af6c8b9759 Mon Sep 17 00:00:00 2001
+From: Ricardo Wurmus &lt;rekado@elephly.net&gt;
+Date: Sat, 7 Jan 2017 22:31:41 +0100
+Subject: [PATCH] Split up CTypes
+
+This is necessary to avoid a control stack overflow in Hugs when
+building the FFI library with nhc98 running on Hugs.
+---
+ src/prelude/FFI/CStrings.hs     |  2 ++
+ src/prelude/FFI/CTypes.hs       | 14 --------------
+ src/prelude/FFI/CTypes1.hs      | 20 ++++++++++++++++++++
+ src/prelude/FFI/CTypes2.hs      | 22 ++++++++++++++++++++++
+ src/prelude/FFI/CTypesExtra.hs  |  2 ++
+ src/prelude/FFI/FFI.hs          |  2 ++
+ src/prelude/FFI/Makefile        |  8 ++++----
+ src/prelude/FFI/MarshalAlloc.hs |  2 ++
+ src/prelude/FFI/MarshalUtils.hs |  2 ++
+ 9 files changed, 56 insertions(+), 18 deletions(-)
+ create mode 100644 src/prelude/FFI/CTypes1.hs
+ create mode 100644 src/prelude/FFI/CTypes2.hs
+
+diff --git a/src/prelude/FFI/CStrings.hs b/src/prelude/FFI/CStrings.hs
+index 18fdfa9..f1373cf 100644
+--- a/src/prelude/FFI/CStrings.hs
++++ b/src/prelude/FFI/CStrings.hs
+@@ -23,6 +23,8 @@ module NHC.FFI (
+ import MarshalArray
+ import CTypes
++import CTypes1
++import CTypes2
+ import Ptr
+ import Word
+ import Char
+diff --git a/src/prelude/FFI/CTypes.hs b/src/prelude/FFI/CTypes.hs
+index 18e9d60..942e7a1 100644
+--- a/src/prelude/FFI/CTypes.hs
++++ b/src/prelude/FFI/CTypes.hs
+@@ -4,11 +4,6 @@ module NHC.FFI
+         -- Typeable, Storable, Bounded, Real, Integral, Bits
+         CChar(..),    CSChar(..),  CUChar(..)
+       , CShort(..),   CUShort(..), CInt(..),    CUInt(..)
+-      , CLong(..),    CULong(..),  CLLong(..),  CULLong(..)
+-
+-        -- Floating types, instances of: Eq, Ord, Num, Read, Show, Enum,
+-        -- Typeable, Storable, Real, Fractional, Floating, RealFrac, RealFloat
+-      , CFloat(..),   CDouble(..), CLDouble(..)
+       ) where
+ import NonStdUnsafeCoerce
+@@ -29,12 +24,3 @@ INTEGRAL_TYPE(CShort,Int16)
+ INTEGRAL_TYPE(CUShort,Word16)
+ INTEGRAL_TYPE(CInt,Int)
+ INTEGRAL_TYPE(CUInt,Word32)
+-INTEGRAL_TYPE(CLong,Int32)
+-INTEGRAL_TYPE(CULong,Word32)
+-INTEGRAL_TYPE(CLLong,Int64)
+-INTEGRAL_TYPE(CULLong,Word64)
+-
+-FLOATING_TYPE(CFloat,Float)
+-FLOATING_TYPE(CDouble,Double)
+--- HACK: Currently no long double in the FFI, so we simply re-use double
+-FLOATING_TYPE(CLDouble,Double)
+diff --git a/src/prelude/FFI/CTypes1.hs b/src/prelude/FFI/CTypes1.hs
+new file mode 100644
+index 0000000..81ba0f5
+--- /dev/null
++++ b/src/prelude/FFI/CTypes1.hs
+@@ -0,0 +1,20 @@
++{-# OPTIONS_COMPILE -cpp #-}
++module NHC.FFI
++      ( CLong(..),    CULong(..),  CLLong(..),  CULLong(..)
++      ) where
++
++import NonStdUnsafeCoerce
++import Int    ( Int8,  Int16,  Int32,  Int64  )
++import Word   ( Word8, Word16, Word32, Word64 )
++import Storable       ( Storable(..) )
++-- import Data.Bits( Bits(..) )
++-- import NHC.SizedTypes
++import Monad  ( liftM )
++import Ptr    ( castPtr )
++
++#include "CTypes.h"
++
++INTEGRAL_TYPE(CLong,Int32)
++INTEGRAL_TYPE(CULong,Word32)
++INTEGRAL_TYPE(CLLong,Int64)
++INTEGRAL_TYPE(CULLong,Word64)
+diff --git a/src/prelude/FFI/CTypes2.hs b/src/prelude/FFI/CTypes2.hs
+new file mode 100644
+index 0000000..7d66242
+--- /dev/null
++++ b/src/prelude/FFI/CTypes2.hs
+@@ -0,0 +1,22 @@
++{-# OPTIONS_COMPILE -cpp #-}
++module NHC.FFI
++      ( -- Floating types, instances of: Eq, Ord, Num, Read, Show, Enum,
++        -- Typeable, Storable, Real, Fractional, Floating, RealFrac, RealFloat
++      CFloat(..), CDouble(..), CLDouble(..)
++      ) where
++
++import NonStdUnsafeCoerce
++import Int    ( Int8,  Int16,  Int32,  Int64  )
++import Word   ( Word8, Word16, Word32, Word64 )
++import Storable       ( Storable(..) )
++-- import Data.Bits( Bits(..) )
++-- import NHC.SizedTypes
++import Monad  ( liftM )
++import Ptr    ( castPtr )
++
++#include "CTypes.h"
++
++FLOATING_TYPE(CFloat,Float)
++FLOATING_TYPE(CDouble,Double)
++-- HACK: Currently no long double in the FFI, so we simply re-use double
++FLOATING_TYPE(CLDouble,Double)
+diff --git a/src/prelude/FFI/CTypesExtra.hs b/src/prelude/FFI/CTypesExtra.hs
+index ba3f15b..7cbdcbb 100644
+--- a/src/prelude/FFI/CTypesExtra.hs
++++ b/src/prelude/FFI/CTypesExtra.hs
+@@ -20,6 +20,8 @@ import Storable      ( Storable(..) )
+ import Monad  ( liftM )
+ import Ptr    ( castPtr )
+ import CTypes
++import CTypes1
++import CTypes2
+ #include "CTypes.h"
+diff --git a/src/prelude/FFI/FFI.hs b/src/prelude/FFI/FFI.hs
+index 9d91e57..0c29394 100644
+--- a/src/prelude/FFI/FFI.hs
++++ b/src/prelude/FFI/FFI.hs
+@@ -217,6 +217,8 @@ import MarshalUtils        -- routines for basic marshalling
+ import MarshalError   -- routines for basic error-handling
+ import CTypes         -- newtypes for various C basic types
++import CTypes1
++import CTypes2
+ import CTypesExtra    -- types for various extra C types
+ import CStrings               -- C pointer to array of char
+ import CString                -- nhc98-only
+diff --git a/src/prelude/FFI/Makefile b/src/prelude/FFI/Makefile
+index 99065f8..e229672 100644
+--- a/src/prelude/FFI/Makefile
++++ b/src/prelude/FFI/Makefile
+@@ -18,7 +18,7 @@ EXTRA_C_FLAGS        =
+ SRCS = \
+       Addr.hs Ptr.hs FunPtr.hs Storable.hs \
+       ForeignObj.hs ForeignPtr.hs Int.hs Word.hs \
+-      CError.hs CTypes.hs CTypesExtra.hs CStrings.hs \
++      CError.hs CTypes.hs CTypes1.hs CTypes2.hs CTypesExtra.hs CStrings.hs \
+       MarshalAlloc.hs MarshalArray.hs MarshalError.hs MarshalUtils.hs \
+       StablePtr.hs
+@@ -38,12 +38,12 @@ Word.hs: Word.hs.cpp
+ # dependencies generated by hmake -Md: (and hacked by MW)
+ ${OBJDIR}/MarshalError.$O: ${OBJDIR}/Ptr.$O 
+ ${OBJDIR}/MarshalUtils.$O: ${OBJDIR}/Ptr.$O ${OBJDIR}/Storable.$O \
+-      ${OBJDIR}/MarshalAlloc.$O ${OBJDIR}/CTypes.$O ${OBJDIR}/CTypesExtra.$O 
++      ${OBJDIR}/MarshalAlloc.$O ${OBJDIR}/CTypes.$O ${OBJDIR}/CTypes1.$O ${OBJDIR}/CTypes2.$O ${OBJDIR}/CTypesExtra.$O
+ ${OBJDIR}/MarshalArray.$O: ${OBJDIR}/Ptr.$O ${OBJDIR}/Storable.$O \
+       ${OBJDIR}/MarshalAlloc.$O ${OBJDIR}/MarshalUtils.$O 
+-${OBJDIR}/CTypesExtra.$O: ${OBJDIR}/Int.$O ${OBJDIR}/Word.$O ${OBJDIR}/CTypes.$O
++${OBJDIR}/CTypesExtra.$O: ${OBJDIR}/Int.$O ${OBJDIR}/Word.$O ${OBJDIR}/CTypes.$O ${OBJDIR}/CTypes1.$O ${OBJDIR}/CTypes2.$O
+ ${OBJDIR}/CTypes.$O: ${OBJDIR}/Int.$O ${OBJDIR}/Word.$O ${OBJDIR}/Storable.$O \
+-      ${OBJDIR}/Ptr.$O 
++      ${OBJDIR}/Ptr.$O ${OBJDIR}/CTypes1.$O ${OBJDIR}/CTypes2.$O
+ ${OBJDIR}/CStrings.$O: ${OBJDIR}/MarshalArray.$O ${OBJDIR}/CTypes.$O \
+       ${OBJDIR}/Ptr.$O ${OBJDIR}/Word.$O
+ ${OBJDIR}/MarshalAlloc.$O: ${OBJDIR}/Ptr.$O ${OBJDIR}/Storable.$O \
+diff --git a/src/prelude/FFI/MarshalAlloc.hs b/src/prelude/FFI/MarshalAlloc.hs
+index 34ac7b3..5b43554 100644
+--- a/src/prelude/FFI/MarshalAlloc.hs
++++ b/src/prelude/FFI/MarshalAlloc.hs
+@@ -14,6 +14,8 @@ import ForeignPtr (FinalizerPtr(..))
+ import Storable
+ import CError
+ import CTypes
++import CTypes1
++import CTypes2
+ import CTypesExtra (CSize)
+ import NHC.DErrNo
+diff --git a/src/prelude/FFI/MarshalUtils.hs b/src/prelude/FFI/MarshalUtils.hs
+index 312719b..bd9d149 100644
+--- a/src/prelude/FFI/MarshalUtils.hs
++++ b/src/prelude/FFI/MarshalUtils.hs
+@@ -29,6 +29,8 @@ import Ptr
+ import Storable
+ import MarshalAlloc
+ import CTypes
++import CTypes1
++import CTypes2
+ import CTypesExtra
+ -- combined allocation and marshalling
+-- 
+2.11.0
+</pre>
+
+<p>
+After all this it’s time for a break.  Run the following commands for a long break:
+</p>
+
+<div class="org-src-container">
+<pre class="src src-sh">cd ${NHCDIR}/src/prelude
+time make NHC98COMP=$NHCDIR/hugs-nhc
+</pre>
+</div>
+
+<p>
+After the break—it took more than two hours on my laptop—you should see output like this:
+</p>
+
+<pre class="example">
+ranlib /path/to/nhc98-1.22/lib/x86_64-Linux/Prelude.a
+</pre>
+
+<p>
+Congratulations!  You now have a native nhc98 prelude library!
+</p>
+</div>
+</div>
+
+<div id="outline-container-orgace25de" class="outline-2">
+<h2 id="orgace25de">Building hmake</h2>
+<div class="outline-text-2" id="text-8">
+<p>
+The compiler and additional Haskell libraries all require a tool called “hmake” to automatically order dependencies, so we’ll try to build it next.  There’s just a small problem with one of the source files: <code>src/hmake/FileName.hs</code> contains the name “Niklas Röjemo” and the compiler really does not like the umlaut.  With apologies to Niklas we change the copyright line to appease the compiler.
+</p>
+
+<div class="org-src-container">
+<pre class="src src-sh">cd $NHCDIR/src/hmake
+mv FileName.hs{,.broken}
+tr '\366' 'o' &lt; FileName.hs.broken &gt; FileName.hs
+rm FileName.hs.broken
+NHC98COMP=$NHCDIR/hugs-nhc make HC=$NHCDIR/script/nhc98
+</pre>
+</div>
+</div>
+</div>
+
+<div id="outline-container-org83aa24b" class="outline-2">
+<h2 id="org83aa24b">To be continued</h2>
+<div class="outline-text-2" id="text-9">
+<p>
+Unfortunately, the hmake tools are not working.  All of the tools (e.g. <code>MkConfig</code>) fail with an early segmentation fault.  There must be an error in the runtime, likely in <code>src/runtime/Kernel/mutator.c</code> where bytecode for heap and stack operations is interpreted.  One thing that looks like a problem is statements like this:
+</p>
+
+<pre class="example">
+*--sp = (NodePtr) constptr[-HEAPOFFSET(ip[0])];
+</pre>
+
+<p>
+<code>constptr</code> is <code>NULL</code>, so this seems to be just pointer arithmetic expressed in array notation.  These errors can be fixed by rewriting the statement to use explicit pointer arithmetic:
+</p>
+
+<pre class="example">
+*--sp = (NodePtr) (constptr + (-HEAPOFFSET(ip[0])));
+</pre>
+
+<p>
+Unfortunately, this doesn’t seem to be enough as there is another segfault in the handling of the <code>EvalTOS</code> label.  <code>IND_REMOVE</code> is applied to the contents of the stack pointer, which turns out to be <code>0x10</code>, which just doesn’t seem right.  <code>IND_REMOVE</code> removes indirection by following pointer addresses until the value stored at the given address does not look like an address.  This fails because <code>0x10</code> does look like an address—it’s just invalid.  I have enabled a bunch of tracing and debugging features, but I don’t fully understand how the nhc98 runtime is <i>supposed</i> to work.
+</p>
+
+<p>
+Judging from mails on the nhc-bugs and nhc-users lists I see that I’m not the only one experiencing segfaults.  <a href="https://mail.haskell.org/pipermail/nhc-bugs/2005-October/000529.html">This email</a> suggests that segfaults are “associated with changes in the way gcc lays out static arrays of bytecodes, e.g. by putting extra padding space between arrays that are supposed to be adjacent.”  I may have to try different compiler flags or an older version of GCC; I only tried with GCC 4.9.4 but the <a href="http://sources.debian.net/src/nhc98/1.16-15/debian/rules/">Debian package for nhc98</a> used version 2.95 or 3.3.
+</p>
+
+<p>
+For completeness sake here’s the trace of the failing execution of MkProg:
+</p>
+
+<pre class="example">
+(gdb) run
+Starting program: /path/to/nhc98-1.22/lib/x86_64-Linux/MkProg 
+ZAP_ARG_I1             hp=0x80c5010 sp=0x8136a10 fp=0x8136a10 ip=0x8085140
+NEEDHEAP_I32   hp=0x80c5010 sp=0x8136a10 fp=0x8136a10 ip=0x8085141
+HEAP_CVAL_N1   hp=0x80c5010 sp=0x8136a10 fp=0x8136a10 ip=0x8085142
+HEAP_CVAL_I3   hp=0x80c5014 sp=0x8136a10 fp=0x8136a10 ip=0x8085144
+HEAP_OFF_N1            hp=0x80c5018 sp=0x8136a10 fp=0x8136a10 ip=0x8085145
+PUSH_HEAP              hp=0x80c501c sp=0x8136a10 fp=0x8136a10 ip=0x8085147
+HEAP_CVAL_I4   hp=0x80c501c sp=0x8136a0c fp=0x8136a10 ip=0x8085148
+HEAP_CVAL_I5   hp=0x80c5020 sp=0x8136a0c fp=0x8136a10 ip=0x8085149
+HEAP_OFF_N1            hp=0x80c5024 sp=0x8136a0c fp=0x8136a10 ip=0x808514a
+PUSH_CVAL_P1   hp=0x80c5028 sp=0x8136a0c fp=0x8136a10 ip=0x808514c
+PUSH_I1                    hp=0x80c5028 sp=0x8136a08 fp=0x8136a10 ip=0x808514e
+ZAP_STACK_P1   hp=0x80c5028 sp=0x8136a04 fp=0x8136a10 ip=0x808514f
+EVAL               hp=0x80c5028 sp=0x8136a04 fp=0x8136a10 ip=0x8085151
+eval: evalToS
+
+Program received signal SIGSEGV, Segmentation fault.
+0x0804ac27 in run (toplevel=0x80c5008) at mutator.c:425
+425            IND_REMOVE(nodeptr);
+</pre>
+
+<p>
+<code>ip</code> is the instruction pointer, which points at the current element in the bytecode stream.  <code>fp</code> is probably the frame pointer, <code>sp</code> the stack pointer, and <code>hp</code> the heap pointer.  The <a href="https://www.haskell.org/nhc98/implementation-notes/index.html">implementation notes for nhc98</a> will probably be helpful in solving this problem.
+</p>
+
+<p>
+Anyway, that’s where I’m at so far.   If you are interested in these kinds of problems or other bootstrapping projects, consider joining the efforts of the <a href="http://bootstrappable.org">Bootstrappable Builds project</a>!
+</p>
+</div>
+</div>
+<div id="footnotes">
+<h2 class="footnotes">Footnotes: </h2>
+<div id="text-footnotes">
+
+<div class="footdef"><sup><a id="fn.1" class="footnum" href="#fnr.1">1</a></sup> <div class="footpara">It is unclear when exactly the release was made, but any time between 1991 and 1993 seems likely.</div></div>
+
+
+</div>
+</div></div>
+</div>