Haskell: Можно ли скомпилировать функцию?

Question

Haskell: Можно ли скомпилировать функцию?

Рассмотрим простой интерпретатор языка Haskell Brainf * ck. Просто посмотрите на interpret функция.

import Prelude hiding (Either(..))
import Control.Monad
import Data.Char (ord, chr)

-- function in question
interpret :: String -> IO ()
interpret strprog = let (prog, []) = parse strprog
                    in execBF prog


interpretFile :: FilePath -> IO ()
interpretFile fp = readFile fp >>= interpret


type BF = [BFInstr]
data BFInstr = Left | Right | Inc | Dec | Input | Output | Loop BF

type Tape = ([Integer], [Integer])

emptyTape = (repeat 0, repeat 0)

execBFTape :: Tape -> BF -> IO Tape
execBFTape = foldM doBF

execBF :: BF -> IO ()
execBF prog = do
  execBFTape emptyTape prog
  return ()

doBF :: Tape -> BFInstr -> IO Tape
doBF ((x:lefts),   rights)   Left     = return (lefts,         x:rights)
doBF (lefts,    (x:rights))  Right    = return (x:lefts,         rights)
doBF (left,     (x:rights))  Inc      = return (left,      (x+1):rights)
doBF (left,     (x:rights))  Dec      = return (left,      (x-1):rights)
doBF (left,     (_:rights))  Input    = getChar >>= \c -> return (left, fromIntegral (ord c):rights)
doBF t@(_,      (x:     _))  Output   = putChar (chr (fromIntegral x)) >> return t
doBF t@(left,   (x:     _)) (Loop bf) = if x == 0
                                        then return t
                                        else do t' <- execBFTape t bf
                                                doBF t' (Loop bf)

simpleCommands = [('<', Left),
                  ('>', Right),
                  (',', Input),
                  ('.', Output),
                  ('+', Inc),
                  ('-', Dec)]

parse :: String -> (BF, String)
parse []          = ([], [])
parse (char:prog) = case lookup char simpleCommands of
                      Just command -> let (rest, prog') = parse prog
                                      in (command : rest, prog')
                      Nothing      ->
                        case char of
                          ']' -> ([], prog)
                          '[' -> let (loop, prog')  = parse prog
                                     (rest, prog'') = parse prog'
                                 in (Loop loop:rest, prog'')
                          _   -> parse prog

Так что у меня есть функция применяется как interpret "[->+<]", Это дает мне IO () монадическое действие, которое выполняет данную программу. Он имеет правильный тип, чтобы быть main какой-то программы.

Допустим, мне бы хотелось, чтобы это действие было скомпилировано в исполняемый файл, то есть я хотел бы создать исполняемый файл с результатом interpret ... быть главной функцией. Конечно, этот исполняемый файл должен содержать систему времени выполнения GHC (для бесконечных списков, целочисленной арифметики и т. Д.).

Вопросы:

По моему мнению, совсем невозможно просто выполнить монадическое действие и сохранить его в новом файле. Это правда?
Как можно достичь сравнимого решения? GHC Api и подсказка помогают?

РЕДАКТИРОВАТЬ

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

main = interpret "..."

Но это не то, что мы обычно делаем, когда пытаемся что-то скомпилировать, поэтому подумайте interpretFile :: FilePath -> IO () вместо. Пусть программа BF будет сохранена в файл (helloworld.bf).

Как бы я пошел о создании исполняемого файла, который выполняет содержимое helloworld.bf без необходимости файла?

$ ./MyBfCompiler helloworld.bf -o helloworld

0

haskell compilation ghc hint ghc-api

Источник

user797637 19 июл '18 в 04:29

2 ответа

Решение

Я не уверен, спрашиваете ли вы, как вы пишете компилятор, который может принимать в качестве входных данных такой файл, как helloworld.bfили как вы компилируете программу на Haskell, которая выполняется helloworld.bf,

В первом случае вы бы хотели что-то более конкретное, чем это:

import System.Environment (getArgs)

main :: IO ()
main = do
  (_:fileName:_) <- getArgs
  source <- readFile fileName
  interpret source

interpret :: String -> IO ()
interpret = undefined -- You can fill in this piddly little detail yourself.

Если вы хотите последнее, есть несколько разных вариантов. Во-первых, вы можете хранить содержимое вашего *.bf файл в строковой константе (или еще лучше, Text или строгий ByteString), и передайте это вашей функции интерпретатора. Я был бы удивлен, если GHC достаточно оптимистичен, чтобы полностью встроить и расширить этот вызов во время компиляции, но в принципе компилятор Haskell мог бы.

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

interpret [^<,^+,^>,^.]

Если вы определите (^<) и другие операторы, команды Brainfuck, будут компилироваться в байт-код, представляющий программу Brainfuck.

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

Вы также можете выразить эту идею как

interpret
  (^< ^+ ^> ^.)
  input

Здесь, если команды Brainfuck являются функциями высшего порядка с приоритетом справа налево, и interpret bf input = (bf begin) inputкод Brainfuck просто компилируется в функцию, которую вызывает интерпретатор. У этого есть лучший шанс стать быстрым нативным кодом.

Предыдущий ответ

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

main = interpret foo

В GHC вы можете дать подсказку компилятору, добавив

{-# INLINE main #-}

или даже

{-# INLINE interpret #-}

Вы можете проверить, какой код GHC сгенерирован, скомпилировав модуль с -S и просматривая источник.

2

Источник

user4474419 19 июл '18 в 04:35

Другие вопросы по тегам haskell compilation ghc hint ghc-api

user4942760 19 июл '18 в 08:47 2018-07-19 08:47 · Accepted Answer · 2018-07-19 08:47

Ответ в основном нет.

Есть много способов построить IO ценности:

Встроенные функции, такие как putStrLn
Монад операции как return или же >>=

Если у вас есть значение IO, есть три способа его разбить:

Задавать main равно значению
unsafePerformIO
В качестве возвращаемого значения экспортируемой функции C

Все это разрушает преобразование IO a в a, Нет другого способа проверить его, чтобы увидеть, что он делает.

Точно так же единственное, что вы можете сделать с функциями, это поместить их в переменные или вызвать их (или преобразовать их в указатели на функции C).

Нет вменяемого способа проверить функцию.

Одна вещь, которую вы могли бы сделать, которая не компилируется, а связана с компоновкой, - это запустить основную функцию интерпретатора на некоторой внешней строке c, встроить ее в статический объект, а затем ваш "компилятор" может создать новый объект с этой строкой C программа в ней и ссылка на то, что у вас уже есть.

Существует теория частичной оценки, которая гласит, что если вы выполняете частичную оценку частичного оценщика, примененного к интерпретатору, примененному к некоторому вводу, то вы получаете компилятор, но ghc не является достаточно продвинутым частичным оценщиком.