What does the lambda calculus have to say about return values?

Question

It is by now a well known theorem of the lambda calculus that any function taking two or more arguments can be written through currying as a chain of functions taking one argument:

# Pseudo-code for currying
f(x,y) -> f_curried(x)(y)

This has proven to be extremely powerful not just in studying the behavior of functions but in practical use (Haskell, etc.).

Functions returning values, however, seem to not be discussed. Programmers typically deal with their inability to return more than one value from a function by returning some meta-object (lists in R, structures in C++, etc.). It has always struck me as a bit of a kludge, but a useful one.

For instance:

# R code for "faking" multiple return values
uselessFunc <- function(dat) {
   model1 <- lm( y ~ x , data=dat )
   return( list( coef=coef(model1), form=formula(model1) ) )
}

Questions

1. Does the lambda calculus have anything to say about a multiplicity of return values? If so, do any surprising conclusions result?
2. Similarly, do any languages allow true multiple return values?

Answer 1

According to the Wikipedia page on lambda calculus:

Lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion

And a function, in the mathematical sense:

Associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output

So answering your first question no, lambda calculus (or any other formalism based on mathematical functions) can not have multiple return values.

For your second question, as far as I know, programming languages that implement multiple return values do so by packing multiple results in some kind of data structure (be it a tuple, an array, or even the stack) and then unpacking it later - and that's where the differences lie, as some programming languages make the packing/unpacking part transparent for the programmer (for instance Python uses tuples under the hood) while other languages make the programmer do the job explicitly, for example Java programmers can simulate multiple return values to some extent by packing multiple results in a returned Object array and then extracting and casting the returned result by hand.

Answer 2

A function returns a single value. This is how functions are defined in mathematics. You can return multiple values by packing them into one compound value. But then it is still a single value. I'd call it a vector, because it has components. There are vector functions in mathematics there, so there are also in programming languages. The only difference is the support level from the language itself and does it facilitate it or not.

Answer 3

Nothing prevents you from having multiple functions, each one returning one of the multiple results that you would like to return.

For example, say, you had the following function in python returning a list.

def f(x):
  L = []
  for i in range(x):
    L.append(x * i)
  return L

It returns [0, 3, 6] for x=3 and [0, 5, 10, 15, 20] for x=5. Instead, you can totally have

def f_nth_value(x, n):
  L = []
  for i in range(x):
    L.append(x * i)
  if n < len(L):
    return L[n]
  return None

Then you can request any of the outputs for a given input, and get it, or get None, if there aren't enough outputs:

In [11]: f_nth_value(3, 0)
Out[11]: 0

In [12]: f_nth_value(3, 1)
Out[12]: 3

In [13]: f_nth_value(3, 2)
Out[13]: 6

In [14]: f_nth_value(3, 3)

In [15]: f_nth_value(5, 2)
Out[15]: 10

In [16]: f_nth_value(5, 5)

Computational resources may be wasted if you have to do some of the same work, as in this case. Theoretically, it can be avoided by returning another function that holds all the results inside itself.

def f_return_function(x):
  L = []
  for i in range(x):
    L.append(x * i)
  holder = lambda n: L[n] if n < len(L) else None
  return holder

So now we have

In [26]: result = f_return_function(5)

In [27]: result(3)
Out[27]: 15

In [28]: result(4)
Out[28]: 20

In [29]: result(5)

Traditional untyped lambda calculus is perfectly capable of expressing this idea. (After all, it is Turing complete.) Whenever you want to return a bunch of values, just return a function that can give the n-th value for any n.

In regard to the second question, python allows for such a syntax, if you know exactly, just how many values the function is going to return.

def f(x):
  L = []
  for i in range(x):
    L.append(x * i)
  return L


In [39]: a, b, c = f(3)

In [40]: a
Out[40]: 0

In [41]: b
Out[41]: 3

In [42]: c
Out[42]: 6

In [43]: a, b, c = f(2)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-43-5480fa44be36> in <module>()
----> 1 a, b, c = f(2)

ValueError: need more than 2 values to unpack

In [44]: a, b, c = f(4)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-44-d2c7a6593838> in <module>()
----> 1 a, b, c = f(4)

