Bonjour,
i present Annot+ an annotation and inference type system for scheme/racket/scheme+
I used a one pass method parsing the AST (abstract syntax tree) of a scheme program (racket module) taking apart annotation types declaration and using them to rewrite code and doing this recursively.
Naive idea ! things being very more complex in reality. You have to be very careful with the core of the algorithm.I did not used known theory (like Hindley Milner). I used my own method instead.
Annot+ is written itself in curly-infix/scheme+ using bootstrapping method.
Public Domain Lisp Logo Set By Conrad Barski, M.D.
Here is the scheme+ source code of annot+.rkt :
Annot+ can speed up arithmetic operations in scheme,also with overloaded procedures or operators ,then as fast as if it was pure scheme code and does the same for [ ] indexed access in scheme+.
Annot+ dispatch overloaded procedure with their specialized one depending on argument type at parsing stage: the consequence is there is no more lost of time at runtime.
Here is a little example using the type annotation:
(type [(ℝ) procedure? ()] random) ; random is a procedure returning a racket/flonum? = ℝ
; return a random number between [inf, sup]
(define (uniform-interval inf sup)
(type ℝ inf sup) ; inf and sup are some ℝ
{gap ← sup - inf}
{inf + gap * (random)})
the above annotated scheme+ code is parsed and the resulting scheme code is :
(define (uniform-interval inf sup)
(← gap (fl- sup inf))
(fl+ inf (fl* gap (random))))
The benchmarks talk by themselves:
| program (same source) | Scheme | Scheme+ | Scheme+ annotated | Typed Racket | gain |
|---|---|---|---|---|---|
| floats: Horner, sigmoid, 2·10⁷ | 753 ms | 777 ms | 223 ms | 226 ms | 3.4 × |
| matrices 200×200, 20 products | 1065 ms | 1066 ms | 606 ms | 578 ms | 1.8 × |
| integers: Syracuse up to 10⁶ | 986 ms | 985 ms | 382 ms | 402 / 1099 ms | 2.6 × |
| trapezoids, 2·10⁷ steps | 359 ms | 349 ms | 68 ms | 69 ms | 5.3 × |
Type annotation is an option you can type only a portion of code when you need speed acceleration, you do not need to make a type annotation for all your variables or for all the code. (even in an ANNOTATION-ON module)
Another more complex example about a neural network retropropagation loop:
#reader SRFI-110 ; 105 ; curly-infix
#!curly-infix
ANNOTATION-ON
(require Scheme)
(struct matrix-vect (v)) ;; matrix based on vector of vectors
; modify coefficients layer
;; define getter,setter
(define (matrix-vect-ref M lin col)
(type vector? v {v[]}) ; a vector of vectors : v[lin][col] is specialized for vectors
(type ℕ lin col)
{v <- (matrix-vect-v M)}
{v[lin][col]})
(define (matrix-vect-set! M lin col x)
(type vector? v {v[]}) ; a vector of vectors : v[lin][col] is specialized for vectors
(type ℕ lin col)
{v <- (matrix-vect-v M)}
{v[lin][col] <- x})
;; overload [ ]
(overload-square-brackets matrix-vect-ref matrix-vect-set! (matrix-vect? number? number?))
(define (modification_des_poids M_i_o η z_input z_output z̃_output ᐁ_i_o მzⳆმz̃) ; derivative of activation function of the layer
(type matrix-vect? M_i_o) ; M_i_o[j (i + 1)] calls matrix-vect-ref / matrix-vect-set! directly
; M_i_o[j k] is a flonum by the return type in require-overload-square-brackets
(type ℝ η)
(type #(ℝ) ᐁ_i_o z_input z_output z̃_output)
(type ((ℝ) procedure? (ℝ ℝ)) მzⳆმz̃) ; the parameter მzⳆმz̃ hides the one of the class : its type is written here
; the length of output and input layer with coeff. used for bias update
{(len_layer_output len_layer_input_plus1forBias) <+ (dim-matrix-vect M_i_o)} ; use values and define-values to create bindings
{len_layer_input <- len_layer_input_plus1forBias - 1}
(type ℕ j)
(for ([j (range len_layer_output)]) ; line
(type ℕ i)
(for ([i (range len_layer_input)]) ; column , parcours les colonnes de la ligne sauf le bias
{M_i_o[j (i + 1)] <- M_i_o[j (i + 1)] + η · z_input[i] · მzⳆმz̃(z_output[j] z̃_output[j]) · ᐁ_i_o[j]})
; and update the bias
{M_i_o[j 0] <- M_i_o[j 0] + η * 1.0 * მzⳆმz̃(z_output[j] z̃_output[j]) * ᐁ_i_o[j]}))
notes about the above example: it is not n but η (but η displays as n in code region over discourse)
the example is extracted from module files so do not expect it to work as is : what really works ! are the complete files in examples subdirectories of project.
On the above example of neural retropropagation activating (pragma ANNOTATION-ON) or disabling the annotation (pragma ANNOTATION-OFF) pass changes the speed in a factor of x7 : with type annotation and inference the program is 7 times faster.
Last note:
type annotation works also with nested composite types: the composite types #(T) (a vector) and (T) (a list) compose at any depth: the type of the elements T can itself be a composite type. Some examples of nested composite annotations:
(type #(#(ℝ)) M) ; vector of vectors of floats (a matrix)
(type #(#(#(ℝ))) T) ; vector of vectors of vectors of floats (a 3D array)
(type #(#(ℕ)) grid) ; vector of vectors of natural fixnums
(type (#(ℤ)) Lv) ; list of vectors of fixnums
(type #((ℝ)) VL) ; vector of lists of floats
(type ((ℝ)) LL) ; list of lists of floats
(type ((#(ℝ))) LLv) ; list of lists of vectors of floats
(type #(#()) V2) ; vector of vectors with untyped elements
(type #(flomat?) Ms) ; vector of flomat matrices
(type (#(string?)) Ls) ; list of vectors of strings
The documentation and packages can be find here:
Why annot name? because it is annotation and also for a mountain village near me :
update: source file