Quickdocs

Q

polymorphic-functions

2024-10-12

No Description

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:TOC: :ignore this: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.)

The library primarily aims 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)).

Support for optional and keyword arguments, as well as heterogeneous lambda lists is also provided.

Load the asdf system polymorphic-functions-lite if you are happy with run-time dispatch. It also has lesser dependencies, so more sustainable in the long term.

./pf-lite.png

The system polymorphic-functions provides optional compile-time dispatch through the use of CLTL2 through cl-environments. See below for details. The newly added (= unstable) specializing macro also provides runtime numcl/julia-like JAOT dispatch analogous to specialized-function.

./pf.png

Continuous Integration through Github Actions tests this library on SBCL, CCL, and ECL. The library was initially put to use at numericals, but numericals has subsequently moved to the polymorphic-functions variant at peltadot. This library continues to be used at lisp-polymorph.

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

2Table of Contents

:PROPERTIES::TOC: :include all :ignore this :depth 4:END:

:CONTENTS:

:END:

3Introduction

:PROPERTIES::CUSTOM_ID: introduction:END:

3.1Basic Usage

:PROPERTIES::CUSTOM_ID: basic-usage:END:

Users define a polymorphic-function (analogous to cl:generic-function) with one or more polymorph (similar to cl:method).

(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))

You can use my= like a generic function:

(my= (make-array 1 :element-type 'single-float)
     (make-array 1 :element-type 'single-float))
;=> HELLO
(my= #\a #\a)
;=> T
(my= "world" "hello")
;=> NIL
(my= 5 "hello")
; Evaluation aborted on #<POLYMORPHIC-FUNCTIONS::NO-APPLICABLE-POLYMORPH/ERROR {103A713D13}>.

Unlike generic functions, the specializers for polymorphic functions are CL type specifiers. This means you can use any arbitrary* type specifiers as specializers. For example, with arrays:

(defpolymorph my= ((a (simple-array single-float))
                   (b (simple-array single-float))) symbol
  ;; do something
  'hello)

Furthermore, it is possible to eliminate the run time dispatch overhead by performing static dispatch. When compiled with (declare (optimize speed (debug 1))) declaration in place, polymorphic functions attempts to perform a static dispatch. If successful, the body of the polymorphs is inlined at the call site. For example, below is the disassembly of foo which calls cl:string.

(defun foo (a b)
  (declare (optimize speed)
           (type string a b))
  (string= a b))
; disassembly for FOO
; Size: 34 bytes. Origin: #x54131582                          ; FOO
; 82:       31F6             XOR ESI, ESI
; 84:       48C745F017010050 MOV QWORD PTR [RBP-16], #x50000117  ; NIL
; 8C:       488975E8         MOV [RBP-24], RSI
; 90:       48C745E017010050 MOV QWORD PTR [RBP-32], #x50000117  ; NIL
; 98:       FF7508           PUSH QWORD PTR [RBP+8]
; 9B:       B802D62950       MOV EAX, #x5029D602              ; #<FDEFN SB-KERNEL:STRING=*>
; A0:       FFE0             JMP #S(SB-X86-64-ASM::REG :ID 0)
; A2:       CC10             INT3 16                          ; Invalid argument count trap

The disassembly of another function bar which calls my= defined above is identical!

(defun bar (a b)
  (declare (optimize speed)
           (type string a b))
  (my= a b))
; disassembly for BAR
; Size: 34 bytes. Origin: #x54131642                          ; BAR
; 42:       31F6             XOR ESI, ESI
; 44:       48C745F017010050 MOV QWORD PTR [RBP-16], #x50000117  ; NIL
; 4C:       488975E8         MOV [RBP-24], RSI
; 50:       48C745E017010050 MOV QWORD PTR [RBP-32], #x50000117  ; NIL
; 58:       FF7508           PUSH QWORD PTR [RBP+8]
; 5B:       B802D62950       MOV EAX, #x5029D602              ; #<FDEFN SB-KERNEL:STRING=*>
; 60:       FFE0             JMP #S(SB-X86-64-ASM::REG :ID 0)
; 62:       CC10             INT3 16                          ; Invalid argument count trap

However, if you skip the declarations, or the declarations are not compatible with previously defined polymorphs, then no such static dispatch or inlining takes place.

(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))

Instead, the disassembly of baz above contains a call to the polymorphic function my=.

(disassemble 'baz)
; disassembly for BAZ
; Size: 31 bytes. Origin: #x541319BB                          ; BAZ
; BB:       498B4510         MOV RAX, [R13+16]                ; thread.binding-stack-pointer
; BF:       488945F8         MOV [RBP-8], RAX
; C3:       498BD0           MOV RDX, R8
; C6:       488BFE           MOV RDI, RSI
; C9:       B904000000       MOV ECX, 4
; CE:       FF7508           PUSH QWORD PTR [RBP+8]
; D1:       B8E2FD3A50       MOV EAX, #x503AFDE2              ; #<FDEFN MY=>
; D6:       FFE0             JMP #S(SB-X86-64-ASM::REG :ID 0)
; D8:       CC10             INT3 16                          ; Invalid argument count trap

Of course, inlining and static dispatch has its caveats. That is why, a number of options are provided to turn off optimization:

  • If you know your project will never require aggressive optimization: You can use the polymorphic-functions-lite system instead of polymorphic-functions. As its name suggests, the lite version has lesser features - particularly, no option to dispatch statically - but also significantly lesser dependencies. Lesser dependencies also mean easier long term maintenance.
  • If you will sometimes require optimization and other times not: You can (setq \*disable-static-dispatch\* t) to turn off static dispatch globally.
  • Locally, you can (declare (notinline my=)) to turn off static dispatch for a particular polymorph, such as the my= above.
  • Furthermore, to turn off inlining for a particular polymorph, you can supply the :inline nil option during its definition.
(defpolymorph (my= :inline nil) ((a number) (b number)) boolean
  (= a b))
  • You can also turn off inlining but turn on static-dispatch by a combination of the option :static-dispatch-name and the inline-pf and notinline-pf declarations.

In addition, each polymorph can also have an accompanying compiler macro.

(defpolymorph-compiler-macro my= (number number) (&whole call-form x-form y-form)
  (if (and (constantp x-form)
           (constantp y-form))
      (= (eval x-form)
         (eval y-form))
      call-form))

Note however that the policy under which these may be invoked is undefined. In essence, user code must not rely on compiler macros for correctness.

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

3.2Installation

:PROPERTIES::CUSTOM_ID: installation: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+.

3.2.1Getting it from ultralisp

:PROPERTIES::CUSTOM_ID: getting-it-from-ultralisp:END:
(ql-dist:install-dist "http://dist.ultralisp.org/"
                      :prompt nil)

OR

(ql:update-dist "ultralisp")
(ql:quickload "polymorphic-functions")
;;; OR if you are happy with runtime dispatch and want minimal dependencies
(ql:quickload "polymorphic-functions-lite")

3.2.2Getting it from clpm

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

Recently, clpm support also exists.

TODO: Elaborate, and perhaps update.

3.2.3Getting it using download-dependencies

:PROPERTIES::CUSTOM_ID: getting-it-using-download-dependencies:END:

Clone to somewhere asdf can find. If you have installed quicklisp, $QUICKLISP_HOME/quicklisp/local-projects/ is a usual location.

cd $QUICKLISP_HOME/quicklisp/local-projects/

git clone https://github.com/digikar99/download-dependencies

Running the following in lisp will download or update peltadot as well as some of its dependencies to *dependencies-home*.

(asdf:load-system "download-dependencies")
(let ((download-dependencies:*dependencies-home*
        (first ql:*local-project-directories*)))
  (download-dependencies:ensure-system
   "polymorphic-functions"
   :source-type :git
   :source "https://github.com/digikar99/polymorphic-functions"))

Finally quickload it to install other dependencies.

(ql:quickload "polymorphic-functions")
; OR
(ql:quickload "polymorphic-functions-lite")

3.2.4Using roswell

:PROPERTIES::CUSTOM_ID: using-roswell:END:

For just the lite variant -

ros install digikar99/polymorphic-functions

The compilation will probably fail. But ros run and (ql:quickload "polymorphic-functions-lite").

For the nonlite/full polymorphic-functions, some quicklisp dependencies are yet to be updated. Therefore -

ros install alex-gutev/cl-environments alex-gutev/cl-form-types digikar99/compiler-macro-notes digikar99/polymorphic-functions

Finally quickload it to install other dependencies.

(ql:quickload "polymorphic-functions")
; OR
(ql:quickload "polymorphic-functions-lite")

4Advanced Usage

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

4.1Static Dispatch / Inline Optimizations

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

As stated earlier, a speed=3 optimization coupled with debug<3 optimization results in (attempts to) static-dispatch. It is up to the user to ensure that a polymorph that specializes (or generalizes) another polymorph has 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). (However, 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 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.

4.2Subtype Polymorphism

:PROPERTIES::CUSTOM_ID: subtype-polymorphism:END:

polymorphic-functions supports CLTL2 based subtype polymorphism. This means that during the compilation of a call to polymorphic function, in addition to inlining, 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.

However, this requires treating the parameters of the polymorph 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.

Note that SBCL already performs this optimization. Thus, a call to a function that was originally defined for the generic type number, when compiled with arguments single-float or fixnum, SBCL propagates these types inside the function during inlining. However, this step is performed after compiler/macroexpansions have been completed, thus portable lisp code cannot make use of this. polymorphic-functions provide this facility portably through cl-environments.

4.3Discussion and Advanced Usage

:PROPERTIES::CUSTOM_ID: discussion-and-advanced-usage:END:

The library was primarily built 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.

4.4Parametric polymorphism ala Type templating

:PROPERTIES::CUSTOM_ID: parametric-polymorphism-ala-type-templating:END:

Previous versions of polymorphic functions supported a form of type templating. Unfortunately, this became a rabbit hole in itself, and this is no longer supported in this version of polymorphic-functions. However, peltadot ships with a version of polymorphic functions that supports type templating - peltadot reimplements the common lisp type system itself.

4.5Type list / Polymorph specificity

:PROPERTIES::CUSTOM_ID: type-list--polymorph-specificity:END:

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.

4.6SLIME/Swank Integration

:PROPERTIES::CUSTOM_ID: slimeswank-integration:END:

At the moment, SLIME is non-extensible. There is an open issue here about this. Until then, loading (asdf:load-system "polymorphic-functions-lite/swank") or (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.

4.7Compiler Error Messages

:PROPERTIES::CUSTOM_ID: compiler-error-messages:END:

It is a very valid concern to want good error messages from your compiler.

For polymorphic-functions-lite which performs only run time dispatch, the sole place compiler error messages arise is during the compilation of the polymorphs themselves. Polymorphic functions does not do any special compilation of the polymorph bodies beyond macroexpansion - the compilation is handled by the underlying lisp system itself. Thus, the goodness of compiler error messages is limited by the underlying lisp system. For example, consider compilation of the below code on SBCL 2.3.11:

(defpackage :pf-user
  (:use :cl :polymorphic-functions))

(in-package :pf-user)

(defpolymorph my= ((a string) (b string))
    boolean
  (string= 2 a))

The error messages are generated very similar to a function defined using cl:defun:

cd /home/shubhamkar/
3 compiler notes:

*slime-scratch*:6:1:
  style-warning:
    The variable B is defined but never used.
    --> EVAL-WHEN SETF LET* LET* POLYMORPHIC-FUNCTIONS::LIST-NAMED-LAMBDA
    --> SB-INT:NAMED-LAMBDA
    ==>
      #'(SB-INT:NAMED-LAMBDA (POLYMORPHIC-FUNCTIONS:POLYMORPH PF-USER::MY=
                              (STRING STRING))
            (PF-USER::A PF-USER::B)
          (DECLARE (IGNORABLE))
          (DECLARE (TYPE STRING PF-USER::B)
                   (TYPE STRING PF-USER::A))
          (DECLARE)
          (POLYMORPHIC-FUNCTIONS::WITH-RETURN-TYPE BOOLEAN
            (BLOCK PF-USER::MY= (LOCALLY (STRING= 2 PF-USER::A)))))


,*slime-scratch*:8:3:
  note: deleting unreachable code
  warning:
    Constant 2 conflicts with its asserted type (OR STRING SYMBOL CHARACTER).
    See also:
      SBCL Manual, Handling of Types [:node]

Compilation failed.

The case for the nonlite polymorphic-functions is more complex. The polymorphs themselves stay the same and will produce similar error messages as above. But another class of compiler error messages arise pertaining to the compilation of calls to these polymorphic-functions. To consider a slightly non-trivial case^, we will look into optimizing the compilation of a call to numericals:mean which compute the mean of the elements of a given array-like. numericals:mean is itself a polymorphic-function as you can check from the result of (type-of (fdefinition 'numericals:mean)). This, however, is implemented as a polymorphic-function over numericals:sum.

(uiop:define-package :numericals-user
  (:mix :numericals :cl))

(in-package :numericals-user)

;; To focus on the compiler notes by polymorphic-functions,
;; instead of SBCL, we muffle SBCL's compiler notes.
(declaim (sb-ext:muffle-conditions sb-ext:compiler-note))

(defun generic-mean (array-like)
  (declare (optimize speed))
  (mean array-like))

Compiling the last form should emit a compiler note such as the following:

; processing (DEFUN GENERIC-MEAN ...)
; In file /tmp/slimePh90MB
; (Compiler) Macro of
;    #<PELTADOT/POLYMORPHIC-FUNCTIONS:POLYMORPHIC-FUNCTION MEAN (8)>
; is unable to optimize
;   (MEAN ARRAY-LIKE)
; because:
;
;   Type of
;     NUMERICALS.IMPL::OUT
;   could not be determined
;   Type of
;     ARRAY-LIKE
;   could not be determined

If you are using SLIME, you should also see the (mean array-like) form underlined to indicate that it was this form that emitted this compiler note. This should also be evident from the compiler note emitted above. This compiler note says that the type of array-like could not be derived. Let us try supplying a more specific argument.

(defun single-float-mean (array)
  (declare (optimize speed)
           (type (simple-array single-float) array))
  (mean array))

This compiled without emitting any notes! If you compare (disassemble 'generic-mean) with (disassemble 'single-float-mean), you will find that the latter contains a call to the CFFI function BMAS_ssum^^ while the former is simply calls the numericals:mean function. Let us check if this makes any performance difference!

(let ((a (rand 1000 1000 :type 'single-float)))
  (time (loop repeat 1000 do (generic-mean a))))
;; Evaluation took:
;;   0.636 seconds of real time
;;   0.636028 seconds of total run time (0.636028 user, 0.000000 system)
;;   100.00% CPU
;;   1,404,383,458 processor cycles
;;   0 bytes consed
(let ((a (rand 1000 1000 :type 'single-float)))
  (time (loop repeat 1000 do (single-float-mean a))))
;; Evaluation took:
;;   0.632 seconds of real time
;;   0.632850 seconds of total run time (0.632850 user, 0.000000 system)
;;   100.16% CPU
;;   1,397,359,136 processor cycles
;;   0 bytes consed

For a single-float array of size 1000x1000, this made no performance difference. This makes sense, because for such a large array, we expect most of the time to be spent within the C function BMAS_ssum itself and very overhead would be involved in the 1000 function calls. But what about for smaller arrays and greater number of high level function calls?

(let ((a (rand 100 :type 'single-float)))
  (time (loop repeat 10000000 do (generic-mean a))))
;; Evaluation took:
;;   4.201 seconds of real time
;;   4.199076 seconds of total run time (3.883141 user, 0.315935 system)
;;   [ Real times consist of 0.500 seconds GC time, and 3.701 seconds non-GC time. ]
;;   [ Run times consist of 0.500 seconds GC time, and 3.700 seconds non-GC time. ]
;;   99.95% CPU
;;   9,269,228,604 processor cycles
;;   160,052,784 bytes consed
(let ((a (rand 100 :type 'single-float)))
  (time (loop repeat 10000000 do (single-float-mean a))))
;; Evaluation took:
;;   0.920 seconds of real time
;;   0.918671 seconds of total run time (0.918671 user, 0.000000 system)
;;   99.89% CPU
;;   2,028,490,598 processor cycles
;;   0 bytes consed

Here, for arrays of size 100, this results in a performance difference of about 4 times! If or not this is relevant depends on your use case.

^: numericals:mean actually uses peltadot instead of polymorphic-functions, but the concepts are similar. Improving the compiler notes for these cases is still a work in progress. So, expect rough edges!

^^: BMAS_ssum uses SIMD under the hood. Because it is a C function, you can use it wherever you can use CFFI!

PS: Thanks to u/corbasai on reddit for the motivation for this section!

4.8Pitfalls and Limitations

:PROPERTIES::CUSTOM_ID: pitfalls-and-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.
  • 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 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.
  • 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.

5Tests

:PROPERTIES::CUSTOM_ID: tests:END:

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

6Related Projects

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

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

6.1Comparison against specialized-function

:PROPERTIES::CUSTOM_ID: comparison-against-specialized-function:END:

6.1.1Doesn't pf's use of AOT imply 2500 specialized variants as sf says?

:PROPERTIES::CUSTOM_ID: doesnt-pfs-use-of-aot-imply-2500-specialized-variants-as-sf-says:END:

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

6.1.2But, what about inline induced code-bloat?

:PROPERTIES::CUSTOM_ID: but-what-about-inline-induced-code-bloat:END:

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.

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

:PROPERTIES::CUSTOM_ID: that-sounds-bad-isnt-there-a-best-of-both-worlds:END:

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

6.2Comparison against generic-function, fast-generic-functions, specialization-store

:PROPERTIES::CUSTOM_ID: comparison-against-generic-function-fast-generic-functions-specialization-store:END:

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.

7Acknowledgements

:PROPERTIES::CUSTOM_ID: acknowledgements:END:

8API Reference

:PROPERTIES::CUSTOM_ID: api-reference:END:

8.1*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.2*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.3define-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)))
          (dispatch-declaration (quote (quote (optimize compilation-speed)))))

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.4defpolymorph

: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-NAMEINVALIDATE-PF MORE-OPTIMAL-TYPE-LIST SUBOPTIMAL-NOTE)
  • Possible values for INLINE are T, NIL and :MAYBE
  • STATIC-DISPATCH-NAME could be useful for tracing or profiling
  • If INVALIDATE-PF is non-NIL then the associated polymorphic-functionis forced to recompute its dispatching after this polymorph isdefined.
  • 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.5defpolymorph-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.6find-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.7inline-pf

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

No documentation found for inline-pf

8.8more-optimal-polymorph-inapplicable

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

8.9no-applicable-polymorph

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

  Condition

8.10not-pf-defined-before-use

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

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

8.11notinline-pf

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

No documentation found for notinline-pf

8.12pf-defined-before-use

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

No documentation found for pf-defined-before-use

8.13polymorph

: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.14polymorph-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.15polymorphic-function

:PROPERTIES::CUSTOM_ID: polymorphic-function:END:
  Function

Direct Slots

documentation

8.16polymorphic-function-type-lists

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

8.17specializing

: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. The function is compiled in a null lexical environment, with only access to variables specified in vars.

  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 ; runtime compilation overhead on first call

  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.

In addition, this is not suitable for mutating variables outside the specializing form.

8.18specializing-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 T)

8.19suboptimal-polymorph-note

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

8.20undefine-polymorphic-function

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

Remove the polymorph(-WRAPPER) defined by DEFINE-POLYMORPH CL:FMAKUNBOUND will be insufficient, because polymorphic-functions also have a compiler macro defined for them. Additionally, on SBCL, they may also have transforms associated with them.

8.21undefpolymorph

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

Remove the polymorph associated with name with type-list

Dependencies (5)

  • alexandria
  • fiveam
  • introspect-environment
  • optima
  • slime

Dependents (0)

    • GitHub
    • Quicklisp