On Lisp読書会第一回まとめ

On Lisp
On Lisp読書会　第一回

一度Schemeを学んでいるので基本的な事項は結構はしょってます。
結構忘れていましたが…

せっかくだからと関数型言語の利点欠点を調べたら、

  • 関数型言語の利点
    • 計算に本質的ではない副作用が起こらないことと。
    • 再帰呼び出しを容易に記述できること。
    • プログラムを書くプログラムを書ける。マクロ！
    • ボトムアップアプローチでプログラムを書ける。
    • 処理系と書き方によってはプログラムの速度がC++並みに速い
  • 関数型言語の欠点
    • 性能を引き出すのが難しい。
    • 他の言語と比べて異色で学びにくい(それが長所でもあるが)。
    • 大規模プログラムを書いている時には、時間又は領域において容認できない程非効率なプログラムができる場合がある。
    • 扱い辛いラムダ計算の副作用。
    • IO型との戦い。

ちなみにクラッシュバンディクーはLispで書かれているらしい。

コンピューティングの基本原則

Don't repeat yourself
  • 基本的にプログラムは何度も繰り替えされる共通の動作を関数にする。
  • 関数を呼び出すことでプログラムの繰り返し記述をやめる。

リストの中に入ってほしくない時、関数として呼び出さないでほしい時は要素前に'(シングルクオート)をつける

シンボルとは何か

名前、関数定義、変数値、属性リストを格納する。
すなわち、(hoge hoge)でhogeという関数にhogeという変数を代入したことになる！！

SBCLにおける関数定義の仕方

(defun 関数名 (引数)
	(ここから処理、手続き
	…
	))

Schemeでは

(define (関数名 引数)
	(ここから処理、手続き
	…
	))

とdefineとdefun、関数、引数のかっこが微妙に違ってなれない。。
関数型言語の返り値は最後に評価した式の値。
英語で{}がbrace, <>がbracket,[]と()は何だろう？ふと気になった。

レキシカル変数とグローバル変数

  • レキシカル変数は定義された範囲内で使える変数
  • グローバル変数はすべての場所で使える変数
  • レキシカル変数が定義されている時はレキシカル変数を使う
  • レキシカル変数が定義されていない、かつグローバル変数が定義されている時はグローバル変数を使う
  • レキシカル変数の定義
    • 関数letを使う
(let (
　　(変数名 初期値)
　　 (同様)
　　 …
　　 )
　　 変数を使った処理)

letで宣言された変数はletの中でしか使えない。

例

与えられた引数x,yの和、差、積、商を表示する関数をつくって下さい。
表示する商は小数表示で、関数の返り値は商の分数表示になるようにして下さい

SBCL
(defun shisoku (x y)
	(print (+ x y))
	(print (- x y))
	(print (* x y))
	(let ((sho (/ x y)))
		(print (float sho))
		sho))

(shisoku 2 3)
5 
-1 
6 
0.6666667 
2/3
とちゃんと動いているみたい

Scheme(JAKLD)
printが定義されていなかったから自分で定義した。
どうにも分数表示する方法が見つからなかったので割愛
(define (print x)
	(display x)(newline))
(define (shisoku x y)
	(print (+ x y))
	(print (- x y))
	(print (* x y))
    (print (/ x y)))

(shisoku 2 3)
5
-1
6
0.6666666666666666

値としての関数

  • 汎関数は引数として関数を受け取る。
  • シンボルには関数の中身と変数の中身が入る。
  • 関数の中身と変数として入る関数は違う。
  • 値としての関数を作る時は関数名の前に#'をつける。
  • 値としての関数のおかげで関数の引数や返り値に関数が使える。
  • 関数を引数に取る関数を汎関数と呼ぶ。

ラムダ式

  • ラムダ式は無名の関数、匿名関数を定義する。
  • 汎関数で引数に使う関数として、より自由度の高い関数を指定できる。
  • わざわざ定義する必要がない時にも使える。
  • (lambda (仮引数) 処理)
練習問題

Card1には1,2,3,4,5,6,7,8
Card2には1,2,3,4,9,10,11,12
Card3には1,2,5,6,9,10,13,14
Card4には1,3,5,7,9,11,13,15が書いてあります。
1から16までのある数字を思い描いて、その数字がどのカードにあるかないかを長さ4のリストで表現します。
これを引数としてどんな数字を思い描いたか当てるプログラムを作って下さい。
例:(t nil t t) => 5

