Давайте считать суммы. Не ахти какое полезное занятие, но очень показательное.
Начнем с простой - сумма i для i=a..b

(define (sum-i a b)
    (if (> a b)
        0
        (+ a (sum-i (+ 1 a) b))))

Теперь посчитаем сумму квадратов
(define (sum-sq a b)
    (if (> a b)
        0
        (+ (square a) (sum-i (+ 1 a) b))))

Программы похожи - это сигнал, что что-то не так. Что же?
Напишем их в математической нотации: sigma ... 
В математической нотации есть идея суммирования, и "программы" используют ее, поэтому они понятны.
В наших программах идеи суммирования нет - вот в чем дело.
Давайте ее выразим.

(define (sum-of term a next b)
    (if (> a b)
        0
        (+ (term a) (sum-of term (next a) b))))

Не очень понятно, зачем next - но он пригодится, например, для вычисления pi/4 = 1/(3*5) + 1/(7*9) + ...

Перепишем теперь примеры:
(define (id a) a)
(define (add a)
    (lambda (x) (+ x a)))
(define (sum-i a b)
    (sum-of id a (add 1) b))
(define (sum-sq a b)
    (sum-of square a (add 1) b))
(define (pi-sum a b)
    (define (pi-term a)
        (/ 8 a (+ a 2)))
    (sum-of pi-term a (add 4) b))

Это уже выглядит понятнее - видно, что программа вычисляет сумму, и видно, сумму чего именно она вычисляет. Теперь sum-of выражает идею суммирования, а конкретные sum-i, sum-sq и т.п. используют эту идею.
Но можно сказать: программы и так были не очень-то сложными, можно "наметать глаз" и видеть и в них сразу их предназначение. Однако, во-первых, в случае более сложных программ такого уже не будет; во-вторых:

Наша реализация sum-of рекурсивна. Давайте сделаем ее итеративной:
(define (sum-of term a next b)
    (define (iter a s)
      (if (> a b)
          s
          (iter (next a) (+ s (term a)))))
    (iter a 0))

Магическим образом итеративными стали все остальные суммы.
Мы дали имя просочившемуся всюду духу рекурсивного суммирования, получили над ним власть и переколдовали его в итеративного.

Основная цель абстракции - контроль сложности; в частности, она делает программы более читаемыми.
Еще один характерный пример: если бы мы в речи не называли людей именами, а каждый раз при упоминании полностью, с нуля, описывали внешность, характер и т.п.

Можно сделать эту функцию еще более общей - например, добавить условие "фильтровать некоторые термы", обобщить условие останова...
В какой-то момент параметров станет много, а программы, использующие эту функцию, станут нечитаемыми. (If you have a procedure with 10 parameters, you probably missed some). А потом это превратится в полноценный интерпретатор :) и мы вернемся к тому, с чего начинали.
Когда же остановить обобщение?
- когда объем информации для задания нужных нам программ начинает опять становиться больше, чем их реальная сложность.



Рассмотрим теперь sqrt:
(define (sqrt-iter x)
    (define (good-enough? y) 
      (< (abs (- (square y) x)) 0.001))
    (define (improve y)
      (average y (/ x y)))
    (define (iter y)
      (if (good-enough? y)
          y
          (iter (improve y))))
    (iter 1.0))

Совершенно непонятно, что эта программа делает, с первого взгляда. Чтобы догадаться, что это предел последовательности, надо прочитать iter и распознать в нем хвосторекурсивную функцию; хорошо, хоть есть good-enough? и improve - они хорошо названы.
Чтобы догадаться, предел какой последовательности - надо залезть в реализацию improve.
Чтобы догадаться, когда останов - надо залезть в good-enough?.
И уж подавно ниоткуда не понятно, что эта последовательность сходится именно к тому что нам надо.
В более сложной программе пришлось бы лазать за несколько экранов вбок, и непонятно было бы вообще ничего.

Ну, давайте все-таки выясним, что же тут происходит:
    (define (iter y)
      (if (good-enough? y)
          y
          (iter (improve y))))
Ага, это неподвижная точка improve, и мы находим ее с помощью последовательного применения improve, пока результат не перестанет меняться.
Не у всех функций можно таким образом найти неподвижную точку, но у некоторых можно; типичный пример - cos: можно тыкать на калькуляторе cos, пока результат не сойдется.

Давайте выразим sqrt как неподвижную точку:
> (define (fixpoint f guess)
    (define (iter cur next)
      (if (close-enough? cur next)
          next
          (iter next (f next))))
    (define (close-enough? a b)
      (< (abs (- a b)) 0.0001))
    (iter guess (f guess)))

> (define (sqrt x)
    (define (improve y)
      (/ (+ y (/ x y)) 2))
    (fixpoint improve 1))

Теперь sqrt и fixpoint по отдельности стали куда яснее.
fixpoint упрощать дальше некуда, а в sqrt пока непонятно, почему именно такая формула.

Такая формула - потому, что если y = sqrt(x), то (y + x/y)/2 = y.
Однако почему бы не fix-point (\y . x/y)? Ведь x/(x/y) = y!
Эта функция осциллирует, ее неподвижную точку нельзя найти таким способом.
Осциллирующую функцию часто можно "погасить", если в качестве следующего x брать среднее x и f(x): сделаем "гасилку:

(define average-damp
    (lambda (f)
        (lambda (x)
            (average x (f x)))))

(define (sqrt x)
    (fixpoint (average-damp (lambda (y) (/ x y))) 1))

Стало еще понятнее, а функция average-damp наверняка еще пригодится.


Вспомним декларативное описание sqrt:
sqrt = {y : y^2 = x, y >= 0}
Это уравнение относительно y. Уравнения можно решать методом Ньютона:
f(x) = 0
x(n+1) = x(n) - f(x(n))/f'(x(n))

(define (sqrt x)
    (newton (lambda (y) (- x (square y))) 1))
Красота!

> (define (derive f)
    (lambda (x)
      (/ (- (f (+ x dx)) (f x))
         dx)))
> (define dx 0.0001)
> (define (newton f guess)
    (define df (derive f))
    (define (xform x)
      (- x (/ (f x) (df x))))
    (fixpoint (average-damp xform) guess))


Мы построили систему с помощью одной из самых важных техник - "слоистость":

sqrt
-------
newton
-------
derive, fixpoint, average-damp
-------
square, +, -, ...

И отделили задачу проектирования от задачи реализации с помощью "wishful thinking".
Сделаем теперь то же самое для данных.

==== Данные ====
Пример: рациональные.
Давайте сделаем арифметику над рациональными числами - с сложением и умножением.
Например, 1/2 + 1/4 = 3/4.
Однако у нас пока нет способа сказать "3/4", нет способа создать нечто, в чем есть и 3, и 4. Пока можем только по отдельности создать число 3 и число 4.
Давайте предположим, что такой способ все-таки есть, а каков он - потом разберемся. Это - wishful thinking:

(make-rat num den) - конструктор
(numer r) - селектор
(denom r) - селектор

Тогда (+rat) выражается как
(define (+rat a b)
    (make-rat (+ (* (numer a) (denom b)) (* (denom a) (numer b)))
              (* (denom a) (denom b))))
а *rat - как
(define (*rat a b)
    (make-rat (* (numer a) (numer b))
              (* (denom a) (denom b))))

Никаких проблем.

Но проблем вроде не было бы и если бы мы сделали (define (+rat-n na da nb db))  и аналогично (+rat-d) - подумаешь, 4 аргумента, 2 возвращаемых значения.

Однако плоды отсутствия абстракции не заставляют себя ждать.
Вычислим, например, (x+y)(x-2/1*y).
Код с отсутствием абстракции столь прекрасен, что "мы не будем его показывать" - там огромное количество временных переменных, их всех надо как-то назвать, не перепутать, и они друг с другом вообще никак не связаны; программа не имеет ничего общего с формулой, которую выражает. Чтобы изменить эту программу, надо в голове "перекомпилировать" эту формулу в низкоуровневый и неабстрагированный код для этой "библиотеки".

В общем, необходимость абстракции достаточно очевидна.

В принципе, реализация готова - осталось только определить make-rat, numer и denom.
В лиспе есть "клей" для данных - это пара, cons.
(cons x y) - это штуковина, содержащая в себе x и y.
(car p) - достает x из p.
(cdr p) - достает y из p.
(car (cons x y)) = x, (cdr (cons x y)) = y.

Названия странные - они пошли из древних времен, от лисп-машин: car - contents of address register, cdr - contents of decrement register, cons - construct.
Как они реализованы? Не важно; остановимся пока на этом барьере абстракции.

Довольно минималистично, но раз есть 2 - есть и сколько угодно. Например, можно запихнуть 3 значения:
(cons x (cons y z)) или (cons (cons x y) z)
В этом можно было бы запутаться, но всю эту сложность можно изолировать с помощью абстракции:

(define (make-triple a b c)
    (cons a (cons b c)))
(define (first t)
    (car t))
(define (second t)
    (cadr t))
(define (third t)
    (cddr t))

и дальше можно пользоваться make-triple,first,second, забыв о реализации.

Для cons'ов принята нотация "прямоугольников и стрелочек":

(cons x (cons y z)):

 ______   ______
 |.|  *-->|.| .|
 -|----   -|--|-
  |        |  |
  x        y  z

Итак, реализуем рациональные:
(define (make-rat n d) (cons n d))
(define (numer r) (car r))
(define (denom r) (cdr r))

Посчитаем 1/2 + 1/4:
> (+rat (make-rat 1 2) (make-rat 1 4)) 
(6 . 8)

6 . 8 - это лисповая нотация для пар.

Неправильно! Мы хотели 3/4. Дело, понятно, в том, что мы не сокращаем дробь.
Давайте сократим ее в make-rat:

(define (make-rat n d)
    (let ((g (gcd n d)))
        (cons (/ n g)
              (/ d g))))
Вуаля. Поменялась одна-единственная функция, все остальное заработало.

Это не единственный вариант, и даже не единственно верный.
Например, можно было бы сделать так:
(define (numer r)
    (/ (car r)
       (gcd (car r) (cdr r))))

В каких-то ситуациях это могло бы быть выгоднее - если мы редко интересуемся numer и denom, а в основном просто создаем числа.

Итак, у нас получилась такая слоистая система:


+rat,    *rat,    -rat   <--- Использование
----------------------
make-rat, numer, denom   <--- Барьер абстракции
---------------------- 
cons,     car,     cdr   <--- Реализация

Какой из этих вариантов на самом деле "верный" - "ведь мы-то знаем, что на самом деле внутри должны храниться сокращенный числитель и знаменатель".
Однако это зависит от того, чего мы хотим от нашего типа данных.
Разумно хотеть такой аксиомы: Если x = (make-rat n d), то (numer x)/(denom x) = n/d. Можно прибавить к этому аксиомы "(denom r) > 0" или "(gcd (numer r) (denom r)) = 1"; это зависит от задачи.
Еще важнее, что мы нигде, кроме реализации конструкторов и селекторов, не используем cons/car/cdr - и не знаем, как "по-настоящему" они устроены. Эти рациональные - вроде бы данные, но что это значит? Все что мы о них знаем - то, что они удовлетворяют каким-то аксиомам.

Хуже того, говорить "cons/car/cdr - вот, это данные" - тоже неправильно; про них мы ТОЖЕ знаем только то, что они удовлетворяют аксиомам.
Они вполне могли бы быть реализованы так:
(define (cons a b)
    (lambda (p) (p a b)))
(define (car x)
    (x (lambda (a b) a)))
(define (cdr x)
    (x (lambda (a b) b)))
    
Все состоит из воздуха, из процедур. Вообще нет необходимости делать понятие данных чем-то базовым, как в си! Нет такого математического понятия. Есть только системы аксиом.


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


Самое важное в cons'ах, как и в любом средстве абстракции - это то, что они обладают свойством замыкания, то есть, что cons - такой же полноправный объект, как любое другое значение; и может быть "участником" другого cons'а. 
Казалось бы, очевидно - однако, например, в фортране можно сделать массив целых, но нельзя сделать массив массивов.
Из средств абстракции, обладающих этим свойством, можно строить иерархические структуры; они могут уменьшить сложность программы (сложность, а не время работы) экспоненциально. Из средств, им не обладающим - иерархические структуры строить нельзя, и они могут уменьшить сложность разве что в константу раз - в лучшем случае получится свернуть один слой, например, объединить несколько логически связанных данных в структуру или массив, как в фортране.

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

* примечание: Отчасти это различие между Scheme и Си/Паскалем объясняется тем, что у Scheme типизация динамическая, а у си - статическая, поэтому компилятор си имеет все основания обругать нас при попытке написать функцию, работающую со списком любого типа - непонятно, как объявить тип этой функции.
Про функцию, осмысленно работающую с любой структурой, встает другой вопрос - что в этой функции можно вообще сделать, если ничего об этой структуре не известно? Формально эта проблема будет сформулирована в одной из ближайших лекций, о системах типов - изоморфизм Карри-Говарда; окажется, что такой нетривиальной функции не может быть вообще.
С++ решает эту проблему с помощью шаблонов, C# и Java с помощью Generics, Хаскелл - с помощью полиморфных типов - это все похожие вещи; о них также пойдет речь в лекции о системах типов.

