Супер муравейник на ClojureCLR

в 18:22, , рубрики: .net, ants, clojure, многопоточность, Программирование, метки: ,

Многопоточность в Clojure выведена на новый уровень развития, поскольку там реализованы транзакции изменений памяти STM (The software transactional memory system). В качестве демонстрации Рич Хикки (божественный автор Clojure) и Дэвид Миллер (человек, который написал реализацию Clojure под .Net) предлагают программу «ants», которая моделирует муравейник. Каждый муравей там живет в отдельном потоке. Муравьи бегают по клеткам общего поля, собирают еду, носят ее в муравейник и не конфликтуют друг с другом.

Результат своих упражнений с этой программой я и хочу вынести на общее обозрение. Надеюсь, статья будет полезна тем, кто начинает знакомиться с Clojure на платформе .Net.

Сперва ссылки:

github.com/kemerovo-man/super-ants-clojure-clr
youtu.be/xZ9AGQ3L-EI
sourceforge.net/projects/clojureclr/files
github.com/clojure/clojure-clr/blob/master/Clojure/Clojure.Source/clojure/samples/ants.clj

Что сделано мною.
1. Графика. В оригинале программы муравей — это только черточка. У меня насекомые изображены натуральнее.
2. Новые герои. Кроме муравьев у меня реализованы тли и божьи коровки.
3. Взаимодействие героев. Растет трава, тля ест траву, производит сахар и откладывает яйца (размножается). Божьи коровки едят тлю и яйца. Муравьи обходят препятствия на пути. (Еще муравьи должны таскать тлю на траву и мешать божьим коровкам пожирать тлю, но это еще не реализовано.)
3. Поведение. Поведение муравьев усложнилось, они стали умнее, чем в оригинале. Добавлено поведение новых героев.
4. Графики. Видна динамика процессов на графиках. Рост травы, численность тли, количество сахара в муравейнике и в окружающем пространстве.
5. Примитивная лупа можно разглядывать детали. Правая кнопка мышки.
6. Мышка. При клике на клетку поля в консоль выводится информация содержащаяся в клетке. Колесиком мышки можно менять скорость движения насекомых.

Меняя параметры инициализации можно получать разные сценарии развития этой экосистемы. Чем быстрее растет трава, тем быстрее размножается тля и тем больше появляется сахара на поле. Трава не растет на сахаре, поэтому бурная жизнедеятельность тли сказывается на росте травы. Различные соотношения насекомых при запуске (сколько тли, сколько божьих коровок, сколько муравьев) определяют новую динамику.

Каждое насекомое видит только четыре клетки: ту на которой находится, и три клетки перед собой, по ним и ориентируется.
Муравьи реагируют на феромоновый след. Для них очень важно не терять муравейник, иначе они могут бесконечно бегать с едой «в зубах», не находя, куда ее нужно положить. Я добавил им несколько фич, связанных с феромонами, чтобы они могли эффективно ориентироваться, где еда, где муравейник.

Ближе в коду. Но начну издалека.
Для начала необходимо познакомиться с такими понятиями в Clojure, как atom, agent и ref. Их можно назвать менеджерами переменных. Код не напрямую обращается к значению переменной, а через посредника. Atom, agent и ref — это три типа посредника.

(def atom1 (atom 0))
(def agent1 (agent 0))
(def ref1 (ref 0))

Здесь мы определили atom1, agent1 и ref1. Начальное значение у всех равно 0.

(swap! atom1 inc)
(prn @atom1)
;->1

(send agent1 inc)
(prn @agent1)
;->1

(dosync
     (alter ref1 inc))
(prn @ref1)
;->1

Здесь мы передаем в atom1, agent1 и ref1 функцию inc которая увеличивает значение на 1 и видим, что значения везде стали равны 1.

(reset! atom1 0)
(send agent1 (fn [_] 0))
(dosync 
	(ref-set ref1 0))

Здесь мы меняем текущие значения atom1, agent1 и ref1 на 0.

