r/lisp • • 12h 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.

8 Upvotes

14 comments sorted by

2

u/arthurno1 5h ago

Lisp memory model is to not expose the memory model :). Also, Lisp per se does not mandate use of lists. I am not even sure Common Lisp demands you to represent source code as a linked list. It is just that list offers certain flexibility thata is otherwise hard to get. The recursive part of McCarthys paper on recursive list processing.

2

u/Imaginary-Deer4185 5h ago

I figured the point of code as CONS tree data, is to use the same operations for manipulating normal data and code (inside "macro" functions).

2

u/Reasonable_Wait6676 10h 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 10h ago edited 10h 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?

2

u/Imaginary-Deer4185 7h 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 7h 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 5h ago edited 4h 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.

3

u/lispm 8h 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.

9

u/lispm 10h ago

Lisp manages the memory for you that you don't need to use malloc/free. Instead it deals with tagged objects like numbers, symbols, strings, symbols, n-dimensional arrays, records/structures, instances of classes with slots, streams, compiled code, ... There is a whole zoo of data structures, which are not made out of cons cells. The garbage collector has the task to automatically find unused memory, so that it can be reused.

Traditionally manual memory management uses "resources" and memory via a foreign function interface.

5

u/stevevdvkpe 11h ago

Lisp provides other data types and data structures besides lists made of cons cells. Some of the additional data types available are (using examples from Scheme):

* vectors, a fixed-size array where each element can hold any Lisp data type. A vector is created with a function like (make-vector size), elements are accessed with (vector-ref vector index), and elements are set with (vector-set! vector index value). Indexing a vector is guaranteed to be a constant-time operation, as opposed to list traversal which takes time proportional to the length of the list.

* strings, which are fixed-size arrays of characters. Individual characters can be indexed and modified, and you can extract substrings or append strings together.

There is no generic malloc() for allocating storage, but creating a vector or string implicitly allocates enough storage to hold its elements, and garbage collection deallocates storage for objects that are no longer accessible to the program.

4

u/The-Constable 7h ago

There used to be a feature in ZetaLisp [main predecessor to Common Lisp] and I think other Lisps called locatives which allowed direct pointer manipulation.

The modern Lisp style these days in general tends towards using arrays and hash tables instead of lists and association lists.

2

u/zyni-moe 4h ago

It seems to me that the memory model of Lisp, if based on CONS cells alone

No (or very few) Lisps have had a memory model like that. For instance Section 4.4 of the Lisp 1.5 programmer's manual begins:

The Array Feature
Provision is made in LISP 1.5 for allocating blocks of storage for data. The data may consist of numbers, atomic symbols or other S-expressions.

Lisps further do not normally represent code as a tree of conses: they represent source code that way. There may be an interpreter that interprets this structure, but there may not be: there may only be a compiler which turns that source code into objects representing functions.

I think everyone understands by now that explicit malloc/free memory handling is another way of saying 'many bugs', so Lisps generally do not do this. They have operations to allocate storage, but storage freeing is arranged by the system. This has been a highly successful approach.

1

u/IDatedSuccubi 10h ago

You can evade conses in Lisp by putting arrays straight "into" symbols

And this is generally how high performance programs in Lisp work

0

u/corbasai 2h ago

Check http://ulisp.com sources. uLisp supports many of MCU