3 ms·

What? There are zero lisp compilers that store COMPILED lisp code as cons structures. He might as well reference GCC's abstract syntax tree, notice that it's hu

What? There are zero lisp compilers that store COMPILED lisp code as cons structures. He might as well reference GCC's abstract syntax tree, notice that it's huge, and quickly dismiss C as appropriate for embedded work. Most lisp compilers go to machine code. If you want an interesting comparison, you would have to look at something like CLISP, which has a byte code representation.

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".
kragen 16y ago
I understand if you didn't feel like reading the article, but I don't understand why you commented anyway. I wasn't concluding that Lisp was inappropriate for embedded work. I was pointing out that cons structures are inefficient not only in runtime but also in space, so that's a bad way to store code on machines where the limiting factor is space, not speed. It's well-established that that's a bad way to store code on machines where the limiting factor is speed. Conclusion of the article: it turns out that, although a bytecode like Smalltalk's is a lot slower than machine code, it's also a lot more compact. This conclusion is equally applicable to implementing embedded Lisps as embedded Smalltalks.

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".

kragen 16y ago

I understand if you didn't feel like reading the article, but I don't understand why you commented anyway. I wasn't concluding that Lisp was inappropriate for embedded work. I was pointing out that cons structures are inefficient not only in runtime but also in space, so that's a bad way to store code on machines where the limiting factor is space, not speed. It's well-established that that's a bad way to store code on machines where the limiting factor is speed. Conclusion of the article: it turns out that, although a bytecode like Smalltalk's is a lot slower than machine code, it's also a lot more compact. This conclusion is equally applicable to implementing embedded Lisps as embedded Smalltalks.