«В.Э. Вольфенгаген, Л.В. Гольцева, Л.Ю. Исмаилова АППЛИКАТИВНЫЕ ВЫЧИСЛЕНИЯ на основе комбинаторов и -исчисления Издание 3-е, стереотипное Проект: Аппликативные ...»

МОСКОВСКИЙ ИНЖЕНЕРНО-ФИЗИЧЕСКИЙ ИНСТИТУТ

(ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ)

В.Э. Вольфенгаген,

Л.В. Гольцева,

Л.Ю. Исмаилова

АППЛИКАТИВНЫЕ

ВЫЧИСЛЕНИЯ

на основе комбинаторов и -исчисления

Издание 3-е, стереотипное

Проект: Аппликативные Вычислительные Системы

Руководитель проекта, кандидат технических наук Л.Ю.Исмаилова Москва 2007 I Факультет кибернетики Проект: Аппликативные Вычислительные Системы Руководитель проекта, кандидат технических наук Исмаилова Л.Ю.

Д.т.н., профессор Вольфенгаген В.Э., к.т.н., Гольцева Л.В., к.т.н., Исмаилова Л. Ю.

Аппликативные вычисления на основе комбинаторов и -исчисления.— 3-е изд.— М.: МИФИ, 2007.—72 с.

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

Аппликативные вычисления излагаются как набор таких методов и средств.

Для студентов и аспирантов всех специальностей. Может быть использована для первоначального самостоятельного изучения предмета.

c В.Э. Вольфенгаген, 1992– c Институт Актуального Образования “ЮрИнфоР-МГУ”, c Московский инженерно-физический институт, Московский инженерно-физический институт Лаборатория ИИТ и ВС, комната 119а Москва, 115409 РФ Fax: +7 (495) 323-94- E-mail: vew@jmsuice.msk.ru II Оглавление Предисловие к 1-му изданию........................... Предисловие ко 2-му изданию.......................... 1. Введение......................................... Часть I. Элементарная техника аппликативных вычислений 2. -исчисление..................................... 2.1 -обозначения................................... 2.2 Формальная система -исчисления................ 3. Структура терма и подстановка..................... 3.1 Структура терма................................. 3.2 Подстановка..................................... 4. Графическое представление термов................. 5. Свертывание...................................... 6. Комбинаторная логика............................. 6.1 Комбинаторы.................................... 6.2 Формальная система комбинаторов................ 7. Слабая редукция.................................. 8. Теорема о неподвижной точке...................... 9. Формальные теории и CL..................... IV Оглавление 10. Модели CL...................................... Часть II. Лабораторный практикум 12. Механизмы построения практикума................. 13. Восстановление скобок в -термах.................. 16. Разложение термов в базисах I, K, S и I, B, C, S.... 17. Расширение базисной системы комбинаторов........ 18. Техника анализа введенных результатов............. Предисловие к 1-му изданию Настоящее учебное пособие подготовлено для проведения семинарских занятий и лабораторных работ и охватывает вопросы использования комбинаторов и -исчисления при реализации аппликативных вычислений. Наряду с теоретическими сведениями основное внимание уделено выполнению упражнений, закрепляющих навык владения комбинаторной логикой. Материал ориентирован на развитие на развитие у студентов умения соединять теоретическое рассмотрение задачи с ее практической реализацией на компьютере. Решение задач предполагает проведение дополнительных преобразований с целью оптимизации выражений, устранения в них переменных, упрощения целевого исполняемого выражения. Аппликативные вычисления излагаются как набор таких методов и средств.

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

Общая идея разработки практикума, который бы позволил начинающему без излишних трудозатрат освоить методы записи аппликативных форм возникла в 1986 г. при проведении в МИФИ практических занятий со студентами по соответствующим разделам дисциплин по компьютерным наукам. Постановка задачи принадлежит к.т.н. Л.Ю. Исмаиловой, под чьим общим руководством аспиранткой Л.В. Гольцевой было реализовано программное обеспечение.

