この記事は，プログラミング言語Schemeをほとんど知らない，けれども他の言語でプログラミングに触れた経験がある人向けに，最低限の記述方法と応用例をまとめたものです．※わかる人向け：SICP冒頭一時間体験コースもどき

#主に想定される読者

本格的にプログラミングを学びたいけど，メジャーな言語は文法やライブラリが複雑・大規模で敷居が高く，もうちょっと手軽に体験できる言語で試してから，他の言語にステップアップしたい．
プログラミングは極めているがSchemeはよく知らないので，『知っている言語』を増やすため，とりあえずどういう言語か知っておきたい．
…といった要望が身近にあって，何か参考資料が欲しい人．（←記事を作成した主な理由）

なお，この記事の後半で紹介している応用例は次の通りです．

末尾再帰によるフィボナッチ数計算
高階手続きを用いた数値微分
クロージャを用いたリスト構造
ブラックボックス手法によるFizzBuzz問題
ストリームによる無限リスト
ラムダ計算による条件分岐

#Scheme記述の実行
この記事内容に限っては，スマートフォンのSchemeアプリでほぼ実行可能です．『JDoodle』などのWeb実行環境でも良いかもしれません．言語処理系としてはGauche，GNU Guile，SCMなどがあり，JDoodleではGaucheが用いられています．

#基本的な記述方法

##括弧と空白
Schemeでは，プログラム記述のほとんどが(?? ?? ?? ...)という，括弧と空白の組合せで表現されます．通常，括弧内の先頭の要素が処理を行う『手続き』の名前であり，残りの要素は，その手続きに渡す値となります．四則演算を表す+ - * /もあらかじめ用意された手続きであることから，計算式はいわゆる前置記法となります．

次の記述例は，実行すると(10+30)*(20-30)の計算が行われ，-400が表示されます．なお，Schemeにおけるセミコロン（;)は，それ以降の記述がコメント文とみなされ，無視されます．

(display (* (+ 10 30) (- 20 30)))    ; => -400

上記の記述例にあるdisplayは，表示のためにあらかじめ用意された手続きです．値はひとつしかとりませんので，必要に応じて繰り返し用いることになります．文字列を扱いたい場合は，その文字列をダブルクォート（"）で囲みます（たとえば，空白は" "，改行は"\n"）．

##条件式と条件分岐
大小関係を表す記号には= < >などがありますが，これらもあらかじめ用意されている手続きです．したがって，四則演算の記号と同じく，括弧の中の最初の要素として記述し，比較する値をふたつとることになります．この手続き処理が『条件式』として成立していれば#t，成立していなければ#fという特別な値が出力されます．

(display (= (- 20 30) -10))          ; => #t
(display (> (- 20 30) (- 30 20)))    ; => #f

この条件式を利用して，condという記号を用いた条件分岐の手続きが記述できます．条件式と，その条件式が#tの時に行わせたい処理を括弧でセットにして記述します．全ての条件式が#fの時に行わせたい処理がある時は，elseという記号と組み合わせます．

(cond ((> 20 30) (display "20 > 30")) (else (display "20 <= 30")))
; => "20 <= 30"

なお，condとelseは，特別な処理を行うための記号であり，四則演算や大小関係のような手続きの名前ではないことに注意して下さい．手続きでは，括弧内の残りの要素を全て実行してから処理が行われますが，condやelseを用いた記述では，一部の要素のみが実行されます．上記の例では，(> 20 30)が#fであるため，(display "20 > 30")は実行されません．

##値や手続きへの名前付け
defineは，値や手続きに名前を対応付けるために用いられる記号です．次の記述例は，xに100，yに40を対応付けてから，xがyの2倍より大きいかどうかを判断した結果を表示しています．

(define x 100)
(define y 40)
(display (> x (* y 2))) ; => #t

手続きに名前を対応付ける場合は，まずlambdaという記号を用いて手続きを構成し，その後，defineで名前を対応付けます．lambdaで構成した手続きは，名前を付けずに実行することも可能です．

次の例は，上記の条件式について，2つの値x，yをとる手続きをlambdaで構成し，それから，funcという名前をdefineで付けています．

(define func (lambda (x y) (> x (* y 2))))
(display (func 100 40))    ; => #t

; 名前を付けずに実行することも可能
(display ((lambda (x y) (> x (* y 2))) 100 40))
; => #t

なお，defineとlambdaも手続きの名前ではなく，特別な処理のために用いる記号です．特に，lambdaを用いた記述は，その記述の時点では実行されず，手続きとして呼び出された時にあらためて実行されることに注意して下さい．

##再帰手続き
手続きに名前を対応付けることで，その手続きの中で，自身の手続きを再帰的に（recursively）呼び出すことができます．

次の記述例は，再帰手続きを用いて，1からxの値までの整数を足す手続きsumを定義し，実行しています．自身を繰り返し呼び出しているため，記述よりも多くの処理が実際には行われることに注意して下さい．

(define sum (lambda (x) (cond ((= x 0) 0) (else (+ x (sum (- x 1)))))))
(display (sum 10))    ; => 55

ところで，プログラム記述は通常，改行や不要な空白は無視されますので，括弧の対応さえ正確であれば，字下げや改行，コメントなどを用いて見やすくすることができます．

(define sum
  (lambda (x)
    (cond ((= x 0) 0)    ; xが0の時は，0を返す
          (else                    ; xが0ではない時          
           (+ x (sum (- x 1))))))) ; x-1で自身を呼び出した結果にxを足して返す
(display (sum 10))    ; => 55

#応用例

##フィボナッチ数
n番目の値は，前の2つの値，すなわち，n-1番目のフィボナッチ数とn-2番目のフィボナッチ数を足したもの，と定義される値です．なお，1番目のフィボナッチ数は0，2番目のフィボナッチ数は1とします．

定義に沿って，x番目のフィボナッチ数を求めるプログラムを再帰手続きによって作成した例が次の記述です．

fib1.scm

(define fib
  (lambda (x)
    (cond ((= x 1) 0)
          ((= x 2) 1)
          (else (+ (fib (- x 1)) (fib (- x 2)))))))
(display (fib 15))    ; => 377

この手続きでは，3番目以降のフィボナッチ数を求めるために，自分自身を2回呼び出して1つ前と2つ前のフィボナッチ数を得てから計算しています．そして，5番目以降となると，自分自身を1回呼び出すごとに，更にそこからそれぞれ2回呼び出して計算していくことになります．このため，40番目ともなると膨大な時間がかかることになり，50番目あたりになると，多くのコンピュータで処理しきれなくなります．

そこで，自分自身を呼び出した結果を用いて計算するのではなく，計算を行ってから自分自身を呼び出すようにすることで，計算を後回しにして溜め込んでいくことがないようにします．次の記述例は，前の2つのフィボナッチ数を表す名前として新たにf1，f2を設け，最初に0,1をそれぞれ対応付けつつ，自分自身を呼び出す前に，f1の値をそれまでのf2に，f2の値をf1+f2の値にして自分自身を呼び出しています．呼び出すたびにxの値も1減らし，xが1となった時のf1の値を結果として出力します．

fib2.scm

(define fib2
  (lambda (x f1 f2)
    (cond ((= x 1) f1)
          (else (fib2 (- x 1) f2 (+ f1 f2))))))
(display (fib2 50 0 1))    ; => 7778742049

このような『自分自身を呼び出すのは，必要な処理を全て行ってから』という処理パターンを，末尾再帰呼び出し（tail recursive call）と呼び，実質的には，単純な繰り返し処理に相当します．

##数値微分
lambdaを用いた手続きは，他の手続きに渡す値として指定することができます．また，手続きの中でlambdaを用いた手続きを新しく記述して，手続きの処理結果としてその新しい手続きを返すことができます．このような手続きを，高階手続き（higher-order procedure）と呼びます．

次の記述例は，三乗を計算する手続きcubeを定義し，5の三乗を求めています．ただし，すぐに(cube 5)と呼び出さず，cubeをexecという手続きに値として渡してから実行しています．

deriv1.scm

(define exec (lambda (f x) (f x)))
(define cube (lambda (x) (* x x x)))
(display (exec cube 5))    ; => 125
; 手続きexecにf=cube，x=5を渡し，(cube 5)を実行した結果を表示している

上記を修正し，手続きexecもすぐにはcubeを実行せず，実行するための手続きを更にlambdaで作り出し，その手続きを用いて，あらためて実際の処理を行うようにしたのが，次の記述例です．

deriv2.scm

(define exec (lambda (f) (lambda (x) (f x))))
(define cube (lambda (x) (* x x x)))
(display ((exec cube) 5))    ; => 125
; 手続きexecにf=cubeを渡し，(lambda (X) (cube x))を作り出す
; 作り出した手続きは((lambda (x) (cube x)) 5)として実行される

これを利用すると，値として渡した手続きをそのまま実行せず，別の処理を追加した上で実行することができます．次の記述例は，手続きexecに導関数$f'(x)=\lim_{h \to 0}\frac{f(x+h)-f(x)}{h}$の定義を加えたものです．

deriv3.scm

(define h 0.000001)
(define exec
  (lambda (f)
    (lambda (x)
      (/ (- (f (+ x h)) (f x)) h))))

(define cube (lambda (x) (* x x x)))
(display ((exec cube) 5))    ; => 75.00001501625775

##リスト構造
lambdaを用いた手続きは，更にその手続きの中でlambdaを用いることで，最初のlambdaで引数として指定した名前を，その中のlambdaの手続き専用の保管場所のように使用することができます．これをクロージャ（closure）と呼びます．

次の記述例は，保管場所をふたつ用意する手続きpair，保管場所からそれぞれの値を取り出す手続きpa，pbを定義して利用しています．

list1.scm

(define pair (lambda (a b) (lambda (f) (f a b))))    ; a, bが保管場所
(define pa (lambda (f) (f (lambda (a b) a))))
(define pb (lambda (f) (f (lambda (a b) b))))

(define x (pair 10 20))    ; => xに10と20が保管される
(display (pa x))    ; => 10
(display (pb x))    ; => 20

この手続きを利用して，『リスト』と呼ばれるデータ構造を作成することができます．具体的には，pairで保管するふたつの値について，paで取り出される値を実際の値，pbで取り出される値を次のpairとします．リストは，必要に応じて値を数珠つなぎに追加していくもので，処理をしながら値を蓄積していくのに向いています．

次の記述例は， "Hello" → "nice" → "to" → "meet" → "you" と，5つの文字列が数珠つなぎとなったリストを作成しています．なお，ここではリストの最後を示すために，-1をふたつ保管したpairを用いています．

list2.scm

(define strs
  (pair "Hello"
        (pair "nice"
              (pair "meet"
                    (pair "to"
                          (pair "you"
                                (pair -1 -1)))))))

(display (pa strs))    ; => Hello
(display (pa (pb strs)))    ; => nice
(display (pa (pb (pb (pb (pb strs))))))    ; => you
(display (pa (pb (pb (pb (pb (pb strs)))))))    ; => -1

次の記述例は，1からxの値までの整数の列を，(pair -1 -1)の前にxの値を1減らしながら追加していくことでリストにする手続きを定義し，1〜20のリスト構造を作り出しています．更に，保管された値をリストの先頭から表示する手続きl-disp1，リストの最後から表示する手続きl-disp2を定義し，実際に表示しています．

list3.scm

(define listnum
  (lambda (x p)
    (cond ((= x 0) p)
          (else (listnum (- x 1) (pair x p))))))

(define l-disp1
  (lambda (L)
    (cond ((= (pa L) -1) )    ; リストの最後に来たらなにもせず戻る
          (else (display (pa L)) (display " ")
                (l-disp1 (pb L))))))
(define l-disp2
  (lambda (L)
    (cond ((= (pa L) -1) )    ; リストの最後に来たらなにもせず戻る
          (else (l-disp2 (pb L))
                (display (pa L)) (display " ")))))

(define a (listnum 20 (pair -1 -1)))
; aに(pair 1 (pair 2 ... (pair 20 (pair -1 -1)) ... ))と同じ内容が保管される

(l-disp1 a)    ; => 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
(l-disp2 a)    ; => 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

##FizzBuzz問題
1から順にひとつずつ値を増やし，その値が3で割り切れるならば"Fizz"，5で割り切れるならば"Buzz"，3でも5でも割り切れるならば"FizzBuzz"と表示し，それ以外はそのままその値を表示する，という問題です．3でも5でも割り切れる，というのは，15で割り切れる，と考えることもできます．

ある値xがnで割り切れる，という判断を行うには，xをnで割った時の余りを求める必要があります．Schemeではそのための手続きがあらかじめ用意されていますが，ここでは，新しく%という名前で手続きを定義してみましょう．考え方としては，xからnの値をどんどん引いていき，xの値がnの値よりも小さくなった時のxの値が余り，というものです．なお，今回は負の値は扱わないことにします．

fb1.scm

(define %
  (lambda (x n)
    (cond ((< x n) x)
          (else (% (- x n) n)))))

この%を用いて，xがnで割り切れるか否かを判断する手続きdを定義します．ついでに，表示のための手続きdisplayは，呼び出す名前としては長いので，pだけで呼び出せるようにします．

fb2.scm

