2 вопроса в конце курса функционального программирования

Question

Вот, кажется, две самые важные вещи, которые я могу извлечь из курса «Как проектировать программы (упрощенная ракетка)», который я только что закончил, прямо из примечаний к лекциям курса:

1) Оптимизация вызова на хвосте,и его отсутствие в нефункциональных языках:

К сожалению, большинство других языков не поддерживают ОПТИМИЗАЦИЮ TAIL CALL.Другими словами, они создают стек даже для хвостовых вызовов.

Оптимизация вызовов на хвост была изобретена в середине 70-х годов, задолго до того, как были разработаны основные элементы большинства языков.Поскольку они не имеют оптимизации хвостового вызова, эти языки предоставляют фиксированный набор КОНСТРУКЦИЙ ПЕТЛИ, которые позволяют проходить данные произвольного размера.

a) Каковы эквиваленты этому типу оптимизации в процедурномязыки, которые не показывают это?б) Использование этих эквивалентов означает, что мы избегаем создания стека в подобных ситуациях в языках, в которых его нет?

2) Мутация и многоядерные процессоры

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

• , несмотря на то, что он фундаментальный, он удивительно сложен

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

• чрезмерное использование мутации также может затруднить понимание программ и затруднить понимание.хорошо их протестируйте

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

Я изучил некоторые Java, Python и C ++, прежде чем пройти этот курс, поэтому пришел к выводу, что мутация является само собой разумеющимся.Теперь, когда все вышесказанное было подтверждено вышеприведенным заявлением.Мои вопросы:

а) где я могу найти более подробную информацию о том, что предлагается во 2-м пункте, и что с этим делать, и б) какие шаблоны появятся из "в основном функционального программирования""стиль, в отличие от более небрежного стиля, который я, вероятно, имел бы, если бы продолжил изучать другие языки вместо того, чтобы пройти этот курс?

Answer 1

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

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

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

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

Answer 2

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

Трудно получить правильную синхронизацию. Если вы чрезмерно синхронизируете, у вас будут взаимоблокировки, низкая (последовательная, а не параллельная) производительность и т. Д. Если вы не синхронизированы, у вас частично наблюдаемые изменениягде другое ядро ​​видит только часть изменений, которые вы сделали из другого ядра), оставляя ваши объекты наблюдаемыми в недопустимом состоянии «наполовину изменено».

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

Answer 3

a) Каковы эквиваленты этого типа оптимизации в процедурных языках, в которых она отсутствует?б) Использование этих эквивалентов означает, что мы избегаем создания стека в подобных ситуациях в языках, в которых его нет?

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

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

a) Где я могу найти более подробную информацию о том, что предлагается во 2-м пункте и что с этим делать

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

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

Вы смотрели на Haskell?или Clojure?Оба сильно склонны к очень функциональному стилю, подчеркивая контролируемую мутацию.Haskell более строг в этом, но имеет множество инструментов для работы с ограниченными формами изменчивости, в то время как Clojure немного более неформален и может быть более знаком вам, поскольку это еще один диалект Lisp.