Lisp

2024-04-172024
29.2% (107/366)
April
53.5% (16/30)
Week 16
29.6% (2/7)
Day 17 Wed
7.8% (1.8/24)

訪問者

total: 11827
today: 1
yesterday: 4
now: 15

↑

更新

MenuBar

はじめに
教材・開発環境
魔法言語リリカル☆Lisp 学習ノート
Clojure

はじめに †

学生時代に挫折した関数型言語にもう一度取り組んでみよう
GUI のイベント処理を効率的に記述するために、関数型言語の考え方が取り入れられつつある。Ajax なんかまさにそれ
普通のコンピュータが多コアになり、並列処理プログラミングの需要が増大。並列処理を効率的に記述するために、関数型言語の考え方が取り入れられつつある。Java には Java SE 8 で導入される予定

↑

教材・開発環境 †

とりあえず「魔法言語リリカル☆Lisp」をやってみようと思う
- λ組による萌え系 Lisp 教材
- Mac での動かし方 → Mac WindowsアプリをMacで動かす
Ready Lisp
- Mac での Lisp の開発環境
- Common Lisp の開発環境。Aquaemacs + SBCL + SLIME
Closure
- Java VM または .NET で動く LISP 方言
- 開発環境 > NetBeans Enclojure

↑

魔法言語リリカル☆Lisp 学習ノート †

↑

第 1話式 †

Lisp は全部[式]
```
(式1 式2 式3 式4 ...)
```
- 式1 : 演算子
- 式2,3,4... : 被演算子
Lisp インタプリタは、式を読み込み・評価し・結果を印刷し、式の入力状態に戻る
- Read-Eval-Print Loop

↑

第 2話変数 †

変数に値を束縛する
```
(define x 123)
```
Lisp は、式と環境を評価する。define は、環境に x=123 を設定する。

↑

第 3話シンボル †

Atom
- () で囲われていない式
- Atom = 数値 | シンボル
- シンボル
```
(quote aiueo)
省略表記　→ 'aiueo
```
演算子を関数とも言う
```
(関数 引数1 引数2 引数3 ...)
```
スペシャルフォーム
引数を評価しない演算子
```
(quote aiueo)
(define x 'auieo)
```

↑

第 4話リスト †

リスト
```
(cons 'a 'b)
```
- Lisp のデータ構造は、CONS の集まり。
- CONS は、CAR 部と CDR 部からなる
- 例は、CAR部に a へのポインタ
- 例は、CDR部に b へのポインタ

CAR と CDR を読み出す

(car (cons 'a 'b)) -> a
(cdr (cons 'a 'b)) -> b

