Вопросы с тегом «lambda-calculus»

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

44
Как комбинатор Y иллюстрирует «несоответствие лямбда-исчисления»?

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

35
Квантовое лямбда-исчисление

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

29
Характеристика лямбда-терминов, которые имеют типы объединения

Многие учебники охватывают типы пересечений в лямбда-исчислении. Правила набора для пересечения могут быть определены следующим образом (поверх простого типа лямбда-исчисления с подтипами): Γ ⊢ M: T1Γ ⊢ M: T2Γ ⊢ M: T1∧ T2( ∧ я)Γ ⊢ M: ⊤( ⊤ я)Γ⊢M:T1Γ⊢M:T2Γ⊢M:T1∧T2(∧I)Γ⊢M:⊤(⊤I) \dfrac{\Gamma \vdash M...

29
Является ли лямбда-исчисление чисто синтаксическим?

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

28
Понятный, интуитивно понятный вывод комбинатора с фиксированной точкой (Y комбинатор)?

Комбинатор FIX с фиксированной запятой (он же Y-комбинатор) в (нетипизированном) лямбда-исчислении ( λλ\lambda ) определяется как: FIX ≜λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))≜λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))\triangleq \lambda f.(\lambda x. f~(\lambda y. x~x~y))~(\lambda x. f~(\lambda y....

26
Есть ли типизированное исчисление SKI?

Большинство из нас знает соответствие между комбинаторной логикой и лямбда-исчислением . Но я никогда не видел (может быть, я недостаточно глубоко изучил) эквивалент «типизированных комбинаторов», соответствующих простейшему типу лямбда-исчисления. Существует ли такая вещь? Где можно найти...

23
калькуляция с отражением

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

22
Почему функциональные языки Тьюринга завершены?

Возможно, мое ограниченное понимание предмета неверно, но это то, что я понимаю до сих пор: Функциональное программирование основано на лямбда-исчислении, сформулированном Алонзо Черчем. Императивное программирование основано на модели машины Тьюринга, созданной Аланом Тьюрингом, учеником Черча....

21
Что такое бета-эквивалентность?

В сценарии, который я сейчас читаю по лямбда-исчислению, бета-эквивалентность определяется следующим образом: -эквивалентность является наименьшей эквивалентности , который содержит .ββ\beta≡β≡β\equiv_\beta→β→β\rightarrow_\beta Я понятия не имею, что это значит. Может кто-нибудь объяснить это более...

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

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

19
Базисные наборы для комбинаторного исчисления

Хорошо известно, что комбинаторы S и K образуют базис для исчисления комбинаторов в том смысле, что все другие комбинаторы могут быть выражены через них. Существует также базис Карри B, C, K, W, который обладает тем же свойством. Таких баз должно быть бесконечное количество, но я не знаю других....

19
Почему важно, чтобы функции были анонимными в лямбда-исчислении?

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

18
Лямбда-исчисление не казалось абстрактным. И я не вижу смысла в этом

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

16
Изучение теории языка программирования

Недавно я чрезвычайно заинтересовался пониманием и доказательством аспектов (функциональных) языков программирования. Однако, как я углублюсь в глубину, такие вещи, как исчисление , теория категорий и денотационная семантика, немного трудно найти без надлежащего объяснения.λλ\lambda Я читаю SICP...

14
«Аппликативный порядок» и «Нормальный порядок» в лямбда-исчислении

Аппликативный порядок: всегда полностью оценивайте аргументы функции перед оценкой самой функции, например: (λx.x2(λx.(x+1)  2)))→(λx.x2(2+1))→ (λx.x2(3))→ 32 → 9(λx.x2(λx.(x+1)  2)))→(λx.x2(2+1))→ (λx.x2(3))→ 32 → 9(\lambda x. x^2(\lambda x.(x+1) \ \ 2))) \rightarrow (\lambda x....

14
Представление отрицательных и комплексных чисел с использованием лямбда-исчисления

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

14
Есть ли рецензируемые статьи, в которых рассматриваются плюсы и минусы функционального программирования?

Может ли кто-нибудь отослать меня к рецензируемым статьям, изучающим преимущества или недостатки написания кода в функциональном стиле? Существуют ли документы, в которых обсуждается применение лямбда-исчисления в таких областях, как машинное обучение, языковой дизайн и т....

14
Решение функциональных уравнений для неизвестных функций в лямбда-исчислении

Существуют ли методы решения функциональных уравнений для неизвестных функций в лямбда-исчислении? Предположим, у меня есть функция тождества, определенная как таковая: Ix=xIx=xI x = x (то есть, записывая уравнение для ожидаемого поведения этой функции) , и теперь я хочу , чтобы решить эту проблему...