0

我写了一个非常简单的实现,可能类似于汇编/机器代码。

它甚至可以递归,如下例所示:

9 6
IFEQ R0,0
RET 1
ENDIF
MOV R1,R0
SUB R1,1
CALL R1
MOV R2,R9
MUL R2,R0
RET R2

输出:720(6的因数)

描述:

9 = Program Lines
6 = Program Input. Will be set to registry R0 value at class construction
CALL = calls the program again with the passed value (recursion)
RET = returns the program with the specified value. Sets registry R9 value to output value.

R0 to R9 -> general purpose registry.
R0 - program input value
R9 - program output value

-编辑:程序命令: MOV, ADD, SUB, MUL, DIV, MOD, IFEQ, IFNEQ, IFG, IFGE, IFL, IFLE, ENDIF, CALL, RET

但是程序可以进入无限循环/递归。例如:

2 0
CALL 10
RET 1 //will never be reached

如何验证的程序是否会进入无限循环/递归?

这是我的实现,不知道是否有必要,但以防万一。(这是整个代码......希望你不介意)。

#include <iostream>
#include <map>
#include <string> //std::getline
#include <sstream>
#include <vector>

namespace util
{
    template<typename I>I readcin(I& input) {
        std::cin >> input;
        std::cin.clear(); std::cin.ignore();
        return input;
    }
    template<typename I, typename...O> I readcin(I& input, O&... others) {
        readcin(input);
        return readcin(others...);
    }
}

//operations
enum OP
{
    MOV, ADD, SUB, MUL, DIV, MOD,
    IFG, IFL,
    IFEQ, IFGE, IFLE,
    IFNEQ,
    CALL,
    RET,
    ENDIF,
};
std::map<std::string, OP> OPTABLE
{
    {"MOV", MOV}, {"ADD", ADD}, {"SUB", SUB}, {"MUL", MUL}, {"DIV", DIV}, {"MOD", MOD},
    {"RET", RET},
    {"IFG", IFG}, {"IFL", IFL},
    {"IFNEQ", IFNEQ}, {"IFEQ", IFEQ}, {"IFGE", IFGE}, {"IFLE", IFLE},
    {"CALL", CALL},
    {"ENDIF", ENDIF}
};
//registry index
enum RI
{
    R0, R1, R2, R3, R4, R5, R6, R7, R8, R9, RI_MAX
};
std::map<std::string, RI> RITABLE =
{
    {"R0", R0}, {"R1", R1}, {"R2", R2}, {"R3", R3}, {"R4", R4}, {"R5", R5},
    {"R6", R6}, {"R7", R7}, {"R8", R8}, {"R9", R9}
};

struct Instruction
{
    OP op;
    RI r1;
    int r2value;
    Instruction() = delete;
    Instruction(OP operation, RI firstRegister, int _2ndRegValue = -1)
    {
        op = operation;
        r1 = firstRegister;
        r2value = _2ndRegValue;
    }
};


class Assembly
{

private:
    int REG[RI::RI_MAX] {0};
    int GetRegistryValue(RI ri) const { return REG[ri]; }
    void SetRegistryValue(RI ri, int val) { REG[ri] = val; }

    enum CMP_FLAG{ CMP_FAIL, CMP_OK };
    CMP_FLAG flag { CMP_OK };
    CMP_FLAG GetFlag() const { return flag; }
    void SetFlag(bool setFlag) { flag = static_cast<CMP_FLAG>(setFlag); }

    std::vector<std::string> programLines;

    OP ExtractOP(const std::string& line);
    RI ExtractRI(const std::string& line, OP op);
    int Extract2ndRIval(const std::string& line, OP op);
public:
    void addCommand(const std::string& line) { programLines.push_back(line); }
    void Execute();

    Assembly() = delete;
    Assembly(int inputValue) { REG[R0] = inputValue; }
    int ReturnValue() const { return REG[R9]; }
private:
    //recursion only
    Assembly(int inputValue, const std::vector<std::string>& progLines) {
        REG[R0] = inputValue;
        programLines = progLines;
        this->Execute();
    }
};

OP Assembly::ExtractOP(const std::string& line)
{
    std::istringstream issline{ line };
    std::string operation;
    issline >> operation;

    return OPTABLE[operation];
}

RI Assembly::ExtractRI(const std::string& line, OP op)
{
    auto space = line.find(' ');
    if(op <= IFNEQ){
        auto comma = line.find(',');
        return RITABLE[std::string(line.begin() + space + 1, line.begin() + comma)];
    }
    return RI_MAX;
}

