3 ms·

Yeah, we replaced the old Lisp-style List implementation with a different implementation a while ago: https://github.com/postgres/postgres/commit/d0b4399d81f39d

by neilc 8y ago

Yeah, we replaced the old Lisp-style List implementation with a different implementation a while ago: https://github.com/postgres/postgres/commit/d0b4399d81f39decccb23fa38f772b71b51bf96a https://github.com/postgres/postgres/commit/d0b4399d81f39dec... You can still see the Lisp heritage in a few places, but overall I wouldn't say Postgres is "literally lisp in C".

agumonkey 8y ago
You should host teachings in college and schools.
kazinator 8y ago
I see that this diff contains a lot of fluff: in many places, functions and variables are changing names while the code which uses them remains the same. 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 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 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.)
- neilc 8y ago
  > In code that truly embraces "Lispy" lists, you cannot switch to an encapsulated list representation without making substantial changes to the code. 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.

by neilc 8y ago

agumonkey 8y ago

You should host teachings in college and schools.

kazinator 8y ago

I see that this diff contains a lot of fluff: in many places, functions and variables are changing names while the code which uses them remains the same. 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 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 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.)

neilc 8y ago
> In code that truly embraces "Lispy" lists, you cannot switch to an encapsulated list representation without making substantial changes to the code. 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.