Пока разница между посредниками не видна, она только синтаксическая.

Определим три функции:

(defn atom1-change []
	(prn "atom1-change")
	(swap! atom1 inc)
	(prn @atom1))	

(defn agent1-change []
	(prn "agent1-change")
	(send agent1 inc)
	(prn @agent1))

(defn ref1-change []
	(prn "ref1-change")
	(dosync
		(alter ref1 inc))
	(prn @ref1))

Вызовем их:

	
(atom1-change)
;"atom1-change"
;1

(prn @atom1)
;1

(agent1-change)
;"agent1-change"
;0

(prn @agent1)
;1

(ref1-change)
;"ref1-change"
;1

(prn @ref1)
;1

Мы видим, что в случае агента (send agent1 inc) вызывается асинхронно. Этим агент отличается от остальных.

Нам потребуется функция задержки. Определим ее, используя стандартный Sleep из .Net и увидим interop в действии.

(defn sleep [ms] 
	(. System.Threading.Thread (Sleep ms))) 

Создадим поток, который будет увеличивать значение агента каждую секунду.

(defn agent1-thread[x] 
	(sleep 1000)
	(send *agent* agent1-thread)
	(prn x)
	(inc x))

(send agent1 agent1-thread)

*agent* это текущий агент.
Тут может показаться (мне показалось), что если поменять местами sleep и send, случится что-то страшное. Ведь send вызывается рекурсивно и асинхронно, поток должен плодиться и размножаться, однако этого не происходит и можно смело писать так:

(defn agent1-thread[x] 
	(send *agent* agent1-thread)
	(sleep 1000)
	(prn x)
	(inc x))

(send agent1 agent1-thread)

Подводные грабли, однако, есть. Обратите внимание на то, что последняя сточка (inc x) возвращает значение, хранящееся в агенте, увеличенное на 1 и именно это последнее возвращаемое значение записывается в агент.

Теперь три способа положить Clojure на пол с эксепшн стэк оверфлоу:

(reset! atom1 atom1)

(dosync (ref-set ref1 ref1))

(send agent1 (fn [_] agent1))

Здесь мы записываем в качестве значений атома рефа и агента их самих. Это приводит к стэк оверфлоу.

Часто агенты используются для организации таймеров без изменения значения самих агентов, например:

(def timer (agent nil) )
(defn on-timer [_] 
	(sleep 1000)
	(send *agent* on-timer)
	(prn "tic-tac"))

(send timer on-timer)

Тут стоит заметить, что prn возвращает nil и именно этот нил записывается в значение агента.
Так как функция send возвращает сам агент, прекрасный способ выстрелить себе в ногу:

(def timer (agent nil) )
(defn on-timer [_] 
	(sleep 1000)
	(prn "tic-tac")
	(send *agent* on-timer))

(send timer on-timer)

И тут, вроде бы, даже будет все в порядке, пока не захочется посмотреть, чему равен timer, а равен он стэк оверфлоу с падением Clojure.

Следующий показательный пример:

(def agent1 (agent nil))
(def agent2 (agent nil))	
(def timer (agent nil))

(def atom1 (atom 0))
(def atom2 (atom 0))

(defn atoms-change-thread1 [_]
	(reset! atom1 1)
	(sleep (rand-int 90))
	(reset! atom2 2)
	(sleep (rand-int 90))
	(send *agent* atoms-change-thread1)
	nil)

(defn atoms-change-thread2 [_]
	(reset! atom1 3)
	(sleep (rand-int 90))
	(reset! atom2 4)
	(sleep (rand-int 90))
	(send *agent* atoms-change-thread2)
	nil)	

(defn on-timer [_]
	(prn @atom1 @atom2)
	(sleep 1000)
	(send *agent* on-timer)
	nil) 

(send agent1 atoms-change-thread1)
(send agent2 atoms-change-thread2)
(send timer on-timer)

