Simple Stack 1.0

Simple Stack is a minimalist stack-based programming language. During execution, there is a single stack; all operations manipulate this stack. There is also a call stack, so the program can return from a procedure call. However, there are no local variables, or for that matter, any variables at all.

A program is a series of procedure definitions, separated by commas. A definition is a name, followed by zero or more commands (separated by whitespace). There are three possible commands:

There is no direct support for comments; however, you can achieve the same effect by defining a procedure that you never call (though be careful about commas, since those end the procedure).

When the interpreter starts, the stack is empty, and it'll execute the command main!.

Simple Stack Higher-Level

To make programming easier, there's also a slightly higher-level version of Simple Stack that can fairly easily be compiled to the lower-level version. This variant adds support for enums and switch statements to examine them, and reserves the characters [ and ]. Programs that do not include brackets are the same in both versions of the language.

Programs are now a list of procedure and enum definitions. Enum definitions are just a list of values in brackets (no commas between the values, though the whole definition is separated from other definitions by commas). Enum types don't have names. Enum values should only be defined once, and should not have the same name as a procedure.

An additional command type is allowed: a list, in square brackets, of the form [name1 commands, name2 commands, name3 commands...]. The set of names must be the same as an enum that's been declared. This command pops the current value (which must be one of the specified names, otherwise behavior is undefined) and executes the corresponding list of commands.

Translation to lower-level

Each case in a switch statement becomes its own command, with a name containing brackets (thus not conflicting with any possible names in the higher-level language). The enum values are all procedures that push all commands for the cases selecting that value onto the stack. The switch statement executes the top of the stack, then pops enough off to get to the right command, and executes it. The commands for the cases then pop off the rest.

For instance, 

[true false],
foo [true yes!, false no!],
not [true false, false true]

translates to something like 

true true[0] true[1], false false[0] false[1],
foo ! . !, true[0] yes!, false[0] no!,
not ! !, true[1] . false, false[1] . true

where the names true[0], true[1], false[0], false[1], and the order in which they're pushed onto the stack, are implementation-dependent.

Examples

Hello, world 

main Hello! world!

Pushes Hello onto the stack, then pops it and prints it, and does the same thing for world.

Fibonacci 

a ! *! b,
b ! a b,
end end,
mainloop ! |! mainloop!,
main end b mainloop!

Prints the Fibonacci series; with each number represented by a sequence of asterisks (*); and the numbers separated by vertical bars (|). The output should start: | * | * | * * | * * * | * * * * * | * * * * * * * * ...

The current state is represented by the contents of the stack; the number of a's on the stack represents the current value, and the number of b's on the stack represents the next value. The program pops all the a's and b's off the stack (until it gets to end) while remembering them in the call stack, and then pushes the correct number of a's and b's for the next iteration as each procedure returns.

New number of a's = old number of b's, new number of b's = old number of a's + old number of b's, so b is replaced by a b and a is replaced by b.

Binary addition 

[+ '0 '1 '10],
find-next-number
[+ [+ + + '0, '0 + '0, '1 + '1, '10 error1!],
 '0 find-next-number! [+ error2!, '0 '0 '0, '1 '0 '1, '10 error3!],
 '1 find-next-number! [+ error4!, '0 '1 '0, '1 '1 '1, '10 error5!],
 '10 find-next-number! [+ error6!, '0 '10 '0, '1 '10 '1, '10 error7!]],

carry
[+ + '1, '0 '1, '1 '10, '10 error8!],

result=0 add! 0!,
result=1 add! 1!,
result=10 carry! add! 0!,
result=11 carry! add! 1!,
print-rest [+, '0 print-rest! 0!, '1 print-rest! 1!, '10 error9!],

add
[+ print-rest!,
 '0 find-next-number! [+ error10!, '0 result=0!, '1 result=1!, '10 error11!],
 '1 find-next-number! [+ error12!, '0 result=1!, '1 result=10!, '10 error13!],
 '10 find-next-number! [+ error14!, '0 result=10!, '1 result=11!, '10 error15!]],

main
1001+111=! + '1 '0 '0 '1 + '1 '1 '1 add!
1010+1010=! + '1 '0 '1 '0 + '1 '0 '1 '0 add!
1000+1=! + '1 '0 '0 '0 + '1 add!
1+1000=! + '1 + '1 '0 '0 '0 add!
1011010+1101100=! + '1 '0 '1 '1 '0 '1 '0 + '1 '1 '0 '1 '1 '0 '0 add!

Adds two binary numbers together. This can be extended to higher bases, but would require a lot more typing. Digits are expressed by an enumerated type, which also includes + (which separates the two numbers and marks the start of the input) and '10 (which can occur in the last digit of the second number after carrying).

The program starts at the end of the second number (which is the top of the stack). find-next-number brings the last digit of the first number to the top of the stack (after the second number), so that add can look at it and decide the result. Once it finds the result, it remembers it on the call stack and then adds the rest of the number; once that's done, it prints the digit.

Turing machine 

end-of-tape end-of-tape :0!, [:0 :1], [s1 s2 s3 s4 s5 halt],

s1:0 :0 halt,
s1:1 [:0 s2:0!, :1 s2:1!] [s1 s1:0!, s2 s2:0!, s3 s3:0!, s4 s4:0!, s5 s5:0!, halt halt:0!],

s2:0 [:0 s3:0!, :1 s3:1!] [s1 s1:0!, s2 s2:0!, s3 s3:0!, s4 s4:0!, s5 s5:0!, halt halt:0!],
s2:1 [:0 s2:0!, :1 s2:1!] [s1 s1:1!, s2 s2:1!, s3 s3:1!, s4 s4:1!, s5 s5:1!, halt halt:1!],

s3:0 :1 s4,
s3:1 [:0 s3:0!, :1 s3:1!] [s1 s1:1!, s2 s2:1!, s3 s3:1!, s4 s4:1!, s5 s5:1!, halt halt:1!],

s4:0 :0 s5,
s4:1 :1 s4,

s5:0 [:0 s1:0!, :1 s1:1!] [s1 s1:1!, s2 s2:1!, s3 s3:1!, s4 s4:1!, s5 s5:1!, halt halt:1!],
s5:1 :1 s5,

halt:0 :0 halt,
halt:1 :1 halt,

print-result [:0 0!, :1 1!] print-result!,

main
end-of-tape :1 :1 s1:1! .
print-result!

Shows how one could implement a Turing machine by implementing one of the Turing machine examples from Wikipedia. Since the method used here could be used for any Turing machine (at least, those that only expect the tape to be unbounded in one direction), this shows that Simple Stack is Turing-complete.

A tape (like in a Turing machine) can be simulated with two stacks; it just so happens that we have two stacks in this language: the data stack and the call stack. Values to the right of the cursor are stored in the data stack (as :0 and :1; we need 0 and 1 by themselves for outputting), and values to the left of the cursor are stored in the call stack.

For states that move to the right, we have to call a procedure to transition to the next state. (That procedure needs to know what the next symbol is, so we pop the stack to find it.) When that procedure returns, we know that the read/write head has come back to the cell we were supposed to write, so we pass the value we're supposed to write to the next state. (Of course, we need to read the next state from the stack.)

For states that move to the left, we just have to push the new value onto the stack, and also push the next state onto the stack so that the procedure we're returning to knows which state to transition to.

Interpreter

Program:

Run the program:

Execute operations every seconds.

Output:

Call stack:

Data stack: