заявка на победу: окончание

[swizard]

Наконец-то появилось время дооформить задачку и отослать организаторам.

Честно говоря, я уже сомневаюсь, что займу там какое-то место. С эталонным "osmosis" там какая-то путаница, он в разных режимах выдает какие-то рандомные результаты, не соответствующие условиям задания, которые я никак не могу интерпретировать.

Детальное изучение diff'ов заставляет меня верить, что я прав, а эталон нет. Но я не знаю, как там будет проводиться сравнение. Я уж не говорю о первом пункте про "краткость и читаемость решения", которое автоматически указывает, что предпочтения будут оказываться решениям на хаскеле и эрланге :)

Ну да ладно. Основные мои цели, зачем я вообще этим заморочился, были такие:

• Продемонстрировать, что common lisp не является deprecated, как утверждалось где-то в журнале
• Продемонстрировать, что решения на CL практичны: при сравнимом LOC оказываются производительнее и потребляют меньше памяти, нежели решения на других языках
• В выгодном свете акцентировать внимание на самых сильных сторонах CL: метапрограммирование и генерация кода в рантайме

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

Генерация кода

Используется мной в задаче определения принадлежности точки полигону обрезки. Я беру исходный .poly файл, генерирую по нему исходник фукнции на CL, которая определяет, попадает ли (x, y) в полигон и компилирую в нативный код. Соответственно, для проверки я пользуюсь подсчетом количества пересечений граней полигона горизонтальным лучом (вот тут есть описание). Например, вот такой код получается для файла sakhalin.poly:


(COND
((AND (> Y 42.965324) (<= Y 54.692776))
(COND
((AND (> Y 51.11711) (<= Y 54.692776))
(WHEN (<= X (+ (* Y -3.0087342) 306.6176))
(SETF CROSS (LOGNOT CROSS)))
(COND
((> Y 54.099148)
(WHEN (<= X (+ (* Y 0.029405717) 140.45332))
(SETF CROSS (LOGNOT CROSS))))
((<= Y 51.62894)
(WHEN (<= X (+ (* Y 4.129624) -58.274612))
(SETF CROSS (LOGNOT CROSS)))
(COND
((> Y 51.19278)
(WHEN (<= X (+ (* Y -3.135153) 316.7981))
(SETF CROSS (LOGNOT CROSS))))))
((AND (> Y 52.99881) (<= Y 53.746616))
(WHEN (<= X (+ (* Y -0.3500023) 160.2204))
(SETF CROSS (LOGNOT CROSS))))
((AND (> Y 52.383385) (<= Y 52.8256))
(WHEN (<= X (+ (* Y 0.32559264) 124.49829))
(SETF CROSS (LOGNOT CROSS))))
((AND (> Y 53.746616) (<= Y 54.099148))
(WHEN (<= X (+ (* Y 1.8018049) 44.56803))
(SETF CROSS (LOGNOT CROSS))))
((AND (> Y 52.14762) (<= Y 52.383385))
(WHEN (<= X (+ (* Y -0.14995793) 149.40924))
(SETF CROSS (LOGNOT CROSS))))
((AND (> Y 52.84809) (<= Y 52.99881))
(WHEN (<= X (+ (* Y 0.6042015) 109.64873))
(SETF CROSS (LOGNOT CROSS))))
((AND (> Y 52.8256) (<= Y 52.84809))
(WHEN (<= X (+ (* Y -5.259837) 419.552))
(SETF CROSS (LOGNOT CROSS)))))))
(COND
((AND (> Y 47.88031) (<= Y 52.14762))
(WHEN (<= X (+ (* Y 0.18784428) 131.79366))
(SETF CROSS (LOGNOT CROSS)))
(COND
((AND (> Y 50.30867) (<= Y 51.19278))
(WHEN (<= X (+ (- Y) 207.4937))
(SETF CROSS (LOGNOT CROSS))))
((AND (> Y 49.766396) (<= Y 50.30867))
(WHEN (<= X (+ (* Y 0.5555665) 129.23521))
(SETF CROSS (LOGNOT CROSS))))
((AND (> Y 49.719467) (<= Y 49.766396))
(WHEN (<= X (+ (* Y -3.0089417) 306.62793))
(SETF CROSS (LOGNOT CROSS)))))))
(COND
((AND (> Y 42.965324) (<= Y 49.719467))
(WHEN (<= X (+ (* Y 1.6237954) 76.29072))
(SETF CROSS (LOGNOT CROSS)))
(COND
((<= Y 43.59513)
(WHEN (<= X (+ (* Y -0.517238) 168.28091))
(SETF CROSS (LOGNOT CROSS))))
((AND (> Y 44.528984) (<= Y 45.74067))
(WHEN (<= X (+ (* Y -1.2019796) 199.16792))
(SETF CROSS (LOGNOT CROSS))))
((AND (> Y 45.795887) (<= Y 46.891037))
(WHEN (<= X (+ (* Y -0.014922306) 141.6298))
(SETF CROSS (LOGNOT CROSS))))
((AND (> Y 43.812305) (<= Y 44.528984))
(WHEN (<= X (+ (* Y 0.5151565) 122.7056))
(SETF CROSS (LOGNOT CROSS))))
((AND (> Y 47.193726) (<= Y 47.88031))
(WHEN (<= X (+ (* Y 0.86301005) 99.466515))
(SETF CROSS (LOGNOT CROSS))))
((AND (> Y 43.59513) (<= Y 43.812305))
(WHEN (<= X (+ (* Y -1.0000175) 189.08887))
(SETF CROSS (LOGNOT CROSS))))
((AND (> Y 46.98366) (<= Y 47.193726))
(WHEN (<= X (+ (* Y -3.8077252) 319.89594))
(SETF CROSS (LOGNOT CROSS))))
((AND (> Y 46.891037) (<= Y 46.98366))
(WHEN (<= X (+ (* Y 0.70128906) 108.04591))
(SETF CROSS (LOGNOT CROSS))))
((AND (> Y 45.74067) (<= Y 45.795887))
(WHEN (<= X (+ (* Y -58.71558) 2829.8784))
(SETF CROSS (LOGNOT CROSS)))))))))

