4.1 Introduction🔗

You may have seen the term “program analysis” before. The idea behind program analysis is to obtain information statically (i.e., without running the program) about the state of the program when it is run.

In this assignment we will perform a very simple kind of program analysis. The goal is to simulate your programming editor’s auto-complete feature. That is, you put the cursor somewhere, and it offers the names you could write there.

4.2 Assignment🔗

We set up this assignment in a way that avoids the details of graphical user interfaces and so on by distilling the problem down to its essence. (Think for a moment how you might do this!)

The essence of the problem is this. We assume that we have a program with a hole in it. The cursor is positioned at the hole, and the programmer is asking for the set of names that can fill the hole.

We represent this by adding the “hole” to the source program. Concretely, we write this as @ in the surface syntax. You will write a function

that takes a program containing exactly one hole and returns the variables that are in scope at the hole. Your function should not make either of the errors described above, and it should always terminate. If you run into difficulty achieving all these goals, post on EdStem telling us why and we’ll try to help you out.

You will do this twice, for two languages: Paret with Holes, which is Paret from Desugar plus the hole, in paret_holes.rhm; and Typed Paret with Holes, which is Typed Paret from stage 2 of Type Checker plus the hole, in tparet_holes.rhm. Each module defines a Surface type with a parser, parse_surface and parse_surface_str as in Desugar, and a core Expr type. As in Desugar, your desugar removes the sugar terms. Copy your desugarer from Desugar or from stage 2 of Type Checker and extend it with the hole. Your file then exports both desugar and calc_locals, and a program is analyzed by calc_locals(desugar(parse_surface_str(...))).

4.3 Grammar🔗

and likewise for Typed Paret. A hole may appear anywhere an expression may.

4.4 Abstract Syntax🔗

Surface is the surface type of the language, from Desugar or Type Checker, plus one constructor, s_hole(); Expr is the core type plus e_hole(). Your desugarer maps the one to the other, and the hole to the hole.

4.5 What “In Scope” Means🔗

A variable is in scope at the hole if the hole is inside the body of a lam whose parameter it is, or inside the body of a let that binds it. In the core, after desugaring, there is only lam. For example, in

the variables in scope at the hole are x, y, and f, in any order. The definition of scope is the same for the typed language. The difference between the two—the type annotations—dictates what type each variable has, but they don’t change the set of variables in scope. In

the variables in scope at the hole are x and f.

4.6 Testing🔗

The result of calc_locals is compared as a set: order and duplicates do not matter. Each language module provides same_set, so a test can take the form

A program must contain exactly one hole; the provided parser rejects programs with no hole or with more than one, so calc_locals never sees such a program.

Because calc_locals analyzes the desugared program, remember to put holes inside non-core surface terms too, to make sure the hole is being conveyed through the desugaring process correctly.

4.7 Starter Code🔗

You are provided with:

• calc_vars.rhm and typed_calc_vars.rhm, the stencils for the two languages, each with a place for your desugarer and your calc_locals.

• calc_vars_tests.rhm and typed_calc_vars_tests.rhm, the stencils for your tests.

• paret_holes.rhm and tparet_holes.rhm, the two languages, with sexp.rhm and sexp.rkt, which they use to read S-expressions.

4.8 What To Hand In🔗

You will submit to four Gradescope drops, one for each file:

• calc_vars.rhm, to the “Untyped: Code” drop.

• calc_vars_tests.rhm, to the “Untyped: Tests” drop.

• typed_calc_vars.rhm, to the “Typed: Code” drop.

• typed_calc_vars_tests.rhm, to the “Typed: Tests” drop.