# PostFix

## Basics

PostFix is a stack-based language. Its only data structure is the array. All objects are immutable. PostFix is inspired by PostScript, Forth, Racket, and NewLisp.

The Hello World program in PostFix is:

≫ "Hello, world!" println

Note that the ≫ just denotes the prompt, i.e., PostFix expects your input here. Do not enter the ≫ in your program.

The program output is:

Hello, world!

A program that adds 1 and 2 is written like this:

≫ 1 2 +

and results in

3

A program that doubles the number that the user enters looks like this:

≫ read-int 2 *

For user input

5

this program computes

10

### Integrated Development Environment (IDE)

You can edit source code and run programs with the Web-based PostFix IDE. With the IDE you can also execute a program step by step and observe the values on the stack and in the current dictionary.

The PostFix IDE has a read-evaluate-print loop (REPL) for trying out individual PostFix commands. We recommend that you try the examples below in the PostFix REPL. The '≫' at the beginning of the lines is the prompt at which the interpreter waits for your input.

The PostFix IDE is available here: PostFix IDE

### Types

Data in PostFix is categorized into different basic types.

• :Obj, the root of the type hierarchy, any value, except nil, is a :Obj
• :Nil with value nil, used to denote “nothing”
• :Bool with values true and false
• :Int, 64-bit signed integer values
• :Flt, 64-bit floating-point values, floating-point literals may not omit a leading zero before the floating point, so 0.123 is allowed, but .123 is not allowed
• :Num, numbers, either :Int or :Flt
• :Str, strings, i.e., sequences of characters, enclosed in “…”
• :Arr, arrays of arbitrary objects, elements of an array may have different types, arrays are written as […]
• :ExeArr, executable arrays of arbitrary objects, elements of an executable array may have different types, executable arrays are written as {…}
• :Params, parameter lists, used with function definitions, lambda expressions, data definitions, or on their own, parameter lists are written as (…)
• :Sym, symbols (names), symbols can be used as names for other objects, symbols are written with a preceding or trailing colon (':'), i.e., :x and x: denote the same symbol

### Execution model

During execution PostFix stores intermediate results on a stack (the “runtime stack”) and in dictionaries. A stack is a data structure that acts like a stack of books. You can push a new book on top of the stack or you can remove the topmost book from the stack to read it. But you cannot easily access a book in the middle of the stack. Pushing a new object on top of the stack is called the push operation. Obtaining (and removing) the topmost book on the stack is called the pop operation. Stacks alone are too restrictive for practical programming languages. This is why PostFix also uses dictionaries. Dictionaries are data structures that allow associating names with objects and retrieving objects by name. The two main operations of dictionaries are putting a name-object pair into the dictionary (and replacing an already existing association of this name to another object) and looking up an object by name (or returning a special value if that name is not present in the dictionary). The entry operation is called put, the lookup operation is called get. The name-object pair is also called a key-value pair.

PostFix programs are stored in text files (ending in “.pf”) or are directly entered into the interpreter. The interpreter reads program text as a stream of characters and groups subsequent characters into tokens (“words”). Tokens are non-whitespace strings. Tokens are delimited by whitespace characters. The set of whitespace characters includes the space character, the tabulator character, linebreak characters, and commas. Commas are treated as whitespace, but you may use them to increase readability. Brackets – (, ), [, ], {, } – are self-delimiting tokens, i.e., they do not require whitespace around them. Tokens are case sensitive. Tokens are used to generate objects, e.g., an integer-number object or a plus-operation object. Objects can be pushed onto the runtime stack, stored in arrays, bound to symbols, or executed. Objects may have an effect on the runtime stack when they are executed.

Parsing steps:

Characters –grouped to–> Tokens –converted to–> Objects –executed–> Stack Effect

Example:

Characters Tokens Objects Stack Effect (when executed)
'1' '2' '3' “123” Int(123) push integer value 123 onto the stack
'1' '2' ' ' '3' ' ' '+' “12” “3” “+” Int(12) Int(3) Plus push 12; push 3; pop 3, pop 12, push 15

Objects are executed as they are encountered. For some types (such as :Int) execution simply means that the object is pushed onto the runtime stack. For other objects the semantics is different. For example, executing the Plus operation means that the two topmost objects are popped from the stack, used as arguments to the Plus operation, and the result is pushed onto the stack.

The only exception is if an executable array {…} is currently being parsed. In this case, any object between {…} is just pushed onto the stack, but not yet executed.

The detailed operation of parsing executable arrays {…} is as follows: When '{' is executed, an ExeArrOpen object is pushed onto the stack as a marker. The objects for the following tokens are just pushed onto the stack, but not yet executed. The execution of these objects is deferred for later. When '}' is encountered, the objects down to the topmost ExeArrOpen object are popped from the stack and collected in an executable array (ExeArr) object, which is then pushed onto the stack. The ExeArr object may then be executed.

The detailed operation of parsing data arrays […] is as follows: When '[' is executed, an ArrOpen object is pushed onto the stack as a marker. The objects for the following tokens are immediately executed as usual. Their execution may result in further objects being pushed onto the stack. When ']' is encountered, the objects down to the topmost ArrOpen object are popped from the stack and collected in an array (Arr) object, which is then pushed onto the stack.

The differences are illustrated by the following examples: { 1 2 + } vs. [ 1 2 + ]. For convenience the stack is rotated 90° clockwise, i.e., the rightmost element is the top of the stack.

next token stack
“{” ExeArrOpen
“1” ExeArrOpen Int(1)
“2” ExeArrOpen Int(1) Int(2)
“+” ExeArrOpen Int(1) Int(2) Plus
“}” ExeArr(Int(1) Int(2) Plus)

The result is an executable array with three elements.

next token stack
“[” ArrOpen
“1” ArrOpen Int(1)
“2” ArrOpen Int(1) Int(2)
“+” ArrOpen Int(3)
“]” Arr(Int(3))

The result is a data array with one element.

The difference is that in the data array […] the Plus operation is immediately executed, whereas in the executable array {…} the Plus operation is not executed yet, but just pushed onto the stack.

## Arithmetics

Arithmetic operations operate on numbers. PostFix uses postfix notation – rather than the traditional infix notation – to allow for the simple execution model described above. PostFix uses 64-bit signed integers and 64-bit floating-point numbers. For the computer, integer numbers and floating-point numbers are different things. Integer numbers (in a limited range) can be represented exactly in the computer, whereas not all real numbers (not even all real numbers in a limited range) can be represented as floating-point numbers. (The term real number refers to the mathematical concept, whereas the term floating-point number refers to a particular representation in computer memory.) Moreover, operations on integer values are typically more efficient than floating-point operations.

Arithmetic operations in PostFix try their best not to discard information. For example, if an integer number and a floating-point number are added, the integer number is first converted to a floating-point number and the result will be a floating-point number. If the division operator (/) processes two integer operands the result will be a floating-point number, since otherwise information would be potentially be discarded. If you are just interested in the integral part of the division, then use the integer division (i/) operator. Examples are given below.

The traditional infix expression 1 + 2 translates into

≫ 1 2 +

and evaluates to

3
≫ 2 3 *
6
≫ 3 2 /
1.5
≫ 3 2 i/     # integer division
1
≫ 3 2 mod    # modulo function, i.e., rest of a division
1

# starts a comment to the end of the line, the comment does not have an effect on the execution

#<
This is a multiline comment.

It is useful to comment out parts of the program that
should not be executed or to provide documentation.
>#

Integer numbers can be converted to floating-point numbers, and vice versa, like this:

≫ clear                # clear empties the runtime stack

≫ 123 type             # 123 is an integer number (the type operations tells us the type of its operand)
:Int
≫ clear 123.0 type     # 123.0 is a floating-point number
:Flt
≫ clear 123 flt        # convert integer number 123 to floatint-point number 123.0
123.0
≫ clear 123.123 int    # convert floating-point number 123.123 to integer number 123
123
≫ clear 123.9 int      # the conversion just truncates the digits after the decimal point
123
≫ clear 123.5 round    # rounding to the nearest integer number
124

