deniok

Что-то мне эта версия непонятна. Скобочек по-моему не хватает в одном месте...

А что летом у вас было?

From:

Там были алгоритмы Маркова на самом деле, но поскольку я о них кроме названия ничего не знаю, то делали лямбда-исчисление :)
А откуда у тебя в журнале реклама? От неё фокс глючит.

From:

Там - это где? Я не в курсе совершенно...

Реклама у меня из-за улучшенного аккаунта, а он из-за желания иногда картинок выложить. Я бы и платный оплатил - только лень и не знаю как :)

From:

на icfpc2007

From:

F = (\g. \m. m g g) (\g'. \m'. m' g' g')
Так?

From:

Ну это-то альфа-конверсия, она и так подразумевается где надо; а в конце всё равно не получается:

FM = (\g. \m. m g g) (\g'. \m'. m' g' g') M 
   = M (\g'. \m'. m' g' g') (\g'. \m'. m' g' g')
   фиг а не = M F, аппликация левоассоциативна

На самом деле чтобы сошлось надо

F = GG
G = \g m . m (g g)

но лучше не изобретать Y-подобный велосипед, а сразу им (Y) пользоваться, как

lomeo.

From:

Дык, это если Y уже есть. То есть, совет невеждам не подходит. :)

From:

Ну Y это средоточие всех тайн и загадок. Держи:

Теорема 1. Для любого терма F существует терм X, такой что

FX = X

Этот X мудрецы зовут неподвижной точкой.
Доказательство: Введём

G = \x.F(xx)

тогда искомая неподвижная точка

X = GG

Воистину, это так

X = GG 
  = (\x.F(xx))(\x.F(xx)) 
  = F((\x.F(xx))(\x.F(xx))) 
  = F(GG)
  = FX

From:

Теорема 2 Существует комбинатор неподвижной точки Y,

Y=\f.(\x.f(xx))(\x.f(xx))

такой что для любого F

F(YF)=YF

Доказательство: Из предыдущей теоремы замечаем, что

YF = (\x.F(xx))(\x.F(xx)) 
   = GG
   = X

From:

Как полный чайник, который интересуется ЛИ и функциональным программированием, не могу найти ответы на следующие вопросы:
А дальше что? Зачем нужны все эти неподвижные точки и Y-ки? Почему все так носятся с ними? Что пытаются доказать или выразить?

From:

Ну, если вы интересуетесь ЛИ, то непонятно, в чём вопрос. Как только мы ввели основные понятия (лямбда-терм с абстракцией и аппликацией) и задали схему бета-редукции, тут же Y и вылезает. Без него ЛИ не полное по Тьюрингу - арифметику, например, не задашь.

From:

Вопрос в том, что хочется видеть конечную цель. Без такого видения очень сложно отделять главное от шелухи. Вот задали арифметику, а потом что? Ради чего её задавали? Может быть есть какой-нибудь мануал, где бы уделялось место не вопросу "как", а "зачем"? Или без мощного математического бэкграунда в эту область лучше не соваться?

From:

Конечная цель - это очень индивидуально, нес па?

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

From:

Полностью с вами согласен насчёт индивидуальности цели. На что, по вашему мнению, мне стоит обратить особое внимание при изучени ФП, если я преследую цель повышения продуктивности и выразительности труда программиста? Не является ли утопией моя задумка иметь конвертор (Haskell, например) -> (C, например)?

From:

>На что, по вашему мнению, мне стоит обратить особое внимание при изучени ФП, если я преследую цель повышения продуктивности и выразительности труда программиста?

По-моему так задачек побольше решать надо: SICP, YAHT стоит прочесть и упражнения прорешать (ну второе, конечно, не такое заслуженно именитое как первое). Первое, кстати, многие люди делают не только на Схеме, но и, параллельно, на Хаскелле.

>Не является ли утопией моя задумка иметь конвертор (Haskell, например) -> (C, например)?

Не очень понятно, зачем. Компилятор GHC сам по себе и есть почти что такой конвертер. И потом Хаскелл всё-таки ленивый язык, ему сишная модель исполнения не очень подходит.

From: