[plt-scheme] Why multiple values?

>> Anyway, this isn't (just) an efficiency issue.  It's a matter of what
>> the programmer can express.  Multiple values says "this program
>> outputs these two things".  Lists say "this program outputs a list".
>
> I think were settled on the effiency issue, but I'm not seeing the 
> non-effencity issue in this one.  Are you saying that when i have a set 
> of numbers, that i'm actually saying "i have a set of numbers, not a 
> list of numbers with special set properties added to them"?


Hi Corey,

Let's backtrack for a moment.


In a HTDP-influenced viewpoint, when we have a function return a list of 
things, that list must be homogenous. For example:

     ;; sort: (listofX) -> (listof X)

Now we already know that Scheme is a bit looser about this: we have the 
freedom to return heterogeneous elements of a list in vanilla Scheme. 
But let's tie our own hands a bit, just for this experiment, and pretend 
we're dealing with a restricted subset of Scheme where lists are not 
heterogeneous.

If we're trying to return back a collection of values with different 
types, one might traditionally stuff those things into a list.  But if we 
live with a homogenous-list restriction, what might such a world look 
like?


Let's look at this concretely with that stack example again.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(module stack mzscheme
   (require (lib "list.ss"))

   (provide empty-stack
            stack-empty?
            stack-push
            stack-pop
            (struct stack ()) ;; make stacks opaque
            (struct popoff (elt rest)))

   ;; A (stackof X) is constructed with:
   ;;
   ;; (make-stack elts)
   ;;
   ;; where elts is of type (listof X).
   (define-struct stack (elts))

   (define empty-stack (make-stack '()))

   ;; stack-empty?: (stackof X) -> (stackof X)
   (define (stack-empty? a-stack)
     (empty? (stack-elts a-stack)))

   ;; stack-push: (stackof X) X -> (stackof X)
   (define (stack-push a-stack elt)
     (make-stack (cons elt (stack-elts a-stack))))

   ;; A (popoff X) is constructed with:
   ;;
   ;; (make-popoff elt rest)
   ;;
   ;; where elt is of type X and rest is of type (stackof X)
   (define-struct popoff (elt rest))

   ;; stack-pop: (stackof X) -> (popoff X)
   (define (stack-pop a-stack)
     (make-popoff (first (stack-elts a-stack))
                  (make-stack (rest (stack-elts a-stack))))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;



The thing to see here is that STACK-POP is using a "popoff" data structure 
to package up those multiple things into a single value.  And it's not too 
bad to use this, even with all those data structures, if we make proper 
use of the plt-match.ss library:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(module test-stack mzscheme
   (require "stack.ss"
            (lib "plt-match.ss"))

   (match-let*
       ([a-stack empty-stack]
        [a-stack (stack-push a-stack "world")]
        [a-stack (stack-push a-stack "hello")]
        [a-stack (stack-push a-stack "merry")]
        [(struct popoff (w a-stack)) (stack-pop a-stack)]
        [a-stack (stack-push a-stack "festivus")]
        [(struct popoff (x a-stack)) (stack-pop a-stack)]
        [(struct popoff (y a-stack)) (stack-pop a-stack)]
        [(struct popoff (z a-stack)) (stack-pop a-stack)])
     (printf "w=~a, x=~a, y=~a, z=~a, and stack-empty=~a~n"
             w x y z (stack-empty? a-stack)) a-stack))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


Still, this seems like extra work to create that popoff data structure. 
If we still want lists to be homogenous, but don't want to define that 
extra popoff data structure, we can still write similar code, using 
VALUES:

   ;; stack-pop: (stackof X) -> (values X (listof X))
   (define (stack-pop a-stack)
     (values (first (stack-elts a-stack))
             (make-stack (rest (stack-elts a-stack)))))


With this change, our test code now looks like this:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(module test-stack mzscheme
   (require "stack.ss")

   (let*-values
       ([(a-stack) empty-stack]
        [(a-stack) (stack-push a-stack "world")]
        [(a-stack) (stack-push a-stack "hello")]
        [(a-stack) (stack-push a-stack "merry")]
        [(w a-stack) (stack-pop a-stack)]
        [(a-stack) (stack-push a-stack "festivus")]
        [(x a-stack) (stack-pop a-stack)]
        [(y a-stack) (stack-pop a-stack)]
        [(z a-stack) (stack-pop a-stack)])
     (printf "w=~a, x=~a, y=~a, z=~a, and stack-empty=~a~n"
             w x y z (stack-empty? a-stack)) a-stack))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


This expresses basically the same thing as the previous test code.  So, 
even by abiding with the "lists are homogenous" restriction we put 
ourselves in, we can do pretty well.


Best of wishes!