Scheme 手習い（３）

第4章は数字に関する関数をどうやって再帰的に書くかという話が中心。

第４章：数字宛てゲーム

add1/sub1

(define (add1 n)
  (+ n 1))

(define (sub1 n)
  (- n 1))

数に 1 を足す関数と数から 1 をひく関数。

+/-

(define (+ n m)
  (cond [(zero? m) n]
        [else (add1 (+ n (sub1 m)))]))

(define (- n m)
  (cond [(zero? m) n]
        [else (sub1 (- n (sub1 m)))]))

足し算と引き算を add1、sub1 を使って再帰的に定義する。

「n に m 回だけ 1 を足す（または引く）」という考え方。

addtup

(define (addtup tup)
  (cond [(null? tup) 0]
        [else (+ (car tup) (addtup (cdr tup)))]))

tup は数字のみで構成されたリスト。

addtup は tup の要素を足し合わせる関数。 終了条件には null? を使って 0 を返す。

*

(define (* n m)
  (cond [(zero? m) 0]
        [else (+ n (* n (sub1 m)))]))

足し算を使って掛け算を定義する。

「n を m 回だけ足し合わせる」という考え方。

第１の戒律（改訂版）

【第１の戒律（改訂版）】

アトムのリスト lat を再帰するときは、２つの質問をすべし。すなわち、(null? lat) と else なり。

数 n を再帰するときは、２つの質問をすべし。すなわち、(zero? n) と else なり

第４の戒律

【第４の戒律（改訂版）】

再帰の間は少なくとも１つの引数を常に変化させるべし。

引数は終わりに向けて変化させることを要す。変化する引数は最終条件にてテストすべし。 すなわち、cdr を用いるときは、null? で最終テストし、sub1 を用いるときは、zero? で最終テストせよ

第５の戒律

【第５の戒律】

+ で値を作らんとせしときは、行を終える時に常に値として 0 を用うべし。なんとなれば、0 を加うるは加算の値を変えるぬからなり。

* で値を作らんとせしときは、行を終える時に常に値として 1 を用うべし。なんとなれば、1 を掛けるは乗算の値を変えぬからなり。

cons で値を作らんとせしときは、行を終えるときに常に値として () を考えるべし。

tup+

(define (tup+ tup1 tup2)
  (cond [(null? tup1) tup2]
        [(null? tup2) tup1]
        [else (cons (+ (car tup1) (car tup2))
                    (tup+ (cdr tup1) (cdr tup2)))]))

両方の tup の要素を足し合わせて新しいリストにする関数。

片方が空リストの場合は、もう片方のリストを返すのがポイント。

>, <, =

(define (> n m)
  (cond [(zero? n) #f]
        [(zero? m) #t]
        [else (< (sub1 n) (sub1 m))]))

(define (< n m)
  (cond [(zero? m) #f]
        [(zero? n) #t]
        [else (< (sub1 n) (sub1 m))]))

(define (= n m)
  (cond [(> n m) #f]
        [(< n m) #f]
        [else #t]))

大なり、小なりも sub1 と zero? のみを使って実装できる。

片方の引数が 0 になるまで 1 を引いていき、最終的には zero? を使って大小を判断する。

expt

(define (expt n m)
  (cond [(zero? m) 1]
        [else (* n (expt n (sub1 m)))]))

累乗を計算する関数。

/

(define (/ n m)
  (cond [(< n m) 0]
        [else (add1 (/ (- n m) m))]))

割り算も - を使って再帰的に定義できる。

「m で何回引き算できるか」を使って割り算を定義する。 これはなかなかおもしろい考え方。

length

(define (length lat)
  (cond [(null? lat) 0]
        [else (add1 (length (cdr lat)))]))

リストの長さを計算する関数。

pick/rempick

(define (pick a lat)
   (cond [(zero? (sub1 a)) (car lat)]
         [else (pick (sub1 a) (cdr lat))]))

(define (rempick n lat)
  (cond [(zero? (sub1 n)) (cdr lat)]
        [else (cons (car lat) (rempick (sub1 n) (cdr lat)))]))

リストから対象の要素を除去する関数。

no-nums/all-nums

(define (no-nums lat)
  (cond [(null? lat) '()]
        [(number? (car lat)) (no-nums (cdr lat))]
        [else (cons (car lat) (no-nums (cdr lat)))]))

(define (all-nums lat)
   (cond [(null? lat) '()]
         [(number? (car lat)) (cons (car lat) (all-nums (cdr lat)))]
         [else (all-nums (cdr lat))]))

リストから数を除去する関数と数だけを抽出する関数。

eqan?

(define (eqan? a1 a2)
  (cond [(and (number? a1) (number?a2)) (= a1 a2)]
        [(or (number? a1) (number? a2)) #f]
        [else (eq? a1 a2)]))

同じアトムかどうかを調べる関数。

両方とも数字なら = で比較。片方だけが数字なら偽。それ以外なら eq? で比較する。 片方が数字の場合は eq? を使えないので注意（Eq? の掟）

occur

(define (occur a lat)
  (cond [(null? lat) 0]
        [(eqan? a (car lat)) (add1 (occur a (cdr lat)))]
        [else (occur a (cdr lat))]))

リストの中の該当の要素の数を計測する関数。

one?

(define (one? n)
  (cond [(zero? n) #f]
        [else (zero? (sub1 n))]))

与えられた引数が 1 かどうかを調べる関数。 マイナスをケアするために、n がゼロかどうかを調べている（ゼロにsub1 するのは違反）

当然、次のようにも書ける

(define (one? n)
  (= n 1))

感想

再帰のパターンがだいぶ身についてきた。

Scheme 手習い（２）

第３章：偉大なる cons

rember

(define (rember a lat)
  (cond [(null? lat) '()]
        [(eq? (car lat) a) (cdr lat)]
        [else (cons (car lat) (rember a (cdr lat)))]))

rember は remove member の略。 ラット（すべての要素がアトムのリスト）内で一致した最初のアトムを削除する関数。

第２の戒律

【第２の戒律】

リストを作るには cons を用いるべし

そのまんまなんだけど、リストを作りたいときは cons を利用する。

firsts

(define (firsts l)
  (cond [(null? l) '()]
        [else (cons (car (car l)) (firsts (cdr l)))]))

firsts はリストを含むリストの最初の要素を集めて再びリストにする関数。

第３の戒律

【第３の戒律】

リストを作らんとせしときは、最初の要素になるものを記述し、しかる後にそれを自然なる再帰に cons すべし。

cons は第一引数は要素、の第二引数は再帰、の形にする。

insertR/insertL

(deifne (insertR new old lat)
  (cond [(null? lat) '()]
        [(eq? (car lat) old) (cons (car lat) (cons new (cdr lat)))]
        [else (cons (car lat) (insertR new old (cdr lat)))]))

insertR は old の右側に new を挿入する関数。

(define (insertL new old lat)
  (cond [(null? lat) '()]
        [(eq? old (car lat)) (cons new lat)]
        [else (cons (car lat) (insertL new old (cdr lat)))]))

insertL は old の左側に new を挿入する関数。

subst/subst2

(define (subst new old lat)
  (cond [(null? lat) '()]
        [(eq? old (car lat)) (cons new (cdr lat))]
        [else (cons (car lat) (subst new old (cdr lat)))]))

old を new に置き換える関数。

(define (subst2 new o1 o2 lat)
  (cond [(null? lat) '()]
        [(or (eq? o1 (car lat)) (eq? o2 (car lat)))
         (cons new (cdr lat))]
        [else (cons (car lat) (subst2 new o1 o2 (cdr lat)))]))

o1 か o2 を new に置き換える関数。

multirember

(define (multirember a lat)
  (cond [(null?o lat) '()]
        [(eq? (car lat) a) (multirember a (cdr lat))]
        [else (cons (car lat) (multirember a (cdr lat)))]))

ラット内のすべての要素 a を削除して新しいリストを作る関数。 rember の複数要素対応ってところ。

multiinsertR/multiinsertL

(define (multiinsertR new old lat)
  (cond [(null? lat) '()]
        [(eq? (car lat) old)
         (cons old (cons new (multiinsertR new old (cdr lat))))]
        [else (cons (car lat) (multiinsertR new old (cdr lat)))]))

(define (multiinsertL new old lat)
  (cond [(null? lat) '()]
        [(eq? old (car lat))
         (cons new (cons old (multiinsertL new old (cdr lat))))]
        [else (cons (car lat) (multiinsertL new old (cdr lat)))]))

insertL と insertR の複数要素対応版。

感想

第３章は再帰の基本的な構造を学んだ。

ここら辺は SICP でやったことがあるところなので、特に難しくなかった。 でも、SICP よりパターン化してあるからこちらの方がより定着率は高いかな。

『Scheme 手習い』はじめました。

Gauche 本を進めていたけれど、なんだかあんまり身についてる気がしなかったので『Scheme 手習い』に手を出してみた

Scheme手習い

第１章：おもちゃ

アトム、リスト、S 式とは

Gauche は atom? が定義されてないので、本に書いてあるように定義する。

(define atom?
  (lambda (x)
    (and (not (pair? x)) (not (null? x)))))

(atom? '0) ; => #t

「(atom? '0) が #f になることを確かめてほしい」って本に書いてあるけど、おかしい…。 本の誤植かも。

(atom? 'atom) ; => #t
(atom? 1492) ; => #t
(atom? '()) ; => #f
(atom? '(1 2 3)) ; => #f

アトムはリストではないもの。

(list? 'atom) ; => #f
(list? 1492) ; => #f
(list? '()) ; => #t
(list? '(1 2 3)) ; => #t

リストは S 式を括弧でくくったもの。

アトムは S 式。 リストもそれ自体が S 式となる。

car とは

(car '(A B C)) ; => A
(car '(A)) ; => A
(car 'hotdog) ; => 未定義
(car '()) ; => 未定義

car は空でないリストの先頭の S 式を取り出す。 アトムと空のリストに対する操作は定義されていない。

cdr とは

(cdr '(A B C)) ; => (B C)
(cdr '(A)) ; => ()
(cdr 'hotdog) ; => 未定義
(cdr '()) ; => 未定義

cdr は空でないリストの先頭以外のリストを取り出す。 アトムと空のリストに対する操作は定義されていない。 cdr は常にリストとなる。

cons とは

(cons 'a '(b c)) ; => (a b c)
(cons 'a '()) ; => (a)
(cons 'a 'b) ; => 本では扱わない

cons は任意の S 式をリストの先頭につける。 第一引数は S 式。第二引数は任意のリスト。 ドット対は扱わないようだ。

null? とは何か

(null? '()) ; => #t
(null? '(a)) ; => #f
(null? 'a) ; => 本では扱わない

null? は空リストかどうかを調べる。 アトムに対する null? は定義されていない。

eq? とは何か

(eq? 'atom 'atom) ; => #t
(eq? '(1) '(1)) ; => 本では扱わない
(eq? 7 6) ; => 本では扱わない

eq? は同じアトムであるかどうかを調べる。 eq? はどちらも数でないアトムでなければならない。

１章はこれで終わり。

第２章：一度、もう一度、さらにもう一度、またもう一度、……

lat?

(define (lat? lis)
  (cond [(null? lis) #t]
        [(atom? (car lis)) (lat? (cdr lis))]
        [else #f]))

(lat? '()) ; => #t
(lat? '(a b c)) ; => #t
(lat? '((a) b c)) ; => #f
(lat? '(() b c)) ; => #f

lat? はリスト内の S 式がすべてアトムだった場合に #t を返す関数。

or

(or (null? '()) (null? '())) ; => #t
(or (null? '()) (null? '(a b c))) ; => #t
(or (null? '(a b c)) (null? '())) ; => #t
(or (null? '(a b c)) (null? '(a b c))) ; => #t

or の確認。

member?

(define member?
  (lambda (lis a)
    (cond [(null? lis) #f]
          [(eq? (car lis) a) #t]
          [else (member? (cdr lis) a)])))

(member? '(a b) 'a) ; => #t
(member? '(a b) 'c) ; => #f
(member? '() 'a) ; => #f

与えられたアトムがリスト内にあるかどうかを調べる関数。

第１の戒律

【第１の戒律】

（仮）いかなる関数を表現するときも最初の質問はすべて null? にすべし。

感想

再帰の練習って感じ。まずはじめに null? を質問するのがコツ。 ここらへんはまだまだ簡単。

そういえば、紙の本買ったのひさしぶりだなぁ。

クラウドのもろさとは

昨日起きた AWS の障害。自分の会社も AWS を利用しているので影響を受けた。

この出来事に対してクラウドを利用することへのもろさを懸念する論調が一部であがった。

「もろさ」には二種類あると思う。個別のサービスに対するもろさと、社会全体として見たときのもろさ。

大手が提供するクラウドサービスを利用すること個別のサービスのもろさは低減されると思う。自社でサーバーを管理するよりも高度な体制で管理されているだろうし、今回のような事件があっても復旧は早い。

しかし、多くのサービスが特定の業者のクラウドに依存するようになると、社会としてのもろさは確実に上昇するだろう。オール電化のマンションが停電すると何もできないように。

ウェブサービスが載っかるインターネットは分散システムになっていることとは対照的だと感じた。

あと、このあたりの切り分けをせずにこのことを論じると、なんだか水掛け論だなぁとツイッターなどを見ていて思った。

AWS のデフォルト VPC

AWS で新規にアカウントを作成すると最初から『デフォルト VPC』が設定されている。

docs.aws.amazon.com

ただそれだけ。

Scheme の number? と complex?

Scheme にある number? と complex? という手続き。

• number? : 引数が数値であるかどうか
• complex? : 引数が複素数であるかどうか

(number? x) => #t かつ (complex? x) => #f の数値ってあるのかな？と思った。

リファレンス（6.3.2 数値に関する述語）を見るとまさに解答が書かれていた。

Gaucheでは、数の集合は複素数の集合と同一であり、...（略）

「Gauche では、」ってことは他の処理系ではそういう数値があるのかなぁ？

Dart の非同期プログラミング（Future, async/await）

仕事で Flutter をちょっといじっていて、いい加減 async あたりをちゃんと理解しておこうと思ったのでメモ。

https://dart.dev/tutorials/language/futures

Dart コードはシングルスレッドで実行される

Dart は基本的にシングルスレッドで実行される。 並列処理を行いたい場合は Isolate を利用する。

Future は非同期オペレーションの結果を表す

Future は非同期オペレーションの結果を表している。 ここは Java と同じだね。

Future が完了するまで待つには async 関数で await を使う

void main() async {
  await something();
  print('all done');
}

await を使うためには関数に async を付与する必要がある。

async 関数では以下の条件のいずれかを満たすまで同期的に実行される。 以下のどれかにたどりつくと Future を返し、非同期的に実行される。

• 関数で最初の await
• return 文
• 関数の終わり

await のあれこれ

await expression の expression は通常 Future を返す関数である。 しかし、expression が Future を返さない場合は、自動的に Future でラップされる。

なお、await expression 文自体は Future の完了した値を返す。

import "dartd:async";

void main() async {
   // 自動的に Future にラップされ、Future の完了値 int を返す
   int i = await something();
   print(i);
}


int something() {
  return 1;
}

完了を待ちつつスレッドをブロックしない、っていうのが await で気楽に使えるのはいいなぁ。