grass.grass

## The Grass Compiler
#
# This file contains a compiler for Grass, written in Grass. Use it like this:
#
# input stack:   pointer length  (this should point to Grass source code)
# output stack:  pointer length  (this points to compiled Ground code)
#
# The compiler allocates new memory for the output, but doesn't free the input.

## A Refresher on Grass
#
# Grass stands for Ground assembly (because I use it to write Ground byte code),
# but really it's encoding agnostic. The compiler goes through the file, turning
# names into bytes. It's somewhat similar to Forth, but also not really.
#
# - The 255 names "00" to "ff" are predefined, each stands for a single byte.
# - You can define new names using:
#   - A colon (:) to start a definition.
#   - The name to be defined.
#   - The names making up the definition (forward references allowed, but please
#     avoid cycles).
#   - A semicolon (;) to end the definition.
# - You can use @label outside of definitions to define a label. Every reference
#   ^label (allowed in definitions) then gets replaced by the absolute offset of
#   the corresponding label (64-bits, little endian encoded).

jump ^main

: . ; # Allows me to use dots for aligning code, like on a restaurant menu.

## Instructions
#
# I don't want to have to remember the opcodes, so here are aliases/mnemonics.

# mnemonic          opcode    immediates            data stack
: nop . . . . . . . . . 00 ;#                     |               ->
: add . . . . . . . . . a0 ;#                     |       a:8 b:8 -> (a+b):8
: subtract  . . . . . . a1 ;#                     |       a:8 b:8 -> (a-b):8
: multiply  . . . . . . a2 ;#                     |       a:8 b:8 -> (a*b):8
: divide  . . . . . . . a3 ;#                     |       a:8 b:8 -> (a/b):8
: modulo  . . . . . . . a4 ;#                     |       a:8 b:8 -> (a%b):8
: compare_zero  . . . . a5 ;#                     |           a:8 -> ordering:1
: and . . . . . . . . . b0 ;#                     |       a:8 b:8 -> (a&b):8
: or  . . . . . . . . . b1 ;#                     |       a:8 b:8 -> (a|b):8
: xor . . . . . . . . . b2 ;#                     |       a:8 b:8 -> (a^b):8
: shift_left  . . . . . b3 ;#                     |       a:8 b:8 -> (a<<b):8
: shift_right . . . . . b4 ;#                     |       a:8 b:8 -> (a>>b):8
: lower_byte  . . . . . b5 ;#                     |           a:8 -> a:1
: byte_to_word  . . . . b6 ;#                     |           a:1 -> a:8
: push_padding  . . . . c0 ;#                     |           n:1 -> _:n
: push_byte . . . . . . c1 ;# a:1                 |               -> a:1
: push_word . . . . . . c2 ;# a:8                 |               -> a:8
: push_byte_from_stack  c3 ;# offset:8            |               -> byte:1
: push_word_from_stack  c4 ;# offset:8            |               -> word:8
: pop . . . . . . . . . c5 ;# amount:1            |      _:amount ->
: pop_below_top . . . . c6 ;# a:8 b:1             |    _:b kept:a -> kept:a
: malloc_word_aligned . d0 ;#                     |        size:8 -> ptr:8
: free_word_aligned . . d1 ;#                     |  ptr:8 size:8 ->
: store_byte  . . . . . d2 ;#                     |     ptr:8 b:1 ->
: store_word  . . . . . d3 ;#                     |     ptr:8 w:8 ->
: load_byte . . . . . . d4 ;#                     |         ptr:8 -> b:1
: load_word . . . . . . d5 ;#                     |         ptr:8 -> w:8
: store_bytes . . . . . d6 ;# len:8 b:len         |         ptr:8 ->
: malloc_byte_aligned . d7 ;#                     |        size:8 -> ptr:8
: free_byte_aligned . . d8 ;#                     |  ptr:8 size:8 ->
: crash . . . . . . . . e0 ;#                     |   ptr:8 len:8 -> CRASH
: jump  . . . . . . . . f0 ;# target:8            |               ->
: jump_table  . . . . . f1 ;# len:1 targets:8*len |   b:1 ->
: call  . . . . . . . . f2 ;# target:8            |               ->
: push_indirect . . . . f3 ;# target:8            |               -> fun:8
: call_indirect . . . . f4 ;# pop:1               |   _:pop fun:8 ->
: return  . . . . . . . f5 ;#                     |               ->

