Declarations

Bindings and Bindables

A bindable is any value in a programming language that can be named. Bindables typically include data values such as numbers, strings, records, and arrays; as well as functions, types, and modules.

A value binding is an association between a name and a bindable:

<Name>=<Bindable>

A type binding is an association between a name and the type of the bindable it is (or will) be associated with:

<Name>:<Type>

Environments and Elaboration

A declaration is a phrase that produces a binding when it is executed. Executing a declaration is called elaboration. The binding produced by a declaration is stored in the context, and a token is returned indicating that the elaboration was successful:

token = elab(declaration, context)

For example:

elab("const pi 3.1416", context)

produces the binding:

pi = 3.1416

This binding is stored in the context and the token "done" is returned.

The context stores bindings in symbol tables called frames. For example, elaborating the following C++ constant declarations:

const int x = 1900;
const float y = 32.1;
const string z = "hi";

create the bindings:

x=1900
y=32.1
z="hi"

and store them in a frame:

The environment is a special data structure in the language processor's context that holds these frames. The environment might be a stack or tree of frames. In either case, this data structure is rooted by a special frame called the global frame or global environment. The bindings contained in this frame are called global bindings. All top-level declarations-- i.e., declarations that do not appear as sub-phrases of some other type of phrase-- create global bindings when elaborated.

Types of Declarations

Constant Declaration

Here's an example of a C++ constant declaration:

const double pi = 3.1416;

Theoretically, this declaration produces a binding between the name pi and the number 3.1416. In practice, a binding is made between pi and the address of a read-only variable containing 3.1416.

Variable Declarations

Here's an example of a C/C++/Java variable declaration:

int count = 0;

Note the binding created by elaborating this declaration isn't "count=0". It is "count=0xABCD" where 0xABCD is the address of a variable in memory that currently contains 0.

Type Declarations

The Haskell type declarations:

type Point = (Float, Float)
data Vector = (Vec Float Float)

bind the name Point to the type of all pairs of floating point numbers and the name Vector to a new type which has the type of all pairs of floating point numbers as its domain.

The equivalent C++ declarations would be:

typedef struct {Float xc, yc; } Point;
struct Vector {Float xc, yc; };

Note that even though points and vectors are pairs of numbers, they are not interchangeable.

Function Declarations

The Scheme language provides two ways to declare a function:

(define square(x) (* x x))
(define cube (lambda (x) (* x x x)))

Here are the equivalent declarations in Haskell:

square x = x * x
cube = \x->x*x*x

The declaration of square includes the parameter list with the name of the function. The declaration of cube looks more like the declaration of a constant, a constant declaration that binds the name square to the value produced by calling the lambda function. The lambda function is a special function that produces other functions as its output. Lambda is a function factory.

We have no equivalent notion of a function factory in C. Here's what a declaration of a global function looks like:

double square(double x) { return x * x; }

Module Declarations

A module is a collection of declarations. Classes and packages are examples of modules. In C++, a package is called a namespace. Here's an example:

namespace business {
class Account { ... };
class Customer { ... };
// etc.
}

Of course the Account class is also a module:

class Account
{
private:
double balance;
double rate; // monthly interest rate
public:
double futureValue(int months);
// etc.
};

In Java we simply place the line:

package business;

at the top of Account.java, Customer.java, or any other file containing declarations of business-related classes.

Sequential Declarations

Declarations versus Definitions

In C++

Some C/C++ declarations only create type bindings, while others create value bindings. For example, the following declarations create type bindings only:

extern int x;
double square(double x);
struct Date;

These next declarations create value bindings (hence type bindings by inference):

int x;
double square(double x) { return x * x; }
struct Date {int m, d, y; };

C/C++ programmers call declarations that create value bindings definitions. The definition of a variable or function may only occur once in a program, while all other declarations may occur as often as needed.

In Theory

In theory, a definition is a declaration that produces a binding and nothing else. For example, here are two Java declarations:

Account a = new Account();
Account b = a;

The first declaration creates an account, then binds the name a to this account, while the second declaration simply binds the name b to the account named by a. No additional account is created, hence the second declaration is an example of a defcinition.

Elaboration

Assume the syntax of a declaration follows the rule:

<Declaration> ::= const <String> <Expression>

Declarations should know how to elaborate themselves. Therefore, we declare our Declaration class as follows:

class Declaration extends Phrase {
private String name;
private Expression exp;
public static boolean isSymbol(String s) { ... }
public static boolean next(List tokens) { ... }
public Declaration(List tokens) throws ParseError { ... }
public String toString() { ... }
public String elab(Context context) { ... }
// etc.
}

The Declaration constructor acts as a parser when Declaration.next(tokens) is true. Naturally, this parser will recursively call Expression.parse(tokens) to extract the expression part of the declaration. The isSymbol() method uses the scanner, Lex, to make sure that the name part of the declaration is a legal name (no characters other than letters and digits, no leading digits, etc.)

The context will store bindings in symbol tables. We assume these tables will implement Java's Map interface:

interface Map {
Object get(Object key);
Object put(Object key, Object value);
Object remove(Object key);
// etc.
}

A simple environment might consist of a single symbol table, the Global Environment:

class Context {
// the global environment:
private Map environment = new Hashtable();
public Object get(String name) throws EvalError { ... }
public void put(String name, Object val) { ... }
public Object apply(String operator, List args) throws EvalError {
...
}
// etc.
}

The implementation of the elaboration method is now straight forward:

String elab(Context context) {
Object val = exp.eval(context);
context.put(name, val);
return "done";
}