Karma

Karma is a Turing tarpit created by revcompgeek that was designed to have no explicit loops. Instead it has lines that can be jumped between, acting somewhat like functions. It has one stack and one deque as its only data structures. The stack and deque hold bytes and are unbounded (interpreter is limited by memory).

Information

Karma's commands each consist of a single character. The program ends when the interpreter runs out of characters to execute. Errors are caused whenever an unknown command is encountered or when a command tries to move up or down out of the range of the program.

Syntax

Math

For these commands, first is the top of the stack, second is the value underneath

+ - pop two values, push first + second
- - pop two values, push first - second
* - pop two values, push first * second
/ - pop two values, push first / second (integer division)
% - pop two values, push first % second (modulus)
& - pop two values, push first & second (bitwise AND)
| - pop two values, push first | second (bitwise OR)
^ - pop two values, push first ^ second (bitwise XOR)
~ - bitwise NOT the top of the stack
! - logical NOT the top of the stack

Logic

Each of these pops the top of the stack

= - push 1 if top of stack equals front of deque, else push 0
> - push 1 if top of stack is greater than front of deque, else push 0
@ - skip the next command if top of stack is not 1

Stack/Deque

digit - push digit onto stack
} - pop, insert front
{ - remove from front, push
[ - pop, insert back
] - remove from back, push
# - destroy top of stack
\ - clone the top of the stack

IO

? - input and push char
: - pop and output char
; - pop and output as number

Jumping

, - move down and begin at beginning of the line
. - move down and continue where it last left off
' - move back up and return where it last left off
< - jump back to the beginning of the current line

Examples

Comments are not allowed, but any character not encountered by the interpreter will be ignored. This means that any line can begin with ,' and it will be effectively ignored anywhere in the program. Also, if the last instruction in a line is ' then you can safely put anything after it (as long as it isn't after a @)

Example:
, This line will be ignored
12+;
The last line will end and therefore so will the program, this is never executed.

Programs can be designed so that lines can be called like functions. The following is a working example of this idea:

, This program will "call" the numbered function below it
1},5},2},5},4},5},3},
1=!\@,@'{#1;1'     (1)
2=!\@,@'{#456**:1' (x)
3=!\@,@'{#81;;1'   (18)
4=!\@,@'{#855+*:1' (P)
5=!\@,@'{#55+:1'   (newline)

In this program, =!\@,@'{# is what separates the function number with the code, and }, will call whatever function is on top of the stack.

Turing completeness

Proof by emulation of Bitwise Cyclic Tag (actual code untested but principle is sound):

,Data string in order with 2 and 5 delimiter:
1[1[1[0[0[1[1[0[1[0[2[5,
,Command string in reverse order with 4 delimiter:
40101110101,
,Following is the actual BCT interpreter:
4}\=!@,6,
{#,
,<
0}\>\@,@'{#{#['
#{#1}\>\@,@'[\[[311,1'
#{#1}\>\@,@'{#{<
#{#2}\>\@,@']}1,1'
#{#2}\>\@,@'{#}<
#{#3}\>\@,@'{##{1'
#{#4}\>\@,@']<
#{#5}\>@,[1111111'
1

External resources

• Karma Interpreter written in D