## Decimal Words
#
# In some places, Ground expects little-endian numbers. Writing those by hand is
# tedious, so I did it only once here and re-use those below.

: $-1  ff ff ff ff ff ff ff ff ;
: $0   00 00 00 00 00 00 00 00 ;
: $1   01 00 00 00 00 00 00 00 ;
: $3   03 00 00 00 00 00 00 00 ;
: $7   07 00 00 00 00 00 00 00 ;
: $8   08 00 00 00 00 00 00 00 ;
: $15  0f 00 00 00 00 00 00 00 ;
: $16  10 00 00 00 00 00 00 00 ;
: $22  16 00 00 00 00 00 00 00 ;
: $24  18 00 00 00 00 00 00 00 ;
: $28  1c 00 00 00 00 00 00 00 ;
: $29  1d 00 00 00 00 00 00 00 ;
: $32  20 00 00 00 00 00 00 00 ;
: $33  21 00 00 00 00 00 00 00 ;
: $40  28 00 00 00 00 00 00 00 ;
: $48  30 00 00 00 00 00 00 00 ;
: $56  38 00 00 00 00 00 00 00 ;

## Character and String Constants
#
# Grass doesn't have string literals. Unlike those high-level developers writing
# code using their fancy-pants sophisticated assemblers, _real_ developers start
# by defining their ASCII literals and string constants by hand.

: 'newline     0a ;
: 'space       20 ; : '_ space ;
: 'quote       22 ;# "
: 'octothorpe  23 ;# #
: 'colon       3a ;# :
: 'semicolon   3b ;# ;
: 'at          40 ;# @
: 'tick        60 ;# ^

: '0 30 ; : '2 32 ; : '4 34 ; : '6 36 ; : '8 38 ;
: '1 31 ; : '3 33 ; : '5 35 ; : '7 37 ; : '9 39 ;

: 'a 61 ; : 'e 65 ; : 'i 69 ; : 'm 6d ; : 'q 71 ; : 'u 75 ; : 'y 79 ;
: 'b 62 ; : 'f 66 ; : 'j 6a ; : 'n 6e ; : 'r 72 ; : 'v 76 ; : 'z 7a ;
: 'c 63 ; : 'g 67 ; : 'k 6b ; : 'o 6f ; : 's 73 ; : 'w 77 ;
: 'd 64 ; : 'h 68 ; : 'l 6c ; : 'p 70 ; : 't 74 ; : 'x 78 ;

# Todo: Rethink life choices.
: '":"         'quote 'colon 'quote ;
: '";"         'quote 'semicolon 'quote ;
: 'definition  'd 'e 'f 'i 'n 'i 't 'i 'o 'n ;
: 'defined     'd 'e 'f 'i 'n 'e 'd ;
: 'error:_     'e 'r 'r 'o 'r 'colon '_ ;
: 'ends        'e 'n 'd 's ;
: 'has         'h 'a 's ;
: 'in          'i 'n ;
: 'is          'i 's ;
: 'multiple    'm 'u 'l 't 'i 'p 'l 'e ;
: 'name        'n 'a 'm 'e ;
: 'never       'n 'e 'v 'e 'r ;
: 'no          'n 'o ;
: 'not         'n 'o 't ;
: 'of          'o 'f ;
: 'oom         'o 'o 'm ;
: 'outside     'o 'u 't 's 'i 'd 'e ;
: 'times       't 'i 'm 'e 's ;

# Now, finally, we get to phrases.
: 'error:_":"_in_definition          'error:_ '":" '_ 'in '_ 'definition ;
: 'error:_";"_outside_of_definition  'error:_ '";" '_ 'outside '_ 'of '_
                                     'definition ;
