Oz - 一般的計算モデル(宣言的計算モデル(末尾再帰, スタックの大きさ))

コンピュータプログラミングの概念・技法・モデル
(IT Architect' Archive
クラシックモダン・コンピューティング6)
(IT Architects’Archive CLASSIC MODER)
(翔泳社)
セイフ・ハリディ (著), ピーター・ヴァン・ロイ (著)
Peter Van-Roy (著), Seif Haridi (著), 羽永 洋 (翻訳)
原書: Concepts, Techniques,
and Models of Computer Programming

開発環境

• OS X Yosemite - Apple (OS)
• Emacs (Text Editor)
• Oz (プログラミング言語)
• Mozartプログラミングシステム(Mozart 2) (実装)

コンピュータプログラミングの概念・技法・モデル(IT Architect' Archiveクラシックモダン・コンピューティング6) (IT Architects’Archive CLASSIC MODER)(セイフ・ハリディ (著)、ピーター・ヴァン・ロイ (著)、Peter Van-Roy (著)、 Seif Haridi (著)、羽永 洋　(翻訳) 、翔泳社、原書: Concepts, Techniques, and Models of Computer Programming(CTM))の第部(一般的計算モデル)、第2章(宣言的計算モデル)、2.9(練習問題)、9-b.(末尾再帰)を解いてみる。

9-b.(末尾再帰)

{Sum1 10}を手で実行。

コード(Emacs)

([(
local Sum1 X A in
   Sum1= proc {$ N ?R}
            if N==0 then R=0
            else
               local Rr in
                  {Sum1 N-1 Rr}
                  R=N+Rr
               end
            end
         end
   X=10
   {Sum1 X A}
end,
Φ)],
Φ)

local文を実行
([(
Sum1= proc {$ N ?R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end
X=10      
{Sum1 X A},
{Sum1 -> s, X -> x, A -> a})],
{s, x = 10, a})

直列合成
([(
Sum1= proc {$ N ?R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end
, {Sum1 -> s, X -> x, A -> a}),
({Sum1 X A}, {Sum1 -> s, X -> x, A -> a})],
{s, x = 10, a})

束縛Sum1=..を実行
([({Sum1 X A}, {Sum1 -> s, X -> x, A -> a})],
{t = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ),
 s = t, x = 10, a})

{t = ..., s = t}を簡略化
([({Sum1 X A}, {Sum1 -> s, X -> x, A -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ), x = 10, a})

手続き{Sum1 X A}の呼び出しを実行
([(
if N==0 then R=0
else
   local Rr in
      {Sum1 N-1 Rr}
      R=N+Rr
   end
end, {Sum1 -> s, N -> x, R -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ), x = 10, a})

比較 N==0の実行後
([(local Rr in {Sum1 N-1 Rr} R=N+Rr end, {Sum1 -> s, N -> x, R -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ), x = 10, a})

local Rr in ...文を実行
([({Sum1 N-1 Rr} R=N+Rr end, {Rr -> r, Sum1 -> s, N -> x, R -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ), x = 10, a, r})

直列合成
([({Sum1 N-1 Rr}, {Rr -> r, Sum1 -> s, N -> x, R -> a}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ), x = 10, a, r})

手続き{Sum1 N-1 Rr}の実行
([(
if N==0 then R=0
else
   local Rr in
      {Sum1 N-1 Rr}
      R=N+Rr
   end
end, {Sum1 -> s, N -> x1, R -> r}),
(R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ), x = 10, a, r, x1 = 9})

比較 N==0の実行後
([(local Rr in {Sum1 N-1 Rr} R=N+Rr end, {Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ), x = 10, a, r, x1 = 9})

local文の実行
([({Sum1 N-1 Rr} R=N+Rr end, {Rr -> r1, Sum1 -> s, N -> x1, R -> r})
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ), x = 10, a, r, x1 = 9, r1})

直列合成
([({Sum1 N-1 Rr}, {Rr -> r1, Sum1 -> s, N -> x1, R -> r})
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ), x = 10, a, r, x1 = 9, r1})

手続き{Sum1 N-1 Rr}の呼び出しを実行
([(proc {$ N R} ... end, {Sum1 -> s, N -> x2, R -> r1}),
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ), x = 10, a, r, x1 = 9, r1, x2 = 8})

比較N==0の実行後
([(local Rr in {Sum1 N-1 Rr} R=N+Rr end, {Sum1 -> s, N -> x2, R -> r1}),
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ), x = 10, a, r, x1 = 9, r1, x2 = 8})

local文の実行
([({Sum1 N-1 Rr} R=N+Rr, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1}),
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ), x = 10, a, r, x1 = 9, r1, x2 = 8, r2})

直列合成
([({Sum1 N-1 Rr}, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1}),
  (R=N+Rr, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1})
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ), x = 10, a, r, x1 = 9, r1, x2 = 8, r2})

