Условный формализм МакКарти

предыдущая серия

Условные выражения будем конструировать в классическом стиле липсовода МакКарти.

В Си имеется тернарный оператор

условие ? выражение-1 : выражение-2

В Питоне тоже есть аналог:

выражение-1 if условие else выражение-2

Не забывая, что все значения в лямбда-исчислении — функции (в том числе и логические величины True/False), напишем вот такие определения:

TRUE = lambda true_value: lambda false_value: true_value
FALSE = lambda true_value: lambda false_value: false_value

Мы будем само условие трактовать как каррированную функцию с двумя параметрами (в клаузе if и в клаузе else):

условие(выражение-1)(выражение-2)

Тогда, соответственно, сам условный «оператор» IF запишется так:

IF = (lambda cond: lambda true_value: lambda false_value: cond(true_value)(false_value))

Это каррированная функция с тремя параметрами, первый из которых — это функция нашего «типа» TRUE/FALSE, а два других — соответствующие возвращаемые значения для вариантов истина/ложь.

Так, выражение

IF(TRUE)(+1)(-1)

вернёт +1, а выражение

IF(FALSE)(+1)(-1)

вернёт -1.

Однако нам требуется в качестве условия задавать произвольную функцию, а не «константы» TRUE/FALSE. Как это сделать?

Возможное непонимание тут связано с тем, что мы рассматриваем бестиповое лямбда-исчисление. Многое станет сразу понятнее, как только мы условимся, что TRUE/FALSE — это «значения» логического типа. Соответственно, в качестве условия требуется функция, которая возвращает логическую величину.

В простейшем случае она может быть такой:

POSITIVE = lambda x: TRUE if x>=0 else FALSE

А вот таким — её вызов:

IF(POSITIVE(-1))(+1)(-1) # -1

Подобная схема, применяющаяся в Лиспе, известна как формализм МакКарти, который был отмечен в легендарной книге Марвина Мински «Вычисления: конечные и бесконечные машины», выпущенной в 1967 году.

следующая серия

Поделиться статьей ...Share on Facebook0Share on Google+0Tweet about this on TwitterShare on LinkedIn0Share on VKPrint this page

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *