bernsteinbear.com
this repo has no description
1# /// script
2# requires-python = ">=3.12"
3# dependencies = [
4# "unittest-parallel",
5# ]
6# ///
7import tempfile
8import unittest
9from run import run
10
11WORD_SIZE = 8
12FIXNUM_SHIFT = 2
13FIXNUM_MASK = 0b11
14FIXNUM_TAG = 0b00
15CHAR_TAG = 0b00001111
16CHAR_SHIFT = 8
17BOOL_TAG = 0b0011111
18BOOL_SHIFT = 7
19BOOL_MASK = 0b1111111
20BOOL_BIT = 1 << BOOL_SHIFT
21EMPTY_LIST = 0b00101111
22CONS_TAG = 0b001
23CLOSURE_TAG = 0b110
24HEAP_ALIGNMENT = 2 * WORD_SIZE
25
26def immediate_rep(val):
27 match val:
28 case bool(_):
29 return (val << BOOL_SHIFT) | BOOL_TAG
30 case int(_):
31 return val << FIXNUM_SHIFT
32 case Char():
33 return (val.byte << CHAR_SHIFT) | CHAR_TAG
34 case _:
35 raise NotImplementedError(val)
36
37class Char:
38 def __init__(self, c):
39 b = c.encode("utf-8")
40 assert len(b) == 1
41 self.byte = b[0]
42
43 def __eq__(self, other):
44 return isinstance(other, Char) and self.byte == other.byte
45
46 def __repr__(self):
47 return f"Char({self.byte})"
48
49NEXT_LABEL = -1
50
51CLOSURE_BASE = "rdi"
52HEAP_BASE = "rsi"
53
54def indirect(reg, offset):
55 if offset >= 0:
56 return f"[{reg}+{offset}]"
57 else:
58 return f"[{reg}{offset}]"
59
60def stack_at(si):
61 assert si < 0
62 return indirect("rsp", si)
63
64BUILTINS = frozenset({
65 "add1", "integer->char",
66 "char->integer", "null?", "zero?",
67 "not", "integer?", "boolean?", "+",
68 "cons", "car", "cdr",
69})
70
71def compile_expr(expr, code, si, env):
72 emit = code.append
73 def comment(msg):
74 emit(f"# {msg}")
75 def heap_at(offset):
76 return indirect(HEAP_BASE, offset)
77 def unique_label():
78 global NEXT_LABEL
79 NEXT_LABEL += 1
80 return f"L{NEXT_LABEL}"
81 def align(size):
82 if size % HEAP_ALIGNMENT == 0:
83 return size
84 return size + WORD_SIZE
85 match expr:
86 case int(_) | Char():
87 emit(f"mov rax, {immediate_rep(expr)}")
88 case str(_):
89 emit(f"mov rax, {env[expr]}")
90 case []:
91 emit(f"mov rax, {EMPTY_LIST}")
92 case ["add1", e]:
93 compile_expr(e, code, si, env)
94 emit(f"add rax, {immediate_rep(1)}")
95 case ["integer->char", e]:
96 compile_expr(e, code, si, env)
97 emit(f"shl rax, {CHAR_SHIFT-FIXNUM_SHIFT}")
98 emit(f"or rax, {CHAR_TAG}")
99 case ["char->integer", e]:
100 compile_expr(e, code, si, env)
101 emit(f"shr rax, {CHAR_SHIFT-FIXNUM_SHIFT}")
102 case ["null?", e]:
103 compile_expr(e, code, si, env)
104 emit(f"cmp rax, {EMPTY_LIST}")
105 emit(f"mov rax, 0")
106 emit(f"sete al")
107 emit(f"shl rax, {BOOL_SHIFT}")
108 emit(f"or rax, {BOOL_TAG}")
109 case ["zero?", e]:
110 compile_expr(e, code, si, env)
111 emit(f"test rax, rax")
112 emit(f"mov rax, 0")
113 emit(f"sete al")
114 emit(f"shl rax, {BOOL_SHIFT}")
115 emit(f"or rax, {BOOL_TAG}")
116 case ["not", e]:
117 compile_expr(e, code, si, env)
118 emit(f"xor rax, {BOOL_BIT}")
119 case ["integer?", e]:
120 compile_expr(e, code, si, env)
121 emit(f"and al, {FIXNUM_MASK}")
122 emit(f"test al, al")
123 emit(f"mov rax, 0")
124 emit(f"sete al")
125 emit(f"shl rax, {BOOL_SHIFT}")
126 emit(f"or rax, {BOOL_TAG}")
127 case ["boolean?", e]:
128 compile_expr(e, code, si, env)
129 emit(f"and al, {BOOL_MASK}")
130 emit(f"cmp al, {BOOL_TAG}")
131 emit(f"mov rax, 0")
132 emit(f"sete al")
133 emit(f"shl rax, {BOOL_SHIFT}")
134 emit(f"or rax, {BOOL_TAG}")
135 case ["+", e0, e1]:
136 compile_expr(e0, code, si, env)
137 emit(f"mov {stack_at(si)}, rax")
138 compile_expr(e1, code, si-WORD_SIZE, env)
139 emit(f"add rax, {stack_at(si)}")
140 case ["let", bindings, body]:
141 new_env = env.copy()
142 new_si = si
143 for (name, val) in bindings:
144 comment(f"Code for {name}")
145 compile_expr(val, code, new_si, env)
146 comment(f"Store {name} on the stack")
147 emit(f"mov {stack_at(new_si)}, rax")
148 new_env[name] = stack_at(new_si)
149 new_si -= WORD_SIZE
150 compile_expr(body, code, new_si, new_env)
151 case ["if", test, conseq, altern]:
152 L0 = unique_label()
153 L1 = unique_label()
154 compile_expr(test, code, si, env)
155 emit(f"cmp rax, {immediate_rep(False)}")
156 emit(f"je {L0}")
157 compile_expr(conseq, code, si, env)
158 emit(f"jmp {L1}")
159 emit(f"{L0}:")
160 compile_expr(altern, code, si, env)
161 emit(f"{L1}:")
162 case ["cons", car, cdr]:
163 comment("Compile car")
164 compile_expr(car, code, si, env)
165 emit(f"mov {stack_at(si)}, rax")
166 comment("Compile cdr")
167 compile_expr(cdr, code, si-WORD_SIZE, env)
168 emit(f"mov {heap_at(WORD_SIZE)}, rax")
169 emit(f"mov rax, {stack_at(si)}")
170 emit(f"mov {heap_at(0)}, rax")
171 comment("Tag a cons cell")
172 emit(f"lea rax, {heap_at(CONS_TAG)}")
173 size = align(2 * WORD_SIZE)
174 comment("Bump the heap pointer")
175 emit(f"add {HEAP_BASE}, {size}")
176 case ["car", cell]:
177 compile_expr(cell, code, si, env)
178 emit(f"mov rax, {indirect('rax', 0*WORD_SIZE-CONS_TAG)}")
179 case ["cdr", cell]:
180 compile_expr(cell, code, si, env)
181 emit(f"mov rax, {indirect('rax', 1*WORD_SIZE-CONS_TAG)}")
182 case ["labelcall", str(label), *args]:
183 new_si = si - WORD_SIZE # Save a word for the return address
184 for arg in args:
185 compile_expr(arg, code, new_si, env)
186 emit(f"mov {stack_at(new_si)}, rax")
187 new_si -= WORD_SIZE
188 # Align to one word before the return address
189 si_adjust = abs(si+WORD_SIZE)
190 emit(f"sub rsp, {si_adjust}")
191 emit(f"call {label}")
192 emit(f"add rsp, {si_adjust}")
193 case ["funcall", func, *args]:
194 # Save a word for the return address and the closure pointer
195 clo_si = si - WORD_SIZE
196 retaddr_si = clo_si - WORD_SIZE
197 new_si = retaddr_si
198 # Evaluate arguments
199 for arg in args:
200 compile_expr(arg, code, new_si, env)
201 emit(f"mov {stack_at(new_si)}, rax")
202 new_si -= WORD_SIZE
203 compile_expr(func, code, new_si, env)
204 # Save the current closure pointer
205 emit(f"mov {stack_at(clo_si)}, {CLOSURE_BASE}")
206 emit(f"mov {CLOSURE_BASE}, rax")
207 # Align to one word before the return address
208 si_adjust = abs(si)
209 emit(f"sub rsp, {si_adjust}")
210 emit(f"call {indirect(CLOSURE_BASE, -CLOSURE_TAG)}")
211 emit(f"add rsp, {si_adjust}")
212 emit(f"mov {CLOSURE_BASE}, {stack_at(clo_si)}")
213 case ["closure", str(lvar), *args]:
214 comment("Get a pointer to the label")
215 emit(f"lea rax, {lvar}")
216 emit(f"mov {heap_at(0)}, rax")
217 for idx, arg in enumerate(args):
218 assert isinstance(arg, str)
219 comment(f"Load closure cell #{idx}")
220 # Just a variable lookup; guaranteed not to allocate
221 compile_expr(arg, code, si, env)
222 emit(f"mov {heap_at((idx+1)*WORD_SIZE)}, rax")
223 comment("Tag a closure pointer")
224 emit(f"lea rax, {heap_at(CLOSURE_TAG)}")
225 comment("Bump the heap pointer")
226 size = align(WORD_SIZE + len(args)*WORD_SIZE)
227 emit(f"add {HEAP_BASE}, {size}")
228 case _:
229 raise NotImplementedError(expr)
230
231def compile_lexpr(lexpr, code):
232 match lexpr:
233 case ["code", params, freevars, body]:
234 env = {}
235 for idx, param in enumerate(params):
236 env[param] = stack_at(-(idx+1)*WORD_SIZE)
237 for idx, fvar in enumerate(freevars):
238 env[fvar] = indirect(CLOSURE_BASE, (idx+1)*WORD_SIZE - CLOSURE_TAG)
239 compile_expr(body, code, si=-(len(env)+1)*WORD_SIZE, env=env)
240 code.append("ret")
241 case _:
242 raise NotImplementedError(lexpr)
243
244def lift_lambdas_rec(expr, labels, bound, free):
245 match expr:
246 case int(_) | Char():
247 return expr
248 case str(_) if expr in bound or expr in BUILTINS:
249 return expr
250 case str(_):
251 free.add(expr)
252 return expr
253 case ["lambda", params, body]:
254 body_free = set()
255 assert all(isinstance(v, str) for v in params)
256 body = lift_lambdas_rec(body, labels, set(params), body_free)
257 assert all(isinstance(v, str) for v in body_free)
258 free.update(body_free - bound)
259 body_free = sorted(body_free)
260 label = f"f{len(labels)}"
261 labels[label] = ["code", params, body_free, body]
262 return ["closure", label, *body_free]
263 case ["let", bindings, body]:
264 new_bindings = []
265 names = {name for name, _ in bindings}
266 for name, val_expr in bindings:
267 new_bindings.append([name, lift_lambdas_rec(val_expr, labels, bound, free)])
268 new_body = lift_lambdas_rec(body, labels, bound | names, free)
269 return ["let", new_bindings, new_body]
270 case ["if", test, conseq, alt]:
271 return ["if",
272 lift_lambdas_rec(test, labels, bound, free),
273 lift_lambdas_rec(conseq, labels, bound, free),
274 lift_lambdas_rec(alt, labels, bound, free)]
275 case [func, *args]:
276 result = [] if isinstance(func, str) and func in BUILTINS else ["funcall"]
277 for e in expr:
278 result.append(lift_lambdas_rec(e, labels, bound, free))
279 return result
280 case _:
281 raise NotImplementedError(expr)
282
283def lift_lambdas(expr):
284 labels = {}
285 expr = lift_lambdas_rec(expr, labels, set(), set())
286 labels = [[name, code] for name, code in labels.items()]
287 return ["labels", labels, expr]
288
289def compile_program(expr):
290 code = [".intel_syntax", ".global scheme_entry"]
291 match expr:
292 case ["labels", labels, body]:
293 for (lvar, lexpr) in labels:
294 code.append(f"{lvar}:")
295 compile_lexpr(lexpr, code)
296 code.append("scheme_entry:")
297 compile_expr(body, code, si=-WORD_SIZE, env={})
298 code.append("ret")
299 case _:
300 expr = lift_lambdas(expr)
301 assert isinstance(expr, list) and expr[0] == "labels"
302 return compile_program(expr)
303 return "\n".join(code)
304
305class LambdaTests(unittest.TestCase):
306 def test_int(self):
307 self.assertEqual(lift_lambdas(3), ["labels", [], 3])
308
309 def test_bool(self):
310 self.assertEqual(lift_lambdas(True), ["labels", [], True])
311 self.assertEqual(lift_lambdas(False), ["labels", [], False])
312
313 def test_char(self):
314 self.assertEqual(lift_lambdas(Char("a")), ["labels", [], Char("a")])
315
316 def test_freevar(self):
317 self.assertEqual(lift_lambdas("x"), ["labels", [], "x"])
318
319 def test_call_plus(self):
320 self.assertEqual(lift_lambdas(["+", 3, 4]), ["labels", [], ["+", 3, 4]])
321
322 def test_call(self):
323 self.assertEqual(lift_lambdas(["f", 3, 4]), ["labels", [], ["funcall", "f", 3, 4]])
324
325 def test_lambda_no_params_no_freevars(self):
326 self.assertEqual(lift_lambdas(["lambda", [], 3]),
327 ["labels", [
328 ["f0", ["code", [], [], 3]],
329 ], ["closure", "f0"]])
330
331 def test_lambda_no_params_with_freevars(self):
332 self.assertEqual(lift_lambdas(["lambda", [], "z"]),
333 ["labels", [
334 ["f0", ["code", [], ["z"], "z"]],
335 ], ["closure", "f0", "z"]])
336
337 def test_lambda_with_params_no_freevars(self):
338 self.assertEqual(lift_lambdas(["lambda", ["x"], "x"]),
339 ["labels", [
340 ["f0", ["code", ["x"], [], "x"]],
341 ], ["closure", "f0"]])
342
343 def test_lambda_with_params_and_freevars(self):
344 self.assertEqual(lift_lambdas(["lambda", ["x"], ["+", "x", "y"]]),
345 ["labels",
346 [["f0", ["code", ["x"], ["y"], ["+", "x", "y"]]]],
347 ["closure", "f0", "y"]])
348
349 def test_let(self):
350 self.assertEqual(lift_lambdas(["let", [["x", 5]], "x"]),
351 ["labels", [], ["let", [["x", 5]], "x"]])
352
353 def test_let_lambda(self):
354 self.assertEqual(lift_lambdas(["let", [["x", 5]],
355 ["lambda", ["y"],
356 ["+", "x", "y"]]]),
357 ["labels",
358 [["f0", ["code", ["y"], ["x"], ["+", "x", "y"]]]],
359 ["let", [["x", 5]], ["closure", "f0", "x"]]])
360
361 def test_nested_lambda(self):
362 self.assertEqual(lift_lambdas(["lambda", ["x"],
363 ["lambda", ["y"],
364 ["+", "x", "y"]]]),
365 ["labels",
366 [["f0", ["code", ["y"], ["x"], ["+", "x", "y"]]],
367 ["f1", ["code", ["x"], [], ["closure", "f0", "x"]]]],
368 ["closure", "f1"]])
369
370 def test_nested_let(self):
371 self.assertEqual(lift_lambdas(["let", [["x", 5]],
372 ["let", [["y", 6]],
373 ["lambda", [],
374 ["+", "x", "y"]]]]),
375 ["labels",
376 [["f0", ["code", [], ["x", "y"], ["+", "x", "y"]]]],
377 ["let", [["x", 5]],
378 ["let", [["y", 6]],
379 ["closure", "f0", "x", "y"]]]])
380
381 def test_let_inside_lambda(self):
382 self.assertEqual(lift_lambdas(["lambda", ["x"],
383 ["let", [["y", 6]],
384 ["+", "x", "y"]]]),
385 ["labels",
386 [["f0", ["code", ["x"], [],
387 ["let", [["y", 6]],
388 ["+", "x", "y"]]]]],
389 ["closure", "f0"]])
390
391 def test_paper_example(self):
392 self.assertEqual(lift_lambdas(["let", [["x", 5]],
393 ["lambda", ["y"],
394 ["lambda", [],
395 ["+", "x", "y"]]]]),
396 ["labels", [
397 ["f0", ["code", [], ["x", "y"], ["+", "x", "y"]]],
398 ["f1", ["code", ["y"], ["x"], ["closure", "f0", "x", "y"]]],
399 ],
400 ["let", [["x", 5]], ["closure", "f1", "x"]]])
401
402 def test_freevar_inside_let_binding(self):
403 self.assertEqual(lift_lambdas(["lambda", ["x"],
404 ["let", [["y", "x"]],
405 ["+", "x", "y"]]]),
406 ["labels",
407 [["f0", ["code", ["x"], [],
408 ["let", [["y", "x"]],
409 ["+", "x", "y"]]]]],
410 ["closure", "f0"]])
411
412 def test_if(self):
413 self.assertEqual(lift_lambdas(["if", 1, 2, 3]),
414 ["labels", [], ["if", 1, 2, 3]])
415 self.assertEqual(lift_lambdas(["lambda", [],
416 ["if", "x", "y", "z"]]),
417 ["labels",
418 [["f0", ["code", [], ["x", "y", "z"],
419 ["if", "x", "y", "z"]]]],
420 ["closure", "f0", "x", "y", "z"]])
421
422def link(program, outfile=None, verbose=True):
423 if not outfile:
424 outfile = "a.out"
425 with tempfile.NamedTemporaryFile(suffix=".s") as f:
426 with tempfile.NamedTemporaryFile(suffix=".o") as runtime_o:
427 f.write(program.encode("utf-8"))
428 f.flush()
429 run(["ccache", "clang", "-O0", "-ggdb", "-c", "runtime.c", "-o", runtime_o.name], verbose=verbose)
430 compiled_object = f"{f.name}.o"
431 run(["ccache", "clang", "-masm=intel", f.name, "-c", "-o", compiled_object], verbose=verbose)
432 run(["ccache", "clang", "-O0", "-no-pie", compiled_object, runtime_o.name, "-o", outfile], verbose=verbose)
433 return outfile
434
435class EndToEndTests(unittest.TestCase):
436 def _run(self, expr):
437 return self._run_program(["labels", [], expr])
438
439 def _run_program(self, program):
440 asm = compile_program(program)
441 with tempfile.NamedTemporaryFile(suffix=".out", delete_on_close=False) as f:
442 link(asm, f.name, verbose=False)
443 f.close()
444 result = run([f.name], verbose=False, capture_output=True)
445 self.assertIsNot(result.stdout, None)
446 return result.stdout.removesuffix("\n")
447
448 def test_int(self):
449 self.assertEqual(self._run(123), "123")
450
451 def test_char(self):
452 self.assertEqual(self._run(Char("a")), "'a'")
453
454 def test_bool(self):
455 self.assertEqual(self._run(True), "#t")
456 self.assertEqual(self._run(False), "#f")
457
458 def test_empty_list(self):
459 self.assertEqual(self._run([]), "()")
460
461 def test_add1(self):
462 self.assertEqual(self._run(["add1", 3]), "4")
463 self.assertEqual(self._run(["add1", ["add1", 3]]), "5")
464
465 def test_integer_to_char(self):
466 self.assertEqual(self._run(["integer->char", 97]), "'a'")
467
468 def test_char_to_integer(self):
469 self.assertEqual(self._run(["char->integer", Char("a")]), "97")
470
471 def test_nullp(self):
472 self.assertEqual(self._run(["null?", 123]), "#f")
473 self.assertEqual(self._run(["null?", []]), "#t")
474
475 def test_zerop(self):
476 self.assertEqual(self._run(["zero?", 123]), "#f")
477 self.assertEqual(self._run(["zero?", 0]), "#t")
478 self.assertEqual(self._run(["zero?", []]), "#f")
479
480 def test_not(self):
481 self.assertEqual(self._run(["not", True]), "#f")
482 self.assertEqual(self._run(["not", False]), "#t")
483
484 def test_integerp(self):
485 self.assertEqual(self._run(["integer?", 123]), "#t")
486 self.assertEqual(self._run(["integer?", 0]), "#t")
487 self.assertEqual(self._run(["integer?", []]), "#f")
488 self.assertEqual(self._run(["integer?", Char("a")]), "#f")
489 self.assertEqual(self._run(["integer?", True]), "#f")
490 self.assertEqual(self._run(["integer?", False]), "#f")
491
492 def test_booleanp(self):
493 self.assertEqual(self._run(["boolean?", 123]), "#f")
494 self.assertEqual(self._run(["boolean?", 0]), "#f")
495 self.assertEqual(self._run(["boolean?", []]), "#f")
496 self.assertEqual(self._run(["boolean?", Char("a")]), "#f")
497 self.assertEqual(self._run(["boolean?", True]), "#t")
498 self.assertEqual(self._run(["boolean?", False]), "#t")
499
500 def test_add(self):
501 self.assertEqual(self._run(["+", 3, 4]), "7")
502 self.assertEqual(self._run(["+", ["+", 1, 2], ["+", 3, 4]]), "10")
503
504 def test_let_no_bindings(self):
505 self.assertEqual(self._run(["let", [], 3]), "3")
506
507 def test_let_one_binding(self):
508 self.assertEqual(self._run(["let", [["a", 3]], "a"]), "3")
509
510 def test_let_multiple_bindings(self):
511 self.assertEqual(self._run(["let", [["a", 3], ["b", 4]], ["+", "a", "b"]]), "7")
512
513 def test_if(self):
514 self.assertEqual(self._run(["if", True, 3, 4]), "3")
515 self.assertEqual(self._run(["if", False, 3, 4]), "4")
516
517 def test_cons(self):
518 self.assertEqual(self._run(["cons", 3, 4]), "(3 . 4)")
519 self.assertEqual(self._run(["cons", ["cons", 1, 2], ["cons", 3, 4]]), "((1 . 2) . (3 . 4))")
520
521 def test_car(self):
522 self.assertEqual(self._run(["car", ["cons", 3, 4]]), "3")
523
524 def test_cdr(self):
525 self.assertEqual(self._run(["cdr", ["cons", 3, 4]]), "4")
526
527 def test_labelcall_no_args(self):
528 self.assertEqual(self._run_program(
529 ["labels",
530 [
531 ["const", ["code", [], [], 3]]
532 ],
533 ["labelcall", "const"],
534 ]), "3")
535
536 def test_labelcall_with_args(self):
537 self.assertEqual(self._run_program(
538 ["labels",
539 [
540 ["add", ["code", ["a", "b"], [], ["+", "a", "b"]]]
541 ],
542 ["labelcall", "add", 3, 4],
543 ]), "7")
544
545 def test_labelcall_with_tmp_on_stack(self):
546 self.assertEqual(self._run_program(
547 ["labels",
548 [
549 ["add", ["code", ["a", "b"], [], ["+", "a", "b"]]]
550 ],
551 ["+", 2, ["labelcall", "add", 3, 4]],
552 ]), "9")
553
554 def test_nested_labelcall_with_args(self):
555 self.assertEqual(self._run_program(
556 ["labels",
557 [
558 ["add", ["code", ["a", "b"], [], ["+", "a", "b"]]],
559 ["g", ["code", ["a", "b"], [],
560 ["+",
561 ["labelcall", "add", "a", "b"],
562 ["labelcall", "add", "a", "b"],
563 ],
564 ]],
565 ["f", ["code", ["a"], [], ["labelcall", "g", "a", 4]]],
566 ],
567 ["labelcall", "f", 3],
568 ]), "14")
569
570 def test_empty_closure(self):
571 self.assertEqual(self._run_program(
572 ["labels",
573 [
574 ["const", ["code", [], [], 3]],
575 ],
576 ["closure", "const"],
577 ]), "<closure>")
578
579 def test_closure_one_var(self):
580 self.assertEqual(self._run_program(
581 ["labels",
582 [
583 ["const", ["code", [], [], 3]],
584 ],
585 ["let", [["a", 1]],
586 ["closure", "const", "a"],
587 ]
588 ]), "<closure>")
589
590 def test_closure_multiple_vars(self):
591 self.assertEqual(self._run_program(
592 ["labels",
593 [
594 ["const", ["code", [], [], 3]],
595 ],
596 ["let", [["a", 1]],
597 ["closure", "const", "a", "a", "a"],
598 ]
599 ]), "<closure>")
600
601 def test_funcall_empty_closure(self):
602 self.assertEqual(self._run_program(
603 ["labels",
604 [
605 ["const", ["code", [], [], 3]],
606 ],
607 ["let", [["f", ["closure", "const"]]],
608 ["funcall", "f"]]
609 ]), "3")
610
611 def test_funcall_empty_closure_with_params(self):
612 self.assertEqual(self._run_program(
613 ["labels",
614 [
615 ["const", ["code", ["x", "y"], [], ["+", "x", "y"]]],
616 ],
617 ["let", [["f", ["closure", "const"]]],
618 ["funcall", "f", 3, 4]]
619 ]), "7")
620
621 def test_funcall_closure_with_freevar(self):
622 self.assertEqual(self._run_program(
623 ["labels",
624 [
625 ["const", ["code", [], ["z"], "z"]],
626 ],
627 ["let", [["v", 3]],
628 ["let", [["f", ["closure", "const", "v"]]],
629 ["funcall", "f"]]]
630 ]), "3")
631
632 def test_lambda(self):
633 self.assertEqual(self._run_program(["lambda", ["x"], "x"]), "<closure>")
634
635 def test_lambda_one_var(self):
636 self.assertEqual(self._run_program(
637 ["let", [["y", 5]], ["lambda", [], "y"]]),
638 "<closure>")
639
640 def test_call_lambda(self):
641 self.assertEqual(self._run_program([["lambda", ["x"], "x"], 3]), "3")
642
643 def test_lambda_lift_paper_example(self):
644 self.assertEqual(self._run_program(["let", [["x", 5]],
645 ["lambda", ["y"],
646 ["lambda", [],
647 ["+", "x", "y"]]]]),
648 "<closure>")
649 self.assertEqual(self._run_program([["let", [["x", 5]],
650 ["lambda", ["y"],
651 ["lambda", [],
652 ["+", "x", "y"]]]], 4]),
653 "<closure>")
654 self.assertEqual(self._run_program([[["let", [["x", 5]],
655 ["lambda", ["y"],
656 ["lambda", [],
657 ["+", "x", "y"]]]], 4]]),
658 "9")
659
660
661if __name__ == "__main__":
662 unittest.main()