Funciton

(Redirected from Funciton/Fundamentals)

Funciton (pronounced: /ˈfʌŋkɪtɒn/) is a two-dimensional, minimalistic, declarative programming language invented by User:Timwi in 2011.

```                   ╓───╖
║ ! ║
╙─┬─╜   ┌───╖  ╔═══╗
┌─────┴─────┤ > ╟──╢ 2 ║
│           ╘═╤═╝  ╚═══╝
╔════╗  ┌───╖ │             │
║ −1 ╟──┤ + ╟─┴─┐           │
╚════╝  ╘═╤═╝   │           │
┌─┴─╖   │    ╔═══╗  │
│ ! ║   │    ║ 1 ║  │
╘═╤═╝   │    ╚═╤═╝  │
│   ┌─┴─╖  ┌─┴─╖  │
│   │ × ╟──┤ ? ╟──┘
│   ╘═╤═╝  ╘═╤═╝
└─────┘      │
```

Example: The factorial function.

(None of the functions seen here (addition, multiplication, greater-than) are built-in.
All of them have their own implementation in Funciton.)

Features

• Programs use the Unicode box-drawing characters to create a graphical representation of data flow.
• Funciton is not electronics. Programs look a bit like circuit diagrams, but they are not circuit diagrams.
• Funciton is invariant under 90° rotations. 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.
• Funciton currently has only one datatype, the arbitrary-size integer. However, Funciton defines an encoding that expresses arbitrary strings as a single integer.
• Funciton has only five built-in instructions (NAND, less-than, shift-left, function invocation and lambda expressions); all other functionality (arithmetic, string handling, lazy-evaluated sequences, etc.) is implemented in terms of these.
• Funciton has a fully working interpreter and a compiler to IL; see External resources at the bottom.

Syntactic elements

 Function declaration header ``` ╓───╖ ╒═══╕ ──╢ + ╟── ──┤ + ├── ╙───╜ ╘═══╛ ``` Function call ``` ┌───╖ ╓───┐ ╔═══╕ ╒═══╗ ──┤ + ╟── ──╢ + ├── ──╢ + ├── ──┤ + ╟── ╘═╤═╝ ╚═╤═╛ ╙─┬─┘ └─┬─╜ │ │ │ │ ``` NAND or splitter ``` │ │ │ ──┴── ├── ──┬── ──┤ │ │ │ ``` less-than and shift-left ``` │ ──┼── │ ``` Function return value ``` │ ──── │ │ ``` Integer literal ``` ╔═══╗ ║ 1 ╟── ╚═══╝ ``` Read string from STDIN ``` ╔═══╗ ║ ╟── ╚═══╝ ``` Lambda expression ``` │ │ │ │ ╒═╧═╗ ╓─┴─╖ ╔═╧═╕ ╔═╧═╗ ──┤ ╟── ──╢ ╟── ──╢ ├── ──╢ ╟── ╘═╤═╝ ╚═╤═╝ ╚═╤═╛ ╙─┬─╜ │ │ │ │ ``` Lambda invocation ``` │ │ │ │ ┌─┴─╖ ┌─┴─┐ ╓─┴─┐ ╒═╧═╕ ──┤ ╟── ──┤ ├── ──╢ ├── ──┤ ├── └─┬─╜ ╘═╤═╛ ╙─┬─┘ └─┬─┘ │ │ │ │ ``` Comment ``` ╔════════════╗ ║ Hi, Bob! ║ ╚════════════╝ ```

Introduction

Simply speaking, Funciton programs consist of lines and boxes. Each line carries data from one box to the next.

A Funciton program must have exactly one loose end; a line that just stops somewhere. This is the program output.

Boxes with a double-struck line and at least one outgoing line are literals. Such a box may contain an integer literal. A very simple program might look like this:

```  ╔════╗
║ 47 ║
╚═╤══╝
│
```

This program prints `/`, which is Unicode character number 47.

Boxes with a double-struck line can be empty, too. In this case, such a box represents the data passed to the program via STDIN. The data is encoded according to the string encoding which is described later in string handling. (Multiple such boxes in a program do not read multiple different inputs from STDIN. The interpreter reads STDIN only once, and then all such boxes return the same data.)

```  ╔═══╗
║   ║
╚═╤═╝
│
```

This program prints its input, so it is a cat program.

NAND and the splitter

A T-junction in which the two opposite-direction connectors are inputs and the perpendicular one is an output calculates the NAND of two numbers. In C notation, NAND(a,b) = ~(a & b). Consider the following programs:

```  ╔═══╗   ╔═══╗       ╔═══╗   ╔═══╗       ╔════╗  ╔════╗
║ 5 ║   ║ 5 ║       ║ 5 ║   ║ 0 ║       ║ -2 ║  ║ -1 ║
╚═╤═╝   ╚═╤═╝       ╚═╤═╝   ╚═╤═╝       ╚══╤═╝  ╚══╤═╝
│       │           │       │            │       │
└───┬───┘           └───┬───┘            └───┬───┘
│                   │                    │
```

The above three programs calculate −6, −1 and 1, respectively. (The actual output will be an unprintable character.)

Remember that numbers in Funciton are arbitrary-size integers. Negative numbers are logically modeled by having infinitely many 1-bits on the left (2’s complement). `-1` has all bits set.

Also remember that Funciton programs are rotation-invariant, so all of the following programs do exactly the same thing:

