Что означает «не сочинять»?

35

Я вижу много текстов, особенно тексты о функциональном программировании, утверждающие, что определенные концепции CS «не сочиняются» . Примеры: замки не сочиняются, монады не сочиняются.

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

Может кто-нибудь объяснить, что означает эта фраза, когда она используется в выражениях, подобных двум приведенным выше примерам (то есть замкам и монадам)?

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

Ответы:

35

Когда люди говорят «Х не составляет», то, что они подразумевают под «сочинять», на самом деле просто означает «соединить», и то , что и как вы их соединяете, может сильно отличаться, в зависимости от того, что именно означает «Х».

Кроме того, когда они говорят «не сочиняет», они могут означать несколько разные вещи:

  1. Вы не можете соединить два X вместе, точка.
  2. Вы можете соединить два X, но результатом может быть не X (IOW: X не замкнуто в композиции .)
  3. Вы можете соединить два X, но полученный X может работать не так, как вы ожидаете.

Пример для # 1 - парсеры со сканерами / лексерами. Вы можете услышать фразу «сканеры / лексеры не сочиняют». Это не совсем так. То, что они имеют в виду, это «синтаксический анализатор, который использует отдельную стадию лексинга, не создает».

Почему вы хотите сочинять парсеры? Представьте, что вы являетесь поставщиком IDE, таким как JetBrains, Eclipse Foundation, Microsoft или Embarcadero, и вы хотите создать IDE для веб-фреймворка. В типичной веб-разработке мы часто смешиваем языки. У вас есть HTML-файлы с <script>элементами, содержащими ECMAScript и<style>элементы, содержащие CSS. У вас есть файлы шаблонов, содержащие HTML, некоторый язык программирования и некоторый метасинтаксис языка шаблонов. Вы не хотите писать разные подсветки синтаксиса для «Python», «Python, встроенный в шаблон», «CSS», «CSS в HTML», «ECMASCript», «ECMAScript в HTML», «HTML», «HTML в» шаблон "и так далее и тому подобное. Вы хотите написать подсветку синтаксиса для Python, одну для HTML, одну для языка шаблонов, а затем объединить три в подсветку синтаксиса для файла шаблона.

Однако лексер анализирует весь файл в поток токенов, что имеет смысл только для этого одного языка. Парсер для другого языка не может работать с токенами, которые его передает лексер. Например, синтаксические анализаторы Python обычно написаны таким образом, что лексер отслеживает отступы и внедряет фальшивые INDENTи DEDENTтокены в поток токенов, что позволяет синтаксическому анализатору быть свободным от контекста, даже если синтаксис Python фактически таковым не является. HTML-лексер, однако, будет полностью игнорировать пробелы, так как он не имеет значения в HTML.

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

Пример для # 2 - строки с запросами SQL в них. Вы можете иметь две строки, каждая из которых содержит синтаксически правильный SQL-запрос, но если вы объедините две строки, результатом может быть не синтаксически правильный SQL-запрос. Вот почему мы имеем запрос алгебру , как ARel, которые делают сочинять.

Замки являются примером № 3. Если у вас есть две программы с блокировками, и вы объединяете их в одну программу, у вас все равно есть программа с блокировками, но даже если две исходные программы были полностью правильными, без тупиков и гонок, получающаяся в результате программа не обязательно будет иметь это свойство. Правильное использование блокировок - это глобальное свойство всей программы и свойство, которое не сохраняется при создании программ. Это отличается от, например, операции, которые делают сочинять. Программа, которая правильно использует транзакции, может быть составлена ​​с другой такой программой и даст комбинированную программу, которая правильно использует транзакции.

Йорг Миттаг
источник
1
Другими словами, «не составляет» означает «не образует полугруппу» (или, чуть более сильно, моноид).
Джон Перди
Я не уверен, что ассоциативность необходима, поэтому больше похожа на Магму (о которой я узнал буквально 3 секунды назад :-D)
Йорг Миттаг
Однако, если вы спросите кого-то, что они имеют в виду, когда говорят «блокировки не составляют», я почти уверен, что они не ответят: «Я имею в виду, что набор правильных параллельных программ с блокировками и операцией композиции образуют магму». ,
Йорг Миттаг
Ха, конечно нет. Просто альтернативная формулировка. У меня есть ощущение, что ассоциативность необходима для поддержания «плоского» чувства композиции, но нет веских аргументов в поддержку этого.
Джон Пурди
20

Композиционность означает, что вы можете легко и надежно комбинировать программные компоненты, чтобы получить более крупные компоненты и более сложные функции.

Некоторые вещи, которые помогают сделать компоненты более компонуемыми:

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

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

  3. Неизменность. Состояние неизменяемого объекта не может быть изменено после его создания. Это улучшает возможность компоновки, поскольку вы можете полагаться на стабильное значение объекта, не беспокоясь о том, изменила ли какая-либо функция или объект где-либо состояние объекта после его создания.

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

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

Фраза "монады не сочинять" не имеет большого смысла для меня. Весь смысл монады в том, чтобы взять что-то с состоянием, например, ввод с клавиатуры или с экрана, и превратить его в более чистую, математическую форму, которая на самом деле более компонована.

Роберт Харви
источник
4
Я думаю, что stackoverflow.com/questions/7040844/… делает хорошую работу, объясняя, что, вероятно, означает «монады не сочиняют», хотя я согласен, что монады гораздо более компонуемы, чем блокировки.
Ixrec
Ваши баллы за «ссылочную прозрачность» и «чистоту» на самом деле являются двумя требованиями к чистоте . Следует избегать термина «ссылочная прозрачность», потому что он не является четко определенным .
BlueRaja - Дэнни Пфлугхофт
1
Монада - это алгебраическая структура с определенными операциями. В последнем абзаце вы описали IOтип, который фиксирует «действия с состоянием», такие как ввод с клавиатуры. Значения IOтипа, действительно, составляют, но весь тип IO является монадой. Этот тип не объединяется с другими типами, которые являются монадами, такими как, скажем, тип списка. То есть мы не можем систематически создавать тип, IO . Listкоторый ведет себя как одновременно, так IO и Listодновременно. Имеет ли это смысл? Я не уверен, что объяснил это хорошо.
Тихон Джелвис