The Iphigeneia Programming Language

↑Cat's Eye Technologies: iphi

Language version 1.0, distribution version 2007.1125

Introduction

The Iphigeneia programming language was designed as a workbench for an exercise in transliterating between single-assignment (functional) and mutable-variable (imperative) program forms. As such, the language contains features paradigmatic to both forms.

As languages go, Iphigeneia is not particularly esoteric, nor is it particularly practical; it's more academic, resembling those exciting languages with inspired names like Imp and Fun that you're apt to find in textbooks on formal semantics.

Note that this document only covers the Iphigeneia language itself, not the transliteration process. This is because I still haven't fully worked out the details of the transliteration, and that shortly after designing the language, I changed my mind and decided that, for clarity, it would probably be better to do the transliteration between two distinct languages, rather than within a single language. So Iphigeneia wanders a little bit from the original design goal, and reflects a couple of design choices that are simply on whim rather than strictly in support of the transliteration idea.

Note also that this document is an informal description of the language that relies on the reader's intuition as a computer programmer. I would like to write a formal semantics of Iphigeneia someday, since it's a simple enough language that this isn't an unthinkably complex task. In the meantime, you may wish to refer to the reference implementation of the Iphigeneia interpreter for a more formal definition (if you believe Haskell is sufficiently formally defined.)

The name Iphigeneia comes from the name of Agamemnon's daughter in Greek mythology. The name was not chosen because of any particular significance this figure holds — I just think it's a nice name. However, I suppose if you wanted to force an interpretation, you could say that Iphigeneia has two natures, princess and priestess, and so does her namesake: imperative and functional.

Language

The language constructs are generally straightforward to understand if you've had any experience with the usual assortment of imperative and functional languages, so forgive me if I'm a bit sketchy on the details here and there, even to the point of just mentioning, rather than describing, run-of-the-mill constructs like while.

The basic constructs of Iphigeneia are expressions, which evaluate to a single value, and commands, which transform a store (a map between variable names and values.) Expressions relate to the functional or single-assignment side of things, and commands provide the imperative or mutable-variable aspect of the language.

There are only two kinds of values in Iphigeneia: boolean values and unbounded integer values. In addition, only integers can be "denoted" (be stored in variables or have names bound to them); boolean expressions can only appear in conditional tests. To keep things simple, there are no subroutines, function values, pointers, references, arrays, structures, or anything like that.

Constructs relating to the single-assignment side of things include let, loop, repeat, and valueof. Imperative constructs include begin blocks, while loops, and of course destructive variable update with the := operator. The lowly if makes sense in both "worlds", and so leads a double life: one flavour appears in expressions and has branches that are also expressions, and the other is a command and has branches that are also commands.

Iphigeneia supports input and output. However, to further emphasize the "split" in the language (and for no other good reason,) input is considered "functional", leading to an input ... in form, while output is considered "imperative", leading to a print command.

Expressions

Expressions are formed from the usual assortment of infix operators with their normative meaning and precedence. There are two kinds of expressions, boolean expressions and integer expressions. Boolean expressions only appear in tests (if and while). Integer expressions appear everywhere else, and can also contain some more involved forms which are explained in the remainder of this section.

Expressions are generally evaluated eagerly, left-to-right, innermost-to-outermost. This only affects order of output with the print command, however, since evaluation of an expression can never side-effect a store. (Command sequences embedded in expressions always work exclusively on their own, local store.)

let name = expr0 in expr1

The let construct establishes a new binding. The expression expr0 is evaluated, and the result is associated with the given name during the evaluation of expr1. That is, where-ever the name appears in expr1 or any sub-expression of expr1, it is treated as if it had the value of expr0. Note however that embedded commands (such as those appearing in a valueof) are not considered to be sub-expressions, and the influence of let bindings does not descend into them.

Let bindings shadow any enclosing let bindings with the same name.

valueof name in cmd