```  ╔════╗  ╔════╗           │          ╔════╗               ╔════╗
║ -2 ║  ║ -1 ║       ┌───┴───┐      ║ -1 ╟──┐         ┌──╢ -2 ║
╚══╤═╝  ╚══╤═╝       │       │      ╚════╝  │         │  ╚════╝
│       │      ╔══╧═╗  ╔══╧═╗            ├──     ──┤
└───┬───┘      ║ -1 ║  ║ -2 ║    ╔════╗  │         │  ╔════╗
│          ╚════╝  ╚════╝    ║ -2 ╟──┘         └──╢ -1 ║
╚════╝               ╚════╝

╔══════════════════════════════════════════════════╗
║  All four of the above programs are equivalent.  ║
╟──────────────────────────────────────────────────╢
║  Also, a double-lined box with no outgoing       ║
║  lines (like this one) is a comment.             ║
╚══════════════════════════════════════════════════╝
```

A T-junction in which the two opposite-direction connectors are outputs and the perpendicular one is an input is a splitter. This is not an operation, but simply a syntactic element that splits a line into two. It allows you to access the same value more than once. For example, consider the following program:

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

This program computes the value `(3 NAND 2) NAND (2 NAND 1)` and thus outputs character number 2 (which, again, is an unprintable character). (The order of the NAND arguments is significant due to its short-circuit semantics.)

Whether a T-junction is a NAND operation or simply a splitter is implicit in which incoming lines are inputs and which are outputs:

```╔═════════════════╗    ╔═════════════════════╗    ╔══════════════════════════╗
║ This is a NAND. ║    ║ This is a splitter. ║    ║ This program is invalid. ║
╚═════════════════╝    ╚═════════════════════╝    ╚══════════════════════════╝

╔═══╗
╔═══╗         ╔═══╗         ──────┬──────                  ║ 3 ║
║ 3 ╟────┬────╢ 2 ║               │                        ╚═╤═╝
╚═══╝    │    ╚═══╝             ╔═╧═╗                        │    ╔═══╗
│                      ║ 3 ║                        ├────╢ 2 ║
│                      ╚═══╝                        │    ╚═══╝
```

(But notice that the second program is also invalid because it has more than one output.)

Declaring a function

A function declaration consists of a declaration header and one or more loose ends. The header is a box, containing the function name, that has two double-lined and two single-lined edges on opposite sides. A loose end defines a function output.

We can now construct a function for each of the familiar logic gates:

```                                                  ┌──────────────────────┐
╓─────╖        ╓─────╖            ╓────╖          │  ╓─────╖             │
║ not ║     ┌──╢ and ╟──┐      ┌──╢ or ╟──┐       ├──╢ xor ╟─────┐       │
╙──┬──╜     │  ╙─────╜  │     ┌┴┐ ╙────╜ ┌┴┐      │  ╙─────╜ ┌┐  │    ┌┐ │
│        └─────┬─────┘     └┬┘        └┬┘      └───┬──────┤├──┴──┬─┤├─┘
┌┴┐            ┌┴┐           └────┬─────┘           │      └┘     │ └┘
└┬┘            └┬┘                │                 └────┬────────┘
│              │                                        │
```

Notice that NOT consists of a splitter and a NAND.

The lines emerging from the declaration header define inputs to the function. Loose ends define outputs. A function can have multiple outputs. The directions in which the inputs “leave” the declaration header and the directions in which the outputs “point” determine how the function can be called; more about this later.

Less-than and shift-left

Less-than and shift-left are both calculated by a single operator, the cross:

```      ╔═══╗
║ a ║
╚═╤═╝
╔═══╗  │
║ b ╟──┼──── (a < b)
╚═══╝  │
│
│
(a SHL b)
```

The less-than operation returns `−1` for true and `0` for false. This enables boolean logic using the NAND operation; if true were represented by `1`, then `NOT 1` would be `−2`.

The shift-left operation can also do shift-right simply by giving it a negative operand.

In order to use this to evaluate only less-than or only shift-left, we need a little trick.

The Starkov construct

The Starkov construct, named for Cambridge computer scientist and entrepreneur Roman Starkov, who discovered this construct months into Funciton’s existence, is a trick to “nullify” a wire. It consists of a NAND operator that is connected to itself. The following declarations for a less-than and greater-than function demonstrate this:

``` ╔╤════════════╗   ╔╤═══════════════╗
║│ less than  ║   ║│ greater than  ║
╚╧════════════╝   ╚╧═══════════════╝
╓───╖
┌────────┐         ┌─╢ > ╟──┐
│ ╓───╖  │         │ ╙───╜  │
└─╢ < ╟──┼─────┐   └────────┼─────┐
╙───╜  ├──┐  │            ├──┐  │
└──┘               └──┘
```

In these examples, the less-than part of the cross operator is connected to the function output, while the shift-left part is connected to a Starkov construct. Since this does not constitute a function output, it is never evaluated and thus effectively nullifies that part of the calculation.

Calling a function

It would be no use declaring functions if you couldn’t call them. A call box consists of two adjacent double-lined edges and two single-lined ones. This is best demonstrated by an example, so let’s define some more comparison operators:

```  ╔╤══════════════╗   ╔╤═══════════════╗
║│ less than    ║   ║│ greater than  ║
║│ or equal to  ║   ║│ or equal to   ║
╚╧══════════════╝   ╚╧═══════════════╝
╓───╖               ╓───╖
┌──╢ ≤ ╟──┐         ┌──╢ ≥ ╟──┐
│  ╙───╜  │         │  ╙───╜  │
│         │         │         │
│  ┌───╖  │         │  ┌───╖  │
└──┤ < ╟──┘         └──┤ > ╟──┘
╘═╤═╝               ╘═╤═╝
┌┴┐                 ┌┴┐
└┬┘                 └┬┘
│                   │
```

These declarations may at first look wrong. After all, “less-than-or-equal-to” is not the same as “NOT less-than”! To understand why this declaration is correct, you have to consider the direction in which data is flowing:

So basically, what goes in to the right of the call node comes out of the left of the declaration box (if the outputs are oriented the same way in the declaration and the call). The fact that the wires take a 180° turn in the code for less than or equal to effectively swaps the order of the operands.

The conditional operator

The conditional operator, written in C-like languages as `a ? b : c`, which returns `c` if `a` is zero and `b` otherwise, is equivalent to the expression `((a ≠ 0) NAND b) NAND ((a = 0) NAND c)`. Here we can really show off the splitter: the test for `a ≠ 0` is evaluated only once even though it is used in two places.

```  ╔═══╗  ┌───╖  ╓───╖
║ 0 ╟──┤ ≠ ╟──╢ ? ╟─┐        ╔══════════════════════════════╗
╚═══╝  ╘═╤═╝  ╙─┬─╜ │        ║  conditional operator        ║
│      ├─┬─┤        ║  WITH A PROBLEM (read on)    ║
│      │  ┌┴┐       ╟──────────────────────────────╢
│      │  └┬┘       ║  ?(a, b, c) = (a ≠ 0 & b) |  ║
│      └─┬─┘        ║               (a = 0 & c)    ║
└────────┘          ╚══════════════════════════════╝
```

Now, I hate to break it with you, but it’s not quite this simple. The above declaration has a big problem which we will come to later.

Incomplete first attempt

Addition will be our first recursive function. The simplest way to do addition is to add/subtract 1 at a time:

```+(a, b) = a ? +(a−1, b+1) : b;
```

However, this would be incredibly slow (it would be exponential-time). We can do better — we can do linear time by harnessing the power of the shift-left. We will implement addition as a recursive function using the following formula:

```+(a, b) = b ? +(a XOR b, (a AND b) SHL 1) : a
```

You can easily convince yourself that this works by considering the following:

• The XOR does the addition on each individual bit, ignoring the carry.
• The AND calculates the carry. SHL carries it to the next bit and then the recursive call adds it to the previous result.

Unfortunately, we run into three problems. The first problem is immediately apparent here:

```            ╓───╖
┌──╢ + ╟──┐
│  ╙───╜  │
┌────┴────┬────┴────┐
│  ┌┐     │      ┌┐ │
┌─┴──┤├──whoops!─┬─┤├─┴─┐
│    └┘     │    │ └┘   │          ╔════════════════════════════╗
│    ┌──────┴───┬┘      │          ║  addition — WITH           ║
│   ┌┴┐        ┌┴┐      │          ║  THREE PROBLEMS (read on)  ║
│   └┬┘        └┬┘      │          ╟────────────────────────────╢
│ ┌──┴─╖  ┌───╖ │       │          ║  +(a, b) = b               ║
│ │ << ╟──┤ + ╟─┘       │          ║      ? +(a^b, (a&b) << 1)  ║
│ ╘══╤═╝  ╘═╤═╝         │          ║      : a                   ║
│  ╔═╧═╗    │           │          ╚════════════════════════════╝
│  ║ 1 ║    │           │
│  ╚═══╝  ┌─┴─╖         │
└─────────┤ ? ╟─────────┘
╘═╤═╝
│
```

Problem #1: crossing lines (solution: cross-nop)

We need for those two lines to cross. But as we saw before, crossing two lines causes less-than and shift-left to be calculated; we don’t want that. We need a cross that is a no-op. A cross-nop.

Fortunately, there is a way to cross two lines. We can declare a function that takes two inputs and two outputs, and which... does nothing:

```                     ╔═══════════════════╗
╒═══╕          ║  cross-nop        ║
│ · ├──        ╟───────────────────╢
╘═╤═╛          ║  (x, y) = (x, y)  ║
│            ╚═══════════════════╝
```

Notice that this declaration says that:

• the function has two inputs which are adjacent
• the function has two outputs which are adjacent, and opposite the inputs
• each output is equal to the input opposite to it

which is exactly what we want.

If you are a fan of the wire-crossing problem, you can set yourself the challenge of writing programs without this function.

Problem #2: recursion (solution: short-circuit evaluation)

Another problem with our addition function above is that it is recursive. A recursive function needs a terminating condition, otherwise it... won’t terminate. The terminating condition in this case is, of course, `b`; but we somehow need to guarantee that the rest of the code (the part containing the recursive call) is not going to get evaluated when `b` is zero.

To this end, the NAND operator has built-in short-circuit semantics:

```  ╔═══╗   ╔═══╗
║ x ║   ║ 0 ║      ╔═══════════════════════════════╗
╚═╤═╝   ╚═╤═╝      ║  short-circuit evaluation:    ║
┌─┴─╖     │        ║  the NAND operator returns    ║
│ F ║     │        ║  −1 without evaluating F(x).  ║
╘═╤═╝     │        ╚═══════════════════════════════╝
└───┬───┘
│
```

