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(練習問題)、11.(相互再帰(mutual recursion))を解いてみる。

11.(相互再帰(mutual recursion))

% 関数を翻訳
IsEven= proc {$ X R}
          if X==0 then R=true
          else
             {IsOdd X-1 R}
          end
       end
IsEven= proc {$ X R}
           if X==0 then R=false
           else
              {IsEven X-1 R}
           end
        end


([({IsOdd N R}, {IsOdd -> io, IsEven -> ie, N -> n, R -> r})],
 {ie = (proc {$ X R} if X==0 then R=true else {IsOdd X-1 R} end end, Φ),
 io = (proc {$ X R} if X==0 then R=false else {IsEven X-1 R} end end, Φ),
 n = 10, r})

([(if X==0 then R=false else {IsEven X-1 R} end end,
   {IsOdd -> io, IsEven -> ie, X -> n, R -> r})],
 {ie = (proc {$ X R} if X==0 then R=true else {IsOdd X-1 R} end end, Φ),
 io = (proc {$ X R} if X==0 then R=false else {IsEven X-1 R} end end, Φ),
 n = 10, r})

([({IsEven X-1 R}, {IsOdd -> io, IsEven -> ie, X -> n, R -> r})],
 {ie = (proc {$ X R} if X==0 then R=true else {IsOdd X-1 R} end end, Φ),
  io = (proc {$ X R} if X==0 then R=false else {IsEven X-1 R} end end, Φ),
  n = 10, r})

([({IsEven N R}, {IsOdd -> io, IsEven -> ie, N -> x, R -> r})],
 {ie = (proc {$ X R} if X==0 then R=true else {IsOdd X-1 R} end end, Φ),
  io = (proc {$ X R} if X==0 then R=false else {IsEven X-1 R} end end, Φ),
  n = 10, x = 9, r})

([(if X==0 then R=true else {IsOdd X-1 R} end end,
  {IsOdd -> io, IsEven -> ie, X -> x, R -> r})],
 {ie = (proc {$ X R} if X==0 then R=true else {IsOdd X-1 R} end end, Φ),
  io = (proc {$ X R} if X==0 then R=false else {IsEven X-1 R} end end, Φ),
  n = 10, x = 9, r})

([({IsOdd X-1 R}, {IsOdd -> io, IsEven -> ie, X -> x, R -> r})],
 {ie = (proc {$ X R} if X==0 then R=true else {IsOdd X-1 R} end end, Φ),
  io = (proc {$ X R} if X==0 then R=false else {IsEven X-1 R} end end, Φ),
  n = 10, x = 9, r})

([({IsOdd N R}, {IsOdd -> io, IsEven -> ie, N -> x1, R -> r})],
 {ie = (proc {$ X R} if X==0 then R=true else {IsOdd X-1 R} end end, Φ),
  io = (proc {$ X R} if X==0 then R=false else {IsEven X-1 R} end end, Φ),
  n = 10, x = 9, x1 = 8, r})

% よって、呼び出し{IsOdd 10}は一定のスタックの大きさ(1)で実行する。
% このことはすべての被負整数について成り立つ。
% 同様に、呼び出し{IsEven N}もすべての被負整数Nについて一定のスタックの大きさで実行する。