Talk:Funciton

Praise

This language is a work of art, both syntactically and semantically. A superb effort. —ehird 05:43, 15 April 2011 (UTC)

Many thanks for your encouraging words! I am glad that someone took notice of this and bothered to respond :) — Timwi 11:48, 15 April 2011 (UTC)

Input

Could input be done by having a special kind of dangling end (another symbol, say) that denotes an input, possibly with a name? So the program would be a function from a predefined number of integers to an integer. —ehird 05:43, 15 April 2011 (UTC)

Yeah, actually a friend of mine just had the idea that the program could be a function declaration with an empty name. I’m a bit reluctant to making such fundamental changes though because my interpreter already works for the language as specified now. — Timwi 11:47, 15 April 2011 (UTC)

Implementation

By the way, are you planning to/in the process of implementing this language, or would you prefer to leave the task to someone else? —ehird 05:46, 15 April 2011 (UTC)

I have already implemented the part above “Possible future extensions”. (I wanted to make sure that it can actually work before I post it here.) I’ll publish the interpreter over the weekend (it currently uses a library that I’m not allowed to publish, I need to remove that dependency first). It is written in C# and it uses BigInteger values only. On my machine it can calculate factorial of 79 in less than a second, but 80 factorial causes a stack overflow exception. The Fibonacci function is extremely slow. — Timwi 11:47, 15 April 2011 (UTC)

Were it not for the horrific prospect of parsing this thing, I would have a go at implementing this; I wouldn't think it should be inherently slower or less practical to evaluate than e.g. doing arithmetic with Church numerals. Less so, actually, because you have proper log-storage/complexity (presumably) integers from the host machine. It sounds like you could work around the stack overflow by maintaining a stack yourself, but that'll probably be slower and also a real pain, code-structure-wise.

I wonder if any implementation of the CLI lets you adjust the stack limit? I wouldn't be surprised if Mono did, for instance. Of course you can only push it too far before running into implementation limits. —ehird 11:58, 15 April 2011 (UTC)

If you want something to do, how about a challenge? Implement the Ackermann function in Funciton :) — Timwi 16:00, 15 April 2011 (UTC)

Eek. Maybe when I'm not so tired :) Have you been managing the boxes by hand? Emacs' artist-mode will probably come in handy here, but a specialised editor would be vastly better than both... —ehird 16:23, 15 April 2011 (UTC)

So far I’ve been using a non-specialised text editor (Programmer’s Notepad). Virtual spaces and column-select are already a tremendous help. Of course I agree that a specialised editor would make it easier, but if you want to make it easier, you could as well just write the functions in C syntax... :) — Timwi 16:55, 15 April 2011 (UTC)

How does it decide what's an input and what's an output?

For example, in this example

  ╔═══╗              ╔═══╗              ╔═══╗
  ║ 1 ║ ╔════════╗   ║ 2 ║ ╔════════╗   ║ 3 ║
  ╚═╤═╝ ║ ↓ NAND ║   ╚═╤═╝ ║ ↓ NAND ║   ╚═╤═╝
    │   ╚════════╝     │   ╚════════╝     │
    └─────┬────────────┴─────┬────────────┘
          │ ╔════════════╗   │
          │ ║ splitter ↑ ║   │
          │ ╚════════════╝   │
          │     ╔════════╗   │
          │     ║ ↓ NAND ║   │
          │     ╚════════╝   │
          └───────┬──────────┘
                  │

how does it decide that those two gates near the top are NANDs? What stops the one near the left from splitting the number 1 downwards and rightwards, forming a NAND with the 2 that then forms a NAND with the 3? -- Smjg 11:42, 16 April 2011 (UTC)

You can’t split a number downwards and rightwards. The splitter outputs are always in opposite directions, and similarly the NAND inputs. If the parser finds two inputs or two outputs that are at right angles at a T-junction, it is a syntax error. (By contrast, the cross operator expects the inputs and outputs to be at right-angles. In that case, if two inputs are opposite each other, it is a syntax error.) You are right that without this restriction, the language would be highly ambiguous. — Timwi 14:37, 16 April 2011 (UTC).

