Чем функциональные языки отличаются с точки зрения реализации языка

Question

Существует совершенно новая парадигма «функционального программирования», которая требует полного изменения образа мышления по сравнению с процедурным программированием.Он использует функции высшего порядка, чистоту, монады и т. д., которые мы обычно не видим в императивных и объектно-ориентированных языках.

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

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

Answer 1

Реализации языков функционального программирования используют широкий спектр методов реализации.Отличное введение в реализацию Scheme (диалект Лиспа) дает эта книга: Лисп в маленьких кусочках Кристиан Кеннек.

Answer 2

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

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

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

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

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

Answer 3

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

Функциональные языки часто используют рекурсию.Поэтому любая реализация должна попытаться оптимизировать этот случай.Например.определить хвостовую рекурсию и преобразовать ее в цикл внутри (таким образом экономя накладные расходы на вызовы функций, такие как сохранение/восстановление стека).(http://en.wikipedia.org/wiki/Tail_recursion)

Answer 4

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

Answer 5

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

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

Answer 6

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

Answer 7

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

Тем не менее, существуют аргументы в пользу эффективности, которые отдают предпочтение замыканиям перед глобальными переменными (особенно в контексте реализации компилятора).[Но я знаю функциональные языки, которые не обеспечивают замыкания напрямую, хотя «работающие одинаково» могут быть реализованы.]

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

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

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