Я начинаю свой первый год (в колледже) в области компьютерных наук в следующем году, и я пишу в основном на C (если это имеет значение). Я пробовал искать, но большая часть того, что я нашел, предполагает знание лямбда-исчисления. Почему при программировании лямбда-исчисление считается гораздо более полезным, чем исчисление с одной переменной? Есть ли связь между лямбда-выражениями и функциональными программами? Была ли работа Алонзо Черча по лямбда-исчислению, которая повлияла на развитие языков программирования?
Все за пределами школы постоянно жужжат об этом, и я понятия не имею, о чем они будут говорить, хотя я очень хочу выучить это и посмотреть, как это напрямую связано с моим программированием и пониманием языков программирования.
programming-languages
computer-science
lambda-calculus
RonaldMunodawafa
источник
источник
Ответы:
Лямбда-исчисление является интересным, элегантным и значительно облегчает понимание функциональных языков программирования. Тем не менее, вы не столкнетесь с LC в типичном курсе бакалавриата по CS, поэтому вам не нужно изучать его прямо сейчас - я бы рекомендовал сначала поэкспериментировать с функциональными языками, прежде чем пересматривать Lambda Calculus. Я считаю, что OCaml является хорошей отправной точкой в функциональном программировании для программиста на C, и что Scheme является хорошей отправной точкой для погружения в Lambda Calculus.
Лямбда-исчисление не связано с исчислением (которое вместо этого следует называть анализом). В общем, исчисление - это «формальная система», то есть набор правил, чтобы что-то делать. В то время как дифференциальное исчисление предоставляет правила, касающиеся изменения значений, правила лямбда-исчисления описывают само вычисление. Из этого набора базовых правил мы можем строить произвольные вычисления, представления данных, такие как логические значения, целые числа или списки, и даже конструкции потока управления, такие как условные выражения или циклы. LC эквивалентен машинам Тьюринга, но у любой модели есть свои сильные стороны.
Лямбда-исчисление оказало огромное влияние на языки программирования. Вторым языком высокого уровня, который должен быть реализован, был Lisp, который можно понимать как прямое кодирование LC в язык программирования. Это «функциональное программирование» оказывает огромное влияние на развитие языков программирования. Такие функции, как анонимные функции, указатели на функции, замыкания (вложенные функции), сборка мусора, область видимости переменных, метапрограммирование, усовершенствования в системах типов, вывод типов, интерпретируемые языки, языки с динамической типизацией, объектно-ориентированное программирование - все это во многом обусловлено к функциональной ветви программирования языков программирования. Есть шутка, что любой новый (не академический) язык программирования добавляет только те функции, которые Lisp уже имел в течение десятилетий.
Кроме того, лямбда-исчисление и другие связанные исчисления являются незаменимыми инструментами в теории языка программирования и в некоторых методах построения компилятора.
Любой язык, который имеет анонимные функции, которые ведут себя как замыкания и могут свободно передаваться, немедленно содержит кодировку лямбда-исчисления. Анонимные функции соответствуют лямбда-выражениям, за исключением того, что в функциях LC всегда есть ровно один аргумент. Однако любой язык, полный по Тьюрингу, эквивалентен LC, поэтому LC всегда можно реализовать поверх таких языков. Это обычно происходит в системах сопоставления правил или чрезмерно интеллектуальных форматах конфигурации, приводя к «десятому правилу Гринспуна» (в шутку - в основном): « Любая достаточно сложная программа на C или Fortran содержит специальную, неофициально заданную, подверженную ошибкам , медленная реализация половины Common Lisp. »
источник
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
. Это частичное приложение / карри.Лямбда-исчисление не имеет ничего общего с дифференциальным / интегральным исчислением. Исчисление в самом общем смысле этого слова означает просто систему расчетов.
На очень высоком уровне лямбда-исчисление является моделью вычислений так же, как машина Тьюринга является моделью вычислений. Причина, по которой исследователи языка программирования изучают лямбда-исчисление, заключается в том, что в качестве модели он тесно связан с формальными методами математики, такими как логика и теория категорий. Таким образом, методы из этих областей могут применяться для изучения различных аспектов и расширений лямбда-исчисления, что, в свою очередь, помогает создавать лучшие языки программирования с определенными свойствами.
Наиболее прямое влияние лямбда-исчисления на языки программирования обычно проявляется в форме функций и замыканий первого класса. В C нет поддержки замыканий, поэтому вам нужно изучить эту концепцию на более высокоуровневом языке, таком как Lisp, Python, Ruby, JavaScript и т. Д. Исторически Lisp считается первой конкретной реализацией лямбда-исчисления как языка программирования. ,
источник