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

Second Assignment


Develop an interpreter for a language based on property lists, strings, and concatenation. The interpreter shall be written in a dynamically typed language like Python and Ruby.

The Language

A property list is a list of named properties (playing the role of variables), each associated with a value represented by a further property list (or a block, see below). The value of each property can be changed by assigning a new value. In the same way the property list is extended by assigning a value to a property that did not exist before. When accessing a property that has not been specified yet, we get the empty string "".

An application of the concatenation operator + to two property lists results in a new property list containing the properties of the two operands. In general, if a property of the same name occurs in both operands, the value is taken from the second operand. If an operand is a block, corresponding properties are added by the execution of commands (see below).

A string is a special property list having a sequence of characters beside properties. When concatenating two strings, the character sequence in the resulting string is the concatenation of the character sequences of the arguments. When concatenating a string with a non-string property list, the resulting string has the same character sequence as the string operand. Properties are taken from both arguments as for all applications of +. There are string literals in the usual syntax: "abc 123". Since strings are built-in property lists while all other property lists are defined by programmers, strings contain almost all built-in functionality of the language as properties. Programmers get access to build-in functionality by using properties of string literals.

A block is essentially a sequence of commands that can be used to initialize a new property list. The commands are executed when the block is used as an operand of +. The left-hand side of + is executed first (starting with a new empty property list), the right-hand side afterward (starting with the result of applying the left-hand side). There are several kinds of commands:

Blocks can be used as routines. Formal parameters are accessed as properties, but they are not specified. A routine call is of the form A + B where A is a property list containing a property for each argument, and B is a block where commands use these properties. In A + B + C (or equivalently (A + B) + C) block C is applied to the result of A + B, whereas in A + (B + C) block C is applied to the properties specified by B and the result is concatenated to A.

Proposed Language Details

Here is the proposed syntax of the language in EBNF where terminal symbols are in quotes:
    block      ::=  '{' { command } '}'

    command    ::=  '[' guard ':' { command } ']'
                 |  [ { '*' } name '=' ] expression ';'
                 |  '^' expression ';'

    guard      ::=  expression ( '=' | '#' ) expression [ ',' guard ]

    expression ::= ( string_literal | block | { '*' } name | '(' expression ')' ) { '.' name } [ '+' expression ]
A program is a block. When executing the program, this block is applied to a property list constructed from named command-line arguments.

A guard X = Y is satisfied if X and Y have equal strings, and X # Y is satisfied if X = Y is not satisfied. A guard can be composed of several string comparisons separated by commas; it is satisfied only if each of the string comparisons is satisfied. For program simplicity several commands can depend on the same guard. While = is a comparison operator in a guard, it is an assignment operator in a command: Within a command Y = X; the left-hand side Y specifies a property, and X its new value. A simple command of the form X; computes X, but does not store the resulting value anywhere; it is useful if the computation of X has side effects. A return statement ^X; replaces the current property list with X and terminates the execution of the block.

Each expression belongs to the block determined by the innermost braces surrounding the expression. This is the current block. A simple name used as expression refers to a property of the property list constructed by executing the current block. Blocks can occur within blocks. To refer to a property of an outer block we use *-notation: A name preceded by * refers to a name of the block directly surrounding the current block, a name preceded by ** to the block surrounding the block surrounding the current block, and so on. A name of the form x.y.z (or *x.y.z) refers to a property of name z in a property list referred to by x.y (or *x.y) in the property list referred to by x (or *x). The syntax of commands is restricted such that new values can only be assigned to properties easily visible in the program text, i.e., properties determined without .. For comments we use a Lisp-like style: Everything between an occurrence of % and the end of the same line is a comment. Here is an example of a program with a routine computing the maximum of three numbers:

    max = {  % number a, number b, number c -> number or "error"
        [ c = "" : c = "0"; ]  % by default use "0" if c not specified
        ab = {} + ("test " + a + " -le " + b).syscall;
        [  ab = "1" :
            ac = {} + ("test " + a + " -le " + c).syscall;
	    [ ac = "1" : ^c; ]
            [ ac = "0" : ^a; ]
        ][ ab = "0" :
            ^ { a = *a; b = *c; c = *b; } + *max;
        ^ "error";
    result = { a = "12"; b = "27"; c = "18"; } + max;
    {} + ("echo " + result).syscall;
    {} + ("echo " + ({ a = "-12"; b = "-27"; } + max)).syscall;
Because there is no numerical type in the language, we use strings instead. And because there are no appropriate comparison operators, we invoke foreign programs to perform the comparison. First, we assign a block to the property max. Then, we call max on a property list containing a property for each parameter expected by max (this is a, b and c) and assign the resulting value to result. The Linux command echo x just writes x to the standard output. We invoke this Linux command by calling syscall (a parameter-less block assumed to be built-in in strings) on a string containing the Linux command. The last command also writes the result of a call of max to standard output, in this case without specifying a property for parameter c and without storing the result in a property.

The first guarded command in max assigns "0" to c if c had no value (or the invalid value "") before. We use the Linux command test for comparing integer values. For example test 1 -le 2 gives us the return code "0" (yes, 1 is less than or equal to 2), test 2 -le 1 gives us the return code "1" (no, 2 is not less than or equal to 1), and test a -le b gives us a return code of "2" or larger (inappropriate arguments or another error). The return code of comparing the values of the properties a and b is stored in property ab. Depending on the return code a further comparison is necessary before max can return the correct string as result. A recursive call of max occurs in one case. In this call we have to use *-notation because the corresponding properties belong to outer blocks. If a return code of test signals an error (neither "0" nor "1"), then max returns "error".

Here is another example to show how the property lists can be used to simulate objects:

    error = "0";
    fact = { % number num -> number; set error if something is wrong
        continue = {} + ("test 1 -ge " + num).syscall;
        [  continue = "0" :
            [ {} + ("test 0 = " + num).syscall # "0" :
                *error = "1";
            ^ "1";
        nextnum = { in = *num + "-1"; } + "bc -lq".iosyscall;
        [ nextnum.result = "0" : 
            result = { in = { num = **nextnum.out; } + **fact + "*" + *nextnum.out; } + "bc -lq".iosyscall;
            [ result.result = "0" :
                ^ result.out;
        *error = "2";
        ^ "0";
    value = { num = "5"; } + fact;
    [ error = "0" : { in = "result: " + *value; } + "echo".iosyscall; ]
    [ error # "0" : { in = "error #" + *error; } + "echo".iosyscall; ]
In some sense, error is an object variable accessed in the method fact (in a similar way as character sequences of strings are accessed in syscall). We assume iosyscall to be a further property of string; this block takes the whole contents of an input stream as a parameter. Furthermore, iosyscall probably does not use a return statement. Instead, it just produces a property list (as stored in nextnum or result). The property result accessible through result.result or nextnum.result contains the return code of the Linux command, and the property out the complete standard output. There could also be a property err with the standard error output (not used here). As we see, the boarders between objects and methods are blurred when using property lists.

Built-in functionality is located as properties in strings. We used syscall and iosyscall as examples. Please design and implement your own list of properties that you regard as necessary or useful.

Details given above describe an example of a language you shall develop. Please feel free to change details and develop your own language. However, your language must be based on property lists, strings and guarded commands. It must be able to invoke other programs.


Please develop at least one nontrivial program in your language to test the language and its implementation.
      frühere Lehre
         LVAs 2017 W
         LVAs 2017 S
         LVAs 2016 W
         LVAs 2016 S
               1st Assignment
               2nd Assignment
               3rd Assignment
         LVAs 2015 W
         LVAs 2015 S
         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: 2016-05-20 (Puntigam)