Talk:Spl
Jump to navigation
Jump to search
I don't think this is a push-down automaton. A PDA only has a finite number of values that can be put on the stack, while you have both lists and functions. For computation input can be embedded in the program. I suspect it is already Turing-complete like Underload, a simpler similar language. --Ørjan 10:29, 13 September 2009 (UTC)
- I think you're right; thanks! Also, I'm interested to note that Underload uses the same symbol as I do, ~, for the "swizzle" operator. soundandfury 10:38, 13 September 2009 (UTC)
- Thinking about it, I don't think spl is essentially a superset of Underload, since Underload programs are a single line and can freely put arbitrary code onto the stack, whereas spl has function calls, and can only put variables onto the stack, so the method of flow control is different. spl unforced functions are more like "promises" in Unlambda, really. soundandfury 10:48, 13 September 2009 (UTC)
- Promises with ordered sets as arguments are similar enough to Underload code-strings that it might be possible to do a mapping from Underload to spl; if you could implement Underload's ^ somehow, you'd probably be done. I don't think there's an obvious way to do the mapping; but I think it's entirely plausible that there's a non-obvious way. (You would probably have to effectively embed a mini-Underload interpreter into the spl program.) --ais523 19:55, 14 September 2009 (UTC)
- Well, we'll find out spl's class (fairly) soon, because I'm attempting to write a Brainfuck interpreter in it (I put some details in the article on how to make user-stacks, and I think I can do it using two stacks for 'cells to left of pointer' and 'cells to right of pointer', and doing something similar with the code. The looping will be harder, because matching up the brackets correctly will involve keeping a count). If it works, then spl is Turing-complete, because BF is. As for Underload, don't forget that in spl, the function is bound to its argument with the %, not the f, so there's no equivalent to (something^) in spl. (As soon as you mention a function, you give its argument; you can't supply the argument at force time) However, if spl is TC, then of course you can compile Underload to it, but it wouldn't necessarily be easy. soundandfury 20:43, 14 September 2009 (UTC)
- The stack's global, isn't it? Arguments to functions are given on the global stack in Underload, and it would be easy enough to mirror that in spl. --ais523 22:09, 14 September 2009 (UTC)
- No, the stack's not global. (I probably should have made that clearer). Each function, when forced, gets its own stack, which initially has only its argument on it. Actually, that's a lie: initially, the stack is empty; the first time the stack underflows and there is no more code to read, the argument is pushed, and evaluation re-attempted. soundandfury 22:25, 14 September 2009 (UTC)
- OK, that sounds evil. So you cannot pass new information to already constructed functions in any way, I take (except by reading input, which doesn't help.) I guess that ruins my idea that you could easily do combinatory logic (which Underload's proof uses) in it. --Ørjan 13:00, 15 September 2009 (UTC)
- It is pretty evil, but it's like that to make the interpreter easier. Yes, you can't pass information after the % call. The only uses of functions are delaying side effects and producing recursion (recursion is the only way to loop in spl). So far as I can see, there's no easy way to implement SK logic. However, as I mentioned above, I'm working on a BF interpreter; it's proving very difficult. 87.243.208.102 19:56, 15 September 2009 (UTC)
- OK, that sounds evil. So you cannot pass new information to already constructed functions in any way, I take (except by reading input, which doesn't help.) I guess that ruins my idea that you could easily do combinatory logic (which Underload's proof uses) in it. --Ørjan 13:00, 15 September 2009 (UTC)
- No, the stack's not global. (I probably should have made that clearer). Each function, when forced, gets its own stack, which initially has only its argument on it. Actually, that's a lie: initially, the stack is empty; the first time the stack underflows and there is no more code to read, the argument is pushed, and evaluation re-attempted. soundandfury 22:25, 14 September 2009 (UTC)
- The stack's global, isn't it? Arguments to functions are given on the global stack in Underload, and it would be easy enough to mirror that in spl. --ais523 22:09, 14 September 2009 (UTC)
- Well, we'll find out spl's class (fairly) soon, because I'm attempting to write a Brainfuck interpreter in it (I put some details in the article on how to make user-stacks, and I think I can do it using two stacks for 'cells to left of pointer' and 'cells to right of pointer', and doing something similar with the code. The looping will be harder, because matching up the brackets correctly will involve keeping a count). If it works, then spl is Turing-complete, because BF is. As for Underload, don't forget that in spl, the function is bound to its argument with the %, not the f, so there's no equivalent to (something^) in spl. (As soon as you mention a function, you give its argument; you can't supply the argument at force time) However, if spl is TC, then of course you can compile Underload to it, but it wouldn't necessarily be easy. soundandfury 20:43, 14 September 2009 (UTC)
- Promises with ordered sets as arguments are similar enough to Underload code-strings that it might be possible to do a mapping from Underload to spl; if you could implement Underload's ^ somehow, you'd probably be done. I don't think there's an obvious way to do the mapping; but I think it's entirely plausible that there's a non-obvious way. (You would probably have to effectively embed a mini-Underload interpreter into the spl program.) --ais523 19:55, 14 September 2009 (UTC)