The IDE helps you in executing PostFix code step-by-step. Simply right-click the token before you wish the program to stop. A red dot appears before the token, at which execution will halt. Try step-by-step execution using the following example.

clear 1 1 + 2 + 3 4 5 + + +

Exercise: What is the corresponding infix expression?

Exercise: Transform 2 + 3 * (4 - 5) into a PostFix expression and let PostFix compute its result.

## Booleans

PostFix also operates on truth values (Booleans).

### Logical operators

or, and, and not are logical operators, which operate on truth values.

≫ true true or
true
≫ true false or
true
≫ false true or
true
≫ false false or
false

≫ true true and
true
≫ true false and
false
≫ false true and
false
≫ false false and
false

≫ true not
false
≫ false not
true

### Short-circuit logical operators

The operators and and or expect either two boolean operands or a single array with an arbitrary number of operands. The array may be a data array or an executable array. This latter form may be used for “short-circuit and” and “short-circuit or”: For and, if any of the operands in the array evaluates to false, the result is false. For or, if any of the operands in the array evaluates to true, the result is true. The array elements are evaluated in turn, starting with the first, but only as many as required to determine the overall result. The first element that evaluates to false (for and) or true (for or), respectively, determines the result. The further operands do not have to be examined.

{true false "this is never reached"} and     # the first false stops further evaluation
{false true "this is never reached"} or      # the first true stops further evaluation
[{false not} {1 1 +  2 =} {3 2 >}] and       # true

### Relational and equality operators

All of the relational and equality operators yield boolean results:

1 1 =     # true
1 2 =     # false
1 1 !=	  # false
1 2 !=    # true
1 2 <     # true
2 1 >     # true
1 1 <=	  # true
1 1 >=	  # true

1 2 + 3 =            # true
0.1 0.2 + 0.3 =      # false!

"hello" "hello" =    # true
"hello" "world" !=   # true
"Alice" "Bob" <      # true

## Strings

Strings are sequences of characters. Two strings may be concatenated (+), the length of a string may be computed (length), another data type may be converted to a string (str), and the character at a specific index may be returned from a string (get). PostFix does not have a data type for characters. A character is just its Unicode integer value.

≫ clear "what a" " lovely" + " day" +   # concatenating strings
"what a lovely day"
≫ clear "abc" length        # number of characters in a string
3
≫ clear "abc" 0 get         # get the first character of the string
"a"
≫ clear "abc" .0            # shorthand: .0 is equivalent to 0 get
"a"
≫ clear 123 str             # convert integer to string
"123"                       # strings are written surrounded by "..."
≫ clear "abc" length 20 +   # "abc" length => 3, 3 20 + => 23
23

## Naming Things

In PostFix you can give names to objects. Sometimes it is easier to access an object by name (that you are free to invent) rather than by its position on the stack. PostFix does not distinguish between constants and variables, but by convention, names that are not intended to be reassigned during program execution (constants) are written in uppercase letters, whereas names that are intended to get reassigned (variables) are written in lowercase letters. By convention, multipart names are segmented-by-dashes.

The exclamation mark is used to give a name to an object. The exclamation mark is the assignment operator (it assigns an object to a name). The name without the exclamation mark retrieves the currently associated object.

# define variables
3 x!    # give the name x to the value 3
4 y!    # give the name y to the value 4
# use variables
x       # lookup the value associated with x and put it on the runtime stack
y       # lookup the value associated with y and put it on the runtime stack
+       # add the two topmost objects on the runtime stack (3 and 4)
x 10 +  # 3 10 + => 13
x y *   # 3 4 * => 12

# define constants
100 WIDTH!
WIDTH 2 i/ WIDTH/2!     # 100 2 i/ => 50 WIDTH/2! (the '/' character is part of the name)
# use constants
WIDTH
WIDTH/2

There is an alternative syntax for giving a name to an object, which is sometimes easier to read:

x: 3 !
y: 4 !
WIDTH: 100 !
WIDTH/2: WIDTH 2 i/ !

In this second variant the exclamation mark is surrounded by whitespace (not attached to a name) and the name (rather than the object to name) comes first. The name begins or ends with a colon (':') to tell PostFix that this is just a name and that PostFix should not try to look up a value for this name (there is no such association in the dictionary yet). The construct x: is denoted as a symbol. The ! (assignment) operator expects two operands on the stack: The symbol (first) and the object (second). When the ! operator is executed it pops those two operands from the stack and enters the association (name, value), e.g., (x: 3, y: 4, etc.) into the dictionary. Using the name later without the colon references the associated value, i.e., the value is looked up and pushed onto the stack.

## Conditionals

The execution of certain program parts may depend on a condition. PostFix has if and cond for conditionally executing executable arrays.

### if

≫ 2000 z!
≫ z 1000 > { "large" } { "small" } if
"large"

The condition is true (z > 1000), so execute the first executable array { “large” } but not the second { “small” }. The result of executing if is the string “large”.

≫ 200 z!
≫ z 1000 > { "large" } { "small" } if
"small"

The condition (z > 1000) is false, so execute the second executable array { “small” } but not the first { “large” }. Now, the result of executing if is the string “small”.

The detailed execution of condition then-part else-part if is as follows. if pops its three operands from the stack: (1) the boolean condition (i.e., true or false), (2) the then-part, which has to be an executable array {…}, and (3) the else-part, which also has to be an executable array {…}. Depending on the condition either the then-part or the else-part gets executed.

### if without else

Sometimes the else-part is not necessary. In such cases, you may use if without the else-part:

≫ score 1000 > { "explode" println } if

If the score is larger than 1000, print “explode”, otherwise do nothing.

### cond

cond is a general, but also more complex conditional. It allows to distinguish between an arbitrary number of conditions.

10 age!
{
{ age 3 <= } { "Toddler" }
{ age 13 <= } { "Child" }
{ age 18 < } { "Teenager" }
{ true } { "Adult" }
} cond

cond expects a single array on the runtime stack, which contains an arbitrary number of condition-action pairs. cond tries each condition in sequence from first to last until it finds one that evaluates to true. It then executes the corresponding action. The conditions after the first matching one are not tested. If you want a default action that should get executed when none of the other conditions match, simply use { true } as the last condition, as in the example above. This is comparable to the else-part of if.

In the above example, age is bound to value 10, so the first condition { age 3 <= } is false and the first action { "Toddler" } is skipped. The second condition { age 13 < = } is true, so the second action { "Child" } is executed, which concludes the execution of cond with value “Child”.

An if can be converted in an equivalent cond, but not vice versa (because if only handles two mutually exclusive cases).

z 1000 > { "large" } { "small" } if
# is equivalent to
{ { z 1000 > } { "large" } { true } { "small" } } cond

By the way: Line breaks and indentations do not have a semantic meaning in PostFix. Try to optimize the readability in your source code by inserting line breaks and indentations. The previous cond should have been written onto multiple lines, with one condition-action pair on each line.

## Functions

Functions are arguably one of the most important abstraction mechanism in programming. Functions involve giving a name to a piece of code such that it can be reused as often as needed, rather than specifying each step of the function anew. Moreover, functions typically specify what input they expect to do their work and what kind of result they produce.

An executable array can be given a name such that it can be applied to data later on. This is not quite a function yet, because there is no specification of the required parameters or return value.

≫ { 1 + } f!    # Executable array { 1 + } is given the name f.
# The stack is now empty.
≫ 10 f          # The executable array is referenced...
11              # processes its argument (10) and produces result 11.
≫ f             # The executable array is referenced again...
12              # processes its argument (11) and produces result 12.

