Russian Lambda Planet

02 декабря 2016

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

CPS Interpreter in Rust Language

Итак, в прошлых постах мы построили парсер диалектов K, а именно: K3, K4, K5 и Q. Теперь пришла пора написать CPS интерпретатор, такой который смог бы крутить бесконечные циклы лямбдочки быстрее эрланга.

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

Вложенные контексты — это наш Environment или Dictionary, когда мы создаем дочерний контекст, например при аппликации лямбды, мы линкуем дочерний контекст с родителькому, поэтому в имплментациях акссесоров у нас будет рекурсивный Find — он не только должен вернуть значение по ключу, но и вернуть контекст в котором он это нашел в цепочке контекстов. Значения — это AST (чтобы не плодить много типов, мы просто некоторые конструкторы AST объявляем боксами Integer, String, Boolean, Float, поэтому в процессе работы интерпретатора он вычислит и положит результат в тот же тип AST, в байткоде виртуальной машины — это может выглядеть как просто состояние регистров и инструкции для загрузки или выгрузки констант), а Контексты — это счетчики ссылок на ячейки (AST, Rc<RefCell<Environment>>). Если сказать о контекстах высоко — то вложенные контексты соответствуют Сигма типу и являются свидетелями контекстуальной полноты.
pub struct Environment {
    parent: Option<Rc<RefCell<Environment>>>,
    values: HashMap<String, AST>,
}

impl Environment {
    pub fn new_root() -> Result<Rc<RefCell<Environment>>, Error> {
        let mut env = Environment {
            parent: None,
            values: HashMap::new(),
        };
        Ok(Rc::new(RefCell::new(env)))
    }
    pub fn new_child(parent: Rc<RefCell<Environment>>) -> Rc<RefCell<Environment>> {
        let env = Environment {
            parent: Some(parent),
            values: HashMap::new(),
        };
        Rc::new(RefCell::new(env))
    }
    pub fn find(&self, key: &String) -> Option<(AST, Rc<RefCell<Environment>>)> {
        match self.values.get(key) {
            Some(val) => Some((val.clone(), Rc::new(RefCell::new(self.clone())))),
            None => {
                match self.parent {
                    Some(ref parent) => parent.borrow().find(key),
                    None => None,
                }
            }
        }
    }

Интерпретатор хранит рутовый контекст.
pub struct Interpreter {
    root: Rc<RefCell<Environment>>,
}

Отложенные вычисления — используются нами для проскакивания цепочки AST, и форсинг когда достигли определенного события. Обычно во всех базовых функциональных библиотеках (типа PureScript и Elm) называется Lazy Type. У нас Lazy параметризирован контекстами и протоколом выполнения — Environment и Continuation. Вообще тут мистики никакой нет. Если посмотреть на любое выражение — то половина времени тратится на Defer и приблизительно половина на Force, причем все дефер обычно заканчиваются сразу парными форсами. Это сделано для того, чтобы вечные циклы крутились в нулевом стеке. Что еще можно сказать про этот интерпретатор? Я лично хотел добиться от этого интерпретатора идиоматичности, чтобы его понимал и прокурор и милиция. Я намеренно в посте исключил имплементации обычных выражений + и * чтобы показать суть интерпретатора. Так как многие знают что этого уже достаточно для моделирование вычислительных вселенных. По крайней мере такты интерпретатора уже можно считать. Если бы этот интерпретатор был клаудом, он бы чарджил и билил только форсы.
pub enum Trampoline {
    Defer(AST, Rc<RefCell<Environment>>, Continuation),
    Force(AST, Continuation),
    Return(AST),
}

Протокол исполнения: Лямбда исчисление + синтаксические расширения — ядро интерпретатора (Assign, Cond, Lambda, Call) которое создает контексты, делает по ним лукапы и биндит переменные при аппликациях. У нас не аппликативно-божественный (на subst, как в OM/EXE), а нормально-колхозный порядок бета редукции (ALGOL68, LUA, K), зато если поместиться в 32К L1 то можно сорвать большой куш, как это делают K и LuaJIT, остальные сосут с call-by-name причмокивая. Тут хочется быть максимально расширяемым, чтобы новые конструкторы AST ложились на этот протокол отложенных вычислений. Особой мистики тут не нужно, можно считать — это управляющим протоколом, вся магия будет происходить в векторном DSL, там целые блоки будут транслироваться в Lazy структуры итераторы Rust и выполняться в интерпретаторе как единые инструкции, для которых определен AST конструктор. Лямбда исчисление является свидетелем функциоальной полноты нашей системы. Если добавить сюда Пи тип, мы сможем превратить интерпретатор в теорем прувер? :-)
pub enum Continuation {
    EvaluateExpressions(AST, Rc<RefCell<Environment>>, Box<Continuation>),
    EvaluateAssign(AST, Rc<RefCell<Environment>>, Box<Continuation>),
    EvaluateCond(AST, AST, Rc<RefCell<Environment>>, Box<Continuation>),
    EvaluateFunc(AST, AST, Rc<RefCell<Environment>>, Box<Continuation>),
    EvaluateVerb(AST, AST, Rc<RefCell<Environment>>, Box<Continuation>),
    EvaluateAdverb(AST, AST, Rc<RefCell<Environment>>, Box<Continuation>),
    Return,
}

В CPS интерпретаторе самое главное — это цикл, который крутит AST дерево и создает отложенные вычисление, периодически форся вычисления. Обычно это проистодит в стиле Defer-Force, но все зависит от программ.
fn process(exprs: AST, env: Rc<RefCell<Environment>>) -> Result<AST,Error> {
    if exprs.len() == 0 {
        return Ok(AST::Nil);
    }
    let mut b = try!(evaluate_expressions(exprs, env, Box::new(Continuation::Return)));
    loop {
        match b {
            Trampoline::Defer(a, e, k) => b = try!(handle_defer(a, e, k)),
            Trampoline::Force(x, k) => b = try!(k.run(x)),
            Trampoline::Return(a) => return Ok(a),
        }
    }
}

handle_defer выглядит примерно так:
fn handle_defer(a: AST,
                env: Rc<RefCell<Environment>>,
                k: Continuation)
                -> Result<Trampoline,Error> {
    match a {
        AST::Assign(box name, box body) => {
            Ok(Trampoline::Force(body,
                                 Continuation::Assign(name, env, Box::new(k))))
        }
        AST::Call(box callee, box args) => evaluate_function(callee, env, args, k),
        AST::Name(name) => {
            match lookup(name, env) {
                Ok(v) => k.run(v),
                Err(x) => Err(x),
            }
        }
        x => k.run(x),
    }
}

evaluate_function разворачивает Name и деферит лямбду.
fn evaluate_function(fun: AST,
                     env: Rc<RefCell<Environment>>,
                     args: AST,
                     k: Continuation)
                     -> Result<Trampoline, Error> {
    match fun {
        AST::Lambda(box names, box body) => {
            Ok(Trampoline::Force(body, Continuation::Func(names, args, env, Box::new(k))))
        }
        AST::Name(s) => {
            match env.borrow().find(&s) {
                Some((v, x)) => evaluate_function(v, x, args, k),
                None => {
                    Err(Error::EvalError {
                        desc: "Function Name in all Contexts".to_string(),
                        ast: AST::Name(s),
                    })
                }
            }
        }
        x => {
            Err(Error::EvalError {
                desc: "Call Error".to_string(),
                ast: x,
            })
        }
    }
}

evaluate_expressions создает один отложеный такт интерпретатора, типа R(1).
fn evaluate_expressions(exprs: AST,
                        env: Rc<RefCell<Environment>>,
                        k: Box<Continuation>)
                        -> Result<Trampoline,Error> {
    match exprs.shift() {
        Some((car, cdr)) => {
            Ok(Trampoline::Defer(car,
                                 env.clone(),
                                 Continuation::EvaluateExpressions(cdr, env, k)))
        }
        None => {
            Err(Error::EvalError {
                desc: "Empty list".to_string(),
                ast: AST::Nil,
            })
        }
    }
}

Обработчики Лямбда исчисления простые, эвалуатор ложит и кладет в контексты, сравниватель сранивает, биндинг переменной биндит переменную.
impl Continuation {
    pub fn run(self, val: AST) -> Result<Trampoline,Error> {
        match self {
            Continuation::EvaluateExpressions(rest, env, k) => {
                if rest.is_cons() || !rest.is_empty() {
                    evaluate_expressions(rest, env, k)
                } else {
                    Ok(Trampoline::Force(val, *k))
                }
            }
            Continuation::EvaluateFunc(names, args, env, k) => {
                let local_env = Environment::new_child(env);
                for (name, value) in names.into_iter().zip(args.into_iter()) {
                    try!(local_env.borrow_mut().define(name.to_string(), value));
                }
                evaluate_expressions(val, local_env, k)
            }
            Continuation::EvaluateCond(if_expr, else_expr, env, k) => {
                match val {
                    AST::Bool(false) => Ok(Trampoline::Defer(else_expr, env, *k)),
                    _ => Ok(Trampoline::Defer(if_expr, env, *k)),
                }
            }
            Continuation::EvaluateAssign(name, env, k) => {
                match name {
                    AST::Name(ref s) => {
                        try!(env.borrow_mut().define(s.to_string(), val));
                        Ok(Trampoline::Force(AST::Nil, *k))
                    }
                    x => {
                        Err(Error::EvalError {
                            desc: "Can assign only to var".to_string(),
                            ast: x,
                        })
                    }

                }
            }
            _ => Ok(Trampoline::Return(val)),
        }
    }
}

Вот и весь интерпретатор (кроме правил для Verb и Adverb, там умножение и вычитание необходимые для факториала и Cond вообще говоря тоже, который в K языке повешен на Cast). Традиционно бенчмарки против Erlang написанном на С.
1> Fac = fun Factorial(X) -> case X of 1 -> 1; _ -> X * Factorial(X-1) end end.
#fun<1131414>
2> Fac(5).
120
3> timer:tc(fun() -> Fac(5) end).
{91,120}

Интерпретатор написанном на Rust:
"fac:{[x]$[x=1;1;x*fac[x-1]]};fac[5]"
test tests::fac ... bench:      16,850 ns/iter (+/- 1,169)

91 микросекунд (Erlang) против 17 микросекунд (O-CPS INTERPRETER)

02 декабря 2016, 23:49

29 ноября 2016

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

Угадайте язык по BNF :-)

Я сейчас пишу один язычок, у нас на самом деле в компании где я сейчас работаю, трое человек пишет этот язык. Еще один сотрудник недавно критиковал этот язык в ЖЖ, по делу конечно.

29 ноября 2016, 21:44

Векторный DSL

Надо как-то назвать язык. Назову его О. Задачи языка:

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

— Выстувать в роли векторного DSL для K Cell. Каждая K Cell — это по сути вектор или растовский итератор, поддерживающий все его интерфейсы и поддающийся векторизации. Есть также библиотеки распаралеливания этих итераторов.

Сейчас язык парсает основные диалекты K, Q, oK.js, а также Kona. В К мире не приянято писать декларативные парсеры, так как строятся ручные интерпетаторы с встроеным токенайзером. Но поскольку мы воспринимам К программу как DSL к итераторам, нам нужно все AST сразу для ленивого выполнения, поэтому так или иначе строить его нужно. Ну и еще листы в векторы сворачивать, все это тоже можно эффективно делать на этапе парсинга.

Покажу на примере, например нам нужно вычислить скалярное произведение двух векторов:
+/{x*y}[(1;3;4;5;6);(2;6;2;1;3)]

А теперь представим вместо очередей Ioverb устройства, индексы кольцевых буферов в стиле как мы идектируем потоки ввода выводы (0: и 1:) — "1212:" или "3600:".
+/{x*y}[1212:;3600:]

Это транформируется в растовский:
vec1.iter()
    .zip(vec2.iter())
    .map(|(i, j)| i * j)
    .sum()

И в итоге векторизируется LLVM в:
.LBB0_7:
	testq	%r8, %r8
	je	.LBB0_9
	movdqu	16(%rdx,%rax,4), %xmm2
	movdqu	16(%rdi,%rax,4), %xmm3
	pshufd	$245, %xmm2, %xmm4
	pmuludq	%xmm3, %xmm2
	pshufd	$232, %xmm2, %xmm2
	pshufd	$245, %xmm3, %xmm3
	pmuludq	%xmm4, %xmm3
	pshufd	$232, %xmm3, %xmm3
	punpckldq	%xmm3, %xmm2
	paddd	%xmm2, %xmm1
	movdqu	(%rdx,%rax,4), %xmm2
	movdqu	(%rdi,%rax,4), %xmm3
	pshufd	$245, %xmm2, %xmm4
	pmuludq	%xmm3, %xmm2
	pshufd	$232, %xmm2, %xmm2
	pshufd	$245, %xmm3, %xmm3
	pmuludq	%xmm4, %xmm3
	pshufd	$232, %xmm3, %xmm3
	punpckldq	%xmm3, %xmm2
	paddd	%xmm2, %xmm0

29 ноября 2016, 21:43

О Интерпретатор SPEC

Немного о том, как я написал парсер языка О. Хотя netch80 и ругает у себя в посте язык К справедливо, хочу попытаться зафиксировать основные правила синтаксиса и привнести некоторый порядок в язык, предоставив формальную нотацию для LR парсеров. Имплементация прототипа делалась на lalrpop — это нетабличный однопроходной LR парсер который поставляется с голимым регэксп токенайзером. Токенайзер вместо регекспов хочется кастомный на NOM, но руки не доходят.

Существует три вида скобочек: [], (), {} — множества, списки и лямбды. Другими словами это M-expressions, S-expressions и Лямбда-калкулус соответственно (который в К можно представить как Pi-calculus, так как K-Cell содержит вектор, а значит все параметры — это стримы, и если трактовать срабатывание функции на появление нового элемента в любом стриме-параметре, то это уже будет Пи-калкулус и CHR, штука которая полезна не только для моделирования самобалансирующего скедулера но для потокового бизнес роутинга).

> ()
> []
> {}

Ok(Nil)
Ok(Nil)
Ok(Lambda(Nil, Nil))


Эти Nil могут либо схлопываться, либо рости при встраиваниях. Например [[]] и (()) не изменяются при встраиваниях, а {{}} растет:

> (())
> [[]]
> {{}}

Ok(Nil)
Ok(Nil)
Ok(Lambda(Nil, Lambda(Nil, Nil)))


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

> ((()))
> ()()()
> [][]()
> {}{}{}

Ok(Nil)
Ok(Call(Nil, Call(Nil, Nil)))
Ok(Call(Nil, Call(Nil, Nil)))
Ok(Call(Lambda(Nil, Nil), Call(Lambda(Nil, Nil), Lambda(Nil, Nil))))


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

>  1 2 3
> (1 2 3)
> [1 2 3]
> {1 2 3}
> (1(2(3(4))))
> [1[2[3[4]]]]
> [[[[1]2]3]4]
> {1{2{3{4}}}}

Ok(Call(Number(1), Call(Number(2), Number(3))))
Ok(Call(Number(1), Call(Number(2), Number(3))))
Ok(Call(Number(1), Call(Number(2), Number(3))))
Ok(Lambda(Nil, Call(Number(1), Call(Number(2), Number(3)))))
Ok(Call(Number(1), Call(Number(2), Call(Number(3), Number(4)))))
Ok(Call(Number(1), Call(Number(2), Call(Number(3), Number(4)))))
Ok(Call(Call(Call(Number(1), Number(2)), Number(3)), Number(4)))
Ok(Lambda(Nil, Call(Number(1), Lambda(Nil, Call(Number(2), Lambda(Nil, Call(Number(3), Lambda(Nil, Number(4)))))))))


Если множество в своем списке-носителе содержит присваивания к именам то такой множество трактуется как словарь, если список множества — это просто имена — то это бинд параметр функции {[x;y;z]...}, если параметр множества если функция без параметров бинда, то x,y,z трактуются как имена контекста по умолчанию. Если члены списка словаря просто выражения, то это множество носитель параметров. Множества называются M-expressions.

> [1;2]
> function[1;2]
> [a:1;b:2]
> {[x;y]x*y+x}

Ok(Dict(Cons(Number(1), Number(2))))
Ok(Call(Name("function"), Dict(Cons(Number(1), Number(2)))))
Ok(Dict(Cons(Adverb(Assign, Name("a"), Number(1)), Adverb(Assign, Name("b"), Number(2)))))
Ok(Lambda(Cons(Name("x"), Name("y")), Verb(Times, Name("x"), Verb(Plus, Name("y"), Name("x")))))


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

> (1;2;3;4)
> [1;2;3;4]
>  1 2 3 4
> `a`b`c`d

Ok(List(Cons(Number(1), Cons(Number(2), Cons(Number(3), Number(4))))))
Ok(Dict(Cons(Number(1), Cons(Number(2), Cons(Number(3), Number(4))))))
     Ok(Call(Number(1), Call(Number(2), Call(Number(3), Number(4)))))
     Ok(Call(Symbol("a"), Call(Symbol("b"), Call(Symbol("c"), Symbol("d")))))


У меня получилась BNF нотация на 13 правил. Что скажете? Можно короче, красивее?

List:      AST = { "(" ")" => AST::Nil, "(" <l:exprlist> ")" => list(l), };
Dict:      AST = { "[" "]" => AST::Nil, "[" <l:exprlist> "]" => dict(l), };

Lambda:    AST = { "{" <m:exprlist> "}"                      => fun(AST::Nil,m),
                   "{[" <c:namelist> "]" <m:exprlist> "}"    => fun(c,m),
                   "{" "}"                                   => fun(AST::Nil,AST::Nil)};

Call:      AST = { <c:noun> <a:callcont>                     => call(c,a), };
NameList:  AST = { Name, <o:name> <m:namecont>               => cons(o,m), };
ExprList:  AST = { ExprCont, Expr, <o:expr> <m:exprcont>     => cons(o,m), };

CallCont:  AST = { Noun, <m:call>                            => m };
NameCont:  AST = { ";" => AST::Nil, ";" <m:namelist>         => m };
ExprCont:  AST = { ";" => AST::Nil, ";" <m:exprlist>         => m };

Noun:      AST = { Name, Number, Hexlit, Bool, Symbol, List, Dict, Sequence, Lambda, Ioverb };
Expr:      AST = { Noun, Call, Verbs, Adverbs, };

Verbs:     AST = {           <v:verb>               => verb(v,AST::Nil,AST::Nil),
                             <v:verb>     <r:expr>  => verb(v,AST::Nil,r),
                   <l:call>  <v:verb>     <r:expr>  => verb(v,l,r),
                   <l:noun>  <v:verb>     <r:expr>  => verb(v,l,r), };

Adverbs:   AST = {           <a:adverb>             => adverb(a,AST::Nil,AST::Nil),
                             <a:adverb>   <e:expr>  => adverb(a,AST::Nil,e),
                   <l:call>  <a:adverb>   <r:expr>  => adverb(a,l,r),
                   <l:noun>  <a:adverb>   <r:expr>  => adverb(a,l,r), };

Терминалы думаю написать на NOM попробовать, чтобы быстрее парсалось.
Number:    AST = { <n:r"\d+"> => AST::Number(u64::from_str(n).unwrap()), };
Hexlit:    AST = { <h:r"0x[a-zA-Z\d]+"> => AST::Number(u64::from_str_radix(&h[2..], 16).unwrap()), };
Bool:      AST = { <b:r"[01]+b"> => AST::Number(u64::from_str_radix(&b[0..b.len()-1], 2).unwrap()), };
Name:      AST = { <n:r"[a-zA-Z][-a-zA-Z\d]*"> => AST::Name(String::from(n)), };
Symbol:    AST = { <s:r"`([a-z][a-z0-9]*)?"> => AST::Symbol(String::from(&s[1..s.len()])), };
Adverb: Adverb = { <a:r"[\x27:\x5C\x2F]:?"> => Adverb::from_str(a).unwrap(), };
Verb:     Verb = { <v:r"[+\x2D*$%!&|<>=~,^#_?@.]"> => Verb::from_str(v).unwrap(), };
Ioverb:    AST = { <i:r"\d+:"> => AST::Ioverb(String::from(i),Box::new(AST::Nil)), };
Sequence:  AST = { <s:r"\x22(\\.|[^\x5C\x22])*\x22"> => AST::Sequence(String::from(&s[1..s.len()-1])), };



Этот парсер парсает все исходники К и Q которые мне попадались на глаза, включая диалекты типа Kona (K4) и oK.js (K5). Это около 128КБ, включая саму имплементацию Q, каталоги примеров других диалектов и корпоративный продакшиновский К код. Принципиальной и абсолютной совестимости я не хочу, но максимальное покрытие диалектов и высокая портируемость не помешает.

29 ноября 2016, 21:43

David Sorokins WebLog

Сетевое моделирование с Айвикой

Давно присматриваюсь к сетевому моделированию (англ. network simulation). Нахожу, что многое можно моделировать с помощью моей Айвики уже сейчас, в том числе, моделировать распределенно на кластере или параллельно на суперкомпьютере.

Основная идея такая. Обычно говорят о портах - источниках данных. В Айвике источники могут быть как активными, так и пассивными. Активный источник сам проталкивает данные дальше для обработки. Это у меня тип Signal a (или Signal m a в обобщенной версии). Тогда каналом будет просто преобразование одного сигнала в другой. Модуль будет функцией, отображающей входные сигналы на выходные.

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

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

Пассивные источники данных у меня в Айвике представлены потоками Stream a (или Stream m a в обобщенной версии). Их нужно запрашивать, чтобы вытянуть из них данные. Их можно распараллеливать для обработки, а потом снова сливать в один поток.

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

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

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

p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica} p.p2 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica; min-height: 14.0px}
В общем, у меня есть достаточно общий аппарат, который может быть применен к широкому классу задач на мой взгляд. Более того, используя модуль aivika-distributed, такие задачи можно обсчитывать распределенно на кластере или параллельно в случае необходимости. Как раз на днях значительно улучшил этот модуль.

написал dsorokin (noreply@blogger.com) 29 ноября 2016, 20:25

Распределенное моделирование c Айвикой

Обновил версию aivika-distributed, которую можно использовать для распределенного и параллельного моделирования. Реализована оптимистичная стратегия по методу Time Warp. В этой версии значительно улучшена синхронизация глобального времени. Используется алгоритм Самади. В общем, если соединения между узлами достаточно надежные, то распределенная имитация должна вполне хорошо работать.

Чтобы использовать эту версию, достаточно вооружиться документацией PDF по базовой версии Айвики. Здесь все то же самое, т.е. события, процессы, ресурсы, сигналы, потоки транзактов, все это применимо и к распределенной версии. Только типы будут выглядеть по другому. Там, где был Event a, станет Event DIO a и т.д.  Последний Event - это фактически монадный трансформер, но я решил не добавлять к его названию букву T, как это обычно делают, а сохранить все названия из базовой версии. Тому были причины.

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

Собственно, все! В следующем сообщении напишу, как это можно применить к сетевому моделированию (англ. network simulation)
p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica} p.p2 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica; min-height: 14.0px}

написал dsorokin (noreply@blogger.com) 29 ноября 2016, 20:23

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

Неизвестная Миру Лямбда Кодировка с CPS Континуатором

НАМО ЛЯМБДАГАРБХА

Итак, как вы все знаете, в PTS системах для кодирования индуктивных типов данных принято использовать лямбда исчисление. Все вы знаете про Church, Parigot, Scott кодировки. Если кто забыл, я быстро напомню! Но есть одна особая кодировка, которая круче чем все эти кодировки, но которая почему-то совершенно не описана в литературе. Кто найдет ее упоминание в интернете -- пишите сюда.

Будем использовать инфиксную скобочную форму записи лямбды: "(a b -> c)" означает "λ a b . c", чтобы λ не мусолила глаза и легче было распознавать узор последовательности.

1. Church кодировка. Самая простая. Она представляет структуры в виде своих правых фолдов. Будем рассматривать простейшие структуры данных натуральные числа. Они же используются дя чистого моделирования вселенных.

0 = (f x -> x)
1 = (f x -> (f x))
2 = (f x -> (f (f x)))
3 = (f x -> (f (f (f x))))

pred    = (n (g h -> (h (g succ))) (const zero) id) -- O(n), хуйня.
foldNat = (s z nat -> (nat s z))                    -- Нерекурсивный, заебись.

С ней есть "маленькая" проблемка: pred такого числа или tail списка занимает O(n).

2. Scott кодировка. Дана Скотт предложил кодирвать структуры не в виде их фолдов а в виде их паттерн мачинг элиминаторов.

0 = (f x -> x)
1 = (f x -> (f (f x -> x)))
2 = (f x -> (f (f x -> (f (f x -> x)))))
3 = (f x -> (f (f x -> (f (f x -> (f (f x -> x)))))))

pred    = (nat -> (nat (pred -> pred) _))                       -- O(1). Заебись.
foldNat = (s z nat -> (nat (pred -> (s (foldNat s z pred))) z)) -- Рекурсия, Хуйня.

Для такой кодировки у нас pred натурального числа занимает константу, но для выражения нужна рекурсия. А мы на это в Групоид Инфинити никак не можем пойти.

3. Кодировка Parigot. Является смесью Скотт и Черч кодировок. Паригот убирает рекурсию из фолдов.

0 = (f x -> x)
1 = (f x -> (f (f x -> (f x)) (f x -> x)))
2 = (f x -> (f (f x -> (f (f x))) (f x -> (f (f x -> (f x)) (f x -> x)))))
3 = (f x -> (f (f x -> (f (f (f x)))) (f x -> (f (f x -> (f (f x))) (f x -> (f (f x -> (f x)) (f x -> x)))))))

pred    = (nat -> (nat (_ pred -> pred) _)) -- O(1). Заебись.
foldNat = (nat -> (nat (fold _ -> fold) _)) -- Нерекурсивный, Заебись.

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

4. Кодировка CPS. Вместо нумералов черча мы храним континуаторы (c -> (c f x)). Описание этой кодировки вы не найдете в интернете ни в одном пейпере.

0 = (f x -> x)
1 = (f x -> (f (c -> (c f x)) (f x -> x)))
2 = (f x -> (f (c -> (c f x)) (f x -> (f (c -> (c f x)) (f x -> x)))))
3 = (f x -> (f (c -> (c f x)) (f x -> (f (c -> (c f x)) (f x -> (f (c -> (c f x)) (f x -> x)))))))

pred    = (nat -> (nat (_ pred -> pred) _))                   -- O(1). Заебись!
foldNat = (s z nat -> (nat (cont pred -> (s (cont pred))) z)) -- Нерекурсивная Заебись!

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

