Регистрация | Войти
Lisp — программируемый язык программирования
Трамплины и продолжения
Любопытно, конечно, что наибольшую популярность завоёвывают именно плохие с инженерной точки зрения технологии. Я не могу объяснить этот феномен: казалось бы, согласно эволюционной теории "более лучшие" вещи должны постепенно заменять эквивалентные по функционалу "более худшие", но этого не происходит. И даже не всегда проблема в том, что что-то сложнее, а что-то легче: обычно, в плохо продуманных технологиях сложность как раз выше, просто она "отложенная".

Давайте, например, посмотрим на такие платформы: Common Lisp/Scheme, Haskell или OCaml. А потом на такие: Java или Javascript. В чём разница? Правильно, в одних есть хвостовая рекурсия, в других нет :)

Ладно, на самом деле, большинству программистов наджави эта рекурсия нафиг не сдалась. Полагаю, что многие и не подозревают даже что это такое, и подобное неведение никак не мешает им вполне комфортно существовать на свете. Но оная проблема встаёт достаточно остро для пользователей более вменяемых языков, которые используют джаву или js в качестве бэкенд-платформы. Например, Clojure для jvm или Elm для javascript. Эти языки предполагают функциональную парадигму программирования, и отсутствие TCO при этом причиняет серьёзные неудобства.

Честно говоря, натолкнувшись на переполнение стека в Elm, я был несколько ошарашен. Ничто не предвещает беды, вокруг тепло и уютно: с одной стороны, у тебя почти хаскель, с другой тебе было обещано отсутствие рантайм-исключений (если ты не выходишь за рамки чистого elm). И тут херак, привет из js:

RangeError: Maximum call stack size exceeded

Я поначалу даже растерялся — к такому меня жизнь явно не готовила. Пришлось потратить некоторое количество времени, чтобы разобраться, как в таких случаях следует поступать: ведь никаких специальных технических средств для написания явных циклов руками в ельме нет. Он умеет оптимизировать только самые простые хвостовые вызовы, но любая чуть более сложная рекурсия сразу становится "честной". Поэтому пишу этот материал постфактум в качестве инструкции — мало ли кому ещё поможет.

Итак, давайте рассмотрим следующий синтетический пример:


isEven : Int -> Bool
isEven x =
    case abs x of
        0 -> True
        v -> isOdd <| v - 1


isOdd : Int -> Bool
isOdd x =
    case abs x of
        0 -> False
        v -> isEven <| v - 1


isSumEven : Int -> Int -> Bool
isSumEven a b =
    isEven a == isEven b


Я тут попытался смоделировать проблему: у нас есть две взаимно-рекурсивные функции (определяющие, чётное или нечётное число на входе) и одна утилитарная, которая их как-то использует (предсказывает, будет ли сумма двух чисел чётная).

Можно сразу посмотреть в репле, как они (не) работают:


> isEven 2
True : Bool
> isOdd 13
True : Bool
> isSumEven 100 1
False : Bool
> isEven 100000
RangeError: Maximum call stack size exceeded


Как их заставить работать, если платформа не поддерживает TCO? Никак, надо переписывать.

Общепринятая практика использовать в таких случаях технику, которая называется trampolining. Она широко используется, например, в Clojure. Идея там достаточно простая. Мы рефакторим функции, использующие рекурсию таким образом, чтобы:

  1. во всех местах, где производится рекурсивный вызов, вместо этого возвращалось наружу продолжение (достаточно просто обычного замыкания: thunk)
  2. на самом "верхнем" уровне выполняется обычный тупой цикл (trampoline), который последовательно вызывает отрефакторенную функцию до тех пор, пока она возвращает продолжения

Тем самым все функции перестают быть рекурсивными, и использование стека становится чётко детерминировано: из всех условных веток возвращаются либо результаты, либо замыкания (которые потом будут вызваны из трамплина).

В Elm, оказывается, есть даже микро-пакетик с трамплинами: elm-lang/trampoline. С его помощью можно переписать вышеприведённые взаимно-рекурсивные функции следующим образом:


import Trampoline exposing (Trampoline, done, jump, evaluate)


isEvenTr : Int -> Trampoline Bool
isEvenTr x =
    case abs x of
        0 -> done True
        v -> jump <| \() -> isOddTr <| v - 1


isOddTr : Int -> Trampoline Bool
isOddTr x =
    case abs x of
        0 -> done False
        v -> jump <| \() -> isEvenTr <| v - 1



В данном случае, всё получается достаточно прямолинейно: когда готов результат, возвращаем его через done, а когда нужно выполнить рекурсивный вызов, оборачиваем его в thunk и возвращаем через jump. Соответственно, в пакете trampoline лежит ещё функция evaluate, которая как раз крутит цикл, вызывая по-очереди все возвращаемые продолжения. Проверяем:


> evaluate <| isEvenTr 2
True : Bool
> evaluate <| isOddTr 13
True : Bool
> evaluate <| isOddTr 100000
False : Bool


Да, в этом варианте всё работает!

Кстати, небольшое отступление. Очевидно, что многим (включая меня) может не понравиться, как выглядит вот этот кусок кода:


jump <| \() -> isOddTr <| v - 1


Лично я его автоматически написал сначала так:


jump <| always <| isOddTr <| v - 1


За что был наказан потерянным часом на отладку. Кто может предположить, в чём кроется засада? :) Для справки: always.

Ладно, возвращаемся к примерам. Как написать трамплин-версию isSumEven? В принципе, можно как-то так:


isSumEvenTr : Int -> Int -> Trampoline Bool
isSumEvenTr a b =
    done <| (evaluate <| isEvenTr a) == (evaluate <| isEvenTr b)


Конкретно для этого синтетического примера, наверно, такой вариант особо ничем не плох. Но всё же: можно ли обойтись только одним evaluate? Очевидно, что можно, если получится каким-то образом "попасть внутрь" типа Trampoline a, чтобы достать значение a или, хотя бы, как-то его преобразовать. Но вот незадача: этот тип не является функтором или монадой, никаких соответствующих комбинаторов для него нет, да и вообще это всё страшные слова, и такой мерзости у нас в эльме не водится! Следовательно, единственный вариант — это честно интерпретировать Trampoline a через evaluate. Или нет?

На самом деле, есть способ "состыковать" несколько Trampoline-ов, чтобы выполнить их в одном цикле-эвалюаторе: опять же, CPS. Но для этого нам опять нужно отрефакторить функции, на этот раз в continuation passing style:


isEvenTrK : Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isEvenTrK x k =
    case abs x of
        0 -> k True
        v -> jump <| \() -> isOddTrK (v - 1) k


isOddTrK : Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isOddTrK x k =
    case abs x of
        0 -> k False
        v -> jump <| \() -> isEvenTrK (v - 1) k


isSumEvenTrK : Int -> Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isSumEvenTrK a b k =
    isEvenTrK a <|
        \resultA ->
            jump <| \() -> isEvenTrK b <|
                \resultB ->
                    k <| resultA == resultB



Главное изменение: функции теперь не возвращают результаты напрямую (логически, они уже ничего не должны возвращать), вместо этого они принимают дополнительные параметр: "продолжение", которому этот результат передаётся. Теперь в isEvenTrK появилась возможность состыковать две "затрамплиненные" функции внутри продолжения, при этом сохранив тип возвращаемого значения Trampoline Bool, который уже скармливается единственному evaluate:


> evaluate <| isSumEvenTrK 100000 1 done
False : Bool
> evaluate <| isSumEvenTrK 100000 100000 done
True : Bool


В принципе, этот трюк может пригодится, например, когда завёрнутым в трамплин типом является тот же Result — и надо уметь в процессе работы запускать разные ветки вычислений в зависимости от того, успешно ли отработал один из рекурсивных вызовов, или нет.

Ну, в целом, как-то так. Далее полагается, чтобы я написал какие-то выводы или подытоги, но какие тут могут быть выводы? Сложно, запутанно. Но это и есть та самая "отложенная сложность", про которую я говорил в начале поста. Был бы в вашем джаваскрипте изначально родной TCO, я бы не писал этот текст, а вместо этого сделал бы что-нибудь полезное.
Лидерборд апдейт
Сейчас 8:48. Какие-то бомжи на первом месте в лидерборде.


ICFPC-2016, меньше 12 часов до старта
В общем, осталось времени до старта совсем чуть-чуть, расчехляемся потихоньку. Ну и заодно смотрим, что нам там пишут организаторы. А пишут следующее (последние три записи):

1.upto(99){|_|puts'FizzBuzz '[o=_**4%-15,o+13]||_}
Это на руби. Выводит следующую последовательность:
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
Fizz
22
23
Fizz
Buzz
26
Fizz
28
29
FizzBuzz
31
32
Fizz
34
Buzz
Fizz
37
38
Fizz
Buzz
41
Fizz
43
44
FizzBuzz
46
47
Fizz
49
Buzz
Fizz
52
53
Fizz
Buzz
56
Fizz
58
59
FizzBuzz
61
62
Fizz
64
Buzz
Fizz
67
68
Fizz
Buzz
71
Fizz
73
74
FizzBuzz
76
77
Fizz
79
Buzz
Fizz
82
83
Fizz
Buzz
86
Fizz
88
89
FizzBuzz
91
92
Fizz
94
Buzz
Fizz
97
98
Fizz
=> 1
 Смысл в том, что выводятся числа от 1 до 99 и там, где число делится на 3, пишут Fizz, где на 5, пишут Buzz, а где и на 3, и на 5 - FizzBuzz. В общем, такая шляпа широко используется в качестве тестового задания и даже приводят почему именно оно так хорошо раскрывает потенциал программиста. Правда, я не понял. :) Точнее, задача позволит отсеить откровенного непрограммиста.

Так же это детская игра считалочка, когда детки садятся в круг и считают. По тем же правилам, что выше описано. Кто ошибся, вылетает. Ну и в конце останется только один. :)

Далее что мы имеем? Имеем некий запрос - Закидывание забутонами. Забутон это такой стул без ног. Которым кидают в сумоиста, который по рангу сильнее, но проиграл. Такие вот японские забавы. У моря живут, помидоров и яиц дефицит.

И третий пост - "Check or Fold?" Термины check и fold относятся к покеру. Check - пропуск хода, fold - сброс карт. 

Итого в конце останется только один! Победитель. Вероятно, всё будет в форме игры. То есть решения будут соревноваться друг с другом. Без рейтинговой таблицы. Возможно, что-то будет похожим на карты. И проигравшего закидают тухлыми яйцами. Простите, забутонами. В общем, сидим, ждём.

И да, самый главый момент. В этом году наша команда выступает на хаскеле. Я его всю неделю учил. Не скажу, что понравился, но и не скажу, что прям сильно не понравился. Ясно, что в ICFPC и иже с  ним далеко не язык определяет победу. Так что начало в 03 утра по Мск. Ждём. :)
ICFPC-2016, вот он и пришёл
Причём пришёл совершенно нежданно и негаданно. Всё смотрел, ждал и ждал, а тут и бац, в скайпе вылавливают и сообщают. В общем, страница контеста. А вот ещё и их twitter. В общем, пока непонятно и никаких подсказок не увидел. Буду мониторить. А, да, начало то 5 августа в 03:00 по MSK. Это 00:00 по UTC. В общем, вот так вот.
Вероятностные алгоритмы.

Введение.

Традиционным образом (то есть, в самые последние сутки дедлайна) я поучаствовал в конкурсе, организованном ребятами из конторы Hola.

Задание было придумано очень крутое. "Очень крутое" -- это, в моём понимании, такое задание, которое:

  1. Имеет практическую ценность.
  2. Не подразумевает одного единственного верного решения, до которого просто нужно додуматься в процессе конкурса.

Полностью условие можно почитать на офсайте, а вкратце оно звучит так:

  • Дан словарь из ~660k записей. Ориентировочно, это английские слова.
  • Надо написать функцию "test(word)", которая возвращает true, если заданное слово входит в словарь, и false, если нет.
  • Суммарный объём программы и файла с данными, которым она может пользоваться, не должен превышать 65536 байт.
  • Побеждает решение, которое даст максимальный процент правильных ответов на большом количестве тестов.

Чтобы было повеселее, в тестах используется специальный генератор слов, которые визуально (и грамматически) очень похожи на нормальные английские, но при этом в словаре их нет, например: "goldrunk". И, напротив, в заданном словаре есть весьма странные записи, в которых распознать английский язык очень сложно, например, "qwertys" или "rRNA".

Согласно комментариям участников в соответствующем треде на хабрахабре, основные идеи (успешных) решений были следующие:

  • Максимальное обрезание словаря, выделение значащих префиксов/суффиксов/нграмм, и последующее запихивание всего этого в фильтр Блума.
  • Машинное обучение. В основном, это разновидности деревьев решений.
  • Решения, воссоздающие словарь из тестовых данных в рантайме.

Я решил пойти немного другим путём, и сделал решение, основанное на использовании вероятностного алгоритма отличного от блумфильтра. Возможно, в конкретно данной ситуации оно и не показало самого оптимального результата, но, вообще, в целом, вероятностные алгоритмы -- это невероятно удобный инструмент, если хорошо его освоить. Я как раз давно хотел накатать про них какой-нибудь обзорный пост, но не было подходящего контекста. Поэтому, пользуясь случаем, делаю щас.

Немного теории.

В статье на русскоязычной википедии говорится, что: "Вероятностный алгоритм — алгоритм, предусматривающий обращение на определённых этапах своей работы к генератору случайных чисел с целью получения экономии во времени работы за счёт замены абсолютной достоверности результата достоверностью с некоторой вероятностью". Это не совсем так -- принципиально, к ГСЧ в вероятностных алгоритмах обращаться необязательно. В англоязычной версии этой статьи есть более корректное определение: "uniformly random bits". Опять же, экономия может достигаться не только во времени работы, а по памяти, например.

Неплохой демонстрацией может служить широко известный фильтр Блума, который является "вероятностной структурой данных". Источником "случайных" значений с дискретно-равномерным распределением здесь служит хеш-функция, а выигрыш получается в более экономном использовании памяти. Взамен мы получаем, правда, неуверенность в ответе: вместо да и нет мы имеем вероятно, да и точно нет. Эта неуверенность обусловлена вероятностью возникновения коллизии, но эту вероятность можно достаточно точно подобрать, чтобы применение блумфильтра было обосновано для конкретной задачи.

Соответственно, возможность такого рода компромисса в постановке задачи (значительный выигрыш по ресурсам взамен некоторой допустимой недостоверности ответа) может быть хорошим признаком того, что в решении имеет смысл использовать вероятностный алгоритм. Например, это конкурс про упаковку огромного словаря в 64Kb :)

Самое главное, что здесь нужно запомнить, это фразу: дискретно-равномерное распределение. "Равномерное распределение" на практике должно означать следующее: если случайная величина (ГСЧ, хэш-функция, значение сигнала) генерирует нам какое-то значение из интервала R, нужно, чтобы вероятность получения каждого значения из R была 1/R (или, хотя бы, очень близко к этому). При этом количество таких значений должно быть конечно (дискретно). Визуально, это выглядит следующим образом: допустим, мы взяли поле 10x10 и ткнули в рандомную точку. Получилось, например, как-то так:

А если мы воткнули их несколько тыщ, то должно получиться относительно равномерное покрытие, что-то типа такого:

Соблюдение условия дискретно-равномерного распределения даёт нам возможность достаточно точно оценивать вероятности выпадения конкретных значений, которые могут нас интересовать в рамках моделирования наших алгоритмов. Без этой возможности мы теряем предсказуемость, что вырождает алгоритм в рандомный.

Так что перед реализацией вероятностного алгоритма надо обязательно проверять, что источник случайности в нашей задаче ведёт себя согласно дискретно-равномерному распределению. В большинстве случаев, достаточно просто взглянуть на график: например, в отличие от предыдущей картинки, вот эти значения явно не выглядят равномерно распределёнными:

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

Немного практики.

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

  • Locality-sensitive hashing: подбирает для множества элементов хэш-функцию таким образом, что "схожие" элементы попадают в одну корзину (хеши дают коллизию ожидаемым образом). Таким образом достигается существенное уменьшение размерности данных, и используется, например, в задачах кластеризации.
  • MinHash: ускорение расчёта коэффициента Жаккара для вычисления степени схожести двух множеств. Широко используется, например, для задач выявления нечётких дубликатов среди большого количества документов.
  • Семплирование потока данных. В отличие от простой выборки каждого N-ого элемента из потока, хешируют некоторый составной ключ (например, "пользователь"/"запрос"/"таймстамп"), после чего берут N корзин, и отбрасывают все результаты, не попавшие в одну из них. Это позволяет семплировать поток по сложным условиям, избегая дорогостоящей группировки.
  • Flajolet–Martin algorithm, и его развитие в виде HyperLogLog. Алгоритмы используют достаточно изящный хак для быстрой аппроксимации количества уникальных элементов в заданном множестве. Я реально советую ознакомится с описанием, это, действительно, хитрый трюк :)

Конкурсная задача.

Вернёмся к задаче про словарь. Итак, уже в условии однозначно написано про компромисс "допустимая недостоверность в обмен на ограниченные ресурсы". Следовательно, задачу можно пробовать решать вероятностным алгоритмом.

Самый простой вероятностный алгоритм, который можно придумать, это подбрасывание монетки:

function test(word) {
    return Math.random() < 0.5;
}

Несложно догадаться, что он совершенно бесплатно даёт нам 50% правильных ответов, при этом даже не пользуясь своим аргументом :) Соответственно, это значение будет базисом, с которым можно сравнивать результативность других алгоритмов.

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

Но, если понимать как работают вероятностные алгоритмы в принципе, можно попробовать придумать что-нибудь чуть более оригинальное. Я позаимствовал некоторые идеи из MinHash, и получилось вот что.

В качестве источника случайных значений я взял множество рандомных хеш-функций, как это сделано в minhash. Для этого я выбрал fnv (просто потому, что она мне нравится), которому я на вход подаю сначала случайное число, а потом сам аргумент.
Соответственно, набор таких случайных чисел (seeds) будет однозначно определять множество хеш-функций, которое будет использовано в задаче.

Применив K таких случайных хеш-функций к одному и тому же аргументу (например, слову из словаря) мы получим K результатов, которые будут, опять же, случайно распределены по всему диапазону значений fnv. Я взял 32-х битную версию, соответственно, результаты хеширования будут в диапазоне 0 - 0xffffffff. Дальше надо как-то убедиться, что эти результаты имеют равномерное распределение. Этот факт явно каким-то образом должен доказываться, но я, к сожалению, не математик, поэтому тупо нарисовал график и посмотрел на него глазами. Выглядит как равномерное :) Это свойство в данном случае мне важно для того, чтобы можно было оценить вероятность того, что случайная хэш-функция даст конкретное значение. При равномерном распределении эта вероятность будет 1/R, где R = 232.

Дальше сделаем вот что: возьмём одну такую случайную хеш-функцию H, и прогоним через неё все N слов из словаря. Получим N чисел (хешей слов), которые как-то случайным образом будут раскиданы в интервале от 0 до 232 - 1. Теперь нам надо найти какое-то такое утверждение P, которое бы:

  1. Выполнялось бы для всех полученных чисел.
  2. Не выполнялось для как можно большего количества остальных чисел из [0, 232).

Идея понятна: алгоритм получает слово, считает от него хеш с помощью хеш функции H, проверяет результат на условие P, и, если оно ложно, то это слово точно не из словаря. Если условие истинно, то слово, с какой-то вероятностью, может быть в словаре. С какой? Это зависит от природы утверждения P. Далее нам достаточно провести несколько проб (повторить алгоритм несколько раз для различных хеш-функций), с каждым разом увеличивая вероятность срабатывания P, чтобы достичь удовлетворяющей нас достоверности ответов.

Допустим, к примеру, сложилось такая ситуация, что все хеши слов из словаря оказались чётными. Тогда все нечётные значения из интервала от 0 до 232 означали бы true negative. Вероятность этой ситуации (хеш проверяемого слова оказался нечётным) была бы почти 0.5 -- это очень крутой результат для одной только пробы. Ведь тогда нам для достоверности ответа "слова точно нет в словаре" в 99% достаточно log0.50.01 = ~7 проб, то есть, всего семь рандомных хеш-функций.

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

Конкретно под наш словарь можно попробовать делить всё множество значений хеш-функций не на две корзины (чётные и нечётные числа), а на большее количество: M > 2. Тогда нашей задачей будет подобрать для каждой используемой хеш-функции такое (в идеале, минимальное) количество корзин, чтобы при хешировании всех слов из словаря одна из корзин оказалась пустой.

Если значения хеш-функций имеют равномерное распределение (а они имеют в нашем случае), вероятность попадания хеша в одну из корзин будет равняться 1/M. Каким же должен быть M, чтобы, раскидав по этому такому количеству корзин 660 тысяч хешей, у нас бы осталась одна пустая корзина? Это как-то явно подсчитывается при помощи математики, но (если вы, подобно мне, ничерта не помите из тервера) можно немного схалтурить, и получить нужные цифры при помощи несложного программирования.

Проведём эксперимент: сгенерируем нужное количество 32-х битных случайных чисел, по одному на слово из словаря -- как будто, это результаты хеширования. Программный ГСЧ должен давать равномерное распределение, и хеш-функция тоже даёт равномерное распределение, так что это относительно равноценная замена. Далее тупо брутфорсом попробуем подобрать минимальное количество корзин так, чтобы в одну из них ни одно рандомное число не попало. Вот как это примерно может выглядеть на Common Lisp:

(defun get-minimum-buckets-count (words-count)
  (iter
    ;; generate pseudo hashes
    (with pseudo-hashes =
              (iter (repeat words-count)
                    (collect (random (ash 1 32)) result-type simple-vector)))
    (for buckets-count from 2)
    ;; make buckets with hit counters
    (for buckets-hits =
         (make-array buckets-count
                     :element-type 'fixnum
                     :initial-element 0))
    ;; collect hits
    (iter (for i from 0)
          (for hash in-sequence pseudo-hashes)
          (for bucket = (mod hash buckets-count))
          (incf (elt buckets-hits bucket)))
    ;; check whether an empty bucket exists
    (for empty-bucket = (position 0 buckets-hits))
    (when empty-bucket
      (return-from get-minimum-buckets-count
        (values buckets-count empty-bucket)))))        

Небольшое отступление: даже если вы уверено считаете считаете такие вещи формулами, я, в принципе, рекомендую не лениться, и всё равно проверять свои гипотезы с помощью подобного рода кода. Пишутся такие микро-программки три минуты, но позволяют достаточно точно смоделировать рассматриваемую задачу, и потенциально выявить некоторые моменты, которые легко упустить при рассуждениях в уме.

Запустив эту функцию для 660000 слов, мы (через некоторое время) получим результат для M порядка ~33000. Разумеется, при каждом запуске он будет разный (так как псевдо-хеши генерируются каждый раз случайным образом), но это будут всегда приблизительно одинаковые значения с небольшим разбросом. На практике это означает, что мы можем получить с одной пробы вероятность 0.00003, что слово не входит в заданный словарь: для этого достаточно проверить, что хеш слова попал в пустую корзину. На первый взгляд совсем мизерный шанс, но давайте прикинем, что с этого можно получить.

Итак, мы можем взять одну рандомную хеш функцию H0, словарь, и найти для них два числа: M0 (минимальное количество корзин, раскидывая хеши по которым образуется одна пустая), и B0 (номер пустой корзины). Эти два числа описывают пробу P0, которая даёт шанс в 0.003%, что проверяемое слово точно не принадлежит словарю. Если же мы посчитаем таким же образом P1 для другой функции H1, мы сможем провести две независимые пробы, увеличив вероятность true negative до 0.00006 (вероятность не попасть в пустую корзину для одной пробы равняется 1.0 - 0.00003 = 0.99997, а для двух независимых проб вероятности умножаются). Аналогично, десять подобных проб дадут уже вероятность в 0.03%, сто в 0.3%, а десять тысяч, например, целых 26.1%. Продолжая этот ряд, можно подобрать число 153000 -- именно столько проб нужно выполнить, чтобы с вероятностью 99% определить true negative.

Одна проба однозначно задаётся двумя числами M и B, соответственно, для 150-ти тысяч проб нужно сохранить 300 тысяч чисел. Это явно больше того, что можно запихать в заданные задачей лимиты. Нетрудно прикинуть, что, если мы аллоцируем, ориентировочно 14 бит для M и 15 бит для B, в 64 Kb можно вместить всего порядка 18000 проб. А ведь там ещё должно остаться какое-то место для сценария на js! Соответственно, чуть более реалистичная цифра в 17000 проб даст вероятность определения true negative в ~40%.

Что это означает на практике? Это означает следующие вещи:

  • Если на вход функции test было подано слово из словаря, все пробы будут успешными (хеши не попадут в пустые корзины), и будет возвращена истина. Это true positive.
  • Если на вход функции test было подано слово не из словаря, то:
    1. с вероятностью 40% одна из проб даст неуспех (один из хешей попадёт в пустую корзину), и будет возвращена ложь. Это true negative.
    2. с вероятностью 60% все пробы, всё же, дадут успех, и будет возвращена истина. Это false positive.
  • Ситуация false negative в данной конфигурации невозможна, потому что мы, формируя множество проб, специально так подбирали числа M, чтобы для слов из словаря обязательно оставалась пустая корзина.

Итоговый процент верных ответов зависит от характера тестовых данных: в худшем случае он будет стремиться к 40% (если на вход подаются только слова не из словаря), в лучшем -- к 100% (если на входе только слова из словаря), а в случае половина тех, и половина других, это должно быть значение порядка 70%.

Эту цифру можно чуть-чуть улучшить, параллельно значительно упростив формат сериализованной пробы (что тоже немаловажно, ведь размер js-скрипта тоже имеет значение). Можно подбирать M специальным образом, чтобы пустая корзина оказывалась всегда, например, в нулевой позиции (B == 0, или H % M == 0). В этом случае для записи пробы нам достаточно только одного числа M. Эксперименты показывают, что это получаются значения из диапазона примерно 38000 - 91000: это означает, что соответствующие вероятности для проб будут меньше, но зато для их упаковки теперь достаточно 16 бит, следовательно количество проб можно увеличить до ~32000, и, главное, сильно упростить код для их упаковки/распаковки.

Конечно, полученная цифра в 70% верных ответов выглядит не очень впечатляюще. Но следует отметить две вещи про это решение:

  1. Удивительная простота алгоритма в целом, и элементарная масштабируемость: для достижения нужной точности нужно просто последовательно увеличивать количество проб.
  2. Это абсолютно "чистый" и "честный" результат: на нетронутых оригинальных входных данных, когда словарь взят полностью как есть. Всегда можно приложить некоторые усилия к препроцессингу: порезать слова, оканчивающиеся на "'s", разделить на префиксы/суффиксы, и т.п. Ребята в комментариях к задаче на хабрахабре писали, что они относительно безболезненно уменьшали словарь до 280000 записей. А 280 тысяч хешей в нашем алгоритме уже означают M ~ 13000, что, в свою очередь, даёт вероятность одной пробы 0.0076% и порядка 18000 проб в 64 Kb, выдающих, суммарно, почти 75% true negative! А это уже больше 87% верных ответов для случая 50/50 словарных и не словарных слов.

В целом, надеюсь, мне удалось более-менее доступно рассказать про вероятностные алгоритмы, и подать идею, как их можно применять на примере решения этой конкурсной задачи. Из минусов конкретно моего подхода следует отметить серьёзную ресурсоёмкость этапа компиляции, когда происходит подбор брутфорсом значений M для проб. Собственно, из-за этой ресурсоёмкости мне так и не удалось уложиться в дедлайн конкурса, потому что банально не нашёл вовремя достаточно мощной машины с десятком-другим свободных ядер :)

Полностью моё решение, вместе с расчитанными данными, можно взять в этом репо: сами хеши я породил из js (директория generator), а компилятор проб из них сделал на Rust (директория compiler).

Геймификация скучных процессов
13 апреля я опубликовал пост с текстом интересной, как мне тогда казалось, вакансии, и он провисел неделю. Много ли за эту неделю заинтересовалось ей людей? Нуль!
19 апреля я предложил развлекательную тестовую задачку для потенциальных кандидатов и им сочувствующих, и внезапно за одну такую же неделю мне наприсылали какие-то полчища резюме, что я даже немного впал в ступор :) Честно говоря, начал даже понимать профессиональных эйчаров, это не такая уж и простая работа, оказывается.

Так что, коллеги, кому нужны сотрудники (например), можете перенимать лайфхак, дарю бесплатно и без регистрации.
Тяжести разработки под Android и HTML5
Наконец-то опубликовали нашу простенькую игру Пузыри в гугл плей - (официальный пресс-релиз). Немножко под катом - игра основана на технологии HTML5, а в Javascript компилируется Clojurescript. Причём, использование ClojureScript открывает широкие возможности по написанию кода и отлаживанию его. Кстати, всё это работает и в браузере. В целом, в Android используется тот же браузер, но есть нюансы. Первый - этот браузер (системный WebView) везде разный и на что-то положиться особо нельзя. Да и более или менее приличный идёт только начиная с Android 5.0. Чтобы выйти из этой ситуации, в приложении тащим Chromium, который весит уже поболее. Хотя, в наше время это не так критично, но всё же. С другой стороны, я посмотрел, все так делают. Да и к этому нужно было прийти. Есть проекты типа cordova, которые бы позволили опубликовать это легко и удобно, но и там свои нюансы. Например с фуллскрином и сплешскрином. Из нормальных - coconjs, но он весь такой из себя облачный, что вносит свои неудобства. Ну и главный препон - это технологическое развитие. Я имею в виду всякие WebGL, с которыми всё быстре и которое нормально будет работоать с 5.0 Android. Хотя, терпимо работает и на 4.4. В общем, опубликовали, в итоге. :)


Задачка для интересу
Чёто вакансия вызвала интерес у удивительно малого количества народу, я даже затрудняюсь объяснить этот феномен :) Все так недолюбливают Эрланг? Но у меня же ещё Elm и Rust, и вообще, потенциально определённая свобода в этом плане. Пишите, когда ещё вам предложат попрограммировать с пользой на чём-то неунылом за деньги :)

Для подогрева интереса к вакансии выкладываю тестовую задачку для потенциальных кандидатов. А то чё я её зря что ли придумывал.
UPD 2016-04-20: добавил "sample_9".
UPD 2016-04-21: пофиксил рефенсные тайминги.

Итак, задачка из трёх частей, в порядке увеличения сложности. Делать надо на эрланге, если умеете эрланг, или на чём угодно, если не умеете. Ориентировочные критерии оценки такие:
  • Если человек сделал первую часть, то хорошо: с ним уже есть о чём говорить.
  • Если получилась вторая — очень хорошо.
  • Если третья — совсем круто!

Общее условие

Дана программа в виде упрощённого S-expression (что это?), например:

sample_1() -> <<"(+ (* 4 4) (* 2 (- 7 5)) 1)">>.

где первый элемент каждого списка — это операция (всего их три вида):
  1. сложение: атом "+"
  2. вычитание: атом "-"
  3. умножение: атом "*"
Все остальные возможные атомы — это целые числа.
Ещё примеры:

sample_2() -> <<"10">>.
sample_3() -> <<"(* 10 (- 0 1))">>.
sample_4() -> <<"(- (+ 10 10) -5 0)">>.
sample_5() -> <<"(+ (- (* (+ (- (* 1))))))">>.
sample_6() -> <<"(* 2 (+ (- 10 9) (- 3 (* 2 1))) (+ (- 10 9) (- 3 (* 2 1))))">>.
sample_7() -> <<"(+ (* 2 1) (+ 8 8) (- (+ 4 3 2 1) (* 3 3) (* 2 2)) (* 5 7))">>.
sample_8() -> <<"(- (+ (+ 3 3) (- 3 3) (+ 3 3) (- 3 3)) (* 2 2))">>.
sample_9() -> <<"(+ (- 6 1) (+ 0 1 1) (- 7 2) (* 3 4 5) (- 3 1) (+ 2) (- 0 10))">>.

Задача 1

Реализуйте функцию-интерпретатор "interpret/1" и вычислите результаты вышеприведённых программ.

Например:
interpret(sample_1()). --> 21
interpret(sample_2()). --> 10
interpret(sample_3()). --> -10
interpret(sample_4()). --> 25
interpret(sample_5()). --> 1
interpret(sample_6()). --> 8
interpret(sample_7()). --> 50
interpret(sample_8()). --> 8
interpret(sample_9()). --> 66

Задача 2

Представим, что все операции в программе имеют константную задержку, которая не зависит от процессора. Например, это некоторого рода длительная сетевая активность.
Итого, реализация каждой из операции теперь должна содержать вызов "timer:sleep(X)":
  • X = 2000 ms для сложения "+"
  • X = 3000 ms для вычитания "-"
  • X = 10000 для умножения "*"

Реализуйте функцию-интерпретатор "interpret_network/1", которая вычисляет результат заданной программы с минимально возможной задержкой.

Например:
interpret_network(sample_1()). --> 21 (delay 15 s)
interpret_network(sample_2()). --> 10 (delay 0 s)
interpret_network(sample_3()). --> -10 (delay 13 s)
interpret_network(sample_4()). --> 25 (delay 5 s)
interpret_network(sample_5()). --> 1 (delay 30 s)
interpret_network(sample_6()). --> 8 (delay 25 s)
interpret_network(sample_7()). --> 50 (delay 15 s)
interpret_network(sample_8()). --> 8 (delay 13 s)
interpret_network(sample_9()). --> 66 (delay 12 s)

Задача 3

Представим, что все операции в программе имеют константную задержку, которая зависит от процессора. Например, это некоторого рода тяжелые вычисления, выедающие 100% ядра процессора.
Наша машина оборудована N физическими ядрами.
Итого, реализация каждой из операции теперь должна содержать вызов "timer:sleep(X)", при этом максимальное количество "одновременно выполняющихся" операций должно быть меньше или равно N:
  • X = 2000 ms для сложения "+"
  • X = 3000 ms для вычитания "-"
  • X = 10000 для умножения "*"

Реализуйте функцию-интерпретатор "interpret_cpu/2", которая, используя процессор максимально оптимальным образом, вычисляет результат заданной программы с минимально возможной задержкой.

Например:
interpret_cpu(sample_1(), 2). --> 21 (delay 15 s)
interpret_cpu(sample_2(), 2). --> 10 (delay 0 s)
interpret_cpu(sample_3(), 2). --> -10 (delay 13 s)
interpret_cpu(sample_4(), 2). --> 25 (delay 5 s)
interpret_cpu(sample_5(), 2). --> 1 (delay 30 s)
interpret_cpu(sample_6(), 2). --> 8 (delay 28 s)
interpret_cpu(sample_6(), 3). --> 8 (delay 25 s)
interpret_cpu(sample_7(), 2). --> 50 (delay 26 s)
interpret_cpu(sample_7(), 3). --> 50 (delay 22 s)
interpret_cpu(sample_7(), 4). --> 50 (delay 15 s)
interpret_cpu(sample_8(), 2). --> 8 (delay 15 s)
interpret_cpu(sample_8(), 3). --> 8 (delay 13 s)
interpret_cpu(sample_9(), 2). --> 66 (delay 15 s)