Whenever the first operand to a NAND operation evaluates to `0`, the second operand is never evaluated. Notice that if the NAND’s output is pointing down, the first operand is on the right; if it is pointing up, the first operand is on the left, and analogously for the other two possible rotations.

Now the problem with the conditional operator we defined before may become apparent. The diagram actually encodes the operation `((a = 0) NAND c) NAND (b NAND (a ≠ 0))`; the second part is the wrong way round because we need to evaluate `a ≠ 0` first in order to know whether to evaluate `b`. Therefore, we need to flip this around. At this point we run into the line-crossing problem again, so we use our newly-defined cross-nop:

```╔═══╗  ┌───╖    ╓───╖
║ 0 ╟──┤ ≠ ╟────╢ ? ╟─┐
╚═══╝  ╘═╤═╝    ╙─┬─╜ │        ╔══════════════════════════════╗
│      ┌─┴─╖ │        ║  conditional operator        ║
│  ┌───┤ · ╟─┤        ╟──────────────────────────────╢
│  │   ╘═╤═╝ │        ║  ?(a, b, c) = (a ≠ 0 & b) |  ║
│  └──┬──┤  ┌┴┐       ║               (a = 0 & c)    ║
│     │  │  └┬┘       ╚══════════════════════════════╝
│        └─┬─┘
└──────────┘
```

Problem #3: It doesn’t work with negative numbers

Well, it works with some negative numbers. But there are combinations of inputs for which the recursive formula is endless (the terminating condition is never reached).

Specifically, it works fine only if:

• a ≥ 0 and b ≥ 0, or
• a + b < 0

But it doesn’t manage to do the jump from a negative input to a positive (or zero) output. `a XOR b` will be negative and stay negative, and the `(a AND b) SHL 1` will be positive and just keep on growing indefinitely.

The successor function

We need a separate function to do the job of jumping from `−1` to `0`. We will use the successor function for this, which is defined as:

```♯(a) = a + 1
```

But we can’t define it in terms of addition because we need it in order to do addition, so we need to do something else:

```                            ╓───╖
║ ♯ ║             ╔════════════════════════════╗
╙─┬─╜             ║  successor function        ║
┌──────────┴────────┐      ╟────────────────────────────╢
╔════╗  ┌────╖  │    ╔═══╗          │      ║  ♯(a) = a = -1 ? 0 :       ║
║ -1 ╟──┤ << ╟──┴─┬──╢ 1 ║          │      ║    a & 1 ? ♯(a>>1) << 1 :  ║
╚════╝  ╘══╤═╝    │  ╚═══╝          │      ║    a | 1                   ║
┌─┴─╖   ┌┴┐   ╔═══╗ ╔════╗ │      ╟────────────────────────────╢
│ ♯ ║   └┬┘   ║ 0 ║ ║ -1 ║ │      ║  Note: can’t actually use  ║
╘═╤═╝    │    ╚═╤═╝ ╚══╤═╝ │      ║  >> because >> depends on  ║
┌──┴─╖  ┌─┴─╖  ┌─┴─╖  ┌─┴─╖ │      ║  ~ (unary minus) which in  ║
│ << ╟──┤ ? ╟──┤ ? ╟──┤ = ║ │      ║  turn depends on the       ║
╘══╤═╝  ╘═╤═╝  ╘═╤═╝  ╘═╤═╝ │      ║  successor function.       ║
╔═╧═╗ ┌┐ │ ┌┐   │      ├───┘      ╚════════════════════════════╝
║ 1 ╟─┤├─┴─┤├──────────┘
╚═══╝ └┘   └┘
```

Note that the formula uses both SHL and SHR, but we haven’t defined SHR yet; we need unary minus for that, which we’ll get to later. Therefore, we use `SHL −1`.

Introducing private functions

Since the addition function we already defined is potentially an infinite loop, you don’t really want any code to call it other than code that knows what it’s doing. Therefore, we will declare it private. A private function is a function that can only be called by functions within the same source file; in other words, its scope is its containing file. Private functions are marked with an extra little tag in the declaration box as seen here:

```                    ╓┬───╖
┌──╫┘+p ╟──┐
│  ╙────╜  │
┌────┴─────┬────┴────┐
│ ┌───┐  ┌─┴─╖    ┌┐ │
┌─┴─┤   ├──┤ · ╟──┬─┤├─┴─┐
│   └───┘  ╘═╤═╝  │ └┘   │          ╔═════════════════════════════╗
│    ┌───────┴───┬┘      │          ║  addition in the case of    ║
│   ┌┴┐         ┌┴┐      │          ║  (a≥0 & b≥0) | (¬b)≥a       ║
│   └┬┘         └┬┘      │          ╟─────────────────────────────╢
│ ┌──┴─╖  ┌────╖ │       │          ║  +p(a, b) = b               ║
│ │ << ╟──┤ +p ╟─┘       │          ║      ? +p(a^b, (a&b) << 1)  ║
│ ╘══╤═╝  ╘══╤═╝         │          ║      : a                    ║
│  ╔═╧═╗     │           │          ╚═════════════════════════════╝
│  ║ 1 ║     │           │
│  ╚═══╝   ┌─┴─╖         │
└──────────┤ ? ╟─────────┘
╘═╤═╝
│
```

