Linear looper

あけましておめでとう。I want to follow up yesterday's post with notes on looping in my theoretical stack language. I think it composes nicely with the implementation of conditions.

Syntax

A loop is a non-ternary condition wrapped in parentheses, with the semicolon on the outside. Like so.

( 100 x > ? 1 x + Ω ) ;

Once the condition is false, the program reads past the ;.

Ω = assume that some kind of memory writing operation exists to reassign x after it is incremented. Beyond the scope of these notes.

Bytecode

The compiled loop also makes use of GOTO.

100 x > ? 12 g 1 x + Ω 0 g

As long as the condition is true, the program will read to its natural end, which terminates with 0 g: a jump back to the start. It will only break when the condition is false and 12 g jumps past the loop.

Compilation

Stacks come in handy again. Consider four constructs here.

• I → User input string.
• P → The program compiled in bytecode.
• S → Stack of conditional GOTO locations, explained in yesterday's notes.
• L → Stack of loop GOTO locations, which operates on a similar principal.

In addition to the conditional logic, the I→P compiler handles parentheses as follows.

• ( → Push current P write address on L. Does not increment |P|.
• ) → Pop L and write popped value α to P as α g.

Basic loop

The first example.

I → ( 100 x > ? 1 x + Ω ) ;
P →
S →
L →

Begin by popping address of ( onto L.

I → 100 x > ? 1 x + Ω ) ;
P →
S →
L → 0

Conditional logic is familiar. Note the address pushed to S. The opening parenthesis did not offset it.

I → ) ;
P → 100 x > ? α g 1 x + Ω
S → 4
L → 0

) pops from L and creates the loop GOTO.

I → ;
P → 100 x > ? α g 1 x + Ω 0 g
S → 4
L →

; provides an address for α to jump beyond the loop when the condition is false.

I →
P → 100 x > ? 12 g 1 x + Ω 0 g
S → 
L →

Nested loop

This is where stacks are needed.

I → ( 100 x > ? y 100 - ( 100 y > ? 1 y + Ω ) ; 1 x + Ω ) ;
P →
S →
L →

Through the first condition.

I → ( 100 y > ? 1 y + Ω ) ; 1 x + Ω ) ;
P → 100 x > ? α g y 100 -
S → 4
L → 0

Encountering a second ( before a matching ) pushes another address on L.

I → 100 y > ? 1 y + Ω ) ; 1 x + Ω ) ;
P → 100 x > ? α g y 100 -
S → 4
L → 0 9

The inner loop's condition.

I → ) ; 1 x + Ω ) ;
P → 100 x > ? α g y 100 - 100 y > ? β g 1 y + Ω
S → 4 13
L → 0 9

Encountering the first ) pops L and writes the inner loop GOTO.

I → ; 1 x + Ω ) ;
P → 100 x > ? α g y 100 - 100 y > ? β g 1 y + Ω 9 g
S → 4 13
L → 0

The first ; pops S and writes the inner condition GOTO.

I → 1 x + Ω ) ;
P → 100 x > ? α g y 100 - 100 y > ? 21 g 1 y + Ω 9 g
S → 4
L → 0

The outer loop operation.

I → ) ;
P → 100 x > ? α g y 100 - 100 y > ? 21 g 1 y + Ω 9 g 1 x + Ω
S → 4
L → 0

The outer loop GOTO.

I → ;
P → 100 x > ? α g y 100 - 100 y > ? 21 g 1 y + Ω 9 g 1 x + Ω 0 g
S → 4
L →

The outer loop condition GOTO.

I →
P → 100 x > ? 27 g y 100 - 100 y > ? 21 g 1 y + Ω 9 g 1 x + Ω 0 g
S →
L →

Can it really be this simple?