2025年9月15日月曜日

ForthのCFスタックに似た記述：Lisp（TAGBODY/GO）と連結言語（PostScript/Factor/Joy）

ForthのCFスタックに似た記述：Lisp（TAGBODY/GO）と連結言語（PostScript/Factor/Joy）

Forthの CF（制御フロー）スタック に似た記述

A) Lisp：TAGBODY/GO（未解決ジャンプの後パッチ）と、B) 連結言語：PostScript/Factor/Joy（quotation合成子）での対比を、コード例と対応表でまとめました。

A) Common Lisp：TAGBODY/GO で “前方ラベル→後で確定”

Forthの IF/ELSE/THEN は、実行時には 0BRANCH/BRANCH へ展開され、コンパイル時は “未解決ジャンプ先” を CFスタックで保持して THEN で埋めます。Common Lisp でも TAGBODY/GO と gensym を使えば同趣旨を実現できます。

;;; Statement風（値は変数経由で返す）
(defmacro my-if (test then &optional else)
  (let ((ELSE (gensym "ELSE-")) (END (gensym "END-")) (res (gensym "RES-")))
    `(let (,res)
       (tagbody
         (unless ,test (go ,ELSE))
         (setf ,res (progn ,then))
         (go ,END)
       ,ELSE
         (setf ,res (progn ,@ (when else (list else))))
       ,END)
       ,res)))

(defmacro my-while (test &body body)
  (let ((START (gensym "START-")) (END (gensym "END-")))
    `(tagbody
       ,START
         (unless ,test (go ,END))
         (progn ,@body)
         (go ,START)
       ,END)))

;; 使用例
(let ((x 3))
  (my-if (> x 0)
         (format t "pos~%")
         (format t "non-pos~%")))

(let ((i 0))
  (my-while (< i 3)
    (format t "i=~A~%" i)
    (incf i)))
ポイント： ネストすると ELSE/END ラベルが LIFO で解決されます。これは “CFスタックに未解決を積み、THENでポップしてパッチ” と同型です。

対応図：ForthのIF…THEN と Lispマクロ

Forth 構文CFスタック効果（概念）Lisp 側の動作
IF( C: -- orig ) 未解決0分岐(unless test (go ELSE)) を生成
ELSE( C: orig1 -- orig2 )then部末尾に (go END)、ついで ELSE: ラベル
THEN( C: orig -- ) 解決END: ラベルで前方ジャンプが確定
補足：式コンテキストでの値返却

TAGBODY/GO は飛び先指向で値を返しません。上の my-if は一時変数 res に値を詰めて最後に返すことで、式風に使えるようにしています。

B) 連結言語：合成子（quotation）で分岐を表現

PostScript / Factor / Joy では、分岐先を 第一級オブジェクト（実行配列＝quotation）として積み、if/ifelse/when/ifte/while といった 合成子で実行します。内部実装は処理系次第ですが、低レベルでは「条件評価→選んだ塊へジャンプ」であり、Forthの展開と平行です。

PostScript

/abs { dup 0 lt { neg } { } ifelse } def

% while相当（擬似）：
/while { % ( procCond procBody -- )
  { 2 copy exec { pop exec true }{ pop pop false } ifelse } loop
} def

Factor

: abs   ( n -- n )  dup 0< [ neg ] when ;
: abs2  ( n -- n )  dup 0< [ neg ] [ ] if ;

! while:  ( .. quot:cond .. quot:body -- .. ) while

Joy

DEFINE abs == dup 0 < [ neg ] [ ] ifte .

! while:  [ cond ] [ body ] while
直観： 「分岐先＝値」として積むので、ネストは自然に安全です。処理系がJIT/VM化すれば、適宜 BRANCH/0BRANCH に落とし込み、必要に応じて**後パッチ**します。

対応表：Forth ⇔ Lisp/連結言語

Forth（構文）CF効果（概念）Lisp（TAGBODY/GO）連結言語（合成子）
IF ... ELSE ... THEN orig を積んで THEN で解決 unless test (go ELSE) → then末尾で (go END) → END: cond [ then ] [ else ] if/ifelse
BEGIN ... UNTIL dest を積み、条件成立で後方に0分岐 START: / unless test (go END) / (go START) [ cond ] [ body ] while（語による）
DO ... LOOP Rに loop-sys（limit/index） 低レベルではインデックス変数＋GOで再現可能 [ body ] each等、語彙に依存

実装ノート／落とし穴

  • Lisp側： TAGBODY/GO は「飛ぶ」ための構文です。式として値を返したい場合は、例のように一時変数で束ねるか BLOCK/RETURN-FROM の組み合わせを検討します。
  • Forth側： Rスタックは本来システム用。ループの I/J/K や LEAVE と干渉しうるため、>R R> による退避はスコープを短く。
  • 連結言語： quotationは第一級。最適化やJITでジャンプ命令に落とす場合、ネストの解決順は概ねLIFO（CFスタック的）になります。
このページは単一HTMLとして作成されています。必要に応じてCDNの highlight.js を読み込みます（オフラインでも表示は可能）。
投稿者