3

我的理解是 CPU 的简单模型是状态机。

当我查看序言时，它似乎是树搜索（或图形搜索）组合，同时停止运行直到找到它的目标的约束。

有人告诉我，您可以在 prolog 中模拟一个简单的 CPU。

是否可以在 prolog 中像简单的 CPU 一样表示状态机模型？

4

2 回答 2

3

Prolog 是图灵完备的语言，因此您可以在其中表达任意计算，包括对 CPU 的模拟。您可以将单个指令的执行表示为 CPU 的两种状态之间的关系，一种在指令执行之前，一种在指令执行之后（接下来要执行的指令也是状态的一部分，因为它例如可用在或通过 CPU 的寄存器之一）：

cpustate0_cpustate(State0, State) :-
      ....

程序的完整执行可以声明性地描述为 CPU 的一系列状态转换。在程序上，你转换一个给定的状态，直到它达到某个定义的最终状态，例如，直到某个寄存器包含或指向一个特定的值：

cpu_before_after(State0, State) :-
    (    final_state(State0) -> State = State0
    ;    cpustate0_cpustate(State0, State1),
         cpu_before_after(State1, State)
    ).

编辑：例如，CPU 的状态可能看起来像 Prolog 术语cpu(10, 20, 0) ，它可能是第一个寄存器包含值 10，第二个寄存器包含值 20，第三个寄存器包含值 0 的特定状态。让我们假设第三个寄存器是指令指针IP，CPU总是执行机器RAM中IP指向的指令。所以我们还需要在状态表示中包含机器的 RAM。让我们将机器的状态表示为一对 RAM-CPU，其中 RAM 是机器 RAM 内容的合适表示，而 CPU 是 CPU 寄存器的表示：

cpustate0_cpustate(State0, State) :-
     State0 = RAM0-cpu(_,_,IP0),   
     ram_at_value(RAM0, IP0, Instruction),
     instruction_state0_state(Instruction, State0, State).

假设现在有一条指令add，它将前两个寄存器的值相加并将结果存储在第一个寄存器中，而 RAM 保持不变：

instruction_state0_state(add, RAM-cpu(A0,B,IP), RAM-cpu(A1,B,IP)) :-
    A1 #= A0 + B.

您可以通过此谓词的附加子句来描述其他可用指令的效果。

于 2012-11-24T01:24:56.490 回答
2

正如 mat 所说，这完全有可能。

当然，这是一个不平凡的问题。

是的，您可以在 prolog 中拥有一个状态机 - 关于在 stackoverflow 上制作一个状态机有几个问题。

我建议虽然 CPU 确实是一个有限状态机，但它很容易成为一个大的——常用的 8051 控制器有 15 个字节的寄存器。由于粗略估计假设任何人都可以假设任何值是合理的，

1 ?- X 是 2^(15*8) | . X = 1329227995784915872903807060280344576。

状态。这还没有对外部存储器进行建模。您可能很难找到具有这么多内存的机器。

您可能会发现状态机的用途是解释单个指令。

所以，如果你是 Prolog 的新手，我建议你在尝试这个范围的东西之前多学习一点。我从玩井字游戏开始。那是关于正确的范围。

于 2012-11-24T22:36:21.723 回答