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

Задача 12.1. Функция соединения списков (++) в языке Haskell может быть определена уравнениями [] ++ list = list.

(x:listl) ++ list2 = x: (listl ++ list2).

Скомпилируйте определение этой функции в коды SECD-машины низкого уровня.

Решение. Функция соединения списков определена рекурсивно, так что в расширенном лямбда-исчислении она может быть выражена с помощью рекурсивного блока либо применения Y-комбинатора. Определение функции с помощью рекурсивного блока может выглядеть гак: let join = Xsl. Xs2.if null si then s2 else

cons (head si) (join (tail si) s2) in join Функции null, head, tail и cons считаем примитивными функциями над списками.

Будем представлять это выражение в виде значения типа Ехрг, обозначая отдельные элементы выражения идентификаторами. В результате может получиться следующий набор определений на языке Haskell: thenPart = Variable «s2» .

elsePart = Application (Application (Function «cons»).

• (Application (Function «head»)(Variable «si»)))
• (Application (Application (Function «join»)
• (Application (Function «tail»)(Variable «si»)))(Variable «s2»))

body = If (Application (Function «null»)(Variable «si»)) thenPart elsePart.

letrec = Letrec [(«join», Lambda «si» (Lambda «s2» body))] (Variable «join»).

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

" compile letrec.

[Dummy, LoadConst (List []), LoadFunc [LoadFunc [Load (1,0), LoadSect «null», Apply, Select [Load (0,0)] [Load (0,0), Load (1,0), LoadSect «tail», Apply, LoadSect «join», Apply, Apply, Load (1,0), LoadSect «head», Apply, LoadSect «cons», Apply, Apply], Return],.

Return], LoadSect «cons», Apply, Apply, LoadFunc [Load (0,0), Return], RecApply, Stop].

Это и есть требуемый результат компиляции.

Задача 12.2. Разработайте способ исключения сложной команды Select из списка команд SECD-машины низкого уровня, заменив ее простыми командами, не содержащими внутри себя других последовательностей команд.

Решение. Можно ввести команду Skip п, смысл которой состоит в том, чтобы пропустить исполнение следующих п команд из списка управления. Работу такой команды можно описать неформально следующим образом (здесь функция drop — это стандартная функция языка Haskell, отбрасывающая заданное количество начальных элементов списка):

(s, ctx, Skip n: c, d) —" (s, ctx, drop n c, d).

С помощью этой команды можно организовать «переходы вперед» по списку команд. Тогда команда Select может вообще не содержать операндов, а ее работа будет состоять в том, что она анализирует состояние вершины стека значений и, в зависимости от значения, хранящегося на вершине стека, пропускает или нет следующую команду:

• ((Boolean True):s, ctx, Select: cl:c, d) —" (s, ctx, c, d)
• ((Boolean False) :s, ctx, Select: cl:c, d) —> (s, ctx, cl: c, d) Теперь можно описать процесс компиляции условного выражения. Мы компилируем выражения, составляющие ветви условного выражения, и вычисляем число команд, которые получились после компиляции. После этого нужно добавить команды Skip в начало списка команд для каждой из ветвей, чтобы организовать обход одной из ветвей и исполнение другой ветви:
• (If cond eThen eElse) ** context =
• (cond ** context) ++
• (Select: Skip (n+1): compThen) ++
• (Skip m: compElse) where compThen = eThen ** context compElse = eElse ** context n = length compThen m = length compElse

Задачи для самостоятельного решения

Задача 12.3. Скомпилируйте в коды команд SECD-машины низкого уровня программу для вычисления факториала числа 100.

Задача 12.4. Внесите в компилятор, представленный в листинге 12.1, изменения согласно решению задачи 12.2. Используйте модифицированный таким образом компилятор для решения задач 12.1 и 12.3.