WIRING UP WIREWORLD Using Haskell

More details attached.

Assignment 1 student template/make_n_run_Wireworld
./make_Wireworld
./Wireworld

Assignment 1 student template/make_n_run_Wireworld_on_Windows.bat
./make_Wireworld_on_Windows
./Wireworld

Assignment 1 student template/make_Wireworld
ghc –make -O2 -W Sources/Wireworld.hs -iSources -odir `uname -m` -hidir `uname -m` -o Wireworld

Assignment 1 student template/make_Wireworld_compile_everything
ghc –make -O2 -W Sources/Wireworld.hs -fforce-recomp -iSources -odir `uname -m` -hidir `uname -m` -o Wireworld

Assignment 1 student template/make_Wireworld_compile_everything_on_Windows.bat
ghc –make -O2 -W Sources/Wireworld.hs -fforce-recomp -iSources -odir “Objects” -hidir “Interfaces” -o Wireworld

Assignment 1 student template/make_Wireworld_on_Windows.bat
ghc –make -O2 -W Sources/Wireworld.hs -iSources -odir “Objects” -hidir “Interfaces” -o Wireworld

Assignment 1 student template/Sources/Commandline/Options.hs
—
— Uwe R. Zimmer
— Australia 2012
—
module Commandline.Options (

Options (world_filename, no_of_tests, model, fps),

Data_Structure (List_2D, Ordered_Lists_2D),
default_options, — :: Options
args_to_options — :: [String] -> Options

) where

import System.Console.GetOpt (getOpt, ArgOrder (Permute), usageInfo, OptDescr (Option), ArgDescr (OptArg))
data Data_Structure = List_2D | Ordered_Lists_2D
deriving Eq
data Options = Options {
world_filename :: String,
no_of_tests :: Int,
model :: Data_Structure,
fps :: Int
}
default_options :: Options
default_options = Options {
world_filename = “Wireworlds/Playfield.bmp”,
no_of_tests = 25,
model = Ordered_Lists_2D,
fps = 25
}
data Flags = World_Filename String | No_Of_Tests Int | Model Data_Structure | FPS Int
header = “Usage: Wireworld [OPTION…]” :: String
available_options :: [OptDescr Flags]
available_options = [
Option [‘w’] [“world”] (OptArg from_maybe_filename “” ) “a bmp file which contains a wireworld”,
Option [‘t’] [“tests”] (OptArg from_maybe_no_of_tests “” ) “number of test transitions performed”,
Option [‘m’] [“model”] (OptArg from_maybe_model “List_2D | Ordered_Lists_2D”) “data structure for the wireworld state”,
Option [‘f’] [“fps” ] (OptArg from_maybe_fps “” ) “frames per second for the animation”
]
from_maybe_filename :: Maybe String -> Flags
from_maybe_filename maybe_filename = case maybe_filename of
Nothing -> World_Filename (world_filename default_options)
Just filename -> World_Filename filename
from_maybe_no_of_tests :: Maybe String -> Flags
from_maybe_no_of_tests maybe_no_of_tests = case maybe_no_of_tests of
Nothing -> No_Of_Tests (no_of_tests default_options)
Just no_of_tests_string -> No_Of_Tests (read no_of_tests_string)
from_maybe_model :: Maybe String -> Flags
from_maybe_model maybe_name = case maybe_name of
Nothing -> Model (model default_options)
Just “List_2D” -> Model List_2D
Just “Ordered_Lists_2D” -> Model Ordered_Lists_2D
_ -> error “Unknown model given in option ‘-m'”

from_maybe_fps :: Maybe String -> Flags
from_maybe_fps maybe_fps = case maybe_fps of
Nothing -> FPS (fps default_options)
Just f -> FPS (read f)

flags_to_options :: [Flags] -> Options
flags_to_options flags = flags_to_options’ flags default_options
where
flags_to_options’ :: [Flags] -> Options -> Options
flags_to_options’ flags current_options = case flags of
World_Filename name: cs -> flags_to_options’ cs (current_options {world_filename = name})
No_Of_Tests n : cs -> flags_to_options’ cs (current_options {no_of_tests = n})
Model name: cs -> flags_to_options’ cs (current_options {model = name})
FPS f : cs -> flags_to_options’ cs (current_options {fps = f})
[] -> current_options

args_to_options :: [String] -> Options
args_to_options args = case getOpt Permute available_options args of
(flags, [], []) -> flags_to_options flags
(_, nonOpts, [] ) -> error $ “unrecognized arguments: ” ++ unwords nonOpts
(_, _ , msgs) -> error $ concat msgs ++ usageInfo header available_options

Assignment 1 student template/Sources/Data/Cell.hs
—
— Uwe R. Zimmer
— Australia 2012
—
module Data.Cell (
Cell (Head, Tail, Conductor, Empty)
) where
data Cell = Head | Tail | Conductor | Empty
deriving Eq

instance Show Cell where
show cell = case cell of
Head -> “H”
Tail -> “T”
Conductor -> “C”
Empty -> ” ”

Assignment 1 student template/Sources/Data/Coordinates.hs
—
— Uwe R. Zimmer
— Australia 2012
—
module Data.Coordinates (
Distance,
X_Coord,
Y_Coord,
Coord,
Element_w_Coord,
) where
type Distance = Integer;
type X_Coord = Integer;
type Y_Coord = Integer;
type Coord = (X_Coord, Y_Coord);
type Element_w_Coord e = (e, Coord)

Assignment 1 student template/Sources/Data/List_2D.hs
—
— Uwe R. Zimmer
— Australia 2012
—
module Data.List_2D (
List_2D,
{- the central data structure of this module:
A single list containing elements with their associated coordinates.
No order on the coordinates is assumed or preseverd -}
singleton_world, — :: Element_w_Coord e -> List_2D e
insert_element, — :: Element_w_Coord e -> List_2D e -> List_2D e
combine_List_2D, — :: List_2D e -> List_2D e -> List_2D e
read_element, — :: Coord -> List_2D e -> Maybe e
element_occurrence, — :: Eq e => e -> List_2D e -> Int
first_coord, — :: List_2D e -> Maybe Coord
next_coord, — :: Coord -> List_2D e -> Maybe Coord
remove_elements_less_than_x, — :: X_Coord -> List_2D e -> List_2D e
remove_elements_less_than_y, — :: Y_Coord -> List_2D e -> List_2D e

local_lines, — :: Y_Coord -> List_2D e -> List_2D e
— +/- 1 y coordinate lines neighbourhood (including the y line itself, if it exists)
local_elements, — :: Coord -> List_2D e -> List_2D e
local_elements_list, — :: Coord -> List_2D e -> [e]
— +/- 1 (x, y) coordinates elements neighbourhood – including the element at (x, y) itself, if it exists
map_list_2D, — :: (Element_w_Coord e -> b) -> List_2D e -> List_2D b
map_list_2D_to_list, — :: (Element_w_Coord e -> b) -> List_2D e -> [b]
map_list_2D_w_context, — :: (Element_w_Coord e -> c -> b) -> c -> List_2D e -> List_2D b
map_List_2D_w_context_to_list, — :: (Element_w_Coord e -> c -> b) -> c -> List_2D e -> [b]
— apply a function with or without a context to all elements in a list_2D structure
— and return the results in the same structure or in a flat list

size, — :: List_2D e -> Int

list_2D_to_list, — :: List_2D e -> [e]
— roll out a list_2D structure to a flat list containing the elements only
) where
import Data.Coordinates (Distance, Coord, Element_w_Coord, X_Coord, Y_Coord)

type List_2D e = [Element_w_Coord e]

singleton_world :: Element_w_Coord e -> List_2D e
singleton_world element = [element]
insert_element :: Element_w_Coord e -> List_2D e -> List_2D e
insert_element element world = element: world
combine_List_2D :: List_2D e -> List_2D e -> List_2D e
combine_List_2D list world = list ++ world
read_element :: Coord -> List_2D e -> Maybe e
read_element (x, y) world = case world of
(element, (x_e, y_e)): cs
| x == x_e
&& y == y_e -> Just element
| otherwise -> read_element (x, y) cs
[] -> Nothing
element_occurrence :: Eq e => e -> List_2D e -> Int
element_occurrence element list = case list of
(local_element, _): cs
| local_element == element -> 1 + element_occurrence element cs
| otherwise -> element_occurrence element cs
[] -> 0
first_coord :: List_2D e -> Maybe Coord
first_coord world = scan_world_first world Nothing
where
scan_world_first :: List_2D e -> Maybe Coord -> Maybe Coord
scan_world_first world candidate = case world of
(_, (x_e, y_e)): cs -> case candidate of
Just (x_c, y_c)
| y_e < y_c || (y_e == y_c && x_e < x_c) -> scan_world_first cs (Just (x_e, y_e))
| otherwise -> scan_world_first cs candidate
Nothing -> scan_world_first cs (Just (x_e, y_e))
[] -> candidate
next_coord :: Coord -> List_2D e -> Maybe Coord
next_coord coord world = scan_world_next coord world Nothing
where
scan_world_next :: Coord -> List_2D e -> Maybe Coord -> Maybe Coord
scan_world_next (x, y) world candidate = case world of
(_, (x_e, y_e)): cs -> case candidate of
Just (x_c, y_c)
| (y_e > y || (y_e == y && x_e > x ))
&& (y_e < y_c || (y_e == y_c && x_e < x_c)) -> scan_world_next (x, y) cs (Just (x_e, y_e))
| otherwise -> scan_world_next (x, y) cs candidate
Nothing
| y_e > y || (y_e == y && x_e > x) -> scan_world_next (x, y) cs (Just (x_e, y_e))
| otherwise -> scan_world_next (x, y) cs candidate
[] -> candidate
remove_elements_less_than_x :: X_Coord -> List_2D e -> List_2D e
remove_elements_less_than_x x world = case world of
(element, (x_e, y_e)): cs
| x_e < x -> remove_elements_less_than_x x cs
| otherwise -> (element, (x_e, y_e)): remove_elements_less_than_x x cs
[] -> []
remove_elements_less_than_y :: Y_Coord -> List_2D e -> List_2D e
remove_elements_less_than_y y world = case world of
(element, (x_e, y_e)): cs
| y_e < y -> remove_elements_less_than_y y cs
| otherwise -> (element, (x_e, y_e)): remove_elements_less_than_y y cs
[] -> []
local_lines :: Y_Coord -> List_2D e -> List_2D e
local_lines y world = read_neighbouring_lines y 1 world

