Я ' Я пытаюсь написать небольшой скрипт, который анализирует и выполняет код Brainfuck, чтобы понять варианты оптимизации GHC, я пытаюсь оптимизировать код, чтобы он работал немного быстрее и чтобы понять, что там происходит.
the parts - это внутренняя репрезентация BF-кода, я использую для этого специальный тип данных. Вот исходный код, включающий две функции, выполняющие преобразования:
data BFinstruction
= AdjustValue Int
| MovePointer Int
| GetChar
| PutChar
| Loop BFcode
deriving (Eq)
type BFcode = [BFinstruction]
unsafeCompileBrainfuck :: String -> BFcode
unsafeCompileBrainfuck = fst . parse [] where
-- arguments: input string, built code; output: output code, rest of input
parse :: BFcode -> String -> (BFcode,String)
parse c ('+':s) = parse (AdjustValue 1 :c) s
parse c ('-':s) = parse (AdjustValue (-1):c) s
parse c ('>':s) = parse (MovePointer 1 :c) s
parse c ('<':s) = parse (MovePointer (-1):c) s
parse c ('.':s) = parse (PutChar :c) s
parse c (',':s) = parse (GetChar :c) s
parse c (']':s) = (reverse c, s)
parse c ('[':s) = parse (Loop l :c) s' where (l,s') = parse [] s
parse c [] = (reverse c ,"")
parse c ( _ :s) = parse c s
simplifyBrainfuck :: BFcode -> BFcode
simplifyBrainfuck ((AdjustValue x):(AdjustValue y):zs) = if x + y /= 0
then simplifyBrainfuck (AdjustValue (x + y):zs)
else simplifyBrainfuck zs
simplifyBrainfuck ((MovePointer x):(MovePointer y):zs) = if x + y /= 0
then simplifyBrainfuck (MovePointer (x + y):zs)
else simplifyBrainfuck zs
simplifyBrainfuck (x :zs) = x: simplifyBrainfuck zs
simplifyBrainfuck [] = []
Идея состоит в том, что код будет считываться из некоторого ввода (строки), предварительно анализироваться и упрощаться с помощью приведенного выше кода, а затем выполняться некоторыми другими функциями. (Предполагается, что введенные данные действительны.)
Чтобы оптимизировать этот пример, я попытался распаковать параметры Int конструкторов MovePointer
и AdjustValue
, выполнив приглушение как это:
data BFinstruction -- BangPatterns
= AdjustValue {-# UNPACK #-} !Int
| MovePointer {-# UNPACK #-} !Int
| GetChar
| PutChar
| Loop BFcode
deriving (Eq)
Это превратит упакованный в коробку тип Int
в распакованный, необработанный тип Int #
, который является деталью реализации GHc. Пока я читал, этот вариант хорош только в некоторых случаях, поэтому я хочу спросить, на какие вещи мне нужно обратить внимание, если я хочу выполнить такую оптимизацию. Моя цель - разрешить выполнение BF-кода с использованием преимуществ Haskell - лени (я хочу архивировать, что код может храниться в памяти только по мере необходимости) и простоты.