: 'error:_definition_has_no_name     'error:_ 'definition '_ 'has '_ 'no '_
                                     'name ;
: 'error:_definition_never_ends      'error:_ 'definition '_ 'never '_ 'ends ;
: '_is_defined_multiple_times        '_ 'is '_ 'defined '_ 'multiple '_ 'times ;
: '_is_not_defined                   '_ 'is '_ 'not '_ 'defined ;

## Higher Level Instructions
#
# Writing a lot of low-level stuff is cumbersome. Take this piece of assembly:
#
# push_word $2
# push_word $3
# add
#
# In order to keep my sanity, I try to keep my assembly concatenative, just like
# Forth or other stack-based programming languages. In Forth, you can write code
# like this:
#
# 2 3 +
#
# My plan to get a Forth-like feel in here and to keep my sanity:
#
# - Number literals push their value to the stack. To disambiguate them from the
#   predefined byte literals, they use an underscore prefix.
# - I use short names and symbols for operations, like "+" instead of "add".
# - Many little helper functions such as "dup" or "swap" make managing the stack
#   bearable.
# - All values on the stack are one word (8 bytes) in size. This includes bools,
#   chars, and strings. Numbers in operations are given in word-amounts: Instead
#   of "push_word_from_stack $16", I write "over2".
# - I avoid postfix arguments whenever possible, even if that implies creating a
#   couple of hardcoded operations. For example, instead of using "pop 08" in my
#   code in multiple places, I define "pop1" and use that consistently. A visual
#   unit in the code (a name) usually corresponds to a semantic unit. Sometimes,
#   this is not possible; for example, an "if" expects postfix labels.
# - I put multiple operations on the same line to keep my code more consise, but
#   I use two spaces between them. This way, I can distinguish postfix arguments
#   from runs of operations.
# - I define names for operations, even if those just do "call ^operation".
# - I document how operations affect the stack. For example, "0?" has the effect
#   (int -> bool).
# - Sometimes I document the current state of the stack in comments.

: _-1          push_word $-1 ;                                         #( -> -1)
: _0           push_word $0 ;                                           #( -> 0)
: _1           push_word $1 ;                                           #( -> 1)
: _3           push_word $3 ;                                           #( -> 3)
: _7           push_word $7 ;                                           #( -> 7)
: _8           push_word $8 ;                                           #( -> 8)
: _15          push_word $15 ;                                         #( -> 15)
: _16          push_word $16 ;                                         #( -> 16)
: _22          push_word $22 ;                                         #( -> 22)
: _24          push_word $24 ;                                         #( -> 24)
: _28          push_word $28 ;                                         #( -> 28)
: _29          push_word $29 ;                                         #( -> 29)
: _32          push_word $32 ;                                         #( -> 32)
: _33          push_word $33 ;                                         #( -> 33)
: _40          push_word $40 ;                                         #( -> 40)
: _48          push_word $48 ;                                         #( -> 48)
: _56          push_word $56 ;                                         #( -> 56)
: true         push_word $1 ;                                        #( -> bool)
: false        push_word $0 ;                                        #( -> bool)
: dup          push_word_from_stack $0  ;                            #(a -> a a)
: over         push_word_from_stack $8  ;                        #(a b -> a b a)
: over2        push_word_from_stack $16 ;                    #(a b c -> a b c a)
: over3        push_word_from_stack $24 ;                #(a b c d -> a b c d a)
: over4        push_word_from_stack $32 ;            #(a b c d e -> a b c d e a)
: over5        push_word_from_stack $40 ;        #(a b c d e f -> a b c d e f a)
: pop1         pop 08 ;                                                 #(a -> )
: pop2         pop 10 ;                                               #(a b -> )
: pop3         pop 18 ;                                             #(a b c -> )
: pop4         pop 20 ;                                           #(a b c d -> )
: keep1_pop1   pop_below_top $8 08 ;                                 #(a b -> b)
: keep2_pop1   pop_below_top $16 08 ;                            #(a b c -> b c)
: keep2_pop3   pop_below_top $16 18 ;                          #(a b c d -> c d)
: swap         call ^swap ; @swap  over  keep2_pop1  return        #(a b -> b a)
: +            add ;                                           #(int int -> int)
: -            subtract ;                                      #(int int -> int)
: *            multiply ;                                      #(int int -> int)
: /            divide ;                                        #(int int -> int)
: +1           _1  + ;                                             #(int -> int)
: +8           _8  + ;                                             #(int -> int)
: +16          _16  + ;                                            #(int -> int)
: +24          _24  + ;                                            #(int -> int)
: +32          _32  + ;                                            #(int -> int)
: *2           _1  << ;                                            #(int -> int)
: *8           _3  << ;                                            #(int -> int)
: /8           _3  >> ;                                            #(int -> int)
: <<           shift_left ;                                    #(int int -> int)
: >>           shift_right ;                                   #(int int -> int)
: compare      -  compare_zero  byte_to_word ;                     #(a b -> ord)
: not          call ^not ;  @not  _1  swap  -  return            #(bool -> bool)
: !=           call ^neq ;                                        #(a b -> bool)
               @neq  compare  _3  over  >>  _1  and  lower_byte  return