Let's see what happens step by step. Parsing the character sequence { 1 + } results in a two-element executable array on the stack: ExeArr(1 +). f! gives a name to this executable array and stores it in the dictionary. The stack is now empty. Executing 10 f leads to the following sequence of stack states: 10 → 10 1 → 11. When the parser encounters reference f it looks up its associated value and executes it. Executing the executable array involves executing 1 (which just means pushing 1) and executing + (which pops two values and pushes the result). Referencing f again leads to the same steps, but now a different argument (11) is on the stack. The stack states are: 11 → 11 1 → 12. The following table provides an overview of these steps.

Tokens Stack Dictionary Comment
{ 1 + } { 1 + } Push executable array on the stack
f! f → { 1 + } Enter executable array into dictionary
10 10 f → { 1 + } Push 10
f 10 f → { 1 + } Lookup f, execute array
1 10 1 f → { 1 + } Push 1
+ 11 f → { 1 + } Execute +
f 11 f → { 1 + } Lookup f, execute array
1 11 1 f → { 1 + } Push 1
+ 12 f → { 1 + } Execute +

As a second example let's write an executable array that squares its argument, i.e., that computes $f\left(x\right)={x}^{2}=x\ast x$$f(x) = x^2 = x * x$. The * operator expects two numbers on the stack. So if we want to multiply $x$$x$ by itself, then $x$$x$ has to be on the stack twice. Either the caller has to put $x$$x$ on the stack twice (which is inconvenient) or the executable array has to duplicate $x$$x$. PostFix's dup operator duplicates the topmost value on the stack.

≫ { dup * } f!  # Associate name f with this executable array.
# The stack is now empty.
≫ 3 f           # Duplicate the topmost value on the stack and multiply it with itself.
9               # The result.

The following table shows step by step what happens:

Tokens Stack Dictionary Comment
{ dup * } { dup * } Push executable array on the stack
f! f → { dup * } Enter executable array into dictionary
3 3 f → { dup * } Push 3
f 3 f → { dup * } Lookup f, execute array
dup 3 3 f → { dup * } Execute dup
* 9 f → { dup * } Execute *

It is also possible to define variables in an executable array. So this could be rewritten as:

≫ { x! x x * } f!
≫ 3 f
9

Again step by step:

Tokens Stack Dictionary Comment
{ x! x x * } { x! x x * } Push executable array on the stack
f! f → { x! x x * } Enter executable array into dictionary
3 3 f → { x! x x * } Push 3
f 3 f → { x! x x * } Lookup f, execute array
x! f → { x! x x * }, x → 3 Store argument in dictionary
x 3 f → { x! x x * }, x → 3 Lookup x
x 3 3 f → { x! x x * }, x → 3 Lookup x, again
* 9 f → { x! x x * }, x → 3 Execute *

The only downside is that x is entered in the only dictionary we have right now, which may lead to the problem of unintentionally changing a variable:

100 x!              # set x to 100
x println           # output: 100 (println prints its argument and then prints a line break)
{ x! x x * } f!     # set f to { x! x x * }
3 f                 # executing f changes x to 3
x println           # output: 3
Tokens Stack Dictionary Comment
100 100
x! x → 100 Put x → 100 into dictionary
x 100 x → 100 Reference (execute) x
println x → 100 Print (and pop) the topmost value on the stack
{ x! x x * } { x! x x * } x → 100 Push executable array onto stack
f! x → 100, f → { x! x x * } Put into dictionary
3 3 x → 100, f → { x! x x * } Push 3 onto stack
f 3 x → 100, f → { x! x x * } Execute array
x! x → 3, f → { x! x x * } Put into dictionary, replace 100
x x 3 3 x → 3, f → { x! x x * } Look up value of x in dictionary, twice
* 9 x → 3, f → { x! x x * } Execute *
x 9 3 x → 3, f → { x! x x * } Look up value of x in dictionary
println 9 x → 3, f → { x! x x * } Output 3

### Local variables

In the previous example x was assigned to the value 100. In the executable array x is reassigned to the value 3. This change is later visible outside of the executable array. To prevent this, we can provide the executable array with its own local dictionary so that any variables set in the executable array are entered in this local dictionary. Such a local variable lives in the local dictionary of the executable array and is independent of any variable of the same name outside of that executable array. To provide an executable array with its own dictionary, use the lam operator. (lam stands for lambda, more on this later.) The lam operator creates an independent copy of the current dictionary and adds it to the executable array. Any changes to the copy do not affect the original dictionary. Whenever the executable array is executed, its own local dictionary becomes the current dictionary. The following example illustrates this idea.

100 x!              # set x to 100
x println           # output: 100
{ x! x x * } lam f! # the lam operator adds a local dictionary to the executable array
3 f                 # executing f changes x to 3 (but only in the local dictionary)
x println           # output: 100
Tokens Stack Current Dictionary Comment
100 100 Push 100 onto stack, there is one empty dictionary
x! x→100 Put x → 100 into dictionary
x 100 x→100 Reference (execute) x
println x→100 Print (and pop) the topmost value on the stack
{ x! x x * } { x! x x * } x→100 Push executable array on the stack
lam {! x! x x * } x→100 Add a local dictionary to the executable array, which is a copy of the current dictionary, {!…} denotes an executable array with its own local dictionary
f! x → 100, f → {! x! x x * } enter f → {!…} into the current dictionary
x → 100, f → { x! x x * } lam {!…} and {…} lam are equivalent ways of writing an executable array with a local dictionary
3 3 x → 100, f → { x! x x * } lam Push 3 onto stack
f 3 x → 100 Reference (execute) f, f's local dictionary becomes the current dictionary
x! x → 3 Store x → 3 in the current dictionary
x x 3 3 x → 3 Reference (execute) x twice
* 9 x → 3 Replace the two top values on the stack with their product
9 x → 100, f → { x! x x * } lam Return from f, the outer dictionary is restored as the current dictionary
x 9 100 x → 100, f → { x! x x * } lam Reference (execute) x
println 9 x → 100, f → { x! x x * } lam Print (and pop) the topmost value on the stack

The expression {…} lam f! may be abbreviated to: f: {…} fun. (One difference between these to variants is that fun puts the function in the local dictionary as well, which is relevant for recursive functions.)

100 x!              # set x to 100
x println           # output: 100
f: { x! x x * } fun # set f to { x! x x * } ({...} now has its own local dictionary)
3 f                 # executing f changes x to 3 (but only in local dictionary)
x println           # output: 100

In this way we can now define local names without worrying that an outer variable will be affected. A function can only return its results on the stack. It cannot change values in outer dictionaries.

Conceptually, there is a stack of dictionaries. Initially there is a global dictionary. When f is executed its local dictionary is pushed on the top of the dictionary stack and becomes current dictionary. When the execution of f ends it is popped from the dictionary stack. New key-value pairs are always entered in the current dictionary, i.e., the one on the top of the stack.

When lam or fun are executed, the current dictionary is copied and stored with the executable array. lam and fun create a “snapshot” of the current environment – i.e., the set of currently visible key-value mappings – and stores it together with the executable array. All key-value mappings that are already defined are visible locally. The next example illustrates this latter point.

7 x!
f: { y! x y * 1 x! x y * } fun
3 f

Variable x is visible in the executable array.

Tokens Stack Current Dictionary Comment
7 7 Push 7 onto stack, there is one empty dictionary
x! x→7 Put x → 7 into dictionary
f: {…} f: {…} x → 7 Push name (symbol) f and executable array onto stack
fun x → 7, f → {…} lam Define function: Pop function name and executable array, add local dictionary, store f → {…} lam
3 3 x → 7, f → {…} lam Push 3 onto stack
f 3 x → 7 Reference (execute) f: f's local dictionary becomes the current dictionary
y! x → 7, y → 3 Store y → 3 in the current dictionary
x 7 x → 7, y → 3 Reference (execute) x
y 7 3 x → 7, y → 3 Reference (execute) y
* 21 x → 7, y → 3 Replace the two top values on the stack with their product
1 21 1 x → 7, y → 3 Push 1 onto stack
x! 21 x → 1, y → 3 Reassign x → 1 in current dictionary
x y 21 1 3 x → 1, y → 3 Reference x and y
* 21 3 x → 1, y → 3 Reference (execute) *
21 3 x → 7, f → {…} lam Return from f, restore the outer dictionary

