Что означает составляемость в контексте функционального программирования? - PullRequest
59 голосов
/ 22 мая 2010

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

Вот некоторые из утверждений такого рода, которые я прочитал:

  • Управляющие структуры не компонуются.
  • Темы не составляют.
  • Монадические операции компонуются.

Ответы [ 7 ]

52 голосов
/ 22 мая 2010

Марсело Кантос дал довольно хорошее объяснение , но я думаю, что это можно сделать чуть точнее.

Тип вещи может быть составлен, когда несколько экземпляров могут быть объединены определенным образом для производства одного и того же типа вещи.

Возможность компоновки структуры управления. В таких языках, как C, проводится различие между выражениями , которые могут быть составлены с использованием операторов для создания новых выражений, и выражениями , которые могут быть составленным с использованием управляющих структур, таких как if, for и «структуры управления последовательностью», которая просто выполняет операторы по порядку. Дело в том, что эти две категории не находятся в равных условиях - многие управляющие структуры используют выражения (например, выражение, оцениваемое if, чтобы выбрать, какую ветвь выполнять), но выражения не могут использовать управляющие структуры. (например, вы не можете вернуть цикл for). Хотя может показаться сумасшедшим или бессмысленным желание «возвращать цикл for», на самом деле общая идея трактовать управляющие структуры как первоклассные объекты, которые можно хранить и передавать, не только возможна, но и полезна. В ленивых функциональных языках, таких как Haskell, управляющие структуры, такие как if и for, могут быть представлены как обычные функции, которыми можно манипулировать в выражениях, как и любым другим термином, позволяя таким вещам, как функции, которые «строят» другие функции в соответствии с Параметры, которые они передают, и возвращают их вызывающей стороне. Таким образом, хотя C (например) делит «то, что программист может захотеть сделать» на две категории и ограничивает способы объединения объектов из этих категорий, Haskell (например) имеет только одну категорию и не накладывает таких ограничений так что в этом смысле он обеспечивает большую сочетаемость.

Возможность компоновки потоков. Я предполагаю, что, как и Марсело Кантос, вы действительно говорите о возможности компоновки потоков, использующих блокировки / мьютексы. Это немного более сложный случай, потому что на первый взгляд у может есть потоки, которые используют несколько блокировок; но важным моментом является то, что у нас не может быть потоков, использующих множественные блокировки с гарантиями, что они должны иметь .

Мы можем определить блокировку как тип вещи, которая имеет определенные операции, которые могут быть выполнены с ней, которые идут с определенными гарантиями. Одна гарантия: предположим, что существует объект блокировки x, при условии, что каждый процесс, который вызывает lock(x), в конечном итоге вызывает unlock(x), любой вызов lock(x) в конечном итоге будет успешно возвращен с x, заблокированным текущим потоком / процесс. Эта гарантия значительно упрощает рассуждения о поведении программы.

К сожалению, если в мире более одной блокировки, это уже не так. Если поток A вызывает lock(x); lock(y);, а поток B вызывает lock(y); lock(x);, возможно, что A захватывает блокировку x и B захватывает блокировку y, и они оба будут бесконечно ждать, пока другой поток освободит другую блокировку: deadlock. Таким образом, блокировки не поддаются компоновке, потому что когда вы используете более одной, вы не можете просто утверждать, что эта важная гарантия все еще действует - , не анализируя код подробно, чтобы увидеть, как он управляет блокировками . Другими словами, вы больше не можете рассматривать функции как «черные ящики».

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

32 голосов
/ 22 мая 2010

Простым примером компоновки является командная строка Linux, где символ канала позволяет комбинировать простые команды (ls, grep, cat и т. Д.) Практически неограниченным количеством способов, тем самым «составляя» большое количество сложных поведения из небольшого числа простых примитивов.

Существует несколько преимуществ компоновки:

  • Более равномерное поведение: например, имея единственную команду, которая реализует "показать результаты на одной странице время "(more) вы получаете степень однородность пейджинга, которая не будет возможно, если каждая команда реализовать свои собственные механизмы (и флаги командной строки) для подкачки.
  • Меньше повторных работ по внедрению (СУХОЙ): вместо того, чтобы иметь число различные реализации пейджинга, есть только один, который используется во всем мире.
  • Больше функциональности для заданной суммы усилий по реализации: существующие Примитивы могут быть объединены, чтобы решить гораздо больший спектр задач, чем что было бы в случае, если те же усилия вошел в реализацию монолитные несложные команды.

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

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

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

Более того, меньшее количество типов данных дает большую возможность компоновки. Рич Хики из Clojure сказал что-то вроде

каждый новый тип объекта по своей природе несовместим со всем кодом когда-либо написано

что, безусловно, хорошо сделано.

Практическая компоновка также зависит от стандартизации небольшого набора типов данных, как это делают команды Unix со своим стандартом «текст на основе строк, разделенных табуляцией».

Постскриптум

Эрик Рэймонд написал книгу о философии Unix, два из перечисленных принципов проектирования были

  • Правило модульности: напишите простые детали, соединенные чистыми интерфейсами.
  • Правило композиции: разработка программ для связи с другими программами.

С http://catb.org/~esr/writings/taoup/html/ch01s06.html#id2877537

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

22 голосов
/ 22 мая 2010

Композиция в информатике - это способность составлять сложное поведение путем агрегирования более простого поведения.Функциональная декомпозиция является примером этого, в результате чего сложная функция разбивается на более мелкие простые для понимания функции и собирается в конечную систему с помощью функции верхнего уровня.Можно сказать, что функция верхнего уровня «скомпоновала» части в единое целое.

Некоторые понятия нелегко составить.Например, потокобезопасная структура данных может позволить безопасную вставку и удаление элементов, и это происходит путем блокирования структуры данных или некоторого ее подмножества, чтобы один поток мог выполнять необходимые манипуляции без вмешательства в его изменения - иСтруктура данных повреждена - пока она работает.Однако бизнес-функция может потребовать удаления элемента из одной коллекции с последующей его вставкой в ​​другую, чтобы вся операция выполнялась атомарно.Проблема в том, что блокировка происходит только для структуры данных.Вы можете безопасно удалить элемент из одного, но тогда вы можете обнаружить, что не можете вставить его в другой из-за нарушения ключа.Или вы можете попытаться вставить его в одну секунду, а затем удалить его из первой, только чтобы обнаружить, что другая нить украла его из-под вашего носа.Понимая, что вы не можете завершить операцию, вы можете попытаться вернуть вещи такими, какими они были, только чтобы обнаружить, что обращение не удалось по тем же причинам, и теперь вы находитесь в подвешенном состоянии!Конечно, вы могли бы реализовать более богатую схему блокировки, которая охватывает несколько структур данных, но это работает, только если все согласны с новой схемой блокировки и несут бремя ее использования постоянно, даже когда все их операции выполняются на однойструктура данных.

Таким образом, блокировка в стиле мьютекса - это концепция, которая не является составной.Вы не можете реализовать поточно-безопасное поведение более высокого уровня, просто агрегируя поточно-безопасные операции более низкого уровня.Решением в этом случае является использование концепции, которая составляет, например, STM .

5 голосов
/ 22 мая 2010

Я согласен с ответом Марсело Кантоса, но думаю, что он может предполагать больше знаний, чем некоторые читатели, что также связано с тем, почему композиция в функциональном программировании особенная. Композиция функций функционального программирования по существу идентична композиции функций в математике. В математике у вас может быть функция f(x) = x^2 и функция g(x) = x + 1. Составление функций означает создание новой функции, в которой аргументы функции передаются «внутренней» функции, а выход «внутренней» функции служит входом для «внешней» функции. Составление f внешнего с g внутренним может быть написано f(g(x)). Если для x указано значение 1, то g(1) == 1 + 1 == 2, поэтому f(g(1)) == f(2) == 2^2 == 4. В целом, f(g(x)) == f(x + 1) == (x+1)^2. Я описал композицию, используя синтаксис f(g(x)), но математики часто предпочитают другой синтаксис, (f . g)(x). Я думаю, это потому, что проясняет, что f composed with g - это отдельная функция, которая принимает один аргумент.

Функциональные программы построены полностью с использованием композиционных примитивов. Программа на Haskell - это, возможно, упрощенно, функция, которая принимает в качестве аргумента среду времени выполнения и возвращает результат некоторых манипуляций с этой средой. (Гроккинг этого утверждения потребует некоторого понимания монад.) Все остальное делается с помощью композиции в математическом смысле .

2 голосов
/ 22 мая 2010

Другой пример: рассмотрим асинхронное программирование в .NET.Если вы используете такой язык, как C #, и вам нужно выполнить серию асинхронных (неблокирующих) вызовов ввода / вывода через API Begin / End, то для последовательного вызова двух операций, Foo и Bar, выдолжны выставить два метода (BeginFooAndBar, EndFooAndBar), где BeginFooAndBar вызывает BeginFoo и передает обратный вызов Intermediate, а Intermediate затем вызывает BeginBar, и вы должны получить промежуточные значенияи IAsyncResult информация о состоянии через, и если вам нужен блок try - catch вокруг всего этого, тогда удачи, вам нужно продублировать код обработки исключений в трех местах, да, и это ужасный беспорядок.

Но затем с F # есть тип async, построенный поверх функциональных продолжений, которые являются составными, и поэтому вы можете написать, например,

let AsyncFooAndBar() = async {
    let! x = Async.FromBeginEnd(BeginFoo, EndFoo)
    let! y = Async.FromBeginEnd(BeginBar, EndBar, x)
    return y * 2 }

или что у вас, и это простои если вы хотите поместить try - catch вокруг него, прекрасно, код весь в одном методе, а не распределен по трем, вы просто поместите try - catch вокруг него, и он заработает.

1 голос
/ 08 октября 2015

Возможность компоновки позволяет сообществу разработчиков постоянно повышать уровень абстракции, на несколько уровней, не привязываясь к базовому уровню.

1 голос
/ 22 мая 2010

Вот пример из реальной жизни. Имена всех людей, которые живут в вашем доме, - это список имен всех мужчин в вашем доме вместе со списком всех женщин в вашем доме.

Это составно, поскольку каждая из этих двух подзадач может быть решена независимо и без вмешательства в решение другой.

С другой стороны, многие рецепты не являются составными, поскольку шаги должны выполняться в определенном порядке и основываться на результатах других шагов. Вы должны разбить яйца, прежде чем взбить их!

...