WHAT'S NEW
CONTENTS
お気楽 Scheme プログラミング入門
CONTENTS
- 2007/12/22 Scheme の基礎知識 [1]
Scheme はリストが主人公、リストの構造、関数の実行、シンボルと文字列、式の計算、複雑な式を計算する、関数とプログラミング、関数定義、変数とは？
- 2007/12/22 Scheme の基礎知識 [2]
変数への代入、局所変数と大域変数、評価しちゃだめ、基本的なリスト操作、ドット対とドットリスト、リストの分解と合成、リストの操作は非破壊的
- 2007/12/23 Scheme の基礎知識 [3]
条件分岐、述語、数と算術演算、再帰定義、再帰定義とリスト操作、型述語
- 2007/12/23 Scheme の基礎知識 [4]
let による局所変数の定義、累乗の計算、累乗の高速化、複雑な条件分岐、繰り返し、末尾再帰、リストの反転、フィボナッチ関数、名前付き let、繰り返しと再帰定義
- 2007/12/24 数当てゲーム [1]
乱数のお話、線形合同法、1 から 100 までの乱数を生成する、データの入力、ゲーム本体の作成、等値関係を調べる述語、ゲームの実行
- 2007/12/29 数当てゲーム [2]
マスターマインド、数字を 4 つ選ぶ、入力処理を作る、文字型データ、bulls を数える、cows を数える、ゲーム本体を作る、ゲームの実行
- 2007/12/30 Scheme の入出力 [1]
標準入出力とは？、出力、format、入力、read-line、ファイル入出力、with-input-from-file と with-output-to-file、コマンドラインからパラメータを受け取る方法
- 2008/01/05 Scheme の入出力 [2]
平均値と標準偏差、ファイルを行単位で連結する、オプションの取得、行番号を表示する、文字列ポート
- 2008/01/06 Scheme プログラミング中級編 [1]
高階関数、マップ関数、マップ関数の作成、フィルター、畳み込み、畳み込みの応用例、apply、ラムダ式、リストの探索、連想リスト
- 2008/01/12 Scheme プログラミング中級編 [2]
局所変数の有効範囲 (レキシカルスコープ)、ダイナミックスコープ、ラムダ式と局所変数、高階関数とラムダ式、ラムダ式とクロージャ、関数を生成する関数、カリー化、ジェネレータ、乱数ジェネレータ
- 2008/01/13 順列と組み合わせ
順列の生成、バックトラック法の実装、プログラムの作成、高階関数版の作成、順列をリストに格納する、組み合わせの数、パスカルの三角形、組み合わせの生成 (1)、組み合わせをリストに格納する、組み合わせの生成 (2)、組み合わせに番号を付ける方法
- 2008/01/19 Scheme プログラミング中級編 [3]
配列、ベクタの操作関数、ベクタ用の高階関数、リストとベクタの比較、二分探索、ソート (挿入ソート)
- 2008/01/20 Scheme プログラミング中級編 [4]
リスト構造の修正、リストの連結、リストの反転、リストによるキューの実装、可変個引数、循環リスト、循環リストのチェック、循環リストによるキューの実装
- 2008/01/26 二分木
木、二分木、リストによる二分木の実装、節の構造、データ抽象、プログラムの作成、データの探索、データの挿入、データの削除、巡回、実行例
- 2008/01/27 ヒープとハッシュ法
ヒープ、ヒープの構築 (1)、ヒープの再構築、ヒープの構築 (2)、優先度付き待ち行列、実行例、ハッシュ法、ハッシュ法の仕組み、チェイン法、プログラムの作成、データの探索、データの挿入、データの削除、巡回、実行例
- 2008/02/02 集合、グラフ、経路の探索
集合、union、intersection、set-difference、set-exclusive-or、subset?、集合の構築、実行例、グラフ、隣接行列と隣接リスト、連想リストによる方法、経路の探索、バックトラックによる探索 (深さ優先探索)、幅優先探索、経路の管理、プログラムの作成、反復深化、反復深化による経路の探索
- 2009/05/30 継続と継続渡しスタイル
継続とは？、継続渡しスタイルとは？、再帰呼び出しと継続渡しスタイル、二重再帰と継続渡しスタイル、継続渡しスタイルの便利な使い方、継続、大域脱出、繰り返しの中断、再帰呼び出しからの脱出、letrec、イテレータ、イテレータを生成する関数、追記 (2011/01/23) : 高階関数と継続渡しスタイル
- 2009/06/06 マクロ (1)
Ｃ言語のマクロ、伝統的なマクロ、マクロとコンパイラの関係、スタックの操作、スタックを操作するマクロ、バッククオート、伝統的なマクロの問題点 (1)、伝統的なマクロの問題点 (2)、マクロの再帰定義
- 2009/06/07 マクロ (2)
健全なマクロ、伝統的なマクロとの違い (1)、伝統的なマクロとの違い (2)、識別子の使い方、マクロの再帰定義、健全なマクロの弱点
- 2009/06/07 メモ化と遅延評価
たらいまわし関数、ハッシュ表、メモ化による高速化、メモ化関数、遅延評価による高速化、クロージャによる遅延評価
- 2017/02/05 遅延ストリーム (1)
遅延ストリームの構造、遅延ストリームの生成、遅延ストリームへの変換、遅延ストリームの操作関数、遅延ストリームの連結、高階関数、stream-map の便利な使い方、stream-flatmap、stream-take-while と stream-drop-while、エラトステネスの篩、より高速な方法
- 2017/02/05 遅延ストリーム (2)
遅延ストリームの併合、集合演算、ハミングの問題、順列の生成、遅延ストリーム版、８クイーンの解法、木の巡回と CPS、木の巡回と遅延ストリーム、ツリーマッチング
- 2017/02/12 遅延ストリーム (3)
遅延ストリームをプロミスで表す、stream-delay、実行速度の比較、問題点、SRFI-40、Gauche の遅延シーケンス
- 2009/06/20 便利なリスト操作関数
iota と list-tabulate、take と drop、マッピング、フィルター、畳み込み、解きほぐし (逆畳み込み)、リストの探索、リスト操作関数の一般化、木の操作関数の一般化、追記 (2009/11/22)、修正 と 補足 (2011/01/23)
- 2009/07/11 多値
call-with-values と values、receive と let-values、define-values と set!-values、values-ref、クイックソート、クイックソートの弱点、追記 (2011/01/29) 多値と継続渡しスタイル
- 2009/07/11 非決定性
amb の動作、関数版 amb の作成、解をすべて求める、論理パズル、マクロ版 amb の作成、地図の配色問題
- 2009/07/18 非決定性 (2)
amb は深さ優先探索、経路の探索、幅優先探索版 amb の作成、水差し問題、反復深化、do、反復深化による経路の探索、反復深化による水差し問題の解法、積木の移動
- 2009/07/25 Scheme で作る micro Scheme
S 式の評価、関数適用、変数束縛と値の取得、シンタックス形式の処理、read-eval-print-loop、簡単な実行例、レキシカルスコープとクロージャの動作、再帰定義とリスト操作、ダイナミックスコープと funarg 問題
- 2009/08/01 Scheme で作る micro Scheme (2)
マクロの定義、バッククオートの処理、マクロの評価、set! と eqv? の追加、let、and と or、let*、letrec、名前付き let、begin、cond、case、do
- 2009/08/08 Scheme で作る micro Scheme (3)
継続渡しスタイル (CPS) による継続の実装、S 式の評価の修正、シンタックス形式の修正、マクロの修正、関数適用の修正、REPL の修正、簡単な実行例、大域脱出、繰り返しからの脱出、再帰呼び出しからの脱出、イテレータの生成、末尾再帰最適化
- 2009/09/12 micro Scheme コンパイラの作成
SECD 仮想マシン、SECD 仮想マシンの命令、コンパイラの作成、引数とラムダ式本体の評価、局所変数の位置を求める、簡単なコンパイラのテスト、仮想マシンの作成、read-eval-print-loop、簡単な実行例、レキシカルスコープとクロージャの動作、再帰定義とリスト操作
- 2009/09/19 micro Scheme コンパイラの作成 (2)
マクロの定義、マクロのコンパイル、バッククオートの処理、簡単な実行例、set! と eqv? の追加、let、and と or、let*、letrec、名前付き let、begin、cond、case、do
- 2009/09/20 micro Scheme コンパイラの作成 (3)
継続の実装、call/cc のコンパイル、ldct の追加と app の修正、apply の実装、簡単な実行例、大域脱出、繰り返しからの脱出、再帰呼び出しからの脱出、イテレータの生成
- 2009/09/21 micro Scheme コンパイラの作成 (4)
末尾再帰最適化、コンパイラの修正、仮想マシンの修正、簡単な実行例、たらいまわし関数、遅延評価
2012/03/03 Appendix: ldg, gset 命令の改良
2013/08/24 Appendix: バッククォートの修正
- 2011/04/17 コルーチン
コルーチン、コルーチンの動作、コルーチンの作成、簡単なテスト、高階関数をジェネレータに変換、順列の生成、エラトステネスの篩
- 2011/04/17 部分継続
部分継続、イテレータを生成する関数、部分継続によるコルーチンの実装、継続による部分継続の実装、部分継続によるバックトラックの実装 (2012/07/29)
- 2011/06/05 コルーチン (2)
並行プログラミングとは？、簡単なマルチプロセスの作成、簡単な実行例、キューによる同期処理、哲学者の食事、実行結果 (1)、デッドロックの防止、実行結果 (2)、デッドロックの防止 (2)、実行結果 (3)
- 2011/07/30 電卓プログラムの作成
プログラミング言語処理系の基本的な構造、文法の表現、式の構文、字句解析、構文解析、式の入力と評価、実行例、単項演算子の追加、実行例 (2)
- 2011/07/31 電卓プログラムの作成 (2)
変数、関数、変数と関数の操作、字句解析、構文解析、実行例、代入を文として実装する場合、実行例 (2)
- 2011/08/06 電卓プログラムの作成 (3)
ユーザー関数の定義、文法の変更、文字列ポート、字句解析、構文解析、ユーザー関数の評価、引数の処理、関数定義、実行例
- 2011/08/07 電卓プログラムの作成 (4)
論理演算子と比較演算子の優先順位、条件分岐、文法の修正、字句解析の修正、構文解析の修正、条件分岐の処理、実行例
- 2011/08/13 電卓プログラムの作成 (5)
字句解析と構文解析の分離、ユーザー関数の定義、ユーザー関数の評価、begin 式と while 式、begin 式の処理、while 式の処理、関数 calc の修正、実行例
- 2011/08/14 関数型電卓プログラム fncalc の作成
fncalc の文法、fncalc 用の SECD マシン、式のコンパイル、文のコンパイル、if 文のコンパイル、block 文のコンパイル、while 文のコンパイル、let 文のコンパイル、簡単なテスト
- 2011/08/21 関数型電卓プログラム fncalc の作成 (2)
SECD 仮想マシンの作成、実行例、連結リストの作成、リストの破壊的な修正、ファイルのロード
- 2011/08/27 関数型電卓プログラム fncalc の作成 (3)
継続の導入、callcc のコンパイル、ldct の追加と app の修正、簡単な実行例、大域脱出、繰り返しの中断、再帰呼び出しからの脱出、ジェネレータの作成
- 2011/08/28 関数型電卓プログラム fncalc の作成 (4)
末尾再帰とは？、末尾最適化の仕組み、末尾最適化の実装、仮想マシンの修正、簡単な実行例、相互再帰、たらいまわし関数、遅延評価による高速化
- 2011/09/10 関数型電卓プログラム fncalc の作成 (5)
and と or の修正 (短絡演算子)、and と or のコンパイル、実行例 (1)、ベクタの生成とアクセス方法、ベクタのコンパイル、要素の書き換え、SECD マシンの修正、実行例 (2)
- 2011/09/18 関数型電卓プログラム fncalc の作成 (6)
データの探索、二分探索、バブルソート、選択ソート、単純挿入ソート、クイックソート、エラトステネスの篩、素因数分解、木の操作関数
- 2011/10/30 記号のパターンマッチング
パターンマッチング、パターン変数は連想リストで管理する、match の実装、ユニフィケーション、unify の実装
Appendix : Prolog ライクなユニフィケーション
パズルの解法
- 2008/01/14 パズルの解法 [1]
8 クイーン、斜めの利き筋のチェック、8 クイーンの解法、プログラムの高速化、マスターマインド、推測アルゴリズム、プログラムの作成、何回で当たるか
- 2008/02/09 パズルの解法 [2]
８パズルの説明、幅優先探索による解法、実行結果、双方向探索、最長手数の求め方、プログラムの作成、dolist、when と unless、実行結果
- 2008/02/11 パズルの解法 [3]
ペグ・ソリテア、Hoppers、跳び先表とペグの移動、反復深化による Hoppers の解法、実行結果、反復深化による 8 パズルの解法、実行結果、下限値枝刈り法、下限値枝刈り法のプログラム、実行結果
- 2009/06/21 パズルに挑戦 (1)
小町算、覆面算、蛙跳びゲーム、川渡りの問題、油分け算、解答 (2009/06/27)
- 2009/06/28 パズルに挑戦 (2)
大町算、騎士の周遊、嫉妬深い夫の問題、地図の配色問題、スライドパズル NO-OFF、解答 (2009/07/04)
- 2010/05/15 パズルに挑戦 (3)
Four Four's (解答 2010/05/22)、騎士の交換 (解答 2010/05/22)、ペグ・ソリティア (解答 2010/05/29)、８めくり (解答 2010/05/29)、スライドパズル (解答 2010/05/29)
- 2010/06/05 パズルの解法 [4]
ちょっと便利なビット操作関数、N Queens Problem
2013/11/23 (改訂) 数独、単純なバックトラックによる解法、実行例 (1)、データ構造を工夫する、フラグの操作関数、バックトラックによる解法、実行例 (2)
- 2010/06/12 パズルの解法 [5]
2013/11/24 (改訂) 数独の高速化、ちょっと便利な高階関数、確定サーチ、置ける数字がひとつしかないマスを探す、縦横枠で置くことができる数字を探す、実行例 (3)、追記 : 試行順序の変更 (2013/11/30)
2010/06/13 ちょっと寄り道「ラテン方陣」
- 2010/06/19 パズルの解法 [6]
2013/11/30 (改訂) 数独の確定的アルゴリズム、データ構造の変更、バックトラックによる解法、実行例 (4)、Enclosure と Negation、Enclosure の実装、Negation の実装、確定的アルゴリズムによる解法、実行例 (5)
- 2010/06/27 パズルの解法 [7]
2013/12/01 (改訂) 数独の確定的アルゴリズム、Intersection、Intersection の具体例、Intersection の実装、実行例
- 2010/08/08 ミニマックス法と三目並べ
ゲームの木、ミニマックス法、三目並べ、プログラムの作成、勝敗の判定、先手の指し手、後手の指し手、初手の評価値を求める、実行結果、戦略に基づいたプレイ、プログラムの作成 (2)、実行結果 (2)
- 2010/08/14 アルファベータ法とミニミニリバーシ
ミニミニリバーシ、盤面のデータ構造、反転する石を求める、ミニマックス法のプログラム、実行結果、アルファベータ法、アルファベータ法のプログラム、実行結果 (2)、探索順序の変更
- 2010/08/15 ネガマックス法とネガアルファ法
ネガマックス法、ネガアルファ法、ネガアルファ法の改良、プログラムの作成、実行結果
- 2010/08/21 ネガスカウト法
ミニミニリバーシ変形版、プログラムの修正、実行結果、null window search、ネガスカウト法、プログラムの作成、実行結果 (2)
- 2010/08/28 置換表と MTD(f) 法
置換表とは？、ネガマックス法と置換表、プログラムの作成、実行結果、アルファベータ法と置換表、実行結果 (2)、MTD(f) 法、実行結果 (3)
Yet Another Scheme Problems
オブジェクト指向編
- 2010/03/14 オブジェクト指向の基礎知識
オブジェクトとは？、クラスとインスタンス、メソッド、クラスの定義、キーワード、汎変数、インスタンスの生成、メソッドの定義、スロットのアクセス、<point> クラス、既存のデータ型とクラスの関係
- 2010/03/14 双方向リスト
双方向リストとは？、双方向リストのメソッド、クラスの定義、データの参照、データの更新、データの挿入、データの削除、畳み込みと巡回、データの変換、その他のメソッド、実行例
- 2010/03/21 継承 (1)
継承とは？、単一継承と多重継承、単一継承の使い方、スロットとメソッドの継承、スーパークラスに同じスロット名がある場合、データ型の継承、メソッドの選択、複数の引数がある場合、メソッドのオーバーライド
- 2010/03/21 継承 (2)
制限付き双方向リスト、継承は is-a 関係を表す、スタックの実装、キューの実装、ディーキューの実装
- 2010/03/28 多重継承
多重継承の使い方、多重継承におけるメソッドの選択、スーパークラスに同じスロットがある場合、多重継承の問題点、Mix-in、クラス <enumerable>、イテレータを使う方法
- 2010/03/28 コレクションとシーケンス
既存のデータ型とクラスの関係、コレクションのメソッド、シーケンスのメソッド、コレクションクラスの実装、メタクラスとは？、クラスの定義、メソッドの定義、コレクションの実行例、シーケンスクラスの実装、シーケンスの実行例
- 2010/04/04 モジュール
モジュールとは？、モジュールの定義と評価、import と export、モジュールの作り方、モジュールのロード
- 2010/04/04 共有スロット
共有スロットの設定、共有スロットの継承、共有スロットの衝突、局所スロットと共有スロットの衝突
- 2010/04/17 インスタンスの初期化
総称関数 initialize、ベクタによるキューの実装、プログラムの作成、実行例
- 2010/04/17 可変長ベクタ
可変長ベクタの仕様、クラスの定義とベクタの初期化、汎変数の定義、ベクタのリサイズ、データの使いと取り出し、イテレータ、実行例
- 2010/04/29 ヒープ
ヒープとは？、ヒープの仕様、クラスの定義、メソッドの定義、実行例、ハフマン符号、ハフマン符号のアルゴリズム、節の定義、出現頻度表の作成、ハフマン木の生成、符号化と復号
- 2010/05/01 二分木
二分木の仕様、クラスの定義、データの探索、データの挿入、データの削除、巡回、イテレータと畳み込み、実行例
はじめに
Scheme は 1975 年に Gerald J.Sussman と Guy L. Steele Jr. によって作成された Lisp の方言です。伝統的な Lisp はダイナミックスコープですが、Scheme はレキシカルスコープを採用しています。その後、Common Lisp でもレキシカルスコープが採用されました。Scheme は Common Lisp に比べ、言語仕様がコンパクトにまとまっていて、関数を first class object として扱うことができます。参考文献 [2] では、first class object を「一等値」と訳していますが、ようするにプログラミング言語で計算対象となるデータ（値）のことです。
関数型言語の場合、関数は他のデータと同等に扱うことができます。つまり、関数を変数に代入したり、関数を引数として渡すことができます。また、関数を値として返すこともできます。ところが、Common Lisp の関数は完全な first class object ではありません。次の例を見てください。
> (setq func #'(lambda (x y) (+ x y)))
#<FUNCTION :LAMBDA (X Y) (+ X Y)>
> (funcall func 1 2)
3
上の例は CLISP で実行した場合です。ラムダ (lambda) 式は無名の関数を返します。それを変数 func に格納して呼び出すことができます。Common Lisp の場合、変数に格納された関数は (func 1 2) のように呼び出すことはできません。funcall や apply を使って呼び出します。これに対し、Scheme は (func 1 2) と呼び出すことができます。次の例を見てください。
> (define func (lambda (x y) (+ x y)))
func
> (func 1 2)
3
このように、Common Lisp よりも簡単に関数を取り扱うことができます。また、「継続 (continuation) 」を取り扱うことができるのも Scheme の特徴です。継続はプログラムの実行状態を保存しておいて、あとから実行を再開することができます。これは Common Lisp にはない強力な機能です。
Scheme には多数の処理系がありますが、このページでは Shiro Kawai さんが開発されている Gauche をメインに使いたいと思います。M.Hiroi は Scheme 初心者ですが、「継続」を使いこなすことができるようにがんばりたいと思います。たいしたことはできませんが、よろしければお付き合いくださいませ。
Scheme Junk Scripts
M.Hiroi が Scheme の勉強で書いたジャンクスクリプトです。
参考文献, URL
- R. Kent Dybvig (著), 村上雅章 (訳), 『プログラミング言語 SCHEME』, 株式会社ピアソン・エデュケーション, 2000
- Ravi Sethi (著), 神林靖 (訳), 『プログラミング言語の概念と構造』, アジソンウェスレイ, 1995
- 紫藤貴文, 『もうひとつの Scheme 入門』, 紫藤のページ
- Dorai Sitaram (著), Nobuo Yamashita (訳), 『独習 Scheme 三週間』, WWW.SAMPOU.ORG
『お気楽 Scheme プログラミング入門』と『Scheme Junk Scripts』の著作権は筆者「広井誠 (Makoto Hiroi) 」が保持します。無断使用や無断転載は禁止いたします。お気楽 Scheme プログラミング入門と Scheme Junk Script で作成したプログラムはフリーソフトウェアとします。ご自由にお使いください。プログラムの改造や配布もご自由にどうぞ。その際は、出典を明記してくださるようお願いいたします。
ただし、これらのプログラムは無保証であり、使用したことにより生じた損害について、作者「広井誠 (Makoto Hiroi) 」は一切の責任を負いません。また、これらのプログラムを販売することで利益を得るといった商行為は禁止いたします。
Copyright (C) 2006-2017 Makoto Hiroi
All rights reserved.