Преимущества компиляторов для функциональных языков по компиляторам для императивных языков

Нет.

Компилятор F # не пытается анализировать ссылочную прозрачность метода или лямбда. .NET BCL просто не предназначен для этого.

В спецификации языка F # зарезервировано ключевое слово «чистый», поэтому ручная пометка метода как «чистый» может быть возможна в vNext, что позволяет более агрессивно сокращать графы лямбда-выражений.

Однако, если вы используете либо записи, либо алгебраические типы, F # создаст операторы сравнения и равенства по умолчанию и предоставит семантику копирования. Среди многих других преимуществ (сопоставление с образцом, предположение о замкнутом мире) это значительно снижает нагрузку!

Да, если не учитывать F#, но учитывать, например, Хаскелла. Тот факт, что побочных эффектов нет, действительно открывает массу возможностей для оптимизации.

Например, рассмотрим на языке Си like:

int factorial(int n) {
    if (n <= 0) return 1;
    return n* factorial(n-1);
}

int factorialuser(int m) {
    return factorial(m) * factorial(m);
}

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

Обратите внимание, F# в настоящее время не является "чистым" функциональным языком. Поэтому я привёл Хаскелла (что здорово!).

Правильно ли я предполагаю, что компилятор F # может выполнять определенные оптимизации, зная, что он имеет дело с в значительной степени неизменяемым кодом?

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

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

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

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

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

• Эффективное использование памяти. По возможности работайте с «распакованными» значениями, избегая выделения и дополнительного уровня косвенного обращения к куче. В частности, слияние потоков и другие методы обезлесения очень эффективны, потому что они устраняют выделение ресурсов.

• Иметь сверхбыстрый распределитель и амортизировать проверки нехватки кучи по нескольким выделениям.

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

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

• Не упускайте из виду классические скалярные и циклические оптимизации. Они имели огромное значение для таких компиляторов, как TIL и Objective Caml.

Если у вас ленивый функциональный язык, такой как Haskell или Clean, с преобразователями есть еще много специализированных вещей.

Сноски:

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

• Написать хороший компилятор для F # сложнее, чем написать типичный компилятор (если он есть), потому что F # очень сильно ограничен: он должен хорошо выполнять функциональные задачи, но он также должен эффективно работать в рамках .NET Framework. , который не был разработан с учетом функциональных языков. Мы в долгу перед Доном Саймом и его командой за такую ​​отличную работу над проблемой с большими ограничениями.

К сожалению, поскольку F # в основном чистый, возможностей для агрессивной оптимизации не так уж и много. Фактически, есть некоторые места, где F # «пессимизирует» код по сравнению с C # (например, создает защитные копии структур для предотвращения наблюдаемых мутаций). С другой стороны, компилятор в целом выполняет хорошую работу, несмотря на это, обеспечивая производительность, сравнимую с C #, в большинстве случаев, тем не менее, одновременно делая программы более понятными.

Дополнительные оптимизации для функциональных языков иногда возможны, но не обязательно из-за неизменности. Внутри многих компиляторов код будет преобразован в SSA (единое статическое присваивание), где каждая локальная переменная внутри функции может быть присвоена только один раз. Это может быть сделано как для императивных, так и для функциональных языков. Например:

x := x + 1
y := x + 4

может стать

x_1 := x_0 + 1
y := x_1 + 4

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

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