如何为Haskell自定义Instr数据类型编写对应iexec指令执行函数

1. 示例中fromList[]的含义 #

你示例输出中Config的第二个字段是内存存储结构，它是Data.Map类型的空实例。Haskell中Data.Map的Show实例会将内部存储的键值对以fromList [键值对列表]的格式输出，空Map就会显示为fromList []。你执行LOADI指令时没有修改内存，所以输出的内存部分和输入的empty（也就是空Map）完全一致。

2. Config类型声明是否正确 #

你当前写的type Config = (Int, [*], [*])是不合法的，其中[*]是类型占位符，不能直接用于编译。
合法的定义需要先补全所有涉及的基础类型，示例如下：

import qualified Data.Map as M

-- 先定义Val类型，这里按你的用法定为整数
type Val = Int
-- 第二个字段是变量内存，用Map存储变量名到值的映射
type Memory = M.Map String Val
-- 第三个字段是操作数栈，存储Val类型的元素
type Stack = [Val]
-- 最终合法的Config定义：(程序计数器, 内存, 操作数栈)
type Config = (Int, Memory, Stack)

改完之后你示例的运行输出就会和你给出的结果完全匹配。

3. iexec函数的实现思路 #

直接对Instr的每个构造子做模式匹配，按照指令语义修改Config的三个字段即可，基础实现如下：

import qualified Data.Map as M

iexec :: Instr -> Config -> Config
-- LOADI：把立即数压入栈顶，计数器+1，内存不变
iexec (LOADI v) (pc, mem, stack) = (pc + 1, mem, v : stack)
-- LOAD：从内存读取指定变量的值压入栈顶，计数器+1，内存不变
iexec (LOAD k) (pc, mem, stack) = (pc + 1, mem, (mem M.! k) : stack)
-- ADD：栈顶元素加立即数，结果压回栈，计数器+1，内存不变
iexec (ADD v) (pc, mem, top:rest) = (pc + 1, mem, (top + v) : rest)
-- STORE：弹出栈顶元素存入内存对应变量，计数器+1
iexec (STORE k) (pc, mem, top:rest) = (pc + 1, M.insert k top mem, rest)
-- JMP：直接修改程序计数器为指定值，内存和栈不变
iexec (JMP target) (_, mem, stack) = (target, mem, stack)
-- JMPLESS：弹出两个栈顶元素a、b，若a < b则跳转到目标地址，否则计数器+1
iexec (JMPLESS target) (pc, mem, a:b:rest) = if a < b then (target, mem, rest) else (pc + 1, mem, rest)
-- JMPGE：弹出两个栈顶元素a、b，若a >= b则跳转到目标地址，否则计数器+1
iexec (JMPGE target) (pc, mem, a:b:rest) = if a >= b then (target, mem, rest) else (pc + 1, mem, rest)
-- 异常分支：栈元素不足时的错误提示
iexec _ (_, _, []) = error "操作数栈为空，无法执行当前指令"
iexec _ (_, _, [_]) = error "操作数栈元素不足，无法执行当前指令"

你可以根据自己的需求调整各指令的语义，比如跳转是相对偏移还是绝对地址、变量寻址的规则等。

内容的提问来源于stack exchange，提问作者Ethan Gallagher