1
Implementing GHC External Core: an experiment with the BNF Converter
2
--------------------------------------------------------------------
7
The starting point of the work are the files
8
ExternalCore.lhs and ParserExternalCore.y contained in the GHC External Core
9
source package. The goal is to get an abstract syntax as close as possible
10
to the original. The hope is that External Core is well-behaved, since
11
it has few concerns for "user-friendly" syntax.
14
THE PHASES OF THE WORK
16
Start 11.10, by converting the abstract syntax file to BNF grammar
17
with nonterminals only. Finished 11.24. Then go through the Happy
18
file to insert terminals properly. At 12.00 the resulting grammar file,
19
Core.cf, gets compiled in bnfc, but gets some conflicts.
21
Aften an hour's lunch break, find the obvious reduce/reduce
22
conflict between Var and DCon in Exp. Change Var to unqualified
23
identifiers. Start testing with a hello world -program Hello.hcr,
26
ghc -fext-core AbsCore.hs Hello.hs
28
This gets parsed, but some other files don't. The reason turns out
29
to be that GHC 5.02.2 generates qualified identifiers where the
30
Core syntax expects qualified ones. Changing this does not quite suffice,
31
however, since GHC also generates qualified ones; therefore,
32
divide the constructor for Vdef into two, VdefQ and VdefU.
34
At this point, test files get so big (3860 in AbsCore.hcr) that Hugs does
35
manage them, so create a compilable test file TopCore, compiled with
37
ghc --make -i/home/aarne/BNFC TopCore.hs -o TopCore
39
Now manage to parse AbsCoreAt at 14.02, after 1 hour's work on grammar writing,
40
1 hour on debugging. One reduce/reduce conflict remains. Come back to it
41
later and locate it in the %forall rule: I had just missed the dot (".") in
42
the Happy file! The ParCore.info file was useful in locating it, in 5 minutes.
44
Trying other examples, there is still a problem with string and character
45
literals: the standard ones of BNFC do not handle everything that appears in Core.
46
First experiment with changes in the generated file LexCore.x. Then make it
47
the proper way, by defining the token types Str and Chr in Core.cf.
48
At 15.18 manage to parse all my examples with the BNFC-generated parser, the
49
biggest one being the parser of Core itself:
52
64907 143661 1797533 ParCore.hcr
54
15.18 made the Str and Chr token definitions in Core.cf. Now manage to
55
parse all examples completely with BNFC-generated parser.
57
This document was being written as book-keeping while programming.
58
Some clean-up was done afterwards, and also some comments were added
59
to Core.cf. Next morning, the document was rewritten to the current shape.
64
The work took 1h grammar writing, 1h debugging, 30m fine-tuning.
66
The resulting grammar parses all tested examples, but the abstract
67
syntax is slightly different, mostly due to BNFC not having polymorphic
68
pair and Maybe types. In addition, the original uses some foldr's
69
as semantic actions, where we just have to retain the lists.
71
The External Core language is reasonably well-behaved, and the source
72
files gave good support to the grammar development.
74
The pretty-printer might be fine-tuned. In particular, the qualifier
75
dots (but not the %forall dots!) should not be separated by spaces.
77
It seems straightforward to translate back and forth between the
78
original syntax and our AbsCore.hs. However, if the External Core
79
language had been defined in the BNF converter language from the
80
beginning, this would not be necessary. The generated abstract syntax
81
is not very much worse then the hand-written one. There would be
82
a guaranteed match between the abstract syntax, the parser, the pretty
83
printer, and the language document - and only a fraction of the current
84
amount of code and text would have had to be written:
90
89 243 1324 ExternalCore.lhs
91
240 1042 5168 ParserExternalCore.y
92
168 906 4667 PprExternalCore.lhs
95
where the lexer source and the language document are still missing.
100
The BNF Converter: http://www.cs.chalmers.se/~markus/BNFC/
102
GHC External Core: http://www.haskell.org/ghc/docs/papers/core.ps.gz