How to implement + in a language where functions accept only one argument? [closed]

Question

While reading about currying, I found the argument that it is beneficial in languages, which have only functions accepting only one argument.

I am wondering how to implement a 2-ary function like the addition in a language having only 1-ary functions?

The cited blog gives the following example:

function threeArity(x: number, y: number, z: number): number {
    return x + y + z;
}

function curriedThree(x: number): (y: number) => ((z: number) => number) {
    return function (y: number): (z: number) => number {
        return function (z: number): number {
            return x + y + z;
        }
    }
}

console.log(threeArity(1, 2, 3));
console.log(curriedThree(1)(2)(3));

But I think this is cheating, because in the end the 2-ary + is used. If the language has only 1-ary functions such a 2-ary + can not exist. How would a 1-ary addition look like?

Answer 1

I think this is cheating, because in the end the 2-ary + is used. If the language has only 1-ary functions such a 2-ary + can not exist.

Not so—in GHC Haskell, the primitive operations are still defined with curried function types. For instance, the unboxed integer addition operator is this: (+#) :: Int# -> Int# -> Int#. If you apply it to two operands, it can compile directly to an addition instruction; but you can also allocate a closure by applying it to only one operand.

In JavaScript, of course that isn’t the case: the curried function needs to be defined in terms of the binary + operator. However, it’s worth noting that in JavaScript and many other languages, this is a primitive binary operation that isn’t a function.

In a similar vein, Haskell’s tuple type can be constructed with a function (,) :: a -> b -> (a, b), or with built-in tuple syntax, which has its own typing rule unrelated to functions: (e1, e2) :: (A, B) if e1 :: A and e2 :: B.

How would a 1-ary addition look like?

If we don’t have any primitive binary operations like addition, we might still implement it using only a unary increment operation. But supposing we didn’t even have that, we could still construct it using Church encoding.

Numerals are made from the zero numeral Z and the successor function S. A numeral has two parameters: an “increment” function for the inductive case, and an initial “zero” value for the base case. Its numeric value is encoded implicitly, in unary, by the number of times that it applies the function to the value. For example, 2 is S(S(Z)).

const Z =
  (inc) => (zero) => zero;

const S =
  (n_times) =>
    (inc) => (zero) => inc(n_times(inc)(zero));

The addition of two numerals, add2, is just applying one numeral after the other, with the same increment function, to an initial value. So add2( S(S(Z)) )( S(S(Z)) ) (2 + 2) should be equivalent to S(S(S(S(Z)))) (4). Adding three numerals, add3, can be done similarly, or in terms of add2.

const add2 =
  (m_times) => (n_times) =>
    (inc) => (zero) => m_times(inc)(n_times(inc)(zero));

const add3 =
  (x) => (y) => (z) => add2(x)(add2(y)(z));

Now we can make a few constants, or a conversion from JavaScript’s native Number type, as well as an example expression.

const one = S(Z);
const two = S(one);
const three = S(two);

function from_number(x) {
  let n = Z;
  for (let i = 0; i < x; ++i) {
    n = S(n);
  }
  return n;
}

const one_plus_two_plus_three = add3(one)(two)(three);

We can test that the example term gives the right answer by converting it back to a printable type such as Number.

const number_zero = 0;
const number_inc = (x) => x + 1;
const to_number = (n) => n(number_inc)(number_zero);

console.log(to_number(one_plus_two_plus_three));

In general, any target type will work, since numerals are polymorphic. Here’s a conversion of the numeral n to a String of n asterisks.

const asterisk_zero = "";
const asterisk_inc = (x) => x + "*";
const to_asterisk = (n) => n(asterisk_inc)(asterisk_zero);

console.log(to_asterisk(one_plus_two_plus_three));

Answer 2

I think this comment from benrg is a useful insight:

There is a binary operator in lambda calculus, namely function application. You could argue that it's a two-argument function.

In other words, we can express anything in the form apply(function, argument) by carefully choosing values for function and argument.

In the expression 1 + 3, we have three pieces of information: the operator/function add, and the numerals 1 and 3. If we had a function apply(function, argument1, argument2), we could write apply(add, 2, 3). But if we have only apply(function, argument), where does the extra piece of information go?

The answer is into the definition of function: instead of add, we define a function add2, so that we can write apply(add2, 3).

---

Let's start by defining add1. If you only need to handle a finite set of numbers, you can do this with an exhaustive lookup table. In Haskell, you could do this with pattern matching; in JavaScript, you could use a switch statement:

add1 = (n) => { 
    switch(n) {
        case 0: return 1;
        case 1: return 2;
        case 2: return 3;
        // etc
    }
}

We could use the same technique to write add2, add3, and so on; but actually we don't need to if we realise that adding 2 is the same as adding 1, then adding 1 again. In other words, given a definition of add1, we can do this:

add2 = (n) => add1(add1(n));
add3 = (n) => add1(add1(add1(n)));
// etc

The only extra case we need is add0, which just returns its input unchanged. This is known as the "identity function":

identity = (x) => x
add0 = identity

To add any pair of numbers, we need a function which takes a number, and returns a function which adds that number: for the input 2, return the function add2, and so on. Again, a simple implementation could use a lookup table:

add = (m) => {
    switch(m) {
       case 0: return add0;
       case 1: return add1;
       case 2: return add2;
       case 3: return add3;
       // ...
    }
}

So now, without ever defining 2-ary addition directly, we have our curried implementation:

add(2)(3);

---

There's various ways we can take this further. One is by deciding the pattern of repeatedly applying add1 is something we might want to use with other functions. So we could write some helpers which take a function, and return a new function applying it multiple times:

repeat2 = (func) => (x) => func(func(x))
add2 = repeat2(add1)

As before, there are some special cases to consider:

• repeat0 needs to ignore the function passed to it, and use a function that "does nothing" in its place: the identity function we defined earlier. In other words, repeat0(anything)(n) will reduce to identity(n), which is just n.
• repeat1 could be written the same way as the others, as (func) => (x) => func(x), but (x) => func(x) is equivalent to func. That leaves (func) => func, which is just identity again. That makes sense: repeating something once is the same as just doing the thing.

repeat0 = (func) => identity
repeat1 = identity

Then, just as we did for add, we can write a general repeat function which takes a number, and returns an appropriate repeatN function:

repeat = (times) => {
    switch (times) {
        case 0: return repeat0;
        case 1: return repeat1;
        case 2: return repeat2;
        case 3: return repeat3;
        // ...
    }
}

Or, if we skip the separate named functions, and put everything into repeat itself:

repeat = (times) => {
    switch (times) {
        case 0: return (func) => identity;
        case 1: return identity;
        case 2: return (func) => (x) => func(func(x));
        case 3: return (func) => (x) => func(func(func(x)));
        // ...
    }
}

Now we can simplify our definitions of add2, add3, etc:

add2 = repeat(2)(add1)
add3 = repeat(3)(add1)

Another thing we can do is skip the named definitions of add2, add3, etc and move their definitions inside add itself:

add = (m) => {
    switch(m) {
       case 0: return identity;
       case 1: return add1;
       case 2: return repeat(2)(add1);
       case 3: return repeat(3)(add1);
       // ...
    }
}

But hang on, we know that repeat(0)(add1) is identity, and repeat(1)(add1) is add1

So we don't actually need the lookup table any more, we can just use repeat:

add = (m) => repeat(m)(add1)

So we've defined add based on just three functions: identity, repeat, and add1.

---

We can carry on further if we want to: Church encoding gives definitions for both add1 (a successor function) and repeat using recursive application of a single function, rather than a lookup table.

Answer 3

Assuming a functional language with currying and only unary functions where add implements addition:

• add has type int -> (int -> int)
• add 5 returns an (anonymous) unary function that adds 5 to its argument
• (add 5) 7 would apply this function to 7 - resulting in 12.

Usually the parentheses are not written explicitly because -> is right associative and function application is left associative.

Transforming x + y into add x y is purely syntactical and is performed by the parser of the language.