Примеры решения задач

Задача 11.1. Выражение расширенного лямбда-исчисления представлено следующим определением типа данных, описанным в параграфе 11.1:

data Ехрг =

Integral Integer | — целые константы.

Logical Bool | — логические константы.

Function String | — идентификаторы примитивных функций.

Variable String | — переменная.

Lambda String Expr | — лямбда-выражение.

Application Expr Expr | — применение функции.

Let String Expr Expr | — простой блок.

Letrec [ (String, Expr)] Expr — рекурсивный блок Опишите функцию, выполняющую а-преобразование в заданном выражении, заменяя все свободные вхождения переменной с заданным именем на переменную с другим заданным именем.

Решение. Переменная будет свободной, если она не связана. Связывание имен переменных происходит в выражениях, определяемых конструкторами Lambda, Let и Letrec. Если имя переменной, подлежащей переименованию, совпадает с именем, упомянутым в заголовках соответствующих конструкций, то внутри этих конструкций переменная уже не будет свободной. Отсюда сразу же следует определение искомой функции: alpha:: String -> String -> Expr -> Expr alpha old new e@ (Variable x) | x == old = Variable new.

| otherwise = e.

alpha old new (Application el e2) = Application (alpha old new el).

(alpha old new e2).

alpha old new e0 (Lambda x body).

| x == old = e.

| otherwise = Lambda x $ alpha old new body alpha old new (Let x el e2).

| x == old = Let x (alpha old new el) e2 | otherwise = Let x (alpha old new el) (alpha old new e2) alpha old new e@(Letrec pairs body).

| old 'elem' (map fst pairs) = e.

I otherwise = Letrec (map rename pairs) $ alpha old new body where rename (name, expr) = (name, alpha old new expr) alpha _ _ e = e.

Обратите внимание, что при обработке простого (нерекурсивного) блока связывание переменной происходит только в теле блока, но не в заголовке. Это означает, что, скажем, в выражении let х = х+1 in х+2 в части х+1 переменная х — свободная, а в части х+2 — связанная.

Задача 11.2. В выражении, заданном описанием типа данных, предложенном в задаче 11.1, проведите упрощение выражений, содержащих арифметические действия сложения, умножения и вычитания с константами. Упрощению подлежат следующие виды выражений:

• • 0 * е, е * 0 ^ О
• • 1 * е, е * 1 —> е
• • 0 + е, е + 0 -> е
• • е — 0 -" е

Решение. Задача несложная, она сводится к анализу формы выражений, в которых примитивная функция применяется к операндам специального вида. Единственная трудность состоит в том, чтобы не проводить анализ одних и тех же выражений повторно. При преобразовании такого выражения, как (1 * е) * (е * 0), нужно сначала понять, что операнды внешней операции умножения сводятся к выражениям е и 0 соответственно, а потом уже привести все выражение к нулю. Иными словами, анализ внешней конструкции применения функции следует проводить уже после того, как обработаны операнды.

Выражения указанного вида имеют следующее представление в виде конструкции типа Ехрг:

Application (Application (Function f) el) e2.

где f — идентификатор одной из трех примитивных функций «+ «, или Функция simplify, решающая задачу, может иметь следующий вид:

simplify: Ехрг -> Ехрг.

simplify (Lambda х body) = Lambda х (simplify body) simplify (Let x el e2) = Let x (simplify el) (simplify e2) simplify (Letrec pairs body) =.

Letrec (map simple pairs) $ simplify body where simple (name, expr) = (name, simplify expr) simplify (Application (Application (Function f) el) e2) = case (f, sel, se2) of

(«*», e, Integral 0) -> Integral 0.

Integral 0, e) -> Integral 0.

• («*», e, Integral 1) -> e
• («*», Integral 1, e) -> e
• («+ «, e, Integral 0) -> e
• («+», Integral 0, e) -> e
• («-», e, Integral 0) -> e
• -> Application (Application (Function f) sel) se2 where sel = simplify el se2 = simplify e2 simplify (Application el e2) =

Application (simplify el) (simplify e2) simplify e = e.

Задача 11.3. Рассмотрим следующее определение тина данных Ехрг:

data Ехрг =.

Integral Integer I — целые константы.

Logical Bool I — логические константы.

Function String | — идентификаторы примитивных функций.

Variable String | — переменная.

Lambda String Expr | — лямбда-выражение.

Application Expr Expr | — применение функции.

Let String Expr Expr — блок В этом определении есть только один тип блока. Будем считать, что в общем случае он может быть рекурсивным, т. е. идентификатор, упомянутый в заголовке блока, может быть использован не только в теле блока, но и рекурсивно в определяющем выражении. Считая Y-комбинатор примитивной функцией с идентификатором Y, напишите функцию преобразования произвольного выражения, которая исключает из выражения блоки, заменяя рекурсивный блок на выражение, содержащее Y-комбинатор, а нерекурсивный блок — на эквивалентную конструкцию применения лямбда-выражения к аргументу.

Решение. Прежде всего, необходимо определить, каким является блок — простым или рекурсивным. Блок будет рекурсивным, если переменная, определяемая в заголовке блока, имеет свободное вхождение в выражение, определяющее эту переменную. В этом случае рекурсивный блок let х = el in е2 преобразуется в нерекурсивный блок let х = Y (Хх. el) in е2. В свою очередь, нерекурсивный блок let х = el in е2 может быть преобразован в выражение (Лх.е2) el. Как и в предыдущих задачах, внутренние части других сложных конструкций подлежат преобразованию, при этом вид внешней конструкции не меняется.

Функция, определяющая, есть ли в выражение свободное вхождение заданной переменной, может иметь вид.

free:: String -> Expr -> Bool free x (Variable у) = x == у.

free x (Lambda у body) = x /= у && free x body free x (Application el e2) = free x el II free x e2 free x (Let у el e2) = x /= у && (free x el II free x e2) free _ e = False.

Тогда функция преобразования выражения, исключающая из него блоки, может быть записана следующим образом:

convert: Expr -> Expr.

convert (Lambda x body) = Lambda x $ convert body.

convert (Application el e2) = Application (convert el) (convert e2).

convert (Let x el e2) | free x el =.

convert (Let x (Application (Function «Y») (Lambda x el)) e2).

I otherwise =.

convert (Application (Lambda x e2) el) convert e = e.

В этом решении может представлять интерес то, как сначала рекурсивный блок преобразуется в нерекурсивный, а затем функция применяется повторно для того, чтобы уже преобразовать полученный нерекурсивный блок в применение лямбда-выражения. Фактически, можно сделать функцию несколько более эффективной, если преобразование блоков делать не в два этапа, а в один. Правда, уравнение для преобразования блока при этом получается более сложным: convert (Let х el е2) I free х el =.

Application (Lambda x (convert e2)).

(Application (Function «Y»)(Lambda x (convert el))).

| otherwise =.

Application (Lambda x (convert e2)) (convert el).