手続きの呼び出し、比較、local文の実行、直列合成後
([({Sum1 N-1 Rr}, {Rr -> r3, Sum1 -> s, N -> x3, R -> r2}),
  (R=N+Rr, {Rr -> r3, Sum1 -> s, N -> x3, R -> r2}),
  (R=N+Rr, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1})
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ), x = 10, a, r, x1 = 9, r1, x2 = 8, r2, x3 = 7, r3})

手続きの呼び出し、比較、local文の実行、直列合成後
([({Sum1 N-1 Rr}, {Rr -> r4, Sum1 -> s, N -> x4, R -> r3}),
  (R=N+Rr, {Rr -> r4, Sum1 -> s, N -> x4, R -> r3}), 
  (R=N+Rr, {Rr -> r3, Sum1 -> s, N -> x3, R -> r2}),
  (R=N+Rr, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1})
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ), x = 10, a, r, x1 = 9, r1, x2 = 8, r2, x3 = 7, r3, x4 = 6, r4})

手続きの呼び出し、比較、local文の実行、直列合成後
([({Sum1 N-1 Rr}, {Rr -> r5, Sum1 -> s, N -> x5, R -> r4}),
  (R=N+Rr, {Rr -> r5, Sum1 -> s, N -> x5, R -> r4}), 
  (R=N+Rr, {Rr -> r4, Sum1 -> s, N -> x4, R -> r3}), 
  (R=N+Rr, {Rr -> r3, Sum1 -> s, N -> x3, R -> r2}),
  (R=N+Rr, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1})
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ),
x = 10, a, r, x1 = 9, r1, x2 = 8, r2, x3 = 7, r3, x4 = 6, r4, x5 = 5, r5})

手続きの呼び出し、比較、local文の実行、直列合成後
([({Sum1 N-1 Rr}, {Rr -> r6, Sum1 -> s, N -> x6, R -> r5}),
  (R=N+Rr, {Rr -> r6, Sum1 -> s, N -> x6, R -> r5}), 
  (R=N+Rr, {Rr -> r5, Sum1 -> s, N -> x5, R -> r4}), 
  (R=N+Rr, {Rr -> r4, Sum1 -> s, N -> x4, R -> r3}), 
  (R=N+Rr, {Rr -> r3, Sum1 -> s, N -> x3, R -> r2}),
  (R=N+Rr, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1})
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ),
x = 10, a, r, x1 = 9, r1, x2 = 8, r2, x3 = 7, r3, x4 = 6, r4, x5 = 5, r5,
x6 = 4, r6})

手続きの呼び出し、比較、local文の実行、直列合成後
([({Sum1 N-1 Rr}, {Rr -> r7, Sum1 -> s, N -> x7, R -> r6}),
  (R=N+Rr, {Rr -> r7, Sum1 -> s, N -> x7, R -> r6}), 
  (R=N+Rr, {Rr -> r6, Sum1 -> s, N -> x6, R -> r5}), 
  (R=N+Rr, {Rr -> r5, Sum1 -> s, N -> x5, R -> r4}), 
  (R=N+Rr, {Rr -> r4, Sum1 -> s, N -> x4, R -> r3}), 
  (R=N+Rr, {Rr -> r3, Sum1 -> s, N -> x3, R -> r2}),
  (R=N+Rr, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1})
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ),
x = 10, a, r, x1 = 9, r1, x2 = 8, r2, x3 = 7, r3, x4 = 6, r4, x5 = 5, r5,
x6 = 4, r6, x7 = 3, r7})