Здесь у нас два атома и два потока изменяющих их значения.
Первый поток пишет в атомы значения 1 и 2, второй поток — значения 3 и 4.
Также есть таймер, который раз в секунду выводит значения атомов.
Вывод будет примерно такой:

3 4
1 2
1 4
3 2
1 2
3 4
1 4
3 2

Теперь, наконец о транзакциях. Перепишем предыдущий пример, но вместо атомов у нас будут рефы.

(def agent1 (agent nil))
(def agent2 (agent nil))	
(def timer (agent nil))

(def ref1 (ref 0))
(def ref2 (ref 0))

(defn refs-change-thread1 [_]
	(dosync 
		(ref-set ref1 1)
		(sleep (rand-int 90))
		(ref-set ref2 2)
		(sleep (rand-int 90)))
	(send *agent* refs-change-thread1)
	nil)

(defn refs-change-thread2 [_]
	(dosync
		(ref-set ref1 3)
		(sleep (rand-int 90))
		(ref-set ref2 4)
		(sleep (rand-int 90)))
	(send *agent* refs-change-thread2)
	nil)

(defn on-timer [_]
	(prn @ref1 @ref2)
	(sleep 1000)
	(send *agent* on-timer)
	nil) 

(send agent1 refs-change-thread1)
(send agent2 refs-change-thread2)
(send timer on-timer)

Вывод будет примерно такой
3 4
3 4
1 2
3 4
1 2
3 4
1 2
3 4
3 4
1 2

Теперь становится понятно, зачем писать dosync. Это определение границ транзакции. Изменения рефов происходит транзакционно. Этим они и отличаются от остальных.

Хотя, если заменить рефы на агенты мы тоже увидим транзакционность. Агенты также действуют в STM и границами транзакции является вся функция изменяющая значение агента.

(def agent1 (agent nil))
(def agent2 (agent nil))	
(def timer (agent nil))

(def agent3 (agent 0))
(def agent4 (agent 0))

(defn agents-change-thread1 [_]
	(send agent3 (fn [_] 1))
	(sleep (rand-int 90))
	(send agent4 (fn [_] 2))
	(sleep (rand-int 90))
	(send *agent* agents-change-thread1)
	nil)

(defn agents-change-thread2 [_]
	(send agent3 (fn [_] 3))
	(sleep (rand-int 90))
	(send agent4 (fn [_] 4))
	(sleep (rand-int 90))
	(send *agent* agents-change-thread2)
	nil)

(defn on-timer [_]
	(prn @agent3 @agent4)
	(sleep 1000)
	(send *agent* on-timer)
	nil) 

(send agent1 agents-change-thread1)
(send agent2 agents-change-thread2)
(send timer on-timer)

1 2
3 4
1 2
1 2
3 4
1 2
1 2
1 2

Наконец, после всего этого можно вернуться к муравейнику. Если сильно упростить задачу, то выглядеть она будет так:

(def v [1 1 0 0 0])
(def world (vec 
	(map 
		(fn [x] (ref x))
	v)))
(defn place [x] (world x))
(def agent1 (agent 0))
(def agent2 (agent 1))
(def agent-show-world (agent nil))

(defn agent-change [x]
	(let [old (place x)
	  new-coord (rand-int (count world))	
	  new (place new-coord)]
	(sleep (rand-int 50))
	(if (= @old 1)
	(do
		(send *agent* agent-change)
		(dosync
			(if (= @new 0)
				(do
					(ref-set old 0)
					(ref-set new 1)
					new-coord)
				x)))
	(prn "agent " *agent* "is out"))))
	
(defn show-world [_]
	(sleep 1000)
	(send *agent* show-world)
	(prn (map (fn [x] (deref x)) world)))

(send agent-show-world show-world)
(send agent1 agent-change)
(send agent2 agent-change)