### Parameter lists

Let's write a function that returns the difference between its two arguments. Let's call it diff.

diff: { x! y!
x y -
} fun

≫ 1 2 diff
1

When executing 1 2 diff the result surprisingly is 1 and not -1. The reason is that the argument that was provided last (2) is on the top of the stack and will get assigned to parameter x and the first argument (1) will get assigned to parameter y, so we have x → 2 and y → 1. To let x name the first and y name the second argument we would have to reverse the order of the assignments:

diff: { y! x!
x y -
} fun

≫ 1 2 diff
-1

Executing 1 2 diff now results in the expected -1, because we have y → 2 and x → 1.

As reversing the variables in this way is not intuitive, PostFix offers parameter lists. They are written as (…). The following is equivalent to the previous example.

diff: (x y) {
x y -
} fun

Parameter lists can also state the expected types of the arguments. Here, both x and y are expected to be numbers:

diff: (x :Num y :Num) {
x y -
} fun

Moreover, the type of the return value(s) may be specified. Here, the return value is defined to be a number. So overall, this parameter list says that diff takes two numbers and returns a number.

diff: (x :Num y :Num -> :Num) {
x y -
} fun

To clarify which parameter goes with which type, you may insert a comma. As stated above, commas are treated as whitespace but may be used to increase readability.

diff: (x :Num, y :Num -> :Num) {
x y -
} fun

Note that the type name follows the parameter name. Within parameter lists parameter names are not treated as references (i.e., no dictionary lookup occurs), even though the colon (:) is missing.

If parameter types are specified, it is an error if the argument types do not match the declared parameter types:

≫ 1 "hello" diff
1 "hello" (Error: Parameter list expects :Num, but found :Str)

Errors are simply objects with an informative message that are pushed onto the stack. Further program execution is suspended if an error is pushed onto the stack.

If return types are specified, it is an error if the type of the actually returned value(s) do(es) not match the declared type(s):

diff: (x :Num y :Num -> :Str) {
x y -
} fun

≫ 1 2 diff
-1 (Error: Return list expects :Str, but found :Int)

Moreover, it is an error if the function puts more or less stuff on the stack than is declared in the return list:

emphasize: (s :Str -> :Str) {
s "!" +
"and something else"
} fun

≫ "hello" emphasize
"hello!" "and something else" (Error: The function is expected to return 1 element, but returns 2 elements)

emphasize: (s :Str -> ) {
s "!" +
} fun

≫ "hello" emphasize
"hello!" (Error: The function is expected to return 0 elements, but returns 1 element)

If we really intend to return two strings, we may declare the return list like this:

emphasize: (s :Str -> :Str :Str) {
s "!" +
"and something else"
} fun

≫ "hello" emphasize
"hello!" "and something else"

Parameter lists may also be used independently of functions for assigning multiple variables at once in the order in which they appear on the stack:

≫ 1 2 3 (a b c)
1 2 3 ( a :Obj b :Obj c :Obj )      # No types specified, PostFix assumes the most general type :Obj
≫ popv                              # Pop values from stack and name them as specified by the parameter list.
# The stack is now empty.
≫ a b c                             # Referencing by name...
1 2 3                               # puts the associated values on the stack.

### Example functions

Some example functions follow. They illustrate particular details.

#### dist

dist computes the Euclidean distance of a 2D point from the origin of the coordinate system.

dist: (x y) {
x x * y y * + sqrt              # sqrt computes the square root of a number
} fun

≫ 3 4 dist
5.0

# is equivalent to:

dist: { y! x!
x x * y y * + sqrt
} fun

≫ 3 4 dist
5.0

# which in turn is equivalent to:

dist: {
dup *           # Duplicate the topmost element and multiply with itself.
swap dup *      # Swap two topmost elements, duplicate, and multiply with itself.
+ sqrt          # Add two topmost elements and take the square root.
} !                 # Note the "!" (no local dictionary) rather than "fun" (local dictionary)

≫ 3 4 dist
5.0

The latter variant is particularly hard to read but avoids a local dictionary and variables. Understanding how it works requires hard mental operations and is best shown step by step:

Tokens Stack Comment
3 4 3 4 put arguments on the stack
dist 3 4 reference (execute) executable array
dup 3 4 4 duplicate topmost element
* 3 16 multiply with itself
swap 16 3 swap two topmost elements
dup 16 3 3 duplicate topmost element
* 16 9 multiply with itself
+ 25 add two topmost elements
sqrt 5.0 take square root

#### Exercise

Define the function cube-volume, which accepts the length of the side of a cube and computes its volume. Write one variant as a function with side as its local variable (and defined with fun) and one variant as an executable array without variables (and defined with !). Call cube-volume with a few sample side lengths.

#### rectangle-classify

We are interested in a function that classifies rectangles as “tall”, “wide”, or “square”, depending on whether they are higher than wide, wider than high, or have the same width and height. The function has the parameters width and height.

rectangle-classify: (width height) {
{
{ height width > } { "tall" }
{ width height > } { "wide" }
{ true } { "square" }
} cond
} fun

The combination of cond and fun can be abbreviated to cond-fun:

rectangle-classify: (width height) {
{ height width > } { "tall" }
{ width height > } { "wide" }
{ true } { "square" }
} cond-fun

≫ 20 30 rectangle-classify
"tall"
≫ 30 20 rectangle-classify
"tall" "wide"
≫ 10 10 rectangle-classify
"tall" "wide" "square"

To test a function we may call it with a few test values and observe if the output is as we expect. However, it is even better to be able to write tests and keep them in the code (potentially in a separate test module). This leads us to the next topic.

## Tests

The test=, test~=, and test-stats operators allow writing down tests, comparing actual results to expected results, and showing test statistics. Here are some test cases for the previous example. Given the arguments 20 and 30 we expect the result “tall”:

20 30 rectangle-classify  "tall"  test=

Given the arguments 30 and 20 we expect the result “wide”:

30 20 rectangle-classify  "wide"  test=

And given the arguments 10 and 10 we expect the result “square”:

10 10 rectangle-classify  "square"  test=

PostFix tells us how many tests passed, how many failed, and how many were tried. If a test fails, it tells us what went wrong:

≫ 20 30 rectangle-classify  "tall"  test=
≫ 30 20 rectangle-classify  "wide"  test=
≫ 10 10 rectangle-classify  "square"  test=
≫ test-stats
All 3 tests passed!

Let's construct a failing test:

≫ 20 30 rectangle-classify  "tall"  test=
≫ 30 20 rectangle-classify  "wide"  test=
≫ 10 10 rectangle-classify  "square"  test=
≫ 10 10 rectangle-classify  "hello"  test=
≫ test-stats
REPL, line 1: Actual value "square" differs from expected value "hello".
1 of 4 tests failed.

The precision of floating-point values as represented in PostFix is limited. For this reason tests that involve floating-point values should not test for equality but check whether a value is within a predefined tolerance range. This is the domain of the test~= operator, which tests for approximate equality and is illustrated in the next example.

We'd like to define a function cm→inch, which accepts a length in cm and computes the corresponding length in inch (1 inch corresponds to 2.54 cm). We are satisfied if our implementation produces values within $±{10}^{-10}$$\pm 10^{-10}$ of the expected result. This is formulated as follows:

cm->inch: (cm) {
cm 2.54 /
} fun

2.54 cm->inch 1.00 1e-10 test~=
5.08 cm->inch 2.00 1e-10 test~=
test-stats

test~= takes three parameters: the actual result, the expected result, and the allowed tolerance.

Output:

Both tests passed!

## Loops

PostFix has a general loop as well as for and fori loops that iterate over ranges and arrays.

### loop

The general loop operator takes an executable array as its argument and repeatedly executes it until a break or breakif operator is encountered.

