Streams

Apr. 21st, 2017 05:52 pm
thedeemon: (vonny tropics)
Вот Идрис синтаксически очень похож на хаскель, однако не ленивый. В хаскеле ленивость-по-умолчанию сопровождается строгостью-по-запросу, добавшяешь перед полем значок ! и оно строгое. Оказывается, в Идрисе нынче есть симметричная штука: добавляешь перед типом поля волшебное слово Inf, и поле оказывается "ленивым": когда данные конструируются, выражение для вычисления этого поля не вычисляется сразу, а автоматически оборачивается в Delay (если явно поленился это сделать), а при паттерн-матчинге оно когда надо автоматически форсится через Force (т.е. механика практически как в окамле с ленивыми значениями, но вручную необязательно оборачивать и форсить, компилятор сам вставляет).
Например, через этот механизм сделан тип бесконечных последовательностей:
data Stream : Type -> Type where
(::) : (value : elem) -> Inf (Stream elem) -> Stream elem

Благодаря автоматическому расставлению делеев и форсов, код с такими коданными выглядит так же просто и чисто, как в хаскеле:
countFrom : Integer -> Stream Integer
countFrom x = x :: countFrom (x+1)

first : Nat -> Stream a -> List a
first Z xs = []
first (S k) (x :: xs) = x :: first k xs

prepend : List a -> Stream a -> Stream a
prepend [] ys = ys
prepend (x :: xs) ys = x :: prepend xs ys

Обратите внимание, что в функциях выше :: используется в паттерн-матчинге и в конструировании сразу и для списков и для стримов, компилятор сам по типу понимает где что, и для стримов вставляет delay/force.
Подобно Основное Теореме Арифметики и Основной Теореме Алгебры, есть Основная Теорема Функционального Программирования (это, по Карри-Говарду, конечно же тоже функция), ее можно записать так:
fibs : Stream Integer
fibs = 1 :: 1 :: zipWith (+) fibs (drop 1 fibs)

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

— Не пугайтесь, Екатерина Петровна, и не волнуйтесь. Только нет в мире никакого равновесия. И ошибка-то всего на какие-нибудь полтора килограмма на всю вселенную, а все же удивительно, Екатерина Петровна, совершенно удивительно!
thedeemon: (faculty of numbers)
http://math.andrej.com/2016/08/06/hask-is-not-a-category/
И в конце отличный анекдот про "let’s just pretend".
thedeemon: (office)
Когда понадобилось численно просчитать эволюцию системы из ее производной по времени, и наивное решение не заработало, вспомнил слова "Рунге-Кутта", которые со студенческой скамьи не использовал. Быстро находимые описания в интернетах не супер понятные, а конкретные примеры порой слишком частные, но оказалось, что алгоритм можно очень просто выразить в довольно общем виде. Он работает для любого типа (представления состояния системы), для которого даны всего три операции: сложение, умножение на вещественное число и вычисление производной по времени. Такой вот тайпкласс. Например, состоянием может быть набор координат и скоростей точек, тогда сложение и умножение на число делается с координатами и скоростями поэлементно, а производная по времени ставит скорости вместо координат и вычисленные из координат и скоростей ускорения - вместо скоростей. У меня состоянием был массив комплексных чисел - волновая ф-я. Весь код получения состояния системы через шаг времени 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), что у меня активно используется в программе.

Elm 0.17

Jun. 22nd, 2016 12:52 pm
thedeemon: (office)
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" и выкинули все сигналы нафиг. Read more... )
thedeemon: (bednota)
Группа ученых под руководством Дэниела Лебреро из Лаборатории Торговых Программных Интерфейсов британской компании IG Markets Ltd провела статистическое исследование о связи числа баг-репортов и языков программирования на базе информации об открытых проектах на сайте "Центр деятельности мерзавцев" (GitHub.com, организация разрешена в России, за исключением некоторых периодов, когда она запрещена). Выяснилось, что наличие статической типизации и продвинутой системы типов не помогает в уменьшении ошибок, а порой даже вредит, в то время как меньше всего ошибок получается в программах на максимально простых языках.

Плотность багов у проектов с 10 звездами и более:


Теперь научно доказано, что [livejournal.com profile] theiced был прав: типы не нужны, а писать надо на Кложури. А также Эрланге и Го. Адептам сложных языков и развитых систем типов надлежит раскаяться, одуматься и перестать уже своими надуманными неработающими идеями отвлекать благородных донов, занятых TDD.
thedeemon: (faculty of numbers)
Говорили, на ноль нельзя делить, а вот британские учоные научились! Берешь хаскель и делишь себе, получаешь конкретные числа:
Prelude> floor (1/0)
179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216


Для 1, -1 и 0 ответы разные выходят.
thedeemon: (office)
Неплохое и не без юмора совсем вводное введение в ФП для ОО программистов, верующих в дизайн паттерны:

