How can we specify a programming language? Without a clear specification, the features of a language can seem awkward, overly complicated, and lacking in uniformity.
A specification of a language, L, consists of specifications of the tokens, phrases, values, and contexts of L:
Spec(L) = Tokens(L) + Phrases(L) + Values(L) + Contexts(L)
plus a semantic map of the form:
execute: Phrase(L) x Contexts(L) -> Values(L)
For example, the semantic map tells us that executing a particular phrase relative to a particular context produces a particular value:
execute(phrase, context) = value
As a side effect, the context may be altered.
It's worth noting that the specification language of L, that is the language L' that we use to formalize Spec(L) is often called the meta-language, while L is referred to as the object language. Of course if someone doesn't understand L', then they won't understand Spec(L) and hence won't understand L. In this case we may first need to specify L'. But what language will we write Spec(L') in? Will this be a meta-meta language L''? There is a danger of entering an infinite regress of meta languages. One way to minimize this problem is to choose L' to be a much simpler language than L. (In fact most languages can specify themselves!)
The Holy Grail of programming languages is the notion of a compiler-compiler. A compiler-compiler is a program that takes a formal specification, Spec(L), as input, and produces as output a compiler or interpreter for L (preferably commercial grade). Compiler-compilers already exist that take Tokens(L) or Phrases(L) as input and produce commercial grade scanners and parsers as output (Lex, YACC, ANTLR, etc.)
Semantic prototyping is a useful but half step toward compiler-compilers. The idea is to implement the semantic map of L as an interpreter, taking care to make the semantics of the object language as clear as possible (even if to do so makes the interpreter less efficient). As its name suggests, the prototype can serve as a roadmap for building commercial grade L compilers and interpreters. It can also serve as a roadmap to L programmers who need to clarify fine points of L semantics.
Omega is an experimental programming language created as an object language for this class. In many ways Omega is an ideal language. Omega features include LISP-like syntax, commands, declarations, expressions, blocks, abstracts, modules, and polymorphic types. There are no unnecessary restrictions in Omega; Omega obeys the abstractions and qualification principles.
Several subsets of Omega are noteworthy:
Alpha = Expressions only
Beta = Alpha + Declarations
Gamma = Beta + Commands
Gamma 2.0 = Gamma + Blocks
Delta = Gamma + Abstracts
Delta 2.0 = Gamma 2.0 + Abstracts
You will be asked to build a semantic prototype of each subset of Omega. Although Scheme is traditionally used as a meta language, Java will be used as our meta language.