Programmiersprachen – Programming Languages
LVA 185.208, VU, 3 ECTS, 2017 S

Second Assignment

Develop an interpreter for a language that operates by manipulating a set of entities (where the elements of the set can be manipulated in arbitrary ordering or in parallel) according to a set of rules. The interpreter shall be written in a dynamically typed language like Python and Ruby.

The Language

Current programming languages are usually based on sequential execution. In the future we expect languages based on computation models not restricted to sequential execution to become more important. For this programming assignment we explore a computation model based on the manipulation of a set.

The computation shall use two sets, a set E of entities to be manipulated (or several sets if there are different kinds of entities), and a set R of rules specifying how entities in E shall be manipulated. Most of the rules are determined by a program, some rules can be fixed in the language definition. The computation model is simple: Select entities from E and a rule r from R where r is applicable to the selected entities, remove the selected entities from E, and (optionally) add further entities to E as specified by r. These steps are repeated again and again (sequentially or in parallel) until no rule in R is applicable to any subset of E.

Please develop an interpreter of a language operating in this way and show that your language is useful by giving simple programming examples in your language. There are no further constraints. Please feel free to find your own application area and design your own language. Be careful to keep the syntax simple and avoid the use of expensive compiler technologies (no lexer, parser, AST, etc. necessary).

An Example Language

Here is the description of a language as an example. If you want, you can implement this language to solve the assignment, but implementing your own language should be preferred.

All data in the example language are possibly open character sequences (unterminated string, stream, ...) consisting of tokens that are separated from each other by white space. This is the syntax in EBNF:

   <program> ::= { <rule> }
      <rule> ::= <head> <body> '.'
      <head> ::= <atom>
      <body> ::= { ':' <goal> }
      <goal> ::= <atom>
               | <pattern> '=' <pattern>
               | '$' <pattern> <pattern> '-' <pattern> <pattern>
      <atom> ::= <name> { <pattern> } '-' { <pattern> }
      <name> ::= <token>
   <pattern> ::= '(' { [ '+' ] <token> } [ '*' <token> ] ')'

<token> is a sequence of characters not containing white space. Special characters used in the syntax (':', '.', '=', '$', '-', '(', '+', '*', ')') as well as '\' occurring in a token must be preceded by '\', e.g. x\$\+ stands for the character sequence x$+.

Within a <pattern>,

<token> (without preceding '+' or '*') stands for a token consisting just of the characters of <token> (as a literal);
'+' <token> is a variable supposed to stand for a single token;
'*' <token> is a variable supposed to stand for a possibly open character sequence.

A pattern specifies a possibly open character sequence consisting of the given tokens (e.g., x or +y) separated by arbitrary white space. With *z at the end, the character sequence is open, and *z stands for the rest of the sequence. The special empty pattern () stands for an empty (no longer open) character sequence.

The scope of a variable (e.g., +y or *z) is the single <rule> where the variable occurs within. Each variable can get a value only once – single assignment. The variable can be initialized or uninitialized. When a pattern contains no uninitialized variable, we call this pattern full. A full pattern specifies a character sequence possibly containing known tokens at the beginning (if specified) and possibly being open (when ending with e.g. *z). This is, for full patterns it is not necessary that the corresponding character sequence is already closed. A pattern containing neither + nor * is always full.

Let a₁,...,a_m and c₁,...,c_n be literal tokens or variables standing for tokens (m,n ≥ 0), and let b and d be variables standing for character sequences. A not necessarily full pattern (a₁ ... a_m) or (a₁ ... a_m b), where b is unitialized, matches a full pattern (c₁ ... c_n) or (c₁ ... c_n d), thereby initializing uninitialized variables in a₁,...,a_m,b, in the following case:

For i=1,...,min(m,n): if a_i is initialized, then a_i and c_i stand for the same token; if a_i is uninitialized, a_i becomes initialized with the token that c_i stands for.
If n > m and there is an uninitialized b, then b becomes initialized with a character sequence constructed from c_m+1 to c_n with white space between the tokens and d at the end (if d is specified).
If m > n and d is specified, then the character sequence in d contains at the begin tokens for all i=n+1,...,m separated by white space such that
- these tokens (in the given order) correspond to a_i where a_i is not an uninitialized variable,
- these tokens are used to initialize a_i where a_i is an uninitialized variable,
and if b is specified, b is initialized with the remainder of the character sequence in d after removing the already used m - n tokens, or otherwise d contains just the m - n already used tokens and then ends.

In all other cases the patterns do not match.

For an execution we need a set G of goals according to <goal>, a set R of rules according to <rule>, and a map V associating values to variables. We repeatedly select an appropriate goal g from G and (if necessary) a corresponding rule r from R, remove g from G, add corresponding new goals g₁,...,g_k to G, and map variables to values in V when variables are initialized, so that

g syntactically corresponds to <atom>, where
- g is of the form x p¹₁ ... p¹_m - p²₁ ... p²_n,
- p¹₁,...,p¹_m are all full (according to V),
- a copy of r (with all variables in r replaced with fresh variables of the same kind not occurring anywhere else to avoid name clashes) is of the form x q¹₁ ... q¹_m - q²₁ ... q²_n : g_n+1 :...: g_k.,
- for i=1,...,m each q¹_i matches p¹_i (possibly introducing associations into V),
- for j=1,...,n each g_j is q²_j = p²_j;
g is of the form q = p where p is full and q matches p (possibly introducing associations into V) and k is 0 (no r needed and no new goals added to G);
g is of the form $p₁ p₂ - p₃ p₄ (causes the character sequence specified by p₁ to be executed in a separate shell using p₂ as standard input stream and p₃ as standard output stream, returning the result of the execution in p₄) where p₁ and p₂ are full, p₁ specifies a closed character sequence, k is 2, g₁ is p₃ = out (out being the standard output stream of the shell) and g₂ is p₄ = res (res being an internal resource to be replaced by the result of the execution after termination).

The word matches in this specification implies that variables become initialized. We have to be careful to use the same value for each occurrence of the same variable and to distinguish between different variables. Especially, we must distinguish between variables belonging to different applications of the same rule. For that reason we replace all variables occurring in a rule with fresh variables when applying a rule. The reason of using goals of the form $p₁ p₂ - p₃ p₄ is simplification: Since we can use all resources of the operating system, it is not necessary to define elementary operations (numbers, arithmetic and logic operations, etc.). When writing programs we need not make use of goals of the form q = p; these goals are used mainly in the execution to postpone the return of results (to the right of -) to a later point of time when these results are known. To start the computation, we take the program as rule set R, an empty mapping V, and a set G usually containing only a single goal (to invoke the rule that starts the computation).

Here is an example of a program in this language that opens all pdf files in the current directory (executing ls *.pdf to list all such files and xpdf ... for each listed file in arbitrary order or in parallel):

    main-:findFiles-(*files):showFiles(*files)-.
    showFiles(+x*x)-:showFile(+x)-:showFiles(*x)-.
    showFiles()-.
    findFiles-(*f):$(ls \*\.pdf)()-(*f)(*x).
    showFile(+f)-:$(xpdf+f)()-(*a)(+b).

To execute the program, we assume G initially to be the set { main- }. Note that +x and *x in line 2 are different variables, and variables of the same name in different lines are different because of different scopes.