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
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401 | (*
An implementation of a FALSE variant by OliveIsAWord in MiniML:
https://github.com/pithlessly/miniml
To run MiniML, please ask me or GnuRadioShows for an unvetted Scheme file
with which to execute this program and/or bootstrap the compiler (or just
adapt this code to the ML of your choice :3).
This implementation is, by some metrics, performant. On my computer with an
AMD Ryzen 7 5800X 8-Core Processor, the following program takes ~18 seconds
to execute:
```false
[$ 1 > [1- $ f;! \ 1- f;! +]?]f:
33 f;! . {compute & print 33th fibonacci number}
```
This program requires the files "olive.false" and "olive.stdin" in the cwd.
*)
let source_code_filepath = "olive.false"
let stdin_filepath = "olive.stdin"
let false_true = 0 - 1
let false_false = 0
let bit_width = 32
let index_of_var c: int = int_of_char c - int_of_char 'a'
let var_of_index i: char = char_of_int (i + int_of_char 'a')
let false_parse_error msg =
prerr_endline ("FALSE parse error: " ^ msg);
exit 1
let false_eval_error msg =
prerr_endline ("FALSE eval error: " ^ msg);
exit 1
let internal_panic msg =
prerr_endline ("internal error: " ^ msg);
prerr_endline "ya girlie olive screwed up :pleading_face:";
exit 1
let _todo () = internal_panic "todo"
let xor a b = match (a, b) with
| (true, true) | (false, false) -> false
| _ -> true
let (--) i j =
let rec aux n acc =
if n < i then acc else aux (n-1) (n :: acc)
in aux (j - 1) []
let rec list_find elem list = match list with
| [] -> false
| x :: xs -> if x = elem then true else list_find elem xs
let rec list_get list i = match list with
| [] -> false_eval_error "stack_underflow"
| x :: xs -> if i = 0 then x else list_get xs (i - 1)
let list_take list n =
let rec aux list n acc = if n = 0 then (acc, list) else match list with
| [] -> false_eval_error "stack_underflow"
| x :: xs -> aux xs (n - 1) (x :: acc)
in aux list n []
let get_or str i =
if i < String.length str then Some (String.get str i) else None
let option_map_or f default x = match x with
| Some x -> f x
| None -> default
let option_unwrap_or_else f x = match x with
| Some x -> x
| None -> f ()
let rec do_n n f =
if n > 0 then f (); do_n (n - 1) f else ()
let rec while condition body =
if condition () then body (); while condition body else ()
let sign x = x < 0
let flip_sign_if b x = if b then 0 - x else x
let abs x = flip_sign_if (sign x) x
let mul x y =
let product = ref 0 in
let (a, b) = if abs x < abs y then (x, y) else (y, x) in
do_n (abs a) (fun () -> product := (b + deref product));
let mag = deref product in
flip_sign_if (sign a) mag
let pow base power =
let value = ref 1 in
do_n power (fun () -> value := (mul base (deref value)));
deref value
let div divisor dividend =
if divisor = 0 then
false_eval_error (
"division by zero: " ^
string_of_int dividend ^
" / " ^
string_of_int divisor)
else ();
let x = ref (abs dividend) in
let y = abs divisor in
let mag = ref 0 in
while (fun () -> deref x >= y) (fun () ->
x := (deref x - y);
mag := (deref mag + 1)
);
flip_sign_if (xor (sign dividend) (sign divisor)) (deref mag)
let int_cap = pow 2 bit_width
let signed_cap = pow 2 (bit_width - 1)
let bits_of_int i: bool list =
let i = if i >= 0 then i else int_cap - i in
snd (List.fold_right (fun bit (x, acc) ->
let mask = pow 2 bit in
let new_bit = x >= mask in
let new_x = if new_bit then x - mask else x in
(new_x, new_bit :: acc)
) (0 -- bit_width) (i, []))
let int_of_bits bs: int =
List.fold_right (fun bit n ->
let bit = if bit then 1 else 0 in
n + n + bit
) bs 0
let string_of_bits bs: string =
String.concat "" (List.map (fun b -> if b then "1" else "0") bs)
let wrap_int i: int =
let rec wrap_neg i = if i >= 0 then i else wrap_neg (i + int_cap) in
let rec wrap_pos i = if i < signed_cap then i else wrap_pos (i - int_cap) in
wrap_pos (wrap_neg i)
let string_of_char = String.make 1
let char_list_of_string str =
let indices: int list = 0 -- String.length str in
(List.map) (String.get str) indices
type token =
| PushInt of int
| PushChar of int
| PrintString of string
| PushQuote of token list
| PushVar of int
| Instruction of char
let rec string_of_token_partial token int_prev = match token with
| PushInt i -> (if int_prev then " " else "") ^ string_of_int i
| PushChar i -> "'" ^ string_of_char (char_of_int i)
| PrintString s -> "\"" ^ s ^ "\""
| PushQuote tokens -> string_of_quote tokens
| PushVar v -> string_of_char (var_of_index v)
| Instruction c -> string_of_char c
and string_of_token token = string_of_token_partial token false
and string_of_tokens tokens =
let rec aux acc int_prev tokens = match tokens with
| [] -> acc
| x :: xs ->
let to_str = string_of_token_partial x int_prev in
let is_int = match x with | PushInt _ -> true | _ -> false
in aux (to_str :: acc) is_int xs
in String.concat "" (List.rev (aux [] false tokens))
and string_of_quote tokens = "[" ^ string_of_tokens tokens ^ "]"
type value =
| Int of int
| Ref of int
| Quote of token list
let string_of_value value = match value with
| Int i -> string_of_int i
| Ref v -> string_of_char (var_of_index v)
| Quote q -> string_of_quote q
let bad_type expected value = false_eval_error (
"expected type " ^
expected ^
", found " ^
string_of_value value)
let read_to_string filepath =
let f = In_channel.open_text filepath in
let text = In_channel.input_all f in
In_channel.close f;
text
let src = read_to_string source_code_filepath
let stdin = ref (char_list_of_string (read_to_string stdin_filepath))
let stdout = ref []
let stack = ref []
let pop (* :flushed: *) () = match deref stack with
| [] -> false_eval_error "stack underflow"
| x :: xs -> stack := xs; x
let pop_int () = match pop () with
| Int a -> a
| x -> bad_type "int" x
let pop_ref () = match pop () with
| Ref a -> a
| x -> bad_type "variable reference" x
let pop_quote () = match pop () with
| Quote a -> a
| x -> bad_type "quote" x
let pop_bool () = pop_int () <> false_false
let push x = stack := (x :: deref stack)
let stack_debug () =
let reprs = List.map string_of_value (deref stack) in
let ordered = List.rev reprs in
let pretty = "(" ^ String.concat ", " ordered ^ ")" in
print_endline pretty
let stack_index i =
if i < 0 then
false_eval_error ("executed `O` with negative index" ^ string_of_int i)
else ();
list_get (deref stack) i
let stack_manip n map =
let (top, rest): (value list * value list) = list_take (deref stack) n in
let new_top = List.fold_left (fun acc i ->
let index = n - 1 - (int_of_string (String.sub map i 1)) in
let elem = list_get top index in
elem :: acc
) [] (0 -- String.length map) in
stack := (new_top @ rest)
let int1 f =
let x = pop_int () in
push (Int (wrap_int (f x)))
let int2 f =
let rhs = pop_int () in
let lhs = pop_int () in
push (Int (wrap_int (f lhs rhs)))
let bitwise2 f =
let rhs = bits_of_int (pop_int ()) in
let lhs = bits_of_int (pop_int ()) in
push (Int (int_of_bits (List.map2 f lhs rhs)))
let push_digits str = stack := (Int (int_of_string str) :: deref stack)
let false_print str = stdout := (str :: deref stdout)
let is_digit c = Char.('0' <= c && c <= '9')
let is_var c = Char.('a' <= c && c <= 'z')
let is_instruction c =
let instructions = char_list_of_string (";:$%\\@O+-*/_&|~=>!?#^,.B" ^ "Q")
in list_find c instructions
let variable_map: value option ref list = List.map (fun _ -> ref None) (0 -- 26)
let get_var i = match deref (list_get variable_map i) with
| Some value -> value
| None -> false_eval_error (
"accessed uninitialized variable " ^
string_of_char (var_of_index i))
let set_var var v =
let target = var in
let i = ref (0 - 1) in
List.iter
(fun var_ref ->
i := (deref i) + 1;
if deref i = target then var_ref := Some v else ())
variable_map
let lex str: token list =
let rec lex_partial str: (token list) * (string option) =
let rec aux acc str =
let skip i = String.sub str i (String.length str - i) in
if String.length str = 0 then
(acc, None)
else match String.get str 0 with
| ' ' | '\n' | '\r' -> aux acc (skip 1)
| '{' ->
let i = ref 1 in
while (fun () -> option_map_or
(fun x -> x <> '}')
false
(get_or str (deref i)))
(fun () -> i := (deref i + 1));
let i = deref i in
if i >= String.length str then
false_parse_error "unclosed `{`"
else ();
aux acc (skip (i + 1))
| '}' -> false_parse_error "trailing `}`"
| '\'' -> (match get_or str 1 with
| None -> false_parse_error "Expected character after `'`"
| Some c -> aux (PushChar (int_of_char c) :: acc) (skip 2))
| '"' ->
let i = ref 1 in
while (fun () -> option_map_or
(fun x -> x <> '"')
false
(get_or str (deref i)))
(fun () -> i := (deref i + 1));
let i = deref i in
if i >= String.length str then
false_parse_error "unclosed `\"`"
else ();
let str_span = String.sub str 1 (i - 1) in
aux ((PrintString str_span) :: acc) (skip (i + 1))
| '[' ->
let (quote_tokens, rest) = lex_partial (skip 1) in
let rest = option_unwrap_or_else
(fun () -> false_parse_error "unclosed `[`")
rest
in aux ((PushQuote quote_tokens) :: acc) rest
| ']' -> (acc, Some (skip 1))
| '`' -> false_parse_error "the ` instruction is not supported"
| c ->
if int_of_char c = 9 then
(* hiii christine add \t support please :pleading_face: *)
aux acc (skip 1)
else if is_digit c then
let i = ref 1 in
while (fun () -> option_map_or is_digit false (get_or str (deref i)))
(fun () -> i := (deref i + 1));
let i = deref i in
let digits = String.sub str 0 i in
let int_token = PushInt (int_of_string digits) in
aux (int_token :: acc) (skip i)
else if is_var c then
let var_token = PushVar (index_of_var c) in
aux (var_token :: acc) (skip 1)
else if is_instruction c then
aux (Instruction c :: acc) (skip 1)
else false_parse_error (
"unexpected character `" ^
(string_of_char c) ^
"`")
in let (tokens, rest) = aux [] str in (List.rev tokens, rest)
in fst (lex_partial str)
let rec eval_op op = match op with
| PushInt i | PushChar i -> push (Int (wrap_int i))
| PrintString s -> false_print s
| PushQuote quote -> push (Quote quote)
| PushVar v -> push (Ref v)
| Instruction c -> match c with
| 'Q' -> stack_debug ()
| ';' -> push (get_var (pop_ref ()))
| ':' ->
let var = pop_ref () in
let value = pop () in
set_var var value
| '$' -> stack_manip 1 "00"
| '%' -> stack_manip 1 ""
| '\\' -> stack_manip 2 "01"
| '@' -> stack_manip 3 "102"
| 'O' ->
let i = pop_int () in
push (stack_index i)
| '+' -> int2 (+)
| '-' -> int2 (-)
| '*' -> int2 mul
| '/' -> int2 div
| '_' -> int1 (fun x -> 0 - x)
| '&' -> bitwise2 (&&)
| '|' -> bitwise2 (||)
| '~' -> int1 (fun x -> (0 - 1) - x)
| '=' -> int2 (fun x y -> if x = y then false_true else false_false)
| '>' -> int2 (fun x y -> if x > y then false_true else false_false)
| '!' -> eval (pop_quote ())
| '?' ->
let quote = pop_quote () in
if pop_bool () then eval quote else ()
| '#' ->
let body = pop_quote () in
let condition = pop_quote () in
while (fun () -> eval condition; pop_bool ())
(fun () -> eval body)
| '^' ->
let code_point = match deref stdin with
| [] -> 0 - 1
| x :: xs -> stdin := xs; int_of_char x
in push (Int code_point)
| ',' -> false_print (String.make 1 (char_of_int (pop_int ())))
| '.' -> false_print (string_of_int (pop_int ()))
| 'B' -> ()
| c -> internal_panic ("bad instruction `" ^ string_of_char c ^ "`")
and eval code = List.iter eval_op code
let () =
let code = lex src in
eval code;
print_endline (String.concat "" (List.rev (deref stdout)));
()
|
post a comment