Due by 11:59pm on Thursday, April 22
Submission: When you are done, submit with
--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
Using Ok: If you have any questions about using Ok, please refer to this guide.
Readings: You might find the following references useful:
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.
Assignment Hint Video
This video provides some helpful direction for tackling problems on this assignment.
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
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
Q3: WWSD: Eval and Apply
How many calls to
scheme_applywould 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______6scm> (+ 2 4 6 8) ; number of calls to scheme_apply______1scm> (+ 2 (* 4 (- 6 8))) ; number of calls to scheme_eval______10scm> (+ 2 (* 4 (- 6 8))) ; number of calls to scheme_apply______3scm> (if #f (+ 2 3) (+ 1 2)) ; number of calls to scheme_eval______5scm> (if #f (+ 2 3) (+ 1 2)) ; number of calls to scheme_apply______1scm> (define (cube a) (* a a a)) ; number of calls to scheme_eval______1scm> (define (cube a) (* a a a)) ; number of calls to scheme_apply______0scm> (cube 3) ; number of calls to scheme_eval______8scm> (cube 3) ; number of calls to scheme_apply______2
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
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