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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
|
# Bad Diode's Lisp
For some time I've been meaning to learn more about compilers and programming
language theory. And so I found myself again delving into a rabbit hole of
wheel-reinvention for the purpose of fun and learning.
The language, `bdl` is inspired by `Scheme`, but it doesn't aim to be compatible
with it grammatically or in terms of behaviour. Instead, the core language is
much smaller and we will grow it organically as needed. As such, it is heavily
in flux and not ready for any kind of production usage.
Currently `bdl` conforms with the grammar described below. It is a dynamically
typed language, garbage collected and supports lambdas, lexical scopes and
closures.
Up to [v0.7][v0.7] we were building a fully functional tree-walking interpreter.
A writeup for the different building blocks can be found in [a series of
articles][bdl-series] that go into great detail about the implementation and
basic concepts behind the language.
From [v0.7][v0.7] to [v0.8][v0.8], we created a second interpreter
implementation. It was built by following along the second part of the [Crafting
Interpreters][crafting-interpreters] book. This reimagining of the project uses
a single-pass compiler to generate bytecode for an custom abstract virtual
machine. This interpreter is much faster than the tree-walking version and still
supports closures, but it has no garbage collector and leaks memory. It was
a good learning exercise but the VM is too abstracted for my taste and I don't
wish to maintain a half-baked implementation.
Current development focuses on building from the fundamentals of previous
iterations to create a native compiler that could be used with multiple backends
for code generation (e.g. `LLVM`, `x86_64`/`aarch64` assembly, `uxn` bytecode,
etc.). One of the goals of this part is to have trivial `C` interop when
compiled natively, meaning it should be possible to call `bdl` code from `C` and
`C` functions from `bdl` (though some wrappers may be necessary).
[bdl-series]: https://git.badd10de.dev/bdl/tag/?h=v0.7
[v0.7]: https://git.badd10de.dev/bdl/tag/?h=v0.7
[v0.8]: https://git.badd10de.dev/bdl/tag/?h=v0.8
# Grammar
```
; Support for multiple return values, some options:
fn foo_name(arg1 :u8, arg2 :u16) :u32, :str {
; foo body... returns a tuple of two elements
}
fn foo_name(arg1:u8, arg2:u16):(u32, str) {
; foo body... returns a tuple of two elements
}
; Support for default function names maybe
fn foo_name(
arg1: u8
arg2: u16
arg3: u16
arg4: u16 = 52
arg5: u16
arg6: u16
): (u32 str) {
; foo body... returns a tuple of two elements.
; commas could be syntax sugar, converting to whitespace during parsing.
}
; Everything is an expression, including functions and variable definitions,
; which evaluate to `nil`.
; All of these could be equivalent
let a:s32 124
let a:s32
124
let
a:s32
124
let
a:s32 124
; What happens if we make a mistake and use let over let?
let a:s32 let b:u32 c
; or
let a:s32 <missing value here>
let b:u32 c
; well since, we have an expression that evaluates to nil it should be fine
if x == 2 {
; expressions
}
if (x == 2) foo()
if
true {
; expressions
}
else {
; expressions
}
if
(x == 2) if (x != 1) else 2
(x == 3) bar()
if (x == 1) (foo x y)
if (x == 2) foo(x y)
if (x == 3) bar()
if (x == 4) baz()
if (x == 5) "literals too"
match symbol
case 5 "block"
case 32 foo()
case 49 "alsd asdlk aslkdf alskdf"
match (symbol or literal)
case (symbol or literal) block
case (symbol or literal) foo()
case (symbol or literal) "alsd asdlk aslkdf alskdf"
cond (10 == 1) {
~a << b & 10
; How do we declare and use hashmap types? (builtin)
#str:u32
}
```
```
<literal> ::= <boolean> | <number> | <string> | <nil>
/* any unicode rune really really */
<character> ::= [a-z] | [A-Z]
<string> ::= "\"" <character>+ "\""
<comment> ::= ";" <character>* "\n"
<newline> ::= "\n"
/* notably the symbol can't be a reserved word or start with a numeric value, modify later */
<symbol> ::= <character>+
<nil> ::= "nil"
/* boolean literals */
<boolean> ::= "true" | "false"
/* numbers TODO: Missing imaginary numbers (for the future maybe?) */
<number> ::= <integer> | <real>
<fractional> ::= <digit>+ "." <digit>+
<real> ::= ("+" | "-")? <fractional>
| ("+" | "-")? <fractional> ("e" | "E") ("+" | "-")? <digit>+
<integer> ::= ("+" | "-")? <digit>+
| "0b" [0-1]+
| "0x" ([0-9] | [a-f])+
<digit> ::= [0-9]
/* conditional expressions */
<condition> ::= <expression> | "else"
<case> ::= "case" <literal> <expression>
<conditional> ::= "if" (<condition> <expression>)+
| "match" <expression> <case>+
/* variables and functions */
<varpair> ::= <symbol> <type> | <symbol> <type>? "=" <expression>
<vardecl> ::= "let" <varpair>
| "let" "{" <varpair>+ "}"
<fundecl> ::= "fun" <symbol> "(" <argument>* ")" <type>* <expression>
<argument> ::= <symbol> <type>? ("=" <literal>)?
<type> ::= ":" <symbol>
<funcall> ::= <symbol> ("." <symbol>)? "(" <expression>+ ")"
<flowchange> ::= "return" ("(" <expression>+ ")")?
| "continue" | "break"
<loop> ::= "while" <expression> <expression>
| "while" <vardecl> <expression> <expression>
<assignment> ::= "set" <symbol> "=" <expression>
| "set" "{" (<symbol> "=" <expression>)+ "}"
<expression> ::= <equality>
<equality> ::= <comparison> ( ( "!=" | "==" ) <comparison>)*
<comparison> ::= <term> ( ( ">" | ">=" | "<" | "<=" ) <term>)*
<term> ::= <factor> ( ( "-" | "+" ) <factor>)*
<factor> ::= <logical> (("/" | "*") <logical>)*
<logical> ::= <unary> (("and" | "or") <unary>)*
<unary> ::= "!" <unary> | <bitlogic>
<bitlogic> ::= <bitshift> (("&" | "|") <bitshift>)*
<bitshift> ::= <bitneg> (("<<" | ">>") <bitneg>)*
<bitneg> ::= "~" <bitneg> | <primary>
<primary> ::= <literal>
| <symbol>
| <funcall>
| <conditional>
| <loop>
| <block>
| <flowchange>
| <assignment>
| "(" <expression> ")"
<structdecl> ::= "struct" <symbol> "{" ((<symbol> <type> ("=" <literal>)?) <fundecl>)+ "}"
<declaration> ::= <fundecl> | <vardecl> | <structdecl> | <expression>
<block> ::= "{" <declaration>+ "}"
<program> ::= <declaration>+ "EOF"
/* TODO: Missing arithmetic and logic operations, type declarations */
```
# Resources
- [Structure and Interpretation of Computer Programs][sicp]
- [Crafting Interpreters][crafting-interpreters]
- [Building a Scheme from scratch][scheme-from-scratch]
- [Compiling a Lisp][compiling-a-lisp]
- [An Incremental Approach to Compiler Construction][ghuloum11]
- [Make-A-Lisp Guide][mal]
- [An Introduction to Scheme and its Implementation][intro-to-scheme-and-imp]
- [Scheme to C][scheme-to-c]
[sicp]: https://mitpress.mit.edu/sites/default/files/sicp/index.html
[crafting-interpreters]: https://craftinginterpreters.com/
[scheme-from-scratch]: http://peter.michaux.ca/articles/scheme-from-scratch-introduction
[compiling-a-lisp]: https://bernsteinbear.com/blog/compiling-a-lisp-0/
[ghuloum11]: http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf
[mal]: https://github.com/kanaka/mal/blob/master/process/guide.md
[intro-to-scheme-and-imp]: https://www.cs.utexas.edu/ftp/garbage/cs345/schintro-v14/schintro_toc.html#SEC271
[scheme-to-c]: https://github.com/akeep/scheme-to-c
|
