Какие языковые функции не могут быть определены в терминах лямбда?

Question

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

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

Answer 1

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

function id(x) { 
 
    return x; 
 
}

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

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

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

authorize_nuclear_attack(launch_codes); // oops 

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

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

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

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

Как?

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

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

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

Любая другая функция языка является:

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

Учтем:

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

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

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

   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); 
   

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

   

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

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

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.

Lambda calculus отражает понятие вычислимости.

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

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

Единственным ограничением исчисления лямбда является то, что вы не можете выразить решения проблем, для которых нет решений (даже частичных решений). Примером такой проблемы является “ с заданной программой 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 не всегда останавливается, он всегда останавливается.

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

Единственный случай использования, не охватываемый лямбда-исчислением, способен вычислять невычислимые функции. Тем не менее, поскольку бескомпромиссные функции являются небольшим битом uncomputable Я бы сказал, что нет случайных случаев, которые не покрываются лямбда-исчислением.

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

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