РЕФАЛ (РЕкурсивных Функций АЛгоритмический язык) - это функциональный язык программирования, ориентированный на так называемые "символьные преобразования": обработку символьных строк (например, алгебраические выкладки), перевод с одного языка (искусственного или естественного) на другой, решение проблем, связанных с искусственным интеллектом. Функциональные языки программирования в настоящее время пользуются вполне заслуженной популярностью. Один из старейших членов этого семейства (впервые реализован в 1968 году в России, где широко используется и поныне), РЕФАЛ соединяет в себе математическую простоту с практической ориентацией на написание больших и сложных программ. ( См. *)
РЕФАЛ-5 является диалектом языка РЕФАЛ, разработанным в Нью-Йоркском Сити Колледже. Возможности, включенные в РЕФАЛ-5, прошли проверку временем.
В настоящем руководстве вы найдете примеры РЕФАЛ-программ следующих типов:
| * | Простые строковые преобразования: редактирование текстовых последовательностей, перевод слов и т.д. |
| * | Обработка деревьев и графов. |
| * | Хорошо известные алгоритмы сортировки. |
| * | Решение проблем искусственного интеллекта ("Миссионеры и каннибалы", задача, используемая во многих работах по ИИ). |
| * | Трансляция арифметического выражения в программу для одноадресной машины |
Реализации РЕФАЛ-5, как и всякого языка программирования, могут различаться в некоторых деталях. Наши примеры написаны для реализации РЕФАЛ-5, осуществленной Рефал Систем Инкорпорейтед; она будет в дальнейшем именоваться просто "РЕФАЛ-системой". В этой реализации внимание сконцентрировано на существенных особенностях языка, имеет место лишь основной интерфейс пользователя с системой, достаточно большое внимание уделено средствам отладки. В разделах Справочника приведены наиболее важные черты нашей РЕФАЛ-системы.
В отличие от ЛИСПа, основу РЕФАЛа составляет сопоставление с образцом. Благодаря этому типовая программа на РЕФАЛе вдвое-втрое короче по объему, чем аналогичная программа на языке ЛИСП, и гораздо более читаема. От ПРОЛОГа РЕФАЛ отличает концептуальная простота. Его сопоставление с образцом работает в прямом направлении, а не в обратном (начиная от цели), как в ПРОЛОГе. Это более естественный подход к написанию алгоритмов, что делает их более легкими для тестирования и отладки.
Далее, имеется существенное различие между структурами данных в РЕФАЛе и в большинстве других языков высокого уровня. Основные структуры данных в ЛИСПе и ПРОЛОГе - это списки, которые могут читаться только в одном направлении. РЕФАЛ использует более общие структуры. Вы можете строить и читать их слева-направо и справа-налево и, конечно же, прыгать внутрь и наружу по скобочным структурам. Это очень удобно для программиста. РЕФАЛ дает свободу и удобство в создании структур данных наряду с использованием лишь математически простых механизмов управления - сопоставления с образцом и подстановки. Это именно то, что нужно для символьной обработки и для искусственного интеллекта.
Перечислим другие черты языка: простота, высокая модульность, встроенная структурируемость программ (вы не смогли бы встроить GO TO в РЕФАЛ, даже если бы захотели). Весьма простая семантика РЕФАЛа облегчает трассировку и отладку. РЕФАЛ-система включает в себя мощный трассировщик-отладчик, который может, помимо всего прочего, отловить момент, когда аргумент вычисляемой функции удовлетворяет некоторому заданному образцу.
Частичное вычисление вызовов функций превратилось со временем в важный тип программной трансформации. РЕФАЛ-5 содержит такое средство ("морозильник"), которое специально предназначено для эффективных частичных вычислений.
Благодаря своей фундаментальной простоте, РЕФАЛ является прекрасным выбором для первоначального знакомства студентов с языками функционального программирования. Он изучается в Нью-Йоркском Сити Колледже уже несколько лет, и получены весьма положительные отзывы от студентов. РЕФАЛ также является великолепным средством для исследований по теории программирования и преобразования программ. Лицам с математической ориентацией РЕФАЛ предоставляет всю мощь практического языка программирования, но при этом исключается необходимость изучать множество мелких деталей, которыми, как известно, изобилуют многие другие языки программирования.
* См., например, V.Turchin, The concept of supercompiler, ACM Transactions on Programming Languages and Systems, vol. 8, pp.292-325 (1986). Эта статья содержит также краткое описание упрощенной версии РЕФАЛа.