I guess multiple values were introduced as a concept for functions to
return completely unrelated objects as a result of the computation. This is
a rare occassion, and can be more elegantly modeled with first class tuples
in languages with only one return value such as Haskell and ML. Also a
special syntax had to be invented to receive those values (which
deliberately resembles tuples).

I understand multiple values as a way to optionally getting back more
information. The best example is the integer division also returning a
modulus. Some algorithms require both pieces of information, and both are
produced by the processor. So why call two functions (as in C: / and %)?

There would be a {*filter*} ambiguity in returning multiple results as lists (or
sequences). You can never know if the function returned multiple values or
in fact a proper sequence of objects.

This is a special case of the typing consideration. You can specify the
type for each return value (well, almost) but you cannot type a list that
has an integer as first element and a string as the second.

In conclusion I would prefer first class tuples in Dylan, but then again
the need for special syntax would arise.

        Gabor

PS: I assume your question did not refer to <<implementing>> multiple
values as lists, where the answer would indeed be clear.

PPS: Incidentally I could have used Dylans integer division recently for
transposing an (A x B) matrix to a (B x A) matrix in memory. I had to do it
in C because Dylan was not an option. I did not manage to do it in-place.
Does anyone know such an in-place algorithm?

Sure.  Let's invent one :-)

First: you can't do it at all without *some* sort of additional storage --
it's just a question of how *much* additional storage.

Assuming you're allowed space to store one element (could be reduced to
one byte or one bit if you *really* insisted :-) ...

define method main(appname, #rest arguments)

  let A = 3;
  let B = 7;
  let s = "abcdefgABCDEFG1234567";

  for (root from 0 below A * B)
    block (next-root)

      // see if this char has already been swapped
      let (row, col) = floor/(root, A);
      let item = col * B + row;
      while (item ~= root)
        if (item < root) // this root must have already been on a cycle
          next-root();
        end;
        let (row, col) = floor/(item, A);
        item := col * B + row;
      end;

      // permute a cycle
      format-out("saving %c at %d\n", s[root], root);
      let tmp = s[root];
      let (row, col) = floor/(root, A);
      let item = col * B + row;
      let prev = root;
      while (item ~= root)
        format-out("Copying %c from %d to %d\n", s[item], item, prev);
        s[prev] := s[item];
        prev := item;
        let (row, col) = floor/(item, A);
        item := col * B + row;
      end;
      s[prev] := tmp;
      format-out("Putting saved item %c at %d        %s\n", tmp, prev, s);

    end;
  end for;

  format-out("Transposed = '%s'\n", s);

  exit(exit-code: 0);
end method main;

./transpose
saving a at 0
Putting saved item a at 0        abcdefgABCDEFG1234567
saving b at 1
Copying A from 7 to 1
Copying C from 9 to 7
Copying d from 3 to 9
Putting saved item b at 3        aAcbefgCBdDEFG1234567
saving c at 2
Copying 1 from 14 to 2
Copying 5 from 18 to 14
Copying g from 6 to 18
Putting saved item c at 6        aA1befcCBdDEFG5234g67
saving e at 4
Copying B from 8 to 4
Copying 3 from 16 to 8
Copying F from 12 to 16
Putting saved item e at 12        aA1bBfcC3dDEeG52F4g67
saving f at 5
Copying 2 from 15 to 5
Putting saved item f at 15        aA1bB2cC3dDEeG5fF4g67
saving D at 10
Putting saved item D at 10        aA1bB2cC3dDEeG5fF4g67
saving E at 11
Copying 4 from 17 to 11
Copying 6 from 19 to 17
Copying G from 13 to 19
Putting saved item E at 13        aA1bB2cC3dD4eE5fF6gG7
saving 7 at 20
Putting saved item 7 at 20        aA1bB2cC3dD4eE5fF6gG7
Transposed = 'aA1bB2cC3dD4eE5fF6gG7'

If you don't mind using one bit of storage per array element, you can
avoid the first while loop by instead testing a bit vector to see if that
particular element has already been moved.

-- Bruce

Sure, that works, at the expense of having to read each item six times and
write it three times, instead of read once and write once.

Not that the code posted is super-efficient in the first place, with all
those divmod operations required... (1.5 per element).  You could drop
that to one divmod per element if you can spare one bit per element as a
flag.  If you can spare one integer per element then you can get rid of
the divmod altogether.

In any case, transposing by copying is going to be *far* more efficient in
the presence of cache, TLBs, VM etc, if you "block" the code.

-- Bruce