Finally, we define the real addition function in terms of this private one. We know that the above function works for negative numbers if the result is negative. Therefore, if we can tell (using ≥) that it is going to be non-negative, just negate both operands; then the result will be negative, which we negate again to get the real result. Since binary negation is actually one away from unary minus, we need to use the successor function to correct the discrepancy.

```      ┌──────────────────────────────┐  ╔══════════════════════════════════╗
│       ╓───╖                  │  ║  addition                        ║
├───────╢ + ╟───────┐          │  ╟──────────────────────────────────╢
┌─┴─╖     ╙───╜       │          │  ║  +(a, b) = (a≥0 & b≥0) | (¬b)≥a  ║
┌──┤ · ╟─────────────────┴──┐       │  ║           ? +p(a,b)              ║
│  ╘═╤═╝          ┌─────────┴──┐    │  ║           : ¬(♯(+p(¬a, ¬b)))     ║
│    │            │  ┌────╖  ┌─┴─╖  │  ╚══════════════════════════════════╝
│    │            └──┤ +p ╟──┤ · ╟──┴──────────────────┐
┌┴┐  ┌┴┐              ╘═╤══╝  ╘═╤═╝┌───╖  ╔═══╗  ┌───╖  │
└┬┘  └┬┘                │       └──┤ ≤ ╟──╢ 0 ╟──┤ ≥ ╟──┴─┐
│    │                 │          ╘═╤═╝  ╚═══╝  ╘═╤═╝    │
│ ┌──┴─╖  ┌───╖  ┌┐  ┌─┴─╖          └──────┬──────┘      │
│ │ +p ╟──┤ ♯ ╟──┤├──┤ ? ╟─────────────────┤             │
│ ╘══╤═╝  ╘═══╝  └┘  ╘═╤═╝                 │             │
│    │                 │                   │             │
└────┤                                   ┌─┴─╖           │
└───────────────────────────────────┤ < ╟───────────┘
╘═══╝
```

String handling

As hinted at in the introduction, Funciton programs receive all text passed in through STDIN encoded as a single humongous integer. The format in which these strings are encoded could be referred to as UTF-21: every 21 bits form a Unicode character. This way the complexity arising from surrogates in UTF-16 is avoided, while still being more memory-efficient than UTF-32.

The least significant 21 bits contain the first character in the string. Thus, if you were to look at the bit pattern of an integer, the string would appear to be stored backwards (unless you habitually write in Arabic, Hebrew, Syriac, or any other RTL script). The operation s SHR 21 removes the first character and thus appears to be shifting the characters in the string to the left.

After the last character in the string, the rest of the integer may optionally be either all zeroes or all ones. The latter allows strings ending in the NUL character (U+0000) to be encoded unambiguously. A compliant interpreter must use the latter if the text provided through STDIN does indeed end with the NUL character, and it must tolerate both formats when interpreting the number returned by the Funciton program.

This takes us directly to some simple string handling functions, string length and string concatenation:

```              ╔════╗           ╔═══════════════════════════════════════════════╗
║ 21 ║           ║  String length                                ║
╚═╤══╝  ╓───╖    ╟───────────────────────────────────────────────╢
┌───╖  ┌─┴──╖  ║ ℓ ║    ║  ℓ(s) = (s = 0 | s = −1) ? 0 : ♯(ℓ(s >> 21))  ║
┌───┤ ℓ ╟──┤ >> ║  ╙─┬─╜    ╚═══════════════════════════════════════════════╝
│   ╘═══╝  ╘═╤══╝    │
┌─┴─╖          └───────┴──┐                           ╓───╖
│ ♯ ║        ╔═══╗  ┌───╖ │                        ┌──╢ ‼ ╟────────────────────────┐
╘═╤═╝   ┌────╢ 0 ╟──┤ ≠ ╟─┴┐                       │  ╙───╜  ┌───╖  ┌───╖  ╔════╗  │
│   ┌─┴─╖  ╚═══╝  ╘═╤═╝  │                    ┌──┴─────────┤ ℓ ╟──┤ × ╟──╢ 21 ║  │
└───┤ ? ╟───────────┤    │                    │            ╘═══╝  ╘═╤═╝  ╚════╝  │
╘═╤═╝ ╔════╗  ┌─┴─╖  │                 ┌──┴─────────┐      ┌────┴──┐         │
│   ║ −1 ╟──┤ ≠ ╟──┘                 │   ┌───╖  ┌─┴─╖  ┌─┴──╖    │         │
╚════╝  ╘═══╝                    │ ┌─┤ + ╟──┤ · ╟──┤ << ║    │         │
└─┤ ╘═╤═╝  ╘═╤═╝  ╘═╤══╝    │         │
╔════════════════════════════════════════════╗  │ ┌─┴─╖  ┌─┴─╖  ╔═╧═╗     │ ┌────╖  │
║  String concatenation                      ║  └─┤ ? ╟──┤ > ║  ║ 1 ║     └─┤ << ╟──┘
╟────────────────────────────────────────────╢    ╘═╤═╝  ╘═╤═╝  ╚═══╝ ╔═══╗ ╘══╤═╝
║  ‼(a, b) =                                 ║     ┌┴┐     └──────────╢ 0 ║   ┌┴┐
║     let c = 21 × ℓ(a);                     ║     └┬┘                ╚═══╝   └┬┘
║     (a < 0 ? a + (1 << c) : a) | (b << c)  ║      └──────────────┬───────────┘
╚════════════════════════════════════════════╝                     │
```