リスト
- CDR部に CONS へのポインタを入れるとリストになる
- 行儀の悪いリスト (末端の CDR 部に値(へのポインタ)が入っている)
```
(cons 'a (cons 'b 'c)) = '(a b . c)
[・][・]→[・][・]->c
 ↓        ↓
 a         b
```
  - CONS の CDR部が CONS の時には ( を省略する
  - 末端の CDR は、. を入れる
- 行儀の良いリスト (末端の CDR 部が nil)
```
(cons 'a (cons 'b '())) = '(a b '() )  =  '(a b)
[・][・]→[・][・]->nil
 ↓        ↓
 a         b
```
  - 末端の CDR に nil ('()) を入れる場合には、そのことを省略できる。
S式
- リストを ( ) で表現する表現方法
- BNF
```
<S式>  ::= <List> | <Atom> 
<List> ::= (<S式>*) 
<Atom> ::= <Symbol> | <Number>
```
- 今まで出てきたのも含めて Lisp は全部 S 式できている
CAR とか CDR って何？
- http://www.iwriteiam.nl/HaCAR_CDR.html
- Lisp が初めて動作した IBM 7090 (1959) の特殊命令
```
012 345678901234567 890 123456789012345
OP  値(Decrement)   X   Address
命                  レ
令                  ジ
                    ス
                    タ
```
  - レジスタ X に {値} を OP して、Address に飛ぶ
  - 通常、演算OP と JUMP の 2 命令必要なところを 1 命令でできる
- CAR : Content of Address part of Register
- CDR : Content of Decrement part of Register
- CAR と CDR の順番が Lisp と逆のような気がするが、その理由は参照先の著者さんにもわからないらしい

↑

第 5話関数 †

関数定義
```
(lambda (仮引数) (演算式))
```

仮引数と実引数

         仮引数       実引数
         ---          --
((lambda (x) (+ x 1)) 9) 
 -------------------- --
 演算子               被演算子

関数は、関数名に束縛しなくても無名のまま実行することもできる

仮引数が二つある関数
```
(lambda (x y) (cons x (cons y '())))
```

関数の定義 = 関数を値に束縛する

(define caar (lambda (lst) (car(car lst))))

これは、CAR の CAR を求める関数

(caar '((a b) (c d))) = a

[・][・]→[・][・]→ d
 ↓        ↓
[・][・]   c
 ↓  ↓
 a   b

環境に格納されている変数名と、仮引数の変数名がかぶった場合には仮引数が使われる
```
(define x 10)
(define y 20)
((lambda (x) (+ x y)) 100) → 120
```

↑

第 6話条件分岐・再帰 †

(define x 3)
(if (= x 3)
  'Three 
  'NotThree)
→ Three

(= a b)

a==b のとき #t を返す。a!=b のとき #f を返す。

cond

(define x 3)
(cond (
  (= x 1) 'One 
  (= x 2) 'Two 
  (= x 3) 'Three 
  else 'Other)
)
→ Three

再帰

(define sigma
  (lambda (n) 
    (if (= n 0) 
      0 
      (+ n (sigma (- n 1)))
    )
  )
)
(sigma 10) → 55

10           9                8
Σ(i) = 10 + Σ(i) = 10 + 9 + Σ(i) = ... = 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0
i=0          i=0              i=0

↑

第 7話大域変数と局所変数 †

大域変数
```
(define x 10)
```
局所変数
```
(define x 10)
(let ((y 20) (z 30)) (+ x (+ y z)))
```
- (let ((局所変数1 値1) (局所変数2 値2) ... ) 式)
- 局所変数は式の中だけで有効
変数の有効範囲　＝　スコープ
let は lambda に置き換えることもできる＝ let は lambda の sugar syntax
```
(let ((x 10) (y 20)) (+ x y)) → 30
((lambda (x y) (+ x y)) 10 20) → 30
```
- ' は quote の sugar syntax
- '(a b c) は ('a ('b ('c '()))) の sugar syntax
- sugar syntax : 糖衣表現 (苦いクスリを砂糖でくるんで子供にも飲みやすくする)
述語
- #t/#f を返す関数
- (= a b) : a と b が等しいか？
- (null? list) : list は nil か?

↑

第 8話 Closure! (状態を持つ関数) †

変数の値を変更する
```
(define x 9)
(set! x 19)
x → 19
```
- set! は、値を返さない (一律 #t を返す)
- "!" が付く関数は、値を書き換えるなどの破壊的な操作を行う。ban とよむ set! は、set-ban とよむ。
set! した結果を取り出したいときには、begin を使う
```
(begin 式1 式2 ... 式n)
```
begin は、式 n の評価結果を返す
- 使用例
```
(define (set-x! m n)
  (begin
    (set! x (+ m n))
    x
  )
)
```
- lambda では begin を省略できる

いよいよ本命、「状態を持つ関数」を返す関数。Closure

(define ma
  (lambda (n)
    (lambda (x)
      (set! n (+ n x))
      n
    )
  )
)

ma(n) は、 f(x){ n=n+x ; return n } という状態(n)を持つ関数を返す関数
```
((ma 11) 22) → 33
(define ma1 (ma 1))
(ma1 2) → 3
(ma1 3) → 6
(ma1 4) → 10
```

おー Closure だ
状態(n) は、どこからも参照されなくなったら削除される = GC (Garbage Collection)

↑

第 9話参照と実体 †

シンボルが同じだと、同じ実体になる

(define x 'a)
(define y 'a)
(eq? x y) → #t     // 参照先が同じ
(equal? x y) → #t  // 値が同じ

x も y もおなじシンボルの実体へのポインタ
```
x [・]
　 ↓
   'a
   ↑
y [・]
```

CONSは別の実体になる

(define lx (cons 'a 'b)))
(define ly (cons 'a 'b)))
(eq? lx ly) → #f    // 参照先が違う
(equal? lx ly) → #t // リストの中身の値が同じ

lx と ly は、別の CONS へのポインタ。それぞれの car と cdr はおなじシンボルの実体へのポインタになっている

               CONS
lx [・] → 【[・][・]】
  　          ↓  ↓
              'a  'b
              ↑  ↑
ly [・] → 【[・][・]】
               CONS

同じCONSを参照している場合

(define lx2 (cons 'a 'b)))
(define ly2 lx2)
(eq? lx2 ly2) → #t    // 参照先が同じ
(equal? lx2 ly2) → #t // リストの中身の値が同じ

lx2 と ly2 は、同じ CONS へのポインタ

                CONS
lx2 [・] → 【[・][・]】 ← [・] ly2
  　           ↓  ↓
               'a  'b

lx2 の参照先を変更すると ly2 の参照している値も変更されることになる
```
lx2 → (a . b)
ly2 → (a . b)
(set-car! lx2 'c)
lx2 → (c . b)
ly2 → (c . b)
```

↑

第10話補足説明(末尾再帰・コンソールからの入力) †

末尾再帰
- 再帰呼び出しを関数の最後に書くと、新しい環境が作られない
- 関数の最後で再帰呼び出しをする場合、古い環境を取っておく必要性はないので、Lipsインタプリタは古い環境をそのまま破壊的に使う最適化をする
```
01: (define sigma
02:   (lambda (n) 
03:     (if (= n 0) 
04:       0 
05:       (+ n (sigma (- n 1)))
06:     )
07:   )
08: )
```
- と書くと、05行の sigma の呼び出しでは新しい環境 (変数 n) を作らずに、外側の変数 n を使うのでヒープサイズを節約できる
コンソールからの読み込み
- read : 読み込み
- write : 書き出し
- eval : 評価
```
(eval read)
```
  でコンソールからの入力待ちになり、入力した S 式が評価される

↑

第11話関数を引数に取る関数 †

関数 op を引数に取る関数 fi。
```
(define (fi op lst ans)
  (if
    (null? lst)
    ans
    (fi op (cdr lst) (op ans (car lst)))
  )
)
```
- lst の要素同士を op する。ans には途中結果が格納される。
- 総和(Σ)と総積(Π)は、fi の第一引数にそれぞれ + * を与えれば作ることができる。
```
(define (sigma lst) (fi + lst 0))
(define (pai lst) (fi * lst 1))

(sigma '(1 2 3 4 5)) -> 15
(pai '(1 2 3 4 5)) -> 120
```
map関数は、第一引数に関数op、第二引数以降にリストを取る。リストの各要素に op を適用する。関数 op の引数が 2 つあるときには引数のリストは 2 つになる。
```
(map f '(a b c)) = ((f a) (f b) (f c))
(map g '(a b c) '(d e f)) = ((g a d) (g b e) (g c f))
```
- mapの実装はこんな感じ
```
(define map1 
  (lambda (op lst) 
    (if (null? lst) 
      '() 
      (cons (op (car lst)) (map1 op (cdr lst)))
    )
  )
)
```

↑

第12話まとめ、頭の体操 †

リストの長さを値とする世界の四則演算を作ってみる
```
'() = 0
'(o) = 1
'(o o) = 2
'(o o o) = 3
...
```

Increment, Decrement

(define (zero) '())
(define (inc lst) (cons 'o lst))
(define (dec lst) (cdr lst))

(zero) → nil
(inc '(o o)) → (o o o)
(dec '(o o)) → (o)

add

(define (add x y)
  (if 
    (null? y)
    x
    (add (inc x) (dec y))
  )
)

(add '(o o) '(o o o)) → (o o o o o)

y が null になるまで Decrement し、その分 x を Increment する。

subtact
```
(define (sub x y)
  (cond
    ((null? x) x)
    ((null? y) x)
    (else (sub (dec x) (dec y)))
  )
)

(sub '(o o o) '(o o)) → (o)
```
y が null になるまで Decrement し、その分 x を Decremt する。この方法では負の数は表せないので、x が null になったら null を返す

multiple

(define (mul x y) (muli x y (zero)))
(define (muli x y ans) 
  (if 
    (null? y) 
    ans 
    (muli x (dec y) (add ans x))
  )
)

(mul '(o o) '(o o o)) → (o o o o o o)

y が null になるまで Decremant し、その分 ans に x を足し込む

division

(define (div x y) (divi x y (zero)))
(define (divi x y ans) 
  (if 
    (null? x) 
    ans 
    (divi (sub x y) y (inc ans))
  )
)

(mul '(o o o o o o) '(o o)) → (o o o)

x が null になるまで y を引き、その回数を ans で数える

↑

Clojure †

[しばらく手がつけられない]

MenuBar

目次

訪問者

更新

最新の10件

人気の10件

MenuBar

はじめに †

教材・開発環境 †

魔法言語リリカル☆Lisp 学習ノート †

第 1話式 †

第 2話変数 †

第 3話シンボル †

第 4話リスト †

第 5話関数 †

第 6話条件分岐・再帰 †

第 7話大域変数と局所変数 †

第 8話 Closure! (状態を持つ関数) †

第 9話参照と実体 †

第10話補足説明(末尾再帰・コンソールからの入力) †

第11話関数を引数に取る関数 †

第12話まとめ、頭の体操 †

Clojure †

Lisp

目次

訪問者

更新

最新の10件

人気の10件

MenuBar

はじめに †

教材・開発環境 †

魔法言語 リリカル☆Lisp 学習ノート †

第 1話 式 †

第 2話 変数 †

第 3話 シンボル †

第 4話 リスト †

第 5話 関数 †

第 6話 条件分岐・再帰 †

第 7話 大域変数と局所変数 †

第 8話 Closure! (状態を持つ関数) †

第 9話 参照と実体 †

第10話 補足説明(末尾再帰・コンソールからの入力) †

第11話 関数を引数に取る関数 †

第12話 まとめ、頭の体操 †

Clojure †

魔法言語リリカル☆Lisp 学習ノート †

第 1話式 †

第 2話変数 †

第 3話シンボル †

第 4話リスト †

第 5話関数 †

第 6話条件分岐・再帰 †

第 7話大域変数と局所変数 †

第 9話参照と実体 †

第10話補足説明(末尾再帰・コンソールからの入力) †

第11話関数を引数に取る関数 †

第12話まとめ、頭の体操 †