4 ms·

How does one represent Lisp as byte code anyway? I had a look at http://clisp.cons.org/impnotes/instr-set.html http://clisp.cons.org/impnotes/instr-set.html and

by johkra 16y ago

How does one represent Lisp as byte code anyway? I had a look at http://clisp.cons.org/impnotes/instr-set.html http://clisp.cons.org/impnotes/instr-set.html and this is my idea: (1 2 3 4) => Push 4; Push 3; Push 2; Push 1 In other words: Lists are simply pushed onto the stack, probably in reverse order or car would be difficult. (+ 1 2) => Push 2; Push 1; Call n 2 (where n is the number of the '+'-function) Looking at my understanding of the problem, it's directly translatable from list-based to stack-based and hence equivalent to Forth, isn't it? Please correct me, if I'm wrong. Edit: Thinking about it, I have no clue how to represent a nested list on a stack. How would you represent ((1 2) (3 4))?

nostrademons 16y ago
Lists themselves are usually allocated on the heap. Code represented as lists is compiled to some other form, either bytecode or machine code, to be executed. The lists are basically treated as an AST, and from there you can use standard compiler techniques to go to a given instruction set.
kragen 16y ago
> Thinking about it, I have no clue how to represent a nested list on a stack. How would you represent ((1 2) (3 4))? In PostScript, it looks like this: GS>[[1 2] [3 4 GS<5>pstack 4 3 -mark- [1 2] -mark- The [ pushes a mark onto the stack, and ] allocates an array of the appropriate size, sticks stuff into the array from the stack, and leaves the array on the stack. (A pointer to it, if you want to get nitty-gritty.) Two more ]'s would pack the above up into a single nested array. Perl uses a similar strategy. On the other hand, if you're representing (car '((1 2) (3 4))) in Lisp bytecode (e.g. elisp), it looks more like this: pushconst 83258023 car That's the approach my Ur-Scheme takes in machine code, too; I just posted the assembly it generates for that expression at http://gist.github.com/427828 http://gist.github.com/427828. (Ur-Scheme is a very dumb, naïve compiler, like something you might write for an exercise in a compilers class, and it uses the x86 as a stack machine.) Finally, if you are representing (list (list 1 2) (list 3 4)) in stack bytecode, you end up with something like this: pushconst 1 pushconst 2 pushconst #list call 2 pushconst 3 pushconst 4 pushconst #list call 2 pushconst #list call 2 You can also use a PostScript-style stack mark instead of an argument count, and sometimes (e.g. commonly in Smalltalk) the function and argument count are all packed up in a single bytecode. If the argument count is implicit in the function (e.g. it's checked at compile-time) you don't need the argument count at all, but that doesn't allow you to write variadic functions like "list".

by johkra 16y ago

nostrademons 16y ago

Lists themselves are usually allocated on the heap. Code represented as lists is compiled to some other form, either bytecode or machine code, to be executed. The lists are basically treated as an AST, and from there you can use standard compiler techniques to go to a given instruction set.

kragen 16y ago

> Thinking about it, I have no clue how to represent a nested list on a stack. How would you represent ((1 2) (3 4))? In PostScript, it looks like this: GS>[[1 2] [3 4 GS<5>pstack 4 3 -mark- [1 2] -mark- The [ pushes a mark onto the stack, and ] allocates an array of the appropriate size, sticks stuff into the array from the stack, and leaves the array on the stack. (A pointer to it, if you want to get nitty-gritty.) Two more ]'s would pack the above up into a single nested array. Perl uses a similar strategy. On the other hand, if you're representing (car '((1 2) (3 4))) in Lisp bytecode (e.g. elisp), it looks more like this: pushconst 83258023 car That's the approach my Ur-Scheme takes in machine code, too; I just posted the assembly it generates for that expression at http://gist.github.com/427828 http://gist.github.com/427828. (Ur-Scheme is a very dumb, naïve compiler, like something you might write for an exercise in a compilers class, and it uses the x86 as a stack machine.) Finally, if you are representing (list (list 1 2) (list 3 4)) in stack bytecode, you end up with something like this: pushconst 1 pushconst 2 pushconst #list call 2 pushconst 3 pushconst 4 pushconst #list call 2 pushconst #list call 2 You can also use a PostScript-style stack mark instead of an argument count, and sometimes (e.g. commonly in Smalltalk) the function and argument count are all packed up in a single bytecode. If the argument count is implicit in the function (e.g. it's checked at compile-time) you don't need the argument count at all, but that doesn't allow you to write variadic functions like "list".