Collections of accessor functions and patterns to access the elements in compound type specifier, e.g. `dimensions' in `(array element-type dimensions)'

type-r

* Type-R

[[https://travis-ci.org/guicho271828/type-r][https://travis-ci.org/guicho271828/type-r.svg?branch=master]]

This library provides a parser interface for the built-in compound types
defined in Common Lisp.

*NEWS (2019/04/14)* : Pattern compilation especially for the large subtypes (e.g. real-subtype)
are made faster by around x10 by reducing the duplicates in the resulting pattern expansion.
(Example: 1.155 sec -> 0.175 sec on Thinkpad X240 (Celeron 1.6GHz) for the code below)

#+begin_src lisp
TYPE-R> (time (compile nil '(lambda (x) (trivia:match x ((real-subtype low high) (print low) (print high))))))
#+end_src

*NEWS (2019/10/11)* : Now it is much faster due to the basic improvement in Trivia's compiler. (0.043 sec)

* Introduction

Consider when we have an unknown type specifier. It is easy to determine if
this type is a subtype of =string= --- just use =subtypep=. Ok, so, is it
also easy to parse the declared length of this string?

Not quite trivial as expected. This is because CL allows a bunch of
alternative representations for a =string= subtypes. We have to consider
all of =(simple-base-string 50)= , =(string)= or =string=. This is the
target of this library.

This was initially a re-implementation of
Bike/compiler-macro/type-utils.lisp . While it maintains the accessor for each
type manually with lots of /cond/ and /case/ statements, I 
automated the definition of accessors with macros and pattern matcher
[[https://github.com/guicho271828/trivia][Trivia]], and provide more complete API for Common Lisp.

Types covered by this library are shown in the table below: which means,
every compound types in CL.
For the complete list of accessors, see [[http://quickdocs.org/type-r/api][quickdocs reference]].

c.f. http://www.lispworks.com/documentation/HyperSpec/Body/04_bc.htm

|              |              |                    |
|--------------+--------------+--------------------|
| and          | long-float   | simple-base-string |
| array        | member       | simple-bit-vector  |
| base-string  | mod          | simple-string      |
| bit-vector   | not          | simple-vector      |
| complex      | or           | single-float       |
| cons         | rational     | string             |
| double-float | real         | unsigned-byte      |
| eql          | satisfies    | values             |
| float        | short-float  | vector             |
| function     | signed-byte  | bit                |
| integer      | simple-array | sequence           |
| fixnum       |              |                    |
| bignum       |              |                    |
| ratio        |              |                    |
| null         |              |                    |
| list         |              |                    |
|--------------+--------------+--------------------|

** Type Accessors

We have several accessor functions which returns the corresponding metadata
of a given type specifier.
The name of a function that obtains the /Y/ portion of a given type
/X/ is named /X-type-Y/, e.g., for /size/ portion of /string/,
we have /string-type-size/.

#+BEGIN_SRC lisp
(string-type-size '(string 50)) ; --> 50
(string-type-size '(string))    ; --> '*
(string-type-size 'string)      ; --> '*
(string-type-size 'base-string) ; |- error
(string-type-size '(base-string 50)) ; |- error
#+END_SRC

At this moment, the subtype relationship is not considered. For example,
/string-type-size/ does not match /base-string/. We have
/string-subtype-size/ and similar variants that matches all such
subtypes.

#+BEGIN_SRC lisp
(string-subtype-size '(string 50)) ; --> 50
(string-subtype-size '(string))    ; --> '*
(string-subtype-size 'string)      ; --> '*
(string-subtype-size 'base-string) ; --> '*
(string-subtype-size '(base-string 50)) ; --> 50
#+END_SRC

*List of general pattern names related to arrays*

+ base-string-subtype
+ simple-string-subtype
+ string-subtype
+ bit-vector-subtype
+ vector-subtype
+ simple-array-subtype
+ array-subtype
+ sequence-subtype

For type specifiers that are "/Compound Type Specifier Kind: Specializing./" or
"/Compound Type Specifier Kind: Abbreviating./" in CLHS, there may be more
metadata that do not explicitly appear in the type specifier but is still useful. For
example, =string= implies that [[http://www.lispworks.com/documentation/lw51/CLHS/Body/t_string.htm][it is an array of =character= subtypes]] .

Given that array's element-type is accessible through
=array-type-element-type=, we also provide =string-type-element-type= and
so on.

#+BEGIN_SRC lisp
(array-type-element-type 'array)               ; --> '*
(array-type-element-type '(array * 20))        ; --> '*
(array-type-element-type '(array character *)) ; --> 'character
(string-type-element-type 'string)             ; --> 'character
(array-subtype-element-type 'string)           ; --> 'character
(array-type-element-type 'string)              ; |- error (use *-subtype-* instead)
#+END_SRC

** Number types

The similar set of functions are provided for numbers.
The signature follows that of the type specifier signature.

#+BEGIN_SRC lisp
(mod-type-n '(mod 5))                        ; --> 5
(bit-type-p 'bit)                            ; --> t
(bit-type-p '(bit))                          ; --> t
(unsigned-byte-type-bits '(unsigned-byte 5)) ; --> 5
(unsigned-byte-type-bits '(unsigned-byte))   ; --> '*
(unsigned-byte-type-bits 'unsigned-byte)     ; --> '*
(signed-byte-type-bits 'signed-byte)         ; --> '*
(byte-subtype-bits '(signed-byte 5))         ; --> 5
(byte-subtype-bits '(unsigned-byte 5))       ; --> 5
(fixnum-type-p 'fixnum)                      ; --> t
(bignum-type-p 'bignum)                      ; --> t
(integer-type-p 'bignum)                     ; --> nil
(integer-subtype-p 'bignum)                  ; --> t
(integer-subtype-low 'bignum)                ; --> '*
(integer-subtype-high 'bignum)               ; --> '*
(integer-subtype-high '(unsigned-byte 5))    ; --> 32
(integer-subtype-high 'fixnum)               ; --> most-positive-fixnum
(integer-subtype-high '(mod 5))              ; --> 4

(float-type-low 'float)                         ; --> '*
(single-float-type-low 'single-float)           ; --> '*
(single-float-type-low '(single-float -1.0 2.0) ; --> 1.0
(float-subtype-low '(single-float -1.0 2.0)     ; --> 1.0
(ratio-type-p 'ratio)                           ; --> t

(real-subtype-low 'float)                  ; --> '*
(real-subtype-low 'single-float)           ; --> '*
(real-subtype-low '(single-float -1.0 2.0) ; --> 1.0
(real-subtype-low 'ratio)                  ; --> '*
(real-subtype-low '(mod 5))                ; --> 0
(real-subtype-low '(signed-byte 5))        ; --> -32
(real-subtype-low '(unsigned-byte 5))      ; --> 0
(real-subtype-low 'fixnum)                 ; --> most-negative-fixnum
(real-subtype-low 'bignum)                 ; --> '*
(real-subtype-low '(integer -3 5))         ; --> -3

(complex-type-element-type '(complex (integer -3 5)) ; --> '(integer -3 5)
(number-subtype-p '(complex (integer -3 5))          ; --> t
(number-subtype-p '(integer -3 5)                    ; --> t
#+END_SRC

*List of general pattern names related to numbers*

+ byte-subtype --- covers both =(unsigned-byte ...)= and =(signed-byte ...)= variants.
+ integer-subtype --- covers all of =mod,bit,unsigned-byte,signed-byte,bignum,fixnum,integer= type specifiers.
+ fixnum-subtype --- Same as integer-subtype but it matches only when =low,high= are within the fixnum range.
+ float-subtype
+ rational-subtype
+ real-subtype
+ number-subtype

** Other types

We also support =function=, =values=, =member=, =or=, =and=, =cons=, =member=, =eql=.

+ =function= has =function-type-return-type= / =function-type-args-type= accessors.
+ =member= has =member-type-members-=.
+ =or= / =and= has =or/and-type-types=.
+ =cons= has =cons-type-car/cdr-type=.
+ =eql= has =eql-type-object=.

** Pattern Matcher Integration

Type-R is implemented with a pattern matcher Trivia. This allows further
integration of type specifiers with pattern matchers.

For a given type specifier /X/, there is a Trivia pattern /X-type/, e.g., for /string/, we
have a pattern named /string-type/ .

#+BEGIN_SRC lisp
(match '(string 50)
  ((string-type size) size)) ; --> 50

(match '(string)
  ((string-type size) size)) ; --> '*

(match 'string
  ((string-type size) size)) ; --> '*
#+END_SRC

#+BEGIN_SRC lisp
(ematch '(simple-array * 3)
  ((array-type _ rank) rank)) ; --> match error!

(ematch '(simple-array * 3)
  ((array-subtype _ rank) rank)) ; --> 3

(ematch '(simple-array * (3 2))
  ((array-subtype _ (list _ column)) column)) ; --> 2
#+END_SRC

#+BEGIN_SRC lisp
(ematch '(simple-string 5)
  ((simple-string-type size) size)) ; --> 5

(ematch '(simple-string 5)
  ((simple-string-type _ type) type)) ; --> 'character

(ematch '(base-string 5)
  ((base-string-type _ type) type)) ; --> 'base-char
#+END_SRC

For number types, we have patterns like /(float-type low high)/. Similarly
to the array types, we have optional values that are bounded by default,
e.g.,

#+BEGIN_SRC lisp

(match 'fixnum
  ((integer-subtype low _) low)) ; --> [MOST-NEGATIVE-FIXNUM] (implementation dependent)

#+END_SRC


# ** Predicates
# 
# These are fundamentally not different from =cl:subtypep=.
# 
# We have several predicates which returns true when a given type exactly matches
# the expected type.
# These predicates are named according to the standard convention:
# /X-type-p/ for a type /X/.
# 
# #+BEGIN_SRC lisp
# (string-type-p '(string 50)) ; --> t
# (string-type-p '(string))    ; --> t
# (string-type-p 'string)      ; --> t
# (string-type-p 'base-string)      ; --> nil
# #+END_SRC
# 
# As you see, the subtype relationship is not considered. For example,
# /string-type-p/ does not match /base-string/. Instead, the library has
# /string-subtype-p/ and similar variants that matches all such
# type specifiers.


** Example

When writing a numerical manipulation library,
it is sometimes necessary to convert a set of several type specifiers under REAL, e.g. RATIO, INTEGERS, FLOATS,
to the least specific FLOAT type when any one of them are not integers. The rule for writing this could be cumbersome
without this library.


Let's start with an incomplete function that converts two given types into a long-float type
when one of them is a long-float type specifier:

#+begin_src lisp
(defun upgrade-to-long-float (type1 type2)
  (ematch* (type1 type2)
    (((long-float-type l1 h1) (long-float-type l2 h2))
     
     `(long-float ,(min* l1 l2)
                  ,(max* h1 h2)))
    
    (((real-subtype l1 h1) (long-float-type l2 h2))
     
     `(long-float ,(min* l1 l2)
                  ,(max* h1 h2)))
    
    (((long-float-type l2 h2) (real-subtype l1 h1))
     
     `(long-float ,(min* l1 l2)
                  ,(max* h1 h2)))))
#+end_src

This function takes two types, then performs a pattern match on them.
We used =ematch*= which we can feed multiple objects (unlike =ematch=),
and =ematch*= signals an error when none of the patterns are matched,
unlike =match*= which just returns a =nil= when that happens.

The code dispatches to the corresponding branch and decomposes the type specifier into its =low= and =high= component.

Note that we cannot use the standard =min= or =max= because =low= and =high= could be a symbol ='*=.
=min*= and =max*= are exactly those variants as defined below.

Also note that we use =real-subtype= pattern instead of =real-type= pattern because we want to match all type specifiers
that is a subtype of =real=.

#+begin_src lisp
(defun min* (a b)
  (declare ((or (eql *) real) a b))
  (ematch* (a b)
    (('* _) '*)
    ((_ '*) '*)
    ((_ _) (min a b))))

(defun max* (a b)
  (declare ((or (eql *) real) a b))
  (ematch* (a b)
    (('* _) '*)
    ((_ '*) '*)
    ((_ _) (max a b))))
#+end_src

Now what we finally need to do is to cover all subtypes of float.
Note that the match is performed in a top-down manner therefore
we don't have to worry =short-float= matched before =long-float= etc.

#+begin_src lisp
(defun upgrade-to-float-type (&rest typespecs)
  (reduce (lambda (prev now)
            (ematch* (prev now)
              (((long-float-type l1 h1) (long-float-type l2 h2))
               `(long-float ,(min* l1 l2)
                            ,(max* h1 h2)))
              
              (((real-subtype l1 h1) (long-float-type l2 h2))
               `(long-float ,(min* l1 l2)
                            ,(max* h1 h2)))
              
              (((long-float-type l2 h2) (real-subtype l1 h1))
               `(long-float ,(min* l1 l2)
                            ,(max* h1 h2)))

              
              (((double-float-type l1 h1) (double-float-type l2 h2))
               `(double-float ,(min* l1 l2)
                              ,(max* h1 h2)))
              
              (((real-subtype l1 h1) (double-float-type l2 h2))
               `(double-float ,(min* l1 l2)
                              ,(max* h1 h2)))
              
              (((double-float-type l2 h2) (real-subtype l1 h1))
               `(double-float ,(min* l1 l2)
                              ,(max* h1 h2)))

              
              (((single-float-type l1 h1) (single-float-type l2 h2))
               `(single-float ,(min* l1 l2)
                              ,(max* h1 h2)))
              
              (((real-subtype l1 h1) (single-float-type l2 h2))
               `(single-float ,(min* l1 l2)
                              ,(max* h1 h2)))
              
              (((single-float-type l2 h2) (real-subtype l1 h1))
               `(single-float ,(min* l1 l2)
                              ,(max* h1 h2)))

             
              (((short-float-type l1 h1) (short-float-type l2 h2))
               `(short-float ,(min* l1 l2)
                             ,(max* h1 h2)))
              
              (((real-subtype l1 h1) (short-float-type l2 h2))
               `(short-float ,(min* l1 l2)
                             ,(max* h1 h2)))
              
              (((short-float-type l2 h2) (real-subtype l1 h1))
               `(short-float ,(min* l1 l2)
                             ,(max* h1 h2)))

              ;; the specific flaot type is unspecified.
              (((float-type l1 h1) (float-type l2 h2))
               `(float ,(min* l1 l2)
                       ,(max* h1 h2)))
              
              (((real-subtype l1 h1) (float-type l2 h2))
               `(float ,(min* l1 l2)
                       ,(max* h1 h2)))
              
              (((float-type l2 h2) (real-subtype l1 h1))
               `(float ,(min* l1 l2)
                       ,(max* h1 h2)))

              ;; Now both are rationals = (or integer ratio) = (or (or bignum fixnum) ratio).
              ;; Ratios are converted into single-floats.

              (((ratio-type l1 h1) (ratio-type l2 h2))
               `(single-float ,(min* l1 l2)
                              ,(max* h1 h2)))
              
              (((real-subtype l1 h1) (ratio-type l2 h2))
               `(single-float ,(min* l1 l2)
                              ,(max* h1 h2)))
              
              (((ratio-type l2 h2) (real-subtype l1 h1))
               `(single-float ,(min* l1 l2)
                              ,(max* h1 h2)))

              ;; Now both are integers.
              ;; we first match the case with two fixnums:
              (((fixnum-subtype l1 h1) (fixnum-subtype l2 h2))
               ;; note that this also includes the bignum type specifiers
               ;; with a sufficiently small limit.
               `(integer ,(min l1 l2) ,(max h1 h2)))

              ;; the last case is the integers beyond the fixnum range.
              (((real-subtype l1 h1) (real-subtype l2 h2))
               `(single-float ,(min* l1 l2)
                              ,(max* h1 h2)))))
          typespecs))
#+end_src

** Dependencies

This library is at least tested on implementation listed below:

+ SBCL 1.2.8 on X86-64 Linux  3.13.0-46-generic (author's environment)

Also, it depends on the following libraries:

+ Trivia by Masataro Asai ::
     NON-Optimized Pattern Matching Library

+ alexandria by  ::
    Alexandria is a collection of portable public domain utilities.

+ iterate by  ::
    Jonathan Amsterdam's iterator/gatherer/accumulator facility

** Author

+ Masataro Asai (guicho2.71828@gmail.com)

* Copyright

Copyright (c) 2015 Masataro Asai (guicho2.71828@gmail.com)


* License

Licensed under the LLGPL License.





type-r

Upstream URL

Author

License

type-r

Version:

License:

Authors:

Dependencies:

type-r.test

License:

Authors:

Dependencies:

Dependencies (3)

Dependents (4)