Quickdocs

Q

polymorphic-functions

2023-06-18

Type based dispatch for Common Lisp

Upstream URL

github.com/digikar99/polymorphic-functions

Author

Shubhamkar Ayare (shubhamayare@yahoo.co.in)

License

MIT
README
Provided Systems

1About

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

BIG CAVEAT: This will especially fail with multiple inheritance, because I thought subtyping is the same as subclassing! But subtyping is different from subclassing. (Also this.)

This library is declared to be 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:

The core goal of this library is to provide a function type to dispatch on types rather than classes, for dispatching on specialized array types such as (simple-array single-float) or (simple-array double-float) or (simple-array (signed-byte 32)) in numericals. (See Basic Usage.)

Support for optional and keyword arguments, as well as heterogeneous lambda lists is also provided. Runtime dispatch is the default, compile-time dispatch is provided through the use of CLTL2 through cl-environments, and takes place when the call-site is compiled with (declare (optimize speed (debug 1))) declaration in place. The newly added (= unstable) specializing macro also provides runtime numcl/julia-like JAOT dispatch analogous to specialized-function.

If you'd like to use this library on your favourite implementation, push its developers to provide support for CLTL2. Without CLTL2, there isn't much hope for a numerical computing library in Common Lisp! Currently, only SBCL provides a good-enough support for CLTL2, and that too has bugs; cl-environments has to work hard to provide support on other implementations. Continuous Integration through Github Actions tests this library on SBCL, CCL, and ECL.

The library provides all of

Besides the standard Common Lisp types, 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. Until the PR gets merged digikar99/cl-form-types may be used.

Besides numericals, this library has also been put to use in lisp-polymorph.

