Comments
Description
Transcript
講義概要 プログラミング言語の分類 LISP
教科書と参考文献 Scheme による記号処理入門(1994): 計算機代数入門 猪股俊光，益崎真治，森北出版 2003.4.15 第1回 http://www.morikita.co.jp Scheme によるプログラミング入門と演習 (1996): 角川裕次， 中川重和（倉敷芸術科学大学） http://kakugawa.aial.hiroshima-u.ac.jp/Hacks/ LISP入門(1986): 黒川利明，培風館 講義概要 プログラミング言語の分類 手続き型．．．C, FORTRAN, Pascal LISP(Scheme)の紹介 数学的フォーマリズムに基づくプログラミング Schemeプログラミング 論理型．．．Prolog 計算機代数 述語論理の体系をプログラミング言語化 オブジェクト指向型．．．C++, Java 数式処理システムの作成 LISP プログラム＝アルゴリズム＋データ構造 記号処理とは？… 数値計算以外の計算を指す 記号とは？ 記号という言葉の解釈 日常 文字にたいしての記号 地図上の郵便局のマークなど 計算機の分野 文字も記号の仲間 数値と数値以外 はすべて記号 記号処理の多くの概念が LISP の中に実現されている LISP の適用される分野 計算機の命令列を逐次実行 データの転送経路やタイミングを推定 関数型．．．LISP 再帰処理 現行の計算機の動作原理を反映して設計 Ｓ式・リスト Scheme処理系 計算機代数 人工知能 基本アルゴリズムと その実装について学ぶ LISP の方言である Scheme を学ぶ 効率のよいプログラムを作成するには、アルゴ リズムだけでなく、データ構造にも考慮する必 要がある ＬＩＳＰで扱うデータ構造は全てリスト ＬＩＳＰでは、プログラムもプログラムが扱う データもすべてリストで表現される 大雑把にいうと、リストとは要素を括弧対でく くったもの 括弧の洪水に悩まされるかも… 1 Ｓ−式 S-式とリスト S-式 = Symbolic expression アトムとは，数字の並びと 数字以外の文字で始まる文字列の並び S-式の定義 このように略記する アトムと () はS-式である S1 と S2 がS-式ならば，(S1 . S2) はS-式である xy, (), (a . ()) , (1 . (2 . 3)) 1z, ((), ○ ○ ○ × Si はS-式 (S1 S2 ・ ・ ・ Sn . Sn+1) （）は，空リスト（null list）と呼ばれ， S-式の例 (S1 . (S2 . ( ・ ・ ・. ( Sn . Sn+1) ・・))) 特に Sn+1 が () のとき， nilと書くこともある (a . b) （s1 . s2）の， s1 をcar部，s2を cdr部と呼ぶ リスト (S1 S2 ・・・Sn) (1 . (2 . 3)) => (1 2 . 3) (1 . (2 . (3 . ()))) => (1 2 3) リストを用いた問題解決のための表現 (リストに意味をもたせることができる) ボックス記法によるS-式の表現 (S1) = (S1 . ()) (S1 . S2) 線形リスト a b + 木 S1 S2 - (foo (bar baz)) a 連想リスト foo bar bar baz (* 3 x) (* * x 2) α+β (+ α β) ⇓ x 2 + 3x * 8 A B 80 90 C 70 b 4 ((A . 80) (B . 90) (C . 70)) Schemeのインストール 多項式の表現 3x x2 (+ (- a 8) (* b 4)) S1 ((foo bar)) foo (a b c) c Chez Schemeをゲット Chez Editをゲット (+ (* * x 2) (* 3 x)) http://www.scheme.c om/ http://www5a.biglobe .ne.jp/~sasagawa/ML Edit/Scheme/index.ht ml Scheme環境が整った 2 構文要素(1) 構文要素(2) 述語とデータ操作手続きの命名法 識別子…変数名や手続き名として使用 アトムから整数を除いたもの 構文キーワード 既に使用法が定められている => do or and else qausiquote begin if quote case lambda set! cond let unquote define let* Unquote-splicing delay letrec 空白とコメント 空白で識別子を区切る ；はコメント、行末まで 真偽値 真 偽 ＃ｆ以外の値 ＃ｆ 記憶領域 Scheme処理系の流れ(read-eval-print) 変数 式 > (car ‘(a b c)) a > 入力を受け取る それの評価 pred?...predが述語であること side!...sideが記憶領域の内容を操作する手続きの名 前であること インタプリタ方式 入力の単位は式および定義 「評価」＝「計算」 式・定義・評価については後で説明 結果の表示 束縛 変数の値 変数 データが格納される記憶場所に付けた名前 リテラル クオート(‘exp)，真偽値（#t, #f），数，文字定数， 文字列 手続き呼び出し （op arg1 … ） ラムダ式 （lambda (x1 … xn) e1 … em） 記憶領域 条件式 var (if pred e1 e2) expr 束縛 代入 (set! var expr) 記憶領域 評価 定義 変数の定義 式の評価 （define var exp） 手続きの定義 ラムダ式に名前を付ける (define proc (lambda (x1 … xn) e1 … em)) (define (var x1 … xn) e1 … em) 記憶領域 var 束縛 exp 束縛 束縛 expr 変数が束縛されている記憶場所に格納されてい る値を求めること （var => varの値=expr） プログラムの実行と共に変数と記憶場所との束縛関係 は変化している 手続きの評価 （op arg1 … ） (+ 10 (* 3 2)) => (+ 10 6) => 16 引数 arg1 … を評価し，それらの値をもとに計算する 記憶領域 proc var (lambda …) 3 Quoteについて Schemeによるプログラミング > (+ (* (− 5 4 ) (− 3 1)) 10 ) ‘foo = (quote foo) 12 Schemeのプログラムは式と定義の集まりである 評価 いずれの式や手続きからも実行可能 計算機内部での式の評価順序 引数の評価を最初に行い，次に式の評価を実行 Schemeにおいては，データをＳ式で表現するの みならず，プログラムもＳ式で表現する 演習（教科書P13, 1.4） ‘ （quoteと読む）は略記 ‘foo Æ foo (quote foo) Æ foo ‘(+ 1 3) Æ (+ 1 3) … ○ ‘(+ 1 3) Æ (+ 1 3) … × (+ 1 3) Æ 4 … ○ 演習解答(1) (a b . c) 次のリストをボックス記法によって表現せ よ (a b . c) (a b) (a (b)) ((a) b) ((a b) c) (a (b (c))) a (a b) b c a b ((a) b) (a (b)) 教科書 2.2 2.3 b a b 演習解答(2) ((a b) c) もう少し演習 (a (b (c))) c 次のリストをボックス記法によって表現せ よ (a) ((a)) (a b c) ((a) (b) (c)) a b a a b c car部はボックスの左へ cdr部はボックスの右へ 4