Forth LEAVE ... LOOP 是如何实现的，因为事先不知道 LEAVE 的数量？

Question

LOOP 一词被描述为"Resolve the destination of all unresolved occurrences of LEAVE"。（强调我的）

与 IF ... ELSE ... THEN 不同的是，前向引用的数量总是一个，LOOP 对 LEAVE 的数量没有限制。那么如何实现呢？

我想到的一种方法是始终将LEAVE 的数量保持在栈顶。每个 LEAVE 都会递增此计数器并将其自身置于其下。 LOOP 从顶部读取计数器并解析那么多引用。但这似乎是一个廉价的把戏。

真正的 Forth 系统是如何实现这种循环的？我不需要 teh codez（将 Forth 作为一种学习经验），只需要概念。

Answer 1

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

另一种方法是将控制流堆栈深度存储在 DO 上，将控制流堆栈上未解析的前向引用放在 [=10 上所有其他已放置的值（使用存储的深度）之下=]，然后解析 LOOP.

上所有放置的前向引用

在BEGIN UNTIL和AHEAD THEN的基础上看我DO LOOP的high-level implementation（剧透警告）。

Answer 2

由于有人已经发布了一个很好的高级解决方案，我认为这可能有助于从不同的角度解决问题。我最近在 ARM-Thumb2 汇编中编写了一个名为 Shi 的 Forth 库。

如果您对阅读汇编代码感到满意，可以找到 leave 的来源 here。

它的工作方式几乎与您描述的一样。我使用了一个字节来计算 do...loop 构造的嵌套级别和一个我称之为 "control-flow stack pointer" 的专用堆栈指针。这个特殊的堆栈指针指向数据堆栈的末尾，可以倒序向前推引用。从另一边推入的好处是堆栈上的其他所有东西都保持不变。

然后，嵌套级别和一些指针算法允许我解析一个 leave 可能留下的所有潜在前向引用，而不管循环嵌套的深度或有多少个 leaves。

Answer 3

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

最后我做的是这样的：

每个循环都有一个从循环顶部到循环编译的分支底部，这是 ?DO 的必要条件，但即使对于 DO，我也会编译它无论如何。
每个LEAVE通过无条件分支到TOP来工作循环的（好吧，略低于顶部 - 开口右侧 branch），然后所有在它自己的分支上返回到清理代码在底部。
这样，LOOP/+LOOP就不用解析了，都已经搞定了。

我怎么想出那个喘息声来的 - 我今晚又读了一遍代码，但我仍然不明白我是如何让它工作的！

Answer 4

作为另一种方法，您可以通过未解析的地址 "holes" 线程化单链表。当 I implemented 在我的 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 !
;

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 一旦执行到那里就会停止循环。

Forth LEAVE ... LOOP 是如何实现的，因为事先不知道 LEAVE 的数量？

How is Forth LEAVE ... LOOP implemented, since number of LEAVEs is not known beforehand?

language-implementation

forth