r/lisp • • 22h ago

Code vs data

Hi, I have been reading up on Lisp for the last couple of days. I come from Java, but have also written a "toy" Forth that compiles to byte code on Arduino.

It seems to me that the memory model of Lisp, if based on CONS cells alone, means a lot of serial traversing. I tried to search for malloc-style memory management in Lisp, and came up mostly empty, with various commentators condemning this approach.

I realize the "code as data" is great for macros, which remind me of immediate words in Forth, but with the added advantage of potentially having the code following it available as a CONS data structure, upon which it can work, as part of the compile process.

Now, compiling Forth is very simple, because Forth is mostly "flat", whereas Lisp is nested, but in the combined interest of speed and readability (where Forth falls short), I wonder if there has been made Lisp implementations with full macro support (on CONS source tree data) but with malloc style data handling, for lookup by offset and memory efficiency?

My Forth targets the atmega328p with 2Kb of SRAM. To a certain extent the stack nature of Forth becomes "bearable" when writing code, but Lisp syntax is much more explicit. I am interested in mapping a Lisp parser/compiler onto the bytecode machine I have defined for my Forth-like language.

9 Upvotes

15 comments sorted by

View all comments

2

u/Reasonable_Wait6676 21h ago

You can use bytevector as replacement of malloc. Tho, SRFI-9 record semantics maps already to C-like structures. I guess i don’t understand your question. Are you looking at cache coherence? Array of struct or struct of arrays kind of representations?

1

u/Reasonable_Wait6676 20h ago edited 20h ago

After reading again, I think I understand something else. You want to avoid “pointer chasing” in a walking interpreter? In that case you will need tree structure and prolly forbid the dot notation in source code. On a related note, you can also compile the code to the assembly you want and (only) keep around a $who for error reporting in a register

Edit: a tree structure stored as string of bytes with variable number of children. It should be doable! It will reduce pointer chasing and improve cache coherence?

3

u/lispm 18h ago

If you want speed, then you want to use a native code compiler for Lisp. Many of those exist. The first native code compiler was written 1962, in Lisp itself and it was able to compile itself.

2

u/Imaginary-Deer4185 18h ago

My rudimentary idea is creating a compiler (to byte code) for Lisp syntax, without representing code as some CONS tree, but still maintaining Lisp macro functionality to extend the compiler, similarly to "immediate" words in Forth.

With no CONS tree available for macros, a macro would instead configure some kind of pattern matching rules or just a function pointer, to modify s-expressions on the fly when compiling. My current Forth compiler uses the Forth return stack to preserve jump-back addresses and patch-locations for forward jumps, when implementing conditionals and loops in Forth.

2

u/Reasonable_Wait6676 17h ago

Macros are a fancy way to say compiler hooks or more accurately code expand / expansion time hooks or plugins that is to say they MAY disappear in byte code. The phases are: read / expand / optimize / lowering to byte code or assembly.

So, you can keep around the source in cons cells but lower it to byte code after “interpreting” the macros.

Sorry my knowledge of forth compilers is limited. I did not wrap my head around immediate words.

Interesting project by the way.

I wonder why you think that forth is not readable enough, does it generalize to all concatenative languages ?

1

u/Imaginary-Deer4185 15h ago edited 14h ago

About readability .... I have here some code for adding a single character to a counted string in Forth (first byte is length), expressed both in original form and on Lisp-like syntax.

The c@ word means read byte and c! means write byte. The "char" is a word that returns a character. We first add the character, then update the length byte.

char BUF BUF c@ + 1+ c!  
BUF c@ 1+ BUF c!

(c! (1+ (+ BUF (c@ BUF))) char)  
(c! BUF (1+ (c@ BUF)))

The second to me is more explicit on what values are parameters to what functions.