Бенчмарк CPS кодирвки против Church кодировки:
Pack/Unpack 1 000 000 Inductive Nat Church:  {410682,#Fun}
Pack/Unpack 1 000 000 Inductive Nat CPS:     {712684,1000000}
Pack/Unpack 1 000 000 Inductive Church List: {717695,'_'}


Типа в два раз медленнее.

%  data nat: * :=
%       (zero: () → nat)
%       (succ: nat → nat)

% Church
nat    () -> [fun (Succ) -> 1 + Succ end, 0 ].
zero   () -> fun (Succ) -> fun (Zero) -> Zero end end.
succ   () -> fun (Nat) -> fun (Succ) -> fun (Zero) -> Succ((Nat(Succ))(Zero)) end end end.

% CPS
nat1() -> [fun (F) -> fun (X) -> F(X) + 1 end end, 0 ].
zero1() -> fun (F) -> fun (X) -> X end end.
succ1() -> fun (Z) -> fun (F) -> fun (X) -> (F(fun(C) -> (C(F))(X) end))(Z) end end end.


https://github.com/groupoid/om/blob/master/src/cc.erl

ОМ ЛЯМБДА ГАРБХА ХУМ

29 ноября 2016, 19:12

28 ноября 2016

beroal

достаточно одной функции

Из свойства суммы морфизмов (например, для 3-местной суммы: A_0+A_1+A_2→B ≅ (A_0→B)×(A_1→B)×(A_2→B)) следует, что несколько функций можно заменить на одну. Говоря языком простых программистов, семейство функций можно заменить на одну глобальную функцию, которая принимает имя функции из этого семейства и аргумент и вычисляет функцию, имя которой приняла.

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

28 ноября 2016, 08:26

24 ноября 2016

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

Лямбда Калкулус на Стримах

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

Плюсы такой системы: интеграция интерпретатора и паралелизатора стримов с интерпретатором лямбда калкулуса в единую библиотеку комбинаторов. Наряду с векторизирующими Fold, Map, Over, Scan, Filter комбинаторами мы имеем Lambda, Call, Cond, Assign. Дальше синтаксические конструкции дерева могут расширятся — мы просто ложим файл хендлер единой функции poll соотв. комбинатора.

Посмотрел бегло интернет но такого чтобы имплементации такого интерпретатора — то нет, не найти. Може я гоню или идея ок? Простой и элегантный векторизирующий лямбда интерпретатор. В таком интерпретаторе имплементация размазана по веткам дерева, в отличие от классических интерпретаторов об одном switch.

Может кто знает пейперы какие есть?

24 ноября 2016, 23:58

23 ноября 2016

nponeccop

Габриэль жжот

http://www.haskellforall.com/2016/07/auto-generate-service-api-endpoints.html
{-# LANGUAGE DeriveGeneric #-}

import Server.Generic

data Command
    = Add      Double Double
    | Multiply Double Double
    deriving (Generic)

instance ParseRecord Command

handler :: Command -> IO Double
handler (Add      x y) = return (x + y)
handler (Multiply x y) = return (x * y)

main :: IO ()
main = serveJSON 8080 handler
If you run the above code, you get a server that has two endpoints:
/add/:double/:double
/multiply/:double/:double
You can run the server and test that they work:
$ curl 'localhost:8080/add/2/3'
5
$ curl 'localhost:8080/multiply/2/3'
6
Ну то есть, если по русски, - пейнлесс тайпед рест

23 ноября 2016, 03:09

HNC - очередная перезагрузка

HNC задумывался как small hackable codebase, но с хакабилити получилось не очень. В-основном, из-за высокотехнологичности - куда ни плюнь, попадёшь в пейпер. Что не обязательно хорошая черта, но помогает уменьшить размер и держать меня мотивированным. Но кроме параморфизмов, мешает ещё и монолитная структура. Буду её разделять. Ну и лигаси (SPL) можно вырезать, всё равно там чекер нерабочий.

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

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

Минимально понадобится:

1. Парсер

- переписать на синтаксис с отступами, тогда я сделать не мог, т.к. не знал монад
- вырезать лигаси
- добавить while и :=
- добавить информацию о строке-столбце
- добавить парсинг нескольких топ-определений

2. Тайпчекер

- Оставить на UUAG и unfication-fd, но синтезировать дополнительный атрибут - AST, декорированное типами. Сейчас эта декорация сидит внутри UUAG и как бы фьюзится, тут же потребляясь кодогенератором С++, т.е. снаружи UUAG не видна. Соответственно, человек не может посмотреть, какой результат выдает чекер - трассировка сгенерированного UUAG катаморфизма повергнет его в ступор. И не может легко его забрать к себе, поскольку в UUAG нет внутренней модульности атрибутов и не очевидно, какие атрибуты ему нужны, а какие приватны для чекера.
- добавить while и :=
- добавить тайпклассы. Без Ord, Eq, Show жизнь не мила

3. Оптимизатор

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

На самом деле он вообще требует только графа, GraphCompiler/GraphDecompiler у меня и так уже отделены. Но конечно полный игрушечный пайплайн (парсер-графкомпилер-оптимизатор-графдекомпилер-приттипринтер) нужен, поскольку легче ковырять руками, термы понятнее, чем текстовое представление из графа. Можно убрать из декомпилера восстановление дерева скоупов и оставить только восстановление имён, опять же чтобы было понятнее.

4. Классификатор-кодогенератор

Это самый адов ад, просто из-за дебилизма С++ как низкоуровневой хрени, но сейчас пользователь именно его видит в первую очередь https://github.com/nponeccop/HNC/blob/master/Bar.ag#L88 и пугается.

Можно оставить как есть (с зафьюженным модифицированным чекером из п.2, благо в UUAG это выглядит просто как инклуд).

5. AST генерируемого подмножества С++ и его приттипринтер

Они и так отделены в CPP.Intermediate и CPP.Visualise, но можно ещё более отделить в какой-нибудь Data.CPP. Увидел тут, что часть приттипринтера лежит в CPP.BackendTools, надо исправить.

6. Тривиальные бекенды

Допилить Lean (который не тривиален, поскольку типы, но прост), и запилить какие-нибудь JS и PHP. А че, даже парсер + чекер + кодоген в ПХП будет прикольной игрушечкой кому-нить.

23 ноября 2016, 02:25

22 ноября 2016

nponeccop

M-божественность

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

Скажем, asm.js - это попытка сделать Javascript более SSA-божественным, поскольку иначе всякие динамические фичи показывают хуй. OpenCL во многом мотивирован желанием божественности относительно полиэдрической векторизации.

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

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

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

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

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

22 ноября 2016, 19:56

HNC - Этап Кодогенератора

Задачей было из Милнеровского лет-полиморфного ЛИ получить C++ путём буквального кодирования замыканий классами, функций - boost::function, а полиморфизма - шаблонами. Ну, и чтоб работало совместно с вызовом деструкторов при выходе из блока, и рушилось в рантайме при фунаргах.

AST бралось из быстро написанного на Парсеке парсера и аннотировалось типами с помощью чекера inv2004. Притти-принтинг С++ как таковой тоже не составлял трудностей, основная трудность - в классификации идентификаторов из ЛИ в один из 13 подвидов, которые в С++ выглядят по-разному.

Вот первые 5 из 13 способов которыми может транслироваться милнеровская аппликация a и x в зависимости от относительного "дебрюйновского" положения a и x и кучи других факторов:
data CppQualifier
	= CppAtomVar			-- a(x), x(a)
	| CppContextVar			-- a(ctx.x), ctx.x(a)
	| CppContextMethod		-- a(hn::bind(ctx, &local::a), ctx.x(a)
	| CppFqConst String		-- a(aaa::bbb::x)
	| CppFqMethod String		-- a(&aaa::bbb::x), aaa::bbb::x(a)
        | ...
При этом 13 это не все случаи, поскольку я не допилил и есть падающие тесты.

В процессе написания выяснилось, что как не пиши классификатор - выходит атрибутная грамматика. Поискал грамматики на хакадже, нашёл какую-то недоделанную на тот момент на тайп-фу, плюнул и нашёл Utrecht University Attribute Grammar Compiler, который кондовый препроцессор в духе Happy безо всякого тайп-фу, только вместо генерации AST генерит функцию из наследуемых атрибутов в синтезированные https://wiki.haskell.org/The_Monad.Reader/Issue4/Why_Attribute_Grammars_Matter , которая у меня и так была.

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

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

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

Да и даже если б я пробился - всё равно столь чудовищные монстры меня не устраивали, и я решил, что пора браться за оптимизатор.

22 ноября 2016, 03:20

Haskell actively rewards worst practices and punishes best practices!

По материалам Габриэля нашего Гонзалеса.

1) Poor performance

The path of least resistance is to use linked lists and strings instead of text and vector. This problem is so pervasive that I see even respected and experienced library authors who care a lot about performance succumb to the convenience of these less efficient types every once in a while.

2) Excessive abstraction

As you learn the language you begin to realize that Haskell makes some types of advanced abstraction very syntactically cheap and some people get carried away. The language fosters and encourages "architecture astronauts". The temptation to play with all of Haskell's abstract facilities is so strong for some because for those people abstraction is too fun!

3) Unchecked exceptions

A lot of people mistakenly use error instead of throwError without realizing the consequences of doing so. I've seen otherwise very smart and talented Haskell programmers get this wrong.

error is the worst way to throw a Haskell exception because it is:
- marked pure, so it can strike anywhere
- asynchronous, so it can strike at any time
- completely invisible at the type level
- triggered by accidental evaluation

22 ноября 2016, 00:24

21 ноября 2016

nponeccop

HNC, Windows, SublimeHaskell и stack