: ==           call ^eq ;  @eq  !=  not  return                   #(a b -> bool)
: 0?           _0 == ;                                            #(int -> bool)
: <0?          compare_zero  byte_to_word  _1  >> ;               #(int -> bool)
: at?          push_byte 'at          byte_to_word  == ;         #(char -> bool)
: colon?       push_byte 'colon       byte_to_word  == ;         #(char -> bool)
: newline?     push_byte 'newline     byte_to_word  == ;         #(char -> bool)
: semicolon?   push_byte 'semicolon   byte_to_word  == ;         #(char -> bool)
: space?       push_byte 'space       byte_to_word  == ;         #(char -> bool)
: tick?        push_byte 'tick        byte_to_word  == ;         #(char -> bool)
: octothorpe?  push_byte 'octothorpe  byte_to_word  == ;         #(char -> bool)
: if           not  if_not ;                    # Usage: bool if ^then ^else
: if_not       jump_table 02 ;                  # Usage: bool if_not ^then ^else
: malloc       call ^malloc ;                                     #(size -> ptr)
               @malloc       malloc_word_aligned
                             dup  0?  if ^malloc.oom ^malloc.yeah
               @malloc.yeah  return
               @malloc.oom   _3  malloc_byte_aligned  # allocate for "oom"
                             dup  0?  if ^malloc.shit ^malloc.meh
               @malloc.shit  _0  _0  crash  # we can't even get three bytes -_-
               @malloc.meh   dup  store_bytes $3 'oom  _3  crash
: free         free_word_aligned ;                                    #(ptr -> )
: load         load_word ;                                        #(ptr -> word)
: store        store_word ;                                      #(ptr word -> )
: loadb        load_byte  byte_to_word ;                          #(ptr -> byte)
: storeb       lower_byte  store_byte ;                          #(ptr byte -> )
: memcopy      call ^memcopy ;                             #(from to amount -> )
               @memcopy       _0
               @memcopy.loop  over  over  ==  if ^@memcopy.done ^memcopy.copy
               @memcopy.copy  over2  over  +  over4  over2  +
                              load_byte  store_byte  +1  jump ^memcopy.loop
               @memcopy.done  pop4  return

