Различные, взаимодействующие уровни состояния в Haskell - PullRequest
Новая
       50

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

6 голосов
/ 01 февраля 2012

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

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

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

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

State Program' String

, который работал отлично, за исключением того факта, что мне нужен выход RUNNING. Что бы я ни делал, я не мог одновременно удерживать строку и состояние.

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

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. Видя, как я сейчас вытаскиваю монадные трансформаторы, можно ли перестать воспринимать «работающий выход» как состояние и просто подсунуть его монаде ввода-вывода? Это было бы здорово, вместо того, чтобы держаться за него, я мог бы просто напечатать его.
  3. На сколько слоев я должен разделить состояние? Я вижу два разных уровня, но они тесно зависят друг от друга (и память, и регистры зависят от состояния как памяти, так и регистров). Должен ли я хранить их вместе как одно государство или отделять их и складывать? Какой подход даст наиболее читаемый код?

Ответы [ 2 ]

9 голосов
/ 01 февраля 2012

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

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

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

Конечно, это по сути превращает ваш код в императивную мутацию набора глобальных переменных, но на самом деле это преимущество, так как это точно парадигма, на которой основан эмулируемый процессор. И с *Пакет 1026 * data-lens-template , вы можете получить эти объективы из определения записи в одну строку.

2 голосов
/ 01 февраля 2012

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

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).Они позволяют использовать изменяемые ссылки и массивы внутри функции, в то же время гарантируя чистоту снаружи.

...