Лямбда-исчисление. Денис Николаевич Москвин. СПбАУ РАН, CS Center. План лекции. 1 Функциональное vs императивное . Просто типизированное лямбда-исчисление. Денис Москвин. Системы в стиле Карри лямбда-исчисление с присваива-. Вообще говоря, лямбда-исчисление не относится к предметам. Так лямбда-исчисление впервые громко заявило о себе, но ещё пару. Антон Холомьёв · Лекции по функциональному программированию. Нальные языки программирования. Лямбда-исчисление было изобретено в начале 30-х годов логиком. Черчем, который надеялся использовать его в .

Смысловая составляющая осталась прежней. Вступление. Возможно, у этой системы найдутся приложения не тольков роли логического исчисления. Это такая теоретическая штука, изучение которой необходимо, когда вы собираетесь заняться исследованием систем типов или хотите создать свой функциональный язык программирования. Тем не менее, если у вас есть желание разобраться в том, что лежит в основе Haskell, ML и им подобных, «сдвинуть точку сборки» на написание кода или просто расширить свой кругозор, то прошу под кат. Начнём мы с традиционного (но краткого) экскурса в историю.

В 3. 0- х годах прошлого века перед математиками встала так называемая проблема разрешения (Entscheidungsproblem), сформулированная Давидом Гильбертом. Суть её в том, что вот есть у нас некий формальный язык, на котором можно написать какое- либо утверждение. Существует ли алгоритм, за конечное число шагов определяющий его истинность или ложность? Ответ был найден двумя великими учёными того времени Алонзо Чёрчем и Аланом Тьюрингом. Они показали (первый — с помощью изобретённого им . Entscheidungsproblem в общем случае неразрешима.

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

План лекции. Y-комбинатор позволяет ввести рекурсию в . Лямбда-терм может иметь одну из двух форм:

В этом смысле оно созвучно машине Тьюринга, только соответствует функциональной парадигме, а не императивной. Мы с вами рассмотрим его наиболее простую форму: чистое нетипизированное лямбда- исчисление, и вот что конкретно будет в нашем распоряжении. Термы: переменная: xлямбда- абстракция (анонимная функция): . Действительно, в мире чистого лямбда- исчисления возвращаемое функцией значение тоже может быть функцией. Следовательно, мы можем применить первоначальную функцию только к одному её аргументу, «заморозив» прочие.

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

Выглядеть это будет примерно так: f = . Преобразование закончено. Переменная x называется связанной, если она находится в теле t .

Если же x не связана какой- либо вышележащей абстракцией, то её называют свободной. Например, вхождения x в x y и .

Если все переменные в терме связаны, то его называют замкнутым, или комбинатором. Мы с вами будем использовать следующий простейший комбинатор (функцию тождества): id = .

Она не выполняет никаких действий, а просто возвращает без изменений свой аргумент. Процесс вычисления. Рассмотрим следующий терм- применение: (.

Каждый шаг вычисления будет заключаться в замене всех вхождений переменной x внутри t на y. Терм- применение такого вида носит имя редекса (от reducible expression, redex — «сокращаемое выражение»), а операция переписывания редекса в соответствии с указанным правилом называется бета- редукцией. Существует несколько стратегий выбора редекса для очередного шага вычисления. Рассматривать их мы будем на примере следующего терма: (. В этом случае каждый раз редекс внутри вычисляемого терма выбирается произвольным образом. Первым всегда сокращается самый левый, самый внешний редекс.

Вызов по имени. Порядок вычислений в этой стратегии аналогичен предыдущей, но к нему добавляется запрет на проведение сокращений внутри абстракции. Это так называемые «ленивые» вычисления. Мультфильмы Кряк Бригада И Бурундуки на этой странице. Вызов по значению. Здесь сокращение начинается с самого левого (внешнего) редекса, у которого в правой части стоит значение — замкнутый терм, который нельзя вычислить далее. Для чистого лямбда- исчисления таким термом будет .

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

Рассмотрим для примера выражение (. На её- то вычислении и зависнет стратегия вызова по значению, в то время как стратегия вызова по имени начнёт с самого внешнего терма и там определит, что второй аргумент не нужен в принципе. Вывод: если у редекса есть нормальная форма, то «ленивая» стратегия её обязательно найдёт.

Ещё одна тонкость связана с именованием переменных. Например, терм (. Действительно, назови мы локальную переменную не y, а z — первоначальный терм имел бы вид(.

Для исключения неоднозначностей такого рода надо чётко отслеживать, чтобы все свободные переменные из начального терма после подстановки оставались свободными. С этой целью используют . В этом случае данное выражение будет эквивалентно просто t.

Такое преобразование называется . На этом закончим вводную в лямбда- исчисление. В следующей статье мы займёмся тем, ради чего всё и затевалось: программированием на.