Какие языковые особенности нельзя определить с точки зрения лямбды?

Question

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

Какие случаи использования не охватываются лямбда?

Answer 1

Лямбда (то есть функция) сама по себе не очень интересна. Вот функция в JavaScript:

function id(x) {
    return x;
}

Что делает эта программа JavaScript? Ничего такого.

Однако функции имеют опасное свойство быть вызываемым.

При вызове функция может потенциально делать что угодно (применяются условия):

authorize_nuclear_attack(launch_codes); // oops

Следовательно, тривиально лямбда может потенциально делать что угодно.

Подумайте об этом, каждая программа на С - это функция, называемая main,

Но Аадит, вам понадобится какая-то другая языковая функция для реализации тела лямбды.

1. Как бы вы объявили, определили, обновили и оценили переменные?
2. Как бы вы приняли решение, не используя if заявление?
3. Как бы вы повторили блок кода произвольное количество раз без for цикл?
4. Как бы вы написали последовательный блок кода без оператора последовательности?
5. Как бы вы добавили два числа без использования примитива + оператор?

Как?

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

Тем не менее, это чертовски близко к достаточно.

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

Любая другая языковая особенность:

1. Либо присуще одно из этих трех свойств.
2. Или могут быть получены из этих трех функций.

Давайте рассмотрим:

1. Способность объявлять переменные присуща лямбда-абстракции:

   function id(x) { // declare variable x
       return x;    // valuate variable x
   }
   

2. Способность определять переменные (и обновлять рекурсию viz-a-viz) присуща лямбда-приложению:

   id(something);   // let x := something in the body of the function id
   

3. Способность принимать решения может быть получена из лямбда-абстракции и выборочной оценки:

   function boolean_true(then_branch, else_branch) {
       return then_branch;
   }
   
   function boolean_false(then_branch, else_branch) {
       return else_branch;
   }
   
   function if_statement(boolean_condition, then_branch, else_branch) {
       return boolean_condition(then_branch, else_branch);
   }
   

4. Способность повторять можно получить, "съев свой хвост" следующим образом:

   function dragon(dragon) {
       return dragon(dragon); // infinite loop
   }
   
   dragon(dragon);
   

   Я, конечно, имею в виду дракона Уроборос:

   

   Представьте, что дракон вращается как колесо навсегда, пытаясь съесть свой собственный хвост. Бесконечный цикл.

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

5. Мощность последовательности операций может быть получена путем составления функций:

   function substitution(f, g) { // S combinator from SKI combinator calculus
       return function (x) {
           return f(x, g(x));
       };
   }
   
   // substitution(f, g) is equivalent to (statement g; statement f)
   // where the semicolon is the sequencing operator like in C
   

6. Возможность добавить два числа может быть получена путем кодирования чисел в виде функций:

   function zero(f, x) {         // 0
       return x;
   }
   
   function add1(n) {            // n + 1
       return function (f, x) {
           return f(n(f, x));
       };
   }
   
   function add(m, n) {          // m + n
       return function (f, x) {
           return m(f, n(f, x));
       };
   }
   

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

Лямбда-исчисление охватывает понятие вычислимости.

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

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

Единственным ограничением лямбда-исчисления является то, что вы не можете выразить решения проблем, для которых нет решений (даже частичных решений). Примером такой проблемы является "данная программа P делает P остановить на всех входах? "

Другими словами, невозможно написать функцию H такой, что H(P) = true если P останавливается на всех входах, и H(P) = false иначе. Если вам удастся написать функцию H тогда это всегда будет неверно для следующей программы:

function P(x) {
    return H(P) ? P(x) : x;
}

Если H считает, что P всегда останавливается P идет в бесконечный цикл.

Если H считает, что P не всегда останавливается, то всегда останавливается.

Какие случаи использования не охватываются лямбда?

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

При этом никто не использует лямбда-исчисление для какого-либо реального программирования (как никто не использует машину Тьюринга в качестве реального компьютера). И лямбда-исчисление, и машины Тьюринга равны по мощности. Однако они очень разные звери.

Большинство императивных языков программирования, таких как C и Java, основаны на машине Тьюринга. Большинство функциональных языков программирования, таких как Haskell и OCaml, основаны на лямбда-исчислении. Хороший программист является экспертом в любом из них, но не в другом. Отличный программист знаком с обоими.