Вопросы к экзамену по дисциплине

«Функциональное и логическое программирование»

Язык Лисп.

1. Базовые функции обработки списков.

2. Определение и вызов функций с помощью λ-выражений. λ-список, λ-преобразование. Свободные и связанные переменные. Функция DEFUN

3. Локальные определения (форма LET).

4. Функции более высокого порядка. Функциональный аргумент, функциональное значение. Способы композиции функций.

5. Автоматическое управление памятью в Лиспе. «Сборка мусора».

6. Создайте Лисп-список, предсталяющий собой список планет Солненой системы.

7. Почему значения в Лиспе представлены указателями?

8. Определите функцию add5(n), которая увеличивает числовой параметр n на 5.

9. Определите функцию add5(n), которая увеличивает числовой параметр n на 5, используя синтаксис λ-определения.

10. Суперпозиция (или «композиция») функций как средство формирования более сложных функций.

11. Какую (двоякую) роль играет в Лиспе функция eval?

12. Возвращение функцией нескольких величин.

13. Базовые функции Лиспа.

14. Опишите три варианта предиката равенства в Лиспе.

Язык Пролог.

1. Равенство в Прологе.

2. Встроенные предикаты. Предикаты взаимодействия.

3. Встроенные предикаты. Размещение данных.

4. Аппарат вычислений. Обработка списков.

5. Аппарат вычислений. Рекурсивные определения в Прологе.

6. Аппарат вычислений. Управление откатом: отсечение.

7. Аппарат вычислений. Поиск в глубину с возвратом.

8. Аппарат вычислений. Вывод и процедура отката.

9. Аппарат вычислений. Процедура унификации в Прологе.

10. Синтаксис данных (термы и основные объекты Пролога).

11. Структура программы в языке Пролог (синтаксис языка).

12. Логическая и управляющая компоненты Пролога.

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

14. Общая характеристика языка Пролог.

1Базовые функции обработки списков.

Базовыми функциями обработки символьных выражений (атомов и списков) являются: first, rest, cons, atom и eq.

  У функции cons и eq имеются два аргумента, у остальных примитивов - по одному. В качестве имён аргументов и результатов функций использовано названия типов, описывающих аргументы.

  Функции atom и eq являются базовыми предикатами. Предикаты - это функции, которые проверяют выполнение некоторого условия и возвращают в качестве результата false или nil.

С помощью селекторов first и rest можно выделить из списка его голову и хвост. Функция first возвращает в качестве значения первый элемент списка, т.е. головной элемент списка.

Функция REST возвращает в качестве значения хвостовую часть списка.

Функция CONS включает новый элемент в начало списка.

При работе с выражениями необходимо иметь возможность проверить, является ли выражение атомом или списком. Это может потребоваться, например, перед применением функции first и rest, так как эти функции определены лишь для аргументов, являющихся списками. Базовый предикат atom используется для идентификации лисповских объектов, являющихся атомами.

EQ проверяет тождественность двух символов

2Определение и вызов функций с помощью λ-выражений. Λ-список, λ-преобразование. Свободные и связанные переменные. Функция defun

В Лиспе лямбда-выражение имеет вид: (lambda (x1 x2 … xn) {fn})

Символ lambda означает, что мы имеем дело с определением функции. Символы xi являются формальными параметрами определения, которые именуют аргументы в описывающем вычисления теле функции {fn}. Входящий в состав формы список, образованный из параметров, называют лямбда-списком.

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

(obj лямбда-выражение a1 a2 … an)

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

(lambda (x1, . . ., хп).ехр), где lambda - фиксированный атом, (x1, . . ., хп) - список связанных переменных, обозначающих аргументы функции, а ехр - выражение, вычисляющее значение функции и содержащее в себе x1, . . ., хп как свободные переменные.

(defun <символ> <список аргументов> <выражение>...)

DEFUN - определяет функцию с именем <символ>. За функцией следует список аргументов (возможно пустой), за которым следует (факультативно) косая черта (slach) и имена одного или более локальных переменных функции. Косая черта должна отстоять от первого локальной переменной и последнего аргумента хотя бы на один пробел. Если нет аргументов и локальных символов, которые следует объявлять, за именем функции следует поставить пустые скобки. (defun myfunc (x y) ... ) ;(функция берет два аргумента) (defun myfunc (/ a d) ... ) ;(функция имеет две локальных переменных)