Big-ass coding binge presents: a Lisp.

This implements a continuation-passing interpreter, which means we get tail calls ferfree. I stopped short of implementing call/cc, because I don't think we need it, but we can get there if we have to.

6 files changed, 185 insertions, 8 deletions

diff --git a/tests/forms.py b/tests/forms.py
new file mode 100644
index 0000000..1a49636
--- /dev/null
+++ b/tests/forms.py
@@ -0,0 +1,76 @@
+from hypothesis.strategies import integers, decimals as hypo_decimals, booleans, characters, text, tuples, lists as hypo_lists, just, one_of
+from hypothesis.strategies import deferred, recursive
+
+from actinide.symbol_table import *
+from actinide.types import *
+
+# Generators for forms. Where these generators create a symbol, they will use
+# the global symbol table defined in this module. Do not do this in your own
+# code! A global symbol table is a memory leak, and only the fact that tests
+# exit before they can do any substantial damage prevents this from being a
+# bigger problem.
+#
+# Each generator produces the parsed version of a form.
+
+symbol_table = SymbolTable()
+
+# Generates nil.
+def nils():
+    return just(None)
+
+# Generates integers.
+def ints():
+    return integers()
+
+# Generates language decimals.
+def decimals():
+    return hypo_decimals(allow_nan=False, allow_infinity=False)
+
+# Generates booleans.
+def bools():
+    return booleans()
+
+# Generates strings.
+def strings():
+    return text()
+
+# Generates any character legal in a symbol, which cannot be part of some other
+# kind of atom.
+def symbol_characters():
+    return characters(blacklist_characters='01234567890#. \t\n();"')
+
+# Generates symbols guaranteed not to conflict with other kinds of literal. This
+# is a subset of the legal symbols.
+def symbols():
+    return text(symbol_characters(), min_size=1)\
+        .map(lambda item: symbol_table[item])
+
+# Generates atoms.
+def atoms():
+    return one_of(
+        nils(),
+        ints(),
+        decimals(),
+        bools(),
+        strings(),
+        symbols(),
+    )
+
+# Generates arbitrary conses, with varying depth. This may happen to generate
+# lists by accident.
+def conses():
+    return recursive(
+        tuples(atoms(), atoms()).map(lambda elems: cons(*elems)),
+        lambda children: tuples(children | atoms(), children | atoms()).map(lambda elems: cons(*elems)),
+    )
+
+# Generates lists, with varying depth.
+def lists():
+    return recursive(
+        hypo_lists(atoms()).map(lambda elems: list(*elems)),
+        lambda children: hypo_lists(children | atoms()).map(lambda elems: list(*elems)),
+    )
+
+# Generates random forms.
+def forms():
+    return one_of(nils(), ints(), bools(), strings(), symbols(), conses(), lists())
diff --git a/tests/programs.py b/tests/programs.py
new file mode 100644
index 0000000..78c52c7
--- /dev/null
+++ b/tests/programs.py
@@ -0,0 +1,57 @@
+from hypothesis.strategies import integers, decimals, booleans, text, tuples
+from hypothesis.strategies import one_of, composite, deferred
+
+from actinide.types import *
+from actinide.environment import *
+from actinide.symbol_table import *
+
+symbol_table = SymbolTable()
+
+def literals():
+    return one_of(
+        booleans(),
+        integers(),
+        decimals(allow_nan=False, allow_infinity=False),
+        text(),
+    ).map(lambda value: (value, (value,), []))
+
+def symbols():
+    return text().map(lambda symb: symbol_table[symb])
+
+def values():
+    return literals()
+
+@composite
+def ifs(draw, conds, trues, falses):
+    cond, (cond_result,), cond_bindings = draw(conds)
+    true, true_result, true_bindings = draw(trues)
+    false, false_result, false_bindings = draw(falses)
+
+    expr = list(symbol_table['if'], cond, true, false)
+    result = true_result if cond_result else false_result
+    bindings = cond_bindings + (true_bindings if cond_result else false_bindings)
+
+    return expr, result, bindings
+
+def if_exprs():
+    return ifs(exprs(), exprs(), exprs())
+
+def if_progs():
+    return ifs(exprs(), programs(), programs())
+
+@composite
+def defines(draw):
+    symbol = draw(symbols())
+    value, (value_result,), value_bindings = draw(values())
+    return (
+        list(symbol_table['define'], symbol, value),
+        (),
+        value_bindings + [(symbol, value_result)],
+    )
+
+def exprs():
+    return deferred(lambda: one_of(literals(), if_exprs()))
+
+def programs():
+    return deferred(lambda: one_of(literals(), defines(), if_progs()))
+
diff --git a/tests/test_evaluator.py b/tests/test_evaluator.py
new file mode 100644
index 0000000..d989f85
--- /dev/null
+++ b/tests/test_evaluator.py
@@ -0,0 +1,18 @@
+from hypothesis import given, event
+
+from actinide.evaluator import *
+from actinide.environment import *
+from actinide.types import *
+
+from .programs import *
+
+# Cases for the evaluator:
+
+# * Given a program, does it produce the expected evaluation?
+@given(programs())
+def test_evaluator(program_result):
+    program, result, bindings = program_result
+    environment = Environment()
+    assert run(eval(program, environment, symbol_table, None)) == result
+    for symbol, value in bindings:
+        assert environment[symbol] == value
diff --git a/tests/test_ports.py b/tests/test_ports.py
index c2d1e06..d755dcf 100644
--- a/tests/test_ports.py
+++ b/tests/test_ports.py
@@ -6,24 +6,24 @@ from actinide.ports import *
 @given(text(), integers(min_value=1, max_value=2**32 - 1))
 def test_read(input, n):
     port = string_to_input_port(input)
