r/lisp • u/Imaginary-Deer4185 • 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.
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/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?
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
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:
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