Лямбда, которую мы потеряли

[deniok]

Пара задачек по лямбда-исчислению.

(1) Сконструируйте лямбда-терм F, такой что для любого терма M выполнялось бы

FM = MF

(2) Сконструируйте лямбда-терм G, такой что для любых термов M и N выполнялось бы

GMN = NG(NMG)

Ответы не скринятся, так что если хотите думать сами - не смотрите в комменты.

Comments

[deni-ok.livejournal.com]

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

[kernelring.livejournal.com]

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

[deni-ok.livejournal.com]

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

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

[kernelring.livejournal.com]

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

[deni-ok.livejournal.com]

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

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

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

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

[kernelring.livejournal.com]

Спасибо за советы.
>Не очень понятно, зачем
В данном случае просто интересно провернуть такую комбинацию:
исходник на Haskell->конвертор->исходник на С->целевое окружение, для которого ещё нет (и скорее всего не будет в ближайшее время) поддержки Haskell runtime.
А эту ленивость можно обойти? Не пользоваться ей, например? Или без ленивости получится как в С без указателей? :-)

[deni-ok.livejournal.com]

>А эту ленивость можно обойти?

Обойти-то всё можно, только зачем тогда Хаскелл?