Способы реализации рекурсии

В рассмотренных нами методах (в редукции графов и в суперкомбинаторах)

рекурсия осуществляется по именам, т.е. имеем дело с именованными выражениями.

Пример.

ƒac n: if n=Ø 1 n*ƒac(n-1)

λn.if n= Ø 1 n*ƒac(n-1)

1)Редукция графа:

Разворачиваем тело графа.

Суперкомбинаторы (рекурсия):

letrec ƒ=N(ƒ) M

letrec ƒac=(λn.if n= Ø 1 n*ƒac(n-1))(ƒac3)(λƒac.(ƒac3))(λn.if n= Ø 1 n*ƒac(n-1))

Контрольные вопросы

1. Приведите общую схему реализации аппликативных языков.
2. Какие новые конструкции введены в расширенное λ–исчисление по сравнению с традиционным?
3. Дайте определение глубины связывания переменной.
4. Постройте и редуцируйте граф разбора для выражения (λxy.+ x y)7((λx.x)12)
5. Приведите к суперкомбинаторному виду выражение (λx.+ x ((λy.x)5))
6. Какими средствами организуется рекурсия для суперкомбинаторных выражений?

Дата добавления: 2014-01-11