Simple Stack is a minimalist stack-based programming language. During execution, there is a data 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; the name is separated from the commands and the commands from each other whitespace (the whitespace is only necessary between words; it can be omitted before and after ! and .). There are three possible commands:
,), exclamation point (!), and period (.).
. pops a word off the top of the stack and discards it. If the stack is empty, prompts for input as described in the next section.
! pops a word off the top of the stack and executes it. If the word that was popped was the name of a procedure, calls that procedure and then continues with the next command when the procedure finishes; otherwise, prints the word. If the stack is empty, prompts for input.
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!.
Starting in version 1.1, if you try to pop an element off the data stack and the stack is empty, the program will prompt for input. The input is then split into words, and each word has an apostrophe (') prepended to it, so hello world becomes 'hello 'world (this allows the same word to be used as input and as output). Then the words are pushed onto the stack in reverse order, so the first word entered is the first item popped. The command that tried to pop the word is then re-executed. There is no way of determining when a line ends.
In version 1.0, popping from the data stack when it's empty was a runtime error. This means that any 1.0 program that didn't cause an error will work the same in 1.1, and if you're running a 1.0 program and it prompts for input, you can treat it as if it's an error. You can run a 1.1 program in a 1.0 interpreter if you put the input reversed with apostrophes at the beginning of main (though if main calls itself, you'll need to move that to a new procedure).
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 square 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.
Each case in a switch statement becomes its own command, with a name containing brackets (which is allowed in the lower-level language but can't conflict with any possible names in the higher-level language). Each enum values becomes a procedure that pushes all commands for the cases selecting that value onto the stack. The switch statement executes the top of the stack (pushing all the commands onto 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 of the case commands.
For instance,
[true false], print [true yes!, false no!], not [true false, false true]
translates to something like
true true[1] true[0], false false[1] false[0], print ! !, 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.
main Hello! world!
Pushes Hello onto the stack, then pops it and prints it, and does the same thing for world.
main ! main!Copies the input to the output. The exclamation mark at the beginning reads the next word of input, and then main! recurses. Note that each word is prefixed by '.
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.
[+ '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.
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 (reading 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.
Simple Stack 1.0 is available here.
Version 1.1 adds/changes the following:
Note that the higher-level version was around since I started the language; it's not a later addition.
Run the program:
Execute operations every seconds.
Output:
Data stack
Call stack