From d6e375e2df252ca27de32fa29c2d69a69ce9f65b Mon Sep 17 00:00:00 2001
From: Marvin Borner
Date: Sun, 15 Oct 2023 01:40:29 +0200
Subject: Universal machine interpreter

This is a fun lambda calculus interpreter, written in bruijn itself.
The code is based on @Tromp submission to IOCCC 2012.

Performance-wise the unary (fac 9) takes 11.4s simulated vs 1.2s native.
-> main problem is memory, simulated (fac 10) causes memory overflow on
32GB.
---
 samples/fun/interpreter.bruijn | 41 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)
 create mode 100644 samples/fun/interpreter.bruijn

(limited to 'samples/fun/interpreter.bruijn')

diff --git a/samples/fun/interpreter.bruijn b/samples/fun/interpreter.bruijn
new file mode 100644
index 0000000..0691f4a
--- /dev/null
+++ b/samples/fun/interpreter.bruijn
@@ -0,0 +1,41 @@
+# originally written in obfuscated form by John Tromp for IOCCC 2012
+# run with `printf 000010 | bruijn interpreter.bruijn`
+# note that Tromp's IO uses an additional abstraction at the beginning ("00" ++ ...)
+
+:import std/Combinator .
+:import std/Number .
+:import std/List .
+:import std/Char C
+
+# TODO: finish types
+uni [0 0] int [0 Ω] ⧗ (List Bit) → Term
+	int [[[0 go (2 2) 1]]]
+		go [[[[2 match]]]]
+			match [4 case-0 case-1]
+				case-0 2 exp
+					exp [1 case-00 case-01]
+						case-00 2 abs
+							abs [[2 [0 1 2]]]
+						case-01 3 [3 app]
+							app [2 0 (1 0)]
+				case-1 0 case-10 case-11
+					case-10 1 cont
+						cont [0 1]
+					case-11 [3 [3 var] 4]
+						var [1 (0 3)]
+
+str→blc map (=?‣ ∘ C.number!)
+
+:test (str→blc "0010") ([[1]] : ([[1]] : ([[0]] : {}[[1]])))
+
+exec uni ∘ str→blc
+
+:test (exec "0011") ([0])
+:test (exec "001111") ([0])
+:test (exec "000010") ([0])
+:test (exec "00000001110011100111010") ((+3u))
+:test (exec "0001010000000001011111011001011110110100000011100111001110100000011100111001110011100111010") ((+8u))
+:test (exec "00010000010101110000001100111000000101111011001110100011000100000011100111001110011100111010") ((+120u))
+:test (exec "000101010100010001110000101110110100001110000101110110100000000001011000000001010111111110111111001011111110111110111011011001000000010111101011000000001011011101100000100001011000000001110011001100110011001110011100110111000010110000000011001110011001100110011100111001101110000101100000000111001110011001100110011100111001101110000010") ("cba")
+
+main exec
-- 
cgit v1.2.3