{"size": 7875, "ext": "scrbl", "max_stars_repo_path": "www/midterms/1.scrbl", "max_stars_repo_name": "plum-umd/cmsc838e", "max_stars_repo_stars_event_min_datetime": "2021-01-27T00:45:41.000Z", "max_stars_repo_stars_event_max_datetime": "2021-01-27T00:45:41.000Z", "max_issues_repo_path": "www/midterms/1.scrbl", "max_issues_repo_name": "plum-umd/cmsc838e", "max_issues_repo_issues_event_min_datetime": null, "max_issues_repo_issues_event_max_datetime": null, "max_forks_repo_path": "www/midterms/1.scrbl", "max_forks_repo_name": "plum-umd/cmsc838e", "max_forks_repo_forks_event_min_datetime": "2021-04-16T11:44:17.000Z", "max_forks_repo_forks_event_max_datetime": "2021-04-16T11:44:17.000Z"}
{"max_stars_count": 1, "max_issues_count": null, "max_forks_count": 1, "avg_line_length": 27.4390243902, "max_line_length": 89, "alphanum_fraction": 0.6996825397}
#lang scribble/manual

@(require (for-label racket))

@title{Midterm 1}

@bold{Due: Tuesday, October 13th 11:59PM}

@(define repo "https://classroom.github.com/a/Fj9gbJzI")

Midterm repository:
@centered{@link[repo repo]}

The repository contains a single plaintext file @tt{m1.txt}, which you
can edit to submit your answers to the following questions.  Your
submission must be pushed by 11:59 EDT on Tuesday, October 13th.

During the 72 hours of the exam period, you may only ask private questions to
the staff (via email, discord, etc.) if you need clarification.
You may not communicate or collaborate with any one else about the
content of this exam.

Questions that are deemed applicable to the entire class will be shared, along
with their responses, with the rest of the class.

@section{Short answer}

@bold{Question 1}

[10 points]

Assuming that the value in @tt{rax} is 42 and the value in @tt{rsp} is 1024,
briefly describe the difference, if any, between these two Asm instructions.
Ensure that you mention what the value residing in @tt{rax} would be after
executing each of these.

@verbatim{
(mov rax rsp)
}

@verbatim{
(mov rax (offset rsp 0))
}

@bold{Question 2}

[10 points]

Assume that the register @tt{rbx} currently holds the value 2048.
Please write two sequences of instructions.
The first should load the value @emph{stored} at address 2048 in memory,
and place that value in @tt{rax}.
The second should store the value 42 at address 2048.


@section{Representation}

@bold{Question 3}

[20 points]

