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

First Assignment

Exercise

Develop a simulator of a programmable calculator according to the following specification, and write a program to test the calculator as described below. To implement the calculator you can use any language you like, but the test program must be written in the language of the calculator.

How to use the calculator

The calculator uses post-fix notation – first the arguments, then the operator. Arguments are integers and blocks, see below. For example, 5 12+ applies the operator + to the arguments 5 and 12, giving 17 as result. White space between 5 and 12 is necessary to separate the integers from each other.

Post-fix expressions are evaluated using a stack. Arguments are simply pushed onto the stack, operators take arguments from the stack and push results onto the stack. For example, 1 2 3 4+*- is evaluated to 13: First, the four numbers are pushed onto the stack, then the evaluation of + takes 4 and 3 from the top of the stack and pushes the result 7 onto the stack, the evaluation of * takes 7 and 2 from the stack and pushes 14 onto the stack, and finally - takes 14 and 1 from the stack and pushes 13 onto the stack.

Data enclosed in rectangular brackets build blocks. A block is evaluated when applying the operator a to it. For example, [2*] is a block. When evaluating 4 3[2*]a+, first 4, 3 and [2*] are pushed onto the stack, then a takes the block from the stack and causes its contents to be evaluated by pushing 2 onto the stack and applying * to 2 and 3, and finally + adds 4 and 6. Hence [2*]a doubles the integer on top of the stack.

Architecture of the calculator

The calculator consists of the following parts:

Input stream:

A sequential stream of integers, blocks and operators typed into the keyboard (or added during execution, see below). Every character that is not part of an integer or block is regarded to be an operator.

Output stream:

Integers and blocks written to the output stream are displayed on a screen. The contents of blocks is displayed without surrounding brackets (to be usable in a similar way as strings), and spaces are automatically inserted between the written elements.

Data stack:

This is the stack holding data when evaluating expressions in post-fix notation.

For simplification there can be reasonable limits on the sizes of integers, blocks, the data stack and the streams.

Operations

Always the first element in the input stream gets executed. On execution this element is removed from the input stream and causes the next element to become executable. The kind of element determines the operation. Some Operations take arguments which are determined by the topmost elements on the data stack.

Integer or block:

When occurring as first element of the input stream, an integer or block is simply taken from the input stream and pushed onto the data stack.

Arithmetic operator, comparison operator or logical operator (+, -, *, /, %, &, |, =, <, >):

These binary operators have the usual semantics, where % computes the rest of a division, & is the logical AND and | is the logical OR. Each of these operators takes two integers from the data stack and pushes an integer as result onto the data stack. The integer 0 corresponds to false and 1 to true. An error is reported if any of the two topmost elements on the data stack is no integer or an argument of & or | differs from 0 and 1. The comparison operator = is an exception: If = is applied to two equal blocks or two equal integers, then the result is 1, otherwise the result is 0. The ordering of arguments has to be considered for non-associative operations: 2 4- and 2 4/ and 4 2% have 2 as result, and 2 4> and 4 2< give 1 (true). An error shall be reported when executing / or % if the second element from the top of the data stack equals 0.

Negation ~:

This unary operator changes the sign of an integer on the data stack. An error is reported if its argument is not an integer.

Copy c

replaces the top element n of the data stack with a copy of the nth element on the data stack (counted from the top of the stack). An error is reported if n is not a positive number or the stack does not contain a sufficient number of elements.

Delete d

takes the top element n from the data stack and additionally removes the nth element from the data stack (counted from the top of the stack). An error is reported if n is not a positive number or the stack does not contain a sufficient number of elements.

Apply a:

If the single argument is a block, then the block is taken from the data stack and its content is inserted into the input stream to be executed next; the content of the block is divided into elements of the input stream in the same way as if typed on the keyboard. Otherwise this operation has no effect.

Read integer i:

The whole execution is suspended until a complete integer (terminated by any character not being part of an integer) has been typed into the keyboard. This integer is directly pushed onto the data stack. Characters different from digits are ignored until the first digit has been typed.

Read block b:

The whole execution is suspended until a line has been typed into the keyboard. The line content is pushed as a new block onto the data stack. Nothing is written to the input stream.

Write w

takes an argument from the data stack and writes it into the output stream.

Exit x

stops the execution of the calculator.

White space

does nothing.

Any other character in the input stream

causes an error.

If an error occurs, the calculator simulator shall simply stop its execution and report an error message.

Examples

The following examples clarify the use of some operators and introduce specific programming techniques. We specify the state of the calculator by the contents of its data stack (to the left of ^, the top of the stack adjacent to ^) and its input stream (to the right of ^, the first element adjacent to ^). Arrows between state specifications show how the states change by executing operations.

