If I read the spec correctly, this is not necessarily Turing complete because there is only one stack and the number is not explicitly unbounded. (You can achieve TC with two stacks of bounded numbers or one stack of unbounded numbers though.) In particular JavaScript implementation uses an ordinary JS number, which is essentially bounded. The original TC claim [1] seems dependent to another language (Volatile) which uses explicitly unbounded numbers.
I assume the other way, if integers aren't limited, assume they are unbounded. They are in the Python implementation.
If you start worrying about implementation bounds, C gets iffy -- pointers have to have a known size, and be convertable to and from integers, so you cant have unbounded memory in any given implementation (you can get closer with files, but files still have offsets which imply limited maximum size, and there is a limited space of possible strings to name files).
That's true for any language. Computers are finite state machines, though with a lot of states, therefore no actual computer can really run a Turing complete language. As many mathematical things, Turing completeness is an abstraction that doesn't really map on reality without caveats.
You are correct. For this reason esolang community actually has defined a related concept called bounded-storage machine (BSM) [1]. C has a bounded memory but it can simulate an arbitrary large BSM by increasing memory and thus pointer size, so it is very close to (but not exactly) TC.
By comparison SSL has two axes of bounds (stack length bounds and number bounds), only one of which is useful for simulating an arbitrary large BSM. I would say it is also close to TC but less so than C, because you need number bounds proportional to the max memory of simulated BSM and it is much easier to hit number bounds than stack length bounds.
But wouldn't that require additional instructions to exchange values between the two stacks? Otherwise you'd basically just run two independent programs at the same time. In theory you could just replace a single letter's functionality with "push first element to other stack". v and w are redundant, for example.
You can put only ones and zeros to two stacks and branch against one stack to manipulate another stack. This is enough for simulating a two-symbol tape and thus any TM operating on that tape.
Neat! SSL is similar to Forth and Slash/A in that any of them could easily serve as the ”DNA” of “organisms” in linear genetic programming (a paradigm in which organisms are programs represented as strings which evolve via mutation and crossover).
I created an esolang in Mathematica to test out genetic programming, by ruling out possibility of infinite looping, implementing mutation and crossovers to result in a program that would convert a list of numbers to a target number. Even a naïve implementation worked, which was pretty neat!
No backward jumps. It was a language with a single register (accumulator) and various arithmetic functions that would let it advance a certain number of steps on the tape, or add/multiply/subtract from the accumulator accordingly.
It is possible to implement a real forth in this language.. but it would be as slow as molasses in January. You can get the depth of the stack, you can swap arbitrary positions of the stack, and do math... so you could build a system of fixed allocation of memory IN the stack, which means you could then compile new definitions
The interpreter doesn't add like forth... it leaves the 2 values to be added still on the stack... you have to do "glblb" to do a normal add, for example.
A fun exercise, but not a language I'd want to work with.
Edit: Specifically missing are any ways to persist variables, or allocate memory. Yes, you could fake all of that with some very careful coding, but a single mistake or clear stack (y) would send it all tumbling down.
Here's an interesting puzzle: is SSL Turing-complete? This is a non-trivial question. On the one hand, it is known that single-stack machines are not Turing-complete. On the other hand, perhaps one of the SSL primitives is enough to make it Turing-complete? If so, which one?
As nested pairs I would think. That is, when jumping forward from t to u scan the program incrementing a counter each time you see a t and decrement when you see a u, when the counter goes negative you have reached the matching u.
But what is supposed to happen when there is no matching u? Undefined like C and so implementation dependent? Or is the documentation just a summary and the real specification is the Python implementation?
In fact looking at the Python on the esolang site that is what happens and if there is no matching u then the program counter will have advanced beyond the end of the program and the program terminates. Going back fro u to t is slightly different in that if there is no matching t then it will simply continue from the first instruction.
Language design is difficult even for seemingly simple languages.
29 comments
[ 3.5 ms ] story [ 74.9 ms ] thread[1] https://esolangs.org/w/index.php?title=StupidStackLanguage&d...
If you start worrying about implementation bounds, C gets iffy -- pointers have to have a known size, and be convertable to and from integers, so you cant have unbounded memory in any given implementation (you can get closer with files, but files still have offsets which imply limited maximum size, and there is a limited space of possible strings to name files).
By comparison SSL has two axes of bounds (stack length bounds and number bounds), only one of which is useful for simulating an arbitrary large BSM. I would say it is also close to TC but less so than C, because you need number bounds proportional to the max memory of simulated BSM and it is much easier to hit number bounds than stack length bounds.
[1] https://esolangs.org/wiki/Bounded-storage_machine
Curious: Does that make the language easier to use in any way? (“Easier” here being very relative of course)
https://en.m.wikipedia.org/wiki/Linear_genetic_programming
How? No while loops? No backwards jumps? Or something clever? :-)
The interpreter doesn't add like forth... it leaves the 2 values to be added still on the stack... you have to do "glblb" to do a normal add, for example.
A fun exercise, but not a language I'd want to work with.
Edit: Specifically missing are any ways to persist variables, or allocate memory. Yes, you could fake all of that with some very careful coding, but a single mistake or clear stack (y) would send it all tumbling down.
This seems especially prone to some kinds of nasty bugs if you're not careful with what you're doing:
Would you like to save your progress? [y/n] >> y
Obviously not the first nor the last. Lots of room for expansion and syntax pre-compilers.
But what is supposed to happen when there is no matching u? Undefined like C and so implementation dependent? Or is the documentation just a summary and the real specification is the Python implementation?
In fact looking at the Python on the esolang site that is what happens and if there is no matching u then the program counter will have advanced beyond the end of the program and the program terminates. Going back fro u to t is slightly different in that if there is no matching t then it will simply continue from the first instruction.
Language design is difficult even for seemingly simple languages.