Russian Lambda Planet

27 августа 2016

swizard

Трамплины и продолжения

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

Давайте, например, посмотрим на такие платформы: 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, я бы не писал этот текст, а вместо этого сделал бы что-нибудь полезное.

27 августа 2016, 03:19

nponeccop

Когда GHC FFI недостаточно быстр - лепим примопсы

Чувак дабы избавиться от оверхеда говномаршаллинга при FFI, генерит как я понял из Ragel Си, из сей - LLVM assembly, а оный ассемблер хачит седом, дабы получился примопс непосредственно с коллинг конвеншеном STG:

http://breaks.for.alienz.org/blog/2012/05/23/ffi-vs-primops/
http://breaks.for.alienz.org/blog/2012/02/09/parsing-market-data-feeds-with-ragel/

27 августа 2016, 02:29

caml_programmer

Заколхозил тест ввода/вывода для всех языков программирования

Вот такая ситуация пока получается.



https://github.com/dmsoftware/cats

Haskell и SBCL рисовать не стал, они оба где-то 2m50s отрабатывают,
и масштаб графика сильно портят. Ну Haskell там монады из себя
высасывает, а SBCL-то что капризничает?

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

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

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

27 августа 2016, 00:47

24 августа 2016

rssh

SE-2016 и Objective-C++

Занимаюсь сейчас подготовкой к выступлению на SE-2016 https://se2016.inhacking.com/ - буду рассказывать о эволюции языков программирования и современном ландшафте области [Киев, 3 сентября]. Давно хотел куда-то вставить о Objective-C++ , думал в этом выступлении, но получается и так слишком много материала, непонятно удастся ли включить и эту тему(?). Напишу пока в ЖЖ. Objective-C++ это первый язык, который возник "случайно", "сам по себе".

Сам Objective-C - это препроцессор над C, который написан Smalltalk. Его автор (Brad-Cox [блог: http://bradjcox.blogspot.it/ ; вот еще интервью с ним: http://www.mactech.com/articles/mactech/Vol.25/25.07/2507RoadtoCode-BradCoxInterview/index.html ] перетащил из Smalltalk OO-часть, что-бы можно было писать "как на Smalltalk" без медленного интерпретатора и сбора мусора, но с OO-dispath. Далее, компилятор внизу (gnu gcc или clang) может понимать как C, так и С++, следовательно если через препроцессор прогнать C++ класс, то С++ классы останутся классами, а Objective-C конструкции преобразуются в наборы вызовов C-функций. Некоторые разработчики обнаружили, что довольно удобно UI объекты представлять как Objective-C интерфейсы, а внутренние "не-UI" логику - C++ классами. Apple, следуюя запросам community, добавил поддержку Objective-C++ в XCode (вот архив документации: http://web.archive.org/web/20101203170217/http://developer.apple.com/library/mac/#/web/20101204020949/http://developer.apple.com/library/mac/documentation/Cocoa/Conceptual/ObjectiveC/Articles/ocCPlusPlus.html ). Потом они устыдились, доку снесли но поддержку де-факто оставили (XCode понимает расширение .mm ) . Некоторые примеры использования Objective-C++ с современным C++ можно посмотреть в презентации Peter Stainberger-а на AltConf-2015 https://realm.io/news/altconf-peter-steinberger-objective-c++-what-could-possibly-go-wrong/ Вот такая beautiful madness.

24 августа 2016, 12:28

22 августа 2016

Максим Сохацкий

Respect Proper Proof of Setoid Cat

Нас спрашивают, как выглядит код на EXE. Здесь записана модель Категории, на языке, у которого нет встроеного равенства (кроме definitional конечно):

define Respect (A,B: Type) (C: A → Type) (D: B → Type) (R: A → B → Prop)
       (Ro: ∀ (x: A) (y: B) → C x → D y → Prop) : 
       (∀ (x: A) → C x) → (∀ (x: B) → D x) → Prop :=
       λ (f g: Type → Type) → (∀ (x y) → R x y) → Ro x y (f x) (g y).

record Proper (A: Type) (R: A → A → Prop) (m: A): Prop :=
       (Proof: R m m)
       
record Setoid: Type :=
       (Carrier: Type)
       (Equ: Carrier → Carrier → Prop)
       (Refl: ∀ (e0: Carrier) → Equ e0 e0)
       (Trans: ∀ (e1,e2,e3: Carrier) → Equ e1 e2 → Equ e2 e3 → Equ e1 e3)
       (Sym: ∀ (e1 e2: Carrier) → Equ e1 e2 → Equ e2 e1)

record Cat: Type :=
       (Ob: Type)
       (Hom: ∀ (dom,cod: Ob) → Setoid)
       (Id: ∀ (x: Ob) → Hom x x)
       (Comp: ∀ (x,y,z: Ob) → Hom x y → Hom y z → Hom x z)
       (Dom1◦: ∀ (x,y: Ob) (f: Hom x y) → (Hom.Equ x y (Comp x x y id f) f)) 
       (Cod1◦: ∀ (x,y: Ob) (f: Hom x y) → (Hom.Equ x y (Comp x y y f id) f)) 
       (Subst◦: ∀ (x,y,z: Ob) → Proper (Respect Equ (Respect Equ Equ)) (Comp x y z))
       (Assoc◦: ∀ (x,y,z,w: Ob) (f: Hom x y) (g: Hom y z) (h: Hom z w)
                → (Hom.Equ x w (Comp x y w f (Comp y z w g h)) 
                               (Comp x z w (Comp x y z f g) h)))


zeit_raffer переписал Subst◦ без Proper/Respect:

       (Subst◦: ∀ (x,y,z: Ob) (f1,f2: Hom x y) (Hom.Equ x y f1 f2) 
                              (g1,g2: Hom y z) (Hom.Equ y z g1 g2) 
             → (Hom.Equ x z (Comp x y z f1 g1) (Comp x y z f2 g2))) 


Вроде компактнее уже нельзя. Не нашел ни одной библиотеки на Agda на github, где по компакности хоть кто-то приблизился бы. Достигнут новый золотой стандарт лямбда-йобства!

22 августа 2016, 11:47

Благословение от Хенка получено

Henk Barendrecht wrote:

Dear Maxim,

1. Great that you have reached a point in your software
development where you need automated verification
via formalization. Indeed you have my blessings.
My co-author and former colleague Freek Wiedijk
will almost for sure be interested in your project.
He is not happy with the existing provers and has
reimplemented automath.

...


Работаем дальше!

22 августа 2016, 10:04

Identity Types in EXE





____________________
[1] E.Bishop Foundations of Constructive Analysis 1967
[2] T.Streicher, M.Hofmann The groupoid interpretation of type theory 1996
[3] G.Barthe, V.Capretta Setoids in type theory 2003
[4] M.Sozeau, N.Tabareau Internalizing Intensional Type Theory 2013
[5] V.Voevodsky Identity types in the C-systems defined by a universe category 2015
[6] D.Selsam and L.de Moura Congruence Closure in Intensional Type Theory 2016

22 августа 2016, 10:04

Американская и Британская школы Лямбды

Выражаю почтение и склоняюсь перед де Брейном,
отцом всех пруверов,
создателем AUTOMATH


Сейчас я объясню мотивацию синтаксиса OM/EXE. Навскидку есть несколько синтаксисов для лямбды:

    λ x . B x            — нетипизированная классика
    λ x : A , B x        — в научных статьях
    λ (x: A) → B x       — современный синтаксис Morte/Om
    λ (x: A) , B x       — Lean
    (x: A) B x           — LISP синтаксис
    [x: A] B(x)          — AUTOMATH
    fun (x: A) => B x    — языки программирования и французкая школа
    fun (X) -> B(X)      — Erlang


Классика используется студентами, которые решают домашки, на википедии, и в HOL/Isabelle. Второй синтаксис используется в самых крутых статьях по лямбда исчислению, его использует например Страйхер, третий используется тоже часто в статьях, например Пфенинг. LISP синтаксис заюзал в своей работе по индуктивных семейставах Дыбьер. Но все это вариации AUTOMATH, где есть [], что есть там и квантор и лямбда. Есть еще логический синтаксис правил вывода, который заюзал МакБрайд в Эпиграмме, но это уже через чур. Синтаксис, который используется в современных языках программирования, тоже приведен, тут по столько по скольку, так как статьи на нем писать неудобно. Мы выбрали в качестве синтаксиса лямбда исчисления в OM тот, где есть и скобочки и стрелочки. Нормальные формы лямбд мы выстраиваем вертикально так как это делал Дыбьер, чтобы видеть паттерн и глубину терма.

То как выглядят индуктивные типы условно можно разделить на британскую школу LCF/ML/HOL/Hope/Miranda/Haskell/Agda/Idris и американскую LISP/ACL2/NuPRL/Lean/EXE школу. Это помогает понять почему мы выбрали скобочки и тут. Синтаксисом OM/EXE мы хотим показать приемственность к другой, не-британской школе. Как мы определяем List и как это делают британцы:

    data List (A: *): * :=
         (Nil: List A) 
         (Cons: A → List A → List A)

    data List (A : Set) : Set where
         []  : List A
         _∷_ : (x : A) (xs : List A) → List A


Тут сразу несколько моментов, мы хотим, в базовой поставке EXE, без notation, парсер должен быть минималистичный, мы всячески избегаем 2D синтаксиса ориентированного на \n и \r и обрамляем все скобочками, как это происходит в лиспах и Lean. Благодаря чему параметры индуктивных конструкторов напоминают множественные параметры наших лямбд \ (B: *) (x: A) -> B x.

Т.е. OM/EXE классифицируется исключительно, как синтаксис американской школы, с еще большим уклоном в LISP, чем калифорнийская Annah/Morte. Этот синтаксис создан для того, чтобы статьи выглядели красиво и читались ревьюверами мгновенно (кроме этого еще код нужно компактный писать, чем не все типовые теоретики могут похвастаться даже в своих Agda репозиториях).

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

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

22 августа 2016, 10:03

Собеседование в Групоид Инфинити

Как-то тут зашла речь, что якобы мы в Групоид Инфинити пиздаболы, и кодировки наши не кодировки, и веры в нас нет никакой. На что у меня сразу появилось отдельное, не связанное с этим, ответное предложение — составить тестовое задание на вход в команду:

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

Так вот для статьи я начал выписывать семантику. Ну ее еще Мартин Леф выписал в 1972 для Пи типов, т.е. наш ОМ. А потом уже идет семантика EXE.

В EXE дальше идет у нас равенство с J элиминатором. В 1988 году была записана семантика для теории категорий (наша рабочая теория) в теории типов Мартина Лефа. Потом была записана семантика для Well Founded Trees, которые полиномиальные функторы, они же индуктивные типы в общем случае, ну а дальше идут высшие индуктивные типы. Как выписать Type Inference Judgment Rules для скажем Транкейшина или Гомотопической Сферы — тривиальная задача, которую может выполнить даже такой дибил как я. А в команду мы возьмем того, кто выпишет правила вывода для высших индуктивных типов в общем случае (HIT-form, HIT-intro, HIT-elim, HIT-comp).

Ждем ваших писем! :-)

22 августа 2016, 09:56

14 августа 2016

Максим Сохацкий

Наноядра чистый изумруд

В Твиттере пошла волна репостов про https://github.com/littlekernel/lk Но среди молодняка мало кто знает, что автор этого ядра Тревис Гейзельбрехт был со-автором ядра операционной системы BeOS, а также автором NewOS, которое фактически в неизменном виде стало основой HaikuOS. Теперь Google начало пилить Фуксию, ОС основанную на LK. Все-таки BeOS выстрелил! Also если кто незнает из NewOS известный ебанат Дима Завалишин понадергивал кусков и всем говорит что заебашил PhantomOS с нуля.

Я когда-то дико упарывался по BeOS, Haiku и даже ебашил там на С++ чаты и KHTML портировал с KJS. Но теперь у меня смешанные чувства: с одной стороны я рад, что правительство Гугла дало добро на закапывание Линукса, с другой я уже перерос это байтойобство. Только лямбдочку хардварную верифицировнную мне подавай. К старости говорят все капризными становятся как дети.

Таки дела, пацаны.

14 августа 2016, 21:25

Scala@livejournal.com

Вопрос про трейты

Я не очень понимаю трейты, но иногда приходится с ними иметь дело. В основном из-за legacy. И вот возник такой вопрос:

Допустим, у нас есть trait A и trait A1 extends A. Можно ли как-то сделать так, чтобы трейт A1 нельзя было подмешать к трейтам, которые не extends А ?

P.S. Очевидно, trait A1 extends A {this: A => } не работает.

написал Michael 14 августа 2016, 18:52

Максим Сохацкий

Порядок редукций и Элиминатор Bool

Поднял из анналов, старый тред akuklev, nponeccop и udpn про if и "заходить в две ветки"

http://udpn.livejournal.com/78084.html

Напомнимаю, что мы все у себя давно померяли, для нормализации/ненормализации, eager/lazy вариантов:

http://maxim.livejournal.com/471966.html

Наткнулся на фразу

> В extensional ITT существуют сетоиды, но это жалкая замена левой руки.

Интересно что имелось ввиду? Что круто писать на J элиминаторе все, как на предыдущих слайдах? :-)

