Учебник по Haskell

очень часто применяется для построения компиляторов. Мы рассмотрели очень простой язык, но в более

сложном случае суть останется прежней. Дополнительный параметр позволяет нам закодировать в парамет-

ре тип функций нашего языка. Спрашивается: зачем нам дублировать вычисления в функции eval? Зачем нам

сначала кодировать выражение конструкторами, чтобы только потом получить то, что мы могли вычислить

и напрямую.

При таком подходе у нас есть полный контроль за деревом выражения, мы можем проводить дополни-

тельную оптимизацию выражений, если нам известны некоторые закономерности. Ещё функция eval может

вычислять совсем другие значения. Например она может по виду выражения составлять код на другом языке.

Возможно этот язык гораздо мощнее Haskell по вычислительным способностям, но беднее в плане вырази-

тельности, гибкости синтаксиса. Тогда мы будем в функции eval проецировать разные конструкции Haskell

в конструкции другого языка. Такие программы называются предметно-ориентированными языками програм-

мирования (domain specific languages). Мы кодируем в типе Exp некоторую область и затем надстраиваем

над типом Exp разные полезные функции. На самом последнем этапе функция eval переводит всё дерево

выражения в значение или код другого языка.

Отметим, что не так давно было предложено другое решение этой задачи. Мы можем закодировать типы

функций в классе:

class E exp where

true

:: exp Bool

false

:: exp Bool

iff

:: exp Bool -> exp a -> exp a -> exp a

val

:: Int -> exp Int

add

:: exp Int -> exp Int -> exp Int

mul

:: exp Int -> exp Int -> exp Int

Преимуществом такого подхода является модульность. Мы можем спокойно разделить выражение на две

составляющие части:

class (Log exp, Arith exp) => E exp

class Log exp where

true

:: exp Bool

false

:: exp Bool

iff

:: exp Bool -> exp a -> exp a -> exp a

class Arith exp where

val

:: Int -> exp Int

add

:: exp Int -> exp Int -> exp Int

mul

:: exp Int -> exp Int -> exp Int

Интерпретация дерева выражения в этом подходе заключается в создании экземпляра класса. Например

создадим класс-вычислитель Eval:

newtype Eval a = Eval { runEval :: a }

instance Log Eval where

256 | Глава 17: Дополнительные возможности

true

= Eval True

false

= Eval False

iff p t e = if runEval p then t else e

instance Arith Eval where

val

= Eval

add a b = Eval $ runEval a + runEval b

mul a b = Eval $ runEval a * runEval b

instance E Eval

Теперь проведём такую же сессию вычисления значений, но давайте теперь сначала определим их в тексте

программы:

notE :: Log exp => exp Bool -> exp Bool

notE x = iff x true false

squareE :: Arith exp => exp Int -> exp Int

squareE x = mul x x

e1 :: E exp => exp Int

e1 = squareE $ iff (notE true) (val 1) (val 2)

e2 :: E exp => exp Bool

e2 = notE true

Загрузим в интерпретатор:

*Exp> :r

[1 of 1] Compiling Exp

( Exp. hs, interpreted )

Ok, modules loaded: Exp.

*Exp> runEval e1

4

*Exp> runEval e2

False

Получились такие же результаты и в этом случае нам не нужно подключать никаких расширений. Теперь

создадим тип-принтер, он будет распечатывать выражение:

newtype Print a = Print { runPrint :: String }

instance Log Print where

true

= Print ”True”

false

= Print ”False”

iff p t e = Print $ ”if (” ++ runPrint p ++ ”) {”

++ runPrint t ++ ”}”

++ ”{” ++ runPrint e ++ ”}”

instance Arith Print where

val n

= Print $ show n

add a b = Print $ ”(” ++ runPrint a ++ ”)+(” ++ runPrint b ++ ”)”

mul a b = Print $ ”(” ++ runPrint a ++ ”)*(” ++ runPrint b ++ ”)”

Теперь распечатаем предыдущие выражения:

*Exp> :r

[1 of 1] Compiling Exp

( Exp. hs, interpreted )

Ok, modules loaded: Exp.

*Exp> runPrint e1

”(if (if (True) {False}{True}) {1}{2})*(if (if (True) {False}{True}) {1}{2})”

*Exp> runPrint e2

”if (True) {False}{True}”

При таком подходе нам не пришлось ничего менять в выражениях, мы просто заменили тип выражения

и оно автоматически подстроилось под нужный результат. Подробнее об этом подходе можно почитать на

сайте http://okmij.org/ftp/tagless-final/course/course.html или в статье Жака Каре (Jacques Carette), Олега Киселёва (Oleg Kiselyov) и Чунг-Че Шена (Chung-chieh Shan) Finally Tagless, Partially Evaluated.

Расширения | 257

Семейства типов

Семейства типов позволяют выражать зависимости типов. Например представим, что класс определяет

не только методы, но и типы. Причём новые типы зависят от конкретного экземпляра класса. Посмотрим,

например, на определение линейного пространства из библиотеки vector-space:

class AdditiveGroup v where

zeroV

:: v

(^+^)

:: v -> v -> v

negateV :: v -> v