Декларативное программирование

[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]

© 2003 И.А. Дехтяренко

5.4. Структуры данных.

Лисп обеспечивает единое средство композиции данных. Любые два объекта можно объединить в структуру называемую парой при помощи примитивной функции cons (сокращение от construction). Эта функция получает два параметра и возвращает, составной объект данных, состоящий из этих параметров. Обычно пара, состоящая из объектов a и b, отображается как (a . b).

Функции car и cdr используются, чтобы получить составные части пары. Их имена унаследованы от первоначальной реализации Лиспа на IBM 704¹. Трудно сказать, почему эти названия сохранились. Возможно потому, что очень удобно давать имена функциям вида cadr, caddr и т.п.

(define (cadr x) (car (cdr x)))
(define (cddr x) (cdr (cdr x)))

Если же эти имена почему либо не нравятся, нетрудно определить новые.

(define first car)
(define second cdr)

С парами можно обращаться так же, как и с примитивными объектами данных. Им можно давать имена, их можно передавать в качестве аргументов. Что особенно важно, можно формировать пары, чьими элементами являются пары. Это свойство замкнутости операции cons даёт возможность простым и изящным способом создавать сколь угодно сложные структуры данных и описывать на них весьма общие операции.

(define (equal? a b)     ; два объекта равны
   (or (eq? a b)         ; если они - равные атомы
       (and (pair? a)    ; или они оба - пары
            (pair? b)    ; причем с равными
            (equal? (car a) (car b))   ; певрым и
            (equal? (cdr a) (cdr b))))); вторым
                                       ; элементами
(define (copy a)
   (if (pair? a)   ; копия пары - пара, составленная
       (cons (car (copy a)) ; из копии певрого и
             (cdr (copy a))); копии второго элемента
        a))        ; копия атома - сам этот атом

Списки

Одна из полезных структур, которые можно создавать с помощью пар - последовательность. Конечно, последовательности можно представлять в виде пар разными способами. Например, последовательность 1, 2, 3, 4 можно представить как

• ((1.2).(3.4))
• (((1.2).3).4)
• (1.(2.(3.4)))

Но одно представление имеет особенное значение. Последовательность может быть представлена как цепочка вложенных пар.

• (1.(2.(3.(4.nil)))

Первый элемент каждой пары представляет собой соответствующий элемент последовательности, а второй - следующая пара в цепочке. Второй элемент заключительной пары - специальное значение, представляющее пустую последовательность. Традиционно в Лиспе оно обозначается nil (сокращение от латинского nihil - ничто), но в Scheme обычно используется другое обозначение - (). Такая структура называется списком и отображается как последовательность элементов, заключенных в круглые скобки. Список можно создать вложенными применениями cons:

(cons 1 (cons 2 (cons 3 (cons 4 nil))))
(1 2 3 4)

но примитивная функция list, значительно упрощает дело.

(list 1 2 3 4)
(1 2 3 4)

(list)
()

Выражение (list a1…an) эквивалентно выражению (cons a1 (cons ... (cons an nil)…)).

Удобно интерпретировать car и cdr как функции, возвращающие соответственно «голову» (первый элемент) списка и его «хвост» (подсписок, состоящий из всех элементов кроме первого). Чтобы подчеркнуть такую интерпретацию мы можем определить.

(define head car)
(define tail cdr)
(head (list 1 2 3 4))
1
(tail (list 1 2 3 4))
(2 3 4)

Соответственно, (cons e x) возвращает список x с дополнительным элементом e в начале.

(cons 0 (list 1 2 3 4))
(0 1 2 3 4) 

Еще одно методически полезное определение, позволяющее отвлечься от особенностей представления пустого списка.

(define nil (list))

Вложенные применения car и cdr могут использоваться, чтобы извлечь второй, третий, и последующие элементы списка.

(car (cdr (list 1 2 3 4)))
2

Конечно, обрабатывая список, необходимо отделять случай пустого списка. Примитивный предикат null? проверяет, является ли его параметр пустым списком. О другом предикате pair? проверяющем, что его аргумент является парой, уже упоминалось. Полезно определить и противоположный ему.

(define (atom? x) (not (pair? x))

Обратите внимание на рекурсивную природу определения списка. Список представляет собой либо пустой список, либо пару, второй элемент которой является списком. Это позволяет нам написать процедуру, определяющую является ли данный объект списком.

(define (list? x)
   (or (null? x)
       (and (pair? x)
            (list? (cdr x)))))

Это же определение даёт нам ключ к созданию различных функций на списках. Например определим функцию length, возвращающую количество элементов в списке. Пустой список содержит 0 элементов, а любой другой - на 1 больше, чем его хвост.

(define (length x)
   (if (null? x)
       0
       (+ 1 (length (cdr x)))))

Аналогично определяется функция sum, вычисляющая сумму элементов списка. Если список пуст, она равна 0, иначе - сумме первого элемента и всех остальных.

(define (sum x)
   (if (null? x)
       0
       (+ (car x) (sum (cdr x)))))

Это напоминает нам об абстракции «накопления». Соответствующая абстракция для списков называется «приведение» (reduce) или «свертка» (fold).

(define (fold op e x)
   (if (null? x)
       e
       (op (car x) (fold op e (cdr x)))))

В терминах этой абстракции легко определяются разные полезные функции.

(define (sum x)  (fold + 0 x))
(define (prod x) (fold * 1 x))

(define (all x)  (fold and #t x))
(define (any x)  (fold or  #f x))

Однако вспомним, что мы определяли две процедуры: accr и accl. Одна из них выполняет операции справа налево, другая в противоположном направлении (на это и указывают суффиксы -r и -l ). Например, сумму чисел от 1 до n эти процедуры посчитают соответственно, как.

(…(0 + 1) + 2) … + n) и (1 + (2 … + (n + 0)…)

Результаты их совпадают, поскольку операция сложения ассоциативна и коммутативна. Но cons не обладает ни тем, ни другим свойством, поэтому:

(accr cons nil sqr 0 3)
(0 1 4 9)
(accl cons nil sqr 0 3)
((((() . 0) . 1) . 4) . 9)

Подобным образом можно определить две функции свертки правую (foldr) и левую (foldl). Первую из них мы уже определили, а вторую нетрудно определить по аналогии.

(define (foldl op e x)
   (if (null? x)
       e
       (foldl op (op e (car x)) (cdr x))))

Работа функции foldr становится нагляднее, если записать список в явном виде, а затем интерпретировать (foldr op e l) как замену все вхождений cons на op, а nil - на e.

(foldr * 1 (list 1 2 3))=
(foldr * 1 (cons 1 (cons 2 (cons 3 nil))))=
(* 1 (* 2 (* 3 1))))=
6

Ясно, что (foldr cons nil x) вернет копию списка x, а если вместо nil подставить другой список, то объединение списков.

(define (append x y)
    (foldr cons y x))

(append (list 1 2) (list 3 4))
(1 2 3 4)

Упражнение.

Дайте рекурсивное определение append.

Упражнение.

Определите функцию concat, получающую список, элементами которого являются списки и возвращающую список, состоящий из всех элементов этих списков. Например:

(concat (list (list 1 2 3) (list 3 2 1)))
(1 2 3 3 2 1)

Упражнение.

Функция reverse, возвращает список, состоящий из всех элементов аргумента в противоположном порядке. Дайте два определения этой функции: одно рекурсивное, другое - с использованием foldl.

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

(define (sqr-list x)
  (if (null? x)
      nil
      (cons (sqr (car x))
            (sqr-list (cdr x)))))

Мы можем выделить эту общую идею и выразить её как функцию высшего порядка. Эта функция получает в качестве параметров функцию одного аргумента и список, и возвращает список результатов, полученных применением функции к каждому элементу списка. Традиционно она называется отображением (map).

(define (map f x)
   (if (null? x)
       nil
       (cons (f (car x))
             (map f (cdr x)))))

(map abs (list -1 2 -3.5 10))
(1 2 3.5 10)

(map (lambda (x) (* x 2)) (list 1 2 3 4))
(2 4 6 8)

Теперь мы можем дать новое определение sqr-list в терминах map:

(define (sqr-list x)  (map sqr x))

Функции высшего порядка типа map или fold важны не только потому что фиксируют общие образцы, но и потому что устанавливают более высокий уровень абстракции в обработке списков. В первоначальном определении sqr-list, рекурсивная структура программы привлекает внимание, прежде всего к поэлементной обработке списка. Определение через map скрывает этот уровень подробностей и подчеркивает что что наша функция преобразует список элементов в список результатов. Различие между этими двумя определениями не в том, что компьютер выполняет различные процессы (на самом деле это один и тот же процесс), но в том что мы по-другому думаем об этом процессе. Например, сравните следующие определения функций с их более прямыми определениями.

(define (for-all p x)
   (all (map p x)))

(define (vector-len x)
   (sqrt(sum (map sqr x)))

(define (length x)
   (sum (map (lambda (t) 1) x) )

Не правда ли, оригинальный способ определить длину списка? Мы заменяем все элементы единицами и подсчитываем их сумму.

Ещё одна полезная операция - фильтрование последовательности, то есть выбор только тех элементов, которые удовлетворяют некоторому предикату.

(define (filter p x)
   (cond ((null? x) nil)
         ((p (car x)) (cons (car x) (filter p (cdr x))))
         (else (filter p (cdr x)))))

(filter odd? (list 1 2 3 4))
(1 3)
(sum (map sqr (filter odd? (list 1 2 3 4))))
10

Упражнение.

Дайте нерекурсивное определении функции filter, в терминах рассмотренных функций.

Списки помогают дать интерпретацию функциям произвольного числа агрументов, подобных примитивным функцям + и and. Если функция определена посредством (define (f . a) e) то при вызове (f a1…an) агрументы передаются в виде списка (a1…an). Например функцию list можно было бы определить следующим образом.

(define (list . x) x)

Деревья

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

Например, определим функцию count-leaves, возвращающую число листьев дерева. Для пустого дерева оно равно 0, для листа - 1. Наконец, если дерево представляет собой список ветвей, то число листьев в нём равно сумме числа листьев в первой ветви и числа листьев в остальных ветвях. Получаем

(define (count-leaves x)
   (cond ((null? x) 0)
         ((atom? x) 1)
         (else (+ (count-leaves (car x))
                  (count-leaves (cdr x))))))

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

(define (tree-fold op e t)
   (cond ((null? t) e)
         ((atom? t) t)
         (else (op (tree-fold op e (car t))
                   (tree-fold op e (cdr t))))))

Упражнение.

Функция fringe (другое общеупотребительное название flatten) является обобщением concat. Она получает как параметр дерево (представленное как список списков) и возвращает «крону» дерева, то есть список, содержащий все листья дерева. Например:

(fringe (list 1 (list 2 (list 3 4)) 5))
(1 2 3 4 5)

Запишите процедуру fringe.

Рекурсивная схема функции отображения дерева подобна уже рассмотренным:

(define (tree-map f t)
  (cond ((null? t) nil)
        ((atom? t) (f t))
        (else (cons (tree-map f (car t))
                    (tree-map f (cdr t))))))

Упражнение.

Многие операции на деревьях можно выполнять комбинируя операции на списках и рекурсию. Завершите следующее определение tree-map:

(define (tree-map f t) (map <???> t))

Пример: Символьное дифференцирование.

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

Кроме того, эта задача послужит примером «экспериментального» или «прототипного» программирования. Ведь не всегда программа создаётся как готовый продукт. Иногда программы пишутся для проверки каких-нибудь идей, для того, чтобы убедиться в их плодотворности или наоборот в бесперспективности. В таких случаях нет смысла тратить время на создание «полноценной» программы, которая всё равно будет выброшена. Главное - быстро написать работающий прототип с которым можно поэкспериментировать. Лисп очень хорошо подходит для такого рода задач. Вероятно, именно поэтому столь многие новшества пришли к нам из Лиспа.

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

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

(define (diff expr x)

   (define (dx t)
      (if (pair? t)
          (if (null?  (cddr t))
              (unary  (car t) (cadr t)))
              (binary (car t) (cadr t)(caddr t))))
          (if (eq? t x) 1 0)))

   (define (binary f u v)
      (cond
         ((eq? f '+) (list '+ (dx u) (dx v)))
         ((eq? f '-) (list '- (dx u) (dx v)))
         ((eq? f '*) (list '+
                           (list '* (dx u) v)
                           (list '* (dx v) u)))
         ((eq? f '/) (list '/
                           (list '-
                                 (list '* (dx u) v)
                                 (list '* (dx v) u))
                           (list 'expt v 2)))
         ((eq? f 'expt)(list '+
                             (list '*
                                   (dx u) v
                                   (list 'expt u (list '- v 1)))
                             (list '*
                                   (dx v)
                                   (list 'expt u)
                                   (list 'log u))))
         (else (error "неизвестная операция"))))

   (define (unary f u)
      (list '*
            (dx u)
            (cond ((eq? f 'exp) (list 'exp u))
                  ((eq? f 'log) (list '/ u))
                  ((eq? f 'sin) (list 'cos u))
                  ((eq? f 'cos) (list '- (list 'sin u)))
                  (else (error "неизвестная операция"))))

   (dx expr))

Наша программа способна найти производную любой элементарной функции, однако результаты выглядят довольно неожиданно. Давайте пробуем самый простой пример: найдём производную функции x² относительно x.

(diff '(expt x 2) 'x)
(+ (* 1 2 (expt x (- 2 1))) (* 0 (expt x) (log x)))

Вероятно, потребуется некоторое время, чтобы понять, что это выражение - действительно эквивалентно 2*x. Программа «не знает» что 2*1 = 2 , 2-1 = 1, 0*x = 0 и т.п. Фактически, она не может упростить выражение. В действительности, упрощение - главная проблема в компьютерной алгебре. Конечно, мы могли бы добавить в программу ряд правил упрощения выражений и добиться приемлемой формы ответов. Но для того, чтобы получать ответы в «самом простом» виде пришлось бы в корне пересмотреть наше представление данных.

Однако можно найти применение программе даже в таком виде. Интересно объединить символьное дифференцирование с численными вычислениями. То, что выражение не упрощено, в данном случае не столь существенно. Например, мы можем использовать её вместе с процедурой решения уравнений методом Ньютона. Для этого необходимо вычислять значения функций определяемых символьными выражениями. Можно было бы написать соответствующую процедуру и затем использовать её в программе решения уравнений. Но мы поступим хитрее и напишем процедуру, преобразующую символьное выражение в функцию. Для этого достаточно преобразовать выражение в лямбда-выражение и вычислить его значение.

(define (expr->fun var expr)
   (eval (list 'lambda (list var) expr)))

Теперь мы можем написать новую процедуру для метода Ньютона. Она имеет три аргумента: выражение, определяющее функцию, имя переменной и начальное приближение. Процедура дифференцирует выражение по переменной, преобразует это выражение и его производную в функции, а затем использует newton-method для решения уравнения.

(define (newton-method-smart expr var x)
   (newton-method (expr->fun var expr)
                  (expr->fun var (diff expr var))
                  x))

Например, можно вычислять квадратные корни весьма экстравагантным методом.

(define (sqrt a)
   (newton-method-smart (list '- a '(* x x)) 'x 1))

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

¹ Эта машина имела схему адресации, которая разрешала ссылаться на части «адреса» и «декремента» местоположения в памяти. CAR и CDR - сокращения «Contents of Address part of Register» и «Contents of Decrement part of Register» соответственно

[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]