==== Списки ====
Стандартный способ в лиспе "склеить" множество значений - такой:
(cons x (cons y (cons z (... (cons t null)))))
null - это значение, обозначающее "пустой список".
Это просто конвенция; вполне можно было бы делать и так - (cons (cons (cons ...(cons null t) ... z) y) x) - но тогда доступ за O(1) был бы не к первому, а к последнему элементу списка, и не к его хвосту, а к его "туловищу" - всему, кроме хвоста. В некоторых ситуациях может понадобиться и такое представление.

Можно было бы и (cons x ... (cons u t)), но так нарушается единообразие - теперь не все значения находятся в car, и сложнее написать всяческие функции для работы со списками - они должны будут иногда лезть в car, а иногда в cdr, к тому же - вот это уже showstopper - нельзя понять, где список заканчивается.

Есть встроенная функция list:
(cons 1 (cons 2 (cons 3 null))) = (list 1 2 3).
Интерпретатор напечатает это как (1 2 3), но задавать список так нельзя! Получится "применение 1 к аргументам 2, 3"

> (define first-primes (list 2 3 5 7))
> (car first-primes)
2
> (cdr first-primes)
(3 5 7)
> (cons 0 (cons 1 first-primes))
(0 1 2 3 5 7)
> (cons 0 (cons 1 (cdr (cdr first-primes))))
(0 1 5 7)

[стрелочные диаграммы для этого примера]

cons, car, cdr ничего не меняют! Они только возвращают либо свежесозданные объекты, либо куски уже существовавших. Поэтому несколько списков могут разделять между собой хвост, к примеру.

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

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

(упражнение: написать итеративный length и "как можно более итеративный" (count-leaves list))

Доступ по индексу (фиг знает, зачем он нужен - к спискам лучше не делать доступ по индексу, медленно)

(define (nth list n)
    (cond ((null? list) (error "Empty list"))
          ((= n 0) (car list))
          (else (nth (cdr list) (- n 1)))))

Конкатенация списков:

(define (append a b)
    (if (null? b)
        a
        (cons (car a)
              (append (cdr a) b))))

Переворот:

(define (reverse list)
    (if (null? list)
        null
        (append (reverse (cdr list))
                (list (car list)))))

Ужасно медленно!      

Супер-мега-важное упражнение: Сделать итеративный reverse - конечно, с другим алгоритмом. Потом сделать с его помощью итеративный append.


Менее привычные, но более полезные функции:
map - применяет функцию к каждому элементу списка

(define (map f list)
    (if (null? list)
        null
        (cons (f (car list)) (map f (cdr list)))))
Упражнение: сделать итеративно

Например:
> (map (lambda (x) (* x 2)) (list 1 2 3))
(2 4 6)
> (map (lambda (x) (- (length x) 1)) (list (list 1 2 3) (list 4 5 6 7) (list 3)))
(2 3 0)

Упражнение: (foreach print (list 1 2 3))

filter - фильтрует :)

(define (filter f list)
    (cond ((null? list) null)
          ((f (car list))
           (cons (car list) (filter f (cdr list))))
          (else
           (filter f (cdr list)))))

> (define (has x) 
     (lambda (list) 
        (not (null? (filter (lambda (y) (= y x)) list)))))
> (filter (has 5) (list (list 1 2 3) (list 4 5 6 7) (list 5) (list 2 8)))
((4 5 6 7) (5))


Все эти операции - это частные случаи левой и правой свертки (foldl/foldr, также известно как reduce - см. MapReduce):

(define (foldl f seed list)
    (define (iter r list)
        (if (null? list)
            r
            (iter (f r (car list)) (cdr list))))
    (iter seed list))

(define (foldr f seed list)
    (if (null? list)
        seed
        (f (car list) (foldr f seed (cdr list)))))

Сумму можно записать как (define (sum list) (foldl + 0 list))

foldl - итеративна, foldr - рекурсивна; они принципиально отличаются не только этим; для некоммутативных бинарных операций они будут давать разные результаты.
Кроме того, никто не говорит, что это бинарная операция над элементами одного "типа"; и они применяют операцию в разном порядке - у foldl первый аргумент имеет тип результата, а второй - элемента, у foldr наоборот.

В этом легко запутаться; распутаемся в лекции о системах типов.

