LISP
担当教員
授業の到達目標及びテーマ
Schemeによるリスト処理のプログラミングを通して、リストの様な帰納的に定義されたデータ構造に対する再帰的プログラミングや初歩の関数的プログラミングとその有効性を習得する事を目標とします。
授業の概要と方法
LISP言語族の中で最も簡潔で判りやすい言語仕様を持つSchemeによるプログラミングの入門を通して、関数の再帰呼出を活用したプログラミングスタイル、特に、データ構造に基づいた再帰プログラミングへの理解を深め高階関数やデータ抽象化等の高度なプログラミング技法への入門を果たす事を目標します。講義は、Schemeの言語機能の基本的なものに関してプログラミングでの使用法を述べ、理解度の確認と評価の為の小テストを頻繁(学期中に8回前後)に実施します。
授業計画
| 回 | テーマ | 内容 |
|---|---|---|
| 1 | ガイダンス・序論 | 本講義の概要、目的、評価方法ならびに諸注意事項の説明を行い、LISPという言語(今では一連の言語から成る言語族)が誕生し発展して来た歴史的背景について説明を行う。更に本講義で扱うScheme言語の範囲についても述べる。 |
| 2 | プログラムの基本要素と基本データ (1): 基本データ | Schemeで用意されているデータの種別と、それらの中で内部構造を持たない基本的なデータとしての真偽値・数値・記号に関して、それらを扱う為の構文および標準手続きについて紹介する。 |
| 3 | プログラムの基本要素と基本データ (2): 2項対とリスト | LISPという名前の由来でもあり最も重要なデータ構造であるリストおよび2項対(ペア)の概念と、それを用いる為の標準手続き群について説明する。 |
| 4 | 関数と再帰的定義(1) | 関数定義の方法を説明し、更にSchemeプログラミングで最も重要な関数の再帰的定義について解説する。 |
| 5 | 関数と再帰的定義(2) : 再帰的定義の正しさ | 再帰的に定義された関数の正しさを証明する方法としての数学的帰納法を説明し、それを用いて具体的な関数の再帰的定義の正しさの証明を行う。 |
| 6 | Schemeでの関数の高度な機能 | Schemeの関数の持つポテンシャルの高さを知ってもらう為に、可変個の引数を受け取る関数の定義法と使い方、関数を引数として受け取ったり結果値として返す高階関数の考え方、引数無し関数を用いた無限データ構造(無限リスト)の作り方と使い方を説明する。 |
| 7 | データ構造に基づく再帰 | Schemeの最も重要なデータ構造であるリストのデータ構造としての再帰性に基づいてリスト処理関数を再帰的に定義する考え方を説明する。 |
| 8 | 局所宣言と環境 | 変数の局所的な宣言の為の構文、ならびにそれが表す意味としての環境という概念を学ぶ。 |
| 9 | 関数の抽象化: データとしての関数(1) | 第5回で触れた高階関数についてより深く学ぶ。複数の引数を受け取る関数を引数を1つずつ段階を分けて受け取る関数へと変換するカリー化の概念と方法について学習する。 |
| 10 | 関数の抽象化(2) | 前回の続きとしてカリー化での注意点、カリー化の逆操作、高階関数を用いた再帰的定義のパターン化について学習する。 |
| 11 | 再帰的に定義された関数の高速化 | 再帰的な関数を高速化する手段としての末尾再帰の概念を説明し、大変な高速化が可能なケースがある事を具体例で学ぶ。同時にリスト処理関数の末尾再帰化での注意点についても具体例から学ぶ。 |
| 12 | 破壊的代入による手続き的プログラミング | CやJavaといった普通のプログラミング言語では常識的な「変数の値を書き変えながら計算を進める」という手続き的プログラミングをSchemeで行う為の構文や標準手続きについて説明する。 |
| 13 | ベクトルを用いたプログラミング | SchemeにおいてC/Javaでの1次元の配列に相当するベクトルの概念と標準手続きの利用法について説明し、ベクトルを用いたプログラミングを学ぶ。 |
| 14 | Schemeの理論的背景としてのλ-計算 | Schemeの理論的背景としてのλ-計算について説明する。その結果として、万能計算系(Turing機械と同等の計算能力を有する計算系)の構築には、高階関数さえ用いれば再帰的定義すら必要ない事を学ぶ。 |
| 15 | まとめ | 今までのSchemeの言語の発展の歴史を振り返り、また今後の展望について概説します。 |
授業外に行うべき学習活動
初回の講義でSchemeの処理系(Dr. Racket)のインストール法を紹介します。受講生各自でその処理系を各自のパソコンにインストールして使用して下さい。特に毎回の講義の復習として、次の講義までに前回の講義で紹介したりテキストとして配布する資料に挙がっている例を実際に動かして試して下さい。 また、講義の理解が不十分だと感じた時には、講義資料やノートを読み直して十分な復習をし、必要と感じたら次の講義の際に堂々と質問すべく準備しておいて下さい。
テキスト
オリジナルのテキストを使用し、毎回、出席者に配布します。
参考書
ケント・ディヴィグ (Kent R. Dybvig)「プログラミング言語SCHEME」ピアソン・エデュケーション (2000). ジェラルド・ジェイ・サスマン(Gerald Jay Sussman), ハロルド・エイブルソン(Harold Ableson)「計算機プログラムの構造と解釈、第2版」ピアソン・エデュケーション (2000). ダニエル・フリードマン(Daniel P. Friedman)他「Scheme手習い」オーム社 (2010). ダニエル・フリードマン(Daniel P. Friedman)他「Scheme修行」オーム社 (2011). いずれも1階図書コーナーに複数冊所蔵されています。前者はSchemeの言語仕様の詳しい解説書、後者はSchemeを用いた高度なプログラミングの解説書です。 なお、Webリソースとしては、次のHPにScheme関連の情報が集積されていますので、活用して下さい。 http://www.schemers.org/
成績評価基準
講義は毎回出欠を取り、講義中に行う小テストの点数に基づいて評価します。
情報機器使用
本講義では直接には使用しませんが、各自の学習においてはパソコンに初回講義で紹介するScheme処理系をインストールして学習の助けとする為に各自はパソコンを用意しておいて下さい。インストール方法に関しては初回講義の際に資料を配布して説明します。
前年度の授業改善アンケートからの気づき
2011年度のアンケート結果は本シラバス作成時点では未だ受け取っていませんが、過去のアンケートで要望が多かった例題については、ある程度の纏まった例題や関数定義の例は講義資料に入れる様に心掛けました。 標準関数や構文などの簡単な細かい使用例は板書で示します。 これは講義をちゃんと聴き、板書をノートにとるという基本的な学習習慣を守り身に着けてもらう為に敢えて意図的にそうしています。
その他
今までに学んだプログラミングの講義での手続きや関数の再帰呼出しについて良く復習して十分に理解しておいて下さい。 なお、講義そのものではPCを使用しませんが、対となるプログラミング演習がないので、講義の初回に紹介するSchemeの処理系(Dr. Rachet)を各自のPCにインストールし、例題などを打ち込んで実際にSchemeプログラムを動かすと理解が容易になりまた深まりますので、必ず自分で処理系を動かして使用するようにして下さい。 また講義の板書はちゃんとノートにとるように心掛けて下さい。