Файл: Учебные пособия по логическому и функциональ ному программированию В. М. Зюзькова. В пособие внесены изменения в 2020 г.pdf

58
Следующие три определения реализуют эти функции (необязательно в том же порядке):
1)
(defun f (s x)
(cond ((null s) nil)
((equal x (first s)) (f (rest s) x))
((listp (first s)) (cons (f (first s) x) (f (rest s) x)))
(t (cons (first s) (f (rest s) x)))))
2)
(defun f (s x)
(cond ((null s) nil)
((equal x (first s)) (rest s))
(t (cons (first s) (f (rest s) x)))))
3)
(defun f (s x)
(cond ((null s) nil)
((equal x (first s)) (f (rest s) x))
(t (cons (first s) (f (rest s) x)))))
Введите через пробел номера определений, соответствующих действиям в порядке 1), 2), 3).
Вопрос 57
Лисп. Сколько элементов самого верхнего уровня в следующих списках:
1) ((1 2 3));
2) ((a b) c (d (e)));
3) (a ((())) nil nil);
4) ((((a (b (c d) e) f) g) h ((i (j) k) l) m) n)
Введите последовательность ответов через пробел (в порядке нумерации).
Вопрос 58
Лисп. Определите значения следующих выражений:
1) (length '(+ 2 (* 3 4)));
2) (length (+ 2 '(* 3 4)));
3) (length (+ 2 ('* 3 4)));
4) (length (+ 2 (* 3 '4)));
5) (length (quote 'quote));
6) (length (quote 2));
7) (length '(quote nil)).
Введите последовательность ответов через пробел (в порядке нумерации).
Возможные ответы: число или слово error (ситуация ошибки).

59
Вопрос 59
Лисп. Может ли функция принимать разные значение на одних и тех же ар- гументах?
Варианты ответов:
1) нет, если "чистая" функция;
2) да, если есть побочные эффекты у других функций;
3) да, если используются глобальные переменные.
Введите последовательность номеров правильных ответов через пробел (в порядке нумерации).
Вопрос 60
Лисп. Какие из следующих вызовов возвращают значение t?
1) (atom '(cdr nil));
2) (equal '(a b) (cons '(a) '(b)));
3) (atom (* 2 (+ 2 3)));
4) (null (null t));
5) (eq nil (null nil))
6) (eql 2.0 2)
7) (equal 2.0 2)
8) (= 2.0 2)
9) (equal (atom nil) (caar '((t))))
Введите последовательность номеров правильных ответов через пробел (в порядке нумерации).
Вопрос 61
Лисп. Дана последовательность выражений:
1) (length (cons nil '(nil)));
2) (length (cons nil nil));
3) (length (cons '(nil) '(nil)));
4) (length (cons (car '(a b)) (cdr '(a b))));
5) (length (car '(car (a b c))));
6) (length (cdr (car (cdr '(a b c))))).
Введите последовательность ответов через пробел (в порядке нумерации).
Возможные ответы: число или слово error (ситуация ошибки).

Вопрос 62
Лисп. Вычислите значения следующих выражений:
1) (length ((lambda (x) (cons x nil)) 'y));
2) (length ((lambda (x y) (list y x)) 'x y));
3) (length ((lambda (x) (list x)) (list nil)));
4) (length ((lambda (x) (list x)) ((lambda (x) (list x)) (list nil)))).
Введите последовательность ответов через пробел (в порядке нумерации).
Возможные ответы: число или слово error (ситуация ошибки).

60
Вопрос 63
Лисп. Вычислите значения следующих выражений:
1) (length ((lambda (x y) (list x y)) '(+ 2 3) 'c));
2) (length ((lambda (x y) ((lambda (z) (list x y z)) 'c));
3) (length ((lambda (x y) (list x y))
((lambda (z) z) 'a) 'b)).
Введите последовательность ответов через пробел (в порядке нумерации).
Возможные ответы: число или слово error (ситуация ошибки).
Вопрос 64
Лисп. Вычислите значения следующих вызовов:
1) (length (apply 'list '(a b)));
2) (length (funcall 'list '(a b)));
3) (length (funcall 'apply 'list '(a,b)));
4) (length (funcall 'list 'apply '(a b))).
Введите последовательность ответов через пробел (в порядке нумерации).
Возможные ответы: число или слово error (ситуация ошибки).
Вопрос 65
Лисп. Какова неподвижная точка функции (lambda (x) (+ 1 (/ x 2))?
Введите значение.
Вопрос 66
Следующие предложения на Лиспе должны следовать друг за другом. В каж- дом случае укажите, имеет ли результат какой-либо смысл. (Например, если за (setq x 'y) следует (setq z (+ 6 x)), то второе из этих предложений - очевид- ная бессмыслица, потому что оно пытается сложить 6 с символом y.)
1) (setq a (+ 3 7))
2) (setq a (+ a 7))
3) (set a (+ a 7))
4) (setq b 'alpha)
5) (set b 'beta)
6) (setq c (+ 6 alpha))
7) (setq c (+ 6 'alpha)).
Введите последовательность номеров через пробел тех выражений, которые имеют смысл (в порядке возрастания).
Вопрос 67
Лисп. Имеется два определения символьного выражения.
1. Символьное выражение составляется из атомов (которые могут быть кон- стантами или переменными) и скобок таким образом, что если мы пред- ставим себе счетчик, установленный вначале в нуль, и будем увеличивать

61 его на единицу при движении слева направо каждый раз, когда встречается левая скобка, и уменьшать на единицу каждый раз, когда встречается пра- вая скобка, то его конечное значение будет нуль. Атомы между собой должны разделяться пробелами.
2. Символьное выражение - это либо атом, либо левая круглая скобка, за ко- торой следует последовательность символьных выражений, отделенных друг от друга пробелами, и следующая за нею правая круглая скобка.
Правильны ли эти определения?
Варианты ответов:
1) оба правильны;
2) оба неправильны;
3) первое - правильное, второе - неправильное;
4) второе - правильное, первое - неправильное.
Введите номер правильного ответа.
Вопрос 68
Лисп. Каково общее число подсписков в подсписках (т. е. списки уровня 3; исходный список имеет уровень 1) в следующих списках:
1) (6 (3 6 (7 (4 5) 8)) (9 3));
2) (((a 9( (b 7) c) (d 5));
3) (quote (s (3 5) (7 (9 8))));
4) (d (q 2 7 4) (+ 1 (* 7 (+ 3 (- 2)))))?
Введите последовательность чисел через пробелы в порядке перечисления исходных списков.
Вопрос 69
Лисп. Дан лямбда-терм
(h. (x. h(x x))(x. h(x x))) ((x. x) (+ 1 5)) и некоторые его подтермы:
1) x. h(x x);
2) h. (x. h(x x))(x. h(x x));
3) (x. h(x x))(x. h(x x));
4) (h. (x. h(x x))(x. h(x x))) ((x. x) (+ 1 5));
5) ((x. x) (+ 1 5));
6) (x. x);
7) (+ 1 5).
Какие из этих подтермов являются редексами?
Введите номера соответствующих подтермов через пробел (в порядке возрас- тания).

62
Вопрос 70
Лисп. Дан лямбда-терм
(x. y. x (z. y z))(((x. y. y) 8)(x. (y. y) x)) и некоторые его подтермы:
1) x (z. y z);
2) x. y. x (z. y z);
3) x. y. y;
4) (x. y. y) 8;
5) (y. y) x;
6) x. (y. y) x;
7) (x. y. x (z. y z))(((x. y. y) 8)(x. (y. y) x));
8) ((x. y. y) 8)(x. (y. y) x).
Какие из этих подтермов являются редексами?
Введите номера соответствующих подтермов через пробел (в порядке возрас- тания).
Вопрос 71
Лисп. Дан лямбда-терм
(h. (x. h(x x))(x. h(x x))) ((x. x) (+ 1 5)) и некоторые его подтермы:
1) x. h(x x);
2) h. (x. h(x x))(x. h(x x));
3) (x. h(x x))(x. h(x x));
4) (h. (x. h(x x))(x. h(x x))) ((x. x) (+ 1 5));
5) ((x. x) (+ 1 5));
6) ((x. x);
7) (+ 1 5).
Какой из этих подтермов является самым левым из самых внешних редексов и самым левым из самых внутренних редексов?
Введите номера соответствующих подтермов через пробел (сначала номер самого левого из самых внешних редексов, потом номер самого левого из самых внутренних).
Вопрос 72
Лисп. Дан лямбда-терм
(x. y. x (z. y z))(((x. y. y) 8)(x. (y. y) x))

