summaryrefslogtreecommitdiff
path: root/trees/blog/mk-lisp-1.typ
diff options
context:
space:
mode:
Diffstat (limited to 'trees/blog/mk-lisp-1.typ')
-rw-r--r--trees/blog/mk-lisp-1.typ413
1 files changed, 413 insertions, 0 deletions
diff --git a/trees/blog/mk-lisp-1.typ b/trees/blog/mk-lisp-1.typ
new file mode 100644
index 0000000..1a71e7e
--- /dev/null
+++ b/trees/blog/mk-lisp-1.typ
@@ -0,0 +1,413 @@
+#import "html_elements.typ": post
+#show: post
+
+
+This is the second part of a series of articles that I'm writing to document by
+progress on building a Interpreter for myLisp, a lisp-like language. For the previous post [click
+here](/mk-lisp-0).
+
+
+
+== What is an interpreter?
+
+An Interpreter is a program that takes souce code as input and executes it. It
+is composed of several parts, today we are going to write a lexer and a parser.
+
+The lexer will read a string of characters and output a vector of tokens, with
+some information attached to them like its type. The lexer is important to the
+parser because it returns the soure code in a better representation, holding
+only information that matters to it, _(this is a very important pattern in
+programming, thowing away information that is not important for what we want, by
+keeping the data in a more convenient representation)_.
+
+The parser will take the vector of tokens created by the lexer and create a data
+structure _(in our case S-Expressions)_ which can then be executed by another part of the interpreter.
+
+== The interpreter's implementation
+
+I will be writing this interpreter in C. The most important reason for it is that
+this is a learning project more than anything else, and in C provides us with
+the bare minimum to create what we want.
+It is important to note that there are better ways to implement it, but I don't
+like to read other people's code before I try my own way. Maybe in the future when I'm done,
+I'll change it.
+
+== Lexer
+
+First, lets define a little macro to help us debug.
+
+```c
+#ifdef DEBUG_F
+
+#define DEBUG(fmt, args...) \
+ printf("(%s:%d) " fmt, __FILE__,__LINE__, ##args)
+
+#else
+
+#define DEBUG(f, fmt, args...) /* Do nothing */
+
+#endif
+
+```
+
+Next, we need to create a few data types to store the tokens.
+_As you can see our Lisp won't support strings and floats for now_.
+
+
+```c
+enum Token_Type {
+ TOKEN_OPEN=0,
+ TOKEN_CLOSE=1,
+ TOKEN_NUMBER=2,
+ TOKEN_SYMBOL=3,
+};
+
+/*
+** Used to debug the lexer
+*/
+char* Token_Type_Str[4] = {"(", ")", "NUM", "SYM"};
+
+typedef struct {
+ enum Token_Type type;
+
+ union {
+ int number;
+ char* name;
+ }data;
+
+}Token;
+```
+
+And then the tokenize fuction, there are a few details about it that need to be discussed.
+Usually in Lisp, symbol names can be in some written in some formats, like `+1, +$,
[email protected]`. But for simplicity's sake we have a different set of rules: They must start
+with an alphabetical character and not contain any whitespace or parenthesis.
+
+
+
+```c
+Token* tokenize(char* in, int* ret_sz) {
+ int cursor = 0;
+ int sz = 0, alloc=1;
+ Token* vec = (Token*) malloc(sizeof(Token));
+
+ while(in[cursor] != '\0') {
+
+ Token cur;
+
+ if(in[cursor]=='(') {
+ cur.type = TOKEN_OPEN;
+ cursor++;
+
+ } else if(in[cursor]==')') {
+ cur.type = TOKEN_CLOSE;
+ cursor++;
+
+ } else if(isdigit(in[cursor])) {
+ int number;
+ sscanf(in+cursor,"%d",&number);
+
+
+ while(in[cursor] != '\0'
+ && isdigit(in[cursor])) {
+ cursor++;
+ }
+
+ cur.type = TOKEN_NUMBER;
+ cur.data.number = number;
+ DEBUG("TOKEN_NUMBER: %d\n", number);
+
+ } else if(isalpha(in[cursor])) {
+
+ char* name = (char*) malloc(MAX_SYM_SZ);
+ assert(name!=NULL);
+
+ int ptr = 0;
+
+ while(in[cursor] != '('
+ && in[cursor] != ')'
+ && in[cursor] != ' '
+ && in[cursor] != '\0')
+ {
+
+ if(isalpha(in[cursor])) in[cursor] = toupper(in[cursor]);
+ name[ptr] = in[cursor];
+ ptr++, cursor++;
+ }
+
+ name[ptr] = '\0';
+
+ cur.type = TOKEN_SYMBOL;
+ cur.data.name = name;
+ DEBUG("TOKEN_NAME: %s\n", name);
+
+ } else {
+ cursor++;
+ continue;
+ }
+
+ if(alloc <= sz+1) {
+
+ alloc *= 2;
+ vec = (Token*) realloc(vec, sizeof(Token)*alloc);
+ }
+
+ DEBUG("TOKEN: %s\n", Token_Type_Str[cur.type]);
+
+ vec[sz++] = cur;
+ }
+
+ *ret_sz = sz;
+
+ return vec;
+}
+```
+
+And that's about it for the lexer.
+
+== Representing S-Expressions
+
+Before we start to implement the parser we need to write the data types for it.
+But this time it is a little bit different because the parser will generate a
+data structure which can be executed. We are going to represent those structures
+as lisp S-Expressions.
+
+First, let's define the type `Lisp_Object`, _(it has nothing to do with OOP's
+objects)_, which will represent everything that a cons cell can hold as its car
+or cdr.
+
+== Tagged Pointers
+
+There are a few ways that we could choose to represent `Lisp_Object`, we are
+going to use tagged pointers, which are common in many Lisp implementations.
+
+Every variable in C has at least 8 bits, so every valid pointer points to an
+address which is a multiple of 8. This means that the least significant bits of
+a valid address will aways end with three zeros. So we can use these bits to
+store additional information about what the pointer is pointing to. When we need
+to deference it we just mask out those three bits.
+
+They are useful because a pointer usually occupies eight bytes and an `int` or
+`float` just 4, so we can embed ints and floats into them, all we have to do is to
+shift them up three bits. That's a huge improvement over deferencing a pointer
+to an integer which is allocated on the heap. Using tagged pointers we can
+utilize ints and floats on the stack.
+
+
+Now, we will define a variable that will represent everything that a cons cell
+can hold as its car and cdr: `Lisp_Object`.
+
+```c
+typedef uintptr_t Lisp_Object;
+#define NIL (Lisp_Object)0;
+```
+
+`Lisp_Object` is a tagged pointer, that's why we used `uintptr_t` _(it is
+defined be a variable that can store a pointer)_. And now a few functions to
+operate on it.
+
+
+```c
+enum Tag {
+ TAG_SYMBOL = 0,
+ TAG_NUMBER = 1,
+ TAG_CONS = 2
+ /* ... */
+};
+
+Lisp_Object ptr_tag(Lisp_Object obj, enum Tag tag) {
+ return obj | (int)tag;
+}
+
+Lisp_Object ptr_untag(Lisp_Object obj) {
+ return obj & ~((Lisp_Object) 7);
+}
+
+int ptr_getTag(Lisp_Object obj) {
+ return (int)(obj&7);
+}
+
+```
+Those are the basic operations that we are going to be doing with them. But now we
+need a few helper functions and macros to help us create new objects.
+
+```c
+#define OBJ(val, type) \
+ Obj_New_ ## type (val)
+
+Lisp_Object Obj_New_symbol(char* str) {
+ char* nstr = (char*) malloc(sizeof(str));
+ strcpy(nstr, str);
+ Lisp_Object ret = ptr_tag((Lisp_Object)nstr, TAG_SYMBOL);
+
+ return ret;
+}
+
+Lisp_Object Obj_New_number(int val) {
+ Lisp_Object nval = val;
+ nval = val<<3;
+
+ return ptr_tag(nval, TAG_NUMBER);
+}
+
+typedef struct {
+
+ Lisp_Object car;
+ Lisp_Object cdr;
+
+}Lisp_Cons_Cell;
+
+Lisp_Object fcons(Lisp_Object a, Lisp_Object b) {
+ Lisp_Cons_Cell* cell = (Lisp_Cons_Cell*) malloc(sizeof(Lisp_Cons_Cell));
+ cell->car = a, cell->cdr = b;
+
+ return ptr_tag((Lisp_Object)&cell, TAG_CONS);
+}
+
+```
+
+`OBJ` is a little helper macro do help us create new objects. We use it like
+this:
+
+Lisp_Object a = OBJ("hello-there", symbol);
+Lisp_Object b = OBJ(42, number);
+
+I didn't write a `Obj_New_cons` because we will be using the fcons function to
+create new conses.
+
+== Printing S-Expressions
+Before we start the parser itself we need to create a function to print
+S-Expressions, in order to debug it. There's an algorithm for it but I won't get
+into detail. Here it is:
+
+```c
+void _Lisp_Print(Lisp_Object obj, int head);
+
+void Lisp_Print_cons(Lisp_Object obj, int head) {
+ if(head) putchar('(');
+
+ _Lisp_Print(fcar(obj), 1);
+
+ if(ptr_untag(fcdr(obj))==NIL) {
+ putchar(')');
+ } else if(ptr_getTag(fcdr(obj))!=TAG_CONS) {
+ printf(" . ");
+ _Lisp_Print(fcdr(obj), 0);
+ putchar(')');
+ } else {
+ putchar(' ');
+ _Lisp_Print(fcdr(obj), 0);
+ }
+}
+
+
+void _Lisp_Print(Lisp_Object obj, int head) {
+ enum Tag tag = ptr_getTag(obj);
+
+ switch(tag) {
+ case TAG_NUMBER:
+ printf("%d", GET_VAL(obj, number));
+ break;
+ case TAG_SYMBOL:
+ printf("%s", GET_VAL(obj, symbol));
+ break;
+ case TAG_CONS:
+ Lisp_Print_cons(obj, head);
+ break;
+ default:
+ break;
+ }
+}
+
+
+void Lisp_Print(Lisp_Object obj) {
+ _Lisp_Print(obj, 1);
+ putchar('\n');
+}
+
+```
+
+== The parser
+
+I really liked implementing a Lisp parser a for another interpreter a few days
+ago, the algorithm is so simple!
+
+If a S-Expression is a list, whe can think of it as a list of atoms and for each
+atom we parse it recursively. So, how do we parse a simple list? This is how it
+would like in ~~py~~pseudocode:
+
+def parse (n):
+obj = get_obj(n)
+
+if obj == nil:
+return obj
+
+else:
+return cons(obj, parse(n+1))
+
+
+It doesn't work for every S-Expression *yet*, but the main takeaway for it is that
+you cons the current object with the rest of the list recursively. The only
+difference between this and a complete parser is that the latter handles
+parenthesis by parsing what is inside the current block and consing it with the
+rest of the list.
+
+```c
+Lisp_Object parse(Token* tokens, int pos, int sz) {
+ if(pos==sz) return NIL; /* the stop condition */
+
+ if(tokens[pos].type == TOKEN_OPEN) {
+
+ Lisp_Object car = parse(tokens,pos+1,sz);
+
+ int aux = 1, balance = -1;
+
+ while(balance != 0) { /* Looking for the matching ) */
+
+ assert(aux+pos < sz);
+
+ if(tokens[pos+aux].type == TOKEN_OPEN)
+ balance--;
+ if(tokens[pos+aux].type == TOKEN_CLOSE)
+ balance ++;
+
+ aux++;
+ }
+
+ Lisp_Object cdr = parse(tokens, pos+aux, sz);
+
+ return fcons(car, cdr);
+
+ } else if(tokens[pos].type == TOKEN_CLOSE) {
+
+ return NIL;
+
+ } else if(tokens[pos].type == TOKEN_NUMBER) {
+
+ int n = tokens[pos].data.number;
+ Lisp_Object car = OBJ(n, number);
+
+ return fcons(car, parse(tokens, pos+1, sz));
+
+ } else if(tokens[pos].type == TOKEN_SYMBOL) {
+
+ char* str = tokens[pos].data.name;
+
+ Lisp_Object car = OBJ(str, symbol);
+ return fcons(car, parse(tokens, pos+1, sz));
+
+ }
+
+ return NIL;
+}
+
+```
+
+This code isn't that much different from the pseudocode that I've written
+before, the main difference is the parenthesis handling. The code for this
+article can be seen
+[here](https://github.com/gbrls/lisp-interpreter/blob/a15eb40743e64e9cc60c9e01474050ebf25b59ec/main.c).
+
+Every cons and symbol in which we allocate are not fred, so our interpreter is
+leaking memory. The solution for this is called garbage collection, we are going
+to implement it in a latter article.
generated by cgit v1.3 (git 2.53.0) at 2026-10-02 05:09:09 +0000