blob: 6d792fd26a197009f6ff34aed23d65eaadafdebb (
plain) (
blame)
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
|
# Brainfuck2Scheme
A simple compiler from Brainfuck to R5RS. The compiler will output a Scheme
list that is a lambda with three arguments:
* `data`: The data vector.
* `dptr`: The initial data pointer.
* `debugger`: Debugger function
To turn the list into an executable Scheme function, just give it to
`eval`. `(execute scheme len)` will run the Scheme code in `scheme`
with a data vector of length `len`.
This dialect of Brainfuck supports `#` to call the `debugger` procedure
with `data` and `dptr` as arguments.
Since Brainfuck programs become Scheme procedures, you can modularize
Brainfuck code and (ab)use the debugger for things like procedure calls
and foreign libraries.
## How It Works
Brainfuck is a very simple Harvard architecture computer. The data is
stored as a vector `data` and the data pointer is an integer `dptr`.
The big idea is that all the code is compiled to a big lambda form, but
there are some wrinkles due to jumps.
Data access brainfuck instructions are translated like
* `+` -> `(vector-set! data dptr (+ 1 (vector-ref data dptr)))`
* `-` -> `(vector-set! data dptr (+ -1 (vector-ref data dptr)))`
* `>` -> `(set! dptr (+ dptr 1))`
* `<` -> `(set! dptr (- dptr 1))`
* `.` -> `(display (vector-ref data dptr))`
* `,` -> `(vector-set! data dptr (read-char))`
* `#` -> `(debugger data dptr)`
Branches are trickier. Basically, all code that will be executed in a block
is in a lambda. Given `[code...]`, the `code...` will be compiled to a
lambda in a `letrec`, with a conditional at the end that will tail-call the
lambda if the current data pointer is not zero.
The transformation then goes like
`[ CODE ... ] REST ...` ->
(letrec ((between (lambda ()
(TRANSLATE CODE ...)
(if (not (zero? (vector-ref data dptr)))
(between)))))
(if (not (zero? (vector-ref data dptr)))
(between)))
(TRANSLATE REST ...)
where `(TRANSLATE CODE ...)` translates `CODE` to Scheme instructions
like above.
|
