# 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