Сошников Дмитрий Валерьевич к.ф.-м.н., доцент Факультет инноваций и высоких технологий Московский физико-технический институт

2 Лекция 2 Абстракция и декомпозиция. Декларативное программирования

©2008 Сошников Д.В. 3 Описание решения сложной задачи с помощью множества простых шагов Основная проблема – борьба со сложностью Способы борьбы со сложностью: Декомпозиция («разделяй и властвуй») Абстракция («не обращай внимание на мелочи») Как это воплощено в современных языках: Структурное программирование, процедуры/функции Объектная ориентированность (наследование, полиморфизм)

©2008 Сошников Д.В. 4 Какие способы комбинирования функций доступны в традиционном программировании? function myexp(x:real):real; var s : real; i : integer; begin s:=0; for i:=0 to 10 do s:=s+taylor(x,i); end; function taylor(x : real, i:integer):real; begin taylor:=power(x,i)/fact(i); end; Вызов Композиция

©2008 Сошников Д.В. 5 Более богатые возможности композиции за счет рассмотрения «функций-как- данных» iter – функциональная абстракция, лежащая в основе вычисления myexp, pow, fact и др. iter – может быть получено как частный случай абстракции let iter f a b i = fold_left f i [a..b];; let rec iter f a b i = if a>b then i else f (iter f (a+1) b i) a;; let pow x n = iter (fun y i -> y*x) 1 n 1.0;; let fact n = iter (fun y i -> y*(float i)) 1 n 1.0;; let taylor x n = pow x n / fact n;; let myexp x = iter (fun y n -> y+taylor x n) ;; f(f(f(…f(i,b),b-1)),…,a+1),a)

©2008 Сошников Д.В. 6 При этом: Технология мемоизации и ленивых вычислений могут увеличить эффективность вычисления факториала и степени до линейной, за счет запоминания предыдущих результатов вычислений Функционально-декомпозированный (более простой для человека) алгоритм будет обладать такой же эффективностью, что и более сложный алгоритм вычисления суммы в одном цикле (домножение предыдущего слагаемого на фактор) iter fold_left MyExp Taylor PowFact

©2008 Сошников Д.В. 7 Сравните: function sum_even(L:List):integer; var s : integer; begin s:=0; foreach (var x in L) do if x mod 2 = 0 then s:=s+x; sum_even:=s; end; let sum_even L = sum(filter (fun x->x%2==0) L);;

©2008 Сошников Д.В. 8 Императивный подход На первый взгляд – большая эффективность по памяти (не создается копия списка), по времени (один проход по списку) Для определения суммы нечетных элементов придется переписывать функцию Функциональный подход Высокий уровень абстракции -> суммирование нечетных элементов получается автоматически Проще для программиста Пусть компилятор заботится об эффективности! Большая эффективность при параллельных вычислениях (возможность распараллеливания, поскольку sum и filter не имеют зависимостей по данным) При использовании ленивых вычислений – получаем однопроходный алгоритм, эквивалентный итерационному!

©2008 Сошников Д.В. 9 Мы описываем функции, работающие над данными – система программирования решает, как их вычислять! let rec fact = function 1 -> 1 | x -> x*fact(x-1);; var res = (from x in L where (x%2==0) select x^2).sum(); let sum_even L = sum(filter (fun x->x%2==0) L);;

©2008 Сошников Д.В. 10 void quickSort (int a[], int l, int r) { int i = l; int j = r; int x = a[(l + r) / 2]; do { while (a[i] < x) i++; while (x < a[j]) j--; if (i quicksort ([ for x in t when x quicksort ([ for x in t when x>h -> x]);;

©2008 Сошников Д.В. 11 Математика: double : N N Крестики-нолики: NextMove: boardState boardState Обработка текста: Translate: text text PastTense: text text Обработка изображений: ToBlackWhite: image image Mirror: image image Transform: (pixel pixel) x image image Компилятор: Compile: sourceCode byteCode Compile = Parse Transform Optimize

©2008 Сошников Д.В. 12 flipH flipV mirror invert stack glue,, Какие функции можно получить композицией? Какие свойства можно увидеть? right

©2008 Сошников Д.В. 13 mirror = flipH o flipV = flipV o flipH flipH o flipH = flipV o flipV = Id flipH = right o right flipH flipV mirror flipV flipH right