For our labs, you will work with a designated study group of 2–3 people throughout the week. You will turn in a single lab write-up for each lab for your entire group. I recommend that you designate one person in your group for writing up your solutions, turning them in, and sending everyone a copy of the final version for their records. Note that all labs for a given week are due on the Saturday of the week, giving you time to coordinate with your partners to finish up work if you need additional time.

In a subsequent lab, we will introduce Markdown a plaintext document format that allows for the creation of documents with mathematics without the steep learning curve of other systems in this space (\(\LaTeX\), I’m looking at you…). You will use Markdown for authoring and submiting your demonstration exercises.

However, for lab assignments, I will strongly recommend that you write your solutions on paper. I personally find that the immediacy of paper better facilitates that mathematical problem solving and exploration processes that we will be emphasizing in this course. It is easy to get lost in debugging syntax and lose your creative momentum if you write down your work directly in Markdown/\(\LaTeX\).

Regardless of how you author your lab assignment, you should should submit a PDF to the relevant assignment entry on Gradescope.

• If you use Markdown, you can print the rendered output to a PDF in most editors/platforms. Note: please do not print your Markdown source, but the rendered output instead!
• If you use paper, feel free to phone-scan your work and compile the results into a final PDF. Both the OneDrive app and Google Drive app have the capability to take multiple photos and turn them into a PDF.

If you have difficulties doing this, please let me know as soon as possible!

Exploring the Substitutive Model for Racket

In class, we’ll (re-)introduce the substitutive model of computation for Racket. In lab, we’ll explore some of the corner cases of this model. Note that this is a common mode of operation in mathematics, one that we will perform repeatedly in this course:

1. Define a mathematical model which precisely defines the objects we are talking about and how they operate.
2. Explore the non-obvious effects of the model, in particular, the ambiguous cases and the corner cases.

Problem 1: What’s in a name?

A strength of possessing an explicit computation model is explaining tricky corner cases in the language’s design. In this problem, we’ll look at some of the issues arising with names in Racket.

Consider the following function definitions.

(define f1
  (lambda (x y)
    (+ x y x)))

(define f2
  (lambda (n)
    (* n 3)))

(define f3
  (lambda (n)
    (+ (f2 4) (f2 n) n)))

1. Give execution traces for each of the following expressions. Try to let each member of your group take the lead on writing down the derivation, so everyone gets their practice in. The remaining members of the group should check their work.

   • (f1 (+ 1 2) 7)
   • (f2 (f2 (f2 5)))
   • (f3 11)

2. Consider an alternative definition of f2 given below:

   (define f2
     (lambda (x)
       (* x 3)))

   Compare the second expression’s execution from the last part with the old and new definitions of f2. In a few sentences:

   • Comment on the relative behavior of both versions of f2.
   • From this example, what can you say about the choice of names of function parameters between different functions. Does it matter what names you choose? Why or why not?

3. Now consider the following top-level declarations:

   (define value 12)            # A
   
   (define f
     (lambda (value)            # B
       (let* ([x value]         # 1
              [value 5]         # C
              [y (+ value 3)])  # 2
         (+ x y value))))       # 3

   Give an execution trace for the expression (+ value (f 3)). Double-check your final result in DrRacket.

4. Based on your derivation of (f 3), determine which definitions of value (points labeled A–C) are used for each usage of value in f, i.e., the points labeled 1–3.

5. Give a rule for determining which of the definitions of a variable applies to some use of that variable. Once you have a candidate rule, check your answer with a member of the course staff.

Problem 2: Loop the Loop

Another corner case in the evaluation of Racket programs concerns non-termination. Consider the following recursive function:

(define mystery
  (lambda (n x)
    (if (zero? n)
        '()
        (cons x (mystery (- n 1) x)))))

1. Give execution traces for each of the following expressions. Again, let every group member take lead on at least one of the expressions. Note that we didn’t talk about recursion in the reading! However, there is nothing new to say here—recursion “just works” in this model, so follow your nose!

   • (mystery 0 10)
   • (mystery 1 "a")
   • (mystery 3 #f)

2. Now, trace the execution of this expression. What happens to your execution trace for this expression? Give enough of your trace to explain what is going on.

   • (mystery -1 "q")

3. Run this expression in DrRacket. What happens? Try to reconcile explain the behavior of DrRacket in terms of how your trace played out.

4. Try tracing this curious expression:

   • ((lambda (x) (x x)) (lambda (x) (x x)))

   Be very careful about variable names and substitution here! What happens in your execution trace for this expression? Give enough of your trace to explain what is going on.