where
read_neighbouring_lines :: Y_Coord -> Distance -> List_2D e -> List_2D e
read_neighbouring_lines y dist list = case list of
(element, (x_e, y_e)): cs
| abs (y_e – y) <= dist -> (element, (x_e, y_e)): read_neighbouring_lines y dist cs
| otherwise -> read_neighbouring_lines y dist cs
[] -> []
local_elements :: Coord -> List_2D e -> List_2D e
local_elements (x, y) list = read_neighbours (x, y) 1 list
where
read_neighbours :: Coord -> Distance -> List_2D e -> List_2D e
read_neighbours (x, y) dist list = case list of
(element, (x_e, y_e)): cs
| abs (x_e – x) <= dist && abs (y_e - y) <= dist -> (element, (x_e, y_e)): read_neighbours (x, y) dist cs
| otherwise -> read_neighbours (x, y) dist cs
[] -> []

local_elements_list :: Coord -> List_2D e -> [e]
local_elements_list (x, y) list = read_neighbours_list (x, y) 1 list
where
read_neighbours_list :: Coord -> Distance -> List_2D e -> [e]
read_neighbours_list (x, y) dist list = case list of
(element, (x_e, y_e)): cs
| abs (x_e – x) <= dist && abs (y_e - y) <= dist -> element: read_neighbours_list (x, y) dist cs
| otherwise -> read_neighbours_list (x, y) dist cs
[] -> []
map_list_2D :: (Element_w_Coord e -> b) -> List_2D e -> List_2D b
map_list_2D f list = case list of
(element, (x_e, y_e)): cs -> (f (element, (x_e, y_e)), (x_e, y_e)): map_list_2D f cs
[] -> []

map_list_2D_to_list :: (Element_w_Coord e -> b) -> List_2D e -> [b]
map_list_2D_to_list f list = map f list
map_list_2D_w_context :: (Element_w_Coord e -> c -> b) -> c -> List_2D e -> List_2D b
map_list_2D_w_context f context list = case list of
(element, (x_e, y_e)): cs -> (f (element, (x_e, y_e)) context, (x_e, y_e)): map_list_2D_w_context f context cs
[] -> []

map_List_2D_w_context_to_list :: (Element_w_Coord e -> c -> b) -> c -> List_2D e -> [b]
map_List_2D_w_context_to_list f context list = case list of
c: cs -> f c context: map_List_2D_w_context_to_list f context cs
[] -> []

size :: List_2D e -> Int
size list = length list
list_2D_to_list :: List_2D e -> [e]
list_2D_to_list list = case list of
(element, _): cs -> element: list_2D_to_list cs
[] -> []

Assignment 1 student template/Sources/Data/Ordered_Lists_2D.hs
—
— Uwe R. Zimmer
— Australia 2012
—
module Data.Ordered_Lists_2D (
Ordered_Lists_2D,
{- the central data structure of this module:
A list of lists where y coordinate are attached to every list at top level (the “lines”)
and every element inside the line lists has an x coordinate attached to it.
All lists are sorted in ascending order, yet the coordinates do not need to be
consecutive (or “dense”) -}

Sparse_Line (Sparse_Line, y_pos, entries),
Placed_Element (Placed_Element, x_pos, entry),
Placed_Elements,

singleton_world, — :: Element_w_Coord e -> Ordered_Lists_2D e
insert_element, — :: Element_w_Coord e -> Ordered_Lists_2D e -> Ordered_Lists_2D e
insert_list, — :: List_2D e -> Ordered_Lists_2D e -> Ordered_Lists_2D e
combine_Ordered_Lists_2D, — :: Ordered_Lists_2D e -> Ordered_Lists_2D e -> Ordered_Lists_2D e
read_element, — :: Coord -> Ordered_Lists_2D e -> Maybe e
element_occurrence, — :: Eq e => e -> Ordered_Lists_2D e -> Int
first_coord, — :: Ordered_Lists_2D e -> Maybe Coord
next_coord, — :: Coord -> Ordered_Lists_2D e -> Maybe Coord
remove_elements_less_than_x, — :: X_Coord -> Ordered_Lists_2D e -> Ordered_Lists_2D e
remove_elements_less_than_y, — :: Y_Coord -> Ordered_Lists_2D e -> Ordered_Lists_2D e
local_lines, — :: Y_Coord -> Ordered_Lists_2D e -> Ordered_Lists_2D e
— +/- 1 y coordinate lines neighbourhood (including the y line itself, if it exists)
local_elements, — :: Coord -> Ordered_Lists_2D e -> Ordered_Lists_2D e
local_elements_list, — :: Coord -> Ordered_Lists_2D e -> [e]
— +/- 1 (x, y) coordinates elements neighbourhood – including the element at (x, y) itself, if it exists
map_Ordered_Lists_2D, — :: (Element_w_Coord e -> b) -> Ordered_Lists_2D e -> Ordered_Lists_2D b
map_Ordered_Lists_2D_to_list, — :: (Element_w_Coord e -> b) -> Ordered_Lists_2D e -> [b]
map_Ordered_Lists_2D_w_context, — :: (Element_w_Coord e -> c -> b) -> c -> Ordered_Lists_2D e -> Ordered_Lists_2D b
map_Ordered_Lists_2D_w_context_to_list, — :: (Element_w_Coord e -> c -> b) -> c -> Ordered_Lists_2D e -> [b]
— apply a function with or without a context to all elements in a sparse_list_2D structure
— and return the results in the same structure or in a flat list

size, — :: Ordered_Lists_2D e -> Int
sparse_list_2D_to_list, — :: Ordered_Lists_2D e -> [e]
sparse_list_2D_to_list_2D, — :: Ordered_Lists_2D e -> List_2D e
— roll out a sparse_list_2D structure to a flat list containing the elements only or the elements with their coordinates
) where
import Data.Coordinates (Distance, X_Coord, Y_Coord, Coord, Element_w_Coord)
import Data.List_2D (List_2D)

data Placed_Element e = Placed_Element {x_pos :: X_Coord, entry :: e}
type Placed_Elements e = [Placed_Element e]
data Sparse_Line e = Sparse_Line {y_pos :: Y_Coord, entries :: Placed_Elements e}

type Ordered_Lists_2D e = [Sparse_Line e]

instance (Show e) => Show (Sparse_Line e) where
show line = (show (y_pos line)) ++ “: ” ++ show (entries line) ++ “\r” ++ “\n”
instance (Show e) => Show (Placed_Element e) where
show element = (show (x_pos element)) ++ “: ” ++ show (entry element)

singleton_world :: Element_w_Coord e -> Ordered_Lists_2D e
singleton_world (cell, (x, y)) = [Sparse_Line {y_pos = y, entries = [Placed_Element {x_pos = x, entry = cell}]}]
insert_element :: Element_w_Coord e -> Ordered_Lists_2D e -> Ordered_Lists_2D e
insert_element (cell, (x, y)) world = case world of
l: ls
| y < y_pos l -> (Sparse_Line {y_pos = y, entries = insert_cell_to_entries cell x []}): world
| y == y_pos l -> (Sparse_Line {y_pos = y, entries = insert_cell_to_entries cell x (entries l)}): ls
| otherwise -> l: insert_element (cell, (x, y)) ls
[] -> singleton_world (cell, (x, y))
where
insert_cell_to_entries :: e -> X_Coord -> Placed_Elements e -> Placed_Elements e
insert_cell_to_entries cell x entries = case entries of
c: cs
| x < x_pos c -> Placed_Element {x_pos = x, entry = cell}: entries
| x == x_pos c -> Placed_Element {x_pos = x, entry = cell}: cs
| otherwise -> c: insert_cell_to_entries cell x cs
[] -> [Placed_Element {x_pos = x, entry = cell}]
insert_list :: List_2D e -> Ordered_Lists_2D e -> Ordered_Lists_2D e
insert_list list world = case list of
element_with_coord: cs -> insert_element element_with_coord (insert_list cs world)
[] -> world
combine_Ordered_Lists_2D :: Ordered_Lists_2D e -> Ordered_Lists_2D e -> Ordered_Lists_2D e
combine_Ordered_Lists_2D left right = case left of
[] -> right
l: ls -> case entries l of
c: cs -> combine_Ordered_Lists_2D ((Sparse_Line {y_pos = y_pos l, entries = cs}): ls) (insert_element ((entry c), (x_pos c, y_pos l)) right)
[] -> combine_Ordered_Lists_2D ls right