The first example shows how to deal with conditional execution: On the data stack we expect 0 (false) or 1 (true). Depending on this value we want to execute the one or the other block. First we push the block for the false-path [9~] onto the stack, then the one for the true-path [8], and finally we execute [3c4d1+da], the code for conditional execution. The steps show what happens if previously 0 was on the data stack.

    0 ^ [9~][8][3c4d1+da]a
--> 0[9~] ^ [8][3c4d1+da]a
--> 0[9~][8] ^ [3c4d1+da]a
--> 0[9~][8][3c4d1+da] ^ a
--> 0[9~][8] ^ 3c4d1+da
--> 0[9~][8]3 ^ c4d1+da
--> 0[9~][8]0 ^ 4d1+da
--> 0[9~][8]0 4 ^ d1+da
--> [9~][8]0 ^ 1+da
--> [9~][8]0 1 ^ +da
--> [9~][8]1 ^ da
--> [9~] ^ a
--> ^ 9~
--> 9 ^ ~
--> -9 ^

The next example shows recursion in the computation of 3 factorial. For simplification we use A as shorthand for [2c1 3c-1c1=3c[]Ca2d*] and C as shorthand for [3c4d1+da] – see above. Please note that the only purpose of A and C is a simplification to improve readability. In the calculator the blocks occur instead of their shorthands.

    3 ^ A2c3d2ca2d
--> 3A ^ 2c3d2ca2d
--> 3A2 ^ c3d2ca2d
--> 3A3 ^ 3d2ca2d
--> 3A3 3 ^ d2ca2d
--> A3 ^ 2ca2d
--> A3 2 ^ ca2d
--> A3A ^ a2d
--> A3 ^ 2c1 3c-1c1=3c[]Ca2d*2d
--> A3 2 ^ c1 3c-1c1=3c[]Ca2d*2d
--> A3A ^ 1 3c-1c1=3c[]Ca2d*2d
--> A3A1 ^ 3c-1c1=3c[]Ca2d*2d
--> A3A1 3 ^ c-1c1=3c[]Ca2d*2d
--> A3A1 3 ^ -1c1=3c[]Ca2d*2d
--> A3A2 ^ 1c1=3c[]Ca2d*2d
--> A3A2 1 ^ c1=3c[]Ca2d*2d
--> A3A2 2 ^ 1=3c[]Ca2d*2d
--> A3A2 2 1 ^ =3c[]Ca2d*2d
--> A3A2 0 ^ 3c[]Ca2d*2d
--> A3A2 0 3 ^ c[]Ca2d*2d
--> A3A2 0A ^ []Ca2d*2d
--> A3A2 0A[] ^ Ca2d*2d
--> A3A2 0A[]C ^ a2d*2d
...
--> A3A2A ^ a2d*2d
--> A3A2 ^ 2c1 3c-1c1=3c[]Ca2d*2d*2d
--> A3A2 2 ^ c1 3c-1c1=3c[]Ca2d*2d*2d
--> A3A2A ^ 1 3c-1c1=3c[]Ca2d*2d*2d
--> A3A2A1 ^ 3c-1c1=3c[]Ca2d*2d*2d
--> A3A2A1 3 ^ c-1c1=3c[]Ca2d*2d*2d
--> A3A2A1 2 ^ -1c1=3c[]Ca2d*2d*2d
--> A3A2A1 ^ 1c1=3c[]Ca2d*2d*2d
--> A3A2A1 1 ^ c1=3c[]Ca2d*2d*2d
--> A3A2A1 1 ^ 1=3c[]Ca2d*2d*2d
--> A3A2A1 1 1 ^ =3c[]Ca2d*2d*2d
--> A3A2A1 1 ^ 3c[]Ca2d*2d*2d
--> A3A2A1 1 3 ^ c[]Ca2d*2d*2d
--> A3A2A1 1A ^ []Ca2d*2d*2d
--> A3A2A1 1A[] ^ Ca2d*2d*2d
--> A3A2A1 1A[]C ^ a2d*2d*2d
...
--> A3A2A1[] ^ a2d*2d*2d
--> A3A2A1 ^ 2d*2d*2d
--> A3A2A1 2 ^ d*2d*2d
--> A3A2 1 ^ *2d*2d
--> A3A2 ^ 2d*2d
--> A3A2 2 ^ d*2d
--> A3 2 ^ *2d
--> A6 ^ 2d
--> A6 2 ^ d
--> 6 ^

Testing

To test the calculator write an interactive program that repeatedly asks the user for a number as input, determines all prime factors of this number, and writes them to output. As an example, for 63 the output should be something like 3 3 7. This loop terminates if the user asks for the prime factors of 0. The program shall be user-friendly by asking for input and presenting the result in an understandable way.