Knuth MIX 计算机模拟器
4.91/5 (26投票s)
Don Knuth 的《计算机程序设计艺术》中的 MIX 计算机的汇编器和模拟器。
引言和背景
MIX 计算机是由 Don Knuth 在 20 世纪 60 年代发明的一个虚构计算机，用于阐述他对计算机算法的论述。正如 Knuth 所说，使用虚构的计算机和机器语言有助于避免读者因某个特定计算机系统的技术细节而分心，从而将重点放在那些永远有效、不受任何技术演进或当前趋势影响的真理上。
这一陈述的真实性毋庸置疑。然而，现在出现了另一种问题。MIX 计算机，嗯……是虚构的。读者无法对其进行实验，也无法通过坐在真实的计算机终端前编写程序来尝试解决练习题。甚至无法确定某个练习题的特定解决方案是否正确，除非检查练习的答案，而且即使如此，一个问题也可能有很多不同的解决方案，但答案只提供一个。除非读者愿意在脑海中或纸上模拟 MIX。这很可能就是 Knuth 对读者的期望。毕竟，毫无疑问，从书中获益最多的是那些有耐心、勤奋地完成这类过程的读者。但它仍然是一项艰巨的任务，通常令人沮丧，而且对许多人来说，在很多方面，这正是 Knuth 最初希望读者避免的那种分心。
这正是 MIX 模拟器试图解决的问题：一个能够汇编和执行用 MIXAL 语言（MIX 计算机的汇编语言）编写的程序的工具套件。其功能包括一个简化的调试器、对 MIX 计算机设备的完整实现、符号表生成、列表生成以及为 TeX 排版等。
MIX 计算机和 MIXAL 汇编语言的完整规范可以在《计算机程序设计艺术》第一卷中找到。事实上，如果您没有阅读过或无意阅读这系列书籍、遵循其示例并解决其练习题，那么这个软件包对您几乎没有用处。所以，尽情享受使用它吧，但首先，请享受阅读书籍的乐趣！
使用工具
MIXWare 发行版包含完整的 PDF 格式文档。在其中，您可以找到有关如何执行汇编器并充分利用模拟器的详细说明。不过，这里有一个（非常）简短的教程。
汇编 MIXAL 程序
MIXASM -f:card -o:primes.deck primes.mixal
此命令将文件“primes.mixal”汇编成打孔卡片组，并将输出保存到“primes.deck”。
MIXASM 的通用语法是
MIXASM [arguments] [input-file]
其中可选的 input-file 参数是包含 MIXAL 代码的文本文件的名称（如果未指定，则从键盘输入），而 arguments 控制编译过程。特别是，--output（或简称为 -o）参数指定编译后的输出文件名（如果未指定，则发送到标准输出），例如 --output:primes.deck 将输出发送到文件 primes.deck。--format（或简称为 -f）参数指定编译后的输出是打孔卡片组还是序列化的二进制文件。例如，-f:card 指定输出为卡片组，而 -f:binary 指定输出为序列化的二进制文件。--symtab（或简称为 -s）将程序的符号表输出到标准输出或指定文件（其工作方式与 --output 参数相同）。类似地，--list-file（或简称为 -lf）生成程序列表。在这种情况下，文件名是必需的。如果您请求了列表或符号表，您还可以选择指定 --pretty-print（或简称为 -pp）来请求将输出生成为 TeX 文件，以便您可以运行 TeX 进行精美的排版。
启动模拟器
MIX --deck primes.deck or MIX --binary primes.bin
此命令启动模拟器，并加载文件“primes.deck”或“primes.bin”中的卡片组，具体取决于源文件是编译为卡片组还是序列化二进制文件。
模拟器启动后，会立即显示一个提示符，供您输入命令。此时，您可以按 ? 获取有关其他命令的帮助，其中最重要的命令是“run”，它会开始执行程序直到程序停止；“step”，它只执行程序计数器指向的下一个命令；当然，还有“quit”，如果您已经受够了！还有大量命令，都以“show”开头，用于显示 MIX 计算机的当前状态，以及另一组以“set”开头的命令，用于修改该状态。例如：
show memory- 显示 MIX 内存的内容。您可以指定一个范围，例如show memory 3000 3010以仅显示 11 个字。如果指定了范围，您还可以请求反汇编，例如show memory 3000 3010 with disassembly。show state- 显示 MIX 的内部状态，即所有寄存器、标志和程序计数器的值。set <reg> <value>- 设置特定 MIX 寄存器的值，例如set rA 100。
文档的第 1 章和第 2 章详细描述了 MIXASM 和 MIX，包括模拟器的命令集以及汇编器命令行参数的完整描述。
关注点
开发这两个工具是编译器编写的一次绝佳练习。MIXAL 编译器是完全手工编写的。一个特别有趣的点是，MIXAL 文法必须转换为 LL(1) 才能让递归下降解析器对其进行解析。文档的第 4 章详细描述了解析器的开发。附录 B 包含 MIXAL 语法图。
扫描器实现
一个值得注意的有趣点是扫描器。Scanner 类最重要的属性是 Tokens 属性，这是一个 Token 对象的枚举。Token 类未在下面列出，但简而言之，它包含扫描器刚刚识别的令牌类型以及它在源代码文件中的位置。
public IEnumerable<Token> Tokens
{
get
{
StringReader input = new StringReader(line);
ScannerState state = ScannerState.LABEL;
byte col = 0, endCol = 0;
while (input.Peek() != -1)
{
char ch = (char)input.Peek();
if (char.IsUpper(ch) || char.IsDigit(ch))
{
StringBuilder accum = new StringBuilder();
while (char.IsUpper(ch) || char.IsDigit(ch))
{
accum.Append(ch);
input.Read();
endCol++;
ch = (char)input.Peek(); // Get the next character
}
int temp = 0;
switch (state)
{
case ScannerState.LABEL:
// Labels cannot be numeric constants
if (int.TryParse(accum.ToString(), out temp))
{
throw new ScannerException(lineNum, col,
"Expected: SYMBOL, Found: NUMBER");
}
// Symbols can be up to ten characters
if (accum.ToString().Length > 10)
{
throw new ScannerException(lineNum, col,
string.Format("Symbol '{0}' is too long",
accum.ToString()));
}
yield return new Token { ColumnNumber = col,
Text = accum.ToString(), Type = TokenType.LABEL };
col = endCol;
break;
// Opcodes are special MIX keywords
case ScannerState.OPCODE:
// Here we check the text to see that it conforms
// to the MIX instruction set, or a pseudo op etc...
var tokText = accum.ToString().Trim();
if (MIXMachine.INSTRUCTION_LIST.FindIndex(
i => i.Name == tokText) != -1)
yield return new Token { ColumnNumber = col,
Text = tokText, Type = TokenType.KEYWORD };
else if (tokText == "ORIG")
yield return new Token { ColumnNumber = col,
Text = tokText, Type = TokenType.ORIG };
else if (tokText == "EQU")
yield return new Token { ColumnNumber = col,
Text = tokText, Type = TokenType.EQU };
else if (tokText == "CON")
yield return new Token { ColumnNumber = col,
Text = tokText, Type = TokenType.CON };
else if (tokText == "ALF")
{
state = ScannerState.STRING;
yield return new Token { ColumnNumber = col,
Text = tokText, Type = TokenType.ALF };
}
else if (tokText == "END")
yield return new Token { ColumnNumber = col,
Text = tokText, Type = TokenType.END };
else
throw new ScannerException(lineNum, col,
string.Format("Expected: KEYWORD " +
"or PSEUDO, Found: '{0}'", tokText));
col = endCol;
break;
// Operands can be any symbol or number
case ScannerState.OPERAND:
if (int.TryParse(accum.ToString(), out temp))
{
if (accum.ToString().Length > 10)
{
throw new ScannerException(lineNum, col,
string.Format("Number '{0}' is too long",
accum.ToString()));
}
yield return new Token { ColumnNumber = col,
Text = accum.ToString(), Type = TokenType.NUMBER };
}
else
{
if (accum.ToString().Length > 10)
{
throw new ScannerException(lineNum, col,
string.Format("Symbol '{0}' is too long",
accum.ToString()));
}
yield return new Token { ColumnNumber = col,
Text = accum.ToString(), Type = TokenType.SYMBOL };
}
col = endCol;
break;
}
}
else if (ch == '/')
{
input.Read();
endCol++;
if ((char)input.Peek() == '/')
{
input.Read();
endCol++;
yield return new Token { ColumnNumber = col, Text = "//",
Type = TokenType.SLASHSLASH };
}
else
yield return new Token { ColumnNumber = col, Text = "/",
Type = TokenType.SLASH };
col = endCol;
}
else if (char.IsWhiteSpace(ch))
{
// Read the first blank
input.Read();
endCol++;
if (state != ScannerState.STRING)
{
// Change the scanner state
switch (state)
{
case ScannerState.LABEL:
state = ScannerState.OPCODE;
col = ReadToNextChar(input, col);
break;
case ScannerState.OPCODE:
state = ScannerState.OPERAND;
col = ReadToNextChar(input, col);
break;
case ScannerState.OPERAND:
yield break;
}
}
else
{
ch = (char)input.Peek();
if (char.IsWhiteSpace(ch))
{
input.Read();
endCol++;
ch = (char)input.Peek();
}
string sc = ((char)input.Read()).ToString();
// Read four more characters
for (var i = 0; i < 4; i++)
{
if (input.Peek() == -1)
yield return new Token { ColumnNumber = col,
Type = TokenType.STRING, Text = sc.PadRight(5) };
sc += (char)input.Read();
}
yield return new Token { ColumnNumber = col,
Type = TokenType.STRING, Text = sc };
}
}
else
switch (ch)
{
case '+':
endCol++;
input.Read();
yield return new Token { ColumnNumber = col,
Text = "+", Type = TokenType.PLUS };
col = endCol;
break;
case '-':
endCol++;
input.Read();
yield return new Token { ColumnNumber = col,
Text = "-", Type = TokenType.MINUS };
col = endCol;
break;
case '*':
endCol++;
input.Read();
yield return new Token { ColumnNumber = col,
Text = "*", Type = TokenType.STAR };
col = endCol;
break;
case '(':
endCol++;
input.Read();
yield return new Token { ColumnNumber = col,
Text = "(", Type = TokenType.LPAREN };
col = endCol;
break;
case ')':
endCol++;
input.Read();
yield return new Token { ColumnNumber = col,
Text = ")", Type = TokenType.RPAREN };
col = endCol;
break;
case ',':
endCol++;
input.Read();
yield return new Token { ColumnNumber = col,
Text = ",", Type = TokenType.COMMA };
col = endCol;
break;
case ':':
endCol++;
input.Read();
yield return new Token { ColumnNumber = col,
Text = ":", Type = TokenType.COLON };
col = endCol;
break;
case '=':
endCol++;
input.Read();
yield return new Token { ColumnNumber = col,
Text = "=", Type = TokenType.EQUALS };
col = endCol;
break;
default:
throw new ScannerException(lineNum, col,
string.Format("Unexpected character: '{0}'", ch));
}
}
}
}
扫描器在任何时候都可能处于以下状态之一：LABEL、OPCODE、OPERAND 或 STRING。一旦扫描器遇到空格，它会按此顺序更改状态：LABEL -> OPCODE -> OPERAND，除非 OPCODE 是“ALF”，在这种情况下，序列为 LABEL -> OPCODE -> STRING。这可能令人惊讶，但扫描器会特殊处理“ALF”操作码，因为它需要知道它将扫描字符串还是操作数。这个小细节本应是解析器的任务，但在这种情况下，它使事情变得更容易。还要注意 yield return 的使用。这使我们只有在需要下一个令牌时才能查询扫描器。
模拟器实现
MIX 机器由各种组件组成：
- 4000 字的内存；
- 各种字长的寄存器；
- 约 150 条指令的指令集；
- 各种可选的异步 I/O 设备：磁带驱动器、磁盘、打卡机、行式打印机、纸带和终端。
这些组件已封装在 C# 类中，并由 MIXMachine 类将它们全部串联在一起。
MIXWord 类表示 MIX 内存的一个字：5 个 6 位字节。该类中最相关部分如下所示。
public class MIXWord
{
#region Fields
public int this[byte index]
{
get
{
if (index < 0 || index > WORD_SIZE)
throw new Exception("Invalid word index.");
if (index == 0)
return Sign == Sign.Positive ? 0 : 1;
string strBitmask = BYTE_ONE + Enumerable.Repeat(BYTE_ZERO,
(WORD_SIZE - index)).Aggregate("", (x, y) => x + y);
int bitmask = Convert.ToInt32(strBitmask, 2);
return (data & bitmask) >> ((WORD_SIZE - index) * BYTE_SIZE);
}
set
{
if (index < 0 || index > WORD_SIZE)
throw new Exception("Invalid word index.");
if (index == 0)
{
if (value == 1)
Sign = Sign.Negative;
else if (value == 0)
Sign = Sign.Positive;
else
throw new Exception("Invalid sign value.");
}
else
{
byte leftCount = (byte)(index - 1);
byte rightCount = (byte)(WORD_SIZE - index);
int bitmaskClear = Convert.ToInt32(
"1" + // Sign
Enumerable.Repeat(BYTE_ONE, leftCount).Aggregate("", (x, y) => x + y) +
BYTE_ZERO +
Enumerable.Repeat(BYTE_ONE, rightCount).Aggregate("", (x, y) => x + y),
2);
string valString = Convert.ToString(Math.Abs(value), 2);
valString = Enumerable.Repeat("0",
BYTE_SIZE - valString.Length).Aggregate("", (x, y) => x + y) + valString;
int bitmaskSet = Convert.ToInt32(
"0" +
Enumerable.Repeat(BYTE_ZERO, leftCount).Aggregate("", (x, y) => x + y) +
valString +
Enumerable.Repeat(BYTE_ZERO, rightCount).Aggregate("", (x, y) => x + y),
2);
data &= bitmaskClear;
data |= bitmaskSet;
}
}
}
public int this[byte l, byte r]
{
get
{
// If the fieldspecs are given in the wrong order
if (l > r)
{
byte t = r;
r = l;
l = t;
}
if (l < 0 || l > WORD_SIZE)
throw new Exception("Invalid word index (left).");
if (r < 0 || r > WORD_SIZE)
throw new Exception("Invalid word index (right).");
if (r == 0)
return this[0];
bool useSign = false;
if (l == 0)
{
l++;
useSign = true;
}
byte leftCount = (byte)(l - 1);
byte midCount = (byte)(1 + (r - l));
byte rightCount = (byte)(WORD_SIZE - r);
int bitmask = Convert.ToInt32(
Enumerable.Repeat(BYTE_ZERO, leftCount).Aggregate("", (x, y) => x + y) +
Enumerable.Repeat(BYTE_ONE, midCount).Aggregate("", (x, y) => x + y) +
Enumerable.Repeat(BYTE_ZERO, rightCount).Aggregate("", (x, y) => x + y),
2);
int result = (data & bitmask) >> (rightCount * BYTE_SIZE);
if (useSign && Sign == Sign.Negative)
return -result;
return result;
}
set
{
// If the fieldspecs are given in the wrong order
if (l > r)
{
byte t = r;
r = l;
l = t;
}
if (l < 0 || l > WORD_SIZE)
throw new Exception("Invalid word index (left).");
if (r < 0 || r > WORD_SIZE)
throw new Exception("Invalid word index (right).");
if (r == 0)
{
this[0] = value;
return;
}
bool useSign = false;
if (l == 0)
{
l++;
useSign = true;
}
byte leftCount = (byte)(l - 1);
byte midCount = (byte)(1 + (r - l));
byte rightCount = (byte)(WORD_SIZE - r);
int bitmaskClear = Convert.ToInt32(
"1" + // Sign
Enumerable.Repeat(BYTE_ONE, leftCount).Aggregate("", (x, y) => x + y) +
Enumerable.Repeat(BYTE_ZERO, midCount).Aggregate("", (x, y) => x + y) +
Enumerable.Repeat(BYTE_ONE, rightCount).Aggregate("", (x, y) => x + y),
2);
string valString = Convert.ToString(Math.Abs(value), 2);
valString = Enumerable.Repeat("0",
BYTE_SIZE * midCount - valString.Length).Aggregate("", (x, y) => x + y) +
valString;
int bitmaskSet = Convert.ToInt32(
"0" + // Sign
Enumerable.Repeat(BYTE_ZERO, leftCount).Aggregate("", (x, y) => x + y) +
valString +
Enumerable.Repeat(BYTE_ZERO, rightCount).Aggregate("", (x, y) => x + y),
2);
data &= bitmaskClear;
data |= bitmaskSet;
if (useSign)
{
// Clear sign
data &= PLUS_MASK;
Sign = value < 0 ? Sign.Negative : Sign.Positive;
}
}
}
#endregion
}
MIXWord 类已实现，因此我们可以对其进行索引以获取单词切片。这已通过位掩码完成。
MIX 的异步设备都继承自 MIXDevice 抽象类。
public abstract class MIXDevice
{
/// <summary>
/// The descriptive name of this device
/// </summary>
public string Name { get; private set; }
/// <summary>
/// The device's backing store
/// </summary>
protected Stream Store
{
get { return store; }
set
{
lock (this)
{
Ready = false;
store = value;
StoreChanged();
Ready = true;
}
}
}
public bool Ready { get; protected set; }
private Stream store;
protected virtual void StoreChanged() { }
/// <summary>
/// The device's block size in MIX words
/// </summary>
protected byte BlockSize { get; private set; }
/// <summary>
/// The MIX machine this device is attached to
/// </summary>
protected MIXMachine Machine { get; private set; }
protected MIXDevice(MIXMachine machine, string name,
Stream store, byte blockSize)
{
Name = name;
Store = store;
BlockSize = blockSize;
Machine = machine;
}
public void Redirect(Stream newStore)
{
if (Store != null) Store.Close();
Store = newStore;
}
public void Flush()
{
if (Store != null && Store.CanWrite) Store.Flush();
}
protected string MIXWordToString(MIXWord w)
{
string result = "";
for (byte i = 1; i < 6; i++)
{
var ch = from c in MIXMachine.CHAR_TABLE
where w[i] == c.Value
select c.Key;
result += ch.DefaultIfEmpty('â–ˆ').First().ToString();
}
return result;
}
public override string ToString()
{
string result = "";
if (Store == null)
result = string.Format("NAME: {0}; BLOCK SIZE: {1}; BACKING STORE: N/A",
Name, BlockSize);
else if (Store is FileStream)
result = string.Format("NAME: {0}, BLOCK SIZE: {1}, BACKING STORE: {2}",
Name, BlockSize, (Store as FileStream).Name);
else if (Store is MemoryStream)
result = string.Format("NAME: {0}, BLOCK SIZE: {1}, BACKING STORE: MEMORY",
Name, BlockSize);
else
result = string.Format("NAME: {0}, BLOCK SIZE: {1}, BACKING STORE: CONSOLE",
Name, BlockSize);
return string.Format(result);
}
public void Out(int M)
{
Thread t = new Thread(OutProc);
t.Start(M);
}
public void In(int M)
{
Thread t = new Thread(InProc);
t.Start(M);
}
public void IOC(int M)
{
Thread t = new Thread(IOCProc);
t.Start(M);
}
protected abstract void OutProc(object M);
protected abstract void InProc(object M);
protected abstract void IOCProc(object M);
}
具体设备是通过继承该类并覆盖 OutProc()、InProc() 和 IOCProc() 方法来实现的。每个设备都有一个后备存储，可以是 MemoryStream、FileStream 或控制台本身。Redirect() 方法提供了一种更改此后备存储的方法。
MIX 基础设施的最后一部分是其指令集。每条 MIX 指令都是一个 MIXInstruction 对象。
public class MIXInstruction
{
private Action<MIXWord, byte, byte> executionProc;
public string Name { get; private set; }
public MIXInstruction(string name, Action<MIXWord, byte, byte> executionProc)
{
this.Name = name;
this.executionProc = executionProc;
}
public void Execute(MIXWord address, byte index, byte field)
{
executionProc(address, index, field);
}
public void Execute(MIXWord address, byte index, byte left, byte right)
{
executionProc(address, index, (byte)(left * 8 + right));
}
}
为了创建一个 MIXInstruction 对象，我们将一个匿名方法传递给其构造函数，该方法会在请求执行该指令对象时被执行。
instructionTable = new List<MIXInstruction>();
#region Load Operators
instructionTable.Add(new MIXInstruction("LDA",
(a, i, f) =>
{
int M = a + (i > 0 ? I[i - 1].Value : 0);
A.Value = Memory[M][(byte)(f / 8), (byte)(f % 8)];
PC++;
}));
其他细节
MIX 模拟器接口 MIX 是命令行驱动的。文档的第 3 章描述了其大纲。此程序没有什么特别值得注意的。但是，值得注意的是，上面描述的构成 MIX 机器的类存储在一个单独的库中，因此您可以开发 MIX 机器的 GUI，而不是这些工具提供的命令行界面。此类贡献非常受欢迎！
历史
- 2011 年 2 月 1 日：首次公开发布。