From posting-system@google.com Tue Oct 21 21:11:29 2003 Date: Tue, 21 Oct 2003 13:11:27 -0700 From: oleg@pobox.com (oleg@pobox.com) Newsgroups: comp.lang.scheme Subject: Multiple values as an effect Message-ID: <7eb8ac3e.0310211211.3c684996@posting.google.com> Status: OR 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. 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