книги / Функциональное программирование

P

print – псевдофункция вывода, выводит значение аргумента на монитор, а затем возвращает значение аргумента

prog1, prog2, prong – предложения для выполнения последовательных действий

R

read – функция ввода

return–функцияокончаниявычисленияивозвратазначения reverse – функция, которая изменяет порядок элементов

в аргументе

S

symbol-function – в «Лиспе» выдает определение функции symbol-value – в «Лиспе» выдает значение символа S-выражение – это либо атом, либо список

T

t–специальнаяконстанта«Лиспа»,обозначающаяtrue(истина)

U

unless – условное предложение

W when – условное предложение

А

Ада – алгоритмический язык программирования. Алгоритм унификации – алгоритм, который находит

наибольший общий унификатор двух термов, если такой существует. Если термы не унифицируемы, алгоритм сообщает об отказе.

151

Аппликативный язык программирования – строго функциональный язык программирования.

Аппликация – применение функции к своим аргументам. Арность – количество аргументов предиката.

Атомы – это простейшие объекты «Лиспа», из которых строятся остальные структуры. Атомы бывают двух типов – символьные и числовые.

Г

Граничное условие – некоторое условие, которое останавливает рекурсию.

Д

Декларативный язык программирования (от лат. declaratio – «объявление») – язык программирования высокого уровня, построенный на описании данных и на описании искомого результата. Декларативные языки подразделяются на функциональные и логические.

Домен (тип данных) – характеристика набора данных, которая определяет диапазон возможных значений данных из набора, допустимые операции, которые можно выполнять над этими значениями, способ хранения этих значений в памяти. Различают простые типы данных: целые, действительные числа и др., составные типы данных: структуры, списки и др.

И

ИИ – искусственный интеллект.

Императивное программирование – задающее жесткую последовательность действий программирование.

Инфиксная запись – запись, в которой имя функции или действия располагается между аргументами.

К

Карри Хаскелл – см. Хаскелл Карри.

Клин (Clean) – язык функционального программирования.

152

Ключевые слова:

&OPTIONAL – необязательные параметры; &REST – переменное количество параметров; &KEY – ключевые параметры;

&AUX – вспомогательные переменные.

Контекст – совокупность действующих связей переменных с их значениями.

Л

Лексема – наименование смысловой единицы, распознаваемой лексическим анализатором в тексте программы. Лексемами являются переменные, символы и ключевые слова, целые числовые литералы, вещественные числовые литералы, сегменты строк, ограничители.

Лисп – язык функционального программирования.

Лямбда-выражение (λ-выражение) – изображает парамет-

ризованные вычисления. λ-выражение – это определение вычислений и параметров функции в чистом виде без фактических параметров, или аргументов. Лямбда-выражение – функция без имени.

М

Маккарти Джон – создатель языка Lisp.

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

153

Многозначные функции – функции, которые возвращают множество значений.

Н

Нейман Джон – см. Фон Нейман Джон.

О

ООП – объектно-ориентированное программирование. Остовное дерево графа G – это связный граф Т = (V, Е'), где

Е' – подмножество Е, такое, что Т – связный граф и в Т нет циклов.

П

Правила Бэкуса – Наура – служат для определения и работы со списками:

список → NIL

список → (голова. хвост) голова → атом голова → список хвост → список

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

Префиксная форма записи – форма, в которой имя функции или действия стоит перед аргументами и записывается внутри скобок.

Программа машины фон Неймана – см. машина фон Неймана.

Простая рекурсия – см. рекурсия простая. Псевдофункция – функция, у которой кроме значения есть

побочный эффект.

154

Р

Рекурсивная процедура – процедура, вызывающая сама себя до тех пор, пока не будет соблюдено некоторое условие, которое остановит рекурсию.

Рекурсия взаимная – когда в определении функции f вызывается некоторая функция g, которая, в свою очередь, содер-

жит вызов функции f: (defun f … (g…) …); (defun g …. (f …) …).

Рекурсия является взаимной между двумя или более функциями, если они вызывают друг друга.

Рекурсия параллельная – когда тело определения функции f содержит вызов некоторой функции g, несколько аргументов которой являются рекурсивными вызовами функ-

ции f: (defun f … (g… (f …) … (f …) …) …). Рекурсию назы-

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

Рекурсия простая – если в ее определении содержится вызов самой этой функции.

Рекурсия более высокого порядка – когда аргументом рекурсивного вызова является рекурсивный вызов: (defun f …. (f… (f…) …) …).

Рекурсия по аргументам – если в качестве результата функции возвращается значение некоторой другой функции и рекурсивный вызов участвует в вычислении аргументов этой функции.

Рекурсия по значению – когда рекурсивный вызов является выражением, определяющим результат функции.

С

Свободная переменная – переменная в теле функции, не входящая в число ее формальных параметров.

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

155

Т

Теория рекурсивных функций – область математики, где изучаются теоретические вопросы, связанные с вычислимостью.

Терм – синтаксическая конструкция, обозначающая элемент данных. Различаются простые и составные термы.

Тьюринг Алан – основоположник программирования.

У

Унификатор двух термов – подстановка, которая делает термы одинаковыми.

Унификация – операция сравнения (отождествления) двух объектов, связывающая переменные в составе объектов. Унификация различных (несвязанных) переменных приводит к сцеплению этих переменных.

Ф

Фон Нейман Джон – основоположник программирования. Функтор – имя, которому приписана некоторая арность

(число аргументов).

Функционал (функция высшего порядка) – функция, принимающая функцию в качестве аргумента.

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

Функция – правило, сопоставляющее каждому элементу некоторого класса Х соответствующий ему единственный элемент класса Y, где Y – область значений; Х – область определения.

Функция высшего порядка – см. функционал.

156

Х

Хаскелл Карри – основоположник функционального программирования.

Ч

Чёрч Алонзо – создатель λ-исчисления.

Ш

Шёнфинкель Мозес – основоположник функционального программирования.

Я

Язык программирования «Лисп» (Lisp – List Processing) –

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

157

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

1.Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Структуры данных: учебник. – Нижний Новгород: Издательство Нижегородского госуниверситета, 2004. – 291 с.

2.Новицкая Ю.В. Основы логического и функционального программирования: учеб. пособие. – Новосибирск, 2006. – 60 с.

3.Филд А., Харрисон П. Функциональное программирование: пер. с англ. – М.: Мир 1993. – 637 с.

4.Хювёнен Э., Сенпянен И. Мир «Лиспа»: в 2 т.: пер.

сфин. – М.: Мир, 1990. – Т. 1. Введение в язык «Лисп» и функциональное программирование. – 447 с.

5.Фленов М. Библия Delphi. – СПб.: БХВ-Петербург, 2004. – 880 с.

6.Душкин Р.В. Лекции по курсу функционального программирования. – М., 2001.

158