read_element :: Coord -> Ordered_Lists_2D e -> Maybe e
read_element (x, y) world = case world of
l: ls
| y < y_pos l -> Nothing
| y == y_pos l -> case entries l of
c: cs
| x < x_pos c -> Nothing
| x == x_pos c -> Just (entry c)
| otherwise -> read_element (x, y) [(Sparse_Line {y_pos = y_pos l, entries = cs})]
[] -> Nothing
| otherwise -> read_element (x, y) ls
[] -> Nothing
element_occurrence :: Eq e => e -> Ordered_Lists_2D e -> Int
element_occurrence element world = case world of
l: ls -> contains_element_line element (entries l) + element_occurrence element ls
where
contains_element_line :: Eq e => e -> Placed_Elements e -> Int
contains_element_line element cells = case cells of
c: cs
| (entry c) == element -> 1 + contains_element_line element cs
| otherwise -> contains_element_line element cs
[] -> 0
[] -> 0
first_coord :: Ordered_Lists_2D e -> Maybe Coord
first_coord world = case world of
[] -> Nothing
l: ls -> case (entries l) of
[] -> first_coord ls
c: _ -> Just (x_pos c, y_pos l)
next_coord :: Coord -> Ordered_Lists_2D e -> Maybe Coord
next_coord (x, y) world = case world of
[] -> Nothing
l: ls
| y < y_pos l -> Nothing
| y == y_pos l -> next_coord_in_entries x (entries l) l ls
| otherwise -> next_coord (x, y) ls

where
next_coord_in_entries :: X_Coord -> Placed_Elements e -> Sparse_Line e -> Ordered_Lists_2D e -> Maybe Coord
next_coord_in_entries x current_entries current_line rest_world = case current_entries of
[] -> Nothing
c: cs
| x < x_pos c -> Nothing
| x == x_pos c -> case cs of
c2: _ -> Just (x_pos c2, y_pos current_line)
[] -> case rest_world of
[] -> Nothing
l2: _ -> case (entries l2) of
[] -> Nothing
c2: _ -> Just(x_pos c2, y_pos l2)
| otherwise -> next_coord_in_entries x cs current_line rest_world
remove_elements_less_than_x :: X_Coord -> Ordered_Lists_2D e -> Ordered_Lists_2D e
remove_elements_less_than_x x world = case world of
l: ls -> remove_from_line x l: remove_elements_less_than_x x ls
[] -> []
where
remove_from_line :: X_Coord -> Sparse_Line e -> Sparse_Line e
remove_from_line x line = Sparse_Line {y_pos = y_pos line, entries = remove_from_entries x (entries line)}
where
remove_from_entries :: X_Coord -> Placed_Elements e -> Placed_Elements e
remove_from_entries x cells = case cells of
c: cs
| x_pos c < x -> remove_from_entries x cs
| otherwise -> cells
[] -> []

remove_elements_less_than_y :: Y_Coord -> Ordered_Lists_2D e -> Ordered_Lists_2D e
remove_elements_less_than_y y world = case world of
[] -> []
l: ls
| y_pos l < y -> remove_elements_less_than_y y ls
| otherwise -> world
local_lines :: Y_Coord -> Ordered_Lists_2D e -> Ordered_Lists_2D e
local_lines y world = read_neighbouring_lines y 1 world
where
read_neighbouring_lines :: Y_Coord -> Distance -> Ordered_Lists_2D e -> Ordered_Lists_2D e
read_neighbouring_lines y dist world = case world of
l: ls
| y < (y_pos l) - dist -> []
| abs (y – y_pos l) <= dist -> l: read_neighbouring_lines y dist ls
| otherwise -> read_neighbouring_lines y dist ls
[] -> []

local_elements :: Coord -> Ordered_Lists_2D e -> Ordered_Lists_2D e
local_elements (x, y) world = read_neighbours (x, y) 1 world
where
read_neighbours :: Coord -> Distance -> Ordered_Lists_2D e -> Ordered_Lists_2D e
read_neighbours (x, y) dist world = case world of
l: ls
| y < (y_pos l) - dist -> []
| abs (y – y_pos l) <= dist -> neighbours_in_line l: (read_neighbours (x, y) dist ls)
| otherwise -> read_neighbours (x, y) dist ls
[] -> []
where
neighbours_in_line :: Sparse_Line e -> Sparse_Line e
neighbours_in_line line = Sparse_Line {y_pos = y_pos line, entries = neighbours_in_entries (entries line)}
where
neighbours_in_entries :: Placed_Elements e -> Placed_Elements e
neighbours_in_entries list = case list of
c: cs
| x < (x_pos c) - dist -> []
| abs (x – x_pos c) <= dist -> Placed_Element {x_pos = (x_pos c), entry = (entry c)}: neighbours_in_entries cs
| otherwise -> neighbours_in_entries cs
[] -> []
local_elements_list :: Coord -> Ordered_Lists_2D e -> [e]
local_elements_list (x, y) world = read_neighbours_list (x, y) 1 world
where
read_neighbours_list :: Coord -> Distance -> Ordered_Lists_2D e -> [e]
read_neighbours_list (x, y) dist world = case world of
l: ls
| y < (y_pos l) - dist -> []
| abs (y – y_pos l) <= dist -> neighbours_in_entries (entries l) ++ (read_neighbours_list (x, y) dist ls)
| otherwise -> read_neighbours_list (x, y) dist ls
[] -> []
where
neighbours_in_entries :: Placed_Elements e -> [e]
neighbours_in_entries list = case list of
c: cs
| x < (x_pos c) - dist -> []
| abs (x – x_pos c) <= dist -> entry c: neighbours_in_entries cs
| otherwise -> neighbours_in_entries cs
[] -> []
map_Ordered_Lists_2D :: (Element_w_Coord e -> b) -> Ordered_Lists_2D e -> Ordered_Lists_2D b
map_Ordered_Lists_2D f world = case world of
l: ls -> map_line f l: map_Ordered_Lists_2D f ls
[] -> []
where
map_line :: (Element_w_Coord e -> b) -> Sparse_Line e -> Sparse_Line b
map_line f line = Sparse_Line {y_pos = (y_pos line), entries = map_elements f (y_pos line) (entries line)}
where
map_elements :: (Element_w_Coord e -> b) -> Y_Coord -> Placed_Elements e -> Placed_Elements b
map_elements f y elements = case elements of
c: cs -> Placed_Element {x_pos = (x_pos c), entry = f ((entry c), ((x_pos c), y))}: map_elements f y cs
[] -> []

map_Ordered_Lists_2D_to_list :: (Element_w_Coord e -> b) -> Ordered_Lists_2D e -> [b]
map_Ordered_Lists_2D_to_list f world = case world of
l: ls -> map_line f l ++ map_Ordered_Lists_2D_to_list f ls
[] -> []
where
map_line :: (Element_w_Coord e -> b) -> Sparse_Line e -> [b]
map_line f line = map_elements f (y_pos line) (entries line)
where
map_elements :: (Element_w_Coord e -> b) -> Y_Coord -> Placed_Elements e -> [b]
map_elements f y elements = case elements of
c: cs -> f ((entry c), ((x_pos c), y)): map_elements f y cs
[] -> []
map_Ordered_Lists_2D_w_context :: (Element_w_Coord e -> c -> b) -> c -> Ordered_Lists_2D e -> Ordered_Lists_2D b
map_Ordered_Lists_2D_w_context f context world = case world of
l: ls -> map_line f context l: map_Ordered_Lists_2D_w_context f context ls
[] -> []
where
map_line :: (Element_w_Coord e -> c -> b) -> c -> Sparse_Line e -> Sparse_Line b
map_line f context line = Sparse_Line {y_pos = (y_pos line), entries = map_elements f context (y_pos line) (entries line)}
where
map_elements :: (Element_w_Coord e -> c -> b) -> c -> Y_Coord -> Placed_Elements e -> Placed_Elements b
map_elements f context y elements = case elements of
c: cs -> Placed_Element {x_pos = (x_pos c), entry = f ((entry c), ((x_pos c), y)) context}: map_elements f context y cs
[] -> []

map_Ordered_Lists_2D_w_context_to_list :: (Element_w_Coord e -> c -> b) -> c -> Ordered_Lists_2D e -> [b]
map_Ordered_Lists_2D_w_context_to_list f context world = case world of
l: ls -> map_line f context l ++ map_Ordered_Lists_2D_w_context_to_list f context ls
[] -> []
where
map_line :: (Element_w_Coord e -> c -> b) -> c -> Sparse_Line e -> [b]
map_line f context line = map_elements f context (y_pos line) (entries line)
where
map_elements :: (Element_w_Coord e -> c -> b) -> c -> Y_Coord -> Placed_Elements e -> [b]
map_elements f context y elements = case elements of
c: cs -> f ((entry c), ((x_pos c), y)) context : map_elements f context y cs
[] -> []

size :: Ordered_Lists_2D e -> Int
size world = case world of
l: ls -> length (entries l) + size ls
[] -> 0

