Просто типизированное лямбда-исчисление

[deniok]

Сделал в ру-Википедии статью про сабж. Еле поспел к Рождеству.  Держите.

Comments

[nivanych.livejournal.com]

Годно. Опечаток не заметил.
Хотя и чем дальше, чем больше, я лично к лямбдам отношусь всё более не очень хорошо ;-)

[nivanych.livejournal.com]

Ну вот ещё, к чему этот экстремизм, это расжигание! ;-)

[juan-gandhi.livejournal.com]

Бета-редуцируй.

Спасибо за статью.

[thedeemon.livejournal.com]

А что вместо них? Пи и сигма?

[nivanych.livejournal.com]

;-) Алгорифм Маркова.

[nponeccop.livejournal.com]

;-) Грамматики, конечно же

[thedeemon.livejournal.com]

Есть что почитать на эту тему?
Примерно в эту сторону у меня давно мысли крутятся, но не уверен, что мы об одном и том же.

[nivanych.livejournal.com]

Если я правильно понятно, то это всякие вариации rewriting'ов.
Если уже даже перепись строчки можно сделать Тьюринг-полной, то деревья и подавно.
Ну и плюс к тому, алгорифм Маркова, это по сути и есть грамматика нулевого типа.
Однако, я давно уже переболел ими ;-)

Я же хочу категорное.
По сравнению с лямбдами, разве что, для практики существеннен всякий scope.
А описание гораздо чище. И не надо приводить мне в сравнение хацкелевой бесточечный стиль.

[nponeccop.livejournal.com]

http://en.wikipedia.org/wiki/Chomsky_hierarchy
http://en.wikipedia.org/wiki/Rewriting

Можете почитать книгу parsing techniques (там, правда, совсем обзорно о тьюринг-полноте неограниченных грамматик) и про системы перезаписи в Plasmeier-Eckelen (системы перезаписи основаны на той же идее, что и грамматики, но эмуляция хаскеля более очевидна).

[thedeemon.livejournal.com]

А, это я читал уже.