14 августа 2016, 00:01

13 августа 2016

Scala@livejournal.com

Библиотека для HttpClient

По-моему, библиотека для написания http client-а должна быть такой:
  • классы Request, Response, а также служебные Url, Entity, и т.д. это просто контейнеры для данных (как POJO или DTO на Джаве). Без всякой связи с собственно работой по сети.

  • Синтаксическй сахар для создания всех этих Request'ов, типа:
    get("myhost") / "foo" / "bar" withQuery("qp" -> "xxx")
  • Служебные функции для преобразования Request в Kleisli:
    Request => HttpConnection => Try[Response]
    Request => HttpConnection => Future[Response]
    и т.д.
  • Благодаря implicit class эти функции можно вызывать как методы Request'а:
    val req = get("a/b/c")
    val sync  : HttpClient => Try[Response]    = req.sync[HttpClient]
    val async : HttpClient => Future[Response] = req.async[HttpClient] 
    
Тут важно, что я могу единообразно использовать самые разные библиотеки, которые занимаются собственно работой по сети. В том числе Apache HttpClient, Async HttpClient, Netty, Finagle, и даже наши собственные библиотеки на джаве.

Как вам такой подход ?

написал Michael 13 августа 2016, 18:06

12 августа 2016

Теория категорий

MONADS NEED NOT BE ENDOFUNCTORS

We will elsewhere comment on the relation of our relative monads to the recent gen- eralization of monads by Spivey [31] that was also motivated by programming examples: he fixes a functor K ∈ C → J (notice the direction) to then look for monad-like structures with an underlying functor J → C. With Paul Levy we have checked that a fair amount of monad theory transfers to his generalized monads, but they are not monoids in [J, C] unless K has a left adjoint, in which case they are equivalent to relative monads. Sam Staton has considered an enriched variant of relative monads.

http://jmchapman.github.io/papers/relmon-lmcs.pdf

написал Namdak Tonpa 12 августа 2016, 18:57

Максим Сохацкий

