Scheme演習 第1回

品川 嘉久, 浅井 健一, 萩谷 昌己, 西澤 弘毅, 原 謙治
[Table of Contents] [Index] [携帯版]

Scheme 演習の概要

関数型言語 LISP のひとつの方言である Scheme を使って、種々のプログラミングを行なう。再帰関数、高階関数、リスト、抽象データ型、環境モデル、状態等を学習し、最終的には Scheme で Scheme 自身のインタプリタを作成することを目指す

授業内容は、資料の解説である。出席はとらないので必ずしも出席する必要は無い。遅刻、途中退室してもかまわない。また、このホームページ上でも資料のダウンロードができる。

http://www-ui.is.s.u-tokyo.ac.jp/~hara2001/scheme/


Gambit Scheme の使い方
起動
~rr36125/gambc30/gsi/gsi
終了
(exit)。または、ctrl-D
割り込み
ctrl-C
デバッグ
,? と入力すると help が出る。

実行例

> は gsi のプロンプトである。式を入力して Enter を押すと、評価(式を計算すること)の結果をすぐ下に出力する。から行末まではコメントとして無視される。

% ~shagiya/gambc30/gsi/gsi
Gambit Version 3.0
>1
1
> 123 ; 456
123
> (exit)
%

Scheme 処理系
Gambit Scheme
R4RS 準拠。Windows, Mac 等用のものもある。コンパイラもある。
scm
R4RS 準拠。Windows, Mac 等でも動く。
xscheme
古い。が、古い 98 でも動く。
elk
Mutual tail recursion をサポートしていない。
MIT-Scheme
R4RS 準拠。MIT で作っている Scheme。
chezscheme
R4RS 準拠。売り物。速い。強力なコンパイラがある。Petite Chez Schemeはフリー(Windows, linux他)
http://www.scheme.com/
Gauche
ライブラリが豊富
http://www.shiro.dreamhost.com/scheme/gauche/index-j.html
STk
schemeでGUI作成可能
http://kaolin.unice.fr/STk/

Scheme の式 (expression)

Scheme の式は次の4つからなる。