The valueof construct was a late addition, and is not strictly necessary, although it adds a nice symmetry to the language. I decided that, since there was already a (completely traditional) way to embed expressions in commands (namely the := assignment operator,) there ought to be a complementary way to embed commands in expressions.

valueof blocks are evaluated in a completely new store; no other stores or let bindings are visible within the block. There is no need to declare the name with a var inside the block; the valueof counts as a var, declaring the name in the new store.

loop ... repeat

The loop construct is modelled after Scheme's "named let" form. When repeat executed, the innermost enclosing loop expression is re-evaluated in the current environment. Since loop expressions do not take arguments like a "named let", the values of bindings are instead altered on subsequent iterations by enclosing the repeat in a let expression, which gives new bindings to the names.

A repeat with an unmatched loop is a runtime error that aborts the program. Also, the influence of a loop does not extend down through a valueof expression. That is, the following repeat is not matched: loop valueof x in x := repeat.

input name in expr

Works like let, except that the program waits for a character from the standard input channel, and associates the ASCII value of this character to the name when evaluating expr.

Commands

begin ... end

Commands can be sequentially composed into a single compound command by the begin...end construct.

var name in cmd

The var construct declares a new updatable variable. Variables must be declared before they are used or assigned.

print expr

The print command evaluates expr and, if the result is between 0 and 255, produces a character with that ASCII value on the standard output channel. The behaviour for other integers is not defined.

Grammar

Command ::= "if" BoolExpr "then" Command "else" Command
          | "while" BoolExpr "do" Command
          | "begin" Command {";" Command} "end"
          | "var" VarName "in" Command
          | "print" NumExpr
          | VarName ":=" NumExpr.

BoolExpr ::= RelExpr {("&" | "|") RelExpr}
	   | "!" BoolExpr
	   | "(" BoolExpr ")".

RelExpr ::= NumExpr (">" | "<" | ">=" | "<=" | "=" | "/=") NumExpr.
NumExpr ::= MulExpr {("+" | "-") MulExpr}.
MulExpr ::= Primitive {("*" | "/") Primitive}.

Primitive ::= "(" NumExpr ")"
            | "if" BoolExpr "then" NumExpr "else" NumExpr
            | "let" VarName "=" NumExpr "in" NumExpr
	    | "valueof" VarName "in" Command
	    | "loop" NumExpr
	    | "repeat"
            | "input" VarName "in" NumExpr
            | VarName
	    | NumConst.

An Iphigeneia program, at the topmost level, is a command. (One idiom for giving "functional" Iphigeneia programs is var r in r := expr, or even just print expr.) Comments can be given anywhere in an Iphigeneia program by enclosing them in (* and *). Do not expect comments to nest.

Implementation

There is a reference implementation of Iphigeneia written in Haskell 98. It has been tested with ghc and Hugs, against a series of test cases which are included with the distribution.

The reference implementation actually contains two interpreters. One is a monadic interpreter, which supports the I/O facilities of Iphigeneia. The other is a "pure" interpreter, which is written without the use of monadic types; it does not support I/O, but its code may be easier to follow. The pure interpreter always binds the name that occurs in a input construct to zero, and it does not even evaluate the expressions in print commands.

Compiling the reference implementation with ghc produces an executable iphi which takes the following command-line options:

  • -p uses the pure interpreter instead of the default monadic interpreter.
  • -q suppresses the output of the final state of the program upon termination.

The reference interpreter is mostly written in a straightforward (sometimes painfully straightforward) manner (except for, arguably, Main.hs, which does some ugly things with continuations.) It provides its own implementation of maps (environments) in Map.hs, instead of using Haskell's Data.Map, to make the definition of the language more explicit. The code is also released under a BSD-style license. So, even though Iphigeneia is not a particularly exciting language, this interpreter might serve as a good starting point for experimenting with unusual features to add to an otherwise relatively vanilla imperative and/or functional language.

-Chris Pressey
November 25, 2007
Chicago, Illinois