MONADS NEED NOT BE ENDOFUNCTORS

We will elsewhere comment on the relation of our relative monads to the recent gen- eralization of monads by Spivey [31] that was also motivated by programming examples: he fixes a functor K ∈ C → J (notice the direction) to then look for monad-like structures with an underlying functor J → C. With Paul Levy we have checked that a fair amount of monad theory transfers to his generalized monads, but they are not monoids in [J, C] unless K has a left adjoint, in which case they are equivalent to relative monads. Sam Staton has considered an enriched variant of relative monads.

http://jmchapman.github.io/papers/relmon-lmcs.pdf

Кто еще раз пизданет что Монада — это моноид в категории эндофункторов, сразу с вертушки :-)

12 августа 2016, 18:56

Scala@livejournal.com

ru_scala @ 2016-08-12T20:43:00

Ещё одна версия "игры жизнь". На этот раз добавлен zipWith (по совету sassa_nf, за что ему огромное спасибо). К сожалению этот вариант длиннее изначального за счёт всех этих операций сдвига. Теперь было бы интересно написать визуализацию на scala.js.
object MatrixConway {

  type Board = Vector[Vector[Int]]

  def tick(board: Board): Board = {

    val cell: (Int, Int) => Int = {
      case (c, 2) => c
      case (_, 3) => 1
      case _ => 0
    }

    val shifts: Seq[Board => Board] = {

      def shiftL[T](ts: Vector[T], pad: T): Vector[T] = (ts drop 1) :+ pad
      def shiftR[T](ts: Vector[T], pad: T): Vector[T] = pad +: (ts dropRight 1)

      val shiftW = { b: Board => b map (shiftL(_, 0)) }
      val shiftE = { b: Board => b map (shiftR(_, 0)) }

      val zeros = Vector.fill(board.length)(0)
      val shiftN = { b: Board => shiftL(b, zeros) }
      val shiftS = { b: Board => shiftR(b, zeros) }

      val shiftNW = shiftN andThen shiftW
      val shiftSE = shiftS andThen shiftE
      val shiftNE = shiftN andThen shiftE
      val shiftSW = shiftS andThen shiftW

      Seq(shiftW, shiftE, shiftN, shiftS, shiftNW, shiftSE, shiftNE, shiftSW)
    }

    def zipWith[A](f: (A, A) => A): (Vector[A], Vector[A]) => Vector[A] = (_, _).zipped map f
    val zipBoardWith: ((Int, Int) => Int) => ((Board, Board) => Board) = f => zipWith(zipWith(f))

    val neighbors: Board => Board = b => shifts map (_.apply(b)) reduce zipBoardWith(_ + _)

    zipBoardWith(cell)(board, neighbors(board))
  }
}

написал Michael 12 августа 2016, 17:59

10 августа 2016

caml_programmer

Чистые функции против сайдэффектов.

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

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

Также можно вспомнить всякого рода сканеры электро-магнитного поля
для жестких дисков (чтобы считывать более старые записи по тому же адресу) -
в этом плане жесткие диски чем-то бумагу (материальный носитель)
напоминают.

Возникает вопрос, что для материальной реальности более естественно -
переаллокация или присваивание?

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

В общем, неоднозначно можно сказать что ничерта не понятно
как всё устроено.

10 августа 2016, 21:53

Scala@livejournal.com

ru_scala @ 2016-08-10T18:25:00

Ещё одна имплементация "игры жизнь" по подсказке sassa_nf, за что ему большое спасибо. Мне очень понравилась идея использовать операции с матрицами вместо манипуляций с индексами (только, к сожалению, не могу объяснить почему).

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

  type Board = Vector[Vector[Int]]

  def tick(board: Board): Board = {

    val cell: (Int, Int) => Int = {
      case (_, n) if n < 2 || n > 3 => 0
      case (c, 2) => c
      case (_, 3) => 1
    }

    def shiftL[T](ts: Vector[T], pad: T): Vector[T] = (ts drop 1) :+ pad
    def shiftR[T](ts: Vector[T], pad: T): Vector[T] = pad +: (ts dropRight 1)

    val shiftW: Board => Board = _ map (shiftL(_, 0))
    val shiftE: Board => Board = _ map (shiftR(_, 0))

    val zeros = Vector.fill(board.length)(0)
    val shiftN: Board => Board = shiftL(_, zeros)
    val shiftS: Board => Board = shiftR(_, zeros)

    val shiftNW: Board => Board = shiftN andThen shiftW
    val shiftSE: Board => Board = shiftS andThen shiftE
    val shiftNE: Board => Board = shiftN andThen shiftE
    val shiftSW: Board => Board = shiftS andThen shiftW

    val shifts = Seq[Board => Board](shiftW, shiftE, shiftN, shiftS, shiftNW, shiftSE, shiftNE, shiftSW)

    val addUp: (Board, Board) => Board = (b1, b2) => (b1, b2).zipped map ((v1, v2) => (v1, v2).zipped map (_ + _))
    val neighbors: Board => Board = b => shifts map (_.apply(b)) reduce addUp

    (board, neighbors(board)).zipped map ((v1, v2) => (v1, v2).zipped map ((c, ns) => cell(c, ns)))
  }
}

написал Michael 10 августа 2016, 16:41

Dee Mon journal

Bashkortostan ftw

As you surely know, Bashkortostan is the world leader in technology,
computer science and algebraic topology. With this submission, we expect to
cement the positions of our motherland in the exciting new field of
computational geometry. Don't worry: resistance is very obviously futile.

From young age, our children are trained in the art of convex decomposition
of polyhedra, computing barycenters of weighted point sets, and triangulated
surface mesh skeletonization; hoping, that one day they'd be tasked with a
crucially important problem of...

https://github.com/cakeplus/icfp-2016-wild-bashkort-mages
Самый суперский отчет (точнее, readme к исходникам) с нынешнего ICFPC. Почитайте целиком, не пожалеете.

В этом году контест был очень классным, и очень суровым.

10 августа 2016, 05:42

09 августа 2016

Adept

ICFPC-2016: день первый

(Это первая часть рассказа, а вот вторая и третья)

В этом году ICFPC был про оригами.

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

Вот на картинке контур закрашен красным, а линии скелета выделены:


Контур может быть сложным - не обязательно выпуклым, может содержать дырки и самопересечения и т.д. и т.п. Это все было заботливо описано в задании, но картики огранизаторы благоразумно не прилагали, чтобы сразу не отпугнуть всех участников.

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



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


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

Был интерактивный leaderboard.

По истечении 24 часов открывалась возможность засылать свои задачки и решать чужие. Авторы задач получали (5000-размер задачи)/молодцов очков, что по первым прикидкам было чуть больше, чем дофига (если твою задачу никто не решил).

День первый

В моей временной зоне все начиналось в час ночи. Собрав волю в кулак, я пошел спать до того, как было опубликовано задание, и на следующий день проснулся аж в 10:00 и засел читать условие. Первые впечатления были смешанные. Ура, в этом году без навязшего в зубах AI. Ура, leaderboard. Ура, не надо готовить свой код для исполнения на сервере организаторов. Ура, просто засылаем решение в каком-то простом формате, а решать можно на чем угодно и как угодно.

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


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

REST API, говорите? С примерами на curl? Замечательно, заворачиваем все в bash, суем в нужные места "sleep 0.5", чтобы сервер не ругался на слишком много запросов (еще 0.5 секунд добавляют тормоза баша), и скрипт для выкачивания задач готов.

Это задало определенный тон на все соревнование -- больше, больше шелла и скриптов. Я колебался, что именно брать для рисования задач -- cairo2 или ocaml'овский graphics, и в результате выбрал gnuplot + все тот же bash.

