Talk:FALSE
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)
- In the context under which it was released, it was pretty clear (to me anyway) that brainfuck was Urban's "response" to Wouter's "hey look how ridiculously small this compiler is" release of FALSE. Befunge was inspired by both of these languages, not in terms of having a small compiler of course, but in terms of "hey look we can design gawd-awful languages for fun" (I had not heard of INTERCAL at the time.) --Chris Pressey 05:27, 17 November 2010 (UTC)
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.
- Oh God! Having in mind quantum theory concepts, I like the way FALSE is kind of a paradox respecting Turing completeness: complete? not-complete? complete? not-complete? ... and so on. Kind of "Turing´s cat"? ;-) --Quezadav (talk) 19:43, 25 May 2012 (UTC)
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:
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)
- The phrase "all variables (and also stack items) are 32 bits" doesn't restrict the size of the stack. Every element of the stack should (if we are adhering to the 32bit limit) be 32bit, but the size of the stack itself is not a False variable or stack item, so isn't so restricted. With this interpretation, the stack can be arbitrarily large. With no restriction on stack size, the approach outlined above of duplicating the entire working stack to simulate a deep stack change is enough to show Turing completeness. However, all data, including N as above, have to be stored on the stack in some bignum format. --Morph 05:45, 24 October 2010 (UTC)
;and:can be used for peeking and poking the memory when supplied with any int32 value (https://strlen.com/files/lang/false/false.txt), but it still doesn't get around the fact that the accessible storage is limited. Besides, the stack is in the memory page (upper half of the OS stack actually), so you should be able to peek / poke easily if you hold a pointer variable storing the address of the stack.
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.)
- Better Firefox compatibility.
- Some refactoring: seek() and matching_brace() return new instruction pointer for fewer side-effects.
--IanO 23:40, 18 August 2007 (UTC)
A further update:
- Neither version of '.' append a space.
- The parentheses now push and pop to and from the return stack, like Forth's >R and R>. This makes the variant Turing complete.
- Noted that you can store to numeric values as well as the 26 letter variables (a JavaScript side-effect).
--IanO 19:16, 2 May 2009 (UTC)
The referenced page now only interprets FALSE. The DUP variant is on its own page. --IanO 01:16, 30 September 2009 (UTC)
Unix's dc calculator
The FALSE language is quite similar to the dc desk calculator. For example, both languages are RPN and use [ ] for lambdas (which are just strings in dc). Unlike FALSE, the registers are any single character (so there's at least 255 or 256 of them), and each register is both an array and a stack. There's even a version of dc in sed, which uses dc to implement some of its own functions. There's also a program called bc, which is a yacc-based compiler for dc. It transforms infix assignments into postfix, allows function declarations (with 'auto' local variables), C-style loops, etc. It can probably be modified to compile into FALSE (or another similar language) instead. --(this comment by 69.54.60.34 at 18:01, 1 September 2010 UTC; please sign your comments with ~~~~)
Another trial to prove turing completeness
There is, in fact, two stacks in the FALSE language - the regular stack, and the calling stack. I think one can simulate a turing machine using these two stacks. You need to define 2 functions which correspond to the 2 values of a bit, and when you want to push a bit into the calling stack, you call the function that correspond to the value you want to push. Popping from the calling stack is pushing some data into the regular stack, and exiting the function. --84.229.128.137 12:15, 30 December 2010 (UTC)
- Looks promising to me. --Ørjan 20:02, 30 December 2010 (UTC)
- Lets look on the following description of an esoteric language, which we may call FH (FALSE helper):
- the memory consists of 2 stacks, each one can contain the values 0, -1.
- the program is a list of numbers which represents each one a command:
0 - push 0 into regular stack 1 - push -1 into regular stack 2 - push 0 into calling stack 3 - push -1 into calling stack 4 - drop from regular stack 5 - drop from calling stack 6 - unconditional jump to the (n+1)th number in the program, when n is the number following the 6 in the program 7 - like 6 but jumps only if at top of calling stack there is -1, and don't drop it 8 - halt. If you don't use 8 it may be an undefined behavior 9 - move a value from regular stack to calling stack 10 - input a character and push its bits (a 1 bit becomes -1) into the regular stack (high-order first) 11 - output a character from the regular stack (high order bit is the most inner) 12 - like 6 but jumps only if at top of calling stack there is 0, and don't drop it
- any other number, when trying to execute, is an undefined behavior.
- at 7,12, if the jump is not performed,then the number which follow them and marks the destination to jump, is not being executed. for example:
2 7 0 3 8
- would push 0 to the calling stack, check if it is -1 (it is not), so it is not jumps to the first (0+1) number (which is it 2), but it skips the 0 and arrive to 3.
- Back to FALSE, here is a description of an experimental semi-interpreter of FH. Let 'a' contain a function which gets a natural number (including 0) n and puts in the stack the (n+1)th number in the FH program, for example,if you want to execute the program
2 7 0 3 8
- you need to write:
[8\3\0\7\2\ø\%\%\%\%\%]a:
- the rest of the semi-interpreter is:
{Insert the program here by definition of 'a'.}
[
[e;f;&][
{ 12 }[d;1+a;!d:]
{ 11 }[d;1+d: _ \_2*+ \_4*+ \_8*+ \_16*+ \_32*+ \_64*+ \_128*+ ,]
{ 10 }[d;1+d: ^255&z: z;128&128/_ z;64&64/_ z;32&32/_ z;16&16/_ z;8&8/_ z;4&4/_ z;2&2/_ z;1&_ 0z:]
{ 9 }[d;1+d: $[\c\]?~[b]? ;!]
{ 8 }[0f:]
{ 7 }[d;2+d:]
{ 6 }[d;1+a;!d:]
{ 5 }[d;1+d:0e:]
{ 4 }[%d;1+d:]
{ 3 }[d;1+d:c;!]
{ 2 }[d;1+d:b;!]
{ 1 }[d;1+d:0~]
{ 0 }[d;1+d:0]
d;a;!ø
\%\%\%\%\%\%\%\%\%\%\%\%\%
!
]#0~e:
]b:
[
[e;f;&][
{ 12 }[d;2+d:]
{ 11 }[d;1+d: _ \_2*+ \_4*+ \_8*+ \_16*+ \_32*+ \_64*+ \_128*+ ,]
{ 10 }[d;1+d: ^255&z: z;128&128/_ z;64&64/_ z;32&32/_ z;16&16/_ z;8&8/_ z;4&4/_ z;2&2/_ z;1&_ 0z:]
{ 9 }[d;1+d: $[\c\]?~[b]? ;!]
{ 8 }[0f:]
{ 7 }[d;1+a;!d:]
{ 6 }[d;1+a;!d:]
{ 5 }[d;1+d:0e:]
{ 4 }[%d;1+d:]
{ 3 }[d;1+d:c;!]
{ 2 }[d;1+d:b;!]
{ 1 }[d;1+d:0~]
{ 0 }[d;1+d:0]
d;a;!ø
\%\%\%\%\%\%\%\%\%\%\%\%\%
!
]#0~e:
]c:
0~e:0~f:0d: [f;][b;!]#
- Explanation of the variables:
- Variable a holds the program to execute
- Variable b holds a function which represents a value 0 on the calling stack.
- Variable c holds a function which represents a value -1 on the calling stack.
- Variable d holds the current place in the program that needs to be executed
- Variable e is a flag that is usually holding -1, and it changes to 0 when there is a need to return from one function on the calling stack
- Variable f is similiar to e, but its effect is to halt the program
- Variable z is a temporary variable, used to save the key input when the command 11 is executed.
- 87.70.96.62 12:51, 11 January 2011 (UTC)
- Indeed such a call stack method does work. I had forgotten (well, at least consciously) about this discussion but pondered a similar question for Underload. Just after I solved that, an edit to the FALSE page reminded me of this discussion again, and it turns out all the Underload instructions I used have corresponding FALSE instructions! --Ørjan 00:24, 19 February 2011 (UTC)
- Very cool! I never would have thought of that. --Nthern 17:39, 20 July 2011 (UTC)
FC - FALSE C-like Compiler
I made a program I call FC, based on the bc source code, which is like a C-ish compiler for FALSE. It only uses one-character functions and variables, which are the same as FALSE variable names. It uses some weird notations like . and @ for representing certain values on the stack. You have to think of every variable as a 32-bit int or a function pointer (because that's all that FALSE supports). It allows named functions with proper return() (that allows returning up to two values using swap & rotate!), and allows up to 26 named parameters or dynamically-scoped local variables per function (the previous values are saved on the stack). You can't use def within a function, but you can use lambdas like a={function stuff}. It also works with the C preprocessor.
FC can use "asm" to put FALSE code directly into the program. A def statement with an empty prototype and no "auto" variables allows direct access to the stack without creating any stack frames. Inputs:
def a() {;asm "1+";}
Outputs:
[1+]a:
It properly handles ? : conditional operators and nested functions. Inputs:
def a(m,n){ /* Ackermann function */
"ack( ";m;", ";n;")
";flush
return(m==0?n+1:a(m-1,n==0?1:a(m,n-1)))
}
Outputs:
[n;1°n:m;3°m:"ack( "m;.", "n;.") "ßm; 0=$[n; 1+\]?~[m; 1-n; 0=$[ 1\]?~[m;n; 1-a;!]?a;!]?\m:\n:\%\%]a:
It also supports C-style pointers. Inputs:
def k(a,b){ /* function with pointers */
return(**a+*b)
}
p=20;i=&p;j=30;k(&i,&j)
Outputs:
[b;1øb:a;3øa:a;;;b;;+\a:\b:\%\%]k:20p:pi:30j:ijk;!.
This weird function is, in fact, proper FALSE. It works on the JavaScript interpreter and the reference interpreter.
If anyone's interested, I'll upload the EXE and/or the source.
(forgot to sign) Ian 23:24, 25 February 2011 (UTC)
- I'd personally love to see it. I can host the binary/source if you want. --EzoLang 21:42, 7 March 2012 (UTC)
- The file archive would probably be the best place to put the source. —ehird 21:43, 7 March 2012 (UTC)
Falsish
A FALSE superset inspired by fish ><>.
- Falsish can create new stacks, each with their own local (lowercase) variable array. The top N stack elements are transferred on creation. When dropped, the remaining elements are moved onto the next lower stack.
- Stacks are reversible, making them sort of deque-like, enhancing Turing completeness.
- Global variables are uppercase.
- Assembly is not supported. Instead, ` breaks out of the current function execution.
- other stack functions.
See: Falsish and Falsish interpreter in Python
See also: False interpreter in Python