Let's write a loop that produces the multiples of some integer number:

5 x!
1 i!
{   i 10 > { break } if     # exit from the loop if the condition is true
i x * println           # output i * x
i 1 + i!                # increase i
} loop

Output:

5
10
15
20
25
30
35
40
45
50

condition { break } if may be abbreviated to condition breakif:

5 x!
1 i!
{   i 10 > breakif      # exit from the loop if the condition is true
i x * println       # output i * x
i 1 + i!            # increase i
} loop

The break and breakif operators may be placed anywhere in the loop. There may also be multiple of these operators in a single loop.

### for over ranges

Because it is so common to iterate over integer ranges, there is a special loop for this task: the for loop.

The example from above may be written more succinctly as:

5 x!
1 11 {
x * println
} for

For expects three parameters: (1) the lower bound of the integer range (inclusive), (2) the upper bound of the integer range (exclusive), and (3) the loop body (an executable array):

lower-bound upper-bound body for

The current iteration value is put on the stack before each execution of the loop. In the example this value is then processed by the * operator. The simplest possible for-loop with an empty body illustrates this:

≫ 1 11 {} for
1 2 3 4 5 6 7 8 9 10

The empty loop body simply leaves the produced iteration values on the stack. Of course, the iteration value may also be assigned to a variable:

100 i!
5 x!
1 11 { i!           # pop iteration index from stack and put in dictionary
i x * println
} for
i println           # output: 10 (from last loop iteration), not 100

The loop body is an executable array without a local dictionary. So the definition of i may change a variable of the same name outside the loop body. To prevent this we can provide the executable array with a local dictionary by adding the lam operator after the loop body like this:

100 i!
5 x!
1 11 { i!           # pop iteration index from stack and put in dictionary
i x * println
} lam for           # note the lam :-) (the executable array gets its own dictionary)
i println           # output: 100 (as defined initially)

lam actually defines an anonymous function – a function without a name – so we might even supply a parameter list:

100 i!
5 x!
1 11 (i) {          # note the parameter list (i)
i x * println
} lam for           # note the lam
i println           # output: 100 (as defined initially)

lam takes either one or two parameters: The function body only (an executable array) or a parameter list followed by the function body:

• body lam
• argument-list body lam

Loops may be nested:

1 5 { row!
1 10 { column!
row print  "," print  column print  " " print
} for
"" println
} for

Output:

1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9
2,1 2,2 2,3 2,4 2,5 2,6 2,7 2,8 2,9
3,1 3,2 3,3 3,4 3,5 3,6 3,7 3,8 3,9
4,1 4,2 4,3 4,4 4,5 4,6 4,7 4,8 4,9 

### for over arrays

In addition to iterating over integer ranges for may also iterate over the elements of an array and process each element in turn.

#### map

Transforming each element of an array individually:

≫ [10 20 30] a!
≫ a { println } for             # print each element of the array
10
20
30
≫ [ a { 1 + } for ]             # add 1 to each element, put the result in a new array
[ 11 21 31 ]
≫ clear [ a { dup } for ]       # duplicate each element, put result in new array
[ 10 10 20 20 30 30 ]
≫ clear [ a { dup * } for ]     # square each element, put result in new array
[ 100 400 900 ]
≫ clear [ a { sqrt } for ]      # take the square root of each element, put result in new array
[ 3.1622776601683795 4.47213595499958 5.477225575051661 ]

≫ clear
≫ ["peanut sauce" "rice" "vegetables"] a!
≫ make-question: (s) { s "?" + } fun
≫ [a { make-question } for]
[ "peanut sauce?" "rice?" "vegetables?" ]
≫ [a { "!" + } for]
[ "peanut sauce!" "rice!" "vegetables!" ]

#### fold / reduce

An array of values may also be reduced to a single value:

≫ [10 20 30] a!
≫ clear 0 a {+} for             # compute the sum of the elements of the array
60

In this example, for takes the array a and the loop body {+} from the stack. 0 is now the topmost value on the stack. The first iterated value (10) is added to 0, resulting in 10 on the stack, and so on. The individual iterations are:

Tokens Stack Comment
clear Empty the stack
0 0 Push 0 onto stack
a 0 [10 20 30] Reference the data array
{+} 0 [10 20 30] {+} Push the executable array
for 0 Before the first iteration, for pops its two arguments from the stack
0 10 Start of first iteration, for provides first array element (10)
+ 10 Loop body executed
10 20 Start of second iteration, for provides second array element (20)
+ 30 Loop body executed
30 30 Start of third iteration, for provides third array element (30)
+ 60 Loop body executed

Compute the total number of characters of all elements of an array of strings:

≫ ["vegetables" "rice" "pizza" "burger"] a!
≫ clear 0 a {length +} for
25

Count the number of strings in an array:

≫ [1 "hello" -3.14 "world" :yummy] a!
≫ clear 0 a { type :Str = { 1 + } if } for
2
≫ clear 0 a { str? { 1 + } if } for    # may be abbreviated like this
2

Test if all elements of an array satisfy a condition:

forall: (a predicate) {
true a { predicate not { pop false break } if } for
} fun

≫ clear [1 2 3 4] {3 <} forall
false
≫ clear [1 2 3 4] {5 <} forall
true

Test if there is at least one element in an array that satisfies a condition:

exists: (a predicate) {
false a { predicate { pop true break } if } for
} fun

≫ [1 2 3 4] {1 <} exists
false
≫ [1 2 3 4] {2 <} exists
true

#### filter

Keep only the strings in an array:

≫ [1 "hello" -3.14 "world" :yummy] a!
≫ clear [a { dup type :Str != { pop } if } for]
[ "hello" "world" ]
≫ clear [a { dup str? not { pop } if } for]    # equivalently
[ "hello" "world" ]

The latter may be easier to read with a variable:

≫ [1 "hello" -3.14 "world" :yummy] a!
≫ clear
≫ [ a (x) { x str? { x } if } lam for ]
[ "hello" "world" ]

One may write a filter function to further increase readability:

filter: (a predicate) {
[a { dup predicate not { pop } if } for]
} fun

≫ ["a" "b" 6 -3] { str? } filter
[ "a" "b" ]
≫ ["a" "b" 6 -3] { int? } filter
[ 6 -3 ]
≫ [1 0 6 -3] { 0 > } filter
[ 1 6 ]

### fori over arrays

fori is a variant of for that not only provides the array elemen on each iterationt, but also its index in the array:

≫ [10 20 30] a!
≫ a { } fori             # element and its index are provided with each iteration
10 0 20 1 30 2

To get just the elements at even index positions:

≫ [10 20 30] a!
≫ [a { 2 mod 0 != {pop} if } fori]
[ 10 30 ]

## Arrays

Arrays are the main data structure of PostFix. An array may have elements of arbitrary types, element types may be mixed, arrays may be nested:

[]                      # 0-element (empty) array
[1 "two" false 3.14]    # 4-element array, elements of different types
[1 [2 3]]               # 2-element array, nested array as second element

### get, set, length

Getting an array element:

≫ clear [1 2 3] 0 get
1
≫ clear [1 2 3] .0      # abbreviation
1
≫ 1 i!
≫ [1 2 3] .i            # abbreviation
2

Setting an array element:

≫ clear [1 2 3] 0 :x set
[ :x 2 3 ]
≫ [1 [2 3]] length
2

### append, +

Adding an element creates a new array. An array cannot be modified:

≫ [1 2 3] 4 append
[ 1 2 3 4 ]
≫ length
4

Concatenating arrays:

≫ ["hop" "skip"] ["jump" "now"] +
[ "hop" "skip" "jump" "now" ]
≫ length
4

### contains, find

Check whether a value is present in an array:

≫ ["hop" "skip" "jump"] "fall" contains
false

Return the index of an element in an array (or nil if not present):

≫ [1 2 3] 3 find
2                               # 3 found at index 2
≫ [1 2 3] 4 find
≫ [1 2 3 1 2 3] 1 2 find-from   # start looking for 1 at index 2
3                               # 1 found at index 3

### remove, insert, slice

Remove an element, insert an element, and return a subarray:

≫ [1 2 3] 2 remove              # remove element 2
[ 1 3 ]
≫ [1 2 3] 2 remove-at           # remove element at position 2
[ 1 2 ]
≫ [1 2 3] 0 x: insert           # insert before first
[ :x 1 2 3 ]
≫ [1 2 3] 3 x: insert           # insert after last
[ 1 2 3 :x ]
≫ [1 2 3 4 5 6] 1 3 slice       # subarray from index 1 (inclusive) to index 3 (exclusive)
[ 2 3 ]

### reverse, sort, shuffle

Reverse the order of elements, randomly shuffle, and sort arrays:

≫ [1 2 3] reverse
[ 3 2 1 ]
≫ [1 2 3 4 5 6] shuffle
[ 4 2 5 3 1 6 ]
≫ sort
[ 1 2 3 4 5 6 ]

## Key-Value Arrays

Arrays can be used in PostFix in a similar manner as association lists in Lisp: The array may store a key (symbol) followed by a value. The value can then easily be retrieved using the key.

Here is a key-value array that describes a 2D point. Its x- and y-coordinates may easily be accessed:

### get and key-get

≫ [x: 10 y: 20] point!
≫ point :x get            # get x-coordinate by key
10
≫ point .:x               # equivalent abbreviation
10
≫ point :y get            # get y-coordinate by key
20
≫ point .:y               # equivalent abbreviation
20
≫ point .:z               # try non-existent key
nil
≫ dist: point .:x point .:x *  point .:y point .:y  *  +  sqrt !
≫ dist
22.360679774997898

Symbols always serve as keys when accessing array elements. Other types can also be used as keys, but then the key-get operator is preferred. The key-get operator expects a third argument: the value to return if the key is not present. get simply returns nil in this case. For example, let's define an array that has information on the sizes of some planets:

≫ planet-sizes: [ "Mercury" 4878  "Venus" 12104  "Earth" 12756  "Mars" 6780  "Jupiter" 139822 ] !
≫ planet-sizes "Earth" get          # use string as key
12756
≫ planet-sizes "Pluto" get          # try non-existing key
nil
≫ planet-sizes "Earth" 0 key-get    # use key-get, return 0 if key is not present
12756
≫ planet-sizes "Pluto" 0 key-get    # use key-get, return 0 if key is not present
0

The following example illustrates the difference between get and key-get:

≫ [9 8 7 6] 0 get                   # get element at index 0
9
≫ [9 8 7 6] 0 "unknown" key-get     # get key 0 (which is not present), mappings: 9 -> 8, 7 -> 6
"unknown"
≫ [9 8 7 6] 9 get                   # get element at index 9 (which is not a valid index)
(Error: Index out of range: 9)
≫ [9 8 7 6] 9 "unknown" key-get     # get key 9 (which is present), mappings: 9 -> 8, 7 -> 6
8

Note that using an invalid index with get is an error, whereas trying to lookup a value with an unknown key is not.

There is an ambiguity if a key also occurs as a value:

≫ [1 2 2 1] 2 "unknown" key-get     # mappings: 1 -> 2 and 2 -> 1
2                                   # error: returns the element after the first 2

To solve this issue, simply hide values in a one-element array:

≫ [1 [2] 2 [1]] 2 ["unknown"] key-get .0    # mappings: 1 -> 2 and 2 -> 1
1                                           # the intended value
≫ [1 [2] 2 [1]] 3 ["unknown"] key-get .0    # mappings: 1 -> 2 and 2 -> 1
"unknown"                                   # the intended value

### set and key-set

There are two functions to set elements or key-value pairs in key-value arrays: set and key-set. If the second argument of set is not an integer, then the argument is interpreted as the key for the value following it. If the second argument of set is an integer, then the integer is interpreted as an index into the array. key-set always treats its second argument as a key, even integers.

≫ [name: "Fred" age: 21] f!
≫ f :age 22 set
[name: "Fred" age: 22]           # set value following key :age (was 21)
≫ f 1 22 set
[name: 22 age: 21]               # set element at index 1 (was "Fred")
≫ f :age 23 key-set
[name: "Fred" age: 23]           # set value following key :age (was 21)
≫ f 1 23 key-set
[name: "Fred" age: 21 1 23]      # interpret 1 as an integer key, enter new key-value pair
≫ f "x" 22 set
[name: "Fred" age: 21 "x" 22]    # interpret "x" as an integer key, enter new key-value pair

So, key-set always interprets its second argument as a key, even integers, whereas set treats integers as indices and other types as keys.

#### key-update

A task that often occurs with key-value arrays is to update a value, which involves reading the present value, modifying it, and storing it again:

≫ [name: "Fred" age: 21] f!
≫ f :age f .:age 1 + set
[ :name "Fred" :age 22 ]

This works, but is hard to read. A more convenient way to update an array is to use the key-update operator:

≫ [name: "Fred" age: 21] f!
≫ f :age 0 {1 +} key-update
[ :name "Fred" :age 22 ]

The key-update operator takes four parameters:

array key neutral procedure key-update

The procedure is an executable array that gets provided the current value on the stack and may modify it. The neutral element is used as the current value if the key-value mapping is not present yet.

### Setting elements in nested arrays

The path-set, path-key-set, and path-update operators simplify setting elements in nested arrays. Their parameters specify the path to the target element.

#### path-set

≫ [[0 0] [100 100]] line!                       # line defined by its end points
≫ line [1 0] 200 path-set                       # set second point (index 1), first component (index 0)
[ [ 0 0 ] [ 200 100 ] ]                         # new array on the stack
≫ line                                          # note that line still refers to the old array
[ [ 0 0 ] [ 100 100 ] ]
≫ line!                                         # let line refer to the new array

#### path-key-set

≫ [p1: [x: 0 y: 0] p2: [x: 100 y: 100]] line!   # line defined by its end points
≫ line [p2: y:] 200 path-key-set                    # set second point's (:p2) y-component (:y)
[ :p1 [ :x 0 :y 0 ] :p2 [ :x 100 :y 200 ] ]     # new array on the stack

#### path-upate

≫ [p1: [x: 0 y: 0] p2: [x: 100 y: 100]] line!   # line defined by its end points
≫ line [p2: y:] 0 {1 +} path-update line!       # add 1 to second point's (:p2) y-component (:y)
[ :p1 [ :x 0 :y 0 ] :p2 [ :x 100 :y 101 ] ]     # the y-element of the p2-element got updated

## String Operations

Many operations on arrays, such as for, also work on strings. Strings can be regarded as arrays of characters – however, they are implemented differently.

≫ "az" .0               # get first character of string
"a"                     # one-element string of first character
≫ "az" .1               # get second character of string
"z"                     # one-element string of second character
≫ "az" str->chars       # convert string into an array of integers (ASCII/Unicode values)
[ 97 122 ]              # Unicode value of character 'a' is 97 and of 'z' is 122
≫ "hello world!?" s!
≫ [s str->chars { c! c 97 >= c 122 <= and {c 32 -} {c} if } for] chars->str
"HELLO WORLD!?"

Let's investigate the for loop in more detail:

[ s str->chars { c!
c 97 >= c 122 <= and {
c 32 -
} {
c
} if
} for ] chars->str

The body of the for loop is executed for each character of the string. The condition of the if operator checks whether the current character is a lower-case character. If so, it is converted to an uppercase character (by subtracting 32 from the Unicode value), otherwise the character is not changed. All this is embedded in a data array and finally converted back to a string.

There are many more string operations, such as replace-first, replace-all, format, trim, char→str, contains, find, split, etc.

## Input and Output

There are several functions that read data of different types from the keyboard:

• read-int reads characters up to the next whitespace character and tries to convert them to an integer number
• read-flt reads characters up to the next whitespace character and tries to convert them to a floating-point number

