AdministrativeThis exam is intended for two hours. The question scores sum up to
a total of 127 points, but it will be graded “out of a 100” so you can skip more than
a whole question, small pieces, or just shoot for a bonus.
|
| |||||||||||||||||||||||||||||||
Write a Racket function called subseq? that accepts two lists, and determines whether the first one is a sub-sequence of the second. A list L1 is a sub-sequence of a list L2 if and only if the members of L1 all apear in L2 in the same order, possibly with other values in between them.
Examples (as test cases) — all of these are true:
(test (subseq? '() '(1 2 3))) (test (subseq? '(1 2 3) '(1 2 3))) (test (subseq? '(1 2 3) '(0 1 0 2 0 3 0))) (test (subseq? '(1 2 3) '(1 1 2 2 3 3))) (test (subseq? '(1 1 2 3) '(1 1 11 2 3))) (test (not (subseq? '(1 1 2 3) '(1 2 3)))) (test (not (subseq? '(1 1 2 3) '(1 2 1 3)))) |
In class we have seen the currify higher-order function that converts a function of two inputs to a single-argument function that returns a single-argument function.
Here is the code and some examples:
(: currify : (All (A B C) (A B -> C) -> (A -> B -> C))) ;; convert a double-argument function to a curried one (define (currify f) (lambda (x) (lambda (y) (f x y)))) (define plus (currify +)) (test 3 ((plus 1) 2)) (test 3 (((currify +) 1) 2)) (test '(2 3 4) (map (plus 1) '(1 2 3))) |
Write a similar higher-order function, currify3, that converts three-argument functions into a three-staged curried function. Again, don’t forget a proper type and purpose statement.
Obviously, this not the only way of currying a three argument function. Instead of a three-level curried function, we could have used a two level function. There are two ways to do that: write the type definitions for these two options. (Just the type, not the code.)
Write a BNF grammar for the language of palindromes over A, B, and C. Make sure that your grammar can derive palindromes of both even and odd lengths. For example, your grammar should be able to derive all of these: ABCCBA, ABCBA, C, CCCC. For this, we consider a palindrome as an actual word — so the empty string should not be in the language.
(* (blank) 2) |
(define blank (lambda () 330)) |
In class, we have defined a “closed” expression as one that does not have any free identifiers. This is a property that is usually necessary for correct programs in a lexically scoped language, and it is one that can be checked statically, without running the code. For example, if we take care to check that the original program that is fed to our substitution-based evaluator is closed, then we avoid the obvious bug that we have talked about when it is made to do lazy evaluation.
Write such a predicate, closed?, that takes in a FLANG syntax value and determines whether it is closed. (Use the FLANG evaluator for the type definition.)
Here are a few test cases to help:
(test (closed? (parse "{+ 1 2}")))
(test (closed? (parse "{with {x 5} {+ 1 2}}")))
(test (closed? (parse "{fun {x} {+ 1 x}}")))
(test (closed? (parse "{with {x 1} {with {y x} {+ x y}}}")))
(test (not (closed? (parse "{+ 1 x}"))))
(test (not (closed? (parse "{with {x x} {+ 1 x}}")))) |
Implementation hint: write a helper function that uses an additional arguments holding a list of the currently known-to-be bound identifiers. This helper should do most of the work, and closed? is actually a simple wrapper that calls it. (You need to write a proper type for the helper function too.)
As we have seen, the semantics of call, like the semantics of with, are eager: the argument is evaluated before the substitution happens. We want to extend the substitution-based FLANG evaluator (FLANG-ENV) with a lcall construct that is similar to call except that it is lazy. (Important: do not use the environment-based evaluator for this!)
As usual, this requires a few changes to the code.
<FLANG> ::= ...same...
| { lcall <FLANG> <FLANG> } |
(define-type FLANG ;; ...same... [LCall FLANG FLANG]) |
(: parse-sexpr : Sexpr -> FLANG)
(define (parse-sexpr sexpr)
(match sexpr
...same...
[(list 'call fun arg) (Call (parse-sexpr fun) (parse-sexpr arg))]
[(list 'lcall fun arg) (LCall (parse-sexpr fun) (parse-sexpr arg))]
...same...)) |
(: subst : FLANG Symbol FLANG -> FLANG)
(define (subst expr from to)
(cases expr
...same...
[(Call l r) (Call (subst l from to) (subst r from to))]
[(LCall l r) (LCall (subst l from to) (subst r from to))]
...same...)) |
The main work is the new semantics: the definition and the corresponding eval definition. Begin with the new evaluation rule for lcall expressions, and then extend eval to implement this rule for instances of LCall. For both of these, you don’t need to copy the existing set of rules and the eval code — write only the new rule, and the new LCall clause for eval.
In our encoding of Church numerals, we have defined the zero? predicate as follows:
(define zero? (lambda (n) (n (lambda (x) #f) #t))) |
As we know, if n is a function that encodes a number N, then it applies its first argument over its second argument N times. Since this is exactly what this definition of zero? does, an important question is whether it is fast or not. In other words, if it is used with a very large number, say 1000000, would we need a huge number of evaluation steps to compute (zero? 1000000)?
Show that this is not the case, and that zero? would still require only the same (small) number of steps to return #f when given a big number. Do this by starting from (zero? 4) and showing how it reduces to #f. (You can use either (lambda (f x) (f (f (f (f x))))) or (add1 3) as the definition of 4.)
Unless told otherwise, choose the best answer in each of the following questions. (Note that there could be several answers that are correct, but one should be the most accurate.)