63 и некоторые его подтермы:
1) x (z. y z);
2) x. y. x (z. y z);
3) x. y. y;
4) (x. y. y) 8;
5) (y. y) x;
6) x. (y. y) x;
7) (x. y. x (z. y z))(((x. y. y) 8)(x. (y. y) x));
8) ((x. y. y) 8)(x. (y. y) x).
Какой из этих подтермов является самым левым из самых внешних редексов и самым левым из самых внутренних редексов?
Введите номера соответствующих подтермов через пробел (сначала номер самого левого из самых внешних редексов, потом номер самого левого из самых внутренних).
Вопрос 73
Лисп. Какие из следующих утверждений верны?
1. -исчисление - это исчисление безымянных функций. Оно включает в себя нотацию для записи выражений и набор правил преобразований этих вы- ражений.
2. -исчисление может быть дополнено произвольным набором констант, та- ких, как целые числа, и связанных с ними функций, называемых
-правилами.
3. Когда есть возможность выбрать редекс для преобразования, выбор опре- деляется порядком редукций. Двумя альтернативными стратегиями выбора являются аппликативный порядок редукций и нормальный порядок редук- ций, тесно связанные с ленивым вычислением и энергичным вычислением, соответственно.
4. Удалив -правила, мы получим чистое -исчисление. В нем нельзя выра- зить некоторые функции.
Введите номера правильных утверждений через пробел (в порядке возраста- ния).
Вопрос 74
Лисп. Что является наименьшей неподвижной точкой выражения x. * x x ?
Введите число.

64
Вопрос 75
Лисп. Какие из следующих утверждений верны?
1. Язык XLisp - функциональный язык с ленивыми вычислениями.
2. Язык XLisp - функциональный язык с энергичными вычислениями.
3. Язык XLisp - функциональный язык с энергичными и ленивыми вычисле- ниями.
4. Язык C++ - функциональный язык.
Введите номера правильных утверждений через пробел (в порядке возраста- ния).
Вопрос 76
Лисп. Пусть M  x. ((y. y y) x).
Различные цепочки редукций выражения M M могут привести только к четы- рем различным термам. Найдите в следующем списке терм, к которому мы не можем редуцировать M M :
1) M M;
2) x. M;
3) (x. x x) M;
4) M (x. x x);
5) (x. x x) (x. x x).
Введите номер терма.
Вопрос 77
Лисп. Пусть M  x. y. x y y. Различные цепочки редукций выражения
W W W могут привести только к трем различным термам. Найдите в следу- ющем списке терм, к которому мы не можем редуцировать W W W :
1) W W W;
2) (y. W y y)W;
3) (y. y y y) W;
4) (y. y y W) W.
Введите номер терма.
Вопрос 78
Лисп. Пусть IF  p. q. r. p q r, FALSE  x. y. y . Сколько шагов редукции требуется для преобразования IF FALSE A B к нормальной форме?
Введите число.

