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

Ответ 1

Сначала узнайте, что машина Тьюринга (из Википедии).

Машина Тьюринга - это устройство, которое манипулирует символами на ленте ленты в соответствии с таблицей правил. Несмотря на свою простоту, машина Тьюринга может быть адаптирована для моделирования логики любого компьютерного алгоритма и особенно полезна для объяснения функций ЦПУ внутри компьютера.

Речь идет о исчислении Ламды. (из Википедии).

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

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

Что я подразумеваю под "фундаментальной моделью вычислений"? Ну, все языки можно представить в двух слоях: один, некоторый основной язык Turing, а затем слои либо абстракций, либо синтаксический сахар (в зависимости от того, нравится вам это или нет), которые определены в терминах базового Turing- полный язык. Основной язык для императивных языков - это вариант классической машинной модели Тьюринга, которую можно назвать "языком C". На этом языке память представляет собой массив байтов, который можно читать и записывать, и у вас есть один или несколько процессоров, которые читают память, выполняют простые арифметические операции, ветки на условиях и т.д. То, что я подразумеваю под фундаментальной моделью вычисления этих языков, является машина Тьюринга.

Фундаментальной моделью вычисления для функциональных языков является лямбда-исчисление, и это проявляется двумя разными способами. Во-первых, одна вещь, которую делают многие функциональные языки, - это написать свои спецификации явно в терминах перевода в лямбда-исчисление, чтобы указать поведение программы, написанной на языке (это называется "денотационная семантика" ). И во-вторых, почти все языки функционального программирования реализуют свои компиляторы для использования явного лямбда-исчисляющего промежуточного языка - Haskell имеет Core, Lisp, а схема имеет свое "desugared" представление (после применения всех макросов), Ocaml (Objective категорический абстрактный машинный язык) имеет свое промежуточное представление в виде lispish и т.д.

Итак, что это за лямбда-исчисление, о котором я уже говорил? Ну, основная идея состоит в том, что для любых вычислений вам нужны только две вещи. Первое, что вам нужно - это функция абстракции - определение неназванной, однопараметрической функции. Церковь Алонсо, которая сначала определила исчисление Лямбды, использовала довольно неясную нотацию, чтобы определить функцию как греческую букву лямбда, за которой следует односимвольное имя аргумента функции, за которым следует период, за которым следует выражение, которое было тело функции. Таким образом, функция тождества, которая дает какое-либо значение, просто возвращает это значение, будет выглядеть как "λx.x". Я собираюсь использовать немного более понятный для человека подход. Я собираюсь заменить символ λ словом "fun", период с "- > " и разрешить пробел и разрешить многосимвольные имена. Поэтому я мог бы написать функцию идентичности как "fun x → x" или даже "повеселиться - что угодно". Изменение нотации не меняет фундаментальной природы. Обратите внимание, что это источник имени "лямбда-выражения" в таких языках, как Haskell и Lisp - выражения, которые вводят неназванные локальные функции.

Единственное, что вы можете сделать в исчислении лямбда, это вызвать функции. Вы вызываете функцию, применяя к ней аргумент. Я буду следовать стандартным соглашениям, что приложение - это всего лишь два имени в строке, поэтому f x применяет значение x к функции с именем f. Мы можем заменить f другим выражением, в том числе выражением Lambda, если хотим - и мы можем. Когда вы применяете аргумент к выражению, вы заменяете приложение телом функции, при этом все вхождения имени аргумента заменяются с любым значением, которое было применено. Таким образом, выражение (fun x -> x x) y становится y y.

