WikiDer > Формализм Берда-Меертенса

Bird–Meertens formalism

В Формализм Берда-Меертенса (BMF) это исчисление за вывод программ из технические характеристикифункциональное программирование установка) посредством процесса эквационального рассуждения. Это было разработано Ричард Берд и Ламберт Меертенс как часть их работы в Рабочая группа 2.1 ИФИП.

Иногда это упоминается в публикациях как BMF, как намек на Форма Бэкуса – Наура. В шутку это также называют Squiggol, как дань уважения АЛГОЛ, который также входил в компетенцию WG 2.1, а также из-за «волнистых» символов, которые он использует. Менее используемый вариант имени, но на самом деле первый из предложенных: СКВИГОЛ.

Основные примеры и обозначения

карта хорошо известная функция второго порядка, которая применяет данную функцию к каждому элементу списка; в BMF написано :

Так же, уменьшать это функция, которая сворачивает список в одно значение с помощью повторное применение бинарного оператора. Написано / в BMF. как подходящий бинарный оператор с нейтральным элементом е, у нас есть

Используя эти два оператора и примитивы (как обычное дополнение), и (для конкатенации списков), мы можем легко выразить сумму всех элементов списка, и сплющивать функция, как и , вбезточечный стиль. У нас есть:

Вывод Алгоритм Кадане

Точно так же написание за функциональный состав и за соединение, легко написать функцию, проверяющую, что все элементы списка удовлетворяют предикату п, просто как :

Берд (1989) преобразует неэффективные простые для понимания выражения («спецификации») в эффективные задействованные выражения («программы») с помощью алгебраических манипуляций. Например, спецификация ""является почти дословным переводом" алгоритм максимальной суммы сегмента ",[1] но запуск этой функциональной программы в списке размеров потребуется время в целом. Исходя из этого, Bird вычисляет эквивалентную функциональную программу, которая выполняется во времени. , и фактически является функциональной версией Алгоритм Кадане.

Вывод показан на картинке, с вычислительной сложностью.[2] указаны синим цветом, а приложения закона - красным. Примеры законов можно открыть, нажав на [Показать]; они используют списки целых чисел, сложение, минус и умножение. Обозначения в статье Берда отличаются от использованных выше: , , и соответствуют , , и обобщенная версия выше, соответственно, а и составить список всех префиксы и суффиксы своих аргументов соответственно. Как и выше, функциональная композиция обозначается "", у которого самый низкий обязательный приоритет. В примерах экземпляров списки раскрашены по глубине вложенности; в некоторых случаях новые операции определяются специально (серые поля).

Лемма о гомоморфизме и ее приложения к параллельным реализациям

Функция час в списках это список гомоморфизм если существует ассоциативный бинарный оператор и нейтральный элемент такое, что имеет место следующее:

В лемма о гомоморфизме утверждает, что час является гомоморфизмом тогда и только тогда, когда существует оператор и функция ж такой, что .

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

Смотрите также

Рекомендации

  1. ^ Где , , и возвращает наибольшее значение, сумму и список всех сегментов (то есть подсписок) данного списка.
  2. ^ Каждое выражение в строке обозначает исполняемую функциональную программу для вычисления максимальной суммы сегментов.
  • Ламберт Меертенс (1986). «Алгоритмика: к программированию как математической деятельности».. В J.W. де Баккер; М. Хазевинкель; J.K. Ленстра (ред.). Математика и информатика, Монографии CWI Том 1. Северная Голландия. С. 289–334.
  • Ламберт Меертенс; Ричард Берд (1987). «Два упражнения из книги по алгоритмике» (PDF). Северная Голландия.
  • Ричард С. Берд (1989). «Алгебраические тождества для программного расчета» (PDF). Компьютерный журнал. 32 (2): 122–126. Дои:10.1093 / comjnl / 32.2.122.
  • Ричард Берд; Oege de Moor (1997). Алгебра программирования, Международная серия по вычислительной технике, Vol. 100. Прентис Холл. ISBN 0-13-507245-X.