2

为帖子的奇怪标题道歉，我不确定描述它的最佳方式是什么。

一般问题：

对 Seq.map （或类似函数）进行顺序应用，除了列表中的每一项外，还传入一个“上下文”。每次迭代都可以修改这个“上下文”，更新后的版本应该传递到列表中的下一项。

具体问题：

我正在 F# 中创建一个编译器。我目前正在进行的步骤是将基于堆栈的 IL 转换为基于寄存器的 IL。我在想我可以“遍历”基于堆栈的 IL 并携带当前的“eval 堆栈”（类似于 .NET 的 eval 堆栈）。显然，每个堆栈 IL 操作码都会改变堆栈（例如：“添加”操作码将两个项目从堆栈中弹出并推送结果）。这个更新的堆栈将被传递到下一个操作码的发射周期。

请注意，我对函数式编程非常陌生（我是在一周前了解到的），来自 C# 背景，我的主要问题是“什么是‘函数式’方法来做到这一点？”

这是我对“功能”方法的最佳猜测（伪代码）。我不喜欢“transformStackToRegisterIL”的元组返回值，如果我想保持不可变值的标准，是否需要它？另外，我担心过长的 IL 块会导致堆栈溢出，这是我的担忧吗？

let rec translate evalStack inputIl =
    match inputIl with
        | singleOpcode :: tail ->
            let (transformed, newEvalStack) = transformStackToRegisterIL evalStack singleOpcode
            transformed :: translate newEvalStack tail
        | [] -> []

编辑：List.scan是我想要的内置功能吗？（看起来很相似，但并不完全正确......但它可能是正确的，我不确定）

4

3 回答 3

3

我将尝试使用一个非常基本的示例来解释这一点，该示例在某种程度上受到您的问题的启发（但没有实现任何现实的东西）。

所以，让我们假设我们有 IL 指令Push，它将一个命名变量压入堆栈，并在堆栈Add上添加最后两个项目（为简单起见，假设它只是将结果打印到控制台）。目标是一种注册表语言，它带有Nop两个Add变量名，将它们添加（并将结果打印到控制台）：

type IL = 
  | Push of string
  | Add

type Reg =
  | Add of string * string
  | Nop

let input = [ IL.Push "a"; IL.Push "a"; IL.Push "b"; IL.Add; IL.Push "c"; IL.Add ]

输入应转换为Reg.Add("b", "a")andReg.Add("c", "a")和一些 Nops。转换函数采用当前堆栈和一条指令：

let transform stack = function
  | IL.Push var -> Reg.Nop, var::stack
  | IL.Add -> Add(stack.Head, stack.Tail.Head), stack.Tail.Tail

要转换整个列表，我们可以使用List.foldwhich 保持当前“状态”。它调用具有当前状态和单个输入指令的提供函数，并且提供的函数必须返回一个新状态。这里，“状态”是堆栈，也是我们正在生成的寄存器机器指令列表：

let endStack, regsReversed =
  input |> Seq.fold (fun (stack, regs) il ->
      // Transform current IL instruction, given current 'stack'
      let reg, newStack = transform stack il
      // Add new registry instruction to 'regs' and return new stack
      (newStack, reg::regs) ) ([], [])

使用递归也可以做到这一点。结构非常相似，只是我们将状态保留为参数并通过递归调用来更改它：

let rec compile (stack, regs) = function
  | [] -> (stack, regs)
  | il::ils -> 
      // Transform current IL instruction, given current 'stack'
      let reg, newStack = transform stack il
      // Add new registry instruction to 'regs' and return new stack
      compile (newStack, reg::regs) ils

let endStack, regs = compile ([], []) input

现在我们可以检查堆栈最后是否为空并打印注册机指令（注意我们将它们附加到前面，所以我们需要反转结果）：

if endStack <> [] then printfn "Stack is not empty!"
regs |> List.rev

正如杰克所提到的 - 您还可以使用更高级的方法来处理这个问题，比如计算表达式（状态）。我认为编写严肃的编译器实际上是一个使用它们有意义的地方，但如果你正在学习 F#，从折叠和递归等基本概念开始会更容易。

于 2013-08-21T00:56:26.980 回答
3

传递“上下文”并对其进行变异-您正在谈论state工作流程；在那里，状态将是您的评估堆栈。

如果您确实使用state工作流（我建议您这样做），您可以使用ExtCoreState.List.map中的函数——它将一个列表映射到另一个列表，在处理列表时将上下文值从一个元素传递到下一个元素。

不用担心长 IL 块（即大的方法体）会使堆栈溢出——只有在调用堆栈非常深时才会担心堆栈溢出。

于 2013-08-21T01:12:00.923 回答
0

您可以使用List.reduce或使用自定义计算表达式（类似于 async 的工作方式）来做到这一点。我可能会使用，除非您要经常重复使用它或者由于其他原因List.reduce它没有修复。List.reduce

于 2013-08-20T23:59:54.243 回答