Multiple values as an effect
ol...@pobox.com
this newsgroup showed a large degree of angst over multiple values in
Scheme. Posters often mention one disturbing feature of multiple
values: their apparent second-class nature. Indeed, the result of the
function 'values' with the number of arguments other than one cannot
be bound to variables, cannot be stored in data structures, and cannot
be passed to functions other than call-with-values.
I believe there is a way to look at multiple values that might prove
less confusing and disturbing. Multiple values is a computational
_exception_. When the function 'values' is invoked with more or fewer
than one argument, the function does not return at all. Rather, it
throws an exception. We can define the following translation of R5RS
Scheme into a Scheme without multiple values but with SRFI-12
exceptions [2]
(define (values . args)
(if (= 1 (length args)) (car args)
(abort (make-property-condition '*MV* 'mvalues args))))
Most of the non-tail expressions (including all argument expressions)
are to be wrapped in a form 'single'
(define-syntax single
(syntax-rules ()
((single exp)
(handle-exceptions
exc
(if ((condition-predicate '*MV*) exc)
(abort (make-property-condition 'exn ; run-time error
'message
"multiple values for a single-value continuation"))
(abort exc)) ; re-throw
exp))))
Tail expressions are not wrapped up: they propagate the values and
effects from the tail call upwards. The function call-with-values has
the following implementation.
(define (call-with-values producer consumer)
(apply consumer
(handle-exceptions
exc
(if ((condition-predicate '*MV*) exc)
((condition-property-accessor '*MV* 'mvalues) exc)
(abort exc) ; re-throw
)
(list (producer)))))
It is the only case where the argument expression '(producer)' is not
wrapped into 'single'.
Here are the tests. The first one is an example of call-with-values
from R5RS. It displays number 5.
(display
(single
(call-with-values
(single (lambda () ((single values)
(single 4) (single 5))))
(single (lambda (a b) (single b))))))
(newline)
; another example of call-with-values from R5RS. It displays -1
(display (single (call-with-values (single *) (single -))))
(newline)
; propagation of the exception. The code prints 42
(define (my-apply-2 fn arg1 arg2)
; tail call: don't wrap (fn arg1 arg2) into 'single'
((single fn) (single arg1) (single arg2)))
(display
(single
(call-with-values
(single ; the exception is generated inside my-apply-2
(lambda () ((single my-apply-2)
(single values) (single 43) (single 1))))
(single -))))
(newline)
We observe that every expression that appears in a single-value
context is wrapped into a form 'single'. The latter form catches *MV*
exceptions and re-throws them as runtime errors. This operation seems
to be called 'chaining' in Java. Only the function call-with-values
truly handles the *MV* exception.
Not surprisingly, the denotational semantics of Scheme in Section 7.2
of R5RS takes a similar view: many continuations (in particular,
continuations from argument expressions, if-test, value to set!) are
marked as accepting only single values (by an auxiliary function
'single').
The view of multiple values as exceptions clarifies design choices for
common extensions. For example, we can normalize expressions,
converting
(single ((single exp1) (single exp2) (single exp3)))
to
(single (exp1 exp2 exp3))
reducing the number of checks for the exception. OTH, we can alter the
form 'single' to extract the first value from the *MV* exception (or
choose #f if there are no values) and disregard the rest. This
approach will bring Scheme closer to CL as far as multiple values are
concerned.
Let us turn to the second-class nature for multiple values. In our
interpretation, when 'values' is applied to more or fewer than one
argument, it doesn't yield a value. Rather, 'values' performs a
computational effect. As with any effect, we cannot easily store it in
data structures or pass it to functions. However, we can convert an
effect to its denotation -- a pure value. The latter is first-class,
can be stored in data structures and passed and returned from
functions. We can also turn the denotation of an effect into the
effect itself: perform the denoted effect. The first operation -- from
an effect to its denotation -- is called a (monadic) reification. Its
converse is a (monadic) reflection. Scheme has tools to build such
reification/reflection pairs: delay and force. Indeed, (delay exp) is
a first-class value that denotes any effect that may be latent in
'exp'. The procedure 'force' forces the promise and causes the
performance of the effect. Alas, R5RS does not specify the behavior of
(delay exp) where exp returns more or fewer than one
value. Fortunately, R5RS gives us another tool to build the
reflection/ reification pair for the multiple-value effect. Let us
first define a record (SRFI-9) mv-record to be a denotation of the
effect:
(define-record-type mv-record (make-mv-record val)
mv-record?
(val mv-record-val)
)
; Reify a potentially effectful expression exp into a pure value
(define-syntax mv-reify
(syntax-rules ()
((mv-reify exp)
(call-with-values (lambda () exp)
(lambda vals (if (= 1 (length vals)) (car vals)
(make-mv-record vals)))))))
; If the value of 'arg' denotes a mv effect, perform it:
; that is, raise the *MV* exception
(define (mv-reflect arg)
(if (mv-record? arg) (apply values (mv-record-val arg)) arg))
Expressions of the types other than mv-record represent pure
(multiple-value--effect---free) computations. For such types, mv-reify
is an identity. Values of the type mv-record are first-class values,
and as such can be stored in a data structures, bound to variables, and
passed to functions. When mv-reflect is applied to a value of the type
mv-record, it causes the *MV* exception to be raised, thus performing
the effect. It is easy to see that reify and reflect are indeed the
inverses in their corresponding domains: "for any expression E of type
'a' (possibly with effects) and any value V of type Ta" [3]
reify(reflect(V)) === V
reflect(reify(E)) === E
Here is an example:
(define (plus-minus x y) (values (+ x y) (- x y)))
(let ((x1 (mv-reify (plus-minus 21 3)))
(x2 (mv-reify 7)))
(display
(list (+ x2 x2)
(+ (mv-reflect x2) (mv-reflect x2))
(call-with-values (lambda () (mv-reflect x1)) +)))
(newline))
Both x1 and x2 bound to values. x2 is bound to a non-mv-record value.
For such values, applying mv-reflect has no effect (pun intended).
OTH, evaluating (mv-reflect x1) raises the *MV* exception, which
propagates upwards and is eventually caught by call-with-values
(which is defined at the beginning of this article).
We must note that this pattern of reification and reflection of
multiple values is quite common. For example, it occurs in the
following snippet from Scheme48 source code, file
scheme/rts/channel-port.scm
(define (call-with-output-file string proc)
(let* ((port (open-output-file string))
(results (call-with-values (lambda () (proc port))
list)))
(close-output-port port)
(apply values results)))
Call-with-values reifies the result of the executing of (proc
port). (apply value results) reflects that value. This reflection
pattern, (apply values results), explicitly occurs in the Scheme48
source code code 25 times.
An article [4] showed that other effects such as the division by zero
or taking a 'car' of an empty list can be reified and thus treated as
values. We should also note that a (non-signaled) NaN is also a
reified effect.
[1] P. J. Landin. The next 700 programming languages.
Comm.ACM, Volume 9 , Issue 3 (1966), pp. 157-166.
http://www.acm.org/pubs/articles/journals/cacm/1966-9-3/p157-landin/p157-landin.pdf
The paper was presented in August 1965! The paper is a must read.
A pertinent quote:
"Treat argument lists as a special case of lists. So a triadic
function can have its arguments supplied by a conditional whose arms
are 3-listings, or by application of a function that produces a
3-list. A similar situation arises when a 3-listing occurs as a
definee. (Even LISP trips up here, over lists of length one.)"
See also a question by Abrahams in the discussion Section of the paper.
[2] The implementation of SRFI-12 is readily available for Bigloo and
Gambit. http://pobox.com/~oleg/ftp/Scheme/util.html#srfi-12
[3] Andrzej Filinski. Representing monads. In Conference
Record of POPL '94: 21st ACM SIGPLAN-SIGACT
Symposium on Principles of Programming Languages,
Portland, Oregon, pages 446--457.
http://citeseer.nj.nec.com/filinski94representing.html
[4] Re: multilambda implementation: recreational macrology challenge!
http://google.com/groups?selm=7eb8ac3e.0206101216.1eb26713%40posting.google.com
David Rush
> Multiple values have a 40-year long history [1]. Recent discussions on
> this newsgroup showed a large degree of angst over multiple values in
> Scheme.
Angst? No. Dislike? Yes.
> Posters often mention one disturbing feature of multiple
> values: their apparent second-class nature.
That's barely a reason in my book. Just looking at it philosophically,
how could multiple values be anything *but* second class? If a value
not a (single) value then it must be second class because there simply
isn't enough semantic room in the term value to hold the notion of
'multiple'. Now if you want to take a different view; namely that
multiple-values is a clumsy hack that really means tuples+pattern match
it's a whole different story. You don't take that approach below, but
I have other issues with the sequel.
> I believe there is a way to look at multiple values that might prove
> less confusing and disturbing. Multiple values is a computational
> _exception_. When the function 'values' is invoked with more or fewer
> than one argument, the function does not return at all. Rather, it
> throws an exception.
Which once again goes to show that call/values is a
continuation-manipulating
operator. In point of fact I consider it dual (assuming I understand the
technical definition of 'dual') to call/cc. call/cc projects a continuation
from its call-site into its argument. call/values injects its argument as
the
continuation of the thunk's call-site.
Your discussion only supports my annoyances with call/values. Your
formulation
in the sequel very nicely shows how pervasive the consistent treatment of
multiple
values must be. I'm not too sure that this is much better than simply
using CPS
to *directly* inject the continuation. In Scheme continuation injection is
(as my 4-year old would say) easy-peasy lemon squeezy - it's just a
tail-call
away.
> Let us turn to the second-class nature for multiple values. In our
> interpretation, when 'values' is applied to more or fewer than one
> argument, it doesn't yield a value. Rather, 'values' performs a
> computational effect. As with any effect, we cannot easily store it in
> data structures or pass it to functions. However, we can convert an
> effect to its denotation -- a pure value. The latter is first-class,
> can be stored in data structures and passed and returned from
> functions. We can also turn the denotation of an effect into the
> effect itself: perform the denoted effect. The first operation -- from
> an effect to its denotation -- is called a (monadic) reification. Its
> converse is a (monadic) reflection.
This is cute, but it's worth noting that (IIRC) R5RS semantics leaves the
meaning of values in non-tail position undefined. You end up defining it
here with the side-effect that all multiple-valued functions become
escapers
and requires that, in addition to the 'single' annotation being liberally
sprinkled through the code (although perhaps the compiler can do that on
the programmer's behalf), that mv-reify be used in all single-value
receiving
contexts. Again, this could all be automated by a SSC, but the only way to
do it without overheads is to do whole-program analysis - which might as
well just do the continuation injection in the first place.
IMO, the *real* fix is to define non-tail values as 'is an error' so that
bats can come flying out of the disk drive when such a thing is done.
> [1] P. J. Landin. The next 700 programming languages.
> "Treat argument lists as a special case of lists. So a triadic
> function can have its arguments supplied by a conditional whose arms
> are 3-listings, or by application of a function that produces a
> 3-list. A similar situation arises when a 3-listing occurs as a
> definee. (Even LISP trips up here, over lists of length one.)"
YOW! This cuts *right* to the heart of the problem: the desire to
manipulate
_argument lists_ as first-class objects. I really think that the only sane
way to achieve that is to use the SML model where all functions have
only a single argument and use pattern-matching of tuple types to
deconstruct multiple arguments. Any other method is ultimately going to
trip itself up because the problem isn't about multiple-values - it's
about manipulating argument lists (the multiple-values case is the special
case where the argument list is applied to a continuation)
david rush
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
Anton van Straaten
> Multiple values have a 40-year long history [1].
Or a 60-year history...
> [1] P. J. Landin. The next 700 programming languages.
> Comm.ACM, Volume 9 , Issue 3 (1966), pp. 157-166.
>
http://www.acm.org/pubs/articles/journals/cacm/1966-9-3/p157-landin/p157-lan
din.pdf
> The paper was presented in August 1965! The paper is a must read.
> A pertinent quote:
> "Treat argument lists as a special case of lists. So a triadic
> function can have its arguments supplied by a conditional whose arms
> are 3-listings, or by application of a function that produces a
> 3-list. A similar situation arises when a 3-listing occurs as a
> definee. (Even LISP trips up here, over lists of length one.)"
> See also a question by Abrahams in the discussion Section of the paper.
How about Church, 1941:
"According to another scheme, which is the better one for certain purposes,
a function of two variables is regarded as a function (of one variable)
whose arguments are ordered pairs, a function of three variables as a
function whose arguments are ordered triads, and so on." [The Calculi of
Lambda Conversion, pg. 4]
Erann Gat
van Straaten" <an...@appsolutions.com> wrote:
> How about Church, 1941:
>
> "According to another scheme, which is the better one for certain purposes,
> a function of two variables is regarded as a function (of one variable)
> whose arguments are ordered pairs, a function of three variables as a
> function whose arguments are ordered triads, and so on." [The Calculi of
> Lambda Conversion, pg. 4]
Reading Church 1941 is a real eye-opener. Turns out he even invented Lisp
syntax:
"If f denotes a particular function, we shall use the notation ( f a ) for
the value of the function f for the argument a."
E.
Ray Dillinger
I think that if something wants to return multiple values,
that's an unusual condition. And the right thing to do isn't
having this weird halfway-there semantics of multiple-value
returns; the right thing to do is to have it box up
the values its returning in some kind of freshly-allocated
first-class containing object (probably a list, for symmetry
with the (lambda args ... ) argument list) and return that.
Yes, it could impose additional runtime overhead on multi-valued
returns in some cases. But I like it because it would get us
away from the multi-valued return as a continuation-manipulating
operator, and it would create a very clear correspondence
between multi-valued returns and multi-arument continuations;
the one returns a list and the other is applied to a list.
One rule for in, a mirror image of that rule for out, nothing
returns a value anywhere that can't be simply stored in a
variable, and the model is clean again. CPS works, and other
techniques work too, and we don't have a problem.
All functions are conceptually one-argument and one-return
in lambda calculus. Even if we optimize away boxing the
values on call and return, that's only a memory management
sweet spot that's identified a garbage-collectible structure
before it's allocated. It doesn't really change the fact
that arguments are, in theory, just an argument list.
Multiple returns should, in theory, just be a return list.
We can have some kind of multiple-value recieving form at
the call site, and a compiler that sees that should elide
boxing and unboxing the same way it does when calling a multi-
arg function. But if it's a single-value recieving form
at the call site, then it ought to get a list of results,
the same way a one-argument lambda with no parens gets a
list of arguments.
I'm convinced that multiple-valued function returns were a bad
idea. If this machinery is to exist, let it be stuffed under
the hood as an optimization the compiler makes when it sees
common usage patterns, and not dragged out to mess with the
simple semantic model of the language.
Bear
Aki Helin
> Multiple values have a 40-year long history [1]. Recent discussions on
> this newsgroup showed a large degree of angst over multiple values in
> Scheme. Posters often mention one disturbing feature of multiple
> values: their apparent second-class nature.
In many cases where the problems are caused by multiple values not being
first class, a lightweight solution is to (at least locally) equate multiple
values with a list.
(define call/cc
call-with-current-continuation)
(define (enlist x)
(if (list? x) x
(list x)))
(define vals list)
(define (call/vals producer consumer)
(apply consumer
(enlist (producer))))
Now for example in Scheme48
> (call/vals
(lambda () (vals 4 5))
(lambda (a b) b))
5
> (call/vals * -)
-1
> (call/cc
(lambda (out)
(call/vals
(lambda () (vals 42))
out)))
42
> (call/cc
(lambda (out)
(call/vals
(lambda () (vals 42 'foo))
out)))
; 2 values returned
42
'foo
--
aki helin
Marcin 'Qrczak' Kowalczyk
The following choices seem to be possible:
N-1. A sequence of arguments, one result (R4RS, current Python, Ruby,
most languages actually).
ERR. A sequence of arguments, a sequence of results, multiple results
passed as an argument are an error (R5RS).
SPL. A sequence of arguments, a sequence of results, multiple results
are spliced into argument lists (Perl).
FIR. A sequence of arguments, a sequence of results, the first result
(or nil for no results) is used from each argument (CL).
1-1. One argument, one result. Multiple arguments are packed in a tuple,
but a single argument is passed directly; same for results (SML,
ancient Python).
CUR. One argument, one result. For multiple arguments functions are
curried, multiple results are packed in a tuple (OCaml, Haskell).
Lua uses a combination of FIR & SPL (only the last argument is spliced).
I believe the best choice for the Scheme paradigm (dynamic typing,
beauty more important than efficiency) is N-1. Its only disadvantage
is that returning multiple results requires memory allocation. N-1 is
convenient if you have a nice syntax for unpacking the sequence used to
pack the results into seprate variables.
I don't agree that the asymmetry of arguments and results is unnatural.
A node in a syntax tree has some number of children and *one* parent.
A sequence of sequences of values (outer sequence of arguments, inner
sequences of results of each argument) must be somehow transformed into
a sequence of arguments, and in other cases a sequence must be transformed
into a single value - there is no obvious choice how to do it.
ERR makes function results second class and generic functions like compose
either require ugly code or don't work in rare cases when multiple results
are actually used.
I tried SPL in a little language of my own and abandoned it. It shares the
flaw of ERR and adds more: some errors are hard to find - when a function
with a wrong number of results is used, it shifts the rest of arguments
with funny effects, and there is usually no way to detect incorrect arity
at compile time - and making efficient code is significantly harder.
FIR has the same flaw as ERR and it's a bit hard to produce efficient code,
but easier than with SPL (the "multiple-result return point a fixed offset
before the single-result return point" method can be used). The ability to
return a "secondary result" which is usually ignored is interesting, but
IMHO it's not worth the complexity of the model.
1-1 was tried in Python and abandoned. See Misc/HISTORY in Python sources,
Release 0.9.4 (24 Dec 1991), which is less than a year after the first
Python distribution. It works for statically typed languages because they
detect arity mismatches statically as type mismatches and because they
usually can't have a statically unknown number of arguments anyway.
With dynamic types we want to detect arity mismatches at least at runtime,
which this model sometimes doesn't allow; and we want some functions with
a variable number of arguments, in particular they should be able to
distinguish one argument which happens to be a tuple from multiple
arguments. These problems are much less significant for results than for
arguments because multiple results are rare and variable number of results
is even rarer (they can be packed in a list when really needed).
CUR also works well with static typing only. Dynamic typing has the same
two problems as above: you can't detect arity mismatches even at runtime
and it prevents variable arity functions, which otherwise fit dynamic
typing so well.
--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Bradd W. Szonye
> Now if you want to take a different view; namely that multiple-values
> is a clumsy hack that really means tuples+pattern match it's a whole
> tuple matching] is ultimately going to trip itself up because the
> problem isn't about multiple-values - it's about manipulating argument
> lists (the multiple-values case is the special case where the argument
> list is applied to a continuation)
In the past, I've wanted language support for multiple-value returns for
two reasons: syntactic convenience and efficiency.
For example, I was recently working on a splay-tree implementation for
Scheme. It's easy enough to do if you don't mind a side-effects; just
hide the splaying inside the various access procedures. A purely
functional implementation is yucky, though, because every procedure must
have some way to return both the usual result and the splayed tree.
I can do this by always returning a result-tree pair, but it's difficult
to use in practice. For most dictionary-like ADTs, you can use a simple
FIND interface like this:
(let ((val (hash-table-find ht key)))
body ...)
But for a splay tree that returns pairs, it's ugly:
(let* ((result (splay-tree-find st key))
(val (car result))
(st (cdr result)))
body ...)
It's not horrible, but it gets tedious after a while. Also, if the
returned values are some arbitrary tuple -- not just a pair -- I'm
probably duplicating work that the translator can do more efficiently
than a user can.
Some Schemes provide a let-values form to avoid the ugly syntax and the
extra work. With these, splay-tree access is much closer to other ADTs:
(let-values (((val st) (splay-tree-find st key)))
body ...)
In this case, it's not about manipulating argument lists, but providing
a convenient syntax for handling tuple return values in general.
If I understand correctly, this is one of the major uses of monads, no?
--
Bradd W. Szonye
http://www.szonye.com/bradd
Marcin 'Qrczak' Kowalczyk
> In the past, I've wanted language support for multiple-value returns for
> two reasons: syntactic convenience and efficiency.
[...]
> If I understand correctly, this is one of the major uses of monads, no?
One of common useful monads, the state monad, indeed hides passing an
extra argument and returning a new value for it together with the real
result. This is just one of many monads.
(It's orthogonal to whether the results are physically packed in a tuple,
in a list, or returned as multiple values in a language which supports
that.)