With string concatenation implemented, 99 bottles of beer on the wall is now very easy.

List handling

The Funciton language does not have any built-in functionality for lists; but that is not necessary because we can implement lists entirely in Funciton itself. The encoding used to represent lists in a single humongous integer is not fundamental to the language; anyone could come up with a different encoding and implement all the list handling functions for that.

(However, the official Funciton interpreter has a feature that allows you to trace the execution of a specific function. This feature will detect values that encode lists and decode them for the purposes of debugging. The encoding I describe here is the encoding understood by this feature of the interpreter as well as the one used by all the list handling functions.)

Since strings are encoded as integers, a list of integers can automatically double as a list of strings. Furthermore, since lists themselves are encoded as single integers, one can also have lists of lists, arbitrarily nested.

List encoding grammar

Since integers are arbitrary-size, we cannot assume each element in a list fits into any particular number of bits. Therefore, we have to define a variable-length encoding for integers. The encoding I used chops each integer into chunks of 21 bits. (The number 21 is arbitrary, but since characters in a string are already 21 bits, I decided to reuse the number.)

• In the above graphic, the least significant bit is on the left.
• Each element in the list is split into chunks of 21 bits.
• The least significant bits of the final encoding contain the most significant chuck from the element.
• Each chunk is preceded by a continuation bit: 0 = more chunks to come, 1 = this is the last chunk.
• The last chunk is followed by a sign bit. If the sign bit is set, the entire element is stored negated.

Notice that this encoding has several consequences:

• The empty list is represented by the number 0.
• The number 1 encodes a list containing one element, which is 0.
• The number 2 is not a valid list.
• Negative numbers also never constitute a valid list.
• Many of the list functions will get stuck in infinite loops if you pass them an invalid list.

Examples

List containing two items, each ≤ 21 bits long (again, in this diagram, the least significant bit is on the left):

List containing one item between 22 and 42 bits long:

Lambda expressions

Since Dec 2013, Funciton supports lambda expressions (anonymous functions). There are two new types of box for this, summarized in the following:

``` ╔══════════════════════════════╗          ╔══════════════════════════════╗
║       Lambda expression      ║          ║       Lambda invocation      ║
╟──────────────────────────────╢          ╟──────────────────────────────╢
║             output 1         ║          ║           lambda             ║
║                ↓             ║          ║             ↓                ║
║              ╔═╧═╕           ║          ║           ┌─┴─╖              ║
║  output 2 → ─╢   ├─ → input  ║          ║  input → ─┤   ╟─ → output 2  ║
║              ╚═╤═╛           ║          ║           └─┬─╜              ║
║                ↓             ║          ║             ↓                ║
║              lambda          ║          ║          output 1            ║
╚══════════════════════════════╝          ╚══════════════════════════════╝
```

Every lambda has one input (parameter) and two outputs (return values). In cases where only one output is desired, the convention is that the lambda expression returns 0 for the second output and the invocation uses a Starkov construct to discard it.

Since a lambda can easily itself return a lambda, any number of parameters are possible via currying. Similarly, if more than two return values are desired, simply return the first value in output 1 and another lambda in output 2 which will successively produce the remaining values.

Since we already have lists, we can now implement interesting operations that take a list and a lambda. The map and filter functions (well-known to functional programmers) can be implemented thusly:

```                   ┌──────────────┐
┌──────────────┴─────┐      ╓─┴─╖          ╔════════════════════════════════╗
│   ┌───┬─┐          │      ║ ᴍ ║          ║  map a function over a list    ║
│ ┌─┴─╖ └─┘  ┌───╖ ┌─┴─╖    ╙─┬─╜          ╟────────────────────────────────╢
└─┤   ╟──────┤ › ╟─┤ ᴍ ║   ┌──┴──┐         ║  ᴍ(l, f) =                     ║
└─┬─╜      ╘═╤═╝ ╘═╤═╝ ┌─┴─╖ ┌─┴─╖       ║      let (h, t) = ‹(l);        ║
│  ╔═══╗ ┌─┴─╖   └───┤ · ╟─┤ ‹ ╟─┐     ║      l ? ›(ᴍ(t, f), f(h)) : 0  ║
│  ║ 0 ╟─┤ ? ╟───┐   ╘═╤═╝ ╘═══╝ │     ╚════════════════════════════════╝
│  ╚═══╝ ╘═╤═╝   └─────┘         │
│          └───                  │
└────────────────────────────────┘

┌────────────────────────────┐
│             ┌───╖ ┌───┐    │
│     ┌───────┤ ‹ ╟─┘ ┌─┴─╖  │
│ ┌───┴─────┐ ╘═╤═╝   │ Ƒ ╟──┤         ╔══════════════════════════════════╗
│ │         │   └─┐   ╘═╤═╝  │         ║  filter a list                   ║
│ │ ┌───╖ ┌─┴─╖ ┌─┴─╖ ┌─┴─╖  │         ╟──────────────────────────────────╢
│ └─┤ › ╟─┤ · ╟─┤ · ╟─┤ · ╟──┘         ║  Ƒ(l, f) =                       ║
│   ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝            ║      let (h, t) = ‹(l);          ║
│   ┌─┴─╖ ┌─┴─╖ ┌─┴─╖   ├────┐         ║      let r = Ƒ(t, f);            ║
└───┤ ? ╟─┤   ╟─┤ · ╟───┘  ╓─┴─╖       ║      l ? f(h) ? ›(r, h) : r : 0  ║
╘═╤═╝ └─┬─╜ ╘═╤═╝      ║ Ƒ ║       ╚══════════════════════════════════╝
╔═══╗ ┌─┴─╖   ├─┐   │        ╙─┬─╜
║ 0 ╟─┤ ? ╟─┐ └─┘   ├──────────┘
╚═══╝ ╘═╤═╝ └───────┘
└──
```

