Programmiersprachen – Programming Languages
LVA 185.208, VU, 3 ECTS, 2015 S
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.
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
= matches that to the right,
:= and @= are empty,
=.
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):
=, variables can become initialized only in the string to the left of =.
:=.
The result is assigned to the variable to the left of :=.
It is an error if there is no matching procedure.
@=.
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 @==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.