M.Hiroi's Home Page

Functional Programming

Scheme Programming

[ Home | Functional ]

WHAT'S NEW

CONTENTS


お気楽 Scheme プログラミング入門

CONTENTS

●入門編

●応用編

●思考ルーチン編

●パズルの解法

●micro Scheme 編

●言語処理系編

●オブジェクト指向編


はじめに

Scheme は 1975 年に Gerald J.Sussman 氏と Guy L. Steele Jr. 氏によって作成された Lisp の方言の一つです。伝統的な Lisp は「動的スコープ (ダイナミックスコープ, dynamic scope)」ですが、Scheme は「静的スコープ (レキシカルスコープ, lexical scope)」を採用しています。その後、Common Lisp でもレキシカルスコープが採用されました。

Scheme の言語仕様は「Revisedn Report on the Algorithmic Language Scheme (RnRS)」と呼ばれていて、IEEE によって公式に定められています。n には数字が入ります。M.Hiroi の知識は R5RS (改訂 5 版, 1998 年) で止まっています。当時の Scheme は、言語仕様がコンパクトにまとまっていて、R5RS でも 50 ページ程度の分量しかありません。

ところが、その後に成立した R6RS (2006 年) では、多くの機能を盛り込んだため言語仕様が大きくなってしまいました。Scheme - Wikipedia によると、R6RS の文章量は R5RS の約 3 倍になるそうです。これに不満を持つ人たちも少なからずいて、なかには独自の規格 (ERR5RS) を検討する人たちもいるようです。

このため、Scheme の言語仕様を大規模バージョン (R7RS-large) と、そのサブセットとなる小さな言語仕様 (R7RS-small) の二つに分けることが 2009 年に発表されました。R7RS-large はまだ制定されていませんが、R7RS-small は 2013 年に制定されました。M.Hiroi はシンプルなプログラミング言語が好みなので、R7RS-small で Scheme を勉強 (再入門) してみようと思っております。M.Hiroi のサビついた腕をどこまでブラッシュアップできるかわかりませんが、興味のある方はお付き合いくださいませ。

●Scheme と Common Lisp の違い

Scheme は関数を first class object として扱うことができます。参考文献 [2] では、first class object を「一等値」と訳していますが、ようするに、プログラミング言語で計算対象となるデータ (値) のことです。関数型言語の場合、関数は他のデータと同等に扱うことができます。つまり、関数を変数に代入したり、関数を引数として渡すことができます。また、関数を値として返すこともできます。

ところが、Common Lisp の関数は完全な first class object ではありません。次の例を見てください。

* (setq func (lambda (x y) (+ x y)))

#<FUNCTION (LAMBDA (X Y)) {100326EA3B}>
* (funcall func 1 2)

3

上の例は SBCL で実行した場合です。ラムダ (lambda) 式は無名の関数を返します。Lisp / Scheme では、それを変数 func に格納して呼び出すことができます。Common Lisp の場合、変数に格納された関数は (func 1 2) のように呼び出すことはできません。funcall や apply を使って呼び出します。これに対し、Scheme は (func 1 2) と呼び出すことができます。次の例を見てください。

gosh> (define func (lambda (x y) (+ x y)))
func
gosh> (func 1 2)
3

このように、Common Lisp よりも簡単に関数を取り扱うことができます。

それから、Scheme は「末尾再帰最適化」を行うことが言語仕様に明記されています。末尾再帰最適化が行われると、次に示すような関数呼び出しにおいて、スタックを消費せずに実行することができます。

gosh> (define foo (lambda () (foo)))
foo

gosh> (foo)
=> 無限ループになる

末尾再帰最適化が行われる場合、foo を評価すると無限ループになります。Common Lisp の場合、末尾再帰最適化は仕様に含まれてないので、最適化の実装は処理系に依存します。M.Hiroi が使っている SBCL は末尾再帰最適化をサポートしています。

また、「継続 (continuation)」を取り扱うことができるのも Scheme の大きな特徴の一つです。継続はプログラムの実行状態を保存しておいて、あとから実行を再開することができます。これは Common Lisp にはない強力な機能です。

●Gauche のダウンロード