sermon

Sep. 29th, 2015 10:52 am
thedeemon: (office)
На днях мудрый [livejournal.com profile] _xacid_ разразился замечательной проповедью, прочитав которую даже человек с черствым сердцем непременно почувствует в груди огонь любви к божественному, пойдет обрежет себе ООП и начнет отращивать монады. Читать первый уровень ответов к этому сообщению.

LISP

Aug. 5th, 2015 09:46 pm
thedeemon: (office)
thedeemon: (office)
Посмотрел тут свежее выступление одного из активных пильщиков Идриса: David Christiansen - Coding for Types: The Universe Patern in Idris. Он там рассказывает, что вот в языках с зависимыми типами у нас типы вроде как первоклассные, можно их как обычные значения создавать, передавать и использовать, но вот паттерн-матчить по ним не положено - это отнимет бесплатные теоремы (id может начать возвращать 42 для всех натуральных аргументов, например) и помешает стиранию этих типов из рантайма. Не положено (надо бы сказать "нельзя", но по крайней мере несколько версий назад кое-какой простой матчинг по типам там работал), но порой очень хочется. Для этого есть дизайн паттерн: The Universe Pattern, заключающийся в том, что для интересующего нас набора типов мы делаем тип данных, их кодирующий (аки AST), где хотим матчимся по нему, а когда нужны сами типы, то просто отображаем их из этой кодировки. Например, есть у нас таблички, где поля могут быть строками, целыми или вещественными числами. Описываем это алгебраиком:
data Column = TEXT | REAL | INTEGER

и сразу делаем отображение в "настоящие" типы:
interpCol : Column -> Type
interpCol TEXT -> String
interpCol REAL -> Double
interpCol INTEGER -> Integer 

Надо превратить поле одного из этих типов в строку? Пожалуйста:
printCol : (c : Column) -> interpCol c -> String
printCol TEXT    x = x
printCol REAL    x = doubleToString x
printCol INTEGER x = intToString x  

Тут функция с двумя аргументами, где тип второго зависит от значения первого, т.е. зависимые типы как они есть. Можно вызвать printCol TEXT "hi", а можно printCol INTEGER 77, но printCol TEXT 77 уже не скомпилируется, будет ошибка типов.
Read more... )
thedeemon: (mosquito)
Есть такой подкаст о распределенных базах данных DevZen, почему-то выдающий себя за подкаст о программировании. Но недавно они сделали исключение, выгнали женщин и детей, пригласили двух замечательных гостей - Романа Чепляку, которого мы все любим за его Cartesian Closed Comics, и Дениса Шевченко, автора книжки "О Haskell по-человечески" - и получился довольно хороший и познавательный выпуск, рекомендую.

Роман рассказал, что в свое время интервьюировал не меньше двух десятков хаскеллистов в Киеве, и практически никто не смог во время интервью решить такую задачку: есть длинный список чисел, надо найти их среднее арифметическое за один проход по списку и О(1) памяти. Занятно.

FP is dead

Jun. 5th, 2015 12:37 am
thedeemon: (house)
.. as a topic. Помните, было такое "структурное программирование"? Люди в чатиках конца шестидесятых срались на тему СП vs. GoTo, кричали "considered harmful!", писали посты на своих печатных машинках, такая движуха была. И где оно все, почему прекратились срачи? Все основные языки впитали в себя (или взросли на) СП, и тема рассосалась. Наблюдая за интенсивностью тем об ФП на разных форумах, в ЖЖ, в журнале ПФП и прочих интернетах, в этом году могу констатировать аналогичную ситуацию: ФП как темы больше нет, расходимся. Все основные языки впитали в себя (или взросли на) ФП, по крайней мере полезные его части (первоклассные функции, ФВП, лямбды, замыкания, иммутабельность, произведение типов, копроизведение типов, экспонента, применение этого всего в первую очередь в виде map/filter/reduce), а бесполезные части оказались выкинуты на задворки, в уголке музея эзотерики на них всегда можно будет полюбоваться, но в основном только там. Думаете, другая часть ФП еще себя покажет, и расширение линз Кана вправо-вверх вдоль контравариантного функтора еще выстрелит? Не будет этого, dead end.
thedeemon: (office)
Андрей Александреску, который когда-то непоправимо и бесповоротно изнасиловал мозги С++ программистов книгой об изощрениях на С++ шаблонах, выступил на днях как тролль 78-го уровня:

Доклад с названием Generic Programming Must Go содержит фразы вроде "Generic Programming is fail" и "Concepts are fail". Но не обольщайтесь, он не содержит призывов переходить на Го, где нет генериков. Речь о другом.
Read more... )

Rust

