\begin{slide}{Ameisen}


Wegfindung (Nahrungssuche) gesteuert durch Pheromone.

Zustandsänderungen (Ameise, Spielfeld) synchronisiert
durch Transaktionen.

ist beliebter Testfall für nebenläufige Programme:

  \begin{itemize}\itemsep 0pt
  \item Rich Hickey, Clojure: \url{http://clojure.googlegroups.com/web/ants.clj}
  \item Peter Vlugter, Scala: \url{https://github.com/jboner/akka/tree/master/akka-samples/akka-sample-ants/}
  \item Jeff Foster, Haskell: \url{http://www.fatvat.co.uk/2010/08/ants-and-haskell.html}
  \end{itemize}


\end{slide}


\begin{slide}{Ameisen (Modell)}

\begin{verbatim}
type Pos = (Int, Int)
data Ant = Ant { position :: TVar Pos 
               , direction :: TVar Int
               }
data Cell = Cell { occupied :: TVar Bool
                 , pheromone :: TVar Double 
                 }
type Board = Array Pos Cell
data World = World { board :: Board
           , population :: [ Ant ] 
           }
\end{verbatim}
  \begin{itemize}
  \item Invariante?
  \item Zustandsübergänge?
  \end{itemize}


\end{slide}


\begin{slide}{Ameisen (Aufgabe)}

1. Ameise darf nur auf leeres Nachbarfeld laufen.

\begin{itemize}
\item Transaktionen für: Feld verlassen, Feld betreten
\end{itemize}


\bigskip

2. Ameise soll ein zufälliges solches Nachbarfeld betreten.

\begin{itemize}
\item Welcher Fehler ist in folgendem Ansatz?
\end{itemize}


\begin{verbatim}
walk :: World -> Ant -> IO ()
walk w a = do
    d <- random ( 0, 7 )
    atomically $ do
        a läuft_in_Richtung d
\end{verbatim}

\end{slide}

\begin{slide}{Ameisen (Haskell) (Vorbereitung)}

\begin{verbatim}
import Data.Array
import Control.Concurrent.STM
import Control.Concurrent
import Control.Monad ( forM, forever, void )
import System.Random
import System.IO

type Pos = (Int,Int)
type Dir = Int

data Ant = Ant { position :: TVar Pos 
               , direction :: TVar Dir
               , moves :: TVar Int  
               }

data Cell = Cell { occupied :: TVar Bool
                 }
type Board = Array Pos Cell

data World = World
           { size :: Pos 
           , board :: Board
           , population :: [ Ant ]
           , generator :: TVar StdGen 
           }

-------------------------------------------------------------------

main :: IO ()
main = do
    w <- make_world (20,20) 10
    forM ( population w ) $ \ ant -> 
        forkIO $ forever $ walk w ant
    forever $ do
        pos <- snapshot w
        threadDelay $ 10^6 -- microseconds

info :: Ant -> STM String
info ant = do
    pos <- readTVar $ position ant
    dir <- readTVar $ direction ant
    mov <- readTVar $ moves ant
    return $ unwords [ "pos", show pos, "dir", show dir, "moves", show mov ]

snapshot :: World -> IO ()
snapshot w = do
  infos <- atomically $ forM ( population w ) $ info
  putStrLn $ unlines infos
  
---------------------------------------------------------------------------

-- | verschiebe in gegebene Richtung, 
-- mit wrap-around an den Rändern (d.h. Torus)
shift :: (Int,Int) -> Pos -> Dir -> Pos
shift (width,height) (x,y) d =
    let (dx,dy) = vector d
    in  ( mod (x+dx) width, mod (y+dy) height )

vector :: Dir -> Pos
vector d = case mod d 8 of
    0 -> ( 1,0) ; 1 -> ( 1, 1) ; 2 -> (0, 1) ; 3 -> (-1, 1)
    4 -> (-1,0) ; 5 -> (-1,-1) ; 6 -> (0,-1) ; 7 -> ( 1,-1)

-------------------------------------------------------------------------------

randomRT :: Random a => TVar StdGen -> (a,a) -> STM a
randomRT ref bnd = do
    g <- readTVar ref
    let (x, g') = randomR bnd g
    writeTVar ref g'    
    return x

random_selection :: TVar StdGen -> Int -> [a] -> STM [a]
random_selection ref 0 xs = return []
random_selection ref k xs = do
    ( pre, y : post ) <- random_split ref xs
    ys <- random_selection ref (k-1) ( pre ++ post )
    return $ y : ys

random_split :: TVar StdGen -> [a] -> STM ( [a], [a] )
random_split ref xs = do
    k <- randomRT ref ( 0, length xs - 1 )
    return $ splitAt k xs

------------------------------------------------------------------

make_world :: (Int,Int) -> Int -> IO World
make_world (width,height) num_ants = do
    b <- make_board (width, height)        
    gen <- newStdGen
    ref <- atomically $ newTVar gen    
    ants <- make_ants ref b num_ants
    return $ World 
        { size = (width, height), board = b, population = ants 
        , generator = ref
        }

make_board :: (Int,Int) -> IO Board
make_board (width,height) = do    
    let bnd = ((0,0),(width-1,height-1))
    cells <- forM ( range bnd ) $ \ xy -> do
          occ <- atomically $ newTVar False
          return (xy, Cell { occupied = occ } )
    return $ array bnd cells
    
make_ants :: TVar StdGen -> Board -> Int -> IO [ Ant ]    
make_ants ref b num_ants = atomically $ do
    sel <- random_selection ref num_ants $ indices b
    forM sel $ \ pos -> do
        p <- newTVar pos
        enter $ b ! pos
        dir <- randomRT ref ( 0, 7 )
        d <- newTVar dir
        m <- newTVar 0
        return $ Ant { position = p, direction = d, moves = m }

\end{verbatim}

\end{slide}
\begin{slide}{Ameisen (Haskell) (Aufgaben)}

Ergänzen Sie die Funktionen (Transaktionen):
\begin{verbatim}
count :: Ant -> STM ()
count ant = do
    m <- readTVar ( moves ant )
    writeTVar ( moves ant ) $! (m + 1 )

-- | Zelle betreten, falls sie frei ist
enter :: Cell -> STM ()
enter c = do
    ... <- readTVar ...
    check ...
    writeTVar ...
-- | Zelle verlassen
leave :: Cell -> STM ()

-- | ein Schritt in aktuelle Richtung
forward :: World -> Ant -> STM ()
forward w ant = do
    ...
    let pos' = shift ( size w ) pos dir
    ...
-- | Richtung verändern
rotate :: Int -> Ant -> STM ()
rotate turn ant = do
    ...
    ...    ( dir + turn )
\end{verbatim}

\end{slide}

\begin{slide}{Ameisen (Haskell) (Diskussion)}
verschiedene Varianten für das Laufen einer Ameise:
\begin{itemize}
\item Drehung vor dem Laufen würfeln (separate Transaktionen)
\begin{verbatim}
walk :: World -> Ant -> IO ()
walk w ant = do
    turn <- atomically 
         $ randomRT ( generator w ) (-1, 1)
    atomically $ do
        rotate turn ant
        forward w ant
        count ant  
\end{verbatim}
\item Drehung innerhalb der Lauf-Transaktion würfeln
\item welches ist eine passende Ersatz-Transaktion,
falls Commit für Laufen fehlschlägt?
\begin{verbatim}
   forever $ orElse (walk w ant) ...
\end{verbatim}
\end{itemize}
      


\end{slide}
