values function in Common Lisp

Question

Is the values function in Common Lisp just syntactic sugar for packaging multiple values into a list that gets destructured by the caller?. I am asking because I thought Common Lisp supports "true" multiple value return rather than returning a tuple or a list as in other languages, such as python. Someone just told me that it's just syntactic sugar, so I would like someone to kindly explain it. To try to understand the type that is returned by the values function, I typed (type-of (values 1 2 3)), and the output was BIT. I searched in the Common Lisp reference for that and I couldn't find it mentioned in the datatypes section. Also, can anyone share some resources that suggest how the values function is implemented in Common Lisp?. Thank you.

Maida

You have heard that Common Lisp has a standard? Here is the index. Lookup things like BIT and VALUES. BIT is under B and VALUES is under V. lispworks.com/documentation/HyperSpec/Front/X_Symbol.htm – Anemone

Thanks for the link, I understand what BIT is now. I initially Googled it and I couldn't find it. – Maida

Answer 1

Multiple Values in CL

The language Common lisp is described in the ANSI standard INCITS 226-1994 (R2004) and has many implementations. Each can implement multiple values as it sees fit, and they are allowed, of course, to cons up a list for them (in fact, the Emacs Lisp compatibility layer for CL does just that - but it is, emphatically and intentionally, not a Common Lisp implementation).

Purpose

However, the intent of this facility is to enable passing (at least some) multiple values without consing (i.e., without allocating heap memory) and all CL implementations I know of do that. In this sense the multiple values facility is an optimization.

Of course, the implementation of this feature can be very different for different platforms and scenarios. E.g., the first few (say, 20 - required by the standard) are stored in a static of thread-local vector, the next several (1000?) are allocated on the stack, and the rest (if needed) are allocated on the heap as a vector or list.

Usage

E.g., the function floor returns two values. If you write

(setq a (floor 10 3))

you capture only the first one and discard the second one, you need to write

(setf (values q r) (floor 10 3))

to capture both values. This is similar to what other languages might express as

q,r = floor(10,3)

using tuples, except that CL does not allocate memory to pass (just a few) multiple values, and the other languages often do.

IOW, one can think of multiple values as an ephemeral struct.

Note that CL can convert multiple values to lists:

(destructuring-bind (q r) (multiple-value-list (floor 10 3))
  ; use q & r here
  ...)

instead of the more efficient and concise

(multiple-value-bind (q r) (floor 10 3)
  ; use q & r here
  ...)

MV & type

CL does not have a special type for the "multiple value object" exactly because it does not allocate a separate object to pass around multiple values. In this sense one can, indeed, claim that values is syntactic sugar.

However, in CL one can declare a function type returning multiple values:

(declaim (ftype (real &optional real) (values real real)) floor)

This means that floor returns two values, both reals (as opposed to returning a value of type (values real real)), i.e., in this case one might claim abuse of notation.

Your case

In your specific case, type-of is an ordinary function (i.e., not a macro or special operator). You pass it a single object, 1, because, unless you are using multiple-value-bind and friends, only the first value is used, so

(type-of (values 1 2 3))

is identical to

(type-of 1)

and type of 1 is bit.

PS: Control return values

One use of values is to control the return values of a function. Normally a CL function's return values are those of the last form. Sometimes it is not desirable, e.g., the last form return multiple values and you want your function to return one value (or none, like void in C):

(defun 2values (x y)
  (floor y x))
(defun 1value (x y)
  (values (floor y x)))
(defun no-values (x)
  (print x)
  (values))

Incline

Awesome, that makes a lot of sense. Thank you for the nice detailed answer. – Maida

it is allocating memory, but on the stack. – Anemone

@RainerJoswig: not necessarily; this is implementation dependent. Some implementations use a static (thread-specific) storage. – Incline

Then it is allocating memory in that static storage for the return values, unless that static storage is already full. Then the static memory may have to be extended (if possible) or it may even cause a stack overflow... – Anemone

@RainerJoswig: they only need an array of length 20. – Incline

SBCL gives 536870911 as multiple-values-limit on my ARM computer... I doubt that I can return so many values without allocation memory. – Anemone

On my Mac the multiple-values-limit for SBCL is 4611686018427387903. Where, when not on the heap would it allocate memory for that? – Anemone

It will probably allocate those gazillion values on the heap. However, the INTENT of the facility is to avoid having to do that and I am sure they don't allocate the first few values on the heap. – Incline

Someone should point out or add that a non-return can be specified with (values) at the end. This would be something like a void return in other languages. – Humbug

Note that it's completely implementation dependant how the values are actually stored. It could be registers, or on the stack, or a thread-local vector, or a series of thread-local vectors for different amounts of values, or a top-of-the-stack-allocated vector, or a heap-allocated user-hidden vector type (thus no longer saving you from consing), or a freshly consed list in an interpreter, or a combination of these, or yet something else. I've seen a few of these in actual implementations. – Shredding

Answer 2

The values function isn't just syntactic sugar for making a list for the caller to destructure.

For one, if the caller expects only a single value, it will get only one value (the first), not a list, from a form that returns multiple values. Since type-of takes only one value as an argument, it is giving you the type of the first value, 1. 1 is of type BIT.

Each Common Lisp implementation is free to pursue its own strategy for implementing multiple values. I learned a lot from what Frode Fjeld wrote about how his implementation, Movitz, handles it in The Movitz development platform, section 2.5.

Wellordered

Thank you very much for that link, that certainly clarifies a lot of things. Btw, do you know if some Common Lisp implementations perform multiple value returns using lists or some other special structures?. – Maida

I don't think any implementation does that. – Wellordered

Allegro CL has mv-vector, apparently thread-bound instances, but I don't know how much of it can be regarded as a first-class Lisp object. The :i top-level command can inspect one, though. – Shredding

Answer 3

If you make a CL implementation you could implement it with lists as long as it coheres to the spec. You need to handle one value specific and you need some way to tag zero, 2..n values and the other functions need to understand that format and print can be made to display it the same way as in other makes.

Most likely values and its sister functions is an optimization where the implementations use the stack instead of consing the values to a list structure just to get it destructured in the next level. In the olden times where RAM and CPU was not to be wasted it was very important, but I doubt you'll notice real trouble should you use destructuring-bind instead of multiple-value-bind today.

Common Lisp differs from Scheme a great deal in the positive direction that you can make a function, eg. floor where in it's calculations end up with the remainder in addition to the quotient answer, return all values at the same time but you are allowed to use it as if it only returned the very first value. I really miss that sometimes when writing Scheme since it demands you have a call-with-values that is similar to multiple-value-call or syntactic sugar like let-values to handle all the returned values that again makes you end up with making three versions in case you only need just one of the values.

Crowning