状態は引数と戻り値の狭間に埋まってしまうのかも知れない

チューリングマシンには状態がある。ラムダ計算はチューリングマシンと等価な数理モデルだが、状態がない。これは一体どう考えればいいんだろう？というのが前回までのお話。

以下の考え方や用語の使い方は間違っているかも知れない。そもそもまったくオハナシにならないレベルの可能性がある。何かアドバイスがあったらご指摘ください。

セミナー非参加者にもわかるリアルワールド向けラムダ計算 - 檜山正幸のキマイラ飼育記さんのページには、次のように書いてある（と思う）。

汎用コンピュータは1つの関数で表現できる
「マシンmで、コードcをデータdに対して実行したら、結果がrだった」というのをm(c,d)=rと表す

これを読んで、頭の中でパキーンという音がした。何かがわかった気がする。その何かを、できないながら説明してみると、次のようになる。

チューリングマシンは、無限に長いテープからデーターを入力し、処理して、同じテープ上に結果を出力する。処理するときに内部状態が変化する。

ラムダ計算の関数は、データーを一気に読み込み、処理して、結果を一気に吐き出す。内部状態は変化しない。

チューリングマシンでは、逐次的にデーターを読み込みながら状態を変化させるのに対し、ラムダ計算の関数では、一気にデーターを読み込む。状態はどこへ行っちゃったかというと、たぶん処理の狭間に詰め込まれてしまって見えなくなっている。

以下は上記のことと関係あるかも知れないし、まったく関係ないかも知れない。

整数のリスト（あるいは配列）を与えられたときに、そのリストの要素をすべて足した値を返す関数を考えてみよう。

VBでは次のように書ける。

Function SumOfArray(anArray() As Long) As Long
    Dim i As Integer
    Dim Sum As Long

    Sum = 0
    For i = LBound(anArray) To UBound(anArray)
        Sum = Sum + anArray(i)
    Next

    SumOfArray = Sum
End Function

一方、Schemeでは次のように書ける。

(define (sum-of-list l)
  (if (null? l) 0
      (+ (car l) (sum-of-list (cdr l)))))

VBのプログラムでは、変数iとSumが使われていて、両方ともForループの中で値（状態）が変化している。

Schemeのプログラムでは、引数としてリストlのcdrを渡しながら再帰することで、VBでiにあたるループカウンタが不要になっている。また、値を返しながらリターンすることで、VBでSumにあたる合計を記憶する変数が不要になっている。

両方とも同様の計算をするのに、VBで必要だった「状態」は、Schemeでは引数と戻り値の引き渡し処理の狭間に埋まってしまっている。

チューリングマシンに状態があり、ラムダ計算に状態がなくて、それでいて等価だというのは、これと似たような状況なのだろうか？我ながらすごくいいかげんなことを言っている気がする。