Для lightning round организаторы дали 100 задач, сложность которых росла очень медленно. Квадратик. Квадратик, сдвинутый из начала координат. Повернутый квадратик. Чуть меньший квадратик. В 12:00 я заслал первое (идеальное) решение для тупого квадратика и был доволен собой. И тут внезапно (зацените всю красоту гнуплота, кстати - на статической картинке этого не видно, но можно было щелкать мышкой и включать-выключать видимость контура и скелета по отдельности):



Или вот:


Это нифига не очевидно с первого взгляда, но такую фигуру нельзя сложить без так называемого inside reverse fold. Это мне очень вовремя объяснила жена, у которой с оригами не в пример лучше моего. То есть, нужно сделать несколько сгибов, а потом один из них вот этак вытащить наружу (или наборот - заправить внутрь под уже сложенные слои бумаги).

Я понял, что я вообще не понимаю, как это можно 1)распознать по описанию задачи 2)запрограммировать. Но унывать нельзя, надо что-то делать. И я сделал програмку, которая распознает задачи, являющиеся переносом-повотором квадрата 1х1 и решает их. Чисто чтобы отладить парсер заданий, принтер решений, работу с числами (которые были в виде натуральных дробей -- привет, Num) и все такое прочее. "Такое прочее" заняло у меня порядочно времени (как всегда бывает), и этот игрушечный солвер был у меня готов только к 15:00.

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

Дальше я понял, что раз "лыжи не едут", то надо делать хоть что-то. Этим хоть чем-то оказалась идея, которая пришла в голову, думаю, всем без исключения - можно в качестве решения отсылать листик 1х1 без всяких сгибов, заботливо положеный поверх требуемого оригами. Это давало какие-то небольшие очки, но все-таки лучше, чем ничего. Опять же, можно написать еще скриптов - чтобы решать все задачи, засылать все решения и т.п.

К 18:00 я накрыл квадратиками все задачи и неожиданно поднялся на 18 место. Приободренный, я подумал, что я могу пойти на один шаг дальше -- если оригами меньше квадрата 1х1, то я могу положить оригами в угол моего листа, загнуть правый и верхний края, и результат будет лучше (т.к. получившийся квадратик с подгибами будет "более похож" на результат). Прелесть в то, что структура такого решения всегда одна и та же -- лист бумаги будет разделен сгибами на четыре прямоугольника, номера точек и номера вершин прямоугольников всегда одни и те же, отличаются только их координаты (в зависимости от того, насколько сильно подогнут листик). Но координаты-то как раз посчитать легко. А все остальное можно захардкодить.

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

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

К 23:00 у меня появилось первое приближение к коду, который загибает уголок у листа бумаги (это я так думал, на самом деле там не работало примерно ничего, но я об этом узнаю только завтра). После полуночи закончился lightning (я был где-то на 18-м месте), организаторы опубликовали первую любовно сделанную моей женой задачу, на нее никто в течении часа не позарился, и я получил где-то 4000 очков и взлетел до 13 места. Окрыленный этим результатом, я пошел спать.

Хронология взлетов и падений:


Продолжение.

09 августа 2016, 22:58

ICFPC-2016: день третий

Предыдущие части : день первый, день второй.

На третий день (традиционно, в 10:00) я обнаружил, что сполз до 42 места (из около 200 активных участников). Какое-то время ушло на вытягивание новых задач и разглядывание того, как другие участники решают мои задачи. В 11:00 я вернулся к написанию солвера.

На третий день количество написанного кода превысило критический порог и наконец-то ПОПЁРЛО.

К 12:00 я сделал вычисление выпуклой оболочки (convex hull) и стал писать солвер, который заворачивает любое оригами как подарок -- кладет сверху лист бумаги и подгибает все края по граням выпуклой оболочки, пока бумага не перестанет торчать за пределы нужного контура.

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

Конечно, меня не покидала мысль о том, что это очень простецкий подход, но судя по состоянию "таблицы чемпионов" по-прежнему тупил не один только я, и у меня был шанс выбиться в лидеры среди тех, кто тупит :)

Где-то в 13:00 я начал первые пробные запуски нового солвера, и на удивление он почти сразу же заработал. Единственной найденной проблемой было то, что я сдвигал оригами к (0,0), потом оборачивал вокруг него бумагу, а потом двигал результат обратно в то место, где он должен быть по условию задачи. И вот это последнее движение могло превратить все мои координаты в ужасные громадные дроби, что приводило к превышению лимита в 5000 байт.

К 14:00 я закончил допиливать скрипты для проверки решений, и поставил решение задач и их отправку на поток, а сам принялся разглядывать неидеально решенные задачи.

С ключом -debug солвер мог сохранять на диск картинки до и после каждого сгибания. Вот как это выглядит (линии тонкие, рекомендую фуллскрин):


Очень быстро я понял, что в отдельные моменты хочется сказать "да где ты загибаешь! Ты не вот там загибай, ты вот тут загибай!". К этому моменту (15:30) жена прошерстила статистику по имеющимся задачам и моим решениям, и сказала мне, что есть довольно много задач, которые по сути являются выпуклой оболочкой, которую потом перегнули еще раз или два. И если бы мой солвер мог сделать еще и это ...

Как именно вычислить такие задачи и сделать дополнительный шаг или два я в тот момент сообразить не мог. Зато я вспомнил ICFPC 2007, на котором jabber.ru решил все задачи вручную (написав для этого подходящие инструменты).

К 16:00 я залили все решения, которые только мог произвести и скакнул с 52 места на 20-е. Дальше имеющийся солвер меня поднять не мог.

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

На картинке я рисовал исходный лист бумаги и точки "скелета" на нем, а рядом - текущий вид оригами и, опять-таки, точки скелета. Управлялся процесс интерактивной сборки через простой командный интерфейс. Программа имела/умела:
  • ввод через readline с историей и поиском
  • неограниченное undo (undo)
  • сгибание через произвольные координаты (fc x,y x2,y2)
  • сгибание через линию, проходящую через а произвольные точки (fp точка1 точка2)
  • смещение бумаги на произвольный вектор (mv dx,dy)
  • совмещение точек на оригами и скелете (mp paper_point skeleton_point)
  • показать координаты точек скелета (skeleton)
  • показать размер решения (size)
  • и самая киллер-фича: многократно сгибать бумагу по двум указанным линиям, пока есть, что сгибать. В результате она свернется в полоску, края которой совпадают с этими линиями (strip line1_point1 line1_point2 line2_point1 line2_point2)

Последняя команда была добавлена из-за того, что было очень много задач вида "полоска, согнутая 1-3 раза".

В 18:30 интерактивная решалка заработала. Этого набора команд оказалось достаточно, чтобы решить любую задачу, которая моя "бумага" в принципе могла позволить решить.

Вот как это выглядит:


С 19:00 до 21:00 я допиливал фичи в интерактивный решатель, делал новые задачи и вручную решал имеющиеся. Жена постоянно подбрасывала мне информацию о том, какие задачки выглядят решаемыми (глядя в статистику и картинки). Первым делом я старался решать задачи, которые присутствовали в N копиях, чтобы получить побольше очков.

Очень скоро стали понятны ограничения моего кода. Самым серьезным оказалось то, что сгиб по линии сгибал всё оригами целиком, тогда как для некоторых задач надо было согнуть только его часть. Кроме того, я не мог сделать нетривиальные сгибы с вытаскиванием или засовыванием углов (тот самый inside reverse fold, который я разглядывал в первый день).

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

Жена решила мне вручную какое-то невообразимое количество задач (что-то около 30), которые были моему коду не по зубам.