Глобальная претензия к SublimeHaskell всего одна - https://github.com/nponeccop/HNC не поддерживается, т.к. кастом билд использует новые фичи кабала 1.24 (setup-depends), которые не поддерживаются стеком, из-за чего не получается собрать HNC стеком, а сборку кабалом мне было лень сетапить под виндой. Претензию выставлять в гитхабе нет смысла поскольку это баг стека, который уже есть в трекере стека, а под кабалом может оно и заработает. Штатно я (и тревис) собираем HNC кабалом под линуксом, но там из-за бага в ядре нет иксов под используемым мной нестандартным гипервизором.

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

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

Тестил только https://github.com/nponeccop/HNC/blob/master/HNC.hs#L41-L60

Чего хочется, находясь в теле ff (что я попробовал, и не получилось):

- комплита локальных идентификаторов, пусть даже текстового - dump должен предлагать dumpOptFlag и dumpGraphFlag
- комплита qualified imports - M. должно предлагать комплит экспортов из Data.Map
- правильной подсветки guards (этот баг есть в трекере саблайма). Причем лично для меня безглючность подсветки важнее фичастости - т.е. лучше некоторые сущности отдельным цветом не выделять вообще, чем выделять их каждый раз разным цветом.

Что я не попробовал, но попробую, как только начнет собираться:

- https://github.com/nponeccop/HNC/blob/master/Test/Main.hs должен видеть QuickCheck и HUnit (это часто не поддерживается, поскольку Test.Main считается принадлежащим другому таргету в SPL.cabal где quickcheck не указан в build-depends)

- https://github.com/nponeccop/HNC/blob/master/CPP/CompileTools.hs должен видеть Bar (это как правило не поддерживается, потому что о местонахождении Bar знает только плагин uuagc-cabal, который говорит это Кабалу. Т.е. если вместо спрашивания у кабала пытаться угадать - будет хуй. Высший пилотаж там же - это догадаться, что файлов Bar.hs у меня минимум два (разные файлы в разных таргетах) и соответственно предлагать 2 места при go to definition у AG.compile2

- https://github.com/nponeccop/HNC/blob/master/HN/MilnerTools.hs - на нём любили падать все, уж не припомню почему

21 ноября 2016, 23:10

Готовы к продакшену

Вот уж не знаю, у одного меня ли так, но я постоянно использую инструменты за пределами некоего happy path воображаемого их разработчиками. Причём на всех языках - перле, жс-ноде, с++ и х-е (заметьте, выбор языков тоже не прямолинейный, нет чтобы на жабопитоне).

В данном случае HNC не собирается стеком, ибо у стека с мая незакрытая фича https://github.com/commercialhaskell/stack/issues/2094

Фейспалм. Но как следствие, SublimeHaskell не получит отрицательного вердикта, хотя всё к тому идёт. Хотя то немногое, что я видел работающим, работало очень шустро, это не какой-то там ghc-mod.

Впрочем, 500 багов и 2000 звезд у стека говорит о том что таки кто-то юзает. ФП вышло в массы (ну, относительно).

21 ноября 2016, 01:48

20 ноября 2016

nponeccop

Вмемориз!

-- | Monomorphic containers that can be mapped over.
class MonoFunctor mono where
    -- | Map over a monomorphic container
    omap :: (Element mono -> Element mono) -> mono -> mono
    default omap :: (Functor f, Element (f a) ~ a, f a ~ mono) => (a -> a) -> f a -> f a
    omap = fmap

20 ноября 2016, 07:48

stack install hsdev

Этот саблайм-хаскель требует себе hsdev - типа NIH ghc-mod с человеческим лицом от создателя саблайм-хаскеля. ghc-мод тормозит, а в автокомплите, вешающем vim на две секунды, нет никакого смысла. Ну и, чтобы два раза не вставать, ghc-mod не умеет в комплишен локальных идентификаторов, типа комплитьте их текстово, а у нас только импортные идентификаторы, поскольку текстово они комплитятся не очень.

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

Виндовые инструкции стека, конечно, линуксоидное ололо - Дефолтовые Пути, Пропатчьте Ваш Патх, Установите Эту Переменную Непременно До и тому подобное пионерство.

Короче, не стал я трогать их инсталлятор палкой (разумеется, это был нсис), а распаковал стек.ехе из зипа. И пока работает почему-то, без патхов. Создал - вытянул - собрал тестовый проект из шаблона, романтика!

Дошла очередь до hsdev. Поскольку кабала не наблюдается, да и стек есть - решил stack install hsdev. Ну и обнаружился stack hell: старый haskell-src-exts несовместим с hsdev, а новый не поддерживаетcя предложенным мне по дефолту lts-снапшотом.

Ну я не стал со снапшотами играться, а также знал что там действительно попереломали всё в src-exts и по-моему даже снойман заплакал, так что взял в руки напильник, и прописал в stack.yml тестового проекта лжезависимости:
resolver: lts-7.9

extra-deps:
- haskell-src-exts-1.18.2
- simple-log-0.5.0
- hdocs-0.5.0.1
- hlint-1.9.37
Всё, стек закукарекал и скопировал мне собранные экзюшники, вы не поверите, в %APPDATA%\local\bin. С одной стороны, конечно, это прогресс - традиционно говнолюди кладут если не в %WinDir%\system32 - так в c:\novayagovnopapkalatinicejbezprobelov\usr\local\bin. C другой, 588 метров роуминг профайла означают, что количество энтерпрайз-пользователей у них нулевое. Одни линупсоиды, учоные да хеллоувордисты.

Померял внимательнее - 1.2 гига роуминг профайла, и 1.7 гб нероумящихся. Видимо, писали разные люди. Так что гхц+мсис ставятся в локальный профиль, а всё остальное (например, собираемые либы и бинарники) - в роумящийся.

Да, ещё вспомнил пидарасню. 7z.exe как-то не дружит с дефолтовой антималварью. В результате пишется на SSD 3 метра в секунду, и 3 процента цпу и 0.2 размер дисковой очереди. Короче, 7z ничего не ест, но тормозит. Но в то же время антималварь отъела себе целое ядро. В-общем, родная однопоточная пидарасня подралась с неродной. Тоже однопоточной и тоже пидараснёй.

20 ноября 2016, 05:30

Фак ю интегрейшон

Leksah Haskell IDE собирается тревисом. Последний зелёный билд был 5 месяцев назад. Всем похуй™

Но хотя бы новый код продолжают хуячить!

20 ноября 2016, 01:15

Гниём вместе

Ещё одной Haskell IDE стало меньше (после как минимум Visual Haskell и FPComplete IDE):

EclipseFP is currently NOT maintained anymore. Feel free to fork and take up maintainership!

Событие произошло в мае 2015, т.е. уже более года как. А была наверное лучшей IDE, не считая богомерзкого емакса.

Тут можно старый анекдот про "нет спроса" вспомнить:

- Почему у вас нет в продаже черной икры? - спросил иностранец.
- Нет спроса!
Тот не поверил и целый день проторчал возле прилавка.
Действительно, никто не спросил.

20 ноября 2016, 00:50

19 ноября 2016

nponeccop

Когда в руках профунктор

Профункторы - это штуки, похожие на функции вида M a -> N b, к которым можно прикомпозить слева или справа другие функции:
class Profunctor p where
  lmap :: (c -> a) -> p a b -> p с b
  rmap :: (b -> d) -> p a b -> p a d

Метафорически, это "(c -> a) . (a -> b) . (b -> d)". Т.е. если к (a -> b) прилепить слева (с -> a) - то получим (c -> b). А если слева ничего не прилепливать, а справа прилепить b -> d - то получим a -> d. Есть ещё dimap, прилепливающий сразу с двух сторон, и получающий с -> d из a -> b.

В-общем, лонг стори шот, Data.Map похож на функцию из ключа в значение, и я решил я спрятать констрейнт в экзистеншиал и залепить инстанс:
{-# LANGUAGE GADTs, TypeFamilies #-}
import qualified Data.Map as M
import Data.Profunctor
import Prelude hiding (lookup)

data MapPK k v where
        MapPK :: Ord i => (k -> i) -> (M.Map i v) -> MapPK k v

instance Profunctor MapPK where
        dimap f g (MapPK ff mm) = MapPK (f `lmap` ff) (g `fmap` mm)

lookupPK k (MapPK f m) = M.lookup (f k) m
Тут для симметрии вместо lmap для (->) должен был идти совпадающий с ним Data.Functor.Contravariant.contramap, но я поленился.

В-общем, интересно, можно ли эту конструкцию кметтизировать - обобщить и встроить в библиотеку типа keys или lens. А может, кто-то уже.

19 ноября 2016, 04:30

18 ноября 2016

nponeccop

Загадка "Кметт изобретает reinterpret_cast"

import Data.Functor.Contravariant (contramap)

coerce :: (Contravariant f, Applicative f) => f a -> f b
coerce = contramap (const ()) . fmap (const ())
Что тут происходит? Комменты скринятся.

18 ноября 2016, 23:49

17 ноября 2016

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

Emily Riehl - Category Theory in Context

Table of contents
Preface
Chapter 1. Categories, Functors, Natural Transformations
Chapter 2. Universal Properties, Representability, and the Yoneda Lemma
Chapter 3. Limits and Colimits
Chapter 4. Adjunctions
Chapter 5. Monads and their Algebras
Chapter 6. All Concepts are Kan Extensions
Epilogue: Theorems in Category Theory


https://golem.ph.utexas.edu/category/2016/11/category_theory_in_context.html
(внутри ссылка на бесплатный pdf)

написал Александр Грызлов 17 ноября 2016, 14:28

16 ноября 2016

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

Блокчейн для формальных теорий

http://qeditas.org

Bitcoin is for money, Ethereum is for computation, Qeditas is for deduction

Qeditas is a project to apply block chain technology to support the construction of a library of formalized mathematics.
It is intended to be a realization (or possibly revival) of the QED project, as described in the QED Manifesto.

Со ссылкой на манифест из универсистета Немийгена. Дожили до метаверификации :-) Чтобы паленые свои теоремы не распространяли направо на лево!

16 ноября 2016, 00:54

14 ноября 2016

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

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

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

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

написал Dark Magus (noreply@blogger.com) 14 ноября 2016, 09:53

12 ноября 2016

nponeccop

Маккарти изобретает лисп

Rumor has it that the name MapReduce is not even derived from these functions in FP, but rather from “reduction of maps”, as most of the datasets processed by the original Google system were maps (sets of key-value pairs). An older API even referred to a MapReduce program as a “MapReduction”.

12 ноября 2016, 21:32

Minimal блядь

Minimal complete definition
null, (take, drop | splitAt), (revTake, revDrop | revSplitAt), splitOn, (break | span), intersperse, filter, reverse, uncons, unsnoc, snoc, cons, find, sortBy, length, singleton

12 ноября 2016, 18:02

Перекметтифицировать Кметта непросто!

Кметтификация через профункторы почти не удалась - cata/ana являются частным случаем hylo (c "тривиальной" коалгеброй/алгеброй соответственно), а отец всех схем hylo симметричный, и с ним ничего не сделаешь, получаются соревнования по перетягиванию одеяла на себя.
{-# LANGUAGE LambdaCase, FlexibleInstances, MultiParamTypeClasses #-}
module Main where

import Data.Profunctor
import Data.Functor.Foldable
import Control.Newtype
import Data.Function

cataR f = hyloR f project
anaR f = hyloR embed f

hyloR :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
hyloR f g = fix (protoHylo4 f g)

protoHylo1, protoHylo2, protoHylo3, protoHylo4
        :: Functor f => (f b -> b) -> (a -> f a) -> (a -> b) -> a -> b

protoHylo1 f g c = f . fmap c . g
protoHylo2 f g c = under Costar (lmap c) f . g
protoHylo3 f g c = f . under Star (rmap c) g
protoHylo4 f g = dimap g f . fmap

instance Newtype (Costar f d c) (f d -> c) where
        pack = Costar
        unpack = runCostar

instance Newtype (Star f d c) (d -> f c) where
        pack = Star
        unpack = runStar

sumR = \case
        Cons a b -> a + b
        Nil -> 0 :: Int

main = print $ 42 == cataR sumR [40, 2]

12 ноября 2016, 02:52

11 ноября 2016

nponeccop

Дальнейшая кметтификация кода Кметта

Легко видеть™, что алгебра в катаморфизме из recursion-schemes - это в точности профунктор Сostar из profunctors. Коалгебра в анаморфизме - соответственно Star.

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

Интересно отрезать хаки с project/embed/Base и посмотреть, что ещё интересного профункторность нам готовит.
{-# LANGUAGE LambdaCase, FlexibleContexts, NoMonomorphismRestriction #-}
module Main where

import Data.Profunctor
import Data.Functor.Foldable

type Coalgebra t a = Star (Base t) a a
type Algebra t a = Costar (Base t) a a

class Functor (Base t) => R t where
    projectR :: Coalgebra t t

type CataR t a = Algebra t a -> t -> a

cataR :: R t => CataR t a
cataR f = c where c = runCostar (lmap c f) . runStar projectR

instance R [a] where
    projectR = Star $ \case
        a : b -> Cons a b
        [] -> Nil

sumR = Costar $ \case
    Cons a b -> a + b
    Nil -> 0

main = print $ (42::Int) == cataR sumR [40, 2]

11 ноября 2016, 10:34

08 ноября 2016

Ратибор

Структура данных с приятными свойствами

Небрежный плод моих забав,
Бессонниц, лёгких вдохновений.

На GitHub: https://github.com/vadimvinnik/multi-trie
На Hackage: https://hackage.haskell.org/package/multi-trie
Отдельно - PDF с лежащим в основе математическим понятием: https://drive.google.com/file/d/0B92c_8xqCcoLZVdJUHF0Nk5obGs/view?usp=sharing

08 ноября 2016, 00:10

06 ноября 2016

nponeccop

Процесс кметтификации

Читая на ночь репозы Кметта, наткнулся на https://hackage.haskell.org/package/folds

В ридми указано, что к процессу кметтификации идеи некоего Макса Рабкина о композабельных фолдах, помимо Кметта, приложили руку Конал Элиотт и Габриэль Гонзалес.

06 ноября 2016, 05:23

31 октября 2016

nponeccop

Медленное распиливание

Cнова попилил. Тайм трекер показал, что на эту хуйню ушло 4 часа, типа 3 ч 20 в путте и ещё 40 мин на сайтах хакаджа и гитхаба.

Интересно, есть ли какие-то техники тренировки производительности. Не для х-я конечно. По ощущениям, на других языках примерно те же яйца у меня.

31 октября 2016, 21:26

29 октября 2016

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

String Diagrams for Free Monads

We show how one can reason about free monads using their universal properties rather than any concrete implementation. We introduce a graphical, two-dimensional calculus tailor-made to accommodate these properties.

Maciej Piro ́g, Nicolas Wu: https://people.cs.kuleuven.be/~maciej.pirog/papers/free-strings.pdf

29 октября 2016, 10:31

22 октября 2016

nponeccop

Новости HNC

Попереливал HNC из пустого в порожнее для разминки.

Чует сердце, пора отказываться от хака с эмуляцией while через функцию whileF и как Милнер лепить while в коре. Это, впрочем, и так планировалось, но похоже, отложить не получится, и починить кодогенерацию из whileF будет труднее чем сделать "прямо", с бейсик блоками и этим всем. Благо Hoopl есть.

22 октября 2016, 07:39

21 октября 2016

nponeccop

Not Invented Here

На хакадже есть 5 функций Bool -> a -> Maybe a и 3 флипнутых варианта того же самого

21 октября 2016, 22:46

18 октября 2016

rssh

current [scala-{symposium, UA-Харьків, courses in codespace} ]

1. Буду рассказывать о scala-gopher на scala-symposium [http://conf.researchr.org/track/scala-2016/scala-2016 ]; ну раз все равно в Амстердам ехать - останусь на весь SPLASH [http://2016.splashcon.org/ ]; Так что кто будет там в это время - дайте знать. Ну и на тему бытовых вопросов (типа как покупать симку в аэропорту итд ) хотелось бы с кем-то поговорить..

2. ScalaUA / Харьков ориентировочно будет 10 декабря (правда пересекается с f.by -- в принципе еще не поздно перенести - надо подумать). Кто хочет прокатится в Харьков с докладом -- скажите, pls.

3. В ноябре буду вести более или менее фундаментальный курс по scala (80 часов): http://www.codespace.com.ua/courses/scala/
Это может быть облегчить нашим разработчикам расширения команд: можно взять juniora с опытом на java и послать ко мне на курсы || с введением в реальный проект.

18 октября 2016, 08:35

nponeccop

Ещё один Haskell sandbox

http://blog.ezyang.com/2016/05/announcing-cabal-new-build-nix-style-local-builds/

Короче, в cabal 1.24 добавили new-configure и new-build :)

Ну, и чтоб два раза не вставать, есть новые коммиты в UHC :)

18 октября 2016, 00:56

16 октября 2016

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

EXE/OM in Rust

Первое решение, или точнее сказать первый pivot в выборе технологии — решено использовать в качестве языка имплементации Rust вместо Erlang, для сертифицированных сред — это лучше, достаточно иметь сертифицированный LLVM, думаю эту часть на себя скоро возьмет индустрия. Судя по тому, как Rust упаковывает в битики деревья и рекорды, проектировали его грамотные люди. Пускай вы не найдете формальной спецификации на язык, кроме The Rust Reference и двух книжек, но вы можете писать enum с параметрами (привет GADT и индуктивные типы), и вменяемая работа с рекордами и их интерфейсами. Синтаксис вообще как я люблю, большинство ключевых слов трехсимвольные (use, mut, pub, mod, ...) — поэтому помещается в 4-х спейсовую табуляцию, вообщем круче руби и эликсир даже. Есть типизированные макросы на таком AST:

item: an item
block: a block
stmt: a statement
pat: a pattern
expr: an expression
ty: a type
ident: an identifier
path: a path
tt: either side of the => in macro rules
meta: the contents of an attribute


Я поискал по гитхабу, нашел порты scalaz и даже категорные библиотеки. 3 штуки фьючерсов и пачку сетевых стеков. Сейчас (1.12) все юзают mio на базе net2. Хотя я находил нормальные NOBLOCK сервера через libc, нафига mio/net2 еще у меня под вопросом. Несколько FRP библиотек.

AST OM на Rust:



В ближайжее время, когда попробую Rust на вкус, напишу про одну неизвестную кодировку, которая круче чем париготовская и скотта даже. И заодно потестирую как LLVM сгенеренний растом фолдит индуктивный лист в этой кодировке. Там конечно тоже нужны self-типы (другая, более слабая форма Fixpoint), но кодировка интересная, так как обладает всеми параметрами продакшин кодировок: термы не растут экспоненциально как в париготе, тейл списка вычисляется за одну операцию.

В Visual Studio Code все прикольно и работает вместе с LLDB дебагером.

Воообщем ждите новостей об EXE/OM на Rust.

--------------------------
[1]. http://aturon.github.io/blog/2016/09/07/futures-design/
[2]. https://lise-henry.github.io/articles/optimising_strings.html
[3]. https://github.com/AndyShiue/pts
[4]. https://github.com/freebroccolo?language=rust&tab=repositories
[5]. http://always-learning.timmcnamara.nz/2016/10/15/borrow-checker-escape-hatches/

16 октября 2016, 16:42

03 октября 2016

nponeccop

Устраняем кодирование контрол-флоу юнитами

По совету друзей™ почитал тут A Proposal for Standard ML, Milner, 1984

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

а) and/or
б) if
в) while