There are functions to read data from a URL:

### Formatted output

For formatted output PostFix currently uses format strings as known from C and Java. This is subject to change in the future. The operators for formatted printing are printf, printfln, and format:

• format-string [values] printf # print formatted
• format-string [values] printfln # print formatted, followed by a line break
• format-string [values] format # create a formatted string

Here are a few examples:

≫ "%.2f * 2 = %.2f\n" [1.234 2.468] printf
≫ "%.2f * 2 = %.2f" [1.234 2.468] printfln    # or equivalently
output: 1.23 * 2 = 2.47
≫ "|%8s|" ["hello"] printfln
output: |   hello|
≫ "|%s|%d|" ["hello" 123] format
"|hello|123|"

The most common placeholders are “%d for integer numbers, ”%f“ for floating-point numbers, and ”%s“ for strings. For floating point numbers it is helpful to define the number of places to round the output to (e.g., two places with ”%.2f“). The full specification of the format string is available here.

## Data Definitions

PostFix allows you to compose composite data types (also called compound data types) from the built-in data types—such as numbers, strings, or booleans—as well as from composite data types. This provides a way to specify that a certain grouping of elements should be regarded as a whole. For example, a point in the 2D plane is composed of its two coordinates, which are numbers. Data about a bank account may be composed of an integer value representing the account number, a string for the account holder's name, and a number for the current balance. Point and Account, respectively, are composite types. In PostFix composite data types are defined in data definitions.

PostFix supports two kinds of composite types: product types, also known as structures or records, and sum types, also known as unions or variants. These two kinds of composite types are described below.

### Product types (Structures)

Product types group multiple attributes to a new type. (The name product type refers to the notion of the Cartesian product.) For example, a point in the 2D plane with attributes x and y is defined as:

Point: (x y) datadef

You may optionally specify the types of the components:

Point: (x :Num y :Num) datadef

Since :Point is a new type (and to avoid name collisions) it has to be written in Title case, like all types.

The above data definition automatically defines the following functions in the current dictionary. These functions help creating new instances of :Point, testing whether something is a point, and accessing the attributes of a point.

point: (x :Num y :Num -> :Point) {...} fun   # constructor function
point?: (p :Obj -> :Bool) {...} fun          # detector function
point-x: (p :Point -> :Num) {...} fun        # attribute access
point-y: (p :Point -> :Num) {...} fun        # attribute access

When looking at the generated implementations, it becomes apparent that data types store the components and metadata in standard PostFix arrays:

point: (x :Num y :Num -> :Point) { # constructor function
[ :datadef :Point x y ]
} fun

point?: (p :Obj -> :Bool) { # detector function
[ { p arr? }
{ p length 2 >= }
{ p 0 get :datadef = }
{ p 1 get :Point = } ] and
} fun

point-x: (p :Point -> :Num) { p 2 get } fun   # attribute access
point-y: (p :Point -> :Num) { p 3 get } fun   # attribute access

These functions may be used to create and work with point instances:

≫ 1 2 point p!
≫ p point?
true
≫ p point-x
1
≫ p point-y
2

Members of data definitions may be data definitions themselves:

≫ Point: (x :Num y :Num) datadef
≫ Line: (p1 :Point p2 :Point) datadef
≫ 1 2 point a!
≫ 3 4 point b!
≫ a b line l!
≫ l line-p2 point-y
4

You now may write functions that use these new types:

line-length: (l :Line) {
l line-p1 p1!
l line-p2 p2!
p1 point-x  p2 point-x  -  dx!
p1 point-y  p2 point-y  -  dy!
dx dx *  dy dy *  +  sqrt
} fun

≫ l line-length
2.8284271247461903

#### Exercise

• Write a data definition for cities. A city value is supposed to represent the name, area, and number of inhabitants of the city.

### Sum types (Unions)

Sum types represent one of several possible cases of data. A value of a sum type stores information of the case it currently represents. A simple example would be a 2D point that is either represented by euclidean or by polar coordinates:

Point: {
Euclid: (x :Num, y :Num)
Polar: (theta :Num, magnitude :Num)
} datadef

This data definition defines the types :Point, :Euclid, and :Polar and the functions:

point?: (p :Obj -> :Bool) {...} fun            # detector function

euclid: (x :Num y :Num -> :Euclid) {...} fun   # constructor function
euclid?: (p :Obj -> :Bool) {...} fun           # detector function
euclid-x: (p :Euclid -> :Num) {...} fun        # attribute access
euclid-y: (p :Euclid -> :Num) {...} fun        # attribute access

polar: (x :Num y :Num -> :Polar) {...} fun     # constructor function
polar?: (p :Obj -> :Bool) {...} fun            # detector function
polar-theta: (p :Polar -> :Num) {...} fun      # attribute access
polar-magnitude: (p :Polar -> :Num) {...} fun  # attribute access

The constructur, detector, and attribute access functions are defined as described above. point? is defined as:

point?: (p :Obj -> :Bool) { [ { p euclid? } { p polar? } ] or } fun

These functions are used like this:

distance: (p :Point -> :Num) {
{ p euclid? } {
p euclid-x  p euclid-x  *
p euclid-y  p euclid-y  *
+  sqrt
}
{ p polar? } {
p polar-magnitude
}
} cond-fun

≫ 3 4 euclid e!
≫ e distance
5.0
≫ 7 8 polar p!
≫ p distance
8

The above function accepts a :Point in either variant. Then it checks whether the current variant is a euclidean or a polar point and uses the appropriate accessor functions to compute the distance from the origin.

Here is another example involving a data definition for different kinds of 2D shapes, namely rectangles, circles, and equilateral triangles.

Shape: {
Rect: (width :Num, height :Num)
Triangle: (base :Num, height :Num)
} datadef

And here is a function that computes the area of shapes:

area: (s :Shape -> :Num) {
{ s rect? } { s rect-width  s rect-height  * }
{ s circle? } { s circle-radius r! PI r * r * }
{ s triangle? } { s triangle-base  s triangle-height  *  0.5 * }
} cond-fun

≫ 3 4 rect r!
≫ 1 circle c!
≫ 2 1 triangle t!
≫ r area
12
≫ c area
3.141592653589793
≫ t area
1.0

Variants are often used with recursive definitions, e.g., for lists and trees.

A list may be defined as being either empty or a value followed by a list:

List: {
Null: ()
Cons: (value :Obj, next :List)
} datadef

empty is the name of a built-in function, so we use null here. Cons refers to “constructing” a new list. Let's build a list of integers and compute its length:

≫ 1 2 3 4 5 null cons cons cons cons cons x!

list-length: (l) {
{ l null? } { 0 }
{ l cons? } { l cons-next list-length 1 + }
} cond-fun

≫ x list-length
5

The empty list has length 0. A non-empty list is one larger than the rest of the list when the first element is removed.

Now let's define a binary tree of numbers:

BinTree: {
Leaf: ()
Node: (value :Num, left :BinTree, right :BinTree)
} datadef

Defined like this only inner nodes carry values, whereas leaves are empty.

Let's create a simple tree:

tree-sum: (t :BinTree -> :Num) {
{ t leaf? } { 0 }
{ t node? } {
t node-value
t node-left tree-sum +
t node-right tree-sum +
}
} cond-fun

1 leaf leaf node node1!
4 leaf leaf node node4!
3 leaf node4 node node3!
5 node1 node3 node node5!
node5 tree-sum

## Graphics

With PostFix you can create interactive programs and games. The core elements of these are images. PostFix allows creating and combining 2D graphics primitives and processing keyboard and mouse input on them. The approach is inspired by the Racket Universe Library.

### Static graphics

Images are simply specified using arrays. The image-width and image-height functions tell us about their dimensions.

≫ [rectangle: 300 200 "red"] r!
≫ r image-width
300.0
≫ r image-height
200.0

≫ cat image-width
320.0
≫ cat image-height
213.0
≫ cat show-image

