アルゴリズムとデータ構造演習 Schemeまとめ

このページは、http://hagi.is.s.u-tokyo.ac.jp/ade2008/1217.html をまとめたものです。

Schemeの入門については書いていませんので、Schemeを勉強したい方はリンクへどうぞ

Contents

Scheme全般に関して

コマンドまとめ

コマンド名

関数かシンタックスか

重要度

構文

内容

e.g.

使用例

備考

四則演算

+

関数

{*} {*} {*} {o} {o}

(+ a1 a2 a3 ...)

足し算 : a1+a2+a3+a4...

e.g.

(+ 1 2) -> 3
(+ 1 2 3 4 5 6 7 8 9) -> 45

-

関数

{*} {*} {*} {o} {o}

(- a1 a2 a3 ...)

引き算 : a1-a2-a3-a4...

e.g.

(- 5 2) -> 3
(- 1 2 3 4 5 6 7 8 9) -> -43

-

関数

{*} {*} {*} {o} {o}

(- a1)

マイナス : -a1

e.g.

(- 5) -> -5
c.f. (- 5 0) -> 5
c.f. (- 0 5) -> -5

単引数の場合、複数の引数をとる場合の、最初の引数を0にした場合になる。

*

関数

{*} {*} {*} {o} {o}

(* a1 a2 a3 ...)

掛け算 : a1*a2*a3*a4...

e.g.

(* 1 2) -> 2
(* 1 2 3 4 5 6 7 8 9) -> 362880

/

関数

{*} {*} {*} {o} {o}

(/ a1 a2 a3 ...)

割り算 : a1/a2/a3/a4...

e.g.

(/ 1 2) -> 1/2
(/ 3628800 1 2 3 4 5 6 7 8) -> 90

/

関数

{*} {*} {*} {o} {o}

(/ a1)

逆数 : 1/a1

e.g.

(/ 5) -> 1/5
c.f. (/ 5 1) -> 5
c.f. (/ 1 5) -> 1/5

単引数の場合、複数の引数をとる場合の、最初の引数を1にした場合になる。

組み込み述語

述語:ブール値を返す関数

zero?

関数

{*} {o} {o} {o} {o}

(zero? a1)

0かどうかを返す : a1==0

e.g.

(zero? (+ 1 -1)) -> #t
(zero? 0.00001) -> #f

null?

関数

{*} {*} {*} {o} {o}

(null? a1)

nullかどうかを返す : a1==「()」

e.g.