Rotation invariant?

"This means you can take any program or any individual function declaration and turn it by 90° without altering its semantics or the semantics of anything that calls it."

This is effectively saying you can rotate any function, and it will still do the same even when the call isn't rotated. But for this to work, the implementation would have to know which way up a given function is relative to its caller. In most cases, this can be determined by the arrangement of input and output lines. But there's one ambiguous case: a function taking two inputs in opposite directions and returning two outputs in opposite directions perpendicular to the inputs. Is this illegal because of the ambiguity?

Interesting. I totally didn’t think of the possibility of having two opposite outputs and two opposite inputs. It would indeed be ambiguous, and the parser would throw an error in this situation (“Program is ambiguous: cannot determine the direction of all the edges in <function name>” — which is the wrong message, so it’s misleading...). Thanks for pointing that out. — Timwi 20:41, 16 April 2011 (UTC)

Indeed, it can determine the direction of all edges, but not which input is which and which output is which. But I've figured that there might also be cases involving combinations of 1→3, adjacent 2→2 and 3→1 functions where not all directions can be unambiguously determined. I'll have to investigate.... -- Smjg 16:36, 17 April 2011 (UTC)

Did you find an example in which the directions are ambiguous? I haven’t so far, and I’ve written quite a bit of Funciton code. — I did find a case in which my interpreter failed to deduce the directions, but that was due to a limitation in the algorithm, which I’ve fixed now. — Timwi (talk) 18:00, 21 December 2013 (UTC)

And am I right in understanding that, in declaration headers and call boxes, the orientation of the single/double borders is immaterial? -- Smjg 18:13, 16 April 2011 (UTC)

Yes, you are right. I was going to add a section to the article to clarify this. Stay tuned :) — Timwi 20:41, 16 April 2011 (UTC)

I would guess, that the position of double lines is important. But that would also seem some of the example programs are wrong that the double lines are always on the right/bottom but shouldn't always be? --Zzo38 20:34, 16 April 2011 (UTC)

They can be where they want. They don’t have to be aligned with the orientation of the inputs/outputs. — Timwi 20:41, 16 April 2011 (UTC)

Then there will be sometimes ambiguities, isn't it? --Zzo38 04:19, 21 April 2011 (UTC)

Did you find an example that is ambigous? — Timwi (talk) 18:00, 21 December 2013 (UTC)

What I mean is that, if you can put them anywhere, and there are multiple inputs/outputs, how do you know which inputs/outputs do you want? --Zzo38 (talk) 07:20, 23 December 2013 (UTC)

Well, you know all edges attached to a literal or a declaration box are outgoing, and the edge leading to the dangling end is incoming. From that, the interpreter successively deduces which of the connectors on every box are incoming or outgoing given the orientation of inputs/outputs in every function declaration. So far, the algorithm has resolved every valid function or program I’ve ever written. — Does this answer your question? If not, can you give an example program or function that confuses you? — Timwi (talk) 00:48, 4 January 2014 (UTC)

I think this is an example of an ambiguous call

                       ┌──────┐                                                
╓───╖ ┌───╖   ╔═══╗  ┌─┴─╖  ┌─┴─╖                                              
║ @ ╟─┤ f ╟─┐ ║   ╟──┤ @ ╟─ │ g ║                                              
╙─┬─╜ ╘═══╝ │ ╚═══╝  ╘═╤═╝  ╘═╤═╝                                              
  └─                   └──────┘                                                

-- Qpliu (talk) 07:30, 5 January 2019 (UTC)

Thank you for providing this example! Turns out the parser does error out saying that this is ambiguous. Fortunately, the program is also meaningless (it’s a circular dependency, or equivalently, an infinite loop), so I have no issue with this ambiguity existing. — Timwi (talk) 12:44, 7 June 2023 (UTC)

