Talk:FALSE
From Esolang
Contents |
[edit] Inspiration
Was False really what inspired those other esolangs? --Ihope127 16:13, 9 Oct 2005 (GMT)
- It depends on how you define 'inspired'. It seems plausible that Urban Mueller was aware of False, as the original assemblers for each were for 68k architectures, and so he may have seen it and was determined to do better in terms of smallest assembler. Of course, for a sufficiently loose definition of 'inspired', you could argue that INTERCAL inspired every other esoteric programming language. --Safalra 16:30, 9 Oct 2005 (GMT)
- I don't know about Befunge (but I guess Chris could clarify that), but it seems to be generally recognized that False was what inspired Urban to create Brainfuck. I seem to remember having seen a quote form Urban somewhere about that, but I can't remember where (I could be completely wrong here). --Rune 20:59, 9 Oct 2005 (GMT)
- I checked out the False homepage, and it lists both Befunge and Brainfuck as languages inspired by False. --Rune 21:03, 9 Oct 2005 (GMT)
[edit] Computational Class
Suppose we call the bottom N values on the stack the "working stack". N can be arbitrarily large, large enough to hold all the values needed to solve the problem at hand. The actual stack size can be larger than N, but no values beyond N are needed. Consider the following:
Variable a holds N.
Variable b holds the index (0-based) of the stack element one wants to change.
Variable c holds the new value for the stack element.
The code fragment
a;[$0>][a;ø\1-$b;=[\%c;\]?]#%
will re-create the working stack with the desired change. The original N stack values will remain just above the working stack (as will anything that was above the previous working stack). Thus, for every change to the working stack, N useless values will be placed on the stack.
The following demonstration code can be tried on the JavaScript FALSE Interpreter in classic mode:
{ Create an initial stack }
110 109 108 207 106 105 104 103 102 101 100
{ a is the size of the desired stack to keep (10 values in this case)
b is the value to change (8th value in this case)
c is the value to change to (change to 7) }
11a: 7b: 107c:
{ now re-create the stack with the change }
a;[$1>][a;<\$b;=[\%c;\]?1-]#
A brainfuck interpreter written in FALSE would obviously eat up enormous amounts of memory (given how often one has to change the stack to do anything in brainfuck), but it seems that it would be possible. Thus, FALSE is probably Turing complete.
[edit] Update
Here is a one-for-one translation from brainfuck to FALSE.
First, initialize FALSE with the following code:
{ setup: create an array (tape) of length 1 and value 0
store array length in a
store array pointer (location) in b }
0a:0b:0
{ the c procedure cycles through the a values in the stack
using d as a countdown counter. When d = b, the procedure
in e is executed }
[[d;1_>][a;øb;d;=e;?d;1-d:]#]c:
{ store the BF + procedure in f }
[a;d:[1+]e:c;!]f:
{ store the BF - procedure in g }
[a;d:[1-]e:c;!]g:
{ store the BF > procedure in h }
[b;1+$b:a;>[0a;d:b;a:[]e:c;!]?]h:
{ store the BF < procedure in i }
[b;1-$b:1_=[a;1+a:0b:0]?]i:
{ store the BF . procedure in j }
[b;ø,]j:
{ store the BF , procedure in k }
[a;d:[%^]e:c;!]k:
{ store the BF [] procedure in m }
[b;ø0=~]m:
Then just translate brainfuck code and append the to the initialization code according to the following translation:
+ -> f;! - -> g;! > -> h;! < -> i;! . -> j;! , -> k;! [ -> m;[ ] -> ]#
The following FALSE script was created using the above method to translate the brainfuck "Hello World!" example. It can be pasted into the JavaScript FALSE Interpreter and run in classic mode ("ø"s are changed to "<"s):
0a:0b:0
[[d;1_>][a;<b;d;=e;?d;1-d:]#]c:
[a;d:[1+]e:c;!]f:
[a;d:[1-]e:c;!]g:
[b;1+$b:a;>[0a;d:b;a:[]e:c;!]?]h:
[b;1-$b:1_=[a;1+a:0b:0]?]i:
[b;<,]j:
[a;d:[%^]e:c;!]k:
[b;<0=~]m:
h;!f;!f;!f;!f;!f;!f;!f;!f;!f;!
m;[i;!f;!f;!f;!f;!f;!f;!f;!f;!h;!g;!]#
i;!j;!h;!f;!f;!f;!f;!f;!f;!f;!
m;[i;!f;!f;!f;!f;!h;!g;!]#
i;!f;!j;!f;!f;!f;!f;!f;!f;!f;!j;!j;!f;!f;!f;!j;!h;!h;!h;!
f;!f;!f;!f;!f;!f;!f;!f;!
m;[i;!f;!f;!f;!f;!h;!g;!]#
i;!j;!h;!h;!h;!f;!f;!f;!f;!f;!f;!f;!f;!f;!f;!
m;[i;!f;!f;!f;!f;!f;!f;!f;!f;!f;!h;!g;!]#
i;!g;!g;!g;!j;!i;!i;!i;!i;!j;!f;!f;!f;!j;!g;!
g;!g;!g;!g;!g;!j;!g;!g;!g;!g;!g;!g;!g;!g;!j;!h;!h;!f;!j;!
It creates a FALSE stack of 1285 values, of which only the top 5 are needed :-). --Nthern 20:54, 20 June 2007 (UTC)
- This all seems pretty cool. I don't have any experience on False (and no time to start learning and going through your code), but I just wanted to ask that does it matter in this if N can't be arbitrarily large -- as according to the specs it can't, as "all variables (and also stack-items) are 32bits.", and thus variable a can't hold it. But perhaps there are ways around this. Good work, anyways. :) --Keymaker 21:31, 20 June 2007 (UTC)
- I think it does matter. That 32 bit limit means that you can't access a stack value beyond value # 2^31 (assuming signed integers) unless you delete stack items and, hence, destroy some of your data. 2^31 places is a pretty big stack, nevertheless. I think it's a moot point anyway, for two reasons:
- 1) The original implementation of FALSE is dead unless you're programming on an Amiga. If I were to re-implement FALSE (and I probably will), I would likely create additional features such as random stack write access.
- 2) The spirit of esoteric languages is more concerned with a language's design than with practical limits.
- --Nthern 16:14, 22 June 2007 (UTC)
- Hardly a moot point in my opinion, as it means FALSE isn't Turing-complete -- or at least can't be proven so this way. Yes, agree with your point about the spirit of esolangs; languages allowing infinite values often have limitations in their interpreters (and who has seen infinite memory?), but in this case the language was defined to have limited variable range -- the author could've said that it's just an implementation issue, that really the language has unbounded variables -- yet he didn't, instead he said what I quoted above in my earlier reply, and thus I take it that the variables are not meant to be unbounded. So... Let's see... There's one infinite stack, finite variables -- not enough for Turing-completeness because it can't be accessed well enough. But -- what about FALSE's lambda functions? Are those, combined with the other forms of storage, enough? Too bad I don't know anything about that stuff. --Keymaker 18:18, 25 June 2007 (UTC)
- FALSE does not have any way to create new lambda functions not in the source, so those don't help. --Ørjan 09:16, 26 June 2007 (UTC)
[edit] JavaScript interpreter updated
I updated the interpreter to fix some browser compatibility problems and make the interpreter a little more usable.
- Added both Classic/Ian's prime number finder for comparison.
- Each sample on the page has a button to copy the source and set the correct Classic/Ian's interpreter.
- I broke down and filled in the classic PICK (ø) and FLUSH (ß) for both interpreters. (Doesn't need '<' anymore.)
- Classic '.' doesn't append a space.
- Better Firefox compatibility.
- Some refactoring: seek() and matching_brace() return new instruction pointer for fewer side-effects.
--IanO 23:40, 18 August 2007 (UTC)
