Current mood:	tired
Entry tags:	programming

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

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

И увидел я там шикарную фразу, которая меня вогнала в некоторый ступор. Фраза звучала так:

Автоматное программирование предложено А.А.Шалыто в 1991 году

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

Особенно меня удивило то, что я уже лет пять студентам рассказываю, как использовать в событийно-ориентированных приложениях технику автоматного программирования, а сам эту технику использую примерно с года эдак 1992го (раньше я вообще программировать не умел, увы мне), но ни о каком Шалыто никогда почему-то не слышал.
"Как же так?!" -- подумал я. И попробовал в этом деле разобраться. Для начала запостил соответствующий вопрос в ru_cs.

Там сходу нашелся один сторонник Шалыто (к счастью, только один, и не агрессивный). Он, правда, так и не смог объяснить мне, что же нового в работах Шалыто, да ещё настолько, чтобы присваивать себе авторство всей автоматной парадигмы, но некая несомненная польза от нашей с ним встречи всё же была: он выдал мне email самого Шалыто, чтобы я вопросы мог задать напрямую.

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

Уважаемый Анатолий Абрамович!

Я работаю на факультете ВМиК МГУ, занимаюсь практическими
методами сочетания разнородных стилей программирования.

Редактируя статью "Парадигмы программирования" для Википедии, я
наткнулся на статьи, посвященные парадигме автоматного
программирования и лично Вам:

http://ru.wikipedia.org/wiki/%D0%A8%D0%B0%D0%BB%D1%8B%D1%82%D0%BE
http://ru.wikipedia.org/wiki/%D0%90%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5
http://en.wikipedia.org/wiki/Automata-Based_Programming
http://en.wikipedia.org/wiki/Anatoly_Shalyto

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

Заранее признателен за ответ.

С уважением,
--
Андрей Викт. Столяров
ВМиК МГУ

Через несколько дней я получил ответ, от которого моя челюсть отпала ещё сильнее:

    Андрей Викторович!

    Указанные статьи написаны с моим участием - поэтому с ними
    согласен.
[...skip...]

Ещё продолжая надеяться на лучшее, я сочинил второе письмо. Привожу его
текст целиком:

Уважаемый Анатолий Абрамович!

Ваше письмо привело меня в состояние крайнего удивления.

Дело в том, что программирование в стиле конечных автоматов
(statemachine-based programming) известно по меньшей мере с
середины 1960х годов. Во всяком случае, в известной книге Ахо и
Ульмана "Теория синтаксического анализа, перевода и компиляции"
оно уже активно используется, а английский оригинал этой книги
вышел в 1973 году -- причем книга представляет собой не
оригинальное исследование, а скорее обзор имеющихся результатов.
В русском переводе (М.:МИР, 1978) на стр. 295 в первом томе можно
найти, например, следующее примечание:

<<<<<<<<<<<<<<<<<<<
первой большой системой, в которой при построении лексических
анализаторов использовалась техника конечных автоматов, была
система AED RWORD. Обзор этой системы дан Джонсоном и др. [1968].
Томпсон [1968] приводит алгоритм, который по регулярному
выражению строит программу в машинном языке, моделирующую
соответствующий недетерминированный конечный автомат...
>>>>>>>>>>>>>>>>>>>

В библиографии при этом имеются следующие ссылки:

Томпсон [1968] (Thompson K.) Regular expression search algorithm,
Comm. ACM, 11:6, 419-422

Джонсон и др. [1968] (Johnson W. L., Porter J. H., Ackley S. I.,
Ross D. T.) Automatic generation of efficient lexical processors
using finite state techniques, Comm ACM, 11:12, 805-813

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

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

Я готов допустить, что возглавляемая Вами исследовательская
группа под "автоматным программированием" понимает нечто отличное
от "программирования в терминах конечных автоматов", чем и
обусловлено утверждение о том, что "автоматное программирование
предложено А.Шалыто в 1991 году". Следует отметить, однако, что
подобные особые случаи применения терминологии должны быть
оговорены в явном виде, особенно если учесть энциклопедические
традиции Википедии и действующие там (заметим, явно
сформулированные и опубликованные) правила.

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

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