When studying the @secref{Dupe} language, we used the least
significant bit of a 64-bit integer to indicate whether the value
being represented was an integer (tagged with @code[#:lang
"racket"]{#b0}) or a boolean (tagged with @code[#:lang
"racket"]{#b1}).

What is one alternative approach to disambiguating types at runtime (i.e. not
a static type system)? It can be a completely new design of your own if you'd like.

One way to consider the possibilities is to think about how you would implement the logic
we use in @tt{main.c} to determine how to print the value returned by running the code
that was generated by our compiler.

Once you've described your chosen alternative approach, do the following:

@itemlist[

@item{Describe one way in which this design is worse that the tagging
approach we have used in class.}

@item{Describe one way in which this design is better than the tagging approach
used in class.}

@item{Describe, at a high-level in English, how you could implement
@racket[add1] using this design.}

]

@section{Interpreting Variadic Primitive}

@bold{Question 4}

[25 points]

Consider the following interpreter from @secref{Extort}.

@#reader scribble/comment-reader
(racketblock 
;; type Answer = Value | 'err
 
;; Expr -> Answer
(define (interp e)
  (match e
    [(int-e i) i]
    [(bool-e b) b]
    [(add1-e e0)
     (match (interp e0)
       [(? integer? i) (add1 i)]
       [_ 'err])]
    [(sub1-e e0)
     (match (interp e0)
       [(? integer? i) (sub1 i)]
       [_ 'err])]
    [(zero?-e e0)
     (match (interp e0)
       [(? integer? i) (zero? i)]
       [_ 'err])]
    [(if-e e0 e1 e2)
     (match (interp e0)
       ['err 'err]
       [v
        (if v
            (interp e1)
            (interp e2))])]))

)

Now extend the interpreter to include @racket[+] and @racket[*]
functions similar to those found in Racket.

Unlike our language @tt{Grift}, both of these forms can take any number of
subexpressions. The subexpressions are evaluated from left to right, but should
halt when one of the subexpressions results in an error, or if one of the
subexpressions is not an integer. The resulting error should be propagated up,
as it is in the interpreter above. Aside from the possible error conditions,
the resulting value should be the @emph{sum} and @emph{product} (for @tt{+} and
@tt{*}, respectively) of the subexpressions. If there are @emph{no}
subexpressions, the result should be the identity element for the given
operation (see the examples below).

For example:

@#reader scribble/comment-reader
(racketblock 
;; The following would result in 26
(+ 5 6 7 8)

;; The following would result in 0
(+)
 
;; The following would result in 1680
(* 5 6 7 8)

;; The following would result in 1
(*)

;; Both of the following would result in 'err
(+ 5 6 #t 8)
(* 5 (zero? #t) 7 8)

)

To make things interesting, you should not use Racket's variadic @racket[+] and
@racket[*] in @racket[interp] (but you can use them as binary operators, e.g.
@tt{(+ a b)} is okay but @tt{(+ a b c)} is not).

You can assume two new AST nodes @tt{sum-e} and @tt{prod-e} that each have one
field, which is a list of expressions.

@section{Writing a transformation over the AST}

@bold{Question 5}

[35 points]

In our language @secref{Grift}, we briefly discussed the notion of
Administrative Normal Form (ANF). We will take inspiration from ANF
and make the following restriction on our ASTs for @tt{Grift}: all
primitive operations (i.e. anything of the form @tt{prim-e p es} can
only have @emph{variables} and @emph{literals} as subexpressions (i.e.
@tt{var-e}, @tt{int-e}, and @tt{bool-e}).

Restrictions like this are popular in compilers because they make certain
analyses and optimizations more straightforward, but no one would want to
@emph{program} with these restrictions. So compiler writers @emph{transform}
their programs into this form.

Your task is to write a compiler @emph{transformation}, @tt{to-restricted} that
takes ASTs without this restriction and produces ASTs that abide by this
restriction.  You will do this by recursively `lifting out' complex expressions
and binding them to a new variable with a @tt{let} (use @tt{gensym} for
creating new variable names, just make sure you keep track!).

Things that may make your life easier:

@itemlist[

@item{If you'd like, you can use the generalized @tt{let-e} from Assignment \#4.}

@item{Redundant @tt{let-e}'s are fine, as long as the restriction described above
is maintained.}

]

Below we have provided all of the uninteresting bits of the traversal. You will
need to fill in the rest.  I urge you to define helper functions and explain
your reasoning with comments. If you document your thought process well, you
are more likely to get partial credit.

@#reader scribble/comment-reader
(racketblock
;; Expr -> Expr
(define (to-restricted e)
  (match e
    [(int-e i)     e]
    [(bool-e b)    e]
    [(var-e v)     e]
    [(if-e e t f)  (if-e (to-restricted e) (to-restricted t) (to-restricted f))]
    [(let-e bs b)  (let-e (restrict-binds bs) (to-restricted b))]
    [(prim-e p es)
      (error "TODO")]))

(define (restrict-binds bnds)
  (match bnds
    ['() '()]
    [(cons (binding v e) bnds) (cons (binding v (to-restricted e))
                                     (restrict-binds bnds))]))
)

@subsection{Example 1}

@#reader scribble/comment-reader
(racketblock
(prim-e '+ (list (var-e 'x) (var-e 'y)))
)

Would be unchanged.

@subsection{Example 2}

@#reader scribble/comment-reader
(racketblock
(prim-e
 '+
 (list (prim-e 'sub1 (list (int-e 5))) (prim-e 'add1 (list (int-e 5)))))
)

Becomes:

@#reader scribble/comment-reader
(racketblock
(let-e
 (list
  (binding 'g348 (prim-e 'sub1 (list (int-e 5))))
  (binding 'g347 (prim-e 'add1 (list (int-e 5)))))
 (prim-e '+ (list (var-e 'g348) (var-e 'g347))))
)

@subsection{Example 3}

Don't forget about nested expressions!

@#reader scribble/comment-reader
(racketblock
(prim-e
 '+
 (list
  (prim-e 'sub1 (list (prim-e 'sub1 (list (int-e 6)))))
  (prim-e 'add1 (list (int-e 5)))))
)

Becomes:

@#reader scribble/comment-reader
(racketblock
(let-e
 (list
  (binding
   'g352
   (let-e
    (list (binding 'g353 (prim-e 'sub1 (list (int-e 6)))))
    (prim-e 'sub1 (list (var-e 'g353)))))
  (binding 'g351 (prim-e 'add1 (list (int-e 5)))))
 (prim-e '+ (list (var-e 'g352) (var-e 'g351))))
)
