基本的な計算のための scheme 備忘録

# scheme レジュメ

scheme 言語を3月に勉強しました。次にやるときに思い出すための覚え書です。
内容の重要性というよりは忘れそうだなと思うところを中心に採録。

## 環境

- 処理系
    - Gauche: version "0.9.10"

## S式

```scheme
(operator 引数1 引数2 引数3 ... 引数N)
```

Lisp 系言語を象徴する構文木をそのまま書き下ろしたような構文。

基本的なデータ構造(Common Lisp などではアトムという)あるいはリストが0個以上ネストしている式。

scheme には他の言語でいう関数である手続きの他に特殊形式とマクロがあるが、全てこのS式で記述される。

## 分岐

Scheme では条件分岐を行うために `if` と `cond` という2つの方法がある。

### `if`

`if` は基本的な条件分岐を行う式。形式は以下の通り。

```scheme
(if 条件式
    真の場合の式
    偽の場合の式)
```


```scheme
(if (> 5 3)
    (display "5は3より大きい")
    (display 'error))  ; => "5は3より大きい"

;; 2つ以上の式に分岐したい場合は begin を使う。
(if (> 5 3)
    (begin 
        (display "5は3より")
        (newline)
        (display "大きい")
    )
    (display 'error))  ; => "5は3より\n大きい"

```

### `cond`

`cond` は `if` よりも複数の条件を扱いやすい構文。書式は以下の通り。

```scheme
(cond
  (条件1 式1)
  (条件2 式2)
  ...
  (else  デフォルトの式))
```

例えば、数値の符号を判定する関数は以下のように書ける。

```scheme
(define (sign x)
  (cond
    ((> x 0) "正の数")
    ((< x 0) "負の数")
    (else "ゼロ")))

(sign 10)  ; => "正の数"
(sign -5)  ; => "負の数"
(sign 0)   ; => "ゼロ"
```

`cond` の場合、最初に真になった条件の式が評価され、その結果が返される。どの条件にも当てはまらなかった場合は `else` 節が実行される。


## 手続き

他の言語でいう関数にあたる。

scheme の手続きはファーストクラスオブジェクトであり、変数に束縛、手続きの引数にすること、手続きの返り値にすることができる。

手続きの呼び出し方は特殊形式、マクロと全く同じである。

### `define`

scheme は手続きと変数が同じオペレータで定義される。

```scheme
;; 変数に値を束縛する
(define 変数 値)

;; 手続きを定義する
(define (proc 引数1 引数2 ...) (S式))
```

scheme では変数に値が束縛されるように、手続きが束縛される。

```scheme
;; これは上記と同じ意味
(define proc
    (lambda (proc 引数1 引数2 ...) (S式))
```

### `lambda`

手続きを作る特殊形式。
```scheme
;; lambda 式のパターンは以下の通り
(lambda (引数1 引数2 ...)
  式1
  式2
  ...
  式N)

;; 例: 引数の2乗を返す手続き
(define square
  (lambda (x)
    (* x x)))

```

### `let`

内部スコープを作る。名前付き let で手続きの名前が作られるので再帰ができる。

```scheme
;; let 式のパターンは以下の通り
(let ((変数1 値1)
      (変数2 値2)
      ...)
  式1
  式2
  ...)

;; 例: 2つの変数の和を計算する
(let ((a 10)
      (b 20))
  (+ a b)) ; => 30

;; 名前付き let 式のパターン
(let 手続き名 ((変数1 値1)
      (変数2 値2)
      ...)
  式1
  式2
  ...)

;; 例： 10 数えるループ
(let loop ((i 0))  ; i を 0 から開始
  (if (< i 10)
    (begin
      (display i)  
      (loop (+ i 1))
      )
    (display "DONE\n"))
  ) ; => 0123456789DONE

```

let はマクロで定義することができる。

