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
          • 2 is discarded
      • 3 is discarded
  • the top element is now 5
• if b is false, then
  • + is discarded
    • discarding + causes the next two elements to be discarded
      • 2 is discarded
      • 3 is 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]

See also

• Tg