ここから下は回答例、下に行く程汎用性が高い答えになってます。

解1
まず、あるかないかの2択が怪しい。とりあえず2進数を疑ってみるのがCSを学んでいる人間の心情では？
ぱっと見て、
Card1は始めの8個の数字
Card2は始めの4個の数字、次の4個の数字をとばして、また次の4個の数字
Card3は始めの2個の数字、…
Card4は1個飛ばしに数字が並んでいる。
この直感は正しそう。
つまりn番目のcardがtなら何もせず、nilなら2の(4-n)乗を足す。iを4から始めていけば2の(i-1)乗になる。
最後に1を加えればいいのだ！
これは条件を満たしていることを確認できる。
で、プログラムは、

(defun pow (x y)
	(if (= y 0)
		1
		(* x (pow x (- y 1)))))
(defun check (list i n)
	(if (= i 0) n
		(if (equalp (car list) 't)
			 (check (cdr list) (- i 1) n)
			 (check (cdr list) (- i 1) (+ n (pow 2 (- i 1)))))))
(defun check-card (list)
	(check list 4 1))

同じ考えでFさんのコード
僕のコードよりすっきりしています。

(defun fsan (list)
  (let ((x 16) (y 3))
    (dolist (z list)
      (if z
          (setf x (- x (expt 2 y))))
      (setf y (- y 1)))
    x))

解2
担当者の用意した答え
nilならば、1から16のリストの中からcardのリストを取り除く。
tならば、なにもしない。最終的にその中での最小値を取る。
先の例より汎用性があるが、16がどこにも入っていないというのが成立条件の一つ。

(defun magic (list)
	(let ((cards '((1 2 3 4 5 6 7 8)
			      (1 2 3 4 9 10 11 12)
			      (1 2 5 6 9 10 13 14)
			      (1 3 5 7 9 11 13 15)))
			numbers)
		(dotimes (x 16) (setf numbers (cons (- 16 x) numbers)))
		(dotimes (x 4)
			(when (not (nth x list))
				(setf numbers (remove-numbers numbers (nth x cards)))))
		(car numbers)))
(defun remove-numbers (number list)
	(dolist (number list)
		(setf numbers  (remove number numbers)))
	numbers)

解3
更に汎用性のある理学部数学科の人の答え
逐次実行する関数fold
その要素が含まれるかチェックする関数elementp
和集合を求める関数my-union
積集合を求める関数my-intersection
一方に含まれている要素から、他方に含まれている要素を取り除く関数my-difference
以上を用いて、1〜16のリストに対して
tならばカードの要素に対してmy-intersectionを、
nilならばカードの要素に対してmy-differenceを適用する。
これを逐次実行すればよい。
ちなみに一つの関数の長さはこれぐらいがいいそうです

;; Fold
(defun foldl (f c x)
  (if (null x)
      c
      (foldl f (funcall f c (car x)) (cdr x))))

(defun foldl2 (f c d x)
  (if (null d)
      c
      (foldl2 f (funcall f c (car d) (car x)) (cdr d) (cdr x))))

;; Set function
(defun elementp (e x)
  (foldl #'(lambda (z w)
             (or (equalp e w) z))
         nil x))

(defun my-union (x y)
  (foldl #'(lambda (z w)
             (if (elementp w x)
                 z
                 (cons w z)))
         x y))

(defun my-intersection (x y)
  (foldl #'(lambda (z w)
             (if (elementp w x)
                 (cons w z)
                 z))
         nil y))

(defun my-difference (x y)
  (foldl #'(lambda (z w)
             (if (and (elementp w x) (not (elementp w y)))
                 (cons w z)
                 z))
         nil x))

;; Data
(setq cards '((1 2 3 4 5 6 7 8)      ;card1
              (1 2 3 4 9 10 11 12)   ;card2
              (1 2 5 6 9 10 13 14)   ;card3
              (1 3 5 7 9 11 13 15))) ;card4
(setq card0
      (let ((tmp (foldl #'my-union nil cards)))
           (cons (+ 1 (car tmp)) tmp)))

;; magical-lisp
(defun magic (x)
 (car (foldl2 #'(lambda (z w s)
              (if s
                  (my-intersection z w)
                  (my-difference z w)))
            card0 cards x)))