Примерный вывод будет такой
(1 0 0 1 0)
(0 0 1 1 0)
(1 0 0 1 0)
(0 1 1 0 0)
(0 0 1 1 0)
(1 0 0 1 0)
(0 0 1 1 0)
(0 0 1 1 0)
(1 0 1 0 0)
(1 0 0 1 0)
(0 0 1 0 1)
(0 1 0 1 0)
(1 0 1 0 0)
(1 0 0 1 0)
(0 0 0 1 1)
(0 1 1 0 0)
(1 1 0 0 0)
(1 0 1 0 0)
(0 0 0 1 1)
(1 0 1 0 0)
(1 0 0 0 1)
(1 0 0 1 0)
(0 1 0 0 1)

Здесь мы определили вектор v в нем два первых элемента единицы, а остальные — нули. В контексте муравейника будем считать, что единицы — это муравьи, а нули — свободные клетки. Сделали вектор world — это вектор рефов, значениями которых являются элементы вектора v. У нас есть два агента значениями которых являются координаты вектора world. И есть два потока, перемещающих единицы по вектору world. Благодаря транзакционности два потока не запишут одновременно единицу в одну и ту же клетку.

Обратите внимание что в транзакцию обернута не только запись, но и чтение-проверка:

(dosync
	(if (= @new 0)
		(do
			(ref-set old 0)
			(ref-set new 1)
			new-coord)
		x)))

Если по новой, случайно сгенерируемой, координате находится 0, т.е. пустая ячейка, тогда пишем в старую ячейку 0, а в новую 1. Таким образом перемещаем муравья из старой координаты в новую.

Если обернуть в транзакцию только запись, будет не потокобезопасно.

(defn agent-change [x]
	(let [old (place x)
	  new-coord (rand-int (count v))	
	  new (place new-coord)]
	(sleep (rand-int 50))
	(if (= @old 1)
	(do
		(send *agent* agent-change)
		(if (= @new 0)
			(do
				(dosync
					(ref-set old 0)
					(ref-set new 1))
				new-coord)
			x))
	(prn "agent " *agent* "is out"))))

С таким вариантом функции вывод будет примерно такой:
(0 0 0 1 1)
(1 0 1 0 0)
(0 0 1 0 1)
(1 0 0 0 1)
«agent » #<Agent@549043: 4> «is out»
(1 0 0 0 0)
(0 0 1 0 0)
(0 0 1 0 0)
(0 1 0 0 0)
(0 0 0 1 0)
(0 0 1 0 0)

Т.е. потоки записали одновременно единицу в одно и тоже место, потом один поток угнал эту единицу в новое место, а второй не обнаружил своей единицы на том месте где оставил и свернулся. Все. Был муравей и не стало. Вернее два муравья слились воедино.

Что касается многопоточности, пожалуй, это все.

Как реализована графика:

(def ant-vert-bitmap
						'(0 0 0 0 0 0 0 0 0 2 2 0 0 0 1 1 0 0 0 0
						0 0 0 0 0 1 1 0 2 2 2 2 0 1 0 0 0 0 0 0
						0 0 0 0 1 0 0 1 2 3 3 2 1 0 0 0 0 0 0 0
						0 0 0 0 0 0 0 0 1 2 2 1 0 0 0 0 0 0 0 0
						0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0
						0 0 0 1 0 0 0 0 1 5 5 1 0 0 0 0 0 0 0 0
						0 0 0 0 1 0 0 0 1 4 4 1 0 0 0 1 0 0 0 0
						0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 0
						0 0 0 0 0 0 1 0 1 5 5 1 0 1 0 0 0 1 0 0
						0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0
						0 0 0 1 0 0 0 0 1 4 4 1 0 0 0 0 0 0 0 0
						0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0
						0 0 0 0 0 0 0 1 5 5 5 5 1 0 0 0 1 0 0 0
						0 0 0 0 0 0 0 1 5 5 5 5 1 1 1 0 0 1 0 0
						0 0 0 0 0 1 1 1 5 4 4 5 1 0 0 1 0 0 0 0
						0 0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0
						0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
						0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
						0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
						0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))

