6
$\begingroup$

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?

$\endgroup$
11
  • 2
    $\begingroup$ You can go as deep down the rabbit hole as you like. The answers go as far as Church encoding. If you're interested in the abstract details of the bit, then there's your answer. If you're interested in doing currying in a practical programming language, then using a bootstrapped or built-in + is your answer. $\endgroup$ Nov 24, 2023 at 17:56
  • 9
    $\begingroup$ I don't understand this as a question about language design or implementation. When you implement a programming language, you generally do so in a different language (the host language). So even if your language doesn't support 2-ary functions or operators, you can still implement your curried "plus" function using the host language's + operator. $\endgroup$
    – kaya3
    Nov 24, 2023 at 18:16
  • 1
    $\begingroup$ @kaya3, the point is that you can't self-express the fundamentals of the language, following your logic. Obviously, a simplistic and limited language can always be expressed by calling into a more fundamental and more complete language. A language considering only of 1-adic functions is a simplistic and limited language, which is either computationally useless, or it is implemented in terms of a much more complicated assembly language (i.e. it relies on causing certain computations to occur which cannot be expressed in the language itself). $\endgroup$
    – Steve
    Nov 24, 2023 at 20:11
  • 4
    $\begingroup$ @Steve That's not a language design or implementation problem, though. In practice a language doesn't need to self-express its own native operations (including addition), they are implemented in some other language, or ultimately implemented by logic gates in hardware. $\endgroup$
    – kaya3
    Nov 24, 2023 at 21:59
  • 1
    $\begingroup$ @kaya3, it's a problem for those who are trying to discern whether they've understood a particular language correctly, and whether a particular language incorporates concepts that can cope with all essential aspects of what a computer does. Even hardware gates have multiple inputs as standard. The purpose of questions like these is not to understand languages in their own terms - it is to establish whether a particular language is fit to be integrated into an all-encompassing mental model. So what the language claims to do has to reconcile globally within your own understanding. (1/2) $\endgroup$
    – Steve
    Nov 25, 2023 at 4:17

3 Answers 3

12
$\begingroup$

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));
$\endgroup$
3
  • $\begingroup$ Comments have been moved to chat; please do not continue the discussion here. Before posting a comment below this one, please review the purposes of comments. Comments that do not request clarification or suggest improvements usually belong as an answer, on Programming Language Design and Implementation Meta, or in Programming Language Design and Implementation Chat. Comments continuing discussion may be removed. $\endgroup$
    – Michael Homer
    Nov 25, 2023 at 20:08
  • 1
    $\begingroup$ I allowed myself to extend your example a bit, to make it more obvious what is part of the Church encoding and what is not. And now I am wondering if the Church encoding is just another fancy way of cheating. Because the actual addition happens in the incrementation. But the Church encoding does not say anything about the incrementation, it just uses it as a parameter. $\endgroup$
    – ceving
    Nov 26, 2023 at 10:03
  • $\begingroup$ @ceving Maybe const number_inc = (x) => ++x would be clearer? There's no two-operand addition needed, just a rule that can take any number, and return the "next" number. $\endgroup$
    – IMSoP
    Nov 27, 2023 at 20:34
5
$\begingroup$

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.

$\endgroup$
1
3
$\begingroup$

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.

$\endgroup$
1

Not the answer you're looking for? Browse other questions tagged .