Где-то к 22:00 я написал код, который вытягивал из snapshot-а информацию о задачах, которые идеально решило меньше трех человек. Я просматривал их картинки и пытался решить их вручную, и решил что-то около десятка.

Две задачи требовали ручного сдвига бумаги "на чуть-чуть", я пытался высчитать правильное значение, но не смог, и в результате решил их с resemblance=0.99999999999. Обидно :)

Остаток времени ушел на то, чтобы еще раз прогнать солвер по всем задачам, убедиться, что все решения отправлены, еще раз посчитать статистику и решить максимальное количество задач вручную. Последнюю задачу я решил за 15 секунд до конца и отправить уже не успел :)

Хронология последнего дня (время в часах от начала ICFPC):


Исходники (там вместе с задачками, картинками и всеми снепшотами, около 100М):
https://bitbucket.org/dastapov/icfpc2016/

Статистика:
  • Идеально решенных задач: 1120
  • С подобием от 0.5 до 1.0: 2125
  • С подобием меньше 0.5: 236

По своим задачам точную статистику я не вел, но помню, что были какие-то, решенные всего 2-3 участниками.

Надеюсь, что с 19-го я поднимусь хотя быть на 18-е место :)

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

Выводы:
  • Жена, увлекавшаяся оригами - страшная сила
  • Без команды вполне себе ничего
  • Гулять - хорошо :)
  • Если что-то приуныл - пиши скрипты, разглядывай картинки, что-то делай. Мысль придет
  • После ежедневного ocaml на работе я даже и не думал писать на haskell -- уже не ориентируюсь в современных библиотеках, а тратить время на разбирательство неохота.
  • Это, конечно, не 2006 год, но тоже неплохо.


EOF

(первая часть, вторая часть)

09 августа 2016, 22:56

ICFPC-2016: день второй

(предыдущая часть, следующая часть)

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

Так как решение состоит из точек (заданных координатами на начальном листике), полигонов (заданых порядковыми номерами точек) и финальной формы оригами (заданной конечными координатами точек), то я подумал, что моя модель бумаги будет состоять из:
  • текущего положения точек (список координат)
  • полигонов (заданых списками номеров точек)
  • какой-то истории сгибов

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

Наутро второго дня (в 10:00) я перечитал написаный код и понял, что дела не будет. Во-первых, полигоны в виде списка точек неудобны, так как постоянно нужна "предыдущая точка" или "следующая точка". То есть, удобнее будет задавать полигоны отрезками.

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

В-третьих, моя реализация имела ошибку, и уверенно работала только в том случае, если в результате сгиба поворачивался только один "уголок" бумаги с одной вершиной.

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

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

В общем и целом выходило так, что моя "бумага" ни на что не годилась.


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

К 12:00 я понял, что нужно расставить приоритеты. Я выкачал новую порцию задачек, сгенерировал для них картинки, сделал сводную статистику моих решений и их успешности и сел вместе с женой над ними медитировать. Выводов намечалось два: нужно делать свои задачи, они дают очки (и много). Но одними задачами выехать не получится - ты можешь размещать не более одной задачи в час, всего 46 штук. А твои конкуренты, которых 100-200 команд, могут за это время разместить до 8000 задач. То есть, все-таки нужен решатель. Более умный, чем "накрываем листиком, подворачиваем края".

Второй вывод заключался в том, что за ночь некоторые команды запостили уже по 8-9 задач. У некоторых это был просто квадрат (0,0),(0,1),(1,1),(1,0) (ура!). У некоторых это было что-то позаковыристее, но все время одно и то же. Прелесть в том, что сервер считал некий хэш от описания задачи, и повторяющиеся задачи можно было легко найти.

Первым делом жена сделала мне вручную описание задачки-"змеи". Вот она:


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

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

Тут на меня нашло какое-то затмение и я почему-то подумал, что надо найти реализацию синуса-косинуса через, например, continued fractions, и все замечательно получится. Такая библиотека была найдена, но (как можно было бы и догадаться) чуда не произошло. "Polygon #0 is not mapped congruently", все в сад, повторять школьную математику. Можно было бы взять значение синуса равным какому-то произвольному числу, и вычислить, какое при этом будет значение косинуса, но там же \sqrt{1-cos^2{\alpha}}, а корень квадратный у нас - что? Правильно, такая же фигня, как и с синусом и косинусом.

Идея перебрать натуральные дроби из какого-то диапазона, удовлетворяющие a^2+b^2=c^2, и положить синус равным a/c, а косинус - b/c мне тогда в голову не пришла. В результате змея так и осталась неповернутой.

На неравный бой с тригонометрией у меня ушел битый час. Потом я еще какое-то время почитал всякие статьи, некоторые из них были довольно любопытными. В частности, из "Folding Flat Silhouettes and Wrapping Polyhedral Packages: New Results in Computational Origami" я узнал, что можно сложить оригами в виде любого плоского многогранника - хоть и невыпуклого, хоть бы и с дырками. Доказательство было конструктивным, но вот беда - подразумевало неограниченное количество бумаги. Кому лень читать статью - идея была в том, чтобы сложить узкую полоску, а потом "змейкой" замостить полигон, и напоследок завернуть под него выступающие части "змейки". Даже если бы я и умудрился сложить из квадрата очень узкую и очень длинную полоску, у меня было всего 5000 байт на решение, а такое количество точек и ребер туда бы не влезло.

В процессе всего этого я периодически вяло выкачивал новые задания и решал их, постепенно сползая к 30-му месту.

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

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

А это значит, что, например, если мы делим некий отрезок AB новой точкой C пополам, то текущие координаты C можно просто посчитать, а координаты C на оригинальном листе можно узнать, разделив пополам отрезок между оригинальными точками AB. Аналогичным образом все работает для деления отрезков в любой другой пропорции.

С этой новой идеей я за время где-то с 17:00 до 22:00 написал новую модель бумаги и процедуру ее сгибания вдоль произвольной линии, заданной двумя точками A и B. При этом линия считалась идущей из A в B, и все, что лежало справа от нее, перегибалось налево. Кроме того я реализовал "отладочный вывод", заключавшийся в том, что после каждого сгибания модель бумаги сохраняла на диск .png с изображением "разогнутого" и текущего состояний. Мой ocaml был собран без graphics, интерфейс cairo2 был большим и мне незнакомым, поэтому я нашел векторыне библиотеки Vg и Gg и использовал их (потеряв, наверное, на этом сколько-то времени). Зато -- и это оказался большой плюс -- Vg/Gg позволяли рисовать в произвольных координатах и сами транслировали нарисованное в рамки картинки.

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

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

Хронология второго дня выглядит так (время в часах от начала ICFPC):


(предыдущая часть, следующая часть)

09 августа 2016, 22:56

08 августа 2016

beroal

придумайте какую-нибудь теорию

Задача из учебника по физике: «Запишите уравнение Менделеева—Клапейрона. Придумайте задачу на его применение и решите её». По мотивам я придумал свою: «Изучите теорию категорий. Научите теории категорий других. Придумайте ещё какую-нибудь теорию».

08 августа 2016, 19:14

Максим Сохацкий

Про линзы в Хаскеле

http://andrej.com/

Edward Kmett explained to me once (at about three times the speed I could follow) how lenses are just a bunch of category theory. That’s the sort of thing that this broken Hask non-category is good for.

08 августа 2016, 16:44

Крипто-ебанаты. Выпуск #1

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

Вот одна криптовалюта https://www.ethereum.org, которая разрабатывается в том числе и математиками, была хакнута и из нее вывели 50 лимонов, потом начали транзакцию отменять, делать форк, и сейчас наверно оно уже мертвое. Все репозитории Эфира на гитхабе на JavaScript. Читать тут: http://www.coindesk.com/understanding-dao-hack-journalists/

