polymorphic-functions

2022-07-08

Type based dispatch for Common Lisp

Upstream URL

github.com/digikar99/polymorphic-functions

Author

Shubhamkar Ayare (shubhamayare@yahoo.co.in)

License

MIT
README

1About

:PROPERTIES::CUSTOM_ID: polymorphic-functions:END:

This library is still unstable, albeit the main interface comprising of the below symbols hasn't changed in at least the last six months. Users are also recommended to avoid non-trivial uses of &rest type-lists:

  • define-polymorphic-function
  • undefine-polymorphic-function
  • defpolymorph
  • defpolymorph-compiler-macro
  • undefpolymorph
  • find-polymorph
  • polymorph-apropos-list-type

The library provides all of

to dispatch on the basis of types rather than classes. Compile-time dispatch is also provided but this requires support for CLTL2 through cl-environments. In addition, extended types are also provided through two means:

  1. ctype, and the system polymorphic-functions
  2. extensible-compound-types, recommended usage is (cl:pushnew :extensible-compound-types cl:*features*) and then (asdf:compile-system ... :force t). You may optionally need to recompile dependencies, and it might be recommendable to force compile "extensible-compound-types" itself, so that others are recompiled automagically.

The library was primarily made to dispatch on specialized-arrays for use in numericals, since CLHS does not enable generic-functions for specialized-arrays. But has also been put to use in lisp-polymorph.

See also: pitfalls.

2Table of Contents

:PROPERTIES::TOC: :include all:END:

:CONTENTS:

:END:

3Usage

:PROPERTIES::CUSTOM_ID: usage:END:

3.1Basic Usage

:PROPERTIES::CUSTOM_ID: basic-usage:END:
  • Users are expected to define a polymorphic-function (analogous to cl:generic-function) with one or more polymorph (similar to cl:method). These may be dispatched at runtime or at compile time if optimization policy is (and (= speed 3) (/= debug 3)) abbreviated as optim-speed.
  • Adhoc Polymorphism is supported in the sense that different polymorphs can have different implementations.
  • Subtype Polymorphism is supported in the sense that once a polymorph is defined, then when a call to it is being compiled, then the type declarations inside the lambda-body of the polymorph are enhanced using the more specific type declarations in the environment. Thus, apolymorph that was defined for vector when compiled with arguments declared to be simple-string, then the body is made aware at compiler/macroexpansion time that the arguments are actually simple-string rather than just vector. Code further in the succeeding compiler/macroexpansion phases can then make use of this information. This requires that the parameters to the polymorph be treated as read-only variables; otherwise the consequences can be undefined because code might have been initially written assuming the parameter/variable to be a vector and not merely a simple-string.
  • Individual polymorphs may also additionally have compiler macros. However, the policy under which these may be invoked is undefined. In essence, user code must not rely on compiler macros for correctness.
  • See Discussion and Advanced Usage for parametric polymorphism. Adhoc and Subtype polymorphisms should suffice in most cases for optimization; parametric polymorphism can aid in further type safety.

3.1.1Examples

:PROPERTIES::CUSTOM_ID: examples:END:

