Lazy Prefix

Lazy Prefix is an esoteric programming language designed to look like any other stack-based language, except that it heavily relies on lazy evaluation - a feature that reflects in its syntax by the use of prefix notation, as opposite to the usual suffix notation in most stack-based languages. Lazy Prefix was inspired by Tg.

Lazy Prefix is a work in progress. You are welcome to contribute with your ideas and suggestions.

Instructions

Note: the "before" and "after" columns show how the instruction would affect the stack, if it was a regular stack-based language; they are merely indicative and do not reflect Lazy Prefix's lazy evaluation.

Instruction Description before after
any decimal number
push a number to the stack `[tail]` `[x, tail]`
`+`
addition: push (pop1 + pop2) `[y, x, tail]` `[x + y, tail]`
`-`
subtraction: push (pop2 - pop1) `[y, x, tail]` `[x - y, tail]`
`*`
multiplication: push (pop1 * pop2) `[y, x, tail]` `[x * y, tail]`
`/`
integer division: push (pop2 / pop1) `[y, x, tail]` `[x / y, tail]`
`%`
push remainder of pop2 / pop1 `[y, x, tail]` `[x mod y, tail]`
`pop`
discard top element `[x, tail]` `[tail]`
`swap`
swap top two elements `[y, x, tail]` `[x, y, tail]`
`dup`
duplicate top element `[x, tail]` `[x, x, tail]`
`eq`
equality: push 1 if pop1 = pop2, 0 otherwise `[y, x, tail]` `[x = y, tail]`
`<`
less than: push 1 if pop1 < pop2, 0 otherwise `[y, x, tail]` `[x < y, tail]`
`not`
logical negation: push 1 if pop1 = 0, 0 otherwise `[x, tail]` `[not x, tail]`
`if`
if-then-else: if pop1 is true, then discard second element, otherwise discard top element `[b, x, y, tail]` `[b ? x : y, tail]`
`block`
make one block of n top elements `[n, x1, ..., xn, tail]` `[(x1 ... xn), tail]`
`deblock`
deblock a block, such that `deblock block n` is a no-op `[(x1 ... xn), tail]` `[x1, ..., xn, tail]`
`input`
push one element from input `[tail]` `[x, tail]`
`output`
pop and display top element `[x, tail]` `[tail]`

Lazy evaluation

Rather than an explanation of how programs in Lazy Prefix work, here is an example. Analyze the following program.

```2 3 + 2 dup output 3 * b if
```

If it were a random stack-based language, it will evaluate `2 3 +`, then `2 output 3 *`, then the if-then-else statement will select either 5 or 6; as a side-effect, the element 2 will always be displayed, notwithstanding the value of b. If it were a Lazy Prefix program, on the other hand, evaluating `if` will cause the following:

• b is evaluated
• if b is true, then
• `+` is evaluated
• `+` causes 2 and 3 to be evaluated
• then `*` is discarded
• discarding `*` causes the next two elements to be discarded (since it is a binary operator)
• output is discarded, which causes one more element to be discarded (since it is a unary operator)
• dup is discarded, which causes one more element to be discarded
• the top element is now 5
• if b is false, then
• `+` is discarded
• discarding `+` causes the next two elements to be discarded
• `*` is evaluated
• `output` is evaluated
• `dup` is evaluated
• 2 is evaluated
• as a side effect of output, 2 is displayed
• 3 is evaluated
• the top element is now 6

To reflect the way things work in Lazy Prefix, that program will actually be written `if b + 2 3 * output dup 2 3`.

Flow control

In order for Lazy Prefix to be an actual programming language, it needs some kind of looping construct. Here are two propositions.

• Some kind of while loop.
Instruction Description
`while`
while pop1 is true, repeat top element

It sort of made sense last night just before I fell asleep. Not really sure if it still does, and what that would mean.

• Functions.
 `(fun f = body)` make f an instruction equivalent to body, where body is a sequence of instructions, with no restriction on recursive calls
• An instruction similar to Fueue's `\$` operator.
Instruction Description before after
`repeat`
push a number of copies `[n, x, tail]` `[x, ..., x, tail]`