Shuffling in Whitespace

Until now, programmers interested in using randomized algorithms in Whitespace have been required to supply some random stuff as input to their program. To solve this, I propose adding a new instruction to the Whitespace language that will shuffle the stack. This feature can then be used to implement various randomized algorithms, including a random number generator.

Command Reference and Sample Program

As a stack operation, this instruction is prefixed by the [Space] IMP. The command code is selected to allow for future expansion of Whitespace's stack operations and in homage to a musical group that my wife assures me is not disco.

Command	Parameters	Meaning
[Tab][Tab][Space]	-	Randomly permute the order of all values on the stack.

You can download a sample program which prints out the digits 0-9 in a random order.

Implementation

You may download my enhanced version of Whitespace here.

For your convenience, the changes to the reference implementation of Whitespace follow.

--- WSpace/Input.hs	2004-05-04 10:10:15.000000000 -0700
+++ WSpaceS/Input.hs	2011-03-10 11:26:53.000000000 -0800
@@ -13,7 +13,10 @@
 We have:
 
 * Stack instructions (Preceded by A)
-     Push (Integer)    A
+     Push n        A
+     Copy nth      BA
+     Shuffle       BBA
+     Slide n       BC
      Dup           CA
      Swap          CB
      Discard       CC
@@ -67,6 +70,7 @@
 parse (A:C:A:xs) = Dup:(parse xs)
 parse (A:B:A:xs) = let (num,rest) = parseNumber xs in
 		   (Ref num):(parse rest)
+parse (A:B:B:A:xs) = Shuffle:(parse xs)
 parse (A:B:C:xs) = let (num,rest) = parseNumber xs in
 		   (Slide num):(parse rest)
 parse (A:C:B:xs) = Swap:(parse xs)

--- WSpace/VM.hs	2004-05-04 10:10:41.000000000 -0700
+++ WSpaceS/VM.hs	2011-03-10 12:37:56.000000000 -0800
@@ -1,6 +1,8 @@
 module VM where
 
+import Array
 import IO
+import System.Random
 
 {- Stack machine for running whitespace programs -}
 
@@ -8,6 +10,7 @@
        Push Integer
      | Dup
      | Ref Int
+     | Shuffle
      | Slide Int
      | Swap
      | Discard
@@ -61,6 +64,9 @@
     = vm (VM prog (Stack (n:n:stack)) cs heap pc)
 doInstr (VM prog (Stack (stack)) cs heap pc) (Ref i)
     = vm (VM prog (Stack ((stack!!i):stack)) cs heap pc)
+doInstr (VM prog (Stack stack) cs heap pc) Shuffle
+    = do shuffled <- shuffle stack
+	 vm (VM prog (Stack shuffled) cs heap pc)
 doInstr (VM prog (Stack (n:stack)) cs heap pc) (Slide i)
     = vm (VM prog (Stack (n:(drop i stack))) cs heap pc)
 doInstr (VM prog (Stack (n:m:stack)) cs heap pc) Swap
@@ -143,3 +149,18 @@
 store x n [] = do hp <- store x (n-1) [] 
 		  return (0:hp)
 
+-- Shuffling the stack
+
+shuffle :: [Integer] -> IO [Integer]
+shuffle nums = do shuffled <- shuffle' arr 1
+		  return $ elems shuffled
+  where arr = array (1, length nums) $ zip [1..] nums
+
+shuffle' :: Array Int Integer -> Int -> IO (Array Int Integer)
+shuffle' arr start = do
+   newIx <- randomRIO (start, end)
+   let (v1, v2) = (arr ! start, arr ! newIx)
+   -- putStrLn $ "Swapping " ++ (show (start, newIx))
+   let swapped = arr // [(start, v2), (newIx, v1)]
+   if start < (end - 1) then shuffle' swapped (start+1) else return arr
+  where end = snd $ bounds arr

--- WSpace/main.hs	2003-03-31 07:33:44.000000000 -0800
+++ WSpaceS/main.hs	2011-03-10 12:07:15.000000000 -0800
@@ -37,7 +37,7 @@
 
 usage :: IO ()
 usage = do
-	putStrLn "wspace 0.2 (c) 2003 Edwin Brady"
+	putStrLn "wspace 0.4 (c) 2003 Edwin Brady"
 	putStrLn "-------------------------------"
 	putStrLn "Usage: wspace [file]"