Diferentes niveles de estado que interactúan en haskell

Question

Estoy emulando un microprocesador de 4 bits. Necesito hacer un seguimiento de los registros, la memoria y el resultado de ejecución (puntos de bonificación por tener también un contador de ciclos de búsqueda y ejecución). He logrado hacer esto sin mónadas, pero se siente desordenado al pasar tantas cosas a la vez explícitamente. Además, la definición de la función es desordenada, larga y difícil de leer.

He intentado hacer esto con mónadas y simplemente no encaja. Traté de tratar todos los componentes de estado por separado como un solo tipo, pero eso me dejó con el problema de qué hacer con el valor.

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

Era el único tipo que tenía sentido. Pero en ese momento, ¿por qué molestarse? He intentado romper hacia arriba tirando de la cuerda de mi tipo de compuesto y tratándolo como el valor

State Program' String 

el que funcionaba muy bien, excepto por el hecho de que necesitaba salida de RUNNING. No importaba lo que hiciera, no podía mantener tanto la cuerda como el estado al mismo tiempo.

Ahora estoy tratando de lidiar con transformadores de mónada. Parece que tengo que separar todos los diferentes niveles de estado. Pero mi cabeza está explotando rápido.

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)))) 

¡Ni siquiera he puesto en el contador FEcycle todavía!

Preguntas:

1. estoy en el camino correcto?
2. Al ver que estoy sacando transformadores de mónada ahora, ¿es posible dejar de tratar el "resultado de ejecución" como estado y simplemente llevarlo a la mónada IO? Eso sería increíble, en lugar de aferrarme a él, podría simplemente imprimirlo.
3. ¿A cuántas capas debo separar el estado? Puedo ver dos capas distintas, pero dependen estrechamente unas de otras (tanto la memoria como los registros dependen del estado de la memoria y de los registros). ¿Debo mantenerlos juntos como un único estado o separarlos y apilarlos? ¿Qué enfoque producirá el código más legible?

Answer 1

La superposición de múltiples mónadas de estado una encima de la otra es una mala idea: tendrás que componer un montón de lift para obtener cada estado, identificado solo por el número de capas de la pila que está. ¡Yuck! De hecho, la biblioteca mtl en general está diseñada para ser utilizada, con raras excepciones, con un transformador de mónada de cada "clase" en una pila.

En cambio, sugeriría StateT Program IO(). La interfaz para el estado es la misma y usted puede, como usted dijo, hacer una salida en IO simplemente usando liftIO. Claro, el tipo de valor es (), pero ¿qué hay de malo en eso? No hay ningún valor relevante que puede devolver desde el emulador de nivel superior. Y, por supuesto, es probable que tenga componentes más pequeños y reutilizables como parte de su emulador, y esos tendrán tipos de resultados relevantes. (De hecho, get es uno de esos componentes.) No hay nada de malo en no tener un valor de retorno significativo en el nivel superior.

En cuanto al acceso conveniente a cada parte del estado, lo que está buscando son lentes; this Stack Overflow answer es una excelente introducción. Le permiten acceder y modificar de manera simple y fácil las partes independientes de su estado. Por ejemplo, con la implementación data-lens, puede escribir fácilmente algo como regA += 1 para incrementar regA, o stack %= drop 2 para eliminar los primeros dos elementos de la pila.

Claro, es esencialmente convirtiendo el código en la mutación imperativo de un conjunto de variables globales, pero esto es en realidad una ventaja, ya que eso es exactamente el paradigma de la CPU que está emulando se basa en. Y con el paquete data-lens-template , puede derivar estos lentes de una definición de registro en una sola línea.

Answer 2

Una forma sencilla de hacer esto sería la creación de un tipo de datos que representa los registros y la memoria:

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

Luego tienen algunas funciones que actualizan el registro/memoria. Ahora utilizar este tipo para su estado y la salida para su tipo:

type Simulation = State Machine Output 

Ahora cada operación podría ser en la forma:

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

Aquí previous es la salida anterior de la máquina. Usted puede incorporarlo en el resultado también.

El tipo Machine representa el estado de la máquina; estás enhebrando la salida de las operaciones previas a través de él.

Una forma más sofisticada sería usar state threads (Control.Monad.ST). Éstos le permiten usar referencias y matrices mutables dentro de una función a la vez que se garantiza la pureza en el exterior.