初めての人のためのLISP (第1講-第5講)

日が開くとどうもやる気が無くなってしまうので読んでいる本のノートは少しずつ残していこうと思います.
初めての人のためのLISP[増補改訂版]のメモ.

第1講 初めての人のためのLISP(p.1-)

  • アトム
    • 数は全てアトム
    • スぺースを含まない文字列は(日本語も含め)全てアトム
  • リスト
    • アトムを並べて括弧でくくったもの
    • 空リスト()はニル(nil)と呼ぶ
    • リストはリストを要素にできる
((1 25) (14 5))

第2講 carとcdrで世間を渡れば権兵衛もたじろぐ(p.16-)

  • n組
    • n個の情報からなる複合情報
    • n組自身もn組を構成する1つの情報とみなすことができる
    • リストはn組を表現する方法の1つ
    • n組の要素は1番目の要素を第0要素として数え始める
  • 並び
    • 情報の個数を固定しないリストの使い方を「並び」という
  • carとcdr
    • car: リストの第0要素.カー.Contents of the Address part of Register number.
    • cdr: carの存在するリストからcarを取り除いたリスト.クダー.Contents of the Decrement part of Register number.
    • carはアトムでcdrはリスト
    • cdrはリストの先頭の括弧を一つ後ろに下げたものと覚える
    • アトムのcarやcdrはとれない
    • nilのcarやcdrはない(Common Lispではnilになる)
    • cdrのcdrのcarのcarなどはcaaddrなどと略記する方法がある.cdrのcar,つまりリストの第1要素を示すcadr(カーダー,カードゥル)などはよく使う.
  • S式
    • アトムとリストの総称
  • S式の観測装置
    • atom: アトムであるS式にtと答え,それ以外はnilと答える.ただしnilにもtと答える.
    • null: nilに対しt,それ以外にnilと答える.
  • 題付きの並び
    • carが特別な意味を表すと約束した並び
    • 関数を次のようなリストで表現できる
(gcd x y)
(max x y z)

第3講 解釈は評価なり…辞書なくして世は渡れず(p.33-)

  • 評価
    • (+ 5 3)などはただのリストであり,評価により8というアトムが生ずる
    • S式は評価によりS式を生む
    • 次のS式を評価してもaというアトムは返ってこない.aも評価されるので,aという演算の結果が(定義されていれば)帰ってくる.
(car (a b c))
    • 評価してほしくないS式は直前に'を置く.'hogeは(quote hoge)の略記.
(car '(a b c)) ;; => a
(car (quote (a b c))) ;; => a
  • LispにおけるプログラムとはS式の評価のこと
    • リストのcarが関数,cdrが引数
    • 数の評価は数自身になる(5と'5は同じ)
    • 名前を評価すると辞書にある(あれば)S式を返す
    • nilは評価するとnilを返す
  • 辞書
    • 始めはtならばtを返すということだけが書いてある
    • set関数で語彙を増やせる
(set 'x 'hoge) ;; xを評価するとhogeというアトムが返るようになる
    • setq関数を使うと第一引数の'を省略できる(Common Lispではいきなりsetqを使うとエラーになるのでdefvarなどを使う)
(setq x 'hoge)
    • set, setqなどを代入式と呼ぶ
  • 基本的な関数
    • car, cdr
      • リストのcarやcdrを返す
      • cadrなどはcarとcdr合わせて4つの組み合わせまで用意されているのが一般的
    • atom
      • 引数がatomならt,そうでないならnil
    • null
      • 引数がnilならt,そうでないならnil
    • set, setq
      • 第2引数を返す(S式の評価は必ずS式を生む)

第4講 基本関数を修了するや,突然,関数定義 なんと大それた…(p.49-)

  • list関数
    • 引数を順に並べたリストを返す
    • 引数は左から順に全て評価される
    • 呼出の度,新しいリスト(コピー)が作成される
(list 1 2 3) ;; => (1 2 3)
(list (+ 5 4) 'a 99) ;; => (9 a 99)
  • cons関数
    • リストを作成する関数としてlistより基本的な関数(listはconsだけの組み合わせで表現できるが逆は必ずしも可能ではない)
    • 第1引数をcar,第2引数をcdrとするリストが返る
    • 空でないlistのcdrはリストかnilなので,consの第2引数もリストかnilでなければならない
(cons 'a '(b c d)) ;; => (a b c d)
(cons 'a (cons 'b (cons 'c (cons 'd nil)))) ;; => (a b c d)
  • eq関数
    • 引数に与えられた2つのS式が同一ならばt,異なればnil
    • 見た目が同じでも実体が異なる場合(コピー)は同一とは見なさない
    • 整数は値が同じならば同一と見なす場合が多いが未定義のこともある(数の比較は普通=を使う)
    • 名前は文字が同じように並んでいるなら同一
  • defun関数
    • 多くのLispでは関数のための辞書を持ち,登録にdefun関数を使う
    • (defun 関数名 引数のリスト 関数本体)の形式で用いる
    • defunの引数はどれも評価されないので'は不要
(defun square (x) (* x x))
(square 5) ;; => 25
    • 関数実行時における仮引数への代入はLispだと束縛(binding)と呼ぶ

第5講 今度はcond, 再帰と再起を混同せぬように(p.66-)

  • cond
    • conditional expressionの略
(cond (条件1 帰結1)
      (条件2 帰結2)(条件n 帰結n))
    • (条件i 帰結i)をcond節と呼ぶ
    • cond節を上から順に評価し,もしcarが真ならばそれに続くS式を左から順に評価する
    • 全てのcond節のcarがnilならばcondはnilを返す

基本的な関数

意味
(numberp x) xは数か(~pという関数は引数が~か?と尋ねる)
(+ x1 x2 ... xn) Σx(*の場合は同様にΠ,-はx1-x2-...,/はx1/x2/...)
(= x y) x=yか
(/= x y) x≠yか
(abs x) xの絶対値
(truncate x) xの0方向への丸め
(floor x) x以下の最大の整数
(symbolp x) xはシンボルか
(consp x) xはリスト(nil除く)か
  • 再帰
    • リストの最後の要素を返す関数last-elem
(defun last-elem (x)
       (cond ((null x) nil)
             (t (last-elem2 x)))) ;; リストが空かどうかのチェック
(defun last-elem2 (x)
       (cond ((null (cdr x)) (car x))
             (t (last-elem2 (cdr x))))) ;; 他のcond節がnilだった場合常に評価させたいcond節はcarをtにする
    • Lispは最初,繰り返し動作は再帰だけで書くように設計された