65
Вопрос 79
Лисп. Пусть IF  p. q. r. p q r, TRUE  x. y. x . Сколько шагов редукции требуется для преобразования IF TRUE A B к нормальной форме?
Введите число.
Вопрос 80
Лисп. Пусть FALSE  x. y. y , TRUE  x. y. x и OR  x. y. (x TRUE) y.
Сколько шагов редукции требуется для преобразования TRUE OR FALSE к нормальной форме?
Введите число.
Вопрос 81
Лисп. Пусть FALSE  x. y. y , TRUE  x. y. x и
AND  x. y. x y FALSE . Сколько шагов редукции требуется для преобра- зования TRUE AND FALSE к нормальной форме?
Введите число.
Вопрос 82
Лисп. Пусть CONS  h. t. s. s h t и REST  x. x FALSE. Сколько шагов редукции требуется для преобразования REST (CONS A B) к нормальной форме?
Введите число.
Вопрос 83
Лисп. Дано определение функции
(defun rol (f g)
(function (lambda x y)
(funcall f (funcall g x y) (funcall g y x)))))
Чему равно значение (funcall (rol '* '+) 2 3) ?
Вопрос 84
Лисп. Даны определения функций
(defun twice (f)
(function (lambda (x) (funcall f (funcall f x)))))
(defun do (x) (funcall (twice 'list) x))
Чему равно значение (do '0) ?

66
Вопрос 85
Лисп. Дано определения функций
(defun many (f x)
(mapcar #'(lambda (g) (funcall g x)) f)
(defun f1 (x) (+ x x))
(defun f2 (x) (* x x))
Чему равно значение (length (many '(f1 f2) 1)) ?
Вопрос 86
Лисп. Дано определение функции
(defun f (p s)
(cond ((null s) t)
((funcall p (car s)) (f p (cdr s)))
(t nil)))
Чему равно значение (f 'zerop '(0 0 0 0)) ?
Вопрос 87
Лисп. Дано определение функции
(defun f (p s)
(cond ((null s) nil)
((funcall p (car s)) t)
(t (f p (cdr s)))))
Чему равно значение (f 'zerop '(1 1 1)) ?
Вопрос 88
Лисп. Дано определение функции
(defun create (x y)
(eval (cons 'defun (cons x (cdr y)))))
Вызов этой функции приводит к определению некоторой новой функции f.
(create 'f '(lambda (x) (* x x)))
Чему равно значение (f 2)?
Вопрос 89
Лисп. Дано определение функции
(defun create (x y)
(eval (cons 'defun (cons x (cdr y)))))
Вызов этой функции приводит к определению некоторой новой функции f.
(create 'f '(lambda (x) (+ x x)))
Чему равно значение (f 5)?
Вопрос 90
Лисп. Дано определение функции

67
(defun create (x y)
(eval (cons 'defun (cons x (cdr y)))))
Вызов этой функции приводит к определению некоторой новой функции f.
(create 'f '(lambda (x) (+ x 1)))
Чему равно значение (f 2)?
Вопрос 91
Лисп. Запишите с помощью функций C…R последовательность вызовов CAR и CDR, выделяющих из приведенных ниже списков символ goal.
1) (1 2 goal 3 4)
2) ((1) (2 goal) (3 (4)))
3) ((1 (2 (3 4 goal))))
Введите последовательность ответов - имен функций через пробел (в порядке нумерации).
Вопрос 92
Лисп. Дано определение функции
(defun factor (n)
(if (< n 2 ) '(1) (append (factor (- n 1)) (list '* n))))
Чему равно значение (length (factor 3)) ?
Вопрос 93
Лисп. Дано определение функции
(defun mix (x y)
(if (null x) y (cons (car x) (mix y (cdr x)))))
Чему равно значение (length (mix '(1 2) '(a b))) ?
Вопрос 94
Лисп. Дано определение функции
(defun f (s)
(cond ((null s) nil)
((null (cdr s)) s)
(t (cons (car s) (f (cddr s))))))
Чему равно значение (length (f '(a b))) ?
Вопрос 95
Лисп. Дано определение функции
(defun f (x s)
(if (= x (car s)) 1 (+ 1 (f x (cdr s)))))
Чему равно значение (f 2 '(1 3 2)) ?

68
Вопрос 96
Лисп. Какая из функций, чье имя начинается с C, кончается R и содержит буквы A и D, (например CADDR) будет:
1) давать (3 4), когда применяется к (1 2 (3 4));
2) давать (3 4), когда применяется к (1 2 3 4);
3) давать (6 3), когда применяется к (((4 (6 3)) 8) 7);
4) давать 12, когда применяется к (5 ((12) 23 34));
5) давать (12), когда применяется к (5 ((12) 23 34))?
Введите последовательность функций через пробел (в порядке нумерации).
Вопрос 97
Лисп. Каково значение каждого из следующих выражений:
1) (atom (car (quote ((1 2) 3 4))));
2) (null (cddr (quote ((5 6) (7 8)))));
3) (equal (car (quote ((7)))) (cdr (quote (5 7))));
4) (zerop (cadddr (quote (3 2 1 0)))) ?
Введите последовательность значений через пробел (в порядке нумерации).
Вопрос 98
Лисп. Дано определение функции
(defun f(s)
(if (null s) nil (cons (car s) (f (f (cdr s))))))
Чему равно значение (f '(1 2 3)) ?
Вопрос 99
Лисп. Даны две функции
(defun g (x) (atom (car x))) и (defun f (s) (> (cadr s) (cadddr s))).
Чему равно значение (length (append (g '((1) 2)) (f '(1 2 3 4 5)))) ?
Вопрос 100
Лисп. Какое значение каждого из следующих выражений:
1) (eval (list (quote -) (+ 3 4)));
2) (eval (list (car (quote (atom x))) 6));
3) (eval (list (quote equal) (+ 2 2) (* 2 2))) ?
Введите последовательность значений через пробел (в порядке нумерации).
Вопрос 101
Лисп. Каково значение следующего выражения
(eval (cons (quote >) (cons 5 (list ((lambda (x y) (- x y)) 3 7))))) ?
Введите значение.