Boolet

From Esolang
Jump to: navigation, search

Boolet is a stack-based esolang created by User:joshop.

Memory/Stack

Boolet uses a single stack, which can contain bits or functions (i.e. lambdas). Unlike usual stack based languages it allows the programmer to move the stack pointer using > and <. However, the stack pointer's location is relative to the top of the stack.

Commands

Programs are run command by command. Each command is a single character. Parentheses () must be matched unless they are inside another set of parentheses and that is never executed (an error would occur during runtime).

Command Result
0 Push 0 onto the stack
1 Push 1 onto the stack
( Opens a function
) Closes a function, pushes the code from the matching ( onto the stack
~ Inverts the top stack value
| Performs a logical or between the top two stack values, popping them and pushing the result
& Performs a logical and between the top two stack values, popping them and pushing the result
/ Duplicates top stack value
$ Swap top two stack values
> Move the stack pointer one element down
< Move the stack pointer one element up
\ Pop the top value off the stack, discarding it
. Returns from a function call or halts if no function called (not needed at end of program)
= Compares the top two stack values and push 1 if they are equal and 0 if they are not
! Execute the function on top of the stack, popping it
? Pop the top value off the stack, and if it is 1, execute the function below it (function is popped either way)

Input is supplied as initial stack state, and after execution, the values on the stack are popped from top down, printing the value of the bit if the value is a bit and the contents of a function if the value is a function.

Example programs

Feel free to add program examples if you want

Hello, World!

(Hello, World!)

Infinite loop

(/!)/!

Truth-machine

(>//</>$<$?)/!\\

XOR

XORs two bits on top of stack.

/>$/<&~>|<&

Computational class

Boolet is at least Turing-complete because it embeds a Turing-complete subset of Underload:

Underload Boolet
~ $
: /
! \
(…) (…)
^ !

(There is no direct analogue of Underload's a, * or S commands, but none of these are necessary for Turing-completeness.)

However, it's possible that Boolet is more powerful than this. The = command is defined as comparing stack values, and the language includes functions as stack values. If this is interpreted as comparing the functions' source codes, then the language is Turing-complete. However, if it compares the functions' behaviour (i.e. ensuring that "the functions do the same thing", the normal definition of equality on functions), the language is uncomputable (comparing functions is one of the things that a Turing-complete language can't do).

Implementations

An implementation here, not very strictly tested.