%tc04.tex
\chapter{リストと再帰的定義}
\section{リストとは何か}%1
Logo の特色として、「型宣言が不要」を前の章であげました。コンピュータでの変数は、メモリーに名前をつけてデータを保存し、その名によって後で利用できるようにするものです。メモリーの正体は 0,1 を電圧で表現する半導体素子に他なりません。そのデータが整数型か倍精度型か文字列かなどによって使うメモリーのサイズが違う。そのため普通はプログラムの冒頭に宣言をする必要があります。Pascal はその最右翼で、使う変数名をことごとく宣言する必要があります。入ってくるお客の人数によって部屋をシングルとして使うかツインとして使うかホテルのフロントが決めますが、同じような作業をメモリーに関して扱うデータのサイズによってしておく必要があるのです。Logo とはその両極端の関係にあります。ベクトルや行列も、普通の言語では「配列」として宣言されますが、Logo ではリストという柔軟なデータ構造を持っているのでその必要はないのです。
では、リストとは何でしょうか。その前に、ワードという言葉を説明しましょう。
文字列でも、数値でもデータのことを「ワード」と言います。また、関数の名前やデータの名前もワードです。リストとは、ワードやリストを並べたものです。
%Backus Naur Form で記述すると、
さも簡単に書いてしまいましたが、並べる個数は何でもよいのですし、リストの中にあるリストがまたリストを含んでるといった何重にも入れ子になったものでも良いのです。
このリストもデータとして扱うことができます。
データを変数へ代入するには、\\
\begin{verbatim}
make （変数の名前であるワード）
（変数に入れるデータ）
\end{verbatim}
によります。これを実行すると該当する変数を探し、もしないなら新しくその名の変数を作り、データをその変数へ入れます。
\begin{itembox}{変数の例}
\begin{tabular}{ll}
\verb+make "Speed 76.8 / ( 83 / 60
)+&
\begin{minipage}[t]{12zw}
これはある私鉄特急の表定速度です。\end{minipage}\\
\verb+make "Aisatu "おはようございます+&
\begin{minipage}[t]{12zw}
文字列も記憶させることができます。\end{minipage}\\
\verb+make "Puffy [Ami Yumi]+&
\begin{minipage}[t]{12zw}
２つのワードの組。［］の中なので "を前に記しません。
\end{minipage}\\
\verb+make "Max [Rina Miina Reina Nana]+& ４人組でも大丈夫です。\\
\verb!make "i :i + 1!&
\begin{minipage}[t]{12zw}
変数 i に入っている数値のデータを 1 増やします。\end{minipage}
\end{tabular}
\end{itembox}
ここで、{\tt make } の第１引数が \verb+:+ を前に置かず、\verb+"+ を前に置いていることに注意して下さい。ちょっと Pascal や C , Basic などの普通の代入文を見慣れた目には居心地が悪い書き方ですが、代入するべき箇所をあらかじめの計算できめるといった使い方もできます。あとで若干、例を出します。
\section{文字列処理}%2
Basic の特徴のひとつに強力な文字列処理機能があります。例えば、
\begin{center}
\begin{verbatim}
電話番号 = 市外局番 + "-" + 市内局番 + "-" + 加入者番号
\end{verbatim}
\end{center}
などという芸当ができます。このように文字列に文字列をつなげることを単に足し算記号 \verb:+: であらわすことができたりするのです。しかし、データの型の宣言をしない Logo ではこれに足し算記号を使うと、数学の加法をあらわすのか文字列の連結かわからなくなります。そこで、２つのワードをつなげて１つのワードにする \verb+word+ という関数があります。上に記したデータの例を用いて類似の他の関数についての例をあげておきましょう。
\begin{center}
\begin{tabular}{r|l}
文例&出力\\ \hline
\verb+word "boy "friend+ &
\verb+boyfriend+ \\
\verb+( word "multi "task
"ing )+& \verb+multitasking+\\
\
&
\begin{minipage}{15zw}
{\small ３つ以上のものをつなげるにはこのように括弧でくくります。}
\end{minipage}
\\
\verb+list "Tsuyoshi "Kohichi+
& \verb+[Tsuyoshi Kohichi]+\\
\verb+list :Max :Puffy+ &
\begin{minipage}{14zw}
\verb+[[Rina Miina Reina Nana]+\\
\verb+
[Ami Yumi]]+
\end{minipage}\\
\verb+sentence :Max :Puffy+ &
\verb+[Rina Miina Reina Nana Ami Yumi]+\\
\verb+fput "Namie :Max+ &
\verb+[Namie Rina Miina Reina Nana]+\\
\
&
{\small ワードをリストの初めに入れます。}\\
\verb+lput "Namie :Max+ &
\verb+[Rina Miina Reina Nana Namie]+\\
\verb+( list :KinkiKids :Tokio :V6)+ & 出力は \verb+:J_Friends ?+\\
\
&
\begin{minipage}{15zw}
{\small ここでも３つ以上のものを処理しています。}
\end{minipage}\\
\hline
\end{tabular}
\end{center}
ただの括弧があるかないかじゃないかと思われるかもしれませんが、この括弧があらわすデータの構造が問題なのです。\verb+list :Max :Puffy+ とは、きょうの番組の出演はこの2組だなという程度の意味ですが、\verb+sentence
:Max :Puffy +とは6人組なのです。\\
{\bf （問２−１）}初めの９個の奇数を
\verb+:A1,:A2,:A3,.....,:A9 +%4/10 18:14
にそれぞれ値として入れる命令を {\tt
repeat} を使ってかいてみてください。%\vspace{1zh}
その他の関数について機能を記しておきます。
\begin{center}
\begin{tabular}{ll}
\verb+first+ & リストまたはワードの初めの要素（あるいは文字）。\\
\verb+last+ & 同じく最後の要素あるいは文字。\\
\verb+butfirst+& first 以外の要素あるいは文字列。\\
\verb+butlast+ & last 以外の要素あるいは文字列。\\
\verb+list?+ & そのデータがリストかどうかの真偽。\\
\verb+word?+ & そのデータがワードかどうかの真偽。\\
\verb+empty?+ & そのデータが空かどうかの真偽。\\
\end{tabular}
\end{center}
この関数を使って他の関数を説明しましょう。\verb+count
:L +は、データ\verb+ :L +が文字列のときはその字数を、リストのときは要素の数を出力します。
これと同じ機能を持つ \verb+Count_
:L +を下記のように作ることができます。
\begin{itembox}{count を同等の機能を持つ関数}
\begin{verbatim}
to Count_ :L
if empty? :L [ output 0 ]
output ( Count_ butfirst :L ) + 1
end
\end{verbatim}
\end{itembox}
この例では、自分の定義に自分自身を使っています。にわとりが先かたまごが先かで示したように、そのファイル（ページ）に定義されているか、プリミティブであるかする関数で定義すればよいのです。自分自身もそのファイルにあるのですから定義に使えるというわけです。このような定義が許されているのでリストという柔軟な構造を扱うことができます。節を改めて再帰的定義の練習をしてみましょう。
\section{再帰的定義の練習}%3
まずは、例題からいきましょう。初項が 2 公差が 3 の等差数列、
$$ 2,5,8,11,14,17,20,\cdots$$
の第$n$番目の項を出力する関数{\verb+ Tousa :n+}は次のように作れます。
\begin{itembox}{等差数列の例}
{%\small
\begin{verbatim}
to Tousa :n
if :n <= 0
[ print (list "Tousaへの入力 :n "が不正です。)
stop
]
if :n = 1 [ output 2 ]
output 3 + Tousa ( :n - 1 )
end
\end{verbatim}
} %---- end of \small
\end{itembox}
これは、{\tt Tousa 2.7 }などと引数が自然数ではないものが入ったときの対策として
\verb+if :n <= 0 + で始まる命令が入っています。\verb+<= +とは、≦ のこと。{\tt
stop } とは、ここでこの関数に関する処理をやめてこの関数を呼び出したところに戻ることを意味します。{\tt output} があると以降の処理をしないで出力を出しますが、これは出力を出さない処理の中断です。
\begin{enumerate}
\item 初項が 3、公比が 2 の等比数列 $3,6,12,24,48,\cdots$\\ の第$n$番目の項を出力する \verb+Touhi :n +を作れ。
%1
\item $n$番目のフィボナッチ数、$1,1,2,3,5,8,13,21,\cdots$\\ を出力する \verb+Fib :n +を作れ。
%2
\item リスト\verb+:L +に含まれている数の最大値を出力する \verb+Max :L +を作れ。
%3
\item リスト\verb+:L +に含まれている数の合計を出力する
\verb+Sum_ :L +を作れ。
%4
\item \verb+item :n :d +は、データ\verb+ :d +の $n$番目の要素（あるいは文字）を出力します。それと同等な機能を持つ\verb+ Item_ :n :d +を作れ。
%5
\item \verb+sentence :m :n +と同等な機能を持つ\verb+ Sentence_ :m :n +を
作れ。
%6
\item \verb+member? :m :n +は、\verb+:m が :n+ に含まれることの真偽を出力します。それと同等な機能を持つ\verb+ Member?_ :m :n +を作れ。%6.5
\item Basic では、文字列\verb+word+の左側の$n$文字列を出す関数 \verb+left$(word,n)+ があります。それと同等な機能を持つ \verb+Left$ :word :n + を作れ。また、同様に \verb+Right$ :word :n+ を作れ。
%7
\item Basic で、\verb+mid$(l,m,n) +は、文字列\verb+l+の左から$m$番目からあとの$n$文字を出力する関数です。これをまねる\verb+Mid$ :L :M :N+を作れ。
%8
\item Basic では、数をあらわすワード\verb+ :n +にその前へ空白を入れることによって指定された桁数\verb+ :k +の文字列にする\verb+
string$(n,k) +があります。
これをまねる\verb+ String$ :n
:k +を作れ。なお、空白を含む文字列は引用符の次に縦線で括ってあらわします。つまり空白は \verb+"| | +とあらわせます\footnote{他にも ASCII コードから文字を出力する関数を利用して\verb+char 32+などとあらわせます。}。
%8.5
\item 例えば、$(6,3,4)$を、\verb+[ 6 3 4
]+ のように、リストとしてあらわされた2つのベクトル\verb+:m :n +の和を出力する\verb+V_Sum :m :n +を作れ。
%9
\item 2つのベクトルの内積を出力する\verb+Inner_Prod :m :n +は？
%10
\item 初めの$n$個のフィボナッチ数を（小さい方から大きさの順に）並べたリストを出力する関数 \verb+FibL :n +を作れ。
%11
\item 初めの$n$個の素数$
2,3,5,7,11,13,\cdots $ を並べたリストを出力する関数\verb+PrimeL
+を作れ。
%12
\item 自然数\verb+:n +の素因数分解（例えば、$24=2\times2\times2\times3$）を出力する関数\verb+ Factri :n +を作れ。
%13
\item \verb+[[The teacher] said [that
[[that that] [that [that boy] used]]
was wrong].]+ などとやたらと入れ子が深いリストでも、括弧をとった
\begin{center}
\verb+[ The teacher said that that that
that that .....]+
\end{center}
を出力できる\verb+P_Sentence_+
を作れ。
%14
\end{enumerate}
手続き型言語の経験があると具体的な手続きを頭に思い浮べる癖ができていますが、なるべく再帰的定義を使おうとしてみて下さい。この程度の問題数でもかなりのトレーニングになるはずです。
\section{再帰的定義に関する注意}%4
\subsection{ユークリッドの互除法}
最大公約数を求める算法として古代ギリシャから知られ、アルゴリズムの語源ともなったものです。これは、２つの数 $a,b $ の最大公約数 $g$ は、$a$ を $b$ で割ったあまりを $r$ とすると、$b,r $ の最大公約数に一致することを利用するものです。
えっ、なぜかって？$a = bq + r $ですから、$b と r $の最大公約数を$ d $とすると、$d $は、$a $の約数、つまり、$a,b $の公約数でもあります。$a,b $の最大公約数を$ e $とすると、「最大」の定義から、$d≦e$。同様に、$r = a - bq $から、$e≦d $を示すことができます。プログラムの形にすると次のようになります。
%\newpage%1998.4.10.19:14
\begin{itembox}{ユークリッドの互除法(その１)}
\begin{verbatim}
to GCM :a :b
make "a abs :a
make "b abs :b
if :b = 0 [ output :a ]
if remainder :a :b = 0 [ output :b ]
output ( GCM :b ( remainder :a :b ) )
end
\end{verbatim}
\end{itembox}
%\newpage%1998.4.10.19:16
例えば、448 と 168 の最大公約数がどのように求められるか手順を追ってみましょう。
まず、\verb+GCM 448 168 +が呼ばれると、これの定義を探します。そして、\verb+ if +による場合分けによって、\verb+output ( GCM :b ( remainder
:a :b ) ) +に行き着きます。この場合、\verb+:b,(
remainder :a :b ) +はそれぞれ、168, 112 になりますから、\verb+GCM 448 168 +は、\verb+GCM 168 112 +に置き換ります。つまり、これを呼んだことと同じと言うわけです。以下次々に置き換えを実行して、
\begin{center}
\verb+ GCM 448 168 → GCM 168 112 → GCM 112 56 +
\end{center}
となるのですが、112 は 56 で割り切れるので、２番目の
\verb+ if +によって
\verb+:b +に置き換り 56 が出力されるのです。
このような状態を分かりやすくするために、途中を報告させましょう。
\begin{itembox}{ユークリッドの互除法(その２)}
\begin{verbatim}
to GCM :a :b
print ( list "いま :a :b "の最大公約数を考えています。)
if :b = 0 [ output :a ]
if remainder :a :b = 0 [ output :b ]
output ( GCM :b ( remainder :a :b ) )
end
\end{verbatim}
\end{itembox}
これを裏のページにかいてから、\verb+print
GCM 448 168 +をコマンドセンターから命じてみましょう。さて、これをみると\verb+ remainder +が２ヵ所に出ていますね。それほど計算時間を要しない関数ですが、２回まったく同じ計算をするのは効率が悪いですね。そこで、変数 :r に覚えさせて利用しましょう。ついでに、２つの数の最大公約数と大きな方を小さな方で割った余りとは違うことをはっきりさせるために次のようなプログラムを作ってみました。
\begin{itembox}{ユークリッドの互除法(その３)}
\begin{verbatim}
to GCM :a :b
if :b = 0 [ output :a ]
make "r
remainder :a :b
output ( GCM :b :r )
end
to CallingGCM :x :y
make "r remainder :x :y
print ( list :x "を :y "で割ったあまりは :r "ですが )
print ( list "最大公約数は GCM :x :y "です。)
print ( list "ほら、あまりの :r "とは違うでしょ？ )
end
\end{verbatim}
\end{itembox}
\vfil
\newpage%1998.4.10. 19:12
実は、これを実行するとおかしな結果になります。なぜおかしくなるかを調べるには、
\verb+to GCM :a :b +の次の行として、
\begin{center}
\verb+ print (sentence [ :a=] :a [ , :b=]
:b [ , :r=] :r ) +
\end{center}
を挿入してみてください。そうです、GCM のなかにも変数 :r があって、計算中に書き換えられています。だから、実行の前と後では値が違うのです。うっかり関数の定義に変数を使うとこのような副作用があるとなると恐ろしいですね。そこで、「名前が重複する時は、新たに別のメモリーを確保して、処理が終わったら消す変数」である、ローカル変数を指定することができます。変数の隠蔽と言ってプログラムのモジュール化には重要な概念です。その変数名の前に\verb+ local +とかきます。ローカルにする変数が複数あるときは次の例のようにリストにして宣言します\footnote{Pc Logoでは、\verb+ (
local "x "y "r ) +のようにします。}。なお、引数は何も言わなくともローカルです。\vfil
\noindent
{\bf （問４−１）}関数が引数を何個取るかは定義をみればわかります。次のその４が裏のページにかいてあるとして、\verb+GCM GCM 12 16 18 +を命ずるとどのようなことが起こりますか？\vfil \noindent
{\bf （問４−２）}その４では、
\verb+:a :b ;（CallingGCMの中での）:x,:y,:r;+
\verb+（GCMの中での）:x,:y,:r +
という変数があらわれます。これらの値がどのように変っていくか表にまとめましょう。
\vfil
\begin{center}$
\begin{array}{|rr|rrr|rrr|}\hline
\ &\ &
\multicolumn{3}{|c|}{\small \rm
CallingGCM}&
\multicolumn{3}{|c|}{\small \rm GCM}\\
\cline{3-8}
\verb+ :a +&\verb+ :b +&\verb+ :x
+&\verb+ :y +&\verb+ :r +&
\verb+ :x +&\verb+ :y +&\verb+ :r +\\
\hline
\ &\
& -54&
8&\ &\ &\ &\ \\
\ &\
& -54&
8& -6&\ &\ &\ \\
-54&
8& -54&
8& -6&\ &\ &\ \\
-54&
8& -54&
8& -6& 54& 8&\ \\
-54&
8& -54&
8& -6& 54& 8& 6
\end{array}$
\end{center}
\newpage
\begin{itembox}{ユークリッドの互除法(その４)}
\begin{verbatim}
to GCM :a :b
local [x y r]
make "x abs :a
make "y abs :b
if :y = 0 [ output :x ]
make "r
remainder :x :y
output ( GCM :y :r )
end
to CallingGCM
make "x -54
make "y 8
make "r remainder :x :y
print ( list :x "を :y "で割ったあまりは :r "です。 )
print ( list "最大公約数は GCM :x :y "です。)
print ( list :x "を :y "で割ったあまりは :r "です。 )
end
\end{verbatim}
\end{itembox}
\subsection{フィボナッチ数列を求める速さ}
既に練習問題としてフィボナッチ数を計算する関数を考えてもらっていますが、\vspace*{0.01zh}
\\その解答を兼ねて次のようなプログラム例を考えてみましょう。
\vspace{1.5zh}\\{\bf フィボナッチ数を書き並べる}\vspace{0.21zh}
{%\small
\begin{verbatim}
to MainFib
make "i 1
repeat 15
[ insert String$ :i 5
make "i :i + 1
]
print "
make "i 1
repeat 15
[ insert String$ Fib1 :i 5
make "i :i + 1
]
print "
make "i 1
repeat 15
[ insert String$ Fib2 :i 5
make "i :i + 1
]
print "
make "i 1
InitFib3
repeat 15
[ insert String$ Fib3 :i 5
make "i :i + 1
]
print "
make "i 1
end
to String$ :n :k
if ( count :n ) >= :k [ output :n ]
output String$ ( word "| | :n ) :k
end
to Fib1 :n
if :n < 3 [ output 1 ]
output (Fib1 ( :n - 1 )) + (Fib1 ( :n - 2 ))
end
to Fib2 :n
if :n < 3 [ output 1 ]
output Fib2Job 1 1 3 :n
end
to Fib2Job
:Mae :SonoMae :i :n
if :i = :n [ output :Mae + :SonoMae ]
output Fib2Job (:Mae + :SonoMae) :Mae (:i
+ 1) :n
end
to InitFib3
local [i a b]
make "F1 1
make "F2 1
make "i 3
repeat 13
[ make "a thing ( word "F ( :i - 1 ))
make "b thing ( word "F ( :i - 2 ))
make ( word "F :i ) :a + :b
make "i :i + 1
]
end
to Fib3 :n
output thing ( word "F :n )
end
\end{verbatim}
}%-------end of \small
%\vspace{1zh}\\
新しい単語は\verb+ thing +ですね。これはワードを引数にとりこの名前をもつ変数の値を出力します。つまり、\verb+thing
"Moji とは、:Moji +と同じです。ついでに申せば、リストを引数に取りそのリストの内容を実行するのが、\verb+run+。なお、
\verb+time+はコンピュータの内部時計の様子を出力する関数ですがこの場合、文字の現れる様子を観察する方が違いがわかります。。
\section{リストの応用例}%5
\subsection{数学での応用}
既に、練習のなかでリストとしてあらわされたベクトルについて触れましたが、リストを他のいろいろな構造へ応用することができます。もっともあらわすだけで、計算操作などは定義してやらないとなりません。CPUの演算機能を呼び出せばよさそうなもの以外は関数として定義するのです。$2 + 3 $の加法を表す演算記号\verb!
+ !は引数を２つとる「足す」という関数（２項演算）をあらわす中置演算子とみることができますが、Logoで新たに定義する関数は、関数一般の例にならってことごとく前置演算子となります。ときには、式をみやすくリストで書いておいてそれをLogoに解釈させたり、計算の結果を画面に見やすく表示するなどの工夫をしてみましょう。
\subsubsection{有理数}
リスト\verb+[m / n]+で分数 $ \dfrac{m}{n} $ をあらわすことにします。有理数\verb+:x+の分子を出力する\verb+ Bunsi :x +を次のように定義することができます。
\vspace{1zh}
\begin{verbatim}
to Bunsi :x
if word? :x [ output :x ]
output first :x
end
\end{verbatim}
%\vspace*{1zh}\\
{\bf （問５−１）}では分母を出力する\verb+ Bunbo :x
+は？\vspace{1zh}\\
これらを利用して分数を既約にする
\verb+Stn :x +を作ることができます。
\vspace{1zh}
\begin{verbatim}
to Stn :x
if word? :x [ output :x ]
if "/ = (item 2 :x)
[ output Yakubun (Bunsi :x) (Bunbo
:x)]
print (list "この分数はおかしいです。(by Stn) :x )
end
to Yakubun :a :b
local "G
make "G
( Gcm :a :b )
if :b < 0
[ make "a minus :a
make "b minus
:b
]
if :b = :G [ output :a / :G ]
output ( list (:a/:G) "/ (:b/:G) )
end
\end{verbatim}
%\vspace*{1zh}\\
このように有理数の分母と分子をわけて実際の計算をする\verb+ Yakubun+を \verb+ Stn +が呼ぶようにすると変数の受け渡しがスムーズです。
\vspace{1zh}\\
{\bf （問５−２）}２つの有理数 :x と :y の和を出力する \verb+ Plus :x :y +と、積を出力する \verb+ Times :x :y +を作ってください。もちろん結果は約分することにします。\\
{\bf （問５−３）}では、減法、除法はどうでしょう。（逆数を出力する\verb+
Inv+を作れば、\verb+Times +が利用できますね。\\
{\bf （問５−４）}\verb![[1/2]+[[1/3]*[1/4]]]!のように有理数に関する計算をあらわしたリスト\verb+ :x +に対してその結果を有理数で出力する\verb+ Eva :x +を作ってください。作ってからの動作試験をお忘れなく。\\
{\bf （問５−５）}他のあなたが知っているプログラム言語との比較をしてみましょう。
\subsubsection{整式と巨大数}
整式 $a_nx^n +
a_{n-1}x^{n-1} + \cdots + a_2x^2 + a_1x + a_0 $ を、リスト［
$a_n~a_{n-1}~\cdots~a_1~a_0$］ であらわすことにします。\\
{\bf （問５−６）}２つの整式\verb+ :m :n +の和、積をそれぞれ出力する
\verb+ Plus_E :m :n,+\\
\verb+Times_E :m :n +を作れ。\\
{\bf （問５−７）}整式\verb+ :f +を$ ( x - a ) $で割ったときの商\verb+ :q +
と、あまり\verb+ :r +とを並べた\verb+ sentence :q :r +
を出力する\verb+ Horner :f :a
+を作れ\footnote{ヒント：剰余の定理、組み立て除法、ホーナー法。}。\\
{\bf （問５−８）}２次方程式 $ax^2+bx+c=0$ を\verb+:e = [ a b c ] +であらわす
とき、その解をページに書くプログラムを作れ。\\
{\bf （問５−９）}整数係数で有理数の解が少なくとも$n-2$個ある$n$次方程式、
$$a_nx^n+a_{n-1}x^{n-1}+\cdots+a_2x^2+a_1x+a_0=0$$
は因数定理を用いて解くことができます。この方程式をリスト\verb+:f = [ +$a_n a_{n-1}
\cdot a_2 a_1 a_0$ \verb+ ]+であらわしたものからその解を並べたリストを出力する\verb+ Solve :f +を作れ。\\
{\bf （問５−10）}Logo Writer の有効桁数は16桁です。それよりも大きい桁を扱おうとするときは、$10^8$未満の正の数を並べたリストで桁数の大きな数をあらわします。
このような２つの巨大数\verb+ :m :n
+を足す\verb+ Plus_M :m :n +を作れ
\footnote{途中のワードが7桁未満のときには、頭に0を入れる必要があることを忘れないでください。}。\\
{\bf （問５−11）}$10^8$未満の自然数\verb+ :n +に対して、その階乗を出力する
\verb+ Kaijou :n +を作れ。\\
\subsubsection{Run と数列}
\noindent
{\bf （問５−12）}ある数列の第$n$項を出力する関数がLogoで、\verb+Series
:n +と定義されているとき、\verb+:Kansuu
= [ Series :n ]+などを引数に持つ関数、
\begin{verbatim}
to Tuginokou :Kansuu :n
make "n :n + 1
output run :Kansuu
end
\end{verbatim}
の出力は何でしょう。
これをヒントに数列 \verb+ Series
:n + の階差数列
\verb!Series (:n+1) - Series :n ! の$n$番目の項を出力する関数を作れ。
また、リストでその一般項があらわされた数列の最初の$k$個の項の和を出力する
\verb+ Sigma :Kansuu :k +を作れ。\\
{\bf （問５−13）}プリミティブ\verb+ repeat + をまねる \verb+ Repeat_ + を作れ。\vspace{1zh}\\
少々強引ですが、\verb+run + 自体もまねることができます。
\begin{verbatim}
to Run_ :Command
if 1=1 :Command
end
\end{verbatim}
\verb+1=1 +とはいつでも真なら何でもよいのですが、論理定数は\verb+ "ほんとう とか "true +です。\verb+print
1=1 +を実行して確かめてみてください。なお、論理関数はすでに出た、\verb+not +の他に、\verb+or,and
+も使えます。ただし、これらは前置演算子です。
\subsubsection{集合と順列}
\noindent
{\bf （問５−14）}リストとしてあらわされた２つの集合が等しいことの真偽を出力する関数\verb+
Equal_Set :a :b +を作れ。つまり、
\begin{verbatim}
Equal_Set [1 2 3 6] [
1 6 2 3 ] は "true
Equal_Set [2 3 4] [1
2 3 4 5] は "false
\end{verbatim}
となるようにするのです。\\
{\bf ［問５−15］}リストの中から$k$個取って並べる順列をリストにして出力する
\verb+ Junretu+ \verb+:List :k +を作ってください。つまり、
\begin{verbatim}
Junretu [Cat Dog Ox]
2 が、
[[Cat Dog][Cat
Ox][Dog Cat][Dog Ox][Ox...]...]
\end{verbatim}
となるようにするのです。
\subsubsection{行列}
\noindent
{\bf （問５−16）}リスト\verb+[[2 1][3 4]]+で行列
$\left(
\begin{array}{rr}
2&1\\
3&4
\end{array} \right) $
をあらわすことにします。\vspace{0.5zh}\\
(1) 引数となっている行列を読みやすくページに記す \verb+Print_Mat+ を作れ。\\
(2) ２つの行列の和を出力する \verb+Plus_Mat :m :n +を作れ。\vspace{0.5zh}\\
(3) 行列$\left(
\begin{array}{rrr}
a_{11}&a_{12}&a_{13}\\
a_{21}&a_{22}&a_{23}
\end{array} \right) $ に対して、行列$\left(
\begin{array}{rr}
a_{11}&a_{21}\\
a_{12}&a_{22}\\
a_{13}&a_{23}
\end{array} \right) $ をもとの行列の\vspace{0.5zh}\\
転置行列と言います。転置行列を出力する\verb+
T_Mat :M +を作れ。\vspace{0.5zh}\\
{\bf ［問５−17］}有理数の行列もリストならあらわすことができます。\verb!*,+! のかわりに\verb+ Plus,Times +を使うことにしましょう。\\
(1) ２つの行列の積を出力する \verb+Times_Mat +を作れ。\\
(2) 行列であらわした連立一次方程式を引数にして、解を並べたリストを出力する
関数をはきだし法を使って作れ。\\
(3) ヒルベルト行列は「性格が悪い」と言われています。数値計算では誤差が大きくなるからです。これを (2) で解け。
\subsection{アニマルというプログラム}
「アニマル」と呼ばれるプログラムは、知識の獲得をまねるものです。
このプログラムは人間との「対話」\footnote{ほとんどの場面での答えは、yes をあらわす y と no の n しか認められませんが。} によって知識を獲得していきます。
いま、「ひとみちゃん」という名の幼児をまねるとすると、初めは［ひとみちゃん］という知識しかないのですが、
\begin{verbatim}
『パパが誰のこと考えてるかあててあげようか』−−−y
『ひとみちゃんでしょ？』−−−−−−−−−−−−−n
『まちがえちゃった。じゃあだあれ？』−−−−−−ママ
『ママが y で、ひとみちゃんが n になる質問なあに』
−−−−−−−−−−−−−−−−−−−−−−おとな
『ふうん、じゃあいまね。
パパが誰のこと考えてるかあててあげようか』−−−y
『おとな？』−−−−−−−−−−−−−−−−−−−y
『ママでしょ？』−−−−−−−−−−−−−−−−−n
『まちがえちゃった。じゃあだあれ？』−−−−−−じじ
『じじが y で、ママが n になる質問なあに』−−おとこ
『ふうん、じゃあいまね。
パパが誰のこと考えてるかあててあげようか』−−−y
『おとな？』−−−−−−−−−−−−−−−−−−−y
『おとこ？』−−−−−−−−−−−−−−−−−−−n
『ママでしょ？』−−−−−−−−−−−−−−−−−y
『ひとみちゃんおりこうでしょ。じゃあいまね。
パパが誰のこと考えてるかあててあげようか』−−−n
『じゃあ、あとでまた遊ぼうね。これ覚えとく？』−−y
（知識を裏のページに書き込んで終了）
\end{verbatim}
この「対話」によって次の図によってあらわされる知識を得ることができます。
\begin{itembox}{ひとみちゃんの世界}
\begin{verbatim}
おとな
／ ＼
ひとみちゃん おとこ
／ ＼
ママ じじ
\end{verbatim}
\end{itembox}
{\bf （問５−18）}例えば、初めの世界を［いぬ］として動物の名前をあてる対話もできます\footnote{だから、アニマルというのですが。}。いろいろな「対話」を手作業で行なって我々の知識の体系と比べてみましょう。
\vspace{1zh}
さて、実はこのような知識体系も、
\begin{verbatim}
［ひとみちゃん おとな ［ママ おとこ
じじ］］
\end{verbatim}
と、リストで表現することができますね。Logo が人工知能の実現に関わりのある Lisp
が元になっていることを味わってもらいましたか？これをどうプログラムとして実現するかは後の章で考えます。