<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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 -&gt; Ant -&gt; IO ()
walk w a = do
    d &lt;- 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 &lt;- make_world (20,20) 10
    forM ( population w ) $ \ ant -&gt; 
        forkIO $ forever $ walk w ant
    forever $ do
        pos &lt;- snapshot w
        threadDelay $ 10^6 -- microseconds

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

snapshot :: World -&gt; IO ()
snapshot w = do
  infos &lt;- 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) -&gt; Pos -&gt; Dir -&gt; Pos
shift (width,height) (x,y) d =
    let (dx,dy) = vector d
    in  ( mod (x+dx) width, mod (y+dy) height )

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

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

randomRT :: Random a =&gt; TVar StdGen -&gt; (a,a) -&gt; STM a
randomRT ref bnd = do
    g &lt;- readTVar ref
    let (x, g') = randomR bnd g
    writeTVar ref g'    
    return x

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

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

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

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

make_board :: (Int,Int) -&gt; IO Board
make_board (width,height) = do    
    let bnd = ((0,0),(width-1,height-1))
    cells &lt;- forM ( range bnd ) $ \ xy -&gt; do
          occ &lt;- atomically $ newTVar False
          return (xy, Cell { occupied = occ } )
    return $ array bnd cells
    
make_ants :: TVar StdGen -&gt; Board -&gt; Int -&gt; IO [ Ant ]    
make_ants ref b num_ants = atomically $ do
    sel &lt;- random_selection ref num_ants $ indices b
    forM sel $ \ pos -&gt; do
        p &lt;- newTVar pos
        enter $ b ! pos
        dir &lt;- randomRT ref ( 0, 7 )
        d &lt;- newTVar dir
        m &lt;- 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 -&gt; STM ()
count ant = do
    m &lt;- readTVar ( moves ant )
    writeTVar ( moves ant ) $! (m + 1 )

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

-- | ein Schritt in aktuelle Richtung
forward :: World -&gt; Ant -&gt; STM ()
forward w ant = do
    ...
    let pos' = shift ( size w ) pos dir
    ...
-- | Richtung verÃ¤ndern
rotate :: Int -&gt; Ant -&gt; 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 -&gt; Ant -&gt; IO ()
walk w ant = do
    turn &lt;- 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}
</pre></body></html>