Jan. 14th, 2015 03:18 pm
thedeemon: (office)
На днях вышла 1.0.0.alpha, решил наконец приобщиться. Почитал онлайн книжку. Если она не слишком много скрывает, язык довольно маленький и простой, это хорошо. Для начала сделал вариант для недавнего микробенчмарка про маленький интерпретатор. В тот раз добрые люди помогли ускорить наивные решения, так что все времена опустились ниже 1 секунды, что делает замеры менее осмысленными. Тем не менее, вот текущие результаты:

D - 0.40 s (при использовании LDC)
Rust - 0.44 s
OCaml - 0.57 s
Haskell - 0.85 s
(с одной закавыкой - Rust тут 64-битный, все остальные 32-битные, так уж получилось)

Т.к. опыт с Rust'ом у меня пока минимальный, впечатления смутные. Одной фразой - "ML в руках плюсовиков". Видишь знакомый набор из алгебраиков, паттерн-матчинга, лямбд, expression-based syntax, начинаешь писать как на ML, и тут на тебя выпрыгивает наследие С++: а ты здесь это значение насовсем передал (у нас move-семантика по-умолчанию, уж больно нам эта фича из С++ понравилась) или хотел лишь по указателю? Ах по указателю, тогда так и напиши везде, и где принимаешь, и где передаешь. А еще и писать туда хотел? Тогда не забудь при передаче &mut дописать. И это же выскакивает при паттерн-матчинге: вот тут ты поле алгебраика заматчил, тебе его так отдать или по ссылке? А обращаться хорошо с ней будешь?
Причем как-то странно сделано, вот есть структуры и есть туплы, разница между ними довольно косметическая, так? Можем пару значений передать как тупл, а можем как структуру. Сделаем пару одинаковых функций, складывающих два поля:
#[derive(Show)]
struct S { x : i32, y : i32 }

fn eat_struct(s : S) -> i32 { 
  s.x + s.y 
}

fn eat_tuple(t : (i32, i32)) -> i32 { 
  let (x,y) = t;
  x + y
} 

Обе получают аргумент по значению.
Теперь попробуем их повызывать:
fn main() {
  let s = S { x: 1, y : 2 };
  let t = (1, 2);
  let rs = eat_struct(s);
  let rt = eat_tuple(t);
  println!("{} {} {:?} {:?}", rs, rt, s, t);
}

И получаем ошибку:
hi.rs:18:39: 18:40 error: use of moved value: `s`
hi.rs:18   println!("{} {} {:?} {:?}", rs, rt, s, t);
                                               ^

Оказывается, когда мы структуру передали в ту функцию, мы ее отдали насовсем, это был move. А вот тупл скопировался, передача по значению, оригинал остается у вызывающей ф-ии. Неожиданно.

Еще занятный момент. В растовском варианте, что по ссылке выше, есть такое выражение:
1 + (if a[i] > a[j] { evalBlock(a, b1) } else { evalBlock(a, b2) })
Казалось бы, его, как в ML вариантах, можно заменить более простым:
1 + evalBlock(a, if a[i] > a[j] { b1 } else { b2 })
Но не тут-то было. Rust считает, что в первом аргументе evalBlock происходит мутабельное заимствование массива а, а при вычислении второго аргумента имеет место иммутабельное заимствование этого же массива. И хотя аргументы должны быть вычислены до вызова функции, и по времени эти два использования массива не пересекаются никак, Rust считает, что тут два параллельных заимствования, одно из которых мутабельное, что недопустимо.

Буду продолжать наблюдения. В целом штука занятная.
thedeemon: (office)
My story begins in Episode IV, when the Galactic Empire was nearing completion of the Death Star...

http://tagide.com/blog/2014/10/jedi-masters/
thedeemon: (office)
Для одной задачки всхотелось мне сделать интерпретатор крайне простого язычка: есть память на дюжину целых чисел и AST из трех операций - сравнение двух ячеек, копирование из одной в другую и обмен значениями меж двух ячеек. Стал делать на хаскеле и сразу столкнулся с тем, что наивное решение в лоб тормозит: аналогичный код на окамле в 4 раза быстрее, а на Ди - в 10 раз. Вот так выглядит мой позор на хаскеле:


data Exp = IfGt Int Int Block Block
         | Swap Int Int
         | Copy Int Int
         deriving Show

type Block = [Exp] 

eval :: STUArray s Int Int -> Exp -> ST s (STUArray s Int Int, Int)
eval a (IfGt i j b1 b2) = do
  ai <- readArray a i
  aj <- readArray a j
  let b = if ai > aj then b1 else b2
  (r, n) <- evalBlock a b 
  return (r, n+1)
eval a (Swap i j) = do 
  ai <- readArray a i 
  aj <- readArray a j
  writeArray a i aj
  writeArray a j ai
  return (a, 1)  
