Anonymous avatar Anonymous committed ec3be86

Initial import of Dieter version 1.0 revision 2011.1214 sources.

Comments (0)

Files changed (18)

+<!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>
+<title>The Dieter Programming Language</title>
+<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
+  <!-- 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 Dieter Programming Language</h1>
+
+<h2>Description</h2>
+
+<p><dfn>Dieter</dfn> (that's Dieter as in the German masculine given name Dieter,
+not dieter as in "one who diets")
+is a little experimental programming language which conflates <em>type qualifiers</em> with <em>modules</em>.
+In this article, we'll first describe these mechanisms.  Then we'll show how their interaction
+produces something that resembles object-oriented programming.</p>
+
+<h3>Type Qualifiers</h3>
+
+<p>A <dfn>type qualifier</dfn> is simply a keyword which may be placed before any type expression,
+further specializing it.  Type qualifiers should be familiar to programmers of C, where
+<em>storage classes</em>, such as <code>const</code> and <code>static</code>, are
+examples of type qualifiers.  The cardinal rule of type qualifiers in Dieter is this:
+<strong>during assignment (or parameter-passing), a variable (or parameter)
+whose type possesses some type qualifier
+<em>only</em> accepts values of the same type that possess <em>at least</em> that same qualifier.</strong></p>
+
+<p>Some basic properties of type qualifiers follow (but first, for concreteness, let's
+stipulate that Dieter has an assortment of primitive types:
+<code>bool</code>, <code>int</code>, <code>rat</code>, and <code>string</code>.
+And <code>void</code> denoting the type of the absence of any value.)
+The order that type qualifiers are given in a type expression doesn't matter:
+if <code>beefy</code> and <code>gnarly</code> are type qualifiers, then
+<code>beefy gnarly int</code> and <code>gnarly beefy int</code> are wholly equivalent types.
+Neither does the number of occurrences matter: <code>beefy gnarly beefy int</code>
+is equivalent to
+<code>beefy gnarly int</code>.  Algebraically speaking, type qualifiers are
+<dfn>commmutative</dfn> and <dfn>idempotent</dfn>.</p>
+
+<p>You can't assign an <code>int</code> to a <code>beefy int</code> (or pass it to a procedure
+expecting a <code>beefy int</code>,) but you can assign a <code>beefy int</code> to an <code>int</code>.
+This might sound counter-intuitive initially, but after you think about it a bit I'm sure
+you'll conclude it's appropriate: it's just like how you can
+assign a <code>const int</code> to an <code>int</code> in C, but not an
+<code>int</code> to a <code>const int</code>.  <code>int</code> is more general, and
+will tolerate information being lost in the copy, whereas <code>beefy int</code>
+is more specific, and will not accept a value with insufficient information associated with it.
+Or, if you prefer, while all <code>beefy int</code>s are <code>int</code>s, there are
+<code>int</code>s that aren't <code>beefy</code> and thus can't be assigned to a
+variable which is restricted to <code>beefy int</code>s.</p>
+
+<h3>Type Operators</h3>
+
+<p>In order to make use of type qualifiers in user programs, Dieter provides <dfn>type operators</dfn>,
+similar to C's type-casting facilities, to manipulate type qualifiers.</p>
+
+<p>In fact, Dieter has only one explicit type
+operator,  called <code>bestow</code>. It can be used in an expression to endow its type
+with further type qualifiers.  <code>bestow</code> takes a
+type qualifier <var>q</var> and a value of some type <var>t</var>
+and returns a new value of type <var>q</var>·<var>t</var>.  (You
+can think of <var>q</var>·<var>t</var> as a kind of pseudo-product type
+that obeys the algebraic laws given in the previous section rather than those of conventional products.)</p>
+
+<p>The complementary operation — stripping <var>q</var>·<var>t</var>
+back to <var>t</var> — is not explicitly denoted; it happens automatically as needed.
+(This is the underlying rule that was in effect, when we stated that
+a <code>beefy int</code> can be assigned to an <code>int</code>.)</p>
+
+<p>Note that type operators in no way alter the <em>value</em> of the expression they are
+used in, only its <em>type</em>.</p>
+
+<h3>Type Variables</h3>
+
+<p>Dieter supports uniform polymorphic types.  Type expressions can contain <dfn>type
+variables</dfn> (which I'll denote with ♥ for no good reason)
+which can unify with concrete types or other type variables during instantiation of a language
+construct.  In practice, this means that procedures can have type
+variables in their parameter and return types; these variables are
+replaced by types specified at the call site whenever a procedure call is type-checked.</p>
+
+<p>The scope of each type variable ranges over a single instance of a single procedure.
+So <code>♥x</code> in the parameter list of <code>grunt</code> is the same type as
+every occurrence of <code>♥x</code> anywhere in the definition of <code>grunt</code> during that
+same invokation of <code>grunt</code>, but may be different from <code>♥x</code> in
+other invokations of <code>grunt</code> (calls to <code>grunt</code> from different call sites),
+and different from <code>♥x</code> appearing in other procedures entirely.</p>
+
+<p>A complication for polymorphism in Dieter is that type variables range not only over core type expressions,
+but <em>also</em> over type qualifiers.  That is, the types <code>beefy gnarly int</code>
+and <code>beefy ♥t</code> unify, and their most general unifier is
+{<code>♥t</code> → <code>gnarly int</code>}.
+This has a few implications for the unification algorithm;
+see <a href="#appendix_a">Appendix A</a> for a detailed discussion of these.</p>
+
+<h3>Modules</h3>
+
+<p>Dieter is a modular language, which has its usual meaning — a Dieter program consists of a set of modules,
+each of which exposes only its interface, not its implementation, to all other modules.
+In Dieter, however, there is a notable twist: every type qualifier is defined by some module which bears the same name.
+The key idea of Dieter is this:
+<strong>a type operator that affects a given qualifier may <em>only</em>
+be used in the module which defines that qualifier.</strong>
+The reasoning for this is similar to the argument
+against using casts in the C language: the goal of typing is to specify constraints
+on the program's structure and to automatically check that they are met.
+If programmers are allowed to muck with types willy-nilly,
+it defeats the purpose of having these constraints in the first place.
+So the power to <code>bestow</code> a particular type qualifier is only given out to
+the module "in charge" of that type qualifier.  This is a form of encapsulation:
+the internal details of some thing (in this case, a type modifier)
+can only be manipulated by the implementation of that thing.</p>
+
+<h3>Procedures</h3>
+
+<p>Each Dieter module consists of a set of procedure declarations.
+Any procedure can be called from any procedure in any module;
+they are comparable to <code>public static</code> methods in Java in this respect.
+Procedures are polymorphic, as mentioned; each one's parameter and return types
+can contain type variables.  At each call site, the type variables are unified with
+the types of the values being passed to them, and resolved ultimately to concrete types.</p>
+
+<p>A bit of administrivia that we should also mention is that Dieter requires procedures to be declared, though not necessarily
+defined, before they are called.  Much like Pascal, it offers a <code>forward</code> declaration
+construct for this purpose.  It can also be used to declare procedures intrinsic to the implementation,
+procedures external to some set of modules, or completely ficticious procedures for the purpose
+of demonstrating and testing the type system.</p>
+
+<h3>Example</h3>
+
+<p>We're now ready to give a very simple example of a Dieter module.</p>
+
+<pre>module beefy
+
+  procedure beef_up(x: ♥t): beefy ♥t
+  begin
+    return (bestow beefy x)
+  end
+
+end</pre>
+
+<p>The intent of this example is to get the general gist of the language across,
+not to demonstrate good programming practice.  The procedure <code>beef_up</code>
+essentially behaves as <code>bestow</code>, except, being a procedure, it may be
+called from any procedure, including those in other modules.  So, it breaks the
+abstraction we just presented; it implements something akin to a
+"generic setter method," providing direct access to a data member that is ordinarily private.</p>
+
+<h3>Object-oriented Programming</h3>
+
+<p>We'll now try to show that this interaction between type qualifiers and modules
+produces something resembling object-oriented programming
+by adding three language features to Dieter: a declaration form and two new types.</p>
+
+<ul>
+<li><dfn>Module-level variables</dfn> are variables that are instantiated
+on, well, the level of the module.  (This is in contrast to local variables
+in procedures, which I haven't said anything about, but which I've nevertheless assumed
+exist in Dieter...)  Module-level variables can't be accessed
+directly from outside the module; they're comparable to <code>private static</code> fields
+in Java.</li>
+<li><code>ref</code> is a built-in type.  These aren't references <em>to</em> anything;
+each is just a unique value, much like values of <code>ref</code> type in the language
+Erlang.  A program can obtain a new <code>ref</code>
+value by calling <code>new_ref()</code>; the value thus obtained is
+guaranteed to be different from all other <code>ref</code> values in
+the program.</li>
+<li><code>map</code> is a built-in type constructor, over range (key)
+and domain (value) types, that defines a data structure that acts like a dictionary.
+The usual square-bracket syntax <code>x[y]</code> is used to reference a location
+within a map.</li>
+</ul>
+
+<p>We can now construct a class of objects like so:</p>
+
+<pre>module person
+
+  var name_map: map from person ref to string
+  var age_map: map from person ref to int
+
+  procedure person_new(name: string, age: int): person ref
+    var p: person ref
+  begin
+    p := bestow person new_ref()
+    name_map[p] := name
+    age_map[p] := age
+    return p
+  end
+
+  procedure person_get_name(p: person ref): string
+  begin
+    return name_map[p]
+  end
+
+  procedure person_attend_birthday_party(p: person ref): void
+  begin
+    age_map[p] := succ(age_map[p])
+  end
+
+end</pre>
+
+<p>Because the type qualifier <code>person</code> is defined by the module
+<code>person</code>, which only uses <code>bestow</code> in one place,
+we know exactly what kind of expressions can result in a type qualified by <code>person</code>.
+More to the point, we know that no other procedure in any other module
+can create a <code>person</code>-qualified type without calling <code>person_new</code>.</p>
+
+<h3>Mixins</h3>
+
+<p>If we loosen the constraints on <code>map</code>s, and say that
+the range (key) type can be left unspecified and that values of all
+types can be used as keys in any given <code>map</code>, then we have
+have a way to make type qualifiers work like <dfn>mixins</dfn>:</p>
+
+<pre>module tagged
+
+  var tag_map : map to string
+
+  procedure make_tagged(x: ♥t): tagged ♥t
+  begin
+    return (bestow tagged x)
+  end
+
+  procedure tag(x: tagged ♥t, y: string): void
+  begin
+    tag_map[x] := y
+  end
+
+  procedure get_tag(x: tagged ♥t): string
+  begin
+    return tag_map[x]
+  end
+
+end</pre>
+
+<p>I think this demonstrates an underrated principle of OO, namely <em>identity</em>.
+If I call <code>tag(make_tagged(4), "mine")</code>, do <em>all</em> occurrences of 4
+have that tag, or just the ephemeral instance of 4 passed to <code>tag</code>?
+If there can't be seperate instances of 4, that might be a reason for OO languages to
+not treat it as an object.  And if you believe seperate instances of 4 are silly, that's
+an argument against "everything is an object".</p>
+
+<h3>Inheritance</h3>
+
+<p>Since module-level variables
+are private to each module, they give Dieter something akin to traditional
+encapsulation.  But what about inheritance?</p>
+
+<p>Well, we can get something like inheritance if we give Dieter another
+feature.  We haven't said much about scope of names so far; in particular,
+we haven't said what happens when one declares two different procedures
+with the same name and number of parameters, and what, if anything, should happen
+when client code tries to call such ambiguously declared procedures.</p>
+
+<p>Hey, in the spirit of compromise, let's just say that when this happens,
+<em>all</em> those procedures are called!  Specifically, all the procedures
+whose formal parameter types are compatible with the types of the actual parameters are called
+— procedures with parameters of completely different types, or of more
+highly qualified types, are not called.</p>
+
+<p>And, to keep this interesting, let's say that the order in which these procedures are called
+depends on the generality of their parameter types.
+If <code>grind(beefy ♥t):void</code> and <code>grind(beefy gnarly ♥t):void</code>
+are both defined, and <code>grind</code> is called with a variable whose type is qualified
+with both <code>beefy</code> and <code>gnarly</code>, then
+<code>grind(beefy ♥t):void</code> (the more general)
+should be called first, then
+<code>grind(beefy gnarly ♥t):void</code> (the more specific)
+called second.</p>
+
+<p>There are a few issues now that need to be dealt with.</p>
+
+<ul>
+<li>We've discussed compatibility of parameter types of a procedure,
+but not its return type.  For simplicity, let's just disallow differing return types
+on different procedures with the same name — it's a compile-time error.</li>
+
+<li>It would be nice if procedures had a way to capture the results of a
+procedure that was called before them in this calling chain.  So, let's say
+that every procedure has access to an implicit read-only variable that holds the result
+of the previous procedure (if any) that was executed along this chain.  The
+type of this variable will always be the same as the return type of the current
+procedure (because by the previous bullet point, the previous procedure must
+have had the same return type as the current one.)  If no previous procedure
+with this signature was executed, the value will be <code>nil</code>.
+For syntax, let's call this implicit variable <code>super</code>.</li>
+
+<li>It would also be nice if a procedure could prevent
+any further procedures from being called in this chain.
+Let's give Dieter a special form of <code>return</code> for
+this purpose — say, <code>return final</code>.</li>
+
+<li>Finally, what about incomparable signatures?  Say that, in the above example,
+procedures <code>grind(gnarly ♥t):void</code> and <code>grind(♥t):void</code>
+are defined too.  Then, when <code>grind</code> is called with a
+<code>beefy gnarly</code> variable, <code>grind(♥t):void</code>
+gets called first (it's the most general), but which gets called next:
+<code>grind(gnarly ♥t):void</code> or
+<code>grind(beefy ♥t):void</code>?  We can let the programmer
+give some sort of disambiguating assertion, like
+<code>order beefy &lt; gnarly</code>, to enforce a partial ordering between type
+qualifiers.  Then we know that the more general procedure —
+in this case <code>grind(gnarly ♥t):void</code> —
+will be called before <code>grind(beefy ♥t):void</code>, because we just
+noted that, all other things being equal, we want <code>gnarly</code>
+to be treated as more general than <code>beefy</code>.</li>
+</ul>
+
+<p>Now: do you think it's a coincidence that the last problem looks similar
+to the problems that come from multiple inheritance, where we don't quite know
+what we should be inheriting when two of our superclasses are descendants of
+the same class?  Well, I can tell you this
+much: it's definately <em>not</em>
+a coincidence that I chose <code>super</code> and <code>final</code> for the
+names of the other two features!</p>
+
+<p>This whole thing looks to me very much as if we were
+approaching object-oriented programming from another direction.
+Which might not be such a surprise, if one thinks of subclassing as
+a special form of type qualification.</p>
+
+<p>Of course, it's not <em>quite</em> the same in Dieter as it is in most OO languages.
+For example, procedures in Dieter do not actually override those with more general
+(less qualified) signatures, they simply add to them.  But, those
+more specific procedures could be written to ignore the results of, and undo the state
+changes of, the more general procedures in the chain that were called first,
+which would accomplish essentially the same thing.</p>
+
+<h2>Background</h2>
+
+<p>Why did I design this language, anyway?</p>
+
+<h3>Hungarian Notation</h3>
+
+<p>The origins of the central idea in Dieter — <strong>encapsulate type qualifiers
+in modules that define them</strong> — was an indirect result of reading
+<a class="external" href="http://www.joelonsoftware.com/articles/Wrong.html">Joel Spolsky's
+explanation of the value of Hungarian notation</a>.  He contrasts the original notion of
+Hungarian notation with the cargo-cultist convention that it somehow degenerated into.  He
+explains how it helps make incorrect programs look incorrect.</p>
+
+<p>I thought, why stop there?  If the purpose of Hungarian notation is to make evident assignment errors between
+variables that have the same type but different <em>roles</em>, then why can't
+you have the compiler type-check the roles, too?  Well, you can, and that's
+basically what Dieter is doing with type qualifiers — using them as
+a computer-checkable form of Hungarian notation.</p>
+
+<h3>Aliasing Prevention</h3>
+
+<p>What further spurred development of the idea was the problem of aliasing.
+Aliasing is where some part of a program
+is dealing with two references which might or might not point to the same
+thing — importantly, you can't make guarantees for the sake of
+safety (or optimization) that they <em>don't</em> point to the same thing.
+So you have to assume that they might.</p>
+
+<p>The contribution of type qualifiers to this is that in some situations
+you might be able to give the two references two different type qualifiers,
+even though they are basically the same type, thus guaranteeing that they
+don't in fact refer to the same value.</p>
+
+<p>There's a significant problem with this, though: it
+still doesn't give you a hard-and-fast guarantee that no aliasing is occurring,
+because the module that defines a modifier can still do whatever it likes with it
+internally.  It gives you only a sort of "module-level guarantee"; only if you trust the
+individual modules involved to not be aliasing values of these types,
+can you be sure the values won't be aliased "in the large".</p>
+
+<p>In addition, it's far from certain that there are lots of cases where this would
+<em>in practice</em> support some genuine non-trivial beneficial code pattern while
+preventing aliasing.  It could be that all examples where this works are quite
+contrived.  I suppose that if I were to do further work on Dieter, it would be to try to
+discover whether this is really the case or not.</p>
+
+<h3>Related work</h3>
+
+<p>Type qualifiers have been around informally for a long time, probably almost as long as
+there have been types.  Here's <a class="external" href="http://www.lysator.liu.se/c/dmr-on-noalias.html">Dennis Ritchie
+ranting against certain type qualifiers proposed for ANSI C</a>.  (One of which, coincidentally, was intended to deal with
+aliasing, albiet quite myopically.)</p>
+
+<p>Mark P Jones has written
+<a class="external" href="http://web.cecs.pdx.edu/~mpj/pubs/esop92.html">a paper</a>
+and <a class="external" href="http://web.cecs.pdx.edu/~mpj/pubs/thesis.html">a thesis-turned-book</a>
+describing a theory of qualified types. Dieter can be seen as a concrete instance of
+Jones's theory (as can many other type systems — it's a very general theory),
+although I have not explicated it as such here, as the resulting article would likely have been much less accessible.</p>
+
+<p>Haskell's type classes (another type system easily seen as a concrete instance of qualified types)
+are very similar to Dieter's type qualifiers.  However, in Haskell, every type either belongs to or does not
+belong to some class: every <code>Int</code> is an <code>Eq Ord</code>, due to the mathematical
+properties of <code>Int</code>s.
+In Dieter, every type can potentially be modified with every qualifier: there can be <code>int</code>s,
+<code>eq int</code>s, <code>ord int</code>s, and <code>eq ord int</code>s, all slightly different.</p>
+
+<p>On the other end of the spectrum, solidly in the domain of application rather than theory,
+<a class="external" href="http://www.cs.umd.edu/~jfoster/cqual/">CQUAL</a>
+is an extension of C which adds user-defined type qualifiers.
+CQUAL is primarily concerned with inferring type qualifiers
+where there are none, and is not concerned with encapsulating qualifiers within modules.</p>
+
+<h2>Conclusion</h2>
+
+<p>I hope you found Dieter to be an entertaining little diversion through type-qualifier-land
+(and that you did not expect too much more, or I imagine you'll have been
+somewhat disappointed.)</p>
+
+<p>Although there is no reference implementation of Dieter (and it's unlikely that there could be without
+some more specified semantics,) there is a reference parser and type-checker (not at all guaranteed to be bug-free)
+written in Python of all things.</p>
+
+<h2>Appendix A</h2>
+
+<h3>Polymorphic Typing with Type Qualifiers</h3>
+
+<p>While Dieter does not support full-blown type inference — all variables must be
+explicitly notated with their type — it does support uniform polymorphic typing using type variables, and it uses the
+core mechanism of type inference, namely unification, to give those variables concrete types at each usage instance.</p>
+
+<p>In place of a concrete type, a type variable may be given.  Like a concrete type, this type variable can
+possess any number of type qualifiers.  During each instance of the thing being
+typed (for example, each call to a procedure,) the type variables are resolved
+into concrete types by unification.</p>
+
+<p>The presence of type qualifiers makes this process more complicated.</p>
+
+<p>The first thing to note is that unification during inference is no longer
+commutative — it is no longer the case that, if <var>A</var>
+unifies with <var>B</var>, then <var>B</var> necessarily unifies with
+<var>A</var>.  As mentioned, a procedure with a formal parameter of
+type <code>gnarly int</code> will not accept (i.e. is not compatible
+with) an actual parameter with type simply <code>int</code>.
+But the reverse situation is acceptable — we think of the
+<code>gnarly</code> modifier being 'dropped'.  The convention we will
+use when describing this non-commutative unification is to call the
+formal parameter (or variable being assigned to) the <dfn>receptor</dfn>
+and write it on the left, and call the actual parameter (or expression
+being assigned) the <dfn>provider</dfn> and write it on the right.</p>
+
+<p>The cardinal rule, which applies to every primitive type expression,
+including those with variables, is that <strong>the qualifiers on the provider
+must be a superset of the qualifiers on the receptor</strong>.</p>
+
+<p>As during the conventional algorithm, an unbound type variable in either type expression will
+unify with (take on the binding of) the type subexpression that corresponds with it in
+the other type expression.  In addition, here it will also take on the type
+qualifiers of that subexpresion, if it can.  This leaves us with the question
+of which ones, and when.</p>
+
+<p>If the variable is in the receptor position, it might as well unify with <em>all</em>
+of the type qualifiers on the provider, because those must be a superset
+of the receptor's in order to unify at all, and because down the road,
+they can always be 'dropped' from the variable, should it be used as a
+provider.</p>
+
+<p>If the variable is in the provider position, the type in receptor position
+can't possibly have any more qualifiers than the variable — or it wouldn't
+be able to unify in the first place.  So the variable might as well unify
+with the whole expression in the receptor position.</p>
+
+<p>If both positions contain variables, the provider's variable should be
+bound to the receptor's type expression, because it will be the one
+that is more general.</p>
+
+<p>The other thing to note that differs from conventional type inference
+is that <strong>a type variable, once bound to a qualified type, may be
+<em>re-bound</em> to a less qualified type</strong>.</p>
+
+<h3>Examples</h3>
+
+<p>Module names aren't really important for this, so they're omitted.
+We'll assume the following intrinsics are available:</p>
+
+<pre>
+forward and(bool, bool): bool
+forward equal(♥t, ♥t): bool
+forward print(string): void
+</pre>
+
+<h4>Example 1</h4>
+
+<pre>
+procedure thing(): void
+  var i, j: int
+  var s, t: string
+begin
+  if and(equal(i, j), equal(s, t)) then print("yes") else print("no")
+end
+</pre>
+
+<p>Should typecheck successfully, because the two calls to <code>equal</code>
+are two seperate instances of the type ♥t, but the two parameters inside the
+type signature of <code>equal</code> are the same instance.</p>
+
+<h4>Example 2</h4>
+
+<pre>
+forward glunt(beefy gnarly ♥t): gnarly ♥t
+...
+procedure thing(): void
+  var i: beefy gnarly int
+begin
+  if equal(glunt(i), 4) then print("yes") else print("no")
+end
+</pre>
+
+<p>Should typecheck successfully. The call to <code>glunt</code>
+returns a <code>gnarly int</code>.  Midway through typechecking the
+call to <code>equal</code>, we obtain {♥t → <code>gnarly int</code>}.
+But when we typecheck the second argument we see that it's simply an <code>int</code>.
+We <em>re-bind</em> the variable to obtain {♥t → <code>int</code>}.
+This is OK with respect to the first argument — we just consider the
+<code>gnarly</code> to be dropped.</p>
+
+<h4>Example 3</h4>
+
+<pre>
+forward traub(beefy gnarly ♥t): bool
+...
+procedure thing(p: beefy ♥s): ♥s
+begin
+  if traub(p) then print("yes") else print("no")
+  return p
+end
+</pre>
+
+<p>Should <em>not</em> typecheck.  The call to <code>traub</code>
+needs something qualified with both <code>beefy</code> and <code>gnarly</code>.
+<code>beefy ♥s</code> will fail to unify with it.</p>
+
+<h2>Grammar</h2>
+
+<pre>
+Dieter    ::= {Module | Ordering | Forward} ".".
+Ordering  ::= "order" Name/qual "&lt;" Name/qual.
+Module    ::= "module" Name/qual {"var" VarDecl} {ProcDecl} "end".
+Forward   ::= "forward" Name/proc "(" [Type {"," Type}] ")" ":" Type.
+VarDecl   ::= Name/var ":" Type.
+ProcDecl  ::= "procedure" Name/proc "(" [VarDecl {"," VarDecl}] ")" ":" Type {"var" VarDecl} Statement.
+Statement ::= "begin" {Statement} "end"
+            | "if" Expr "then" Statement ["else" Statement]
+            | "while" Expr "do" Statement
+            | Name/var ["[" Expr "]"] ":=" Expr
+            | Name/proc "(" [Expr {"," Expr}] ")"
+            | "return" ["final"] Expr
+            .
+Expr      ::= Name/var ["[" Expr "]"]
+            | Name/proc "(" [Expr {"," Expr}] ")"
+            | "(" Expr ")"
+            | "bestow" Qualifier Expr
+            | "super"
+            .
+Type      ::= {Name/qual} BareType.
+BareType  ::= "map" ["from" Type] "to" Type
+            | "♥" Name/tvar
+            | "bool" | "int" | "rat" | "string" | "ref"
+            .
+</pre>
+</body>
+</html>
+/* -*- encoding: utf-8 -*- */
+/* check that diff instances of equal(♥t, ♥t) can unify to diff types */
+
+forward and(bool, bool): bool
+forward equal(♥t, ♥t): bool
+forward print(string): void
+
+module example1
+
+procedure thing(): void
+  var i: int
+  var j: int
+  var s: string
+  var t: string
+begin
+  if and(equal(i, j), equal(s, t)) then print("yes") else print("no")
+end
+
+end.
+/* -*- encoding: utf-8 -*- */
+/* from the article */
+
+module tagged
+
+  var tag_map : map to string
+
+  procedure make_tagged(x: ♥t): tagged ♥t
+  begin
+    return (bestow tagged x)
+  end
+
+  procedure tag(x: tagged ♥t, y: string): void
+  begin
+    tag_map[x] := y
+  end
+
+  procedure get_tag(x: tagged ♥t): string
+  begin
+    return tag_map[x]
+  end
+
+end.
+/* -*- encoding: utf-8 -*- */
+/* check that equal(♥t, ♥t) unifies with equal(gnarly int, int) */
+
+forward and(bool, bool): bool
+forward equal(♥t, ♥t): bool
+forward print(string): void
+
+forward glunt(beefy gnarly ♥t): gnarly ♥t
+
+module example2
+
+procedure thing(): void
+  var i: beefy gnarly int
+begin
+  if equal(glunt(i), 4) then print("yes") else print("no")
+end
+
+end.
+/* -*- encoding: utf-8 -*- */
+/* check that proc(beefy gnarly ♥t) cannot be passed something not known to be gnarly */
+
+forward and(bool, bool): bool
+forward equal(♥t, ♥t): bool
+forward print(string): void
+
+forward traub(beefy gnarly ♥t): bool
+
+module example3 fails /* because we pass traub something that isn't known to be gnarly */
+
+procedure thing(p: beefy ♥s): ♥s
+begin
+  if traub(p) then print("yes") else print("no")
+  return p
+end
+
+end.
+/* -*- encoding: utf-8 -*- */
+/* check that a gnarly int variable can be assigned a value of type beefy gnarly int */
+
+forward and(bool, bool): bool
+forward equal(♥t, ♥t): bool
+forward print(string): void
+
+forward geget(int): beefy gnarly int
+forward traub(gnarly ♥t): bool
+
+module example4
+
+procedure thing(): void
+  var i: gnarly int
+  var j: gnarly int
+begin
+  j := geget(i)
+  if traub(i) then print("yes") else print("no")
+  if traub(j) then print("yes") else print("no")
+end
+
+end.
+/* -*- encoding: utf-8 -*- */
+/* check that "if" can accept a beefy bool */
+
+order beefy < snarky
+
+forward beef(bool, int): int
+forward turkey(int, int, int): bool
+
+module beefy
+  var pink: bool
+  procedure grief(cake: beefy bool): beefy int
+  begin
+    beef(cake,5)
+    pink := turkey(1,2,3)
+    if cake then
+      return bestow beefy 5
+    else
+      return bestow beefy 6
+  end
+end
+
+module snarky
+  procedure polymorph(value: ♥t): ♥t return value
+end.
+/* -*- encoding: utf-8 -*- */
+/* simple check for wrong concrete type assignment */
+
+module example6 fails
+  procedure grief(b: bool, i: int): bool
+  begin
+    b := i
+    return b
+  end
+end.
+/* -*- encoding: utf-8 -*- */
+/* check that only module x can bestow x qualifier on types */
+
+module beefy fails /* because we can't bestow snarky here */
+  procedure hit(input: int): snarky int
+  begin
+    return bestow snarky input
+  end
+end
+
+module snarky
+  procedure polymorph(value: ♥t): ♥t return value
+end.
+/* -*- encoding: utf-8 -*- */
+/* from the article */
+
+module beefy
+
+  procedure beef_up(x: ♥t): beefy ♥t
+  begin
+    return (bestow beefy x)
+  end
+
+end
+/* -*- encoding: utf-8 -*- */
+/* from the article */
+
+forward new_ref(): ref
+forward succ(int): int
+
+module person
+
+  var name_map: map from person ref to string
+  var age_map: map from person ref to int
+
+  procedure person_new(name: string, age: int): person ref
+    var p: person ref
+  begin
+    p := bestow person new_ref()
+    name_map[p] := name
+    age_map[p] := age
+    return p
+  end
+
+  procedure person_get_name(p: person ref): string
+  begin
+    return name_map[p]
+  end
+
+  procedure person_attend_birthday_party(p: person ref): void
+  begin
+    age_map[p] := succ(age_map[p])
+  end
+
+end.
+#!/usr/bin/python
+# -*- coding: utf-8 -*-
+
+"""
+dieter.py -- driver for parsing/typechecking the Dieter programming language.
+$Id: dieter.py 382 2010-01-28 23:40:43Z cpressey $
+"""
+
+import sys
+from optparse import OptionParser
+import logging
+
+from dieter.scanner import Scanner
+from dieter.parser import Parser
+from dieter.context import TypingContext
+
+
+def load(filename, options):
+    f = open(filename, "r")
+    scanner = Scanner(f.read())
+    f.close()
+    parser = Parser(scanner)
+    ast = parser.Dieter()
+    context = TypingContext(None)
+    if options.verbose:
+        logging.basicConfig(level=logging.INFO)
+    ast.typecheck(context)
+    if options.dump_ast:
+        print "--- AST: ---"
+        print ast.dump(0)
+    if options.dump_symtab:
+        print "--- Symbol Table: ---"
+        context.dump()
+
+def main(argv):
+    optparser = OptionParser("[python] dieter.py {options} {source.dtr}\n" + __doc__)
+    optparser.add_option("-a", "--dump-ast",
+                         action="store_true", dest="dump_ast", default=False,
+                         help="dump AST after source is parsed")
+    optparser.add_option("-s", "--dump-symtab",
+                         action="store_true", dest="dump_symtab", default=False,
+                         help="dump symbol table after source is parsed")
+    optparser.add_option("-v", "--verbose",
+                         action="store_true", dest="verbose", default=False,
+                         help="""be verbose about actions taken internally
+                                 (e.g. type unification)""")
+    (options, args) = optparser.parse_args(argv[1:])
+    for filename in args:
+        load(filename, options)
+
+
+if __name__ == "__main__":
+    main(sys.argv)

Empty file added.

src/dieter/ast.py

+#!/usr/local/bin/python
+# -*- coding: utf-8 -*-
+
+"""
+ast.py -- Abstract Syntax Trees for the Dieter programming language.
+$Id: ast.py 398 2010-02-04 00:20:41Z cpressey $
+"""
+
+import logging
+
+import dieter.type as type
+import dieter.context as context
+
+logger = logging.getLogger("ast")
+
+
+class AST:
+    """Class representing nodes in an abstract syntax tree.
+    
+    Each node has a type.  Initially this is None, meaning
+    no type has been assigned.  This is not the same as
+    VoidType.
+    
+    Calling the typecheck method of a node attempts to
+    compute the types of that node, and all of its children,
+    in the given typing context.
+
+    """
+
+    type = None
+
+    def typecheck(self, context):
+        """Checks that this part of the AST is well-typed, and set the type
+        attribute of the AST to the type.
+
+        Returns nothing.  Raises an exception if AST is ill-typed.
+        (This method is abstract, and is only included on AST for the sake
+        of documentation.)
+
+        """
+        raise NotImplementedError
+
+
+class Program(AST):
+    def __init__(self):
+        self.forwards = []
+        self.modules = []
+        self.orderings = []
+
+    def add_forward(self, forward):
+        self.forwards.append(forward)
+
+    def add_module(self, module):
+        self.modules.append(module)
+
+    def add_ordering(self, ordering):
+        self.orderings.append(ordering)
+
+    def dump(self, indent):
+        d = ('  ' * indent) + "program\n"
+        for forward in self.forwards:
+            d += forward.dump(indent + 1)
+        for ordering in self.orderings:
+            d += ordering.dump(indent + 1)
+        for module in self.modules:
+            d += module.dump(indent + 1)
+        return d
+
+    def typecheck(self, context):
+        for forward in self.forwards:
+            forward.typecheck(context)
+        for ordering in self.orderings:
+            ordering.typecheck(context)
+        for module in self.modules:
+            if module.fails:
+                logger.info("typechecking module " + module.name +  " (intends to fail)")
+                failed = False
+                try:
+                    module.typecheck(context)
+                except context.TypingError, e:
+                    logger.info("caught TypingError " + str(e))
+                    failed = True
+                except Exception, e:
+                    logger.info("caught Exception " + str(e))
+                finally:
+                    if not failed:
+                        raise context.TypingError("module claimed to fail typechecking but didn't")
+            else:
+                logger.info("typechecking module " + module.name +  " (intends to succeed)")
+                module.typecheck(context)
+
+
+class Ordering(AST):
+    def __init__(self, before, after):
+        self.before = before
+        self.after = after
+
+    def dump(self, indent):
+        d = ('  ' * indent) + "order " + self.before + " < " + self.after + "\n"
+        return d
+
+    def typecheck(self, context):
+        # XXX context.add_ordering(self.before, self.after)
+        pass
+
+
+class FwdDecl(AST):
+    def __init__(self, name, type_expr):
+        self.name = name
+        self.type_expr = type_expr
+
+    def dump(self, indent):
+        d = ('  ' * indent) + 'forward ' + self.name + " : \n" + self.type_expr.dump(indent+1) + "\n"
+        return d
+
+    def typecheck(self, context):
+        self.type_expr.typecheck(context)
+        self.type = self.type_expr.type
+        context.associate(self.name, self.type)
+
+
+### Modules...
+
+class Module(AST):
+    def __init__(self, name, fails):
+        self.name = name
+        self.fails = fails
+        self.locals = []
+        self.procs = []
+
+    def add_local(self, local):
+        self.locals.append(local)
+
+    def add_proc(self, proc):
+        self.procs.append(proc)
+
+    def dump(self, indent):
+        d = ('  ' * indent) + 'module ' + self.name + "\n"
+        for local in self.locals:
+            d += local.dump(indent + 1)
+        for proc in self.procs:
+            d += proc.dump(indent + 1)
+        return d
+
+    def typecheck(self, context):
+        logger.info("typechecking module " + self.name)
+        context.associate_qualifier(self.name)
+        # make a new context for this module, to contain module-local variables
+        my_context = context.new_module(self)
+        for local in self.locals:
+            local.typecheck(my_context)
+        for proc in self.procs:
+            proc.typecheck(my_context)
+
+
+class VarDecl(AST):
+    def __init__(self, name, type_expr):
+        self.name = name
+        self.type_expr = type_expr
+
+    def dump(self, indent):
+        d = ('  ' * indent) + ('var ' + self.name + ' : ' +
+                               self.type_expr.dump(0) + "\n")
+        return d
+
+    def typecheck(self, context):
+        self.type_expr.typecheck(context)
+        self.type = self.type_expr.type
+        context.associate(self.name, self.type)
+
+
+class ProcDecl(AST):
+    def __init__(self, name):
+        self.name = name
+        self.args = []
+        self.locals = []
+        self.return_type_expr = None
+        self.body = None
+
+    def add_arg(self, arg):
+        self.args.append(arg)
+
+    def add_local(self, local):
+        self.locals.append(local)
+
+    def set_body(self, body):
+        self.body = body
+
+    def set_return_type_expr(self, type_expr):
+        self.return_type_expr = type_expr
+
+    def dump(self, indent):
+        d = ('  ' * indent) + ('procedure ' + self.name + " : " +
+                               self.return_type_expr.dump(0) + "\n")
+        for arg in self.args:
+            d += arg.dump(indent + 1)
+        for local in self.locals:
+            d += local.dump(indent + 1)
+        d += self.body.dump(indent + 1)
+        return d
+
+    def typecheck(self, context):
+        self.return_type_expr.typecheck(context)
+        return_type = self.return_type_expr.type
+        proc_type = type.TypeProc(return_type)
+        # make a new context for this procedure, to contain args and local variables
+        my_context = context.new_procedure(self)
+        for arg in self.args:
+            arg.typecheck(my_context)
+            proc_type.add_arg_type(arg.type)
+        for local in self.locals:
+            local.typecheck(my_context)
+        context.global_context().associate(self.name, proc_type)
+        self.body.typecheck(my_context)
+
+
+### ... statements ...
+
+class CompoundStatement(AST):
+    def __init__(self):
+        self.steps = []
+
+    def add_step(self, step):
+        self.steps.append(step)
+
+    def dump(self, indent):
+        d = ('  ' * indent) + "begin\n"
+        for step in self.steps:
+            d += step.dump(indent + 1)
+        d += ('  ' * indent) + "end\n"
+        return d
+
+    def typecheck(self, context):
+        for step in self.steps:
+            step.typecheck(context)
+
+class IfStatement(AST):
+    def __init__(self, test, then_stmt, else_stmt):
+        self.test = test
+        self.then_stmt = then_stmt
+        self.else_stmt = else_stmt
+
+    def dump(self, indent):
+        d = ('  ' * indent) + "if\n"
+        d += self.test.dump(indent + 1)
+        d += ('  ' * indent) + "then\n"
+        d += self.then_stmt.dump(indent + 1)
+        if self.else_stmt != None:
+            d += ('  ' * indent) + "else\n"
+            d += self.else_stmt.dump(indent + 1)
+        return d
+
+    def typecheck(self, context):
+        self.test.typecheck(context)
+        test_type = self.test.type
+        context.assert_equiv("if", type.TypeBool(), test_type)
+        self.then_stmt.typecheck(context)
+        self.else_stmt.typecheck(context)
+
+
+class WhileStatement(AST):
+    def __init__(self, test, body):
+        self.test = test
+        self.body = body
+
+    def dump(self, indent):
+        d = ('  ' * indent) + "while\n"
+        d += self.test.dump(indent + 1)
+        d = ('  ' * indent) + "do\n"
+        d += self.body.dump(indent + 1)
+        return d
+
+    def typecheck(self, context):
+        self.test.typecheck(context)
+        context.assert_equiv("while", test_type, type.TypeBool())
+        self.body.typecheck(context)
+
+
+class ReturnStatement(AST):
+    def __init__(self, expr):
+        self.expr = expr
+
+    def dump(self, indent):
+        d = ('  ' * indent) + "return\n"
+        d += self.expr.dump(indent + 1)
+        return d
+
+    def typecheck(self, context):
+        self.expr.typecheck(context)
+        return_type = self.expr.type
+        context.assert_equiv("return", return_type, context.get_procedure().return_type_expr.type)
+
+
+class CallStatement(AST):
+    def __init__(self, name):
+        self.name = name
+        self.args = []
+
+    def add_arg(self, arg):
+        self.args.append(arg)
+
+    def dump(self, indent):
+        d = ('  ' * indent) + self.name + "(\n"
+        for arg in self.args:
+            d += arg.dump(indent + 1)
+        d += ('  ' * indent) + ")\n"
+        return d
+
+    def typecheck(self, context):
+        logger.info("typechecking procedure call to " + self.name)
+        arg_types = []
+        for arg in self.args:
+            arg.typecheck(context)
+            arg_types.append(arg.type)
+        return_type = context.check_call(self.name, arg_types)
+        self.type = return_type
+
+
+class AssignStatement(AST):
+    def __init__(self, name):
+        self.name = name
+        self.index = None
+        self.expr = None
+
+    def set_index(self, index):
+        self.index = index
+
+    def set_expr(self, expr):
+        self.expr = expr
+
+    def dump(self, indent):
+        d = ('  ' * indent) + self.name + " "
+        if self.index != None:
+            d += ('  ' * indent) + "[\n"
+            d += self.index.dump(indent + 1)
+            d += ('  ' * indent) + "] "
+        d += ":=\n"
+        d += self.expr.dump(indent + 1)
+        return d
+
+    def typecheck(self, context):
+        lhs_type = context.get_type(self.name)
+        # if this variable is a map type then make sure its index is the right type
+        if isinstance(lhs_type, type.TypeMap):
+            assert self.index != None
+            self.index.typecheck(context)
+            index_type = self.index.type
+            if lhs_type.from_type is not None:
+                context.assert_equiv("index", lhs_type.from_type, index_type)
+            lhs_type = lhs_type.to_type
+        self.expr.typecheck(context)
+        rhs_type = self.expr.type
+        context.assert_equiv("assignment", lhs_type, rhs_type)
+
+
+### ... expressions ...
+
+class IntConstExpr(AST):
+    def __init__(self, value):
+        self.value = value
+
+    def dump(self, indent):
+        d = ('  ' * indent) + str(self.value) + "\n"
+        return d
+
+    def typecheck(self, context):
+        self.type = type.TypeInt()
+
+
+class StringConstExpr(AST):
+    def __init__(self, value):
+        self.value = value
+
+    def dump(self, indent):
+        d = ('  ' * indent) + "\"" + self.value + "\"\n"
+        return d
+
+    def typecheck(self, context):
+        self.type = type.TypeString()
+
+
+class VarRefExpr(AST):
+    def __init__(self, name):
+        self.name = name
+        self.index = None
+
+    def set_index(self, index):
+        self.index = index
+
+    def dump(self, indent):
+        d = ('  ' * indent) + str(self.name) + " "
+        if self.index != None:
+            d += ('  ' * indent) + "[\n"
+            d += self.index.dump(indent + 1)
+            d += ('  ' * indent) + "]"
+        d += "\n"
+        return d
+
+    def typecheck(self, context):
+        self.type = context.get_type(self.name)
+        # if this variable is a map type then make sure its index is the right type
+        if isinstance(self.type, type.TypeMap):
+            assert self.index != None
+            self.index.typecheck(context)
+            index_type = self.index.type
+            if self.type.from_type is not None:
+                context.assert_equiv("index", self.type.from_type, index_type)
+            self.type = self.type.to_type
+
+
+class SuperExpr(AST):
+    def __init__(self):
+        pass
+
+    def dump(self, indent):
+        d = ('  ' * indent) + "super\n"
+        return d
+
+    def typecheck(self, context):
+        # same as the return type of the current procedure
+        self.type = context.get_procedure().return_type
+
+
+class BestowExpr(AST):
+    def __init__(self, qual, expr):
+        self.qual = qual
+        self.expr = expr
+
+    def dump(self, indent):
+        d = ('  ' * indent) + "bestow " + self.qual + "\n"
+        d += self.expr.dump(indent + 1)
+        return d
+
+    def typecheck(self, context):
+        if self.qual != context.get_module().name:
+            raise context.TypingError("type operation on %s used outside of its module (in module %s)" %
+              (self.qual, context.get_module().name))
+        else:
+            self.expr.typecheck(context)
+            self.type = self.expr.type.qualify(self.qual)
+
+
+class CallExpr(AST):
+    def __init__(self, name):
+        self.name = name
+        self.args = []
+
+    def add_arg(self, arg):
+        self.args.append(arg)
+
+    def dump(self, indent):
+        d = ('  ' * indent) + self.name + "(\n"
+        for arg in self.args:
+            d += arg.dump(indent + 1)
+        d += ('  ' * indent) + ")\n"
+        return d
+
+    def typecheck(self, context):
+        logger.info("typechecking function call to " + self.name)
+        arg_types = []
+        for arg in self.args:
+            arg.typecheck(context)
+            arg_types.append(arg.type)
+        return_type = context.check_call(self.name, arg_types)
+        self.type = return_type
+
+
+### ... type expressions ...
+
+class PrimitiveTypeExpr(AST):
+    def __init__(self, token):
+        self.token = token
+
+    def __str__(self):
+        return self.token
+
+    def dump(self, indent):
+        d = ('  ' * indent) + self.token
+        return d
+
+    def typecheck(self, context):
+        map = {
+            'void': type.TypeVoid,
+            'bool': type.TypeBool,
+            'int': type.TypeInt,
+            'rat': type.TypeRat,
+            'string': type.TypeString,
+            'ref': type.TypeRef
+        }
+        self.type = map[self.token]()
+
+
+class MapTypeExpr(AST):
+    def __init__(self, range, domain):
+        self.range = range
+        self.domain = domain
+
+    def dump(self, indent):
+        d = ('  ' * indent) + "map from " + self.range.dump(0)
+        if self.domain is not None:
+            d = d + " to " + self.domain.dump(0)
+        return d
+
+    def typecheck(self, context):
+        self.range.typecheck(context)
+        if self.domain is None:
+            self.type = type.TypeMap(self.range.type, None)
+        else:
+            self.domain.typecheck(context)
+            self.type = type.TypeMap(self.range.type, self.domain.type)
+
+
+class ProcTypeExpr(AST):
+    def __init__(self, arg_type_exprs, return_type_expr):
+        self.arg_type_exprs = arg_type_exprs
+        self.return_type_expr = return_type_expr
+
+    def dump(self, indent):
+        d = ('  ' * indent) + 'proc('
+        for arg_type_expr in self.arg_type_exprs:
+            d += arg_type_expr.dump(0) + ","
+        d = d[:-1] + "): " + self.return_type_expr.dump(0)
+        return d
+
+    def add_arg_type_expr(self, arg_type_expr):
+        self.arg_type_exprs.append(arg_type_expr)
+
+    def typecheck(self, context):
+        for arg_type_expr in self.arg_type_exprs:
+            arg_type_expr.typecheck(context)
+        self.return_type_expr.typecheck(context)
+        self.type = type.TypeProc(self.return_type_expr.type)
+        for arg_type_expr in self.arg_type_exprs:
+            self.type.add_arg_type(arg_type_expr.type)
+
+
+class QualifiedTypeExpr(AST):
+    def __init__(self, qual, type_expr):
+        self.qual = qual
+        self.type_expr = type_expr
+
+    def dump(self, indent):
+        return self.qual + " " + self.type_expr.dump(0)
+
+    def typecheck(self, context):
+        self.type_expr.typecheck(context)
+        self.type = self.type_expr.type.qualify(self.qual)
+
+
+class TypeVariableExpr(AST):
+    def __init__(self, name):
+        self.name = name
+
+    def dump(self, indent):
+        return "*" + self.name
+
+    def typecheck(self, context):
+        self.type = type.TypeVar(self.name)

src/dieter/context.py

+#!/usr/local/bin/python
+# -*- coding: utf-8 -*-
+
+"""
+context.py -- typing contexts for the Dieter programming language.
+$Id: context.py 492 2010-04-26 21:16:03Z cpressey $
+"""
+
+from dieter.type import Type, TypeProc
+import logging
+
+logger = logging.getLogger("context")
+
+
+class TypingError(Exception):
+    """An exception indicating that a type incompatibility was encountered."""
+    pass
+
+
+class TypingContext(object):
+    """Class that associates names with types in a given scope.
+
+    A TypingContext object is passed along the AST during typechecking,
+    being modified as a result.  Each TypingContext can have a parent
+    TypingContext; lookups for types go to it if not found in the current one.
+    
+    It's actually more like a symbol table, because it associates
+    every symbol with some information about it, even if it's not
+    a type...
+
+    """
+
+    def __init__(self, parent):
+        self.map = {}
+        self.parent = parent
+        self.module = None
+        self.TypingError = TypingError
+
+    def associate(self, name, type):
+        """Associate the given name with the given type in this context.
+
+        The name must be a name not already present in this context.
+
+        """
+        if name in self.map:
+            raise TypingError("name " + name + " already bound to " + str(type))
+        assert isinstance(type, Type)
+        logger.info("associating " + name + " with " + str(type))
+        self.map[name] = type
+
+    def associate_qualifier(self, name):
+        logger.info("registering " + name + " as a type qualifier")
+        self.map[name] = "qualifier"
+
+    def get_type(self, name):
+        if name in self.map:
+            logger.info("got type for " +name+ ": " + str(self.map[name]))
+            return self.map[name]
+        elif self.parent != None:
+            logger.info("name " + name + " not found, trying parent context")
+            return self.parent.get_type(name)
+        else:
+            raise TypingError("name " + name + " totally not found")
+
+    def dump(self):
+        for k, v in self.map.iteritems():
+            if isinstance(v, Type):
+                print k + " : " + str(v)  # return string instead?
+            else:
+                print k + " : " + v
+
+    def assert_equiv(self, inwhat, s, t):
+        if not s.unify(t):
+            raise TypingError("in " + inwhat + ": " + str(s) +
+                              " not compatible with " + str(t))
+
+    def check_call(self, proc_name, arg_types):
+        """Check that a call to the named procedure or function in
+        this context, with the given argument types, is legal.
+
+        We start by obtaining the (fully general) type of the
+        procedure being called, and instantiating it so that we
+        can bind any type variables in it.
+        
+        If unification succeeds, we return the (bound) return type
+        of the called procedure.
+
+        """
+        proc_type = self.get_type(proc_name)
+        if not proc_type.is_callable():
+            raise TypingError(self.name + ":" + str(proc_type) + " is not a procedure type")
+        proc_type = proc_type.clone()
+        return_type = proc_type.return_type
+
+        # create a putative type representing the proc we are trying to call
+        putative_type = TypeProc(return_type)
+        for arg_type in arg_types:
+            putative_type.add_arg_type(arg_type)
+
+        logger.info("check_call to '" + proc_name + "' which has type " + str(proc_type))
+        logger.info("putative type is " + str(putative_type))
+
+        # try to unify
+        if proc_type.unify(putative_type):
+            return proc_type.return_type
+        else:
+            raise TypingError(str(proc_type) + " could not unify with " + str(putative_type))
+
+    def new_module(self, module):
+        """Create a new subcontext for a module.
+
+        Given a module AST, return a new subcontext to
+        contain things that cannot be accessed outside the
+        module, such as its module-local variables.  The
+        current context is made the parent of the returned
+        subcontext, so any searches in the subcontext will
+        search the parent if the term is not found.
+
+        """
+        subcontext = TypingContext(self)
+        subcontext.module = module
+        return subcontext
+
+    def get_module(self):
+        if self.module != None:
+            return self.module
+        elif self.parent != None:
+            return self.parent.get_module()
+        else:
+            # XXX this is more of an internal error than a TypingError
+            raise TypingError("get_module: no module in context")
+
+    def new_procedure(self, procedure):
+        """Create a new subcontext for a module.
+
+        Like new_module, but for procedures.
+
+        """
+        subcontext = TypingContext(self)
+        subcontext.procedure = procedure
+        return subcontext
+
+    def get_procedure(self):
+        if self.procedure != None:
+            return self.procedure
+        elif self.parent != None:
+            return self.parent.get_procedure()
+        else:
+            # XXX this is more of an internal error than a TypingError
+            raise TypingError("get_procedure: no procedure in context")
+
+    def global_context(self):
+        if self.parent != None:
+            return self.parent.global_context()
+        else:
+            return self

src/dieter/parser.py

+#!/usr/local/bin/python
+# -*- coding: utf-8 -*-
+
+"""
+parser.py -- parser for the Dieter programming language.
+$Id: parser.py 382 2010-01-28 23:40:43Z cpressey $
+"""
+
+import dieter.ast as ast
+
+class Parser(object):
+    """
+    A recursive-descent parser for Dieter.
+    """
+
+    def __init__(self, scanner):
+        """
+        Creates a new Parser object.  The passed-in scanner is expected
+        to be compatible with a Scanner object.
+        """
+        self.scanner = scanner
+
+    def Dieter(self):
+        program = ast.Program()
+        while self.scanner.token in ["order", "module", "forward"]:
+            if self.scanner.token == "order":
+                ordering = self.Ordering()
+                program.add_ordering(ordering)
+            elif self.scanner.token == "module":
+                module = self.Module()
+                program.add_module(module)
+            elif self.scanner.token == "forward":
+                forward = self.Forward()
+                program.add_forward(forward)
+            else:
+                self.error("expected order, module or forward, found " + token)
+        return program
+
+    def Ordering(self):
+        self.scanner.expect("order")
+        qual1 = self.scanner.grab()
+        self.scanner.expect("<")
+        qual2 = self.scanner.grab()
+        ordering = ast.Ordering(qual1, qual2)
+        return ordering
+
+    def Module(self):
+        self.scanner.expect("module")
+        name = self.scanner.grab()
+        fails = False
+        if self.scanner.token == "fails":
+            self.scanner.expect("fails")
+            fails = True
+        module = ast.Module(name, fails)
+        while self.scanner.token == "var":
+            self.scanner.expect("var")
+            vdecl = self.VarDecl()
+            module.add_local(vdecl)
+        while self.scanner.token == "procedure":
+            pdecl = self.ProcDecl()
+            module.add_proc(pdecl)
+        self.scanner.expect("end")
+        return module
+
+    def Forward(self):
+        self.scanner.expect("forward")
+        name = self.scanner.grab()
+        type_expr = ast.ProcTypeExpr([], None)
+        self.scanner.expect("(")
+        if self.scanner.token != ")":
+            arg_type_expr = self.TypeExpr()  
+            type_expr.add_arg_type_expr(arg_type_expr)
+            while self.scanner.token == ",":
+                self.scanner.expect(",")
+                arg_type_expr = self.TypeExpr()
+                type_expr.add_arg_type_expr(arg_type_expr) 
+        self.scanner.expect(")")
+        self.scanner.expect(":")
+        type_expr.return_type_expr = self.TypeExpr()
+        fwd = ast.FwdDecl(name, type_expr)
+        return fwd
+
+    def VarDecl(self):
+        name = self.scanner.grab()
+        self.scanner.expect(":")
+        type_expr = self.TypeExpr()
+        var = ast.VarDecl(name, type_expr)
+        return var
+
+    def ProcDecl(self):
+        self.scanner.expect("procedure")
+        name = self.scanner.grab()
+        proc = ast.ProcDecl(name)
+        self.scanner.expect("(")
+        if self.scanner.token != ")":
+            arg = self.VarDecl()
+            proc.add_arg(arg)
+            while self.scanner.token == ",":
+                self.scanner.expect(",")
+                arg = self.VarDecl()
+                proc.add_arg(arg)
+        self.scanner.expect(")")
+        self.scanner.expect(":")
+        type_expr = self.TypeExpr()
+        proc.set_return_type_expr(type_expr)
+        while self.scanner.token == "var":
+            self.scanner.expect("var")
+            vdecl = self.VarDecl()
+            proc.add_local(vdecl)
+        stmt = self.Statement()
+        proc.set_body(stmt)
+        return proc
+
+    def Statement(self):
+        stmt = None
+        if self.scanner.token == "begin":
+            stmt = ast.CompoundStatement()
+            self.scanner.expect("begin")
+            while self.scanner.token != "end":
+                step = self.Statement()
+                stmt.add_step(step)
+            self.scanner.expect("end")
+        elif self.scanner.token == "if":
+            self.scanner.expect("if")
+            test = self.Expr()
+            self.scanner.expect("then")
+            then_stmt = self.Statement()
+            else_stmt = None
+            if self.scanner.token == "else":
+                self.scanner.expect("else")
+                else_stmt = self.Statement()
+            stmt = ast.IfStatement(test, then_stmt, else_stmt)
+        elif self.scanner.token == "while":
+            self.scanner.expect("while")
+            test = self.Expr()
+            self.scanner.expect("do")
+            body = self.Statement()
+            stmt = ast.WhileStatement(test, body)
+        elif self.scanner.token == "return":
+            self.scanner.expect("return")
+            if self.scanner.token == "final":
+                self.scanner.expect("final")
+            expr = self.Expr()
+            stmt = ast.ReturnStatement(expr)
+        else:
+            name = self.scanner.grab()
+            if self.scanner.token == "(":
+                self.scanner.expect("(")
+                stmt = ast.CallStatement(name)
+                if self.scanner.token != ")":
+                    expr = self.Expr()
+                    stmt.add_arg(expr)
+                    while self.scanner.token == ",":
+                        self.scanner.expect(",")
+                        expr = self.Expr()
+                        stmt.add_arg(expr)
+                self.scanner.expect(")")
+            else:
+                stmt = ast.AssignStatement(name)
+                if self.scanner.token == "[":
+                    self.scanner.expect("[")
+                    index = self.Expr()
+                    stmt.set_index(index)
+                    self.scanner.expect("]")
+                self.scanner.expect(":=")
+                expr = self.Expr()
+                stmt.set_expr(expr)
+        return stmt
+
+    def Expr(self):
+        expr = None
+        if self.scanner.token == "(":
+            self.scanner.expect("(")
+            expr = self.Expr()
+            self.scanner.expect(")")
+        elif self.scanner.token == "bestow":
+            self.scanner.expect("bestow")
+            name = self.scanner.grab()
+            sub = self.Expr()
+            expr = ast.BestowExpr(name, sub)
+        elif self.scanner.token == "super":
+            self.scanner.expect("super")
+            expr = ast.SuperExpr()
+        elif self.scanner.toktype == "int":
+            value = self.scanner.tokval
+            self.scanner.grab()
+            expr = ast.IntConstExpr(value)
+        elif self.scanner.toktype == "string":
+            value = self.scanner.tokval
+            self.scanner.grab()
+            expr = ast.StringConstExpr(value)
+        else:
+            name = self.scanner.grab()
+            if self.scanner.token == "(":
+                expr = ast.CallExpr(name)
+                self.scanner.expect("(")
+                if self.scanner.token != ")":
+                    sub = self.Expr()
+                    expr.add_arg(sub)
+                    while self.scanner.token == ",":
+                        self.scanner.expect(",")
+                        sub = self.Expr()
+                        expr.add_arg(sub)
+                self.scanner.expect(")")
+            else:
+                expr = ast.VarRefExpr(name)
+                if self.scanner.token == "[":
+                    self.scanner.expect("[")
+                    index = self.Expr()
+                    expr.set_index(index)
+                    self.scanner.expect("]")
+        return expr
+
+    def TypeExpr(self):
+        quals = []
+        # XXX would be better to have 'forward qualifier'
+        while self.scanner.token not in [
+                u"void", u"bool", u"int", u"rat", u"string", u"ref", u"map", u"♥"
+            ]:
+            name = self.scanner.grab()
+            quals.append(name)
+        type_expr = self.BareTypeExpr()
+        for qual in quals:
+            type_expr = ast.QualifiedTypeExpr(qual, type_expr)
+        return type_expr
+
+    def BareTypeExpr(self):
+        token = self.scanner.token
+        if token in ["void", "bool", "int", "rat", "string","ref"]:
+            self.scanner.scan()
+            return ast.PrimitiveTypeExpr(token)
+        elif token == "map":
+            self.scanner.scan()
+            from_type_expr = None
+            if self.scanner.token == "from":
+                self.scanner.expect("from")
+                from_type_expr = self.TypeExpr()
+            self.scanner.expect("to")
+            to_type_expr = self.TypeExpr()
+            return ast.MapTypeExpr(to_type_expr, from_type_expr)
+        elif token == u"♥":
+            self.scanner.scan()
+            name = self.scanner.grab()
+            return ast.TypeVariableExpr(name)
+        else:
+            self.scanner.error("expected valid type expression")

src/dieter/scanner.py

+#!/usr/local/bin/python
+# -*- coding: utf-8 -*-
+
+"""
+scanner.py -- lexical scanner for the Dieter programming language.
+$Id: scanner.py 382 2010-01-28 23:40:43Z cpressey $
+"""
+
+class Scanner(object):
+    """
+    A lexical scanner.
+    """
+
+    def __init__(self, input):
+        """
+        Create a new Scanner object that will consume the given
+        UTF-8 encoded input string.
+        """
+        self._input = unicode(input, 'utf-8')
+        self._token = None
+        self.scan()
+
+    def scan(self):
+        """
+        Consume a token from the input.
+        """
+        self._token = ""
+        if len(self._input) == 0:
+            self.toktype = "eof"
+            return
+        while self._input[0].isspace():
+            self._input = self._input[1:]
+            if len(self._input) == 0:
+                self.toktype = "eof"
+                return
+        if self._input[0].isalpha():
+            while self._input[0].isalnum() or self._input[0] == '_':
+                self._token += self._input[0]
+                self._input = self._input[1:]
+            self.toktype = "ident"
+        elif self._input[0].isdigit():
+            while self._input[0].isdigit():
+                self._token += self._input[0]
+                self._input = self._input[1:]
+            self.toktype = "int"
+            self.tokval = int(self._token)
+        elif self._input[:1] == "\"":
+            st = ""
+            self._input = self._input[1:]
+            while self._input[:1] != "\"":
+                st += self._input[:1]
+                self._input = self._input[1:]
+            self._input = self._input[1:]
+            self.toktype = "string"
+            self.tokval = st
+        elif self._input[:2] == ':=':
+            self._token = ':='
+            self._input = self._input[2:]
+            self.toktype = "op"
+        elif self._input[:2] == '/*':
+            while self._input[:2] != '*/':
+                self._input = self._input[1:]
+            self._input = self._input[2:]
+            return self.scan()
+        elif self._input[:1] == u"♥":
+            self._token = self._input[:1]
+            self._input = self._input[1:]
+            self.toktype = "op"
+        else:
+            self._token = self._input[0]
+            self._input = self._input[1:]
+            self.toktype = "op"
+        #print "scanned: '" + str(self._token) + "'"
+    
+    def get_token(self):
+        """
+        Return the current token as a string.  Using the read-only
+        token property is preferred for readability.
+        """
+        return self._token
+    
+    token = property(get_token)
+
+    def grab(self):
+        """
+        Return the current token as a string, and advance.
+        """
+        t = self._token
+        self.scan()
+        return t
+
+    def expect(self, str):
+        """
+        Expect a certain token to be in the input, and complain
+        if it is not.
+        """
+        if self._token == str:
+            self.scan()
+        else:
+            self.error("expected " + str + ", found " + self._token)
+
+    def error(self, str):
+        """
+        Log the given scan error.
+        """
+        print "error: " + str
+        self.scan()

src/dieter/type.py

+#!/usr/local/bin/python
+# -*- coding: utf-8 -*-
+
+"""
+type.py -- data type structures for the Dieter programming language.
+$Id: type.py 382 2010-01-28 23:40:43Z cpressey $
+"""
+
+import logging
+
+logger = logging.getLogger("type")
+
+
+class Type(object):
+    """
+    A class representing types.  Note that types are *not* AST nodes.
+    After typechecking, every AST node has a type (even if only TypeVoid.)
+    'Simple' types like TypeVoid may be aliased (there need not be multiple
+    instances of TypeVoid; all expressions of type void can point to a
+    single TypeVoid object.)  For this reason it is a good idea for code
+    to treat Type objects as immutable.
+    
+    Note that this class only deals with the structual aspect of types:
+    constructing and unifying them.
+    Type-checking is dealt with in the TypingContext class.
+    """
+
+    def __init__(self):
+        self.qualifiers = []
+
+    def qualify(self, qual):
+        """
+        Returns a new type which is the same as this type except
+        with the given qualifier added to it.
+        """
+        t = self.clone()
+        if qual not in self.qualifiers:
+            t.qualifiers.append(qual)
+        return t
+
+    def unqualify(self, qual):
+        """
+        Returns a new type which is the same as this type except
+        without the given qualifier.
+        """
+        t = self.clone()
+        if qual in t.qualifiers:
+            t.qualifiers.remove(qual)
+        return t
+
+    def has_qualifier(self, qual):
+        """
+        Returns True if this type has the given qualifier.
+        """
+        return qual in self.get_all_qualifiers()
+
+    def get_binding(self):
+        """
+        Returns the concrete type that this type represents.  In the case of
+        actual concrete types, this just returns the same type, but in the case
+        of type variables, the chain of equivalence relations is followed to
+        find the basic concrete type, if any (or None if the variable is unbound.)
+        """
+        return self
+
+    def get_all_qualifiers(self):
+        """
+        Returns all qualifiers on this type.  In the case of concrete types,
+        this is just the set of qualifiers as stored internally, but in the
+        case of type variables, the chain of equivalence relations is followed
+        to collect all qualifiers involved in the binding.
+        """
+        return self.qualifiers
+
+    def can_receive(receptor, provider):
+        """
+        The rule for unification with type qualifiers is this: the qualifiers of
+        the provider must be a superset of the qualifiers of the receptor.
+        
+        A type can receive another type if the other type is at least as qualified
+        as this type.
+        """
+        for qual in receptor.get_all_qualifiers():
+            if not provider.has_qualifier(qual):
+                return False
+        return True
+
+    def is_bound(self):
+        return True
+
+    def isa(self, python_type):
+        """
+        Checks if the type this is bound to is the given type.
+        Crashes on unbound type variables.
+        """
+        return isinstance(self.get_binding(), python_type)
+
+    def is_callable(self):
+        return False
+
+    def __str__(self):
+        """
+        Returns a human-readable string representation of this type.
+        """
+        d = ""
+        for qual in self.qualifiers:
+            d += qual + ' '
+        return d
+
+    def clone(self):
+        """
+        Returns a deep, fresh copy of this type.  Fresh meaning all type
+        variables in the new copy are unbound.
+        
+        The default implementation of this method is appropriate for
+        primitive types -- it just returns another reference to the type,
+        which is safe when the type is immutable, as all primitives are.
+        """
+        return self
+
+    def bestow_qualifiers_onto(self, other):
+        for qual in self.get_all_qualifiers():
+            if not other.has_qualifier(qual):
+                other.qualifiers.append(qual)
+
+    def unify(receptor, provider):
+        """
+        Returns true, and possibly modifies the given types, if this type
+        can be unified with the given type.  By "unify" we mean "make
+        equivalent to by assigning appropriate types to type variables."
+
+        Because these types have special rules regarding type qualifiers,
+        the unify operation is not commutative (as it would usually be).
+        The 'self' type is considered to be the receptor type, whereas the
+        argument is the provider type.  The rule for unification with type
+        qualifiers is this: the qualifiers of the provider must be a
+        superset of the qualifiers of the receptor.
+        """
+        logger.info("unifying " + str(receptor) + " (receptor) with " + str(provider) + " (provider)")
+        if not receptor.can_receive(provider):
+            logger.info("receptor cannot receive provider: unification failed")
+            return False
+        if not provider.is_bound():
+            provider.bind_to(receptor)
+            return True
+        else:
+            return provider.isa(receptor.__class__)
+
+
+class TypeVoid(Type):
+    def __str__(self):
+        return Type.__str__(self) + 'void'
+
+
+class TypeBool(Type):
+    def __str__(self):
+        return Type.__str__(self) + 'bool'
+
+
+class TypeInt(Type):
+    def __str__(self):
+        return Type.__str__(self) + 'int'
+
+
+class TypeRat(Type):
+    def __str__(self):
+        return Type.__str__(self) + 'rat'
+
+
+class TypeString(Type):
+    def __str__(self):
+        return Type.__str__(self) + 'string'
+
+
+class TypeRef(Type):
+    def __str__(self):
+        return Type.__str__(self) + 'ref'
+
+
+# Non-simple types follow.
+
+class TypeMap(Type):
+
+    # NB.  from_type can be None.
+
+    def __init__(self, to_type, from_type):
+        Type.__init__(self)
+        self.to_type = to_type
+        self.from_type = from_type
+
+    def __str__(self):
+        s = Type.__str__(self) + 'map '
+        if self.from_type is not None:
+            s += 'from ' + str(self.from_type)
+        s += ' to ' + str(self.to_type)
+        return s
+
+    def unify(receptor, provider):
+        logger.info("unifying " + str(receptor) + " with " + str(provider))
+        if not receptor.can_receive(provider):
+            logger.info("receptor cannot receive provider: unification failed")
+            return False
+        if not provider.is_bound():
+            provider.bind_to(receptor)
+            return True
+        provider = provider.get_binding()
+        if not (provider.isa(TypeMap)):
+            return False
+        if receptor.from_type is not None:
+            if not receptor.from_type.unify(provider.from_type):
+                return False
+        return receptor.to_type.unify(provider.to_type)
+
+    def clone(self):
+        from_clone = None
+        if self.from_type is not None:
+            from_clone = self.from_type.clone()
+        new_type = TypeMap(self.to_type.clone(), from_clone)
+        self.bestow_qualifiers_onto(new_type)
+        return new_type
+
+
+class TypeProc(Type):
+    def __init__(self, return_type):
+        Type.__init__(self)
+        self.arg_types = []
+        self.return_type = return_type
+
+    def is_callable(self):
+        return True
+
+    def add_arg_type(self, arg_type):
+        self.arg_types.append(arg_type)
+
+    def get_arg_type(self, index):
+        return self.arg_types[index]
+
+    def __str__(self):
+        d = Type.__str__(self) + 'proc('
+        arg_type_strings = []
+        for arg_type in self.arg_types:
+            arg_type_strings.append(str(arg_type))
+        d += ','.join(arg_type_strings) + "): " + str(self.return_type)
+        return d
+
+    def unify(receptor, provider):
+        logger.info("unifying " + str(receptor) + " with " + str(provider))
+        if not receptor.can_receive(provider):
+            logger.info("receptor cannot receive provider: unification failed")
+            return False
+        if not provider.is_bound():
+            provider.bind_to(receptor)
+            return True
+        provider = provider.get_binding()
+        if not provider.isa(TypeProc):
+            return False
+        i = 0
+        for arg_type in receptor.arg_types:
+            if not arg_type.unify(provider.get_arg_type(i)):
+                return False
+            i += 1
+        return receptor.return_type.unify(provider.return_type)
+
+    def clone(self):
+        t = TypeProc(self.return_type.clone())
+        for arg_type in self.arg_types:
+            t.add_arg_type(arg_type.clone())
+        self.bestow_qualifiers_onto(t)
+        return t
+
+
+class TypeVar(Type):
+
+    def __init__(self, name):
+        Type.__init__(self)
+        self.name = name
+        self.bound_to = None
+
+    def __str__(self):
+        return Type.__str__(self) + '*' + self.name
+
+    def __unicode__(self):
+        return Type.__unicode__(self) + u'♥' + self.name
+
+    def is_variable(self):
+        return True
+
+    def is_bound(self):
+        return self.bound_to is not None
+
+    def get_binding(self):
+        if self.bound_to is None:
+            return None
+        if self.bound_to is self:
+            return self
+        return self.bound_to.get_binding()
+        
+    def bind_to(self, target):
+        # Note that when setting the binding for a type variable, we
+        # point to the top of the chain, not the bottom as we probably
+        # normally would in performing disjoint set union in a common
+        # unify.  We do this, even though it is less efficient, in order
+        # to pick up all the type qualifiers that are mentioned along
+        # the unification chain.
+        self.bound_to = target
+
+    def get_all_qualifiers(self):
+        quals = []
+        quals += self.qualifiers
+        type = self
+        while type.bound_to is not None:
+            type = type.bound_to
+            quals += type.qualifiers
+        return quals
+
+    def unify(receptor, provider):
+        logger.info("unifying. receptor:" + str(receptor) + ", provider:" + str(provider))
+        if not receptor.can_receive(provider):
+            logger.info("receptor cannot receive provider: unification failed")
+            return False
+
+        if not receptor.is_bound():
+            receptor.bind_to(provider)
+            return True
+        
+        if not provider.is_bound():
+            provider.bind_to(receptor)
+            return True
+
+        lhs_type = receptor_type.get_binding()
+        rhs_type = provider_type.get_binding()
+        
+        return lhs_type.unify(rhs_type)
+
+    def clone(self):
+        t = TypeVar(self.name)
+        self.bestow_qualifiers_onto(t)
+        return t
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.