## Data Structures
#
# Because this Grass compiler is just used for bootstrapping, execution speed is
# not the bottleneck. Instead, I  mostly struggle with implementation complexity
# given the limited expressiveness of the code. This results in cool, if unusual
# tradeoffs.
#
# First of all: Pointer indirections are great! All pointers have the same size,
# so keeping everything as pointers (or other word-sized values) makes it easier
# to reason about the code.
#
# While I'm not generally a fan of data structures inheriting behavior or state,
# it makes things sooo much easier here:
#
# - A string is a pointer to a tuple ( ptr | len ). The ptr points to the bytes,
#   the len is the length in bytes.
# - A growable buffer is a pointer to a tuple ( ptr | len | cap ). Operations on
#   strings also work on buffers, since they have a compatible memory layout!
# - A list (of word-sized items) is a buffer where the len and cap are multiples
#   of 8.
# - A dictionary from strings to words is a list containing alternating items of
#   keys and values: ( key | value | key | value | ... ). As runtime performance
#   is not really a limitation, dictionaries use a linear search for lookup.

# String stuff
: make_str    call ^make_str ;                                 #(ptr len -> str)
              @make_str  _16  malloc  dup  over3  ptr=
                         keep2_pop1  swap  len=  return
: clone_str   call @clone_str ;                                    #(str -> str)
              @clone_str  dup  ptr  swap  len  make_str  return
: free_str    _16  free ;                                              #(str ->)
              # Note that this does not free the bytes,
              # only the str object.
: ptr         load ;                                               #(str -> ptr)
: ptr=        store ;                                             #(str ptr -> )
: len         +8  load ;                                           #(str -> len)
: len=        swap  +8  swap  store ;                             #(str len -> )
: empty?      len  0? ;                                           #(str -> bool)
: str==       call ^streq ;                                   #(str str -> bool)
              @streq             over  len  over  len  ==
                                 if ^streq.len_same ^streq.len_diff
              @streq.len_diff    pop2  false  return
              @streq.len_same    swap  ptr  swap  dup  ptr  swap  len  _0
              @streq.loop        # (a_ptr b_ptr len cursor)
                                 over  over  ==  if ^streq.done ^streq.cmp_bytes
              @streq.cmp_bytes   over3  over   +  loadb
                                 over3  over2  +  loadb
                                 ==  if ^streq.bytes_same ^streq.bytes_diff
              @streq.bytes_same  +1  jump ^streq.loop
              @streq.bytes_diff  pop4  false  return
              @streq.done        pop4  true   return
: first_char  ptr  loadb ;                                        #(str -> char)
: trim_first  dup  ptr  +1  ptr= ;                                    #(str -> )

# Buffer stuff
: make_buf   call ^make_buf ;                                         #( -> buf)
             @make_buf  _24  malloc  dup  _16  malloc  ptr=
                        dup  _0  len=  dup  _16  cap= ;
: free_buf   call ^free_buf ;                                         #(buf -> )
             @free_buf  dup  ptr  over  cap  free  _24  free ;
: cap        +16  load ;                                           #(buf -> cap)
: cap        swap  +16  swap  store ;                             #(buf cap -> )
: pushb      call ^pushb ;                                       #(buf byte -> )
             @pushb       over  cap  over2  len  ==  if ^pushb.grow ^pushb.push
             @pushb.grow  over  ptr  over2  cap  # (buf byte ptr cap)
                          dup  *2  dup  malloc   # (buf byte ptr cap cap' ptr')
                          over3  over  over4  memcopy
                          over5  swap  ptr=      # (buf byte ptr cap cap')
                          over4  swap  cap=      # (buf byte ptr cap)
                          free                   # (buf byte)
             @pushb.push  over  ptr  over2  len  +  swap  storeb  # (buf)
                          dup  len  +1  len=  return
: push       call ^push ;                                        #(buf word -> )
             @push  over  over  pushb
                    over  over  _8  >>  pushb
                    over  over  _16  >>  pushb
                    over  over  _24  >>  pushb
                    over  over  _32  >>  pushb
                    over  over  _40  >>  pushb
                    over  over  _48  >>  pushb
                    over  over  _56  >>  pushb
                    pop2  return
: overwrite  call ^overwrite ;                             #(buf where word -> )
             @overwrite  # Temporarily give the buf a different length
                         over2  len  # (buf where word original_len)
                         over3  over3  len=
                         over3  over2  push
                         over3  swap  len=
                         pop3  return