Observe that both examples use only the first lambda output as they use a Starkov construct to swallow the other one.

The following (partial) code would use the above filter function to extract only the odd numbers from a list.

```           (list)
↓
┌─┴─╖
│ Ƒ ╟──
╘═╤═╝
╔═══╗     ╔═╧═╕  ╔═══╗
║ 1 ╟──┬──╢   ├──╢ 0 ║
╚═══╝ ┌┴┐ ╚═╤═╛  ╚═══╝
└┬┘   │
└────┘
```

This example provides a lambda expression that bitwise-ands its input with 1 (and sets the second return value to zero as is conventional for single-output lambdas), thus returning 0 for even numbers, causing those to be filtered out.

Since the only datatype in Funciton is the arbitrary-size integer, a compliant interpreter must allocate a non-zero integer to every lambda closure the program creates. The lambda expression box returns an integer that identifies the closure, and the lambda invocation box will use the number to identify the lambda closure to invoke. This approach has many advantages; in particular, you can automatically have lists of functions. The integers returned are required to be non-zero as a convenience so that the user code can still use the number 0 to mean null or false in cases where a lambda is optional.

Now that we have lambda expressions, we can do with them some of the things that are typical of functional programming languages. For example, if we take two lambdas that each produce only one output, we can implement function composition easily:

```           ╓───╖
┌────╢ ∘ ╟────┐
│    ╙───╜    │
│   ┌───┬─┐   │          ╔════════════════════════╗
│ ┌─┴─╖ └─┘ ┌─┴─╖ ┌─┐    ║  Function composition  ║
└─┤   ╟─────┤   ╟─┴─┘    ╟────────────────────────╢
└─┬─╜     └─┬─╜        ║  ∘(f, g) = α·f(g(α))   ║
│ ╔═══╗ ╔═╧═╕        ╚════════════════════════╝
│ ║ 0 ╟─╢   ├─┐
│ ╚═══╝ ╚═╤═╛ │
│       └─┘   │
└─────────────┘
```

Lazy-evaluated sequences

Another exciting use-case for lambda expressions is lazy-evaluated sequences.

First, we decide to use the number `0` to represent an empty sequence. The lambda expression feature specifically allocates only positive integers to represent lambdas for exactly this kind of purpose. This way we can always use the `?` function to test if a sequence is empty.

Second, we make use of the ability for lambda expressions to return two outputs. The first output returns the first element (the head), while the second returns the rest of the sequence (the tail). If the rest of the sequence is empty, this is `0`; otherwise, it’s another lambda. This way, we can retrieve element after element simply by calling the lambdas until we get `0`.

To illustrate this, let’s write a function that takes an input value and returns a lazy sequence containing just that value and nothing else:

```           ╓───╖
║ ⌑ ║
╙─┬─╜
╔═══╗ ╔═╧═╕  ┌─┐
║ 0 ╟─╢   ├──┴─┘
╚═══╝ ╚═╤═╛
│
```

The function’s argument goes into the lambda expression’s first output, making it the head of the sequence. The second output is set to `0`, which indicates the end of the sequence. The completed lambda expression is returned as the function’s output. (The lambda expression doesn’t care what value you pass into it when you call it, so it uses a Starkov construct to nullify its input.)

We can go further than this. If we wanted a sequence containing lots of repetitions of a value, we could concatenate sequences like the above, but there’s a more elegant way. Consider this function:

```           ╓───╖
║ ⁞ ║
╙─┬─╜
╔═╧═╕  ┌─┐
┌─╢   ├──┴─┘
│ ╚═╤═╛
└───┴──┐
│
```

This is almost the same function as above, only instead of the `0` (which would indicate the end of the sequence) it returns another copy of the same lambda. This means that every time you call the lambda, you get the value and another copy of the same lambda. You keep getting the same value and never reach the end of the sequence. We have created an infinite sequence that repeats a value indefinitely.

Since the sequences are lazy-evaluated — meaning the next element in a sequence is not evaluated until you ask for it by invoking the lambda — they do not actually have to terminate. You only need a terminating sequence if your code actually traverses the whole sequence until it encounters the `0` that indicates its end.

To round this up, let’s take a look at the truncate function. You could use this to turn an infinite sequence into a finite one for output.

