Lazy Prefix

From Esolang
Jump to navigation Jump to search

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