: shrink     call ^shrink ;                                        #(buf -> str)
             @shrink  dup  ptr  swap  dup  cap  swap  dup  len  swap
                      _24  free    # (ptr cap len)
                      dup  malloc  # (ptr cap len new_ptr)
                      over3  over  over3  memcopy
                      over3  over3  free
                      over  keep2_pop3  make_str  return

# List stuff
: make_list  make_buf ;
: num_items  len  /8 ;                                            #(list -> int)
: get        *8  swap  ptr  +  load ;                      #(list index -> item)

# Dict stuff
: make_dict  make_list ;                                             #( -> dict)
: free_dict  free_list ;                                             #(dict -> )
: free_keys  call ^free_keys ;                                       #(dict -> )
             @free_keys       _0
             @free_keys.loop  # (dict cursor)
                              over  num_items  over
                              ==  if ^free_keys.done ^free_keys.0
             @free_keys.0     over  over  get  free_str
                              +2  jump ^free_keys.loop
             @free_keys.done  pop2
: put        call ^put ;                                    #(dict str word -> )
             @put  over2  over2  push  keep1_pop1  push  return
: lookup     call ^lookup ;                      #      (dict str -> ...)
                                                 # if found: (... -> value true)
                                                 # if not:   (... -> false)
             @lookup       _0
             @lookup.loop  # (dict str cursor)
                           dup  *2  over3  num_items  ==
                           if ^lookup.nope ^lookup.check
             @lookup.check over2  over  *2  get  over2  str==
                           if ^lookup.found ^lookup.next
             @lookup.next  +1  jump ^lookup.loop
             @lookup.found keep1_pop1  *2  +1  get  true  return
             @lookup.nope  pop3  false  return

## Tokenization
#
# The first step when compiling Grass is to convert the giant string into a list
# of tokens: ":", ";", labels, references, or names referring to definitions. At
# the end of the list, we add an empty token that marks the end of the file.

: tok call ^tok ;                                               #(str -> tokens)
  @tok                  clone_str  make_list
  @tok.loop             # (str tokens)
                        over  empty?  if ^tok.done ^tok.skip_whitespace
  @tok.skip_whitespace  over  first_char
                        dup  octothorpe?  if ^tok.comment  ^tok.not_comment
  @tok.comment          over  trim_first  over  first_char
                        newline?  if ^tok.loop ^tok.comment
  @tok.not_comment      dup  space?  swap  newline?  or
                        if ^tok.whitespace ^tok.name
  @tok.whitespace       over  trim_first  jump ^tok.loop
  @tok.name             # (str tokens)
                        over  ptr
  @tok.name.loop        # (str tokens start)
                        over2  empty?  if ^tok.name.done ^tok.name.check
  @tok.name.check       over2  first_char
                        dup  space?  swap  dup  newline?  swap  octothorpe?
                        or  or  if ^tok.name.done ^tok.name.more
  @tok.name.more        # (str tokens start)
                        over2  trim_first  jump ^tok.name.loop
  @tok.name.done        # (str tokens start)
                        over2  ptr  over  subtract  make_str # (str tokens name)
                        over  over  push  pop1  jump ^tok.loop
  @tok.done             # (str tokens)
                        swap  over  swap  push  # add eoi token (tokens)
                        return

## Inspecting Tokens

: eoi?    empty? ;                       # checks for end of input (str -> bool)
: def?    call ^def? ;                                            #(str -> bool)
          @def?        dup  len  _1  ==  if ^def?.len_1 ^def?.nope
          @def?.len_1  ptr  loadb  semicolon?  return
          @def?.nope   pop1  false  return
: eod?    call ^eod? ;              # checks for end of definition (str -> bool)
          @eod?        dup  len  _1  ==  if ^eod?.len_1 ^eod?.nope
          @eod?.len_1  ptr  loadb  colon?  return
          @eod?.nope   pop1  false  return
: label?  call ^is_label ; @is_label  ptr  loadb  at?  return     #(str -> bool)
: ref?    call ^is_ref ; @is_ref  ptr  loadb  tick?  return       #(str -> bool)

