# Popr Tutorial - Dot Machines

Modified on April 5, 2018

Popr is a new programming language (compiler, try it) that works unlike any other programming language that I know of, so a concise description of the language is difficult.

Rather than describe the semantics in relation to other languages, or listing the formal evaluation rules, I will present a graphical notation that, while impractical for larger programs, shows how Popr programs work in an intuitive way.

In this notation, we will build machines that consume and produce dots.

Before we proceed further, here are the rules for these diagrams:

## Rules

- Arrows point to dots a machine needs to consume,
*not*where to put the dots that the machine produces. - Arrows enter and leave upward and to the left.
- Boxes are dots that hold machines.
- Arrows cannot freely cross each other or pass over any component, so components must consume from top to bottom.
- If a component consumes more dots than available, a new dot is add to the bottom left.
- Each component must have an arrow pointing to each dot it produces.

A component is activated by pulling any of the dots that the component produces. Before the component can run, it must pull in a dot for each arrow. This may in turn activate other components, propagating from right to left.

I will introduce components as needed.

## Operators: `not`

`not`

is a component that produces a `True`

dot when given a `False`

dot, and vice versa.

True not False False not True

`True`

and `False`

are dot names. Dot names start with an uppercase letter.

`not`

is an example of a component that consumes one dot and produces a related dot. There are many similar components, which I will call “operators”, such as arithmetic operators and comparison operators.

## pullN: boxes, `popr`

, and `swap`

Components and dots can be placed in a box, for example, `[A B]`

is a box containing `A`

and `B`

.

Any machine, or even a partial machine, such as `[not]`

, can be placed in a box, and boxes themselves can be consumed and produced like any other dot.

Boxed machines are drawn as a machine surrounded by a rectangle (box.)

`popr`

is a component that pulls one dot from within a box.

```
: [A B] popr
[ A ] B
```

Because every box contains a machine, the machine within is activated when pulling from the box:

: [False not] [ False not ] : [False not] popr [] True

`swap`

is a component that crosses the top two arrows, so that the top dot and the one beneath it are exchanged.

```
: A B swap
B A
```

`pull`

is a machine that combines `popr`

and `swap`

so that the box is above the dot that was pulled out.

```
: [A B] pull
B [ A ]
```

`pull`

is useful because they can be chained together, (the dotted area shows the machines defined above), to create `pull2`

and `pull3`

, which pull 2 and 3 dots, respectively, out of a box.

: [A B C] pull2 C B [ A ] : [A B swap C] pull2 C A [ B ] : [A B C D] pull3 D C B [ A ]

Some machines can be extended in a straightforward way similar to `pull`

, to form *families* of machines. These families are named by replacing each number in the name with an uppercase letter, such as `pullN`

.

## swap2: `drop`

, `pushl`

, and `pushr`

`drop`

is a component that cuts off the top arrow, allowing the other arrow to pass underneath.

When an arrow is cut off, the dot to which it pointed can no longer be pulled, which may prevent activating a machine, and the machines that *that* machine might have activated, and so on.

*Exercise:*Write the machine

`head`

, which removes a single dot from a box.
: :def head: ... : [A] head A

*Tip:* Use the online evaluator to test your solution.

`pushl`

is a component that connects a box to an outside dot, which can be seen as “pushing” the dot into the left side of the box.

```
: A [B] pushl
[ A B ]
```

This is a little misleading, though, because machines only pull. `pushl`

does not activate the machine inside the box; it just connects an arrow from the machine inside the box to a dot outside.

: False [not] pushl [ False not ] : False not [] pushl [ False not ]

The result may be surprising, but this diagram explains the result:

In the second example, `False`

is pulled into the box with `not`

. In both cases `[False not]`

represents a machine that has not been activated.

`popr`

can be used to activate the machine:

```
: False [not] pushl popr
[] True
```

`pushr`

is a component that pushes a dot into the right side of a box, which can be retrieved with `popr`

.

: [A] B pushr [ A B ] : [A] B pushr popr [ A ] B : [] False not pushr [ False not ]

Just like `pushl`

, it does not activate any components or the machine inside the box.

*Note:* The dot is on top of `pushr`

