design philosophy & survey of past libraries

[guicho271828]

there are several past attempts on implementing parametric types on common lisp. as far as remember, cl-adt, https://github.com/danlentz/dstm-collections/blob/master/attic/adt.lisp . Mine is https://github.com/guicho271828/trivialib.typevar (but I'd say this is a failed attempt because it is based on CLOS/structure mixture and it was hard to debug).

This is a very interesting project, and I'd like to hear more about the design philosophy of this library, among which what I'd like to know is whether this library is designed for speed (after compilation). Well, every CLer would know how ugly C++ template is, so essentially no need to complain about its ugliness in the readme :)

[guicho271828]

the reason I wrote this issue is that I see a utility problem similar to pre-quicklisp era. There are bunch of datastructure libraries but it's hard to say CL has the enough number of reliable, benchmarked, extensible SoA (state-of-art) algorithms/datastructure libraries.

If many algorithms / datastructures are implemented on an ADT framework, it becomes increasingly hard to change the framework --- the implementations are locked in. Thus the initial design of template/ADT framework is essential for the future development.

[guicho271828]

if you intend to go beyond beta, I will contribute to this library, initially by implementing all of C++ STL structures. further discussion is welcome.

[guicho271828]

there is CL-STL which is based on CLOS classes (== slow). I personally know the author of this library.

[cosmos72]

Hello guicho,

my intention is to go beyond beta :) This project was surprisingly quick to move from ALPHA to BETA to "almost ready", and on-demand instantiation of template structs, classes and functions works already, including nested ones.

For example, there is a simple PAIR struct in the sources, defined as (TEMPLATE-STRUCT (&OPTIONAL (<T1> T) (<T2> T) (DEFSTRUCT PAIR ...)) It is used as normal Lisp type, i.e. (PAIR <T1> <T2>) and simply using (PAIR FIXNUM FIXNUM) - or any other specialization - in any place where Lisp expects a type, already causes the specialized STRUCT to be instantiated automatically - unless it's instantiated already, of course.

Nested specializations as (PAIR (PAIR FIXNUM BIGNUM) (PAIR CONS HASH-TABLE)) work already too :)

For the performance part: I am obsessed with performance, you can look at my other projects HYPERLUMINAL-MEM and STMX to get an idea. One of my reasons to have C++ templates on Lisp was exactly to be able to automatically generate fast, specialized machine code for the specific use case, from general sources - what C++ templates are good at - and that's also why I started with supporting templatized DEFSTRUCT.

The main missing feature, at the moment, is partial specialization - but I already know how to implement it :)

If you want to contribute, you're more than welcome!

Massimiliano

[cosmos72]

Before I forget... another missing feature is that I don't know yet how to perform compile-time automatic resolution of overloaded functions. At the moment I have implemented manual resolution...

[guicho271828]

Sounds very good. Several comments:

Id like it better if the macro for functions and structures are same, i.e., no template-function, template-structure, etc, and just template instead.

Also, are they able to contain more than 1 sexp? for example, below would be much more convenient:

(template (<T1>)
  (defun ...)
  (defstruct ...)
  (defun ...))

Also, I do not know what it means about "automatic resolution of overloaded functions". can you give me an example?

[guicho271828]

Another thing I care about is the pattern matching friendliness. It should be compatible with Optima or Trivia.

[guicho271828]

"automatic resolution of overloaded functions" --- ok, I think I can guess what it means, does it simply mean "compile-time/runtime dispatch"? I did it once for inlined-generic-function . I used the fact that if you inline the dispatching code into a fully typed environment, clever compiler can dead-code-eliminate the code for non-matching types.

[guicho271828]

Nested specializations as (PAIR (PAIR FIXNUM BIGNUM) (PAIR CONS HASH-TABLE)) work already too :)

can you restrict the parametric types on a template level? i.e.,

(template (<T>)
   (declare (type (equalable <T>))
   (defun ...)))

Edit: well, this may not be so important, since it is not available on C++ either.

[guicho271828]

oh I forgot to mention the most important library currently available --- cl-containers and LIL (lisp interface library). The biggest issue on these libraries are the lack of documentation. We MUST write a thorough documentation in order to make a library usable (I intentionally avoided saying "more useful", because without docs, it has zero usability).

[guicho271828]

Please take a look at my brief survey on how poor the quality of the current datastructure libraries in common lisp are :(

https://github.com/guicho271828/data-structures-in-common-lisp/blob/master/database.sexp

[guicho271828]

another mention to some utilities : https://github.com/guicho271828/type-r (type retrieval) and https://github.com/guicho271828/trivialib.type-unify

[cosmos72]

At the moment there are no "C++ concepts" i.e. no way to specify the requirements on template arguments...

On the other hand, I just implemented some of your suggestions:

1) a single TEMPLATE macro instead of TEMPLATE-FUNCTION, TEMPLATE-STRUCTURE, etc. Actually, it was already implemented before you asked :) I just had to update the documentation.

2) It is now possible to put more 1 sexp in a single TEMPLATE, as for example:

    (template (<t>)
      (defun ...)
      (defstruct ...)
      (defun ...))

[cosmos72]

Oh, and "automatic resolution of overloaded functions" means the following: At the moment, one must write the list of template arguments every time

    (template (<t1> <t2>)
      (defstruct pair
        (first  nil :type <t1>)
        (second nil :type <t2>)))
    (declaim (type (pair fixnum boolean) *p*))
    (defvar *p* (make-pair (fixnum boolean) :first 7 :second t))
    (pair-first (fixnum boolean) *p*)
    (setf (pair-first (fixnum boolean) *p*) 12)

With automatic overload resolution, "a sufficiently smart compiler" would infer the correct specialized function to call based on the DECLAIM TYPE for its arguments (in this case P), and one could write something like:

    (pair-first :auto *p*)
    (setf (pair-first :auto *p*) 12)

and get the same code as above. Something that is taken for granted in statically-typed C++, but non-trivial in Common Lisp

[guicho271828]

so we most probably need a compiler macro hack + cltl2 variable-information.