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

Second Exercise


Develop a simple interpreter for a language based on strings, pattern matching and guards. The interpreter shall be written in a dynamically typed language like Python and Ruby.

The language

All variables in the language can hold strings (there are no other data types) and have a strict single-assignment property. We distinguish between initialized variables holding a string and empty variables without a value. An empty variable becomes initialized when assigning a string to it. No new value must be assigned to an already initialized variable.

Strings can be composed of string literals and variables. For example, if variable x is initialized with "1", y with "2" and three with "3", then the string "a" x y "b" three expands to "a12b3". As long as any of these variables is empty, the string cannot be expanded. Computations depending on the composed string have to be delayed until all variables occurring in the string are initialized.

Actually, waiting for variables to become initialized is all that we need to coordinate the execution. Waiting allows us to express sequences, alternatives, concurrency and synchronization. It is not necessary to force the execution into a specific sequence.

Strings composed of string literals and variables build also a basis for pattern matching. For example, when matching "a" x "/" y with "abc/de", x is initialized with "bc" and y with "de". Matching is not always uniquely defined. For example, there are many possibilities to match "a" x y with "abc/de". Each of these possibilities is equally correct. Programmers have to take care that it does not matter which of these possibilities is selected.

Proposed language details

A program is a sequence of procedures. It has the following syntax (in EBNF where terminals are in quotes):
    program ::= {procedure}

    procedure ::= string '->' string '{' {guarded_command} '}'

    string ::= variable
	     | string_literal
	     | string string
The string to the left of -> is matched with a string provided on procedure invocation, thereby initializing the variables occurring in the string; they represent formal parameters of the procedure. Programmers have to take care that string_literals in such strings determine the procedure in a sufficient way and clearly separate the formal parameters from each other. The string to the right of -> represents the result. A procedure invocation returns the result as soon as all variables in the string are initialized. The scope of all variables occurring in a procedure is restricted to the procedure.

The body of the procedure contains an unordered set of guarded commands:

    guarded_command ::= {guard ':'} command ';'

    guard ::= string
	    | string '==' string
	    | string '!=' string 
	    | 'else'

    command ::= string '=' string
	      | variable ':=' string
	      | variable [variable] '@=' string
A guarded command in a procedure is executable when

A guard consisting just of a string is satisfied as soon as all variables occurring in it are initialized. In a guard comparing two strings for equality or inequality, variables in the strings have to be initialized before the guard can be satisfied. An else guard defers the execution to the latest possible point in time, see below.

There are several kinds of commands (described here in the same ordering as given as alternatives in the EBNF):

  1. When matching strings using =, variables can become initialized only in the string to the left of =.
  2. In a procedure invocation, the invoked procedure is determined by the string to the right of :=. The result is assigned to the variable to the left of :=. It is an error if there is no matching procedure.
  3. An external invocation lets the operating system execute a command specified by the string immediately following @=. The result of the execution (usually "0" for successful termination and other values for erroneous termination) is bound to the first variable to the left of @=. If there is a second variable to the left of =, this variable is bound to a string containing the complete output written to the standard output stream of the executed command.

Each guarded command in a procedure invocation can be executed at most once because after execution corresponding variables are no longer empty. All executable commands can be executed in parallel. However, if several commands initialize the same variable, at most one of them can be executed. The interpreter has to select any of them (provided that it is executable) and ignore the others.

A procedure returns its result as soon as all variables in the result string are initialized. It is possible that a procedure returns its result before the executions of its commands has terminated. In that case the execution continues after return until no executable command is left. It is possible that a variable in the result string never becomes initialized. It is an error if a variable in a result string is empty although no command in the procedure body is executable anymore. An else guard helps us to avoid that case as shown in the following example:

"max of " a " and " b " and " c -> max {
    ab @= "test " a " -le " b;
    bc @= "test " b " -le " c;
    ab == "0" : bc == "0" : max = c;
    ab == "0" : bc == "1" : max = b;
    ab == "1" : bc == "1" : max = a;
    ab == "1" : bc == "0" : ac @= "test " a " -le " c;
    ac == "0" : max = c;
    ac == "1" : max = a;
    else : max = "error";
In Unix that use of test compares two strings supposed to represent integers. If the first integer is less than or equal to the second integer, the result is "0", and if the first integer is larger than the second one, the result is "1". In an invocation of "max of 5 and -3 and 7", two executions of test run concurrently. If possible, the result values determine the result bound to max. Only in one case we need a further execution of test. However, there is a problem because test will return a different unknown value in the case of an error, maybe "2" if any of the arguments is not an integer. The else guard provides a solution: This guard is satisfied only if all other guarded commands are no longer executable and causes the procedure to return a result.

All the details given above describe an example of a language that you shall develop. Please feel free to change all the details and develop your own language. However, your language must distinguish between initialized and empty variables, variables must have a single assignment property, the execution must be coordinated by waiting for variables to become initialized (supporting concurrency, sequences and alternatives), matching must play an important role, and procedures must be recursively invokable.


Please develop at least one nontrivial program in your language to test the language and its implementation. Such coordination languages have advanced capabilities to deal with concurrency and rather complicated forms of coordination. They make it easy to invoke programs in a similar way as do shell scripts. Your test application(s) shall make use of these capabilities. For example, you can develop a tool to sort files into several directories according to file names, file extensions, file sizes, change dates, etc., and create a protocol telling us where files have moved, thereby using a maximum of parallelism.
      frühere Lehre
         LVAs 2017 W
         LVAs 2017 S
         LVAs 2016 W
         LVAs 2016 S
         LVAs 2015 W
         LVAs 2015 S
               1st Exercise
               2nd Exercise
               3rd Exercise
         LVAs 2014 W
         LVAs 2014 S
         LVAs 2013 W
         LVAs 2013 S
         LVAs 2012 W
         LVAs 2012 S
         LVAs 2011 W
         LVAs 2011 S
         LVAs 2010 W
         LVAs 2010 S
         LVAs 2009 W
         LVAs 2009 S
         LVAs 2008 W
         LVAs 2008 S
         LVAs 2007 W
         LVAs 2007 S
         LVAs 2006 W
         LVAs 2006 S
         LVAs 2005 W
         LVAs 2005 S
         LVAs 2004 W
         LVAs 2004 S
         LVAs 2003 W
previous exercise
next exercise
Faculty of Informatics
Vienna University of Technology
top | HTML 4.01 | Datenschutzerklärung | last update: 2015-05-22 (Puntigam)