int Assembly::Extract2ndRIval(const std::string& line, OP op)
{
    if(op == ENDIF) {
        return -1;
    }

    std::size_t spaceOrComma;
    if(op == CALL || op == RET) {
        spaceOrComma = line.find(' ');
    } else {
        spaceOrComma = line.find(',');
    }

    std::string opval = std::string(line.begin() + spaceOrComma + 1, line.end());
    auto it = RITABLE.find(opval);
    if(it != RITABLE.end()){
        return this->REG[it->second];
    }
    auto num = std::atoi(opval.c_str());
    return num;
}

void Assembly::Execute()
{
    for(const std::string& line : programLines)
    {
        OP op = ExtractOP(line);
        RI r1 = ExtractRI(line, op);
        int r2value = Extract2ndRIval(line, op);

        Instruction command ( op, r1, r2value );

        if(GetFlag() == CMP_FAIL)
        {
            if(command.op == ENDIF){
                SetFlag(CMP_OK);
            }
            continue;
        }

        switch(command.op)
        {
            case MOV: { SetRegistryValue(command.r1, command.r2value); } break;
            case ADD: { SetRegistryValue(command.r1, REG[command.r1] + command.r2value); } break;
            case SUB: { SetRegistryValue(command.r1, REG[command.r1] - command.r2value); } break;
            case MUL: { SetRegistryValue(command.r1, REG[command.r1] * command.r2value); } break;
            case DIV: { SetRegistryValue(command.r1, REG[command.r1] / command.r2value); } break;
            case MOD: { SetRegistryValue(command.r1, REG[command.r1] % command.r2value); } break;

            case IFEQ:  { SetFlag(GetRegistryValue(command.r1) == command.r2value); } break;
            case IFNEQ: { SetFlag(GetRegistryValue(command.r1) != command.r2value); } break;
            case IFG:   { SetFlag(GetRegistryValue(command.r1) > command.r2value); } break;
            case IFL:   { SetFlag(GetRegistryValue(command.r1) < command.r2value); } break;
            case IFGE:  { SetFlag(GetRegistryValue(command.r1) >= command.r2value); } break;
            case IFLE:  { SetFlag(GetRegistryValue(command.r1) <= command.r2value); } break;

            case RET:
            {
                SetRegistryValue(R9, command.r2value);
                return;
            }break;

            //oh boy!
            case CALL:
            {
               // std::cout << "value to call:" << command.r2value << std::endl;
                Assembly recursion(command.r2value, this->programLines);
                SetRegistryValue(R9, recursion.ReturnValue());
            }break;
        }
    }
}

int main()
{
    while(true)
    {
        int pl, input;
        util::readcin(pl, input);
        if(pl == 0){
            break;
        }

        Assembly Asm(input);
        for(auto i=0; i<pl; ++i)
        {
            std::string line;
            std::getline(std::cin, line);
            Asm.addCommand(line);
        }
        Asm.Execute();

        std::cout << Asm.ReturnValue() << std::endl;
    }
    return 0;
}
4

4 回答 4

3

在一般情况下,检查程序是否陷入无限循环的唯一方法是检查程序是否进入与先前状态相同的状态。如果它先前已进入完全相同的状态,则它必须继续执行循环,并按照相同的步骤顺序一遍又一遍地返回相同的状态。在实际程序中,这基本上是不可能的,因为程序可以处于大量可能的状态,但是您的汇编语言只允许数量有限的可能状态。

由于您的 CALL 指令就像在开始时调用程序一样工作,这是循环的唯一形式,这意味着检查代码是否两次进入相同状态很简单。带有特定参数的 CALL 指令与以该参数作为输入调用程序的效果完全相同。如果 CALL 指令与任何先前执行的 CALL 指令或程序的输入值具有相同的参数,则它必须在循环中继续执行,在相同的步骤序列中无休止地返回到相同的状态。

换句话说,唯一需要检查的状态是程序开始时的 R0 值。由于该值存储在 aint中,因此在任何常见的 C++ 实现中它只能有 2^32 个可能的值,因此蛮力检查具有给定输入的给定程序是否陷入无限循环是合理且容易的。

事实上,可以使用返回值的记忆来强力检查 O(N) 时间和 O(N) 空间中的所有可能输入,其中 N 是可能输入的数量。有多种方法可以做到这一点,但我会做的是创建三个向量,所有向量的元素数量等于可能输入的数量。第一个向量是一个bool(位)向量,记录给定输入是否已经被记忆,第二个向量也是bool向量,它记录给定输入是否已经在调用堆栈上使用,第二个向量是一个int向量记录结果并使用输入值的链接列表来创建调用堆栈以节省空间。(在下面的代码中,这些向量被称为is_memoized,input_pendingmemoized_value分别。)

我会使用您的解释器循环并将其重写为非递归的,类似于以下伪代码:

input = reg[R0]
if is_memoized[input]: 
    reg[R9] = memoized_value[input]
    return
input_pending[input] = true
memoized_value[input] = input  // mark the top of the stack

