Мы уже познакомились с основами агентов и даже некоторыми деталями. Надеюсь, вы ощутили мощь этого механизма и возможные области его применения.
Фактически возможен следующий уровень гибкости. Прежде чем его освоить, следует рассмотреть математические идеи, лежащие в основе.
Эта замечательная теория разработана в 1930 году еще до появления компьютеров. Через 30 лет обнаружилось, что она дает ясную и прочную основу многих концепций языков программирования. Это оживило интерес к
Основная идея проста: нотация и правила трансформации позволяют нам обращаться с функциями так же, как и с другими математическим объектами.
Для заданных двух чисел a и b можно образовывать различные комбинации, например:
a + b или sin(a) + cos(b), используя функции с хорошо определенной сигнатурой.
sin: REAL → REAL - Смысл: Для любого аргумента типа REAL функция sin
- вырабатывает результат типа REAL
"+": [REAL х REAL] → REAL
- х декартово произведение, квадратные скобки
- применяются для группировки аргументов
Можно ли "играть" в подобные игры не с числами, а с функциями? Даже в элементарной операции мы встречаемся с операциями над функциями. Если f и g — это функции с подходящими сигнатурами, то можно задать их композицию, записываемую как g o f или f ; g (нотация, которую мы будем использовать, поскольку она явно указывает порядок выполнения). Результатом композиции является функция h(x ), такая, что h(x) = g(f (x)) для любого применимого аргумента x. Композиция является такой же операцией над функциями, как "+" над числами.
Мы можем продолжить восхождение по лестнице абстракций. Композиция функций является функцией, поэтому и к ней применима композиция. Пусть X, Y, Z — некоторые множества и заданы сигнатуры функций f и g:
f: X → Y g: Y → Z
Композиция этих функций, названная выше функцией h, имеет сигнатуру X → Z. Определим теперь композицию "; " как функцию, которой передаются два аргумента f и g и которая вырабатывает результат h. Эта функция имеет сигнатуру:
";":[[X → Y ] х [Y → Z ]] х [X → Z]
Мы можем продолжить определение функций, которые оперируют функциями, которые, в свою очередь, оперируют функциями, и так далее.
Прежде всего, нам необходима простая нотация для определения функций. Будем предполагать, что у нас есть базис
из функций, таких как "+", над целыми и вещественными. Это предположение делается для простоты, так как
square с сигнатурой
square : REAL → REAL
Функция в качестве результата возвращает квадрат числа. Ее определение можно задать соответствующим лямбда-выражением:
$$square \triangled \lambda x \colon REAL \mid x * x$$Правая часть определения является лямбда-выражением, запись которого однозначно позволяет установить, что для любого x типа REAL результатом функции будет x * x.
Символ λ (лямбда) - дело соглашения, но он дал имя всему подходу. В математической литературе сигнатуру
от определения функции отделяет символ точки, но в ОО-программировании точка играет другую важную роль, поэтому
вместо точки применяется символ " | " вертикальной черты.
Лямбда-определение функции напоминает ее определение в программировании
square (x: REAL): REAL - x в квадрате. do Result := x * x end
Как правило, математическая нотация всегда компактнее программистской. В этой нотации переменная, следующая за
λ, называется связанной переменной лямбда-выражения, она подобна формальному аргументу метода.
Подобно имени формального аргумента, имя связанной переменной не влияет на смысл выражения и может быть любым. Так что следующее определение задает ту же самую функцию, вычисляющую квадрат числа:
λ y: REAL | y * y
Это наблюдение будет формализовано ниже, используя понятие альфа-преобразования. Лямбда-выражение может иметь более одной связанной переменной, требуется лишь, чтобы у них были разные имена:
λ x, y: INTEGER | x + y — Функция сложения λ x: NATURAL, z : REAL | zx — Нотация для случая разных типов
Чем хорошо лямбда-выражение? На первый взгляд, вместо него можно было бы использовать уже знакомую запись, например, для функции square:
∀ x : REAL | square (x) = x * x
Разница в том, что [6.4] определяет свойства функции, в то время
как [6.2] определяет функцию — математический объект со всеми правами,
аналогично тому, как можно определить константу π, задав ее значение.
Одним из непосредственных преимуществ является возможность определения
Предполагается, что множества X, Y, Z известны. Так как они произвольны, мы можем ввести механизм универсальности в лямбда-выражение, как для классов, превращая имена множеств в формальные родовые параметры. В нашем кратком обзоре нет необходимости в такой нотации.
В этом примере исходное множество в сигнатуре является декартовым произведением [X → Y * [Y → Z] ; соответственно, лямбда-выражение имеет две связанные переменные — f и g.
До сих пор каждому определению функции лямбда-выражением предшествовало задание сигнатуры функции, а каждая связанная переменная сопровождалась указанием ее типа. В принципе, возможно нетипизированное лямбда-выражение, но мы будем продолжать использовать только типизированные, аналогично тому, как мы используем в программировании типизированные языки, такие как Eiffel, повышая читабельность и избегая ошибок.
Объявление сигнатуры
Объявление сигнатуры функции должно предшествовать определению функции лямбда-выражением.
Если сигнатура появляется непосредственно перед определением, то в определении можно опускать связанные переменные, как в этом примере:
$$";":[[X \to Y] * [Y \to Z]] * [X \to Z] \\";" \triangleq \lambda f,g \colon g (f (x)) \text { - Нет необходимости в объявлении f и g}$$В качестве примера функции высшего порядка, которую можно описать лямбда-выражением, рассмотрим карринг.
Карринг назван в честь американского математика Карри Брукса Хаскелла — одного из основателей теории, известной как комбинаторная логика, частью которой является
Квадратные и круглые скобки
В обычной математической нотации круглые скобки служат как для группирования, так и для записи функций. В примере
f(a * (b + с)) внутренние скобки используются для группирования, внешние - для записи функции. Это приводило бы к
непониманию при обсуждении операций над функциями. При обсуждении
[f ; g](a * [b + с])
означает применение композиции функций f и g к
аргументу, заданному выражением - произведением a и суммы b+с.
Часто приходится иметь дело с бинарными функциями, имеющими два аргумента, такими как композиция ";" " или сложение "+". Рассмотрим такую функцию:
f : [ X х Y ] → Z
для заданных X, Y, Z. Зная f, определим функцию f' с сигнатурой:
f' : X → [ Y → Z]
как
$$f' \triangleq \lambda x \colon X [\lambda y \colon Y \mid f (x,y)]$$Что это означает? В отличие от f функция f' принимает только один аргумент типа
X, а также в отличие от f не возвращает результат типа Z. Вместо этого она
для любого x в качестве результата возвращает функцию, заданную в [2.22]. Давайте назовем эту функцию
g. Эта функция от одного аргумента y типа Y возвращает результат типа
Z. Результат g(x) — тот же, что и f(x, y), как если бы сразу применили пару
аргументов к функции f.
Функцию f' называют карризованной версией функции f. Карринг двухаргументной функции означает преобразование ее в одноаргументную функцию, связанную с оригиналом соотношением [6.5]. Говорят также, что карринг означает специализацию функции по первому аргументу. Специализация, связывая первый аргумент, оставляет свободным только второй аргумент, что и преобразует функцию в одноаргументную.
Если функция add — сложение целых, определение которой можно задать лямбда-выражением
$$add \triangleq \lambda x,y:INTEGER \mid x+y$$, то
Так что add' (1) - λy: INTEGER | 1 + y — это функция " плюс 1", добавляющая 1 к заданному числу.
Соответствие между двухаргументной функцией f и ее карризованной версией f' взаимно однозначно. Неформально при проведении карринга никакая информация не теряется, так как эффект второго аргумента остается встроенным в аргумент результирующей функции f'.
Будет интересно — и послужит примером выразительной силы лямбда-нотации — явно установить соответствие между f и f ', рассматривая карринг как функцию X, Y, Z ее сигнатура:
curry: [[X х Y ] → Z ] → [X → [Y → Z ]]
Ее значение
$$curry \triangleq \lambda f:[X х Y ] \to Z \mid [\lambda x : X \mid [\lambda y:Y \mid f(x,y)]]$$Аналогично определите обратное соответствие, создающее f по функции f'.
Во всех примерах карринг применялся к двухаргументной функции по первому аргументу. Достаточно просто обобщить
концепцию: карринг можно применять к любой функции из n (n ≥ 1) аргументов для любого
выбора m аргументов (1 ≤ m ≤ n), задав значения для выбранного набора аргументов. Это превращает исходную функцию в функцию с n - m аргументами, представляя специализированную версию исходной функции, также известной как частичное вычисление. Если m = n, то получаем константную функцию.
Как пример того, что карринг представляет на практике, рассмотрим разницу между компиляцией и интерпретацией.
(рис 6.1) Интерпритация и компиляция
Интерпретатор с абстрактной точки зрения можно рассматривать как функцию с сигнатурой:
interpreter : Program х Input → Output
Здесь Program — множество всех корректных программ, Input и Output — множества возможных входов и выходов (это упрощенная, но достаточно корректная точка зрения на программы). Компилятор создает из исходной программы машинный код, который на компьютере уже без дополнительных усилий может быть выполнен на некотором входе:
Абстрактно работу компилятора можно рассматривать как функцию с сигнатурой:
compiler : Program → [Input → Output]
Когда у нас есть два механизма выполнения для одного и того же языка программирования, важно, чтобы они реализовали одну и ту же семантику.
Это основа работы в EiffelStudio, где постоянно приходится переключаться от полностью скомпилированной, полностью оптимизированной — финальной формы компиляции к быстрой возрастающей перекомпиляции — "технологии тающего льда", где главным образом применяется интерпретация. Конечно, при поставке конечного продукта выполняется финальная компиляция, но результаты работы совпадают с версией "тающего льда".
Требование согласованной работы компилятора и интерпретатора точно и элегантно выразимо с использованием карринга:
compiler = curry (interpreter)
ОО-стиль программирования отвечает духу карринга. ОО-вычисления инициируются вызовом:
x. f ( args)
Фиксирован объект — цель вызова, который и вызывает операцию. Для неквалифицированных вызовов — f(args) неявно заданной целью является объект Current и вызов можно записать в виде Current. f(args).
В ОО-программировании никогда не говорят "Примени эту операцию к тем объектам", что характерно для стиля, отличного от ОО, применяющего вызовы в форме f(x, argl, arg2, ...) со всеми операндами на равной ноге. ОО-программисты говорят "Этот объект применяет операцию, и, если нужны некоторые аргументы, то вот они".
Конечно, все, что выразимо в одном стиле, можно выразить и в другом. Но привычки ОО-стиля, влияющие на структуру программы, глубоки. Напомним только о двух важных понятиях — классе, играющем роль модуля и типа данных, и о наследовании.
Все это прячется в концепциях этого раздела. ОО-программирование является карринг-программированием.
В
α- и β- ).
Для определения этих понятий нам необходимо отличать два вида вхождений переменных в лямбда-выражение — связанные и свободные вхождения.
Как вы помните, мы говорили, что x, y, ... являются связанными
переменными в лямбда-выражении λx: X, y: Y...| e. Тогда нетрудно определить понятие связанного
вхождения. Вхождение переменной a в лямбда-выражение является связанным, если:
a — одна из связанных переменных;a в e.Понятие немедленно обобщается на выражение exp, не являющееся лямбда-выражением: вхождение является связанным в exp, если оно является связанным в одном из его лямбда-подвыражений. Например:
[f ; g](λ a : INTEGER | a + f (a, b))
Здесь вхождение a является связанным, но это не так для f, g и b в данном примере — это свободные вхождения. В следующем примере:
λ x: INTEGER | [λ y: INTEGER | x + y + z ]
вхождения x и y связаны, но вхождение z свободно. Неформально это означает, что x и y являются локальными переменными выражениями, в то время как переменная z должна быть определена вне выражения. Это в точности соответствует тому, что мы имеем в программировании:
f (x, y: INTEGER): INTEGER do Result := x + y + z end
Здесь x и y — формальные аргументы, которые означают удобные имена, используемые при определении функции; любые другие имена работали бы точно так же при условии отсутствия конфликта с другими именами. Переменная z имеет другой статус и должна быть определена в контексте. На практике она должна быть компонентом класса — запросом (атрибутом или функцией без аргументов).
Будем говорить, что x "входит связно" в выражение exp, если имеет по меньшей мере одно связанное вхождение в exp, и что "входит свободно", если имеет по меньшей мере одно свободное вхождение в exp, во втором случае x - свободная переменная в exp.
Другим базисным понятием является подстановка.
Пусть exp - выражение, x - переменная, а e - другое выражение. Тогда
exp [x:= e]
обозначает выражение, полученное из exp путем подстановки (замены) каждого свободного вхождения x на выражение e.
Например, если exp является:
λz:INTEGER | x + y + z*x
и e — это sin(x), то exp [x:= e] — это выражение λz: INTEGER
| sin(x) + y + z *sin(x)
Как показано в примере, выражение может содержать несколько вхождений переменной. Заметьте, подстановка
выполняется только для свободных вхождений. Если exp:
λx, z : INTEGER | x + y + z * x
Данное выражение отличается от предыдущего тем, что теперь x является связанной переменной. После аналогичной
подстановки exp [x:= e] выражение не изменится, поскольку нет свободных вхождений x. Если
exp:
λy : INTEGER | f (x, [λx: INTEGER | x + y])
то подстановка заменит только первое вхождение x, являющееся свободным, но не связанную переменную
x лямбда-выражения. Альфа-преобразование прояснит ситуацию.
Но начнем рассмотрения с бета-редукции — центрального правила, охватывающего суть лямбда-нотации. Бета-редукция
позволяет нам избавиться от связанной переменной (а следовательно, если нет других переменных, то и от λ )
преобразуя
[λ x : X | exp](e)
в
exp [ x := e]
Это справедливо при условии, что нет свободной переменной выраженияe, связно входящей в
exp. Это четко выражает понятие применения функции к фактическим аргументам, так как запись
λx:X| exp интуитивно означает, что exp рассматривается как функция с аргументом
x и что подстановка выражения e вместо x означает замену всех свободных вхождений
x. Вместо слов "бета-редукция трансформирует e в f" будем использовать
обозначение $$e \xrightarrow[\beta]{}f$$
В последнем примере связанная переменная фактически не используется в exp ; в этом случае можно рассматривать лямбда-выражение как константную функцию от x.
Как показывают второй и третий примеры, бета-редукция возможна и в том случае, когда e использует переменные, встречающиеся в exp, лишь бы они были не связанными. Даже третий пример не нарушает ограничение, поскольку в выражении exp (x + y) переменная x не связана — она связана в охватывающем лямбда-выражении, но не в exp. Ограничение имеет место, предотвращая бета-редукцию, только в случаях, подобных данному:
[λx:X| [λy:Y| x + y]] (y)
Здесь редукция приводила бы к выражению λy:Y|y+y, что некорректно, так как порождало бы новые вхождения связанной переменной, не соответствующие неформальному пониманию лямбда-выражения.
Значит ли это, что в подобных случаях бета-редукция невозможна по той причине, что нам не повезло с именем? Это было бы огорчительно, так как имена связанных переменных произвольны и их можно выбирать, не меняя общего смысла. Если мы заменим [6.6] на:
[λx:X| [λz:y|x + z]] (y)
то бета-редукция становится возможной, давая результат λz: Y| y+ z.
В программировании мы делаем то же самое, когда выбираем новое имя для формального аргумента метода, если оно конфликтует с именем атрибута класса.
Для узаконивания таких безвредных изменений связанных переменных нам необходимо второе правило — альфа-преобразование. Для заданной переменной y альфа-преобразование трансформирует лямбда-выражение
λx:X,...| exp
В котором у не имеет ни свободных, ни связанных вхождений в выражение
λy : X, ... | exp [x :=y]
Условие, налагаемое на y, защищает от замены x на y в обоих ниже приведенных случаях:
λx : X|x+y
λy : X | x + y]
При замене результирующее выражение λy: Y | y + y потеряло бы семантику, которая подразумевается в исходном выражении.
y, к которому добавлено значение, переданное функции в качестве аргумента. Для этой функции y — свободная переменная, определенная в контексте выражения (например, в охватывающем выражении). Если же в данном случае подстановка была бы допустимой, то полученное выражение задавало бы функцию, удваивающую значение переданного ей аргумента. Две функции полностью различны!y связано, но тогда альфа-преобразование сливало бы y со свободной переменной x.Последнее наблюдение показывает, что требование на y избыточно, так как в [6.8] предварительно y можно переименовать.
Альфа-преобразование и бета-редукция дают основу для полностью проработанной
Теорема гласит, что если из данного лямбда-выражения exp две различные последовательности трансформаций приводят к различным выражениям expl и exp2, то существуют две другие последовательности трансформаций, которые приводят оба эти выражения к единому выражению f. Это означает, что, если возможны некоторые трансформации для любого частного выражения, то не имеет значения, с какого преобразования начинать, поскольку в конечном итоге придем к одной и той же канонической форме.
(рис 6.2) Свойство Черча - Россера
Я надеюсь, что, прочитав о
Методы, как мы знаем из предыдущих лекций, представляли для нас структурные конструкции нашей программы, но они не участвовали в играх при выполнении программы, как это делают ссылки, базисные объекты, такие как целые, и более сложные объекты. Подобно математическим функциям в отсутствие каркаса, подобного
Аналогично тому, как
Даже в отсутствие механизма агентов методы являются формой лямбда-выражений, и вызов метода является формой
бета-редукции. Но эта редукция должна планироваться статически, через вызовы, такие как f(x, y) с явно
заданным методом f ОО-программирование вводит первый элемент динамизма благодаря динамическому
связыванию, разрешая f иметь несколько вариантов, выбор между которыми делается при каждом вызове
a.f(x, y) на основе типа объекта, присоединенного к а. Такой динамический механизм
позволяет нам представить ряд примеров в виде образца "много маленьких оберток" (с цитированными
ограничениями), но предлагаемый выбор ограничен множеством построенных вариантов. С агентами бета-редукция
становится полностью динамической операцией, вызов a.call([x, y]) не требует от нас какого-либо знания
о методе, который ассоциирован с агентом, за исключением знания сигнатуры.
Концепция
agent f(?, y) открытый аргумент будет задан во время вызова, закрытый аргумент обеспечивается при определении.Вы могли обратить внимание на то, что задание закрытых аргументов, по сути, означает выполнение карринга (в его общей форме — фиксация любых m из n аргументов). Рассмотрим различные динамические формы, которые можно получить из метода.
agent{C}.f — динамическая версия f в полной мере соответствующая сигнатуре оригинала.agent f(x, y) и agent t. f(x, y), где все операнды закрыты,
полностью соответствует карринг-версии, так что можно вызывать (если а агент) а.саll([])
без всяких аргументов. Это, кстати, напоминает нам разницу между математикой и программированием: математическая
функция при выполнении карринга по всем аргументам превращается в константу, в то же время успешные вызовы
а.саll([]) могут давать разные результаты, поскольку даже если а не изменяется, могут
изменяться окружающие объекты.agent a. f(?, x, y), подобный функции с каррингом на закрытых операндах.В одном отношении агенты, которые мы видели до сих пор, менее общие, чем лямбда-выражения. Чтобы использовать
agent а. f(?, x, y) или любой другой вариант, мы должны предположить, что функция f
построена. Такое предположение для лямбда-выражения λx...|exp означало бы ограничение
exp формой f(args). Теперь покажем, как для агентов можно снять это ограничение,
позволяя агентам иметь произвольную форму, как это происходит для exp в лямбда-выражении.
Изучение
Агенты, изучаемые до сих пор, связывались с существующими методами класса. Но иногда хочется иметь агента и не иметь метода
в классе. Представьте себе, что нужно выполнить с использованием агента некоторое простое вычисление. Кажется излишним во всех
случаях создавать в классе метод, который может и не отражать свойства класса. Метод может понадобиться только в одном месте, и
нет смысла перегружать им inline ) позволяют определить агент, не тревожа никакой класс.
Такая необходимость часто возникает при написании контрактов — всех видов предусловий, постусловий, инвариантов
класса. Например, инвариант класса может специфицировать, что все элементы некоторого массива целых являются
положительными. Мы уже знаем, как это установить, благодаря классу INTEGER_INTERVAL и оператору
|..|, рассматриваемому в параграфе "Агенты и итерации" этой лекции. Мы видели, как установить требуемое
условие, эквивалент выражения _s:a.lower..a.upper | a[i]>0 в исчислении предикатов:
(a.lower |..| a.upper). for_all (agent is_positive) [26]
Чтобы сделать это условие выполнимым, следует написать небольшую функцию для данного случая.
is_positive (n: INTEGER): BOOLEAN
- Больше ли n нуля?
do
Result := (n > 0)
ensure
definition: Result = (n > 0)
end
Немного досадно. Не так уж много времени требуется для написания кода. Никогда не жалейте потратить время на нажатие клавиш для получения релевантного результата. Но, представьте, эта функция нужна только для того, чтобы выразить данное свойство [6.9] в инварианте класса. Тогда вы загромоздите класс компонентом, который не представляет соответствующий абстракцию данных класса. Это становится особенно неприятно, если таких свойств много, как происходит, когда мы даем ясное и точное описание контрактов класса. Это правда, что эти компоненты не требуется экспортировать, но они в любом случае становятся частью класса. Было бы лучше выразить релевантные свойства точно в том месте, где возникает в них необходимость, но без видимости их вне этого контекста.
Манифестные агенты в полной мере отвечают поставленной задаче. Манифестный агент, как говорит его имя, задает объявление метода в стиле, подобном объявлению метода, но ничего более не требуется, никакие методы класса не появляются. Синтаксис непосредственно выводится из переписи нашего последнего примера. Мы, по сути, сливаем [6.10]в [6.9], получая в результате:
(a.lower \..\ a.upper). for_all
(agent (n: INTEGER): BOOLEAN [28]
- Больше ли n нуля?
do
Result := (n > 0)
ensure
definition: Result = ( n > 0)
end)
Начиная со второй строчки текст совпадает с [6.10], с тем исключением, что исчезает ненужное теперь имя метода (агент манифестный).
Манифестный агент характеризуется следующим свойством: он задает анонимный метод.
Синтаксис манифестного агента, как показано в примере, совпадает с синтаксисом объявления метода c заменой имени метода на ключевое слово agent. Разрешается включать все компоненты, применимые к методу, такие как предусловия и постусловия, вводить собственные локальные переменные, чьи имена должны отличаться от имен методов класса и локальных переменных охватывающих методов. Это не соответствует соглашению, принятому для лямбда-выражений, где внутреннее связывание сильнее внешнего, но помогает избежать недоразумений. В конце концов, имена не являются
Даже когда нет конфликта с именами локальных переменных охватывающих методов, эти переменные нельзя непосредственно использовать в агенте. Если такая редкая необходимость возникает, то следует применить передачу переменных через аргументы агента.
Манифестные агенты дополняют механизмы агентов, обеспечивая поддержку выразительности наших ОО-программ. В следующей лекции подробно рассмотрим главное приложение этого механизма, которое позволяет построить элегантное решение проблемы "наблюдения", кратко охарактеризованной в этой лекции.
В начале этой лекции обсуждались ситуации, которые требуют использования объектов, представляющих обертку вычислений. Агенты являются эффективным инструментом в подобных случаях.
Не все языки программирования, однако, обладают такие конструкциями. Фактически среди языков, применяемых в индустрии, только Eiffel, Smalltalk и C# имеют похожие средства (существенно отличаясь в деталях). Представляет интерес вкратце рассмотреть, какие же решения являются доступными в зависимости от языка, который, возможно, вы используете.
Применяются четыре основных подхода:
Язык C# вводит понятие делегатов, предназначенных для тех же целей, что и агенты.
Если не принимать во внимание дух и нотацию, можно сказать, что главная разница между делегатами C# и агентами Eiffel в том, что цель делегата не может быть открытой. Выражение agent {STOP}.close не имеет прямого эквивалента в C#. В приложении, посвященному языку C#, о делегатах говорится подробнее.
Язык Smalltalk вводит понятие блока (block) — сегмента кода, который может передаваться как объект. Заметьте, что Smalltalk является нетипизированным языком, поэтому здесь нет способа проверить во время компиляции, что передаваемый блок будет использоваться с подходящими аргументами, — любые несоответствия приводят к появлению ошибок в период выполнения.
Функциональные языки типично поддерживают возможность рассматривать функции как данные. Это пришло еще от языка Lisp, где выражение в форме
(defun f (x y) ("expression involving x and y"))
определяет f как функцию двух аргументов. Тогда можно использовать f как аргумент другой функции, например:
(curry f)
Сама функция
Термин "замыкание" часто используется в функциональных языках для обозначения выражений, которые могут передаваться как данные, даже если они могут нуждаться в доступе к глобальным переменным.
Некоторые языки программирования позволяют передавать методы как аргументы другим методам с примерно таким синтаксисом:
integral (f:function(x: REAL):REAL ; a, b: REAL): REAL
В этом случае методу integral, вычисляющему интеграл, можно передать в качестве фактического аргумента метод с соответствующей сигнатурой, вычисляющий подынтегральную функцию. Язык должен обеспечить подходящую нотацию для вызова соответствующего метода из кода метода, такого как integral.
В сравнении с агентами или замыканиями такое решение имеет ограничения.
Однако этот подход удовлетворяет многим основным потребностям, он успешно применяется в не ОО-языках, начиная с Фортрана и продолжаясь в Паскале и его последователях.
Компьютеры, как вы знаете, используют память для хранения не только объектов, но и программ. Во время выполнения у каждой конкретной программы свой конкретный адрес памяти, где она хранится. Это делает возможным передать управление коду по адресу его расположения: если есть способ для программы обозначить свой адрес и существует механизм, допускающий команду типа "выполнить метод по адресу addr, а затем вернуться и продолжить", то можно рассматривать адреса методов как данные, благодаря которым вызываются соответствующие методы. На машинном уровне эти приемы и обеспечивают нужные потребности.
Когда вы используете метод как аргумент другого метода, компилятор, фактически, будет передавать адрес метода.
Объект, представляющий агента, в одном из своих полей (недоступных клиенту по понятным причинам) будет хранить адрес ассоциированного метода.
Динамическое связывание, необходимое для образца "много маленьких оберток", предполагает способность вызывать метод по его адресу, который хранится в некоторой структуре данных, представляющей свойства типа. Таблица методов, которая описывалась в этой лекции при рассмотрении приемов реализации наследования, является примером такой структуры.
Все эти приемы важны для компилятора в процессе генерирования кода, а не для прикладного программиста, когда он пишет свою программу. Компилятор скрывает адреса методов под одним или несколькими слоями абстракции, позволяя программисту думать в терминах более высокого уровня — методах, объектах, агентах.
Языки С и С++ позволяют передавать имя функции (процедуры рассматриваются как функции, возвращающие значение void ) как фактический аргумент или присваивать его переменной. Тогда, если f является соответствующим формальным аргументом или переменной, можно вызвать функцию следующим образом:
(*f ) (args)
Когда объявляется формальный аргумент, представляющий функцию, можно специфицировать его сигнатуру, известную как прототип, так что фактический аргумент, не соответствующий сигнатуре, должен быть отвергнут во время компиляции. Однако не обязательно задавать сигнатуру. Можно обойтись без этого, потеряв возможность получения предупреждений во время компиляции. Принимая это и рассматривая имя функции как ее адрес, получаем ту же гибкость, что и при программировании на языке ассемблера, теряя преимущества статической проверки типов.
Если язык программирования не поддерживает ни одну из упомянутых техник, но является ОО-языком — с классами, наследованием, полиморфизмом и динамическим связыванием, — то можно использовать образец "много маленьких оберток", изученный в начале этой лекции.
Его главный недостаток — необходимость писать много маленьких классов, часто включающих только один метод.
Язык Java, не имеющий механизма, подобного агентам, и не позволяющий передавать методы в качестве аргументов, смягчает проблему, позволяя программисту объявлять класс, локальный по отношению к другому классу, что также известно как вложенный класс. Тогда можно использовать вложенный класс, как если бы он был компонентом охватывающего класса. Эта техника позволяет избежать создания глобального пространства имен программы (множества имен классов, непосредственно доступных другим программным компонентам), но проблемы остаются.
n аргументов называется специализация (задание значений) m
аргументов (1 ≤ m ≤ n). В результате карринга функция из n аргументов трансформируется в функцию из n — m аргументов.Agent Агент
Beta-reduction Бета редукция
Closed operand Закрытый операнд
Closure Замыкание
Inline agent Манифестный агент
Lambda expression Лямбда-выражение
Nested class Вложенный класс
Open operand Открытый операнд
Operand Операнд
Prototype (C, C++) Прототип (С, С++)
Alpha-conversion Альфа-преобразование
Church-Rosser property Свойство Черча - Россера
First-class citizen Граждане первого класса
Lambda calculus
Many Little Wrappers pattern Образец "много маленьких оберток"
One-Song-Artist class Класс "певец одной песни"
Partial evaluation
Substitution (of a) Подстановка
variable in an expression) (переменной в выражение)
Дайте определения терминам словаря.
Добавьте новые концепции в карту, построенную в предыдущих лекциях.
Смотри соответствующий раздел "Время программирования".
Спроектируйте механизм итерирования, не использующий агентов, но основанный на классе LINEAR_ITERATOR, описывающем объекты, которые допускают итерирование специальной операцией на линейных структурах, подобных списку.
(Это мазохистское упражнение просит вас нарушить все принципы методологии просто для того, чтобы поразмышлять о возникающем беспорядке)
Работая с потомками класса LINEAR, такими как LINEAR_LIST, используйте процедуру
do_all с агентом в качестве аргумента, представляющего метод, который, нарушая явное предписание,
заданное заголовочным комментарием, изменяет структуру. В результате do_all может закончиться неуспехом
или даст несогласованный результат. С помощью отладчика, если необходимо, проанализируйте точные обстоятельства,
ведущие к отказу.
Перепишите do_all итератор LINEAR так, чтобы он не применял манифестный кортеж как аргумент call, а использовал бы кортежную переменную t, которая заполнялась бы значениями перед каждым вызовом.Подсказка 1: вначале создайте объект-кортеж, затем присвойте значение.Подсказка 2: перечитайте разделы о свойствах кортежа, особенно тегах.
Рассмотрите существующее множество классов, например, подмножество классов Traffic. Предположим, что программист может написать операцию visit, имеющую вариант для каждого из классов. Эти версии принимают целевой объект как аргумент. Цель упражнения состоит в определении компонента apply, который применяет подходящую visit операцию к любому такому объекту, переданному как аргумент без знания специфического типа (компонент apply может объявить этот аргумент имеющим тип ANY ).
Не разрешается модифицировать ни один из существующих классов или их потомков. Образец "Посетитель" неприменим, так как вы не можете предполагать, что классы являются потомками класса VISITOR.
Покажите, что желаемую цель можно достичь, используя агенты. Подсказка: следуйте модели итераторных классов, определенных в этой лекции.
Решение, а не только подсказку, можно найти в статье, которая посвящена компонентизации VISITOR,
цитируемой при обсуждении проблемы.
Спроектируйте более выразительное доказательство Проблемы Остановки, которое не использует никаких файлов, каталогов или строк, представляющих тексты программ. Работайте с программными элементами, передаваемыми как агенты.
Отмечалось, что карринг является взаимно обратной функцией. Напишите сигнатуру и определение функции
uncurry, которой передается функция с одним аргументом f, чей результат — функция с одним
аргументом. Функция uncurry должна возвращать функцию с двумя аргументами f такую, что
f '= .
Покажите, что условие бета-редукции: [λx: X| exp](e) — "не должно быть свободных переменных
e, появляющихся связанными в exp", сильнее, чем это фактически требуется для сохранения
неформальной семантики редукции — применения функции к аргументам. Спроектируйте менее строгое, но все еще корректное условие.
Покажите, что условие альфа-преобразования: $$e \triangled \lambda x: X| exp$$ в
λ y: X| exp [x:= y] — "нет ни свободных, ни
связанных вхождений y в e", сильнее, чем это фактически требуется для сохранения неформальной
семантики редукции — применения функции к аргументам. Спроектируйте менее строгое, но все еще корректное условие.
Мы уже познакомились с основами агентов и даже некоторыми деталями. Надеюсь, вы ощутили мощь этого механизма и возможные области его применения.
Фактически возможен следующий уровень гибкости. Прежде чем его освоить, следует рассмотреть математические идеи, лежащие в основе.
Эта замечательная теория разработана в 1930 году еще до появления компьютеров. Через 30 лет обнаружилось, что она дает ясную и прочную основу многих концепций языков программирования. Это оживило интерес к
Основная идея проста: нотация и правила трансформации позволяют нам обращаться с функциями так же, как и с другими математическим объектами.
Для заданных двух чисел a и b можно образовывать различные комбинации, например:
a + b или sin(a) + cos(b), используя функции с хорошо определенной сигнатурой.
sin: REAL → REAL - Смысл: Для любого аргумента типа REAL функция sin
- вырабатывает результат типа REAL
"+": [REAL х REAL] → REAL
- х декартово произведение, квадратные скобки
- применяются для группировки аргументов
Можно ли "играть" в подобные игры не с числами, а с функциями? Даже в элементарной операции мы встречаемся с операциями над функциями. Если f и g — это функции с подходящими сигнатурами, то можно задать их композицию, записываемую как g o f или f ; g (нотация, которую мы будем использовать, поскольку она явно указывает порядок выполнения). Результатом композиции является функция h(x ), такая, что h(x) = g(f (x)) для любого применимого аргумента x. Композиция является такой же операцией над функциями, как "+" над числами.
Мы можем продолжить восхождение по лестнице абстракций. Композиция функций является функцией, поэтому и к ней применима композиция. Пусть X, Y, Z — некоторые множества и заданы сигнатуры функций f и g:
f: X → Y g: Y → Z
Композиция этих функций, названная выше функцией h, имеет сигнатуру X → Z. Определим теперь композицию "; " как функцию, которой передаются два аргумента f и g и которая вырабатывает результат h. Эта функция имеет сигнатуру:
";":[[X → Y ] х [Y → Z ]] х [X → Z]
Мы можем продолжить определение функций, которые оперируют функциями, которые, в свою очередь, оперируют функциями, и так далее.
Прежде всего, нам необходима простая нотация для определения функций. Будем предполагать, что у нас есть базис
из функций, таких как "+", над целыми и вещественными. Это предположение делается для простоты, так как
square с сигнатурой
square : REAL → REAL
Функция в качестве результата возвращает квадрат числа. Ее определение можно задать соответствующим лямбда-выражением:
$$square \triangled \lambda x \colon REAL \mid x * x$$Правая часть определения является лямбда-выражением, запись которого однозначно позволяет установить, что для любого x типа REAL результатом функции будет x * x.
Символ λ (лямбда) - дело соглашения, но он дал имя всему подходу. В математической литературе сигнатуру
от определения функции отделяет символ точки, но в ОО-программировании точка играет другую важную роль, поэтому
вместо точки применяется символ " | " вертикальной черты.
Лямбда-определение функции напоминает ее определение в программировании
square (x: REAL): REAL - x в квадрате. do Result := x * x end
Как правило, математическая нотация всегда компактнее программистской. В этой нотации переменная, следующая за
λ, называется связанной переменной лямбда-выражения, она подобна формальному аргументу метода.
Подобно имени формального аргумента, имя связанной переменной не влияет на смысл выражения и может быть любым. Так что следующее определение задает ту же самую функцию, вычисляющую квадрат числа:
λ y: REAL | y * y
Это наблюдение будет формализовано ниже, используя понятие альфа-преобразования. Лямбда-выражение может иметь более одной связанной переменной, требуется лишь, чтобы у них были разные имена:
λ x, y: INTEGER | x + y — Функция сложения λ x: NATURAL, z : REAL | zx — Нотация для случая разных типов
Чем хорошо лямбда-выражение? На первый взгляд, вместо него можно было бы использовать уже знакомую запись, например, для функции square:
∀ x : REAL | square (x) = x * x
Разница в том, что [6.4] определяет свойства функции, в то время
как [6.2] определяет функцию — математический объект со всеми правами,
аналогично тому, как можно определить константу π, задав ее значение.
Одним из непосредственных преимуществ является возможность определения
Предполагается, что множества X, Y, Z известны. Так как они произвольны, мы можем ввести механизм универсальности в лямбда-выражение, как для классов, превращая имена множеств в формальные родовые параметры. В нашем кратком обзоре нет необходимости в такой нотации.
В этом примере исходное множество в сигнатуре является декартовым произведением [X → Y * [Y → Z] ; соответственно, лямбда-выражение имеет две связанные переменные — f и g.
До сих пор каждому определению функции лямбда-выражением предшествовало задание сигнатуры функции, а каждая связанная переменная сопровождалась указанием ее типа. В принципе, возможно нетипизированное лямбда-выражение, но мы будем продолжать использовать только типизированные, аналогично тому, как мы используем в программировании типизированные языки, такие как Eiffel, повышая читабельность и избегая ошибок.
Объявление сигнатуры
Объявление сигнатуры функции должно предшествовать определению функции лямбда-выражением.
Если сигнатура появляется непосредственно перед определением, то в определении можно опускать связанные переменные, как в этом примере:
$$";":[[X \to Y] * [Y \to Z]] * [X \to Z] \\";" \triangleq \lambda f,g \colon g (f (x)) \text { - Нет необходимости в объявлении f и g}$$В качестве примера функции высшего порядка, которую можно описать лямбда-выражением, рассмотрим карринг.
Карринг назван в честь американского математика Карри Брукса Хаскелла — одного из основателей теории, известной как комбинаторная логика, частью которой является
Квадратные и круглые скобки
В обычной математической нотации круглые скобки служат как для группирования, так и для записи функций. В примере
f(a * (b + с)) внутренние скобки используются для группирования, внешние - для записи функции. Это приводило бы к
непониманию при обсуждении операций над функциями. При обсуждении
[f ; g](a * [b + с])
означает применение композиции функций f и g к
аргументу, заданному выражением - произведением a и суммы b+с.
Часто приходится иметь дело с бинарными функциями, имеющими два аргумента, такими как композиция ";" " или сложение "+". Рассмотрим такую функцию:
f : [ X х Y ] → Z
для заданных X, Y, Z. Зная f, определим функцию f' с сигнатурой:
f' : X → [ Y → Z]
как
$$f' \triangleq \lambda x \colon X [\lambda y \colon Y \mid f (x,y)]$$Что это означает? В отличие от f функция f' принимает только один аргумент типа
X, а также в отличие от f не возвращает результат типа Z. Вместо этого она
для любого x в качестве результата возвращает функцию, заданную в [2.22]. Давайте назовем эту функцию
g. Эта функция от одного аргумента y типа Y возвращает результат типа
Z. Результат g(x) — тот же, что и f(x, y), как если бы сразу применили пару
аргументов к функции f.
Функцию f' называют карризованной версией функции f. Карринг двухаргументной функции означает преобразование ее в одноаргументную функцию, связанную с оригиналом соотношением [6.5]. Говорят также, что карринг означает специализацию функции по первому аргументу. Специализация, связывая первый аргумент, оставляет свободным только второй аргумент, что и преобразует функцию в одноаргументную.
Если функция add — сложение целых, определение которой можно задать лямбда-выражением
$$add \triangleq \lambda x,y:INTEGER \mid x+y$$, то
Так что add' (1) - λy: INTEGER | 1 + y — это функция " плюс 1", добавляющая 1 к заданному числу.
Соответствие между двухаргументной функцией f и ее карризованной версией f' взаимно однозначно. Неформально при проведении карринга никакая информация не теряется, так как эффект второго аргумента остается встроенным в аргумент результирующей функции f'.
Будет интересно — и послужит примером выразительной силы лямбда-нотации — явно установить соответствие между f и f ', рассматривая карринг как функцию X, Y, Z ее сигнатура:
curry: [[X х Y ] → Z ] → [X → [Y → Z ]]
Ее значение
$$curry \triangleq \lambda f:[X х Y ] \to Z \mid [\lambda x : X \mid [\lambda y:Y \mid f(x,y)]]$$Аналогично определите обратное соответствие, создающее f по функции f'.
Во всех примерах карринг применялся к двухаргументной функции по первому аргументу. Достаточно просто обобщить
концепцию: карринг можно применять к любой функции из n (n ≥ 1) аргументов для любого
выбора m аргументов (1 ≤ m ≤ n), задав значения для выбранного набора аргументов. Это превращает исходную функцию в функцию с n - m аргументами, представляя специализированную версию исходной функции, также известной как частичное вычисление. Если m = n, то получаем константную функцию.
Как пример того, что карринг представляет на практике, рассмотрим разницу между компиляцией и интерпретацией.
(рис 6.1) Интерпритация и компиляция
Интерпретатор с абстрактной точки зрения можно рассматривать как функцию с сигнатурой:
interpreter : Program х Input → Output
Здесь Program — множество всех корректных программ, Input и Output — множества возможных входов и выходов (это упрощенная, но достаточно корректная точка зрения на программы). Компилятор создает из исходной программы машинный код, который на компьютере уже без дополнительных усилий может быть выполнен на некотором входе:
Абстрактно работу компилятора можно рассматривать как функцию с сигнатурой:
compiler : Program → [Input → Output]
Когда у нас есть два механизма выполнения для одного и того же языка программирования, важно, чтобы они реализовали одну и ту же семантику.
Это основа работы в EiffelStudio, где постоянно приходится переключаться от полностью скомпилированной, полностью оптимизированной — финальной формы компиляции к быстрой возрастающей перекомпиляции — "технологии тающего льда", где главным образом применяется интерпретация. Конечно, при поставке конечного продукта выполняется финальная компиляция, но результаты работы совпадают с версией "тающего льда".
Требование согласованной работы компилятора и интерпретатора точно и элегантно выразимо с использованием карринга:
compiler = curry (interpreter)
ОО-стиль программирования отвечает духу карринга. ОО-вычисления инициируются вызовом:
x. f ( args)
Фиксирован объект — цель вызова, который и вызывает операцию. Для неквалифицированных вызовов — f(args) неявно заданной целью является объект Current и вызов можно записать в виде Current. f(args).
В ОО-программировании никогда не говорят "Примени эту операцию к тем объектам", что характерно для стиля, отличного от ОО, применяющего вызовы в форме f(x, argl, arg2, ...) со всеми операндами на равной ноге. ОО-программисты говорят "Этот объект применяет операцию, и, если нужны некоторые аргументы, то вот они".
Конечно, все, что выразимо в одном стиле, можно выразить и в другом. Но привычки ОО-стиля, влияющие на структуру программы, глубоки. Напомним только о двух важных понятиях — классе, играющем роль модуля и типа данных, и о наследовании.
Все это прячется в концепциях этого раздела. ОО-программирование является карринг-программированием.
В
α- и β- ).
Для определения этих понятий нам необходимо отличать два вида вхождений переменных в лямбда-выражение — связанные и свободные вхождения.
Как вы помните, мы говорили, что x, y, ... являются связанными
переменными в лямбда-выражении λx: X, y: Y...| e. Тогда нетрудно определить понятие связанного
вхождения. Вхождение переменной a в лямбда-выражение является связанным, если:
a — одна из связанных переменных;a в e.Понятие немедленно обобщается на выражение exp, не являющееся лямбда-выражением: вхождение является связанным в exp, если оно является связанным в одном из его лямбда-подвыражений. Например:
[f ; g](λ a : INTEGER | a + f (a, b))
Здесь вхождение a является связанным, но это не так для f, g и b в данном примере — это свободные вхождения. В следующем примере:
λ x: INTEGER | [λ y: INTEGER | x + y + z ]
вхождения x и y связаны, но вхождение z свободно. Неформально это означает, что x и y являются локальными переменными выражениями, в то время как переменная z должна быть определена вне выражения. Это в точности соответствует тому, что мы имеем в программировании:
f (x, y: INTEGER): INTEGER do Result := x + y + z end
Здесь x и y — формальные аргументы, которые означают удобные имена, используемые при определении функции; любые другие имена работали бы точно так же при условии отсутствия конфликта с другими именами. Переменная z имеет другой статус и должна быть определена в контексте. На практике она должна быть компонентом класса — запросом (атрибутом или функцией без аргументов).
Будем говорить, что x "входит связно" в выражение exp, если имеет по меньшей мере одно связанное вхождение в exp, и что "входит свободно", если имеет по меньшей мере одно свободное вхождение в exp, во втором случае x - свободная переменная в exp.
Другим базисным понятием является подстановка.
Пусть exp - выражение, x - переменная, а e - другое выражение. Тогда
exp [x:= e]
обозначает выражение, полученное из exp путем подстановки (замены) каждого свободного вхождения x на выражение e.
Например, если exp является:
λz:INTEGER | x + y + z*x
и e — это sin(x), то exp [x:= e] — это выражение λz: INTEGER
| sin(x) + y + z *sin(x)
Как показано в примере, выражение может содержать несколько вхождений переменной. Заметьте, подстановка
выполняется только для свободных вхождений. Если exp:
λx, z : INTEGER | x + y + z * x
Данное выражение отличается от предыдущего тем, что теперь x является связанной переменной. После аналогичной
подстановки exp [x:= e] выражение не изменится, поскольку нет свободных вхождений x. Если
exp:
λy : INTEGER | f (x, [λx: INTEGER | x + y])
то подстановка заменит только первое вхождение x, являющееся свободным, но не связанную переменную
x лямбда-выражения. Альфа-преобразование прояснит ситуацию.
Но начнем рассмотрения с бета-редукции — центрального правила, охватывающего суть лямбда-нотации. Бета-редукция
позволяет нам избавиться от связанной переменной (а следовательно, если нет других переменных, то и от λ )
преобразуя
[λ x : X | exp](e)
в
exp [ x := e]
Это справедливо при условии, что нет свободной переменной выраженияe, связно входящей в
exp. Это четко выражает понятие применения функции к фактическим аргументам, так как запись
λx:X| exp интуитивно означает, что exp рассматривается как функция с аргументом
x и что подстановка выражения e вместо x означает замену всех свободных вхождений
x. Вместо слов "бета-редукция трансформирует e в f" будем использовать
обозначение $$e \xrightarrow[\beta]{}f$$
В последнем примере связанная переменная фактически не используется в exp ; в этом случае можно рассматривать лямбда-выражение как константную функцию от x.
Как показывают второй и третий примеры, бета-редукция возможна и в том случае, когда e использует переменные, встречающиеся в exp, лишь бы они были не связанными. Даже третий пример не нарушает ограничение, поскольку в выражении exp (x + y) переменная x не связана — она связана в охватывающем лямбда-выражении, но не в exp. Ограничение имеет место, предотвращая бета-редукцию, только в случаях, подобных данному:
[λx:X| [λy:Y| x + y]] (y)
Здесь редукция приводила бы к выражению λy:Y|y+y, что некорректно, так как порождало бы новые вхождения связанной переменной, не соответствующие неформальному пониманию лямбда-выражения.
Значит ли это, что в подобных случаях бета-редукция невозможна по той причине, что нам не повезло с именем? Это было бы огорчительно, так как имена связанных переменных произвольны и их можно выбирать, не меняя общего смысла. Если мы заменим [6.6] на:
[λx:X| [λz:y|x + z]] (y)
то бета-редукция становится возможной, давая результат λz: Y| y+ z.
В программировании мы делаем то же самое, когда выбираем новое имя для формального аргумента метода, если оно конфликтует с именем атрибута класса.
Для узаконивания таких безвредных изменений связанных переменных нам необходимо второе правило — альфа-преобразование. Для заданной переменной y альфа-преобразование трансформирует лямбда-выражение
λx:X,...| exp
В котором у не имеет ни свободных, ни связанных вхождений в выражение
λy : X, ... | exp [x :=y]
Условие, налагаемое на y, защищает от замены x на y в обоих ниже приведенных случаях:
λx : X|x+y
λy : X | x + y]
При замене результирующее выражение λy: Y | y + y потеряло бы семантику, которая подразумевается в исходном выражении.
y, к которому добавлено значение, переданное функции в качестве аргумента. Для этой функции y — свободная переменная, определенная в контексте выражения (например, в охватывающем выражении). Если же в данном случае подстановка была бы допустимой, то полученное выражение задавало бы функцию, удваивающую значение переданного ей аргумента. Две функции полностью различны!y связано, но тогда альфа-преобразование сливало бы y со свободной переменной x.Последнее наблюдение показывает, что требование на y избыточно, так как в [6.8] предварительно y можно переименовать.
Альфа-преобразование и бета-редукция дают основу для полностью проработанной
Теорема гласит, что если из данного лямбда-выражения exp две различные последовательности трансформаций приводят к различным выражениям expl и exp2, то существуют две другие последовательности трансформаций, которые приводят оба эти выражения к единому выражению f. Это означает, что, если возможны некоторые трансформации для любого частного выражения, то не имеет значения, с какого преобразования начинать, поскольку в конечном итоге придем к одной и той же канонической форме.
(рис 6.2) Свойство Черча - Россера
Я надеюсь, что, прочитав о
Методы, как мы знаем из предыдущих лекций, представляли для нас структурные конструкции нашей программы, но они не участвовали в играх при выполнении программы, как это делают ссылки, базисные объекты, такие как целые, и более сложные объекты. Подобно математическим функциям в отсутствие каркаса, подобного
Аналогично тому, как
Даже в отсутствие механизма агентов методы являются формой лямбда-выражений, и вызов метода является формой
бета-редукции. Но эта редукция должна планироваться статически, через вызовы, такие как f(x, y) с явно
заданным методом f ОО-программирование вводит первый элемент динамизма благодаря динамическому
связыванию, разрешая f иметь несколько вариантов, выбор между которыми делается при каждом вызове
a.f(x, y) на основе типа объекта, присоединенного к а. Такой динамический механизм
позволяет нам представить ряд примеров в виде образца "много маленьких оберток" (с цитированными
ограничениями), но предлагаемый выбор ограничен множеством построенных вариантов. С агентами бета-редукция
становится полностью динамической операцией, вызов a.call([x, y]) не требует от нас какого-либо знания
о методе, который ассоциирован с агентом, за исключением знания сигнатуры.
Концепция
agent f(?, y) открытый аргумент будет задан во время вызова, закрытый аргумент обеспечивается при определении.Вы могли обратить внимание на то, что задание закрытых аргументов, по сути, означает выполнение карринга (в его общей форме — фиксация любых m из n аргументов). Рассмотрим различные динамические формы, которые можно получить из метода.
agent{C}.f — динамическая версия f в полной мере соответствующая сигнатуре оригинала.agent f(x, y) и agent t. f(x, y), где все операнды закрыты,
полностью соответствует карринг-версии, так что можно вызывать (если а агент) а.саll([])
без всяких аргументов. Это, кстати, напоминает нам разницу между математикой и программированием: математическая
функция при выполнении карринга по всем аргументам превращается в константу, в то же время успешные вызовы
а.саll([]) могут давать разные результаты, поскольку даже если а не изменяется, могут
изменяться окружающие объекты.agent a. f(?, x, y), подобный функции с каррингом на закрытых операндах.В одном отношении агенты, которые мы видели до сих пор, менее общие, чем лямбда-выражения. Чтобы использовать
agent а. f(?, x, y) или любой другой вариант, мы должны предположить, что функция f
построена. Такое предположение для лямбда-выражения λx...|exp означало бы ограничение
exp формой f(args). Теперь покажем, как для агентов можно снять это ограничение,
позволяя агентам иметь произвольную форму, как это происходит для exp в лямбда-выражении.
Изучение
Агенты, изучаемые до сих пор, связывались с существующими методами класса. Но иногда хочется иметь агента и не иметь метода
в классе. Представьте себе, что нужно выполнить с использованием агента некоторое простое вычисление. Кажется излишним во всех
случаях создавать в классе метод, который может и не отражать свойства класса. Метод может понадобиться только в одном месте, и
нет смысла перегружать им inline ) позволяют определить агент, не тревожа никакой класс.
Такая необходимость часто возникает при написании контрактов — всех видов предусловий, постусловий, инвариантов
класса. Например, инвариант класса может специфицировать, что все элементы некоторого массива целых являются
положительными. Мы уже знаем, как это установить, благодаря классу INTEGER_INTERVAL и оператору
|..|, рассматриваемому в параграфе "Агенты и итерации" этой лекции. Мы видели, как установить требуемое
условие, эквивалент выражения _s:a.lower..a.upper | a[i]>0 в исчислении предикатов:
(a.lower |..| a.upper). for_all (agent is_positive) [26]
Чтобы сделать это условие выполнимым, следует написать небольшую функцию для данного случая.
is_positive (n: INTEGER): BOOLEAN
- Больше ли n нуля?
do
Result := (n > 0)
ensure
definition: Result = (n > 0)
end
Немного досадно. Не так уж много времени требуется для написания кода. Никогда не жалейте потратить время на нажатие клавиш для получения релевантного результата. Но, представьте, эта функция нужна только для того, чтобы выразить данное свойство [6.9] в инварианте класса. Тогда вы загромоздите класс компонентом, который не представляет соответствующий абстракцию данных класса. Это становится особенно неприятно, если таких свойств много, как происходит, когда мы даем ясное и точное описание контрактов класса. Это правда, что эти компоненты не требуется экспортировать, но они в любом случае становятся частью класса. Было бы лучше выразить релевантные свойства точно в том месте, где возникает в них необходимость, но без видимости их вне этого контекста.
Манифестные агенты в полной мере отвечают поставленной задаче. Манифестный агент, как говорит его имя, задает объявление метода в стиле, подобном объявлению метода, но ничего более не требуется, никакие методы класса не появляются. Синтаксис непосредственно выводится из переписи нашего последнего примера. Мы, по сути, сливаем [6.10]в [6.9], получая в результате:
(a.lower \..\ a.upper). for_all
(agent (n: INTEGER): BOOLEAN [28]
- Больше ли n нуля?
do
Result := (n > 0)
ensure
definition: Result = ( n > 0)
end)
Начиная со второй строчки текст совпадает с [6.10], с тем исключением, что исчезает ненужное теперь имя метода (агент манифестный).
Манифестный агент характеризуется следующим свойством: он задает анонимный метод.
Синтаксис манифестного агента, как показано в примере, совпадает с синтаксисом объявления метода c заменой имени метода на ключевое слово agent. Разрешается включать все компоненты, применимые к методу, такие как предусловия и постусловия, вводить собственные локальные переменные, чьи имена должны отличаться от имен методов класса и локальных переменных охватывающих методов. Это не соответствует соглашению, принятому для лямбда-выражений, где внутреннее связывание сильнее внешнего, но помогает избежать недоразумений. В конце концов, имена не являются
Даже когда нет конфликта с именами локальных переменных охватывающих методов, эти переменные нельзя непосредственно использовать в агенте. Если такая редкая необходимость возникает, то следует применить передачу переменных через аргументы агента.
Манифестные агенты дополняют механизмы агентов, обеспечивая поддержку выразительности наших ОО-программ. В следующей лекции подробно рассмотрим главное приложение этого механизма, которое позволяет построить элегантное решение проблемы "наблюдения", кратко охарактеризованной в этой лекции.
В начале этой лекции обсуждались ситуации, которые требуют использования объектов, представляющих обертку вычислений. Агенты являются эффективным инструментом в подобных случаях.
Не все языки программирования, однако, обладают такие конструкциями. Фактически среди языков, применяемых в индустрии, только Eiffel, Smalltalk и C# имеют похожие средства (существенно отличаясь в деталях). Представляет интерес вкратце рассмотреть, какие же решения являются доступными в зависимости от языка, который, возможно, вы используете.
Применяются четыре основных подхода:
Язык C# вводит понятие делегатов, предназначенных для тех же целей, что и агенты.
Если не принимать во внимание дух и нотацию, можно сказать, что главная разница между делегатами C# и агентами Eiffel в том, что цель делегата не может быть открытой. Выражение agent {STOP}.close не имеет прямого эквивалента в C#. В приложении, посвященному языку C#, о делегатах говорится подробнее.
Язык Smalltalk вводит понятие блока (block) — сегмента кода, который может передаваться как объект. Заметьте, что Smalltalk является нетипизированным языком, поэтому здесь нет способа проверить во время компиляции, что передаваемый блок будет использоваться с подходящими аргументами, — любые несоответствия приводят к появлению ошибок в период выполнения.
Функциональные языки типично поддерживают возможность рассматривать функции как данные. Это пришло еще от языка Lisp, где выражение в форме
(defun f (x y) ("expression involving x and y"))
определяет f как функцию двух аргументов. Тогда можно использовать f как аргумент другой функции, например:
(curry f)
Сама функция
Термин "замыкание" часто используется в функциональных языках для обозначения выражений, которые могут передаваться как данные, даже если они могут нуждаться в доступе к глобальным переменным.
Некоторые языки программирования позволяют передавать методы как аргументы другим методам с примерно таким синтаксисом:
integral (f:function(x: REAL):REAL ; a, b: REAL): REAL
В этом случае методу integral, вычисляющему интеграл, можно передать в качестве фактического аргумента метод с соответствующей сигнатурой, вычисляющий подынтегральную функцию. Язык должен обеспечить подходящую нотацию для вызова соответствующего метода из кода метода, такого как integral.
В сравнении с агентами или замыканиями такое решение имеет ограничения.
Однако этот подход удовлетворяет многим основным потребностям, он успешно применяется в не ОО-языках, начиная с Фортрана и продолжаясь в Паскале и его последователях.
Компьютеры, как вы знаете, используют память для хранения не только объектов, но и программ. Во время выполнения у каждой конкретной программы свой конкретный адрес памяти, где она хранится. Это делает возможным передать управление коду по адресу его расположения: если есть способ для программы обозначить свой адрес и существует механизм, допускающий команду типа "выполнить метод по адресу addr, а затем вернуться и продолжить", то можно рассматривать адреса методов как данные, благодаря которым вызываются соответствующие методы. На машинном уровне эти приемы и обеспечивают нужные потребности.
Когда вы используете метод как аргумент другого метода, компилятор, фактически, будет передавать адрес метода.
Объект, представляющий агента, в одном из своих полей (недоступных клиенту по понятным причинам) будет хранить адрес ассоциированного метода.
Динамическое связывание, необходимое для образца "много маленьких оберток", предполагает способность вызывать метод по его адресу, который хранится в некоторой структуре данных, представляющей свойства типа. Таблица методов, которая описывалась в этой лекции при рассмотрении приемов реализации наследования, является примером такой структуры.
Все эти приемы важны для компилятора в процессе генерирования кода, а не для прикладного программиста, когда он пишет свою программу. Компилятор скрывает адреса методов под одним или несколькими слоями абстракции, позволяя программисту думать в терминах более высокого уровня — методах, объектах, агентах.
Языки С и С++ позволяют передавать имя функции (процедуры рассматриваются как функции, возвращающие значение void ) как фактический аргумент или присваивать его переменной. Тогда, если f является соответствующим формальным аргументом или переменной, можно вызвать функцию следующим образом:
(*f ) (args)
Когда объявляется формальный аргумент, представляющий функцию, можно специфицировать его сигнатуру, известную как прототип, так что фактический аргумент, не соответствующий сигнатуре, должен быть отвергнут во время компиляции. Однако не обязательно задавать сигнатуру. Можно обойтись без этого, потеряв возможность получения предупреждений во время компиляции. Принимая это и рассматривая имя функции как ее адрес, получаем ту же гибкость, что и при программировании на языке ассемблера, теряя преимущества статической проверки типов.
Если язык программирования не поддерживает ни одну из упомянутых техник, но является ОО-языком — с классами, наследованием, полиморфизмом и динамическим связыванием, — то можно использовать образец "много маленьких оберток", изученный в начале этой лекции.
Его главный недостаток — необходимость писать много маленьких классов, часто включающих только один метод.
Язык Java, не имеющий механизма, подобного агентам, и не позволяющий передавать методы в качестве аргументов, смягчает проблему, позволяя программисту объявлять класс, локальный по отношению к другому классу, что также известно как вложенный класс. Тогда можно использовать вложенный класс, как если бы он был компонентом охватывающего класса. Эта техника позволяет избежать создания глобального пространства имен программы (множества имен классов, непосредственно доступных другим программным компонентам), но проблемы остаются.
n аргументов называется специализация (задание значений) m
аргументов (1 ≤ m ≤ n). В результате карринга функция из n аргументов трансформируется в функцию из n — m аргументов.Agent Агент
Beta-reduction Бета редукция
Closed operand Закрытый операнд
Closure Замыкание
Inline agent Манифестный агент
Lambda expression Лямбда-выражение
Nested class Вложенный класс
Open operand Открытый операнд
Operand Операнд
Prototype (C, C++) Прототип (С, С++)
Alpha-conversion Альфа-преобразование
Church-Rosser property Свойство Черча - Россера
First-class citizen Граждане первого класса
Lambda calculus
Many Little Wrappers pattern Образец "много маленьких оберток"
One-Song-Artist class Класс "певец одной песни"
Partial evaluation
Substitution (of a) Подстановка
variable in an expression) (переменной в выражение)
Дайте определения терминам словаря.
Добавьте новые концепции в карту, построенную в предыдущих лекциях.
Смотри соответствующий раздел "Время программирования".
Спроектируйте механизм итерирования, не использующий агентов, но основанный на классе LINEAR_ITERATOR, описывающем объекты, которые допускают итерирование специальной операцией на линейных структурах, подобных списку.
(Это мазохистское упражнение просит вас нарушить все принципы методологии просто для того, чтобы поразмышлять о возникающем беспорядке)
Работая с потомками класса LINEAR, такими как LINEAR_LIST, используйте процедуру
do_all с агентом в качестве аргумента, представляющего метод, который, нарушая явное предписание,
заданное заголовочным комментарием, изменяет структуру. В результате do_all может закончиться неуспехом
или даст несогласованный результат. С помощью отладчика, если необходимо, проанализируйте точные обстоятельства,
ведущие к отказу.
Перепишите do_all итератор LINEAR так, чтобы он не применял манифестный кортеж как аргумент call, а использовал бы кортежную переменную t, которая заполнялась бы значениями перед каждым вызовом.Подсказка 1: вначале создайте объект-кортеж, затем присвойте значение.Подсказка 2: перечитайте разделы о свойствах кортежа, особенно тегах.
Рассмотрите существующее множество классов, например, подмножество классов Traffic. Предположим, что программист может написать операцию visit, имеющую вариант для каждого из классов. Эти версии принимают целевой объект как аргумент. Цель упражнения состоит в определении компонента apply, который применяет подходящую visit операцию к любому такому объекту, переданному как аргумент без знания специфического типа (компонент apply может объявить этот аргумент имеющим тип ANY ).
Не разрешается модифицировать ни один из существующих классов или их потомков. Образец "Посетитель" неприменим, так как вы не можете предполагать, что классы являются потомками класса VISITOR.
Покажите, что желаемую цель можно достичь, используя агенты. Подсказка: следуйте модели итераторных классов, определенных в этой лекции.
Решение, а не только подсказку, можно найти в статье, которая посвящена компонентизации VISITOR,
цитируемой при обсуждении проблемы.
Спроектируйте более выразительное доказательство Проблемы Остановки, которое не использует никаких файлов, каталогов или строк, представляющих тексты программ. Работайте с программными элементами, передаваемыми как агенты.
Отмечалось, что карринг является взаимно обратной функцией. Напишите сигнатуру и определение функции
uncurry, которой передается функция с одним аргументом f, чей результат — функция с одним
аргументом. Функция uncurry должна возвращать функцию с двумя аргументами f такую, что
f '= .
Покажите, что условие бета-редукции: [λx: X| exp](e) — "не должно быть свободных переменных
e, появляющихся связанными в exp", сильнее, чем это фактически требуется для сохранения
неформальной семантики редукции — применения функции к аргументам. Спроектируйте менее строгое, но все еще корректное условие.
Покажите, что условие альфа-преобразования: $$e \triangled \lambda x: X| exp$$ в
λ y: X| exp [x:= y] — "нет ни свободных, ни
связанных вхождений y в e", сильнее, чем это фактически требуется для сохранения неформальной
семантики редукции — применения функции к аргументам. Спроектируйте менее строгое, но все еще корректное условие.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.