Popr Tutorial - Dot Machines

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

1. Arrows point to dots a machine needs to consume, not where to put the dots that the machine produces.
2. Arrows enter and leave upward and to the left.
3. Boxes are dots that hold machines.
4. Arrows cannot freely cross each other or pass over any component, so components must consume from top to bottom.
5. If a component consumes more dots than available, a new dot is add to the bottom left.
6. 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 pushls followed by N poprs, 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:

1. Works if A is True, using G to extract B.
2. 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.