Computer science посвящена не изучению языков программирования или алгоритмов, а изучению вычислительных процессов в целом. В этом курсе обсуждаются вычислительные процессы.
Описание вычислительного процесса - это how-to knowledge. Также существует declarative knowledge.
Пример: sqrt
declarative: sqrt = {y : y>=0, y^2=x}
how-to: sqrt = lim x(i); x(1)=1, x(n+1) = x(n)+y/x(n)


Однако трудности появляются не при вычислении sqrt, а при построении больших систем. Это возможно, лишь поскольку существуют техники контроля сложности.
В основном они связаны не со сложностями предметной области, а со сложностью композиции множества простых компонентов. В CS компоненты идеальны --> композиции могут быть гигантскими (в отличие от electrical engineering, например).

Техники контроля сложности делятся на 3 больших класса, и все они фактически являются частными случаями абстракции.

1. Абстракция "черного ящика"
sqrt = 36 --?--> 6
Ящики должны быть комбинируемы без знания о их содержимом.
В ящики должно быть можно пихать и знания более высокого порядка - "общие схемы вычислений"; sqrt - это fixed-point по y для x + y/x
План:
    Примитивы (примитивные процедуры и данные)
    Средства композиции
        Композиция процедур
        Композиция данных
    Средства абстракции
        Определение процедур
        Абстракция данных
    Выделение общих схем
        Функции высшего порядка
        Данные как процедуры

2. Интерфейсы
    Хочется, чтобы одни и те же операции могли работать над разными объектами. Например, арифметика - над числами, полиномами, комплексными, сигналами...
    Хочется, чтобы легко было добавлять новые типы объектов.

    Обобщенные операции
    ООП
    Потоки

3. Металингвистическая абстракция
    Лисп на лиспе
    Логическое программирование
===================
Лисп.

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

Лямбда
------
Изобретено Алонзо Черчем и Стивеном Клини совсем для другой цели - для борьбы с парадоксами теории множеств. Однако оно положило основу ФП и многого другого.
С его помощью было доказано несколько фундаментальных теорем - теорема Черча-Тьюринга (невозможно придумать алгоритм : (описание языка, логическое выражение на этом языке)=>(верно ли оно)), halting problem (невозможно придумать алгоритм : (описание языка, программа на нем)=>(остановится ли она))

Примеры:
    (\x . x+1)
    (\x y . x + y)
    (\x . (\y . y - x))
    (\f g . (\x . g(f(x))))

