Due by 11:59pm on Thursday, April 22

Instructions

Download hw09.zip.

Submission: When you are done, submit with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on okpy.org. See Lab 0 for more instructions on submitting assignments.

Using Ok: If you have any questions about using Ok, please refer to this guide.

Readings: You might find the following references useful:

• Section 3.5 - Interpeters

Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus. This homework is out of 2 points.

Questions

BNF

Q1: EBNF for PyCombinator

Consider this attempt at an EBNF grammar for Pycombinator, the Python subset that we worked with Lab 11.

?start: pycomb_call

pycomb_call: func "(" arg ("," arg)* ")"

arg: pycomb_call | NUMBER

func: FUNCNAME

FUNCNAME: "add" | "mul" | "sub"

%ignore " "
%import common.NUMBER

Let's understand and modify the functionality of this BNF with a few questions.

Use Ok to test your knowledge by choosing the best answer for each of the following "What Would PyCombinator Do" questions:

python3 ok -q wwpd-bnf -u

RegEx

Q2: What would RegEx Match?

For each of the following regular expressions, suggest a string that would be fully matched.

Use Ok to test your knowledge by choosing the best answer for each of the following questions:

python3 ok -q wwrm -u

Interpreters

Q3: WWSD: Eval and Apply

How many calls to scheme_eval and scheme_apply would it take to evaluate each of these Scheme expressions? Use Ok to test your knowledge by writing the number of calls needed to evaluate each expression:

python3 ok -q wwsd-eval_apply -u

scm> (+ 2 4 6 8) ; number of calls to scheme_eval
______
6
scm> (+ 2 4 6 8) ; number of calls to scheme_apply
______
1
scm> (+ 2 (* 4 (- 6 8))) ; number of calls to scheme_eval
______
10
scm> (+ 2 (* 4 (- 6 8))) ; number of calls to scheme_apply
______
3
scm> (if #f (+ 2 3) (+ 1 2)) ; number of calls to scheme_eval
______
5
scm> (if #f (+ 2 3) (+ 1 2)) ; number of calls to scheme_apply
______
1
scm> (define (cube a) (* a a a)) ; number of calls to scheme_eval
______
1
scm> (define (cube a) (* a a a)) ; number of calls to scheme_apply
______
0
scm> (cube 3) ; number of calls to scheme_eval
______
8
scm> (cube 3) ; number of calls to scheme_apply
______
2

Macros

Q4: Switch

Define the macro switch, which takes in an expression expr and a list of pairs, cases, where the first element of the pair is some value and the second element is a single expression. switch will evaluate the expression contained in the list of cases that corresponds to the value that expr evaluates to.

scm> (switch (+ 1 1) ((1 (print 'a))
                      (2 (print 'b))
                      (3 (print 'c))))
b

You may assume that the value expr evaluates to is always the first element of one of the pairs in cases. You can also assume that the first value of each pair in cases is a value.

(define-macro (switch expr cases)
	(cons _________
		(map (_________ (_________) (cons _________ (cdr case)))
    			cases))
)

Use Ok to test your code:

python3 ok -q switch