Упражнение: вычислить
(foldl / 1 (list 1 2 3))
(foldr / 1 (list 1 2 3))
(foldl cons null (list 1 2 3))
(foldr cons null (list 1 2 3))

Упражнение: написать процедуры (all p list), (any p list), (max list), (min list).
Написать с помощью map+filter итп; потом написать с помощью foldl и foldr, потом без помощи и того и другого. Какой вариант эффективнее? Чем еще эти варианты отличаются? Постарайтесь найти как можно больше важных отличий.

Легко реализовать процедуру flatten, конкатенирующую список списков.
С помощью нее легко сделать flatmap:
> (flatmap (lambda (x) (list (+ x 1) (+ x 2)))
           (list 1 2 3 4))
(2 3 3 4 4 5 5 6)

И совсем просто сделать процедуру range: (range 1 5) --> (1 2 3 4 5)

Итак, в нашем распоряжении есть арсенал из map, filter, append, flatten, flatmap, all, any, has, и двух гигантов foldl и foldr.
Начнем собирать плоды.
Простота числа:
(define (prime? x)
    (all (lambda (y) (not (= 0 (modulo x y))))
         (range 2 (+ 1 (sqrt x)))))

Сумма квадратов простых чисел:
(map square
     (filter prime? (range 1 100))

Сумма квадратов простых чисел среди листьев какого-то дерева:
(map square
    (filter prime? (deep-flatten tree)))

Куча функций выражается таким образом; начинает получаться что-то похожее на SQL, но без оптимизатора запросов.

Еще похоже на конвейер, электрическую схему, обрабатывающую сигналы.
[картинки с черными ящиками и стрелками]



Еще немного о списках:
Мы пока не рассматривали примитивы для _изменения_ элементов пары; вообще, изменение чего-либо - очень непростой вопрос. Можно ли изменить 1? Можно ли изменить (cons 1 2)? Если есть два (cons 1 2) и изменить один из них - изменится ли второй? Оставим эти вопросы пока что; очень многие вещи прекрасно можно делать и без изменений.
В том числе и структуры данных.

Пример:
Простейшие очереди Окасаки:

   F             R
<--------   ------------<

Два списка - передний и задний.
Вытаскиваем элементы из переднего, а добавляем в задний.
Поддерживаем инвариант "Если передний пуст, то задний тоже".
Соответственно, когда передний опустошается - переворачиваем задний.

(define (make-queue)
  (cons null null))

(define (snoc x queue)
  (let ((f (car queue))
        (r (cdr queue)))
    (if (null? f)
        (cons (list x) null)
        (cons f (cons x r)))))

(define (qhead queue)
  (caar queue))

(define (qtail queue)
  (let ((f (car queue))
        (r (cdr queue))) 
    (cond ((null? f) (error "Empty queue"))
          ((null? (cdr f)) 
           (cons (reverse r) null))
          (else
           (cons (cdr f) r)))))

(define (empty? queue)
  (null? (car queue)))

(define (to-list queue)
  (if (empty? queue)
      null
      (cons (qhead queue)
            (to-list (qtail queue)))))

Операции работают в среднем за O(1); каждая операция здесь возвращает _новую_ очередь, т.е. старой можно пользоваться и она не изменится; не будет неявных изменений чего бы то ни было.


Упражнения:

ФВП:
1. Композиция функций, композиция списка функций, repeated, n-кратное сглаживание, поиск неподвижной точки для y -> x/y^(n-1).
2. (define sqrt (iterative-improve sqrt-good-enough? sqrt-improve)) - написать iterative-improve

Данные:
1. mobiles
2. интервальная арифметика
3. все функции над списками через accumulate

Все вместе:
1. Написать mergesort списка с конфигурируемой функцией сравнения на < >
2. Написать функцию (sort-on f), сортирующую по значению функции f: (define sort-on-length (sort-on length)), (sort-on-length list)
3. Написать функцию (compress-on f), которая удаляет в списке группы подряд идущих элементов, равных согласно f: (f a b).
3. Воспользовавшись compose (можно назвать ее "o" : ((o sin square) 2) = (sin 4)), и написав парочку других полезных функций, написать максимально просто и ясно выражение "отсортировать список списков по количеству уникальных, с точностью до знака, простых чисел среди элементов, увеличенных на 1.
(т.е.: в каждом списке - все увеличили на 1, оставили простые, оставили уникальные с точностью до знака; отсортировали большой список по длине полученного)