sparse_list_2D_to_list :: Ordered_Lists_2D e -> [e]
sparse_list_2D_to_list world = case world of
l: ls -> (entries_to_list (entries l)) ++ sparse_list_2D_to_list ls
[] -> []
where
entries_to_list :: Placed_Elements e -> [e]
entries_to_list entries = case entries of
c: cs -> (entry c): entries_to_list cs
[] -> []
sparse_list_2D_to_list_2D :: Ordered_Lists_2D e -> List_2D e
sparse_list_2D_to_list_2D world = case world of
l: ls -> (entries_to_list (y_pos l) (entries l)) ++ sparse_list_2D_to_list_2D ls
[] -> []
where
entries_to_list :: Y_Coord -> Placed_Elements e -> List_2D e
entries_to_list y entries = case entries of
c: cs -> (entry c, (x_pos c, y)): entries_to_list y cs
[] -> []

Assignment 1 student template/Sources/Drawing/Cell.hs
—
— Uwe R. Zimmer
— Australia 2012
—
module Drawing.Cell (
draw_cell — :: (Cell, Coord) -> Float -> Picture
) where
import Data.Cell (Cell)
import Data.Coordinates (Coord)
import Drawing.Cell_To_Colour (cell_to_colour)
import Graphics.Gloss (Picture, rectangleSolid, translate, color)
draw_cell :: (Cell, Coord) -> Float -> Picture
draw_cell (cell, (x, y)) size =
translate x’ y’ (color (cell_to_colour cell) (rectangleSolid (size – 1) (size – 1)))
where x’ = size * fromIntegral x
y’ = size * fromIntegral y

Assignment 1 student template/Sources/Drawing/Cell_To_Colour.hs
—
— Uwe R. Zimmer
— Australia 2012
—
module Drawing.Cell_To_Colour (
cell_to_colour — :: Cell -> Color
) where
import Data.Cell (Cell (Head, Tail, Conductor, Empty))
import Graphics.Gloss (Color, red, blue, yellow, black, dark)
cell_to_colour :: Cell -> Color
cell_to_colour cell = case cell of
Head -> dark blue
Tail -> dark red
Conductor -> dark yellow
Empty -> black

Assignment 1 student template/Sources/Drawing/Constants.hs
—
— Uwe R. Zimmer
— Australia 2012
—
module Drawing.Constants (
Window_Size (x_dim, y_dim),
Window_Pos (x_pos, y_pos),

window_size,
window_pos,

cell_size
) where
import World_Class (World_Dimensions (w_width, w_height))
data Window_Size = Window_Size {x_dim, y_dim :: Int}
data Window_Pos = Window_Pos {x_pos, y_pos :: Int}
window_size = Window_Size {x_dim = 800, y_dim = 800} :: Window_Size
window_pos = Window_Pos {x_pos = 10, y_pos = 10} :: Window_Pos
cell_size :: World_Dimensions -> Float
cell_size dim = (1.0 – border_percentage) * min (x_window_size / f_width) (y_window_size / f_height)

where
(x_window_size, y_window_size) = (fromIntegral (x_dim window_size), fromIntegral (y_dim window_size))
(f_width, f_height) = (fromInteger (w_width dim) , fromInteger (w_height dim))
border_percentage = 0.05 — meaning 5% of the tighter dimension will be used for border

Assignment 1 student template/Sources/Drawing/Simulation (for gloss <= 1.5.2.1).hs -- -- Uwe R. Zimmer -- Australia 2012 -- -- Version for gloss 1.5.2.1 (or older). module Drawing.Simulation ( simulate -- :: Attributed_World world -- starting state -- -> (Attributed_World world -> Picture) — drawing function
— -> (ViewPort -> Float -> Attributed_World world -> Attributed_World world) — transition function
— -> Int — frames per second
— -> IO ()
) where
import Drawing.Constants (Window_Size (x_dim, y_dim), Window_Pos (x_pos, y_pos), window_size, window_pos)
import Graphics.Gloss (simulateInWindow, black, Picture)
import World_Class (Attributed_World)
simulate :: Attributed_World world
-> (Attributed_World world -> Picture)
-> (Attributed_World world -> Attributed_World world)
-> Int
-> IO ()
simulate a_world draw transfer fps = do
simulateInWindow
“Wireworld” — Window title
(x_dim window_size, y_dim window_size) — Window size
(x_pos window_pos , y_pos window_pos) — Window position
black — Background colour
fps — Transitions per second
a_world — Starting state
draw — Function to draw world
(\_ _ -> transfer) — Step world one state

Assignment 1 student template/Sources/Drawing/Simulation (for gloss >= 1.6.0.1).hs
—
— Uwe R. Zimmer
— Australia 2013
—
— Version for gloss 1.6.0.1 (or newer).
module Drawing.Simulation (
simulate — :: Attributed_World world — starting state
— -> (Attributed_World world -> Picture) — drawing function
— -> (ViewPort -> Float -> Attributed_World world -> Attributed_World world) — transition function
— -> Int — frames per second
— -> IO ()
) where
import Drawing.Constants (Window_Size (x_dim, y_dim), Window_Pos (x_pos, y_pos), window_size, window_pos)
import Graphics.Gloss (Display (InWindow), black, Picture)
import qualified Graphics.Gloss (simulate)
import World_Class (Attributed_World)
simulate :: Attributed_World world
-> (Attributed_World world -> Picture)
-> (Attributed_World world -> Attributed_World world)
-> Int
-> IO ()
simulate a_world draw transfer fps = do
Graphics.Gloss.simulate
(InWindow — In a window
“Wireworld” — Window title
(x_dim window_size, y_dim window_size) — Window size
(x_pos window_pos , y_pos window_pos)) — Window position
black — Background colour
fps — Transitions per second
a_world — Starting state
draw — Function to draw world
(\_ _ -> transfer) — Step world one state

Assignment 1 student template/Sources/Drawing/Simulation.hs
—
— Uwe R. Zimmer
— Australia 2013
—
— Version for gloss 1.6.0.1 (or newer).
module Drawing.Simulation (
simulate — :: Attributed_World world — starting state
— -> (Attributed_World world -> Picture) — drawing function
— -> (ViewPort -> Float -> Attributed_World world -> Attributed_World world) — transition function
— -> Int — frames per second
— -> IO ()
) where
import Drawing.Constants (Window_Size (x_dim, y_dim), Window_Pos (x_pos, y_pos), window_size, window_pos)
import Graphics.Gloss (Display (InWindow), black, Picture)
import qualified Graphics.Gloss (simulate)
import World_Class (Attributed_World)
simulate :: Attributed_World world
-> (Attributed_World world -> Picture)
-> (Attributed_World world -> Attributed_World world)
-> Int
-> IO ()
simulate a_world draw transfer fps = do
Graphics.Gloss.simulate
(InWindow — In a window
“Wireworld” — Window title
(x_dim window_size, y_dim window_size) — Window size
(x_pos window_pos , y_pos window_pos)) — Window position
black — Background colour
fps — Transitions per second
a_world — Starting state
draw — Function to draw world
(\_ _ -> transfer) — Step world one state

Assignment 1 student template/Sources/Drawing/Worlds/For_List_2D.hs
—
— Uwe R. Zimmer
— Australia 2012
—
module Drawing.Worlds.For_List_2D (
draw_world — :: List_2D Cell -> Float -> Picture
) where
import Data.Cell (Cell)
import Data.List_2D (List_2D, map_List_2D_w_context_to_list)
import Drawing.Cell (draw_cell)
import Graphics.Gloss (Picture (Pictures))
draw_world :: List_2D Cell -> Float -> Picture
draw_world world cell_size = Pictures (map_List_2D_w_context_to_list draw_cell cell_size world)

Assignment 1 student template/Sources/Drawing/Worlds/For_Ordered_Lists_2D.hs
—
— Uwe R. Zimmer
— Australia 2012
—
module Drawing.Worlds.For_Ordered_Lists_2D (
draw_world — :: Ordered_Lists_2D Cell -> Float -> Picture
) where
import Data.Cell (Cell)
import Data.Ordered_Lists_2D (Ordered_Lists_2D, map_Ordered_Lists_2D_w_context_to_list)
import Drawing.Cell (draw_cell)
import Graphics.Gloss (Picture (Pictures))
draw_world :: Ordered_Lists_2D Cell -> Float -> Picture
draw_world world cell_size = Pictures (map_Ordered_Lists_2D_w_context_to_list draw_cell cell_size world)

Assignment 1 student template/Sources/Load/Pixel_To_Cell.hs
—
— Uwe R. Zimmer
— Australia 2012
—
module Load.Pixel_To_Cell (
Pixel (Pixel, red, green, blue, alpha),
pixel_to_cell — :: Pixel -> Cell
) where
import Data.Cell (Cell (Head, Tail, Conductor, Empty))
import Data.Word (Word8)
data Pixel = Pixel {red, green, blue, alpha :: Word8}
pixel_to_cell :: Pixel -> Cell
pixel_to_cell Pixel {red = r, green = g, blue = b, alpha = _}
| r >= 128 && g >= 128 && b < 128 = Conductor -- somewhat yellow | r >= 128 && g < 128 && b < 128 = Tail -- somewhat red | r < 128 && g < 128 && b >= 128 = Head — somewhat blue
| otherwise = Empty

