Парадигмы программирования, 09 лекция (от 19 ноября)

Материал из eSyr's wiki.

• Аудиозапись: http://esyr.org/lections/audio/paradigms_2009_winter/paradigms_09_11_19.ogg

Рефал.

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

Все подобные вещи, такие как алгоритмическая неразрешимость, теория самоприменимости, взаимоотношение мощности множества подмножеств и множества, они доказываются канторовским диаграммным методом. Доказывается так: предположим, что такой объект есть, а потом покажем такой элемент, на котором отображение заведомо сломается, что приводится к противоречию.

Чем важно доказательство: в глубине души мы верим, что все задачи алгоритмически разрешимы.

Вернемся к теории алгоритмов. Для интерактивности нужен более сложный формализм, но тем не менее. В 60-е годы в ИСП РАН, который возглавлял тогда М. Р. Шура-Бура, ныне покойный, В. Ф. Турчин

М. Р. был одним из последних в той плеяде программистов. Напр., он возг. проект по проекту Буран.

Турчин был диссидентом, его выслали, он уехал в Америку, и он до сих пор преподаёт в универ. в Нью-Йорке.

Интересно, как Т. продолжал работу над рефалом: сначала его вызвали на ковёр, сказали, чтобы не диссиденствовал, но Т. не смог, и его таки вышибли из ИСП, некоторое время он продолжал соверш. язык рефал. Для этого Турчин делал что: он наколачивал перфокарты, его студенты брали перфокарты, обсчитывали, возвр. перфокаторы, после чего он в итоге уехал в Америку. Поэтому большая часть док. англоязычная. Есть рефалодиаспора в России, тоже интересные люди, но весьма специальные, им поди скажи, что рефал не для всего удобен.

Рефал интересен тем, что практ. без библ. функций можно сделать что угодно.

Прогр. на рефале похоже на НАМ, предст. набор правил вида паттерн и набор действий.

Что может быть в выражениях?

• Буква. Обычный символ алфавита.
• Мы помним, что чтобы написать НАМ, нужно было вводить какие-то маркеры, то есть одних символов явно было недостаточно. Нам нужныы ещё нетерминалы. Если мы вводим доп. символы, то это можно рассм. как расширение алфавита, причём произвольное --- можно ввести в рефал-выр символ-метку. Когда-то давно символы-метки брались в слеши, сейчас такого зверства нет. 'abcd' --- терминалы, label --- нетерминал.
• Что ещё может быть в выр.: макроцифра. Посл. цифр, задающая целоае полож. число. Если нужно отр., то перед ним ставим минус: -2738, можно и так: '-'2738. При чём, тут реализ. не совсем удобная арифметика, по осн. 65536 --- можно пост. неск. таких макроцифр получается некоторое длинное число. К счастью, этим особо не пользуются.
• Кроме всего прочего, в выр. могут быть термы. Это скобка, что угодно, закр. скобка. Скобки наз. структурными. Они позв. выделить нечто. Внутри одних скобок могут быть другие, и так далее. Корректным явл. сболансированное скобоч. выр.

Мы подобное выидели ранее в s-выр. Подобное, но не совсем. Тут нет строк.

Здесь, если сравнивать с s-выр, то здесь нет аналога s-выр., только аналоги спискам, в том числе пустым, но анлаога нет.

Почему мы в третий раз видим нечто, похожее на s-выр? Потому что это гетерог. стр. данных, если мы начнём приджумывать что-то такое, то получим примерно то же самое.

Это выраж, данные, над которыми раб. рефал-машина. Но для работы нужно ввести ещё сущности.

Переменные. Есть три типа. Стандарта рефала нет, есть реализации, осн. это refal 2, refal 5 и refal+. Рефал 2 упорото изучают на ая на третьем курсе, но он не модный уже лет 30 лет как. Вообще, с выходом рефал 5 рефал 2 можно было бы и не рассм. Рефал+ неоднозначный. Рефал 5 с т. з. лектора самый правильный. Осн. виды переменных:

• e-переменная (от expression). Она может соспост. произв. правильному выражению (у которого собл. баланс скобок). В том числе пустому
• s-перем. Сопост. одному вимволу: терминалу, нетерм., макроцифр.
• t-перем (term). Может сопост. одному символу, а можно выраж.

Во второй версии были ещё v-перем, которая сопост. непустому выражению. Вообще говоря, она не очень нужна. С помощью этих перем. можно записать тело функций. Леткор будет исп. привычный ему синтаксис. <типа_перем>.<идентификатор>. Обл. вид. перем --- одно выражение, но с ними яснее. Мы добавили перем. можно писать предложения:

образец = шаблон

Xtv jnk/ j,h/ jn j,sxyjuj dshf;tybz& D y`v jvuen ghbcencnd/ gthtv/ dct[ djpv/ nbgjd/ Как вып. функция? Аргумент сопост. с первым образцом (делается попытка найти такие зн. переменных, чтобы он текст. совп. с арг.). Потом строится новое выражение. Берётся шаблон. Он может содерж. переменные в образце, и никакие другие (только те, которые имеют знач. в рез-те отождествления). Мы переменным приписали значения, и имеет место быть шаблон. Мы берём шаблон и на его осн. строим новое выражение. Этот шаблон., будучи преобр. в выр., становится результатом функции. Если ни один из обр. не подошёл, фикс. ошибка. Поэтому в норм. написанной рефал-прогр. обычно присутствет посл. правило с собств. диагностикой.

Теперь, что кас. выз. функции, как они запис., как выз. У функции есть имя, идентификатор. Вызов функции... для него пришло ещё раз расширить понятие рефал-выраж --- вводится угловые скобки, а дальше что-то, до боли напоминающее лисп: <имя_функции аргумент>. Когда у нас такое присутствует в выр., то это значит, что выр. ещё не вычисленно, это значит, что оно должно вычисл. Правила очень простые: находится самый левый из самых внутр. функц. вызовов. После чего выз. функция, получ. некий результат, он записываетс вместо вызова. Получилось ли при этом проще? Как бы не так, результ. выр. может содержать угл. скобки.

Что в итоге предст. работа рефал-машины? У рефал-машины есть поле зрения, оно может содерж. угл. скобки, но не может содерж. переменных. Теперь каждый шаг рефал-магины --- вызов функции. Оно вып., пока не ост. угловых скобок.

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

Попробуем пример функции написать. Лектор сразу напишет его на пятом рефале. Функция будет считать, явл. ли арг. палиндромом.

Pal {
              = true;
          s.1 = true;
  s.1 e.2 s.1 = <Pal e.2>;
          e.1 = false;
}

Какие здесь возм. варианты: Если выр. пустое, то, наверное, всё хорошо.

Помещаем в поле зрения рефал-машины строку:

<Pal 'топот'>

Функции Pal на вход подоно слово из 5 символов. Сопоставится с третьим правилом. Будет построено выражение:

<Pal 'опо'>
<Pal 'п'>
true

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

Возникает вопрос, как передать два аргумента? Передают очень интересно?

<+ (arg_1) arg_2>

Там арифметика вся встроенная, встр. функции вв/вывода.

На словах, конечно, всё выгл. хорошо. Нокогда нач. писать что=то серьёхное, то становится понятно, что этого не хватает. Первое, что придумали --- приделать спецификаторы к переменным.

В рефале 2 можно напистаьт s(...)1, ограничив мн-во возм. значений. Для e-спец. вообще замороченные. Самое главное, что выр. внтри круглых скобок были похожи на рефал, скорее, на рег. выражения.

К счастью, спецификаторы продержались недолго, появился refal5, в котором появились where-clauses. Мы можем в рефал-выр. кроме образца поставить запятую, поставить шаблон, двоеточие и сделать образец:

образец_1, шаблон: образец_2 = шаблон_2;

Как это обрабатывается? Произошло сопоставление. На осн. этого обр. форм. шаблон, он сопост. со вторым образцом. При этом может сформ. рефал-машина, поск. могут быть в шабл. функ. вызове. При этом это рефал. Естественно, конц. это чище, и мощнее. При этом появляются монстры, такие как новое поле видимости. Кроме того, здесь получается бэктрекинг. Поскольку сопоставление возможно разное. Более того, where-clauses может быть сколько угодно. Получается откр. бэктрекинг, это нововведение рефала 5.

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

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

Но далеко не всё стоит делать на рефале, напр. числ. вычилсения.

На что обратить внимание, когда пишется на рефале: не стоит ост. откр. e-переменных: e.1 e.2. Закрытая e-перем. — такая, которая не может принимать разл. выражения. Если это не так, то появл. вариации и пока нужная не найдена, это модет заняьт время.

Вопрос, к какой парадигме отн. к функц. парадигме? Ну, это не совсем так. А какой он? Есть книжка Кауфмана по разл. стилям программирования. И он говорит, что есть выч. модель Макрова-Турчина, дальше расск. про рефал и К. назвал это фитуационным программированием. Нигде, кроме как у К., лектор этот термин не видел. Видимо, он не прижился.Тем не менее, лектору он нравится., поск. К. отличил это от функц. программирования.