关于图灵机、汇编、编译器、模拟器(解释器)的一些思考
我们可以定义一些最基本的计算,比如加减乘除、移位等,然后通过对基本计算进行高阶组合,形成更复杂的计算,比如幂、开方、阶乘等等
而计算机中除了基本的计算,还有基本的控制指令,比如循环、判断、递归、函数调用等
当具备这些特性后,我们就可以用他们进行组合,模拟出一个高阶的机器
比如我们可以使用c语言对内存的控制,对计算的调用,以模拟一个另一个(类)cpu的执行
一个简单的案例如下:
假设我们定义了一个处理器,有以下指令:
“ldc”, “adc”, “ldl”, “stl”, “ldnl”, “stnl”,
“add”, “sub”, “shl”, “shr”, “adj”, “a2sp”, “sp2a”, “call”, “return”,
“brz”, “brlz”, “br”, “HALT”
每个指令都以特定方式操作寄存器
那么我们可以很容易实现一个模拟器
#include "inc.h"
void run() {
switch ((char) ALU) {
case 0:
ldc(ALU >> 8);
break;
case 1:
adc(ALU >> 8);
break;
case 2:
ldl(ALU >> 8);
break;
case 3:
stl(ALU >> 8);
break;
case 4:
ldnl(ALU >> 8);
break;
case 5:
stnl(ALU >> 8);
break;
case 6:
add();
break;
case 7:
sub();
break;
case 8:
shl();
break;
case 9:
shr();
break;
case 10:
adj(ALU >> 8);
break;
case 11:
a2sp();
break;
case 12:
sp2a();
break;
case 13:
call(ALU >> 8);
break;
case 14:
_return();
break;
case 15:
brz(ALU >> 8);
break;
case 16:
brlz(ALU >> 8);
break;
case 17:
br(ALU >> 8);
break;
case 18:
HALT();
break;
default:
printf("invalid opcode: %d\n", (char) ALU);
exit(EXIT_FAILURE);
break;
}
}
void ldc(int param) {
check_pc();
B = A;
A = param;
ALU = *(array + PC++);
}
void adc(int param) {
check_pc();
A += param;
ALU = *(array + PC++);
}
void ldl(int param) {
check_pc();
check_offset(SP + param);
B = A;
A = *(array + SP + param);
ALU = *(array + PC++);
}
void stl(int param) {
check_pc();
check_offset(SP + param);
*(array + SP + param) = A;
A = B;
ALU = *(array + PC++);
}
void ldnl(int param) {
check_pc();
check_offset(A + param);
A = *(array + A + param);
ALU = *(array + PC++);
}
void stnl(int param) {
check_pc();
check_offset(A + param);
*(array + A + param) = B;
ALU = *(array + PC++);
}
void add() {
check_pc();
A += B;
ALU = *(array + PC++);
}
void sub() {
check_pc();
A = B - A;
ALU = *(array + PC++);
}
void shl() {
check_pc();
A = B << A;
ALU = *(array + PC++);
}
void shr() {
check_pc();
A = B >> A;
ALU = *(array + PC++);
}
void adj(int param) {
check_pc();
SP += param;
ALU = *(array + PC++);
}
void a2sp() {
check_pc();
SP = A;
A = B;
ALU = *(array + PC++);
}
void sp2a() {
check_pc();
B = A;
A = SP;
ALU = *(array + PC++);
}
void call(int param) {
check_pc();
B = A;
A = PC;
PC += param;
ALU = *(array + PC++);
}
void _return() {
check_pc();
PC = A;
A = B;
ALU = *(array + PC++);
}
void brz(int param) {
check_pc();
if (!A)
PC += param;
ALU = *(array + PC++);
}
void brlz(int param) {
check_pc();
if (A < 0)
PC += param;
ALU = *(array + PC++);
}
void br(int param) {
check_pc();
PC += param;
ALU = *(array + PC++);
}
void HALT() {
check_pc();
ALU = *(array + PC++);
}
以下是模拟环境运行时
#include "inc.h"
int main(int argc, char** argv) {
int exe_count = 0;
if (!load_obj(*(argv + 1)))
return 0;
A = B = PC = SP = 0;
ALU = *array;
reg_status("initial status");
while ((char) ALU != 18) {
run();
++exe_count;
}
reg_status("final status");
printf("execution complete without errors. %d instructions executed\n",
exe_count);
return 0;
}
int load_obj(const char *filename) {
FILE *obj_file;
if (NULL == (obj_file = fopen(filename, "r"))) {
printf("cannot open file '%s'\n", filename);
return 0;
}
leng = fread(array, sizeof(int), MAX_MEM, obj_file);
return 1;
}
void out_of_mem() {
reg_status("out of memory! exit failure with register status");
exit(EXIT_FAILURE);
}
void reg_status(const char *title) {
printf("%s:\nA=0X%08X,B=0X%08X,PC=0X%08X,SP=0X%08X\n", title, A, B, PC, SP);
}
void check_pc() {
check_offset(PC);
}
void check_offset(int offset) {
if (offset < 0 || offset >= MAX_MEM)
out_of_mem();
}
这样我们就可以用C语言这个机器去实现另一个“虚构”的机器
而这个“虚构”的机器我们是可以用电路将它实现的,而实现之前用C语言模拟以验证这个虚拟的机器是否完善,这只是图灵机的一个用途
而我想表达的重点是,C语言本身是一种抽象,也是一个机器,C语言底层的汇编又是一个抽象,更底层的机器,更加底层的机器指令同样是一个机器。我们可以用一个图灵完备的机器去构造另一个图灵完备的机器,而这背后考的是可计算理论来支撑
相对来说编译器是比模拟器更加容易理解的东西,虽然编译器技术难点也许更多,但是它没有什么神奇的地方,它只负责将一种语言“翻译”成另一种语言