Execute SNUSP/Haskell: Difference between revisions
Content added Content deleted
m (<code>) |
m (<lang>) |
||
Line 15: | Line 15: | ||
The Haskell code starts with lots of imports: |
The Haskell code starts with lots of imports: |
||
< |
<lang haskell> |
||
import System.Environment |
import System.Environment |
||
import System.IO |
import System.IO |
||
Line 28: | Line 28: | ||
import qualified Data.HashTable as H |
import qualified Data.HashTable as H |
||
</ |
</lang> |
||
Use a list as an index into an array: |
Use a list as an index into an array: |
||
< |
<lang haskell> |
||
type Index = [Int] |
type Index = [Int] |
||
Line 44: | Line 44: | ||
inRange (l:ls, u:us) (i:is) = inRange (l,u) i && inRange (ls,us) is |
inRange (l:ls, u:us) (i:is) = inRange (l,u) i && inRange (ls,us) is |
||
rangeSize (ls,us) = product $ map rangeSize $ zip ls us |
rangeSize (ls,us) = product $ map rangeSize $ zip ls us |
||
</ |
</lang> |
||
or into an hashtable (the hash function could probably be improved): |
or into an hashtable (the hash function could probably be improved): |
||
< |
<lang haskell> |
||
cmpList :: Index -> Index -> Bool |
cmpList :: Index -> Index -> Bool |
||
cmpList [] [] = True |
cmpList [] [] = True |
||
Line 60: | Line 60: | ||
combine x 0 = x |
combine x 0 = x |
||
combine x y = z * (z+1) `div` 2 + x where z = x + y |
combine x y = z * (z+1) `div` 2 + x where z = x + y |
||
</ |
</lang> |
||
Here it's important that index lists with trailing zeroes are treated just like this list without the zeroes, so we can handle any number of dimensions. We want the same flexibility when adding index lists: |
Here it's important that index lists with trailing zeroes are treated just like this list without the zeroes, so we can handle any number of dimensions. We want the same flexibility when adding index lists: |
||
< |
<lang haskell> |
||
(<+>) :: Index -> Index -> Index |
(<+>) :: Index -> Index -> Index |
||
[] <+> ys = ys |
[] <+> ys = ys |
||
xs <+> [] = xs |
xs <+> [] = xs |
||
(x:xs) <+> (y:ys) = (x+y) : (xs <+> ys) |
(x:xs) <+> (y:ys) = (x+y) : (xs <+> ys) |
||
</ |
</lang> |
||
Some helper functions: |
Some helper functions: |
||
< |
<lang haskell> |
||
data Thread a = T {mp::a, ip::a, dir::a, stack::[(a,a)]} deriving Show |
data Thread a = T {mp::a, ip::a, dir::a, stack::[(a,a)]} deriving Show |
||
Line 96: | Line 96: | ||
toChar = chr . fromInteger |
toChar = chr . fromInteger |
||
fromChar = toInteger . ord |
fromChar = toInteger . ord |
||
</ |
</lang> |
||
Now, the commands. Given a thread, return a list of threads valid after one simulation step. In that way, ''exec'' can handle forks and thread termination on errors. |
Now, the commands. Given a thread, return a list of threads valid after one simulation step. In that way, ''exec'' can handle forks and thread termination on errors. |
||
< |
<lang haskell> |
||
-- Core SNUSP |
-- Core SNUSP |
||
Line 130: | Line 130: | ||
exec _ d t = return [t] |
exec _ d t = return [t] |
||
</ |
</lang> |
||
The scheduler manages a list ''ts'' of active threads, and a list ''ks'' of threads waiting for input. If there are no more threads in either list, stop. If input is available, one blocked thread is executed. If no input is available and all threads are blocked, we block the interpreter, too (so the OS can do something else). Otherwise, try to execute one of the unblocked threads, first checking if it's still inside the code array. |
The scheduler manages a list ''ts'' of active threads, and a list ''ks'' of threads waiting for input. If there are no more threads in either list, stop. If input is available, one blocked thread is executed. If no input is available and all threads are blocked, we block the interpreter, too (so the OS can do something else). Otherwise, try to execute one of the unblocked threads, first checking if it's still inside the code array. |
||
< |
<lang haskell> |
||
start c = maybe (fst $ bounds $ c) fst $ find (\(_,x) -> x == '$') $ assocs c |
start c = maybe (fst $ bounds $ c) fst $ find (\(_,x) -> x == '$') $ assocs c |
||
Line 150: | Line 150: | ||
| otherwise = exec' x d t |
| otherwise = exec' x d t |
||
where x = c ! (ip t) |
where x = c ! (ip t) |
||
</ |
</lang> |
||
Finally, routines to run code from a string or a file, and the main program. |
Finally, routines to run code from a string or a file, and the main program. |
||
< |
<lang haskell> |
||
runString y s = do |
runString y s = do |
||
d <- H.new cmpList hashList |
d <- H.new cmpList hashList |
||
Line 174: | Line 174: | ||
[s] <- getArgs |
[s] <- getArgs |
||
runFile s |
runFile s |
||
</ |
</lang> |
||
== Extension == |
== Extension == |
||
Line 180: | Line 180: | ||
To demonstrate the ease of introducing even more dimensions, let's implement commands ( and ) to move the data pointer along the z-axis, and a command ^ to rotate the IP direction around the (1,1,1) axis (i.e., left becomes up, up becomes "farther" on the z-axis, "farther" becomes left, etc.). |
To demonstrate the ease of introducing even more dimensions, let's implement commands ( and ) to move the data pointer along the z-axis, and a command ^ to rotate the IP direction around the (1,1,1) axis (i.e., left becomes up, up becomes "farther" on the z-axis, "farther" becomes left, etc.). |
||
< |
<lang haskell> |
||
exec '(' d t = moveMp d t [0,0,-1] |
exec '(' d t = moveMp d t [0,0,-1] |
||
exec ')' d t = moveMp d t [0,0, 1] |
exec ')' d t = moveMp d t [0,0, 1] |
||
exec '^' d t = return [t {dir=(d3:d1:d2:ds)}] where d1:d2:d3:ds = dir t <+> [0,0,0] |
exec '^' d t = return [t {dir=(d3:d1:d2:ds)}] where d1:d2:d3:ds = dir t <+> [0,0,0] |
||
</ |
</lang> |