Вот недавний инцидент с биткоин биржей Bitfinex:
http://www.ft.com/cms/s/0/1ea8baf8-5a11-11e6-8d05-4eaa66292c32.html#axzz4GkdJQNtk И вообще если вы начнете искать и погуглите вы охуеете сколько там дыр и утечек. Пока биткоин был маргинальной валютой, никому это не было интересно, но сейчас, все измненится и ваши биткоины потекут.

Если вы видете, что кто-то у вас рядом создает/запускает blockchain криптовалюты/торговые/аукционные/голосовательные площадки, и там используются криптоалгоритмы не прочеканые на (F*/Agda/Coq/EXE), рано или поздно этой хуйне придет пиздец. Не спасет и Хаскель.

Тот, кто первый построит прочеканную VM, компактное ядро прувера, прочеканый гипервизор, тот и срубит весь куш. И я не говорю про хуйню типа CompCert/VST которая линкуется башем с говнокодом. Я говорю про единую вычислительную среду LING/Erlang/EXE!

Очень интересно увидеть какую-то дыру в непрочеканном кванторами Хаскель коде. Пишите нам и держите нас в курсе.

08 августа 2016, 15:24

Elm support in mad

Наш агент, который делает поддержку Elm в `mad` сообщает:

> втыкал в елм малеха на выходных, сыроватая хуйня конечно
> н2о скрипты не переписать на этой штуке
> даже вебсокеты умеют только в текст и то прикручены нативной жс либой
> вроде для юайчика нормально написали все, но эта нативная срань конечно фейспалмище
> у тебя такой хуйни не было

> вообщем ищут себя походу еще пацаны, половину модулей нужно подправлять в жаваскрипте
> конечно, но нада добить конечно конектор к н2о, может кто возмется эту хуйню дальше развивать

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

08 августа 2016, 11:06

07 августа 2016

Dee Mon journal

срыв покровов

http://math.andrej.com/2016/08/06/hask-is-not-a-category/
И в конце отличный анекдот про "let’s just pretend".

07 августа 2016, 06:16

05 августа 2016

nponeccop

GHC DLL for Windows

Внезапно кто-то чинит баг, поломавшийся в незапамятные времена (в районе GHC 7.6)

https://ghc.haskell.org/trac/ghc/ticket/5987

05 августа 2016, 20:34

"Turtle//BAZON Group"

Лидерборд апдейт

Сейчас 8:48. Какие-то бомжи на первом месте в лидерборде.


написал turtle (noreply@blogger.com) 05 августа 2016, 08:49

04 августа 2016

"Turtle//BAZON Group"

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 утра по Мск. Ждём. :)

написал turtle (noreply@blogger.com) 04 августа 2016, 14:48

03 августа 2016

Adept

ICFPC-2016: осталось два дня

По такому поводу можно вылезти из спячки :)

Через два дня (в пятницу, 6 августа) начинается ICFPC-2016. В прошлом году у меня поучастовавть не получилось, предыдущие два были (по моему мнению) так себе. Посмотрим, что будет в этом году.

PS: если вдруг кто еще не знает, что такое ICFPC, можете почитать мои старые отчеты, начиная с этого, они все под тэгом icfpc.

03 августа 2016, 11:18

02 августа 2016

01 августа 2016

Scala@livejournal.com

Запрос на код ревью

Запрограммировал в качестве упражнения известную "игру жизнь". Вроде работает. Буду рад любой конструктивной критике.
object Conway {

  type Board = Array[Array[Int]]