- 参照 
    - [syntax let](https://www.r6rs.org/final/html/r6rs/r6rs-Z-H-16.html)

## データ型

Lisp 系言語は一般的に動的型付け言語で、scheme も同様。
JavaScript や Python をやっていれば特に詰まるところは無いと思うので特徴的な部分を説明する。

### リスト

Lisp 系言語は一般的にリストによって作られる。
scheme のリストは `'()` で終わるペアの連鎖です。

ペアは `cons` 関数によって作られる。
`car` でリストの最初の要素を取得できる。
`cdr` でリストの残りの部分を取得できる。
`quote` はリストをデータとして扱うために、リストの評価を差し止めることができる。一般的に`'()`のように略記する。

```scheme
;; cons
(cons 1 '(2 3))  ; => (1 2 3)

;; car, cdr
(define my-list (cons 1 (cons 2 (cons 3 '()))))
(car my-list)  ; => 1
(cdr my-list)  ; => (2 3)


```

### 真偽値

真は`#t`で表し偽は`#f`。

C、JavaScript など偽以外も `0` や空文字列などを偽として扱う言語があるが、 scheme は偽でなければ真として扱う。

```scheme
(if 0
    (display "T")
    (display "F")
    ) ; => "T"
```

たとえば、手続きはこのように真として扱われる

```scheme
(if (lambda () #f)
    (display "T")
    (display "F")
    ) ; => "T"
```

## シンボル型

シンボルは Scheme における識別子で、データとして扱える不変の名前である。

```scheme
'hoge  ; シンボル hoge
'symbol-name  ; シンボル symbol-name

(eq? 'hello 'hello)  ; => #t （同じシンボル）
```

## 高階関数

関数型言語の華。いくつか説明する。

- `fold`
畳み込み演算。有名どころだと Haskell にもある。

```scheme
;; 畳み込み

;; 例: リストの総和を計算する
(fold + 0 '(1 2 3 4 5)) ; => 15

;; 畳み込みの方向に注意すること！
(fold cons '() '(1 2 3 4 5)) ; => (5 4 3 2 1)

;; 逆向き
(fold-right cons '() '(1 2 3 4 5)) ; (1 2 3 4 5)
```

- `map`
各要素に関数を適用して新しいリストを返す。最近の言語だとだいたいあるのではないか。
```scheme
(map (lambda (x) (* x 2)) '(1 2 3 4)) ; => (2 4 6 8)
```

- `filter`
条件に合う要素だけを抽出します。これも最近の言語だとだいたいあるのではないか。
```scheme
;; 例: 3より大きい数を抽出する
(filter (lambda (x) (> x 3)) '(1 2 3 4 5))
; => (4 5)
```

## マクロ

scheme のマクロにはオールドスタイルのマクロ `define-macro` と新しいマクロ `define-syntax`があり、新しいマクロは衛生的マクロという。
ここでは define-syntax のみを扱う。
```scheme
;; マクロ定義
;; 衛生的マクロの定義例
(define-syntax when
  (syntax-rules ()
    ((when test expr ...)
     (if test (begin expr ...)))))
     
;; 使用例
(when (> 5 3)
  (display "5は3より大きい"))

```

- 参照
    - [Scheme:マクロ:CommonLispとの比較](https://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3A%E3%83%9E%E3%82%AF%E3%83%AD%3ACommonLisp%E3%81%A8%E3%81%AE%E6%AF%94%E8%BC%83)

## 継続

継続は scheme の特徴の一つでファーストクラスオブジェクトです。
`The continuation represents an entire (default) future for the computation.`
- [R6RS 1.11 Continuations](https://www.r6rs.org/final/html/r6rs/r6rs-Z-H-4.html#node_sec_1.11)

とのこと。
理解しきれていないので省略します。

- 参照
    - [なんでも継続](https://practical-scheme.net/docs/cont-j.html)

## 終わりに

電卓代わりの用途について、これくらいあれば十分日常の計算ができるのではないかと思います。
一例として、ここまでの内容を使ってプロジェクトオイラーの問題を一問解いてみます。

```scheme
;;; https://projecteuler.net/minimal=2
;;; プロジェクトオイラーの第二問
;; <p>Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with $1$ and $2$, the first $10$ terms will be:
;; $$1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots$$</p>
;; <p>By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.</p>

;;; エントリーポイント
(define (main args)
  (print (fold + 0 (filter (lambda (x) (= 0 (remainder x 2))) (fib-list 4000000))))
  0)

;;; 実装
(define (fib-list size)
  (fib-iter 0 1 size))

(define (fib-iter a b size)
  (if (<= size a)
    '()
    (cons b
          (fib-iter b (+ a b) size))))
```


## Link

- [R6RS:翻訳:R6RS](https://practical-scheme.net/wiliki/wiliki.cgi?R6RS%3A%E7%BF%BB%E8%A8%B3%3AR6RS)
- [なんでも継続](https://practical-scheme.net/docs/cont-j.html)
- [Revised^6 Report on the Algorithmic Language Scheme](https://www.r6rs.org/final/html/r6rs/r6rs-Z-H-2.html)
    - [Appendix B Sample definitions for derived forms](https://www.r6rs.org/final/html/r6rs/r6rs-Z-H-16.html)