See file:src/misc-tests.lisp for some more examples.

  (use-package :polymorphic-functions)
  (define-polymorphic-function my= (a b))
  (defpolymorph my= ((a string) (b string)) boolean
    (string= a b))
  (defpolymorph my= ((a character) (b character)) boolean
    (char= a b))
  (defpolymorph my= ((a (simple-array single-float))
                     (b (simple-array single-float))) symbol
    ;; possible here; not possible with cl:defmethod without some MOP-fu
    ;; do something
    'hello)
  CL-USER> (defun foo (a b)
             (declare (optimize speed)
                      (type string a b))
             (string= a b))

  FOO
  CL-USER> (disassemble 'foo)
  ; disassembly for FOO
  ; Size: 39 bytes. Origin: #x5300D1B3                          ; FOO
  ; B3:       31F6             XOR ESI, ESI
  ; B5:       48C745F017011050 MOV QWORD PTR [RBP-16], #x50100117  ; NIL
  ; BD:       488975E8         MOV [RBP-24], RSI
  ; C1:       48C745E017011050 MOV QWORD PTR [RBP-32], #x50100117  ; NIL
  ; C9:       B90C000000       MOV ECX, 12
  ; CE:       FF7508           PUSH QWORD PTR [RBP+8]
  ; D1:       B8E25A3550       MOV EAX, #x50355AE2              ; #<FDEFN SB-KERNEL:STRING=*>
  ; D6:       FFE0             JMP RAX
  ; D8:       CC10             INT3 16                          ; Invalid argument count trap
  NIL
  CL-USER> (defun bar (a b)
             (declare (optimize speed)
                      (type string a b))
             (my= a b))
  BAR
  CL-USER> (disassemble 'bar)
  ; disassembly for BAR
  ; Size: 39 bytes. Origin: #x5300D283                          ; BAR
  ; 83:       31F6             XOR ESI, ESI
  ; 85:       48C745F017011050 MOV QWORD PTR [RBP-16], #x50100117  ; NIL
  ; 8D:       488975E8         MOV [RBP-24], RSI
  ; 91:       48C745E017011050 MOV QWORD PTR [RBP-32], #x50100117  ; NIL
  ; 99:       B90C000000       MOV ECX, 12
  ; 9E:       FF7508           PUSH QWORD PTR [RBP+8]
  ; A1:       B8E25A3550       MOV EAX, #x50355AE2              ; #<FDEFN SB-KERNEL:STRING=*>
  ; A6:       FFE0             JMP RAX
  ; A8:       CC10             INT3 16                          ; Invalid argument count trap
  NIL
  CL-USER> (my= (make-array 1 :element-type 'single-float)
                (make-array 1 :element-type 'single-float))
  HELLO
  CL-USER> (defun baz (a b)
             (declare (type string a)
                      (type integer b)
                      (optimize safety))
             (my= a b))
  ; While compiling
  ;     (MY= A B)
  ;   Following notes were encountered:
  ;
  ;     No applicable POLYMORPH discovered for polymorphic-function
  ;       MY=
  ;     and ARG-LIST:
  ;
  ;       (A B)
  ;
  ;     derived to be of TYPES:
  ;
  ;       (STRING INTEGER)
  ;
  ;     Available Effective-Type-Lists include:
  ;
  ;       (STRING STRING)
  ;       (CHARACTER CHARACTER)
  ;       ((SIMPLE-ARRAY SINGLE-FLOAT) (SIMPLE-ARRAY SINGLE-FLOAT))
  BAZ
  CL-USER> (my= 5 "hello")
  ; Evaluation aborted on #<POLYMORPHIC-FUNCTIONS::NO-APPLICABLE-POLYMORPH/ERROR {103A713D13}>.

3.2Libraries / Projects currently using polymorphic-functions

:PROPERTIES::CUSTOM_ID: libraries-projects-currently-using-polymorphic-functions:END:

3.3Static Dispatch / Inline Optimizations

:PROPERTIES::CUSTOM_ID: static-dispatch-inline-optimizations:END:

A compiler-note-providing compiler-macro has also been provided for compile-time optimization guidelines.

  • A speed=3 optimization coupled with debug<3 optimization results in (attempts to) static-dispatch. This is done using by f-binding gentemps to appropriate function objects.
  • Inline optimization may also be provided by (declare (inline-pf my-polymorph)) or supplying :inline t (default) or :inline :maybe option in the name field of defpolymorph form.
  • static-dispatch can be avoided by declaring/declaiming the polymorphic-function to be cl:notinline. Globally, static-dispatch can be disabled by setting *disable-static-dispatch* to non-NIL.

It is up to the user to ensure that a polymorph that specializes (or generalizes) another polymorph should have the same behavior, under the appropriate definition of same-ness.

For instance, consider

  (define-polymorphic-function my-type (obj))
  (defpolymorph my-type ((obj vector)) symbol
    (declare (ignore obj))
    'vector)
  (defpolymorph my-type ((obj string)) symbol
    (declare (ignore obj))
    'string)

Then, the behavior of my-type-caller depends on optimization policies:

  (defun my-type-caller (a)
    (declare (optimize debug))
    (my-type a))
  (my-type-caller "hello") ;=> STRING

  ;;; VS

  (defun my-type-caller (a)
    (declare (optimize speed)
             (type vector a))
    (my-type a))
  (my-type-caller "hello") ;=> VECTOR

The mistake here is polymorph with type list (vector) produces a different behavior as compared to polymorph with type list (string). (The behavior is "same" in the sense that ="hello"= is indeed a vector; perspective matters?)

This problem also arises with static-dispatch and inlined-generic-functions. The way to avoid it is to either maintain discipline on the part of the user (the way polymorphic-functions [currently] assumes) or to seal domains (the way of fast-generic-functions and sealable-metaobjects).

Inlining especially becomes necessary for mathematical operations, wherein a call to generic-+ on SBCL can be a 3-10 times slower than the optimized calls to fixnum + or single-float + etc. generic-cl (since static-dispatch version 0.5) overcomes this on SBCL by using sb-c:deftransform; for portable projects, one could use inlined-generic-functions [superseded by =fast-generic-functions=] subject to the limitation that there are no separate classes for (array single-float) and (array double-float) at least until SBCL 2.1.1.

3.4Discussion and Advanced Usage

:PROPERTIES::CUSTOM_ID: advanced-usage:END:

The library was primarily made to dispatch on specialized-arrays for use in numericals, since CLHS does not enable generic-functions for specialized-arrays. Compile-time static-dispatch is provided through the use of compiler-macros and CLTL2 environment API in conjunction with cl-form-types.

TODO: Answer What's wrong with typecase? if anything other than non-extensibility.

The closest pre-existing library to polymorphic-functions at the time of writing is

3.4.1Wait, doesn't pf's use of AOT imply 2500 specialized variants as sf says?

Thanks to Subtype Polymorphism, pf's use of AOT can handle this without so many variants.

  (defun dot-original (a b c)
    (declare (optimize (speed 3) (debug 0)))
    (loop
      for i below (array-total-size a)
      do (incf c (* (aref a i) (aref b i))))
    c)

  (defun dot-user ()
    (let ((a (make-array 1000000 :element-type 'single-float))
          (b (make-array 1000000 :element-type 'single-float))
          (c 0.0))
      (time (loop repeat 100 do (dot-original a b c)))))

  (defun sf-dot-original (a b c)
    (declare (optimize (speed 3) (debug 0)))
    (specialized-function:specializing (a b c) ()
      (loop
        for i below (array-total-size a)
        do (incf c (* (aref a i) (aref b i))))
      c))

  (defun sf-dot-user ()
    (let ((a (make-array 1000000 :element-type 'single-float))
          (b (make-array 1000000 :element-type 'single-float))
          (c 0.0))
      (time (loop repeat 100 do (sf-dot-original a b c)))))

  (defpolymorph (pf-dot-original :inline t) (a b c) t
    (loop
      for i below (array-total-size a)
      do (incf c (* (aref a i) (aref b i))))
    c)

  (defun pf-dot-user-undeclared ()
    (let ((a (make-array 1000000 :element-type 'single-float))
          (b (make-array 1000000 :element-type 'single-float))
          (c 0.0))
      (time (loop repeat 100 do (pf-dot-original a b c)))))

  (defun pf-dot-user ()
    (let ((a (make-array 1000000 :element-type 'single-float))
          (b (make-array 1000000 :element-type 'single-float))
          (c 0.0))
      (declare (optimize speed)
               (type (simple-array single-float) a b)
               (type single-float c))
      (time (loop repeat 100 do (pf-dot-original a b c)))))

  (defun pf-dot-user-df ()
    (let ((a (make-array 1000000 :element-type 'double-float))
          (b (make-array 1000000 :element-type 'double-float))
          (c 0.0d0))
      (declare (optimize speed)
               (type (simple-array double-float) a b)
               (type double-float c))
      (time (loop repeat 100 do (pf-dot-original a b c)))))

And the results:

POLYMORPHIC-FUNCTIONS> (dot-user)
Evaluation took:
  3.108 seconds of real time
  0 bytes consed
POLYMORPHIC-FUNCTIONS> (sf-dot-user)
Evaluation took:
  0.192 seconds of real time
  392,832 bytes consed
POLYMORPHIC-FUNCTIONS> (sf-dot-user)
Evaluation took:
  0.236 seconds of real time
  0 bytes consed
POLYMORPHIC-FUNCTIONS> (pf-dot-user-undeclared)
Evaluation took:
  3.248 seconds of real time
  0 bytes consed
POLYMORPHIC-FUNCTIONS> (pf-dot-user)
Evaluation took:
  0.236 seconds of real time
  0 bytes consed
POLYMORPHIC-FUNCTIONS> (pf-dot-user-df)
Evaluation took:
  0.248 seconds of real time
  0 bytes consed

3.4.2But, what about inline induced code-bloat?

Unfortunately, that is a thing. However, consider this. (And correct me if I'm wrong!) If sf is enclosed inside a non-inline function, then there is always going to be a runtime dispatch overhead associated with it. An illustration:

  (defun sf-dot-user-small ()
    (let ((a (make-array 1000 :element-type 'single-float))
          (b (make-array 1000 :element-type 'single-float))
          (c 0.0))
      (time (loop repeat 100000 do (sf-dot-original a b c)))))

  (defun pf-dot-user-small ()
    (let ((a (make-array 1000 :element-type 'single-float))
          (b (make-array 1000 :element-type 'single-float))
          (c 0.0))
      (declare (optimize speed)
               (type (simple-array single-float) a b)
               (type single-float c))
      (time (loop repeat 100000 do (pf-dot-original a b c)))))

  POLYMORPHIC-FUNCTIONS> (sf-dot-user-small)
  Evaluation took:
    0.247 seconds of real time
    0 bytes consed
  POLYMORPHIC-FUNCTIONS> (pf-dot-user-small)
  Evaluation took:
    0.183 seconds of real time
    0 bytes consed

In essence: if you enclose, you will have runtime dispatch overhead.

3.4.3That sounds bad; isn't there a "best of both worlds"?

One observation that might sound useful is the following: the faster the code, the costlier the runtime dispatch. Indeed, no one has forced you to use sf exor pf. You can use both. pf works best for faster/smaller code when dispatch is costly. While sf works best with slower/larger code, when runtime dispatch overhead is insignificant. Thus, what you can have is the following:

  (defun sf-pf-dot-original-100 (a b c)
    (specialized-function:specializing (a b c) ()
      (declare (optimize speed))
      (loop repeat 100 do (pf-dot-original a b c))
      c))

  (defun sf-pf-dot-original-100000 (a b c)
    (specialized-function:specializing (a b c) ()
      (declare (optimize speed))
      (loop repeat 100000 do (pf-dot-original a b c))
      c))

  (defun sf-pf-dot-user ()
    (let ((a (make-array 1000000 :element-type 'single-float))
          (b (make-array 1000000 :element-type 'single-float))
          (c 0.0))
      (time (sf-pf-dot-original-100 a b c))))

  (defun sf-pf-dot-user-small ()
    (let ((a (make-array 1000 :element-type 'single-float))
          (b (make-array 1000 :element-type 'single-float))
          (c 0.0))
      (time (sf-pf-dot-original-100000 a b c))))

  ;; After initial few runs when JIT overhead is taken care of
  POLYMORPHIC-FUNCTIONS> (sf-pf-dot-user)
  Evaluation took:
    0.236 seconds of real time
    0 bytes consed
  POLYMORPHIC-FUNCTIONS> (sf-pf-dot-user-small)
  Evaluation took:
    0.180 seconds of real time
    0 bytes consed

3.4.4Well, that's awesome! What else can you do with polymorphic-functions?

In addition to Subtype Polymorphism, Parametric Polymorphism is provided as well. While subtype polymorphism helps with performance, parametric-polymorphism helps with type-safety, in addition to performance. However, given the limitations of CL, this can be a fair bit limited. See u/stylewarning's comments here.

Support for extended-types is also provided through ctype.

Note that both these are declared to be much more experimental than polymorphic-functions themselves; and it seems they will be that way for a while.

Equally experimental is the support provided for parametric polymorphism through extensible-compound-types. An example is provided in the documentation there.

3.4.5Could you elaborate a bit more on parametric-polymorphism?

Sure!

In addition to subtype-polymorphism described above (under Basic Usage), PF also provides support for parametric-polymorphism. If you are not using extensible-compound-types, this does not provide user-defined parametric types. In fact, sane user-defined parametric-types might be impossible in Common Lisp. What this merely allows for (in the absence of extensible-compound-types) then is parametric-polymorphism on functions aka polymorphs for existing parametric-types. The interface for this is through the following symbols:

  • \*parametric-type-symbol-predicates\*
  • parametric-type-run-time-lambda-body
  • parametric-type-compile-time-lambda-body
  • %deparameterize-type

An example for this is at src/extended-types/parametric-types.lisp and src/misc-tests.lisp.

  CL-USER> (use-package :polymorphic-functions)
  T
  CL-USER> (setq *parametric-type-symbol-predicates*
                 (list (lambda (s)
                         (let* ((name (symbol-name s))
                                (len  (length name)))
                           (and (char= #\< (elt name 0))
                                (char= #\> (elt name (1- len))))))))
  (#<FUNCTION (LAMBDA (S)) {53A475DB}>)

  CL-USER> (defpolymorph foo ((a (array <t>))) <t>
             (aref a 0))
  FOO
  CL-USER> (disassemble (lambda (a)
                          (declare (optimize speed)
                                   (type (simple-array single-float 1) a))
                          (aref a 0)))
  ; disassembly for (LAMBDA (A))
  ; Size: 38 bytes. Origin: #x53A49A5C                          ; (LAMBDA (A))
  ; 5C:       48837AF900       CMP QWORD PTR [RDX-7], 0
  ; 61:       7618             JBE L0
  ; 63:       F30F104201       MOVSS XMM0, [RDX+1]
  ; 68:       660F7EC2         MOVD EDX, XMM0
  ; 6C:       48C1E220         SHL RDX, 32
  ; 70:       80CA19           OR DL, 25
  ; 73:       488BE5           MOV RSP, RBP
  ; 76:       F8               CLC
  ; 77:       5D               POP RBP
  ; 78:       C3               RET
  ; 79:       CC10             INT3 16                          ; Invalid argument count trap
  ; 7B: L0:   CC24             INT3 36                          ; INVALID-VECTOR-INDEX-ERROR
  ; 7D:       08               BYTE #X08                        ; RDX
  ; 7E:       82808010         BYTE #X82, #X80, #X80, #X10      ; 0
  NIL
  CL-USER> (disassemble (lambda (a)
                          (declare (optimize speed)
                                   (type (simple-array single-float 1) a))
                          (foo a)))
  ; disassembly for (LAMBDA (A))
  ; Size: 38 bytes. Origin: #x53A49B0C                          ; (LAMBDA (A))
  ; 0C:       48837AF900       CMP QWORD PTR [RDX-7], 0
  ; 11:       7618             JBE L0
  ; 13:       F30F104201       MOVSS XMM0, [RDX+1]
  ; 18:       660F7EC2         MOVD EDX, XMM0
  ; 1C:       48C1E220         SHL RDX, 32
  ; 20:       80CA19           OR DL, 25
  ; 23:       488BE5           MOV RSP, RBP
  ; 26:       F8               CLC
  ; 27:       5D               POP RBP
  ; 28:       C3               RET
  ; 29:       CC10             INT3 16                          ; Invalid argument count trap
  ; 2B: L0:   CC24             INT3 36                          ; INVALID-VECTOR-INDEX-ERROR
  ; 2D:       08               BYTE #X08                        ; RDX
  ; 2E:       82808010         BYTE #X82, #X80, #X80, #X10      ; 0
  NIL

  CL-USER> (defpolymorph my-add ((a (array <t> (<len>))) (b (array <t> (<len>))))
               (array <t> (<len>))
             (let ((out (make-array <len> :element-type <t>)))
               (loop :for i below <len>
                     :do (setf (aref out i)
                               (+ (aref a i)
                                  (aref b i))))
               out))
  MY-ADD
  CL-USER> (my-add #(0 1) #(1 2)) ; no compilation necessary for usage
  #(1 3)
  CL-USER> (my-add #(0 1) (make-array 2 :element-type 'single-float
                                      :initial-contents '(3.0 4.0)))
  ; Evaluation aborted on #<POLYMORPHIC-FUNCTIONS::NO-APPLICABLE-POLYMORPH/ERROR {1024EB1EA3}>.
  CL-USER> (my-add (make-array 2 :element-type 'single-float
                                 :initial-contents '(3.0 4.0))
                   (make-array 2 :element-type 'single-float
                                 :initial-contents '(3.0 4.0)))
  #(6.0 8.0)
  CL-USER> (type-of *)
  (SIMPLE-ARRAY SINGLE-FLOAT (2))

  ;;; NOTE that the type-parameters cannot be further used in an unevaluated context
  CL-USER> (defpolymorph foo ((a (array <t>))) <t>
             (the <t> (aref a 0)))
  ; WARNING that <T> is an undefined type

TODO (perhaps?): Ping/PR gtype for compile time optimization.

3.4.6And about extended types?

There is a polymorphic-functions.extended-types package (not system!) that provides types based on ctype. This allows one to extend the CL type system beyond what is possible with cl:deftype.

An example for this is the (supertypep TYPE) type at file:src/extended-types/supertypep.lisp.

  • In essence, (supertypep TYPE) is the set of all type-specifiers that are a supertype of TYPE.
  • Thus, (typep 'array '(supertypep vector)) holds.
  • In addition, if one were to (deftype 1d-array () 'vector) then (typep '1d-array '(supertypep vector)) would also hold.

Another example of the usage for this is (type= TYPE) at file:src/extended-types/type=.lisp put to use in trivial-coerce.

However, these types can only be used inside the type-lists of polymorphs or with the shadowed symbols in the polymorphic-functions.extended-types package; they cannot be used inside arbitrary CL forms with cl:declare.

3.4.7Erm, about the polymorphs themselves, is there a notion of specificity of type-lists / polymorphs?

In the case of CLOS generic-functions, the specificity of methods is determined by the ordering of classes in the class-precedence-list. However, an equivalent notion of type-precedence-lists does not make sense. The closest is the subtype relation.

Thus, considering two applicable polymorphs, from left to right, each of the corresponding type-specifier pair has a non-NIL intersection*, or one of them is a subtype of another. The former case is inherently ambiguous in the absence of type-precedence lists, and is detected at compilation time. A continuable error is signalled to help the user handle this case. In the latter case, the polymorph corresponding to the more specialized type in the pair is awarded a higher specificity.

*A trivial example of non-NIL intersection are the types (or string number) and (or string symbol).

Thus, for two-argument polymorphs with type-lists containing array and string have the most-specific-first ordering given by:

(string string)
(string array)
(array  string)
(array  array)

The arguments are ordered in the order they are specified in the case of required and optional arguments. For keyword arguments, they are reordered in lexical order.

3.4.8That looks cool. Is there more comparison against generic-functions and specialization-store?

Here we go: so, polymorphic-function are implemented using the metaclass closer-mop:funcallable-standard-class and closer-mop:set-funcallable-instance-function.

As per CLHS,

A generic function is a function whose behavior depends on the classes or identities of the arguments supplied to it.

By contrast, polymorphic-functions dispatch on the types of the arguments supplied to it. This helps dispatching on specialized arrays as well as user-defined types. Further, the intention of polymorphic-functions is to provide multiple implementations of a high-level operation* corresponding to different specializations, the behavior is supposed to be the "same". "Overriding behavior" makes more sense for generic functions than with polymorphic-functions.

In contrast to sealable-metaobjects and fast-generic-functions, polymorphic-functions does not make any assumptions about the sealedness of a domain for purposes of inlining. Thus, users are expected to abide by the same precautions for inline optimizations here as they do while inlining normal functions. In particular, users are expected to recompile their code after additional polymorphs are defined, and also accordingly manage the compilation order of their files and systems.

IIUC, specialized-function provides a JIT variant of parametric polymorphism. By contrast, PF provides an AOT variant.

A related project specialization-store also provides support for type-based dispatch:

A premise of specialization store is that all specializations should perform the same task. Specializations should only differ in how the task is performed. This premise resolves ambiguities that arise when using types, rather than classes, to select the most specific specialization to apply.

However, the implications of this assumption are that individual specializations in each store-object of specialization-store do not have initializer forms for optional or keyword arguments.

By contrast, like usual generic-functions, PF does allow initializer forms for optional and keywords arguments for individual polymorphs.

In addition to being dispatched on types, PF also provides the ability to install compiler-macros for individual polymorphs.

The runtime dispatch performance of all the three of polymorphic-functions, cl:generic-function and specialization-store is comparable at least for a small number of polymorphs/methods/specializations.

Feature cl:generic-function specialization-store polymorphic-functions
Method combination Yes No No
Precedence Yes Partial^ Yes
&optional, &key, &rest dispatch No Yes Yes^
Run-time Speed Fast Fast Fast
Compile-time support Partial** Yes Yes
Parametric Polymorphism No No Yes

^This is the point about specialization-store having a single common initialization form for all the specializations.

**Using fast-generic-functions - but this apparantly has a few limitations like requiring non-builtin-classes to have an additional metaclass. This effectively renders it impossible to use for the classes in already existing libraries. But, there's also static-dispatch.

3.4.9Like generic-functions and methods, do polymorphic-functions play nice with slime/swank?

At the moment, SLIME is non-extensible. There is an open issue here about this. Until then, loading (asdf:load-system "polymorphic-functions/swank") and calling (polymorphic-functions::extend-swank) should get you going. This system essentially is just one file at file:src/swank.lisp.

3.4.10Thank you so much! Are there any pitfalls I need to be aware of while using pf?

:PROPERTIES::CUSTOM_ID: limitations:END:

Yes, there are quite a few:

  • Integration with SLIME currently works only on SBCL.
  • ANSI is insufficient for our purposes*: we need
    • CLTL2 environment API: this is used through cl-environments (and introspect-environments)
      • For form-type-inference, polymorphic-functions depends on cl-form-types. Thus, this works as long as cl-form-types succeeds, and cl-form-types does get pretty extensive. In cases wherein it does fail, we also rely on sb-c:deftransform on SBCL.
    • closer-mop; if someone needs a reduced feature version within the bounds of ANSI standard, please raise an issue!
      • A bug on CCL may not let PF work as correctly on CCL; subjectively dirty workarounds are possible until it gets fixed.
    • ctype: typexpand functionality and polymorphic-functions.extended-types package
      • A polymorphic-functions.extended-types package (not system!) is also provided based on ctype. This allows one to extend the CL type system to define types beyond what cl:deftype can do to some extent. While these cannot be used inside an arbitrary CL form with cl:declare, these can be used in the type lists of polymorphs. See file:src/extended-types/type=.lisp for an example put to use in trivial-coerce.
  • The variables used in the parameters of the polymorphs should be treated as read-only variables. This is important for inlining with subtype polymorphism, because inlining involves upgrading the declaration of the parameters to the type of the argument declared at the call site, and this type can be more specific than the types of the parameters specified during the compilation of the polymorph itself.
  • Static dispatch relies on policy-quality working as expected, and compiler-macros being called. As a result, it may not work on all implementations.
  • Some implementations produce interpreted functions some times while compiled functions other times; and accordingly differ if or not compiler-macros are called.
  • Currently inlining uses the lexical environment of the call-siterather than the definition-site as is the usual case. To work aroundthis, users should avoid shadowing global lexical elements.
  • Parametric-polymorphism is in a very limited sense. See the discussion here for parametric-types.
  • Avoid using &rest lambda-lists if you are aiming for stability. The algorithms for heterogeneous-type-lists methods for specialization and ambiguity detection implemented at file:src/lambda-lists/rest.lisp are non-trivial; PRs with more simplistic algorithms would be much welcome :D!
  • This library is not meant to compete against Coalton; because safety-wise, CLHS leaves it unspecified about what happens when the type declared at compile time (using declare or the) differs from the actual runtime type of the form or variable, compile time safety only exists on implementations that already provide it, and that too to a lesser extent that a fully static language. But on other implementations this is non-existent. However, an effort is certainly made to use the derived/declared types at the polymorph boundaries when compiled with (debug 3) or (safety 3) to ensure that the runtime types match these declared types, independent of the implementation support.

*If someone would want a reduced-feature ANSI-compatible library, feel free to raise an issue. However, even with ANSI, one needs cl:subtypep working correctly, for instance, on Allegro CL 10.1: (subtypep `(and (or string number) (or string symbol)) nil) returns T T. CI is run on SBCL and ECL.

4Dependencies outside quicklisp

:PROPERTIES::CUSTOM_ID: dependencies-outside-quicklisp:END:

4.1Getting it from ultralisp

:PROPERTIES::CUSTOM_ID: getting-it-from-ultralisp:END:

Ultralisp recently added a feature to allow custom dists. While quicklisp will take a while to update trivial-types (and cl-syntax which several other projects depend upon) to the new repositories since the originals have been archived and trivial-types is still incomplete wrt CLHS, we can use the custom dists to distribute this (and related) libraries.

To do this, add the following to your implementation init file (since you'll possibly need this to keep with the project updates):

  ;;; An attempt was made to include the enumeration function natively at
  ;;;   https://github.com/quicklisp/quicklisp-client/pull/206
  ;;; but it was rejected, so we do this:
  (defun ql-dist::dist-name-pathname (name)
    "Return the pathname that would be used for an installed dist with
  the given NAME."
    (ql-dist::qmerge (make-pathname :directory (list* :relative "dists"
                                               (uiop:split-string name :separator "/")))))
  (defun digikar99-dist-enumeration-function ()
    "The default function used for producing a list of dist objects."
    (loop for file in (directory (ql-dist::qmerge "dists/digikar99/*/distinfo.txt"))
          collect (ql-dist::make-dist-from-file file)))
  (push 'digikar99-dist-enumeration-function ql::*dist-enumeration-functions*)

Once the function is pushed, install the dist:

  ;;; See https://ultralisp.org/dists/digikar99/specialized-array-dispatch for related projects
  (ql-dist:install-dist "http://dist.ultralisp.org/digikar99/specialized-array-dispatch.txt"
                        :prompt nil)
  ;;; If the install-dist step gives a "can't create directory" error, manually
  ;;; create the directory $QUICKLISP_HOME/dists/digikar99
  (ql:update-dist "digikar99/specialized-array-dispatch")
  (ql:quickload "polymorphic-functions")
  (asdf:test-system "polymorphic-functions")

4.2Getting it from clpm

Recently, clpm support was also added.

TODO: Elaborate.

5Tests

:PROPERTIES::CUSTOM_ID: tests:END:

Tests are distributed throughout the system. Run (asdf:test-system "polymorphic-functions").

6Related Projects

:PROPERTIES::CUSTOM_ID: related-projects:END:

7Acknowledgements

:PROPERTIES::CUSTOM_ID: acknowledgements:END:

Dependencies (9)

  • alexandria
  • cl-form-types
  • closer-mop
  • compiler-macro-notes
  • ctype
  • extensible-compound-types
  • fiveam
  • introspect-environment
  • slime
  • GitHub
  • Quicklisp