From 96d27c2a3e1a0fa0878beb3f9cd02f4b4ed8fdbb Mon Sep 17 00:00:00 2001 From: Bad Diode Date: Fri, 8 Oct 2021 10:25:59 +0200 Subject: Initial commit w/ small readline echo function --- .gitignore | 1 + Makefile | 51 +++++++++++++++++++++++++++++++++++++++ README.md | 53 ++++++++++++++++++++++++++++++++++++++++ src/bootstrap/main.c | 61 +++++++++++++++++++++++++++++++++++++++++++++++ src/bootstrap/shorthand.h | 37 ++++++++++++++++++++++++++++ 5 files changed, 203 insertions(+) create mode 100755 .gitignore create mode 100755 Makefile create mode 100755 README.md create mode 100755 src/bootstrap/main.c create mode 100755 src/bootstrap/shorthand.h 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 @@ +.POSIX: +.SUFFIXES: + +# Source code location and files to watch for changes. +SRC_DIR := src/bootstrap +BUILD_DIR := build +SRC_MAIN := $(SRC_DIR)/main.c +WATCH_SRC := $(shell find $(SRC_DIR) -name "*.c" -or -name "*.s" -or -name "*.h") +INC_DIRS := $(shell find $(SRC_DIR) -type d) +INC_FLAGS := $(addprefix -I,$(INC_DIRS)) + +# Output executable. +TARGET := bdl +BIN := $(BUILD_DIR)/$(TARGET) + +# Compiler and linker configuration. +CC := cc +CFLAGS := -Wall -Wextra -pedantic +CFLAGS += $(INC_FLAGS) +LDFLAGS := +LDLIBS := +RELEASE_CFLAGS := -DNDEBUG -O2 +DEBUG_CFLAGS := -DDEBUG -O2 -g + +.PHONY: tools clean run + +# Setup debug/release builds. +# make clean && make DEBUG=0 +# make clean && make DEBUG=1 +DEBUG ?= 0 +ifeq ($(DEBUG), 1) + CFLAGS += $(DEBUG_CFLAGS) +else + CFLAGS += $(RELEASE_CFLAGS) +endif + +main: tools $(BUILD_DIR) $(ROM) $(BIN) + +$(BIN): $(SRC_MAIN) $(WATCH_SRC) + $(CC) $(CFLAGS) $(LDFLAGS) -o $(BIN) $(SRC_MAIN) $(LDLIBS) + +# Create build directory if needed. +$(BUILD_DIR): tools + mkdir -p $(BUILD_DIR) + +run: $(BIN) + ./$(BIN) + +# Remove build directory. +clean: + 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 @@ +# 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 goals for this project are to build a programming language that can be +interpreted directly from a VM and with support for compilation to assembly +(`x86_64` and/or `ARM (thumb or aarch64)`). It could make sense to output +bytecode for LLVM to take advantage of the built in optimizations, but let's +just go one step at a time. At the time I know some ARM assembly, but I'm not so +versed in `x86_64` and know nothing of LLVM bytecode. + +I've chosen to implement a Lisp, perhaps a subset of Scheme. The syntax is not +so important for now, maybe in the future the compiler will take a different +home-brew language, but hopefully this helps setting the fundamentals for +a minimal working compiler. In principle, we could keep the internal +representation and language working as a lisp, but with a different external +syntax. + +The language should have built-in structures for dynamic arrays, hash tables, +strings (and string views). It should be suitable for use in embedded systems +and be linked seamlessly with other compiled objects. + +Accessing system resources, such as stdio or graphics could be done via function +calls to the give APIs. This should help decouple the CPU logic from hardware, +hopefully facilitating porting programs to different platforms (GBA, Rasberry +Pi, etc.). + +The current plan is to build a bootstrap interpreter in C that can be used to +generate the self-hosted version of itself. I'll try to document the process +here as best as I can. + +The bootstrap implementation should be kept simple, since we can focus on +optimization once we have a self-hosting compiler. + +# 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] + +[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 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 @@ +#include + +#include "shorthand.h" + +typedef struct StringView { + char *start; + size_t n; +} StringView; + +void +sv_write(StringView sv) { + for (size_t i = 0; i < sv.n; i++) { + putchar(sv.start[i]); + } +} + +StringView +read_line(void) { + #define RL_BUF_SIZE 1024 + static char readline_buf[RL_BUF_SIZE]; + + // Clear buffer. + for (size_t i = 0; i < RL_BUF_SIZE; i++) { + readline_buf[i] = 0; + } + + // Barebones readline implementation. + size_t n = 0; + char c; + while ((c = getchar()) != '\n') { + if (c == '\b') { + readline_buf[n] = '\0'; + n--; + } else if (((u8)c >= 0x20 && (u8)c <= 0x7F) && n < RL_BUF_SIZE) { + readline_buf[n] = c; + n++; + } + } + + return (StringView){.start = (char *)&readline_buf, .n = n}; +} + +void +display(StringView sv) { + if (sv.n != 0) { + sv_write(sv); + printf("\n"); + } +} + +#define REPL_PROMPT "bdl> " + +int +main(void) { + printf("BDL REPL (Press Ctrl-C to exit)\n"); + while (true) { + printf(REPL_PROMPT); + display(read_line()); + } + return 0; +} 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 @@ +#ifndef SHORTHAND_H +#define SHORTHAND_H + +#include +#include +#include +#include + +// +// This simple header just typedefs the basic C define types to a shorter name, +// loads the quality of life bool macro for _Bool and defines shorthand macros +// for byte sizes. +// + +typedef uint8_t u8; +typedef uint16_t u16; +typedef uint32_t u32; +typedef uint64_t u64; +typedef int8_t s8; +typedef int16_t s16; +typedef int32_t s32; +typedef int64_t s64; +typedef volatile u8 vu8; +typedef volatile u16 vu16; +typedef volatile u32 vu32; +typedef volatile u64 vu64; +typedef volatile s8 vs8; +typedef volatile s16 vs16; +typedef volatile s32 vs32; +typedef volatile s64 vs64; + +#define KB(N) ((u64)(N) * 1024) +#define MB(N) ((u64)KB(N) * 1024) +#define GB(N) ((u64)MB(N) * 1024) +#define TB(N) ((u64)GB(N) * 1024) + +#endif // SHORTHAND_H -- cgit v1.2.1