CSC 324: Assignment 2 clarifications

These clarafications and announcements were originally posted on the assignments page.

• Clarification: for question 4(d), the rule for iff says that if you have the negation of an iff formula, move the not inside to the second subformula (and continue). So, for example,
  (proposition-normalize '(not (A iff B))) => (A iff (not B)), and
  (proposition-normalize '(not (x iff (not y)))) => (x iff y)
• Clarification: for question 3, the tests are checked only to initially find a clause to execute. Once a clause is matched, all expressions (in all subsequent clauses, including the tests) are evaluated until either (a) a break is encountered, or (b) the end of the cond* is reached. (The tests are evaluated in case they have side effects.)
• Clarification: for question 4, I have been getting a lot of questions asking what a wff is. A wff is defined by the four bullets. "Fully-parenthesized" refers to order of operations. For example, 1 + 2 * 3 is not fully-parenthesized, but (1 + (2 * 3)) is. A quick google can confirm the meaning of "fully-parenthesized" if you're unsure.
• Clarification: for question 4c, you do not need an efficient algorithm: a straightforward exponential time algorithm is fine. If you find a polynomial time algorithm, be sure to let me know.
• Q2: the order of variables in the result is not specified.
• Clarification: for Q4, the first bullet states that formulae can include any symbol (anything that Scheme could use as a variable name, such as A, x, this-var, or/something!else-strange), or #t, or #f.
• Examples: several students have asked for examples of how the Q4 solutions would be called. Hope this clarifies things:

        (define f '(A iff B)) ; is f a wff? Let's find out!
        (proposition-wff? f) ;=> #t
        ; How about some other formuala?
        (proposition-wff? '(A and ((B iff #t) or C))) ;=> #t
        ; Of course f could be the formula itself
        (proposition-wff? 'f) ;=> #t
        ; We could write procedures to generate formulae too!
        (proposition-wff? (append f '(not P))) ;=> #f  ; oops, (A iff B not P) not a wff
    

• Q1: Keep in mind that define-syntax specifies code transformation, not evaluation. All macros are expanded before they are executed. Recursion via define-syntax can only be on the form of the code, not on runtime values. So the following has a problem:

        (define-syntax s
          (syntax-rules ()
            ((s n) (if (= n 0) 'done (s (- n 1))))))
  
        (s 1) ; expands to
              ;   (if (= 1 0) 'done (s (- 1 1)))
              ; expands to
              ;   (if (= 1 0) 'done
              ;     (if (= (- 1 1) 0) 'done (s (- (- 1 1) 1))))
              ; expands to
              ;   (if (= 1 0) 'done
              ;     (if (= (- 1 1) 0) 'done
              ;       (if (= (- (- 1 1) 1) 0) 'done (s (- (- (- 1 1) 1) 1)))))
              ; etc.
  

  If you want the transformed code to execute recursively, produce standard recursive code (involving letrec, named let, etc).

• Q5a: The result of your rewrite should behave the same way as the original, you're only changing the implementation.
• Debugging your syntactic forms: To see the code produced, put a quote in front of the result. For example:

       (define-syntax for
         (syntax-rules (in)
           ((_ v in l body ...)
             '(for-each (lambda (v) body ...) l))))
  
       (for i in '(1 2 3) (display i) (newline))
          => (for-each (lambda (i) (display i) (newline)) (quote (1 2 3)))
  

  Note that if you have recursive rules, this will only show one level of expansion. Also, if the result is big, you might want to pretty-print it:

        (require (lib "pretty.ps"))
  
        ; not so exciting, but it would be for big examples.
        (pretty-print (for i in '(1 2 3) (display i) (newline)))
  

• Example hint: several students seem to be mystified about how to get the macro expansions to expand properly. There are two things to keep in mind: (1) pattern variables do text replacement on expressions, and (2) the ... is magic. So if we want to implement a ++ pre-increment operator in Scheme, we could do:

        (define-syntax ++
          (syntax-rules ()
            ((_ var) (begin (set! var (+ 1 var)) var))))
  
        (define x 1)
        (++ x)
        x
  

  Notice that var is just text replaced by x in the expansion. We could generalize this to let ++ apply to a list of variables, and return the incremented value of the last variable:

        (define-syntax ++
          (syntax-rules ()
            ((_ vars ... lastvar)
             (begin (set! vars (+ 1 vars)) ...
                    (set! lastvar (+ 1 lastvar)) lastvar))))
        (let ((a 1) (b 10) (c 100))
          (++ a b c)
          a
          b
        )
  

  The ... in the syntax rule matches 0 or more expressions, so when we mention vars in the expansion, and then use ... sometime after it, it will be repeated once for each expression that matched vars.
• Typo: for question 5e, one close parenthesis is on the wrong line. It should read:

    (define Coloured-Point
      (class (colour x y) (super (Point x y))
        ((colour get colour))
        ((equal? p) (and (super 'equal? p) (equal? colour (p 'colour))))))