手続きの呼び出し、比較、local文の実行、直列合成後
([({Sum1 N-1 Rr}, {Rr -> r8, Sum1 -> s, N -> x8, R -> r7}),
  (R=N+Rr, {Rr -> r8, Sum1 -> s, N -> x8, R -> r7}), 
  (R=N+Rr, {Rr -> r7, Sum1 -> s, N -> x7, R -> r6}), 
  (R=N+Rr, {Rr -> r6, Sum1 -> s, N -> x6, R -> r5}), 
  (R=N+Rr, {Rr -> r5, Sum1 -> s, N -> x5, R -> r4}), 
  (R=N+Rr, {Rr -> r4, Sum1 -> s, N -> x4, R -> r3}), 
  (R=N+Rr, {Rr -> r3, Sum1 -> s, N -> x3, R -> r2}),
  (R=N+Rr, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1})
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ),
x = 10, a, r, x1 = 9, r1, x2 = 8, r2, x3 = 7, r3, x4 = 6, r4, x5 = 5, r5,
x6 = 4, r6, x7 = 3, r7, x8 = 2, r8})

手続きの呼び出し、比較、local文の実行、直列合成後
([({Sum1 N-1 Rr}, {Rr -> r9, Sum1 -> s, N -> x9, R -> r8}),
  (R=N+Rr, {Rr -> r9, Sum1 -> s, N -> x9, R -> r8}), 
  (R=N+Rr, {Rr -> r8, Sum1 -> s, N -> x8, R -> r7}), 
  (R=N+Rr, {Rr -> r7, Sum1 -> s, N -> x7, R -> r6}), 
  (R=N+Rr, {Rr -> r6, Sum1 -> s, N -> x6, R -> r5}), 
  (R=N+Rr, {Rr -> r5, Sum1 -> s, N -> x5, R -> r4}), 
  (R=N+Rr, {Rr -> r4, Sum1 -> s, N -> x4, R -> r3}), 
  (R=N+Rr, {Rr -> r3, Sum1 -> s, N -> x3, R -> r2}),
  (R=N+Rr, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1})
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ),
x = 10, a, r, x1 = 9, r1, x2 = 8, r2, x3 = 7, r3, x4 = 6, r4, x5 = 5, r5,
x6 = 4, r6, x7 = 3, r7, x8 = 2, r8, x9 = 1, r9})

手続きの呼び出しを実行
([(proc {$ N R}
      if N==0 then R=0
      else
         local Rr in
            {Sum1 N-1 Rr}
            R=N+Rr
         end
      end
   end, {Sum1 -> s, N -> x10, R -> r9}),
  (R=N+Rr, {Rr -> r9, Sum1 -> s, N -> x9, R -> r8}), 
  (R=N+Rr, {Rr -> r8, Sum1 -> s, N -> x8, R -> r7}), 
  (R=N+Rr, {Rr -> r7, Sum1 -> s, N -> x7, R -> r6}), 
  (R=N+Rr, {Rr -> r6, Sum1 -> s, N -> x6, R -> r5}), 
  (R=N+Rr, {Rr -> r5, Sum1 -> s, N -> x5, R -> r4}), 
  (R=N+Rr, {Rr -> r4, Sum1 -> s, N -> x4, R -> r3}), 
  (R=N+Rr, {Rr -> r3, Sum1 -> s, N -> x3, R -> r2}),
  (R=N+Rr, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1})
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],   
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ),
x = 10, a, r, x1 = 9, r1, x2 = 8, r2, x3 = 7, r3, x4 = 6, r4, x5 = 5, r5,
x6 = 4, r6, x7 = 3, r7, x8 = 2, r8, x9 = 1, r9, x10 = 0})

比較N==0の実行後
([(R=0, {Sum1 -> s, N -> x10, R -> r9}),
  (R=N+Rr, {Rr -> r9, Sum1 -> s, N -> x9, R -> r8}), 
  (R=N+Rr, {Rr -> r8, Sum1 -> s, N -> x8, R -> r7}), 
  (R=N+Rr, {Rr -> r7, Sum1 -> s, N -> x7, R -> r6}), 
  (R=N+Rr, {Rr -> r6, Sum1 -> s, N -> x6, R -> r5}), 
  (R=N+Rr, {Rr -> r5, Sum1 -> s, N -> x5, R -> r4}), 
  (R=N+Rr, {Rr -> r4, Sum1 -> s, N -> x4, R -> r3}), 
  (R=N+Rr, {Rr -> r3, Sum1 -> s, N -> x3, R -> r2}),
  (R=N+Rr, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1})
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],   
{s = (proc {$ N R}
         if N==0 then R=0
         else
            local Rr in
               {Sum1 N-1 Rr}
               R=N+Rr
            end
         end
      end, Φ),
x = 10, a, r, x1 = 9, r1, x2 = 8, r2, x3 = 7, r3, x4 = 6, r4, x5 = 5, r5,
x6 = 4, r6, x7 = 3, r7, x8 = 2, r8, x9 = 1, r9, x10 = 0})

束縛R=0の実行後
([(R=N+Rr, {Rr -> r9, Sum1 -> s, N -> x9, R -> r8}), 
  (R=N+Rr, {Rr -> r8, Sum1 -> s, N -> x8, R -> r7}), 
  (R=N+Rr, {Rr -> r7, Sum1 -> s, N -> x7, R -> r6}), 
  (R=N+Rr, {Rr -> r6, Sum1 -> s, N -> x6, R -> r5}), 
  (R=N+Rr, {Rr -> r5, Sum1 -> s, N -> x5, R -> r4}), 
  (R=N+Rr, {Rr -> r4, Sum1 -> s, N -> x4, R -> r3}), 
  (R=N+Rr, {Rr -> r3, Sum1 -> s, N -> x3, R -> r2}),
  (R=N+Rr, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1})
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],   
{s = (proc {$ N R}　...  end, Φ),
x = 10, a, r, x1 = 9, r1, x2 = 8, r2, x3 = 7, r3, x4 = 6, r4, x5 = 5, r5,
x6 = 4, r6, x7 = 3, r7, x8 = 2, r8, x9 = 1, r9 = 0, x10 = 0})

意味スタックの最初の要素のポップ、実行を繰り返す
([(R=N+Rr, {Rr -> r8, Sum1 -> s, N -> x8, R -> r7}), 
  (R=N+Rr, {Rr -> r7, Sum1 -> s, N -> x7, R -> r6}), 
  (R=N+Rr, {Rr -> r6, Sum1 -> s, N -> x6, R -> r5}), 
  (R=N+Rr, {Rr -> r5, Sum1 -> s, N -> x5, R -> r4}), 
  (R=N+Rr, {Rr -> r4, Sum1 -> s, N -> x4, R -> r3}), 
  (R=N+Rr, {Rr -> r3, Sum1 -> s, N -> x3, R -> r2}),
  (R=N+Rr, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1})
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],   
{s = (proc {$ N R}　...  end, Φ),
x = 10, a, r, x1 = 9, r1, x2 = 8, r2, x3 = 7, r3, x4 = 6, r4, x5 = 5, r5,
x6 = 4, r6, x7 = 3, r7, x8 = 2, r8 = 1, x9 = 1, r9 = 0, x10 = 0})

([(R=N+Rr, {Rr -> r7, Sum1 -> s, N -> x7, R -> r6}), 
  (R=N+Rr, {Rr -> r6, Sum1 -> s, N -> x6, R -> r5}), 
  (R=N+Rr, {Rr -> r5, Sum1 -> s, N -> x5, R -> r4}), 
  (R=N+Rr, {Rr -> r4, Sum1 -> s, N -> x4, R -> r3}), 
  (R=N+Rr, {Rr -> r3, Sum1 -> s, N -> x3, R -> r2}),
  (R=N+Rr, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1})
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],   
{s = (proc {$ N R}　...  end, Φ),
x = 10, a, r, x1 = 9, r1, x2 = 8, r2, x3 = 7, r3, x4 = 6, r4, x5 = 5, r5,
x6 = 4, r6, x7 = 3, r7 = 3, x8 = 2, r8 = 1, x9 = 1, r9 = 0, x10 = 0})

([(R=N+Rr, {Rr -> r6, Sum1 -> s, N -> x6, R -> r5}), 
  (R=N+Rr, {Rr -> r5, Sum1 -> s, N -> x5, R -> r4}), 
  (R=N+Rr, {Rr -> r4, Sum1 -> s, N -> x4, R -> r3}), 
  (R=N+Rr, {Rr -> r3, Sum1 -> s, N -> x3, R -> r2}),
  (R=N+Rr, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1})
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],   
{s = (proc {$ N R}　...  end, Φ),
x = 10, a, r, x1 = 9, r1, x2 = 8, r2, x3 = 7, r3, x4 = 6, r4, x5 = 5, r5,
x6 = 4, r6 = 6, x7 = 3, r7 = 3, x8 = 2, r8 = 1, x9 = 1, r9 = 0, x10 = 0})

([(R=N+Rr, {Rr -> r5, Sum1 -> s, N -> x5, R -> r4}), 
  (R=N+Rr, {Rr -> r4, Sum1 -> s, N -> x4, R -> r3}), 
  (R=N+Rr, {Rr -> r3, Sum1 -> s, N -> x3, R -> r2}),
  (R=N+Rr, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1})
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],   
{s = (proc {$ N R}　...  end, Φ),
x = 10, a, r, x1 = 9, r1, x2 = 8, r2, x3 = 7, r3, x4 = 6, r4, x5 = 5, r5 = 10,
x6 = 4, r6 = 6, x7 = 3, r7 = 3, x8 = 2, r8 = 1, x9 = 1, r9 = 0, x10 = 0})

([(R=N+Rr, {Rr -> r4, Sum1 -> s, N -> x4, R -> r3}), 
  (R=N+Rr, {Rr -> r3, Sum1 -> s, N -> x3, R -> r2}),
  (R=N+Rr, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1})
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],   
{s = (proc {$ N R}　...  end, Φ),
x = 10, a, r, x1 = 9, r1, x2 = 8, r2, x3 = 7, r3, x4 = 6, r4 = 15, x5 = 5,
r5 = 10, x6 = 4, r6 = 6, x7 = 3, r7 = 3, x8 = 2, r8 = 1, x9 = 1, r9 = 0,
x10 = 0})

([(R=N+Rr, {Rr -> r3, Sum1 -> s, N -> x3, R -> r2}),
  (R=N+Rr, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1})
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],   
{s = (proc {$ N R}　...  end, Φ),
x = 10, a, r, x1 = 9, r1, x2 = 8, r2, x3 = 7, r3 = 21, x4 = 6, r4 = 15, x5 = 5,
r5 = 10, x6 = 4, r6 = 6, x7 = 3, r7 = 3, x8 = 2, r8 = 1, x9 = 1, r9 = 0,
x10 = 0})

([(R=N+Rr, {Rr -> r2, Sum1 -> s, N -> x2, R -> r1})
  (R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],   
{s = (proc {$ N R}　...  end, Φ),
x = 10, a, r, x1 = 9, r1, x2 = 8, r2 = 28, x3 = 7, r3 = 21, x4 = 6, r4 = 15,
x5 = 5,r5 = 10, x6 = 4, r6 = 6, x7 = 3, r7 = 3, x8 = 2, r8 = 1, x9 = 1, r9 = 0,
x10 = 0})

([(R=N+Rr, {Rr -> r1, Sum1 -> s, N -> x1, R -> r}),
  (R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],   
{s = (proc {$ N R}　...  end, Φ),
x = 10, a, r, x1 = 9, r1 = 36, x2 = 8, r2 = 28, x3 = 7, r3 = 21, x4 = 6,
r4 = 15, x5 = 5,r5 = 10, x6 = 4, r6 = 6, x7 = 3, r7 = 3, x8 = 2, r8 = 1,
x9 = 1, r9 = 0, x10 = 0})

([(R=N+Rr, {Rr -> r, Sum1 -> s, N -> x, R -> a})],   
{s = (proc {$ N R}　...  end, Φ),
x = 10, a, r = 45, x1 = 9, r1 = 36, x2 = 8, r2 = 28, x3 = 7, r3 = 21, x4 = 6,
r4 = 15, x5 = 5,r5 = 10, x6 = 4, r6 = 6, x7 = 3, r7 = 3, x8 = 2, r8 = 1, x9 = 1,
r9 = 0, x10 = 0})

([],
{s = (proc {$ N R}　...  end, Φ),
x = 10, a = 55, r = 45, x1 = 9, r1 = 36, x2 = 8, r2 = 28, x3 = 7, r3 = 21,
x4 = 6, r4 = 15, x5 = 5,r5 = 10, x6 = 4, r6 = 6, x7 = 3, r7 = 3, x8 = 2, r8 = 1,
x9 = 1, r9 = 0, x10 = 0})

スタックの大きさの最大値は11

{Sum2 10 0}を手で実行。

([(
local Sum2 X Y A in
   Sum2= proc {$ N S ?R}
            if N==0 then R=S
            else
               {Sum2 N-1 N+S R}
            end
         end
   X=10
   Y=0
   {Sum2 X Y A}
end,
Φ)],
Φ)

([(
Sum2=proc {$ N S R}
        if N==0 then R=S
        else
           {Sum2 N-1 N+S R}
        end
     end
{Sum2 X Y A},
{Sum2 -> s, X -> x, Y -> y, A -> a})],
{s, x = 10, y = 0, a})

直列合成
([(Sum2= proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end end,
     {Sum2 -> s, X -> x, Y -> y, A -> a}),
  ({Sum2 X Y A}, {Sum2 -> s, X -> x, Y -> y, A -> a})],
 {s, x = 10, y = 0, a})

束縛Sum2= proc ...の実行
([({Sum2 X Y A}, {Sum2 -> s, X -> x, Y -> y, A -> a})],
 {s = (proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end, Φ),
  x = 10, y = 0, a})

手続き{Sum2 X Y A}の呼び出しを実行
([(proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end,
  {Sum2 -> s, N -> x, S -> y, R -> a})],
 {s = (proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end, Φ),
  x = 10, y = 0, a})

比較N==0の実行後
([({Sum2 N-1 N+S R}, {Sum2 -> s, N -> x, S -> y, R -> a})],
 {s = (proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end, Φ),
  x = 10, y = 0, a})

手続き{Sum2 N-1 N+S R}の呼び出しを実行
([(proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end,
  {Sum2 -> s, N -> x1, S -> y1, R -> a})],
 {s = (proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end, Φ),
  x1 = 9, y1 = 10, x = 10, y = 0, a})

比較N==0の実行後、手続き呼び出しを実行
([(proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end,
  {Sum2 -> s, N -> x2, S -> y2, R -> a})],
 {s = (proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end, Φ),
  x2 = 8, y2 = 19, x1 = 9, y1 = 10, x = 10, y = 0, a})

比較N==0の実行後、手続き呼び出しを実行
([(proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end,
  {Sum2 -> s, N -> x3, S -> y3, R -> a})],
 {s = (proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end, Φ),
  x3 = 7, y3 = 27, x2 = 8, y2 = 19, x1 = 9, y1 = 10, x = 10, y = 0, a})

比較N==0の実行後、手続き呼び出しを実行
([(proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end,
  {Sum2 -> s, N -> x4, S -> y4, R -> a})],
 {s = (proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end, Φ),
  x4 = 6, y4 = 34, x3 = 7, y3 = 27, x2 = 8, y2 = 19, x1 = 9, y1 = 10, x = 10,
  y = 0, a})

比較N==0の実行後、手続き呼び出しを実行
([(proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end,
  {Sum2 -> s, N -> x5, S -> y5, R -> a})],
 {s = (proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end, Φ),
  x5 = 5, y5 = 40, x4 = 6, y4 = 34, x3 = 7, y3 = 27, x2 = 8, y2 = 19, x1 = 9,
  y1 = 10, x = 10, y = 0, a})

比較N==0の実行後、手続き呼び出しを実行
([(proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end,
  {Sum2 -> s, N -> x6, S -> y6, R -> a})],
 {s = (proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end, Φ),
  x6 = 4, y6 = 45, x5 = 5, y5 = 40, x4 = 6, y4 = 34, x3 = 7, y3 = 27, x2 = 8,
  y2 = 19, x1 = 9, y1 = 10, x = 10, y = 0, a})

比較N==0の実行後、手続き呼び出しを実行
([(proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end,
  {Sum2 -> s, N -> x7, S -> y7, R -> a})],
 {s = (proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end, Φ),
  x7 = 3, y7 = 49, x6 = 4, y6 = 45, x5 = 5, y5 = 40, x4 = 6, y4 = 34, x3 = 7,
  y3 = 27, x2 = 8, y2 = 19, x1 = 9, y1 = 10, x = 10, y = 0, a})

比較N==0の実行後、手続き呼び出しを実行
([(proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end,
  {Sum2 -> s, N -> x8, S -> y8, R -> a})],
 {s = (proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end, Φ),
  x8 = 2, y8 = 52, x7 = 3, y7 = 49, x6 = 4, y6 = 45, x5 = 5, y5 = 40, x4 = 6,
  y4 = 34, x3 = 7, y3 = 27, x2 = 8, y2 = 19, x1 = 9, y1 = 10, x = 10, y = 0, a})

比較N==0の実行後、手続き呼び出しを実行
([(proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end,
  {Sum2 -> s, N -> x9, S -> y9, R -> a})],
 {s = (proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end, Φ),
  x9 = 1, y9 = 54, x8 = 2, y8 = 52, x7 = 3, y7 = 49, x6 = 4, y6 = 45, x5 = 5,
  y5 = 40, x4 = 6, y4 = 34, x3 = 7, y3 = 27, x2 = 8, y2 = 19, x1 = 9, y1 = 10,
  x = 10, y = 0, a})

比較N==0の実行後、手続き呼び出しを実行
([(proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end,
  {Sum2 -> s, N -> x10, S -> y10, R -> a})],
 {s = (proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end, Φ),
  x10 = 0, y10 = 55, x9 = 1, y9 = 54, x8 = 2, y8 = 52, x7 = 3, y7 = 49, x6 = 4,
  y6 = 45, x5 = 5, y5 = 40, x4 = 6, y4 = 34, x3 = 7, y3 = 27, x2 = 8, y2 = 19,
  x1 = 9, y1 = 10, x = 10, y = 0, a})

比較N==0の実行後
([(R=S, {Sum2 -> s, N -> x10, S -> y10, R -> a})],
 {s = (proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end, Φ),
  x10 = 0, y10 = 55, x9 = 1, y9 = 54, x8 = 2, y8 = 52, x7 = 3, y7 = 49, x6 = 4,
  y6 = 45, x5 = 5, y5 = 40, x4 = 6, y4 = 34, x3 = 7, y3 = 27, x2 = 8, y2 = 19,
  x1 = 9, y1 = 10, x = 10, y = 0, a})

束縛R=Sの実行
([],
 {s = (proc {$ N S R} if N==0 then R=S else {Sum2 N-1 N+S R} end, Φ),
  x10 = 0, y10 = 55, x9 = 1, y9 = 54, x8 = 2, y8 = 52, x7 = 3, y7 = 49, x6 = 4,
  y6 = 45, x5 = 5, y5 = 40, x4 = 6, y4 = 34, x3 = 7, y3 = 27, x2 = 8, y2 = 19,
  x1 = 9, y1 = 10, x = 10, y = 0, a=y10})

スタックの大きさの最大値は2