Demonstration Exercise #1

Demonstration exercises are your opportunity to showcase your mastery of the week's material. In lab, you gain practice employing the fundamental skills we introduce in class. In contrast, the demos are integrative in nature, requiring to put those skills into context as well as mix different skills together to solve problems that are more like the ones you find in the real world.

Formatting and Submitting Your Work

Create a LaTeX document for each demonstration exercise, using the csc208_template.tex template file to format your document. Your write-ups for each problem should reflect good writing principles and mathematical style:

• Grammatically correct English prose and mathematics.
• Structure of the prose made obvious through subheadings, paragraphs, and lists.
• Math appropriately integrated into the prose as needed.

To achieve this, you will need to set aside ample time for revision and editing of your work before the deadline. Approach the demonstration exercises not like a one-and-done problem set, but as a writing assignment where you are putting in work that you eventually refine into a polished, complete product.

When you are done, you should compile your LaTeX file to a PDF and then submit that PDF to Gradescope when you are done. Please do not submit your LaTeX source (in textual or PDF format); we would like to only work with a complete, rendered document!

Problem 1: Tracing

Consider the following Python program mystery that performs a more complicated recursive computation:

(define mystery
  (lambda (l)
    (cond
      [(zero? (length l)) null]
      [(equal? (length l) 1) l]
      [else
       (let ([x (car l)]
             [y (car (cdr l))]
             [t (cdr (cdr l))])
         (cons y (cons x (mystery t))))])))

1. Give the step-by-step evaluation of the following expressions.

   • (mystery null)
   • (mystery (list 0 1))
   • (mystery (list "a" "b" "c" "d"))

   Because of the complexity of the function, you may take the two following shortcuts in your derivation:

   • Any call to mystery steps directly to the branch expression that would have been selected by the function.
   • Any let-binding directly steps to the body expression with all relevant values substituted for their respective variables.

   When giving your evaluation traces, please use a verbatim block, placing each step of the derivation on its own line, separated by a long arrow (-->), e.g.,

   \begin{verbatim}
       1 + 2 * 3
   --> 1 + 6
   --> 7
   \end{verbatim}
   

2. In a sentence, describe what the mystery function does.

Problem 2: Blasting Booleans

Consider the following functions over booleans that give implementations of the standard boolean operations not, and, and or:

(define my-not
  (lambda (b)
    (if b
        #f
        #t)))

(define my-and
  (lambda (b1 b2)
    (if b1
        b2
        #f)))

(define my-or
  (lambda (b1 b2)
    (if b1
        #t
        b2)))

Prove the following claims of program equivalence about these definitions:

Make sure not to skip any steps in your derivations!