- [BNF] The following is the FOURAE programming language which supports four fundamental arithmetic expressions but is incomplete.
For concrete syntax, we use +, -, *, / for addition, subtraction, multiplication, division operators respectively.
Note: ? (an item is optional), + (an item exists 1 or more times), '-' followed by digits, e.g., -4, means a negative sign but not an operator for subtraction.
(1) Choose all wrong expressions based on the given BNF. (1P)
(a) {/ 2 {- -4 {+ 5 6}}}
(b) {+ 0001 2.4}
(c) {* {/ 4 2} {/ 3 {/ 4 2}}}
(d) {* 1 4}
(e) {- -4 2}
(f) {- {+ 2 3} {/ {+ 2 3} {- 12.4 3.4}}}
(a), (f)
두 경우 모두, - operation 이후에는 number가 연달아 나와야 하는데 - <number><FOURAE>가 나왔으므로 틀렸다.
(2) Update the BNF above to support all expressions in (1).
먼저 a가 가능하려면 - 부호 이후에 FOURAE로 바꿔야 하고, f의 경우에는 / operation 이후에 FOURAE가 나오게 바꿔주면 된다.
- Answer for the following expression. (4P)
{with {y 7} {+ x {with {x y} x}}}
{{fun {y} {+ x {with {x y} x}}} 7}
(1) Found all binding identifiers (1P):
(2) There is one free identifier which is the first x (1P): True | False
(3) The second y is the bound identifier (1P): True | False
(4) When this expression is interpreted, it results in an error (1P): True | False
- [Laziness] Circle true (T) or false (F).
(1) The idea of the laziness concept is that evaluation of a function argument is deferred when a function is called (1P) ⇒ T | F
(2) The purpose of applying laziness is to make an interpreter efficient by avoiding interpreting an argument expression when we do not need the value of the argument. (1P) ⇒ T | F
(3) The points where the implementation of a lazy language forces an expression to reduce to a value (if any) are called the strictness points of the language. (1P) ⇒ T | F
(4) There are two strictness points (Line#7 and Line#19) in the following LFAE code and we need to set them as strictness points because both id and function definition can be an argument expression of another function to be evaluated later. (1P) T | F
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
;;...
(define (lookup name ds)
(type-case DefrdSub ds
[mtSub () (error 'lookup "free identifier")][aSub (i v saved) (if(symbol=? i name)
(strict v) ;; if v is exprV (num ==> interp it
(lookup name saved))]))
; interp: LFAE DefrdSub -> LFAE-Value
; purpose: to get LFAE-Value from LFAE
(define (interp lfae ds)
(type-case LFAE lfae
[num (n) (numV n)][add (l r) (num+ (interp l ds) (interp r ds))]
[sub (l r) (num- (interp l ds) (interp r ds))][id (s) (lookup s ds)]
[fun (p b) (closureV p b ds)]app (f a) (local [(define f-val (strict (interp f ds)))
(define a-val (exprV a ds (box #f)))]
(interp (closureV-body f-val)
(aSub (closureV-param f-val)
a-val
(closureV-ds f-val))))]))
- [Recursion] As you can recall HW3 task 2 and 3, there were different ways to implement recursion (using syntactic sugar and updating an interpreter). What is the common problem we have to solve when implementing recursion? Explain with an example (the example can be either a code example with explanation or just textual explanation). (3P)
- [Recursion] Discuss the advantage of implementing recursion using syntactic sugar. (1P)
- [Mutable Data Structure] What is the store passing style (SPS)? Why do we need this programming style when implementing mutable data structure? (2P)
-
[Variable] The following Racket code is a part of BMFAE that supports the variable concept. Answer the following questions.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
(define (interp rbmfae ds st)
(type-case BMFAE rbmfae
...
[fun (p b) (v*s (closureV p b ds) st)][refun (p b) (v*s (refclosV p b ds) st)]
[app (f a) (type-case ValueStore (interp f ds st)
[vs (f-value f-store)
(type-case RBMFAE-Value f-value
[refclosV (rc-param rc-body rc-ds)
(local ([define address (lookup (id-name a) ds)])
(interp rc-body
(aSub rc-param
address
rc-ds)
f-store))]
[closureV (c-param c-body c-ds)
(type-case ValueStore (interp a ds f-store)
[vs (a-value a-store)
(local ([define new-address (malloc a-store)])
(interp (closureV-body f-value)
(aSub (closureV-param f-value)
new-address
(closureV-ds f-value))
(aSto new-address
a-value
a-store)))])][else (error interp "trying to apply a number")])])]...1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
(1) The `app' branch deals with both call-by-value and call-by-reference. Write the most important line numbers that implement call-by-value and call-by-reference. (2P)
Call-by-value
The most important Line#:
Why and how does it implement call-by-value in terms of memory use?
Call-by-reference
The most important Line#:
Why and how does it implement call-by-reference in terms of memory use?
(2) The interpreter deals with two syntactic expressions, fun and refun, for call-by-value and call-by-reference as follows. Update the existing BNF to support only fun but developers can support both call-by-value and call-by-reference by putting the & symbol in front of the parameter name. For example, {fun {&a} {seqn {setvar a 1} a}} is for a function with call-by-reference and {fun {a} {seqn {setvar a 1} a}} is for a function with call-by-value. Update BNF for this. Use a line number to explain your thoughts. (2P)
::=
| {+ }
| {- }
|
| {fun {} }
| {refun {} }
| { }
| {newbox }
| {setbox }
| {openbox }
| {seqn }
| {setvar }
1
2
3
4
5
6
7
8
9
10
11
12
Note: postfix* means "repeated 0 or more times", postfix+ means "repeated 1 or more times", and postfix? means "0 or 1 times"
Answer here:
- [First class function] By using the lambda function, we implemented the interp-two function by using the lambda function and branches such as`add have been updated by using it.
(define (interp bmfae ds st)
...
; add implementation
[add (l r) (type-case ValueStore (interp l ds st)
[vs (l-value l-store)
(type-case ValueStore (interp r ds l-store)
[vs (r-value r-store)
(vs (num+ l-value r-value)
r-store)])])]
[sub (l r) (type-case ValueStore (interp l ds st)
[vs (l-value l-store)
(type-case ValueStore (interp r ds l-store)
[vs (r-value r-store)
(vs (num- l-value r-value)
r-store)])])]
;;;-------------------------------------------------------------------------------------------------------------
(define (interp bmfae ds st)
...
; add implementation with the nterp-two function
[add (l r) (interp-two l r ds st (lambda (v1 v2 st1) (v*s (num+ v1 v2) st1)))][sub (l r) (interp-two l r ds st (lambda (v1 v2 st1) (v*s (num- v1 v2) st1)))]
...
....
(define (interp-two expr1 expr2 ds st handle)
(type-case ValueStore (interp expr1 ds st)
[vs (val1 st2)
[type-case ValueStore (interp expr2 ds st2)
[vs (val2 st3)
(handle val1 val2 st3)]]]))
(1) What is the benefit of implementing the interp-two function? (1P)
(2) Discuss the role of the first class function (the lambda expression) in terms of implementing a function like interp-two. (1P)
- [Continuation] Why is learning language concepts such as continuation important? (2P)
