Typeclass Codegen Ideas

[eliaslfox]

Currently typeclass codegen is not very efficient. Here are a series of ideas to improve it.

Lift Static Constructed Dictionaries to a global scope

Typeclass instances without constraints are compiled into instances of a struct while instances with constraints are compiled into functions that return a struct.

(declare f (Int -> Int -> Boolean))
(define (f a b)
  (== a b))

(declare g (Result String Int -> Result String Int -> Boolean))
(declare (g a b)
  (== a b))

(defun (f a b)
  (== |INSTANCE/EQ INT| a b))

(defun (g a b)
  (== (|INSTANCE/EQ (RESULT :A :B) |INSTANCE/EQ STRING| |INSTANCE/EQ INT) a b))

If the Eq dictionary for Result String Int was lifted then the codegen could look something like this

(define-global-lexical #:G402 (== (|INSTANCE/EQ (RESULT :A :B) |INSTANCE/EQ STRING| |INSTANCE/EQ INT) a b))

(defun (g a b)
  (== #:G402 a b))

This would construct the dictionary once instead of constructing it every time that g is called.

Transform calls to typeclass methods to direct function calls

Currently method calls on static dictionaries are compiled as shown below

(defun (a b)
  (+ |INSTANCE/NUM INT| a b))

They could be compiled instead to

(defun (a b)
  (|+-INSTANCE/NUM INT| a b))

This would allow sbcl to much better optimize the call site.

Hoist constructed dictionaries to a higher scope

Currently if a constructed dictionary is used multiple places in a function it will be constructed multiple times.

(declare f ((Result :a :b) -> (Result :a :b) -> (Tuple Boolean Boolean))
(define (f a b)
  (Tuple (== a b) (/= a b)))

The above coalton code would be compiled into the following code

(defun (f #:G401 #:G402 a b)
  (Tuple 
    (== (|INSTANCE/EQ (RESULT :A :B)| #:G401 #:G402) a b)
    (/= (|INSTANCE/EQ (RESULT :A :B)| #:G401 #:G402) a b)))

It could instead be compiled to the following code

(defun (f #:G401 #:G402 a b)
  (let ((#:G403 (|INSTANCE/EQ (RESULT :A :B)| #:G401 #:G402 )))
    (Tuple (== #:G403 a b) (/= #:G403 a b))))