Москва, Институт Актуального Образования “ЮрИнфоР-МГУ” 4 Предисловие 1. Введение -исчисление – это бестиповая теория, рассматривающая функции как правила, а не как графики. Понятие ‘функции как закона или правила’ подразумевает переход от аргумента к значению, процесс, закодированный некоторым определением. -исчисление рассматривает функции с точки зрения их вычисления.

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

6 1. Введение Элементарная техника аппликативных 2. -исчисление, основные определения 2.1 -обозначения Для пояснения -обозначений рассмотрим математическое выражение ‘x y’. Его можно рассматривать как определение функции f от x или функции g от y:

Для их различения требуется такое определение, которое дает функциям f и g различные имена некоторым систематическим способом. Нотация Черча – это систематический способ построения для выражения, включающего переменную ‘x’, обозначения для соответствующей функции от x (аналогичным способом для y):

Например, рассмотрим равенства В -обозначениях они принимают вид:

-обозначения могут быть распространены на случай функций от более, чем одной переменной. Например, выражение ‘x y’ определяет две функции h и k от двух переменных как Эти определения можно переписать как 10 2. -исчисление Однако можно избежать использования специальных обозначений для функций с различными переменными, используя функции, значения которых являются не числами, а представляют собой другие функции. Например, вместо 2-местной функции h, определенной выше, рассмотрим 1-местную функцию h, определенную посредством Для каждого числа ‘a’ получаем:

Следовательно, для каждой пары чисел a и b:

2.2 Формальная система -исчисления Построим формальную систему -исчисления.

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

Определение 2.1 (-терм). Множество выражений, называемых -термами, определяется следующим способом:

i) все переменные и константы, являющиеся -термами, называются атомами;

ii) если M и N – произвольные -термы, то (M N ) – -терм, называемый аппликацией;

iii) если M – произвольный -терм, а x - произвольная переменная, то (x.M ) – -терм, называемый абстракцией.

Пример 2.1. Примеры -термов:

(x.(xy)), ((y.y)(x.(xy))), (x(x(x.x))), (x.(yz)) Прописными буквами будем обозначать произвольные -термы.

Строчными буквами ‘x’, ‘y’, ‘z’, ‘u’, ‘v’, ‘w’ будем обозначать переменные. Скобки опускаются таким образом, что, например, ‘M N P Q’ обозначает (((M N )P )Q). Это преобразование называется сокращением (восстановлением) скобок по ассоциации влево.

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

Графическое равенство будет обозначаться знаком ‘=’. Например, запись ‘M = N ’ будет обозначать, что M в точности такой же терм, что и N. В дальнейшем будет предполагаться, что если Также будет предполагаться, что 4-е класса термов – переменные, константы, аппликации, абстракции, – не имеют общих элементов. Это принимается всегда при определении множеств выражений. Такое определение терма позволяет сформировать больше термов, чем это необходимо для приложений системы. Следовательно, часть термов остается неинтерпретированной.

Если терм M был проинтерпретирован как функция или оператор, то (M N ) интерпретируется как результат приложения (апплицирования) M к аргументу N с обеспечением того, что этот результат определен. Терм (x.M ) представляет оператор, значение которого на аргументе N вычисляется подстановкой N вместо x всюду, где x имеет свободные вхождения в M.

Примеры Пример 2.2. x.x(xy) представляет операцию применения функции дважды к объекту, обозначаемому y, и равенство ( x.x(xy))N = N(Ny) выполняется для всех термов N в том смысле, что обе стороны имеют одинаковую интерпретацию.

Пример 2.3. x.y представляет константную функцию, которая принимает значение y для всех аргументов, и равенство несет тот же смысл, что и предыдущее.

12 2. -исчисление Упражнения Упражнение 2.1. Представить следующие выражения в формальном -обозначении, используя D для обозначения оператора дифференцирования:

Упражнение 2.2. Расставить недостающие скобки: