-
Notifications
You must be signed in to change notification settings - Fork 16
/
Copy pathmiranda.lhs
197 lines (164 loc) · 6.35 KB
/
miranda.lhs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
= Miranda =
Haskell nearly never existed.
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/history.pdf[They
originally planned to build on David Turner's Miranda language] rather than
invent a new one.
Released in the 1980s, Miranda compiles a Haskell-like language to a certain
set of combinators which a C program interprets. This is precisely what we do!
In January 2020, http://miranda.org.uk/downloads[Miranda's source] was
released. Its approach to compilation has remained unchanged through the years,
yielding an excellent opportunity for an exhibition match.
▶ Download the files from this contest: link:cmpmira.tar.gz[cmpmira.tar.gz].
== These go to eleven ==
We bump up a Miranda example that solves the
https://en.wikipedia.org/wiki/Eight_queens_puzzle[eight queens puzzle] to 11
queens:
\begin{code}
include::q11.m[]
\end{code}
On my laptop, to build `mira`, I had to first edit the `Makefile` and change
`quotehostinfo` to `./quotehostinfo`. Afterwards:
------------------------------------------------------------------------
$ mira -make q11.m
$ time mira -exec q11.m > /dev/null
real 0m8.132s
user 0m8.111s
sys 0m0.020s
------------------------------------------------------------------------
We translate it for our `assembly` compiler. We need much more code as we lack
a standard library:
[#q11.toggleshow]
---------
include::q11.hs[]
---------
On my laptop:
------------------------------------------------------------------------
$ (cat rts.c;./assembly < q11.hs) > q11.c
$ cc -O2 q11.c -o q11
$ time ./q11 > /dev/null
real 0m6.783s
user 0m6.734s
sys 0m0.048s
------------------------------------------------------------------------
I can't help feeling proud. Miranda uses
https://arxiv.org/pdf/1510.03794v1.pdf[Turner's bracket abstraction algorithm],
which pushes Schönfinkel's classic approach about as far as it can go. It has a
large set of combinators, including dedicated combinators for map and fold.
And surely its runtime system must be expertly tuned.
Our program, on the other hand, compiles to a handful of basic combinators,
uses the Scott encoding for all data types except unsigned ints, and the source
to its hastily designed virtual machine prizes brevity over efficiency: it
began life as link:ioccc.html[an IOCCC entry] after all.
But really its performance has little to do with my prowess. The credit goes to
Oleg Kiselyov's bracket abstraction algorithm (with minor tweaks from a few
syntactic rewrites).
[#q11-combinators.toggleshow]
------------------------------------------------------------------------
% = Q %;
/ = Q /;
* = Q *;
- = Q -;
+ = Q +;
unsafePerformIO = C (T ?) K;
exitSuccess = .;
fail# = unsafePerformIO .;
ioPure = B C T;
ioBind = C;
succ = T (1 +);
ord = I;
chr = I;
() = K;
if = I;
intLE = Q L;
intEq = Q =;
shows = T I;
>>= = T (K I);
return = T K;
<*> = T (K I);
pure = T K;
fmap = T I;
<= = T I;
== = T I;
putChar = T FFI_0;
, = B C T;
|, = I;
: = B (B K) (B C T);
[] = K;
|[]|: = I;
False = K I;
True = K;
|True|False = I;
{Eq Int} = T intEq;
{Ord Int} = T intLE;
>> = B (R K) (B (B B) (>>=));
$ = I;
. = B;
id = I;
flip = C;
abs = S (S (R 2147483647 ((<=) {Ord Int})) I) ((-) 0);
not = R K (T False);
|| = T K;
&& = R False;
flst = I;
foldr = B (S (B C T)) (S (B B (B C (B B))) foldr);
++ = C (foldr (:));
concat = foldr (++) K;
map = C (B foldr (B (:))) K;
concatMap = B (B concat) map;
and = foldr (&&) K;
undefined = undefined;
!! = R (S (B C (B (B B) (R 0 ((==) {Eq Int})))) (B (C (!!)) (R 1 (-)))) (B B (T undefined));
checks = S (B S (B (B S) (B (B (B (||))) (R (!!) (B B (B B ((==) {Eq Int}))))))) (B (R (R 1 (+))) (B (B S) (B (B (B ((==) {Eq Int}))) (B (B (B abs)) (R (!!) (B B (B B (-))))))));
index = Y (B (B (S (T K))) (B (B (B K)) (B (B (B K)) (B (B (C (T fail#))) (B (B K) (B (S (B B (:))) (R (R 1 (+)) B))))))) 0;
safe = B (B and) (R index (B S (B (B map) (B (B (B not)) checks))));
range = B (R K) (S (B S ((<=) {Ord Int})) (S (B B (:)) (B range (R 1 (+)))));
queens = S (R ((:) K K) ((==) {Eq Int} 0)) (B (concatMap (R (range 1 11) (B concatMap (S (B S (B (B concatMap) (B (B K) (B (R K) (B (B (:)) (C (:))))))) (B (R K) (B (R ((:) K K)) (C safe))))))) (B queens (R 1 (-))));
{Applicative IO} = C (T ioPure) (R (R (B ioPure) (B B C)) (B B C));
{Monad IO} = C (T ioPure) C;
{Functor IO} = T (B ((<*>) {Applicative IO}) ioPure);
mapM_ = B (C (B C (B (B foldr) (B B (>>))))) (R K pure);
putStr = mapM_ {Applicative IO} {Monad IO} putChar;
showInt' = S (R I ((==) {Eq Int} 0)) (S (B B (B showInt' (R 10 (/)))) (B (:) (B ((+) 48) (R 10 (%)))));
{Shows Int} = T (S (R ((:) 48) ((==) {Eq Int} 0)) showInt');
intersperse = B (C (T K)) (B (C (B B (:))) (R K (B foldr (B (B (++)) (R (R K (:)) (B B (:)))))));
{Shows ([] a)} = B T (B (B (B ((:) 91))) (B (R ((:) 93)) (B (B B) (B (B (foldr B I)) (B (B (intersperse ((:) 44))) (B map shows))))));
main = putStr (shows ({Shows ([] a)} ({Shows ([] a)} {Shows Int})) (queens 11) "");
------------------------------------------------------------------------
== A second opinion ==
The difference is even more pronounced for another example that computes 'e' to
4096 decimal places:
------------------------------------------------------------------------
$ time ./e4096 > /dev/null
real 0m6.532s
user 0m6.471s
sys 0m0.060s
$ time mira -exec e4096.m > /dev/null
real 0m14.350s
user 0m14.321s
sys 0m0.013s
------------------------------------------------------------------------
The Miranda original:
\begin{code}
include::e4096.m[]
\end{code}
Our version:
[#e4096.toggleshow]
---------
include::e4096.hs[]
---------
== A rematch? ==
See
https://codesync.global/media/open-sourcing-miranda-david-turner-code-mesh-v-2020-codemeshv2020/[David Turner's talk, _Open Sourcing Miranda_], especially for
tips on updating C code written 30 years ago! I was pleased to hear that:
* Miranda's VM has an ATOMLIMIT that is like our scheme of addressses starting
at 128, with lower values representing combinators. (Though unlike Miranda,
we box our characters.)
* Turner talks about rewriting Miranda's fragile conservative garbage
collector. We began with a robust copying garbage collector.
* Turner also talks about rewriting much of the C in Miranda. Been there,
done that: we wrote everything but the VM in Haskell from the start.
But most of all, I'm pleased Miranda is alive again, and look forward to
rematches with future releases.
+++++++++
include::toggleshow.js[]
+++++++++