  def tick(board: Board): Board = {

    val cell: (Int, Int) => Int = {
      case (_, n) if n < 2 || n > 3 => 0
      case (c, 2) => c
      case (_, 3) => 1
    }

    val neighbors: (Int, Int) => Int = (r, c) => {
      val ns = for {
        dx <- -1 to 1
        dy <- -1 to 1
        (i, j) = (r + dy, c + dx) if (dy != 0 || dx != 0) && (board.indices contains i) && (board.indices contains j)
      } yield board(i)(j)
      ns.sum
    }

    board.zipWithIndex map { case (row, r) => row.zipWithIndex map { case (col, c) => cell(col, neighbors(r, c)) } }
  }

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

написал Michael 01 августа 2016, 15:20

28 июля 2016

ruhaskell.org

Митап 1.0

18 августа сообщество RuHaskell и «Лаборатории Касперского» приглашают всех заинтересованных, чтобы обсудить Haskell и другие языки в функциональной парадигме, поделиться опытом их применения в решении прикладных задач бизнеса, позадавать вопросы и пообщаться.

написал Денис Шевченко 28 июля 2016, 00:00

26 июля 2016

"Turtle//BAZON Group"

ICFPC-2016, вот он и пришёл

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

написал turtle (noreply@blogger.com) 26 июля 2016, 23:35

14 июля 2016

06 июля 2016

Mike Potanin

Где нужны "зависимые типы"?

Все хотят применять "depended types" в разработке больших сложный систем, но мало кто в этом добился хоть каких-нибудь заметных успехов.
Оно и понятно - "зависимые типы" очень усложняют жизнь, а разработкой таких систем занимаются опытные программисты, располагающие развитыми средствами отладки и тестирования. То есть привносимый геморрой не оправдывает потенциальные не слишком радикальные преимущества.
А вот во всяких DSL для конфигурирования, воркфлоу, всяких политик, "умных контрактов" в блокчейнах, скриптов для "интернета вещей", да и просто скриптов для автоматизации рутинной работы чего-то типа "зависимых типов" для обеспечения надежности остро не хватает.
Во первых все эти программы относительно простые, и даже усложнение их разработки в 3-4 раза не так уж и страшно, да и время компиляции от дополнительных проверок сильно не вырастет.
Во вторых средства разработки у них не развиты и врядли для столь узких ниш кто-то этим будет заморачиваться.
В третьих пишут их не профессиональные программисты, а специалисты в своих предметных областях.

06 июля 2016, 12:04

04 июля 2016

Фонд Поддержки Функционального Программирования

Отчёт об июньском конкурсе по ФП

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

https://docs.google.com/document/d/10J9UbsgC1m1RerNOU1nkOF1TmrmD9pRXzimGYMQarnU

написал Dark Magus (noreply@blogger.com) 04 июля 2016, 14:46

darkus

Отчёт об июньском конкурсе по ФП

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

https://docs.google.com/document/d/10J9UbsgC1m1RerNOU1nkOF1TmrmD9pRXzimGYMQarnU

04 июля 2016, 12:50

03 июля 2016

rssh

Вторая порция видео со #scalaua

Из тех что получились:


Остальные, к сожалению, вышли или с пропусками или с плохим звуком.
// напоминаю что первая часть: http://rssh.livejournal.com/230559.html

03 июля 2016, 20:23

22 июня 2016

Dee Mon journal

generic fourth-order Runge-Kutta method

Когда понадобилось численно просчитать эволюцию системы из ее производной по времени, и наивное решение не заработало, вспомнил слова "Рунге-Кутта", которые со студенческой скамьи не использовал. Быстро находимые описания в интернетах не супер понятные, а конкретные примеры порой слишком частные, но оказалось, что алгоритм можно очень просто выразить в довольно общем виде. Он работает для любого типа (представления состояния системы), для которого даны всего три операции: сложение, умножение на вещественное число и вычисление производной по времени. Такой вот тайпкласс. Например, состоянием может быть набор координат и скоростей точек, тогда сложение и умножение на число делается с координатами и скоростями поэлементно, а производная по времени ставит скорости вместо координат и вычисленные из координат и скоростей ускорения - вместо скоростей. У меня состоянием был массив комплексных чисел - волновая ф-я. Весь код получения состояния системы через шаг времени dt выглядит так:

type alias DiffVecSpace v = {
  timeDerivative : v -> v,
  mulByFloat : Float -> v -> v,
  add : v -> v -> v
}

evolveRK : DiffVecSpace v -> Float -> v -> v
evolveRK ops dt state = 
  let a = ops.timeDerivative state
      b = ops.add state (ops.mulByFloat (dt/2) a) |> ops.timeDerivative
      c = ops.add state (ops.mulByFloat (dt/2) b) |> ops.timeDerivative
      d = ops.add state (ops.mulByFloat dt c) |> ops.timeDerivative
  in List.foldl ops.add state [ops.mulByFloat (dt/6) a,
                               ops.mulByFloat (dt/3) b,
                               ops.mulByFloat (dt/3) c,
                               ops.mulByFloat (dt/6) d]


(тут на Elm'e)
Если выразить на языке с нормальными тайпклассами или ООЯ с определяемыми операторами, получится еще проще. С другой стороны, возможно операцию вычисления производной стоит не вносить в тайпкласс, а передавать явно. Тогда можно для одного типа состояния считать его эволюцию при разных внешних условиях (разных методах вычисления сил/ускорений/операторов/whatever), что у меня активно используется в программе.

22 июня 2016, 06:37

Elm 0.17

Elm - это хаскелеподобный чистый функциональный язык для всяких безобразий в браузере, т.е. "компилирующийся" в JavaScript. Знаменит прежде всего тем, что на нем написан визуализатор квантовой механики из предыдущего поста. :)
Три года назад я писал про тогдашний Elm, с тех пор он заметно изменился, а в последней на сегодня версии произошло существенное изменение в архитектуре, отчего большая часть старого кода и описаний перестала быть актуальной.
Изначально он появился как воплощение идей FRP, и thesis (дипломную работу?) автора Elm'a я могу всем рекомендовать как замечательное изложение идей и разных подходов к FRP, плавно переходящее в объяснение исходной архитектуры Elm'а (и без этого объяснения научиться тогдашнему Elm'у было трудно). Там вся динамика была построена на идее сигналов, когда есть обычные иммутабельные данные типов A,B,C... и есть отдельная категория типов A',B',C'... описывающих такие же данные, но меняющие свои значения со временем (навроде Time -> A'), и есть функтор Signal из первой категории во вторую. Пишешь чистый код, работающий с простыми иммутальными данными, потом этим функтором лифтишь свои чистые функции в мир динамически меняющихся значений. Есть набор внешних источников событий/данных, вроде координат мыши, т.е. уже живущих во второй категории, и нужно построить в ней функцию из нужных источников событий/данных в некое дерево контролов, элементов. А рантайм уже сам позаботится о том, чтобы все события и новые данные проходили как надо через все преобразования и получающееся на выходе дерево превращалось в DOM страницы. Ну и были во второй категории специальные комбинаторы для обращения с временнЫми потоками данных, вроде соединения, сворачивания и пр.
Потом в Elm'е появились Mailbox'ы и Elm Architecture, в которой программа описывалась двумя функциями view и update и начальным значением пользователького типа Model (содержащего все данные). update получала значение произвольного заданного пользователем типа Action (обычно это перечисление разных действий) и текущее значение модели, возвращала обновленное значение модели, а view отображала значение модели в дерево элементов, принимая одним из параметров "адрес" (значение специального типа Mailbox). Возвращаемые ф-ей view элементы в своих атрибутах могли иметь функции "что делать при нажатии/изменении", эти функции получали тот самый "адрес", чтобы слать свои оповещения туда. Так все оставалось иммутабельным и чистым, а рантайм заботился о доставке всех событий в форме пользовательского типа Action в функцию update, так осуществлялся круговорот событий-реакций в колесе сансары. Как видите, в явном виде сигналы уже не участвовали в Elm Architecture, но в разных API еще оставались.
В свежей версии 0.17 авторы сказали "прощай FRP" и выкинули все сигналы нафиг. И API для построения дерева элементов поменяли заодно. Зато добавили модный способ работы с первоклассными эффектами, как у взрослых. Осталась Elm Architecture, но уже другая. Теперь программа это
program : { init : (model, Cmd msg), 
         update : msg -> model -> (model, Cmd msg), 
         subscriptions : model -> Sub msg, 
         view : model -> Html msg }  -> Program Never

Т.е. описываешь свой тип Model с любыми нужными данными, описываешь свой тип сообщений (как Action раньше), и три функции: view, update и subscriptions. view тупо отображает модель в DOM HTML, но тип дерева элементов параметризован твоим типом сообщений, ибо в атрибутах элементов вставляются функции реакций на события, которые производят значения этого самого типа твоих сообщений. Им теперь не нужно знать ни про какие мэйлбоксы, не нужно туда ничего слать, просто произвести сообщение, рантайм сам знает куда его доставлять. Кроме того есть функция subscriptions, которая исходя из текущего состояния модели говорит, какие внешние события нам интересно слушать, и тип ее ответа тоже параметризован типом наших сообщений, т.к. внешние события приходят в рамках все того же потока сообщений, а когда подписываешься на внешнее событие, говоришь, как его завернуть в твой тип сообшений. Ну и ф-я update, которая получает все эти сообщения твоего типа и меняет модель, а заодно может произвести "команду" - указание рантайму произвести некоторый эффект, подобно значению типа IO Smthng в хаскеле. Выражение действий в виде данных обещает много бенефитов, но я в эту тему пока не вдавался.Вот такой теперь Elm, больше никаких сигналов, но по-прежнему все чисто функционально.
В версии 0.17 зачем-то изменился синтаксис описания модулей, там мелочь поменялась, но из-за нее некоторые библиотеки не собираются, надо одну строчку поменять в заголовке модуля.

А еще в Elm'e неожиданно оказалась встроенная поддержка WebGL: там не просто есть нужная библиотека, а компилятор умеет распарсить текст шейдеров на GLSL и проверить согласованность используемых типов между шейдерами и основной программой! Во-первых, сама библиотека для работы с WebGL более высокоуровневая и намного более удобная в обращении, чем то, что я видел в примерах про WebGL на JavaScript'e. В JS, похоже, просто копировали Си, там даже указатели есть, и приседаний на каждый чих нужно не меньше дюжины. В элмовском модуле WebGL все это безобразие спрятано, а выставлен довольно чистый и удобный API. Программа на Elm'e производит HTML дерево, соответственно конечная точка в WebGL это
toHtml : List (Attribute msg) -> List Renderable -> Html msg
и наша задача произвести список Renderable, которые получаются так:
render
    :  Shader attributes uniforms varyings
    -> Shader {} uniforms varyings
    -> Drawable attributes
    -> uniforms
    -> Renderable

где
type Drawable attributes
    = Triangle (List (attributes, attributes, attributes))
    | Lines (List (attributes, attributes))
    | LineStrip (List attributes)
    ...

Т.е. кусок графики (Renderable) получается из четырех вещей: двух шейдеров (вершин и пикселей), описания геометрии и общих данных для шейдеров. Причем и геометрия, и общие данные описываются пользовательскими типами - что хочешь, то туда и передавай. Например, набор треугольников представлен списком троек, но троек чего? Чего скажешь: хошь координат, хошь более сложных структур. Вертексный шейдер получит значения из этих списков в виде атрибутов - данных, меняющихся от вершины к вершине, а в качестве uniform данных (общих для всех вершин) получит то, что передашь, тут тоже твой тип, сам решаешь. А как в render передать шейдер? Это значение типа Shader attributes uniforms varyings (где все три типа-параметра - твои, какие скажешь), и описывается значение шейдера специальным синтаксисом с текстом шейдера на GLSL. Компилятор посмотрит, какие данные в тексте шейдера описаны как attribute, uniform и varying, и убедится, что они соответствуют полям твоих типов для attributes, uniforms и varyings, что переданы параметрами типу Shader. Тут происходит связь города и деревни, связь кода на Elm и кода на GLSL. Пример из моей программы:
sphVertSh : Shader { attr | position:Vec3, color:Vec3 } { unif | perspective:Mat4, pos:Vec3 } { v:Vec3 }
sphVertSh = [glsl| 

attribute vec3 position;
attribute vec3 color;
uniform mat4 perspective;
uniform vec3 pos;
varying vec3 v;

void main () {
    gl_Position = perspective * vec4(position*0.1 + pos, 1.0);
    v = position; 
}
|]

Такой вершинный шейдер будет вызван для каждой вершины сферы, он получит данные о вершине в виде attribute vec3 position и color, вычислит требуемое значение позиции и заодно запишет что нужно в выходное значение varying v, которое потом пиксельный шейдер получит проинтерполированным себе на вход и будет использовать для вычисления цвета пикселя. Поскольку оба вершинный и пиксельный шейдер передаются вместе в render, типы их uniforms и varyings обязаны совпадать, таким образом компилятор проверит не только то, что я в шейдеры правильные данные передаю, но и что вершинный шейдер производит именно такие данные, которые принимает пиксельный. При том, что тип этих данных я придумываю сам. Если сравните это с JS'ным WebGL или сишным OpenGL, увидите пропасть как в удобстве, так и в уровне статического контроля. Там все намного труднее делается и с минимумом проверок.

Другие впечатления после написания полтыщи строк. Близкий к хаскелю синтаксис и отличный вывод типов в сочетании с referential transparency от чистоты и иммутабельности позволяют очень легко массировать код: любой кусок можно элементарно превратить в функцию, перенести в другое место, параметризовать, при этом не порождается бойлерплейта и впечатления от процесса очень положительные. Компилятор очень шустрый (единственная быстрая программа на хаскеле из мне известных), сообщения об ошибках более чем подробные и ласковые, об этом авторы особенно заботились. В синтаксисе нет where, и это очень хорошо, на мой взгляд. По-прежнему есть что-то вроде встроенных тайпклассов (вроде number), но нельзя описывать свои тайпклассы или добавлять свои инстансы, когда работаешь с комлексными числами об этом сильно жалеешь. Можно описывать свои операторы, но только на самом внешнем уровне, т.е. определить оператор локально (чтобы было замыкание, задействовать значения из текущего скоупа) нельзя, это тоже обидно немножко.
Но общие впечатления очень положительные. Язык стал проще и одновременно удобнее. Компилятор стал стабильнее и вообще образцовый во многих отношениях. Есть очень классный менеджер пакетов и их репозиторий (причем они умеют гарантировать соблюдение логики semver, это отдельная тема). Есть удобная штука elm reactor, навроде debug mode в рельсах, когда поменял исходник, нажал в браузере F5 и все пересобралось и перезапустилось, благо компилируется мгновенно. А еще там удобные record'ы с row polymorphism'ом! О чем еще мечтать? :)

22 июня 2016, 06:09

17 июня 2016

Фонд Поддержки Функционального Программирования

Июньский конкурс по ФП в 2016 году закрывается

Июньский конкурс по ФП в 2016 году закрывается с этого момента. Итоги будут подведены, я надеюсь, в течение недели. Впрочем, победитель уже определён, мне надо просто написать отчёт. Этим и займусь.

написал Dark Magus (noreply@blogger.com) 17 июня 2016, 11:43

13 июня 2016

Евгений Охотников

[prog.flame] Любопытная заметка "Disadvantages of purely functional programming"

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

Имхо, статейка Disadvantages of purely functional programming как раз в эту же тему. Суть -- чистое ФП классная штука, конечно. Но тормозит. И, в принципе, в определенных местах не может не тормозить.

Отдельно отметил бы ссылочку, которая есть в этой статье: Naive parallelism with HLVM. Особенно мне понравились пути повышения производительности HLVM-программы: Disabling bounds checking provides a substantial 20% performance improvement. Disabling the shadow stack (and, therefore, disabling GC) provides another 25% performance improvement. With these two changes, HLVM is only 24% slower than C++. Ну, т.е., берем язык более высокого уровня, чем C++, и гораздо более безопасный, чем C++, а потом отключаем нафиг те фичи, которые как раз и делают его более высокоуровневым и более безопасным. И все только для того, чтобы не тормозить так сильно.

Ну и вообще, как мне кажется, в последние год-полтора прослеживается интересная тенденция: если раньше во главу угла ставилась скорость разработки и на передний план выходили безопасные языки программирования (причем даже не Java, а всякие Python-ы, Ruby, Erlang-и, Scala, Clojure и прочие OCaml-ы с Haskell-ями), то теперь просто скорости разработки мало. Нужно еще, чтобы результат работал быстро и/или жрал мало. Отсюда и интерес к тому же Go, который позволяет писать что-то так же быстро, как и на Python-е, но работает затем это что-то намного эффективнее, чем на Python-е. И возродившийся интерес к старой ламповой сишечке (а так же вспыхивающие вновь споры C vs C++). И пристальное внимание к Rust-у и Nim-у...

Объяснение сей тенденции я вижу в том, что делать быстро на Python-е (Ruby, Erlang, Scala, Clojure,...) теперь могут практически все. И одним из важнейших факторов становится снижение издержек на эксплуатацию. Для чего нужны не только быстро выходящие на рынок решения, но еще и эффективно работающие. А вот это умеют делать пока не только лишь все :)

PS. Кстати говоря, то, что все стараются друг другу что-то продать (кто-то "продает" Haskell, кто-то "продает" Clojure, я, например, "продаю" SObjectizer) -- это нормально. Правильно сделанная "покупка" сильно облегчает жизнь. Однако, важно понимать, что в процессе "продажи" мало кто будет на 100% откровенен и будет честно и по собственной воле рассказывать не только о достоинствах, но и недостатках. Так что никому нельзя верить. Мне можно ;)