-    output = read(port, n)
+    output = read_port(port, n)
 
     assert input.startswith(output)
     assert (len(output) == 0 and len(input) == 0) != (0 < len(output) <= n)
-    assert output + read_fully(port) == input
+    assert output + read_port_fully(port) == input
 
 @given(text(), integers(min_value=1, max_value=2**32 - 1))
 def test_peek(input, n):
     port = string_to_input_port(input)
-    output = peek(port, n)
+    output = peek_port(port, n)
 
     assert input.startswith(output)
     assert (len(output) == 0 and len(input) == 0) != (0 < len(output) <= n)
-    assert read_fully(port) == input
+    assert read_port_fully(port) == input
 
 @given(text(), integers(min_value=1, max_value=2**32 - 1))
 def test_read_fully(input, n):
     port = string_to_input_port(input)
-    output = read_fully(port)
+    output = read_port_fully(port)
 
     assert output == input
diff --git a/tests/test_reader.py b/tests/test_reader.py
new file mode 100644
index 0000000..54a1681
--- /dev/null
+++ b/tests/test_reader.py
@@ -0,0 +1,28 @@
+from hypothesis import given
+from hypothesis.strategies import text
+
+from actinide.reader import *
+from actinide.ports import *
+from actinide.types import *
+
+from .forms import *
+
+# Cases for the reader:
+
+# * Given a form, can the reader recover it from its display?
+@given(forms())
+def test_reader(form):
+    input = display(form)
+    port = string_to_input_port(input)
+
+    assert read(port, symbol_table) == form
+
+# * Given a form and some trailing garbage, can the reader recover the form
+#   without touching the garbage? This is only reliable with lists and conses.
+@given(lists() | conses(), text())
+def test_reader_with_trailing(form, text):
+    input = display(form) + text
+    port = string_to_input_port(input)
+
+    assert read(port, symbol_table) == form
+    assert read_port_fully(port) == text
diff --git a/tests/test_tokenizer.py b/tests/test_tokenizer.py
index 5c0ddea..7e5c7b3 100644
--- a/tests/test_tokenizer.py
+++ b/tests/test_tokenizer.py
@@ -1,6 +1,4 @@
-from hypothesis import given, settings, HealthCheck, event
-from hypothesis.strategies import just, text, characters, from_regex, one_of, tuples, sampled_from
-import io
+from hypothesis import given
 
 from actinide.tokenizer import *
 from actinide.ports import *