(null? ()) -> #t
(null? (cons () ())) -> #f
(null? '()) -> #t
(null? 0) -> #f
(null? '(())) -> #f

「null」(?がない)なる関数も存在するので注意

pair?

関数

{*} {o} {o} {o} {o}

(pair? a1)

pairかどうかを返す

e.g.

(pair? '(())) -> #t
(pair? ()) -> #f

boolean?

関数

{o} {o} {o} {o} {o}

(boolean? a1)

booleanかどうかを返す : a1==#f or a1==#t

e.g.

number?

関数

{o} {o} {o} {o} {o}

(number? a1)

numberかどうかを返す

e.g.

string?

関数

{o} {o} {o} {o} {o}

(string? a1)

stringかどうかを返す

e.g.

symbol?

関数

{*} {*} {o} {o} {o}

(symbol? a1)

symbolかどうかを返す。quoteとなんか関係があるかも

e.g.

(symbol? 'a) -> #t

eof-object?

関数

{*} {o} {o} {o} {o}

(eof-object? a1)

eof-objectかどうかを返す。

e.g.

readでCtrl+Dでも読み込むのかなぁ

2引数組み込み述語

=

関数

{*} {*} {*} {o} {o}

(= a1 a2 a3... )

数値?が等しいか返す : a1==a2==a3==...

e.g.

(= 1 1 1) -> #t
未稿

数値にしか適用できないっぽい

>とか>=とか

関数

{*} {*} {*} {o} {o}

(> a1 a2 a3...)

順序よく並んでいるかを返す? : a1 > a2 > a3 > ...っぽい

e.g.

(> 3 2 1) -> #t
(> 3 1 2) -> #f

eq?

関数

{*} {*} {*} {*} {*}

(eq? a1 a2 a3...)

等しいかどうか : a1==a2==a3

e.g.

(eq? 1 1 (+ 1 0)) -> #t
(eq? (list 1 2) (list 1 2)) -> #f

リストとかはポインタでやるので、厳しい判断となる。キャーeq?さん(ry

equal?

関数

{*} {*} {*} {*} {o}

(equal? a1 a2 a3...)

等しいかどうか : a1==a2==a3

e.g.

(equal? (list 1 2 3 4 5) (list 1 2 3 4 5)) -> #t

中身を見るっぽい。eq?より優しい判断

論理演算

not

関数

{*} {*} {*} {*} {o}

(not a1)

否定 : !a1

e.g.

(not #t) -> #f
(not 0) -> #f

なんか数字にも適用できてしまったが#fをかえすのか

論理演算マクロ

and

マクロ

{*} {*} {*} {*} {o}

(and a1 a2 a3...)

Cの&&に相当、#f以降は評価しない : a1 && a2 && a3 && ...

e.g.

(and #t #t #f hoge) -> #f

or

マクロ

{*} {*} {*} {*} {o}

(or a1 a2 a3...)

Cの| |に相当、#t以降は評価しない : a1 | | a2 | | a3 | | ...

e.g.

制御マクロ

if

マクロ

{*} {*} {*} {*} {*}

(if 式1 式2 [式3])

まず式1を評価し、返り値として#fでなければ式2を、#fなら式3をその次に実行し、もう一方は実行されない。式3は省略可能 : if(式1!=#f){式2}else{式3}

e.g.

(if 0 4 5) -> 4

cond

マクロ

{*} {*} {*} {*} {*}

(cond (式1 プログラム1) (式2 プログラム2)...[(else プログラムelse)] )

ifの入れ子。式1が#fなら式2を評価して...

e.g.

begin

マクロ

{*} {*} {o} {o} {o}

(begin プログラム1 プログラム2...)

プログラム1を評価して、プログラム2を評価して...最後のプログラムの返り値を全体の返り値として返す。

e.g.

(begin 1 2 3 4 5) -> 5

quote , '

マクロ

{*} {*} {*} {*} {*}

(quote 式) , '式

式そのものを返すらしい

e.g.

(eq? 'x 'x) -> #t
(define a 1) '(a) -> (a)

よくわからん。とりあえずシンボルを生成したりリストを簡単に作れるのは便利

代入と関数

let

マクロ

{*} {*} {*} {*} {o}

(let ((変数名1 式1) (変数名2 式2) ...) プログラム)

変数名1=式1,変数名2 式2...をしてプログラムを実行

e.g.

(let ((x 1))(let ((x 2))x)) -> 2

変数名の多重定義不可、変数のスコープはプログラムの中だけで、代入時には使用不可、関数の再帰不可

letrec

マクロ

{*} {*} {*} {*} {*}

(letrec ((変数名1 式1) (変数名2 式2) ...) プログラム)

letで再帰を可能にしたもの

e.g.

(letrec ((fact (lambda (n) (if (< n 1) 1 (* n (fact (- n 1))))))) (fact 4) ) ->24

let*

マクロ

{*} {*} {*} {*} {o}

(let* ((変数名1 式1) (変数名2 式2) ...) プログラム)

(let ((変数名1 式1)) (let ((変数名2 式2)) ... プログラム)...))に相当するもので、変数を代入時に使用することができるようになった

e.g.

(let* ((x 1)(y x)(x 2))(+ x y)) -> 3

スコープはあくまでプログラムの中

lambda

マクロ

{*} {*} {*} {*} {*}

(lambda (引数1 引数2 ...) プログラム)

関数を新しく作って返す

e.g.

(define f (lambda (x y) (x y a)))(define a 1)(f + 3) -> 4

プログラム中に未定義の値が表れてもかまいませんが、実行時には定義されていないといけません

define

マクロ

{*} {*} {*} {*} {*}

(define 変数名 式)

(define ...)のあるレベルのスコープの変数を宣言、代入

e.g.

(define a 1)a -> 1

これ自体は値を返さず、lambdaやlet,defineの中で使うと、その中でだけ使える変数が作れる

define

マクロ

{*} {*} {*} {*} {*}

(define (関数名 引数1 引数2 ...) プログラム)

(define 関数名 (lambda (引数1 引数2 ...) プログラム))の略記、関数を分かりやすく宣言できる

e.g.

(define (square x) (* x x))

set!

マクロ

{*} {*} {*} {*} {*}

(set! 変数名 式)

すでに存在する変数に代入

e.g.

(define a 1)(set! a 2)a -> 1
(define a 1)(define (func) (set! a 2) a)(func)(display a)->2 2
c.f. (define a 1)(define (func) (define a 2) a)(func)(display a)->2 1

defineにきわめてよく似ているが、微妙に違う。これとdefineを乱用することで手続き型と変わらないプログラミングを楽しめる(ぉ

while

マクロ

{o} {o} {o} {o} {o}

(while 式 プログラム)

式が#fになるまで繰り返す

e.g.

基本使用禁止、再帰を使おう(<-そんなことを言っているからスタックがたりなくなる

リスト操作

cons

関数

{*} {*} {*} {*} {*}

(cons a b)

(a . b)のペアを新しく作って返す

e.g.

(cons 1 (cons 2 3))->(1 2 . 3)
c.f. (eq? (cons 1 2) (cons 1 2))->#f
c.f.(equal? (cons 1 2) '(1 . 2))->#t

list

関数

{*} {*} {*} {*} {*}

(list a1 a2 a3 ... an)

(a1 a2 a3 ... an)のリストを新しく作って返す、(cons a1 (cons a2 ...(cons an '())...))と同じ

e.g.

(list 1 2 3)->(1 2 3)

上と同じく、eq?でオブジェクトが同一か、equal?で、全ての要素が同一化を調べられる

car

関数

{*} {*} {*} {*} {*}

(car pair)

pairの1番目の要素を取り出す。

e.g.

(car (cons 1 2)) -> 1
(car (list 1 2 3))->1

リストを与えれば、最初の要素を返す関数と見ることができます。

set-car!

関数

{*} {*} {*} {*} {o}

(set-car! pair a)

pairの1番目の要素をaに変更する。

e.g.

(define a (cons 1 2))a(set-car! a 3)a -> (1 . 2) (3 . 2)

いわゆる破壊的な操作です。データベースを扱うときなど便利

cdr

関数

{*} {*} {*} {*} {*}

(cdr pair)

pairの2番目の要素を取り出す。

e.g.

(cdr (cons 1 2)) -> 2
(cdr (list 1 2 3))->(2 3)

リストを与えれば、最初の要素を取り除いたリストを返す関数と見ることができます。

set-cdr!

関数

{*} {*} {*} {*} {o}

(set-cdr! pair a)

pairの2番目の要素をaに変更する。

e.g.

(define a (cons 1 2))a(set-cdr! a a)a -> (1 . 2) (1 . #0#)

循環リストなども作れます

cadr

関数

{*} {*} {o} {o} {o}

(cdr list)

listの2番目の要素を取り出す。(car (cdr list))の略記

e.g.

(cadr (list 1 2 3)) -> 2

最初がaなので、要素が取り出されるわけです。

cddr

関数

{*} {*} {o} {o} {o}

(cdr list)

listの3番目以降のリストを取り出す。(cdr (cdr list))の略記

e.g.

(cddr (list 1 2 3)) -> (3)

最初がdなので、リストが取り出されるわけです。他にもcaddrやcdadr,cddddrなどなどたくさんあります。

リスト上の関数

length

関数

{*} {*} {o} {o} {o}

(length list)

listの長さを返す

e.g.

(length (list 1 2 3 4)) -> 4

map

関数

{*} {*} {*} {*} {o}

(map 関数 list)

list上に関数をそれぞれ適用して、結果の関数を新しく作って返す

e.g.

(map square (list 1 2 3 4)) -> (1 4 9 16)

append

関数

{*} {*} {o} {o} {o}

(append list1 list2)

listをくっつけて、結果の関数を新しく作って返す

e.g.

(append (list 1 2 3) (list 3 4 5)) -> (1 2 3 3 4 5)

append!とかもあるらしい

reverse

関数

{*} {*} {o} {o} {o}

(reverse list)

listをひっくり返して、結果の関数を新しく作って返す

e.g.

(reverse (list 1 2 3 4))->(4 3 2 1)

reverse!とかもあるらしい

assoc

関数

{*} {*} {*} {*} {o}

(assoc 連想リスト)

連想リストから、最初に見つかったkeyのペアを返す。一致しなかった場合は#fを返す

e.g.

(assoc 2 '((1 . "a") (2 . "b") (3 . "c") (2 . "B")))->(2 . "b")

keyを探すときはequal?を使う

assq

関数

{*} {o} {o} {o} {o}

(assoc 連想リスト)

連想リストから、最初に見つかったkeyのペアを返す。一致しなかった場合は#fを返す

e.g.

keyを探すときはeq?を使う

入出力

display

関数

{*} {*} {*} {*} {*}

(display a1)

a1を表示する

e.g.

(display 1) -> 何も返さず、1を改行なしで表示
(display "Hello world!\n") -> Hello world!\n
(display +) -> #<primitive-procedure +>と表示

改行されないので、\nをつけよう
スクリプト実行時に非常に重宝する

write

関数

{o} {o} {o} {o} {o}

(write a1)

Schemeの「式を」表示

e.g.

(write "aa") -> 「"aa"」と表示

「""」も表示できる。

newline

関数

{o} {o} {o} {o} {o}

(newline)

改行を表示

e.g.

「""」も表示できる。

read

関数

{o} {o} {o} {o} {o}

(read)

Schemeの「式を」読み込む

e.g.

式を読み込むので、構文解析やquoteとかの処理までやってくれます。

load

関数

{*} {*} {*} {*} {o}

(load filename)

ファイルにあるSchemeの式をロードする

e.g.

(load "lib.scm")

with-input-from-file

関数

{*} {*} {o} {o} {o}

(with-input-from-file filename 関数(引数なし))

ファイルをオープンして、それに対して関数の処理をする。

e.g.

(with-input-from-file "somefile.scm"(lambda ()(define (re-loop vars)(let ((ans (read)))(if (eof-object? ans)(end)(re-loop vars))))(re-loop vars)))

その他

trace

関数

{*} {*} {*} {*} {o}

(trace 関数)

以降指定された関数をトレースするようになる

e.g.

(define (fact n)(if (< n 1)1(* n (fact (- n 1)))))(trace fact)(fact 4) -> (再帰呼び出しの様子)

末尾再帰は表示されないので、本当にスタックがつまれているか確認できる

eval

関数

{*} {o} {o} {o} {o}

(eval '式 環境)

式を評価する

e.g.

(eval '(+ 1 2) (interaction-environment)) -> 3

作る対象です。使わないように^^;

環境

要するに、スコープがあることと、他の言語同様に、オブジェクトとして関数やリストなどが存在しているということ

各オブジェクトの内部は独立したスコープを持つ。

(define a (list 1 2))
(define b (list 1 2))
(define c a)
(eq? a b)               ;=>#f
(eq? a c)               ;=>#t
(equal? a b)    ;=>#t
(define d (lambda (x) x))
(define e (lambda (x) x))
(eq? d e)               ;=>#t

(define (testl)
        (define a 1)
        (define (test)
                (set! a (+ a 1))
                a
        )
        test
)

(define t1 (testl))
(t1)                    ;=>2
(t1)                    ;=>3
(define t2 (testl))
(t2)                    ;=>2
(t1)                    ;=>4
(t2)                    ;=>3
((testl))               ;=>2
((testl))               ;=>2

環境

変数の名前と変数の中身の対応全体のこと

フレーム

各スコープの中での環境

静的スコープ

(define (f x) (+ x a))
(define a 2)
(let ((a 1)) (f 0)) ;=>Schemeでは2,ELISPでは1がかえるらしい

関数の中で現れた変数に対し、その関数が定義されたスコープでその変数を評価しようとする場合を、静的スコープ(Schemeなど)、関数が適用されたスコープで評価しようとする場合を動的スコープ(ELISPなど)という。

tips

高階関数

(define (add f x)
  (lambda (y) (+ (f y) x)))
((add square 1) 3)

このように、関数を引数にとって、関数を返す関数が作れます。

リストと式

以下は全て同じ

(+ 1 2)
(+ . (1 . (2 . ())))
(+ . (1 2))
(+ 1 . (2))

関数によるクラスの作成

(define (myclass initvars)
        (define vars initvars)
        (define (printvars)
                (display vars)
        )
        (define (setvars newvars)
                (set! vars newvars)
        )
        (define (getvars)
                vars
        )
        (define (initiate)
                (printvars)
        )
        (define (selectmode mode)
                (cond
                        ((equal? mode 'setvars) setvars)
                        ((equal? mode 'getvars) getvars)
                        ;(else エラーを起こす)
                )
        )
        (begin
                (initiate)
                selectmode
        )
)
(define i1 (myclass 1))
(define i2 (myclass 2))
((i1 'setvars) 3)
(display ((i1 'getvars)))
(display ((i2 'getvars)))

これは以下のようなJavaのclassにおおよそ対応する。

   1 class myclass{
   2         private int vars;
   3         public myclass(int initvars){
   4                 vars=initvars;
   5                 printvars();
   6         }
   7         private void printvars(){
   8                 System.out.println(vars);
   9         }
  10         public void setvars(int newvars){
  11                 vars=newvars;
  12         }
  13         public int getvars(){
  14                 return vars;
  15         }
  16 }
  17 
  18 public class mainclass{
  19         public static void main(String args[]){
  20                 myclass i1=new myclass(1);
  21                 myclass i2=new myclass(2);
  22                 i1.setvars(3);
  23                 System.out.println(i1.getvars());
  24                 System.out.println(i2.getvars());
  25         }
  26 }

実行の仕方まとめ

guileを起動

guile

guileを終了

(exit)

ソース読み込み

guile -l hoge.scm

(load "lib.scm")

ソースをそのまま実行

guile -s test.scm

guileでは矢印キーが効かないので注意(情報棟の端末以外で一見効いてしまうように見えてしまう現象があるので、注意)

リンク

http://hagi.is.s.u-tokyo.ac.jp/ade2008/1217.html
http://hagi.is.s.u-tokyo.ac.jp/ade2008/guile.html
http://ja.wikipedia.org/wiki/Scheme
http://people.csail.mit.edu/jaffer/r5rsj_toc.html {*} R5RS日本語版 かなり詳しい
http://www.sampou.org/ {*} {*} {*} 「独習 Scheme 三週間」がすごく詳しい

アルゴリズムとデータ構造演習/Schemeまとめ (last edited 2009-02-21 08:27:33 by xyx)