IT-redneck

Готового работающего нет.

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

From:

--конечного автомата с участием пользователя, <...> FP как раз это все более математизировано

В умных книжках пишут что ФП и автоматы - две вещи несовместные, т.к. у автоматов состояния есть, а в ФП их быть не должно.

From:

можно ссылки на эти "умные книжки"?
Монады State и gen_fsm в эрланге, наверное, не существует?

From:

--можно ссылки на эти "умные книжки"?
Боюсь что уже не упомню. Помню что по-английски было.

Обосновывлось так: если у вас сплошные состояния то это уже к товарищу Тюрингу и всякой императивщине, всяческими костылями конечно запихнуть в ФП можно, но зачем?

--Монады State и gen_fsm в эрланге, наверное, не существует?
Конечно существуют.

From:

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

From:

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

--Про костыли интересен более полный ответ - что вы ими считаете и почему?
Деалю системы управления для мобильных роботов.
Ради интереса попробовал на хаскеле.
Получилась куча монад и почти императивно.

From:

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

From:

Кстати, насчет эквивалентности. Я не очень понимаю операционную семантику лямбда-исчисления. Если построить машину Тьюринга в железе и запрограмировать примерно понятно как, то как построить считалку на лямбдах - не очень :)

From:

Как варианты - http://en.wikipedia.org/wiki/SECD http://en.wikipedia.org/wiki/Categorical_abstract_machine (оно же CAM из CAML), в хаскеле вроде G-machine (пока руки не дошли толком разобраться, у Simon Peyton Jones в книжках разбирается вроде как), у клина - ABC-machine, http://www.st.cs.ru.nl/papers/1993/plaseek93/Ch10.ABC.ps
По сути там переписывание графов, хотя не сказал бы что хорошо разбираюсь в теме.

From:

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

From:

С чего это оно ближе к тьюрингу?
Как раз там есть лишь лента и таблица переходов, в отличие от ФП с лямбдами где ты можешь свободно заменять эквивалентные функции. Интересно было бы узнать, где в машине Тьюринга есть композиция/абстракция.

From:

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

From:

Ближе-дальше - какие-то неконкретные категории. На железе реализуется? Реализуется. Лямбды позволяет выполнять? Позволяет.
Что ещё собственно требуется?

From:

gds.livejournal.com

а если передам?

From:

Да совместимо оно, только что состояния в монадах таскаются.

From:

dmzlj.livejournal.com

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

From:

не обязательно в монадах, можно и явной передачей (см. Erlang/Clean)

From:

Явная передача это реализация монад вручную в итоге получится.

From:

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

From:

dmzlj.livejournal.com

Это какие-то неправильные умные книжки. Или вы их как-то неправильно поняли. Вот, например, конечный автомат на два состояния - Пыщь и Адын:

open ExtString

type state = Pysh | Adyn 

let fsm evt =
    let input state x = match state, x with
    | Pysh, '{' -> Adyn
    | Pysh, ' ' -> Pysh 
    | Pysh, c   -> Printf.printf "Pysh! %c\n" c; Pysh
    | Adyn, '}' -> Pysh
    | Adyn, ' ' -> Adyn
    | Adyn, c   -> Printf.printf "Adyn! %c\n" c; Adyn 

    in List.fold_left input Pysh (String.explode evt)

let _ = 
    fsm "000000000 { 1111111111111111111 } 2222222222222222222"

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

заметим еще, что сделать такой автомат на императивном языке "где есть состояния" c++ - будет несколько более громоздко.

From:

--Или вы их как-то неправильно поняли.
Всякое бывает

From: