Forth中如何实现LEAVE ... LOOP，因为LEAVE的数量事先未知？

Question

单词LOOP被描述为“解决所有未解决的LEAVE出现的目标”（我加重了语气）。

与IF ... ELSE ... THEN不同，其中前向引用的数量始终为1，LOOP对LEAVE的数量没有限制。那么如何实现呢？

我想到的一种方法是始终在堆栈顶部保持LEAVE的数量。每个LEAVE都会增加此计数器并将自己放在其下面。LOOP从顶部读取计数器并解决相应数量的引用。但这似乎是一个廉价技巧。

真正的Forth系统如何实现这种循环？我不需要代码（已经在实现Forth作为学习经验），只需要概念。

- shinkarom

Answer 1

在SP-Forth中，循环控制参数包括索引、限制和LOOP后的地址。因此，在编译时不需要解决LEAVE，它可以在运行时从循环控制参数中知道地址。

另一种方法是将控制流堆栈深度存储在DO上，在控制流堆栈上放置未解决的前向引用，该引用位于所有已放置值（使用存储深度）之下，然后在LOOP上解决所有放置的前向引用。

请查看我的高级实现DO LOOP，基于BEGIN UNTIL和AHEAD THEN（剧透警告）。链接：high-level implementation。

- ruvim

---

这里似乎有两个问题。a: 未知数量的LEAVES和b: LEAVE可以跳出另一个控制结构的中间 - 比如DO...IF LEAVE THEN LOOP，这种组合似乎会创建过于复杂且因此脆弱的解决方案？ - Mitra Ardron

@MitraArdron，我的解决方案涵盖了这两个问题，因此它非常健壮。并且可以在任何足够丰富的标准Forth系统中进行测试。唯一实质性的环境依赖是控制流堆栈应该使用数据堆栈来实现。也就是说，否则代码应该被调整以处理单独的控制流堆栈（或者为了可移植性而使用cs-roll）。 - ruvim

Answer 2

作为另一种方法，您可以通过未解决的地址“空洞”来传递单向链表。在我的FORTH中实现计数循环时，我使用了这种方法：我所实现的。

( We can now define DO, ?DO, LOOP, +LOOP and LEAVE. It would be much easier
  if LEAVE didn't exist, but oh well. Because storing LEAVE's data on the stack
  would interfere with other control flow inside the loop, let's store it in a variable. )

VARIABLE LEAVE-PTR

( Let's consider the base case: only one LEAVE in the loop. This can be trivially
  handled by storing the address we need to patch in the variable.

  This would also work quite well with nested loops. All we need to do is store
  the old value of the variable on the stack when opening a loop.

  Finally, we can extend this to an arbitrary number of LEAVEs by threading
  a singly-linked list through the branch target address holes. )

\ ...

: LEAVE, ( -- )
  HERE
  LEAVE-PTR @ ,
  LEAVE-PTR !
;

: LEAVE POSTPONE BRANCH LEAVE, ; IMMEDIATE

: DO ( -- old-leave-ptr loop-beginning )
  LEAVE-PTR @
  0 LEAVE-PTR !
  POSTPONE 2>R
  HERE
; IMMEDIATE

\ SOME-LOOP is the common code between LOOP and +LOOP
: SOME-LOOP ( old-leave-ptr loop-beginning -- )
  POSTPONE 0BRANCH ,
  LEAVE-PTR @
  BEGIN
    ?DUP
  WHILE
    DUP @ >R
    HERE SWAP !
    R>
  REPEAT
  POSTPONE UNLOOP
  LEAVE-PTR !
;

- Maya

Answer 3

在开发我的Forth语言时，我发现这非常困难（就像你一样，作为学习经验）。

最终我做的是：

1. 每个循环都有一个从顶部到底部编译的分支，这对于?DO是必需的，但即使是DO，我也会编译它。
2. 每个LEAVE都通过无条件跳转到循环的顶部（稍微低于顶部 - 直接到开放分支），然后所有自己回到底部的清理代码。
3. 这样，LOOP / + LOOP没有什么需要解决的，所有事情都已经完成了。

我不知道我是如何想出这个点子的 - 我今晚再次阅读代码，我仍然不明白我是如何让它工作的！

- phisheep

---

当LEAVE嵌套时，它如何无条件地返回到循环的顶部，即如何找到该循环，例如在DO..IF..LEAVE .. THEN ... LOOP中。 - Mitra Ardron

好的观点。我忘了提到（当时我是这样做的），我有一个单独的控制堆栈用于循环 - 避免它与所有其他控制结构混淆。因此，尽管我从不知道循环的底部在哪里，但我始终可以找到最内层循环的顶部。 - phisheep

Answer 4

由于已经有人发布了一个很好的高级解决方案，我认为从不同的角度来解决问题可能会有所帮助。我最近写了一个名为Shi的Forth库，它使用ARM-Thumb2汇编语言。

如果您熟悉阅读汇编代码，可以在这里找到leave源代码。

它的工作方式几乎与您描述的相同。我使用了一个单字节来计算do...loop结构的嵌套级别，并使用了一个专用的堆栈指针，我称之为“控制流堆栈指针”。这个特殊的堆栈指针指向数据堆栈的末尾，并且可以以相反的顺序推送前向引用。从另一侧推入东西的好处是堆栈上的其他所有内容都不受影响。

然后，通过嵌套级别和一些指针算术，我可以解析所有可能留下的leave的前向引用，而无论循环嵌套多深或有多少个leave。

- Vinci

Answer 5

在 fig-Forth 中，DO 和其它指令的实现非常简单且体积较小。

它有一组原语词汇来实现运行时行为。这些都是用机器码实现的。

(DO)   ( limit start -- ) move the two values to the return stack
I      ( -- index )       fetch the current value of the index variable
LEAVE  ( -- )             set the current index=limit
(LOOP) ( -- )             checks index<limit and branch back if true.

因此，编译器所要做的就是跟踪单个分支地址返回到循环的起始位置，并编译紧随其后的偏移量（LOOP）。这些都是用高级代码实现的。

: BACK  HERE - , ;
: DO  COMPILE (DO) HERE ; IMMEDIATE
: LOOP  COMPILE (LOOP) BACK ; IMMEDIATE

所以，在这个定义中，LEAVE根本不会执行分支操作。它只是调整存储的索引值，以便LOOP在执行到那里时停止循环。

- luser droog

---

不幸的是，这段代码不符合LEAVE的ANS规范 - 在LEAVE和(LOOP)之间的代码必须被跳过 - 并且解决这些分支很困难。 - Mitra Ardron