数字等
数字(123 など)、真偽値(#t#f)、 文字列("hello" など)。
変数
+=sinfac など(関数も変数の一 種であるが、詳しくは次回)。
関数適用
(+ 1 2)(fac 3) など。
シンタックス形式
if 文、cond 文、define 文、 lambda 文など。

関数(プロシージャ)

関数適用はすべて (関数 引数 ...) という形をしている。関数と引数の間や、複数の引数間は、スペースで区切るが、途中に長いスペースや改行を挿入することができる(全角スペースは不可)。また、任意個の引数を取れる関数もある。


arithmetic operator
  • (+ x1 ...), (- x1 ...), (* x1 ...), (/ x1 ...)
  • (max x1 ...), (min x1 ...), (abs x), (exp x), (sin x)
> (+ 1 2.3)
3.3
> (- 1 2 3 4 5)
-13
> (+ (* 3 (+ (* 2 4) (+ 3 5)))
     (+ (- 10 7) 6))
57
> (abs (- 5 10))  ; 絶対値
5

boolean operator

andor は第一引数から順に評価していき、途中で結果が確定したらそれ以降の引数は評価しない。実はandor はシンタックス形式であるが、関数とみなしても特に問題は無い。

  • (not obj), (and obj1 ...), (or obj1 ...)
> (not #t)
#f
> (and #t #t #f)
#f
> (and #t #f aaa)  ; ここでは aaa を評価するとエラー
#f
> (or #f #t #f)
#t
> (or #t #f aaa)  ; ここでは aaa を評価するとエラー
#t
> (and (or #t #f) (not #f))
#t

述語(boolean を返す関数)

述語の名前は末尾を?とする場合が多い。

  • (number? obj), (real? obj), (integer? obj), (boolean? obj)
  • (zero? x), (odd? x), (even? x), (positive? x), (negative? x)
  • (= x1 ...), (< x1 ...), (> x1 ...), (<= x1 ...), (>= x1 ...)
> (integer? (- 1.5 0.5))
#t
> (odd? (/ 6 2))
#t
> (&lt; 1 3 2)
#f
> (and #t (= 3 3) (&lt; 1 2 4))
#t

シンタックス形式
if
(if <test> <then-expression> <else-expression>)
      
<test> 部をまず評価し、その値が #t なら<then-expression> 部のみを評価して 結果を返す。#f なら<else-expression> 部のみを評価して結果を返す。
> (if (= 1 5) (+ 2 4) (- 2 3))
-1
	
cond
(cond (<test1> <expression1>)
      (<test2> <expression2>)
      ...
      (else <expression>))
      
<test> 部を上から順に評価していき、最初に #t であった節(なければ最後の else 節)の <expression> を評価して返す。最後の else 節は省略可能。
define
2形式ある。
変数を定義するときは
(define <name> <expression>)
関数を定義するときは
(define (<name> <parameter1> ...) <body> ...)
<parameter> 部はなくてもよい。また、<body> は複数あっても良い。その場合には、 前から順に評価していき、最後の<body>の値が返り値となるような関数になる。

> pi       ; まだ定義されていない変数なのでエラー
*** ERROR -- Unbound variable: pi
1> ,d      ; エラー後にプロンプトを直す方法
> (define pi 3.14159)          ; 変数を定義
> pi                           ; 変数を評価(参照と呼ぶ)するとその値を得る
3.14159
> (define radius 10)
> (define circumference (* 2 pi radius))
> circumference
62.8318
> (define (square x) (* x x))  ; 関数を定義
> (square 21)                  ; 関数の適用
441
> (square (+ 2 5))
49
> (define (sum-of-squares x y) ; 関数の定義内で他の関数を使用
    (+ (square x) (square y)))
> (sum-of-squares 3 4)
25
> (define (f a) (sum-of-squares (+ a 1) (* a 2)))
> (f 5)
136
	

ブロック構造

前節のプログラムでは、関数 sum-of-squares が、その内部で関数 squareを使用している。

ここでsquare を、sum-of-squares の中でのみ使用したいとする。そのようなときは関数sum-of-squares の定義内で、最後以外の<body> の場所で square を定義すればよい。

(define (sum-of-squares x y)
  (define (square z) (* z z))
  (+ (square x) (square y)))

このように定義すれば、他の場所でこのsquareを使用することはできなくなる。

プログラムが大規模になってくると、関数の名前が他のところで使われていたりする可能性があるので、補助関数を外から見える形で定義するのは好ましくない。

逆にいうと、補助関数は使われるところのみで局所的に定義されていることが望ましい。

また、この例ではしていないことだが、内部で定義された square のような関数は、包んでいる関数定義の引数(ここでは xy)を直接参照できる。


文字列

標準出力する関数は、返り値は決められていない。標準出力はあくまでも副作用である。したがって、返り値が捨てられてしまうような場所で使用されても、正しく出力される。

  • (write obj)
  • (display obj)
> (display "hello world")
hello world> (display "hello\nworld\n")
hello
world
> (write (+ 1 2))
3> (+ 1 (write (+ 1 2)))
3*** ERROR IN (stdin)@43.1 -- NUMBER expected
(+ 1 '#&lt;void>)
1> ,d
> (define (f x)
     (write x)
     (display "+1=")
     (+ x 1))
> (f 5)
5+1=6
>

ファイルのロード

ファイルの読み込みは、(load "filename.scm")。拡張子 scm は省略可能。

(define (square x) (* x x))
(define (sum-of-squares x y)
  (+ (square x) (square y)))

ファイル 1.scm の内容が上のとき、宣言した変数や関数を下のように使える。

> (load "1.scm")
"/home/rr16017/s/1.scm"
> (sum-of-squares 3 4)
25

Bibliography
1
Abelson, H., and G. J. Sussman with J. Sussman Structure and Interpretation of Computer Programs, 2nd edition, Cambridge: MIT Press (1996).
2
Kelsey, R., Clinger, W., and Rees, J. (editors) ``Revised Report on the Algorithmic Language Scheme", 1998.

レポート課題1

重要:レポートには必ずプログラムの説明と実行例をのせること。


問1

何も変数や関数を宣言していない最初の状態から始めた場合の、次の一連の入力列に対する Scheme の出力(またはエラー)を予測せよ。ただし、エラーが起こった場合は,dでプロンプトを戻してから続きをすること。次に、実際に確かめて、わかる範囲で解説せよ。

> (* (+ 2 4) (- 1 4 6))
> (/ 6 4)
> (/ 6.0 4.0)
> (+)
> (*)
> (and)
> (or)
> (define b (+ a 1))
> (define a 3)
> (define b (+ a 1))
> (define c (+ c 1))
> (= (+ a b) (* a b))
> (cond ((and (= a b) (&lt; a b)) "1st")
        ((or  (= a b) (&lt; a b)) "2nd")
        (else                  "3rd"))
> (define (f a)
    (define b (+ a 10))
    b)
> (f b)
> b
> (define (times4 n) (times2 (times2 n)))
> (define (times2 n) (+ n n))
> (times4 5)

問2

5つの整数を引数として受け取り、そのうち偶数が奇数より多い場合は#tを返し、奇数が偶数より多い場合は#fを返す述語even>odd?を定義せよ。当然、いろいろな定義の仕方がある。

> (even>odd? 1 2 3 4 5)
#f
> (even>odd? 2 -3 4 5 -6)
#t


This page is generated by mtd2html.