Scheme には多数の処理系がありますが、このページでは Shiro Kawai さんが開発されている Gauche をメインに使いたいと思います。Gauche は次のページからダウンロードすることができます。

Windows の場合、バイナリインストーラーが用意されているので簡単です。Unix 系 OS の場合も、インストールスクリプトが用意されているので、それをダウンロードして実行するだけです。また、ソースからビルドすることも簡単にできます。詳細は上記ページをお読みくださいませ。

なお、Unix 系 OS で Gauche をそのまま使う場合、Gauche の REPL (対話モード) にはコマンドラインの編集やコマンド履歴をたどる機能がありません。この場合、rlwrap をインストールすると便利になります。

sudo apt install rlwrap

あとはシェルで rlwrap gosh を実行するだけです。簡単なプログラムであれば、これだけでもかなり便利になります。

●簡単なベンチマーク

Gauche はプログラムをバイトコードにコンパイルする処理系です。その実行速度ですが、拙作のページ Algorithms with Python 再帰定義 の「たらいまわし関数」を使って調べてみました。

リスト : たらいまわし関数 (tak.scm)

(define (tak x y z)
  (if (<= x y)
      z
      (tak (tak (- x 1) y z)
           (tak (- y 1) z x)
           (tak (- z 1) x y))))

それでは実行結果を示します。(tak 22 11 0) を計算しました。実行時間は (time (tak 22 11 0)) で計測できます。

gosh> (load "./tak.scm")
#t
gosh> (time (tak 22 11 0))
;(time (tak 22 11 0))
; real  25.551
; user  25.530
; sys    0.000
11
表 : tak(22, 11, 0) の結果
処理系
Python (ver 3.6.9)69.6
Lua (ver 5.3.3)37.2
Gauche (ver 0.9.9)25.5
Ruby (ver 2.5.1p57)25.4
ocamlc (ver 4.05.0)10.8
SBCL (ver 1.4.5)6.38
LuaJIT (var 2.1.0-β)4.02
SML/NJ (ver 110.98)2.66
Chez Scheme (ver 9.5)2.39
Julia (ver 1.3.0)2.02
SBCL (最適化)1.57
GCC -O2 (ver 7.4.0)1.23
ocamlopt (ver 4.05.0)0.97

ネイティブコードや JIT コンパイルする処理系にはかないませんが、バイトコードにコンパイルする Python, Lua よりも高速で、Ruby と同じくらいの速度になりました。Chez Scheme はプログラムをネイティブコードにコンパイルする処理系です。もともと商用の処理系だったのですが、2016 年にオープンソース化されました。Chez Scheme はとても速いですね。他にもいろいろな Scheme 処理系があるので、興味のある方は試してみてください。


Yet Another Scheme Problems


Scheme Junk Scripts

M.Hiroi が Scheme の勉強で書いたジャンクスクリプトです。


参考文献, URL

●参考文献

  1. R. Kent Dybvig (著), 村上雅章 (訳), 『プログラミング言語 SCHEME』, 株式会社ピアソン・エデュケーション, 2000
  2. Ravi Sethi (著), 神林靖 (訳), 『プログラミング言語の概念と構造』, アジソンウェスレイ, 1995

●参考 URL

  1. R7RS 日本語訳
  2. 紫藤貴文, 『もうひとつの Scheme 入門』, 紫藤のページ
  3. Dorai Sitaram (著), Nobuo Yamashita (訳), 『独習 Scheme 三週間』, WWW.SAMPOU.ORG

権利・免責事項など

『お気楽 Scheme プログラミング入門』と『Scheme Junk Scripts』の著作権は筆者「広井誠 (Makoto Hiroi)」が保持します。無断使用や無断転載は禁止いたします。お気楽 Scheme プログラミング入門と Scheme Junk Script で作成したプログラムはフリーソフトウェアとします。ご自由にお使いください。プログラムの改造や配布もご自由にどうぞ。その際は、出典を明記してくださるようお願いいたします。

ただし、これらのプログラムは無保証であり、使用したことにより生じた損害について、作者「広井誠 (Makoto Hiroi)」は一切の責任を負いません。また、これらのプログラムを販売することで利益を得るといった商行為は禁止いたします。

Copyright (C) 2006-2021 Makoto Hiroi
All rights reserved.

[ Home | Functional ]