ValueError: too many values to unpack

Lastly, here is an example from this Lisp tutorial:

;; in this function, the return result of (+ x x) is not assigned so it is essentially
;; lost; the function body moves on to the next form, (* x x), which is the last form
;; of this function body. So the function call only returns (* 10 10) => 100
* ((lambda (x) (+ x x) (* x x)) 10)
=> 100
;; in this function, we capture the return values of both (+ x x) and (* x x), as the
;; lexical variables SUM and PRODUCT; using VALUES, we can return multiple values from
;; a form instead of just one
* ((lambda (x) (let ((sum (+ x x)) (product (* x x))) (values sum product))) 10)
=> 20 100

Answer 4

I write this as a late response to the accepted answer since it is wrong!

Lambda Calculus does have multiple return values, but it takes a bit to understand what returning multiple values mean.

Lambda Calculus has no inherent definition of a collection of stuff, but it does allow you to invent it using products and church numerals.

pure functional JavaScript will be used for this example.

let's define a product as follows:

const product = a => b => callback => callback(a)(b);

then we can define church_0, and church_1 aka true, false, aka left, right, aka car, cdr, aka first, rest as follows:

const church_0 = a => b => a;
const church_1 = a => b => b;

let's start with making a function that returns two values, 20, and "Hello".

const product = a => b => callback => callback(a)(b);
const church_0 = a => b => a;
const church_1 = a => b => b;
const returns_many = () => product(20)("Hello");
const at_index_zero = returns_many()(church_0);
const at_index_one = returns_many()(church_1);

console.log(at_index_zero);
console.log(at_index_one);

As expected, we got 20 and "Hello".

To return more than 2 values, it gets a bit tricky:

const product = a => b => callback => callback(a)(b);
const church_0 = a => b => a;
const church_1 = a => b => b;
const returns_many = () => product(20)(
    product("Hello")(
        product("Yes")("No")
    )
);
const at_index_zero = returns_many()(church_0);
const at_index_one = returns_many()(church_1)(church_0);
const at_index_two = returns_many()(church_1)(church_1)(church_0);

console.log(at_index_zero);
console.log(at_index_one);
console.log(at_index_two);

As you can see, a function can return an arbitrary number of return values, but to access these values, a you cannot simply use result()[0], result()[1], or result()[2], but you must use functions that filter out the position you want.

This is mindblowingly similar to electrical circuits, in that circuits have no "0", "1", "2", "3", but they do have means to make decisions, and by abstracting away our circuitry with byte(reverse list of 8 inputs), word(reverse list of 16 inputs), in this language, 0 as a byte would be [0, 0, 0, 0, 0, 0, 0, 0] which is equivalent to:

const Byte = a => b => c => d => e => f => g => h => callback =>
    callback(a)(b)(c)(d)(e)(f)(g)(h);

const Byte_one = Byte(0)(0)(0)(0)(0)(0)(0)(1); // preserves 
const Bit_zero = Byte_one(b7 => b6 => b5 => b4 => b3 => b2 => b1 => b0 => b0);

After inventing a number, we can make an algorithm to, given a byte-indexed array, and a byte representing index we want from this array, it will take care of the boilerplate.

Anyway, what we call arrays is nothing more than the following, expressed in higher level to show the point:

// represent nested list of bits(addresses) 
// to nested list of bits(bytes) interpreted as strings.
const MyArray = function(index) {
    return (index == 0)
        ? "0th"
        : (index == 1)
            ? "first"
            : "second"
        ;
};

except it doesnt do 2^32 - 1 if statements, it only does 8 and recursively narrows down the specific element you want. Essentially it acts exactly like a multiplexor(except the "single" signal is actually a fixed number of bits(coproducts, choices) needed to uniquely address elements).

My point is that is Arrays, Maps, Associative Arrays, Lists, Bits, Bytes, Words, are all fundamentally functions, both at circuit level(where we can represent complex universes with nothing but wires and switches), and mathematical level(where everything is ultimately products(sequences, difficult to manage without requiring nesting, eg lists), coproducts(types, sets), and exponentials(free functors(lambdas), forgetful functors)).