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 Markdown document for each demonstration exercise, using headings to label each problem. 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 Markdown file to a PDF and then submit that PDF to Gradescope when you are done. Please do not submit your Markdown source (in textual or PDF format); we would like to only work with a complete, rendered document!

Problem 1: Tracing

Consider the following Racket program mystery that performs a more complicated recursion utilizing pattern matching:

(define mystery
  (lambda (l)
    (cond [(null? l)       '()]
          [(null? (cdr l)) l]
          [else
           (cons (cadr l) (cons (car l) (mystery (cddr l))))])))

1. Give the step-by-step evaluation of the following expressions. In your work, you may go from a cond expression directly to the branch of the cond that would be selected. In other words, if the current expression is:

   (cond [(null? l)       '()]
         [(null? (cdr l)) l]
         [else
          (cons (cadr l) (cons (car l) (mystery (cddr l))))])))

   You can immediately step to:

   l

   If the second branch of the cond was selected.

   • (mystery '())
   • (mystery '(a b))
   • (mystery '(a b c d e))

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

   ~~~racket
       (+ 1 (* 2 3))
   --> (+ 1 6)
   --> 7
   ~~~

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

Problem 2: Confounding Confluence

1. In keeping with a “standard” model of program evaluation, we declared that, when evaluating a program step-by-step, the golden rule is that we evaluate the arguments to a function before substituting the function itself. For example, suppose we have the following program:

   (define avg-3
     (lambda (x y z)
       (/ (+ x (+ y z)) 3)

   First, give an evaluation trace for the following expression:

   (avg-3 (+ 1 1) (* 3 8) (/ 1 2))

2. It turns out this model of program evaluation is only one of many possible strategies for performing substitutive evaluation! This standard model we find it most languages is called “call-by-value” evaluation, where you first evaluate arguments to values before calling a function. However, this is mathematics—we can do whatever we want and observe whether our choices matter at the end of the day.

   Let’s try another evaluation strategy called “call-by-name” evaluation. In this evaluation strategy, rather than evaluating arguments first before substituting for a function call, let’s do it in the other order. Let’s immediately substitute for a function call before evaluating the arguments.

   Give an evaluation trace for the expression from the previous part using this “call-by-name” strategy:

   (avg-3 (+ 1 1) (* 3 8) (/ 1 2))

3. Now, consider the following function

   (define triple
     (lambda (x)
       (+ x (+ x x))))

   Imagine that we are evaluating the call (triple (f x)) where (f x) represents some time-intensive computation. In a few sentences each, explain and justify:

   1. Whether “call-by-value” versus “call-by-name” evaluation produces a different result for (triple (f x)).
   2. Whether “call-by-value” versus “call-by-name” evaluation is more efficient for (triple (f x)).

4. Observe the following formal definitions:

   Definition (Multistep Evaluation): let e and e' be an expression of some language, e.g., of Racket. We write e -->* e' whenever e steps to e' in zero or more single steps of evaluation.

   Definition (Confluence): let e be an arbitrary expression of some language. If it is the case that:

   1. e -->* e1 for some expression e1,
   2. e -->* e2 for some other expression e2, and
   3. Both e1 -->* v and e2 -->* v for some final value v.

   Then we say that the language is confluent.

   In particular, e may step to different expressions e1 and e2 due to different evaluation strategies, e.g., call-by-name versus call-by-value.

   Suppose that a language is confluent. In a few sentences, explain what can we say about the choice of evaluation strategy if we know a language is confluent with respect to consistent output (ignoring efficiency!) In your explanation, use an additional example Racket program and expression that demonstrates your reasoning.

5. It turns out that Racket in the form that we have presented it is not confluent! Give an example Racket program and expression e that does not satisfy the confluence property. To do this, you should play around and explore different programs and evaluation under the call-by-name and call-by-value strategies.

   (Hint: it’ll be hard to get an expression to spit out different results, but what about different behaviors instead? Try out different programs that involve infinite loops and see if you can create a situation where one execution path leads to a value and the other to an infinite loop.)

6. The previous part demonstrates that confluence and infinite loops do not mix! We don’t have the machinery to formalize or prove this fact, but let’s instead use what we’ve seen so far to perform some informed speculation. In a few sentences, argue whether the following claim holds or does not hold:

   Claim: if a language does not have infinite loops, then it is confluent.

   Note that I am not looking for a correct answer here, I am looking for a well-reasoned argument based off of what you have seen so far and any additional examples you would like to develop to explore this open-ended question.