Теоретики пошли на многое, чтобы точно определить, что они подразумевают под "заменой всех вхождений переменной на применяемое значение" и могут продолжаться очень подробно о том, как именно это работает (бросая вокруг таких терминов, как "альфа-переименование" "), но в итоге все работает так, как вы ожидаете. Выражение (fun x -> x x) (x y) становится (x y) (x y) - не существует путаницы между аргументом x внутри анонимной функции и x в применяемом значении. Это работает даже на нескольких уровнях - выражение (fun x -> (fun x -> x x)) (x x)) (x y) становится первым (fun x -> x x) ((x y) (x y)), а затем ((x y) (x y)) ((x y) (x y)). X в самой внутренней функции ("(fun x -> x x)") является другим x, чем другой xs.

Совершенно верно думать о функциональном приложении как о строковой манипуляции. Если у меня есть (забавное x → некоторое выражение), и я применяю к нему какое-то значение, тогда результат будет всего лишь некоторым выражением со всеми xs, замененными по тексту "некоторым значением" (за исключением тех, которые затенены другим аргументом).

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

Итак, все это тоже относится к исчислению Лямбды. Нет, действительно, это все - просто анонимная функция абстракции и функциональное приложение. Я вижу, что вы сомневаетесь в этом, поэтому позвольте мне затронуть некоторые ваши проблемы.

Во-первых, я указал, что функция принимает только один аргумент - как у вас есть функция, которая принимает два или более аргумента? Легко - у вас есть функция, которая принимает один аргумент и возвращает функцию, которая принимает второй аргумент. Например, состав функции может быть определен как fun f -> (fun g -> (fun x -> f (g x))) - считать, что как функция, которая принимает аргумент f, и возвращает функцию, которая принимает аргумент g и возвращает функцию, которая принимает аргумент x и возвращает f (gx).

Итак, как мы представляем целые числа, используя только функции и приложения? Легко (если не очевидно) - номер один, например, является функцией fun s -> fun z -> s z - заданной "преемницей" функцией s и "нулем" z, тогда она является преемницей нулю. Два - это забава s → fun z -> s s z, преемник преемника к нулю, три - fun s -> fun z -> s s s z и т.д.

Чтобы добавить два числа, скажем x и y, снова прост, если он тонкий. Функция добавления - это просто fun x -> fun y -> fun s -> fun z -> x s (y s z). Это выглядит странно, поэтому позвольте мне привести вас к примеру, чтобы показать, что это так, на самом деле работа добавляет числа 3 и 2. Теперь три просто (fun s -> fun z -> s s s z), а два - просто (fun s -> fun z -> s s z), поэтому мы получаем (каждый шаг, применяя один аргумент к одной функции, в определенном порядке):

(fun x -> fun y -> fun s -> fun z -> x s (y s z)) (fun s -> fun z -> s s s z) (fun s -> fun z -> s s z)

(fun y -> fun s -> fun z -> (fun s -> fun z -> s s s z) s (y s z)) (fun s -> fun z -> s s z)

(fun y -> fun s -> fun z -> (fun z -> s s s z) (y s z)) (fun s -> fun z -> s s z)

(fun y -> fun s -> fun z -> s s s (y s z)) (fun s -> fun z -> s s z)

(fun s -> fun z -> s s s ((fun s -> fun z -> s s z) s z))

(fun s -> fun z -> s s s (fun z -> s s z) z)

(fun s -> fun z -> s s s s s z) 

И в конце мы получаем неудивительный ответ преемника на преемника преемника преемника преемника к нулю, известного более разговорно, как пять. Добавление работает, заменяя zero (или на начало отсчета) значения x значением y для определения умножения, вместо этого мы используем понятие "преемник":

(fun x -> fun y -> fun s -> fun z -> x (y s) z)

Я оставлю это вам, чтобы убедиться, что приведенный выше код

Википедия говорит

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

// Fibonacci numbers, imperative style
int fibonacci(int iterations)
{
    int first = 0, second = 1; // seed values

    for (int i = 0; i < iterations; ++i) {
        int sum = first + second;
        first = second;
        second = sum;
    }

    return first;
}

std::cout << fibonacci(10) << "\n";

Функциональная версия (в Haskell) отличается от него:

-- Fibonacci numbers, functional style

-- describe an infinite list based on the recurrence relation for Fibonacci numbers
fibRecurrence first second = first : fibRecurrence second (first + second)

-- describe fibonacci list as fibRecurrence with initial values 0 and 1
fibonacci = fibRecurrence 0 1

-- describe action to print the 10th element of the fibonacci list
main = print (fibonacci !! 10)

Смотрите также этот PDF

Ответ 2

(A) Функциональное программирование описывает решения механически. Вы определяете машину, которая постоянно выводится правильно, например. с Caml:

let rec factorial = function
  | 0 -> 1
  | n -> n * factorial(n - 1);;

(B) Процедурное программирование временно описывает решения. Вы описываете последовательность шагов, чтобы преобразовать заданный вход в правильный выход, например. с Java:

int factorial(int n) {
  int result = 1;
  while (n > 0) {
    result *= n--;
  }
  return result;
}

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