Лямбда-исчисление вне функционального программирования?

21

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

Во-вторых, есть ли смысл в использовании Lambda Calculus в области компьютерных наук, но за пределами функциональных языков программирования?

Иаков
источник

Ответы:

15

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

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

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

Дэйв Кларк
источник
Большое спасибо за ваш ответ, Дэйв. Я думаю, что формальная проверка - лучшая причина, поскольку лямбда-исчисление полезно для меня, и, как ни странно, в следующем семестре я проведу курс по формальной проверке. Вы бы также использовали лямбда-исчисление для формальной проверки программного обеспечения, написанного на любом языке, например, императивном или объектно-ориентированном?
Джейкоб
1
Вы не можете использовать лямбда-исчисление непосредственно при выполнении формальной проверки, но оно появится в основе формальной проверки. Написание спецификаций часто включает в себя написание на функциональном языке, даже для императивного / OO-кода.
Дейв Кларк
Хорошо, это интересно, спасибо, теперь у меня есть немного больше причин для изучения этого. Знаете ли вы, используется ли лямбда-исчисление для разработки каких-либо нефункциональных языков (на более низких уровнях)?
Джейкоб
1
Алгол. Scala. В конечном итоге на ваш вопрос сложно ответить. Лямбда-исчисление стало частью общеизвестного знания (большинства) языковых дизайнеров, и поэтому оно влияет на языковой дизайн, даже если он явно не используется. Рассмотрим блоки в Smalltalk или Ruby, анонимные классы в Java. Это замыкания, которые тесно связаны с функциями высшего порядка в лямбда-исчислении.
Дейв Кларк
Хорошо, большое спасибо, Дэйв, это очень ценится.
Джейкоб
17

Вы запрашиваете приложение вне компьютерных наук и логики. Это легко найти, например, в алгебраической топологии удобно иметь декартову замкнутую категорию пространств, см. Удобную категорию топологических пространств на nLab. Формальным языком, соответствующим декартовым замкнутым категориям, является -калькулус. Позвольте мне проиллюстрировать на простом примере, как это удобно.λ

Во-первых, в качестве разминки предположим, что кто-то спрашивает вас, есть ли функция определенная как дифференцируемо. На самом деле вам не нужно доказывать, что это так, вы просто наблюдаете, что это состав дифференцируемых функций, следовательно, дифференцируемых. Другими словами, вы сделали простой вывод, основанный на форме определения. f ( x ) = x 2 e x + log ( 1 + x 2 )f:RRf(x)=x2ex+log(1+x2)

Теперь для реального примера. Предположим, кто-то спрашивает вас, есть ли функция определенная как непрерывен. Опять может сразу ответить «да», потому что функция определяется с помощью -calculus и начинается с непрерывных отображений , , и т. д.f:RR

f(x)=(λf:C(R).xxf(1+t2)dt)(λy:R.max(x,sin(y+3))
λmaxsin

Различные расширения -calculus позволяют делать то же самое в других областях. Например, поскольку гладкий топос является декартовой замкнутой категорией, любая карта, которая определяется с помощью -calculus, начиная с производных и кольцевой структуры вещественных чисел (и вы можете добавить экспоненциальную функцию, если хотите), автоматически гладкий; плавный. (На самом деле, основной смысл гладких топосов - это существование нильпотентных бесконечно малых величин, которые позволяют вам осмысленно говорить такие вещи, как «мы разбиваем диск на бесконечно тонкие равнобедренные треугольники».)λλ

Андрей Бауэр
источник
1
Спасибо за подробный ответ. На самом деле я пытался найти применение лямбда-исчислению в компьютерных науках, но за пределами функционального программирования, извинения, если это не было ясно. Я изменил вопрос, чтобы более четко изложить это.
Джейкоб
Ах, очень плохо, я бы написал подробный ответ об этом.
Андрей Бауэр
Извиняюсь за это. Не стесняйтесь добавлять любые комментарии, если вы хотите добавить дополнительную информацию :)
Jacob
2
Я думаю, что вопрос Дейва в порядке, мне нечего добавить. Если вы хотите посмотреть, какие захватывающие вещи вы можете сделать с помощью -calculus, возможно, вы сможете взглянуть на невозможные функционалы. Но, как общий ответ, Дейв очень хорош. λ
Андрей Бауэр
7

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

Конечно, можно быть очень хорошим программистом, не зная о -calculus, но вам не хватает чего-то прекрасного, что также очень полезно.λ

Мартин Бергер
источник
5

Microsoft LINQ (Language INtegrated Query) привносит функциональные возможности программирования в процедурные языки. Он широко использует -calculus для распутывания зависимостей и разделения частей дерева выражений, которые могут быть делегированы на сервер базы данных. Это чрезвычайно практичное приложение с высокой коммерческой ценностью.λ

Я написал небольшое коммерческое приложение, используя функциональный язык, и я могу заверить вас, что, несмотря на то, что оно полезно для ученых и исследователей, они менее полезны в коммерческом отношении, чем их процедурные родственники. На самом деле это вопрос лошадей для курсов, и наиболее практичным из всех является язык, который может быть процедурным или функциональным по мере необходимости. Как следствие, функциональные возможности, которые были введены (в C #) для поддержки LINQ, такие как -expressions, довольно широко используются вне контекста запросов к базе данных.λ

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

Питер Воне
источник
2

Не зная больше об этом, я слышу, что лингвисты используют лямбда-исчисление.

http://www.sfu.ca/~jeffpell/Ling406/LambdaAbstractionOH.pdf , https://files.nyu.edu/cb125/public/Lambda/

Лукас Ритц
источник
11
Не могли бы вы обобщить, что находится за ссылками? Они имеют тенденцию ломаться. Это также сделает ваш ответ более автономным.
Юхо