while true:
    for command in program:

        ...

        if command.op == CALL:
             argument = command.r2value

             if input_pending[argument]: 
                 // Since this input value is ready been used as input value 
                 // somewhere on the call stack this the program is about to enter
                 // an identical state as a previous state and so is stuck in
                 // a infinite loop.
                 return false  // program doesn't halt

             if is_memoized[argument]:
                 REG[R9] = memoized_value[argument]
             else:
                 memoized_value[argument] = input   // stack the input value

                 input = argument
                 REG = [input, 0, 0, 0, 0, 0, 0, 0, 0, 0]
                 input_pending[input] = true
                 break  // reevaluate the program from the beginning.

        if command.op == RET:
              argument = command.r2value
              stacked_input = memoized_value[input]
              input_pending[input] = false
              if stacked_input == input:  // at the top of the stack
                  REG[R9] = argument
                  return true   // program halts for this input

              is_memoized[input] = true
              memoized_value[input] = argument
              input = stacked_input
              REG = [input, 0, 0, 0, 0, 0, 0, 0, 0, 0] 
              break  // reevaluate the program from the beginning

然后,您将为每个可能的输入调用此解释器循环,如下所示:

for i in all_possible_inputs:
     if not program.execute(input = i):  // the function written above
          print "program doesn't halt for all inputs"
          return
print "program halts for all inputs"

递归版本应该更快,因为它不必在程序中的每个未存储的 CALL 指令上重新评估程序,但在最坏的情况下它需要数百 GB 的堆栈空间。这个非递归版本只需要 17 GB 的内存。无论哪种方式,它仍然是 O(N) 空间和时间,你只是让一个常数因子变小,另一个变大。

要在合理的时间内执行此操作,您可能还想解析一次代码,然后执行一些字节码表示。

于 2020-03-11T23:11:51.397 回答
2

我认为您正在寻找开箱即用的思维方式。

以这种方式考虑停机问题。图灵证明了程序是不受控制的。但为什么?因为该语言具有控制执行的指令。这意味着可行地调节和预测程序中的执行需要从语言中删除所有控制语义。

甚至我的协作流程架构也无法做到这一点。它只是因为他们制造的混乱而禁止他们。它仍然由包含它们的语言组成。例如,您可以使用 IF 来中断、返回或继续,但不能用于其他操作。函数调用是非法的。我创建了这样的限制来实现可控性。然而,即使是协作组织也没有从语言中删除控制结构以防止它们被滥用。

我的架构通过我的个人资料在线,我的 W 文章中有一个阶乘示例。

于 2020-03-12T19:06:21.207 回答
1

如果程序两次进入相同的配置,那么它将永远循环。图灵机也是如此,只是(无限)输入是机器配置的一部分。
这也是抽水引理背后的直觉。

什么构成模型中的配置?
由于您没有内存和 IO,因此配置由寄存器的内容和当前指令的行号(即指令指针)给出。

什么时候改变配置?
在每一个指令之后,当然。但是在非分支指令的情况下,它之前和之后的配置肯定是不同的,因为即使指令是 NOP,行号也会改变。
在分支的情况下,行号可能是我们以前见过的(对于向后分支),因此机器可以进入相同的配置。

对我来说,唯一感兴趣的跳跃指令似乎是call。相似的IF总是会产生不同的配置,因为它们的表现力不足以产生迭代(跳回并重复)。
如何call更改配置?它将行号设置为 1 并将所有寄存器(除了r0)设置为零。
因此,产生相同配置的调用条件简化为具有相同的输入。

如果您在call实现中检查操作数值是否之前已经使用过(在模拟中),那么您可以知道程序将永远循环。如果寄存器的大小为 n,则可能的状态为 O(2 n ),通常很多。
您必须准备好在(可能可定制的)阈值之后放弃。或者在您的寄存器所在的情况下int,大多数 C++ 实现都有 32-bit int,现代机器可以处理 2^32 位的 512MiB 位图。(std::vector<bool>例如实现一个打包位图;用它索引unsigned以避免负整数)。哈希表是另一种选择(std::unordered_set<int>)。但是,如果您对寄存器使用更广泛的类型,则状态将太大而无法实际记录所有可能的类型,并且您需要一些限制。限制是您的实现内置的一种限制,因为您将溢出 C++ 调用堆栈(C++ 递归深度),然后再看到被模拟机器的 2^32 重复附近的任何地方。

如果寄存器的值是无限的,这会减少到停机问题,因此在一般情况下是不可判定的。(但正如@Brendan 所说,您仍然可以寻找状态的早期重复;许多程序将以简单的方式终止或无限重复。)

如果您将call实现更改为不将其他寄存器归零,则必须回退以检查调用站点的整个配置(而不仅仅是操作数)。


