В.Ш. Кауфман - Языки программирования - концепции и принципы (1990) (1160787), страница 51
Текст из файла (страница 51)
Допустим, что имеется неограниченный набор различных пар функциональных
скобок (как это можно обеспечить?). Будем группировать предложения,
записывая подряд друг за другом такие предложения, левая часть которых
заключена в одинаковые функциональные скобки.
Тогда ведущий терм будет однозначно указывать на соответствующую группу
предложений (в ней и только в ней достаточно искать согласование).
В этом случае функция step распадается на отдельные функции, а
программа - на определения этих функций (за что соответствующее поле, где
помещается МТ-программа, мы и назвали полем определений).
Достаточно различать только левые функциональные скобки (почему?).
Будем считать левой функциональной скобкой название (идентификатор)
функции вместе с непосредственно следующей за ним открывающей фигурной
скобкой.
Например, программу перевода в ПОЛИЗ запишем так:
перевод {e1+e2}R -> перевод {e1} перевод {e2} +
перевод {e1*e2}R -> перевод {e1} перевод {e2} *
перевод {(e)} -> перевод {e}
перевод {e} -> e.
Эту совокупность подстановок естественно считать определением МТ-
функции "перевод". Его удобно использовать в большой программе среди других
подобных определений.
Поле зрения с исходными данными для перевода может иметь при этом вид:
перевод {(a+b) * (c+d)}
Так что и запись самой программы в модели МТ, и обращение к ней весьма
напоминают то, что мы выбрали в качестве идеала в самом начале разговора об
анализе и синтезе. [Недостаточна, правда, выразительная сила применяемых в
нашей модели образцов. Поэтому приходится писать подробнее, чем в БНФ].
До сих пор поле определений рассматривалось как определение одной
функции. Это была либо функция step, если результат считался полученным
после одного применения подстановки, либо (в общем случае рекурсивная)
функция sem, если результатом признавалось только выражение без
функциональных термов.
Когда поле определений разбито на группы подстановок с одинаковыми
левыми функциональными скобками, каждую такую группу естественно считать
определением отдельной функции. С точки зрения одного шага МТ-машины - это
функция, представляющая собой сужение функции step на ведущие термы с
конкретной функциональной скобкой. С технологической точки зрения (с точки
зрения программиста) - это рекурсивная МТ-функция, представляющая собой
сужение функции sem на те же термы.
Замечание. Применение МТ-функций предполагает уже некоторый элемент
прогнозирования со стороны программиста и контроля со стороны МТ-машины,
отсутствовавший в исходной модели.
Именно, употребляя конкретную функциональную скобку в правой части
предложения, программист прогнозирует, что при определенном поведении
исполнителя (если будет выбрано именно это предложение) потребуется
определение соответствующей функции.
МТ-машина, со своей стороны, получает возможность просмотреть поле
определений и проверить, что в нем присутствуют определения всех
использованных МТ-функций. Другими словами, становится возможным статический
контроль программ (т.е. контроль программ до их выполнения, без учета
исходных данных).
Итак, мы можем определять в программе столько рекурсивных функций,
сколько нужно.
Вот, например, как выглядит программа аналитического дифференцирования,
в которой используется частная производная по x и частная производная по y.
Dx{e1+e2}R -> Dx{e1} + Dx{e2}
Dx{e1*e2}R -> e1*(Dx{e2}) + e2*{Dx{e1})
Dx{(e)} -> Dx{e}
Dx{`x'} -> 1
Dx{s: символ} -> 0
Dy{e1+e2}R -> Dy{e1} + Dy{e2}
. . . . . .
. . . . . .
Dy{`y'} -> 1
Dy{s: символ} -> 0
Задача. Можно ли объединить эти функции? Как это сделать?
14. Функциональное программирование (модель Б)
14.1. Функциональное программирование в модели МТ
В соответствии с определением А.П.Ершова функциональное
программирование - это способ составления программ, в которых единственным
действием является вызов (применение) функции, единственным способом
расчленения программ на части - введение имени для функции и задание для
него выражения, вычисляющего значение этойфункции, единственным правилом
композиции (структурой операций) служит суперпозиция функций.
Ясно, что модель МТ с учетом последней "функциональной" модификации
позволяет программировать в строго функциональном стиле. Другими словами -
это одна из моделей функционального программирования.
[Таким образом, одно из отличий "функционального" программирования от
"аппликативного" - возможность явно определять (в общем случае рекурсивные)
функции].
Дополнительные примеры программирования в "функциональном стиле" мы
приведем чуть позже, а пока дадим краткий обзор "функциональной" модели МТ с
точки зрения нашей концептуальной схемы.
14.1.1. Модель МТ с точки зрения концептуальной схемы
Базис: скалярные данные - только литеры, скалярные операции - только
обобщенная поиск-подстановка. Структурные данные - только выражения (есть
подтипы: символ и терм), структурные операции - встроенный цикл, легко
приводящий к комбинациям функций.
[Говорят, что функции комбинируются горизонтально, если их результаты
являются непосредственными составляющими одного функционального терма.
Говорят, что функции комбинируются вертикально, если одна из них не
может быть вычислена до завершения вычисления другой. В такой комбинации
первая называется внешней, а вторая - внутренней.
В модели МТ применяются и горизонтальная, и вертикальная комбинации
функций. Горизонтальная комбинация называется также конструкцией, а
вертикальная, при которой результат внутренней служит полным аргументом
внешней - композицией; произвольная комбинация - суперпозицией.]
Развитие: вверх - только функции типа Е -> Е (однако за счет
структурированности выражений это весьма мощное средство развития (как будет
показано)); вниз - средств нет.
Защита: в базисе средств нет.
14.1.2. Модель МТ и Лисп
Можно показать, что модель МТ отражает не только свойства такого
реального языка, как Рефал, но и свойства еще одного заслуженного языка,
языка Лисп, созданного Джоном Маккарти в 1960 году и с тех пор прочно
удерживающего позиции одного из самых распространенных ЯП (особенно в
качестве инструментального языка в области искусственного интеллекта). В
последние годы интерес к нему усилился еще и как к первому реальному языку
функционального программирования.
Единственной базисной структурой данных в Лиспе служит список (так
называемое S-выражение). Оно естественно представимо в модели МТ выражением
в круглых скобках. Элементарные селекторы и конструкторы Лиспа
(предопределенные функции, позволяющие выбирать из списков компоненты и
строить новые списки из заготовок) легко программируются в модели МТ.
[Приведем упрощенные определения МТ-функций, способных играть роль
селекторов и конструкторов. Для краткости всюду ниже будем считать, что с
обозначениями МТ-переменных, начинающихся с буквы s и t, связаны
соответственно спецификаторы "символ" и "терм" (так и делается в реальном
Рефале)].
Выбор головы (первого элемента) списка:
первый {(t e)} -> t.
Выбор хвоста списка:
хвост {(t e)} -> (e).
Конструирование (создание) списка:
создать {e} -> (e).
Соединение списков:
соединить {(e1)(e2)} -> (e1 e2).
Подобным образом программируются и другие функции, аналогичные
примитивам Лиспа.
Упражнение. Аккуратно выпишите МТ-определения примитивов (базисных
функций) Лиспа. Учтите все их тонкости. Рассмотрите отличия функций первый,
хвост и создать от функций car, cdr и cons Лиспа.
Обратите внимание: по существу мы продемонстрировали способность модели
МТ к развитию - довольно легко определить в модели МТ новый язык,
аналогичный Лиспу.
14.1.3. Критерий концептуальной ясности и функции высших порядков
Продолжая рассматривать модели ЯП с технологической позиции,
продемонстрируем технологическую потребность в функциях высших порядков
(т.е. функциях, аргументами и (или) результатами которых служат функции).
Затем покажем, как их можно ввести в модели МТ, и рассмотрим модель Бэкуса
(модель Б), в которой функции высших порядков играют ключевую роль (введены
в базис).
Напомним, что к модели МТ мы пришли от идеи разделения анализа и
синтеза в обработке данных. И получили мощные средства развития, как только
ввели удобную базисную структуру данных (выражение), локализовали область
воздействия на эту структуру (ведущий терм) и упростили отбор возможных
воздействий (ввели МТ-функции).
Теперь у нас в руках аппарат, который можно развивать в различных
направлениях и (или) использовать в различных целях.
[Например, в реальном Рефале введены операции, позволяющие изменить
поле определений в процессе исполнения программы. Это так называемые
операции "закапывания" и "выкапывания" определений по принципу магазина. При
таком развитии получается стиль программирования, более близкий к
традиционному, с присваиванием глобальным переменным и взаимным влиянием
непересекающихся термов. Нас больше интересует развитие в функциональном
стиле.]
Воспользуемся аппаратом развития, чтобы показать богатейшие возможности
функционального программирования с точки зрения достижения концептуальной
ясности программ.
Идеалом будет служить такая программа, в которой в некотором смысле нет
ничего лишнего. Другими словами этот критерий концептуальной ясности можно
выразить так - структура функции, реализуемой программой, совпадает со
структурой программы.
[Однако при этом функция "состоит" из соответствий, а программа - из
операций.]
Важнейшая абстракция, способствующая приближению к намеченному идеалу -
функция высшего порядка (или, как мы ее назовем, следуя Бэкусу, форма).
Ближайшая задача - показать это на достаточно убедительных примерах.
Замечание. Важно понимать, что хотя модель МТ, конечно, алгоритмически
полна, она (как и любая другая модель) не универсальна в том смысле, что в
ней не всегда легко вводить любые абстракции. Однако формы в ней вводить
довольно легко.
14.1.4. Зачем нужны функции высших порядков
функции высших порядков возникают совершенно естественно. Классический
пример - программа интегрирования (вычисления определенного интеграла). Она
реализует некоторую форму, аргументом которой служит подынтегральная
функция, а результатом - число. Программа аналитического дифференцирования
реализует форму, аргументом которой служит некоторая функция (заданная,
например, многочленом), а результатом - ее производная, т.е. снова функция.
Любая из рассмотренных нами функций, выражающих денотационную семантику
модели Н или МТ, получается, как мы видели, определенной комбинацией
исходных функций, соответствующих базисным конструкциям. Если изменить эти
исходные функции, не меняя зафиксированной нами формы, представленной их
комбинацией, то получим другую семантику модели.
Так, при изменении в модели Н семантики операций изменится семантика
программы. В модели МТ также можно варьировать, например, правила
согласования или подстановки без всякого изменения денотационных соотношений
- они-то и фиксируют вполне определенную форму, отображающую пару (step,p) в
sem.
Замечания о функциях высших порядков.
Напомним, что рассматриваем мы функции только типа
E -> Е.
В частности, это означает, что все они формально имеют один аргумент.
Фактически может быть столько аргументов, сколько нужно - ведь аргументами
можно всегда считать последовательные термы выражения. Отдельные аргументы
можно всегда заключить в круглые скобки.
Однако чтобы не загромождать примеры, договоримся, что отделение
аргументов пробелами эквивалентно заключению в скобки. Другими словами,
будем в значительной степени абстрагироваться от "проблемы круглых скобок",
концентрируя внимание на принципиальных моментах (хорошо понимая, что в
практическом программировании от этой проблемы никуда не деться - в Лиспе,
например, она одна из самых неприятных).
Как только мы сказали, что имеем дело с функциями
Е -> Е
сразу возникает вопрос, как же быть с формами. У них-то аргументы - функции,
а не выражения. Ответ состоит в том, что и аргументы, и результаты форм
всегда будут представлены некоторыми выражениями (например, символами -
названиями функций).
Примем стиль изложения, при котором смысл вводимых программистских
абстракций будем объяснять с помощью определений в модели МТ. Иногда это
может показаться трудным для восприятия. Зато мы, во-первых, постоянно
упражняемся в программировании в модели МТ; во-вторых, немедленно
демонстрируем конкретизацию вводимой абстракции - а именно ее реализацию в
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