Assignment 1 student template/Sources/Load/Wireworld.hs
—
— Uwe R. Zimmer
— Australia 2012
—
— based on a module by:
—
— By Ludvik ‘Probie’ Galois
— Modified 10 Feb 2012
module Load.Wireworld (
read_world_from_bmp_file — :: String — Filename
— -> Attributed_World world — Empty world
— -> (Loaded_World -> Attributed_World world) — prepare function
— -> IO (Attributed_World world) — returns the loaded and prepared world
) where
import Codec.BMP (readBMP, BMP, bmpDimensions, unpackBMPToRGBA32)
import Data.ByteString (unpack)
import Data.Cell (Cell (Empty))
import Data.Word (Word8)
import Load.Pixel_To_Cell (Pixel (Pixel, red, green, blue, alpha), pixel_to_cell)
import System.IO (stderr, hPutStrLn)
import World_Class ( Attributed_World,
Loaded_World (L_World, loaded_dim, loaded_world),
World_Dimensions (World_Dim, w_width, w_height))
read_world_from_bmp_file :: String
-> Attributed_World world
-> (Loaded_World -> Attributed_World world)
-> IO (Attributed_World world)
read_world_from_bmp_file filename empty_world prepare_world = do
inputbmp <- readBMP filename case inputbmp of Left e -> hPutStrLn stderr (show e) >> return empty_world — show error
Right bmp -> return (bmp_to_world bmp prepare_world) — return the loaded world
bmp_to_world :: BMP -> (Loaded_World -> Attributed_World world) -> Attributed_World world
bmp_to_world bmp prepare_world = prepare_world
(L_World { loaded_dim = World_Dim {w_width = width, w_height = height},
loaded_world = cells_with_coordinates})
where
cells_with_coordinates = filter non_empty (zip cells coordinates)
where
non_empty (cell, _) = not (cell == Empty)
cells = map pixel_to_cell rgba_pixels
where
rgba_pixels = split_into_pixel (unpack (unpackBMPToRGBA32 bmp))
coordinates = [(x – (width `div` 2), y – (height `div` 2))
| y <- [0 .. height - 1], x <- [0 .. width - 1]] (width, height) = (fromIntegral width', fromIntegral height') where (width', height') = bmpDimensions bmp split_into_pixel :: [Word8] -> [Pixel]
split_into_pixel list = case list of
r: g: b: a: xs -> Pixel {red = r, green = g, blue = b, alpha = a}: split_into_pixel xs
[] -> []
_ -> error “bitmap does not spit up into four byte pixels”

Assignment 1 student template/Sources/Measure/Time.hs
—
— Uwe R. Zimmer
— Australia 2012
—
module Measure.Time (
time_expression — :: IO e -> IO e — prints the elapsed time for evaluating the expression e
) where
import Data.Time.Clock (getCurrentTime, diffUTCTime)
— import System.CPUTime (getCPUTime)
import Text.Printf (printf)
— Time is currently measured in overall time which has been found to be more predictable.
— While CPU time measurements seem more appropriate, Haskell doesn’t quite seem to deliver as
— advertised on those functions.
time_expression :: IO e -> IO e
time_expression expression = do
start_time <- getCurrentTime -- getCPUTime value <- expression stop_time <- getCurrentTime -- getCPUTime let diff = diffUTCTime stop_time start_time -- (fromIntegral (stop_time - start_time)) / (10^12) printf "\tElapsed time: %0.3f sec" (realToFrac diff :: Double) -- (diff :: Double) return value Assignment 1 student template/Sources/Transitions/For_List_2D.hs -- -- Uwe R. Zimmer -- Australia 2012 -- module Transitions.For_List_2D ( transition_world -- :: List_2D Cell -> List_2D Cell
) where
import Data.Cell (Cell (Head, Tail, Conductor, Empty))
import Data.Coordinates
import Data.List_2D

— Replace this function with something more meaningful:
transition_world :: List_2D Cell -> List_2D Cell
transition_world world = world

Assignment 1 student template/Sources/Transitions/For_Ordered_Lists_2D.hs
—
— Uwe R. Zimmer
— Australia 2012
—
module Transitions.For_Ordered_Lists_2D (
transition_world — :: Ordered_Lists_2D Cell -> Ordered_Lists_2D Cell
) where
import Data.Cell (Cell (Head, Tail, Conductor, Empty))
import Data.Coordinates
import Data.Ordered_Lists_2D

— Replace this function with something more meaningful:

transition_world :: Ordered_Lists_2D Cell -> Ordered_Lists_2D Cell
transition_world world = world

Assignment 1 student template/Sources/Wireworld.hs
—
— Uwe R. Zimmer
— Australia 2012
—
import Data.Cell (Cell (Head))
import Commandline.Options (args_to_options, Data_Structure (List_2D, Ordered_Lists_2D), Options (world_filename, no_of_tests, model, fps))
import Drawing.Simulation (simulate)
import Load.Wireworld (read_world_from_bmp_file)
import Measure.Time (time_expression)
import System.Environment (getArgs)
import Worlds.As_List_2D — (World_model, World_Class (empty_world, prepare_world, transition_world, draw_world, element_occurrence, size))
import Worlds.As_Ordered_Lists_2D — (World_model, World_Class (empty_world, prepare_world, transition_world, draw_world, element_occurrence, size))
import World_Class (Attributed_World)
iterate_function_n_times :: (a -> a) -> Int -> a -> a
iterate_function_n_times f n x
| n > 0 = iterate_function_n_times f (n – 1) (f x)
| otherwise = x
run_tests :: Attributed_World world
-> Int
-> (Attributed_World world -> Int)
-> (Cell -> Attributed_World world -> Int)
-> IO ()
run_tests a_world runs size element_occurrence
| runs > 0 = do
putStr “Active heads in the world: ”
time_expression (putStr (show (element_occurrence Head a_world)))
putStrLn (“\tafter ” ++ show runs ++ ” transitions on ” ++ show (size a_world) ++ ” cells”)
| otherwise = do
putStrLn “No measurements are taken – number of tests has been set to zero”
main :: IO ()
main = do
args <- getArgs let options = args_to_options args case model options of List_2D -> do
world <- read_world_from_bmp_file (world_filename options) empty_world prepare_world :: IO (Attributed_World Worlds.As_List_2D.World_model) let transformed_world = iterate_function_n_times transition_world (no_of_tests options) world run_tests transformed_world (no_of_tests options) size element_occurrence simulate world draw_world transition_world (fps options) Ordered_Lists_2D -> do
world <- read_world_from_bmp_file (world_filename options) empty_world prepare_world :: IO (Attributed_World Worlds.As_Ordered_Lists_2D.World_model) let transformed_world = iterate_function_n_times transition_world (no_of_tests options) world run_tests transformed_world (no_of_tests options) size element_occurrence simulate world draw_world transition_world (fps options) Assignment 1 student template/Sources/World_Class.hs -- -- Uwe R. Zimmer -- Australia 2012 -- module World_Class ( World_Class ( empty_world, -- :: Attributed_World world prepare_world, -- :: Loaded_World -> Attributed_World world
transition_world, — :: Attributed_World world -> Attributed_World world
draw_world, — :: Attributed_World world -> Picture
element_occurrence, — :: Cell -> Attributed_World world -> Int
size — :: Attributed_World world -> Int
),
World_Dimensions (World_Dim, w_width, w_height),
Loaded_World (L_World, loaded_dim, loaded_world),
Attributed_World (A_World, world_dim, world_itself),

fun_world — :: (world -> world) -> Attributed_World world -> Attributed_World world
— Applies a function to the world inside an attributed world – simple helper to make things readable

) where
import Data.Cell (Cell)
import Data.Coordinates (Distance)
import Data.List_2D (List_2D)
import Graphics.Gloss (Picture)
data World_Dimensions = World_Dim {w_width, w_height :: Distance}
data Loaded_World = L_World {loaded_dim :: World_Dimensions, loaded_world :: List_2D Cell}
data Attributed_World world = A_World {world_dim :: World_Dimensions, world_itself :: world}
class World_Class world where
empty_world :: Attributed_World world
prepare_world :: Loaded_World -> Attributed_World world
transition_world :: Attributed_World world -> Attributed_World world
draw_world :: Attributed_World world -> Picture
element_occurrence :: Cell -> Attributed_World world -> Int
size :: Attributed_World world -> Int

fun_world :: (world -> world) -> Attributed_World world -> Attributed_World world
fun_world f a_world = A_World {world_dim = world_dim a_world, world_itself = f (world_itself a_world)}