## Gathering Definitions
#
# In order to allow forward-definitions, we first collect all definitions into a
# dictionary from name to where the token definition starts (index into tokens).
# We do that by walking the tokens from the beginning, skipping top-level stuff.
# When we find a definition (":"), we store the current index in the dictionary.

: defs            call ^defs ;                                 #(tokens -> defs)
  @defs           make_dict  dup  add_builtins  _0
  @defs.loop      # (tokens dict cursor)
                  over2  over  get  dup  eoi?  if ^defs.done ^defs.0
  @defs.0         dup  eod?  if ^error.top_level_eod ^defs.1
  @defs.1         dup  def?  if ^defs.def ^defs.no_def
  @defs.no_def    pop1  +1  jump ^defs.loop
  @defs.def       pop1  +1
                  over2  over  get
                  dup  eod?  if ^error.def_imm_end ^defs.2
  @defs.2         dup  eoi?  if ^error.def_imm_end ^defs.3
  @defs.3         over2  over  lookup  if ^error.name_already_defined ^defs.4
  @defs.4         over2  over  over3  put  pop1
  @defs.def.loop  # (tokens dict cursor)
                  +1  over2  over  get  eoi?
                  if ^error.def_does_not_end ^defs.5
  @defs.5         over2  over  get  eod?  if ^defs.def.loop ^defs.def.done
  @defs.def.done  +1  jump ^defs.loop
  @defs.done      pop2  keep1_pop1  return

# The defs maps names to the token index, but how do we represent builtin bytes?
# We map them to negative numbers! Every two-digit hex string of a number n maps
# to -n-1: "00" maps to -1, "01" to -2, ..., "ff" to -256.
: add_builtins        call ^add_builtins ;                           #(defs -> )
  @add_builtins       _0
  @add_builtins.loop  # (defs index)
                      dup  _256  ==  if ^add_builtins.done ^add_builtins.0
  @add_builtins.0     over  over  to_hex_str  _-1  over3  -  put
                      +1  jump ^add_builtins.loop
  @add_builtins.done  pop2  return
: to_hex_str          call ^to_hex_str ;                           #(int -> str)
  @to_hex_str         _2  malloc
                      dup  over2  _4  >>  to_hex_char  storeb
                      dup  +1  over2  _15  and  to_hex_char  storeb
                      _2  make_str  return
: to_hex_char         call ^to_hex_char ;                         #(int -> char)
  @to_hex_char        dup  _10  <  if ^to_hex_char.<10 ^to_hex_char.>=10
  @to_hex_char.<10    push_byte '0  byte_to_word  add  return
  @to_hex_char.>=10   _10  -  push_byte 'a  byte_to_word  add  return

## Compiling Code
#
# Given that we know where each name is defined, we go through the tokens again.
# This time, we only care about the top-level scope and skip the definitions.

# compiler = ( tokens | defs | out | labels | patches )

@main                                                      #(ptr len -> ptr len)
 make_str  tok  # (tokens)
 _40  malloc    # (tokens compiler)
 dup  over2  swap  store  keep1_pop1  # (compiler)
 dup  +8  make_dict  store
 dup  +16  make_buf  store
 dup  +24  make_dict  store
 dup  +32  make_list  store
 dup  _0  compile  # (compiler)
 dup  out  over  labels  over2  patches  patch  # (compiler)
 @free_tokens        dup  tokens  _0
 @free_tokens.loop   # (tokens cursor)
                     over  num_items  over
                     ==  if ^free_tokens.done ^free_tokens.0
 @free_tokens.0      over  over  get  free_str
                     +1  jump ^free_tokens.loop
 @free_tokens.done   pop1  free_list
 dup  defs    dup  free_keys  free_dict
 dup  labels  dup  free_keys  free_dict
 @free_patches       dup  patches  _0
 @free_patches.loop  # (patches cursor)
                     over  num_items  over
                     ==  if ^free_patches.done ^free_patches.0
 @free_patches.0     over  over  get  free_str
                     +2  jump ^free_patches.loop
 @free_patches.done  pop1  free_list
 dup  out  swap  _40  free  # (out)
 shrink  return