(def ant-diag-bitmap
						'(0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
						0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
						0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 2 2 0 0
						0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 2 1 0
						0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 2 2 1 0 1
						0 0 0 0 0 0 0 0 1 0 0 0 1 5 5 1 1 0 0 0
						0 0 0 0 0 0 0 0 1 0 0 0 1 4 5 1 0 0 0 0
						0 0 0 0 1 1 1 0 1 0 1 1 1 1 1 0 0 0 0 0
						0 0 0 0 0 0 1 0 1 1 1 5 1 0 0 0 0 0 0 0
						0 0 1 0 0 0 1 1 1 5 4 1 1 0 0 0 0 0 0 0
						0 1 0 1 0 1 5 5 5 1 5 1 0 1 1 0 0 0 0 0
						0 0 0 0 1 5 5 5 5 5 1 0 0 0 0 1 0 0 0 0
						0 0 0 0 1 5 4 5 5 5 1 1 1 1 0 0 0 0 0 0
						0 0 0 0 1 5 4 4 5 5 1 0 0 1 0 0 0 0 0 0
						0 0 0 0 1 5 5 5 5 1 0 0 0 0 0 0 0 0 0 0
						0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
						0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
						0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
						0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
						0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))

Это муравей. Есть функции поворота и флипа этих матриц. Дальше все это рендерится в .Net Bitmap:

(defn render-bitmap [bitmap bit color]
	(let [bit-pos (positions #{bit} bitmap)
		  rendered-bitmap (Bitmap. bitmaps-dim bitmaps-dim)]
	(doseq [b bit-pos] 
		(let [dy (quot b bitmaps-dim)
			  dx (rem b bitmaps-dim)]
		(.SetPixel rendered-bitmap dx dy color)))
	rendered-bitmap))

Все картинки кэшируются. При отрисовке кадра все берется из кэша.

Ну и что касается Windows Form и Chart то вот код:

(def current-wins (atom nil))
(def win-app (agent nil))
(def winforms-app-inited? (atom false))

(def chart (atom nil))
(def series (atom nil))

(defn get-series [series-name]
	(first (filter 
		(fn [x] 
			(if (= (. x Name) series-name) true false)) @series)))
			
(defn add-xy [series-name x y]
	(let [series (get-series series-name)]
	(when series
		(.AddXY (.Points series) x y)
		(when (> (.Count (.Points series)) 500) (.RemoveAt (.Points series) 0)))))			

(defn create-series [chart]	
	(let 
		[series1 (. chart Series)]
	(.Add series1 "herb")
	(.Add series1 "sugar")
	(.Add series1 "anthill-sugar")
	(.Add series1 "aphises")

	(doseq [s series1]
		(doto s 
			(.set_ChartType SeriesChartType/Spline)
			(.set_IsVisibleInLegend true)
			))
	(reset! series series1)	
	(doto (get-series "herb")
		(.set_Color Color/Green)
		(.set_LegendText "Herb")
		)
	(doto (get-series "sugar")
		(.set_Color Color/White)
		(.set_LegendText "Free sugar")
		)
	(doto (get-series "anthill-sugar")
		(.set_Color (Color/FromArgb 255 115 61 0))
		(.set_LegendText "Anthill sugar")
		)  
	(doto (get-series "aphises")
		(.set_Color (ControlPaint/Light Color/Green))
		(.set_LegendText "Aphises")
		)))  	

(defn chart-update[chart]
	(add-xy "anthill-sugar" @world-time (anthill-sugar-calc))
	(add-xy "herb" @world-time (herb-calc))
	(add-xy "sugar" @world-time (free-sugar-calc))
	(add-xy "aphises" @world-time (count @aphises))
	
	(let [chart-areas (. chart ChartAreas)
		  chart-area (first chart-areas)
		  axis-x (. chart-area AxisX)]
		(doto axis-x 
			(.set_Minimum (if (> @world-time 500) (- @world-time 500) 0))
			(.set_Maximum (if (> @world-time 500) @world-time 500)))))
		
(defn create-form []
	(let [form (Form.)
		  panel (Panel.)
		  animation-timer (Timer.)
		  world-timer (Timer.)
		  chart1 (Chart.)
		  series1 (. chart1 Series)]
	(doto chart1
		(.set_Name "chart1")
		(.set_Location (new Point size 0))
		(.set_Size (Size. size size))
		(.set_BackColor (ControlPaint/Light  bgcolor)))

	(.Add (. chart1 ChartAreas) "MainChartArea")
	(.Add (. chart1 Legends) "Legend")
	
	(doto (first (. chart1 ChartAreas))
		(.set_BackColor bgcolor))
	
	(doto (first (. chart1 Legends))
		(.set_BackColor bgcolor))
		
	(create-series chart1)
	(reset! chart chart1)
	(chart-update chart1)
	
	(let [chart-areas (. chart1 ChartAreas)
		  chart-area (first chart-areas)
		  axis-x (. chart-area AxisX)
		  axis-y (. chart-area AxisY)]
	(doto axis-x (.set_IsStartedFromZero true))
	(doto axis-y (.set_IsStartedFromZero true)))

	(doto panel
		(.set_Location (new Point 0 0))
		(.set_Name "panel1")
		(.set_Size (Size. size size))
		(.add_Click 
			(gen-delegate EventHandler [sender args]
				(when (= (.Button args) MouseButtons/Right)
					(swap! show-lens? (fn [x] (not x))))
				(when (= (.Button args) MouseButtons/Left)
					(let   [mouse-x (@mouse-pos 0)
							mouse-y (@mouse-pos 1)
							x (/ mouse-x scale)
							y (/ mouse-y scale)
							p (place [x y])]
					(prn [x y] @p)
					(.Focus panel)))))
		(.add_MouseMove 
			(gen-delegate MouseEventHandler [sender args]
				(reset! mouse-pos [
					(* (quot (.X args) scale) scale)
					(* (quot (.Y args) scale) scale)])))
		(.add_MouseWheel 
			(gen-delegate MouseEventHandler [sender args]
				(let [f (fn [x] 
							(let 
								[new-sleep  (+ x (* 50 (/ (.Delta args) 120)))]
							(if (> new-sleep 0) new-sleep 0)))]
				(swap! ant-sleep-ms f)
				(swap! ladybug-sleep-ms f)
				(swap! aphis-sleep-ms f)
				(prn @ant-sleep-ms)))))
				
	(doto animation-timer
		(.set_Interval animation-sleep-ms)
		(.set_Enabled true)
		(.add_Tick (gen-delegate EventHandler [sender args]
			(do 			
				(when @buf-graph 
					(.Render (@buf-graph 0) (@buf-graph 1)))
				(reset! rectangles-in-cells [])
				(reset! rendered-bitmaps [])
				(let [v (vec (for [x (range dim) y (range dim)] 
								@(place [x y])))]
				(dorun 
					(for [x (range dim) y (range dim)]
						(render-place (v (+ (* x dim) y)) x y)))
				(reset! buf-graph (render panel))
				(when @show-lens? 
					(reset! buf-graph (render-lens))))))))
					
	(doto world-timer
		(.set_Interval 5000)
		(.set_Enabled true)
		(.add_Tick (gen-delegate EventHandler [sender args]
			(swap! world-time inc)
			(chart-update chart1))))			
					
	(doto (.Controls form)
		(.Add panel)
		(.Add chart1))
	(doto form
		(.set_ClientSize (Size. (* size 2)  size))
		(.set_Text "Super Ants"))
	form))

(defn init-winforms-app []
    (when-not @winforms-app-inited?
	   (Application/EnableVisualStyles)
	   (Application/SetCompatibleTextRenderingDefault false)
       (reset! winforms-app-inited? true)))
	   
(defn start-gui [x]
    (init-winforms-app)
    (reset! current-wins (create-form))
    (Application/Run @current-wins))

Надеюсь, было не скучно.

Спасибо за внимание.

Автор: kemerovo_man

Источник

Поделиться новостью

* - обязательные к заполнению поля