Основы лямбды:
    V - лямбда-выражение
    (\V . E) - лямбда-выражение
    (E E') - лямбда-выражение.
В чистой лямбде нет чисел, условий, структур данных и т.п. - все это можно выразить и так.

Вычисление лямбда-выражений:
Последовательность бета-редукций - т.е. "раскрытия" вызовов функций. ((\x . e) y) -> e[x := y]
Последовательности существуют разные.

Аппликативная: самый левый самый внутренний вызов (call-by-value)
Нормальная (ленивая): самый внешний вызов
Примеры: 
1. (\square . (\x . (+ x x)) 5) (\a . a*a)  -- тут лучше аппликативная
2. (\x y which . (if which==1 
                  then print x 
                  else print y))
     (+ 1 2) (/ 1 0) 1

Теорема Черча-Россера: Если есть нормальная форма, то она единственна и достижима нормальной стратегией.
Нормальной формы может и не быть: ((lambda (x) (x x)) (lambda (x) (x x)))

Лучшая стратегия - ленивая с мемоизацией.

Важное понятие - понятие "дна" (bottom, _|_, и другие менее благозвучные названия) и "строгости":
_|_ - означает "черт знает что; эксепшн, незавершающееся вычисление, и т.п.; результат любого вычисления над ним, кроме передачи в другое место - тоже _|_".
Функция называется строгой по аргументу x, если при всех значениях остальных аргументов и x=_|_, f(..) = _|_.

С аппликативным порядком все функции - строгие.
С ленивым - не все. Например, if:
if = (\cond then else . (cond then else))
true = (\then else . then)
false = (\then else . else)

(if (= 1 1) 5 (/ 1 0))

Заметим, что с ленивым порядком почти любую control structure можно записать как функцию.

----------
Ну так вот, лисп это лямбда, с некоторыми "практичными" добавлениями: примитивы - числа, строки, примитивные процедуры (арифметика, логика и т.п.); средства композиции - вызов процедур и условные операторы; средства абстракции - лямбда-абстракции.

Выражения: 3 5 (+ 3 5) (* (+ 1 2) 3) ...

(* (+ 1 2) 3) : * - операнд, (+ 1 2) и 3 - операнды, все вместе - комбинация.
Выражения имеют "деревянную" структуру.

(* 5 5)
(* 6 6)
(* 7 7)
-- Надо обобщить, выразить идею квадрата 
(define pi 3.14)
(define square (lambda(x) (* x x)))
Syntactic sugar: (define (square x) (* x x))

(define hypot 
    (lambda (x y) (+ (square x) (square y))))

Условия: 
(define (abs x)
    (cond ((= x 0) 0)
          ((> x 0) x)
          (else    (- x))))
(define (abs x)
    (if (< x 0) (- x) x)
Видно, что if - не аппликативен; cond - тоже.

(define (main) (print "Hello")) - первое выражение с side-эффектами.
Оно нарушает теорему Черча-Россера:
((lambda (x) (+ x x))  (print "Hello"))  - при ленивой и аппликативной стратегии разное на экране
((lambda (x) (- x x))  (read-number-from-keyboard)) - при ленивой и аппликативной стратегии это выражение имеет разные значения (нормальные формы).

----------
Первая программа: sqrt-iter

(define (sqrt-iter x)
    (iter x 1))
(define (iter x y)
    (if (good-enough? x y)
        y
        (iter x (improve x y))))
(define (good-enough? x y)
    (< (abs (- (square y) x)) 0.001))
(define (improve x y)
    (average y (/ x y)))
(define (average a b) 
    (/ (+ a b) 2))
(sqrt-iter 2)
1.4142156862745097

Плохо - 1. много лишних функций видно наружу, 2. x везде просочился
Внутренние define'ы:
(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))
(sqrt-iter 2)
1.4142156862745097

-----------
Рекурсия и итерация

Рассмотрим такой факториал:
int fac(int n) {
    int p = 1;
    while(n > 0) {
        p *= n;
        n--;
    }
    return p;
}

Он порождает процесс:
fac(3)
{p=1, n=3}
{p=3, n=2}
{p=6, n=1}
{p=6, n=0}
6

Рассмотрим такой факториал:
(define (fac n)
    (define (loop m p)
        (if (= m 0) 
            p
            (loop (1- m) (* m p)))) ; Рекурсия во всей красе
    (loop n 1))

Он порождает процесс:
(fac 3)     |
(loop 3 1)  |
(loop 2 3)  |
(loop 1 6)  |
(loop 0 6)  |
6           V

Где же рекурсия?

Теперь рассмотрим такой факториал:
(define (fac n)
    (if (= n 0)
        1
        (* n (fac (1- n)))))

Он порождает процесс:
(fac 3)                 \
(* 3 (fac 2))            \
(* 3 (* 2 (fac 1)))       \
(* 3 (* 2 (* 1 (fac 0))))  >
(* 3 (* 2 (* 1 1)))       /
(* 3 (* 2 1))            /
(* 3 2)                 /
6                      |/

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

Главное отличие между этими процессами: первый протекает с постоянной памятью, и его состояние полностью описывается локальными переменными (аргументами).
Второй протекает с непостоянной памятью, и помимо локальных переменных его состояние описывается "оставшимися" вычислениями.

**Первый из них называется итеративным, второй - рекурсивным.**

"бюрократическое" вычисление факториала:
Рекурсия: В департамент поступает распоряжение вычислить факториал n. Чиновник пишет бумагу "Повелеваю вычислить факториал n-1. Вернуть на согласование такому-то (себе)" и запоминает, что когда ему вернут на согласование - надо умножить на n и вернуть ответ. В каждый момент занята куча чиновников.
Итерация: Чиновник пишет на бумаге n, единицу и "Повелеваю домножить вот это (единицу) на все что осталось (на n)". Следующий пишет новую бумагу "Повелеваю домножить вот это (уже n*1) на все что осталось (n-1)". И т.п. В каждый момент занят только один чиновник.

Часто считается, что первый процесс просто применяет наглый хак - "хвостовую рекурсию" - "а мог бы и не применять, это зависит от компилятора".
Но дело-то не в компиляторе, а в сути процесса. Если процесс состоит в вычислении А при помощи формулы А = В, то применение этой формулы состоит в простой замене А на В:
(loop 3 1) = (loop 2 3) по формуле "(loop m p) = (loop (1- m) (* m p)) если m != 0"

Этот факт становится очевидным, а отсутствие "хвостовой рекурсии" - невообразимым, только если мы воспринимаем программы как математические уравнения, функции; почти декларативное знание -  "верно утверждение: (loop m p) это то же самое, что (loop (1- m) (* m p)), при условии m != 0"
Хвостовая рекурсия основывается на подстановочной модели.
В императивном программировании, целиком базирующемся на how-to knowledge, это далеко не очевидно; про подстановочную модель и то, что программы - тождества, там язык не поворачивается говорить. Можно сказать, нам еще _повезло_, что в императивных языках хвостовую рекурсию _тоже_ можно делать.

--------
Рекурсия может быть и нелинейной.

Пример - числа Фибоначчи.
(define (fib n)
    (if (< n 2) 
        n
        (+ (fib (- n 1)) (fib (- n 2)))))

Порождает древовидный процесс с линейной памятью и O(fib(n)) временем.
[Есть очевидный итеративный способ за O(n). Есть неочевидный итеративный способ за O(log n)]

Еще пример: возведение в степень.
(define (pow n k)
    (cond ((= 0 k) 1)
          ((= 0 (modulo k 2)) (square (pow n (/ k 2))))
          (else (* n (pow n (- k 1))))))
Рекурсия глубины O(log n), линейная; интересное и весьма поучительное упражнение - сделать итеративную версию.

Очень похожий пример: возведение в степень по модулю:
(define (expmod n k mod)
    (cond ((= 0 k) (modulo n mod))
          ((even? k) (modulo (square (expmod n (/ k 2) mod)) 
                             mod))
          (else (modulo (* n (expmod n (/ (- k 1) 2) mod)) mod))))
[Вопрос: почему бы не просто (modulo (pow n k) mod) ? В Scheme встроенная длинная арифметика! Hint: Сравните производительность при очень большом k. Почему так?]

Зачем нужно возводить в большую степень по модулю?
- Криптография (RSA)
- Проверка простоты