継続渡しを使わずに A 正規形 - let の M1 に if0 が含まれる場合

論文、Flanagan 等 The Essence of Compiling with Continuations (以下 FLA1993) の図 9 記載のアルゴリズムは、次のようなパターンに対して正しい A 正規形が得られません。

(let (x (if0 M11 M12 M13)) M2)

この場合、A 正規形の定義から、先行評価器での評価順に処理をしていけば良いので、まず M11 を評価し、その結果により M12 を評価する場合なら、M12 を評価して x を束縛した環境で M2 を評価します。M13 を評価する場合なら、M13 を評価して x を束縛した環境で M2 を評価します。

(let (t1 M11)
  (if0 t1
    (let (x M12) M2)
    (let (x M13) M2)))

さらに、M11、M12、M13 が if0 を含むこともありうるので、再帰的に変形をおこなわなければなりません。図 9 のアルゴリズムを修正するなら、let の M1 を正規化した後、if0 を外にくくりだすように修正します。

(define normalize
  (lambda (M k)
    (match M
      ; 略
      [`(let (,x ,M1) ,M2)
        (normalize M1 (lambda (N1)
          (match N1
            [`(if0 ,t ,N12 ,N13)
              (let ((M12 `(let (,x ,N12) ,M2))
                    (M13 `(let (,x ,N13) ,M2)))
                (k `(if0 ,t ,(normalize-term M12) ,(normalize-term M13)))]
            [N14 `(let (,x ,N14) ,(normalize M2 k))])))]
      ; 略
      [V (k V)])))

継続渡しを使わない ruby 版も、上と同じ処理をおこなうように修正します。

def a_normalize(m, bindings)
  if not Pair === m
    return m
  end
  case m.first
  when QUOTE
    return m
  when LAMBDA
    params = m.last.first
    m1 = m.last.last.first
    n1 = a_normalize_term(m1)
    return list(LAMBDA, params, n1)
  when LET
    x = m.last.first.first
    n1 = a_normalize(m.last.first.last.first, bindings)
    m2 = m.last.last.first
    if Pair === n1 and IF0 === n1.first
      n11 = n1.last.first
      n12 = a_normalize_term(list(LET, list(x, n1.last.last.first), m2))
      n13 = a_normalize_term(list(LET, list(x, n1.last.last.last.first), m2))
      return list(IF0, n11, n12, n13)
    else
      bindings.push list(x, n1)
      return a_normalize(m2, bindings)
    end
  when IF0
    n1 = a_normalize_name(m.last.first, bindings)
    n2 = a_normalize_term(m.last.last.first)
    n3 = a_normalize_term(m.last.last.last.first)
    return list(IF0, n1, n2, n3)
  else
    nlist = n = Pair[nil, nil]
    while not m.nil?
      nfirst = a_normalize_name(m.first, bindings)
      m = m.last
      n.last = Pair[nfirst, nil]
      n = n.last
    end
    return nlist.last
  end
end

これで、次のような2重入れ子の if0 の場合でも、A 正規形に変換することができます。

   (let (x (if0 v
             (let (y (if0 u u1 u2))
               y)
             (let (z (if0 w w1 w2))
               z)))
     x)

-> (if0 v
     (if0 u
       (let (y u1)
         (let (x y)
           x))
       (let (y u2)
         (let (x y)
           x)))
     (if0 w
       (let (z w1)
         (let (x z)
           x))
       (let (z w2)
         (let (x z)
           x))))