1 # Toy lisp interpreter. Incomplete. 2 # 3 # To run: 4 # $ ./ntranslate init.linux 0*.subx apps/subx-params.subx apps/mulisp.subx 5 # $ ./a.elf 6 # 42 7 # => 42 8 # ^D 9 # $ 10 11 == code 12 13 Entry: # run tests if necessary, a REPL if not 14 # . prologue 15 89/<- %ebp 4/r32/esp 16 # initialize heap 17 (new-segment Heap-size Heap) 18 { 19 # if (argc <= 1) break 20 81 7/subop/compare *ebp 1/imm32 21 7e/jump-if-lesser-or-equal break/disp8 22 # if (argv[1] != "test")) break 23 (kernel-string-equal? *(ebp+8) "test") # => eax 24 3d/compare-eax-and 0/imm32 25 74/jump-if-equal break/disp8 26 # 27 (run-tests) 28 # syscall(exit, *Num-test-failures) 29 8b/-> *Num-test-failures 3/r32/ebx 30 eb/jump $main:end/disp8 31 } 32 (repl Stdin Stdout) 33 # syscall(exit, 0) 34 bb/copy-to-ebx 0/imm32 35 $main:end: 36 b8/copy-to-eax 1/imm32/exit 37 cd/syscall 0x80/imm8 38 39 # Data structures 40 # 41 # Lisp is dynamically typed. Values always carry around knowledge of their 42 # type. 43 # 44 # There's several types of types in the description below, so we need a 45 # glossary and notational convention to disambiguate: 46 # lisp type: what Lisp code can see. Looks how you type it at the prompt. 47 # nil num char string symbol pair array 48 # type tag: the numeric code for a lisp type. All caps. 49 # NIL NUM CHAR STRING SYMBOL PAIR ARRAY 50 # memory type: a type specifying memory layout at the SubX level. Starts 51 # with a '$'. 52 # $int $array $(address _) 53 # 54 # Lisp values are represented in memory by the _cell_ data structure. A cell 55 # is 12 bytes long: 56 # tag: $int (4 bytes; we're not concerned about wasting space) 57 # data: 8 bytes whose contents and meaning depend on tag 58 # 59 # What values of the different Lisp types look like in memory: 60 # - nil: cell{ tag: 0/NIL, data: 0 0 } 61 # - num: cell{ tag: 1/NUM, data: $int 0 } 62 # data contains the number 63 # - char: cell{ tag: 2/CHAR, data: $int 0 } 64 # data contains the utf-8 code of the character (no compound glyphs, no 65 # modifiers, etc., etc.) 66 # - string: cell{ tag: 3/STRING, data: $(address stream byte) 67 # data contains an (address array byte) containing the string in utf-8 68 # - symbol: cell{ tag: 4/SYMBOL, data: $(address array byte) 0 } 69 # data contains an (address array byte) containing the name of the symbol in utf-8 70 # alternatively, data could contain an index into the table of interned symbols 71 # - pair: cell{ tag: 5/PAIR, data: $(address cell) $(address cell) } 72 # data contains pointers to car and cdr 73 # - array: cell{ tag: 6/ARRAY, data: $tag $(address stream data) 74 # data contains a pointer to an array of 8-byte data fields and the common 75 # tag for them all 76 77 repl: # in : (address buffered-file), out : (address buffered-file) 78 # . prologue 79 55/push-ebp 80 89/<- %ebp 4/r32/esp 81 # . save registers 82 50/push-eax 83 { 84 (lisp-read Stdin) # => eax : (address cell) 85 # if (eax == 0) break 86 3d/compare-eax-and 0/imm32 87 74/jump-if-equal break/disp8 88 # 89 (lisp-eval %eax) # => eax : (address cell) 90 (lisp-print Stdout %eax) 91 eb/jump loop/disp8 92 } 93 $repl:end: 94 # . restore registers 95 58/pop-to-eax 96 # . epilogue 97 89/<- %esp 5/r32/ebp 98 5d/pop-to-ebp 99 c3/return 100 101 # numbers start with a digit and are always in hex 102 # characters start with a backslash 103 # pairs start with '(' 104 # arrays start with '[' 105 # symbols start with anything else but quote, backquote, unquote or splice 106 # only one s-expression per line 107 lisp-read: # in : (address buffered-file) -> eax : (address cell) 108 # . prologue 109 55/push-ebp 110 89/<- %ebp 4/r32/esp 111 # . save registers 112 51/push-ecx 113 # var s/ecx : (stream byte 512) 114 81 5/subop/subtract %esp 0x200/imm32 115 68/push 0x200/imm32/size 116 68/push 0/imm32/read 117 68/push 0/imm32/write 118 89/<- %ecx 4/r32/esp 119 { 120 # read line into s 121 (clear-stream %ecx) 122 (read-line-buffered *(ebp+8) %ecx) 123 # if (s->write == 0) return null 124 { 125 81 7/subop/compare *ecx 0/imm32 126 75/jump-if-not-equal break/disp8 127 b8/copy-to-eax 0/imm32/eof 128 eb/jump $lisp-read:end/disp8 129 } 130 # ... 131 #? eb/jump loop/disp8 132 } 133 # return s 134 89/<- %eax 1/r32/ecx 135 $lisp-read:end: 136 # . reclaim locals 137 81 0/subop/add %esp 0x20c/imm32 138 # . restore registers 139 59/pop-to-ecx 140 # . epilogue 141 89/<- %esp 5/r32/ebp 142 5d/pop-to-ebp 143 c3/return 144 145 # lisp-read: in : (address buffered-file) -> (address cell) 146 # token tmp = next-mulisp-token(in) 147 # if is-int(tmp) return cell(tmp) 148 # if is-string(tmp) return cell(tmp) 149 # if is-pair(tmp) ... 150 # if is-array(tmp) ... 151 152 next-mulisp-token: # in : (address buffered-file), line : (address stream), result : (address slice) 153 # pseudocode: 154 # if (line->read >= line->write) 155 # read-line-buffered(in, line) 156 # recurse 157 # if (line->data[line->read] == ' ') 158 # skip-chars-matching-whitespace(line) 159 # recurse 160 # if (line->data[line->read] == '#') 161 # read-line-buffered(in, line) 162 # recurse 163 # eax = line->data[line->read] 164 # if (eax == '"') 165 # result->start = &line->data[line->read] 166 # skip-string(in) 167 # result->end = &line->data[line->read] 168 # return 169 # if (is-digit(eax)) 170 # result->start = &line->data[line->read] 171 # skip-hex-int(in) 172 # result->end = &line->data[line->read] 173 # return 174 # if (eax in '(' ')' '[' ']') 175 # result->start = &line->data[line->read] 176 # ++line->read 177 # result->en = &line->data[line->read] 178 # return 179 # else 180 # result->start = &line->data[line->read] 181 # skip-lisp-word(line) 182 # result->en = &line->data[line->read] 183 # return 184 # 185 # . prologue 186 55/push-ebp 187 89/<- %ebp 4/r32/esp 188 # . save registers 189 $next-mulisp-token:end: 190 # . reclaim locals 191 # . restore registers 192 # . epilogue 193 89/<- %esp 5/r32/ebp 194 5d/pop-to-ebp 195 c3/return 196 197 new-int-cell: # in : (address slice) -> eax : (address cell) 198 199 new-string-cell: # in : (address slice) -> eax : (address cell) 200 201 lisp-eval: # in : (address cell) -> eax : (address cell) 202 # . prologue 203 55/push-ebp 204 89/<- %ebp 4/r32/esp 205 # . save registers 206 8b/-> *(ebp+8) 0/r32/eax 207 $lisp-eval:end: 208 # . restore registers 209 # . epilogue 210 89/<- %esp 5/r32/ebp 211 5d/pop-to-ebp 212 c3/return 213 214 lisp-print: # out : (address buffered-file), x : (address cell) 215 # . prologue 216 55/push-ebp 217 89/<- %ebp 4/r32/esp 218 # . save registers 219 # write(x) 220 (write-buffered Stdout "=> ") 221 (write-stream-data Stdout *(ebp+0xc)) 222 (flush Stdout) 223 $lisp-print:end: 224 # . restore registers 225 # . epilogue 226 89/<- %esp 5/r32/ebp 227 5d/pop-to-ebp 228 c3/return 229 230 == data 231 232 Nil: 233 0/imm32/tag 234 0/imm32/data