blob: a77ecbe411843400cd25aef7eacfc6ca78e4afc7 (
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
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
|
# Metaprogramming
Bruijn has a homoiconic meta encoding inspired by Lisp's quoting
feature.
Blog post with more details: [Metaprogramming and
self-interpretation](https://text.marvinborner.de/2023-09-03-21.html).
## Encoding
`X ⤳ [[[2 (+Xu)]]]
`(M N) ⤳ [[[1 `M `N]]]
`[M] ⤳ [[[0 `M]]]
Any quoted term gets converted to this encoding:
``` bruijn
# example quotations
:test (`0) ([[[2 (+0u)]]])
:test (`[0]) ([[[0 [[[2 (+0u)]]]]]])
:test (`'0') ([[[0 [[[0 [[[0 [[[1 [[[2 (+0u)]]] [[[1 [[[2 (+0u)]]] [[[1 [[[2 (+0u)]]] [[[1 [[[2 (+0u)]]] [[[1 [[[2 (+1u)]]] [[[1 [[[2 (+1u)]]] [[[1 [[[2 (+0u)]]] [[[1 [[[2 (+0u)]]] [[[2 (+2u)]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]])
# quotes are nestable!
:test (``0) ([[[0 [[[0 [[[0 [[[1 [[[2 (+2u)]]] [[[0 [[[0 [[[2 (+0u)]]]]]]]]]]]]]]]]]]]]])
:test (`[0 `0]) ([[[0 [[[1 [[[2 (+0u)]]] [[[0 [[[0 [[[0 [[[1 [[[2 (+2u)]]] [[[0 [[[0 [[[2 (+0u)]]]]]]]]]]]]]]]]]]]]]]]]]]])
```
## Quasiquotation
Quoted terms can be escaped (*unquoted*) using the comma symbol.
Unquoted terms will be fully evaluated first before getting quoted
again.
``` bruijn
:test (```,[0]) (``[0])
:test (`,`,[0]) ([0])
:test (`[0 `,[0]]) (`[0 [0]])
```
Unquoted De Bruijn indices will get bound to the respective abstraction
outside of its meta encoding.
``` bruijn
# adds two using normal quotation
add-two `[0 + (+2u)]
:test (!add-two (+2u)) ((+4u))
# adds two using a reaching De Bruijn index
add-two* [`(,0 + (+2u))]
:test (!(add-two* `(+2u))) ((+4u))
```
## Self-interpretation
Using a metacircular self-interpreter, bruijn can reduce the meta
encoding to its normal form. A 194 bit interpreter in the form of
bruijn's logo:
``` code-showcase
01010001 00011100
11010000 ###### 11100110
10000 ############ 00001
01011 ##### ##### 00001
11100 #### #### 00101
01110 #### ##### 00011
00000 #### ###### 10100
00011 #### ### #### 00111
10000 #### ## #### 11111
00001 #### ### #### 11110
00010 ###### #### 11110
10011 ##### #### 10100
11110 #### #### 00011
11000 ##### ##### 00011
11000 ############ 01011
01101110 ###### 00011001
00011010 00011010
```
The code can also be found in the `eval`{.bruijn}/`!‣`{.bruijn} function
of the meta library:
``` bruijn
:test (!`"tacocat".reverse) ("tacocat")
```
## Meta library [`std/Meta`](/std/Meta.bruijn.html)
The meta library enables simple interaction with the meta encoding.
Examples:
``` bruijn
# testing equivalence
:test (α-eq? `[0 0] `[0 0]) (true)
:test (α-eq? `α-eq? `α-eq?) (true)
# BLC length of meta term
:test (length `[0]) ((+4u))
:test (length `[[1 1]]) ((+12u))
# self-modification
:test (lhs `(1 0) `0) (`(0 0))
:test (rhs `(0 1) `0) (`(0 0))
:test (swap `(1 0)) (`(0 1))
:test (map inc `0) (`1)
:test (map (map inc) `[0]) (`[1])
:test (map swap `[0 1]) (`[1 0])
# encoding terms as numbers
:test ((encode `(0 0)) =? (+3)) (true)
:test ((encode `[0]) =? (+8)) (true)
# decoding numbers to terms
:test (decode (+3)) (`(0 0))
:test (decode (+8)) (`[0])
```
|
