Glasgow Haskell Compiler

Средой разработки для Haskell служит Haskell Platform - набор инструментов и библиотек, которые упрощают разработку на этом языке. В состав Haskell Platform входит компилятор Glasgow Haskell Compiler.

GHCi может загружать как откомпилированные для текущей платформы модули (и именно так происходит со стандартными библиотечными модулями), так и работать в режиме интерпретатора (так по умолчанию происходит с исходным кодом, который перед загрузкой преобразуется в байт-код). Буковка i в названии обозначает interactive, но GHCi часто называют интерпретатором.

Библиотека Prelude всегда загружается при запуске GHCi и содержит внутри себя определения наиболее часто используемых стандартных функций, операторов и объектов языка Haskell. 

Prelude> 33 + 3 * 3
42
Prelude> pi
3.141592653589793
Prelude> "ABC" ++ "DE"
"ABCDE"

Приглашение командной строки может быть изменено с помощью команды:

:set prompt "GHCi >"

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

Загрузка модуля на языке Haskell в интерпретатор

Загрузка модуля:
ghci Hello.hs

Вызов функции main:
*Main> main
Hello, world!

В уже запущенный интерпретатор можно загружать некоторый модуль:

Prelude> :load Test
[1 of 1] Compiling Test             ( Test.hs, interpreted )
Ok, modules loaded: Test.
*Test> sayHello
Hello from module Test!

Имя команды можно сокращать до первой буквы, написав :l. Все команды интерпретатора начинаются с двоеточия.

Перезагрузка модуля:

*Test> :reload
[1 of 1] Compiling Test             ( Test.hs, interpreted )
Ok, modules loaded: Test.
*Test> sayHello
Hello World from module Test!

Модель вычислений принятая в функциональных языках

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

В функциональных языках программа представляет собой некоторое выражение. А вычисление выполнения программы заключается в последовательных редукциях этих выражений до состояния, когда такие редукции дальше уже не возможны. Получившиеся отредуцированное выражение представляет собой результат работы программы. Таким образом вычислитель в этой ситуации это некоторая внешняя программа, которая умеет выполнять редукции.

В Haskell вычисления происходят с помощью подстановки. В месте вызова функции осуществляется подстановка тела этой функции с заменой формального параметра на фактический.

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

Редексы

Выражение, которое может быть упрощено непосредственно носит название redex. В ситуации, когда в выражении есть несколько редексов можно реализовывать разные стратегии вычислений.


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

id x = x
const x y = x
max x y = if x <= y then y else x
infixr 0 $
f $ x = f x

В следующем выражении const $ const (4 + 5) $ max 42 имеется 3 редекса.


О выражениях, которые не содержат редексов говорят, что они находятся в нормальной форме. Нормальная форма означает, что выражение дошло до окончательного результата и в нем никаких вычислений больше провести нельзя.

{-
 NF
42 -- просто число
(3,4) -- конструктор пары примененный к двум значениям
\x -> x + 2 -- функции тоже могут находиться в нормальной форме

 не NF
"Real " ++ "world" -- строковое выражение
sin (pi / 2)
(\x -> x + 2) 5 -- можно подставить вместо x пятерку
(3,1+5)
-}

В Haskell есть промежуточная концепция, это понятие слабой головной (заголовочной) нормальной формы (weak head normal form).

{-
 WHNF
\x -> x + 2*3 -- любая лямбда-абстракция
(3,1+5) -- любой конструктор данных
(,) (4*5) -- частично примененный конструктор данных
(+) (7^2) -- частично примененная встроенная функция
-}

Выражения, которые находятся в NF, они в то же время находятся в WHNF. Понятие WHNF расширяет понятие NF. Во многих ситуация вычисления в Haskell останавливаются на WHNF не доводя их до NF. Такого рода остановка позволяет сделать функции еще более определенными в случае расходимости.

Следующие выражения не находятся в нормальной форме, но находятся в слабой головной нормальной форме:

[undefined, 4 + 5, -1]
(+) (2 * 3 * 4)
(,) undefined

Стратегии вычислений

Ленивая семантика в отношении языка Haskell означают, что если какое-то выражение не требуется для получения результата вычислений, это выражение никогда не будет редуцироваться и вычисляться.

Две стратегии вычислений:

module Demo where

sumIt :: Int -> Int -> Int
sumIt x y = x + y


{- Ленивая стратегия:
sumIt (2 + 3) 4 -- сначала осуществляем подстановку
 ~> (2 + 3) + 4 -- вычисляем значение первого аргумента
 ~> 5 + 4
 ~> 9
-}

{- Альтернативная ленивой энергичная стратегия:
sumIt (2 + 3) 4 -- сначала вычисляем значение первого аргумента
 ~> sumIt 5 4 -- вызывается функция
 ~> 5 + 4
 ~> 9
-}

В Haskell принята ленивая стратегия вычислений. Важным свойство чистых функциональных языков является независимость результата вычислений программы от выбранной стратегии. В императивных языках подобное свойство не выполняется из-за наличия изменяемых переменных. В чистых функциональных языках результат не зависит от стратегии до тех пор пока программы являются завершающимися.


В следующем примере ленивая стратегия отрабатывает гораздо лучше, чем энергичная стратегия.

add7 :: Int -> Int -> Int
add7 x y = x + 7 -- второй аргумент игнорируется

{-
Ленивая модель:
add7 1 (2 + 3)
 ~> 1 + 7
 ~> 8

Энергичная модель:
add7 1 (2 + 3)
 ~> add7 1 5
 ~> 1 + 7
 ~> 8
-}

Обратная ситуация.

dup :: Int -> (Int,Int)
dup x = (x,x)

{-
Ленивая стратегия вычислений:
dup (2+3)
 ~> (2+3,2+3)
 ~> (5,2+3)
 ~> (5,5)

Энергичная стратегия вычислений:
dup (2+3)
 ~> dup 5
 ~> (5,5)
-}

Энергичная модель вычислений несколько эффективнее, чем ленивая модель вычислений потому что ленивая модель вычислений для эффективности требует некоторой косвенности вызовов.

Механизм разделения

{- Механизм разделения:
dup (2+3)
 ~> (p,p)  p=2+3
 ~> (5,p)  p=5
 ~> (5,5)
-}

Вместо того чтобы выполнять чисто синтаксическую подстановку при вызове функций, добавляет дополнительный уровень косвенности. Таким образом подставляется не выражение 2+3, а некоторый указатель. Это специальный умный указатель, который указывает на некоторую область памяти, где может храниться отложенное вычисление или значение.


Для того чтобы вычислить значение функции value, при использовании ленивой стратегии вычислений с механизмом разделения потребуется 4 шага редукции (если не считать подстановку тела функции value вместо value).

bar x y z = x + y
foo a b = bar a a (a + b)
value = foo (3 * 10) (5 - 2)

{-
foo (3 * 10) (5 - 2)
 ~> bar (3 * 10) (3 * 10) ((3 * 10) + (5 - 2))
 ~> (3 * 10) + (3 * 10)
 ~> 30 + 30
 ~> 60
-}