►C311/  H311/  A596 Spring 2025 – Programming Languages
▼Assignments
•6 Assignment 6:   Reduction and Mutation
    contents  ← prev  up  next → 

6 Assignment 6: Reduction and Mutation

Assignment

Place your code in a file named a6.rkt and submit it to Autograder.

Part 1: Beta Reduction

In class we introduced beta reduction, which turns one expression into another by changing a subexpression that is a “((λ” (pronounced “left left lambda”, meaning an application of an abstraction).

In each question in this part, you will take a lambda calculus expression and keep beta-reducing it until it can no longer be beta-reduced. (An expression that cannot be beta-reduced is said to be in beta normal form.) Write out all the steps as a Racket list, defined as a constant in your code. Renaming variables (also known as alpha-conversion) does not count as a step and can be done anywhere at any time. Do not do any computation other than beta and alpha.

For instance, suppose we ask you to “Reduce ((λ f (zero? (f 3))) ((λ x x) (λ x x))) to normal form and list the steps in q0.” This expression can be beta-reduced in two ways to start. So, you can put either
(define q0
  '(((λ f (zero? (f 3))) ((λ x x) (λ x x)))
    ((λ f (zero? (f 3))) (λ x x))
    (zero? ((λ x x) 3))
    (zero? 3)))
or
(define q0
  '(((λ f (zero? (f 3))) ((λ x x) (λ x x)))
    (zero? (((λ f f) (λ x x)) 3)) ; renamed x to f because I felt like it
    (zero? ((λ x x) 3))
    (zero? 3)))
in your code. You can either perform these beta-reductions manually or write a program to automate the work.

Tip: Do only one beta-reduction per step. Don’t combine multiple beta-reductions into one step, even if they operate on totally separate parts of the expression.

Tip: After every few steps, submit them to Autograder, which will check them and tell you if you got any of them wrong or just need to keep going.

Tip: The following steps should help, no matter whether you are doing it manually or writing a program:

Beta Recipe

  1. find one expression in the form `((λ ,x ,body) ,rand)

  2. find free variables in rand

  3. for each free variable in rand, find if there is a bound variable in body that has the same name as that free variable, and rename the corresponding bound variable (both the formal and the occurrences) with a new name

  4. return body, with every x in body replaced with rand

  1. Reduce ((λ x (bake (x x))) (λ x (wash x))) to normal form and list the steps in q1.

  2. Reduce ((λ x (λ y ((toss (x y)) (y x)))) (λ x ((stir x) y))) to normal form and list the steps in q2.

  3. Reduce ((λ x ((y (λ y (y x))) (λ x (x z)))) (λ x ((stir x) y))) to normal form and list the steps in q3.

  4. Reduce ((λ f ((f f) (f f))) (λ f (λ x (f (f x))))) to normal form and list the steps in q4. This one is longer, but trust that it will terminate. The lambda calculus is a small language but can express any computation.

Part 2: Programming with Mutation

Recall the grammar of our lambda calculus with explicit references:
  Expr = Number
  | Boolean
  | Symbol
  | (λ Symbol Expr)
  | (Expr Expr)
  | (if Expr Expr Expr)
The initial environment contains the following functions:

  • + is a curried function that adds two given numbers.

  • - is a curried function that subtracts the second given number from the first.

  • zero? is a function that tests whether the given number is zero.

  • newref is a function that stores the given value in a new location.

  • deref is a function that retrieves the current value in the given location.

  • setref is a curried function that mutates the given location to store the given value instead.

In this part, we ask you to practice programming in this language.

  1. Define explicit-accumulate to be an Expr that, when evaluated in the initial environment, creates a function that takes a number and returns the sum of all the numbers it has received so far. For instance, the program
    `((λ f ((+ (f 10)) (f 7)))
      ,explicit-accumulate)
    should produce 27, because (f 10) produces 10 then (f 7) produces 17. In contrast, the beta-reduced
    `((+ (,explicit-accumulate 10))
      (,explicit-accumulate 7))
    should produce 17, because two separate functions are created.

    (Don’t you wish this language had let? Consider writing a compiler that turns programs with let into programs without.)

    Hint: If this is the first program you write in our language, it might seem daunting. First practice writing simpler programs using newref and deref and setref. For instance, write a program that stores 5 in a new location, increments it, then reads it back. Then, write a curried function that swaps the contents of two locations.

Brainteasers

  1. Now write the same program in our lambda calculus with implicit references. Recall that the grammar of implicit references adds a new form := for assignment:
      Expr = Number
      | Boolean
      | Symbol
      | (λ Symbol Expr)
      | (Expr Expr)
      | (if Expr Expr Expr)
      | (Symbol := Expr)
    The initial environment only contains + - zero?

    Define implicit-accumulate, by analogy with explicit-accumulate above.

    contents  ← prev  up  next →