```         ┌────────────┬───────────┐
┌─┴─╖          │  ╓───╖    │
┌─┤   ╟─────┐    └──╢ ȶ ╟──┐ │
│ └─┬─╜   ┌─┴─╖     ╙───╜  │ │    ╔═════════════════════════════╗
│   └─────┤ · ╟────┐       │ │    ║  truncate                   ║
│         ╘═╤═╝    │       │ │    ╟─────────────────────────────╢
│   ┌───┐ ┌─┴─╖  ╔═╧═╕     │ │    ║  Truncates a lazy sequence  ║
│  ┌┴┐  │ │ ȶ ╟──╢   ├─┬─┐ │ │    ║  after at most n elements   ║
│  └┬┘  │ ╘═╤═╝  ╚═╤═╛ └─┘ │ │    ╟─────────────────────────────╢
│ ┌─┴─╖ └───┘    ┌─┴─╖     │ │    ║  ȶ(q, n) =                  ║
│ │ ♯ ║ ┌────────┤ · ╟───┐ │ │    ║    let (e, r) = q(0);       ║
│ ╘═╤═╝ │        ╘═╤═╝   ├─┘ │    ║    q ? n ? •[e, ȶ(r, n−1)]  ║
│  ┌┴┐  │        ┌─┴─╖   │   │    ║      : 0 : 0                ║
│  └┬┘  │   ┌────┤ ? ╟───┘   │    ╚═════════════════════════════╝
│   └───┘   │    ╘═╤═╝       │
│         ╔═╧═╗  ┌─┴─╖       │
└─────────╢ 0 ╟──┤ ? ╟───────┘
╚═══╝  ╘═╤═╝
│
```

If the input sequence is empty, or n = 0, return an empty sequence. In all other cases, return a lambda expression that will retrieve the head of the original sequence and then call truncate recursively with n decremented. Eventually this will reach 0 and the sequence terminates. Observe how this will evaluate each element of the original sequence only if and when the new sequence is evaluated. In the same manner, all the other familiar functional constructions, like map, filter, zip, etc. can be implemented, and unlike the map and filter function we defined for lists above, which always evaluate the entire result list, these would be lazy as well and would therefore work on infinite sequences as well.

More functions

The interpreter comes with an extensive library of useful functions, all listed here:

Fundamentals

· cross-nop (used to cross wires, otherwise a no-op) less than greater than equal to less than or equal to greater than or equal to not equal to conditional operator (if a, then b, else c) shift left shift right XOR (exclusive or)

Arithmetic

♭ predecessor function (minus one) addition (plus) subtraction (minus) unary minus (negative) absolute value multiplication (times) division modulo (negative for negative a; the way most programming languages define it) modulo (always non-negative for positive b; the way mathematicians define it) division and modulo (two-input, two-output function) exponentiation (to the power of) (using up-arrow notation) factorial Fibonacci function (full integer range) Lucas function (full integer range) Ackermann function

Prime numbers

Ṗ lazy sequence of primes up to n lazy sequence of prime factorization of n (empty for n < 2)

String handling

The numbers 0 and −1 both represent the empty string.

ℓ string length string concatenation substring (string, index, length) index of first occurrence of a substring, or −1 if not found (haystack, needle) repeat string a number of times (string, number) reverse string convert string to a lazy sequence of its characters parse string containing decimal digits into an integer (0 if any other characters are encountered) convert integer to string

List handling

The number 0 represents the empty list.

‹ returns head and tail returns result list only adds element to end of list returns leg and foot returns head bitlength and tail returns nth element and its bit offset returns (length − n)th element’s index and bit offset set nth element to a new element returns index of first element that matches a predicate (or −1) returns index of last element that matches a predicate (or −1) returns bit length of all items in list computes a single value by iteratively applying a lambda to each element concatenates two lists counts the number of elements that match a predicate removes duplicate elements from a list
ɛ returns nth element returns (length − n)th element takes index and length, works just like substring returns a list containing only elements that match a predicate index of first occurrence of element (or −1) index of last occurrence of element (or −1) insert element at index returns number of items in list passes every element through a lambda and returns the new list remove element at index reverse list bit offset of nth element bit offset of (length − n)th element returns unshifted list and bitlength of new element concatenates all the lists in a list of lists into a single list

Lazy-evaluated sequences

The number 0 represents the empty sequence. Everything else is a lambda expression that returns the head element and the tail. The tail is another lazy sequence, or 0 if the sequence ends here.

⌠ converts a lazy sequence to a list converts a list to a lazy sequence Fibonacci numbers as an infinite lazy sequence monadic return (lazy sequence containing a single value) repeat a value indefinitely alternate two values indefinitely cycle three values indefinitely all integers starting at x n consecutive integers starting at x concatenate two sequences append a single element to the end of a sequence `−1` if two sequences are equal, `0` otherwise maps a function over the Cartesian product of two sequences lazily split a string at every occurrence of a substring index of first element satisfying a predicate (or `−1`) index of last element satisfying a predicate (or `−1`) first element or default value if sequence empty last element or default value if sequence empty `−1` if all elements satisfy a predicate, `0` otherwise monadic bind (map + concatenate) number of elements
ƈ `−1` if element is in the sequence, `0` otherwise adds an element to a sequence only if it is empty `−1` if any element satisfies a predicate, `0` otherwise retrieve element by its index return only elements that match a predicate computes a value by iteratively applying a lambda to each element group by the results of a selector (result is a sequence of sequences) concatenate sequence of strings using separator pass every element through a lambda omit (remove) element by its index compute all permutations (result is a sequence of sequences) product of all elements in a sequence reverse a lazy-evaluated sequence compute all subsequences (result is a sequence of sequences) ascending sort according to the results of a selector descending sort according to the results of a selector sum of all elements in a sequence remove the first n elements stop after at most n elements pass every pair of same-index elements through a lambda