Вот, например, республика адыгея (схематично):


CL-GEO> (draw-file #p"/home/swizard/devel/lisp/cl-geo/data/poly/adygeya.poly" 150 75)
; compiling (IN-PACKAGE :CL-GEO)
; compiling (DEFUN ADYGEYA-0 ...)
; compiling (DEFUN ADYGEYA-1 ...)
; compiling (DEFUN ADYGEYA-2 ...)
; compiling (DEFUN ADYGEYA ...)
------------------------------------------------------------------------------------------------------------------------------------------------------ 45.19193
----------------------------------------------------------------*********----------------------------------------------------------------------------- 45.172714
---------------------------------------------------------------***********---------------------------------------------------------------------------- 45.1535
-------------------------------------------------------------****************------------------------------------------------------------------------- 45.134285
-----------------------------------------------------------***********************-------------------------------------------------------------------- 45.11507
----------------------------------------------------------*****************************----------------**********------------------------------------- 45.095856
-------------------------------------------------------**************************************--*********************---------------------------------- 45.07664
-----------------------------------------------------****************************************************************--------------------------------- 45.057426
-------------******--------------------------------*********-***********************************************************------------------------------ 45.03821
-***-------********-----------------------------************------------**************************************************---------------------------- 45.018997
-*********************-------------------------************------------***************--**************************************------------------------ 44.999783
-***********************---------*-------******************----------***-*********--------**************************************---------------------- 44.980568
-**************************---******************************--------**-----*****-----------***************************************-------------------- 44.961353
-******-********************************************************-----*-------**------------*****************************************------------------ 44.94214
----------********************************************************-------------------------*-****************************************----------------- 44.922924
------------*******************************************************---------------------------*****************************************--------------- 44.90371
---------------******************************************************------------------------******************************************--------------- 44.884495
------------------****************************************************----------------------********************************************-------------- 44.86528
----------------------**********************************************-------------------------********************************************------------- 44.846066
-------------------------*****************************************------------------------------******************************************------------ 44.82685
--------------------------------------------------***************------------------------------********************************************----------- 44.807636
------------------------------------------------------------------------------------------------********************************************---------- 44.78842
-------------------------------------------------------------------------------------------------********************************************--------- 44.769207
--------------------------------------------------------------------------------------------------*****************************-----*********--------- 44.749992
--------------------------------------------------------------------------------------------------***************************----------******--------- 44.730778
----------------------------------------------------------------------------------------------******************************------------******-------- 44.711563
------------------------------------------------------------------------------------------**********************************------------*******------- 44.69235
-------------------------------------------------------------------------------------------*********************************------------*******------- 44.673134
------------------------------------------------------------------------------------------**********************************--------------******------ 44.65392
------------------------------------------------------------------------------------------********************************-----------------*******---- 44.634705
-------------------------------------------------------------------------------------------*****************************----------------------******-- 44.61549
-------------------------------------------------------------------------------------------****************************-----------------------*******- 44.596275
-----------------------------------------------------------------------------------------******************************------------------------*****-- 44.57706
---------------------------------------------------------------------------------------*********************************------------------------****-- 44.557846
---------------------------------------------------------------------------------------***********************************-----------------------***-- 44.53863
---------------------------------------------------------------------------------------*************************************---------------------****- 44.519417
---------------------------------------------------------------------------------------**************************************--------------------***** 44.500202
----------------------------------------------------------------------------------------**************************************-------------------***** 44.480988
---------------------------------------------------------------------------------------***************************************---------------*******-- 44.461773
-------------------------------------------------------------------------------------****************************************------------------------- 44.44256
------------------------------------------------------------------------------------*****************************************------------------------- 44.423344
-----------------------------------------------------------------------------------******************************************------------------------- 44.40413
----------------------------------------------------------------------------------*******************************************------------------------- 44.384914
---------------------------------------------------------------------------------********************************************------------------------- 44.3657
---------------------------------------------------------------------------------*********************************************------------------------ 44.346485
-----------------------------------------------------------------------------------------**************************************----------------------- 44.32727
------------------------------------------------------------------------------------------**************************************---------------------- 44.308056
-------------------------------------------------------------------------------------------*************************************---------------------- 44.28884
--------------------------------------------------------------------------------------------***********************************----------------------- 44.269627
-----------------------------------------------------------------------------------------------------************************------------------------- 44.250412
------------------------------------------------------------------------------------------------------*********************--------------------------- 44.231197
-----------------------------------------------------------------------------------------------------**********************--------------------------- 44.211983
------------------------------------------------------------------------------***-------------------***********************--------------------------- 44.19277
----------------------------------------------------------------------------*******-----------------***********************--------------------------- 44.173553
----------------------------------------------------------------------------********----------------***********************--------------------------- 44.15434
----------------------------------------------------------------------------********--------------*************************--------------------------- 44.135124
----------------------------------------------------------------------------************--------***************************--------------------------- 44.11591
------------------------------------------------------------------------------***********-------****************************-------------------------- 44.096695
-------------------------------------------------------------------------------**********------*****************************-------------------------- 44.07748
-------------------------------------------------------------------------------*********************************************-------------------------- 44.058266
------------------------------------------------------------------------------*********************************************--------------------------- 44.03905
-----------------------------------------------------------------------------***********************************************-------------------------- 44.019836
-----------------------------------------------------------------------------***************************************************---------------------- 44.00062
------------------------------------------------------------------------------***************************************************--------------------- 43.981407
------------------------------------------------------------------------------***************************************************--------------------- 43.962193
----------------------------------------------------------------------------*****************************************************--------------------- 43.942978
-----------------------------------------------------------------------------***************************************************---------------------- 43.923763
---------------------------------------------------------------------------------*******--************************************------------------------ 43.90455
--------------------------------------------------------------------------------------------*********************************------------------------- 43.885334
-----------------------------------------------------------------------------------------------******************************------------------------- 43.86612
-------------------------------------------------------------------------------------------------***************************-------------------------- 43.846905
----------------------------------------------------------------------------------------------------------******************-------------------------- 43.82769
------------------------------------------------------------------------------------------------------------***************--------------------------- 43.808475
--------------------------------------------------------------------------------------------------------------************---------------------------- 43.78926
----------------------------------------------------------------------------------------------------------------********------------------------------ 43.770046
NIL

После первой компиляции полигона результат сохраняется рядом с исходником в .fasl файле, который может быть впоследствии скормлен #'load. Собственно, это и происходит при всех последующих прогонах программы, тем самым, еще экономится время.

Метапрограммирование

Особенно мне пригодилось при реализации собственного парсера xml (я уже писал, что мне не удалось подобрать вменяемое существующее решение с приемлемой производительностью). Для этого был реализован специализированный DSL, который до примитивного коммон лиспа наикрасивейшим образом macroexpand'ится аж четыре раза!

Эволюция такого многоуровнего dsl-я выглядит так (компиляция сверху вниз):

1. ITER-XML-STREAM: язык для декларативного описания обработки xml тагов
2. ITER-PARSE-STREAM: язык для декларативного описания парсинга входного потока (поиск подстрок, восстановление цифр)
3. ITER-STREAM: язык для описания посимвольной обработки входного потока
4. ITERATE: он и в африке iterate
5. Common Lisp: примитивный, с аккуратной декларацией типов
6. Asm/машинный код: максимально нативный, без боксинга, без задействования GC (ни единой аллокации), без generic-функций.

Помимо этого, верхний iter-xml-stream еще завернут для удобства в пару макросов, упрощающих declare и устанавливающих стратегию компиляции. В итоге, конечный вариант выглядит вот так:

(defun/iter-xml perform-pass-1 ((poly-ctx poly-context) (hash-table node-idx))
"Scans SRC-OSM xml stream extracting tags, checks each node for polygon
belonging via POLY-CONTEXT, and sets index NODE-IDX in case of success"
(with (the (unsigned-byte 56) way-offset) = 0)
(xml-on-tag "node"
(attrs ("id" uint64 node-id)
("lon" float lon)
("lat" float lat))
(on-match (when (poly-check poly-context lon lat)
(setf (gethash node-id node-idx) 1))))
(xml-on-tag "way" (on-match (when (zerop way-offset)
(setf way-offset tag-offset))))
(tracing-tag-offset tag-offset)
(finally (return (1- way-offset))))
Функция perform-pass-1 читает xml из потока и проверяет каждый тег node на предмет принадлежности полигону обрезки. Результатом выполнения должен быть заполненный индекс node-idx и смещение в потоке, где встретился первый тег "way" (второй проход будет начинаться отсюда). Казалось бы, логика довольно сложная. Однако, данная конструкция макроэкспандится не менее шести раз, и в итоге имеем 510 строчек чистейшего и нативнейшего ассемблера, где все взаимодействие с sbcl заключается только в #'READ-SEQUENCE и #'SB-KERNEL:%PUTHASH!

Разумеется, DSL iter-xml-stream не является полноценным и универсальным средством для обработки xml. Он поэтапно эволюционировал до нужд моей текущей задачи, но уже умеет достаточно много. Детально я ему посвящу еще несколько постов, и даже выложу пакет в общий доступ, а пока я хочу отметить пару фактов.

Любой программист со стажем прекрасно знает две аксиомы:

1. За повышение уровня абстракции надо платить потерей производительности
2. Серебряной пули не существует

Common Lisp предлагает свое решение этих проблем: языково-ориентированное программирование. Задача разбивается на предметные области и для каждой области создается "своя пуля" -- DSL, причем в этом процессе активно поощряется композиция оных.

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

Рассмотрим на примере iter-xml-stream:

• DSL iterate используется для описания итеративных процессов. Чтение данных из потока к таким процессам вполне относится
• DSL iter-stream использует два цикла iterate: первый для read-sequence данных в буфер, и второй (вложенный) по только что считанному буферу. Пользователю предлагается абстрактное окружение, в котором для него в цикле предоставляется очередной октет из потока.
• DSL iter-parse-stream использует iter-stream и простенькие КА для фильтрации потока на предмет заданных паттернов
• И, наконец, iter-xml-stream использует iter-parse-stream, предоставляя пользователю язык для описания правил обработки xml-тагов.

Самый интересный момент, что в рамках каждого DSL доступны все предыдущие. Тоесть, например, описывая правила обработки xml через iter-xml-stream можно свободно пользоваться синтаксическими конструкциями iterate, iter-stream и iter-parse-stream (я уж не говорю о самом коммон-лиспе).

Ну, вкрадце, как-то так. Мораль примерно такова: имея язык, в котором можно с такой легкостью "и рыбку съесть, и кости продать", становится непонятно, нахрена нужны все остальные =)