: tokens  load ;
: defs    +8  load ;
: out     +16  load ;
: labels  +24  load ;
: patches +32  load ;

: compile          call ^comp ;                           #(compiler cursor -> )
  @comp            over  tokens  over  get
                   dup  eoi?  over  eod?  or  if ^comp.done ^comp.0
  @comp.done       pop3  return
  @comp.0          dup  label?  if ^comp.label ^comp.1
  @comp.label      # (compiler cursor token)
                   clone_str  trim_first  # cut off the @
                   # store (label, out.len) into the labels map
                   over2  labels  over  over4  out  len  put
                   pop1  +1  jump ^comp
  @comp.1          dup  ref?  if ^comp.ref ^comp.2
  @comp.ref        # (compiler cursor token)
                   clone_str  trim_first  # cut off the ^
                   # store (label, out.len) into the patches list
                   over2  patches  over  push
                   over2  patches  over3  out  len  push
                   over2  out  _0  push
                   pop1  +1  jump ^comp
  @comp.2          # (compiler cursor token)
                   dup  def?  if ^comp.skip ^comp.name
  @comp.skip       pop1
  @comp.skip.loop  +1  over  tokens  over  get  eod?  if ^comp ^comp.skip.loop
  @comp.name       # (compiler cursor token)
                   over2  defs  swap  lookup
                   if ^comp.name.0 ^error.name_not_defined
  @comp.name.0     # (compiler cursor lookup_result)
                   dup  <0?  if ^comp.builtin ^comp.defined
  @comp.builtin    +1  _0  swap  -  # (compiler cursor byte_literal)
                   over2  out  swap  pushb  jump ^comp
  @comp.defined    # (compiler cursor def_cursor)
                   over2  swap  compile  jump ^comp

: patch        call ^patch ;                           #(buf labels patches -> )
  @patch       _0
  @patch.loop  # (buf labels patches cursor)
               over  num_items  over  ==  if ^patch.done ^patch.0
  @patch.0     over  over  get  over2  over2  +1  get
               # (buf labels patches cursor label where)
               swap  over4  swap  lookup  if ^patch.1 ^error.label_not_defined
  @patch.1     # (buf labels patches cursor where target)
               over5  over2  over2  overwrite
               pop2  +2  jump ^patch.loop
  @patch.done  pop4  return

@error.top_level_eod                                                #( -> never)
 _32  malloc  dup  store_bytes 'error:_";"_outside_of_definition  _32  crash
@error.def_imm_end                                                  #( -> never)
 _29  malloc  dup  store_bytes 'error:_definition_has_no_name  _29  crash
@error.def_does_not_end                                             #( -> never)
 _28  malloc  dup  store_bytes 'error:_definition_never_ends  _28  crash
@error.def_in_def                                                   #( -> never)
 _24  malloc  dup  store_bytes 'error:_":"_in_definition  _24  crash
@error.name_not_defined                              #(compiler cursor -> never)
 over  tokens  swap  get  call ^error.is_not_defined
@error.label_not_defined                            #(patches cursor _ -> never)
 over2  over2  get  call ^error.is_not_defined
@error.name_already_defined                                  #(token _ -> never)
 swap  call ^error.is_defined_multiple_times
@error.is_not_defined                                            #(str -> never)
 dup  len  _22  +  malloc
 dup  store_bytes 'error:_
 over  ptr  over  _7  +  memcopy
 dup  _7  +  over2  len  +  store_bytes '_is_not_defined
 over len  _22  +  crash
@error.is_defined_multiple_times                                 #(str -> never)
 dup  len  _33  +  malloc
 dup  store_bytes 'error:_
 over  ptr  over  _7  +  memcopy
 dup  _7  +  over2  len  +  store_bytes '_is_defined_multiple_times
 over len  _33  +  crash