]]> ]]>

GHC

Реализация языка программирования Haskell

GHC — компилятор с открытыми исходниками функционального языка программирования Haskell в нативный код.

GHC начал разрабатываться в 1989-ом как прототип, написанный на LML (Lazy ML) Кевином Хеммондом (Kevin Hammond) в Университете Глазго (“University of Glasgow”). Позже в том же году прототип был почти полностью переписан на Haskell, за исключением парсера, Корделией Холл, Виллом Пертейном и Саймоном Пейтон Джонсом (Cordelia Hall, Will Partain, and Simon Peyton Jones). Первый бета-релиз состоялся 1 апреля 1991-го, в следующих релизах добавился анализатор строгости и расширения языка, к примеру, ввод-вывод на базе монад, изменяемые массивы, распакованные типы данных (unboxed data types) и профайлер.

Пейтон Джонс вместе с Саймоном Марлоу (Simon Marlow) позже были наняты Microsoft Research в Кэмбридже, Англия, где до настоящего времени отвечают за разработку GHC. GHC содержит код также от более чем шестисот других авторов.

Как уже упоминалось, GHC написан на Haskell (с помощью техники известной, как «бутстрэппинг»), кроме системы времени выполнения, важной части компилятора, которая на писана на C и C—. Большая часть GHC написана в стиле литературного программирования (literate programming).

Фронт-энд GHC — включающий в себя лексер, парсер и проверку типов — спроектирован так, чтобы сохранять максимальное количество информации об обрабатываемом исходном коде до момента завершения вывода типов, с целью предоставления ясных сообщений об ошибках конечному пользователю. GHC включает в себя оптимизирующий компилятор, создающий код для нескольких платформ, который также может работать в интерактивном режиме (GHCi), средства профилирования, множество библиотек, а так же интерфейсы к другим языкам программирования.

В последней фазе фронт-энд убирает синтаксический сахар трансформируя Haskell в типизированный промежуточный язык, известный как “Core” (базирующийся на System F с расширением в виде “let” и “case” выражений). Оптимизатор GHC (“middle end”) выполняет свою работу в виду преобразований кода на Core.

На последней стадии Core переводится в STG (сокращение для “Spineless Tagless G-machine”), промежуточный язык низкого уровня. Как и Core, STG — функциональный язык, представляющий абстрактную машину. Бэк-энд GHC проводит преобразования над STG перед трансляцией в C, C— или нативный машинный код.

Примеры:

Факториал:

Пример для версий GHC 6.10.4, GHC 6.6.1

Используется рекурсивное определение факториала. Пример состоит из трех частей:

  • определение функции factorial, принимающей на вход один аргумент типа Integer (целое число неограниченной точности) и имеющей выход того же типа. Функция определяется рекурсивно, тип параметров задан в явном виде, чтобы избежать неоднозначности их определения.
  • определение функции line, которая выводит на печать число и его факториал в нужном формате. Использование команды printf аналогично языку C++.
  • собственно вывод чисел и их факториалов. Для этого командой [0..16] создается список чисел от 0 до 16, включительно. Функция двух аргументов map применяет первый аргумент (функцию line) к каждому элементу второго аргумента (списка [0..16]) и в результате создает список так называемых действий вывода (являющихся в Haskell обычными значениями). Для того, чтобы объединить эти действия в одно, используется команда sequence_, которая, будучи применена к списку действий, выполняет первое действие из списка и затем рекурсивно применяет себя к хвосту списка.
module Main where

import Text.Printf

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

line x = printf "%d! = %d\n" x $ factorial x

main = sequence_ $ map line [0..16]

Факториал:

Пример для версий GHC 6.6.1

Функция fac определена как произведение чисел от 1 до n через встроенную функцию языка product.

module Main where

import Text.Printf

fac n = product [1..n]

main = sequence_ $ map (\x -> printf "%d! = %d\n" x $ fac x) [0..16]

Hello, World!:

Пример для версий GHC 6.10.4
module Main where

main = do
    putStrLn "Hello, World!"

Числа Фибоначчи:

Пример для версий GHC 6.10.4

Этот пример использует одну из основных особенностей языка Haskell — возможность ленивых вычислений и использования бесконечных списков. Бесконечный список чисел Фибоначчи fibs определяется при помощи фунции zipWith, которая применяет первый аргумент (функцию двух переменных, в данном случае +) к парам соответствующих элементов второго и третьего аргументов (списков). tail fibs возвращает хвост списка fibs (т.е. все элементы, кроме первого). Таким образом первый элемент списка, возвращаемого zipWith, является суммой первого и второго элементов списка fibs и становится третьим его элементом.

module Main where

import Text.Printf

fibs :: [Int]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

line n = printf "%d, " $ fibs !! n

main = do
    sequence_ $ map line [1..16]
    putStrLn "..."

Числа Фибоначчи:

Пример для версий GHC 6.10.4

Этот пример использует рекурсивное определение чисел Фибоначчи через пары соседних чисел в последовательности. На печать выводятся только первые элементы пар.

module Main where

import Text.Printf

fibNextPair :: (Int, Int) -> (Int, Int)
fibNextPair (x, y) = (y, x+y)

fibPair :: Int -> (Int, Int)
fibPair n 
    | n == 1 = (1, 1)
    | otherwise = fibNextPair (fibPair (n-1))

line n = printf "%d, " $ (fst.fibPair) n

main = do
    sequence_ $ map line [1..16]
    putStrLn "..."

Квадратное уравнение:

Пример для версий GHC 6.10.4

Haskell предоставляет тип данных для работы с комплексными числами. Функция quadratic принимает в качестве аргумента список трех комплексных чисел (коэффициентов уравнения) и возвращает список корней уравнения. Запись вида root sign позволяет передать знак операции в качестве аргумента и таким образом обобщить запись двух знаков при квадратном корне из дискриминанта.

module Main where

import Data.Complex
import System.IO (hFlush, stdout)

quadratic :: (Complex Double, Complex Double, Complex Double) -> [Complex Double]
quadratic (0, _, _) = []
quadratic (a, b, c)
      | d == 0 = [root (+)]
      | otherwise = [root (+), root (-)]
  where d = b*b - 4*a*c
        root sign = sign (-b) (sqrt d) / (2*a)

main = do
    putStr "A = "
    hFlush stdout
    a <- readLn :: IO Double
    putStr "B = "
    hFlush stdout
    b <- readLn :: IO Double
    putStr "C = "
    hFlush stdout
    c <- readLn :: IO Double
    print $ quadratic (realToFrac a, realToFrac b, realToFrac c)

Числа Фибоначчи:

Пример для версий GHC 6.8.1

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

main = putStrLn $ withDots $ join $ take 16 fibs
       where fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
             join = foldl (\a b -> a ++ show b ++ ", " ) "" 
             withDots = (++ "...")

Комментарии

]]>

blog comments powered by Disqus

]]>

Работа программистам