IU-Fall-2021

Course web page for Fall 2021.

View the Project on GitHub IUCompilerCourse/IU-Fall-2021

Lecture: Dynamic Typing Continued

The Ldyn Language: Mini Racket (Dynamically Typed)

exp ::= int | (read) | ... | (lambda (var ...) exp)
      | (vector-ref exp exp) | (vector-set! exp exp exp)
def ::= (define (var var ...) exp)
Ldyn ::= def... exp

Compiling Ldyn to Lany by cast insertion

The main invariant is that every subexpression that we generate should have type Any, which we accomplish by using inject.

To perform an operation on a value of type Any, we project it to the appropriate type for the operation.

Example: Ldyn:

(+ #t 42)

Lany:

(inject
   (+ (project (inject #t Boolean) Integer)
      (project (inject 42 Integer) Integer))
   Integer)
===>
x86 code

Booleans:

#t
===>
(inject #t Boolean)

Integer:

42
===>
(inject 42 Integer)

Arithmetic:

(+ e_1 e_2)
==>
(inject
   (+ (project e'_1 Integer)
      (project e'_2 Integer))
   Integer)

Variables:

x
===>
x

Lambda:

(lambda (x_1 ... x_n) e)
===>
(inject (lambda: ([x_1 : Any] ... [x_n : Any]) : Any e')
    (Any ... Any -> Any))

example:

(lambda (x y) (+ x y))
===>
(inject (lambda: ([x : Any] [y : Any]) : Any
  (inject (+ (project x Integer) (project y Integer)) Integer))
  (Any Any -> Any))

Application:

(e_0 e_1 ... e_n)
===>
((project e'_0 (Any ... Any -> Any)) e'_1 ... e'_n)

Vector Reference:

(vector-ref e_1 e_2)
===>
(vector-ref (project e'_1 (Vectorof Any)) 
            (project e'_2 Integer))

Vector:

(vector e1 ... en)
===>
(inject 
   (vector e1' ... en')
   (Vector Any .... Any))

Ldyn: (vector 1 #t) heterogeneous

(inject (vector (inject 1 Integer) (inject #t Boolean)) 
   (Vector Any Any)) : Any

Lany: (Vector Int Bool) heterogeneous (Vectorof Int) homogeneous

actually see:

(Vector Any Any)
(Vectorof Any)

Instruction Selection

Vectorof, vector-ref, and vector-set!

The type checker for Lany treats vector operations differently if the vector is of type (Vectorof T). The index can be an arbitrary expression, e.g. suppose vec has type (Vectorof T). Then the index could be (read)

;; vec1 : (Vector Any Any)
(let ([vec1 (vector (inject 1 Integer) (inject 2 Integer))])
  (let ([vec2 (inject vec1 (Vector Any Any))]) ;; vec2 : Any
	(let ([vec3 (project vec2 (Vectorof Any))]) ;; vec3 : (Vectorof Any)
	  (vector-ref vec3 (read)))))

and the type of (vector-ref vec (read)) is T.

Recall instruction selection for vector-ref:

(Assign lhs (Prim 'vector-ref (list evec (Int n))))
===>
movq evec', %r11
movq offset(%r11), lhs'

where offset is 8(n+1)

If the index is not of the form (Int i), but an arbitrary expression, then instead of computing the offset 8(n+1) at compile time, you can generate the following instructions. Note the use of the new instruction imulq.

(Assign lhs (Prim 'vector-ref (list evec en)))
===>
movq en', %r11
addq $1, %r11
imulq $8, %r11
addq evec', %r11
movq 0(%r11) lhs'

The same idea applies to vector-set!.