Scheme

Scheme

• http://mitpress.mit.edu/sicp/

 PLT Scheme

• http://plt-scheme.org/
• DrScheme

プログラムの要素

 式(expression)

• 式(expression)を入力すると解釈系は応答してその式を評価した(evaluating)結果を表示する

整数を与えると、応答を印字

> 486
486

手続き(+や*など)と組み合わせて合成式とし、手続きの作用を表現

> (+ 137 349)
486
> (* 5 99)
495

組合せ、演算子、被演算子、引数

• 式の並びを括弧で囲んで手続きの作用を表現する式を組合せ(combinations)という
• 左端の要素を演算子(operator)、他の要素を被演算子(operands)という
• 組合せの値は、演算子が指定する手続きを、被演算子の値である引数(arguments)に作用させて得る

前置記法

• 演算子を被演算子の左に置く書き方を前置記法(prefix noations)という

利点

• 任意の引数をとる手続きを許す

> (+ 21 35 12 7)
75

• 組合せを入れ子にする(nested)ことを許す

> (+ (* 3 5) (- 10 6))
19

 名前と環境

• オブジェクトを値(value)とする変数(variable)を識別するのものが名前
• defineで名前付け

> (define size 2)
> size
2

 組合せと評価

1. 組合せの部分式を評価する
2. 最左部分式の値である手続き(演算子)を、残りの部分式の値である引数(被演算子)に作用させる

特殊形式(special forms)

• define は、2つの値に作用させるのではなく、対応づけるだけのため、(define x 3) は組合せではない
• このような一般評価規則の例外を特殊形式(special forms)という

• http://typea.info/blg/glob/2010/03/_3.html

 合成手続き

• 手続き定義(procedure definetions) により、合成演算に名前を対応付け、一体として指すことができる

二乗を表すsquare という合成手続き(compund procedure)を作る

> (define (square x) (* x x))
> (square 2)
4

 条件式と述語

場合分け(case analysis)

• cond 場合分けを記述する特殊形式

> (define (abs2 x)
   (cond ((> x 0) x)
         ((= x 0) 0)
         ((< x 0) (- x))))
> (abs2 -19)
19
> (abs2 0)
0

• 特殊記号 else を利用できる

> (define (abs3 x) 
    (cond ((< x 0) (- x))
          (else x)))

• 場合分けが2つの場合、特殊形式の if を利用できる

> (define (abs4 x)
    (if (< x 0)
        (- x)
        x))

論理合成演算

• 基本的述語以外に、以下のような論理合成演算が利用できる

手続きと変数

 変数と有効範囲

束縛変数(bound variable)

• 手続き定義のなかで、仮パラメータはどんな名前でもかまわないし、名前をすべて変更しても手続きの意味は変わらないという意味で、手続き定義は、仮パラメータを束縛している(bind)。そういう名前を束縛変数(bound variable)という。変数が束縛されていなければ、自由である(free)。

有効範囲(Scope)

• 名前が束縛されている式の範囲

ブロック構造(block structure)

• 定義の入れ子。単純な名前保護の機構。
• 手続きの定義の中で別の定義を行うことができる。

(define (sqrt2 x) 
  (define (average x y) (/ (+ x y) 2))
  (define (square x) (* x x))
  (define (good-enough? guess x)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess x)
    (average guess (/ x guess)))
  (define (sqrt-itr guess x) 
    (if (good-enough? guess x)
        guess
        (sqrt-itr (improve guess x)
                  x)))
  (sqrt-itr 1.0 x))

静的有効範囲(lexicacl scoping)

• 上記例で、x は、sqrt2 の定義に束縛されている。なので、その内側の関数は、x の有効範囲内にあるため明示的に渡さなくてもよいので、自由変数にできる。こうしたやり方を静的有効範囲(lexical scoping) という。

(define (sqrt2 x) 
  (define (average a b) (/ (+ a b) 2))
  (define (good-enough? guess)
    (< (abs (- (* guess guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-itr guess) 
    (if (good-enough? guess)
        guess
        (sqrt-itr (improve guess))))
  (sqrt-itr 1.0))