Приглашаю всех желающих порешать, код выкладывайте на какой-нибудь gist и давайте ссылку в комменты. Свой вариант я выложу ближе к концу недели.
Reagent - вся модность ReactJS на ClojureScript
Как описывают создатели ReactJS, пользовательский интерфейс становится всё сложнее и сложнее, и тем он сложнее, чем он комплекснее. А интерфейсы усложняются, пытаются в браузере сделать всё. В целом, может, это и неплохо, но потребность в чём-то просто есть.Вообще, про реактивное программирование говорили ещё давно, но вот сейчас оно пошло в широкие массы.

ClojureScript тоже решил не оставаться в стороне и какие-то ребята запили обёртку под это дело. В целом, там же Getting Started и ещё есть куча различных туториалов, где всё подробно расписано. Суть сводится к тому, что есть некоторое состояние приложения (или несколько их), которое инкапсулируется в реактивном атоме (reagent.core/atom), и есть компоненты, которые суть есть кусок DOM, изменяющийся в зависимости от состояния. Собственно, это автоматическое изменение и есть работа ReactJS. Звучит просто? Но, в целом, так оно и есть. Рассмотрим чуточку подробнее на примере игры Memory Game, исходники которого можно глянуть тут.

(def game (r/atom {}))
Который на старте игры инициализируется  следующим:
(-> game'
(assoc-in [:level] level)
(assoc-in [:state-changed] true)
(assoc-in [:w] w)
(assoc-in [:h] h)
(assoc-in [:can-open] true)
(assoc-in [:board] board)
(assoc-in [:opened] [])
(assoc-in [:opened-count] 0)
(assoc-in [:score] 0)
(assoc-in [:state] :playing))
Собственно, это всё, что хранится в состоянии игры. Ну, а сама инициализация рендеринга:

(r/render-component [game-component] (.getElementById js/document "app"))
Далее, сам компонент game-component является обычной функцией ClojureScript и собирает в себя остальные компоненты:

(defn game-component []
(let [cur-game @game]
[:div.container.container-table
[:div.row
[:div.col-md-3.col-md-offset-2
[:div "Restart with level:"]
[:button.btn.btn-xs.btn-default
{:type "button"
:on-click #(start :easy)}
"Easy"]
[:button.btn.btn-xs.btn-default
{:type "button"
:on-click #(start :normal)}
"Normal"]
[:button.btn.btn-xs.btn-default
{:type "button"
:on-click #(start :hard)}
"Hard"]
[score-component (:score cur-game)]
[game-state-component (:state cur-game) (:score cur-game)]
[:p "Rules: " "Open two matched cards and they will stay opened. "
"Otherwise it will be closed, but you memorize it's locations."]
[:p "Author: " [:a {:href "https://bitbucket.org/turtle_bazon/"} "Azamat S. Kalimoulline"]]
[:p [:a {:href "https://bitbucket.org/turtle_bazon/cljs-games/src/"} "sources"]]]
[board-component]]]))
При этом тут используется расширенный синтаксис квадратных скобочек, который, помимо прочего, означает, что тут необходимо вызвать функцию компонента. При этом не просто вызывать, а как-то что-то сделать и пометить там у себя, чтобы эта функция вызывалась только при изменении той ветки стейта, на основе которой он рендерится. Для этого функция должна принимать аругменты, которые как раз будут веткой (-ами) состояния.

Отдельное внимание стоит уделить компоненту board-component, который рендерит доску NxM размера. По сути, доска состоит из строк, а строки состоят из ячеек. Так вот, получается, что внутри board-component есть повторяющиеся row-component, внутри которых повторяющиеся card-component. Чтобы ReactJS смог разобраться с этим, чтобы не перерендеривать всю строку целиком, ему нужно помочь, задав некоторый идентификатор с помощью "^{:key id}":

(defn row-component [row]
[:div.board-row
(for [[id card] row]
^{:key id} [card-component id card])])

(defn board-component []
(let [cur-game @game
w (:w cur-game)
h (:h cur-game)
cards-array (partition
w
(map (fn [id card]
[id card])
(for [row (range 0 h)
col (range 0 w)]
(+ (* w row) col))
(:board cur-game)))]
[:div.board.col-md-5
(for [[row row-index] (map vector cards-array (range 0 h))]
^{:key (str "r" row-index)}
[row-component row])]))
Ну а вообще, получается вполне симпатично, весь пользовательский интерфейс отрисовывается на основе состояние и изменением состояния контролируется пользовательский интерфейс. Всё чисто и понятно, если нас не подведут Reagent и ReactJS. То есть там происходит какая-то их магия, но пусть.

Итого - очень даже интересная технология, которая позволяет избавиться от жёсткого связывания модели и логики отображения. Из минусов можно отметить, что всё делается в hiccup стиле, что вынуждает верстальщика учить Clojure или, наоборот, программиста учить вёрстку. Что, по моему личному мнению, не очень хорошо. Но как раз для решения таких проблем существует проект kio, который позволяет выделить верстальщика отдельно и радоваться жизни.

Ну а подводя полный итог можно сказать, что уж если мы решили делать интерфейс в вебе, то нам, скорее всего, понадобится использовать что-то подобное, в противном случае он рискует значительно быстрее превратиться в нагромождение непонятной лапши.


ClojureScript и Phaser.io
Недавно я писал, что так и не смог подружить ClojureScript и Phaser, и что там возникала ошибка, чего не было в Parenscript. Тогда времени было мало, сейчас же решили с virvar'ом основательно разобраться. Итого, проблему на github я закрыл. Причина же была проста. В первом примере я вообще забыл *platforms* включить физическое тело, из-за чего дальнейшие операции с ним были недоступны, а во втором варианте при использовании *platforms* не был произведён deref во время операции включения физического тела. Итого два подхода вывалились с одной ошибкой, что не позволило использовать ClojureScript на LispJam. Грустно, но се ля ви. Итого реализовал туториал на ClojureScript с использованием библиотеки phzr. Итоговые изыскания - тут.
Коварные зомби съели мою корову! или история одного Lisp Game Jam
Кто-то режет салат, кто-то его ест, все поздравляют друг друга с новым годом, а мы упоролись. А упоролись такой забавной штукой как Lisp Game Jam 2016. Чтой та я решил? Да просто как-то ещё в конце декабря прошлого года в наш уютный и ламповый чатик товарищ c1tr00z запостил ссылку на предстоящий джем. Что такое джем я тогда не знал, да и сейчас не особо понимаю, но смысл описывался в том, что нужно создать игру на каком-нибудь диалекте лиспа за 7 дней. Позже дедлайн продлили ещё на три дня, но это всё вписывалось на предстоящие каникулы. В общем, подбил я c1tr00z'а, а ещё и virvar'а и понеслась.

Далее идёт портянка для любителей читать, для остальных предлагаю ознакомиться с официальным пресс-релизом группы, где кратенько об этом же, или играть онлайн, либо же посмотреть исходный код.

Phaser

Таки сначала предстояло определиться с тем, что же использовать? Можно было использовать тру CL и cl-sdl в нём, можно было заюзать какие-нибудь биндинги к Unity3d или напилить их, но всё это было не то. Хотелось простоты дистрибутинга, а это нам давал только web. А web это яваскрипт, значит, нам нужен был яваскрипт движок. Не помню что и как искал, но нашёлся turbulenz. Первая проблема возникла после того, как я решил посмотреть что он умеет и что на нём сделано, нашёл игру Monster Force... В общем, через два дня изучения возможностей движка на примере данной игры :), скачал SDK, офигел и закрыл. Какие-то редакторы, что-то компилить и т.д. В общем, даже разбираться не стал. Начал смотреть что есть. Из всего многообразия, включая вские Panda.js и Crafty, c1tr00z таки подсказал, что есть ещё Phaser, что-то ещё и что-то ещё. Так как он был на первом месте, пошёл смотреть его. Был тутор, как создать первую игру, были другие туторы игор. Далее я делал следующее - я читал тутор phaser'а и смотрел, как там написано на яваскрипте, потом я читал доку на parenscript, чтобы написать так, чтобы он перевёл в тот яваскрипт, что на туторе, далее, собственно, это делал сам parenscipt, браузеру приходил красивый явскрипт, который, можно подумать, написал человек. В общем, квес с тутором был пройден, я его продемонстрировал и решили на phaser'е и остановиться.

Parenscript

Изначально, раз CL, то первым выходи parenscript. А это транслятор. С подмножества CL в яваскрипт. Из плюсов - неплохо так это делает, всё читается и дебажится из браузера. Минусы смутили больше, чем обрадовали плюсы - это просто транслятор, нет репла, нет среды разработки, не выработы правила создания, плагин к asdf для компилирования parenscript, который называется paren-files, имел коммит 6 (!) лет назад, с текущим ASDF3 не работает. В общем, ничего нет для parenscript. Сделали и забыли. Эта ситуация сильно удручила и я захотел реализовать это на чём-то современном, например, GWT ClojureScript. Нашёл библиотеку для clojurescript phzr и, засучив рукава, принялся делать ещё один туториал. Но почему-то body или что-то там было undefined, где оно таковым не должно было быть, и решил, что нужно использовать тру clojurescript без всяких обёрток НО ситуация повторилась один в один. Есть issue на гитхабе, где я описал свои злоключения, но ответа до сих пор нет. Что-то другое искать времени уже не было, поэтому решил, что нужно допинать parenscript, а в коде догнаться макросами. В общем, приступили на parenscript. Хорошо это или плохо пока не знаю, но конечный результат есть.

Сам джем

Как и планировалось, c1tr00z занялся исключительно графикой и основной частью гейм дизайна. Решили писать про ковбоя, который будет убивать пришельцев. Как я понял, после попытки прорисовать пришельцев, получились зомби, ну да ладно. Собственно, это была довольно нудная работа по припиливанию новых возможностей. Опять же, имя на руках паренскрипт, у нас был всего лишь яваскрипт со скобочками, что удручало. Тем не менее, использование макросов очень даже помогло. В целом, и движок phaser оказался относительно вменяемым. Дело пошло бодрее, когда подключился virvar, который думал, что 10-го джем только начинается. :) Ну а далее начал страдать дизайн кода, на который уже особо внимания не осталось в виду надвигающегося дедлайна. В общем, кое-как доделали и засабмитили под утро.

Итоги

До этого я ни в каких джемах не участвовал. Максимум, чем развлекался - это ICFPC. Это вообще разные задачи и разный экспириенс. Что же я усвоил и приобрёл?

  • главный итог в том, что игру мы эту таки сделали. Не забросили посередине, а вполне ко сроку уложились и это, считаю, огромный плюс в копилку экспы;
  • гейм индустрия очень интересна и манит кучей всего и тулов есть кучу разных. Изначально искал что-то простое, что подключил, написал, оно и готов. Вот Phaser в этом плане себя оправдал на все 100%;
  • parenscript это всё же яваскрипт со скобочками, ведь вполне присутствую проблемы с this внутри foreach и т.п. Вообще на этом джеме ояваскриптились. Но писать в скобочках всё равно приятнее. :) Но если сравнить ClojureScript и Parenscript, то, несомненно, победителем выходит ClojureScript. Ведь это действительно лисп со всеми его возможностями;
  • hunchentoot что-то не захотел работать у c1tr00z'а под виндой, что тоже насторожило;
  • близость дедлайна может превратить любой код в страшное месиво. :)
Вот. А в остальном было весело. Считаю, что каникулы прошли с пользой. Буду ли участвовать ещё в джеме? Возможно. ;)
Морзянка на Raspberry PI
Продолжаем эксперименты. В прошлый раз мы просто зажигали и гасили светодиод. Но этого нам мало. Я же вообще себя представил где-то на корабле, вокруг волны бются, качает, чемоданы падают и всё такое. В общем, надо бы как-то пообщаться. Для этого издавна уже используется азбука морзе.

Ну на самом деле код бесхитростный - берём по нашим буквам последовательность точек и тире. Таким образом получаем последовательность, которую можно пускать на светодиод. Почему-то я решил, что неплохо бы ещё заодно и парсить эту последовательность в буквы, взял дерево с википедии и с него же строил карту соответствий точек и тире в буквы. Подробнее можно посмотреть тут. В общем, ничего сверхъестественного, не считая, как я обнаружил совсем недавно, что дерево и таблица в википедии  не совпадают, но это уже проблемы данных.

Итак, вернёмся к нашим точкам и тире. По записям из той же вики. Длина точки это наша единица длины. Тире - это три точки. Между точками и тире пауза в одну точку и между словами пауза в 7 точек. Собственно, это и получилось:

(ql:quickload "gpio-sysfs")
(ql:quickload "morse")

(defparameter *pin* 27)
(defparameter *morse-time* 0.1)

(defun initialize ()
  (gpio:initialize-pin *pin* :out 0)
)


(defun wait (times)
  (sleep (* times *morse-time*))
)


(defun morse-dot ()
  (gpio:write-pin *pin* 1)
  (wait 1)
  (gpio:write-pin *pin* 0)
  (wait 1)
)


(defun morse-tire ()
  (gpio:write-pin *pin* 1)
  (wait 3)
  (gpio:write-pin *pin* 0)
  (wait 1)
)


(defun morse-word-letter (word-letter)
  (if word-letter
    (progn
      (map 'list
        (lambda (morse-letter)
          (ecase morse-letter
            (#\. (morse-dot))
            (#\- (morse-tire))
)
)
        word-letter)
      (wait 3))
    (wait 7)))

(defun morse-say (string)
  (let ((morse-struct (morse:to-morse string)))
    (mapcar
      (lambda (word-letter)
        (morse-word-letter word-letter)
)

      morse-struct
)

    nil
))

(initialize)
(morse-say "sos")
Теперь можно посылать различные сигналы вокруг. Например, писать, "Not enough minerals! Mine more minerals!". Выводы светодиода соединены к 27 пину GPIO. sbcl собран из исходников. Всё это работает на Raspberry PI B вроде бы, что-то древнее, но не самое простое.


ICFPC-2015: Отчёт об участии (Ктулху фтагн!)

Начало

Собственно, началось всё довольно обыденно. За пару месяцев до начала списались, договорились участвовать бравые лисперы swizard, sectoid  и grep-z. Заранее спланировали время, чтобы освободить ЭТИ дни на трёхсуточный марафон. Кровь бурлила, были настроены выигрывать. :)

Организаторы сразу начали нагнетать. Сначала в анонсе, затем в своём твиттере. Это и про восстание машин, и про квантовые комьпютеры. Да и вообще кучу всего. Уже предвкушал, предвкушал, потом появился странный твит: "R1 O0 P1 Q1 P1 O0 N0 N0 P1 R1 Q1 P1 O0 P1 Q1 R1 P1 N0 N0 Q1 S1 N1 T1 S1 R1 P1 R1 Q1 P1 O0 O0 P1 Q1 R1 P1 N0 N0". Я его не понял совсем, думал, что-то с кубитами. Затем про пчёл, затем про то, что то, что они видел - это вообще страх и ужас какой, да и лого было многообщеающим.

Но тут, если честно, они несколько разочаровали. Заданием оказался банальный тетрис, правада, в шестигранных сотах. Хекстрис, то бишь. Какой-то такой я играл несколько лет назад. Теперь нужно было научить и компьютер играть. Ну ещё и задача усложнялась тем, что из ходов нужно было подбирать некоторые слова, за которые начисляются дополнительные бонусы.


Картинка взята у какого-то участника. В общем, как и говорил, правила очень простые - двигать фигуры, расставлять, сжигать ряды, кодить всё это в дополнительные фразы. Вроде, если подумать, скукота. :) И тем обиднее, как плохо выступили.

Соревнования

К сожалению, на старте отвалился grep-z, извинившись за внезапно возникшие проблемы, зато добавился товарищ jtootf. Задания прочитали, всё просто, сразу напряглись, предполагая, что же будет в аддонах. Дополнительно ещё фразы были неизвестны, их предлагалось найти самим в произведениях Лавкрафта, да и в предоставленных медиа. Они, кстати, были на картах.

Ну, нацелились на лайтниг и молниеносно ворвались! Я уже не помню, кто что кодил, но swizard взял на себя основную работу, а мы проверяли, подсказывали, что-то пробовали дополнительное. Sectoid и jtootf, будучи более вовлечёнными в тему Ктулху, искали слова. Я с поиском фраз вообще не участвовал, ибо на этих соревнованиях про Ктулху услышал раз во второй, ну или, максимум, в третий.

Началось всё с ГСЧ. Видать, чтобы строго формализовать всю игру, орги определили алгоритм ГСЧ. По описаниям, он совпадал с системным, а вот по значениям не совпадал. Пришлось быстро налабать свой. Дополнительных проблем доставили соты, но их решили, перейдя на кубические координаты.

В общем, первый день кодили, кодили, кодили, кодили, кодили. Прям как девелоперс. При этом сделали карту, бинарь, переход из одной позиции в другую. Правда, алгоритм расположения был кривоват при поиске конечного места. В общем, к лайтнингу что-то уже было. Туповатое, правда. К лайтнингу сабмитим карты и! Огорчаемся. :( Где-то на картах даёт скор, где-то даёт лишь 0 очков. 0! Боль! Смотрим визуализацию и как печально, но некоторые элементы располагаются в начальной позиции не так, как описано в правилах. Бывают в жизни огорчения. Это находим минут за 5 до конца лайтнинг раунда. В общем, прошли мимо лайтнинга.

Далее добавляем к нашему алгоритму подбор места на основе оценки итогового состояния доски. Всё это работает, правда, медленно. Подбираем коэффициенты, пилим для этого генетический алгоритм, но что-то на него забиваем. Но вспоминаем почти под конец. :) Там же лихорадочно лепим подбор на основе выхода из начального положения рандомно куда-нибудь. Правда, ничего уже подобрать особо не успеваем, ищем фразы, добавляем ещё эвристику, но сабмитим наш старый вариант, потому что получая прирост на одних картах, при этом получаем заметный регресс на других, попутно перетирая пару карт с нулевым результатом. Итог - 57 место. Предварительно. Окончательные результаты в сентябре.

