четверг, 2 декабря 2010 г.

Стиль передачи продолжений и связывание

Оператор связывания как синтаксический сахар

По мотивам цикла заметок "Сегодня без...", а именно заметки "Сегодня без return".

Возьмем пример кода из вышеупомянутой заметки и сразу лишим его магии Perl прототипов: все равно в последующем коде они работать не будут:

sub mul {
my ($sub, $x, $y) = @_;
my @r = map { $$x[$_] * $$y[$_] } 0 .. $#$x;
$sub->(@r);
}

sub minus {
my ($sub, $x, $y) = @_;
my @r = map { $$x[$_] - $$y[$_] } 0 .. $#$x;
$sub->(@r);
}

sub say {
my $sub = shift;
print join(" ", @_), "\n";
$sub->();
}

my @i = (1, 2, 3);
my @j = (2, 3, 4);
my @k = (3, 4, 5);

mul sub {
minus sub {
say sub {}, @_
}, \@_, \@k
}, \@i, \@j;

Результат работы это программы - вывод на печать строки "-1 2 7".

А теперь представим, что подпрограмма minus не вызывает продолжение, а возвращает результат:

sub minus {
my ($x, $y) = @_;
map { $$x[$_] - $$y[$_] } 0 .. $#$x;
}

Поэтому напишем для обертку:

sub bind_minus {
my ($sub, $x, $y) = @_;
my @r = minus($x, $y);
$sub->(@r);
}

Которую и будем использовать:

mul sub {
bind_minus sub {
say sub {}, @_
}, \@_, \@k
}, \@i, \@j;

Затем сделаем подпрограмму bind_minus ленивой, чтобы только связывала, но ничего не вычисляла сразу (это пригодиться потом):

sub bind_minus {
my ($sub) = @_;
sub {
my ($x, $y) = @_;
my @r = minus($x, $y);
$sub->(@r);
}
}

# ...

mul sub {
bind_minus(sub {
say sub {}, @_
})->(\@_, \@k)
}, \@i, \@j;

Ленивость bind_minus позволяет по ее образу сделать универсальную подпрограмму Bind для связывания функции и продолжения:

sub Bind {
my ($sub, $cont) = @_;
sub {
my @r = $sub->(@_);
$cont->(@r);
}
}

# ...

mul sub {
Bind(\&minus, sub {
say sub {}, @_
})->(\@_, \@k)
}, \@i, \@j

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

sub mul {
my ($x, $y) = @_;
map { $$x[$_] * $$y[$_] } 0 .. $#$x;
}

sub minus {
my ($x, $y) = @_;
map { $$x[$_] - $$y[$_] } 0 .. $#$x;
}

sub say {
print join(" ", @_), "\n";
}

my @i = (1, 2, 3);
my @j = (2, 3, 4);
my @k = (3, 4, 5);

sub Bind {
my ($sub, $cont) = @_;
sub {
my @r = $sub->(@_);
$cont->(@r);
}
}

Bind(\&mul, sub {
Bind(\&minus, sub {
Bind(\&say, sub {})->(@_)
})->(\@_, \@k)
})->(\@i, \@j)

Кстати, можно даже сделать маленькую tailcall оптимизацию:

sub Bind {
my ($sub, $cont) = @_;
sub {
@_ = $sub->(@_);
goto &$cont;
}
}

А если превратить подпрограмму Bind в оператор, то это становиться на что-то очень-очень похоже... Неужели на Haskell?

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

Если да, то bind и монады в Haskell - это не кусочек императивного мира, а его иллюзия.
То есть Haskell един, а не состоит из двух частей: чистой и грязной. Он чист, абсолютно чист, также как и Clean!

А как же быть с ленивость? Ведь Haskell не только чист, но и ленив. Что-ж рассуждаем дальше.

Порядок для ленивых

Оператор связывания

Представим, что нам надо получить из вне две числа и разделить второе на первое:

my @numbers = (3, 6);
sub get_number() {
shift @numbers;
}

my $x1 = get_number();
my $x2 = get_number();

sub div($$) {
my ($x2, $x1) = @_;
$x2 / $x1;
}