Circles with red background, red background and black outline, and an overlay of a yellow and blue circle:

[circle: 30 "red"] show-image
[circle: 40 "red" "black"] show-image
[circle: 50 "red" "black"] image-width
[overlay: [[circle: 10 "yellow"] [circle: 30 "blue"]]] show-image

Graphical objects are represented as arrays:

[square: 40 "red" "black"]
[square: 40 "yellow" [pen: "blue" 7]]
[rectangle: 40 10 "cyan"]
[circle: 40 "red" "black"]
[ellipse: 40 10 "yellow" "blue"]
[text: "hello" 36 "lime" "black"]
[text: "hello" [font: "Times" 36] "lime" "black"]

Image data is also represented as an array:

[bitmap: "http://.../cat.jpg"]

"http://...cat.jpg" read-image-url data!
[bitmap: data]

Combinations of graphical objects are represented as nested arrays:

[scale: 2.5 [rectangle: 40 10 "yellow" "blue"]]
[rotate: -45 PI * 180 / [rectangle: ...]]

[place-image: [square: 20 "red"]
[square: 20 "blue"]
20 20]
[place-image: [square: 20 "red"]
[square: 20 "blue"]
20 20 "center" "center"]
[place-image: [square: 20 "red"]
[square: 20 "blue"]
20 20 "left" "center"]

[beside:
[[square: 20 "red"] [square: 20 "blue"]]]
[beside:
[[square: 40 "red"] [square: 20 "blue"]] "bottom"]

[above:
[[square: 40 "red"] [square: 20 "blue"]] "left"]

[overlay:
[[square: 20 "blue"] [square: 40 "red"]]]

[underlay: ...]

#### show

show-image can only show a single static image. The show operator is more flexible and is used for static graphics, animations, and interactive graphics. It has five parameters:

window-title window-width window-height initial-state [callback-functions] show

The most interesting of these is the initial-state and the array of callback-functions. The current state is provided to each of the callback functions. The array of callback functions needs at least an on-draw function that converts to current state to graphical output, i.e., it takes the current state as input and produces an image as output. Let's start with a simple draw function that takes the side length of a square as input and produces a red square of that side length as output.

number->square: (s :Num -> :Arr) {
[square: s "red"]
} fun

≫ 5 number->square   [ :square 5 "red" ] test=
≫ 10 number->square  [ :square 10 "red" ] test=
≫ 20 number->square  [ :square 20 "red" ] test=
≫ test-stats
All 3 tests passed!

We use show to produce a visible result:

"Square" 200 200 100 [    # title: "Square", width: 200, height: 200, initial-state: 100
on-draw: { number->square } lam
] show

This may also be written as:

"Square" 200 200 100 [
on-draw: (s :Num -> :Arr) { [square: s "red"] } lam
] show

Or, if you don't like types:

"Square" 200 200 100 [
on-draw: (s) { [square: s "red"] } lam
] show

Or, if you don't like parameter lists:

"Square" 200 200 100 [
on-draw: { s! [square: s "red"] } lam
] show

### Animations

A static square is nice, but an animated one is even better:

"Square" 200 200 100 [
on-draw: (s) {              # takes state, returns an image
[square: s "red"]
} lam
on-tick: (s) {         # takes state, returns new state
s 1 -
} lam
stop-when: (s) {            # takes state, returns a boolean
s 0 <=
} lam
] show

on-tick is called about 60 times per second and allows to periodically update the animation state. stop-when makes the animation stop and the window close when the condition is true.

Here is an animation that never stops but restarts again when the square got too small:

"Square" 200 200 100 [
on-draw: (s) {
[square: s "red"]
} lam
on-tick: (s) {
s 1 <= { 100 } { s 1 - } if
} lam
] show

Here is a rotating square:

# State -> ImageArray
# Takes the current state and returns an image array.
number->image: (theta :Num -> :Arr) {
[overlay: [[rotate: theta [square: 50 "red"]]
[square: 80 "blue"]]]
} fun

# State -> State
# Takes current state and returns next state. Called 60 times per second.
on-tick: (theta :Num -> :Num) { # here, the state is a number
theta 0.03 +
} fun

"Square" 200 200 0 [ # title, width, height, initial-state
on-draw: { number->image } lam
on-tick: { on-tick } lam
] show

Separate functions are not needed:

"Square" 200 200 0 [ # title, width, height, initial-state
on-draw: (theta :Num -> :Arr) {
[overlay: [[rotate: theta [square: 50 "red"]]
[square: 80 "blue"]]]
} lam
on-tick: (theta :Num -> :Num) {
theta 0.03 +
} lam
] show

### Interactive graphics

Key-input may reset the animation to its initial state:

"Square" 200 200 200 [
on-draw: (s) {
[square: s "red"]
} lam
on-tick: (s) {
s 1 <= { 100 } { s 1 - } if
} lam
on-key-press: (s key) { # takes state and pressed key, returns new state
key println         # show the key that was pressed
200                 # reset to initial state
} lam
] show

Link the size of the square to the x-position of the mouse:

"Square" 200 200 200 [
on-draw: (s) {
[square: s "red"]
} lam
on-mouse-move: (s mouse-x mouse-y) { # takes current state and mouse position, returns new state
mouse-x
} lam
] show

Rotate a square based on the x-position of the mouse:

# State -> ImageArray
# Takes the current state and returns an image array.
number->image: (theta :Num -> :Arr) {
[overlay: [[rotate: theta [square: 50 "red"]]
[square: 80 "blue"]]]
} fun

# State, String -> State
# Returns next state depending on the mouse position.
on-mouse-move: (state :Num, x :Num, y :Num -> :Num) {
x 0.05 *
} fun

"Square" 200 200 0 [ # title, width, height, initial-state
on-draw: { number->image } lam
on-mouse-move: { on-mouse-move } lam
] show

The state may be more complex than a single number. For example, it may be an array that stores the current mouse position. The next example shows a red dot that is centered at the mouse position.

[square: 200 "white"] BACKGROUND!
[circle: 15 "red"] DOT!

"Square" 200 200 [0 0] [
on-draw: (pos) {
[place-image: DOT BACKGROUND pos .0 pos .1]
} lam
on-mouse-move: (pos mouse-x mouse-y) { # takes current state and mouse position, returns new state
[mouse-x mouse-y]
} lam
] show

place-image combines two images: it places the first image (DOT) over the second image (BACKGROUND). The resulting image is cropped to the size of the background image. The fourth and fifth element of the place-image array are the coordinates of the center of the front image with respect to the left-top corner of the background image. PostFix provides many such combinators of image (such as overlay, underlay, beside, above, etc.) which leads to high flexibility. This approach is inspired by the Racket Image Library.

Press arrow-left to rotate a the square left, arrow-right to rotate it right, and any other key to stop the rotation. Here, the state is an array containing the the current rotation and the amount the rotation is updated on each tick: [theta delta].

# State -> ImageArray
# Takes the current state and returns an image array.
number->square: (state :Arr -> :Arr) {
state .0 theta!
[overlay: [[rotate: theta [square: 50 "red"]]
[square: 80 "blue"]]]
} fun

# State -> State
# Takes current state and returns next state. Called 60 times per second.
on-tick: (state :Arr -> :Arr) {
[state .0 state .1 +   state .1]
} fun

# State, String -> State
# Returns next state depending on current state and key.
on-key-press: (state :Arr, key :Str -> :Arr) {
{ key "ArrowLeft" = } {[state .0, -0.03] }
{ key "ArrowRight" = } {[state .0, 0.03] }
{ true } { [state .0, 0] }
} cond-fun

"Square" 200 200 [0 0] [ # title, width, height, initial-state
on-draw: { number->square } lam
on-tick: { on-tick } lam
on-key-press: { on-key-press } lam
] show

### Exercise

Write an interactive program that draws a circle at the mouse position. The circle should changes its size depending on the distance to the left side of the image.

## References

PostFix is inspired by PostScript, Forth, Racket, and NewLisp.