Какова связь между лямбда-исчислением и языками программирования? [закрыто]

13

Я начинаю свой первый год (в колледже) в области компьютерных наук в следующем году, и я пишу в основном на C (если это имеет значение). Я пробовал искать, но большая часть того, что я нашел, предполагает знание лямбда-исчисления. Почему при программировании лямбда-исчисление считается гораздо более полезным, чем исчисление с одной переменной? Есть ли связь между лямбда-выражениями и функциональными программами? Была ли работа Алонзо Черча по лямбда-исчислению, которая повлияла на развитие языков программирования?

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

RonaldMunodawafa
источник
2
На этот вопрос лучше ответить на cs.stackexchange.com .
davidk01
@ ChrisF. Может быть, этот вопрос лучше подходит для одного из сайтов информатики. Если нет, то я попытался сузить его и подумать, можно ли его снова открыть в его нынешнем виде.
Том Ау
Mathematica запекла лямбда-исчисление в заметили, что никто не упомянул об этом.
Уильям

Ответы:

26

Лямбда-исчисление является интересным, элегантным и значительно облегчает понимание функциональных языков программирования. Тем не менее, вы не столкнетесь с LC в типичном курсе бакалавриата по CS, поэтому вам не нужно изучать его прямо сейчас - я бы рекомендовал сначала поэкспериментировать с функциональными языками, прежде чем пересматривать Lambda Calculus. Я считаю, что OCaml является хорошей отправной точкой в ​​функциональном программировании для программиста на C, и что Scheme является хорошей отправной точкой для погружения в Lambda Calculus.

Лямбда-исчисление не связано с исчислением (которое вместо этого следует называть анализом). В общем, исчисление - это «формальная система», то есть набор правил, чтобы что-то делать. В то время как дифференциальное исчисление предоставляет правила, касающиеся изменения значений, правила лямбда-исчисления описывают само вычисление. Из этого набора базовых правил мы можем строить произвольные вычисления, представления данных, такие как логические значения, целые числа или списки, и даже конструкции потока управления, такие как условные выражения или циклы. LC эквивалентен машинам Тьюринга, но у любой модели есть свои сильные стороны.

Лямбда-исчисление оказало огромное влияние на языки программирования. Вторым языком высокого уровня, который должен быть реализован, был Lisp, который можно понимать как прямое кодирование LC в язык программирования. Это «функциональное программирование» оказывает огромное влияние на развитие языков программирования. Такие функции, как анонимные функции, указатели на функции, замыкания (вложенные функции), сборка мусора, область видимости переменных, метапрограммирование, усовершенствования в системах типов, вывод типов, интерпретируемые языки, языки с динамической типизацией, объектно-ориентированное программирование - все это во многом обусловлено к функциональной ветви программирования языков программирования. Есть шутка, что любой новый (не академический) язык программирования добавляет только те функции, которые Lisp уже имел в течение десятилетий.

Кроме того, лямбда-исчисление и другие связанные исчисления являются незаменимыми инструментами в теории языка программирования и в некоторых методах построения компилятора.

Любой язык, который имеет анонимные функции, которые ведут себя как замыкания и могут свободно передаваться, немедленно содержит кодировку лямбда-исчисления. Анонимные функции соответствуют лямбда-выражениям, за исключением того, что в функциях LC всегда есть ровно один аргумент. Однако любой язык, полный по Тьюрингу, эквивалентен LC, поэтому LC всегда можно реализовать поверх таких языков. Это обычно происходит в системах сопоставления правил или чрезмерно интеллектуальных форматах конфигурации, приводя к «десятому правилу Гринспуна» (в шутку - в основном): « Любая достаточно сложная программа на C или Fortran содержит специальную, неофициально заданную, подверженную ошибкам , медленная реализация половины Common Lisp. »

Амон
источник
Это лучший ответ, чем тот, который я выбрал раньше. Ваш ответ действительно попадает домой. Это именно то, что я искал!
Рональд Мунодавафа,
«... за исключением того, что в функциях LC всегда есть ровно один аргумент»: эта функция называется каррированием или, по крайней мере, связана с ней?
Джорджио
@Giorgio Curry отличается, но связан. LC не имеет функций с несколькими аргументами, но они могут быть просто закодированы как вложенные функции, каждый из которых принимает один аргумент. Пример, использующий нотацию ML: x = fn (a, b, c) => a + b + c(тип int * int * int -> int, вызов fn (1, 2, 3)) может быть преобразован в x = fn a => fn b => fn c => a + b + c(тип int -> int -> int -> int, вызов ((x 1) 2) 3- parens необязательно в ML). Теперь вместо того, чтобы предоставить все три аргумента, мы также можем предоставить только два: plus3 = x 1 2которые имеют тип int -> int. Это частичное приложение / карри.
Амон
Я думал, что карри означает, что все функции принимают только один аргумент (как в LC).
Джорджио
8

Лямбда-исчисление не имеет ничего общего с дифференциальным / интегральным исчислением. Исчисление в самом общем смысле этого слова означает просто систему расчетов.

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

Наиболее прямое влияние лямбда-исчисления на языки программирования обычно проявляется в форме функций и замыканий первого класса. В C нет поддержки замыканий, поэтому вам нужно изучить эту концепцию на более высокоуровневом языке, таком как Lisp, Python, Ruby, JavaScript и т. Д. Исторически Lisp считается первой конкретной реализацией лямбда-исчисления как языка программирования. ,

davidk01
источник
1
Вы можете упомянуть конкретные языки, которые очень близки к лямбда-исчислению, например Lisp.
Джорджио
1
Я все еще изучаю Scheme с использованием SICP и надеюсь, что узнаю больше об этой области. Спасибо за ваш сложный ответ и предложение.
Рональд Мунодавафа