Зов Ктулху

На третий день соревнований я испытал проблемы с инетом. То же было и у swizard'а. Мы переключились на резервный канал. Затем за полчаса до конца соревнований я испытал проблемы и с резервным каналом, но переключился на ещё один резервный. Наверное, это Ктулху звал нас. Но мы не пошли. :)

Дополнительно


Итого

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

Отчёт swizard'а можно прочитать здесь.

ICFPC-2015, Таки идиш.
Проснулся с утра и новый твит. А там идиш. И позже орги дописали, что да, на идише текст. Имеет ли смысл какой текст или нет - пока не знаю, но явно не просто так он появился. :) Меж тем, перевод, сделанный в гугл транслейт, гласит: "В его доме на R'lyeh смерть kthulhu пшеницы сновидения." Во как, блин!
ICFPC-2015, Всё фигня, кроме пчёл
Опять потвитали орги. Говорят, обычный вопрос про то, где тыква? Да и ещё привели ссылку на пчёл, сопроводив комментарием: "Чёртов агро-комплекс! Если бы только они знали..."
ICFPC-2015, Аааа! Квантовые вычисления.
Накидали орги твитов. Одна из ссылок ведёт на статейку о компьютере гугла, который построит квантовый компьютер. Думаем, думаем...
Моргаем светодиодами на Raspberry PI
В общем, расчехлил я свою малинку и решил что-нибудь поделать. Первым делом, собрал там ccl, потом sbcl. Раньше sbcl собрать было нельзя. Теперь можно. Даже, вроде, работает.
В общем, брат собрался делать умный курятник, нашёптываю ему, что нужен lisp, ибо тру и всё такое. Он что-то пока посматривает на питон. :-\ 
Ну да ладно, теперь по порядку. Дабы чем-то управлять, нужно уметь подавать на выходы. А выходы можно смастерить на GPIO (General Purpose Input Output). А управлять этим GPIO будем... Нет, не из С, а именно из лиспа, в данном случае sbcl.
Собственно, заморачиваться не стал всяким FFI, ибо у нас есть sysfs интерфейс для GPIO. Собственно, по этой документашке накидана на скорую руку простейшая библиотека. Не шедевр, конечно, но функции выполняет. Потом причешу, думаю. Итак, пользовательский код:
(ql:quickload "cl-gpio-sysfs")
(gpio-sysfs:initialize-pin 27 :out 0)

;;; Посылаем 1 на выход порта, светодиод горит
(gpio-sysfs:write-pin 27 1)

;;; Посылаем 0 на выход порта, светодиод гаснет
(gpio-sysfs:write-pin 27 0)

(gpio-sysfs:shutdown-pin  27)
(quit)  


Перед запуском нашу библиотеку нужно забрать в quicklisp/local-projects. Ну а перед этим установить quicklisp.
Собственно, как этот светодиод горит, можно даже посмотреть:



ICFPC-2015, анализ анонса
Сразу скажу, что допёр до всего не сам, но почитал разные ресурсы, в том числе и reddit ну и подёргал цитаты из интернета. Итак, начнём с названия документа, которое выглядит как "OGA-BAA-15-18". Сначала показалось это совсем бессмысленным, но потом вчитался в сам документ. 
OGA - Other Government Agencey, Другое Правительственное Агентство, почти как обычный порошок. Английская википедия говорит, что это некий эвфемизм для CIA (ЦРУ). 
BAA - прямо в шапке и написано "Broad Agency Announcement", некий способ для правительственных организаций США проведения контрактов по исследваниям и разработкам.
15-18 - предположительно номер документа, формируемый из года (15) и, как заметили в комментариях, номер по счёту проводимого состязания.
AS2H2 - что я только ни гуглил, каких только химический соединений не нашёл. А надо было читать документ. Там прямо и написано "Advanced Simulacrum Simulation High-­assurance Haven". Не знаю как правильно перевести, я перевёл как "Расширенная Симуляция Высокогарантированного Пристанища". Ну в общем, какая-то симуляция окружения, наверняка, будет. И к этому какая-то фабула. Предпосылки есть.
Aleister - так называется программа исследований. Гугл выдаёт в основном только этого известного оккультиста. Настолько пафосный товарищ, что пока не понял чем связаны сами исследования с его именем.
Miscatonik University - цитирую с википедии: "вымышленный университет, расположенный в вымышленном городе Аркхем, штат Массачусетс. Был придуман американским писателем Говардом Лавкрафтом и в дальнейшем появлялся не только в его произведениях, но и в произведениях его последователей. Наименование университета образовано от названия реки Мискатоник, протекающей через город. Считается, что Лавкрафт давал таким образом намёк на Массачусетский технологический институт." Имеет отношение к мифам Ктулху.
GCHQ - "Центр правительственной связи (англ. Government Communications Headquarters, GCHQ) — спецслужба Великобритании, ответственная за ведение радиоэлектронной разведки и обеспечение защиты информации органов правительства и армии."
2840 Hazelnut Dr. Woodburn, OR 97071 - это адрес ещё одной OGA. Насколько именно будет гольф или же просто интересно совпадение аббревиатур - не знаю.
Само лого - его можно рассмотреть при увеличении, у этой картинки высокое разрешение. Это некий ящик, в который входит лента, на которой изображение разные символы. Если правильно посчитал, то 8 разных символов. Предположительно, машина Тьюринга. На самой машине ещё есть стрелка и вокруг неё 5 различных изображений: возможно Ктулху (осьминог), иконка (похожая на иконку копирования), знак биологической опасности, астероид, знак радиации. Ну и ещё вырез в самой машине для подкидывания бланка или выпуска распечатки. Возможно, ввод/вывод.
Что ещё - само описание говорит о криптографии, алгоритмах, безопасности. Да ещё и отсылка на среду симуляции позволяет сказать, что задание должно быть, как минимум, интересным. :)

ICFPC-2015, дата проведения
Стала известна дата проведения ICFPC-2015. Как обычно, проходит с пятницы по понедельник. В этом году с 7 по 10 августа. В общем, я уже начинаю морально готовиться. Мои товарищи по команде в прошлом ICFPC-2014 уже высказли своё согласие и тоже начали двигать дела, чтобы освободить эти дни. Выступаем, как обычно, на Common Lisp.
Креш-курс по Лиспу - кому он будет интересен

В июле должен состояться мой мастер-класс введение в практическую разработку на Common Lisp. По этому случаю меня попросили написать статью в блог компании SmartMe, которая проводит это мероприятие. В ней я попытался ответить на вопрос, кому и зачем сейчас может быть интересно разобраться с Лиспом.

Лисп — один из самых старых и, пожалуй, самый загадочный из современных языков программирования. Также бытует мнение, что он не просто стар, а устарел. Почему это не так и где его ниша, я попробую ответить в этой статье.

Лисп — пожалуй единственный динамический системный язык программирования. И среди динамических языков он остается непревзойденным выбором благодаря следующими свойствам:
  • реальной мультипарадигменности, дающей возможность элегантно совмещать процедурный, объектно-ориентированный, функциональный и другие стили
  • уникальной поддержке метапрограммирования
  • легендарной интерактивной среде разработки
  • железобетонному стандарту языка, за которым стоит многолетняя работа мегаумов МИТа, Xerox PARC, CMU и других подобных мест, оплаченная DARPA
  • обширному набору реализаций (компилятор и среда исполнения), коих разработано за его историю около 25, до 10 из которых активно поддерживаются и развиваются
На самом деле, современное положение Лиспа как языка, который обычно не рассматривают для серьезной разработки, обуcловленно отнюдь не техническими причинами, а лишь исторической случайностью — язык сильно опередил свое время,— и человеческим фактором: он и не выбор по-умолчанию (как С++, Java или JavaScript), и не модная новая технология (как Scala, Go или Ruby), и не имеет за собой какую-либо серьезную организацию или сообщество, которые бы продвигали его использование (как C#, Swift или Rust). Тем не менее, миф о непрактичности Лиспа опровергает как мой опыт использования его в ядре Grammarly и предыдущих моих коммерческих проектах (уже более 7 лет), так и опыт поисковика авиабилетов ITA Software, купленной Гуглом за миллиард долларов, или же португальской Siscog, разработчика решений для железных дорог, в которой работает более полусотни Лисп-программистов. А адепты теории о необходимости его модернизации могут почитать Changelog SBCL (лидирующей open source реализации) :)

Конечно, у Лиспа есть и недостатки — помимо небольшого сообщества, представленного в основном энтузиастами, это:
  • непривичный синтаксис
  • часто непривичные подходы и способы разработки
  • отсутствие библиотек для взаимодействия с остальной средой (проект Quicklisp давно доказал обратное :)
Таким образом, еще раз можно повторить, что язык и экосистема Common Lisp не имеет серьезных технических недостатков при ряде бесспорных преимуществ, но он слишком непривычен и нетипичен, поэтому страдает от проблемы курицы и яйца: отсутствие Лисп-программистов не позволяет начинать на нем серьезные проекты, а отсутсвие импульса в сообществе не приводит в него новых программистов. Поэтому, Лисп вряд ли будет в ближайшее время серьезно использоваться в индустрии разработки. В чем же тогда его ниша сегодня? Если оставить за скобками тренды, то я бы сказал, что в первую очередь, это системы, которые пишутся на годы и должны постоянно эволюционировать: в этом плане он находится в точке золотой середины между классическими системными языками, типа C++ и Java, и их динамическими конкурентами, предоставляя невероятно гибкую и, в то же время, достаточну производительную (как в отношении скорости исполнения, так и скорости разработки) среду. Особенно, если такие системы должны иметь средства представления и обработки большого количества знаний. Как раз про них 10-е правило Гринспена:
Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.
Однако, очень мало кто решится писать сейчас такие проекты на Лиспе. Более актуально другое его применение — быстрое прототипирование и среда для экспериментов. В этой нише у Лиспа много конкурентов, таких как Python или же специализированные языки, типа R и MatLab, но преимущество Лиспа в том, что удачный протип можно со временем довести до продакшн системы. Однако, самое важное значение Лиспа для меня — это полная свобода творчества, которую он предоставляет. Кроме шуток, доступ к такой среде дает возможность программисту развиваться не просто набором опыта использования каких-либо инструментов и фреймворков, а через решение нестандартных задач пытаясь найти для этого наиболее удачный способ независимо от случайных ограничений, налагаемых текущими обстоятельствами и принятыми нормами.
ICFPC-2014 - результаты
Ну вот и опубликовали результаты. Какой итог - в общем зачёте заняли 44 место из 142 команд. В молниеносном раунде 53 место из 94 команд. Ну, в 20-ку не попали, но в первой трети. :)
Nagios, нотификация по jabber (xmpp), sms и языковый интернационал
В общем, есть программа nagios для мониторинга, в ней есть нотификации о падении сервисов (ну и вообще настраивается). И можно даже гибко добавлять то, что нужно. Самое удобное - jabber (xmpp) и sms. email у него из коробки есть. Да и email отправляет в очередь почтового сервера, а вот если просто использовать скрипты для отправки, то может случиться так, что нет инета, недоступен сервер jabber или sms api. Но при этом скрипт отработал, хоть и вывалился с ошибкой. С отправлением на email всё понятно. Там отправляется всё на почтарь и висит в его очереди. Что ж. Нам тогда тоже нужна очередь. :)

В качестве очереди нужно было что-то довольно простое и которое умело бы удобный интерфейс командной строки. Вроде бы подошёл redis. Ну на самом деле, положить в очередь:
redis-cli rpush queue "test message"
 Взять из очереди:
redis-cli lpop queue
В общем, очередь у нас получилась легко. Ну и главный критерий при выборе инструментов был, чтобы получалось всё легко. Далее, эту очередь нужно было обрабатывать. Я заранее не знал, какой формат я там выдумаю, а парсить на баше не очень то и хотелось, поэтому я хотел было взять старый добрый picolisp, но передумал, и взял elisp (это тот, на котором построен emacs). И вот что получилось:
#!/usr/local/sbin/emacs-clean --script
; -*- mode: Emacs-Lisp -*-

(defun message-as-string (message)
  (with-output-to-string
    (let ((first (car message))
          (rest (cdr message)))
      (if first
          (princ first)
        (princ ""))
      (dolist (line rest)
        (terpri)
        (if line
            (princ line)
          (princ ""))))))

(defun receive-from-queue (queue-name)
  (process-lines "redis-cli" "lpop" queue-name))

(defun send-to-queue (queue-name message)
  (process-lines "redis-cli" "rpush" queue-name (message-as-string message)))

(defun tmp-queue (queue-name)
  (concat queue-name "-tmp"))

(defun process-mail-message (message)
  t)

(defun process-xmpp-message (message)
  (condition-case nil
      (progn
        (process-lines "send-xmpp" (car message) (message-as-string (cdr message)))
        t)
    (error nil)))

(defun process-sms-message (message)
  (condition-case nil
      (progn
        (process-lines "send-sms" (car message) (message-as-string (cdr message)))
        t)
    (error nil)))

(defun process-message (queue-name message)
  (let ((success-state (pcase queue-name
                         ("mail" (process-mail-message message))
                         ("xmpp" (process-xmpp-message message))
                         ("sms" (process-sms-message message)))))
    (unless success-state
      (send-to-queue (tmp-queue queue-name) message))))

(defun process-queue (queue-name loop-queue)
  (while (let ((next-in-queue (receive-from-queue queue-name)))
           (unless (equal '("") next-in-queue)
             (process-message queue-name next-in-queue)
             loop-queue)))
  (while (let ((next-in-tmp-queue (receive-from-queue (tmp-queue queue-name))))
           (unless (equal '("") next-in-tmp-queue)
             (send-to-queue queue-name next-in-tmp-queue)
             t))))

(pcase (length argv)
  (0 (dolist (queue '("xmpp" "sms"))
       (process-queue queue t)))
  (1 (process-queue (car argv) nil))
  (_ (progn
       (princ "Usage: process-queue ")
       (terpri))))
Смысл заключается в том, чтобы прочитать из очереди по типу сообщения (xmpp, sms), а потом вызвать программу для доставки. Если же произошла какая-то ошибка, то вернуть обратно в очередь, которую затем обработает этот же скрипт, запустившись в кроне.

XMPP решил отправлять питоновским скриптом, ибо он нагуглился быстрее всего. Я его немного, правда, модифицировал, чтобы конфиги читал, да и адресов несколько было:
#!/usr/bin/python
import sys, xmpp, ConfigParser

if len(sys.argv) != 3:
    print("usage: %s " % sys.argv[0])
    sys.exit(1)

config = ConfigParser.ConfigParser()
config.read("/etc/send-xmpp.ini")
xmpp_jid = config.get("general", "jid")
xmpp_pwd = config.get("general", "password")

toliststring = sys.argv[1]
tolist = toliststring.split(",")
msg = sys.argv[2]

jid = xmpp.protocol.JID(xmpp_jid)
client = xmpp.Client(jid.getDomain(), debug = [])
client.connect()
client.auth(jid.getNode(), str(xmpp_pwd), resource = "SrvMonitor")
for to in tolist:
   message = xmpp.protocol.Message(to, msg)
   message.setAttr("type", "chat")
   client.send(message)
client.disconnect()
Конфиг - это обычный INI файл. Для отправки SMS использовался сервис LetsAds. У них есть API, как и у всех. Туда просто отправлял через curl:
#!/bin/bash

if [[ $# -ne 2 ]]; then
  echo "Usage: $0 <phone> <message>"
  exit 1
fi

source /etc/send-sms.conf

TO=$1
MSG=$2

URL="http://letsads.com/api"
XML="<?xml version=\"1.0\" encoding=\"UTF-8\"?>
<request>
    <auth>
        <login>$PHONE</login>
        <password>$PASS</password>
    </auth>
    <message>
        <from>$FROM</from>
        <text>$MSG</text>
        <recipient>$TO</recipient>
    </message>
</request>"

CURLRESULT=`curl --silent --data "$XML" $URL`
CURLEXITCODE=$?
RESULTERROR=`echo "$CURLRESULT"|grep '<name>Error</name>'`

if [[ ! $CURLEXITCODE -eq 0 ]] || [[ ! -z "$RESULTERROR" ]]; then
  exit 1
fi
Ну и последний штрих - скрипт, отправляющий в очередь:
#!/bin/sh

QUEUE_NAME=$1
TO=$2
MESSAGE=$3

redis-cli rpush "$QUEUE_NAME" "`printf "%s\n%s" "$TO" "$MESSAGE"`"
process-queue "$QUEUE_NAME"
Собственно, он и используется в самом нагиосе для того, чтобы положить в очередь:
/usr/local/sbin/queue-notification sms "$_CONTACTPHONE$" "$NOTIFICATIONTYPE$ : $HOSTALIAS$/$SERVICEDESC$ is $SERVICESTATE$ ($OUTPUT$)"
В общем, всё довольно просто и прозрачно. Для пущей надёжности можно было бы ещё добавить сохранение состояния редиса после запихивания сообщения в очередь, но этим уже страдать не стал.
Модный апач и добрый пиколисп
В общем, так вышло, что пришлось обновляться. Обновился также и апач до версии 2.4. В старой версии 2.2 ещё продолжал работать модуль mod_auth_pam и было очень удобно, что я имел аутентификацию такую же, как и системную. В новой версии этот модуль за каким-то лядом выпили и всё перестало работать. Ну ляд там вполне понятный, конечно, кривой код, кривой в итоге модуль. Рекомендовали вместо этого использовать mod_authnz_external. Это, конечно, не то, но тоже решение. Программка pwauth для проверки пользователя по паролю была в комплекте, а вот ещё нужная вещь ограничение по группам пользователя не нашлось. Но нашёлся какой-то перловый скрипт, который шёл в исходниках этого модуля, который почему-то не заработал. Может, поэтому его и не включили в дистрибутивный пакет. Пришлось писать. Основная идея - берем с помощью getent группы и пользователей и создаём списки групп, куда входят как пользователи, которые участвют в списке, так и те, чья группа является основной.
Для реализации пришлось думать что брать. Нужно было, чтобы можно было обрабатывать списки (lisp, ну как же) и при этом чтобы можно было легко и прозрачно взаимодействовать с системой. В прошлом мне нравился Scheme Shell, но его судьба мне теперь неизвестна, вроде на 64 битных платформах с ним туго, хотя, вроде, есть multiarch, но привлёк некий picolisp - с очень свежим (или не очень) взглядом на мир. В общем, в целом обычный лисп, команды относительно удобно вызываются. Пример вызова "getent passwd":

(in (list 'getent "passwd")
  <какие-то действия>)
 Ну а дальше дело пошло. :) В общем, вот целиком готовый скрипт. Ну и как у меня выглядит конфиг апача, раз уж речь о нём тоже зашла. Это в конфиге virtualhost.
        # External auth
        DefineExternalAuth sysauth pipe /usr/sbin/pwauth
        DefineExternalGroup sysgroup pipe /usr/local/sbin/sysgroup
 А это в конфиге уже непосредственно того ресурса, который нужно разграничивать:
        AuthType Basic
        AuthBasicProvider external
        AuthExternal sysauth
        GroupExternal sysgroup
        AuthName "BAZON.RU projects"

        require external-group developers
ICFPC-2014 - невероятно, но факт!
Ещё одна любительская симуляция. Как ни странно, на ней мы показываем неожиданные для себя результаты (напоминаю, что называемся мы Skobochka). В принципе, это не финальная симуляция оргов, но даже такого результата не ожидали. Если всё так и будет идти, то даже есть ненулевой шанс, что мы засветимся в TOP20. Если это произойдёт, то я буду выглядеть приблизительно так:


ICFPC-2014 - мелочь, а приятно
В общем, один из чуваков решил не дожидаться официальных результатов и захотел составить неофициальную таблицу. Для этого он просил запустить у себя и скинуть ему цифры. Не поленился swizard, замерял, отправил. Расстраивает, что в общем зачёте нас даже нет, зато на картах мы там где-то тусуемся в пределах видимости топа. А по карте world-2 так вообще на первом месте! :) Об этом уже похвастался swizard у себя в журнале, ну и я тоже не смог удержаться. :)


ICFPC-2014 report
Ну вот, он и завершился. Первое, что хочу сказать - было круто. Большое спасибо моим товарищам по команде - swizard, sectoid и grep-z. В позапрошлом году участвовали мы на пару с swizard'ом, а прошлогодний я конкретно прослоупочил. Помня контест 2012 года, подумали, что неплохо бы ещё рабочих рук и светлых голов и потому кинули объяву. На которые откликнулись sectoid и grep-z.

В этом году нужно было программировать поведение пакмана в одноименной игре и поведение приведений, которые за этим пакманом гоняются и хотят его съесть. Код пакмана нужно было написать на ассемблере некой лямбда машины, приведённой в спецификации, а для привидений на обычном трушном ассемблере. Кстати, орги назвали пакмана лямбда-меном, а его управляющую часть "General Computing Processor" (GCC). Привидения так привидениями и остались, а их управляющая часть "GHost Cpu" (GHC). Что как бы намекает, но по смыслу наоборот. :)

Орги выкладывали спецификацию частями. Для молниеносного раунда нужно было лишь подготовить программу на GCC. При этом в спецификации встречались некоторые входные параметры, помеченные как "undocumented". "Это неспроста", - подумали мы, поэтому отреверсили их в эмуляторе и получили, что там находится код для гостов (првидений). Понятно было, что наш пакман обладает способностью анализировать гостов, предсказывать их и на этом строить свою стратегию. Это было круто, конечно, но... :)

В общем, как получили задание, так сразу решили написать транслятор некоего лиспа, который мы назвали "intermediate lisp", в код GCC. Не обошлось без багов, например, путали порядок аргументов во фрейме и то, как они располагаются в стеке. Но обошлось. Стратегией сразу занялся swizard и заключалась она в том, чтобы всё жрать, а от гостов бегать. Собственно, где-то такое решение и засабмитили на лайтнинг. Хотя, теперь могу ошибаться. :)

