Commits

Anonymous committed 1764985

Convert documentation to Markdown.

Comments (0)

Files changed (12)

+The Iphigeneia Programming Language
+===================================
+
+Language version 1.0, distribution version 2011.1010
+
+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 `=` expr[0] `in` expr[1]
+
+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.
+
+#### `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

doc/iphi.html

-<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
-<!-- encoding: UTF-8 -->
-<html xmlns="http://www.w3.org/1999/xhtml" lang="en">
-<head>
-<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
-<title>The Iphigeneia Programming Language</title>
-  <!-- begin html doc dynamic markup -->
-  <script type="text/javascript" src="/contrib/jquery-1.6.4.min.js"></script>
-  <script type="text/javascript" src="/scripts/documentation.js"></script>
-  <!-- end html doc dynamic markup -->
-</head>
-<body>
-
-<h1>The Iphigeneia Programming Language</h1>
-
-<p>Language version 1.0, distribution version 2007.1125</p>
-
-<h2>Introduction</h2>
-
-<p>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.</p>
-
-<p>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 <b>Imp</b> and <b>Fun</b> that you're apt to find in
-textbooks on formal semantics.</p>
-
-<p>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 <em>distinct</em> 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.</p>
-
-<p>Note also that this document is an <em>informal</em> 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.)</p>
-
-<p>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.</p>
-
-<h2>Language</h2>
-
-<p>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 <code>while</code>.</p>
-
-<p>The basic constructs of Iphigeneia are <em>expressions</em>, which evaluate to
-a single value, and <em>commands</em>, 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.</p>
-
-<p>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.</p>
-
-<p>Constructs relating to the single-assignment side of things include <code>let</code>,
-<code>loop</code>, <code>repeat</code>, and <code>valueof</code>.  Imperative constructs
-include <code>begin</code> blocks, <code>while</code> loops, and of course destructive
-variable update with the <code>:=</code> operator.
-The lowly <code>if</code> 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.</p>
-
-<p>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 <code>input</code> ... <code>in</code> form, while output is considered "imperative",
-leading to a <code>print</code> command.</p>
-
-<h3>Expressions</h3>
-
-<p>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 (<code>if</code> and <code>while</code>).
-Integer expressions appear everywhere else, and can also contain some more involved
-forms which are explained in the remainder of this section.</p>
-
-<p>Expressions are generally evaluated eagerly, left-to-right, innermost-to-outermost.
-This only affects order of output with the <code>print</code> 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.)</p>
-
-<h4><code>let</code> name <code>=</code> expr<sub>0</sub> <code>in</code> expr<sub>1</sub></h4>
-
-<p>The <code>let</code> construct establishes a new binding.  The expression
-expr<sub>0</sub> is evaluated, and the result is associated with the given
-name during the evaluation of expr<sub>1</sub>.  That is, where-ever the name
-appears in expr<sub>1</sub> or any sub-expression of expr<sub>1</sub>, it
-is treated as if it had the value of expr<sub>0</sub>.  Note however
-that embedded commands (such as those appearing in a <code>valueof</code>)
-are not considered to be sub-expressions, and the influence of <code>let</code>
-bindings does not descend into them.</p>
-
-<p>Let bindings shadow any enclosing let bindings with the same name.</p>
-
-<h4><code>valueof</code> name <code>in</code> cmd</h4>
-
-<p>The <code>valueof</code> 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 <code>:=</code> assignment operator,)
-there ought to be a complementary way to embed commands in expressions.</p>
-
-<p><code>valueof</code> 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 <code>var</code> inside
-the block; the <code>valueof</code> counts as a <code>var</code>,
-declaring the name in the new store.</p>
-
-<h4><code>loop</code> ... <code>repeat</code></h4>
-
-<p>The <code>loop</code> construct is modelled after Scheme's "named <code>let</code>"
-form.  When <code>repeat</code> executed, the innermost enclosing <code>loop</code>
-expression is re-evaluated in the current environment.  Since <code>loop</code> expressions
-do not take arguments like a "named <code>let</code>", the values of bindings are
-instead altered on subsequent iterations by enclosing the <code>repeat</code> in a
-<code>let</code> expression, which gives new bindings to the names.</p>
-
-<p>A <code>repeat</code> with an unmatched <code>loop</code> is a runtime error that aborts the
-program.  Also, the influence of a <code>loop</code> does not extend down through a
-<code>valueof</code> expression.  That is, the following <code>repeat</code> is not
-matched: <code>loop valueof x in x := repeat</code>.</p>
-
-<h4><code>input</code> name <code>in</code> expr</h4>
-
-<p>Works like <code>let</code>, 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.</p>
-
-<h3>Commands</h3>
-
-<h4><code>begin</code> ... <code>end</code></h4>
-
-<p>Commands can be sequentially composed into a single compound command
-by the <code>begin</code>...<code>end</code> construct.</p>
-
-<h4><code>var</code> name <code>in</code> cmd</h4>
-
-<p>The <code>var</code> construct declares a new updatable variable.
-Variables must be declared before they are used or assigned.</p>
-
-<h4><code>print</code> expr</h4>
-
-<p>The <code>print</code> 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.</p>
-
-<h2>Grammar</h2>
-
-<pre>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 {("&amp;" | "|") RelExpr}
-	   | "!" BoolExpr
-	   | "(" BoolExpr ")".
-
-RelExpr ::= NumExpr ("&gt;" | "&lt;" | "&gt;=" | "&lt;=" | "=" | "/=") 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.</pre>
-
-<p>An Iphigeneia program, at the topmost level, is a command.  (One idiom
-for giving "functional" Iphigeneia programs is <code>var r in r := <var>expr</var></code>,
-or even just <code>print <var>expr</var></code>.)
-Comments can be given anywhere in an Iphigeneia program by enclosing them in
-<code>(*</code> and <code>*)</code>.  Do not expect comments to nest.</p>
-
-<h2>Implementation</h2>
-
-<p>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.</p>
-
-<p>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
-<code>input</code> construct to zero, and it does not even evaluate the expressions
-in <code>print</code> commands.</p>
-
-<p>Compiling the reference implementation with ghc produces an executable
-<code>iphi</code> which takes the following command-line options:</p>
-
-<ul>
-<li><code>-p</code> uses the pure interpreter instead of the default monadic
-interpreter.</li>
-<li><code>-q</code> suppresses the output of the final state of the program
-upon termination.</li>
-</ul>
-
-<p>The reference interpreter is mostly written in a straightforward
-(sometimes painfully straightforward) manner (except for, arguably, <code>Main.hs</code>,
-which does some ugly things with continuations.)  It provides its own implementation
-of maps (environments) in <code>Map.hs</code>, instead of using Haskell's
-<code>Data.Map</code>, 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.</p>
-
-<p>-Chris Pressey
-<br />November 25, 2007
-<br />Chicago, Illinois</p>
-
-</body></html>
File contents unchanged.
File contents unchanged.
File contents unchanged.
File contents unchanged.
File contents unchanged.

src/MonadInterp.hs

File contents unchanged.

src/Parser.hs

File contents unchanged.

src/Primitive.hs

File contents unchanged.

src/PureInterp.hs

File contents unchanged.

src/Scanner.hs

File contents unchanged.