Он там их дешугарит в разделе "6. Derived Forms" в стиле учоных (if у него не примитивный, а дешугарится в кейс), но ума на то, что эти конструкции стоит делать спецформами и имплементить особым образом, а не тупо расшугаривать, у него хватило.

По поводу двух последних у меня сомнений не было, а первые вызвали недоумение. Но потом подумал: а ведь and/or являются control constructs по-сути. То есть, их нестрогость систематически используется программистами, и их надо по-особому эвалуэйтить/транслировать.

В-общем, надо срочно включать and/or в базовый синтаксис HN0. Мне их и так надо было по-особому обрабатывать, поскольку, например, в С++ нельзя получить указатель на ||. Я выкрутился (понимая, что это временный хак), определив в С++ bool _or(bool, bool), но это же бред поскольку нестрогость при трансляции теряется.

03 октября 2016, 00:01

02 октября 2016

nponeccop

Swift for Windows

https://swiftforwindows.codeplex.com/

Почитал я про свифт этот. Ощущения двоякие.

С одной стороны, это невероятная хуйня всё, каменный век. Все эти for..in, chaining of optional values, объекты-геттеры-сеттеры, тьфу. Когда вспоминаю recursion-schemes хаскелевские, меня начинает тошнить от свифта.

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

Если посмотреть на шутаут - получается скорость почти как у Си при размере кода почти как у Руби. Надо конечно для сравнения оптимизированные по размеру х-е программы написать для шутаута, я думаю яблоководы-свифтовцы специально старались уменьшали.

02 октября 2016, 21:51

23 сентября 2016

darkus

Сентябрьский конкурс по ФП: систематизация знаний

Ура! Конкурс по функциональному программированию запущен. Сегодня задача связана с построением систем знаний по лекарственным средствам. Это не только увлекательно, но и полезно. Я бы сказал, что душеспасительно. Так что принимайте участие. Подарки будут. Возможно, не только от меня.

Адрес конкурса: http://haskell98.blogspot.ru/2016/09/blog-post.html

23 сентября 2016, 07:35

22 сентября 2016

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

Сентябрьский конкурс по ФП: систематизация знаний

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

Вот здесь вы найдёте список ссылок. По каждой ссылке имеется описание одного лекарственного средства. Например, вот описание Кофеина. Необходимо:

1. Скачать все описания.

2. Распарсить их таким образом, чтобы на выходе с парсера для каждого описания был список пар вида (ключ, значение), где ключом выступают заголовки разделов в описании (или, что то же, ссылки в содержании), а значениями выступают тексты после соответствующего заголовка и до следующего. Кстати, из заголовков необходимо удалять наименование вещества.

3. Объединить все распарсенные описания в огромную таблицу (матрицу), строками в которой являются ключи, а столбцами — наименования лекарственных средств. В ячейках матрицы, для которых не нашлось пары в описаниях, необходимо ставить прочерк «—». После формирования матрицу необходимо записать в формате CSV и кодировке UTF-8 без BOM в файл, который и прислать в качестве результата конкурса.

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

написал Dark Magus (noreply@blogger.com) 22 сентября 2016, 23:11

21 сентября 2016

Adept

ICFPC-2016: afterparty

Организаторы выложили результаты

Моя скромная команда сползла с 19-го места на 22-е (все равно, я считаю, офигенно для этого подхода к решению).

Первое место, как и в прошлом году, взяли Unagi и вот тут можно посмотреть, как работает их солвер.

Lightning round полностью вручную взял jabber.ru, как уже было, кажется, в 2007-м году.

21 сентября 2016, 21:17

20 сентября 2016

Scala@livejournal.com

К предыдущему

Вот скажем, у нас есть QueryParams (что-то вроде Map[String, String]), из которого нужно создать инстанс класса Employee(name: String, age: Int).

Иными словами, имеются функции QueryParams => Try[String] и QueryParams => Try[Int], а из них нужно построить функцию QueryParams => Try[Employee].

Если немного обобщить, то выходит, что у нас есть разные функции вида fа: QueryParams => Try[A], fb: QueryParams => Try[B], и fc: QueryParams => Try[C], а в результате нужно получить fabc: QueryParams => Try[ABC], где ABC это произведение типов A, B, и C.

Предположим теперь, что мы хотим аккумулировать ошибки валидации. Тогда удобнее заменить Try на scalaz.\/ и получится что-то вроде:
import scalaz._
type Result[T] = Exception\/T 
val fa: QueryParams => Result[A] = ...
val fb: QueryParams => Result[B] = ...
val fc: QueryParams => Result[C] = ...

case class ABC(a: A, b: B, c: B)

type ResultNel[T] = NonEmptyList[Throwable]\/ABC

val fabc: QueryParams => ResultNel[ABC] = qp => {
  val va = fa(qp).validation.toValidationNel
  val vb = fb(qp).validation.toValidationNel
  val vc = fc(qp).validation.toValidationNel
  ((va |@| vb |@| vc)(ABC)).disjunction 
}
Теперь вопросы:

Можно ли сделать то же самое попроще ? (Я понимаю, что с Result из ScalaKittens можно избежать преобразований \/ в Validation и обратно, но хотелось бы использовать только "стандартные" средства).

Так и придётся расписывать вручную для всех конкретных типов A, B, C, и ABC или можно как-нибудь избавиться от boilerplate ?

написал Michael 20 сентября 2016, 18:43

17 сентября 2016

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

STREAMS: gen_server will be recorded, stay tuned.

Решил я все-таки написать уничтожитель SSD дисков свою библиотеку аппенд бинари логов. Одна есть неплохая в составе hanoidb, а вторая неплохая в составе rafter имплементации которая включена в cr. В мире сишечки есть eblob в организации reverbrain, которая юзается в Coub, Sputnik и других яндексах. Что хочется от этой библиотеки?

1. Максимум в два раза падение по сравнению с физической на блочном устройстве. Да, конечно хочется интеловские SSD SDK для прямого управления контроллером посекторным, но это будет работать только на линуксе.

2. Простая и понятная привязка к эрланг процессу, т.е. мы стримим все эффекты эрланг процесса. Сколько эфектов навешано на процесс, столько и цепочек. Каждая цепочка отдельный файл. Т.е. N очередей ограничено (например N=500, для сервисов кольца [vnode] ). Это не должно скейлиться на миллионы. Кстати для кольца должна быть отдельная библиотека synrc/ring (вакантное название, желательно из трех букв), которая по заданному имени и степени двойки генерирует совместимые наборы vnode в хеш-кольце и стартует для них по одному gen_server. Эти сервера тоже персистентные, как и цепочки master_node серверов. Т.е. DHT — это просто pub sub такой (пока на эрланг ремоутинге, его обещали в R20 починить и заскейлить до 100 нод лохобаны эриксоновские), где все всё пишут и могут работать в зависимости от CAP конфигурации по разных протоколах-алгоритмах. Алгоритмы эти не влияют никак на библиотеку кольца. В идеале конечно было бы на каждую vnode свой SSD диск. Также vnode могут выступать и в виде виртуальных машин которые уже держат по отдельному процессу для каждого пользователя. Но это хай-энд, незнаю или кто-то уговорит меня такое сделать. Как алоцировать vnode — это отдельный вопрос к трактовкам цепочных схем хранения. Тут тоже могут быть свои протоколы.

3. Эта библиотека должна стать системообразующей наравне с новым gen_server+streams — это как пи и сигма (одно работает, второе пишет), поэтому примитивы должны быть хорошо проработаны чтобы составить основу для EXE примитива персистентного процесса. Это персистентные видимые и индексируемые эффекты процесса. Т.е. — это как примитивная сущность виртуальной машины рассматривается, а не как прикладная библиотека. По крайней мере должно так быть.