Assignment 1 student template/Sources/Worlds/As_List_2D.hs
{-# LANGUAGE FlexibleInstances, TypeSynonymInstances #-}
—
— Uwe R. Zimmer
— Australia 2012
—
module Worlds.As_List_2D (
World_model,

World_Class (
empty_world, — :: World_model
prepare_world, — :: List_2D Cell -> World_model
transition_world, — :: World_model -> World_model
draw_world, — :: World_model -> Float -> Picture
element_occurrence, — :: Cell -> World_model -> Int
size — :: World_model -> Int
)

) where
import Data.Cell (Cell)
import Data.List_2D (List_2D, element_occurrence, size)
import Drawing.Constants (cell_size)
import Drawing.Worlds.For_List_2D (draw_world)
import Transitions.For_List_2D (transition_world)
import World_Class ( World_Class (
empty_world,
prepare_world,
transition_world,
draw_world,
element_occurrence,
size),
World_Dimensions (World_Dim, w_width, w_height),
Loaded_World (loaded_dim, loaded_world),
Attributed_World (A_World, world_dim, world_itself),
fun_world)

type World_model = List_2D Cell

instance World_Class World_model where
empty_world = A_World {world_dim = World_Dim {w_width = 0, w_height = 0}, world_itself = []}
prepare_world l_world = A_World {world_dim = loaded_dim l_world, world_itself = (loaded_world l_world)}
transition_world a_world = fun_world Transitions.For_List_2D.transition_world a_world
draw_world a_world = Drawing.Worlds.For_List_2D.draw_world (world_itself a_world) (cell_size (world_dim a_world))
element_occurrence cell a_world = Data.List_2D.element_occurrence cell (world_itself a_world)
size world = Data.List_2D.size (world_itself world)

Assignment 1 student template/Sources/Worlds/As_Ordered_Lists_2D.hs
{-# LANGUAGE FlexibleInstances, TypeSynonymInstances #-}
—
— Uwe R. Zimmer
— Australia 2012
—
module Worlds.As_Ordered_Lists_2D (
World_model,

World_Class (
empty_world, — :: World_model
prepare_world, — :: List_2D Cell -> World_model
transition_world, — :: World_model -> World_model
draw_world, — :: World_model -> Float -> Picture
element_occurrence, — :: Cell -> World_model -> Int
size — :: World_model -> Int
)

) where
import Data.Cell (Cell)
import Data.Ordered_Lists_2D (Ordered_Lists_2D, insert_list, element_occurrence, size)
import Drawing.Constants (cell_size)
import Drawing.Worlds.For_Ordered_Lists_2D (draw_world)
import Transitions.For_Ordered_Lists_2D (transition_world)
import World_Class ( World_Class (
empty_world,
prepare_world,
transition_world,
draw_world,
element_occurrence,
size),
World_Dimensions (World_Dim, w_width, w_height),
Loaded_World (loaded_dim, loaded_world),
Attributed_World (A_World, world_dim, world_itself),
fun_world)

type World_model = Ordered_Lists_2D Cell

instance World_Class World_model where
empty_world = A_World {world_dim = World_Dim {w_width = 0, w_height = 0}, world_itself = []}
prepare_world l_world = A_World {world_dim = loaded_dim l_world, world_itself = insert_list (loaded_world l_world) []}
transition_world a_world = fun_world Transitions.For_Ordered_Lists_2D.transition_world a_world
draw_world a_world = Drawing.Worlds.For_Ordered_Lists_2D.draw_world (world_itself a_world) (cell_size (world_dim a_world))
element_occurrence cell a_world = Data.Ordered_Lists_2D.element_occurrence cell (world_itself a_world)
size world = Data.Ordered_Lists_2D.size (world_itself world)

Assignment 1 student template/Wireworlds/Circuit.bmp

Assignment 1 student template/Wireworlds/Cycle.bmp

Assignment 1 student template/Wireworlds/Input.bmp

Assignment 1 student template/Wireworlds/Langton’s_Ant_11x11.bmp

Assignment 1 student template/Wireworlds/Langton’s_Ant_3x3.bmp

Assignment 1 student template/Wireworlds/Langton’s_Ant_5x5.bmp

Assignment 1 student template/Wireworlds/Langton’s_Ant_7x7.bmp

Assignment 1 student template/Wireworlds/Langton’s_Ant_cell.bmp

Assignment 1 student template/Wireworlds/Output.bmp

Assignment 1 student template/Wireworlds/Playfield.bmp

Assignment 1 student template/Wireworlds/Seven_Segment_Circular_Counter_delay_line.bmp

Assignment 1 student template/Wireworlds/Seven_Segment_Circular_Counter_shift_back.bmp

Assignment 1 student template/Wireworlds/Seven_Segment_Counter_direct_loopback.bmp

Assignment 1 student template/Wireworlds/Seven_Segment_Counter_with_long_delay.bmp

Assignment 1 student template/Wireworlds/Seven_Segments_9_1.bmp

Assignment 1 student template/Wireworlds/Trollface.bmp

Assignment 1 student template/Wireworlds/XOr.bmp

1 | ANU College of Engineering and Computer Science March 2013

W I R I N G U P W I R E WO R L D
First assignment for Introduction to Programming and Algorithms 2013

Uwe R. Zimmer based on work by Robert Offner (Probie)

What are you looking at on the right?

• A seven segment display showing the number ?

• A picture of a seven segment dis-
play showing the number ?

• A picture of a computer emulating electronic circuits?

• A machine emulating a machine emulating a machine?

• A weird bunch of colour spots?

• A very simple machine, yet as powerful as any other computer?

• A pattern which is probably supposed to change over time?

Yes, you guessed right: this is a cellular automaton. And pattern you see (the whole picture) is
its current state. Most cellular automata have a state which is a finite, fixed (here: two) dimen-
sional, rectangular pattern (grid, matrix) of cells – which makes it easy to display on a screen.
Each cell is in exactly one out of finite list of discrete cell states at any time. As these cell
states are finite and fixed, we give each cell state a colour and just print a dot of this colour for
each cell in the automaton. So far we only have a weird way to describe a bitmap picture.

The interesting aspect of the cellular automata lies in the rules which are used to progress from
one state to the next. So the pictures on this page are actually only snapshots of states and
the cellular automata will make them move. This is done by a (usually stunningly small) set of
rules which only take the current state of the cell itself and its local neighbourhood into ac-
count.

The specific cellular automaton which you see here is called
Wireworld and is defined by four possible states for each cell:

• Empty

• Conductor

• Electron head

• Electron tail

and the accompanying four rules to progress each cell into
the next state:

• Empty Empty&

• Conductor
Electron head
Conductor

Electron heads; if 1 or 2 of the 8 adjacent cells are
; otherwise

& (

• Electron head Electron tail&

• Electron tail Conductor&

This sounds like it is just meant to send an electron through a wire, and in fact it does that
too. Look at the simple state on the right and progress it a few states further by applying the
rules of Wireworld (in your head or on a piece of paper).

2 | ANU College of Engineering and Computer Science March 2013

That’s all? All this effort just to move an electron in a circle?
It turns out that this is just the beginning and those four cell
states and rules of Wireworld can be employed to express any
form of complex computation which for example your computer
in front of you is capable of. To get into the mood, have a closer
look at this state to the right and progress it a few states further
as well in your head (or on a piece of paper).

This state turns out to implement the functionality of an Exclusive-Or gate (the logical function
which returns true if exactly one of the inputs is true). Any other logic gate can be formulated in
a similar way, and based on what we know about logic: we can build any digital computer out
of basic logic gates1.

While Wireworlds can implement logic gates, they are more flexible and we do not need to
restrict ourselves to a design in logic gates alone. As you will watch the Wireworlds move along
in a few days, you will find that there is for instance also a quite complex encoding of time and
synchronization happening. Cellular Automata have been frequently discussed as an alterna-
tive mode of computation and also have interesting relations to Quantum Computing and
Massively Parallel Computing. I’ll leave it to you to dig deeper, if you are so inclined, but here
we continue with your concrete assignment goal.

Programming task
Your task is to make the Wireworld move. In Haskell terms you will need to implement the func-
tion:

transition_world :: World_model -> World_model

In fact your will implement it twice:

transition_world :: List_2D Cell -> List_2D Cell

transition_world :: Ordered_Lists_2D Cell -> Ordered_Lists_2D Cell

based on two different underlying data structures used to store the current world (state of the
automaton) while the Cell states are simply:

data Cell = Head | Tail | Conductor | Empty.

In the first case the world is stored as a single list where each cell has accompanying coordi-
nates attached. Thus List_2D translates into

type List_2D e = [(e, (X_Coord, Y_Coord))]

where e is a placeholder for any type (we use it for our type Cell). No particular order on those
coordinates is assumed.

In the second case the world is split up into lines (cells sharing the same y coordinate) and
each line is stored in a separate list. Each line has a y coordinate, and each cell inside the line
has an x coordinate attached to it. The whole world is then a list of those lines. Thus Ordered_
Lists_2D breaks down into:

type Ordered_Lists_2D e = [Sparse_Line e]

data Sparse_Line e = Sparse_Line {y_pos :: Y_Coord, entries :: Placed_Elements e}

type Placed_Elements e = [Placed_Element e]

data Placed_Element e = Placed_Element {x_pos :: X_Coord, entry :: e}

where e is again a placeholder for any type. All Sparse_Lines are ordered ascending by
Y_Coord and all cells inside Placed_Elements are ordered ascending by X_Coord.

1 In fact we have too much already, as a “not-and” or NAnd gate alone is suf-
ficient to implement any other part of your computer.

3 | ANU College of Engineering and Computer Science March 2013

The two functions transition_world which you need to complete are found in the two mod-
ules in the directory Sources/Transitions.

As both data structures offer the same functions it would be possible to write the same code
for both of your transition_world functions – yet think carefully whether this would be a clever
idea. While the two data-structures offer the same logical functionality, the runtimes which they
take to do so may be quite different. Hence it will make sense to write your transition functions
in a way that they will exploit the characteristics of the underlying data structures. If you are
unsure how they data structures differ, you may also start by running the same code in both
functions and measure the number of transitions which each of them will achieve per second
(read on to find out how to measure those). This will give you a hint as to what’s happening
here. Then start exploring how you could re-arrange your code in order to benefit from the
characteristics of the two offered data structures.

Note that none of those data-structures is “dense”, i.e. not all coordinates need to be explicitly
represented. As you will have noticed when looking at the rules: the Empty cell in Wireworld
will always stay Empty. As it will never change anyway, we don’t need to store it. Similar to the
concept of negative space in art, it is still part of the world, while we will never actually handle
Empty cells. Those data structures are also not limited in size at any time. Wireworlds in its
standard definition will not take advantage of this feature though, as they do not grow or shrink

– all action happens on the existing wires. It is still a handy feature for some other cellular au-
tomata where cells can “spawn” or “vanish” into empty space and this “growth” or “shrinkage”
is not necessarily limited either.

Setting up your account or computer for the assignment
Firstly, if you have not already done so, download the source code for the assignment from
the course web-site. Secondly (if you want to run the assignment also on your own computer),
install the gloss and bitmap libraries for Haskell. This can be done by running

> cabal update
> cabal install gloss bmp

from the terminal (or command prompt on windows). Those libraries are installed in the labs.

You can check if it works by going to the top directory of the Wireworld sources (where you find
make_Wireworld) and compiling it with2 (in one line) (no need to type it: the line is also given to
you in the file make_Wireworld, which you can run with “./make_Wireworld”):

> ghc –make -O2 -W Sources/Wireworld.hs -iSources
-odir `uname -m` -hidir `uname -m` -o Wireworld

You can now run your freshly built program by “./Wireworld”, but as you didn’t write any
transition function yet, the world will remain static. You can drag the world with the mouse, right-
click-drag to rotate the world, or use page-up/page-down (or mouse scroll wheel) to magnify it. If
this all works, you are technically set to begin the assignment, yet you need a concept first.

How to design your functions
You are now confronted (and quite likely for the first time) with a program design job which
clearly goes beyond “fill in the gaps in the way we did in the last lecture”. The provided frame-
work is specifically designed to be neither suggestive nor unnecessary restrictive, thus there

2 “–make” means that the compiler checks what has been changed lately and only re-
compiles the new files and files which depend on them – “-O2” stands for “Optimize
level 2” (basically telling the compiler to put some effort into it) – “-W” activates all Warn-
ings (which gives you more hints about things which might be wrong) – “iSources” tells
the compiler where the source files are – “-odir `uname -m` -hidir `uname -m`”
tells the compiler to keep your source directories neat and tiny and store the ob-
ject and interface files in a directory which has the name of your CPU architec-
ture – “-o Wireworld” specifies the name of the object (executable) file).

4 | ANU College of Engineering and Computer Science March 2013

are hundreds of different ways how to approach the problem. While this sounds good in princi-
ple, you might very well find yourself staring at the cursor for a while and nothing is coming up.

While you can of course design your functions in any way you see fit, I suggest the following
basic process to get there:

a. Grasp the problem: What is the overall goal? What needs to happen to get there?
b. Understand the restrictions and possibilities of the two given data structures: If the world

is represented in either of those two ways: Which forms of access to those data structures
comes easy and natural, and which forms of access are clunky? The provided access
routines look identical (and actual provide the exact same logical functionality), but they will
work at quite different levels of efficiency – you can reason this out on a piece of paper or
you can have a look at the two modules for the basic data structures and see how those
access routines are implemented. The number of provided access functions is a hopeless
overkill for the task at hand. You will only need very few of those in the end, yet understand-
ing more of them gives you more options. Looking over them might also give you ideas
for good concepts in the next step. Use only those functions which you fully understood.

c. Come up with two concepts how to attack the problem with either of those two data-
structures as the underlying model. If you understood the data-structures, your two ap-
proaches will most likely be different. All programming designs need to be efficient and
elegant (I deliberately leave this vague for the moment). For instance, throwing everything
in the air and check whether things are coincidentally sorted once they are back on the
ground, is probably not an overly efficient and elegant concept for sorting. Some con-
cepts will be a lot faster than others and while speed is usually not the only concern
when designing a new concept, it is always one of them (common other concerns are
logical correctness and maintainability). In concrete terms for your problem at hand:
Consider that your program will be used for much larger worlds – will it still hold up?

d. Break it down: You will most likely not want to implement the transition as one big, mono-
lithic monster function, but you will want to break it down into functions which are easy
to understand and implement. This breakdown will determine the structure of your final
program. For example you might think how to transition a single cell before you transi-
tion the whole world. Or you might want to factor out functions which will be required
frequently, like counting the number of a specific cell type in the local neighbours. Those
are just ideas and you can break down your program in many different ways. Hint:
spend some time to come up with really good names when you break down your func-
tions. While it seems tempting for new programmers to “get it over with” and slap down
code massacre lines like “helper3 = ma (test temp2) i worry”, you will not only drive
your tutor mad, but you will loose sight of what you are doing very quickly yourself.

Features of the provided code
The executable program can be provided with additional settings from the command line:

Usage: Wireworld [OPTION…]
-w[] –world[=]
-t[] –tests[=]
-m[List_2D | Ordered_Lists_2D] –model[=List_2D | Ordered_Lists_2D]
-f[] –fps[=]

The individual options:

• -w or –world: Loads an alternative Wireworld, like in
./Wireworld –world=”Wireworlds/XOr.bmp” for instance. By de-
fault “Wireworlds/Playfield.bmp” will be loaded.

• -t or –tests: Sets the number of transition tests the program will execute on the se-
lected wireworld before showing any graphics, like in ./Wireworld –tests=100 for in-
stance. It will display the amount of time it took your program for this number of tran-
sitions. This will become important when you evaluate and compare your solutions.

5 | ANU College of Engineering and Computer Science March 2013

You can use ./Wireworld –tests=0 to suppress any tests. By default 25 transitions
will be performed. The graphical display will still always start with the initial state.

• -m or –model: Chooses the data-structure which is to be used in this run, like in
./Wireworld –model=List_2D for instance. By default Ordered_Lists_2D will be selected.

• -f or –fps: Sets the frequency at which your world and display is updated (in frames per
second), like in ./Wireworld –fps=1 for instance, to slow down everything to a speed
where you can see in detail what’s going on. By default 25 frames per second are set.

Of course, all of those options or any mixture of them can be given. You will need to use those
options when you test both of your transition functions and measure the performance of your
implementations.

Coding standards

• No piece-wise function definitions. While it is actually common in the Haskell community
to write functions by providing multiple versions of the function which all cover only some
parts of the input space (you will have noticed this praxis in our course textbook as well as
in many on-line tutorials), this is considered somewhere between weird, confusing and im-
possible in any other programming language known to me (please educate me, if you know
another language which “features” this method). The danger is that you write some parts of
a function, forget others, or write them in an overlapping fashion. While the Haskell compiler
actually does provide appropriate warnings in the end, it is still hard to read, and somebody
who has to maintain the code will have a much harder time to see whether you covered
all bases, or this patchwork of functions will make a complete function. The better alter-
native – if the function actually needs to branch off into different cases – is to state those
cases in one spot and provide an answer to all of them right there – this way you see much
easier whether the function is fully defined. Simply use case and/or guarded expressions:

•

faculty’ :: Integer -> Integer
faculty’ 1 = 1
faculty’ 0 = 1
faculty’ n = n * faculty (n-1)

faculty :: Integer -> Integer

faculty n
| n == 0 = 1
| n > 0 = n * faculty (n-1)
| otherwise =
error (“faculty undefined for “
++ (show n))

Clear names for everything. A clear name for a function combined with clear names inside
the pattern which matches the inputs documents most functions well and often sufficiently:

•

help3 :: (T, C) -> Float -> Picture
help3 (a, (c1, c2)) i = ..

draw_cell ::
(Cell, Coord) -> Float -> Picture

draw_cell (cell, (x, y)) size = ..

Usage of the Haskell Prelude (or other standard Haskell packages) is ok, yet the
same rule applies as with the modules provided here: Use only what you under-
stood. You need to explain your design in your report and there is no room for mys-
tery functions in there. An unexplained use of Lambda abstractions for instance
(concepts outside of this course) will usually trigger a plagiarism investigation.

• Scope, or “where to put my functions”: Where your functions appear depends on by
which other functions they are used. Scope is a computer science term for the con-
text from which a function is visible and can be accessed. The usual professional
reflex is to keep the scope small, yet to avoid replication. I.e. if a function is exclu-
sively used by exactly one other function (and a future, wider usage is not anticipated),

6 | ANU College of Engineering and Computer Science March 2013

then consider adding it as a where context to this function. If you find that a func-
tion is (or might become) used by multiple other functions in different packages then
place it in a separate package or a package of its own – instead of replicating it.

• Comments where comments are necessary. Never comment the obvious or on a line-by-
line basis (assume that the reader of your code knows the language and can understand
the meaning of most single code lines by just reading them). Not only would you annoy
the reader with silly descriptions (like “this expression increments the index value by one”),
but it also clutters your code which makes it hard to see the actual substance between all
the clutter. Instead, comment in larger blocks where the functionality is no longer imme-
diately obvious. Also document tricky sections locally, i.e. sections where the meaning or
mechanism does not reveal itself easily. It is also a consideration to simply re-write those
and replace them with actually easy to understand versions (instead of spending your time
documenting a weird code section). Yet sometimes there is a trade-off between efficiency
and maintainability, and not everything can be re-written into a more comprehensible form.

— This function creates a singleton world

— It takes an element with a coordinate

— and returns a List_2D which is the new world

singleton_world :: Element_w_Coord e -> List_2D e

— The function profile for singleton_world

singleton_world element = [element]

— singleton_world takes and elements and returns

— a single element list with this element.

Ordered_Lists_2D,

{- the central data structure of this module:

A list of lists where y coordinates are attached to every list at top level

(the “lines”) and every element inside the line lists has an x coordinate

attached to it.

All lists are sorted in ascending order, yet the coordinates do not need to

be consecutive (or “dense”) -}

Measuring your results
Once your transition functions work, take notes of the performance in terms of time for a
certain number of transitions (use the Wireworld command line options). In order to make the
measurement more stable (your machine does other things in the background and even your
Haskell environment can work differently with every run) take measurements over at least 100
transitions. Do this for different size Wireworlds (you find a whole collection in the Wireworlds
directory) as well as for both data-structures and plot your measured times against the num-
ber of cells in those worlds. What do you expect to see? Do your measurements confirm your
expectations?

Program a Wireworld or extend the automaton
This extension part of the assignment is only to be addressed if you did all the previous, basic
parts perfectly and to your fullest satisfaction. Keep in mind that a badly done assignment
which addresses everything is considered worse than an assignment which addresses only the
basic parts – but does it well. So if you are not yet happy with your work in this assignment so
far: I suggest you rather go back and do a better job on the basics first, before you attempt this
section. Otherwise: read on.

So far, you programmed the mechanics of the Wireworld automaton and watched it at work.
Now you will actually program inside Wireworld. This will require a completely new look at pro-

7 | ANU College of Engineering and Computer Science March 2013

gramming. Your task is to transform this (a serial stream of bits which are “clocked” at a period
of four cells):

into that (which repeats the input in the top wire and represents a binary count of how many
electrons have been seen so far in the eight wires below it):

Your task is to add the missing Wireworld somewhere between those two (while your output
field consists of course only of wires when you design the program) and to use the smallest
number of cells which you can manage. In other words, replace the grey area with the “?” in
the wireworld below with an actual program (wireworld state) and connect the input field with
the output field

such that it will eventually produce the required pattern rolling through the output field:

You are not restricted in the size or shape for your solution, which means that you can also
connect the input and output field anywhere to your solution. The grey area above is just for
illustration and does not suggest how much space you should use for your solution.

Before you come up with funny ideas: the input stream can vary (yet will always be clocked on
a period of four cells), so storing the answer pattern as such is not a solution. If this was still
too easy for you, try to design a counter which counts up when there is an electron and counts
down when there is a gap. Careful: this is seriously hard.

If this task is not appealing to you, then you can alternatively also deliver a new cellu-
lar automaton: Introduce one or multiple new cell types and add rules for those. Make

8 | ANU College of Engineering and Computer Science March 2013

a copy of your Wireworld directory (so that you don’t alter any already working solu-
tions for the basic part of the assignment) and name your new sources directory:
Sources_Extended. In your new directory, you will then need to alter the packages Data.Cell,
Load.Pixel_To_Cell, Drawing.Cell_To_Colour, Transitions.For_Ordered_Lists_2D (or
alternatively Transitions.For_List_2D) to define, load, draw and transition your new cell(s).
Trivial extensions like adding a second tail-cell will not count (ask your tutor if you are in doubt
whether your extension might be considered trivial). The new rules do need to introduce some
new quality into Wireworld. Draw a new world for your new cellular automaton to demonstrate
this new quality.

Report your design concepts and findings
Write a short report which addresses the following items:

• What is your rationale for your program designs?
Did you consider alternatives? Which? Why did you
choose the designs which you now submit? What
makes your solutions efficient and/or elegant? or:
are your solutions less efficient but more readable?

• Attach your measured plots and explain why this
confirms or contradicts your expectations. Would
you consider changing anything in your programs
to change those measurements? What specifically?

• What did you observe while programming a
Wireworld (or your own new automaton) in the
extension section of this assignment? Was
this comparable to other programming you
did so far? How was it similar or different?

• Did you learn anything (technical/scientific abili-
ties or knowledge as well as other skills) dur-
ing this assignment? What? What was the
most interesting part of the assignment, and
what did you spend the most time with?

You can structure your report in whichever form you see fit (and use any program you like) as
long as you address the requested items and the output is of reasonably professional quality.
Technically all fonts and graphics need to be “vector form”, i.e. no pixelated or “bitmap” graph-
ics (except when you attach wireworld screenshots, scans or photos – while scans or photos
will need to be of reasonable high resolution). For readability, switch on kerning and ligatures in
your word processor or layout program. All popular, current day programs can produce profes-
sional looking outputs (with varying degrees of effort) – one exception is “Kingsoft Office” or

“WPS Office”, which is known to produce output to make our eyes tear. Your plots can btw be
done on a piece of paper and scanned or photographed (as long as they are clear and com-
plete).

Your writing should always be concise, so avoid or remove “fluff” in your text – no marks are
awarded for text length, but marks are removed for texts of a rambling nature. If you need sup-
port in technical writing in general or to manage your time at uni then check out the offers at:

https://academicskills.anu.edu.au/

If you are not sure what is expected of you: just ask us for clarification and more details.

Deliverables
Make sure your Sources directories have only *.hs files in them – delete any *.o, *.hi or
executable file which might found its way into there. Archive your Sources directory into a
.tgz, .tar.gz, or .zip archive by the name Assignment_1, i.e. your submittable code file will
for instance have the name Assignment_1.tgz. If you did a new cellular automaton, then also

Langton’s Ant design by Nyles Heise

9 | ANU College of Engineering and Computer Science March 2013

include the Sources_Extended directory in your archive. Alternatively, if you wrote a Wireworld
to solve the extension task, then include this solution bmp file.

Your report need to be saved as a pdf file. Call this Assignment_1 . Make sure that the fonts
which are used in your report are embedded.

On the command line of your lab computer, type the following to submit your work:

submit comp1100 Assignment_1 Assignment_1 Assignment_1.tar.gz

or alternatively if you are a student of comp1130:

submit comp1130 Assignment_1 Assignment_1 Assignment_1.tar.gz

Archive formats which are accepted for your sources are .tgz, .zip and .tar.gz.

Important: the submit command allows you to re-submit as often as you want before the
deadline. Make use of that: submit early versions for two reasons: first you know that your
submit command works (if you will get a success message as response to your command)
and second you are safe from last minute glitches, as you already got a version in – even if
your computer explodes on the last day or your hamster is in a bad mood. Arrange your time
management in order to submit one or two days before the actual deadline – submitting close
to the deadline is usually a sign for a high risk strategy and bad time management and you
should be concerned about this.

The deadline for the assignment will be published on the web-site.

The “late policy” for this course is: “tell us in advance or don’t be late”. If you see that a dead-
line will pose a problem for you, then please contact us with a reason for the delay, and we will
work something out – otherwise: just plan to submit everything a day or two in advance and
you will be fine. The submission system will lock down after the deadline.

Marking
The marking is roughly divided into 60% for the code and 40% for the report. For exceptional
reports or code fragments we might take the liberty to shift those percentages slightly to ac-
knowledge extra efforts.

Marks in the code will be awarded for functionality (i.e. it works), clarity of code (i.e. we imme-
diately understand why it works), and efficiency (i.e. it transitions at a reasonable pace).

Marks in the report will be awarded to concise writing, completeness of the report, and your
understanding of your own designs and findings.

Here is a breakdown of example student cases with different marks awarded:

• Pass: The code compiles and works with at least one of the two data-structures. The
report shows basic understanding of the problem and explains the submitted code.

• Credit: The code compiles without warnings and works with both da-
ta-structures. The code is well structured and well supported in the re-
port. The measurements are fully documented and explained well.

• Distinction: The code is well structured and efficient. The report is excellently
written and addresses all items. The measurements are close to the to be ex-
pected optimum for the individual data-structures and are well explained.

• High Distinction: All distinction level criteria are fulfilled and one of the ex-
tensions has been submitted and excellently documented.

Roughly you can expect to be able to reach a distinction level mark with an excellent submis-
sion of the basic parts alone, and a high distinction mark with an excellent submission includ-
ing one of the extensions. Again: keep in mind that addressing an extension does not guaran-
tee you any kind of mark – it only shifts the upper end for the potential mark.

Any plagiarism which is detected in any part of the assignment will lead to zero marks for the
whole assignment and an investigation. So be strict with comments in your code and report

10 | ANU College of Engineering and Computer Science March 2013

about any collaboration and your sources. Name anybody with whom you collaborated with
(and name the form and scope of the collaboration, e.g. “this function has been developed in a
joint session with John von Neumann”) and name any sources which you drew inspiration from
for a specific part of the assignment (e.g. “this function is based on the example in section 4.3
of the course textbook”). Never directly exchange source code or reports as files – collaborate
on paper or white boards and make sure you do not leave anything behind in the room after
you leave. If your code or report (or any part of it) is found in somebody else’s submission,
you will become part of a plagiarism case. More details about plagiarism can be found on the
course web-site.

Independent of any marking we will also look at the submissions in terms of interesting and
beautiful extensions. Some of those will be shown in class, and (with your permission) poten-
tially elsewhere.

We will also extract exceptionally elegant solutions as well as common disasters from the sub-
mitted codes and will discuss them class (with your name removed of course).

What to do if you have a problem
If you can’t get it to run on your own computer � Ask your tutor for help.

If you’re stuck and can’t work out what to do � Take a break and do something else; staring at
it is only going to frustrate you � Join a PAL session or ask your tutor for help � Take another
break � Panic (and send an e-mail to the lecturer).

If you’ve made a bitmap world and it can’t be loaded � Make sure it is a 24-bit bitmap.

In the last week of the assignment your tutor will also ask you how you are fairing and whether
any last minute hints might help.

In all cases: if you have a problem which you cannot work out in reasonable time on your own,
you must contact somebody. This can be your fellow student, the students and mentors in
your PAL session, the students and tutors in your lab session, or the lecturer. All of us react to
e-mail – usually much faster than your think.