Как завершился лайтнинг раунд, орги добавили дополнительную спецификацию, где и раскрывались "undocumented" который мы уже, в принципе, и знали. Сразу сели и подумали по нашим ограничениям. Размер программы гостов содержал максимум 256 инструкциий, а врмя на выполнение ограничивало его на 1024 инструкции. Поэтому делать что-то сложное для них теряло смысл. Решили сконцентрироваться на пакмане.

Но пакманом плотно занимался swizard, за транслятор плотно засел sectoid. Витало несколько идей - трансляции ilisp в common lisp, чтобы можно было отлаживаться и другая - трансляции common lisp  в ilisp, чтобы тоже можно было отлаживаться. Пытались реализоваться оба варианта, но победил последний. Правда, как высказался swizard, наверное, имело смысл сделать транслятор сразу в GCC.

В общем, чтобы не мешаться, мы с grep-z решили накидать какой-нибудь простой алгоритм для гостов. И тут меня почему-то торкнуло, что надо реализовать волновой алгоритм поиска пути. Товарищ grep-z же решил, что надо попробовать тупо простое сближение. При простом сближении госты тупо застревали на стандартной карте, пока рядом не пробегал пакман. Закончив волновой алгоритм, обнаружилось, что он не укладывается в 1024 инструкции выполнения. Тогда я придумал ещё одну хитрю вещь - на одном запуске GHC исполнять часть алгоритма, на другом - другую часть и т.д. Но боты так не могли долго принять решение и я от этой затеи отказался. :)

Время уже поджимало, долго возились с транслятором и компилятором. Я начал читать какие ещё есть алгоритмы поиска пути. В итоге просто решил запоминать тупиковые клетки и туда не ходить. При этом если клетка граничила с другим тупиком, то там тоже считалось, что хода нет. В итоге родился гост, который преследовал пакмана. Нашли ссылку про стандартное поведение гостов в классическом пакмане и тогда я добавил ещё одного госта, который идёт на опережение на 4 клетки с пакманом, а при расстоянии меньшем переключается на преследование. И в финальный сабмишн ушло два этих госта. Сюда компилятор не писали, испугались ограничений. :) Вместо этого написали некое подобие макроассемблера.
 Но программировать на нём - всё равно АДъ!

Что же было не так? Всё же, не хватало знаний по лямбда исчислению. Незнание современных методов поиска пути тоже удручало. Думаю, что надо было попытаться сделать компилятор. Не знаю пока, уложились бы мы с этим компилятором в 256 байт, но повторюсь, это АДъ! Хотя, как привыкнешь, вроде обыденно. Постоянно нас преследовали какие-то ошибки в трансляторе GCC. Вместо отладки ИИ занимались правкой багов.

Что же было отлично? Common Lisp! Хотя, в последнее время я программировал на clojure, но Common Lisp чертовски приятен тоже. Технологично - язык получился hosted и пакмана разрабатывать было хорошо. Хорошая команда. Надеюсь, в следующем году мы точно победим! :)
ICFPC-2014 over
Этот трёхдневный марафон под названием ICFPC-2014 закончился. В этом году участвовал в команде из 4-х человек под названием "Skobochka". Было весело. Подробности отпишу позже, как отосплюсь, а пока смотрите наши исходники.
Ищем Лиспера с горящими глазами
Уже 3 года я работаю в Grammarly, где мы строим (и довольно успешно) самый точный сервис исправления и улучшения английских текстов. В экстремуме эта задача упирается в полноценное понимание языка, но пока мы не достигли этого уровня, приходится искать обходные пути. :) Понятно, что работы у нашей команды, которую мы называем "core team", выше крыши. Но эта работа довольно сильно отличается от обычной программной инженерии, точнее, инженерия — это ее конечный этап, которому предшествует огромное количество экспериментов и исследования.

Я как-то назвал нашу систему Grammar OS, поскольку она чем-то похожа на ОС: в ней есть низкий уровень языковых сервисов, есть промежуточные слои проверщиков, есть и пользовательские приложения. Одним из ключевых компонентов является написанная на Лиспе и постоянно развивающаяся система проверка грамматики. Этот проект помимо собственно сложной задачи, на которую отлично легли возможности Лиспа, high-load'а, также интересен и тем, что над ним работают около 5 компьютерных лингвистов, которые все время дописывают в него какой-то код...

К чему я это веду, это к тому, что мы уже больше полугода ищем Лисп-разработчика, желающего подключиться к развитию этой системы, а в перспеткиве и к работе над новыми Лисп-проектами, о которых мы думаем. Помимо Лиспа в ядре у нас используется много Джавы (даже больше), и мы, в общем-то, ее тоже любим. И немного Питона. А основной фокус сейчас все больше и больше сдвигается в сторону различных алгоритмов машинного обучения.

Наконец, у нас в Grammarly отличная атмосфера и куча людей, у которых есть чему поучиться.

 

В общем, как по мне, практически работа мечты для программиста, которому нравится обработка текстов, R&D или Лисп. Логичный вопрос: почему же мы так долго не можем найти подходящего человека? Ответов несколько:
  • Во-первых, мы всех нанимаем очень долго (почти полгода искали даже Java-разработчика). Почему — смотри выше — качество команды для нас важнее скорости.
  • Во-вторых, лисперов с индустриальным опытом у нас не так и много: в Киеве их от силы пару десятков, в России — больше, но мало кто из них хочет переезжать.
  • В-третьих, даже у технически сильных кандидатов часто не горят глаза :(
Короче говоря, ситуация такова:
  • Есть сложная и интересная работа, с хорошей зарплатой, отличной командой, компанией и перспективами.
  • Нужен увлеченный своей работой программист, который хорошо понимает алгоритмы, математику и статистику, и хочет писать на Лиспе.
  • Опыт на Лиспе нужен, но не обязательно из реального мира: open-source или хобби-проекты тоже покатят. Но тогда важно желание и способность быстро развиваться в этом направлении.
Если что, пишите на vseloved@gmail.com...
Обновление подсветки Common-LISP синтаксиса в Gedit
Решил проверить работает ли старый конфиг для подсветки синтаксиса Common-lisp в последних версиях Gedit ибо давно не касался этой темы. И оказалось посмотрел не зря! Опять все перелопатили)) Теперь конфиги нужно располагать в директории ~/.local/share/gtksourceview-3.0/language-specs/ и сам файл пришлось немного переписать. Ну и заодно добавил characters.
Итак, создаем папку
$ mkdir ~/.local/share/gtksourceview-3.0/language-specs
Создаем файл конфигурации
$ touch ~/.local/share/gtksourceview-3.0/language-specs/lisp.lang
И копируем в него содержание этого гиста https://gist.github.com/LiteTabs/6074753
Перезагружаем Gedit и наслаждаемся радугой

Как создавать библиотеки в Common Lisp'е

Как-то на форуме писал пост, а получился небольшой туториал.

Итак у вас есть всякие переменные и функции в репле или лисп файле:


(defvar *who* "world")

(defun greetings ()
(format t "Hello, ~a" *who*))
  1. Заверните это всё хозяйство в пространство имён. В коммон лиспе это называется пакет. Далее встречая слово пакет нужно думать о пространстве имён. Итак:
    1. Создайте, если ещё не создан файл utils.lisp.
    2. Сперва определите пакет с помощью defpackage. Импортируйте в него стандартный пакет common-lisp. Экспортируйте из него переменные и функции. Кстати в коммон лиспах переменные и функции адресуются с помощью символов. В нашем случае должно получится так:

      (defpackage utils
      (:use common-lisp)
      (:export *who* greetings))
    3. Затем перейдите в этот пакет командой in-package:

      (in-package utils)
    4. А затем уже разместите всё своё хозяйство:

      (defvar *who* "world")

      (defun greetings ()
      (format t "Hello, ~a" *who*))
  2. Теперь необходимо сообщить коммон лиспу о том, как всё это загрузить. Есть много способов, бла-бла-бла. Единственно мейнстримный asdf. Все его используют, все довольны. Следующий шаг создание пакета (в коммон лиспе это называется asdf-система). Теперь всегда встречая слово система, думайте о готовой к использованию библиотеке:
    1. Для этого создаётся файл utils.asd, и в нём с помощью макроса asdf:defsystem перечисляются коммон лисповые системы:

      (asdf:defsystem utils
      :licence "MIT"
      :version "1.0.0"
      :author "Your Name <yourname@email.com>"
      :depends-on ()
      :components ((:file "utils.lisp"))
      :description "Small library.")
      Как вы заметили в этот макрос передаются всякие списки. Первый важный :depends-on содержит другие asdf-cистемы, от которых зависит данная система. Все живое в мире друг от друга зависит, также и коммон лисповые системы могут друг от друга зависеть. Этот список для библиотеки cl-portaudio, которая позволяет играть/записывать звук в коммон лиспе выглядит так:

      :depends-on (:cffi :ffa)
      Далее идёт еще более хитрый параметр :components. В нем перечисляются а) модули (или же просто группы файлов, которые, например в одной папке лежат) б) эти самые файлы в) кого за кем грузить (или порядок загрузки файлов, или же зависимости между файлами). с) ещё пару параметров, сейчас их знать необязательно. Например, для cl-portaudio этот параметр выглядит так:

      :components ((:module src
      :serial t
      :components ((:file "package")
      (:file "portaudio"))))
      :module src означает, что файлы объеденены в модуль, и по-умолчанию находятся в одноимённой папке. :serial t означает, что файлы зависимы друг от друга в том порядке, в котором перечислены.
  3. Вуаля, библиотека на коммон лиспе готова. Допустим это папка myutils, c файлами utils.asd, utils.lisp. Теперь зайлейте это всё на github, ну или вообще на любой хостинг.
  4. В коммон лиспе стараниями Зака Бина появлися прекрасный менеджер библиотек, который позволяет одной командой скачать загрузить как саму библиотеку, так и все её зависимости. Например,

    (quicklisp:quickload '(:cl-gtk2-gtk :cl-portaudio))
    Загрузит cl-gtk2 и cl-portaudio со всеми зависимостями, так что можно писать теперь свой скайп со шлюхами и блекджеком. Для того, чтобы ваша библиотека попала в репозитарий quicklisp'а, просто оставьте на неё ссылку здесь. Внимание, соблюдайте традицию вежливости, начинайте заголовок со слова "Please"!:)
Теперь ещё большее внимание!!! Всё это можно было проделать за ДВЕ команды. Итак:

(ql:quickload :quickproject)

(quickproject:make-project "path/to/library" :depends-on '() :license "MIT" :author "Your name <your@email.com>" :name "utils")
Всем quicklisp, посоны.

Сегодня речь пойдёт о том, как создать свой собственный quicklisp репозиторий. За реализацию этого проекта https://github.com/orivej/quickdist мегаспасибо orivej.

План такой: разместить свой проект с зависимостями так, чтобы пользователь в две строки мог загрузить его себе. Для этого нам необходим всего лишь хостинг для статических файлов. Github это дело умеет.

Скачайте проект quickdist в папку с локальными проектами. В официальном ql репозитории quickdist нет:


cd ~/quicklisp/local-projects
git clone https://github.com/orivej/quickdist.git

Расположите свои проекты в одной директории, например, ~/projects.

Теперь создайте репозиторий, например в папку ~/projects/cl-systems. На этом шаге нужно знать по какой ссылке будет доступен репозитарий. Если вы расположитесь на гитхабе, ссылка будет выглядеть так: http://%username%.github.com/%projectname%. Вызов функции выглядит так (не забудьте заменить %reponame%, %nickname%, %projectname% на свои данные):


sbcl
(quickdist:quickdist :name "%reponame%" :base-url "http://%nickname%.github.com/%projectname%" :projects-dir "~/projects" :dists-dir "~/projects/cl-systems")

Перейдите в папку с репозиторием и поколдуйте гитом, примерно так:


touch index.html # index.html нужен чтобы гитхаб раздавал http доступ к отдельным файлам проекта
git init
git add .
git commit -a -m "initial commit"
git checkout -b gh-pages # гитхаб раздаёт http доступ только для файлов из ветки gh-pages
git push -u origin master
git push -u origin gh-pages

Теперь вы можете добавить ваш репозитарий таким образом:


(unless (ql-dist:find-dist "%reponame%")
(ql-dist:install-dist "http://%username%.github.com/%projectname%/%reponame%.txt" :prompt nil))

Удаление ссылки на репозиторий выполняется функцией ql:uninstall-dist.


(ql:uninstall-dist "%reponame%")

Лисповая библиотека будет загружаться из наиболее последнего установленного дистрибутива. Изменить данное поведение можно с помощью (ql-dist:preference (ql-dist:find-dist "%reponame%"))).

Ansi Common Lisp на русском

Недавно вышел русский перевод книги Пола Грема "Ansi Common Lisp", к которому я немного приложил руку в качестве "научного" редактора. На форуме lisper.ru уже были сообщения от счастливых обладателей бумажной версии книги, а на сайте издательства даже доступен ее электронный вариант по свободной цене.

Хотя изначально я скептически отнесся к выбору именно этой книги для перевода, сейчас я рад, что так вышло. Работая над переводом, хочешь-не хочешь, а пришлось прочитать книгу практически от корки до корки, и могу сказать, что это, пожалуй, самое краткое, простое и доступное введение в язык. Practical Common Lisp лучше открывает глаза, и все-таки остается самой лучшей книгой по Lisp'у в целом, но он существен больше. В общем, ANSI CL — очень хороший вариант для начинающих. И хотя стиль Пола Грема часто критикуют в современном Lisp-сообществе, эта книга достаточно сбаллансированна и не содержит каких-то апокрифических мыслей :)

Книга состоит из двух частей, меньшая из которых — справочник — фактически бесполезна из-за наличия Hyperspec'и. Но это хорошо, поскольку остается меньше текста для прочтения :) Первая же часть состоит из 13 глав, описывающих разные аспекты языка, и 3 глав с решением практических задач. Главы про язык содержат множество примеров использования различных структур данных и реализации с их помощью нетривиальных алгоритмов, что может позволить неплохо прокачать это направления тем, кто не занимается постоянным решением алгоритмических задачек на Codeforces. Особенно, учитывая красоту и ясность реализации этих алгоритмов на Lisp'е. Несколько глав были весьма полезны и мне с моим пятилетним практическим опытом использования языка: например, я смог по достоинству оценить элегентность structs и стал намного больше пользоваться ими, интересными также были главы про оптимизацию и структурирование программ. В последних 3 главах разобраны классические для Lisp'а задачи: логический вывод, создание своей объектной системы (фактически, реализация внутренностей JavaScript'а) и генерация HTML из мета-языка — это те вещи, на которых видны некоторые из самых сильных сторон языка.

