Continuations

COMP 105 Assignment

Due Tuesday, October 9, 2018 at 11:59PM

This assignment is all individual work. There is no pair programming.

Overview

Continuations are a key technology in event-driven user interfaces, such as are found in games and in many Web frameworks. They are also used to implement sophisticated control flow, including backtracking. This assignment introduces you to continuations through backtracking search. It also gives you additional experience with higher-order, polymorphic functions. The assignment builds on the previous two assignments, and it adds new ideas and techniques that are described in section 2.10 of Build, Prove, and Compare.

Setup

The executable μScheme interpreter is in /comp/105/bin/uscheme; if you are set up with use comp105, you should be able to run uscheme as a command. The interpreter accepts a -q (“quiet”) option, which turns off prompting. Your homework will be graded using uscheme. When using the interpreter interactively, you may find it helpful to use ledit, as in the command

  ledit uscheme

In this assignment, you may find the &trace feature especially useful. It is described in the Scheme homework.

Dire Warnings

The μScheme programs you submit must not use any imperative features. Banish set, while, println, print, printu, and begin from your vocabulary! If you break this rule for any exercise, you get No Credit for that exercise. You may find it useful to use begin and println while debugging, but they must not appear in any code you submit. As a substitute for assignment, use let or let*.

Except as noted below, do not define helper functions at top level. Instead, use let or letrec to define helper functions. When you do use let to define inner helper functions, avoid passing as parameters values that are already available in the environment.

Your solutions must be valid μScheme; in particular, they must pass the following test:

    /comp/105/bin/uscheme -q < myfilename > /dev/null

without any error messages or unit-test failures. If your file produces error messages, we won’t test your solution and you will earn No Credit for functional correctness. (You can still earn credit for structure and organization). If your file includes failing unit tests, you might possibly get some credit for functional correctness, but we cannot guarantee it.

We will evaluate functional correctness by testing your code extensively. Because this testing is automatic, each function must be named be exactly as described in each question. Misnamed functions earn No Credit.

Reading Comprehension (10 percent)

These questions are meant to guide you through the readings that will help you complete the assignment. Keep your answers brief and simple.

