EoPL - Ch 1 - Exs 19-26

Exercises 19 through 26 in Chapter 1 of Essentials of Programming Languages begin delving into parsing concepts. In particular, they explore the concepts of free and bound variables in lambda expressions.

In the book, Figure 1.1 provides an implementation of the definition of occurring free and occuring bound (given by Definition 1.3.3). All the exercises are based on this definition; and, Exercises 22 through 26 focus on extending it.

Ex. 19
Define a function free-vars that takes a list structure representing a lambda calculus expression (as referenced by Definition 1.3.3), and returns a set of all variables that occur free within the expression. Similarly, define a function bound-vars that returns a set of all variables that occur bound in a given expression. Solution.

Ex. 20
Give an example of a lambda calculus expression in which the same variable occurs free, but also has a value independent of its free occurence. Solution.

Ex. 21
Give an example of a lambda calculus expression in which the same variable occurs both free and bound. Solution: The solution for Exercise 20 also suffices for this exercise. In fact, I do not see much difference between the problems.

Ex. 22
Modify the functions occurs-free? and occurs-bound? (see Figure 1.1) to allow lambda abstractions and applications with any number of parameters. Solution.

Ex. 23
Modify the functions occurs-free? and occurs-bound? (see Figure 1.1) to include if expressions. Solution.

Ex. 24
Modify the functions occurs-free? and occurs-bound? (see Figure 1.1) to include let and let* expressions. Solution.

Ex. 25
Modify the functions occurs-free? and occurs-bound? (see Figure 1.1) to include expressions of the form (quote [datum]). Solution.

Ex. 26
Modify the functions occurs-free? and occurs-bound? (see Figure 1.1) to include set! assignment expressions. Solution.

The inclusion of set! expressions in Exercise 26 is somewhat ambiguous: if a variable that was not in scope (i.e. free) is set!-ed does it become a bound variable? The actual Scheme interpreter only allows in-scope (i.e. bound) variables to be set!-ed, therefore set! never makes a bound variable from a free one. With that in mind, I chose to make my solution disregard appearance as the first operand in a set! statement as criteria for a bound variable.