values vs. list vs. CPS

19 views
Skip to first unread message

Thomas Hafner

unread,
Mar 30, 2005, 7:27:20 AM3/30/05
to
Hello,

to get a little practice in Scheme, I programmed the ``Towers of
Hanoi'' avoiding assignments. (Is ``Towers of Hanoi'' the correct
English name? I just translated it word by word from German. I mean
the task where a tower is build by several layers and has to be
shifted layer by layer onto another place respecting some special
rules.) If I avoid assignments, I have to recalculate the complete
``scene'' of the game everytime something has been changed (i.e. a
layer has been moved). I did program the ``Towers of Hanoi'' three
times depending on how a scene is represented:

- First[1] I used the procedure ``values'' to express a scene,
- then[2] I let represent a scene by a list, and
- finally[3] I used Continuation Passing Style.

If I look at the resulting programs, especially on the central
procedure ``move-tower'', I'm surprised, because I did not expect the
result:

- I like the list variant better than the values variant. I find the
list variant less verbose. Why does the procedure ``values'' exist?
Is it just a matter of taste? Are there any reasons despite taste to
prefer the values to list?

- I like the CPS version even more, although it was a little bit hard
to program CPS for the first time. The problem how to pass multiple
values does not arise, they just are passed to the continuation as
arguments, and it's a very natural thing that a funcion has several
arguments. But CPS doesn't seem to be very popular. E.g. most
examples in ``The Scheme Programming Language'' are not CPS. Is
there anything I should know in addition before trying to make it my
favorite style?

[1]<http://hafner.sdf-eu.org/pool/hanoi-values.scm>
[2]<http://hafner.sdf-eu.org/pool/hanoi-list.scm>
[3]<http://hafner.sdf-eu.org/pool/hanoi-cps.scm>

Regards
Thomas
--
Es ist viel später als du denkst.
-- Chinesisches Sprichwort

R. Mattes

unread,
Mar 30, 2005, 8:02:53 AM3/30/05
to
On Wed, 30 Mar 2005 14:27:20 +0200, Thomas Hafner wrote:

> Hello,
>
> to get a little practice in Scheme, I programmed the ``Towers of
> Hanoi'' avoiding assignments. (Is ``Towers of Hanoi'' the correct
> English name? I just translated it word by word from German. I mean
> the task where a tower is build by several layers and has to be
> shifted layer by layer onto another place respecting some special
> rules.) If I avoid assignments, I have to recalculate the complete
> ``scene'' of the game everytime something has been changed (i.e. a
> layer has been moved). I did program the ``Towers of Hanoi'' three
> times depending on how a scene is represented:
>
> - First[1] I used the procedure ``values'' to express a scene,
> - then[2] I let represent a scene by a list, and
> - finally[3] I used Continuation Passing Style.
>
> If I look at the resulting programs, especially on the central
> procedure ``move-tower'', I'm surprised, because I did not expect the
> result:
>
> - I like the list variant better than the values variant. I find the
> list variant less verbose. Why does the procedure ``values'' exist?
> Is it just a matter of taste? Are there any reasons despite taste to
> prefer the values to list?

Well, when you return a list the caller has to be aware of this and
in many cases needs to destructure the list. The caller of a function that
returns multiple values can ignore the fact that more than one value is
returned. Think of a function foo that returns an integer and an error
code:
(+ (foo 'a) (foo 'b))

will work. Iff foo would return a list (integer error-code) the code
would look like this:

(+ (car (foo 'a)) (car (foo 'b)))

I guess (values) makes the language more orthogonal: a function can both
receive and provide multiple values.


Just my 0.02$

Ralf Mattes

Scott G. Miller

unread,
Mar 30, 2005, 8:32:33 AM3/30/05
to

Thats not correct. In Scheme it is an error to return multiple values
into a context expecting a single value.

>
> I guess (values) makes the language more orthogonal: a function can both
> receive and provide multiple values.

This is the best aesthetic reason. Another way to phrase it is that
since the language has continuations, which are represented as function
calls, then its symmetric to allow multiple arguments to a continuation,
which creates the concept of multiple value returns.

There is also the argument that it gives you another distinct way to
pass multiple values out of a function, one that may be resolvable at
compile time (and thus you may catch any errors, which you may not with
list destructuring).

That said, there are more than a couple of arguments against multiple
values, which I expect you'll hear from other posters.

Scott

Thomas Hafner

unread,
Mar 30, 2005, 9:24:49 AM3/30/05
to

> Well, when you return a list the caller has to be aware of this and
> in many cases needs to destructure the list. The caller of a function that
> returns multiple values can ignore the fact that more than one value is
> returned. Think of a function foo that returns an integer and an error
> code:
> (+ (foo 'a) (foo 'b))
>
> will work.

Ok, I try this:

(define foo
(lambda (x)
(values (string-length (symbol->string x)) 'ok)))

(foo 'a) =>
1
ok

(foo 'b) =>
1
ok

(+ (foo 'a) (foo 'b)) =>
*** ERROR IN (console)@33.1 -- (Argument 1) NUMBER expected
(+ '#<unknown> '#<unknown>)

I'm using Gambit Version 4.0 beta 11. What's the matter? Does Gambit
lack some nonstandard functionality?

If I replace the symbol 'ok by a number, e.g. 0, it's the same result.

Regards
Thomas

--
Jemand mit einer Uhr, weiß stets wie spät es ist, jemand mit zwei
Uhren ist nie sicher.
-- Sprichwort

Sunnan

unread,
Mar 30, 2005, 9:37:29 AM3/30/05
to
To the original poster:
In some schemes values can be more efficient than lists.
I don't know of any schemes where this is true in practice, though.

Just yesterday, I wanted to make a variant of map that took multiple
values from the procedure it mapped over the lists. I did succeed, but I
ended up not using it, I ended up using append-map and have the
procedure return a list (since that was how my map-with-values worked
internally, anyway, so there was no effiency gain at all, only a loss).

Also, re CPS: many scheme compilers rewrite the code to CPS anyway
(which is one way to have an efficient implementation of values) and
maybe that's nicer than writing the CPS yourself.

Before I discovered scheme and what it can do, I occasionally wrote OOP
code in "object passing style", for recursive operations on
two-dimensional data structures of linked objects. This was annoying to
do and I'm happy that scheme now does it for me, that I don't have to
write CPS by hand.

The less I have to do by hand, the better.

Scott G. Miller wrote:
> Thats not correct. In Scheme it is an error to return multiple values
> into a context expecting a single value.

This is one of the few things I like better in CL. For a while I tried
to create a function, "safe-values", that acted like values does in CL -
e.g. return only one value if the context only expected one value - but
I never came up with a way to do it in pure scheme.

> That said, there are more than a couple of arguments against multiple
> values, which I expect you'll hear from other posters.

One argument seems to be based in math traditions.

Abdulaziz Ghuloum

unread,
Mar 30, 2005, 9:52:32 AM3/30/05
to
Thomas Hafner wrote:

> - I like the list variant better than the values variant. I find the
> list variant less verbose. Why does the procedure ``values'' exist?
> Is it just a matter of taste? Are there any reasons despite taste to
> prefer the values to list?
>
> - I like the CPS version even more, although it was a little bit hard
> to program CPS for the first time. The problem how to pass multiple
> values does not arise, they just are passed to the continuation as
> arguments, and it's a very natural thing that a funcion has several
> arguments. But CPS doesn't seem to be very popular. E.g. most
> examples in ``The Scheme Programming Language'' are not CPS. Is
> there anything I should know in addition before trying to make it my
> favorite style?

In CPS, you have explicit continuations and you can pass to the current
continuation either one value--by calling (k v)-- or many values by
applying (k v0 v1 v1 ...). In direct-style, there is an implicit
continuation. You can pass it one value by just returning v or many
values by doing (values v0 v1 ...).

Most examples in TSPL are not in CPS, correct. If you like CPS, there
is no reason why you can't program in CPS. If you have access to a
high-performance scheme implementation (think Chez), and your
application requires speed, you'll find that programs written in
direct-style outperform the same programs written in CPS (due to various
reasons that I won't list here). I believe this is why Kent
(implementor of Chez and author of TSPL) advocates this style in his
book.

Aziz,,,

Abdulaziz Ghuloum

unread,
Mar 30, 2005, 10:08:17 AM3/30/05
to
Sunnan wrote:

> To the original poster:
> In some schemes values can be more efficient than lists.
> I don't know of any schemes where this is true in practice, though.


Chez does, Petite does, and my compiler (which is not released) does.

Here is an example (along with some powerpc assembly) that shows the
relative performance of the two:

i> (assembler-output #t)
i> (#3%list 1 2 3 4)
0: (ppc:twnei ac 8) ; arg check
1: (ppc:addi p3 0 4)
2: (ppc:addi p2 0 8)
3: (ppc:addi p1 0 12)
4: (ppc:addi p0 0 16)
5: (ppc:addi cp 0 55)
6: (ppc:addi ac 0 0)
7: (ppc:stw ac ap 4088) ; fast heap-overflow check
8: (ppc:addi ac ap 3)
9: (ppc:addi ap ap 8)
10: (ppc:stw p0 ac -3)
11: (ppc:stw cp ac 1)
12: (ppc:addi cp ap 3)
13: (ppc:addi ap ap 8)
14: (ppc:stw p1 cp -3)
15: (ppc:stw ac cp 1)
16: (ppc:addi ac ap 3)
17: (ppc:addi ap ap 8)
18: (ppc:stw p2 ac -3)
19: (ppc:stw cp ac 1)
20: (ppc:addi p0 ap 3)
21: (ppc:addi ap ap 8)
22: (ppc:stw p3 p0 -3)
23: (ppc:stw ac p0 1)
24: (ppc:blr)
(1 2 3 4)
i> (#3%values 1 2 3 4)
0: (ppc:twnei ac 8) ; arg check
1: (ppc:addi p3 0 16)
2: (ppc:addi p2 0 12)
3: (ppc:addi p1 0 8)
4: (ppc:addi p0 0 4)
5: (ppc:addi ac 0 24)
6: (ppc:mflr cp)
7: (ppc:addi cp cp -16) ; multi-values have another return point
8: (ppc:mtlr cp)
9: (ppc:blr)
1
2
3
4


The list version allocates 4 pairs, and accessing elements of the list
would require more operations and many error checks. The values version
allocates nothing, it just returns the four values in registers p0 .. p3
which can be used directly by the caller.

Aziz,,,

Thomas Hafner

unread,
Mar 30, 2005, 10:13:47 AM3/30/05
to
"Scott G. Miller" <scgm...@freenetproject.org> wrote/schrieb <a9mdnXK1pvD...@giganews.com>:

> R. Mattes wrote:
> > I guess (values) makes the language more orthogonal: a function can
> > both
> > receive and provide multiple values.
>
> This is the best aesthetic reason. Another way to phrase it is that
> since the language has continuations, which are represented as
> function calls, then its symmetric to allow multiple arguments to a
> continuation, which creates the concept of multiple value returns.

A continuation gotten by call/cc is a function which expects only one
argument. So if somebody wants to pass multiple values to such a
function, the the procedure ``values'' can be used, Ok.

But in the example, that I call ``CPS variant'', a continuation can
receive more than one argument. Do I misuse the term continuation when
doing so? Is it still CPS? Here's the definition of the procedure
decrease-tower within the file hanoi-cps.scm:

(define decrease-tower
(lambda (tower k)
(apply
(lambda (name top . rest)
(k (cons name rest) top))
tower)))

k is what I intend to be a continuation in the sense of CPS. If I
wanted to return multiple values, I had to write something like
(values (cons name rest) top). But I prefer to pass two arguments to k
instead of only one. Is it Ok if I call k still a ``continuation''?
Nevertheless if ``continuation'' is the correct name or not, I find it
usefull.

Regards
Thomas
--
Wer nicht raucht und auch nichts trinkt, der ist schon auf andere Art
den Teufel verfallen.
-- Spanisches Sprichwort

Thomas Hafner

unread,
Mar 30, 2005, 10:49:13 AM3/30/05
to
Abdulaziz Ghuloum <aghu...@c-s-remove-dashes.indiana.edu> wrote/schrieb <d2efc1$js4$1...@rainier.uits.indiana.edu>:

> Here is an example (along with some powerpc assembly) that shows the
> relative performance of the two:
>
> i> (assembler-output #t)
> i> (#3%list 1 2 3 4)

> [...]


> i> (#3%values 1 2 3 4)

> [...]

Interesting, thanks for the performance demos.

They seem not to take into account, that typically the values resp.
list have/has to be received somewhere for future computing.

Measuring something like (foo1 (list 1 2 3 4)) resp.
(call-with-values (lambda () (values 1 2 3 4)) (foo2 u v w x))
would take that into account (of course foo1 and foo2 being as trivial
as possible).

Maybe I'm completely wrong and it doesn't make any difference, or let
look the list variant even worse, who knows ...

Regards
Thomas

Abdulaziz Ghuloum

unread,
Mar 30, 2005, 11:07:49 AM3/30/05
to
Thomas Hafner wrote:

> "Scott G. Miller" <scgm...@freenetproject.org> wrote/schrieb <a9mdnXK1pvD...@giganews.com>:
>
>
>>R. Mattes wrote:
>>
>>>I guess (values) makes the language more orthogonal: a function can
>>>both
>>>receive and provide multiple values.
>>
>>This is the best aesthetic reason. Another way to phrase it is that
>>since the language has continuations, which are represented as
>>function calls, then its symmetric to allow multiple arguments to a
>>continuation, which creates the concept of multiple value returns.
>
>
> A continuation gotten by call/cc is a function which expects only one
> argument. So if somebody wants to pass multiple values to such a
> function, the the procedure ``values'' can be used, Ok.

No. A continuation obtained by call/cc expects as many arguments as the
context of the call/cc expected:

(call-with-values (lambda () (call/cc (lambda (k) (k 1 2 3 4))))
(lambda (a b c d)
(* a b c d)))
=> 24

(call-with-values (lambda () (values 1 2 3 4))

(lambda (a b c d)
(* a b c d)))
=> 24

> But in the example, that I call ``CPS variant'', a continuation can
> receive more than one argument. Do I misuse the term continuation when
> doing so? Is it still CPS? Here's the definition of the procedure
> decrease-tower within the file hanoi-cps.scm:
>
> (define decrease-tower
> (lambda (tower k)
> (apply
> (lambda (name top . rest)
> (k (cons name rest) top))
> tower)))
>
> k is what I intend to be a continuation in the sense of CPS. If I
> wanted to return multiple values, I had to write something like
> (values (cons name rest) top). But I prefer to pass two arguments to k
> instead of only one. Is it Ok if I call k still a ``continuation''?

It is still a continuation.

By the way, are you abusing apply a little too much? Does your scheme
implementation have a patter-matching facility? Chez has a matcher
which allows you to day:

(define decrease-tower
(lambda (tower k)

(match tower
[(,name ,top ,rest ...) (k `(,name ,rest ...) top)])))

I am sure PLT and others have a similar match.

Aziz,,,

Sunnan

unread,
Mar 30, 2005, 11:22:43 AM3/30/05
to
Abdulaziz Ghuloum wrote:

> Sunnan wrote:
>> In some schemes values can be more efficient than lists.
>> I don't know of any schemes where this is true in practice, though.
> Here is an example (along with some powerpc assembly) that shows the
> relative performance of the two:

The implementation of call-with-values (which I mostly use in it's
"receive"-form) matters more, and how this is use.

I find that lots (not all) of the time when I use values, I end up
collecting the values in a list (for one reason or another) anyway.

Matthias Blume

unread,
Mar 30, 2005, 11:37:56 AM3/30/05
to
Sunnan <sun...@handgranat.org> writes:

Yes, VALUES is nothing more than a (questionable, IMO) performance hack.

There has been plenty of heated discussion on this topic in c.l.s, so
I'll not elaborate further.

Cheers,
Matthias

Abdulaziz Ghuloum

unread,
Mar 30, 2005, 12:03:41 PM3/30/05
to
Thomas Hafner wrote:

> Abdulaziz Ghuloum <aghu...@c-s-remove-dashes.indiana.edu> wrote/schrieb <d2efc1$js4$1...@rainier.uits.indiana.edu>:
>
>
>>Here is an example (along with some powerpc assembly) that shows the
>>relative performance of the two:
>>
>>i> (assembler-output #t)
>>i> (#3%list 1 2 3 4)
>>[...]
>>i> (#3%values 1 2 3 4)
>>[...]
>
>
> Interesting, thanks for the performance demos.
>
> They seem not to take into account, that typically the values resp.
> list have/has to be received somewhere for future computing.

Accessing a value you get in a register is free. Accessing a value you
get boxed in a list is not free (at least one memory reference, maybe
more, maybe some cache misses, maybe some runtime checks of pair?, maybe
some mispredicted branches, ...).


> Measuring something like (foo1 (list 1 2 3 4)) resp.
> (call-with-values (lambda () (values 1 2 3 4)) (foo2 u v w x))
> would take that into account (of course foo1 and foo2 being as trivial
> as possible).


i> (#3%call-with-values (lambda () (#3%values 1 2 3 4))
(lambda (u v w x)
(foo u v w x)))


0: (ppc:twnei ac 8)

1: (ppc:addi p0 0 4)
2: (ppc:addi p1 0 8)
3: (ppc:addi p2 0 12)
4: (ppc:addi p3 0 16)
5: (ppc:addis ac 0 (hi foo 0))
6: (ppc:ori ac ac (lo foo 0))
7: (ppc:lwz cp ac 10) ; this needs to be fixed (todo)
8: (ppc:lwz p4 cp -5)
9: (ppc:addi ac 0 24)
10: (ppc:mtctr p4)
11: (ppc:bctr)

i> (foo (#3%list 1 2 3 4))


0: (ppc:twnei ac 8)

1: (ppc:addis ac 0 (hi foo 0))
2: (ppc:ori ac ac (lo foo 0))
3: (ppc:lwz p4 ac 10)
4: (ppc:addi p3 0 4)
5: (ppc:addi p2 0 8)
6: (ppc:addi p1 0 12)
7: (ppc:addi p0 0 16)
8: (ppc:addi cp 0 55)
9: (ppc:addi ac 0 0)
10: (ppc:stw ac ap 4088)
11: (ppc:addi ac ap 3)
12: (ppc:addi ap ap 8)
13: (ppc:stw p0 ac -3)
14: (ppc:stw cp ac 1)
15: (ppc:addi cp ap 3)
16: (ppc:addi ap ap 8)
17: (ppc:stw p1 cp -3)
18: (ppc:stw ac cp 1)
19: (ppc:addi ac ap 3)
20: (ppc:addi ap ap 8)
21: (ppc:stw p2 ac -3)
22: (ppc:stw cp ac 1)
23: (ppc:addi p0 ap 3)
24: (ppc:addi ap ap 8)
25: (ppc:stw p3 p0 -3)
26: (ppc:stw ac p0 1)
27: (ppc:lwz p1 p4 -5)
28: (ppc:or cp p4 p4)
29: (ppc:addi ac 0 12)
30: (ppc:mtctr p1)
31: (ppc:bctr)

Building data structures (even if it's very cheap to do so) cannot
compare to passing the values directly in machine registers.

And this is one reason why Scheme has procedures that take any number of
arguments. One could argue that it's enough to have procedures that
take a single argument and that one could pass a list of things as a
single argument. (they also argue that a sufficiently smart compiler
could unbox the values when it can prove bla bla bla). For me, I want
to run my programs, run them now, and make them fast.

Aziz,,,

Abdulaziz Ghuloum

unread,
Mar 30, 2005, 12:15:46 PM3/30/05
to
Sunnan wrote:

Interesting. I almost never cons the values I get since they are
usually things of different kinds and will be used for different things
(for the same reason I almost never cons two arguments of a procedure)
If I needed to cons things together, I would return/pass a list. If I
don't need the list, they I pass/return multiple values.

Aziz,,,

Kristof Bastiaensen

unread,
Mar 30, 2005, 12:25:31 PM3/30/05
to
On Wed, 30 Mar 2005 14:37:29 +0000, Sunnan wrote:
> Scott G. Miller wrote:
>> Thats not correct. In Scheme it is an error to return multiple values
>> into a context expecting a single value.

Actually, the standard leaves that unspecified. An implementation can
choose to raise an error, or just take the first argument. Guile
even packs the values up into a values type, though I don't like that
solution, because then it becomes a datatype, instead of a way of passing
multiple values to continuations.

>
> This is one of the few things I like better in CL. For a while I tried
> to create a function, "safe-values", that acted like values does in CL -
> e.g. return only one value if the context only expected one value - but
> I never came up with a way to do it in pure scheme.
>

That's the way I would prefer it too.

KB

Kristof Bastiaensen

unread,
Mar 30, 2005, 12:29:22 PM3/30/05
to
On Wed, 30 Mar 2005 10:37:56 -0600, Matthias Blume wrote:
> Yes, VALUES is nothing more than a (questionable, IMO) performance hack.
>

Perhaps it is a way to make continuations more equal to scheme
functions, by allowing continuations to be passed multiple values.

KB

Abdulaziz Ghuloum

unread,
Mar 30, 2005, 12:23:10 PM3/30/05
to
Matthias Blume wrote:

> Yes, VALUES is nothing more than a (questionable, IMO) performance hack.
>
> There has been plenty of heated discussion on this topic in c.l.s, so
> I'll not elaborate further.

Yes. We all know by now how ML does things and how scheme is different.
:-)

Aziz,,,

Abdulaziz Ghuloum

unread,
Mar 30, 2005, 12:25:35 PM3/30/05
to
Kristof Bastiaensen wrote:

Some prefer the other way around by making functions more equal to
continuations (make everything take/return a single value).

Some don't prefer that of course :-)

Aziz,,,

Joe Marshall

unread,
Mar 30, 2005, 1:30:31 PM3/30/05
to
Thomas Hafner <uucp....@spamgourmet.com> writes:

> - I like the CPS version even more, although it was a little bit hard
> to program CPS for the first time. The problem how to pass multiple
> values does not arise, they just are passed to the continuation as
> arguments, and it's a very natural thing that a funcion has several
> arguments. But CPS doesn't seem to be very popular. E.g. most
> examples in ``The Scheme Programming Language'' are not CPS. Is
> there anything I should know in addition before trying to make it my
> favorite style?

I've always thought it'd be interesting to design a computer language
where CPS is the *only* way to program.

Joe Marshall

unread,
Mar 30, 2005, 1:31:31 PM3/30/05
to
Matthias Blume <fi...@my.address.elsewhere> writes:

> Sunnan <sun...@handgranat.org> writes:
>
>> Abdulaziz Ghuloum wrote:
>>> Sunnan wrote:
>>>> In some schemes values can be more efficient than lists.
>>>> I don't know of any schemes where this is true in practice, though.
>>> Here is an example (along with some powerpc assembly) that shows the
>>> relative performance of the two:
>>
>> The implementation of call-with-values (which I mostly use in it's
>> "receive"-form) matters more, and how this is use.
>>
>> I find that lots (not all) of the time when I use values, I end up
>> collecting the values in a list (for one reason or another) anyway.
>
> Yes, VALUES is nothing more than a (questionable, IMO) performance hack.

So are multiple arguments, for that matter.

Matthias Blume

unread,
Mar 30, 2005, 2:19:52 PM3/30/05
to
Abdulaziz Ghuloum <aghu...@c-s-remove-dashes.indiana.edu> writes:

Yes. And by having first-class multiple values, you can have the best
of both worlds.

> Some don't prefer that of course :-)

That's a theorem: For every PL design choice, there will be some who
prefer the opposite.

Matthias Blume

unread,
Mar 30, 2005, 2:23:36 PM3/30/05
to
Abdulaziz Ghuloum <aghu...@c-s-remove-dashes.indiana.edu> writes:

The point was that Scheme does not need to be different in this regard
-- without even breaking any existing code.

Matthias Blume

unread,
Mar 30, 2005, 2:24:05 PM3/30/05
to
Joe Marshall <j...@ccs.neu.edu> writes:

Well, there's always assembler...

Matthias Blume

unread,
Mar 30, 2005, 2:24:15 PM3/30/05
to
Joe Marshall <j...@ccs.neu.edu> writes:

Indeed.

Bruce Lewis

unread,
Mar 30, 2005, 2:38:02 PM3/30/05
to
Matthias Blume <fi...@my.address.elsewhere> writes:

I'd be interested to see a definition of (factorial n) in a
zero-or-one-argument language.

Joe Marshall

unread,
Mar 30, 2005, 3:26:14 PM3/30/05
to
Matthias Blume <fi...@my.address.elsewhere> writes:

That's a little extreme....


But, I have programmed in CPS in assembly by manually pushing multiple
return address when calling and doing some funky stack adjustment to
pop the right one on returning. It's not much more painful than doing
anything else in assembler, but most higher level languages can't
support CPS because they are either not tail-recursive or they cannot
handle the type inference.

That's probably not what you had in mind.

Matthias Blume

unread,
Mar 30, 2005, 3:56:04 PM3/30/05
to
Bruce Lewis <brl...@yahoo.com> writes:

> Matthias Blume <fi...@my.address.elsewhere> writes:
>
>> Joe Marshall <j...@ccs.neu.edu> writes:
>>
>> > Matthias Blume <fi...@my.address.elsewhere> writes:
>> >>
>> >> Yes, VALUES is nothing more than a (questionable, IMO) performance hack.
>> >
>> > So are multiple arguments, for that matter.
>>
>> Indeed.
>
> I'd be interested to see a definition of (factorial n) in a
> zero-or-one-argument language.

Hmm. Don't know what you are getting at. For example (not claiming
this is the most desirable way of doing it), assuming we have curried
functions * and -, here is what the Scheme code would look like:

(define (factorial n)
(if (zero? n) 1 ((* n) (fac ((- n) 1)))))

Or, if you like things to be tail-recursive:

(define (factorial n)
(define ((loop n) f)
(if (zero? n) f ((loop ((- n) 1)) ((* f) n))))
((loop n) 1))

Of course, what I was really thinking of was a language with
first-class tuples, in which case the factorial would just look like
it always does, except formally a two-argument function call passes a
single argument which is a pair.

Richard C. Cobbe

unread,
Mar 30, 2005, 4:08:01 PM3/30/05
to
Thomas Hafner <uucp....@spamgourmet.com> writes:

Right. Your function foo is returning multiple values to a context that
only expects a single value. This is not related to the fact that + can
take arbitrarily many arguments; neithe is it related to the fact that some
of the values returned by foo are not numbers.

I don't remember whether R5RS specifies how implementations should behave
in this case, but I do know you're not supposed to do it.

R. Mattes was incorrect, at least as far as Scheme is concerned.

Richard

Richard C. Cobbe

unread,
Mar 30, 2005, 4:02:40 PM3/30/05
to
Bruce Lewis <brl...@yahoo.com> writes:

> Matthias Blume <fi...@my.address.elsewhere> writes:
>
>> Joe Marshall <j...@ccs.neu.edu> writes:
>>
>> > Matthias Blume <fi...@my.address.elsewhere> writes:
>> >>
>> >> Yes, VALUES is nothing more than a (questionable, IMO) performance hack.
>> >
>> > So are multiple arguments, for that matter.
>>
>> Indeed.
>
> I'd be interested to see a definition of (factorial n) in a
> zero-or-one-argument language.

It's not really very interesting. The only parts of factorial that require
multiple arguments are the subtraction and multiplication operators, and
you'd just curry those. In Scheme syntax:

(define (factorial n)
(if (zero? n)
1

((*c n) (factorial ((-c n) 1)))))

Here, *c and -c are the curried versions of * and - respectively; since the
language is designed to allow at most one argument; it would have to
provide these as primitives instead of * and -.

Richard

Brian Harvey

unread,
Mar 30, 2005, 4:15:22 PM3/30/05
to
>>> >> Yes, VALUES is nothing more than a (questionable, IMO) performance hack.
>>> > So are multiple arguments, for that matter.

Sorry, I'm coming in in the middle of this, but...

Surely "performance hack" is an unfair description of multiple
arguments, whose main benefit is to simplify the understanding of
programs for human beings, not for compilers.

I take the point that

multiple arguments : inputs :: VALUES : outputs

(even though they took those out of the SAT this year, we're all
old enough to remember them :-) and I understand that neither
feature is strictly necessary. But as I understand the history,
VALUES is more for the sake of performance, and multiple args
more for the sake of human understanding, although both can be
said to contribute to both, I suppose, for those who find VALUES
intuitively flavorful.

PS: I find it fascinating that Scheme is already old enough to
have curmudgeons ("It's all downhill since R3RS"), a group among
whom I number myself, alas.

Joe Marshall

unread,
Mar 30, 2005, 4:50:49 PM3/30/05
to
b...@abbenay.CS.Berkeley.EDU (Brian Harvey) writes:

>>>> >> Yes, VALUES is nothing more than a (questionable, IMO) performance hack.
>>>> > So are multiple arguments, for that matter.
>
> Sorry, I'm coming in in the middle of this, but...
>
> Surely "performance hack" is an unfair description of multiple
> arguments, whose main benefit is to simplify the understanding of
> programs for human beings, not for compilers.

I don't *agree* with Matthias, of course.

> I take the point that
>
> multiple arguments : inputs :: VALUES : outputs
>
> (even though they took those out of the SAT this year, we're all
> old enough to remember them :-) and I understand that neither
> feature is strictly necessary. But as I understand the history,
> VALUES is more for the sake of performance, and multiple args
> more for the sake of human understanding, although both can be
> said to contribute to both, I suppose, for those who find VALUES
> intuitively flavorful.

I always thought that VALUES were added simply because the asymmetry
was really annoying to some. The syntax for multiple values in Scheme
is awkward, and the lack of reasonable defaulting (as in Common Lisp,
if you don't expect multiple values, the excess are silently dropped,
and if you want more than you get the extras are defaulted to nil)
just make them a pain.

> PS: I find it fascinating that Scheme is already old enough to
> have curmudgeons ("It's all downhill since R3RS"), a group among
> whom I number myself, alas.

I find it fascinating that *I* am old enough to be one.

Matthias Blume

unread,
Mar 30, 2005, 5:04:43 PM3/30/05
to
Joe Marshall <j...@ccs.neu.edu> writes:

> I don't *agree* with Matthias, of course.

That's a theorem, too, I think. :-)

Matthias Blume

unread,
Mar 30, 2005, 5:03:17 PM3/30/05
to
b...@abbenay.CS.Berkeley.EDU (Brian Harvey) writes:

>>>> >> Yes, VALUES is nothing more than a (questionable, IMO) performance hack.
>>>> > So are multiple arguments, for that matter.
>
> Sorry, I'm coming in in the middle of this, but...
>
> Surely "performance hack" is an unfair description of multiple
> arguments, whose main benefit is to simplify the understanding of
> programs for human beings, not for compilers.

Yeah right!

Function composition in Scheme is really intuitive:

(define (compose f g)
(lambda args
(call-with-values
(lambda () (apply g args))
f)))

It's a real joy! Imagine the hassle of having to write something as
complicated as this instead:

(define (compose f g) (lambda (x) (f (g x))))

You must either be kidding or have a strange sense of what is "simple
to understand".

> I take the point that
>
> multiple arguments : inputs :: VALUES : outputs

one argument : the input ; one value : the output

Multiple arguments are really just one argument with multiple
components, multiple outputs are just one output with multiple
components.

Data structures that let you group multiple values into one value with
multiple components are already useful in their own right and deserve
to be supported anyway. So the whole issue of argument/result can be
decoupled from the issue of multiplicity. Functions don't need more
(or less) than one argument and one result.

There are compilation strategies (even for a language like Scheme)
that even make this efficient (i.e., strategies which are not less
efficient that the mechanisms we have right now and, in particular,
which avoid allocating the intermediate container) for the common case
that caller provides n values that go into the argument container and
where the callee only wants the components but not the container itself.

Matthias

Sunnan

unread,
Mar 30, 2005, 8:49:31 PM3/30/05
to
Abdulaziz Ghuloum wrote:
> Sunnan wrote:
>> I find that lots (not all) of the time when I use values, I end up
>> collecting the values in a list (for one reason or another) anyway.
>
> If I needed to cons things together, I would return/pass a list. If I
> don't need the list, they I pass/return multiple values.

Right, this is how my code ends up looking. My thought process go like:
"Drats, I ended up needing to cons the values again. Might as well pass
a list"
and then I change it. Often the code is not in a tight enough spot that
I feel I can justify the time/thought expense to come up with a
non-consing way of solving the problem. (The reason I end up using lists
is often because I want the recieving procedure to take any number of
values, not a fixed set of values.)

Not all of the time - sometimes I do use values in a non-wasteful manner
and I'm very happy to have that feature in the language.

Sunnan

unread,
Mar 30, 2005, 8:56:24 PM3/30/05
to
Joe Marshall wrote:
> I've always thought it'd be interesting to design a computer language
> where CPS is the *only* way to program.

Scheme is one of the few languages where you don't have to write CPS.

In most other languages (C, CL), you have to use CPS if you want to call
continuations. (Granted, that's a pretty big "if"...)

Sunnan

unread,
Mar 30, 2005, 9:11:05 PM3/30/05
to
Joe Marshall wrote:
> I always thought that VALUES were added simply because the asymmetry
> was really annoying to some. The syntax for multiple values in Scheme
> is awkward, and the lack of reasonable defaulting (as in Common Lisp,
> if you don't expect multiple values, the excess are silently dropped,
> and if you want more than you get the extras are defaulted to nil)
> just make them a pain.

Agree about the defaulting, but lacking syntax is only a matter of
define-syntax.

(Even way back when I was even newbier than I'm now, I made an
implementation of multiple-value-bind (before I discovered that receive
already existed.)

One thing I'd like, and I guess this is more about semantics than syntax
(I always try to look cool by pretending that I know the difference
between the two (but I think I do, by now)), is for something like the
following:
(list 1 2 (values 3 4) 5 6) to return (1 2 3 4 5 6)

Maybe that's just the crack talking, I don't know. Also, something like:
(+ (values 4 5 6)) to return 15.

(Does it show that I think unquote-splicing is one of the coolest things
ever, and that I think that quasiquotation would totally suck without it?)

Sunnan

unread,
Mar 30, 2005, 9:40:21 PM3/30/05
to
Matthias Blume wrote:
> Function composition in Scheme is really intuitive:
>
> (define (compose f g)
> (lambda args
> (call-with-values
> (lambda () (apply g args))
> f)))

Does compose really use apply? I thought it was like, a super-optimized
primitive. I use compose all the time, is that wasteful?

>>I take the point that
>>
>> multiple arguments : inputs :: VALUES : outputs
>
>
> one argument : the input ; one value : the output
>
> Multiple arguments are really just one argument with multiple
> components, multiple outputs are just one output with multiple
> components.

I'm not sure that that's true for all problem domains.

I used to do shell scripting in unix all the time, and I found it really
annoying that pipes only (as far as I knew) took one stream in and
emitted one stream out.

I've found it a huge bliss that map takes multiple lists, for example.

I might buy that the arguments to, say, + is just a single argument (an
addition) with multiple components (terms), even though I find it far
fetched, but how about something like:

(map (lambda (a b) (display (string-append (prefix) a b) port)) names
suffixes)

To my untrained eyes, that does'nt look like a single argument with
multiple components. It looks like multiple arguments.

> There are compilation strategies (even for a language like Scheme)
> that even make this efficient (i.e., strategies which are not less
> efficient that the mechanisms we have right now and, in particular,
> which avoid allocating the intermediate container) for the common case
> that caller provides n values that go into the argument container and
> where the callee only wants the components but not the container itself.

Well, since you say you can make existing code work with no performance
loss, these compilation strategies seems like something that the scheme
community might want to look seriously at; if it might mean a nice,
clean and fast implementation of compose, for example.

Even though it might go contrary to what my instincts tell me is
aesthetical for a general-purpose programming language, which is that
procedures don't have to work exactly like math functions.

Bruce Lewis

unread,
Mar 30, 2005, 10:03:49 PM3/30/05
to
Matthias Blume <fi...@my.address.elsewhere> writes:

> (define (factorial n)
> (if (zero? n) 1 ((* n) (fac ((- n) 1)))))

I count 3 arguments to the IF syntax there. How would you go about
currying IF?

> Of course, what I was really thinking of was a language with
> first-class tuples, in which case the factorial would just look like
> it always does, except formally a two-argument function call passes a
> single argument which is a pair.

Yoiks. I'm imagining all the parens involved with curried tuple
constructors.

Matthias Blume

unread,
Mar 30, 2005, 10:28:31 PM3/30/05
to
Sunnan <sun...@handgranat.org> writes:

> Matthias Blume wrote:
>> Function composition in Scheme is really intuitive:
>> (define (compose f g)
>> (lambda args
>> (call-with-values
>> (lambda () (apply g args))
>> f)))
>
> Does compose really use apply? I thought it was like, a
> super-optimized primitive. I use compose all the time, is that
> wasteful?

Individual implementations, of course, can provide a built-in COMPOSE
that is somehow known to the compiler and which gets optimized better.
But the problem is not just with compose. Multiple values only work
well if sender and receiver are "adjacent". The moment you need to do
anything else in between, you are basically screwed and have to
capture the values in some first-class data structure.

In the example above, the function constructed by COMPOSE has to
accept as many arguments as g does. AFAIR, there is no other way than
what I showed: you have to capture the arguments as a list and then
use APPLY.

> I'm not sure that that's true for all problem domains.

This has nothing to do with problem domains.

> I used to do shell scripting in unix all the time, and I found it
> really annoying that pipes only (as far as I knew) took one stream in
> and emitted one stream out.

I don't see what this has to do with anything.

> I've found it a huge bliss that map takes multiple lists, for example.

Sure. But it could just as easily take ONE tuple where each component
is a list. (Except the first component, which will be the
function. Even better, MAP should take the function argument as a
curried argument. Unfortunately, Scheme's syntax for curried
functions is awkward.)

> I might buy that the arguments to, say, + is just a single argument
> (an addition) with multiple components (terms), even though I find it
> far fetched,

Why is that far fetched?

> but how about something like:
>
> (map (lambda (a b) (display (string-append (prefix) a b) port)) names
> suffixes)

See above.

> To my untrained eyes, that does'nt look like a single argument with
> multiple components. It looks like multiple arguments.

What's the difference?

> Even though it might go contrary to what my instincts tell me is
> aesthetical for a general-purpose programming language, which is that
> procedures don't have to work exactly like math functions.

Funny. My instincts tell me that the more they work like mathematical
functions, the better.

Matthias Blume

unread,
Mar 30, 2005, 10:30:52 PM3/30/05
to
Bruce Lewis <brl...@yahoo.com> writes:

> Matthias Blume <fi...@my.address.elsewhere> writes:
>
>> (define (factorial n)
>> (if (zero? n) 1 ((* n) (fac ((- n) 1)))))
>
> I count 3 arguments to the IF syntax there. How would you go about
> currying IF?

Since when is IF a function?

>> Of course, what I was really thinking of was a language with
>> first-class tuples, in which case the factorial would just look like
>> it always does, except formally a two-argument function call passes a
>> single argument which is a pair.
>
> Yoiks. I'm imagining all the parens involved with curried tuple
> constructors.

The tuple constructor would be built into the syntax. In fact,
existing programs would work as-is. Try Google. I described this in
quite a bit detail way back when.

Matthias Buelow

unread,
Mar 30, 2005, 10:42:25 PM3/30/05
to
Sunnan <sun...@handgranat.org> wrote:

>Joe Marshall wrote:
>> I always thought that VALUES were added simply because the asymmetry
>> was really annoying to some. The syntax for multiple values in Scheme
>> is awkward, and the lack of reasonable defaulting (as in Common Lisp,
>> if you don't expect multiple values, the excess are silently dropped,
>> and if you want more than you get the extras are defaulted to nil)
>> just make them a pain.
>
>Agree about the defaulting, but lacking syntax is only a matter of
>define-syntax.

I do not agree -- clearly, when a function returns more values than
are expected by the caller, this is a programming error and should
at least be flagged by a warning (recoverable error?) at runtime,
in addition to the compiler trying to figure out, and complain
about, such cases at compile time.

mkb.

Abdulaziz Ghuloum

unread,
Mar 30, 2005, 11:36:44 PM3/30/05
to
Matthias Blume wrote:

> Individual implementations, of course, can provide a built-in COMPOSE
> that is somehow known to the compiler and which gets optimized better.
> But the problem is not just with compose. Multiple values only work
> well if sender and receiver are "adjacent". The moment you need to do
> anything else in between, you are basically screwed and have to
> capture the values in some first-class data structure.

And since you might be `basically screwed' and have to use some data
structure in some situations, you might as well enjoy it in every
situation. Why give the implementor any chance of differentiating
between different level of screwiness? Let's just make everything
uniformly screwed so that you cannot tell really how hard you're ...

So, the current plan is like this:
1. impose uniformly screwed requirements so that all implementations
would at least suck the same.
2. spend years doing research on optimization for said problem.
lemma: optimization of these problems is undecidable in general,
so profit is maximized in many dimentions.
3. find another non-uniform thing and call it a performance hack.
4. goto 1.
5. profit.

Aziz,,,

Sunnan

unread,
Mar 30, 2005, 11:43:36 PM3/30/05
to
Matthias Blume wrote:
>>I'm not sure that that's true for all problem domains.
>
> This has nothing to do with problem domains.

I figure that "doing math stuff" was the one problem domain where single
argument made the most sense, and "doing glue stuff" where your
arguments come from all over is where it makes the least sense.

>>I used to do shell scripting in unix all the time, and I found it
>>really annoying that pipes only (as far as I knew) took one stream in
>>and emitted one stream out.
>
>
> I don't see what this has to do with anything.

I tried to say that I've programmed in a language that (for all I knew
at the time) only had one input and one output, and that it was totally
awkward. (I had to use the "paste" and "cut" programs if I wanted
multiple arguments or multiple values, respectively - similar to
constructing tuples, but in the case of "paste" it requires allocating,
of course.)

>>I've found it a huge bliss that map takes multiple lists, for example.
>
>
> Sure. But it could just as easily take ONE tuple where each component
> is a list.

Yeah, but what would that tuple "be", and how would it be constructed?

>>I might buy that the arguments to, say, + is just a single argument
>>(an addition) with multiple components (terms), even though I find it
>>far fetched,
>
>
> Why is that far fetched?

(+ 1 2 3 4) to me looks like an operator and four terms, not an operator
and a tuple. At best, it could be a tuple which consisted of four terms,
but then what's the gain? You still have to worry about the terms.

>>but how about something like:
>>
>>(map (lambda (a b) (display (string-append (prefix) a b) port)) names
>>suffixes)
>
>
> See above.
>

Should I interpret that as an argument for display to take the port as a
curried argument?


>
>>To my untrained eyes, that does'nt look like a single argument with
>>multiple components. It looks like multiple arguments.
>
>
> What's the difference?

I'm especially thinking about the fact that the arguments come from a
variety of sources. One comes from calling a thunk (which might or
mightn't return the same value every time), two of them come from two
separate list, and one is a variable holding a port. This motley crew
doesn't, to me, seem like it would get along in the "same boat".

>>Even though it might go contrary to what my instincts tell me is
>>aesthetical for a general-purpose programming language, which is that
>>procedures don't have to work exactly like math functions.
>
>
> Funny. My instincts tell me that the more they work like mathematical
> functions, the better.

So I've gathered. I strongly disagree with this.

Sunnan

unread,
Mar 30, 2005, 11:58:12 PM3/30/05
to
Matthias Buelow wrote:
> I do not agree -- clearly, when a function returns more values than
> are expected by the caller, this is a programming error and should
> at least be flagged by a warning (recoverable error?) at runtime,
> in addition to the compiler trying to figure out, and complain
> about, such cases at compile time.

As I tried to say in Message-ID:
<JQy2e.133618$dP1.4...@newsc.telia.net>, I would like one version of
values that worked like it does in scheme today (and as you describe
above), and one that worked like it does in CL, because sometimes that
can be really convenient.

I've defined versions of car and cdr that return '() (and also versions
that returns #f, instead) on non-pair inputs for the few times when
that's useful, like the CL:er's classic example,
(cdr (assq key a-list)).

I've only used this version of cdr once (and yeah, it was with assq - I
wanted to return an empty list if the pair wasn't found in the alist).
It was really convenient, but it's also dangerous and would lead to
hard-to-find bugs if it were the default.

Scheme easily lets me define that, but it doesn't let me (please,
correct me if I'm wrong) define a values that works like in CL.

It would be useful, because if I write a procedure f that I need to call
multiple times in my program, and I only need the extra values a small
subset of the time, I could choose to use the CL-like-values.

If, on the other hand, I wrote a procedure g where all of the values it
returned were vital, I would use normal R5RS values, just to be safe.

Matthias Blume

unread,
Mar 31, 2005, 12:03:05 AM3/31/05
to
Abdulaziz Ghuloum <aghu...@c-s-remove-dashes.indiana.edu> writes:

> Matthias Blume wrote:
>
>> Individual implementations, of course, can provide a built-in COMPOSE
>> that is somehow known to the compiler and which gets optimized better.
>> But the problem is not just with compose. Multiple values only work
>> well if sender and receiver are "adjacent". The moment you need to do
>> anything else in between, you are basically screwed and have to
>> capture the values in some first-class data structure.
>
> And since you might be `basically screwed' and have to use some data
> structure in some situations, you might as well enjoy it in every
> situation. Why give the implementor any chance of differentiating
> between different level of screwiness? Let's just make everything
> uniformly screwed so that you cannot tell really how hard you're ...

You have obviously not even bothered to read up on how this actually works.

First of all, you could at least use a more efficient data structure
than a list. Second, it is quite easy to avoid allocating this data
structure when you don't need it (which is, in fact, every time you can
use VALUES in Scheme right now, so you lose absolutely nothing).

> So, the current plan is like this:
> 1. impose uniformly screwed requirements so that all implementations
> would at least suck the same.

What "requirements"?

> 2. spend years doing research on optimization for said problem.

Actually, back when I was involved in the previous heated debate on
this issue, I worked out the solution in a few hours (and without
working full-time on this problem). And I am not the only one (and
not even the first one) to have done so. Your suggestion that it
would take years of research is ridiculous.

> lemma: optimization of these problems is undecidable in general,
> so profit is maximized in many dimentions.
> 3. find another non-uniform thing and call it a performance hack.
> 4. goto 1.
> 5. profit.

I don't think I want to continue a discussion at this level.

Matthias Blume

unread,
Mar 31, 2005, 12:10:29 AM3/31/05
to
Sunnan <sun...@handgranat.org> writes:

> Matthias Blume wrote:
>>>I'm not sure that that's true for all problem domains.
>> This has nothing to do with problem domains.
>
> I figure that "doing math stuff" was the one problem domain where
> single argument made the most sense, and "doing glue stuff" where your
> arguments come from all over is where it makes the least sense.
>
>>>I used to do shell scripting in unix all the time, and I found it
>>>really annoying that pipes only (as far as I knew) took one stream in
>>>and emitted one stream out.
>> I don't see what this has to do with anything.
>
> I tried to say that I've programmed in a language that (for all I knew
> at the time) only had one input and one output, and that it was
> totally awkward.

That's because that argument had no useful internal structure.

> Yeah, but what would that tuple "be",

Well, it would be... a tuple. What else do you want to hear?

> and how would it be constructed?

It would be allocated on the heap, but lazily, so that every time you
can currently use VALUES you end up not allocating the tuple after
all.

>>>I might buy that the arguments to, say, + is just a single argument
>>>(an addition) with multiple components (terms), even though I find it
>>>far fetched,
>> Why is that far fetched?
>
> (+ 1 2 3 4) to me looks like an operator and four terms, not an
> operator and a tuple.

Right, I forgot a about that. (There is no need for + taking anything
other than 2 arguments. But if it absolutely must, it could take a
k-tuple.)

> Should I interpret that as an argument for display to take the port as
> a curried argument?

Actually, that's not a bad suggestion. This way you can apply it
partially to the port (which probably changes rarely).

>>>To my untrained eyes, that does'nt look like a single argument with
>>>multiple components. It looks like multiple arguments.
>> What's the difference?
>
> I'm especially thinking about the fact that the arguments come from a
> variety of sources. One comes from calling a thunk (which might or
> mightn't return the same value every time), two of them come from two
> separate list, and one is a variable holding a port. This motley crew
> doesn't, to me, seem like it would get along in the "same boat".

Why? They would "get into the same boat" just before calling the
function.

>>>Even though it might go contrary to what my instincts tell me is
>>>aesthetical for a general-purpose programming language, which is that
>>>procedures don't have to work exactly like math functions.
>> Funny. My instincts tell me that the more they work like
>> mathematical
>> functions, the better.
>
> So I've gathered. I strongly disagree with this.

Care to explain why?

Daniel C. Wang

unread,
Mar 31, 2005, 1:40:21 AM3/31/05
to
Joe Marshall wrote:
{stuff deleted}

> I've always thought it'd be interesting to design a computer language
> where CPS is the *only* way to program.

Here's one

http://portal.acm.org/citation.cfm?id=781135

Though a great deal of effort is made hiding this fact from the programmer.

I remember programming in CPS when programing in BASIC, and I'm sure there
are some old time FORTRAN programmers who think these new fangled stacks are
overrated. (Seriously, CPS is just a fancy way of expressing gotos!)


Matthias Buelow

unread,
Mar 31, 2005, 2:14:47 AM3/31/05
to
Sunnan <sun...@handgranat.org> wrote:

>I've defined versions of car and cdr that return '() (and also versions
>that returns #f, instead) on non-pair inputs for the few times when
>that's useful, like the CL:er's classic example,
>(cdr (assq key a-list)).

Cdr/car not working on () is a nuisance sometimes, yes, but it also
leads to more disciplined code, imho. You simply cannot get caught
in an infinite loop where you're traversing a list via (... (cdr
l) ...). In CL you might only notice a programming error when you
find that the program hangs somewhere. In Scheme, it signals an
error, when the end of a list isn't properly checked. Annoying
sometimes it might be but imho beneficial overall. The same might
be said for assq.

>It would be useful, because if I write a procedure f that I need to call
>multiple times in my program, and I only need the extra values a small
>subset of the time, I could choose to use the CL-like-values.

Why not just bind them to dummy arguments (in a call-with-values,
or receive, etc.)? Then for the reader of your program it will be
clear what is going on, and that the function returns multiple
values. It might be a little more typing involved (not much) but
the program is easier to understand then by someone who didn't write
it (or by yourself, a year later). In my opinion, the right decisions
have been made with these two examples, when the semantics where
defined. Besides, you can easily make a wrapper function or macro
that just throws away the superfluous values. Hardly any more
typing involved then and the code will still be clear.

mkb.

R. Mattes

unread,
Mar 31, 2005, 2:17:43 AM3/31/05
to
On Wed, 30 Mar 2005 16:08:01 -0500, Richard C. Cobbe wrote:

> Thomas Hafner <uucp....@spamgourmet.com> writes:
>
>> [quoted text muted]


>
> Right. Your function foo is returning multiple values to a context that
> only expects a single value. This is not related to the fact that + can
> take arbitrarily many arguments; neithe is it related to the fact that some
> of the values returned by foo are not numbers.
>
> I don't remember whether R5RS specifies how implementations should behave
> in this case, but I do know you're not supposed to do it.
>
> R. Mattes was incorrect, at least as far as Scheme is concerned.

Yes, indeed! Too much Common Lisp lately (where this _does_ work). Sorry
for the confusion.

RalfD

> Richard

Jim Blandy

unread,
Mar 31, 2005, 3:44:34 AM3/31/05
to

Sunnan <sun...@handgranat.org> writes:
> Scott G. Miller wrote:
> > Thats not correct. In Scheme it is an error to return multiple
> > values into a context expecting a single value.
>
> This is one of the few things I like better in CL. For a while I
> tried to create a function, "safe-values", that acted like values
> does in CL - e.g. return only one value if the context only expected
> one value - but I never came up with a way to do it in pure scheme.

Thinking of return arity as being parallel to procedure arity, that
would be like calling a procedure in a way that was sensitive to the
procedure's arity.

Pure Scheme doesn't provide a way to do that, but MzScheme does have a
'procedure-arity' function:

$ mzscheme
Welcome to MzScheme version 208, Copyright (c) 2004 PLT Scheme, Inc.
> (procedure-arity (lambda (a b c) (list a b c)))
3
>

I tried applying procedure-arity to a continuation, but I didn't get
what I expected:

> (call-with-values (lambda ()
(call/cc (lambda (k)
(values 'mommy (procedure-arity k)))))
(lambda (mommy arity) arity))
#<struct:arity-at-least>
> (arity-at-least-value <the above>)
0
>

The '#<struct:arity-at-least>' bit is the value procedure-arity
returns to indicate that the procedure expects at least N arguments,
where arity-at-least-value gives you N.

I had been expecting '2', not an arity-at-least structure, since
that's the only number of values the producer there can provide
without provoking an error, but it seems like that information is
getting lost somewhere down the line.

> (procedure-arity (call/cc (lambda (k) k)))
#<struct:arity-at-least>
> (arity-at-least-value (procedure-arity (call/cc (lambda (k) k))))
0
>

Here I was expecting '1', but I got the same thing. Do all MzScheme
continuations accept any number of arguments, with the error
checking being done later? Hmm.

Jim Blandy

unread,
Mar 31, 2005, 4:02:18 AM3/31/05
to

So after all that, I forgot the punchline:

(define (safe-values . v)
(call/cc (lambda (k)
(let ((arity (procedure-arity k)))
(cond

;; I guess we could add more elements onto the end
;; of V here, if it wasn't long enough to satisfy
;; the arity. Like CL does. But who really cares?
((arity-at-least? arity) (apply k v))

;; If we have too many values, just take as many
;; as our continuation expects.
((< arity (length v)) (apply k (take v arity)))

(else (apply k v)))))))

While multiple values do make continuations more symmetrical with
procedures, they do so without giving me much of the satisfaction I'd
expect from that restored symmetry. Hmm.

Marcin 'Qrczak' Kowalczyk

unread,
Mar 31, 2005, 4:43:02 AM3/31/05
to
Sunnan <sun...@handgranat.org> writes:

> Scheme easily lets me define that, but it doesn't let me (please,
> correct me if I'm wrong) define a values that works like in CL.

In Scheme it's possible to implement 'values' in a way which doesn't
affect the calling convention (by allocating an object which holds
the values, as some Scheme implementations do).

In Lisp it's not possible. In order for function calls to be as
efficient as in a language without 'values', the calling convention
must be more elaborate. E.g. some paper describes the trick of putting
a second continuation at a fixed offset from each return address.

--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/

Jan Van lent

unread,
Mar 31, 2005, 5:18:00 AM3/31/05
to
Joe Marshall wrote:
> I've always thought it'd be interesting to design a computer language
> where CPS is the *only* way to program.

You can have a look at the programming language Io.

Raphael L. Levien, "Io: a new programming notation"
in SIGPLAN Notices 24(12) December 1989
http://portal.acm.org/citation.cfm?id=70934&jmp=indexterms&dl=GUIDE&dl=ACM

Implementation and link to online book:
http://www.guldheden.com/~sandin/amalthea.html

jan

Sunnan

unread,
Mar 31, 2005, 6:47:53 AM3/31/05
to
Matthias Blume wrote:
>>Yeah, but what would that tuple "be",
>
>
> Well, it would be... a tuple. What else do you want to hear?

I'm trying to make a useful mental model for what the tuple would represent.

>>and how would it be constructed?
>
>
> It would be allocated on the heap, but lazily, so that every time you
> can currently use VALUES you end up not allocating the tuple after
> all.

How would it look syntactically?

> Right, I forgot a about that. (There is no need for + taking anything
> other than 2 arguments. But if it absolutely must, it could take a
> k-tuple.)

Two arguments are still more than one. So + wouldn't take terms? It
would take... what? A "2-tuple of terms"? How is that neat? And how
would it look syntactically?

>>I'm especially thinking about the fact that the arguments come from a
>>variety of sources. One comes from calling a thunk (which might or
>>mightn't return the same value every time), two of them come from two
>>separate list, and one is a variable holding a port. This motley crew
>>doesn't, to me, seem like it would get along in the "same boat".
>
>
> Why? They would "get into the same boat" just before calling the
> function.

How would this look?

>>>Funny. My instincts tell me that the more they work like
>>>mathematical
>>>functions, the better.
>>
>>So I've gathered. I strongly disagree with this.
>
>
> Care to explain why?

Now, you're probably going to answer that most of the following is based
in math, or can be traced to the mathematical tradition, but here goes:

I like how similar to neurons it works (though, afaik, neurons don't
have "values" either). I think it's beautiful how you can connect a
bunch of transistors and make that into gates, and connect those gates
into adding and other basic instructions, and make an ALU and/or a CPU
out of that, and have that execute scheme code where you can define
abstractions, and have those abstractions help create other
abstractions, and upwards it goes. I don't think that idea should
necessarily be tied to math.

I like how code, data, expressions, statements, operators and procedures
are the same thing (I also strongly prefer lisp-1 to lisp-2).

I like having a general-purpose programming language that's very
suitable for graphics, text, math, audio and other things. I like having
the bang! stuff available (like set!).

What does "work like mathematical function" mean? If everyone had been
totally stuck in the "math tradition box", we'd never see the lambda
calculus, we'd never see polish notation, we'd never see sexps.

I don't like infix notation; I think it looks like a crummy,
one-dimensional, hard-to-parse, ascii-art representation of a
two-dimensional notation.

I'm not very familiar with Miranda, SML and O'Caml. I look at Haskell
from time to time and I prefer Scheme. Scheme is so beautiful.

Sunnan

unread,
Mar 31, 2005, 7:16:04 AM3/31/05
to
Matthias Buelow wrote:
> Cdr/car not working on () is a nuisance sometimes, yes, but it also
> leads to more disciplined code, imho.

My point exactly; as I was trying to say, I've used the "special"
versions only once upon a blue moon - when it was a nuisance, not an
unintended error.

> Why not just bind them to dummy arguments (in a call-with-values,
> or receive, etc.)? Then for the reader of your program it will be
> clear what is going on, and that the function returns multiple
> values. It might be a little more typing involved (not much) but
> the program is easier to understand then by someone who didn't write
> it (or by yourself, a year later).

I'd be more likely to go like "Huh? Why is this program binding to all
these dummy arguments?", in the case of a function that returns some
"extra" data that I might only need part of the time. (CL has plenty of
these as utilities.)

> In my opinion, the right decisions
> have been made with these two examples, when the semantics where
> defined.

The difference is that you can easily define a version of cdr that works
like CL, and use that the .001 % of the time where it's useful. You
can't easily define a version of values that works like CL.

I asked on this list a while ago on how to find out how many arguments a
procedure or continuation takes. I don't believe anyone answered.

> Besides, you can easily make a wrapper function or macro
> that just throws away the superfluous values. Hardly any more
> typing involved then and the code will still be clear.

I did try that solution as well, but it ended up creating a list, since
I wanted my wrapper to work on any number of values.

Sunnan

unread,
Mar 31, 2005, 7:39:00 AM3/31/05
to
Marcin 'Qrczak' Kowalczyk wrote:
> In Scheme it's possible to implement 'values' in a way which doesn't
> affect the calling convention (by allocating an object which holds
> the values, as some Scheme implementations do).

Thanks, that does make sense.

But I was looking for something like the procedure-arity that Jim Blandy
recently referred to.

Would that be implementable with most calling conventions?

Jens Axel Søgaard

unread,
Mar 31, 2005, 8:06:31 AM3/31/05
to
Sunnan wrote:

> But I was looking for something like the procedure-arity that Jim Blandy
> recently referred to.
>
> Would that be implementable with most calling conventions?

If you are interested in a concrete efficient implementation,
I'll recommend the following paper:

J. Michael Ashley and R. Kent Dybvig.
"An Efficient Implementation of Multiple Return Values in Scheme"
<http://repository.readscheme.org/ftp/papers/jmashley/lfp94.pdf>

--
Jens Axel Søgaard

Matthias Blume

unread,
Mar 31, 2005, 9:11:07 AM3/31/05
to
Sunnan <sun...@handgranat.org> writes:

> Matthias Blume wrote:
>>>Yeah, but what would that tuple "be",
>> Well, it would be... a tuple. What else do you want to hear?
>
> I'm trying to make a useful mental model for what the tuple would represent.

Think "cartesian product".

>>>and how would it be constructed?
>> It would be allocated on the heap, but lazily, so that every time
>> you
>> can currently use VALUES you end up not allocating the tuple after
>> all.
>
> How would it look syntactically?

That's a separate question. If (as per my suggestion) you fold tuple
construction into the function call syntax, currently correct programs
don't change at all syntactically. (Some equivalences in the language
are lost, though, i.e., you can distinguish between the behavior of
certain program fragments where you currently can't.)

>> Right, I forgot a about that. (There is no need for + taking anything
>> other than 2 arguments. But if it absolutely must, it could take a
>> k-tuple.)
>
> Two arguments are still more than one. So + wouldn't take terms? It
> would take... what? A "2-tuple of terms"? How is that neat?

"Neat" is not the point. As far as + is concerned, it's no more or
less "neat" that having + take two arguments.

> And how would it look syntactically?

The same it does now (see above).

>>>I'm especially thinking about the fact that the arguments come from a
>>>variety of sources. One comes from calling a thunk (which might or
>>>mightn't return the same value every time), two of them come from two
>>>separate list, and one is a variable holding a port. This motley crew
>>>doesn't, to me, seem like it would get along in the "same boat".
>> Why? They would "get into the same boat" just before calling the
>> function.
>
> How would this look?

See above.

>>>>Funny. My instincts tell me that the more they work like
>>>>mathematical
>>>>functions, the better.
>>>
>>>So I've gathered. I strongly disagree with this.
>> Care to explain why?
>
> Now, you're probably going to answer that most of the following is
> based in math, or can be traced to the mathematical tradition, but
> here goes:

You're right about that. So why do you even bother to list all this
stuff?

> I like how similar to neurons it works (though, afaik, neurons don't
> have "values" either). I think it's beautiful how you can connect a
> bunch of transistors and make that into gates, and connect those gates
> into adding and other basic instructions, and make an ALU and/or a CPU
> out of that, and have that execute scheme code where you can define
> abstractions, and have those abstractions help create other
> abstractions, and upwards it goes. I don't think that idea should
> necessarily be tied to math.

Au contraire! All of this *should* be tied to math (and, in fact, is
-- at a very deep level).

> I like having a general-purpose programming language that's very
> suitable for graphics, text, math, audio and other things. I like
> having the bang! stuff available (like set!).

Sure. What does that have to do with the discussion about single
vs. multiple function arguments?

> What does "work like mathematical function" mean? If everyone had been
> totally stuck in the "math tradition box", we'd never see the lambda
> calculus, we'd never see polish notation, we'd never see sexps.

What?!? The lambda calculus was invented Alonzo Church, a
mathematician. Lisp was developed by John McCarthy, a Princeton math
Ph.D.! Polish notation is due to Jan Lukasiewicz, a Polish
mathematician!

> I don't like infix notation; I think it looks like a crummy,
> one-dimensional, hard-to-parse, ascii-art representation of a
> two-dimensional notation.

Again, what does that have to do with anything?

> I'm not very familiar with Miranda, SML and O'Caml.

Perhaps you should get familiar then. Even if you come back to
Scheme, you'd have had the educational experience.

> I look at Haskell
> from time to time and I prefer Scheme. Scheme is so beautiful.

*shrug*

Sunnan

unread,
Mar 31, 2005, 9:55:46 AM3/31/05
to
Matthias Blume wrote:

> Sunnan <sun...@handgranat.org> writes:
>>I'm trying to make a useful mental model for what the tuple would represent.
>
>
> Think "cartesian product".

All right.

>>How would it look syntactically?
>
>
> That's a separate question.

Yeah, I know.

>>Two arguments are still more than one. So + wouldn't take terms? It
>>would take... what? A "2-tuple of terms"? How is that neat?
>
>
> "Neat" is not the point.

I thought that neatness was the point you were trying to make. What is
the point, then?

>>>>>Funny. My instincts tell me that the more they work like
>>>>>mathematical
>>>>>functions, the better.
>>>>
>>>>So I've gathered. I strongly disagree with this.
>>>
>>>Care to explain why?
>>
>>Now, you're probably going to answer that most of the following is
>>based in math, or can be traced to the mathematical tradition, but
>>here goes:
>
>
> You're right about that. So why do you even bother to list all this
> stuff?

Originally, I listed some of it but decided to delete it (for the above
reason). Then you asked "care to explain why" and I'm kinda shooting in
the dark when I struggle to explain this. So maybe some of the stuff I
listed was irrelevant.

>>I like how similar to neurons it works (though, afaik, neurons don't
>>have "values" either). I think it's beautiful how you can connect a
>>bunch of transistors and make that into gates, and connect those gates
>>into adding and other basic instructions, and make an ALU and/or a CPU
>>out of that, and have that execute scheme code where you can define
>>abstractions, and have those abstractions help create other
>>abstractions, and upwards it goes. I don't think that idea should
>>necessarily be tied to math.
>
>
> Au contraire! All of this *should* be tied to math (and, in fact, is
> -- at a very deep level).

I guess it depends on what your definition of "tied to math" is.

>>I like having a general-purpose programming language that's very
>>suitable for graphics, text, math, audio and other things. I like
>>having the bang! stuff available (like set!).
>
>
> Sure. What does that have to do with the discussion about single
> vs. multiple function arguments?

A general-purpose programming language isn't necessarily the same as a
mathematical notation, though it might be.

>>What does "work like mathematical function" mean? If everyone had been
>>totally stuck in the "math tradition box", we'd never see the lambda
>>calculus, we'd never see polish notation, we'd never see sexps.
>
>
> What?!? The lambda calculus was invented Alonzo Church, a
> mathematician. Lisp was developed by John McCarthy, a Princeton math
> Ph.D.! Polish notation is due to Jan Lukasiewicz, a Polish
> mathematician!

I know that they were mathematicians.

But when I try to write prefix in math class, I get thrown out.

I'm all for kind of math that Church, McCarty and Lukasiewicz did -
daring to break tradition, daring to stand on the shoulders of giants -
I'm all for Gödel and Hofstadter - there are plenty of mathematicians I
admire.

>>I don't like infix notation; I think it looks like a crummy,
>>one-dimensional, hard-to-parse, ascii-art representation of a
>>two-dimensional notation.
>
>
> Again, what does that have to do with anything?

Because when someone says (and I know you haven't said this, and I don't
think you're in that camp): "I want it to look just like a math
textbook" my reflexes trigger.

I like to work with languages and layers of abstraction, tools that work
on tools that work on tools.

It's as much about lingistics as it's about math. It's as much about
grammar as it's about math. Syntax, semantics - are these things really
"math"?

You might say that predicate logic is math, that higher order logic is
math - but is lojban math? Is english math? Is biology math? When does
it cross over from being not math?

Wikipedia currently has mathematics defined as:
"The investigation of axiomatically defined abstract structures using
symbolic logic and mathematical notation."

The investigation of axiomatically defined abstract structures? Yay, I
like it!

Mathematical notation? Not so much.

"Mathematical notation" is what makes me look at math as just another
language. Church and Lukasiewicz drastically changed or built upon that
notation, and I think Lisp/Scheme alters the notation so much that it's
no longer recognizable as mathematical notation (although it's still
operating on axiomatically defined abstract structures, sometimes with
physical side effects (e.g. writing to the video ram, indirectly causing
screen pixels to be displayed in different apparent colors)).

I remember how angry you would appear to become when order of evaluation
was discussed because you didn't want a statement/expression to be
ambiguous. To me, that passion against ambiguity looks more like a
mathematician's passion than a linguist's.

>>I'm not very familiar with Miranda, SML and O'Caml.
>
>
> Perhaps you should get familiar then. Even if you come back to
> Scheme, you'd have had the educational experience.

I've looked at them, and will continue to look at them from time to
time, picking up tidbits here and there.

Sunnan
An off-topic post script:
Can anyone tell me whether or not this news client breaks my lines
correctly?

Bruce Lewis

unread,
Mar 31, 2005, 10:00:57 AM3/31/05
to
Matthias Blume <fi...@my.address.elsewhere> writes:

> The tuple constructor would be built into the syntax. In fact,
> existing programs would work as-is. Try Google. I described this in
> quite a bit detail way back when.

If syntax with multiple subforms is allowed, this doesn't sound like
something that requires much detail. Requiring both single-subform
syntax and single-argument functions would be at least somewhat
interesting.

Matthias Blume

unread,
Mar 31, 2005, 10:33:35 AM3/31/05
to
Sunnan <sun...@handgranat.org> writes:

> Matthias Blume wrote:
>> Sunnan <sun...@handgranat.org> writes:
>>>I'm trying to make a useful mental model for what the tuple would represent.
>> Think "cartesian product".
>
> All right.
>
>>>How would it look syntactically?
>> That's a separate question.
>
> Yeah, I know.
>
>>>Two arguments are still more than one. So + wouldn't take terms? It
>>>would take... what? A "2-tuple of terms"? How is that neat?
>> "Neat" is not the point.
>
> I thought that neatness was the point you were trying to make. What is
> the point, then?

Neatness is the point, in some sense, but it may not manifest itself
so much in simple cases like +. However, consider this: Let F be a
function returning two numeric values, and you need the sum of those.
Right now you have to do this:

(call-with-values
(lambda () (f ... args for f ... ))
(lambda (x y) (+ x y)))

While under the proposal you just write

(+ (f ... args for f ... ))

More generally, if F produces n values and G takes n arguments, you
can simply write (g (f ...)). Furthermore, if you like to do something
"in between", e.g., write a log message to the console, you simply do

(let ((x (f ...))) (display ...) (g x))

and this will work regardless of G's arity and F's corresponding
number of return values.

> So maybe some of the stuff I listed was irrelevant.

Make that "all of it" and we're getting somewhere.

>>>I like having a general-purpose programming language that's very
>>>suitable for graphics, text, math, audio and other things. I like
>>>having the bang! stuff available (like set!).
>> Sure. What does that have to do with the discussion about single
>> vs. multiple function arguments?
>
> A general-purpose programming language isn't necessarily the same as a
> mathematical notation, though it might be.

Every programming language *is* a mathematical notation. In fact, it
is a notation that is even more precise than most everyday math
notation that non-CS (and non-logician) mathematicians tend to use.

> I know that they were mathematicians.
>
> But when I try to write prefix in math class, I get thrown out.

Yeah, and rightfully so. In math class you're supposed to understand
the mathematical concepts and not quibble about notation.

> I'm all for kind of math that Church, McCarty and Lukasiewicz did -
> daring to break tradition, daring to stand on the shoulders of giants

... while all those other non-maverick mathematicians are just
"follow the leader types". Yeah, right!

> Because when someone says (and I know you haven't said this, and I
> don't think you're in that camp): "I want it to look just like a math
> textbook" my reflexes trigger.

You might want to look for professional help then. You are definitely
hung up on something irrelevant.

> Syntax, semantics - are these things really "math"?

Absolutely.

> You might say that predicate logic is math, that higher order logic is
> math - but is lojban math? Is english math? Is biology math? When does
> it cross over from being not math?

I don't know what lojban is. What your English professor is doing
certainly does not qualify as math. What some linguists do, however,
definitely does. Biology nowadays starts to look more and more like
math.

> I remember how angry you would appear to become when order of
> evaluation was discussed because you didn't want a
> statement/expression to be ambiguous. To me, that passion against
> ambiguity looks more like a mathematician's passion than a linguist's.

Indeed. Linguists are forced to deal with ambiguities because these
ambiguities exist in their objects of study -- objects that they have
no control over. As computer scientists, however, we are able to
craft the languages we use to match our preferences, and we can strive
to banish unwanted complications from them. PL theory is not
linguistics, and trying to make programming languages "work like
natural languages" is a grave mistake.

Matthias

Sunnan

unread,
Mar 31, 2005, 11:03:35 AM3/31/05