Sila Dev Log: Implementing Local Variables
Posted on 16th of November 2023 | 2834 words| Plug: Follow the Sila development here. |
I’ve been little bit slacking on the writing aspects of things but also little bit on the side of adding new features to the language as well. So much of my time have been spent on various bikeshedding topics. Although important work nonetheless. I won’t be writing too much about those cleanups and refactorings but you can follow the development of Sila from the link above.
After the bikeshedding, or yak-shaving, I got to writing new features such as initial implementation of the control flow for the language (conditionals and loops). So I could open a little bit on the development of those.
Before I started implementing either conditionals or loops, I wanted to
implement the ability to assign local variables, such as a := 0. Starting
with tokenization, I needed to differentiate somehow between identifiers and
reserved keywords. Starting with my tokenize, adding support for those was
simply adding following to it:
(defun tokenize (src)
"Generate tokens from the given source code."
(let* ((head (make-token))
(cur head)
(src-pos 0))
(macrolet ((gentoken (kind)
(let ((token-gen-fn (intern (format nil "GEN-~a-TOKEN" kind))))
`(multiple-value-bind (token pos)
(,token-gen-fn src src-pos)
(setf (token-next cur) token)
(setf cur (token-next cur))
(setf src-pos pos)))))
(loop :while (< src-pos (length src))
:do (cond
;; [...]
;; Ident or keyword
((alpha-char-p (char src src-pos))
(gentoken ident-or-keyword))
(t
(error 'lexer-error
:lexer-input src
:error-msg "Invalid token."
:token-pos src-pos)))))
;; No more tokens.
(setf (token-next cur) (make-token :kind :eof :position src-pos))
(setf cur (token-next cur))
(token-next head)))
Which basically checks that if the current character in the given source code
starts with a letter, it should be tokenized as either identifier or keyword.
I wrote a simple helper macro genmacro to cleanup some code, which when
called with something like (genmacro ident-or-keyword) would call function
gen-ident-or-keyword and inserts the generated token to the token list.
gen-ident-or-keyword itself looks like this:
(defvar *sila-keywords*
#("return" "if" "else" "for" "loop" "break"))
(defun gen-ident-or-keyword-token (src src-pos)
"Generate IDENT or KEYWORD token and return it and the SRC-POS to the next
token in SRC."
(flet ((keyword-lookup (input pos)
(let ((keyword-end (skip-to #'whitespacep input pos)))
;; Keyword not found
(when (null keyword-end)
(return-from keyword-lookup (values nil pos)))
(let ((keyword (subseq input pos keyword-end)))
(if (find keyword *sila-keywords* :test #'string=)
(values keyword
(skip-to #'(lambda (c) (not (whitespacep c)))
input keyword-end))
(values nil pos))))))
(multiple-value-bind (keyword next-token-pos)
(keyword-lookup src src-pos)
(let* ((punct-pos (skip-to #'punctuatorp src src-pos))
(token-len (cond (keyword (length keyword))
(punct-pos (- punct-pos src-pos))
(t (- (length src) src-pos))))
(token-val (if keyword
keyword
(trim-whitespace
(subseq src src-pos (+ src-pos token-len))))))
(setf src-pos (cond (keyword next-token-pos)
(punct-pos punct-pos)
(t (length src))))
(values (make-token :kind (if keyword :keyword :ident)
:value token-val
:length (length token-val)
:position src-pos)
src-pos)))))
Which is pretty straight-forward function that tries to tokenize something
like a := 0; into a following structure:
SILA/LEXER> (tokenize "a := 0;")
#S(TOKEN
:KIND :IDENT
:POSITION 2
:LENGTH 1
:VALUE "a"
:NEXT #S(TOKEN
:KIND :PUNCT
:POSITION 4
:LENGTH 2
:VALUE ":="
:NEXT #S(TOKEN
:KIND :NUM
:POSITION 6
:LENGTH 1
:VALUE "0"
:NEXT #S(TOKEN
:KIND :PUNCT
:POSITION 7
:LENGTH 1
:VALUE ";"
:NEXT #S(TOKEN
:KIND :EOF
:POSITION 7
:LENGTH 0
:VALUE ""
:NEXT NIL)))))
One thing I immediately noticed with my current tokenization setup was that if I wrote an identifier that start with a number, it would have been tokenized similarly to how rest of the numbers would get tokenized. Which of course wouldn’t work with identifiers. So I had to add a simple error handling in the number generation side to check if the identifier can’t start with numbers:
(defun gen-number-token (src src-pos)
"Generate token for NUMBER and return it and the SRC-POS to the next token in
SRC."
#| [...] |#
;; Idents starting with a letter will be caught with
;; a different conditional so if this is hit, ident
;; starts with a number but contains letters, which
;; isn't acceptable.
(unless (every #'digit-char-p token-val)
(error 'lexer-error
:lexer-input src
:error-msg "Ident can't start with a number."
:token-pos src-pos))
#| [...] |#)
This setup also handles keywords as intended, which naturally will be needed for the implementation of the control flow:
SILA/LEXER> (print-tokens (tokenize "{ a := 0; return a; }"))
#S(TOKEN :KIND PUNCT :POSITION 1 :LENGTH 1 :VALUE {)
#S(TOKEN :KIND IDENT :POSITION 4 :LENGTH 1 :VALUE a)
#S(TOKEN :KIND PUNCT :POSITION 6 :LENGTH 2 :VALUE :=)
#S(TOKEN :KIND NUM :POSITION 8 :LENGTH 1 :VALUE 0)
#S(TOKEN :KIND PUNCT :POSITION 9 :LENGTH 1 :VALUE ;)
#S(TOKEN :KIND KEYWORD :POSITION 17 :LENGTH 6 :VALUE return)
#S(TOKEN :KIND IDENT :POSITION 18 :LENGTH 1 :VALUE a)
#S(TOKEN :KIND PUNCT :POSITION 19 :LENGTH 1 :VALUE ;)
#S(TOKEN :KIND PUNCT :POSITION 21 :LENGTH 1 :VALUE })
#S(TOKEN :KIND EOF :POSITION 21 :LENGTH 0 :VALUE )
; No value
Parsing side of things is little bit more involved on the other hand. I started the implementation with writing following structures:
(defstruct (ast-node-variable
(:include ast-node)
(:copier nil))
(object (util:required 'object) :type object :read-only t))
(defstruct (object
(:copier nil))
(name (util:required 'name) :type string :read-only t)
(offset 0 :type integer)
(next nil :type t))
(defstruct (ast-node-assign
(:include ast-node)
(:copier nil))
(var (util:required 'var) :type ast-node-variable :read-only t)
(expr (util:required 'expr) :type t :read-only t))
Parsing the variables and assign statements then looks like this:
(defun parse-assign-node (tok)
(let (node)
(multiple-value-bind (eql-node rest)
(parse-equality-node tok)
(setf node eql-node
tok rest))
(when (string= (lex:token-value tok) ":=")
(multiple-value-bind (expr-node rest)
(parse-assign-node (lex:token-next tok))
(setf node (make-ast-node-assign :var node
:expr expr-node)
tok rest)))
(values node tok)))
;;; [...]
(defvar *local-variables* nil
"Global variable for holding local variable objects.")
(defun parse-primary-node (tok)
(cond
#| [...] |#
((eq (lex:token-kind tok) :ident)
(let* ((name (lex:token-value tok))
(var (find-local-var name)))
(when (null var)
(setf var (make-object :name name :next *local-variables*))
;; New object should be in front of the list.
(setf *local-variables* var))
(values (make-ast-node-variable :object var)
(lex:token-next tok))))
#| [...] |#
(t (error "Unexpected token value: ~a" tok))))
Since I’m using recursive descent parsing, parsing the variable node happens
via the equality parsing function which trickles down all the way to primary
node. Again relatively straight forward parsing here. One thing to worth
noting is how I save all the local variables to separate variable called
*local-variables*. This is mainly for the fact that when it comes to code
generation I need to save the fixed offsets in the memory for each variable in
use. So I need to know all the variables that I have parsed. There is probably
bunch of optimizations that could be done, but for now, I’m not interested in
those.
Setting those variable offsets happens after the whole program has been parsed:
(defstruct (func
(:copier nil))
(body (util:required 'body) :type t :read-only t)
(locals (util:required locals) :type t :read-only t)
(stack-size 0 :type integer))
;;; [...]
(defun parse-program (tok)
(labels ((align-to (n align)
"Round N to the nearest multiple of ALIGN."
(* (ceiling n align) align))
(set-lvar-offsets (program)
(let ((offset 0))
(loop :for obj := (func-locals program)
:then (setf obj (object-next obj))
:until (null obj)
:do (progn
(incf offset 8)
(setf (object-offset obj) (- offset))))
(setf (func-stack-size program) (align-to offset 16)))
(values)))
(let* ((head (make-ast-node))
(cur head))
(loop :until (eq (lex:token-kind tok) :eof)
:do (multiple-value-bind (node rest)
(parse-statement-node tok)
(setf (ast-node-next cur) node)
(setf cur (ast-node-next cur))
(setf tok rest)))
(let ((program (make-func :body (ast-node-next head)
:locals *local-variables*)))
(set-lvar-offsets program)
program))))
And that’s about for tokenization and parsing. When parsing a program with local variables it should look something like this:
SILA/PARSER> (parse-program (lex:tokenize "{ a := 0; return a; }"))
#S(FUNC
:BODY #S(AST-NODE-BLOCK
:NEXT NIL
:BODY #S(AST-NODE-EXPRESSION
:NEXT #S(AST-NODE-RETURN
:NEXT NIL
:EXPR #S(AST-NODE-VARIABLE
:NEXT NIL
:OBJECT #S(OBJECT
:NAME "a"
:OFFSET -8
:NEXT NIL)))
:EXPR #S(AST-NODE-ASSIGN
:NEXT NIL
:VAR #S(AST-NODE-VARIABLE
:NEXT NIL
:OBJECT #S(OBJECT
:NAME "a"
:OFFSET -8
:NEXT NIL))
:EXPR #S(AST-NODE-INTEGER-LITERAL
:NEXT NIL
:VALUE 0))))
:LOCALS #S(OBJECT :NAME "a" :OFFSET -8 :NEXT NIL)
:STACK-SIZE 16)
Finally, we can proceed to the code generation aspects!
To implement local variables with x86 assembly language, we need to write epilogue and prologue for our function (currently only main function) which prepares the stack for use within the function. These will look like this:
; Prologue push %rbp mov %rsp, %rbp sub STACK_SIZE, %rsp ; Epilogue mov %rbp, %rsp pop %rbp ret
So what’s happening here:
-
Prologue:
push %rbp: Saves the value of the base pointer register (%rbp) onto the stack.mov %rsp, %rbp: Sets the value of the stack pointer (%rsp) as the new base pointer (%rbp).sub STACK_SIZE, %rsp: Allocates space on the stack for local variables by subtracting a amount required by our local variables (STACK_SIZE, calculated above) from the stack pointer (%rsp).
-
Epilogue:
mov %rbp, %rsp: Restores the stack pointer to its original value by copying the value of the base pointer back to the stack pointer.pop %rbp: Restores the original value of the base pointer by popping it from the stack.ret: Returns control flow back to the calling function.
in x86, similar thing could be achieved with
enterandleaveinstructions but they do little bit more than just pushing/popping and moving. So I might start using those at some point if the prologue and epilogue starts to get more complicated. For now, this raw assembly is good enough for me.
So, if we want to write generate x86-64 code for the code we have above ({ a := 0; return a; }), we have to write the following assembly:
.globl main main: ; Prologue push %rbp mov %rsp, %rbp sub $16, %rsp ; Saving 'a' to an address offset relative to the base pointer. lea -8(%rbp), %rax push %rax mov $0, %rax pop %rdi mov %rax, (%rdi) ; Calculating the address offset of 'a' and moving it to rax for return. lea -8(%rbp), %rax mov (%rax), %rax ; Epilogue mov %rbp, %rsp pop %rbp ret
Again, this code could be cleaned up and optimized quite a bit and doesn’t need to be so involved with simple code like this, but I’m leaving the code generation optimizations tasks for future me.
With the code above, we now have a great test for starting to implement the code generation itself. In that, with the AST tree that we generated above, generating code for it is also pretty trivial:
(defun generate-expression (node)
"Recursively generate the x86-64 assembly code."
(flet ((lea (node)
"Load effective address"
(format nil "lea ~d(%rbp), %rax"
(parser:object-offset
(parser:ast-node-variable-object node)))))
(let ((insts (make-inst-array)))
(cond
#| [...] |#
((parser:ast-node-variable-p node)
(vector-push-extend (lea node) insts)
(vector-push-extend "mov (%rax), %rax" insts)
insts)
((parser:ast-node-assign-p node)
(vector-push-extend (lea (parser:ast-node-assign-var node)) insts)
(vector-push-extend (asm-push) insts)
(do-vector-push-inst (generate-expression
(parser:ast-node-assign-expr node)) insts)
(vector-push-extend (asm-pop "rdi") insts)
(vector-push-extend "mov %rax, (%rdi)" insts)
insts)
#| [...] |#))))
So the code above essentially is for the following assembly code:
lea OFFSET(%rbp), %rax push %rax mov VALUE, %rax pop %rdi mov %rax, (%rdi)
In case we want to return the value we need to do the following:
(defun generate-statement (node)
(let ((insts (make-inst-array)))
(cond
#| [...] |#
((parser:ast-node-return-p node)
(do-vector-push-inst (generate-expression
(parser:ast-node-return-expr node)) insts)
(vector-push-extend "jmp .L.return" insts)
insts)
#| [...] |#)))
Which is for generating assembly code for statement like return <expr>;.
Here I decided the use jmp jmp .L.return, so in case I would write an
return statement deeply nested in other statements, like if or for etc.,
I could just exit early from those and jump directly to the epilogue.
So printing the whole program might look something like this:
(defun emit-code (src &key (stream nil) (indent 2) (indent-tabs t))
"Emit assembly code from given source code. Currently emits only x86-64 and
only Linux is tested."
;; Init environment
(setf parser:*local-variables* nil
*stack-depth* 0
*label-count* 0)
(let ((indent (if indent-tabs
#\Tab
(coerce (make-list indent
:initial-element #\Space)
'string))))
(let ((program (parser:parse-program (lex:tokenize src))))
;; TODO(topi): these instructions probably should be collected to some
;; structure so they can be divided in to sections more easily when the
;; programs become more complex.
(format stream
"~{~a~%~}"
(alexandria:flatten
(list
;; ASM Directive
(format nil "~a.globl main" indent)
;; Main Label
"main:"
;; Prologue
(format nil "~apush %rbp" indent)
(format nil "~amov %rsp, %rbp" indent)
(format nil "~asub $~a, %rsp" indent
(parser:func-stack-size program))
;; ASM Routine
(loop :for inst
:across (generate-statement (parser:func-body program))
:collect (if (string= (subseq inst 0 3) ".L.")
;; If instruction is label (.L. prefix),
;; don't indent it.
inst
(format nil "~a~a" indent inst)))
;; Return label
".L.return:"
;; Epilogue
(format nil "~amov %rbp, %rsp" indent)
(format nil "~apop %rbp" indent)
;; Return
(format nil "~aret" indent)))))))
Parameters
stream,indentandindent-tabsare not needed for the functionality of code generation itself, but they are just used here as helpers.
With that we can write a couple of test to see that programs actually work as intended:
(deftest test-compilation-and-compare-rc
(testing "Integer"
(ok (compile-program-and-compare-rc "{ return 0; }" 0))
(ok (compile-program-and-compare-rc "{ ;;;;; return 1; }" 1)))
(testing "Arithmetics"
(ok (compile-program-and-compare-rc "{ return 5 + 40 - 20; }" 25))
(ok (compile-program-and-compare-rc "{ return 2 / (1 + 1) * 8; }" 8)))
(testing "Unary"
(ok (compile-program-and-compare-rc "{ return - -10; }" 10))
(ok (compile-program-and-compare-rc "{ return -10+20; }" 10)))
(testing "Comparisons"
(ok (compile-program-and-compare-rc "{ return 0==1; }" 0))
(ok (compile-program-and-compare-rc "{ return 1!=1; }" 0))
(ok (compile-program-and-compare-rc "{ return 0==0; }" 1))
(ok (compile-program-and-compare-rc "{ return 1!=0; }" 1))
(ok (compile-program-and-compare-rc "{ return 0<1; }" 1))
(ok (compile-program-and-compare-rc "{ return 1<1; }" 0))
(ok (compile-program-and-compare-rc "{ return 1<=1; }" 1))
(ok (compile-program-and-compare-rc "{ return 2<=1; }" 0))
(ok (compile-program-and-compare-rc "{ return 0<1; }" 1))
(ok (compile-program-and-compare-rc "{ return 1<1; }" 0))
(ok (compile-program-and-compare-rc "{ return 1>=1; }" 1))
(ok (compile-program-and-compare-rc "{ return 1>=2; }" 0)))
(testing "Multiple statements"
(ok (compile-program-and-compare-rc "{ return 1; 2; 3; }" 1))
(ok (compile-program-and-compare-rc "{ 1; return 2; 3; }" 2))
(ok (compile-program-and-compare-rc "{ 1; 2; return 3; }" 3)))
(testing "Variables"
(ok (compile-program-and-compare-rc "{ a:=8; return a; }" 8))
(ok (compile-program-and-compare-rc "{ a:=3; b:=5; return a+b; }" 8))
(ok (compile-program-and-compare-rc "{ foo:=3; bar:=5; return foo+bar; }" 8))
(ok (compile-program-and-compare-rc "{ foo2:=3; bar2:=5; return foo2+bar2; }" 8)))
(testing "Block"
(ok (compile-program-and-compare-rc "{ 1; { 2; } return 3; }" 3))))
Testing System sila/tests
;; testing 'sila/tests/compiler'
test-compilation-and-compare-rc
Integer
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ return 0; }" 0) to be true. (492ms)
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ ;;;;; return 1; }" 1) to be true. (441ms)
Arithmetics
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ return 5 + 40 - 20; }" 25) to be true. (423ms)
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ return 2 / (1 + 1) * 8; }" 8) to be true. (431ms)
Unary
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ return - -10; }" 10) to be true. (419ms)
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ return -10+20; }" 10) to be true. (454ms)
Comparisons
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ return 0==1; }" 0) to be true. (476ms)
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ return 1!=1; }" 0) to be true. (483ms)
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ return 0==0; }" 1) to be true. (470ms)
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ return 1!=0; }" 1) to be true. (491ms)
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ return 0<1; }" 1) to be true. (496ms)
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ return 1<1; }" 0) to be true. (487ms)
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ return 1<=1; }" 1) to be true. (474ms)
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ return 2<=1; }" 0) to be true. (498ms)
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ return 0<1; }" 1) to be true. (503ms)
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ return 1<1; }" 0) to be true. (502ms)
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ return 1>=1; }" 1) to be true. (471ms)
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ return 1>=2; }" 0) to be true. (418ms)
Multiple statements
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ return 1; 2; 3; }" 1) to be true. (433ms)
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ 1; return 2; 3; }" 2) to be true. (426ms)
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ 1; 2; return 3; }" 3) to be true. (441ms)
Variables
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ a:=8; return a; }" 8) to be true. (432ms)
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ a:=3; b:=5; return a+b; }" 8) to be true. (454ms)
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ foo:=3; bar:=5; return foo+bar; }" 8) to be true. (467ms)
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC
"{ foo2:=3; bar2:=5; return foo2+bar2; }" 8) to be true. (452ms)
Block
✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "{ 1; { 2; } return 3; }" 3) to be true. (427ms)
;; testing 'sila/tests/codegen'
test-codegen-x86-64
Integer
✓ { return 0; }
✓ { return 42; }
Add and subtraction
✓ { return 5+20-4; }
✓ { return 5 + 20 - 4 ; }
Division and multiplication
✓ { return 2 / (1 + 1) * 8; }
Unary
✓ { return - -10; }
✓ { return -10+20; }
✓ { return - - -10; }
Comparison
✓ { return 1==1; }
✓ { return 1>=1; }
✓ { return 1<=1; }
✓ { return 1<1; }
✓ { return 1>1; }
Multiple statements
✓ { return 1;2;3; }
✓ { 1;return 2;3; }
✓ { 1;2;return 3; }
Variables
✓ { a:=8;return a; }
✓ { foo:=5;bar:=8;return foo+bar; }
Block
✓ { 1; { 2; } return 3; }
✓ 1 test completed
Summary:
All 1 test passed.
He-hey! Tests seemed to pass! Until next time!
| NB: If you want to read earlier posts of this dev log, head over here. |