because it is an abbreviation of a more verbose diagram where the dot is in the middle; see `compose`

.

Now, we can build something a little more interesting using these new components. `swapN`

is another family of machines, starting with `swap`

, which rotates two dots.

`swap2`

rotates three dots, as shown by the labels in the diagram, bringing the bottom dot to the top.

```
: A B C swap2
B C A
```

*Exercise:*Write a machine to swap two dots within a box.

: :def swab: ... : [A B] swab [ B A ]

## dip11: `apNM`

`pushl`

and `popr`

use a box to consume and produce (respectively) one dot, but it can be tedious to do this one dot at a time, so there is a family of components, `apMN`

, which consume `M`

dots and produce `N`

dots.

```
: A B [C] ap21
[ A B ] C
```

`apMN`

is equivalent to `M`

`pushl`

s followed by `N`

`popr`

s, e.g. `ap21`

is equivalent to: `pushl pushl popr`

Therefore, `pushl`

is `ap10`

, and `popr`

is `ap01`

.

`dip11`

runs a dot through a given box, like `ap11`

, but without affecting the dot on top.

The dot labeled `f`

is a box containing a machine that consumes a dot and produces another. `dip11`

uses `pushr`

to stash the dot on top within the given box, and then uses `ap12`

to run the machine and pull the stashed dot back out along with the produced dot. There is no need to produce the remaining box, so it is dropped (*not* pulled.)

: False A [not] dip11 True A : False A [] dip11 False A

## ifte: `!`

(assert), `|`

(alt), and `.`

(compose)

`!`

(assert) either produces the dot from the lower arrow if the upper arrow consumes a dot called `True`

, otherwise, it produces a broken dot, which breaks everything that consumes it. Broken machines don’t produce anything.

: A True ! A : A 42 !

*Note:* Because a broken machine doesn’t produce anything, nothing is printed in this case.

`|`

(alt) represents two versions of the machine to try: one version using the top arrow, and another version using the bottom arrow.

: A B | A B : A B False ! | A

*Note:* The results from both versions of the machine are printed on different lines.

`.`

(compose) puts two boxes together, merging the two machines into one box by connecting them together. This component does not activate the machine within the box.

*Note:* `pushr`

is equivalent to: `[] pushl .`

: [A] [B] . [ A B ] : [False] [not] . popr [] True : [A B] [swap] . [ A B swap ]

Notice that the last example did not print: `[ B A ]`

`ifte`

uses the components discussed to select between two dots, depending on the name of the first dot.

The first part of `ifte`

, `[] ap20 swap pushr`

, arranges the three dots in a box, as shown in the fluffy bubble.

There are two versions of the machine, indicated by the circle (alt) pointing to the boxes `F`

and `G`

. The boxed dots and `F`

(for one version, `G`

for the other) are put together into one box, using compose. The result is pulled out of the box, using the component `head`

, defined in the earlier exercise.

In both `F`

and `G`

, there is an assertion `!`

connected to `A`

. In F, it is negated with `not`

, and `C`

is passed through. In `G`

, `A`

is passed directly to the assertion, and `B`

is passed through, while `C`

is dropped (not needed.)

So, we have two versions of this machine:

- Works if
`A`

is`True`

, using`G`

to extract`B`

. - Works if
`A`

is`False`

, using`F`

to extract`C`

.

Now that we have two machines, we can just try both, and keep the results from the one that doesn’t break. This works as intended, producing `B`

or `C`

depending on if `A`

is `True`

.

: True A B ifte A : False A B ifte B

*Exercise:*Use

`ifte`

to write a machine that inverts the first dot if the second is `True`

.
: :def bxor: ... : False False bxor False : False True bxor True : True False bxor False : True True bxor True

## dup

One of the remaining components is `dup`

, which produces two copies.

```
: A dup
A A
```

*Exercise:*Write the following machine.

: :def abba: ... : A B abba A B B A : B A abba B A A B

## So Then

While this notation isn’t ideal for large programs, both the diagrams and Popr programs can be broken into smaller pieces (as seen in `ifte`

). This notation can be useful to introduce the semantics of Popr programs, and can be used to analyze any behavior that is confusing or surprising.