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

Упражнение 1:

Номер 1

 Какие есть основные модели вычислений?

Ответ:

(1) нормальные алгоритмы Маркова

(2) машина фон-Неймана

(3) машина Тьюринга

(4) логика высказываний

Номер 2

 Какая модель вычислений служит формальной основой функционального программирования?

Ответ:

(1) Машина Тьюринга

(2) логика предикатов

(3) логика высказываний

(4) комбинаторная логика

Номер 3

 В чем преимущества лямбда-исчисления как модели вычислений?

Ответ:

(1) это формальная аксиоматическая система

(2) оно соответствует тому, как происходят вычисления в компьютере

(3) на базе лямбда-исчисления просто построить язык программирования

(4) в лямбда-исчислении хорошо описывается различная семантика вызовов фунций

Упражнение 2:

Номер 1

 Какие базовые операции чистого лямбда-исчисления?

Ответ:

(1) аппликация

(2) абстракция, аппликация

(3) абстракция, аппликация, композиция

(4) абстракция, аппликация, композиция, сложение

Номер 2

 Какая операция повышает порядок функции?

Ответ:

(1) аппликация

(2) абстрация

(3) композиция

(4) унификация

Номер 3

 Какая операция понижает порядок функции?

Ответ:

(1) аппликация

(2) абстрация

(3) композиция

(4) унификация

Номер 4

Какая операция применяет функцию к аргументу?

Ответ:

(1) аппликация

(2) абстракция

(3) композиция

(4) унификация

Упражнение 3:

Номер 1

 Как расставляются скобки в выражении λx.λy.e1e2?

Ответ:

(1) (λx.(λy.e1)e2)

(2) λx.((λy.e1)e2)

(3) (λx.λy).(e1e2)

(4) (λx.(λy.e1e2))

Номер 2

 Как расставляются скобки в выражении f sin x*2?

Ответ:

(1) ((f sin) x)*2

(2) (f (sin x))*2

(3) f(sin(x*2))

(4) f(sin(x))*2

Номер 3

 Как правильно расставить скобки в выражении лямбда-исчисления, чтобы вычислить f(g(x))?

Ответ:

(1) f g x

(2) f(g(x))

(3) f (g x)

(4) (f g) x

Упражнение 4:

Номер 1

 Какое из приведенных ниже преобразований является примером бета-редукции?

Ответ:

(1) (λx.sin x) z → sin z

(2) (λx.sin x) z → (λy.sin y) z

(3) sin 0 → 0

(4) (λx.sin x) 0 → 0

Номер 2

 Какое из приведенных ниже преобразований является примером альфа-редукции?

Ответ:

(1) (λx.sin x) z → sin z

(2) (λx.sin x) z → (λy.sin y) z

(3) sin 0 → 0

(4) (λx.sin x) 0 → 0

Номер 3

 Какие из преобразований надо применить, чтобы редуцировать (λx.sin x) 0 → 0?

Ответ:

(1) альфа-редукцию и бета-редукцию

(2) альфа-редукцию

(3) бета-редукцию

(4) бета-редукцию и дельта-редукцию

Упражнение 5:

Номер 1

 Какой самый внутренний редекс в выражении (λx.λy.y) ((λz.z z) (λz.z z))?

Ответ:

(1) (λz.z z)

(2) (λz.z z) (λz.z z)

(3) (λx.λy.y) ((λz.z z) (λz.z z))

(4) (λx.λy.y)

Номер 2

 Какой самый внешний редекс в выражении (λx.λy.y) ((λz.z z) (λz.z z))?

Ответ:

(1) (λz.z z)

(2) (λz.z z) (λz.z z)

(3) (λx.λy.y) ((λz.z z) (λz.z z))

(4) (λx.λy.y)

Упражнение 6:

Номер 1

 Какой будет следующий шаг при нормальном порядке редукции выражения (λx.x+x)(2+3)?

Ответ:

(1) (2+3)+(2+3)

(2) (λx.x+x) 5

(3) 10

(4) (λx.(2+3)+x)(2+3)

Номер 2

 Какой будет следующий шаг при аппликативном порядке редукции выражения (λx.x+x)(2+3)?

Ответ:

(1) (2+3)+(2+3)

(2) (λx.x+x) 5

(3) 10

(4) (λx.(2+3)+x)(2+3)

Номер 3

 При нормальном порядке редукции:

Ответ:

(1) редуцируется самый левый из самых внешних редексов

(2) редуцируется самый правый из самых внешних редексов

(3) редуцируется самый левый из самых внутренних редексов

(4) редуцируется самый правый из самых внутренних редексов

Номер 4

При аппликативном порядке редукции:

Ответ:

(1) редуцируется самый левый из самых внешних редексов

(2) редуцируется самый правый из самых внешних редексов

(3) редуцируется самый левый из самых внутренних редексов

(4) редуцируется самый правый из самых внутренних редексов

Упражнение 7:

Номер 1

 Что является следствием теоремы Черча-Россера?

Ответ:

(1) применение нормального порядка редукции позволяет всегда получить нормальную форму

(2) применение нормального порядка редукции предпочтительнее, чем аппликативного

(3) если нам удалось редуцировать выражение до нормальной формы, то эта форма единственная, вне зависимости от порядка редукции

(4) если нам удалось редуцировать выражение до нормальной формы, то эта форма единственная с точностью до альфа-преобразования, вне зависимости от порядка редукции

Номер 2

 Что является следствием теоремы стандартизации?

Ответ:

(1) применение нормального порядка редукции позволяет всегда получить нормальную форму

(2) применение аппликативного порядка редукции позволяет всегда получить нормальную форму

(3) если нам удалось редуцировать выражение до нормальной формы, то эта форма единственная, вне зависимости от порядка редукции

(4) если нам удалось редуцировать выражение до нормальной формы, то эта форма единственная с точностью до альфа-преобразования, вне зависимости от порядка редукции

Номер 3

 Какой порядок редукции соответствует передаче параметров по значению?

Ответ:

(1) аппликативный

(2) нормальный

(3) нормальный с мемоизацией

(4) передача параметров не связана с порядком редукции

Номер 4

Какому способу передачи параметров соответствует аппликативный порядок редукции?

Ответ:

(1) по имени

(2) по ссылке

(3) по значению

(4) по адресу

Упражнение 8:

Номер 1

 Как определяют рекурсивные вычисления в лямбда-исчислении?

Ответ:

(1) с помощью оператора неподвижной точки Y

(2) с помощью рекуррентных соотношений

(3) с помощью комбинаторов I, K

Номер 2

 Какие комбинаторы образуют наименьший базис?

Ответ:

(1) S, K

(2) I, K, S

(3) Y

(4) Y, I, K, S

Номер 3

 Какое максимальное количество неподвижных точек может иметь функция?

Ответ:

(1) одну, которая возвращается оператором Y

(2) бесконечное множество – Y возвращает наименьшую неподвижную точку

(3) бесконечное множество – Y возвращает наибольную неподвижную точку

Функциональное программирование - тест 16