要检查每个输入的程序终止,您必须以非确定性象征性的方式进行。
有两个问题:分支和输入值。

一个著名的定理是,一个 TM 可以在 NDTM 的步骤中以指数级的步数模拟一个 NDTM。
唯一有问题的指令是IF那些因为它们产生非确定性的指令。
您可以采取几种方法:

  • 将模拟分成两个分支。一个执行 IF 一个不执行。
  • 重写要模拟的代码以产生指数(在分支数中)数量的无分支代码变体。你可以懒惰地生成它们。
  • 保留一棵配置树,程序中的每个分支在树的当前节点中生成两个子节点。

它们都是等价的。

输入值是未知的,因此很难判断 a 是否以call相同的配置结束。一种可能的方法是记录对输入寄存器的所有更改,例如,您最终可能会得到类似“sub(add(add(R0, 1), 4), 5);”的描述。

这个描述应该很容易操作,因为很容易看出在上面的例子R0中没有改变,因为你得到了“sub(add(R0, 5), 5);” 然后是“R0;”。
这依赖于算术定律,您必须注意逆运算、单位元素 (1 * a = a) 和溢出。
基本上,您需要简化表达式。
然后,您可以检查输入是否在模拟时间的给定点发生了变化。

于 2020-03-11T20:09:53.317 回答
-3

如何验证程序是否会进入无限循环/递归?

在实践中; 停机问题很容易解决。只是理论上是不可能的。

人们认为停止问题无法解决的原因是该问题被构建为一个错误的困境(https://en.wikipedia.org/wiki/False_dilemma)。具体来说; 该问题要求确定程序是否将始终停止或永远不会停止;但还有第三种可能性——有时会停止(有时不会停止)。例如,假设有一个程序询问用户是要永久停止还是立即退出(并正确执行用户请求的操作)。请注意,所有理智的应用程序都是这样的——它们不应该退出,直到/除非用户告诉它们。

更正确;在实践中,有 4 种可能性:

  • 运行直到外部原因导致它停止(电源关闭,硬件故障kill -9,......)
  • 有时会自行停止
  • 总是自行停止
  • 不确定(无法确定是其他 3 种情况中的哪一种)

当然,有了这 4 种可能性,您可以说您创建了一个“停止问题解决程序”,只需将每个程序归类为“不确定”,但这不是一个好的解决方案。这给了我们一种评级系统——极好的“停止问题解决者”很少将程序归类为“不确定”,而极差的“停止问题解决者”经常将程序归类为“不确定”。

所以; 你如何创建一个好的“停止问题解决者”?这涉及 2 个部分 - 为每个函数生成控制流图 ( https://en.wikipedia.org/wiki/Control-flow_graph ) 和为每个函数生成调用图 ( https://en.wikipedia.org/wiki/Call_graph )整个程序;和价值跟踪。

控制流图和调用图

为每个函数/过程/例程生成控制流图并不难,只需检查控制流指令(调用、返回、跳转、条件分支);并且在执行此操作时生成调用图并不难(只需在看到调用指令时检查节点是否已经在调用图中,如果还没有则添加它)。

在执行此操作时,您希望将控制流更改(在每个函数的控制流图中)标记为“条件”或“非条件”,并且您希望将函数(在整个程序的调用图中)标记为“有条件” ”或“无条件”。

通过分析生成的图表,您可以将琐碎的程序分类为“运行直到外部导致它停止”或“总是自行停止”(例如,这足以将 OP 的原始代码分类为“运行直到外部导致它停止”);但大多数程序仍将是“不确定的”。

价值追踪

值跟踪是(尝试)跟踪可能在任何时间点位于任何寄存器/变量/内存位置的可能值。例如,如果一个程序将 2 个无符号字节从磁盘读取到 2 个单独的变量中,您知道这两个变量的值都在 0 到 255 之间。如果将这些变量相乘,您知道结果将是 0*0 到 255*255 之间的值; 如果添加了这些变量,您知道结果将是 0+0 到 255+255 之间的值;等等当然变量的类型给出了绝对最大可能范围,即使对于汇编(没有类型) - 例如(不知道它是有符号还是无符号)你知道从内存读取的 32 位将返回一个来自 -2147483648 的值到 4294967296。

值跟踪的重点是为每个函数在控制流图中标注条件分支;这样您就可以使用这些注释来帮助将程序分类为“不确定”以外的内容。

这就是事情变得棘手的地方——提高“实际停止问题解决者”的质量需要增加价值跟踪的复杂性/复杂性。我不知道是否有可能编写一个完美的“停止问题解决程序”(永远不会返回“不确定”),但我知道有可能编写一个足以满足几乎所有实际目的的“停止问题解决程序”(即返回“不确定”,很少有人关心)。

于 2020-03-09T00:49:27.610 回答