Function names

What are the rules (if any) on what is a valid function name? In particular:

• Can the name span more than one line?
• Are the padding spaces considered part of the name?
• Can any Unicode printable characters (including spaces and box-drawing characters) be used, or are there restrictions?
• Can a function have an empty name, like any or all of these declaration boxes?

╓╖  ╓─╖  ╓╖
║║  ╙─╜  ╙╜
╙╜

-- Smjg 21:52, 17 April 2011 (UTC)

The interpreter enforces the following rules:

• Declaration boxes and call boxes must be single-line (three lines if you count the borders).
• Leading and trailing spaces are removed from the function names. Therefore, “ × ” and “×” are the same.
• No other space munching is done; thus “A  B” is a different function from “A B”.
• The empty function name is not allowed. (It was until now, but since you pointed it out, I made it throw. This way I can reserve it for some special meaning in the future.)

Thanks for the interesting questions! — Timwi 00:22, 21 April 2011 (UTC)

News about the interpreter

I rewrote the evaluation part of the interpreter so that it doesn’t depend on the .NET callstack anymore. It is now possible to calculate much larger numbers than before. On my computer it outputs 1000! (a thousand factorial — a number with 2568 digits) within 20 seconds. However, memory consumption is still a problem — large Fibonacci numbers or very large powers (exponents) can cause the computer to hang swapping forever. — Timwi 00:28, 21 April 2011 (UTC)

Is your Fibonacci function memoizing values? Otherwise it would end up recalculating the value for the same argument an exponential amount because the same argument is re-reached through different branches. Alternatively if you do memoize, this would make the memory problem slightly worse... I've seen in Haskell discussions people say that the usual recursive Fibonacci formulation is a terrible example function for this reason. --Ørjan 08:05, 21 April 2011 (UTC)

No, of course it wasn’t memoizing values, and I was full aware that that is why it was inefficient. By now I have improved the Fibonacci function (not the interpreter) by using a standard technique in functional programming: use a helper function that takes a parameter that acts as an accumulator. Fibo(n) = fibo(0, 1, n); fibo(a, b, n) = n ? fibo(b, a+b, n−1) : a. — Timwi 00:06, 27 April 2011 (UTC)

Is this a Turing tarpit?

Could Funciton be considered a Turing tarpit? It provides only three operations on integers, but it gets most of its Turing-completeness from the ability to call functions recursively. I am not sure where the definition of “Turing tarpit” ends? — Timwi 01:10, 21 April 2011 (UTC)

I don't think that something extensible can be considered Turing tarpit. --TehZ 20:16, 19 October 2011 (UTC)

The interpreter DOES come with an "extensive library of useful functions." IAM (talk) 11:25, 18 June 2016 (UTC)

Just because an interpreter prebuilds functions for ease of use does not mean the functions are part of the base language. If I made a lambda calculus interpreter that prebuilt booleans, lambda calculus wouldn't suddenly have booleans prebuilt in. Why should this be different for Funciton? Funciton is a Turing tarpit as it is Turing complete with few built-in mechanics, despite the interpreter having many functions built in. —CreeperBomb (interact in such a way to use diction in order to achieve the result of conversation or other form of communicating an idea or group of ideas between individuals including myself) 20:48, 7 June 2023 (UTC)

Infinity?

What happens if you use, for example, -1 SHL -1? Will it return infinity? How about -1 SHL -1 SHL 1? What will that return? And -1 SHL -1 SHL -1? Are there multiple infinities? --TehZ 22:53, 22 April 2011 (UTC)

a SHL b = a × 2^b. So -1 SHL -1 = -2^-1 = -0 (when using round-to-zero arithmetic). I somewhat doubt the implementation actually interprets it this way, however. —ehird 23:29, 22 April 2011 (UTC)