Из-за проблем издательства работа над переводом велась очень долго — что-то около двух лет. Точнее, сама работа длилась намного меньше, но ее отдельные части были разделены большими временными промежутками. Переводил allchemist, и сделал это задорно и весело. Своей задачей я видел прежде всего исправление отступлений от оригинала и работу с терминологией. Что касается второго пункта то тут я хотел напоследок рассказать занимательную историю про стог и пул.

Стог и пул

Пару лет назад Иван Сагалаев, который выступал в той же роли научного редактора для книги "Coders at Work", написал следующее по поводу роли научного редактора:

Кто не знает, научный редактор — это человек, совершенно необходимый для специальной литературы. Он берёт сырой перевод и приводит специфичную терминологию в соответствии с принятой в реальном мире. В результате вы читаете книжку, в которой написано не "процесс синтаксического разбора", а просто "парсинг", и не "интерфейс прикладной программы", а "API".

Применительно к Кодерам, которые должны читаться как приключенческий роман, я согласен с подходом Ивана. Но вот что касается таких книг, как ANSI CL, предназначеных прежде всего для (относительных) новичков, я считаю, что выбор должен делаться в сторону максимальной понятности терминов, а не привычности их для людей, которые уже в теме. Т.е., конечно, не "процесс синтаксического разбора", а просто "синтаксический разбор" и местами "разбор" — но не "парсинг". Почему? Да хоть потому, что "парсинг" для новичка создает некий магический ореол вокруг этого термина и выделяет его из ряда других, названных на родном языке, хотя ничего выделяющегося в нем нет. Да, часто подобрать адекватный термин на родном языке очень трудно, порой их даже приходится изобретать, но именно так и происходит развитие терминологии.

По этому поводу в этой книге было 2 очень интересных примера, за первый из которых меня можно смело закидывать помидорами, но я все же буду продолжать настаивать на нем. Давайте перечислим абстрактные структуры данных, с которыми мы чаще всего встречаемя — это, конечно же, лист, три, кью, стек, хип, дек. Ой... Т.е., я хотел сказать: список, дерево, очередь, куча, колода и... стек. Как-то так вышло, что у всех этих структур имена как имена, а вот стек какой-то особенный. Почему? Наверно, из-за лени, но не важно. Если заглянуть в словарь, то для английского слова "stack" можно найти 2 вполне подходящих перевода. Первый из них — стог :) По-моему, удивительный случай созвучности, и, по-своему, очень забавный вариант. Именно его я предложил использовать в качестве термина, когда речь идет об этой структуре данных, и он продержался практически до последней ревизии, однако, в последний момент все-таки был заменен на менее одиозный вариант стопки. Это тоже хороший перевод и с точки зрения соответствия реальности даже более адекватный, так что я остался доволен. Удивительно, почему он так редко встречается в литературе!

Но тут есть еще одна трудность: а как быть со стеком вызовов функций программы, который уже не абстрактная структура данных, а конкретное технологическое решение, вокруг которого есть еще и другие термины, типа "stacktrace"? Вот тут, конечно, намного труднее, и я остановился на том, что в данном случае, чтобы не создавать путаницы, лучше использовать устоявшийся термин, т.е. стек. Возможно, с прочным вхождением в обиход стопки, можно будет перенести этот термин и сюда: стопка вызовов — звучит банально. Зато никакой дополнительной случайной сложности :)

Вторым термином, которым я остался недоволен, был пул. Тут случай хуже, т.к. адекватного перевода его на русский и вовсе нет. Ну не бассейн же. Я так ничего и не придумал. Но, если у вас будут мысли на эту тему, делитесь...

Утилитарный Lisp
Вот как выглядит "клиент" (если для такого простого кусочка кода уместно столь громкое название) для набирающего популярность лог-сервера Graylog2 на современном Lisp'е: По-моему, этот кусочек кода неплохо развеивает миф о проблемах с библиотеками в Lisp-среде: в нашем пайплайне сначала сообщение сериализуется в JSON библиотекой cl-json, затем кодируется в байтовый поток babel, затем зипуется salza2, а затем отправляется через UDP-шный сокет usocket. А еще есть повод использовать прекрасную библиотеку для работу со временем local-time, основанную на статье Эрика Наггума. Ну и чуть-чуть синтаксического сахара из rutils, в том числе и буквальный синтаксис для хеш-таблиц (как в Clojure), модульно подключаемый с помощью named-readtables. Ничего лишнего.
ECL+Quicklisp=костыли

Известный факт: ECL поставляет свой, особенный ASDF. Другой факт: у Quicklisp'а своя версия ASDF, которую он загружает на старте.

Как же быть?

Можно загружать из сети системы с помощью другого лиспа, например SBCL, а в ECL загружать их уже старым добрым asdf:load-system.

Для этого можно воспользоваться простым алиасом.
alias ecl-ql='CL_SOURCE_REGISTRY='\''(:source-registry (:tree (:home "quicklisp/dists/quicklisp/software/")) (:tree (:home "quicklisp/local-projects/")) :inherit-configuration)'\'' ecl -eval "(require :asdf)"'
Теперь можно запускать ecl-ql и компилировать.

Ряд Фибоначчи

Давеча рекламировал свои обобщенные последовательности (Generic Sequences), а какие могут быть последовательности без ряда Фибоначчи? Это что-то вроде обязательного ритуала. Опустим здесь тот факт, что я создал эту библиотеку для вполне практической задачи, когда мне понадобилось быстро и эффективно сравнивать деревья, а там ленивые последовательности дюже полезны.

Итак, ниже приведена рабоче-крестьянская версия, которая выдает ленивую бесконечную последовательности ряда Фибоначчи через то, что я назвал Sequence Comprehension:

(defparameter *fibs-1*
(with-seq/cc
(do ((a 1 b)
(b 1 (+ a b)))
(nil)
(yield/cc a))))

Очень просто, не правда ли?

Теперь каноническая версия через поток:

(defparameter *fibs-2*
(reclet
((fibs (seq->stream
(seq-cons
1 (seq-cons
1 (seq-map
(lambda (x)
(+ (first x) (second x)))
(seq-zip
(delay-seq fibs)
(delay-seq (seq-cdr fibs)))))))))
fibs))

Проверка:

? (seq->list (seq-take 20 *fibs-1*))
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)

? (seq->list (seq-take 20 *fibs-2*))
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)

Дополнение.

Чтобы не сложилось неправильного впечатления, сейчас покажу наиболее эффективную реализацию, которая только возможна в рамках моей библиотеки.

(defparameter *fibs-3*
(make-seq
(labels ((traverse (a b)
(enum-cons a (traverse b (+ a b)))))
(traverse 1 1))))

Основная идея заключается в том, что мы работаем как с обычным списком, что очень удобно при обходе индуктивных/рекурсивных структур данных. Собственно, все комбинаторы написаны у меня в таком стиле.

И если вам по какой-то причине не нравятся комбинаторы, то результат можно получить с помощью известного макроса iter, для которого я добавил конструкцию in-seq:

? (iter (for i from 1 to 20)
(for x in-seq *fibs-3*)
(collect x))
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)
Обобщенные последовательности

Рекламирую свою новую библиотеку Generic Sequences [1] для Common Lisp. Она вводит обобщенные последовательности похожие на обычные списки Common Lisp, ленивые последовательности clojure, списки Haskell, а также похожие на итераторы, которые можно встретить в таких языках программирования как C#, F#, Java и Scala. С помощью комбинаторов легко создавать обобщенные последовательности, и их легко итерировать с помощью макроса ITER.

Более того, есть так называемое Sequence Comprehension, основанное на продолжениях из пакета CL-CONT. Это что-то похожее на синтаксис Sequence Expression из F# и конструкцию Yield из C#, где мы можем определить ленивую последовательность очень простым и декларативным способом.

В то же самое время, обобщенные последовательности могут быть очень легко преобразованы в ленивые потоки, которые широко распространены в мире функционального программирования. Помимо этого, такие потоки также трактуются как обобщенные последовательности. В дополнение к этому, стандартные списки и векторы Common Lisp тоже трактуются как обобщенные последовательности. Еще можно создавать свои последовательности, реализуя протокол из всего двух обобщенных функций.

Есть небольшая документация [2] в формате PDF.


Просто ещё один перевод

Перевод небольшой статьи (а точнее вводного курса) о Common Lisp'е. Если кто-нибудь захочет отредактировать, дополнить --- всегда рад. В соразработчики или пулреквест.

https://github.com/filonenko-mikhail/ub-lisp

К вопросу о долгосрочной надёжности систем, написанных на языке с динамической типизацией.
Есть у нас один продукт, написанный полностью на Коммон Лиспе - конфигуратор и супервизор наших же железкок на FPGA. Не сильно большой, 10к строк движка, UI и компиляторов DSL, плюс 7к5 строк на DSL. Но из-за того, что это сплошные "кластеры метапарадигм", как выразился аноним на ЛОРе, то каждое действие - это маленькое инженерное чудо: классы, код и интерфейсы генерируются и убиваются на лету, в памяти гоняются сотни мегабайт развесистых структур данных, всё такое сложное, динамичное и многопоточное, что аж зубы скрипят.

По заверению адептов языков со статической типизацией, такая система должна всё время падать из-за того, что вместо ожидаемых коров функция получает баранов. Компилятор-то не имеет возможности отловить такие несоответствия на этапе компиляции. И потом, через много дней, когда бараны придут вместо коров, то программисту будет совсем худо, ибо он уже всё забыл, и разбираться с таким багом будет очень сложно. Фигня всё это. Расскажу я вам про типичный баг в лиспософте.

У клиента через 49.7 дней аптайма софта отвалился внутренний механизм кэширования. В ходе анализа ситуации выяснилось, что для маркировки времени обновления кэша использовались встроенные лисповые часы, обновляющиеся 1000 раз в секунду. Лисповская функция, читающая часы, возвращает bignum, но из-за реализации внутренностей кэша от этого числа сознательно брались только 32 младших бита. Через 49.7 дней происходило переполнение, и кэш маркировался всегда устаревшим. Я подчёркиваю слово "сознательно", потому что код, делающий эту операцию со временем, был спецом так написан. И на момент написания 2 года назад он был логически правильным, но потом изменились требования, и код стал неправильным, но про него никто не вспомнил. Соответственно, это тупая алгоритмическая ошибка, и этот же алгоритм, переложенный на, скажем, Хаскель, воспроизводил бы ровно ту же самую ошибку.

А бараны вместо коров в реальной жизни никогда не приходят. Вот.
Рейтинг библиотек в Quicklisp репозитории
  Вообще говоря в движении opensource есть свои плюсы и минусы. Плюсов разумеется гораздо больше! :) Но есть и некоторые минусы. Один из них, например, - качестве библиотек никто не гарантирует и надо тратить время на исследования того, годная ли библиотека вообще для использования. Как с этим бороться? Во-первых, конечно же, нужно советоваться с коллегами, если кто-то получил драгоценный опыт использования какой-либо системы, то неплохо бы его перенять. А во-вторых гарантию качества даёт кол-во библиотек использующих интересующую вас систему. Вот об этом и пойдёт речь в этой заметке.
  Итак, я рад представить сообществу ASDF-систему для оценки рейтингов open-source библиотек из репозитория Quicklisp. Рейтинг системы в данном контексте будет ничем иным, как кол-вом библиотек, которые её используют. Инструкцию по использованию читайте здесь: https://github.com/LinkFly/ql-libs-analizing/blob/master/README_ru.

Сам репозиторий: https://github.com/LinkFly/ql-libs-analizing
Проект в Redmine: http://linkfly.ru:8201/redmine/projects/ql-libs-analizing (временно изменено, см. ниже)

Считаю, это крайне полезная система особенно для тех кто строит бизнес, с упором на использование opensource решений.
Предложения по развитию и баг-репорты пишите в проект на github'е или в Redmine.

P.S. Совершенно внезапно перестал работать 1gb.ru, вместе со своими DNS-серверами, поэтому ссылка на Redmine временно будет следующая: http://178.140.218.145:8201/redmine/projects/ql-libs-analizing
Проект LISP-DEV-TOOLS. Сервис для работы с проектом в Redmine.
    И вот теперь, когда я вновь "свободный художник" займусь вероятно своими open-source проектами:)
Что касается конкретно lisp-dev-tools: вообще говоря, цель достигнута - это удобный инструмент для автоматизации разворачивания инфраструктуры для разработки на Common Lisp, я собственно сам им и пользуюсь. Судите сами: есть (по каким-либо причинам) у вас чистая ОСь (ну прямо девственно-чистая), и вам нужно получить всё самое необходимое для разработки на CL, причём не просто так - а согласно современному состоянию развития open-source инструментария для работы с Common Lisp'ом. Но вы не хотите совершать "лишних телодвижений" (я вот например, их о-о-очень не люблю делать), чтобы получить всё необходимое и обязательно сразу. Если вы пользуетесь lisp-dev-tools, то (даже в каком-нибудь jail'e с кучей ограничений) вы делаете так:

git clone https://github.com/LinkFly/lisp-dev-tools.git
cd lisp-dev-tools
./provide-slime

... И получаете ВСЁ!
Но при этом есть возможность тонко настроить версии инструментов. Например, мне в ближайшем будущем точно понадобится фича в emacs 24-ой версии, позволяющая установливать дополнительные пакеты для Emacs, устанавливаемые в духе пакетной системы дистрибутивов Linux'a и пакетной системы в Quicklisp. Я тупо наугад подобрал версию Emacs'a которая у меня успешно загрузилась/скомпилировалась и установилась внутрь lisp-dev-tools (в репозитории используемого мной дистрибутива 24-ой версии соотв. не оказалось). Номер версии я поменял в lisp-dev-tools/conf/tools.conf.

Кроме того, я иногда заглядываю в исходники sbcl'a и в этом случае, мне недостаточно простой (и быстрой) установки бинарной сборки - в этом случае, я дополнительно делаю:

./rebuild-lisp.sh

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

Далее, время от времени, по некоторым причинам мне нужно использовать другую лисп-систему и/или другую версию используемой лисп-системы и всё решается мгновенно, например:

./change-lisp ecl
./change-version 12.7.1

В любой момент, я временно могу запустить, например тот же SLIME с другой Лисп-системой:

LISP=sbcl ./run-slime

И так далее и тому подобное ...

А теперь у проекта появился, скажем так: "свой дом" в виде Redmine'овском сервиса по управлению проектами:

http://linkfly.ru:8201/redmine/projects/lisp-dev-tools

Я уже вполне его успешно использую этот проект, но некоторые фичи я бы ещё добавил.  В общем это "без 5-ти минут" мощнейший инструмент корпоративного класса и если общественность обратит на него внимание, то в самое ближайшее время - реально довести проект до "мажорной версии" и рекомендовать к использованию в производственных условиях.

Репозиторий на github.com: https://github.com/LinkFly/lisp-dev-tools
Сглаженные шрифты для Stumpwm
#lisp 11:40 <ams> lisp is used to get shit done.

Итак сглаженные шрифты в стампвм. Бетаверсия. Для использования необходимо скачать clx-truetype и stumpwm (ветка release) из моего гитхаба. Xft, FreeType НЕ требуются, пуре лисп солюшн.


cd ~/quicklisp/local-projects
git clone https://github.com/filonenko-mikhail/stumpwm.git
git clone https://github.com/filonenko-mikhail/clx-truetype.git

Сделать кеш TrueType шрифтов.


sbcl
(ql:quickload :clx-truetype)
(xft:cache-fonts)

Затем указать нужный шрифт в ~/.stumpwmrc


