Alpha

Note: I removed type checking from this version of Alpha (fun but too hard). I also added more hints and code.

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
3.14
-> false
false
->(* 1 2 3 4)
Number: 24
-> (+ (+ 3 4) (+ 5 6))
18
-> (and (< 3 5) (= 42 (* 6 7)))
true
-> (+ 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:

<Literal> ::= <Boole Literal> | <Number Literal>
<Boole Literal> ::= true | false
<Number Literal> ::= <Number>

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

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

The Design of Alpha

The phrase package depends on the value package. All packages depend on a special utilities package (jutil) as well as various java packages:

The OmegaConsole class contains the main method and completes the abstract Console class by implementing the abstract execute method.

The Console class roughly follows the Model-View-Controller design pattern. The console itself plays the view and controller roles. The model role is played by a serializable object called the model. In the case of the OmegaConsole, the model is a symbol table (an instance of the Environment class) containing associations between symbols and their values. The Alpha environment contains associations for the Alpha operators.

The implementation of OmegaConsole is given below.

Alpha Values

Alpha values follow the Composite Design Pattern. Accordingly, there are primitive values (that don't have Value subcomponents) and composite values (that do have Value subcomponents).

In Alpha the primitive values are Numbers and Booleans:

The composite values are frames and abstracts:

Frame is simply the base class for all symbol tables. An environment is a frame that contains references to two other environments: calling environment (ce) and defining environment (de). Note that these classes aren't used by Alpha, but must be implemented in order that the other code can be compiled.

An abstract is anything that can be applied to a list of arguments. Examples include user-defined functions and procedures as well as primitive (i.e., system-defined) functions.

Alpha doesn't allow user-defined abstracts, but the initial environment constructed in main contains associations between the ten Alpha operators (+, -, *, /, =, <. >, and, or, not) and instances of the ten subclasses of Abstract.

For example, the default Environment constructor might look like this:

public Environment() {
   de = ce = null;
   put("+", new AddFun());
   put("*", new MulFun());
   // etc.
}

See below for a few implementations.

Alpha Phrases

Phrase, Expression, and Literal are abstract because they do not implement eval or getType.

Every class implements a static parse method, and every class but Phrase implements a static isNext method.

The Implementation of Alpha

The Omega Console

Here's a working version of the Omega console. This should not need to be changed in any of the subsequent assignments. It depends on the Console, AppError, and Lex classes, which can be found at http://www.cs.sjsu.edu/faculty/pearce/jutil/.

public class OmegaConsole extends Console {
   public OmegaConsole(Environment model) {
      super(model);
   }
   public OmegaConsole() { this(new Environment()); }
   protected Environment getModel() { return (Environment)model; }

   protected String execute(String cmmd) throws AppError {
      List<String> tokens = Lex.scan(Phrase.TOKEN, 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();
   }
}

Alpha Values

All Alpha values are subtypes of the Value interface:

public interface Value extends Serializable { }

Here's a near complete implementation of the Number class:

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

   public Number(double value) {
       this.value = value;
   }
   // to be completed:
   public Number add(Number other) {return null;}
   public Number times(Number other) {return null;}
   public Number sub(Number other) {return null;}
public Number div(Number other) {return null;}

   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);
   }
}

Here's a complete implementation of the AddFun class:

public class AddFun implements Abstract {

    public Value apply(List<Value> args, Environment env)
      throws AppError {
        Number result = new Number(0);
        for(Value arg: args) {
            if (! (arg instanceof Number)) {
                throw new AppError("Inputs to add must be numbers");
            }
            Number num = (Number)arg;
            result = result.add(num);
        }
        return result;
    }
}

Note: primitive functions do not need the environment parameter.

Alpha Phrases

Here's a complete implementation of the Phrase class:

public abstract class Phrase {
   // Omega tokens:
   public static final String NUMBER = "\\d*\\.?\\d+";
   public static final String OPERATOR = "\\+|\\*|-|/|=|<|>|%";
   public static final String IDENTIFIER = "[a-zA-Z][a-zA-Z0-9]*";
   public static final String PUNCTUATION =
                                    ";|\\(|\\.|\\)|\\]|\\[|\\}|\\{";
    public static final String SYMBOL =
        Lex.join(IDENTIFIER, OPERATOR);
    public static String TOKEN = SYMBOL;
    static {
     TOKEN = Lex.join(TOKEN, PUNCTUATION);
     TOKEN = Lex.join(TOKEN, 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;
}

Note the way the parser is implemented. It's job is to call the parser in one of its extensions (later Command and Definition will be the extensions of Phrase). It determines which extension by calling the static isNext method in each extension. The parser does not know about extensions of extensions. For example, it does not know about the extensions of Literal. All super class parsers work the same way.

The same is true for all super class recognizers (isNext methods). A super class isNext method simply returns the disjunction of the isNext methods of its extensions. For example here's the isNext method for the Literal class:

public static boolean isNext(List<String> tokens) {
   return BooleanLiteral.isNext(tokens) ||
         NumberLiteral.isNext(tokens) ||
         TypeLiteral.isNext(tokens);
}

All of the real work for recognizing, parsing, type checking, and evaluating is done by the concrete classes.

Here's a complete implementation of BooleanLiteral:

public class BooleanLiteral extends Literal {
    private value.Boolean value;
    public static boolean isNext(List<String> tokens) {
        if (tokens == null || tokens.isEmpty()) {
            return false;
        }
        String token = tokens.get(0);
        try {
            Lex.scan("true | false", token);
        } catch(Exception e) {
            return false;
        }
        return true;
    }
    public static Phrase parse(List<String> tokens) throws AppError {
        if (!isNext(tokens)) {
            throw new AppError("Next token not a boolean");
        }
        BooleanLiteral result = new BooleanLiteral();
        String token = tokens.remove(0);
        boolean val= new java.lang.Boolean(token);

        result.value = new value.Boolean(val);
      return result;
    }

    public Value eval(Environment env) throws AppError {
        return value;
    }
}

Note the basic philosophy of recognizing and parsing. A recognizer never throws an exception, it simply returns true or false based on looking at the first few tokens in the incoming token list by calling tokens.get. A recognizer never removes tokens from this list.

By contrast, a parser removes tokens as it inspects them using tokens.remove. If trouble occurs, a parser throws an AppError that complains about a syntax error. Parsers create a phrase internally, initialize the phrase's fields, then return the phrase.