Importing CL-STL source code

[guicho271828]

https://github.com/show-matz/CL-STL is an attempt to implement STL in CL. It's based on CLOS (so it is slow) but yesterday the author, @show-matz , gave a talk on it at Shibuya.lisp Lisp Meetup and I had an opportunity to discuss this project.

• CLOS is slow but its overhead can be compiled away by inlined-generic-function. I asked him to compare the performance of CL-STL with vs without inlining.
• CL-STL is a 5-year old personal project and most containers are already implemented (e.g. deque, linked-list (bidirectional), map/set/multimap/multisets)
• It does not have templates though.
• It is aimed at reprecating C++, rather than integrating it into common lisp. According to him, his initial motivation of writing the library is to learn lisp. So when we use his code we have to refactor it.

[cosmos72]

I had a look, and it really tries to replicate C++ up to the last detail, including compile-time conditionals to decide between C++98 and some other version of the C++ standard (C++11?), and including vectors, iterators and operators.

My idea for CL-PARAMETRIC-TYPES was: Lispy and fast, i.e. trying to take the good ideas from C++ (templates = generation of specialized code = speed, templatized generic containers, templatized algorithms ...) without necessarily replicating all the details and quirks of C++ standard library

Examples of C++ features I would avoid reimplementing in CL: temporary objects, C++11 rvalue references, copy constructors, assignment operators, destructors, separate pop() and back() due to exception safety in the face of hostile copy-constructors that may throw exceptions... you get the idea.

For example, since CL lacks pointers, to implement one-dimensional arrays I would start from CL native arrays, i.e. (simple-array <t> (*)) for some <t>, and:

1. use it directly if possible - i.e. when no resize is needed
2. wrap it with some template struct to implement resizable arrays

[cosmos72]

I am currently implementing the following template structs:

• BIVECTOR - a resizeable vector that can efficiently grow and shrink at both ends
• BINARY-TREE - a sorted binary tree, to be used as base for balanced RED-BLACK-TREES, that will implement sorted sets and maps - based on the RBMAP class I already wrote and tested in https://github.com/cosmos72/stmx

[guicho271828]

BIVECTOR is a deque in C++? I guess keeping the same name as in C++ would be helpful (reduces the learning overhead)

[cosmos72]

At the moment, BIVECTOR is both C++ std::vector and std::deque. Good point, I will rename it to DEQUE.

More generally, this is the right time to start deciding names, and the fact that several useful names (MAP, LIST, SET, VECTOR...) are already reserved in package COMMON-LISP really does not help. Suggestions are welcome! :) My very incomplete proposal is:

• std::forward_list -> ??? (is a C++ linked list, much more restricted than CL:LIST)
• std::list -> ??? (is a C++ doubly linked list, and LIST exists already in CL with different meaning, see previous item)
• std::map -> SORTED-MAP ? (MAP exists already in CL)
• std::set -> SORTED-SET ? (SET exists already in CL)
• std::multimap -> ??? (should be consistent with name for std::map)
• std::multiset -> ??? (should be consistent with name for std::set)
• std::unordered_map -> HASH-MAP or UNORDERED-MAP ?
• std::unordered_set -> HASH-SET or UNORDERED-SET ?
• std::unordered_multimap -> ??? (should be consistent with name for std::unorderd_map)
• std::unordered_multiset -> ??? (should be consistent with name for std::unorderd_set)
• std::vector -> ??? (VECTOR exists already in CL)
• std::deque -> DEQUE (I will rename from BIVECTOR)
• std::stack -> STACK (C++ adapter, not a container)
• std::queue -> QUEUE (C++ adapter, not a container)
• std::priority_queue -> PRIORITY-QUEUE (C++ adapter, not a container)