Solution Files

You can find the solutions in the hw09.sql file.

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 'cond
		(map (lambda (case) (cons `(equal? ,expr (quote ,(car case))) (cdr case)))
    			cases))
)

Use Ok to test your code:

python3 ok -q switch