Alpha

Alpha is an expression-oriented fragment of the Omega language. Alpha provides basic functionality for evaluating expressions involving arithmetic and logical operators. Alpha lacks names and therefore definitions. Alpha also lacks variables and therefore commands.

Assignment: Implement an interpreter for Alpha. You must submit a print out of your source code plus a print out of a sample Alpha session that is at least two pages long and begins by duplicating the sample session shown below.

An Alpha Session

User input is shown in boldface font:

type "help" for commands
-> 3.14
Number: 3.14
-> false
Boolean: false
->(* 1 2 3 4)
Number: 24
-> (+ (+ 3 4) (+ 5 6))
Number: 18
-> (and (< 3 5) (= 42 (* 6 7)))
Boolean: true
-> Number
Type: Number
-> (+ 2 3
Syntax error
-> (+ 2 true)
Type Error:
-> quit
Save changes?(y/n): n
changes discarded
bye

Alpha Tokens

For convenience, we take Alpha tokens to be the same as Omega tokens:

<Number> ::= (+ | -)?<Digit>+(.<Digit>+)?

<Punctuation> ::= . | ; | ( | ) | [ | ] | { | }

<Letter> ::= [A-Z] | [a-z]
<Digit> ::= [0-9]

Alpha Phrases

Expressions are the only type of Alpha phrase:

Literals and function calls are the only types of expressions:

<FunCall> ::= (<Symbol> <Expression>+)

<Symbol> ::= <ArithmeticOp> | <ComparisonOp> | <LogicOp>
<ArithmeticOp> ::= + | * | - | /
<ComparisonOp> ::= < | > | =
<LogicOp> ::= and | or | not

Design

Alpha consists of two packages. Note the one-way dependency:

In the phrases package you must define the following classes:

Implementation

Here's a working base class for the Phrase hierarchy:

abstract class Phrase {
// Omega Tokens:
public static final String SYMBOL =
     Lex.join(Lex.IDENTIFIER, Lex.OPERATOR);
public static final String NUMBER = Lex.NUMBER;
// PATTERN ::= SYMBOL | OPERATOR | PUNCTUATION | NUMBER
public static String PATTERN = SYMBOL;
static {
     PATTERN = Lex.join(PATTERN, Lex.PUNCTUATION);
     PATTERN = Lex.join(PATTERN, Lex.NUMBER);
}
// top level parser
public static Phrase parse(List<String> tokens) throws AppError {
     if (Expression.isNext(tokens)) return Expression.parse(tokens);
     if (Command.isNext(tokens)) return Command.parse(tokens);
     if (Definition.isNext(tokens)) return Definition.parse(tokens);
     throw new AppError("Unrecognized phrase in Phrase.parse");
}
// top level evaluator
abstract public Value eval(Environment env)throws AppError;
}

Alpha Values

Alpha values are numbers, Booleans, types, frames, and ten pre-defined functions:

Value = Number + Boolean + Frame + Function
Function = {+, *, -, /, <, >, =, and, or, not}

Design

PrimitiveValue and CompositeValue are purely conceptual classes. You don't need to implement them. However, you must implement the other classes:

The composite values include things like objects, composite types, and functions:

Implementation

Alpha values implement an empty Value interface:

interface Value extends Serializable { }

For example, the Number class encapsulates a double:

class Number implements Value, Comparable {
   private static final long serialVersionUID = 1L;
   private double value;

   public Number add(Number other) {...}
   public Number times(Number other) {...}
   public Number sub(Number other) {...}
   public Number div(Number other) {...}

   public String toString() { return "" + value; }

   public boolean equals(Object other) {
      if (other == null) return false;
      Class c = other.getClass();
      if (!c.equals(getClass())) return false;
      Number b = (Number)other;
      return b.value == value;
   }

   public int hashCode() { return toString().hashCode(); }

   public int compareTo(Object arg0) {
      Number arg = (Number)arg0;
      return (int)(value - arg.value);
   }
}

Functions must implement the Abstract interface:

interface Abstract extends Value {
// = result of applying this to args in env
Value apply(List<Value> args, Environment env) throws AppError;
}

Note: A primitive function is a function that doesn't use its Environment parameter, env. Presumably, such functions are so simple that they don't call other functions. These functions might be directly implemented in the ALU circuits on board the processor. All ten Alpha functions are primitive.

Alpha Semantics

A frame is a special kind of value. It is a table of associations between symbols and values. For now we can take symbols to be the same as Java Strings:

class Symbol extends String { } // for now

An environment, also called a Context, is a frame together with (possibly null) references to a defining environment and a calling environment:

Alpha uses a single environment called the global environment. It contains associations between the names of all of the ten Alpha operator symbols and the corresponding function objects.

Phrases produce values when evaluated relative to an environment

phrase.eval(environment) = value

Of course the algorithm for eval varies polymorphically in the different subclasses of Phrase. For example, the value of a literal is itself.

Note: there are currently no phrases that produce frames as values. Frames are strictly internal use values at this stage.

The Omega Console

The Omega Console extends the CUI Framework:

public class OmegaConsole extends Console {
   public OmegaConsole(Serializable model) {
      super(model);
   }

   protected Environment getModel() { return (Environment)model; }
   public OmegaConsole() { this(new Environment()); }

   protected String execute(String cmmd) throws AppError {
      List<String> tokens = Lex.scan(Phrase.PATTERN, cmmd);
      Phrase phrase = Phrase.parse(tokens);
      Environment env = getModel();
      Value value = phrase.eval(env);
      unsavedChanges = true;
      return value.toString();
   }

   public static void main(String[] args) {
      Environment model = new Environment();
      Console console = new OmegaConsole(model);
      console.controlLoop();
   }
}