print div($x2, $x1);

Результат работы вышеприведенного кода - деление 6 (второе число) на 3 (первое число).
Подпрограмма get_number имитирует получение чисел из внешнего источника.

А теперь добавим ленивость:

my @numbers = (3, 6);
sub get_number() {
sub { shift @numbers };
}

my $x1 = get_number(); # метка 1
my $x2 = get_number(); # метка 2

sub div($$) {
my ($x2, $x1) = @_;
$x2->() / $x1->(); # метка 4
}

print div($x2, $x1); # метка 3

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

В нашем примере, добавив ленивость, мы сделали, что при выполнении программы в метке 1 почти ничего не происходит, и в метка 2 также. А вот в метке 3 требуется все таки вывести результат - программа осознает, что хватит лениться и вызывает функцию div, передав ей ленивые x2 и x1. В функции div (метка 4), уже нужны реальные результаты x2 и x1 - происходит получение данных из внешнего источника. Но поскольку нужен сначала x2, а лишь потом x1, то первое число попадает в x2, а не в x1.

Чтобы задать порядок вычисления можно воспользоваться Стилем передачи продолжений -
для простоты сразу возьмем вышеупомянутую функцию Bind:

my @numbers = (3, 6);
sub get_number() {
sub { shift @numbers };
}

sub div($$) {
my ($x2, $x1) = @_;
$x2->() / $x1->();
}

sub Bind {
my ($sub, $cont) = @_;
sub {
@_ = $sub->(@_);
goto &$cont;
}
}

Bind(get_number(), sub {
my $x1 = shift;
Bind(get_number(), sub {
my $x2 = shift;
Bind(\&div, sub {
print @_;
# print "$x2/$x1=$_[0]\n"
})->(sub {$x2}, sub {$x1})
})->();
})->();

Конечно выглядит ужасно!

Но если подпрограммы Bind сделать оператором и упростить запись для анонимных подпрограмм, то все намного лучше:

get_number >>= \x1 -> (get_number >>= \x2 -> (div x2 x1 >>= print))

А при использовании do нотации - все просто замечательно:

do x1 <- get_number
x2 <- get_number
r <- div x2 x1
print r

Примечание: Haskell не знаю - так что эти две записи наверняка с ошибками.


Dataflow переменные

Альтернативный способ задания порядка - это использование unborned dataflow переменных.

Они используется для управления порядком в Mozart-OZ потоках.

Им подобны "Уникальные типы" в Clean.

В Haskell они просматриваются в руководствах посвещенных монадам:

getChar :: RealWorld -> (Char, RealWorld)

main :: RealWorld -> ((), RealWorld)
main world0 = let (a, world1) = getChar world0
(b, world2) = getChar world1
in ((), world2)

Хотя мне не понятно зачем они тут, ведь все красиво делается при помощи связывания?
Конечно, можно предположит, что getChar и прочии IO функции настолько ленивы, что им надо передавать всегда новый RealWorld,
но ведь это можно делать за кулисами.

Выводы

Время от времени читал о Haskell, о монадах - никак не мог понять их. Казалось, что одни руководства противоречат другим.
И только, недавно, когда плюнул на все эти монады, а просто представил чистый и ленивый язык, сразу стало все на свои места.
Нашлось там место и оператору bind, и самим монадам, но не как ключевым фигурам...
Остался один вопрос: зачем так все путанном объясняется в Haskell?


P.S.
После того как была написана эта заметка решил посмотреть подробней на Clean и нашел там подтвержение вышесказаному.
Может тем, кто хочет понять Haskell монады, следует рекомендовать сначала почитать как в Clean обходятся без них.

среда, 1 декабря 2010 г.

IPS::MPS, AnyEvent::HTTPD, AnyEvent::HTTP and DBI

Игрался на perl связкой IPS::MPS, AnyEvent::HTTPD, AnyEvent::HTTP и DBI.
Сделал четыре процесса: главный (управляющий), HTTP сервер, HTTP клиент, DBI клиент.
Хотя блокируемый процесс тут один: DBI, но этого поиграться с межпроцессным взаимодействием в стиле передачи сообщений хватит:

use IPC::MPS::Event;
use AnyEvent::HTTPD;
use AnyEvent::HTTP;
use DBI;

my $port = 9090;

print "Please contact me at: http://127.0.0.1:$port/?q=foo\n";

my $vpid_server = spawn {

my %url2req; # $url => [$req, ...]

my $httpd = AnyEvent::HTTPD->new(port => $port);

$httpd->reg_cb (
'' => sub {
my ($httpd, $req) = @_;
my $q = $req->parm('q');
if ($q) {
my $url = "http://www.google.com/search?q=$q";
snd(0, "req", $url);
push @{$url2req{$url}}, $req;
} else {
$req->respond([404, 'NOT FOUND']);
}
},
);

receive {
msg res => sub {
my ($from, $url, $data, $headers) = @_;
for my $req (@{$url2req{$url}}) {
$req->respond([200, 'OK', {'Content-Type' => 'text/html'}, $data]);
}
delete $url2req{$url};
};
};

};


my $vpid_client = spawn {
receive {
msg req => sub {
my ($from, $url) = @_;
http_get $url, sub {
my ($data, $headers) = @_;
snd($from, "res", $url, $data, $headers);
};
};
}
};


my $vpid_dbi = spawn {

# CREATE DATABASE nick OWNER nick ENCODING 'UTF8';
# CREATE TABLE urls (id_url SERIAL, datetime TIMESTAMP DEFAULT now(), url text, PRIMARY KEY (id_url));
# DROP TABLE urls;
my $data_sourse = "DBI:Pg:dbname=nick;host=localhost";
my $dbh = DBI->connect($data_sourse, "nick", "") or die $DBI::errstr;
my $sth = $dbh->prepare("INSERT INTO urls (url) VALUES (?)") or die $dbh->errstr();

receive {
msg res => sub {
my ($from, $url) = @_;
$sth->execute($url) or die $dbh->errstr();
};
}
};


receive {
msg req => sub {
my ($from, $url) = @_;
snd($vpid_client, "req", $url);
warn "Q; $url";
};
msg res => sub {
my ($from, $url, $data, $headers) = @_;
snd($vpid_server, "res", $url, $data, $headers);
snd($vpid_dbi, "res", $url);
warn "R; $url";
};
};

Забавно получается.

среда, 24 ноября 2010 г.

IPC::MPS - Message Passing Style of Inter-process communication

Немного на русском о межпроцессном взаимодействии в стиле передачи сообщений.

IPC::MPS, - система обмена сообщениями между родительскими и дочерними процессами, а также между дочерними, имеющими общего родителя.

use IPC::MPS;

my $vpid = spawn {
receive {
msg ping => sub {
my ($from, $i) = @_;
print "Ping ", $i, " from $from\n";
snd($from, "pong", $i);
};
};
};

snd($vpid, "ping", 1);
receive {
msg pong => sub {
my ($from, $i) = @_;
print "Pong $i from $from\n";
if ($i < 3) {
snd($from, "ping", $i + 1);
} else {
exit;
}
};
};

Concurrency programming

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

Сообщения передаются посредством UNIX сокетов.

$vpid = spawn {
...
receive {
msg "name 1" => sub {
my ($from, @args) = @_;
...
};
msg "name 2" => sub { ... };
msg "name 3" => sub { ... };
...
};
};

Создание дочерних процессов происходит не при вызове spawn, а потом, при receive, непосредственно перед вызовом цикла отправки-приема сообщений. Это необходимо чтобы все vpid были определены до вызовов fork. vpid - адрес ссылки на сокет с главного процесса в дочерний.

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

Отправка сообщений.

snd($vpid, "msg name", @args);

Если vpid равен 0, то это сообщение родительскому процессу.

Если дочерний процесс видит, что родительский завершился, то он также завершается.

Dataflow programming

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

snd("vpid_1", "msg_1", @args_1);
snd("vpid_2", "msg_2", @args_2);

my $r = wt("vpid_1", "msg_1");
...
my @r = wt("vpid_2", "msg_2");
...

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

my $r = snd_wt($vpid, $msg, @args);

является сокращением для:

snd($vpid, $msg, @args);
my $r = wt($vpid, $msg);


The main differences from Erlang

Внимание, это не Erlang, это Perl IPC::MPS. Основные отличия, вытекающие одно из другого:

1. Полноценные процессы операционной системы.
2. Подпрограмма spawn непосредственно не создает процессы, а лишь осуществляет подготовительные операции. Процессы создаются при вызове receive.
3. "receive" - "многоразовый", а не "одноразовый", как в Erlang.
4. "receive" внутри "receive" не заменяет временно собой предыдущий, а добавляет новые обработчики сообщений и запускает новые процессы.
5. Чтобы дождаться внутри обработчика сообщения ответ на конкретное сообщение следует использовать подпрограмму wt. В Erlang это делается все тем-же "receive".

Распределенное программирование

Чтобы сделать текущий процесс узлом необходимо вызвать подпрограмму listener:

listener($host, $port);

Подключение к уделенному узлу осуществляется при помощи подпрограммы open_node:

my $vpid = open_node($host, $port);

Чтобы обнаружить закрытие соединения следует определить обработчик сообщения NODE_CLOSED:

msg NODE_CLOSED => sub {
my ($vpid) = @_;
...
};

Это утверждение справедливо как для клиента, так и для сервера.

Совместимость с модулями, основанными на Event, EV и AnyEvent

IPC::MPS::Event, IPC::MPS::EV позволяют использовать сторонние модули на основе модулей Event и EV соответственно (напрямую или через AnyEvent).

P.S.
Примеры смотрите в каталоге demo.

понедельник, 18 октября 2010 г.

Почему Perl

Фрагмент из "Распределенное программирование на Perl для домохозяек".

Если ваш муж программирует на Java, C#, Python или другом подобном языке, то он обязательно с недоумением спросит: "зачем Perl"? Более того, он скажет, что Perl слишком путанный язык со сложным синтаксисом и перегружен излишними возможностями. В ответ можно попытаться объяснить преимущества многогранности и многообразия, но не стоит. Лучше продемонстрируйте на практике. А для наглядности - на его собственном примере.

Поведите мужа в Макдоналдс! Пусть с недельку поест там, а не дома. Да, это жестоко, ведь еда из Макдоналдса, как и любой фастфуд, вредна для здоровья. А разве Макдоналдс-языки программирования менее вредны? Только фастфуд наносит вред телу, а эти языки - разуму, так как человек погрязает в тесных рамках тех же ООП (объектно-ориентированных предрассудков) и не видит многообразие мира за ними.

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

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

Аналогия со специями абсолютна. Когда специи попали в Европу, они совершили настоящий переворот в кулинарии. Но потом дошло до абсурда - их стали использовать в таком количестве, что невозможно было определить, что за блюдо подано к столу. Затем произошел полный отказ от специй. И лишь сейчас они занимают место, по праву принадлежащее им: ведь никто не отрицает, что чуточка кардамона сделает дрожжевое тесто вкуснее. А волшебное сочетание корицы и печеных яблок! А мускатный орех - да это же король соусов!

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

среда, 3 февраля 2010 г.

Всякая всячина и книги

Пора заканчивать заниматься ерундой и писать всякую фигню o Perl - блог закрыт. Сажусь за написание двух книг.

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

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

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

Здесь будет опубликованы анонсы. До встречи.

понедельник, 4 января 2010 г.

Если бы в Perl не было бы списков :-)

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

Создание списка

sub list($;$) {
my ($h, $t) = @_;
return sub {
return $h, $t;
}
}

my $x1 = list(1);
my $x2 = list(2, $x1);
my $x3 = list(3, $x2);

Печать списка

sub print_list($);
sub print_list($) {
my ($list) = @_;
my ($h, $t) = $list->();
print_list($t) if $t;
print "$h ";
}

print_list $x3;
print "\n";

map

sub _Map {
my ($sub, $list) = @_;
my ($h, $t) = $list->();
my $r = $t ? _Map($sub, $t) : undef;
list($sub->($h), $r);
}
sub Map(&;$) { &_Map }

print_list Map { $_[0]**$_[0] } $x3;
print "\n";