I have been working for a few years on my own implementation of Lisp. I have extensively described the language syntax here: https://github.com/naver/lispe/wiki.
The real reason of this version of Lisp is that I wanted to explore array languages such as APL, so I implemented a version of Lisp that is based on arrays and not linked lists. Thanks to this implementation, I was able to implement many operators that are very similar to APL, but which would be implemented on top of a Lisp syntax. However, you can still use traditional Lisp instructions such as car and cdr.
This Lisp also provides many specific types: such as tensors, matrices or dictionaries.
For instance, you can create a tensor in one line of code: (rho 4 5 6 (iota 120)).
I have written a blog on this topic: https://github.com/naver/lispe/wiki/6.20-Conway-Game-of-Life-in-LispE
There are also some implementations for the resolution of Advent of Code enigma in the examples directory. That will give you some flavors of what I try to achieve.
I also provide installers for mac (intel and apple silicon) and windows: https://github.com/naver/lispe/tree/master/binaries. I also compile a version for WebAssembly: See the WASM directory for an example of how to execute LispE in a browser.
For those who are interested, I also implemented my own terminal editor, which is part of the language itself but can also be used independently: jag.
It is implemented as two C++ classes, that can be derived for your own purpose, even though the internal documentation might be a bit lacking.
The whole project is open-source, and was developped from within Naver corporation, however, there are not strings attached.
I have also implemented a mechanism to implement external libraries that can be loaded within the language itself.
Interesting.
The only case, when this structure is less efficient is when you need to insert an element at the head. In this case, we need to move all elements one step forward, which in a buffer is quite simple and efficient:
Have you considered using a gap-buffer instead of ordinary vector?
This solution certainly poses some problems and some traditional Lisp algorithms won’t work as expected.
Since you are using C++, isn’t it possible to implement your own vector with overloaded operators to adhere to Lisp list semantics? In other words, isn’t it possible to make your car/cdr & other access functions access elements from the top of the stack so that ordinary list semantics as in standard Lisps still work as expected? Just a curious question, I guess you have already tried.
Very interesting remark. Basically, a gap buffer is a linked list in disguise, which I wanted to avoid since most implementations become much slower when your data are no longer contiguous in memory.
And what you propose is basically what I have implemented. My list is implemented as two different objects: ITEM and LIST, where ITEM contains a buffer that can be extended at will and LIST contains a pointer to ITEM and an _offset_ value.
When I do a _cdr_, I build a new LIST object that shares the same ITEM pointer as the current list but with an offset incremented by 1.
The implementation is here: https://github.com/naver/lispe/blob/master/include/listes.h
a gap buffer is a linked list in disguise
I see a gap buffer more like a generalized std vector in regard to where you insert the items. I am not sure I understand why you think of it as a list, but perhaps we think about different things?
And what you propose is basically what I have implemented.
Mnjah; I am not sure we think of the same thing in that case. What I proposed, or what I asked why you didn’t do it that way, is to keep the “classical” Lisp semantics for lists so that you don’t need to rework many of the existing algorithms based on lists. No idea if that is important or not, but I don’t see a reason why you need to reverse those just because you use std::vector under the hood to store your lists. Where and how you push/pop could be kept just as an implementation detail.
Another thing that I was thinking of is the cost of traversing the list. By generating a new object for each cdr operation and updating reference counters, it becomes quite costly compared to just returning a pointer. Have you done any benchmarks to compare your idea with the “classical” one? Also, have you looked into cdr coding; which is another technique to make list elements contiguous in memory?
To note, perhaps a new Lisp could dispose with car/cdr operations, as long as you have some other alternative to access and traverse lists. After all cons/car/cdr/push/pop as we know them from classical lisp are defined as they are because of the implementation behind them. There is no definition of what a Lisp is, so nobody says a Lisp has to have those operations exactly as they are known in some older Lisps.
You are right, I implemented other methods to access elements in a list, which do not rely on cdr or car (see nth operator). Actually, I also implemented a parallel Linked Lists, where these functions make more sense. You can choose which structure is more adapted.
(list 1 2 3) ; array list
(llist 1 2 3) ; linked list
The “llist” behaves exactly as traditional lists.
I don’t use std::vector under the hood… :-)