r/lisp • • 1d 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.

10 Upvotes

15 comments sorted by

2

u/arthurno1 1d 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 1d 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).

3

u/arthurno1 1d ago

In a sense. That is what it ends up in, but you can break that down to simpler ideas that are easier to digest.

Point of cons data structure is just to have a linked list. Linked lists in their turn are used to store parsed source code in. Each parsed token becomes a node in the linked list representing an expression, and very few tokens have special meaning. Notably parens stand for start of the list and end of the list.

Once you have the source in the list form, you can than use ordinary list operations to process it like you would process any other data in a list. So there comes "code is data, data is code" from. Admittedl, my first comment, and this one, are a bit of a misnomer, because what I really had in mind was the common form of "cdr-ing" and recursive processing over lists, as we know it in classical Lisp(s).

However, nothing says you have to do so, and there are Lisps, that don't store the source code in cons cells. Clojure is one example. We could do recursion even if source was stored in a different data structure, say a vector:

(defun iterate-array (arr &optional (index 0))
  "Recursively traverse ARR and process each element."
  (when (< index (length arr))
    ;; do something with the element here
    (print (aref arr index))
    (iterate-array arr (1+ index))))

Hopefully, your Lisp dialect have TCO optimization and the above is turned into iterative loop version without the function call cost and stack allocations.

For your considerations about performance, I don't think you should really worry. In modern Lisps, such as Common Lisp in SBCL, performant code typically don't use lists for user data. Lists are typically used mostly for processing the source code itself in macros, and for user data where the performance does not matter. It means you typically use arrays, structures, hashtables and trees, and whatever you might need for your application to be efficient, just like in any other programming language.

SBCL also have an efficient cons allocator, bump allocator, which allocates cons cells on thread local "allocation regions" which short said, store cons cells close to each other, in a contigous regions, so access patern is cache friendly, more like a vector. So for practical purpose it means you don't typically point wildly in the heap, but exploit the cache locality. That is of course specific from case to the case.

For your application needs, where performance matters, you would typically use vectors and defstruct which gives you malloc-like, contigous, O(1) time access pattern.

Processing source code is typically a very small part of the compilation and lists representing top-level forms in a lisp file are typically not very huge that linked-list representation would be a bottleneck. By switching to more compact representation like an array for example, you would get probably just a marginal speed-up if even that, but will have to switch to completely different mental model of source code processing. You will have to give up the classical cdr-recursion model which we know from classical, McCarthian, Lisps, which some people will say is not Lisp any more (RMS was the last one well-known who proclaimed Clojure is not a Lisp, I guess for that particular reason).

The above is of course for a big, modern, "desktop" lisp, like SBCL on x86-64 or Arm. A side note from CMUCL manual:

5.10.1 Think Before You Use a List

Although Lisp’s creator seemed to think that it was for LISt Processing, the astute observer may have noticed that the chapter on list manipulation makes up less that three percent of Common Lisp: The Language II. The language has grown since Lisp 1.5—new data types supersede lists for many purposes.

For a constraint system like yours, Micro Lisp (uLisp), already does something similar as you write about. As I read about, they allocate static array and conses are just indexes into that array. However, I am not familiar with uLisp, I looked once at it, more for the curiosity, so I can't tell you much about. Look at the sources, or use it for a while, see what they do and adapt their techniques for your lisp.

2

u/Reasonable_Wait6676 1d 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 1d ago edited 1d 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 1d 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 1d 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 1d ago edited 1d 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 1d 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.

11

u/lispm 1d 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.

7

u/stevevdvkpe 1d 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.

5

u/The-Constable 1d 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.

6

u/zyni-moe 1d 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 1d ago

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

And this is generally how high performance programs in Lisp work

1

u/corbasai 1d ago

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