🗊Презентация Организация вычислений в Лиспе. Часть 2 Рекурсия. Функционалы

Лекция №5 Организация вычислений в Лиспе. Часть 2 Рекурсия. Функционалы.

Передача управления

Рекурсия Функция является рекурсивной, если в ее определении содержится вызов этой же функции. Рекурсия является простой, если вызов функции встречается в некоторой ветви лишь один раз. Простой рекурсии в процедурном программировании соответствует обыкновенный цикл. Например, задача нахождения значения факториала n! сводится к нахождению значения факториала (n-1)! и умножения найденного значения на n. Пример: нахождение значения факториала n!. > (defun factorial (n) (cond ((= n 0) 1) ;факториал 0! равен 1 (t (* (factorial (- n 1)) n)) ;факториал n! равен (n-1)!*n ) ) FACTORIAL

Отладка / трассировка Для отладки программы можно использовать возможности трассировки. Трассировка позволяет проследить процесс нахождения решения. Для того чтобы включить трассировку можно воспользоваться функцией trace. После ввода этой директивы интерпретатор будет распечатывать имя функции и значения аргументов каждого вызова трассируемой функции и полученный результат после окончания вычисления каждого вызова. Например, вызовем трассировку определенной выше функции: > (trace factorial) > (factorial 3) Entering: FACTORIAL, Argument list: (3) Entering: FACTORIAL, Argument list: (2) Entering: FACTORIAL, Argument list: (1) Entering: FACTORIAL, Argument list: (0) Exiting: FACTORIAL, Value: 1 Exiting: FACTORIAL, Value: 1 Exiting: FACTORIAL, Value: 2 Exiting: FACTORIAL, Value: 6 6 Для отключения трассировки можно воспользоваться функцией untrace: > (untrace factorial) NIL

Виды рекурсии Можно говорить о двух видах рекурсии: рекурсии по значению и рекурсии по аргументу. Рекурсия по значению определяется в случае, если рекурсивный вызов является выражением, определяющим результат функции. Рекурсия по аргументу существует в функции, возвращаемое значение которой формирует некоторая нерекурсивная функция, в качестве аргумента которой используется рекурсивный вызов. Приведенный выше пример рекурсивной функции вычисления факториала является примером рекурсии по аргументу, так как возвращаемый результат формирует функция умножения, в качестве аргумента которой используется рекурсивный вызов. … (t (* (factorial (- n 1)) n)) … Примером рекурсии по значению м.б. определение принадлежности элемента списку: > (defun member (el list) (cond ((null list) nil) ;список просмотрен до конца, элемент не найден ((equal el (car list)) t) ;очередная голова списка равна искомому, элемент найден (t (member el (cdr list))))) ;если элемент не найден, продолжить поиск в хвосте списка MEMBER > (member 2 '(1 2 3)) T > (member 22 '(1 2 3)) NIL

