CS320 Programming Languages
Midterm Exam
April 23, 2018 9:00AM ~ 11:00AM
Student ID: _____________________ Name:______________________
Instruction: You have 120 minutes to complete this closed-book, closed-note, closed-computer exam. Please write all answers on the provided answer sheet. Write your answers in English only.
1. Different programming languages have different purposes and target application domains, which lead them to make different design choices. For 2 programming languages of your choice not from this course like FAE and F1WAE but from real world like C, C++, Java, Racket, Kotlin, Python, OCaml, JavaScript and etc., compare their pros and cons clearly.
2. Explain what first-class functions are and write a code example that uses a first-class function in your favorite language (Rust, JavaScript, Java, C++, Racket, ……)
3. Given the following grammar:
| { +
| { *
| { let {
| {
Describe whether each of the following is in
(a) {let{x{+56}}{+8{-x4}}}
(b) {deffun {f 6} {let {x 3} {f x}}}
(c) {with {y 7} {with {x 10} {* x y}}} (d) {let{f{+x5}}{f{+356}}}
(e) {let {f 10} {f {f f}}}
4. Consider the following FWAE syntax and abstract syntax. The semantics of FWAE and FAE(without with expression) are the same as you have learned in the class.
| { +
| { with {
| {fun {
| {
(define-type FWAE
[num (nnumber?)]
[add (lhs FWAE?) (rhs FWAE?)]
[with (name symbol?) (named-expr FWAE?) (body FWAE?)] [id (name symbol?)]
[fun (param symbol?) (body FWAE?)]
[app (ftn FWAE?) (arg FWAE?)])
; subst: FWAE symbol FWAE -> FWAE
; num+: FWAE FWAE -> FWAE
; We will assume that subst and num+ are properly defined.
; interp: FWAE -> FWAE
(define (interp fwae)
(type-case FWAE fwae
[num (n) fwae]
[add (l r) (num+ (interp l) (interp r))] [with (x i b) (interp (subst b x (interp i)))]
[id (s) [fun (x b) [app (f a)
(error ’interp “free indentifier”)]
fwae]
(local [(define ftn (interp f))]
(interp (subst (fun-body ftn)
(fun-param ftn)
(interp a))))]))
We can define FAE by removing with from FWAE without reducing expressive power. That is, we can rewrite a FWAE program to the FAE program without changing program semantics. An example is
(test(interp(parse’{with{x10}x})) (interp(parse’{{fun{x}x}10}))).
(a) Rewrite the following code without using with. You should not “interpret (evaluate)” the code. i. {with {f {fun {x} {+ x 10}}} {f 5}}
ii. {with {y 10} {fun {x} {+ y x}}} iii. {fun {body-prod}
{with {fX {fun {fX}
{with {f {fun {x} {{fX fX} x}}}
{body-proc f}}}}
{fX fX}}}
(b) We are going to write a transformer “transf” that will rewrite a FWAE program in abstract syntax to the FAE program in abstract syntax. That is, a function “transf” will rewrite “with” expression into function application form as you did in (a) with source programs.
(test (transf (parse ’{ with { x 10 } x } )) (parse ’{ { fun { x } x } 10 } ))
; tranf: FWAE -> FAE
(define (transf fwae)
(type-case FWAE fwae
[num (n) _________(A)________________ ]
[add (l r) (add ___(B)___ ____(C)____ ]
[with (x i b) ___________(D)________________ ]
[id (s) (id s) ]
[fun (x b) (fun ___(E)___ ______(F)_______ ) ] [app (f a) (app _________(G)_____________
_________(H)____________ )]))
5. With the following list of functions in F1WAE (which is as same as F1LAE of problem 3):
{deffun {twice x} {+ x x}}
{deffun {x y} y}
{deffun {f x} {+ x 1}}
{deffun {g g} g}
Show the results of evaluating the following expressions. When it is an error, describe which error it is.
(a) {twice twice}
(b) {with {x 5} {x x}} (c) {g 3}
(d) {g f}
(e) {g g}
6. Which of the following are examples of shadowing?
(a) {with {x {with {x 3} {- 5 x}}} {+ 1 x}}
(b) {with {x 3}
{with {y 5} {+ 1 x}}}
(c) {with {x 3}
{with {x 5} {+ 1 x}}}
7. Consider the following language e:
e ::= n |{-ee}
|b
| {andee} | {note}
| {ifeee} |x
| {fun{x}e} |{ee}
; integer
; subtraction
; boolean
; logical and (no short-circuiting, evaluate both e’s) ; logical not
; conditional, the same if that you know about
; identifier
; function declaration
; function application
where n denotes a number, b denotes a boolean, x denotes an identifier, and a value v of the language is one of a number, a boolean, or a closure <x. e, >. It does not support the short-circuiting semantics.
v ::= n
|#t |#f
| <x.e, >
∈Env=Var Val
∪ ∪ <x.e, > ∈ = Exp Env
(a) Write the operational semantics of the form σ ⊢
(Example: if we have { * e e }, we would have a semantics rule:
⊢1 ⟹1 ⊢2 ⟹2 ⊢ ∗ 1 2 ⟹ 12
(b) Write the evaluation derivation of the following expression. First, state the result of the expression. Then draw the proof tree.
φ ⊢ 8 ⟹
v ∈ Val =
⇒
for the expressions.