Language version 1.0, distribution version 2011.1010
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.
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 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.)
The let
construct establishes a new binding. The expression expr[0] is
evaluated, and the result is associated with the given name during the
evaluation of expr[1]. That is, where-ever the name appears in expr[1]
or any sub-expression of expr[1], it is treated as if it had the value
of expr[0]. 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.
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.
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
.
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 can be sequentially composed into a single compound command by
the begin
...end
construct.
The var
construct declares a new updatable variable. Variables must be
declared before they are used or assigned.
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.
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.
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