Примеры рекурсий… Реверс списка (рекурсия по аргументу): > (defun reverse (list) (cond ((null list) nil) ;реверс пустого списка дает пустой список (t (append (reverse (cdr list)) (cons (car list) nil))) ;соединить реверсированный хвост списка и голову списка ) ) REVERSE > (reverse '(one two three)) (THREE TWO ONE) > (reverse ()) NIL

Примеры рекурсий… Копирование списка (рекурсия по аргументу): > (defun copy_list (list) (cond ((null list) nil) ;копией пустого списка является пустой список (t (cons (car list) (copy_list (cdr list)))) ;копией непустого списка является список, полученный из головы и ;копии хвоста исходного списка ) ) COPY_LIST >(copy_list ‘(1 2 3)) (1 2 3) >(copy_list ()) NIL

Другие виды рекурсии… Рекурсию можно назвать простой, если в функции присутствует лишь один рекурсивный вызов. Такую рекурсию можно назвать еще рекурсией первого порядка. Но рекурсивный вызов может появляться в функции более, чем один раз. В таких случаях можно выделить следующие виды рекурсии: параллельная рекурсия – тело определения функции function_1 содержит вызов некоторой функции function_2, несколько аргументов которой являются рекурсивными вызовами функции function_1. (defun function_1 … (function_2 … (function_1 …) … (function_1 …) … ) … ) взаимная рекурсия – в теле определения функции function_1 вызывается некоторая функции function_2, которая, в свою очередь, содержит вызов функции function_1. (defun function_1 … (function_2 … ) … ) (defun function_2 … (function_1 … ) … ) рекурсия более высокого порядка – в теле определения функции аргументом рекурсивного вызова является рекурсивный вызов. (defun function_1 … (function_1 … (function_1 …) … ) …

Параллельная рекурсия Рассмотрим примеры параллельной рекурсии. В разделе, посвященном простой рекурсии, уже рассматривался пример копирования списка (функция copy_list), но эта функция не выполняет копирования элементов списка в случае, если они являются, в свою очередь также списками. Для записи функции, которая будет копировать список в глубину, придется воспользоваться параллельной рекурсией. > (defun full_copy_list (list) (cond ;копией пустого списка является пустой список ((null list) nil) ;копией элемента-атома является элемент-атом ((atom list) list) ;копией непустого списка является список, полученный из копии головы ;и копии хвоста исходного списка (t (cons (full_copy_list (car list)) (full_copy_list (cdr list)))))) FULL_COPY_LIST > (full_copy_list '(((1) 2) 3)) (((1) 2) 3) > (full_copy_list ()) NIL

Взаимная рекурсия Пример взаимной рекурсии – реверс списка. Так как рекурсия взаимная, в примере определены две функции: reverse и rearrange. Функция rearrange рекурсивна сама по себе. > (defun reverse (list) (cond ((atom list) list) (t (rearrange list nil))))) REVERSE > (defun rearrange (list result) (cond ((null list) result) (t (rearrange (cdr list) (cons (reverse (car list)) result))))) REARRANGE > (reverse '(((1 2 3) 4 5) 6 7)) (7 6 (5 4 (3 2 1)))

Функции более высокого порядка.

Применяющие функционалы Функции, которые позволяют вызывать другие функции и применять функциональный аргумент к другим его аргументам называют применяющими функционалами. применяющие функционалы: APPLY (APPLY fn список) FUNCALL (FUNCALL fn x1 x2 ... xn)

Примеры (APPLY ‘+ ‘(4 5 6)) => 15 (apply 'car '((1 2 3))) => 1 (apply 'list '(1 2 3)) => (1 2 3) (defun f (x) (cond ((null x) 'end) (t (print (apply (car x) '(2 3))) (f (cdr x))))) => F (f '(+ - * /)) => 5 => -1 => 6 => 2/3 => END

Примеры (FUNCALL ‘+ 4 5 6) => 15 (SETQ list ‘+) => + (FUNCALL list 1 2) => 3 (LIST 1 2) => (1 2)

Отображающие функционалы Отображающие или MAP-функционалы являются функциями, которые некоторым образом отображают список (последовательность) в новую последовательность или порождают побочный эффект, связанный с этой последовательностью. Каждая из них имеет более двух аргументов, значением первого должно быть имя определенной ранее или базовой функции, или лямбда-выражение, вызываемое MAP-функцией итерационно, а остальные аргументы служат для задания аргументов на каждой итерации. Количество аргументов в обращении к MAP-функции должно быть согласовано с предусмотренным количеством аргументов у аргумента-функции. В общем случае вызов MAP-функций имеет вид: (MAPx fn l1 l2 … ln), где l1 l2 … ln – списки; fn – функция от n аргументов.

Функция MAPCAR повторяет вычисление функции на элементах списка. Значение этой функции вычисляется путем применения функции fn к последовательным элементам xi списков, являющихся аргументами функции: Функция MAPCAR повторяет вычисление функции на элементах списка. Значение этой функции вычисляется путем применения функции fn к последовательным элементам xi списков, являющихся аргументами функции: (MAPCAR fn ‘(x11 x12 ... x1m) …‘(xn1 xn2 ... xnm)) В качестве значения функционала возвращается список, построенный из результатов вызовов функционального аргумента MAPCAR. Примеры. (mapcar '+ '(1 2 3) '(1 2 3)) => (2 4 6) (mapcar '+ '(1 2 3) '(1 2 3)'(1 2 3)) => (3 6 9) (defun f (x1 x2 x3) (list x1 x2 x3)) => F (mapcar 'f '(a b c) '(a b c)'(a b c)) => (A A A) (B B B) (C C C)) (setq x '(a b c)) => (A B C) (mapcar 'cons x '((1) (2) (3))) => ((A 1) (B 2) (C 3)) > (mapcar #'(lambda (x) (+ 5 x)) '(1 2 3 4 5)) (6 7 8 9 10)

MAPLIST действует подобно MAPCAR, но действия осуществляет не над элементами списка, а над последовательными CDR этого списка, начиная с исходного: MAPLIST действует подобно MAPCAR, но действия осуществляет не над элементами списка, а над последовательными CDR этого списка, начиная с исходного: (MAPLIST fn ‘(x11 x12 ... x1m) …‘(xn1 xn2 ... xnm)) Примеры. (maplist 'reverse '(1 2 3)) => ((3 2 1) (3 2) (3)) (maplist 'cons '(a b c) '(1 2 3)) => (((A B C) 1 2 3) ((B C) 2 3) ((C) 3)) Функционалы MAPCAR и MAPLIST используются для программирования циклов специального вида и в определении других функций, поскольку с их помощью можно сократить запись повторяющихся вычислений.

Функции MAPCAN и MAPCON являются аналогами функций MAPCAR и MAPLIST. Отличие состоит в том, что MAPCAN и MAPCON не строят, используя LIST, новый список из результатов, а объединяют списки, являющиеся результатами, в один список. Функции MAPCAN и MAPCON являются аналогами функций MAPCAR и MAPLIST. Отличие состоит в том, что MAPCAN и MAPCON не строят, используя LIST, новый список из результатов, а объединяют списки, являющиеся результатами, в один список. Функциональные аргументы функций MAPCAN и MAPCON должны возвращать в качестве значения списки. Примеры. (mapcan 'f '(a b c) '(a b c)'(a b c)) => (A A A B B B C C C) (mapcon 'reverse '(1 2 3)) => (3 2 1 3 2 3)

Функции MAPC и MAPL также являются аналогами функций MAPCAR и MAPLIST, но отличаются тем, что не собирают и не объединяют результаты. Результаты просто теряются, а в качестве значения возвращается значение первого аргумента функции. Функции MAPC и MAPL являются псевдофункционалами, т.е. их используют для получения побочного эффекта. Функции MAPC и MAPL также являются аналогами функций MAPCAR и MAPLIST, но отличаются тем, что не собирают и не объединяют результаты. Результаты просто теряются, а в качестве значения возвращается значение первого аргумента функции. Функции MAPC и MAPL являются псевдофункционалами, т.е. их используют для получения побочного эффекта. Примеры. (defun f (x1 x2) (set x1 x2)) => F (mapc 'f '(z1 z2 z3) '(1 2 3)) => (Z1 Z2 Z3) z2 => 2 (mapl 'print '(1 2 3)) => (1 2 3) => (2 3) => (3) (1 2 3) Вызовы функционалов можно объединять в более сложные структуры, так же, как и вызовы функций. Функционалы могут комбинироваться с использованием различных видов рекурсии.