代码日17和18的到来:自旋锁和解释器

简体中文 English

第17天和第18天都打败了我。星星1很简单，星星2不简单。不过，对于第一颗星来说，这两个问题都很快解决了，让我们来看看。

第17天-旋转锁

对于代码日17的到来，我们必须实现一个spinlock。自旋锁是实现忙等待的一种方式。

在软件工程中，自旋锁是这样一种锁，它使试图获取它的线程简单地在循环中等待(“自旋”)，同时反复检查锁是否可用。由于线程保持活动，但不执行有用的任务，因此使用这样的锁是一种繁忙的等待。

Image title

哈斯克尔中一个简单的自旋锁实现

第17天没有视频，因为我是在床上做的，是的，我在等待《星际2》完成计算时睡着了。从来没有。我的算法太慢了。

与真正的旋转锁不同，拼图旋转锁试图吞噬无限的记忆和时间。

例如，如果每次插入旋转锁都要步进3次，循环缓冲区将开始像这样发展(在算法的每次迭代后用括号标记当前位置):

(0)，任何插入前的初始状态。
0 (1):自旋锁向前步进三次(0，0，0)，然后在其后插入第一个值1。1成为当前位置。
0 (2) 1:自旋锁向前步进三次(0，1，0)，然后在其后插入第二个值2。2成为当前位置。
0 2 (3) 1:自旋锁向前移动三次(1，0，2)，然后在其后插入第三个值3。3成为当前位置。

问题是，" 2017年之后的值是多少？"

为了找出答案，我在Haskell中构建了上述自旋锁算法的递归实现。因为哈斯克尔很有趣。

spinlock::[Int] -> Int -> Int -> Int -> Int -> (Int, [Int])
spinlock buffer steps pos i iterations
    | i < iterations = spinlock (left ++ [i] ++ right) steps nextPos (i+1) iterations
    | otherwise = (nextPos, buffer)
    where spinPos = mod (pos+steps) (length buffer)
          (left, right) = splitAt (spinPos+1) buffer
          nextPos = spinPos+1

这spinlock方法接受5个参数，我确信这在哈斯克尔中是亵渎神明的，并返回一个元组:一个整数和一个整数列表。

论点是这样的:

buffer是我们的循环缓冲区的当前状态。
steps告诉我们每次旋转要走多少步。
pos给我们缓冲区中的当前位置。
i告诉我们迭代了多少次。
iterations告诉我们总共迭代多少次。

该算法本身易于实现，但却充满了off-by-one errors。

如果我们必须继续下去-i < iterations-然后使用编辑过的缓冲区、更新过的位置和i+1。否则，返回结果。具有下一个位置和最终缓冲区的元组。

我们在旋转后得到位置，spinPos，作为当前位置之间的余数pos和steps，以及缓冲区长度。将缓冲区分成left和right在旋转后的位置，说下一个位置也会在那里。

这对2017星际1的迭代。

star1::Int -> Int
star1 steps = buffer!!pos
    where (pos, buffer) = spinlock [0] steps 0 1 2017

可能有点慢，但是很有效。

对于《星球大战2》，他们希望我们在0当执行50，000，000次迭代时。这不太顺利。

star2::Int -> Int
star2 steps = buffer!!(zeroAt+1)
    where (pos, buffer) = spinlock [0] steps 0 1 50000000
          zeroAt = Data.Maybe.fromJust $ elemIndex 0 buffer

想法很简单:迭代5000万次，寻找0，返回其后的值。

但是旋转锁永远不会结束。哈斯克尔lazy evaluation挡道，我不知道如何让它停下来。

通过惰性评估，我们将自旋锁的所有迭代保存在内存中，直到打印出最终结果。这是个问题。

耸肩

第18天——编程语言解释器

Image title

JavaScript内置的简单解释器的要点

在代码出现的第18天，我们必须为一种简单的编程语言建立一个解释器。有7个命令接受1或2个参数。参数可以是寄存器或值。

snd X播放频率等于x值的声音

set X Y将寄存器X设置为值Y

add X Y将寄存器X增加Y的值

mul X Y将寄存器X设置为寄存器X中的值乘以寄存器Y的值的结果