As usual, you can download the questions.

  1. Section 2.12.3, which starts on page 157, describes the semantics of the true-definition forms. Use the semantics to answer two questions about the following sequence of definitions:

    (val f (lambda () y))
    (val y 10)
    (f)

    Given evaluating lambda in an environment ρ creates a closure using that same ρ, if the definitions above are evaluated in an environment in which y ∈ domρ, then what is the result of the call to f? Pick A, B, or C.

    1. It returns 10.
    2. An error is raised: Run-time error: name y not found.
    3. It returns whatever value y had before the definitions were evaluated.

    If the definitions above are evaluated in an environment in which y ∉ domρ, what is the result of the call to f? Pick either A or B.

    1. It returns 10.
    2. An error is raised: Run-time error: name y not found.

    You are ready to start problem 45.

  2. Read the description of Boolean formulas in the section “Representing Boolean formulas” below. Then read about μScheme’s syntactic sugar for records in section 2.16.6, which starts on page 194. Now assume you are given a formula f0, and answer these questions:

    • How, in constant time, do you tell if f0 has the form (make-not f)?

    • How, in constant time, do you tell if f0 has the form (make-and fs)?

    • How, in constant time, do you tell if f0 has the form (make-or fs)?

    You are ready to start problems L and F.

  3. Read the definition of evaluation in problem E below.

    Each of the following Boolean formulas is evaluated in an environment where x is #t, y is #f, and z is #f. What is the result of evaluating each formula? (For each formula, answer #t, “true”, #f, or “false.”)

    1. x, which in μScheme is constructed by 'x

    2. ¬x, which in μScheme is constructed by (make-not 'x)

    3. ¬y ∧ x, which in μScheme is constructed by (make-and (list2 (make-not 'y) 'x))

    4. ¬x ∨ y ∨ z, which in μScheme is constructed by
      (make-or (list3 (make-not 'x) 'y 'z))

    5. Formula (make-not (make-or (list1 'z))), which has a tricky make-or applied to a list of length 1, and so can’t be written using infix notation

    You are ready to start problem E.

  4. Read about the Boolean-satisfaction problem for CNF formulas, in section 2.10.1, which starts on page 143. The rules for satisfaction are the same for all Boolean formulas, even those that are not in CNF.

    For each of the following Boolean formulas, if there is an assignment to x, y, and z that satisfies the formula, write the words “is solved by” and a satisfying assignment. Incomplete assignments are OK. If there is no satisfying assignment, write the words “has no solution.”

    Examples:

    x‌ ∨ y ∨ z, which in μScheme is constructed by (make-or '(x y z)), is solved by '((x #t))

    x ∧ y ∧ z, which in μScheme is constructed by (make-and '(x y z)), is solved by '((x #t) (y #t) (z #t))

    x ∧ ¬x, which in μScheme is constructed by (make-and (list2 'x (make-not 'x))), has no solution

    For each of these formulas, replace the ellipsis with your answer:

    1. (x ∨ ¬x) ∧ y, which in μScheme is constructed by
      (make-and (list2 (make-or (list2 'x (make-not 'x))) 'y)),

    2. (x ∨ ¬x) ∧ ¬x, which in μScheme is constructed by
      (make-and (list2 (make-or (list2 'x (make-not 'x))) (make-not 'x))),

    3. (x ∨ y ∨ z) ∧ (¬x ∧ x) ∧ (x ∨ ¬y ∨ ¬z), which in μScheme is constructed by

      (make-and 
          (list3 (make-or (list3 'x 'y 'z)) 
                 (make-and (list2 (make-not 'x) 'x))
                 (make-or (list3 'x (make-not 'y) (make-not 'z))))))

    You are ready to start problems S and T.

Programming and Language Design (90 percent)

You will explore an alternative semantics for val (45), and you will solve four problems related to Boolean formulas: recognize a special list (L), recognize a formula (F), evaluate a formula (E), and a solve a formula (S). You will also submit test cases for the solver (T). Problems L, F, E, and S require algebraic laws.

Language-design problem

45. Operational semantics and language design. Do all parts of exercise 45 on page 226 of Build, Prove, and Compare. Be sure your answer to part (b) compiles and runs under uscheme.

Related reading: Rules for evaluating definitions in section 2.12.3, especially the two rules for VAL.

Representing Boolean formulas

This homework involves Boolean formulas. We represent a formula either as a symbol or a record (“struct”), using the following record definitions:

(record not [arg])
(record or  [args])
(record and [args])

In the context of these definitions, a formula is one of the following:

Programming problems

L. Recognizing lists. Define a higher-order function list-of?, which takes two arguments:

Calling (list-of? A? v) returns a Boolean that is #t if v is a list of values, each of which satisfies A?. Otherwise, (list-of? A? v) returns #f.

Hints:

Related reading: Section 2.2, which starts on page 94. And if you need to, the handout “Programming With Scheme Values and Algebraic Laws”, which was first distributed with the scheme homework.

Laws: Function list-of? needs algebraic laws. The last law may include a side condition “all other forms.”

F. Recognizing formulas. Define a function formula?, which when given an arbitrary μScheme value, returns #t if the value represents a Boolean formula and #f otherwise. Follow the above definition of formulas exactly.

A straightforward solution that uses if expressions and “how were you formed?” questions takes 10 lines of μScheme. If you want to get clever with short-circuit operators, you can cut that in half.

Hints:

Related reading: Section 2.2, which starts on page 94. The definition of equal? in section 2.3. The definition of LIST(A) in section 2.6.

Laws: Function formula? needs algebraic laws. In the last law, I encourage you to include a side condition like “v has none of the forms above.” By obviating the need to define a law for every possible form of S-expression, such a law will enable you to focus your laws on just the interesting forms.

E. Evaluating formulas. Define a function eval-formula, which takes two arguments: a formula f and an environment env. The environment is an association list in which each key is a symbol and each value is a Boolean. If the formula is satisfied in the given environment, (eval-formula f env) returns #t; otherwise it returns #f. Evaluation is defined by induction:

It is part of the contract of eval-formula that (eval-formula f env) may be called only when every variable in formula f is bound in env.

My solution is 10 lines, and it is structurally similar to my straightforward implementation of formula?.

You must document your solution with algebraic laws. As usual, we recommend you write the laws before you write the code.

Related reading: The initial basis of μScheme. And if you are uncertain about structure, the implementation of either the Impcore evaluator or the μScheme evaluator. (You could also look at the implementation of a μScheme evaluator in μScheme, which you would find in section 2.15.4, which starts on page 183, but that section has so much detail that it may be easier just to figure out on your own how to structure an evaluator written in μScheme.)

Laws: Function eval needs algebraic laws. The only permissible side condition should be something like “where x is a symbol.”

Your laws should cover only those inputs permitted by eval’s contract. Do not include any laws for inputs that violate the contract. (And in the code, do not include any cases for inputs that violate the contract.)

T. Testing SAT solvers. Create three test cases to test solutions to problem S. Your test cases will be represented by six val bindings, to variables f1, s1, f2, s2, f3, and s3.

As another example, if I wanted to code the test formula

(x ∨ y ∨ z) ∧ (¬z ∨ ¬y ∨ ¬z) ∧ (x ∨ y ∨ ¬z),

I might write

(val f1 (make-and
           (list3 (make-or (list3 'x 'y 'z))
                  (make-or (list3 (make-not 'x) (make-not 'y) (make-not 'z)))
                  (make-or (list3 'x 'y (make-not 'z))))))
(val s1 '((x #t) (y #f)))

As a second test case, I might write

(val f2 (make-and (list2 'x (make-not 'x))))  ; x and not x
(val s2 'no-solution)

Put your test cases into the template at https://www.cs.tufts.edu/comp/105/homework/sat_solver_template.scm.

In comments in your test file, explain why these particular test cases are important—your test cases must not be too complicated to be explained. Consider different combinations of the various Boolean operators.

Design test cases that will find bugs in solvers. (We will run every submitted solver on every submitted test case.)

Related reading: The example formulas and satisfying assignments on page 147 (at the very end of section 2.10.1).

Laws: This problem includes only test cases and results, not any code. No laws are needed.

S. SAT solving using continuation-passing style. Write a function find-formula-true-asst which, given a satisfiable formula in the form, finds a satisfying assignment—that is, a mapping of variables to Booleans that makes the formula true. Remember De Morgan’s laws, one of which is mentioned on page 134.

Function find-formula-true-asst must take three parameters: a formula, a failure continuation, and a success continuation. A call to

(find-formula-true-asst f fail succ)

searches for an assignment that satisfies formula f. If it finds a satisfying assignment, it calls succ, passing both the satisfying assignment (as an association list) and a resume continuation. If it fails to find a satisfying assignment, it calls fail. Notes:

My solution to this exercise is under 50 lines of μScheme.

You’ll be able to use the ideas in section 2.10.1, but not the code. Instead, try using letrec to define the following mutually recursive functions:

In all the functions above, bool is #t or #f. Before defining each of the functions, we recommend completing the following algebraic laws:

(find-formula-asst x            bool cur fail succeed) == ...,
                                                   where x is a symbol
(find-formula-asst (make-not f)  bool cur fail succeed) == ...
(find-formula-asst (make-or  fs) #t   cur fail succeed) == ...
(find-formula-asst (make-or  fs) #f   cur fail succeed) == ...
(find-formula-asst (make-and fs) #t   cur fail succeed) == ...
(find-formula-asst (make-and fs) #f   cur fail succeed) == ...

(find-all-asst '()         bool cur fail succeed) == ...
(find-all-asst (cons f fs) bool cur fail succeed) == ...

(find-any-asst '()         bool cur fail succeed) == ...
(find-any-asst (cons f fs) bool cur fail succeed) == ...

(find-formula-symbol x bool cur fail succeed) == ..., where x is not bound in cur
(find-formula-symbol x bool cur fail succeed) == ..., where x is bool in cur
(find-formula-symbol x bool cur fail succeed) == ..., where x is (not bool) in cur

Include the completed laws in your solution.

The following unit tests will help make sure your function has the correct interface:

(check-assert (procedure? find-formula-true-asst))    ; correct name
(check-error (find-formula-true-asst))                ; not 0 arguments
(check-error (find-formula-true-asst 'x))             ; not 1 argument
(check-error (find-formula-true-asst 'x (lambda () 'fail)))   ; not 2 args
(check-error
   (find-formula-true-asst 'x (lambda () 'fail) (lambda (c r) 'succeed) 'z)) ; not 4 args

These additional checks also probe the interface, but they require at least a little bit of a solver—enough so that you call the success or failure continuation with the right number of arguments:

(check-error (find-formula-true-asst 'x (lambda () 'fail) (lambda () 'succeed)))
    ; success continuation expects 2 arguments, not 0
(check-error (find-formula-true-asst 'x (lambda () 'fail) (lambda (_) 'succeed)))
    ; success continuation expects 2 arguments, not 1
(check-error (find-formula-true-asst
                   (make-and (list2 'x (make-not 'x)))
                   (lambda (_) 'fail)
                   (lambda (_) 'succeed)))
    ; failure continuation expects 0 arguments, not 1

And here are some more tests that probe if you can solve a few simple formulas, and if so, if you can call the proper continuation with the proper arguments.

(check-expect   ; x can be solved
   (find-formula-true-asst 'x
                           (lambda () 'fail)
                           (lambda (cur resume) 'succeed))
   'succeed)

(check-expect   ; x is solved by '((x #t))
   (find-formula-true-asst 'x
                           (lambda () 'fail)
                           (lambda (cur resume) (find 'x cur)))
   #t)

(check-expect   ; (make-not 'x) can be solved
   (find-formula-true-asst (make-not 'x)
                           (lambda () 'fail)
                           (lambda (cur resume) 'succeed))
   'succeed)

(check-expect   ; (make-not 'x) is solved by '((x #f))
   (find-formula-true-asst (make-not 'x)
                           (lambda () 'fail)
                           (lambda (cur resume) (find 'x cur)))
   #f)

(check-expect   ; (make-and (list2 'x (make-not 'x))) cannot be solved
   (find-formula-true-asst (make-and (list2 'x (make-not 'x)))
                           (lambda () 'fail)
                           (lambda (cur resume) 'succeed))
   'fail)

You can download all the tests. You can run them at any time with

-> (use solver-interface-tests.scm)

This problem is (forgive me) the most satisfying problem on the assignment.

Related reading: Section 2.10 on continuation passing, especially the CNF solver in section 2.10.1.

Laws: Complete the laws given in the problem, and include the completed laws with your solution. Place laws for each helper function near the definition of that function.

What and how to submit

You must submit five files:

As soon as you have the files listed above, run submit105-continuations to submit a preliminary version of your work. Keep submitting until your work is complete; we grade only the last submission.

Avoid common mistakes

The most common mistakes on this assignment have to do with the Boolean-formula solver in problem S. They are