►CMSC 430:   Design and Implementation of Programming Languages
▼Midterms
►2 Midterm 2
On this page:
2.1 Short answer
2.2 Code generation
2.3 Program Transformation:   Inlining
7.4
    ← prev  up  next → 

2 Midterm 2

Due: Friday, November 13th 11:59PM

Midterm repository:

https://classroom.github.com/a/Gv1cRIkD

The repository contains a single markdown file m2.md, which you can edit to submit your answers to the following questions. Your submission must be pushed by 11:59pm on Friday (unless you have already arranged otherwise).

During the 72 hours of the exam period, you may only ask private questions on Discord if you need assistance for the course staff. You may not communicate or collaborate with any one else about the content of this exam.

2.1 Short answer

Question 1

[12 points]

Using only cons, '(), symbols, and literal numbers, strings, booleans, or characters, write expressions that are equivalent to each of the following:

For example, '(1 2 3) is equivalent to (cons 1 (cons 2 (cons 3 '()))).

Question 2

[10 points]

Is it possible for the following program to run out of memory? Justify your answer.

(define (fact x)
  (if (<= x 1)
      1
      (* x (fact (sub1 x)))))

How about this one? Again, justify your answer.

(define (fact x)
  (define (fact-prime acc i)
    (if (<= i 1)
        acc
        (fact-prime (* acc i) (sub1 i))))
  (fact-prime 1 x))

Hint: consider Jig.

Question 3

[8 points]

For each of the following expressions, which subexpressions are in tail position? Assume that the top-level expression is in tail position.

2.2 Code generation

Question 4

[20 points]

Suppose we wanted to add a set-box! operation to our language.

A (set-box! e0 e1) expression evaluates e0 and e1. The result of e0 should be a box (otherwise an error is signalled). The box is updated (mutated) to contain the value of e1. Racket’s set-box! returns a special value called void, but your compiler may have the expression return any value.

Here’s an example (note: let is used for sequencing here):

Examples

> (let ((b (box 10)))
    (let ((i1 (set-box! b 2)))
      (unbox b)))

2

Implement the following function in the compiler. (You may assume this code will be added to the Knock compiler and may use any functions given to you.)

; LExpr LExpr CEnv -> Asm
; Compiler for (set-box! e0 e1)
(define (compile-set-box! e0 e1 c) ...)
2.3 Program Transformation: Inlining

Question 5

[20 points]

In our Iniquity: function definitions and calls compiler we introduced function definitions to help us organize our code. Function definitions came along with function calls, and unfortunately function calls come with a performance hit.

One solution is inlining: Taking the body of a funtion definition and replacing a call to that function with an instance of its body. This allows the programmer to have all the benefits of the function abstraction, without the overhead.

For example, consider the following program:

(begin
  (define (f x) (+ x 5))
  (+ 10 (f 42)))

If you inlined f, the result would be the following program:

(begin
  (define (f x) (+ x 5))
  (+ 10 (+ 42 5)))

Your task is to write and document a function named inline which takes a function f and a program p, and inlines the function f at all uses of f in the program (this includes other function definitions!).

(define (inline f p)
  ; TODO)

You can assume that you have a function fvs that given an expression, returns a list of all the free variables in that expression. This is be necessary to avoid creating incorrect programs. If dealing with variable clashes and creating new names seems too complicated, you can assume the existence of a function barendregtify which given a program makes sure that all variables are unique, running it on the following:

(begin
  (define (f x) (+ x 5))
  (define (g x) (+ x 10))
  (f (g 10)))

Would produce something like:

(begin
  (define (f var1) (+ var1 5))
  (define (g var2) (+ var2 10))
  (f (g 10)))

Why should you care about fvs or barendregtify? Well, consider the following inlining:

(begin
  (define (f x) (let ((y 5)) x))
  (let ((y 42)) (f y)))

If you inline f without care, you would get the following:

(begin
  (define (f x) (let ((y 5)) x))
  (let ((y 42)) (let ((y 5)) y)))

Now you’ve changed the program, it would result in 5 instead of 42! You can use fvs to figure out which variables might be captured, and deal with that, or you can use barendregtify to make sure that all variables are unique. Notice how if we had used barendregtify we could have avoided the problem:

(begin
  (define (f var1) (let ((var2 5)) var1))
  (let ((var3 42)) (f var3)))

Then inlining f we get:

(begin
  (define (f var1) (let ((var2 5)) var1))
  (let ((var3 42)) (let ((var2 5)) var3)))

You may have to run/call barendregtify more than once to ensure correctness, when inlining functions.

In addition to your code, make sure you answer the following question as part of your submission:

Other things you should consider:

Part A:

5 points from the total of 20 will be given if you can produce the correct inlining of f for the following program (you are free to do this by hand):

(begin
  (define (f x) (let ((y (+ x 10))) (let ((z 42)) (+ x (+ y z)))))
  (define (g x) (f x))
  (let ((y 1024)) (g (f y))))

Part B:

15 points for completing the implementation below:

(define (inline f p)
  (match p
    [(prog ds e)
          ; TODO]))

Question NaN: Extra Credit

[10 points]

Provide two graphs in dot format (explained in our lecture on Graphviz/Dot) that shows the difference between interpreters and compilers. You can lay this out however you’d like, but the following items should definitely be present in one, or both, of the graphs (though not necessarily connected in the diagram!). These are in alphabetical order, so don’t assume that their order reveals anything about how the diagram should be layed out. If you can think of other things that belong in the diagram, feel free to include them.

In order to get the points for this, we will take your description in dot and run dot on it. If it does not produce an output, you will get not points.

If it produces an output that is a good-faith effort (i.e. there is a clear attempt and showing the difference between compilers and interpreters, you will get 5 points. If it accurately shows the difference you will get 10 points.

    ← prev  up  next →