(set-font (make-instance 'xft:font :family "Consolas" :subfamily "Regular" :size 12))

Затем запустить stumpwm из ~/.xinitrc


exec sbcl --eval "(ql:quickload :stumpwm)" --eval "(stumpwm:stumpwm)"

Поддержка несглаженных шрифтов никуда не делась, поэтому переключится обратно на них можно строкой в ~/.stumpwmrc


(set-font "-*-terminus-medium-r-normal-*-16-*-*-*-*-*-iso10646-1")

clx-truetype будет в следующей версии quicklisp-a.

FFI в Лиспворкс
В общем, потребовалось из лиспа общаться с железкой на MSP430, которая подключена к компу по USB и торчит в системе в виде ttyACM. Чтобы с оным агрегатом общаться, нужно, как минимум, установить бодрейт. В Лиспворксе есть пакет serial-port, который, к сожалению, доступен только под виндой, поэтому юниксоидам нужно делать дополнительные движения.

Сначала я решил не париться, и открыть пайп, на другом конце которого сидит cu из uucp и делает за меня всё tty-специфичное. Но на машинах, где это дело крутиться будет, uucp нет, а для его устанавки нужно делать много действий, которые включают в себя ответы на кучу фиктивных багрепортов. Ещё можно вызывать stty и устанавливать флажки им, а в софте использовать обычный open. Однако, на деле выяснилось, что стандартному open в Лиспворксе от открытия файла устройства в режиме :io плохеет. В общем, надо открывать устройство позиксовым open, крутить tty-ручки и создавать на его основе лисповый stream.

У LispWorks есть foreign language interface, с помощью которого можно описать сишечные функции, структуры, переменные, подгрузить библиотеку и прочие типичные для такой задачи действия, доступные, например, в оупенсорсных UFFI/CFFI. Соответственно, можно или написать обёртку на Си, которая открывает дескриптор, дёргает termios-вызовы и возвращает причёсанный дескриптор в лисп, или вскочить на коня, выхватить шашку и описать нужное подмножество termios.h при помощи FLI. Впрочем, при чтении документации на FLI выяснилась приятная неожиданность: в LW есть встроенный парсер сишных заголовков, который сам всё описывает. Вот мой пример с termios:

(require "foreign-parser")

(foreign-parser:process-foreign-file "/usr/include/termios.h" :dff "/path/to/project/termios.lisp" :package :unix)


Всё. Это даже круче, чем sb-grovel в SBCL! Единственное, что константы, объявленные препроцессором (через #define) автоматически не конвертятся. Ну да ладно.

А вот функция, открывающая в LW tty-девайс:

(defun open-device ()
  (let ((fd (sys::unix-open *dev* 2)))
    (fli:with-dynamic-foreign-objects ((term unix::termios))
      (unix::tcgetattr fd term)
      (unix::cfsetospeed term #o10004) ;; 460800
      (unix::tcsetattr fd 0 term)      ;; TCSANOW
      (unix::tcflush fd 2))            ;; TCOFLUSH
    (sys:attach-stream fd :direction :io :automatically-close t)))

Как сочетать функциональные языки и мейнстрим
Где-то с месяц назад меня позвали на киевскую тусовку функциональных программистов рассказать про практический опыт использования Clojure. В итоге я немного покритиковал Clojure, но в основном хотел сказать несколько о другом: о том, где ниша функциональных и других немейнстримных языков (например, Lisp'а), и как их можно использовать в сочетании с мейнстримными. Получилось, как всегда довольно сбивчиво, поэтому попробую изложить здесь яснее и структурированнее.

Вот видео:


А хотел сказать я всего-то 3 простые вещи, в которых нет ничего особенно нового, но от этого они, как по мне, не теряют своей ценности.

1. Философия Unix для веба


Если говорить о серверной разработке, то самым эффективным подходом к построению масштабируемых систем (как в смысле нагрузки, так и трудоемкости их развития) был и остается Unix way:
small pieces, loosely joined, that do one thing, but do it well

Только в отличие от классики Unix, теперь эти кусочки живут в рамках отдельных узлов сети и взаимодействуют не через pipe, а через сетевые текстовые интерфейсы. Для того, чтобы организовать такое взаимодействие существует ряд простых, надежных, хорошо масштабируемых и, что очень важно, де-факто стандартных и языконезависимых средств. Под разные задачи эти средства разные, и они включают:
  • низкоуровневые механизмы взаимодействия: сокеты и ZeroMQ

  • высокоуровневые протоколы взаимодействия: HTTP, SMTP, etc.

  • форматы сериализации: JSON и еще десяток других

  • точки обмена данными: Redis, разные MQs
Это не REST и не SOA в чистом виде, скорее перечисленные схемы являются несколько специализированными, а иногда и ушедшими сильно в сторону ппримерами воплощения этого подхода. Это не более и не менее, чем инструментарий, поверх которого можно построить любую сетевую архитектуру — от централизованной до P2P.

2. Требования к языкам


Когда программисты сравнивают между собой разные языки, они, как правило, подходят к задаче не с той стороны: от возможностей, а не от требований. Хотя работа в индустрии должна бы была их научить обратному. :) Если же посмотреть на требования, то их можно разделить на несколько групп: требования к языкам для решения неизвестных (исследовательских) задач существенно отличаются от требований к языкам для реализации задач давно отработанных и понятных. Это классическая дихотомия R&D — research vs development — исследования vs инженерия. Большинство задач, с которыми мы сталкиваемся — инженерные, но как раз самые интересные задачи, как с точки зрения профессиональной, так и экономической — исследовательские. Также отдельно я выделяю группу требований для скриптовых языков.

Требования к языкам для исследований

  • Интерактивность (минимальное время цикла итерации)

  • Поддатливость и гибкость (решать задачу, а не бороться с системой)

  • Хорошая поддержка предметной области исследований (если это математика — то хотя бы Numeric Tower, если статистика — то хорошая поддержка матриц, если деревья — то инструменты работы с деревьями и первоклассная рекурсия, и т.д.)

  • Возможность решать задачу на языке предметной области (заметьте, что специфические исследовательские языми — всегда DSL'и)

Требования к языкам для решения стандартных задач

  • Поддерживаемость (возможность легко передать код от одного разработчика другому)

  • Развитая экосистемы инструментов и хорошая поддержка платформы

  • Стабильность и предсказуемость (как правило, мало кто любит истекать кровью на bleeding edge, поэтому выбирают то, что работает просто, но без особых проблем, проверенное)

  • И, порой самое важное — возможность получить быстроработающий результат (подчас скорость работы отличает решение, которое пойдет в продакшн, от того, которое не пойдет)

Требования к скриптовым языкам

  • Первое и основное — хорошая интеграция с хост-системой (оптимизация языка под наиболее часто выполняемые операции в хост-системе)

  • Простота и гибкость (я еще не слышал ни об одном статически типизированном скриптовом языке :)

  • Минимальный footprint (с одной стороны вся тяжелая работа может делаться на стороне хост-системы, с другой стороны — обычно ресурсы ограниченны и очень мало смысла тратить их на ненужное)

Очень много можно рассуждать о том, какие требования стояли во главе угла при создании тех или иных языков, как языки эволюционируют и т.д. Ограничусь лишь тем, что выделю группу языков, которые однозначно создавались чисто для исследовательской работы — это Matlab, Octave, Mathematica, R, Prolog и разные вариации на тему. Слабость таких языков обычно в том, что в них не были заложены общеинженерные механизмы (прежде всего, первоклассная поддержка взаимодействия с другими системами, которые живут за пределами их "внутреннего" мира).

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

Если предаставить эти требования в виде декартовых координат, и расположить на них языки, и обевсти самую интересная область, в нее попадет совсем немного языков — раз-два и обчелся. Прежде всего, это Lisp, также Python, и, может быть, еще пара-тройка.



3. Выбор языка под задачу, а не под платформу


Возвращаясь к нашему Unix'у в облаках, отдельные компоненты этой системы могут быть написаны на любом языке (также, как и на обычном Unix'е) и даже работать на любой платформе. Это дает возможность решать специфические задачи тем инструментом, который подходит лучше всего. И среди всего спектра задач преобладают в основном такие, которые, по большому счету все равно, на каком языке делать. Для этих задач обычно самыми главными критериями выбора являются экосистема инструментов и в половине случаев скорость работы результата (во всяком случае в долгосрочном плане).

Но не все задачи такие: есть много разных областей, в которых мейнстримные языки работают плохо или же фактически не работают вообще. Известный афоризм на этот счет — 10е правило Гринспена. Соответственно, если вы хотите использовать Lisp, Haskell или Factor — решайте на них те задачи, на которых они дают очевидное преимущество, и делайте их полноценными гражданами в облачной экосистеме. Так вы на практике, а не в теории сможете доказать их полезность скептикам, и в то же время будут развиваться как знания остальных программистов о них, так и инструментарий этих языков (по которому они часто проигрывают мейнстримным аналогам). Таким образом, в будущем они получат возможность рассматриваться как кандидаты для решения и других задач, для которых их преимущества не столько очевидны (в 2-3 раза, а не на порядок).

P.S. Пару слов о Clojure


В выступлении я много сравнивал Erlang и Clojure. Оба эти языка делают упор на конкурентную парадигму разработки. Но Erlang в этом смысле стоит особняком от других функциональных языков, поскольку конкурирует с императивными языками не столько на уровне качества языка для решения конкретных задач, сколько как язык-платформа, создающий новую парадигму решения задач за рамками отдельного процесса и отдельной машины. Таким образом, его главная ценность — это роль системного языка для распределенных систем.

Что касается Clojure, то я в шутку разделил все языки на фундаментальные и хипстерские. Фундаментальные языки (такие как C, Lisp, Erlang, Haskell, Smalltalk) появляются, когда группы умных людей долго работают над сложными проблемами и в процессе создают не просто язык, а целую парадигму. В то же время хипстерские языки являются продуктом обычно одного человека, который хочет здесь и сейчас получить самое лучшее из нескольких языков сразу, гибрид. Я перечислял такие примеры, как C++ (C + классы + еще куча всего, понадерганного с разных сторон) — это, пожалуй, архетипный хипстерский язык,— Ruby (Perl + Smalltalk + Lisp), JavaScript (C + Scheme), который со времени пояления V8 и node.js перешел из категории скриптовых языков в общесистемные. Кстати, в большинстве случаев языки второго типа более успешны в краткосрочном плане и завоевывают мир. Точнее, их мировое господство чередуется с господством языков, которые стоят в этом спектре где-то посередине: когда люди устают от подобных гибридов, их в конце концов "побеждают" более здравые варианты. Java вместо C++, Python вместо Ruby (для веба), посмотрим, что будет вместо JS. К сожалению, Clojure — яркий пример такого гибрида: это попытка скрестить Lisp с Haskell'ем, да еще и на Java-основе...
Сглаженные курсоры для CLX

Раз пошла такая пьянка, вот ещё библиотечка для красивых курсоров для CLX. Поддерживает темы, и анимированные курсоры. https://github.com/filonenko-mikhail/clx-cursor

Сглаженные шрифты в CLX
Зарелизил библиотечку: http://filonenko-mikhail.github.com/clx-truetype/.
Никаких внешних зависимостей.
Снимок экрана в stumpwm

Создание снимков экрана/окна для stumpwm на чистом коммон лиспе с использованием библиотеки zpng, т.е. поддерживается экспорт только в png формат.

Использовать так для всего экрана так:

prefix : screenshot RET filename.png RET

для текущего окна так:

prefix : screenshot-window RET filename.png RET

Knowledge Brings Fear
Значит, есть такая мечта детства: самообучающийся и самодописывающийся лиспокод на ходу синтезирует схему, которая на ходу же заливается в ПЛИС. Всё это кладётся в примерно такого железного посланца мира и любви:



Лисп немного осилил, учу в меру ленивости Verilog. Букварь о 800-страницах ещё и до середины не пролистан, но вчера, на ночь глядя, кривыми интернетными тропками вспомнил, что не знаю, как работает целочисленное умножение в процессоре. Решил просветиться.

Собственно, два способа умножения знает любой школьник, а пишущий демки на ассемблере знает и третий:

  1. Дважды-два - четыре. Т.е. заучивается таблица умножения. Компьютер может позволить себе иметь таблицу для параметров не только одноразрядных, но и  чуток побольше. Сложность O(1).
  2. X*Y можно получить, если X в цикле сложить Y раз. Сложность O(N).
  3. Множитель можно разложить на двойки и единицы и использовать их для бинарного сдвига и сложения. Сложность не знаю какая.
Википедия говорит, что очень хорош собой алгоритм Карацубы, который обладает сложностью O(nlog23). Перескажу его кратко:

Нужно перемножить два двухзначных числа, допустим, 12 и 34. Для этого разбиваем числа по разрядам, получаем x1 = 1, x2 = 2, y1 = 3, y2 = 4. Находим:

    A = x1 * y1.
    B = x2 * y2.
    C = (x1 + x2) * (y1 + y2).
    K = C - A - B

Результат умножения получается так: 100 * A + 10 * K + B. Очень просто, в принципе.

Для начала я написал алгоритм на Лиспе. Т.к. дело было ночью, плюс клепание "настоящего" энтерпрайзного софта на работе от таких задач отличается достаточно сильно, то я протупил часа три. Но вот что получил для умножителя 8 на 8 бит:

multx.lisp
(defvar *table* (loop for x from 0 below 8
collect (loop for y from 0 below 8
collect (* x y))))

(defun multiply (x y)
(labels ((vectorize (x &optional (n 4))
(reverse (loop for i = x then (ash i -4)
repeat n
collect (logand i #xf))))
(table-lookup (x y)
(nth x (nth y *table*)))
(trivial-mult (sx sy)
(let* ((x1 (ash sx -2))
(x2 (logand sx 3))
(y1 (ash sy -2))
(y2 (logand sy 3))
(a (table-lookup x1 y1))
(b (table-lookup x2 y2))
(c (table-lookup (+ x1 x2) (+ y1 y2)))
(k (- c a b)))
(+ (ash a 4) (ash k 2) b)))
(vector-multiply (x y)
(loop for x1 in x
for i in '(12 8 4 0)
sum (ash (loop for y1 in y
for i in '(12 8 4 0)
sum (ash (trivial-mult x1 y1) i))
i))))
(vector-multiply (vectorize x) (vectorize y))))

(multiply 12 34) => 408


Табличка умножения 8 на 8 нужна для выполнения внутренних умножений в самом алгоритме. На самом деле, таблица нужна 4 на 4, т.к. размер разряда я принял в 2 бита, но в ходе отладки обнаружилось, что при вычислении C происходит выход за пределы таблицы, поэтому я её малодушно сделал в два раза больше по обоим измерениям.

Следующим шагом было переписывание того же самого на Верилоге. В оном языке, как и в Лиспе, умножение присутствует из коробки, но ради обучения  сей факт проигнорировал, конечно. Значит, вот вымученный 8-битный умножитель (размер разряда у числа - 4 бита):

123
module Multiplier8x8 (x, y, q, clk);
input clk;
input [7:0] x, y;
output [15:0] q;

reg [15:0] q;
reg [7:0] a, b;
reg [11:0] c, k;
wire [3:0] x1, x2, y1, y2;
wire [4:0] cx, cy;

reg [15:0] tbl [0:1023];
wire [4:0] x1l, x2l, y1l, y2l;

initial begin
$readmemb("mult2.tbl", tbl);
end

assign {x1, x2} = x;
assign {y1, y2} = y;
assign cx = x1 + x2;
assign cy = y1 + y2;
assign x1l = x1;
assign x2l = x2;
assign y1l = y1;
assign y2l = y2;

always @ (posedge clk) begin
a <= tbl[{x1l, y1l}];
b <= tbl[{x2l, y2l}];
c <= tbl[{cx, cy}];
q <= (a << 8) + (k << 4) + b;
end

always @ (negedge clk) begin
k <= c - a - b;
end
endmodule

Для внутреннего умножения тоже используется таблица, но размером 32x32 (5 на 5 бит). Генерируется вот таким лиспокодом:

mult-gen.lisp
(with-open-file (f "~/src/verilog/mult2.tbl"
:direction :output
:if-exists :supersede
:element-type 'character)
(dotimes (i 32)
(dotimes (j 32)
(format f "~16,'0b~%" (* i j)))))

Сверхкраткий ракурс в Verilog.

Логика абстрагируется в модуле. У модуля есть входные и выходные параметры. У параметров есть разрядность в битах. Параметры могут быть проводами (wire) или регистрами (reg). Провода от регистров отличаются тем, что первые не хранят значение, а вторые - хранят. Соответственно, выход провода меняет значение одновременно с входом, а регистр выступает в роли защёлки-триггера (которому нужна опорная тактовая частота). Это если очень-очень просто.

assign соединяет провода. assign {x1, x2} = x; разбирает 8-битный x на 4-битные x1 и x2 (фигурные скобки - оператор конкатенации). assign cx = x1 + x2; складывает 4-битные x1 и x2, а 5-битный результат присваивает cx. assign x1l = x1; расширяет 4-битный x1 до 5-битного x1l с нулём в старшем бите.

always @ (posedge clk) срабатывает, когда сигнал опорной частоты clk изменяется с 0 на 1 (передний фронт). always @ (negedge clk) срабатывает, соответственно, наоборот: с 1 на 0 (задний фронт).

В Верилоге есть операции, которые не могут быть синтезированы в железо (например, чтение файла), но их удобно использовать для отладки и симуляции.

Значит, вычисление A, B и C прямолинейно и понятно. Единственное, что стоить отметить: т.к. аргументы у нас 4-битные, а таблица умножения построена для 5-битных множителей из-за переполнения при вычислении C, плюс она является одномерным массивом размерностью 2^(5 + 5), то x1, x2, y1 и y2 расширены до 5 бит. cx и cy (суммы x1 + x1 и y1 + y2) и так 5-битные.

Вкусность программирования под железо заключается в массивном параллелизме. Все операции в коде выполняются одновременно, кроме кода в разных блоках always. Внутри always код тоже полностью параллельный, но K не может быть вычислен одновременно с C, A и B. Поэтому K нужно вынести либо в другой такт, либо повесить его вычисление на спад clk. Таким образом, умножение двух восьмибитных чисел происходит за один такт.

На самом деле, при программировании под реальную железяку вылезет море проблем. Например, tbl смотрится одновременно с тремя наборами параметрами, и для такой возможности нужно иметь, как-минимум, 3-портовую память. Или использовать 3 одинаковые таблицы.

Тестбенч для умножителя:
123
module test;
reg clk = 0;
always #1 clk = ~clk;

wire [15:0] q;
reg [7:0] x, y;

initial begin
$dumpfile("test.vcd");
$dumpvars(0, test);

x = 123;
y = 255;

# 4 $finish;
end

Multiplier8x8 m (x, y, q, clk);
endmodule
Ложим оба модуля в один файл, компилируем Икарусом, выполняем, прогоняем через gtkwave:

$ iverilog mult.v && ./a.out && gtkwave test.vcd



Теперь применим всю мощь массового параллелизма и сделаем на основе 8-битных умножителей один 16-битный. Для этого всего лишь нужно сделать матрицу 2 на 2:
123
module Multiplier16x16 (x, y, q, clk);
input clk;
input [15:0] x, y;
output [31:0] q;

wire [31:0] q;
wire [15:0] v11, v12, v21, v22;

Multiplier8x8 m11 (x[7:0], y[7:0], v11, clk);
Multiplier8x8 m12 (x[7:0], y[15:8], v12, clk);
Multiplier8x8 m21 (x[15:8], y[7:0], v21, clk);
Multiplier8x8 m22 (x[15:8], y[15:8], v22, clk);

assign q = (((v22 << 8) + v21) << 8) + (v12 << 8) + v11;
endmodule

Матрица собирается тоже за один такт, если верить симуляции:
123
module test;
reg clk = 0;
always #1 clk = ~clk;

wire [31:0] q;
reg [15:0] x, y;

initial begin
$dumpfile("test.vcd");
$dumpvars(0, test);

x = 12345;
y = 43210;

# 4 $finish;
end

Multiplier16x16 m (x, y, q, clk);
endmodule



И, чтобы совсем заставить рыдать публику, которой обсчёт матрицы 8 на 8 - это нифига не бесплатно, вот 32-битный умножитель на том же принципе, что и 16-битный:
123
module Multiplier32x32 (x, y, q, clk);
input clk;
input [31:0] x, y;
output [63:0] q;

wire [63:0] q;
wire [31:0] v11, v12, v21, v22;

Multiplier16x16 m11 (x[15:0], y[15:0], v11, clk);
Multiplier16x16 m12 (x[15:0], y[31:16], v12, clk);
Multiplier16x16 m21 (x[31:16], y[15:0], v21, clk);
Multiplier16x16 m22 (x[31:16], y[31:16], v22, clk);

assign q = (((v12 << 16) + v11) << 0) + (((v22 << 16) + v21) << 16);
endmodule
В качестве множителей использованы микрософтовские константы BIG BOOBS и BOOBIES, которые вызвали такие волны околосексистких говен в этих ваших интернетах:
123
module test;
reg clk = 0;
always #1 clk = ~clk;

wire [63:0] q;
reg [31:0] x, y;

initial begin
$dumpfile("test.vcd");
$dumpvars(0, test);

x = 32'hB16B00B5;
y = 32'h0B00B1E5;
# 4 $finish;
end

Multiplier32x32 m (x, y, q, clk);
endmodule


Проверяем результаты в Лиспе:
123
(format nil "~x" (* 123 255)) => "7A85"
(format nil "~x" (* 12345 43210)) => "1FCB74FA"
(format nil "~x" (* #xB16B00B5 #x0B00B1E5)) => "7A014517734C6E9"
Ура! :)

Распознание лица года три назад ещё на Лиспе написал, так что Терминатор, практически, готов! На следующих выходных поставлю на шасси от детской коляски старый вольвовский аккумулятор, стартер, вебкамеру, альтеровский девкит и палку.

Поиск документации по Common Lisp-овым символам

Хочу напомнить, что наиболее удобным/быстрым способом поиска документации по стандартным символам Common Lisp'а является GNU'шная система справки texinfo, которая отлично поддерживается emacs'ом.

Для того, чтобы всё заработало, нужно:

  • Скачать dpans2texi-1.05.tar.gz
  • Выполнить

    cd dpans2texi-1.05
    ./configure
    make wget
    make
  • Поправить емаксовый конфиг. Строку "/path/to/dpans2texi-1.05" поменять на свою.

    (require 'info-look)
    (setq Info-additional-directory-list '("/path/to/dpans2texi-1.05"))

    (eval-after-load "slime"
    ;; register info help (dpans2texi)
    (progn
    (info-lookup-add-help
    :mode 'lisp-mode
    :regexp "[^][()'\" \t\n]+"
    :ignore-case t
    :doc-spec '(("(ansicl)Symbol Index" nil nil nil)))

    (info-lookup-add-help
    :mode 'slime-repl-mode
    :regexp "[^][()'\" \t\n]+"
    :ignore-case t
    :doc-spec '(("(ansicl)Symbol Index" nil nil nil)))

    (defvar slime-old-documentation-lookup-function
    (if (boundp 'slime-documentation-lookup-function)
    slime-documentation-lookup-function))

    (defun slime-ansicl-lookup (symbol-name)
    (interactive (list (slime-read-symbol-name "Symbol: ")))
    (info-lookup-symbol symbol-name 'lisp-mode))

    (setq slime-documentation-lookup-function 'slime-ansicl-lookup)
    (setq slime-ansicl-lookup (symbol-function 'slime-ansicl-lookup))))

Теперь, чтобы просмотреть справку по символу, нужно всего лишь на искомом слове нажать стандартное слаймовское сочетание клавиш C-c C-d h.

Stumpwm модуль сохранения раскладок клавиатуры между окнами

Введение

Долгое время переключаясь между фаерфоксом, скайпом и емаксом испытывал неудобство в постояной необходимости переключать раскладку клавиатуры, так как состояние раскладки было глобальным для всех окон. С задачей сохранения раскладки для каждого окна прекрасно справляется программа perWindowLayoutD. Однако это целый процесс со своим циклом сообщений, съедающий пусть небольшие но ресурсы компьютера. То ли дело подключиться слаймом к stumpwm, и добавить нужный функционал. Посмотрев на исходный код вышеназванной программы, я сделал вывод о том, что для работы с раскладкой клавиатуры требуется всего пару функций: XkbGetState и XkbLockGroup, которые находятся в библиотеке Xkblib, которая входит в пакет libx11. XkbGetState возвращает текущую раскладку, XkbLockGroup устанавливает указанную. К ним-то и нужно получить доступ из stumpwm. Но сначала обо всём по порядку.

Графическая система X

Из википедии X Window System (Иксы)

X Window System использует клиент-серверную модель: X-сервер обменивается сообщениями с различными клиентскими программами. Сервер принимает запросы на вывод графики (окон) и отправляет обратно пользовательский ввод (от клавиатуры, мыши или сенсорного экрана). X-сервер может быть:

  • системной программой, контролирующей вывод видео на персональном компьютере;
  • приложением, отображающим графику в окно какой-то другой дисплейной системы;
  • выделенным компонентом аппаратного обеспечения.

Статья об Иксахhttp://rus-linux.net/papers/xwin/X-Window.html

http://rus-linux.net/papers/xwin/X-Window_html_m1cb95d2e.png

Архитектура системы X Window

В данном случае сервер является механизмом отрисовки окон и передаёт события от устройств ввода. А клиент, подключившись к серверу, обрабатывает присланные события и указывает что и как нарисовать.

Любое приложение, которое хочет предоставить графический интерфейс, является клиентом икс сервера.

Протокол общения между клиентом и сервером состоит из следующих пакетов:

Запрос
клиент требует нарисовать что-либо в окне или запрашивает у сервера информацию;
Ответ
сервер отвечает на запрос;
Событие
сервер сообщает клиенту о событии (например, о нажатии клавиши пользователем);
Ошибка
сервер сообщает об ошибке.

X-сервер состоит из набора расширений, каждое из которых реализует определённые функции: от прорисовки геометрических примитивов до ускорения обработки и вывода на экран трёхмерной графики с использованием возможностей видеоаппаратуры. Почти каждый из этих модулей можно отключить или настроить в конфигурационном файле.

Описание базового протокола и расширений расположены по адресу http://www.x.org/releases/X11R7.6/doc/

Стандартный протокол: http://www.x.org/releases/X11R7.6/doc/xproto/x11protocol.pdf

Помимо стандартного протокола существует расширение XKeyboard, которое позволяет более гибко работать с клавиатурой. Оно-то мне и необходимо для того, чтобы сохранять и восстанавливать раскладку.

Протокол XKeyboard: www.x.org/docs/XKB/XKBproto.pdf

Данное расширение и реализует вышеназванные функции: XkbGetState и XkbLockGroup.

Сишники и не только они могут уже готовые клиентские библиотеки: низкоуровневые libx11 или xcb, высокоуровневые gtk, qt (ну эти так за компанию привёл).

Коммон лисперы (помимо биндингов к вышеназванным библиотекам) могут использовать написаную только на лиспе библиотеку clx, которая, мне кажется, берёт начало ещё в genere. С одной стороны clx реализует только базовый протокол. С другой стороны она содержит API для создания расширений.

clx также используется менеджером окон Stumpwm. Хотя он у меня уже больше похож на окружение, чем на просто менеджер.

Итак, после беглого просмотра исходников xkblib и clx я решил, что напишу:

  • маленькую часть расширения XKeyboard для clx
  • модуль для Stumpwm, который будет сохранять раскладки между окнами

Далее будут идти подробности моей работы, но пользователи Stumpwm могут сразу перейти к разделу "Установка".

CLX

Работа с библиотекой CLX проще-простого:

  • открыть дисплей
  • выполнить рисование
  • циклично обработать события
  • закрыть дисплей

Документация: http://www.stud.uni-karlsruhe.de/~unk6/clxman/contents.html

Расширение XKeyboard для clx

В целом написание расширения для clx состоит из следующих определений:

расширение
макрос define-extension
ошибки
макросы define-condition и define-error
типы данных
макросы deftype и define-accessor
необходимые константы
defconstant
события
макросы define-event и declare-event
функции для запросов/ответов
макросы with-buffer-request, with-buffer-request-and-reply

Создаём новый проект с помощью quickproject.

В зависимостях только библиотека clx.

В папке clx-xkeyboard автоматически будут сгенерированы три файла:

xkeyboard.asd
содержит asdf систему для загрузки данной библиотеки
package.lisp
содержит определение коммон лиспового пакета
xkeyboard.lisp
содержит основные наши функции
README.txt
здесь всё понятно

Необходимо отметить, что дальнейшая работа будет происходить в clx-овом пакете :xlib, поэтому файл package.lisp, можно очистить.

Для простоты в некоторые моменты можно пользоваться xml спецификацией протокола XKeyboard: http://cgit.freedesktop.org/xcb/proto/plain/src/xkb.xml

Приступим к непосредственно рутине. В файле xkeyboard.lisp добавим:

Последняя строка добавляет простой ключевой символ в глобальную переменную features. Таким образом мы рассказываем другим лисповым системам о своём существовании, мало ли чья-нибудь программа захочет воспользоватся XKeyboard расширением.

Определяем расширение, важно написать имя заглавными буквами, также как в спецификации:

В данном виде мы указываем, что для ошибок при работе с XKeyboard использовать тип условия xkeyboard-error.

Далее определяем условие и указываем это для clx:

Определяем новые типы, сначала для коммон лиспа, затем для clx:

Вспомогательные макросы для определения синонимов типов:

Указываем для clx синонимы типов:

Каждый пакет-запрос от клиента к серверу содержит код операции или, проще говоря, номер функции. Коды операций для базового протокола прописаны жестко. Коды операций для расширений также жёстко прописаны, но при работе должны увеличиваться на величину выдаваемую сервером для каждого расширения отдельно.

Создаём список кодов для запросов:

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

Задаём версию расширения:

Для того, чтобы клиент мог вызывать функции расширения, он сначала для своего сеанса должен его включить. Это производится запросом UseExtension.

Его спецификация выглядит так:

SizeType or ValueName
1??opcode
10xkb-opcode
22request-length
2CARD16wantedMajor
2CARD16wantedMinor
11Reply
1BOOLsupported
2CARD16sequence number
40reply length
21serverMajor
20serverMinor
20unused

Теперь подключение к иксам может выглядеть так:

Основные два макроса для взаимодействия с сервером:

  • для отправки запроса и получения ответа with-buffer-request-and-reply
  • для только отправки запроса with-buffer-request

Macros with-buffer-request-and-reply
         (buffer opcode reply-size &key sizes multiple-reply inline)
                       type-args &body reply-forms

В аргумент buffer передаётся открытый с помощью open-display дисплей.

opcode
является приращением для номеров функций для используемого расширения.
reply-size
указывает на размер принимаемого ответа по идее в битах.
sizes
содержит размеры отправляемых полей ….
type-args
содержит формы по отправке данных запроса; может также содержать любой исполняемый код; данные будут отосланы в той последовательности, в которой вызывались формы
reply-forms
содержит формы по получению данных ответа; может также содержать любой код; при получении данных нужно указывать смещение относительно начала пакета

Итак теперь функция XkbGetState. Вот как она выглядит для пользователя Xkblib http://www.x.org/releases/X11R7.7/doc/libX11/XKB/xkblib.html#Determining_Keyboard_State

typedef struct {
unsigned char group; /* effective group index */
unsigned char base_group; /* base group index */
unsigned char latched_group; /* latched group index */
unsigned char locked_group; /* locked group index */
unsigned char mods; /* effective modifiers */
unsigned char base_mods; /* base modifiers */
unsigned char latched_mods; /* latched modifiers */
unsigned char locked_mods; /* locked modifiers */
unsigned char compat_state; /* effective group => modifiers */
unsigned char grab_mods; /* modifiers used for grabs */
unsigned char compat_grab_mods; /* mods used for compatibility mode grabs */
unsigned char lookup_mods; /* modifiers used to lookup symbols */
unsigned char compat_lookup_mods; /* mods used for compatibility lookup */
unsigned short ptr_buttons; /* 1 bit => corresponding pointer btn is down */
}
XkbStateRec
*XkbStatePtr;

Status XkbGetState ( display , device_spec , state_return )
Display * display ; /* connection to the X server */
unsigned int device_spec ; /* device ID, or XkbUseCoreKbd */
XkbStatePtr state_return ; /* backfilled with Xkb state */

А вот она же но в спецификации протокола:

SizeType or ValueName
1??opcode
14xkb-opcode
22request-length
2KB_DEVICESPECdeviceSpec
2unused
11Reply
1CARD8deviceID
2CARD16sequence number
40length
1SETofKEYMASKmods
1SETofKEYMASKbaseMods
1SETofKEYMASKlatchedMods
1SETofKEYMASKlockedMods
1KP_GROUPgroup
1KP_GROUPlockedGroup
2INT16baseGroup
2INT16latchedGroup
1SETofKEYMASKcompatState
1SETofKEYMASKgrabMods
1SETofKEYMASKcompatGrabMods
1SETofKEYMASKlookupMods
1SETofKEYMASKcompatLookupMods
1unused
2SETofBUTMASKptrBtnState
6unused

Начнём со структуры, которая будет возвращаться пользователю. Тип полей структуры взят из спецификации протокола.

Теперь функция:

Теперь определим функцию XkbLockGroup. Для пользователя она выглядит так: http://www.x.org/releases/X11R7.7/doc/libX11/XKB/xkblib.html#Changing_Groups

Bool XkbLockGroup ( display, device_spec, group )
Display * display ; /* connection to the X server */
unsigned int device_spec ; /* device ID, or XkbUseCoreKbd */
unsigned int group ; /* index of the keysym group to lock */

Внутри себя она содержит вызов XkbLatchLockState, которая описана так:

SizeType or ValueName
1??opcode
15xkb-opcode
24request-length
2KB_DEVICESPECdeviceSpec
1SETofKEYMASKaffectModLocks
1SETofKEYMASKmodLocks
1BOOLlockGroup
1KB_GROUPgroupLock
1SETofKEYMASKaffectModLatches
1SETofKEYMASKmodLatches
1unused
1BOOLlatchGroup
2INT16groupLatch

Функция не трубет ответа от сервера, поэтому воспользуемся макросом with-buffer-request

Теперь определим lock-group

Ну что же, как я уже и говорил текущую раскладку можно получить из поля locked-group структуры device-state, а установить с помощью функции lock-group.

Поэтому теперь пришло время патчить Stumpwm.

Модуль для Stumpwm

Документация Stumpwm: http://stumpwm.org/manual/stumpwm.html#NOD1

Я разместил исходный код в папке clx-xkeyboard/test/stumperwindowlayout.lisp

Проверка загрузки расширения, переключение в пакет stumpwm:

Функция для получения текущей раскладки клавиатуры:

Теперь вообще элементарные вещи остались. Определим функцию-ловушку переключения фокуса между окнами:

В stumpwm:*display* хранится текущий дисплей, для которого и выполняется задача управления окнами.

Аргументы window и previos-window содержат соответственно окна получившее и отдавшее фокус. Структура окна определена в stumpwm, нам понадобиться её поле с xlib'овской структурой — (window-xwin previous-window). У каждого окна есть свой список свойств: добавим туда свойство :keyboard-layout.

Сохранение раскладки для предыдущего окна производится формой: (setf (getf (xlib:window-plist (window-xwin previous-window)) :keyboard-layout) current-layout)

Установка раскладки для окна, получившего фокус, производится формой: (xlib:lock-group *display* :group window-layout)

Следует отметить, что при переключении между рабочими столами, фокус предыдущего окна не теряется и параметр previous-window будет равен nil. Необходимо проигнорировать эту ситуацию и отловить событие переключения между рабочими столами:

Теперь определим команды включения и выключения режима запоминания раскладки. Это делается с помощью макроса stumpwm:defcommand.

Установка

Необходимо скопировать репозитарий

git clone http://github.com/filonenko-mikhail/clx-xkeyboard.git --depth 1

А затем в ~/.stumpwmrc добавить строки:

(? 'вопрос)
А вот можно ли сделать такой хак, чтобы в общелиспе при бросании ошибки можно было бы эту ошибку "заметить", не раскручивая стэк, сделать что-нибудь, типа пометки в логе, и пусть эта ошибка идёт дальше? Идеально подошёл бы unwind-protect с доступом к объекту ошибки в cleanup-form, но я что-то в Лиспворксе, немного покопавшись, не нашёл, как такое сделать.

Может, кто-нибудь на свободных лиспах такое делал?
@2009-2013 lisper.ru