You can still see the Lisp heritage in a few places, but overall I wouldn't say Postgres is "literally lisp in C".
You can still see the Lisp heritage in a few places, but overall I wouldn't say Postgres is "literally lisp in C".
In code that truly embraces "Lispy" lists, you cannot switch to an encapsulated list representation without making substantial changes to the code. For instance if you have any cdr recursion going on, that will have to be restructured, because a bag-style list doesn't have a cdr that is itself a bag-style list. (Perhaps the function has to be split into an external one that takes the List and then a local recursive part that works with the ListCell.)
I would say that to a fair extent, it looks to me as if the code anticipated a future retargeting to a different list representation, whereas the "Lispy" approach is to embrace a particular list representation.
Lisp programs sometimes need to improve the performance of adding to the tail of a list; it's done with some wrapping, like a structure that keeps a pointer to the tail. Usually that is only locally used; it doesn't "travel" as part of the representation of the list. It is not an encapsulation device, but only a process device. Of course there is also the common pattern of building up a list in reverse followed by a destructive nreverse. And the meta-approach of designing things to avoid doing work at the tail end of the list.
I just remembered the existence of some C code that has nothing to do with any Lisp implementation internals, which pushes and nreverses: http://www.kylheku.com/cgit/c-snippets/tree/autotab.c#n228
A double-ended queue (deque) can be formed in Lisp by using a pair of lists. So both ends of the queue are list heads, from which we cdr into the interior. I developed such a thing which is hosted here:
http://www.kylheku.com/cgit/lisp-snippets/tree/deque.lisp
With this deque, we simply use the push macro to add items to either end of the queue. pop-deque will remove an item from either end. Underflows are handled by rebalancing the dequeue: shuffling items from one list to the other. The cost of that is amortized. (BTW I see that pop-deque has a multiple-evaluation-of-arguments problem; it really should be written using get-setf-expansion.)
I think changing the list representation made sense in part because the rest of the codebase didn't use lists in a deeply Lispy way, for the most part.