In other programming languages, -1 SHL -1 (or -1 SHR 1) is the same as the maximum integer value. Since integers are unbounded in Funciton, that should return infinity, right? --(this comment by TehZ at 23:33, 22 April 2011 UTC; please sign your comments with ~~~~)

% irb
irb(main):001:0> (-1) >> (-1)
=> -2
irb(main):002:0> ^D

% python
Python 2.6.6 (r266:84292, Sep 15 2010, 16:22:56) 
[GCC 4.4.5] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> (-1) >> (-1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: negative shift count
>>> ^D

% ghci
GHCi, version 6.12.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Prelude> import Data.Bits
Prelude Data.Bits> (-1) `shiftL` (-1) :: Int
-1
Prelude Data.Bits> (-1) `shiftL` (-1) :: Integer
-1
Prelude Data.Bits> ^D
Leaving GHCi.

Please provide an example of a language which interprets -1 SHL -1 in that manner. —ehird 23:53, 22 April 2011 (UTC)

Your irb test seems to use right shift not left... Other than that, I find ghci's interpretation obvious to me, by simply noting that the bit pattern of -1 is an infinite leftward sequence of 1's. It doesn't give a positive infinity because there is no leftmost bit which could be set to 0, unlike with finite bit sizes. Of course the Haskell implementation of Data.Bits on Integers is given by the obvious (to mathematicians) embedding into the 2-adic integers. --Ørjan 07:43, 23 April 2011 (UTC)

It actually depends on whether it is a signed shift or an unsigned shift. BTW for some reason, scala (and therefore all jvm languages) gives the lowest possible value (Integer.MIN_VALUE). So basically, this should give negative infinity? Well, look at it this way: 1...(infinite 1's)...1 >> 1 = 0...(infinite 1's)...1, and the language specifies that x << -y == x >> y, so it should give infinity, right? --TehZ 09:26, 23 April 2011 (UTC)

Well for unbounded integers signed shift is simpler — it works naturally without needing to add any infinities. --Ørjan 18:02, 23 April 2011 (UTC)

How's it simpler? Shouldn't SHL and SHR do what I described? I think the language needs to specify whether or not it is a signed shift. --(this comment by TehZ at 21:44, 23 April 2011 UTC; please sign your comments with ~~~~)

It is simpler because the integers as usually defined in mathematics do not include any members with 0...(infinite 1's)... bit patterns — their 2's complement representations all begin with either infinitely many 0's or infinitely many 1's, followed by finitely many arbitrary bits. To get an unsigned shift working you need to add infinite "integers" explicitly. But signed shifts work directly on ordinary unbounded integers with nothing added. --Ørjan 08:57, 24 April 2011 (UTC)

Maybe we should test it in the interpreter. --TehZ 09:18, 24 April 2011 (UTC)

Well here are the relevant lines from https://bitbucket.org/Timwi/funciton-interpreter/src/52159b63606f/FuncitonFunction.cs (incidentally let me rage about subwindows that provide a horizontal scrollbar but not a vertical one, making the horizontal one extremely annoying to use):

private BigInteger _leftEval;
[...]
_result = _previousSubresult.IsZero ? _leftEval : _previousSubresult > 0 ? _leftEval << (int) _previousSubresult : _leftEval >> (int) -_previousSubresult;

So it will obviously do whatever C#'s BigInteger >> implementation does. (Note I don't know C#.) --Ørjan 13:56, 24 April 2011 (UTC)

Answer

I am surprised that the question of −1 SHR 1 is contentious, but here’s the clarification:

All the shift-rights are, of course, “signed” (assuming the definition of “signed” given in the above thread). There is, of course, no infinity. To me, this seemed obvious because −1 is logically an infinite sequence of 1-bits; if you remove the least significant one and shift everything right by one, you clearly still have an infinite sequence of 1-bits, so you get the same number you started with, which is −1. Therefore, the following results follow naturally:

• −1 SHL −1 = −1 SHR 1 = −1
• (−1 SHL −1) SHL 1 = −1 SHL 1 = −2
• −1 SHL (−1 SHL 1) = −1 SHL −2 = −1 SHR 2 = −1
• (−1 SHL −1) SHL −1 = −1 SHR 1 = −1
• −1 SHL (−1 SHL −1) = −1 SHL −1 = −1

I hope this answers the above questions. — Timwi 21:24, 26 April 2011 (UTC)

Could be turned into a functional language?

Recently, you found out that this isn't a functional language. However, if you add anonymous functions, you can easily make it functional. The anonymous functions could easily be encoded in numbers, if I am correct. If you add those anonymous functions (or someone implements them in the language ;)), then you can easily add a little sugar, and then you have a good, functional language. Every functional language has the possibility of type-classes (I think), and if you combine a type-class with a value, you get an object-oriented object. In other words, if you add a little bit of functionality, you will get a lot of it. --TehZ 14:29, 24 June 2011 (UTC)

One way to implement anonymous functions would be to make an ADT that represents the language elements. Since ADT's are relatively easy to implement in most languages, it should be easy to do it that way. If we add an interpreter for that ADT, we effectively have a self-interpreter. Since a self-interpreter + some code it can interpret effectively is an anonymous function, that should be enough to have anonymous functions. --TehZ 14:33, 24 June 2011 (UTC)

Funciton now supports anonymous functions (lambda expressions). However, it does not encode them as an ADT inside a BigInteger; instead, the interpreter just assigns them sequential integers (starting from 1) and remembers them in an internal list. The reason I decided against trying to encode them as ADTs is because that ADT would have to encode a heck of a lot more than just the lambda itself; it could potentially contain the entire program. — Timwi (talk) 17:52, 21 December 2013 (UTC)

"Libraries" and logic gates

Is it normal that the logic gates (not/and/or/xor) are not in the "libraries" at the end of the article (in Funciton/Fundamentals) ? 85.158.138.21 13:37, 23 November 2012 (UTC)

(Edit : By the way, it seems that a "xor" is used by the "Find the first occurrence of a substring" function.) 85.158.138.21 13:55, 23 November 2012 (UTC)

Indeed, the xor function, ^, is missing from Funciton/Fundamentals — well spotted. It is declared in bitwise.fnc, so I copied it over now. As for the others, you are right — they are shown in the article to demostrate the syntax of declarations, but while writing code, I never used a function call to do bitwise and or or. I even recently discovered that, if b is known to be either 0 or −1 (i.e., a boolean), b ? −1 : x can be written as b | x and b ? x : 0 can be written as b & x. I haven’t measured whether saving a function call actually improves the performance, but I don’t think it can hurt it. — xor is a bit of a special case because it requires twice as much logic as and/or, and it almost always requires a wire-crossing too (it doesn’t in the declaration because I can route one wire around the top). The addition and division functions write it out, but I guess when I wrote ʘ I got tired of it, so I made it a function. — Timwi (talk) 21:38, 24 November 2012 (UTC)

Conditional returning lambda

In this language, how can you make a conditional expression that returns one of two lambda functions depending on whether an integer input is zero? You explain how to make a conditional, but that seems to work only on numbers, because it has to take the complement of a number. – b_jonas 07:17, 27 November 2014 (UTC)

Ah, ignore the question. Apparently functions are represented as integers too, so the same conditional works. – b_jonas 07:30, 27 November 2014 (UTC)

Specifically, it uses an ID number for each lambda. IAM (talk) 11:34, 18 June 2016 (UTC)

Funciton Tools

I wrote a little program that is helpful for programming in Funciton:

╔═══╗
║   ║
╚═╤═╝
  │
┌─┴─────╖
│int→str║
╘═╤═════╝
  │

You enter a string and it tells you the number that represents that string in Funciton. IAM (talk) 11:36, 18 June 2016 (UTC)