mod X Y将寄存器X设置为寄存器X中包含的值除以Y的值的余数(即，将X设置为以Y为模的结果)。

rcv X恢复最后播放的声音的频率，但仅当X的值不为零时(如果它为零，该命令不执行任何操作)。

jgz X Y偏移值为Y时跳转，但前提是X的值大于零(偏移值为2时跳过下一条指令，偏移值为-1时跳转到前一条指令，依此类推)。

我们的目标是找到第一个非零值rcv发现。

我用JavaScript构建了这个，因为为什么不呢？

我们从一堆registers，这是一个JavaScriptMap。

function initRegisters() {
    const registers = new Map(
        "abcdefghijklmnopqrstuvwxyz".split("").map(l => [l, 0])
    );
    registers.set("sound", null);
    registers.set("pointer", 0);

    return registers;
}

这为字母表中的每个字母加上一个sound登记册和apointer。sound会在哪里snd把它的价值和rcv阅读它们，pointer将指向我们正在执行的当前代码行。

解释器本身只有39行代码。毕竟这是一种简单的语言。虽然我认为它有足够的说明Turing-complete，它缺乏记忆。25个寄存器并不能保证图灵的完整性。

当然，你可以把它扩展成无限寄存器...

不管怎样，翻译:

function execute(registers, command) {
    const [com, val1, val2] = command.trim().split(" ");

    function getVal(val) {
        if (registers.has(val)) {
            return registers.get(val);
        } else {
            return Number(val);
        }
    }

    let jumped = false,
        kill = false;

    const commands = {
        snd: a => registers.set("sound", getVal(a)),
        set: (a, b) => registers.set(a, getVal(b)),
        add: (a, b) => registers.set(a, getVal(a) + getVal(b)),
        mul: (a, b) => registers.set(a, getVal(a) * getVal(b)),
        mod: (a, b) => registers.set(a, getVal(a) % getVal(b)),
        rcv: a => (
            console.log("SOUND:", getVal("sound")),
            (kill = true),
            registers.set(a, getVal("sound"))
        ),
        jgz: (a, b) =>
            getVal(a) > 0
                ? ((jumped = true),
                  registers.set("pointer", getVal("pointer") + getVal(b)))
                : null
    };

    commands[com](val1, val2);

    if (!jumped) {
        registers.set("pointer", getVal("pointer") + 1);
    }

    return [kill, registers];
}

我们将这一行代码分成一个command和两个值，val1和val2。

然后我们定义一个读取值的函数，getVal。如果给定的值是一个已知的寄存器，我们从它读取；否则，我们返回值本身。

之后，我们需要两个标志:jump告诉我们是否执行了跳转命令kill告诉我们是否必须停止执行。

将所有可能的命令映射到执行它们的函数的字典帮助我们运行这些命令。每个函数都操纵registers并有可能颠覆jump和kill旗帜。

当当前代码行被执行时，我们推进我们的pointer被+1如果我们不跳下去。解释器返回kill旗帜和新registers。

寄存器实际上是在适当的位置改变的，不需要返回，但是我认为这种方法使我们的实现更加清晰。

有了解释器，我们必须添加一些循环来找到AoC 18 Star 1的答案。

function star1() {
    let registers = initRegisters(),
        kill = false;
    const program = input.split("\n").filter(command => command.length > 0);

    // find sound value at first non-zero rcv
    while (
        registers.get("pointer") >= 0 &&
        registers.get("pointer") < program.length &&
        !kill
    ) {
        [kill, registers] = execute(
            registers,
            program[registers.get("pointer")]
        );
    }
}

创建寄存器，将程序分成行，execute直到awhile条件满足。要么我们跳出程序，要么一行集kill旗帜。

很有魅力。

星际2是它变得棘手的地方。那些snd和rcv命令实际上与声音无关；他们是send和receive命令，您需要并行运行这段代码的两个副本。

他们与snd和rcv。

我们必须扩大我们的sound注册到一个消息队列中，并为两个程序之间如何共享添加一些逻辑。此外，该难题希望我们在等待队列获取值时暂停每个程序的执行。

听起来很难。所以我去睡觉了。