Различные взаимодействующие уровни состояния в haskell

Я эмулирую 4-битный микропроцессор. Мне нужно отслеживать регистры, память и текущий вывод (бонусные баллы за наличие счетчика циклов выборки-выполнения). Мне удалось сделать это без монад, но это кажется грязным, когда я явно пропускаю столько вещей одновременно. Кроме того, определение функции беспорядочное, длинное и трудночитаемое.

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

State Program () -- Represents the state of the processor after a single iteration of the fetch execute cycle

Был единственным типом, который имел хоть какой-то смысл. Но в таком случае зачем вообще заморачиваться? Я попытался разбить его, вытащив строку из моего составного типа и обработав ее как значение

State Program' String

который отлично работал, за исключением того факта, что мне нужен был РАБОТАЮЩИЙ вывод. Что бы я ни делал, я не мог одновременно удерживать и строку, и состояние.

Теперь я пытаюсь бороться с трансформерами монад. Кажется, мне нужно выделить все разные уровни состояния. Но моя голова взрывается быстро.

StateT Registers (StateT Memory (State Output)) a = 
StateT (registers -> (StateT Memory (State Output)) (a,registers))

StateT Registers (StateT Memory (State Output)) a = 
StateT (registers -> (Memory -> (Output -> (((a,Registers),Memory),Output))))

Я еще даже не установил счетчик FEcycle!

Вопросы:

  1. Я на правильном пути?
  2. Раз уж я сейчас вытаскиваю трансформеры монад, можно ли перестать рассматривать «текущий вывод» как состояние и просто подсунуть его монаде IO? Это было бы здорово, вместо того, чтобы держать его, я мог бы просто распечатать его.
  3. На сколько слоев я должен разделить состояние? Я вижу два отдельных слоя, но они тесно зависят друг от друга (и память, и регистры зависят от состояния как памяти, так и регистров). Должен ли я держать их вместе как единое состояние или разделить их и сложить? Какой подход создаст наиболее читаемый код?

person TheIronKnuckle    schedule 01.02.2012    source источник
comment
Возможно, текущий вывод лучше всего представить с помощью монады Writer (см. .html)?   -  person Jeff Foster    schedule 01.02.2012


Ответы (2)


Наслоение нескольких монад состояния друг на друга — плохая идея: вам придется составить кучу lift, чтобы получить каждую часть состояния, идентифицируемую только количеством слоев в стеке. Фу! Действительно, библиотека mtl вообще предназначена для использования, за редким исключением, с одним трансформером монад каждого «вида» в стеке.

Вместо этого я бы предложил StateT Program IO (). Интерфейс состояния тот же, и вы можете, как вы сказали, выполнять вывод в IO, просто используя liftIO. Конечно, тип значения (), но что в этом плохого? Нет подходящего значения, которое вы можете вернуть из эмулятора верхнего уровня. И, конечно же, вы, вероятно, будете иметь меньшие повторно используемые компоненты как часть вашего эмулятора, и они будут иметь соответствующие типы результатов. (Действительно, get является одним из таких компонентов.) Нет ничего плохого в том, что на верхнем уровне нет значимого возвращаемого значения.

Что касается удобного доступа к каждой части состояния, вам нужны линзы; этот ответ на переполнение стека — отличное введение. Они позволяют вам просто и легко получать доступ и изменять независимые части вашего состояния. Например, с реализацией data-lens вы можете легко написать что-то вроде regA += 1 для увеличьте regA или stack %= drop 2, чтобы удалить первые два элемента стека.

Конечно, по сути, это превращает ваш код в императивную мутацию набора глобальных переменных, но на самом деле это преимущество, поскольку именно это парадигма, на которой основан процессор, который вы эмулируете. А с < пакет href="http://hackage.haskell.org/package/data-lens-template" rel="nofollow noreferrer">data-lens-template, вы можете получить эти линзы из определения записи в одна линия.

person ehird    schedule 01.02.2012
comment
Это чертовски круто. Пришло время изучить шаблонный haskell. Легко ли найти поддержку функционального определения, например regA += 1? Потому что, хотя это приятно, читабельно и наиболее четко выражает (очень императивное) намерение, это совсем не похоже на функциональный код. - person TheIronKnuckle; 01.02.2012
comment
Вам не нужно изучать Template Haskell, чтобы использовать data-lens-template; просто вставьте {-# LANGUAGE TemplateHaskell #-} вверху вашего файла и makeLenses [''Program] где-нибудь под определением Program. Что касается определения (+=), конечно; они просто простые оболочки основного API объектива для StateT; источник связан с документацией Hackage. - person ehird; 01.02.2012
comment
Небольшое замечание: монады с многоуровневым состоянием — плохая идея, если только они вам действительно не нужны. Они позволяют разбивать состояние, поэтому вы можете ограничить доступ некоторых клиентов только для чтения к определенному уровню состояния, а не доступ для чтения и записи, это используется для кода, заботящегося о безопасности. В остальном хороший ответ. - person stephen tetley; 01.02.2012
comment
@stephentetley: Действительно, таким образом, редкие исключения :) Я бы в любом случае оборачивал такие вещи в newtype, чтобы избежать двусмысленности, которую вы получили бы с определениями MonadState. - person ehird; 01.02.2012
comment
В последний раз, когда я использовал этот шаблон проектирования: к тому времени, когда я закончил его оптимизацию, подпись изменилась с чего-то вроде State Program [Word8] на что-то более похожее на ReaderT (STProgram s) (ST s) [Word8] - person Jeremy List; 09.06.2015

Простым способом сделать это было бы создать тип данных, представляющий регистры и память:

data Register = ...
data Memory = ...
data Machine = Machine [Register] Memory

Затем есть некоторые функции, которые обновляют регистры/память. Теперь используйте этот тип для своего состояния и вывод для вашего типа:

type Simulation = State Machine Output

Теперь каждая операция может быть представлена ​​в виде:

operation previous = do machine <- get
                        (result, newMachine) <- operate on machine
                        put newMachine
                        return result

Здесь previous — это предыдущий вывод машины. Вы также можете включить его в результат.

Таким образом, тип Machine представляет состояние машины; вы пропускаете через него вывод предыдущих операций.

Более сложным способом было бы использование потоков состояния (Control.Monad.ST). Это позволяет вам использовать изменяемые ссылки и массивы внутри функции, гарантируя чистоту снаружи.

person Tikhon Jelvis    schedule 01.02.2012