eval a (Copy i j) = do
  aj <- readArray a j
  writeArray a i aj
  return (a, 1)

evalBlock :: STUArray s Int Int -> Block -> ST s (STUArray s Int Int, Int)
evalBlock a blk = foldM f (a,0) blk where
  f (a,cnt) exp = fmap (\(r, n) -> (r, cnt + n)) $ eval a exp


А вот прямой перевод на Окамл, почти вчетверо быстрее:
type exp = IfGt of int * int * block * block
         | Swap of int * int
         | Copy of int * int
and block = exp list;;

let rec eval a = function
  | IfGt(i, j, b1, b2) -> 
      let (r,n) = evalBlock a (if a.(i) > a.(j) then b1 else b2) in
      (r, n+1)
  | Swap(i, j) -> 
      let ai = a.(i) and aj = a.(j) in
      a.(i) <- aj; a.(j) <- ai; (a, 1)
  | Copy(i, j) -> 
      a.(i) <- a.(j); (a, 1)

and evalBlock a blk = 
  let f (m, cnt) exp = let (r,n) = eval m exp in (r, cnt + n) in
  List.fold_left f (a,0) blk


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

Полные тексты тестов:
Haskell - 7.19 s
OCaml - 1.85 s
D - 0.69 s (использовался DMD - наименее оптимизирующий из компиляторов D, т.е. можно еще быстрее)

Upd: исправлен баг в окамловской версии, время перемеряно.
Upd2: не, не было там бага.
thedeemon: (office)
Открыл тут заметку.
Девайс с 1 GHz или около того процессором, 2д игрушка с 1 (одним, ОДНИМ!) маленьким движущимся объектом, и у людей возникают большие сложности с тем, чтобы получить хотя бы 25 кадров в секунду. Зато хаскель и FRP.Yampa, модно, молодежно.

yep

Sep. 26th, 2014 07:24 pm
thedeemon: (office)

(c) Paul Snively
thedeemon: (office)
Посмотрел тут свежее выступление известного программиста компьютеров в гамаке Р. Хики. Доклад про трансменьшители.

Помните, во всяких учебниках про ФП есть упражнения по выражению различных функций над списками через fold? Почему именно через fold, а не что-то другое? Да потому что это Котоморфизм Всемогущий: Read more... )

Ну так вот, увидел Хики, что fold это хорошо, но заметил, что реализуя через него операции над списками мы почему-то используем конструкторы списка. А при реализации оных для векторов - конструкторы векторов. Непорядок, недообобщение!



Только один-то конструктор он заметил, а про второй забыл:



Если conj заменить на построитель не-векторов, а [] оставить, будет банальная ошибка типов. В этой его кложури - еще и в рантайме. Ибо про функторы с алгебрами не думал, там-то тип сразу показывает о каких вариантах надо заботиться. Ну и предложил абстрагироваться, вынести конструктор из кода в параметр:



Получилось, что внутри там функция принимает такой конструктор (вроде cons или conj), фрагмент алгебры, a.k.a. reducer, и возвращает такой же. Ну а функции вида Хрень -> Хрень хорошо композятся. Придумал для такого преобразования reducer -> reducer новое имя: transducerинновация!. Но поскольку половину алгебры он в самом начале потерял, в таком виде оно не работает, конечно. Пришлось добавлять хаки. Хак первый: писал он на кложури, а она позволяет функции принимать разное число аргументов и в зависимости от этого вести себя по-разному. Ну и сделал, что ежели аргументов не дали, то пусть работает как вторая половина алгебры: пусть возвращает значение, соответствующее пустому списку. А еще захотел уметь прерывать обработку, не доходя до конца списка. Всякие хаскели это в foldr делают легко за счет ленивости: не обращайся к вычисленному хвосту, он и не будет вычисляться. А в кложури все иначе, поэтому сделал сигналирование о конце заворачиванием значения в специальную обертку, такой вот модный динамически-типизированный способ передать булев флаг. Ну и сделал третий вариант функции от двух аргументов, принимающий лишь один аргумент, в таком случае там она что-то сигналирует. В результате то, что выглядит как композиция функций, есть композиция троек функций (от 0, 1 и 2 аргументов), работающих с неожиданно типизированными вещами. Теперь весь мир побежал это дело переписывать на другие языки. Но мы-то знаем, что, учитывая форму этих алгебр-уменьшателей, речь все равно только о списках и эквивалентных им вещах, и поскольку среди всех таких структур список - самый общий (свободный моноид, панимаиш), то все эти трансменьшители сводятся к такому типу:
transducer: [a] -> [b]

Зато инновации!

Profile

thedeemon: (Default)
Dmitry Popov

September 2017

S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 26th, 2017 07:30 am
Powered by Dreamwidth Studios