Gauche インストール

$ brew install gauche
$ brew install rlwrap

インストールの確認

$ gosh -V
Gauche scheme shell, version 0.9.12 [utf-8,pthreads], x86_64-apple-darwin21.6.0
$ gosh
gosh>

手続き呼び出し

+ は加算の手続き。schemeに演算子というものはない。

gosh> (+ 1 2)
3

sheme では全ては手続き。「(define <変数名> <式>)」式の値を変数に格納しておくことができる

gosh> (define sqrt2 (sqrt 2))
sqrt2
gosh> sqrt2
1.4142135623730951

schemeの世界ではこれを「<変数名>を<式>の値に束縛する」といういう。bindを直訳したもの。

手続きの定義

gosh> (define (pythagoras x y) (sqrt (+ (* x x) (/ y y))))
pythagoras

定義した手続きは、組み込みの手続きと同様「(手続き <引数> ...)」で呼び出すことができる

gosh> (pythagoras 3 4)
5

Gaucheのインタラクティブモードを終了する

gosh> (exit)

sekitats

Racket (処理系) のインストール

DrRacket というIDEも一緒についてくる
SICP Collection のインストール

$ brew install racket --cask
$ raco pkg install sicp

DrRacket の起動

$ drracket

DrRacketが起動したら、ウィンドウの左下 No Language Chosen から Determine language from source を選択する。(R5RSは使用しない)

#lang racket
(+ 1 2)

Command + R で実行 > 結果が出力される

参考: 【2018年3月】SICPを始めるためのScheme処理系準備メモ

FizzBuzz