Я собрал PoC:
>  boot:test(boot:start(1)).
flush: {{<<99,97,108,1,2,3,4,5,6,7,8,1,1,1,1,1>>},
        {ecirca,#Ref<0.0.3.168>,<<>>,<0.196.0>,medium}}
2000100 messages sent in 2s with 847824 m/s rate
Disk write performance: 170 MB/s
ok

Если склеивать сообщения таким образом (буферезировать):
append(Circ,Record) -> <<(term_to_binary(Record))/binary, Circ>> .

То процесс вообще виснет. Если склеивать с помощью листов:
append(Circ,Record) -> [term_to_binary(Record)|Circ].

То упираемся в фольклерные эрланговые 50MB/s. Но если взять библиотеку si14 ecirca:
append(Circ,Record) -> ecirca:push_list(Circ, binary_to_list(term_to_binary(Record))).

То мы уже можем достигать 250МБ/s — это половина линейной сторости моего SSD. С учетом на виртуальную машину и операционную систему (в два раза !!!!). А вы говорите зачем юникернелы.



Есть еще идея писать выровненные данные по колонкам. Но тогда без компрессии. Но зато с мнгновенными операциями get/put, так как оффсет высчитывается по номеру сообщения.

Заметьте, что хотя эрланговый процесс через себя пропускает миллион сообщений, будучи склеинные в цепочки (cons) эти сообщения могут записываться при максимальном рейте 50MB/s. Вот такой эрланговый лимит. Так что либо ecirca либо emmap. Я выбрал ecirca так как она менее системнозависима, ecirca работает только с BIF эрланговыми, а emmap с API ОС.

P.S. Писал я все это на конференции http://OSDN.org.ua, которая сегодня была. Там Влад опять рассказывал про zalora/upcast который оказывается сменили на terraform.

17 сентября 2016, 17:32

13 сентября 2016

12 сентября 2016

11 сентября 2016

Anton Salikhmetov

Token-passing Optimal Reduction with Embedded Read-back

http://dx.doi.org/10.4204/EPTCS.225.7

Token-passing Optimal Reduction with Embedded Read-back
Anton Salikhmetov

We introduce a new interaction net implementation of optimal reduction for the pure untyped lambda calculus. Unlike others, our implementation allows to reach normal form regardless of the interaction net reduction strategy using the approach of so-called token-passing nets and a non-deterministic extension for interaction nets. Another new feature is the read-back mechanism implemented without leaving the formalism of interaction nets.

In Andrea Corradini and Hans Zantema: Proceedings 9th International Workshop on Computing with Terms and Graphs (TERMGRAPH 2016), Eindhoven, The Netherlands, April 8, 2016, Electronic Proceedings in Theoretical Computer Science 225, pp. 45–54.
Published: 10th September 2016.

comment count unavailable comments

11 сентября 2016, 07:02

08 сентября 2016

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

Новый сезон канала HBO

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

С этого момента деканат прикладной математики КПИ величает вашего покорного слугу-грфомана аспирантом (теперь я официально ебанат). В этом году сдают экзамены как на кандидатский (англ., специальность, у меня обе А, готовился чесно, ебанул 50 страниц матфизики вплоть до ядер интегральных операторов и функциональных пространств L2), ну и как всегда на ПМ только дневная форма обучения. Так как это последний год (мне 35) когда я могу поступить в аспирантуру (да да, сейчас КПИ дает PhD дипломы, а не галимого к.ф-м.н). Придется теперь срать тут и везде про рекурсоры и индукции в промышленных масштабах всея ЖЖ и на нескольких языках, чтобы до Андрея Байера слух дошел. Ну и на пары ходить, лекции читать, телочек в КПИ крутезных просто дофига, и все стартапы мутят и матан шарят. Ах Ах Ах.

С кодировками (хотябы CiC, не говоря уже про HIT и QIT) пока не понятно, что буду делать, буду делать pivot наверное. Возьму для начала ебану экстракт Lean, а потом плавно перейду к модифицированому тайпчекеру с Self типами уважаемых Пенг Фу и Аарона Стампа. Если найду хрошего категорщика может продолжу проект о суперкомпактном чистейшем как слеза PTS ядре. Времени дают 3 года.

Мне уже на кафедре посоветовали двух бодхисаттв. Первый бодхисаттва — правая рука Лямбдагарбхи — Любашенко Владимир (Институт Математики НАН Украины), а второй бодхисаттва — Лялецкий Александр (и его сын) из Института Глушкова (тот который придумал кибернетику в СССР Украине). Вот видео Любашенко из цикла лекций про Теорию Гомотопий https://www.youtube.com/watch?v=h2eU6OxHr3c Лялецкий по слухам тоже прувер пишет.

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

08 сентября 2016, 19:38

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

[prog.flame] Давно что-то не писал про ООП vs ФП, надо исправиться... ;)

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

Понятно, что ООП -- это никакая не серебрянная пуля. И даже на заре проникновения ООП в мейнстрим (по крайней мере в наших Палестинах) было очевидно, что на ряде задач выигрыш от ООП может быть только если задача объемная и предполагает развитие в течении длительного времени. Помнится, некоторые аппологеты, вроде Гради Буча, даже предупреждали, что с ООП придется потратить гораздо больше сил и времени по сравнению с процедурным подходом на начальном этапе разработки. Т.е. на C или на Pascal-е вы бы уже могли написать худо-бедно работающий прототип, а на C++, Eiffel или SmallTalk еще бы только-только завершали фазу ОО-анализа и, возможно, фазу ОО-проектирования. И, скорее всего, не написали бы еще никакого кода.

Тем не менее, при всех своих проблемах ООП всегда (по крайней мере так было в начале 90-х) крутился вокруг практических вещей. Вот здесь у нас будет класс Строка. Ok, понятно что это и зачем. Вот здесь -- класс Файл. Снова Ok, снова понятно что и зачем. Вот здесь -- класс COM-порт. И снова Ok, снова все понятно. Аналогично с классами Меню, Диалог, Конфиг, Таймер, Нить и т.д. И вот уже из понятных частей собирается GUI-приложение для работы с неким внешним устройством через COM-порт.

Поэтому ООП было более-менее просто объяснять людям. Мол, смотри, у тебя будет COM-порт. Мы сейчас точно не знаем, что именно будет у него внутри, но более-менее понимаем, как с ним работать. Поэтому давай сделаем набросок класса COM-порт с несколькими очевидными публичными методами и пойдем дальше... На какой-то N-ой итерации мы возвращаемся к нашему классу и уточняем еще чуть больше. А потом еще и еще раз.

Т.е. ООП можно было объяснять "на пальцах", отталкиваясь от практических нужд конкретного разработчика.

Тогда как с ФП лично мне таких объяснений, которые бы отталкивались от практики, особо не попадается. Если говорить совсем грубо, то получается что-то вроде:

-- Вот смотри, у нас есть функция f a b -> c...
-- А что это за функция? Для чего она?
-- Это не важно. У нас просто есть функция f a b -> c. У нее два аргумента. Но, на самом деле, ее можно представить как последовательность функций с одним аргументом f a -> b -> c...
-- И что?
-- И мы может делать каррирование, когда мы из f a b -> c, получаем g b -> c с зафиксированным значением аргумента a. А все месте нам это дает возможность композиции функций!
-- Композиции функций для чего?
-- Для чего угодно. Вот смотри, допустим, нам нужно применить к данным функции x, y и z...
-- К каким именно данным и что именно делают функции x, y и z?
-- Это не важно, важно то, что через композицию мы можем сделать так, что разультат x идет в y, а разультат y идет в z. Мы просто описываем композицию функций декларативно в коде и все.
-- Что все? Какие у нас данные? Как именно мы их обрабатываем? Зачем мы это делаем?
-- Это не важно, я тебе принцип объясняю.

Вот, скажем, как вам такая статья на Хабре: Монады и do-нотация в C++? Но не просто как статья, как демонстрация принципа, на котором можно связать в цепочку последовательность операций. Например, B*x + C, где B и C -- это матрицы, а операции умножения и сложения могут завершаться неудачно.

Собственно, сей пост не является попыткой бросить камень в само ФП. Как по мне, так изрядная часть фишек ФП оказалась в императивном мире давным давно (например, если посмотреть на языки SmallTalk и Ruby, в которых блоки кода есть ни что иное, как лямбды, а изрядная часть методов в стандартной библиотеке базируется на использовании функций высших порядков). И использовалась программистами задолго до возникновения хайпа вокруг ФП, причем многие до сих пор не подозревают об этом, дергая Enumerable#map. Ну и вообще, очень многие вещи из ФП вполне себе просты и понятны, если их объяснять без чрезмерного использования математических формул :)

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

PS. Кстати говоря, ничуть не удивлюсь, если для современной молодежи, которая начала учиться программировать сейчас или даже лет пять назад, ситуация видится прямо противоположной. Вероятно, для нонишних новичков в программировании базисом, с которого они стартуют, являются такие вещи, как функции высших порядков, алгоритмы вроде foldr/foldl/zip, алгебраические типы данных и т.д. А вовсе не правила структурного и модульного программирования, с осознания важности которых довелось начинать моему поколению.

написал Yauheni Akhotnikau (noreply@blogger.com) 08 сентября 2016, 11:36