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:

in x86, similar thing could be achieved with enter and leave instructions 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, indent and indent-tabs are 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.