(define d (lambda (x n) (= (% x n) 0)))
(define p display)

次に，xが3，5，15でそれぞれ割り切れるかを判断し，"Fizz"，"Buzz"，"FizzBuzz"を表示する手続きcを定義します．ここで注意したいのは，3で割り切れたらすぐに"Fizz"と表示してはならず，5でも割り切れたら，すなわち，15で割り切れたら"FizzBuzz"と表示しなければならないことです．これは，最初に5で割り切れる場合も同様です．このため，まず最初に15で割り切れるか否かを判断し，15で割り切れなかった時のみ，3や5で割り切れるかを判断します．

fb3.scm

(define c
  (lambda (x) 
    (cond ((d x 15) (p "FizzBuzz "))
          ((d x  3) (p "Fizz "))
          ((d x  5) (p "Buzz "))
          (else (p x) (p " ")))))

最後に，1からxまでの整数を順番に判断・表示する手続きfbを作成します．次の記述例は，以前の繰り返しの記述を流用しています．

fb4.scm

(define fb
  (lambda (x) 
    (cond ((= x 0) )    ; xが0の時はなにもせず戻る
          (else (fb (- x 1))
                (c x)))))

これで必要な手続きが全て揃いましたので，1から20までの整数で実行します．次の記述例は，全ての手続きをまとめたものです．

fb5.scm

(define %
  (lambda (x n)
    (cond ((< x n) x)
          (else (% (- x n) n)))))

(define d (lambda (x n) (= (% x n) 0)))
(define p display)

(define c
  (lambda (x) 
    (cond ((d x 15) (p "FizzBuzz "))
          ((d x  3) (p "Fizz "))
          ((d x  5) (p "Buzz "))
          (else (p x) (p " ")))))

(define fb
  (lambda (x) 
    (cond ((= x 0))
          (else (fb (- x 1))
                (c x)))))

(fb 20)
; => 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz

今回のプログラム作成のポイントは，FizzBuzz問題を解決するために必要な処理は何かを分割して考えていき，分割した処理ごとに解決のための手続きを作成，その後，あらためてそれらの手続きを組み合わせて最終的な結果を出している点です．プログラムコードを単純に分割するのではなく，意味のあるまとまった機能ごとに分割していることに注意して下さい．

特に，%は独自に定義したにも関わらず，その『使い方』は，本来Schemeであらかじめ用意されている，余りを計算する手続きとほぼ同じです．実際に内部でどのように処理しているかは異なりますが，今回のプログラムにおける役割としては同じあり，規格化された部品と言えます．このような考え方を，一般にブラックボックス手法（black box approach）と呼びます．

##無限リスト
手続きへの名前付けの説明の中で，lambdaを用いた記述は，その記述の時点では実行されず，手続きとして呼び出された時にあらためて実行されることを述べました．

stream1.scm

(display (+ 2 1))    ; すぐに3が表示される
(define x (lambda () (display (+ 2 1))))    ; この時点では(display (+ 2 1)は実行されない
(x)    ; この時点で(display (+ 2 1)が実行され3が表示される

この仕組みを用いて，もう少し使いやすいリスト構造を考えてみましょう．まず，pair，pa，pbは，リスト構造の例で定義した手続きをそのまま使用します．

stream2.scm

(define pair (lambda (a b) (lambda (f) (f a b))))
(define pa (lambda (f) (f (lambda (a b) a))))
(define pb (lambda (f) (f (lambda (a b) b))))

(define x (pair 1 (+ 1 1)))    ; (+ 1 1)がすぐに実行され，1と2がxに保管される
(display (pa x))      ; => 1
(display (pb x))      ; => 2

ここで，paで取り出される値はそのまま記述し，pbで取り出される値は，その値を得るための手続きをlambdaを用いて記述します．

stream3.scm

(define y (pair 1 (lambda () (+ 1 1))))    ; 1と手続き(+ 1 1)がyに保管される
(display (pa y))      ; => 1
(display ((pb y)))    ; この時点で(+ 1 1)が実行され2が表示される

この方法を用いて，nから1ずつ値が増えるリストを，2番目の要素からはその都度計算する手続きmake-linearを定義します．

stream4.scm

(define make-linear
  (lambda (n)
    (pair n (lambda () (make-linear (+ n 1))))))

(define linear (make-linear 10))

作り出されたリストは，最初の要素はそのままpaで取り出せますが，2番目の要素からは，pbで取り出したlambdaの手続きをあらためて実行させながら値を得ることになります．これを繰り返すことで，取り出せる要素の数は（理屈の上では）無限大となります．

stream5.scm

(display (pa linear))    ; => 10
(display (pa ((pb linear))))    ; => 11
(display (pa ((pb ((pb linear))))))    ;=> 12
(display (pa ((pb ((pb ((pb linear))))))))    ;=> 13

上記の各要素の値を取り出す方法を手続き化して，リストの1番目からn番目の値を表示する手続きdisp-listが定義できます．

stream6.scm

(define disp-list
  (lambda (s n)
    (cond ((= n 0))
          (else
           (display (pa s))
           (display " ")
           (disp-list ((pb s)) (- n 1))))))

(disp-list linear 10)    ; => 10 11 12 13 14 15 16 17 18 19 
(disp-list linear 30)    ; => 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

以上の考え方を用いて，フィボナッチ数列を求めてみましょう．a←b，b←a+bと値が増えていくリストを，2番目からはその都度計算する手続きmake-fibを定義します．この手続きを用いて作り出したリストは，上記のdisp-listを用いて，フィボナッチ数を必要な数だけ表示させることができます．

stream7.scm

(define make-fib
  (lambda (a b)
    (pair a (lambda () (make-fib b (+ a b))))))

(define fib (make-fib 0 1))
(disp-list fib 10)    ; => 0 1 1 2 3 5 8 13 21 34 
(disp-list fib 30)    ; => 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229

このように，リストの長さが固定されておらず，必要に応じて次々と連なってくるデータ構造をストリーム（stream）と呼びます．

##条件分岐
condやelseを用いた記述では，一部の要素のみが実行され，したがって，これらは手続きの名前ではなく，特別な処理を行うための記号であると述べました．ですが，lambdaを用いた記述は，その記述の時点では実行されず，手続きとして呼び出された時にあらためて実行されることも述べました．この考え方を利用して，条件分岐を手続きとして実現できないか考えてみましょう．

まず，基本的な条件分岐は，条件式が成り立つか成り立たないかの結果によって，ふたつの処理のうちのいずれかを実行するというものです．あらためて注意したいのは，一方が実行された時には，もう一方は実行されないということです．この方針に基づいて，lambdaを用いたふたつの手続きを値として与えると，必ずどちらか一方の手続きしか実行しない，exec1とexec2のふたつの手続きを定義します．

lambda1.scm

(define exec1 (lambda (x y) (x)))
(define exec2 (lambda (x y) (y)))

(exec1 (lambda () (display "exec1"))
       (lambda () (display "exec2")))    ; => exec1
(exec2 (lambda () (display "exec1"))
       (lambda () (display "exec2")))    ; => exec2

ここで，大小関係を表す手続き= < >を，#tではなくexec1，#fではなくexec2を返すeqn ltn gtnに変換します．

lambda2.scm

(define bdef
  (lambda (p t f)
    (lambda (a b) (cond ((p a b) t) (else f)))))
(define eqn (bdef = exec1 exec2))
(define lth (bdef < exec1 exec2))
(define gtn (bdef > exec1 exec2))

これらを利用すれば，condやelseを使用することなく，新しく定義した手続きのみで条件分岐を表現することができます．

((gtn 20 30)
 (lambda () (display "20 > 30" ))
 (lambda () (display "20 <= 30")))
; => "20 <= 30"

例として，フィボナッチ数を求める関数を定義・実行してみましょう．

lambda4.scm

(define fib
  (lambda (x f1 f2)
    ((eqn x 1)
     (lambda () f1)
     (lambda () (fib (- x 1) f2 (+ f1 f2))))))

(display (fib 50 0 1))    ; => 7778742049

lambdaによる手続きを用いて条件分岐を表現する考え方は，Schemeやプログラミング固有のものではなく，ラムダ計算（lambda calculus）と呼ばれる計算体系に基づくものであり，多くのプログラミング言語に大きな影響を与えています．

#備考

##登場したSchemeの記号・手続き・値

記号：( ) 空白 cond else define lambda " ;
手続き・値：+ - * / = < > #t #f display

##変更履歴

2020-07-29：スライドモードを導入
2020-07-26：基本的な記述方法の部分を簡素化，その他字句修正
2020-07-23：ラムダ計算による条件分岐の実装例を追加
2020-07-22：遅延評価の応用例を追加（後にストリームの例として変更）
2020-07-21：『関数』を『手続き』等に置き換え，special formを区別する説明を追加
2020-07-20：FizzBuzz問題追加，タイトルより（仮題）削除
2020-07-19：初版公開