2.3 Milestone 2: Towards a Declarative Language
2.3.1 Assignment Summary
The goal of this milestone is to introduce the idea of designing languages by abstracting away from annoying details, and implementing those abstractions by compilation. We will (1) abstract away from imperative instructions on locations to expressions on values, and (2) abstract away from a small number of physical locations and replace them with an essentially unboundedly large number of abstract names.
You can use the interrogator to get limited access to the reference solution: https://soft.vub.ac.be/compilers/interrogator?an=a2.
2.3.1.1 Learning Objectives
2.3.1.2 Checklist
Completely new passes
2.3.2 Reading
The reading for this milestone is Abstract Locations and Value Orientation. As usual, this milestone description links to the documentation for each exercise in the chapter for convenience, but you are responsible for the reading the entire chapter.
You should read first and work the relevant exercises as you read.
2.3.3 Exercises
Exercise 1: Design and implement uniquify to resolve all names to abstract locations.
Exercise 2: Design and implement sequentialize-let.
Exercise 3: Design and implement normalize-bind.
Exercise 4: Design and implement select-instructions to compile imperative operations to abstract assembly instructions.
Exercise 5: Implement assign-homes.
Exercise 6: Design and implement uncover-locals to analyze which abstract locations need to be assigned physical locations.
You may find the function aloc? helpful. For working with sets, you may want to use Sets.
Exercise 7: Design and implement assign-fvars assign abstract locations to physical location.
Exercise 8: Design and implement replace-locations to replace abstract locations with their assigned physical location.
Exercise 9: Design and implement flatten-begins to flatten nested instructions.
You may find the function make-begin helpful.
Exercise 10: Design and implement patch-instructions to abstract away from x64 restrictions.
Exercise 11: Design and implement implement-fvars to support the frame variables abstraction.
You may find the function fvar->index helpful.
Exercise 12: Extend generate-x64 to emit displacement mode operands.
Exercise 13: Remove your definitions of wrap-x64-boilerplate and wrap-x64-run-time. These are now provided by cpsc411/2c-run-time, since your run-time system is getting more complicated.
Exercise 14: Which passes were simplified by the ability to nest tails?
2.3.4 Validators and interpreters
In these exercises you extend the well-formedness checkers and the interpreters for the source and target language. Generic definitions are given for these by default which you have to replace with your own implementations. You should however prioritize the exercises above, which do not have default implementation and are therefore more important for obtaining a fully functioning compiler pipeline.
Exercise 15: Redesign and extend the implementation of check-paren-x64. You should be able to modify your validator for the previous Paren-x64 v1 to include cases for displacement mode operands and accept programs for Paren-x64 v2.
You should start by writing new examples and tests for the new specification, and adding new match clauses following the template.
Exercise 16: Redesign and extend your implementation of interp-paren-x64 to support Paren-x64 v2.
> (interp-paren-x64 '(begin (set! rax 42))) 42
> (interp-paren-x64 '(begin (set! rax 42) (set! rax (+ rax 0)))) 42
> (interp-paren-x64 '(begin (set! (rbp - 0) 0) (set! (rbp - 8) 42) (set! rax (rbp - 0)) (set! rax (+ rax (rbp - 8))))) 42
> (interp-paren-x64 '(begin (set! rax 0) (set! rbx 0) (set! r9 42) (set! rax (+ rax r9)))) 42
> (interp-paren-x64 '(begin (set! (rbp - 0) 42) (set! rax (rbp - 0)))) 42
Exercise 17: Design and implement check-values-lang, a validator for Values-lang v3.
Exercise 18: Design and implement interp-values-lang, an interpreter for Values-lang v3.
> (interp-values-lang '(module (+ 2 2))) 4
> (interp-values-lang '(module (let ([x 5]) x))) 5
> (interp-values-lang '(module (let ([x (+ 2 2)]) x))) 4
> (interp-values-lang '(module (let ([x 2]) (let ([y 2]) (+ x y))))) 4
> (interp-values-lang '(module (let ([x 2]) (let ([x 2]) (+ x x))))) 4
> (execute '(module (+ 2 2))) 4
> (execute '(module (let ([x 5]) x))) 5
> (execute '(module (let ([x (+ 2 2)]) x))) 4
> (execute '(module (let ([x 2]) (let ([y 2]) (+ x y))))) 4
> (execute '(module (let ([x 2]) (let ([x 2]) (+ x x))))) 4
> (define (compile-pre-runtime p) (parameterize ([current-pass-list (list check-values-lang uniquify sequentialize-let normalize-bind select-instructions assign-homes flatten-begins patch-instructions implement-fvars check-paren-x64 generate-x64)]) (compile p))) > (require racket/pretty)
> (pretty-display (compile-pre-runtime '(module (+ 2 2))))
mov QWORD [rbp - 0], 2
mov r10, QWORD [rbp - 0]
add r10, 2
mov QWORD [rbp - 0], r10
mov rax, QWORD [rbp - 0]
> (pretty-display (compile-pre-runtime '(module (let ([x 5]) x))))
mov QWORD [rbp - 0], 5
mov rax, QWORD [rbp - 0]
> (pretty-display (compile-pre-runtime '(module (let ([x 2]) (let ([y 2]) (+ x y))))))
mov QWORD [rbp - 8], 2
mov QWORD [rbp - 0], 2
mov r10, QWORD [rbp - 8]
mov QWORD [rbp - 16], r10
mov r10, QWORD [rbp - 16]
add r10, QWORD [rbp - 0]
mov QWORD [rbp - 16], r10
mov rax, QWORD [rbp - 16]