EECS 321 Programming Languages: Homework 2

Part 1 – Free Identifiers

Implement the function free-ids, which take a WAE (see PLAI §3 or the lecture slides) and produces a list of symbols. The list should contain a symbol for each free identifier in the given WAE, each symbol should appear at most once in the list, and the symbols should be ordered according to the symbol<? comparison procedure.

Hint 1: First, write a function that generates an unordered list of symbols with duplicates, and then write separate functions to re-order the list and then remove duplicates.

Hint 2: The PLAI language includes several helpful list-processing functions:

Part 2 – Binding Identifiers

Implement the function binding-ids, which is like free-ids, but the result list contains a symbol for each binding identifier in the given WAE (whether or not the binding identifier is ever referenced by a bound identifier). The result list of symbols must be sorted and have no duplicates.

Part 3 – Bound Identifiers

Implement the function bound-ids, which is like free-ids, but the result list contains a symbol for each bound identifier in the given WAE. The result list of symbols must be sorted and have no duplicates.

Part 4 – Shadowed Variables

Implement the function shadowed-variable?, which accepts a WAE and returns a boolean. The boolean should be #t when the WAE has a bound variable that refers to a binding that shadows another one and #f otherwise.

 

Submit your code using the Handin button in DrRacket.


Last update: Thursday, January 12th, 2017
stamourv@eecs.northwestern.edu