Один из вариантов -- сделать страницу "Автоматное
программирование" страницей disambiguation, то есть указать, что
термин "автоматное программирование" имеет различные значения.
Вопрос здесь в том, как назвать предложенную Вами методологию
(так, чтобы название отличалось от "Автоматное
программирование"). Это может быть что-то вроде "Автоматное
программирование (switch-технология)" либо "Автоматное
программирование (методология Шалыто)", либо что-то ещё. Хотелось
бы узнать Ваши пожелания на эту тему.

С наилучшими пожеланиями,
А. Столяров

Ответа на сей раз пришлось ждать чуть дольше, но он всё-таки воспоследовал.

       Сильно Вас благодарю, что Вы "не машите шашкой", а
       интерсуетесь моим мнением.

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

       Пока четыре замечания.
       1. Непейвода Н.Н. в своих первых книгах этот стиль называл
       программирование от состояний, а теперь называет автоматное
       программирование и считает, что "Термин "автоматное программирование"
       принадлежит, насколько нам известно, А.А. Шалыто. Во всяком случае, ему
       принадлежит заслуга его развития вопреки моде и мнению
       большинства".(http://www.intuit.ru/department/se/progstyles/9/1.html)

       Так, что если мне принадлежит не парадигма, так, по крайней
       мере, ее название.
       2. Где вы найдете так сформулированную парадигму:" Парадигма автоматного
       программирования состоит в представлении программ как систем
       автоматизированных объектов".  http://ru.wikipedia.org/wiki/%D0%90%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%BD%D0
%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%
B2%D0%B0%D0%BD%D0%B8%D0%B5
       Это построение программ в целом, а не только применение
       автоматов для описания поведения программ.

       Под термином "автоматное программирование" понимается не построение и
       реализация конечных автоматов, а проектирование и исполнение программ в
       целом, поведение которых описывается автоматами.
       http://is.ifmo.ru/reflections/automats/

       3. Важно не кто первый что-то где-то предложил, а кто певым
       предложил это сделать методологией. Например, в книге "100
       выдающихся людей" приведен пример с мытьем рук перед операцией.
       Кто первым это предложил неизвестно, а кто стал это читать в
       медицинских институтах и ввел в обязательную практику хорошо
       известен (посмотрю, сейчас не помню).
       4. Аналогичные доводы я уже слышу много лет (частичный ответ
       здесь http://ru.wikipedia.org/wiki/Switch-технология раздел
       1.7).

       Потом напишу еще доводы.

       Если это Вас убеждает или нет,в любом случае очень хотел бы прочесть Ваше
       мнение.


С уважением, Шалыто

---

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

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

На странице обсуждения вот тут: http://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5:%D0%90%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 разгорелся нешуточный флейм. Интересно, кстати, что я практически сразу заметил одну интересную особенность: вся, казалось бы, изрядная толпа моих оппонентов состоит исключительно из шалытовских студентов. Ну, и сам он там пару раз отметился.

Доводы их сводятся в итоге к одному: якобы под автоматным программированием следует понимать (они вообще заявляют "понимается") не программирование в терминах конечных автоматов, а именно вот эту вот методологию, предложенная Шалыто. То, что никто кроме самого Шалыто и его студентов этого не знает, их нимало не смущает. Ну и, естественно, это для них достаточный повод заявлять, что именно Шалыто и придумал автоматное программирование (не уточняя при этом, что конкретно имеется в виду). Разумеется, их не смущает и то впечатление, которое эта фраза вызывает у людей, с группой Шалыто до сей поры не сталкивавшихся.

А что она такое впечатление вызывает -- это к бабке не ходи. Вот сходу нашлось: http://www.cyberforum.ru/programming-theory/thread604.html

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

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

Каждая из этих моделей поведения представляется отдельной процедурой, а вызов процедур определяется "автоматом" примерно такого вида:

режим = ОТДЫХАТЬ;
switch(режим)
{
case ОТДЫХАТЬ: fun_REST(); break;
case ИСКАТЬ: fun_SEARCH(); break;
case АТАКОВАТЬ: fun_ATTACK(); break;

// а здесь идёт логика переключений
if(враг рядом) режим = АТАКОВАТЬ;
if(голодный) режим = ИСКАТЬ;
в противном случае режим = ОТДЫХАТЬ;
};

Эта, наверняка многим известная методика описана в куче книг и представляется почти что народной. Однако судя по статье (равно как и по куче других ссылок в инете) данный подход был изобретён лишь в 1991 году (!), к тому же в России.

Если честно, отказываюсь в это верить. Безусловно, перечисленные в статьи люди сделали очень много для развития этого подхода; им принадлежит творческое его развитие и авторская реализация разных систем программирования, но всё-таки... это же классика.

А теперь внимание, вопрос. Может ли кто-нибудь указать на (1) более раннее описание сходной техники; (2) определить название того, как это называется ("автоматное программирование"?) и когда этот термин появился (со ссылками, разумеется); (3) привести примеры использования данного подхода (не моделирования обычных конечных автоматов -- это любой движок регулярных выражений делает) в сравнительно старых проектах?

(хммм... по указанному адресу цитата уже исчезла, но вот копия в кеше гугла: жать сюда) Интересно, куда это в самый ненужный момент цитаты деваются?

Дальше -- больше. Обнаружились вполне академичные статьи некоего Б.Кузнецова, который тоже интересуется автоматным программированием, с Шалыто знаком, даже не просто знаком, а соавторствовал в нескольких статьях, но, судя по тексту статьи, изобретателем автоматного программирования Шалыто не считает, как и 1991 -- годом, когда его изобрели. Статья вот тут: http://www.softcraft.ru/design/ap/ap01.shtml Автору я сегодня послал письмо, но ответа пока нет.


Короче говоря, я покамест готовлю статью для Википедии взамен той лабуды, которая там сейчас есть. Черновик можно посмотреть тут: http://ru.wikipedia.org/wiki/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:DrCroco/automata_programming Русский вариант практически готов, только добавить ссылок; нужен, подозреваю, ещё и английский, чтобы всё сделать одновременно. Смущает меня только одно: толпа шалытовских студентов хотя и не блещет аргументами, но всё-таки довольно многочисленна, и бодаться с ними в одиночку я уже подустал. Может, поможет кто? Приветствуется любое содействие -- как в виде прямого участия в том флейме, так и в виде ссылок на источники, и в виде привлечения внимания общественности к проблеме.

В конце концов, ну так же нельзя™

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

Очень надеюсь, что тему можно сдавать в архив.