(define (check-num x)
  (cond [(= (modulo x 15) 0) 'FizzBuzz]
        [(= (modulo x 5) 0) 'Buzz]
        [(= (modulo x 3) 0) 'Fizz]
        [else x]))

(define (fizz-buzz check max)
  (map check (iota max 1)))

(fizz-buzz check-num 100)

sekitats

cons の第２引数にリストでないものを与える。これをドット対と呼ばれる。最後が空リストで終わっていない場合はドットリストと呼ばれる。ドットリストに対して最後が空リストで終わっているリストを正式なリストと呼ぶ

(cons 1 2)
(1 . 2)
(cons 1 (cons 2 3))
(1 2 . 3)

手続き null? は引数が空リストであれば真値をそうでなければ偽値を返す

(null? '(1 2 3))
#f
(null? '())
#t

手続き pair? は引数が空でないリストであれば真値をそうでなければ偽値を返す

(pair? '(1 2 3))
#t
(pair? '())
#f

与えられたオブジェクトが正式なリストであることを確かめる手続き list?を考える

(define (list? obj)
  (or (null? obj)
    (and (pairs? obj) (list? (cdr obj)))))

sekitats

リストの捜査

リストの要素を順に処理していく手続きの基本になるのは fold

(require srfi/1)
(fold + 0 '(1 2 3 4 5))
=> 15

(require srfi/1)
(define (product-of-numbers lis)
    (fold * 1 lis))
(product-of-numbers '(1 2 3 4 5))
120

数のリストのうち、最大のものを求める

(define (max-number lis)
    (define (pick-greater a b)
      (if (> a b) a b))
    (if (null? lis)
        (error "max-number needs at least one number")
        (fold pick-greater (car lis) (cdr lis))))

(max-number '(35 60 24 44))
60

(fold cons '() '(a b c d e))
'(e d c b a)

foldの定義

listが空だったら初期値を返す

(define (fold proc init lis)
  (if (null? lis)
      init
      ???))

list の先頭要素を処理する。(proc (car lis) init)
init を上の proc の呼び出しの結果に、lis を (cdr lis)に置き換えて処理を繰り返す

(define (fold proc init lis)
  (if (null? lis)
      init
      (fold proc (proc (car lis) init) (cdr lis))))

sekitats

簡単なリスト処理

空でないリストの最後の対を見つける手続きlast-pair を考える（末尾再帰）

(last-pair '(1 2 3))
(3)

(define (last-pair lis)
  ...)

list の cdr がリストでないこと

(define (last-pair lis)
  (if (pair? (cdr lis)
    ???
     lis))

list の最後の対は、(cdr lis) に対して、last-pair を呼び出す

(define (last-pair lis)
  (if (pair? (cdr lis))
    (last-pair (cdr lis))
     lis))

(last-pair '(1 2 3))
↓
'(1 2 3)
'(2 3)
'(3)

リストをコピーする手続き copy-list を考える

リストが対でなければ、終端なので引数をそのまま返す
リストが対ならばリストの先端を(car list) とリストの残りをコピーしたもの (copy-list (cdr list))で新しいリストを作る

(define (copy-list lis)
  (if (pair? lis)
    (cons (car lis) (copy-list (cdr lis)))
    lis))

2つのリストを連結する手続き append2 を考える

(define (append2 a b)
  (if (pair? a)
    (cons (car a) (append2 (cdr a) b))
    b))

リストの要素を逆転する、reverseを考える

(define (reverse lis)
  (if (null? (cdr lis))
    lis
    (append2 (reverse cdr lis) (list (car lis)))))

find を考える。(末尾再帰)

pred は predicate「真偽値を返す関数」のこと

(define (find pred lis)
  (if (null? lis)
    #f
    (if (pred (car lis))
      (car lis)
      (find pred (cdr lis)))))

cond と 角カッコに書き換え

(define (find pred lis)
  (cond [(null? lis) #f]
             [(pred (car lis)) (car lis)]
             [else (find pred (cdr lis))]))

2種類の再帰

fold, last-pair, find は末尾再帰。append2, reverse は末尾再帰ではない。

リストの長さを数えるlengthを考える。

(define (length lis)
  (if (null? lis)
    0
    (+ 1 (length (cdr lis)))))

これは非末尾再帰。（再帰的に読んだ length の結果を受け取って１を足す、という処理をする必要があるから）

 ;; (+ 1 (+ 1 (+ 1 (+ 1))))

(define (length lis)
  (define (length-rec lis n)
    (if (null? lis)
        n
        (length-rec (cdr lis) (+ n 1))))
  (length-rec lis 0))

「残りのデータ」と「今までの結果」だけを再帰的に渡して行ける場合は簡単に末尾再帰でかけるので、なるべくそうすべき

sekitats

手続き

gosh> sume-of-numbers
#<Closure sum-of-numbers>

これは式の値が「手続き」オブジェクトであることを示す。#<...>はリテラルでは書けないオブジェクトの表記

また、手続きは値として他の変数に束縛したり、引数として他の手続きに渡したり、戻り値として返したりできる。

> (define x sum-of-numbers)
x
(x '(1 2 3 4 5))
15

手続きを定義するのに名前すら与える必要はない。（無名関数）lambda 式は評価されると手続きオブジェウトになる

(lambda (a b) (+ (* a a) (* b b)))
#t

名前もつけられる

(define square-sum (lambda (a b) (+ (* a a) (* b b))))
square-sum
(square-sum 3 4)
25

以下は同じ。手続きとは全て無名の実態 #<closure ...>

(define (名前 引数) 式) #  MIT記法という
(define 名前 (lambda (引数) 式)

(define (length lis)
  (define (increment2 a b) (+ b 1))
  (fold increment2 0 lis))

(length '(1 2 3 4 5))

; 無名関数で書き直す
(define (length lis)
  (fold (lambda (a b) (+ b 1)) 0 lis))

~~lambda の由来~~

手続きを取る手続き

fold は手続きを引数に取ることで、「リストの各要素を操作しながら値を計算してゆく」という一般化された操作を書くことができました。このように、手続きを引数として受け取ることで汎用的な処理を記述するのは、Schemeプログラミングの根幹となています。

(for-each (lambda (x) 
  xを使った処理)
  lis)

(define (tree-walk walker proc tree)
  (walker (lambda (elt)
            (if (list? elt)
                (tree-walk walker proc elt)
                (proc elt)))
          tree))
; walkerとして for-each を、proc として print を渡している
(tree-walk for-each print '((1 2 3) 4 5 (6 (7 8))))

jsで書き直した例

function treeWalk(walker, proc, tree) {
    return walker(function (elt) {
        if (Array.isArray(elt)) {
          return treeWalk(walker, proc, elt);
        } else {
          return proc(elt);
        }
    }, tree);
}

treeWalk(
  (fn, arr) => arr.forEach(fn),
  console.log,
  [[1, 2, 3], 4, 5, [6, [7, 8]]]
)

reverse する

reverse-for-each を定義し、walker に渡す

(define (reverse-for-each proc list)
  (for-each proc (reverse list)))
(tree-walk reverse-for-each print '((1 2 3) 4 5 (6 (7 8))))

js で書き直す

function treeWalk(walker, proc, tree) {
    return walker(function (elt) {
        if (Array.isArray(elt)) {
          return treeWalk(walker, proc, elt);
        } else {
          return proc(elt);
        }
    }, tree);
}

treeWalk(
  (fn, arr) => arr.reverse().forEach(fn),
  console.log,
  [[1, 2, 3], 4, 5, [6, [7, 8]]]
)

map

map は<リスト>の各要素に<手続き>を適用し、結果をリストにして返す

; 各要素を2倍にして返す
(map (lambda (x) (* x 2)) '(1 2 3 4))
(2 4 6 8)

reverse-mapを考える

渡された引数をそのまま返す関数 (lambda (x) x)を渡す

(tree-walk map (lambda (x) x) '((1 2 3) 4 5 (6 (7 8))))

(define (reverse-xxx proc lis)
  (xxx proc (reverse lis)))
; は以下と同じ
(define reverse-xxx
  (lambda (proc lis)
    (xxx proc (reverse li))))

Scheme が for-each を構文ではなく手続きとして提供しているおかげで、このように他の手続きと組み合わせてより高機能な手続きを作りだしてゆくことができる
手続きを受け取る手続き、手続きを返す手続きを（高階手続きと呼ぶ）

filter

(define (for-each-numbers proc lis)
  (for-each (lambda (x)
         (if (number? x) (proc x) '()))
            lis))

(for-each-numbers print '(1 2 "#f" 3 4 "t"))

sekitats

ローカル変数

lambda式は手続になるので、リストの先頭位置におけばそのまま呼び出せる

((lambda (a b) (+ (* a a) (* b b)) 3 4)
; 15

jsで書き換える

((a, b) => console.log((a * a) + (b * b)))(3, 4)

Schemeにおいては、このlambda の仮引数が他の言語でのローカル変数の正体そのもの。ただ、lambdaを使って書くのは見づらいので簡略表記として letという構文がある

(let ((a 3) ; 変数1
      (b 4)) ; 変数2
  (+ (* a a) (* b b))) ; 式

let 式は、他の多くのプログラミング言語における、スコープを作るブロックだと考えて良い。