In Scheme, how can I understand "(define (f x . y) (cons x y))"

Question

I'm new to Scheme, here I get in trouble with dotted list, here is an example:

(define (f x . y) (cons x y))

When I enter: (f 1 2 3) the result is '(1 2 3). Yes, it returns a list, and at this time

x => 1 and y => '(2 3).

My question is how could the interpreter know this when f takes unfixed length of args?

Answer 1

I'm new to Scheme, here I get in trouble with dotted list, here is an example:

(define (f x . y) (cons x y))

When I enter: (f 1 2 3) the result is '(1 2 3). Yes, it returns a list, and at this time

x => 1 and y => '(2 3).

My question is how could the interpreter know this when f takes unfixed length of args?

It's not quite right to say that f takes an unfixed, or arbitrary, number of arguments. It doesn't. It requires at least one argument. If you try calling (f), you'll get an error. The key to understanding what's going on here may be understanding the dotted pair notation in Lisps. It's covered in another Stack Overflow question, Dot notation in scheme, but the short version is that every list is built from pairs. A single pair can be written as (car . cdr). E.g., (cons 1 2) => (1 . 2). A list like (1 2 3) is actually a pair whose cdr is another pair whose cdr is another pair, etc.: (1 . (2 . (3 . ()))). Because that's awkward to read, we typically remove all but the last dot when we write a chain of pairs, and if the last cdr is (), we omit the dot and (), too. So

(1 . (2 . (3 . 4))  === (1 2 3 . 4)
(1 . (2 . (3 . ())) === (1 2 3)

Noete that while the default printer won't print it this way, the list (1 2 3 4) can also be written in these ways:

(1 . (2 3 4)) === (1 2 . (3 4)) === (1 2 3 . (4))

While it won't print that way, you can write that and the system will understand it. E.g.,

> '(1 2 . (3 4))
(1 2 3 4)

That may be the key to understanding the lambda-list notation. When we write a lambda list for a function, it represents a function, and that lambda list gets destructured against the arguments. So, if we have following lambda lists and use them to destructure the argument list (1 2 3), we get the resulting bindings:

lambda-list    x             y      z
-------------------------------------
(x y z)        1             2      3
(x y . z)      1             2    (3)
(x . y)        1         (2 3)    n/a
x              (1 2 3)     n/a    n/a

That last case might be surprising, but you can test that all of these actually work as expected:

((lambda (x y z)   (list x y z)) '(1 2 3)) => (1 2 3)
((lambda (x y . z) (list x y z)) '(1 2 3)) => (1 2 (3))
((lambda (x . y)   (list x y))   '(1 2 3)) => (1 (2 3))
((lambda x         (list x))     '(1 2 3)) => ((1 2 3))

That last one is kind of neat, because it means that if it weren't part of the language already, you could do:

(define (list . elements) elements)