Functasy
| Paradigm(s) | Functional |
|---|---|
| Designed by | Hakerh400 |
| Appeared in | 2019 |
| Computational class | Turing complete |
| Major implementations | Interpreter |
| File extension(s) | .txt |
Another programming language inspired by the lambda calculus concepts. The main difference is that Functasy doesn't allow grouping (all function calls are performed left-to-right linearly (not to be confused with function definition grouping)).
Syntax
Source code consists only of spaces, numbers and parentheses. Other characters are not allowed. Numbers represent identifiers and parentheses represent functions. For example
(0(1)())((1 0 1(())1))
Here we have two global functions (0(1)()) and ((1 0 1(())1)) and several nested functions. Each identifiers has a reference to the argument that is passed when the function is called. Identifier 0 references the argument of the most inner function, identifier 1 references the argument of the wrapper of the most inner function, etc. Identifier should not be larger than the nested level, which means we can use 0 only if we are in at least one function, we can use 1 only if we are in at least two functions, etc.
Evaluation
Evaluation happens from left to right. Two consecutive elements (element is either an identifier or a function) represent function call - the first element is called with the second element as the only argument (all functions take exactly one argument, which may or may not be used in the function body). Then the result is called with the third argument, then fourth, etc.
Meta function
Empty function () is also called "meta function". It has special behavior. Depending on the place where it appears, there are 6 different cases:
- If it is the only element in the parent function, i.e.
(())- then return meta function as result - If it is the first element and the second element is an identifier, i.e.
(()0)- then output bit 1 and save the value of the identifier as the result - If it is the first element and the second element is a function, i.e.
(()(0))- then input next bit, if it's 0 then return the identifier, otherwise call the identifier with meta and save the result - If it is neither the first nor the last element and the next element is an identifier, i.e.
(0()0)- then assign the previous result to the identifier and keep the result unchanged - If it is neither the first nor the last element and the next element is a function, i.e.
(0()(0))- call the next element with the result as the only argument - If it is the last element, but not the only element, i.e.
(0())- output bit 0 and keep the result unchanged
Meta function can't be called directly, but when called it returns itself.
I/O format
The same I/O format as described here.
Examples
Basic examples
Output bit 0
(0())(0)
Explanation: in order to output bit 0, we must construct beforementioned case 6. However, we can't use any identifiers in the global scope, so we need to wrap it in a function and then invoke the function with (0) as the argument. Function (0) is the identity function - it returns the same argument it receives. We could also achieve it without any identifiers:
(())()
This code also outputs bit 0, as case 6 doesn't specify what the type of the previous element must be, so it can be either an identifier or a function. We couldn't do
()()
because then case 3 applies first and depending on the input bit the second meta function is either called or not, but anyway doesn't affect the result. This last example doesn't output anything.
Output bit 1
Now we must use identifiers, as case 2 explicitly states that the meta function must be the first element and the second element must be an identifier.
(()0)(0)
Another way we could do this is
(())(0)()(0 0)
This is a bit more complicated, but demonstrates several edge cases. On the left we have (()) - this is a function that ignores the argument and returns the meta function. The second global function is identity function. The first call that happens is when (()) gets called with (0) as the only argument. According to the case 1, the result is meta function.
Now, this is the important part: when meta function is returned as the result of some other call, it behaves like regular function and no special cases are applied. The next element is the third global function, which is (), so the case 5 applies: function (0 0) is called with the previous result as the only argument. The previous result was the meta function (returned by (())), so (0 0) is called with the meta function as argument. Note: we applied the case 5, but not on the meta function that was returned as the result.
Going further: identifier 0 now has the value meta function in the current scope. However, because 0 is actually meta function, case 2 applies and the program outputs bit 1.
Infinite loop
(0 0)(0 0)
Nothing special to explain here. We have a function that calls itself indefinitely. A good interpreter should optimize this to keep the memory at the same level and doesn't trigger stack overflow or out-of-memory error.
Advanced examples
Cat + Hello world
This program first outputs the input, then outputs the standard hello world string. It can be simplified a lot, but the intention here is to cover the majority of edge cases.
((((((((((9 9()0 0((0))(0)0 1 0(2)((0 11 2 0 2(4)1 0))0 2 0(2)((0))0 9 0(2)((1))0 8 0(2)(((1)2 9 2(4)(2 12 3 0 3(5) 2 12 3 1 3(5)0)2 8 2(4))1(4 0)(1 11))(10 1 0 1(3)1(2(11 3 2))1(3)0)0(2)(0(2 11)(11 2)10)0 5 0(2)(((10 0(9 4(7 0) (11 0)4(6)2 0)12 0)2 0 2(4)0 0)0)9)0)0)0)0)0)0)0)0)0)(())()((0))((((((((((9 9()0 0((0))(0)0 1 0(2)((0 11 2 0 2(4)1 0)) 0 2 0(2)((0))0 9 0(2)((1))0 8 0(2)(((1)2 9 2(4)(2 12 3 0 3(5)2 12 3 1 3(5)0)2 8 2(4))1(4 0)(1 11))(10 1 0 1(3)1(2 (11 3 2))1(3)0)0(2)(0(2 11)(11 2)10)0 5 0(2)(((8 0 3(5)1)2 0 2(4)0 11 11 11 10 11 11 10 11 10 11 10 11 11 10 10 11 11 11 10 10 11 10 10 11 11 11 10 10 11 10 10 11 10 10 10 10 11 10 10 11 11 11 10 10 11 10 11 11 11 11 11 11 11 10 11 11 10 10 10 11 10 11 10 11 10 10 10 10 11 10 10 11 11 10 11 11 10 10 10 11 11 11 10 10 11 10 10 11 11 11 10 11 11 10 10 11 10 11 11 11 11 10)0)9)0)0)0)0)0)0)0)0)0)(())
Interpreters
The interpreter is very simple. This one is written in JavaScript and also has the ability to optimize recursion, so that the memory doesn't grow at all.
const run = (source, io) => { let s = [[]]; // Stack let e = 0; // Element // Tokenize and iterate over tokens for(let t of source.match(/\d+|[\(\)]/g) || []) t === ')' ? (e = s[0], s = s[1]) : (e = e ? e[2] = [] : s[0][1] = [], t === '(' ? (s = [e, s], e = 0) : e[0] = -~t); // Initial invocation parameters let inv = [0, [0, e = s[0][1]], 0, e]; let e1, e2; // Some useful functions const ret = clos => (inv = inv[0]) && (inv[4] = clos); const next = e => ((e = inv[3]) && (inv[3] = inv[3][2]), e); const tc = e => e ? e[0] ? fetch(e[0]) : [inv, e[1]] : 0; const call = (func, arg) => inv = [ inv[3] ? inv : inv = inv[0], func, arg, func[1]]; const fetch = (i, j) => { let k = inv; while(--i) k = k[1][0]; return j ? k[2] = j : k[2]; }; // The main program loop while(inv) (e1 = inv[4], e2 = next()) ? tc(e2)[1] ? e1 ? call(e1, tc(e2)) : inv[4] = tc(e2) : (e2 = next()) ? e2[0] ? e1 ? fetch(e2[0], e1) : (io.write(1), inv[4] = tc(e2)) : e1 ? call(tc(e2), e1) : io.read() ? call(tc(e2), []) : inv[4] = tc(e2) : e1 ? io.write(0) : ret([]) : ret(e1 || []); };
Function run takes argument source and io. Argument source is ascii string representing the program's source code, while io is an object that has methods read and write.