See the pitfalls before using this library in a production environment!

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 at the compilation of the call-site 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 (declaration propagation) using the more specific type declarations in the environment. Thus, a polymorph 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)))
    (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)
    (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)
    (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.
    • 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.
      • A cleaner alternative might be extensible-compound-types, but that itself depends on CLTL2.
  • 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 not only involves emitting the (lambda ...) form at the call-site, but also involves propagating the type declarations of the arguments to the parameters inside the lambda. Such inlining and type-declaration propagation occurs only when the declared/derived types of the arguments are subtypes of the parameter-types of the polymorph under consideration. But because the type-declarations of the arguments can be subtypes of the types that were declared while defining the polymorph, mutating the parameter bindings may lead to bindings that do not respect the propagated types. Thus, to err on the side of caution and avoid unexpected errors, the polymorph's parameters should be treated as read-only variables. Type declaration propagation essentially supercharges common lisp's compiler macros, since they now have access to type declaration at compiler macro expansion time 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. Even then, it can be a treat to see what is possible.
  • 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 fairly adhoc and non-trivial; PRs with more simplistic algorithms would be much welcome :D!
  • This library is not meant to compete against Coalton: 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, but should be NIL T. CI is run on SBCL and ECL.

4Dependencies outside quicklisp

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

polymorphic-functions has been added to quicklisp, but if you want to use the latest, get it from ultralisp! Make sure you have SBCL 2.0.9+.

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 also exists.

TODO: Elaborate, and perhaps update.

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:

8API Reference

8.1%deparameterize-type

:PROPERTIES::CUSTOM_ID: deparameterize-type:END:
  Generic Function: (%deparameterize-type type-specifier-car type-specifier
                     &optional env)

%DEPARAMETERIZE-TYPE is called when the argument to DEPARAMETERIZE-TYPE is a list.

8.2*compiler-macro-expanding-p*

:PROPERTIES::CUSTOM_ID: compiler-macro-expanding-p:END:
  Variable
  Default Value: NIL

Bound to T inside the DEFINE-COMPILER-MACRO defined in DEFINE-POLYMORPH

8.3*disable-static-dispatch*

:PROPERTIES::CUSTOM_ID: disable-static-dispatch:END:
  Variable
  Default Value: NIL

If value at the time of compilation of the call-site is non-NIL, the polymorphic-function being called at the call-site is dispatched dynamically.

8.4*parametric-type-symbol-predicates*

:PROPERTIES::CUSTOM_ID: parametric-type-symbol-predicates:END:
  Variable
  Default Value: NIL

A type-specifier in the type-list of a polymorph qualifies as parametric-type-specifier if there exists a symbol in the list, which when tested against the functions (predicates) in this list, returns non-NIL for at least one predicate

8.5define-polymorphic-function

:PROPERTIES::CUSTOM_ID: define-polymorphic-function:END:
  Macro: (define-polymorphic-function name untyped-lambda-list &key overwrite
          (documentation NIL)
          (default (quote (function no-applicable-polymorph))))

Define a function named name that can then be used for defpolymorph for specializing on various argument types.

If overwrite is T, all the existing polymorphs associated with name are deleted, and new polymorphs will be ready to be installed. If overwrite is NIL, a continuable error is raised if the LAMBDA-LIST has changed.

default should be a FUNCTION that can be called with two arguments at run-time and compile-time in case no polymorph is applicable. - the first of these arguments is the name, while - the second argument is the argument list with which the polymorphic-function was called or compiled. At compile-time compiler-macro-expanding-p is bound to non-NIL.

8.6defpolymorph

:PROPERTIES::CUSTOM_ID: defpolymorph:END:
  Macro: (defpolymorph name typed-lambda-list return-type &body body)

Expects OPTIONAL or KEY args to be in the form

  ((A TYPE) DEFAULT-VALUE) or ((A TYPE) DEFAULT-VALUE AP).
  • name could also be (name &KEY (INLINE T) STATIC-DISPATCH-NAMEMORE-OPTIMAL-TYPE-LIST SUBOPTIMAL-NOTE)
  • Possible values for INLINE are T, NIL and :MAYBE
  • STATIC-DISPATCH-NAME could be useful for tracing or profiling
  • SUBOPTIMAL-NOTE and MORE-OPTIMAL-TYPE-LIST are useful for signallingthat the polymorph chosen for static-dispatch,inlining, or compiler-macro is not the most optimal. It is recommendedthat SUBOPTIMAL-NOTE should be the name of a subclass ofsuboptimal-polymorph-note - thecondition class should have a slot to accept the TYPE-LIST of thecurrently chosen polymorph

Note: - INLINE T or :MAYBE can result in infinite expansions for recursive polymorphs. Proceed at your own risk. - Also, because inlining results in type declaration upgradation for purposes of subtype polymorphism, it is recommended to not mutate the variables used in the lambda list; the consequences of mutation are undefined.

8.7defpolymorph-compiler-macro

:PROPERTIES::CUSTOM_ID: defpolymorph-compiler-macro:END:
  Macro: (defpolymorph-compiler-macro name type-list compiler-macro-lambda-list
          &body body)

Example TYPE-LISTs: (NUMBER NUMBER) (STRING &OPTIONAL INTEGER) (STRING &KEY (:ARG INTEGER)) (NUMBER &REST)

8.8find-polymorph

:PROPERTIES::CUSTOM_ID: find-polymorph:END:
  Function: (find-polymorph name type-list)

Returns two values: If a polymorphic-function by name does not exist, returns NIL NIL. If it exists, the second value is T and the first value is a possibly empty list of polymorphs associated with name.

8.9inline-pf

:PROPERTIES::CUSTOM_ID: inline-pf:END:

No documentation found for inline-pf

8.10more-optimal-polymorph-inapplicable

:PROPERTIES::CUSTOM_ID: more-optimal-polymorph-inapplicable:END:
  Condition

8.11no-applicable-polymorph

:PROPERTIES::CUSTOM_ID: no-applicable-polymorph:END:
  Function: (no-applicable-polymorph name env args &optional arg-types)

  Condition

8.12not-pf-defined-before-use

:PROPERTIES::CUSTOM_ID: not-pf-defined-before-use:END:

No documentation found for not-pf-defined-before-use

8.13notinline-pf

:PROPERTIES::CUSTOM_ID: notinline-pf:END:

No documentation found for notinline-pf

8.14parametric-type-compile-time-lambda-body

:PROPERTIES::CUSTOM_ID: parametric-type-compile-time-lambda-body:END:
  Generic Function: (parametric-type-compile-time-lambda-body type-car type-cdr
                     type-parameter)

Users are expected to specialize on the type-car using an (EQL symbol) specializer. type-car and type-cdr together make up the parametric-type, while type-parameter is one of the type parameter in the parametric-type.

The methods implemented should return a one-argument lambda-/expression/ (not function). The expression will be compiled to a function and called with the appropriate form-type at compile-time. The function should return the value of the type-parameter corresponding to the parametric-type in the form-type.

If the form-type does not match the parametric-type, then NIL may be returned.

8.15parametric-type-run-time-lambda-body

:PROPERTIES::CUSTOM_ID: parametric-type-run-time-lambda-body:END:
  Generic Function: (parametric-type-run-time-lambda-body type-car type-cdr
                     type-parameter)

Users are expected to specialize on the type-car using an (EQL symbol) specializer. type-car and type-cdr together make up the parametric-type, while type-parameter is one of the type parameter in the parametric-type.

The methods implemented should return a one-argument lambda-/expression/ (not function). The expression will be compiled to a function and called with the appropriate object at run-time. The function should return the value of the type-parameter corresponding to the object and the parametric type.

8.16pf-defined-before-use

:PROPERTIES::CUSTOM_ID: pf-defined-before-use:END:

No documentation found for pf-defined-before-use

8.17pflet

:PROPERTIES::CUSTOM_ID: pflet:END:
  Macro: (pflet bindings &body body)

Like LET but when expanded inside PF-COMPILER-MACRO, this uses information in DEPARAMETERIZER-ALIST to deparameterize types.

8.18pflet*

:PROPERTIES::CUSTOM_ID: pflet-1:END:
  Macro: (pflet* bindings &body body)

Like LET* but when expanded inside PF-COMPILER-MACRO, this uses information in DEPARAMETERIZER-ALIST to deparameterize types.

8.19polymorph

:PROPERTIES::CUSTOM_ID: polymorph:END:
  Structure
  • If RUNTIME-APPLICABLE-P-FORM returns true when evaluated inside thelexical environment of the polymorphic-function, then the dispatch isdone on LAMBDA. The prioritization is done by ADD-OR-UPDATE-POLYMORPHso that a more specialized polymorph is checked for compatibilitybefore a less specialized polymorph.
  • The PF-COMPILER-MACRO calls the COMPILER-APPLICABLE-P-LAMBDA with theFORM-TYPEs of the arguments derived at compile time. The compilermacro dispatches on the polymorph at compile time if theCOMPILER-APPLICABLE-P-LAMBDA returns true.
  • If this POLYMORPH is used for INLINE-ing or STATIC-DISPATCH and ifMORE-OPTIMAL-TYPE-LIST or SUBOPTIMAL-NOTE is non-NIL, then emits aOPTIMIZATION-FAILURE-NOTE

8.20polymorph-apropos-list-type

:PROPERTIES::CUSTOM_ID: polymorph-apropos-list-type:END:
  Function: (polymorph-apropos-list-type type &key (name NIL namep)
             (package NIL packagep))

8.21polymorphic-function

:PROPERTIES::CUSTOM_ID: polymorphic-function:END:
  Class

Direct Slots

documentation

8.22polymorphic-function-type-lists

:PROPERTIES::CUSTOM_ID: polymorphic-function-type-lists:END:
  Function: (polymorphic-function-type-lists polymorphic-function)

8.23specializing

:PROPERTIES::CUSTOM_ID: specializing:END:
  Macro: (specializing vars &body body)

Analogous to SPECIALIZED-FUNCTION:SPECIALIZING.

At runtime, compiles and caches a function corresponding to the runtime types of vars, with (optimize speed) declaration. Uses specializing-type-of to avoid overspecializing types.

  POLYMORPHIC-FUNCTIONS> (defun dot-original (a b c)
                           (declare (optimize (speed 3)))
                           (loop
                             for ai across a
                             for bi across b
                             do (incf c (* ai bi)))
                           c)
  DOT-ORIGINAL
  POLYMORPHIC-FUNCTIONS> (let ((a (aops:rand* 'single-float 10000))
                               (b (aops:rand* 'single-float 10000)))
                           (time (loop repeat 1000 do (dot-original a b 0.0f0))))
  Evaluation took:
    0.516 seconds of real time
    0.515704 seconds of total run time (0.515704 user, 0.000000 system)
    100.00% CPU
    1,138,873,226 processor cycles
    0 bytes consed

  NIL
  POLYMORPHIC-FUNCTIONS> (defun dot-specialized (a b c)
                           (specializing (a b c)
                             (declare (optimize (speed 3)))
                             (loop
                               for ai across a
                               for bi across b
                               do (incf c (* ai bi)))
                             c))
  DOT-SPECIALIZED
  POLYMORPHIC-FUNCTIONS> (let ((a (aops:rand* 'single-float 10000))
                               (b (aops:rand* 'single-float 10000)))
                           (time (loop repeat 1000 do (dot-specialized a b 0.0f0))))
  Evaluation took:
    0.076 seconds of real time
    0.076194 seconds of total run time (0.076194 user, 0.000000 system)
    100.00% CPU
    4 forms interpreted
    27 lambdas converted
    168,267,912 processor cycles
    1,502,576 bytes consed

  NIL
  POLYMORPHIC-FUNCTIONS> (let ((a (aops:rand* 'single-float 10000))
                               (b (aops:rand* 'single-float 10000)))
                           (time (loop repeat 1000 do (dot-specialized a b 0.0f0))))
  Evaluation took:
    0.080 seconds of real time
    0.078954 seconds of total run time (0.078954 user, 0.000000 system)
    98.75% CPU
    174,478,140 processor cycles
    0 bytes consed

  NIL

Note that as of this writing, compiling a specialized variant still requires at least one runtime dispatch to take place; as such this is only useful if the specialized variant offsets the cost of dispatch, and may not be useful for wrapping around simple functions such as addition of two numbers, but only for more expensive functions such as element-wise addition of two 10000-sized vectors.

8.24specializing-type-of

:PROPERTIES::CUSTOM_ID: specializing-type-of:END:
  Function: (specializing-type-of object)

A clean wrapper around CL:TYPE-OF to deal with overspecialized types returned by CL:TYPE-OF. For instance, often times knowing an array is (ARRAY SINGLE-FLOAT) can be enough for optimization, (ARRAY SINGLE-FLOAT (2 3 4)) is an overspecialized type in this sense.

Polymorphs:

  • (specializing-type-of SIMPLE-ARRAY)
  • (specializing-type-of ARRAY)
  • (specializing-type-of (SIGNED-BYTE 32))
  • (specializing-type-of FIXNUM)
  • (specializing-type-of ABSTRACT-ARRAY)
  • (specializing-type-of T)

8.25suboptimal-polymorph-note

:PROPERTIES::CUSTOM_ID: suboptimal-polymorph-note:END:
  Condition

8.26undefine-polymorphic-function

:PROPERTIES::CUSTOM_ID: undefine-polymorphic-function:END:
  Function: (undefine-polymorphic-function name)

Remove the polymorph(-WRAPPER) defined by DEFINE-POLYMORPH

8.27undefpolymorph

:PROPERTIES::CUSTOM_ID: undefpolymorph:END:
  Function: (undefpolymorph name type-list)

Remove the polymorph associated with name with type-list

Dependencies (13)

  • alexandria
  • cl-form-types
  • closer-mop
  • compiler-macro-notes
  • ctype
  • extensible-compound-types
  • fiveam
  • introspect-environment
  • let-plus
  • optima
  • slime
  • split-sequence
  • trivial-garbage

Dependents (3)

  • GitHub
  • Quicklisp