This handout describes the disambiguated form of vScheme. If you haven’t read “Welcome to vScheme”, this might be a good time. If you have read it, this handout summarizes the key points.

Referents of names

The translation of a name depends on what the name stands for. In particular,

• If a name stands for a local variable, then a reference to that name is translated into a reference to a VM register.

• If a name stands for a global variable, then a reference to that name is translated into a getglobal or setglobal VM instruction.

• If a name stands for an ordinary user-defined function, then a call to that name is translated to a bunch of register assignments followed by a call instruction, just as in CS 40. (The call instruction will be implemented in module 7.)

• If a name stands for a vScheme primitive function, like +, cons, or null?, then a call to that name is translated to the corresponding VM instruction. (That’s why you just implemented all those primitives in module 4.)

In ordinary Scheme code, as defined by module VScheme in file vscheme.sml, the names can’t be distinguished by looking at them—instead, each name’s meaning has to be looked up in an environment. But passing such an environment to every part of the UFT would be a pain. Instead, we’ll use an environment once to disambiguate the names, then record each name’s meaning using special abstract syntax. This plan not only eliminates the bothersome environment, but it leaves later compiler passes with abstract syntax that can easily be pattern matched.

Disambiguated Scheme

The target language of the disambiguation pass is UnambiguousVScheme, which is also defined in file vscheme.sml. UnambiguousVScheme compares with VScheme like this:

• Both languages have exactly the same if, while, begin, let, and lambda expressions.

• The two languages have almost the same literals, but the unambiguous version lacks the PAIR literal.

• VScheme has just one form of variable, called VAR. UnambiguousVScheme has two forms: LOCAL and GLOBAL.

• VScheme has just one form of assignment, called SET. UnambiguousVScheme has two forms: SETLOCAL and SETGLOBAL.

• VScheme has just one form of function call, written using APPLY. UnambiguousVScheme has two forms: The FUNCALL form is the general-purpose form, and it is used for calls to all functions except named primitives. The PRIMCALL form is used for calls to primitive functions.

  In the function position, the PRIMCALL does not have an exp or even a name. Instead, it has a value of type primitive. This type is defined in module Primitive from file primitives.sml.

• In VScheme, any name may appear in any position consistent with the syntax. But in UnambiguousVScheme, names must satisfy these invariants:

  • A name that refers to a local variable may appear only in the LOCAL and SETLOCAL forms.

  • A name that refers to a primitive function may appear only in the PRIMCALL form (in function position).

  • A name that refers to global variable, provided it is not a primitive function, may appear only in the GLOBAL and SETGLOBAL forms.

  These invariants are established by the disambiguation pass that you will write.

Disambiguation rules

The rules for disambiguating a function application are as follows:

• If the function is a local variable, the application becomes a FUNCALL form, with a LOCAL form of exp in the function position.

• If the function is a variable that is nonlocal and that names a primitive, the application becomes a PRIMCALL form, to the named primitive.

• If the function is any other form, including a global variable that is not a primitive, application becomes a FUNCALL form, with the original form of exp in the function position.

The rules for disambiguating VAR and SET forms are simpler: determine the name’s referent and choose the appropriate LOCAL or GLOBAL form in the target language. There’s one exception: if the name of a primitive function is used outside of a function position, it must be eta-expanded. For example, in

(val plus (curry +))

the + is disambiguated to a lambda expression, as if it were

(val plus (curry (lambda (x y) (+ x y))))

which is equivalent but puts the + in function position. This part of the transformation is implemented by the etaExpand function in file disambiguate.sml.

The main handout for the module includes links to resources on eta-expansion.

That is all you need to know about unambiguous vScheme.