четверг, 14 апреля 2011 г.

Формулирование абстракций с помощью процедур высших порядков


Тут описана идея, важнейшая для любого программиста. Это то, как должен работать мозг у человека создающего такие вещи, как информационные структуры. Идеология приведена из книги "Структура и интерпретация компьютерных программ", Харольда Абельсона и Джеральда Джей Сассмана.
*-Нравится статья? Кликни по рекламе! :)

Функции, в сущности, являются абстракциями, которые описыва-
ют составные операции над числами безотносительно к конкретным числам. Например, когда мы определяем функцию:
def cube(b):
    return b**3
мы говорим не о кубе какого-то конкретного числа, а о способе получить куб любого числа. Часто одна и та же схема программы исполь-
зуется с различными процедурами. Для того чтобы выразить эти схемы как понятия, нам нужно строить процедуры, которые принимают другие процедуры как аргументы либо возвращают их как значения. Процедура, манипулирующая другими процедурами, называется процедурой высшего порядка (higher-order procedure).

Процедуры в качестве аргументов:
Часто за разными процедурами стоит одна общая схема. Большей частью они идентичны и различаются только именем процедуры, функцией, которая вычисляет терм, подлежащий добавлению, и функцией, вычисляющей следующее значение a. Все эти процедуры можно породить, заполнив дырки в одном шаблоне, например:
def <имя>(<терм>, a, <следующий>, b):
    if a>b:
        return 0
    else:
        return <терм>(a)+<имя>(<следующий>(a), b)
Присутствие такого общего шаблона является веским доводом в пользу того, что здесь скрыта полезная абстракция, которую только надо вытащить на поверхность. Действительно, математики давно выделили абстракцию суммирования последовательности (summation of a series) и изобрели «сигма-запись», например:

Сила сигма-записи состоит в том, что она позволяет математикам работать с самим понятием суммы, а не просто с конкретными суммами —
например, формулировать общие утверждения о суммах, независимые от конкретных суммируемых последовательностей.
Подобным образом, мы как проектировщики программ хотели бы, чтобы наш язык был достаточно мощным и позволял написать процедуру, которая выражала бы само понятие суммы, а не только процедуры, вычисляющие конкретные суммы. В нашем языке мы можем без труда это сделать, взяв приведенный выше шаблон и преобразовав «дырки» в формальные параметры. Воспользовавшись этим определением, мы можем вычислить сумму кубов чисел от 1 до 10:
def inc(n):
    return n+1
def sum(term, a, next, b):
    if(a>b):
        return 0
    else:
        return term(a)+sum(term, next(a), next, b)
print sum(cube, 1, inc, 10)
Вот такая вот идея.Этот пример, так же является ярким примером того, где очень помогают lambda функции(и зачем их вообще ввели). Ведь вместо передачи ф-ий в виде аргументов, можно просто вызывать их lambda аналоги, но в данном случае - это не важно, просто учтите этот факт на будущее.
Для того, чтобы показать основное достоинство абстракции, а именно - возможность быстрого создания новых реализаций, покажу как можно вычислить, приближенно, всем известное число Пи :)
Из математики известно следующее: сумму последовательности термов в ряде
очень медленно) сходится к Пи/8. Отсюда возникает следующая функция:
def piterm(a):
    return 1.0/(a*(a+2))
def piinc(a):
    return a+4;
print 8*sum(piterm, 1, piinc, 1000)
МММ...ну ладно, теперь, когда у нас есть sum, ее можно использовать в качестве строительного блока при формулировании других понятий. Например, определенный интеграл функции f
между пределами a и b можно численно оценить с помощью формулы:
для малых значений dx. Мы можем прямо выразить это в виде функции:
def integral(f, a, b, dx):
    def addDx(x):
        return x+dx
    return sum(f, a+dx/2, addDx, b)*dx
print integral(cube, 0, 1, 0.01)
Обратите внимание, что мы использовали блочную структуру, чтобы спрятать определения addDx, поскольку вряд ли эти функции понадобятся зачем-либо еще.
P.S. Точное значение интеграла cube от 0 до 1 равно 1/4.
Используемая литература:
  1. http://mitpress.mit.edu/sicp/