diff options
-rwxr-xr-x | .gitignore | 1 | ||||
-rwxr-xr-x | Makefile | 51 | ||||
-rwxr-xr-x | README.md | 53 | ||||
-rwxr-xr-x | src/bootstrap/main.c | 61 | ||||
-rwxr-xr-x | src/bootstrap/shorthand.h | 37 |
5 files changed, 203 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100755 index 0000000..378eac2 --- /dev/null +++ b/.gitignore | |||
@@ -0,0 +1 @@ | |||
build | |||
diff --git a/Makefile b/Makefile new file mode 100755 index 0000000..8bd5560 --- /dev/null +++ b/Makefile | |||
@@ -0,0 +1,51 @@ | |||
1 | .POSIX: | ||
2 | .SUFFIXES: | ||
3 | |||
4 | # Source code location and files to watch for changes. | ||
5 | SRC_DIR := src/bootstrap | ||
6 | BUILD_DIR := build | ||
7 | SRC_MAIN := $(SRC_DIR)/main.c | ||
8 | WATCH_SRC := $(shell find $(SRC_DIR) -name "*.c" -or -name "*.s" -or -name "*.h") | ||
9 | INC_DIRS := $(shell find $(SRC_DIR) -type d) | ||
10 | INC_FLAGS := $(addprefix -I,$(INC_DIRS)) | ||
11 | |||
12 | # Output executable. | ||
13 | TARGET := bdl | ||
14 | BIN := $(BUILD_DIR)/$(TARGET) | ||
15 | |||
16 | # Compiler and linker configuration. | ||
17 | CC := cc | ||
18 | CFLAGS := -Wall -Wextra -pedantic | ||
19 | CFLAGS += $(INC_FLAGS) | ||
20 | LDFLAGS := | ||
21 | LDLIBS := | ||
22 | RELEASE_CFLAGS := -DNDEBUG -O2 | ||
23 | DEBUG_CFLAGS := -DDEBUG -O2 -g | ||
24 | |||
25 | .PHONY: tools clean run | ||
26 | |||
27 | # Setup debug/release builds. | ||
28 | # make clean && make <target> DEBUG=0 | ||
29 | # make clean && make <target> DEBUG=1 | ||
30 | DEBUG ?= 0 | ||
31 | ifeq ($(DEBUG), 1) | ||
32 | CFLAGS += $(DEBUG_CFLAGS) | ||
33 | else | ||
34 | CFLAGS += $(RELEASE_CFLAGS) | ||
35 | endif | ||
36 | |||
37 | main: tools $(BUILD_DIR) $(ROM) $(BIN) | ||
38 | |||
39 | $(BIN): $(SRC_MAIN) $(WATCH_SRC) | ||
40 | $(CC) $(CFLAGS) $(LDFLAGS) -o $(BIN) $(SRC_MAIN) $(LDLIBS) | ||
41 | |||
42 | # Create build directory if needed. | ||
43 | $(BUILD_DIR): tools | ||
44 | mkdir -p $(BUILD_DIR) | ||
45 | |||
46 | run: $(BIN) | ||
47 | ./$(BIN) | ||
48 | |||
49 | # Remove build directory. | ||
50 | clean: | ||
51 | rm -rf $(BUILD_DIR) | ||
diff --git a/README.md b/README.md new file mode 100755 index 0000000..4caf1c3 --- /dev/null +++ b/README.md | |||
@@ -0,0 +1,53 @@ | |||
1 | # Bad Diode's Lisp | ||
2 | |||
3 | For some time I've been meaning to learn more about compilers and programming | ||
4 | language theory. And so I found myself again delving into a rabbit hole of | ||
5 | wheel-reinvention for the purpose of fun and learning. | ||
6 | |||
7 | The goals for this project are to build a programming language that can be | ||
8 | interpreted directly from a VM and with support for compilation to assembly | ||
9 | (`x86_64` and/or `ARM (thumb or aarch64)`). It could make sense to output | ||
10 | bytecode for LLVM to take advantage of the built in optimizations, but let's | ||
11 | just go one step at a time. At the time I know some ARM assembly, but I'm not so | ||
12 | versed in `x86_64` and know nothing of LLVM bytecode. | ||
13 | |||
14 | I've chosen to implement a Lisp, perhaps a subset of Scheme. The syntax is not | ||
15 | so important for now, maybe in the future the compiler will take a different | ||
16 | home-brew language, but hopefully this helps setting the fundamentals for | ||
17 | a minimal working compiler. In principle, we could keep the internal | ||
18 | representation and language working as a lisp, but with a different external | ||
19 | syntax. | ||
20 | |||
21 | The language should have built-in structures for dynamic arrays, hash tables, | ||
22 | strings (and string views). It should be suitable for use in embedded systems | ||
23 | and be linked seamlessly with other compiled objects. | ||
24 | |||
25 | Accessing system resources, such as stdio or graphics could be done via function | ||
26 | calls to the give APIs. This should help decouple the CPU logic from hardware, | ||
27 | hopefully facilitating porting programs to different platforms (GBA, Rasberry | ||
28 | Pi, etc.). | ||
29 | |||
30 | The current plan is to build a bootstrap interpreter in C that can be used to | ||
31 | generate the self-hosted version of itself. I'll try to document the process | ||
32 | here as best as I can. | ||
33 | |||
34 | The bootstrap implementation should be kept simple, since we can focus on | ||
35 | optimization once we have a self-hosting compiler. | ||
36 | |||
37 | # Resources | ||
38 | |||
39 | - [Structure and Interpretation of Computer Programs][sicp] | ||
40 | - [Crafting Interpreters][crafting-interpreters] | ||
41 | - [Building a Scheme from scratch][scheme-from-scratch] | ||
42 | - [Compiling a Lisp][compiling-a-lisp] | ||
43 | - [An Incremental Approach to Compiler Construction][ghuloum11] | ||
44 | - [Make-A-Lisp Guide][mal] | ||
45 | - [An Introduction to Scheme and its Implementation][intro-to-scheme-and-imp] | ||
46 | |||
47 | [sicp]: https://mitpress.mit.edu/sites/default/files/sicp/index.html | ||
48 | [crafting-interpreters]: https://craftinginterpreters.com/ | ||
49 | [scheme-from-scratch]: http://peter.michaux.ca/articles/scheme-from-scratch-introduction | ||
50 | [compiling-a-lisp]: https://bernsteinbear.com/blog/compiling-a-lisp-0/ | ||
51 | [ghuloum11]: http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf | ||
52 | [mal]: https://github.com/kanaka/mal/blob/master/process/guide.md | ||
53 | [intro-to-scheme-and-imp]: https://www.cs.utexas.edu/ftp/garbage/cs345/schintro-v14/schintro_toc.html#SEC271 | ||
diff --git a/src/bootstrap/main.c b/src/bootstrap/main.c new file mode 100755 index 0000000..861c206 --- /dev/null +++ b/src/bootstrap/main.c | |||
@@ -0,0 +1,61 @@ | |||
1 | #include <stdio.h> | ||
2 | |||
3 | #include "shorthand.h" | ||
4 | |||
5 | typedef struct StringView { | ||
6 | char *start; | ||
7 | size_t n; | ||
8 | } StringView; | ||
9 | |||
10 | void | ||
11 | sv_write(StringView sv) { | ||
12 | for (size_t i = 0; i < sv.n; i++) { | ||
13 | putchar(sv.start[i]); | ||
14 | } | ||
15 | } | ||
16 | |||
17 | StringView | ||
18 | read_line(void) { | ||
19 | #define RL_BUF_SIZE 1024 | ||
20 | static char readline_buf[RL_BUF_SIZE]; | ||
21 | |||
22 | // Clear buffer. | ||
23 | for (size_t i = 0; i < RL_BUF_SIZE; i++) { | ||
24 | readline_buf[i] = 0; | ||
25 | } | ||
26 | |||
27 | // Barebones readline implementation. | ||
28 | size_t n = 0; | ||
29 | char c; | ||
30 | while ((c = getchar()) != '\n') { | ||
31 | if (c == '\b') { | ||
32 | readline_buf[n] = '\0'; | ||
33 | n--; | ||
34 | } else if (((u8)c >= 0x20 && (u8)c <= 0x7F) && n < RL_BUF_SIZE) { | ||
35 | readline_buf[n] = c; | ||
36 | n++; | ||
37 | } | ||
38 | } | ||
39 | |||
40 | return (StringView){.start = (char *)&readline_buf, .n = n}; | ||
41 | } | ||
42 | |||
43 | void | ||
44 | display(StringView sv) { | ||
45 | if (sv.n != 0) { | ||
46 | sv_write(sv); | ||
47 | printf("\n"); | ||
48 | } | ||
49 | } | ||
50 | |||
51 | #define REPL_PROMPT "bdl> " | ||
52 | |||
53 | int | ||
54 | main(void) { | ||
55 | printf("BDL REPL (Press Ctrl-C to exit)\n"); | ||
56 | while (true) { | ||
57 | printf(REPL_PROMPT); | ||
58 | display(read_line()); | ||
59 | } | ||
60 | return 0; | ||
61 | } | ||
diff --git a/src/bootstrap/shorthand.h b/src/bootstrap/shorthand.h new file mode 100755 index 0000000..6fcb82c --- /dev/null +++ b/src/bootstrap/shorthand.h | |||
@@ -0,0 +1,37 @@ | |||
1 | #ifndef SHORTHAND_H | ||
2 | #define SHORTHAND_H | ||
3 | |||
4 | #include <assert.h> | ||
5 | #include <stdbool.h> | ||
6 | #include <stddef.h> | ||
7 | #include <stdint.h> | ||
8 | |||
9 | // | ||
10 | // This simple header just typedefs the basic C define types to a shorter name, | ||
11 | // loads the quality of life bool macro for _Bool and defines shorthand macros | ||
12 | // for byte sizes. | ||
13 | // | ||
14 | |||
15 | typedef uint8_t u8; | ||
16 | typedef uint16_t u16; | ||
17 | typedef uint32_t u32; | ||
18 | typedef uint64_t u64; | ||
19 | typedef int8_t s8; | ||
20 | typedef int16_t s16; | ||
21 | typedef int32_t s32; | ||
22 | typedef int64_t s64; | ||
23 | typedef volatile u8 vu8; | ||
24 | typedef volatile u16 vu16; | ||
25 | typedef volatile u32 vu32; | ||
26 | typedef volatile u64 vu64; | ||
27 | typedef volatile s8 vs8; | ||
28 | typedef volatile s16 vs16; | ||
29 | typedef volatile s32 vs32; | ||
30 | typedef volatile s64 vs64; | ||
31 | |||
32 | #define KB(N) ((u64)(N) * 1024) | ||
33 | #define MB(N) ((u64)KB(N) * 1024) | ||
34 | #define GB(N) ((u64)MB(N) * 1024) | ||
35 | #define TB(N) ((u64)GB(N) * 1024) | ||
36 | |||
37 | #endif // SHORTHAND_H | ||