PPS. Прошу воспринимать написанный выше текст с изрядной долей юмора и иронии.

написал Yauheni Akhotnikau (noreply@blogger.com) 13 июня 2016, 10:12

10 июня 2016

Фонд Поддержки Функционального Программирования

Июньский конкурс по ФП в 2016 году: плотная упаковка полимино

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

Возьмите следующий файл с исходными данными:

ФАЙЛ

В этом файле 100 задач. Каждая задача представляет собой поле вида:
111000
111111
111111
011110
011100
011000
Здесь единицы обозначают те места на поле, которые должны быть заполнены фигурами. Фигуры же перечисляются после поля и представляют собой такие же матрицы. Необходимо так расположить фигуры на поле, чтобы они покрыли все единицы поля своими единицами, и ни одной непокрытой единицы не осталось (ну и нули поля не должны покрываться единицами, но это говорить излишне, так как фигуры подобраны так, чтобы при выполнении первого условия второе выполнялось автоматически).

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

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

написал Dark Magus (noreply@blogger.com) 10 июня 2016, 08:00

darkus

Июньский конкурс по ФП в 2016 году: плотная упаковка полимино

А вот вам конкурс по функциональному программированию, с пылу с жару. Сегодня мы делаем плотную упаковку полимино. Налетай, играй, выигрывай.

http://haskell98.blogspot.ru/2016/06/2016.html

10 июня 2016, 07:00

07 июня 2016

David Sorokins WebLog

Айвика как конструктор общецелевых библиотек имитационного моделирования

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

написал dsorokin (noreply@blogger.com) 07 июня 2016, 15:47