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

First Assignment

Develop a simulator of a programmable calculator according to the following specification, and write program text to test the calculator as described below. To implement the calculator you can use any language you like, but program text for testing 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, 15 2 3 4+*- is evaluated to 1: First, the four numbers are pushed onto the stack, then the evaluation of + takes 3 and 4 from the top of the stack and pushes the result 7 onto the stack, the evaluation of * takes 2 and 7 from the stack and pushes 14 onto the stack, and finally - takes 15 and 14 from the stack and pushes 1 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 3 and 2, 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:
Command stream:
A stream of integers, blocks and operators to be executed in sequential order. Every character that is not part of an integer or block is regarded to be an operator. When switching on the calculator the command stream is initialized with the contents of register 1 (see below).
Data stack:
This is the stack holding integers and blocks when evaluating expressions in post-fix notation. The stack is empty when switching on the calculator.
Register set:
A set of 32 registers (with indexes 0 to 31), each holding a single integer or block. Registers contain predefined values when switching on the calculator. There are operators for reading and writing registers. Two registers have special meanings:
  • Register 0 is connected to the input and output of the calculator. Each value written to register 0 is displayed on the calculator's screen. The contents of blocks is displayed without surrounding brackets (so that blocks are usable in a similar way as strings), and spaces are automatically inserted between the written values. Every time when reading register 0 we get a block containing the contents of the next input line (terminated by pressing the enter/return key).
  • The predefined value of register 1 (which must be a block) is executed when switching on the calculator, this is, the contents of the block in register 1 (without enclosing brackets) are copied to the command stream before the calculator begins to execute operations.

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

Operations

Always the first element in the command stream gets executed. On execution this element is removed from the command stream and the next element becomes 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 command stream, an integer or block is simply taken from the command 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 not an integer, or if 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: 4 2- and 4 2/ and 4 2% have 2 as result, and 4 2> and 2 4< give 1 (true). An error shall be reported when executing / or % if the top element on 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 immediately a:
If the single argument (top element on the data stack) is a block, then the block is taken from the data stack and its contents (without brackets) are inserted at the begin of the command stream to be executed next. Otherwise this operation has no effect.
Apply later z:
The single argument is taken from the data stack and its content (without brackets if it is a block) is inserted at the end of the command stream to be executed after everything else in the command stream has been executed.
Read register r
takes the top element n from the data stack and pushes the contents of register n onto the data stack. An error is reported if n is not a number between 0 and 31.
Write register w
takes the top element n and the second element x from the data stack and writes x to register n. An error is reported if n is not a number between 0 and 31.
Integer check i:
Checks if the top element on the data stack is an integer (without removing this element from the stack) and pushes a corresponding Boolean value (0 or 1) onto the stack.
Nonempty block check b:
Checks if the top element on the data stack is a nonempty block (without removing this element from the stack) and pushes a corresponding Boolean value (0 or 1) onto the stack.
Stack size s:
Pushes the current number of stack entries onto the stack.
Combine @:
Takes two arguments from the stack, creates a new block from them, and pushes the new block onto the stack. If both arguments are blocks, the new block contains the contents of both blocks. If both arguments are integers, the new block contains these integers. If one argument is a block and the other an integer, the new block contains the contents of the block as well as the integer (keeping the ordering).
Divide block : (colon)
takes the top element (which must be a block) from the stack, takes the first element out of the block, pushes the remaining block onto the stack, and pushes the element taken out of the block (if it is an integer) or a block containing just the element taken out of the block (if the element is not an integer) onto the stack. An error is reported if the argument is not a nonempty block.
Exit x
stops the execution of the calculator.
Any other character in the command stream (including white space)
does nothing.

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 command 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

Please write code for testing only in the language of the calculator. Do not extend the calculator with additional operations. Use registers to provide program code that is supposed to exist when switching on the calculator.

First of all, please provide program code in register 1 that causes the calculator to start with a welcome message and to repeatedly ask for input to be executed (showing stack contents as the results after executions).

To test the calculator write program code (in one of the registers) that expects a number on the stack, determines all prime factors of this number and displays them on the calculator's screen. As an example, for 63 the output should be something like 3 3 7.

Complang
Puntigam
   About Me
   Research
   Lehre
      LVAs 2017 W
      LVAs 2017 S
         PK
         FOOP
         Prog.spr.
            1st Assignment
            2nd Assignment
            3rd Assignment
      frühere Lehre
   Links
Sitemap
Contact
Access:
next
Faculty of Informatics
Vienna University of Technology
top | HTML 4.01 | last update: 2017-05-05 (Puntigam)