バックトラックで戻らないpermanent-set!の実装 ;; permanent-set! (define (analyze-permanent-assignment exp) (let ((var (assignment-variable exp)) (vproc (analyze (assignment-value exp)))) (lambda (env succeed fail) (vproc env (lambda (val fa…

ランダムな順に探すrambを実装する． (use srfi-27) (define (random-car lst) (list-ref lst (random-integer (length lst)))) (define (rember item lst) (cond ((null? lst) '()) ((eq? (car lst) item) (cdr lst)) (else (cons (car lst) (rember item (…

(define true #t) (define false #f) ;; eval (define (ambeval exp env succeed fail) ((analyze exp) env succeed fail)) (define (analyze exp) (cond ((self-evaluating? exp) (analyze-self-evaluating exp)) ((quoted? exp) (analyze-quoted exp)) ((v…

きっかけはTwitter． @wat_aro どの処理系使ってるかわからないですがgaucheのswank-gaucheみたいに対応されてたりしませんか？— lispドラッグ常習者 (@rayfill) 2016, 1月 12 早速インストール． READMEに 設定方法 `dot.emacs'の内容を.emacsにコピーしてs…

自然言語の構文解析用プログラムを少し改造するだけで文章の生成ができる． (define (an-element-of items) (require (not (null? items))) (amb (car items) (amb (cdr items)))) (define (parse-word word-list) (list (car word-list) (an-element-of (cd…

adjectiveのみ追加する． ;; 冠詞の解析をparse-article-phraseにしてそこでmaybe-extendに進めばadjectiveも解析されるようにする． (define (parse-simple-noun-phrase) (list 'simple-noun-phrase (parse-article-phrase) (parse-word nouns))) (define (…

(define (parse-verb-phrase) (amb (parse-word verbs) (list 'verb-phrase (parse-verb-phrase) (parse-prepositional-phrase)))) (parse '(the student with the cat sleeps in the class))これを例に考える． verbが問題なのでsleeps in the classだけに…

構文解析器が右から左に非演算子を評価する時 perse-noun-phrase中の (amb noun-phrase (maybe-extend (list 'noun-phrase noun-phrase (parse-prepositional-phrase)))) で，maybe-extendが先に評価されてしまう． すると，実際に名詞が先にきた場合はmaybe…

The professor lectures to the student in the class with the cat. これの５通りの構文解析結果を示す． まずはprofessor に in the class とwith the cat が掛かっている場合． 次はprofessorにwith the cat , student にin the classがかかっている場合…

eight-queenをamb評価器を用いて解く． ただし，まだamb評価器は実装していないのでコードだけ． (define (eight-queen) (define (cross? a b) (= (/ (/ (car a) (car b)) (abs (- (cdr a) (cdr b)))) 1)) (let ((chess (iota 8 1))) (let ((one (cons 1 (am…

まずは素直に問題文に出てくる通りに書いてみる． (define (kansas-state-enginner) (let ((moore (cons (amb 'mary 'gabrielle 'lorna 'rosalind 'melissa) (amb 'mary 'gabrielle 'lorna 'rosalind 'melissa))) (downing (cons (amb 'mary 'gabrielle 'lor…

どちらかが正しいってどうやればいいのか思いつけず， ここを見たらヒントがあったのでその通り排他的論理和を作って解きました． SICP 第4章 Exercise 難易度リスト ( 4.1 ～ 4.79 ) | きのこる庭 (define (xor x y) (or (and x (not y)) (and (not x) y)))…

多住居手続きをschemeで実装． (use util.combinations) (use srfi-1) (define (multiple-dwelling) (filter (lambda (x) (let ((baker (first x)) (cooper (second x)) (fletcher (third x)) (miller (fourth x)) (smith (fifth x))) (and (not (= baker 5)…

人の階への割り当ての組みは，相異なるという要求の前では55通りある． 要求の後では5!通りになる． ambで生成してすぐにテストすることで効率的な手続き (define (multiple-dwelling) (let ((baker (amb 1 2 3 4 5))) (require (not (= baker 5))) (let ((c…

制限の順番は解には影響しないが，その時間には影響する． 失敗が多い制限ほど先にテストするほうが実行速度は速くなる． ;; 本来のmultiple-dwelling (define (multiple-dwelling) (let ((baker (amb 1 2 3 4 5)) (cooper (amb 1 2 3 4 5)) (fletcher (amb …

これを手で解けとな．．． B≠5 C≠1 F≠1 F≠5 C C≠5 |F-C| ≠ 1 答えは5通り． 計算機プログラムの構造と解釈 第2版作者: ハロルドエイブルソン,ジュリーサスマン,ジェラルド・ジェイサスマン,Harold Abelson,Julie Sussman,Gerald Jay Sussman,和田英一出版社/…

(define (a-pythagorean-triple-between low high) (let ((i (an-integer-between low high)) (hsq (* high high))) (let ((j (an-integer-between i high))) (let ((ksq (+ (* i i) (* j j)))) (require (>= hsq ksq)) (let ((k (sqrt ksq))) (require (int…

(define (a-pythagorean-triple-between low high) (let ((i (an-integer-between low high))) (let ((j (an-integer-between i high))) (let ((k (an-integer-between j high))) (require (= (+ (* i i) (* j j)) (* k k))) (list i j k))))) ;; an-integer…

二つの与えられた限界の間の整数を返す手続き (define (an-integer-between low high) (require (<= low high)) (amb low (an-integer-between (+ low 1) high))) 計算機プログラムの構造と解釈 第2版作者: ハロルドエイブルソン,ジュリーサスマン,ジェラル…

遅延対とリストを正当に印字できるようにする． consへのタグづけがどうしてもうまくいかなくてここを参考にしました． SICP Exercise 4.34 | Weiqun Zhang's Blog 前回からの変更箇所のみ (define (eval exp env) (cond ((self-evaluating? exp) exp) ((var…

遅延リストの実装に合わせて，quoteを遅延リストに対応させる． (car '(a b c))で正しくaが表示できるようにする． make-lambdaの(make-quote (car obj))のところ，始め(car obj)だけにしていたら， 数字ではうまくいくのに'(a b c)だとunbound variable: a…

遅延度の高い遅延リストではcar部も遅延されているので未定義の変数を使って構成するできる． ;;; M-Eval input: (define my-stream (cons x y)) ;;; M-Eval value: ok ;;; M-Eval input: my-stream ;;; M-Eval value: (compound-procedure (m) ((m x y)) <procedure-env>) </procedure-env>…

手続きは引数を全て評価してoperatorに渡す． 特殊形式は引数を全て評価するとは限らない． ここではdefineについて見てみる． defineは第１引数は評価せず，第２引数を評価した値を第１引数に束縛する． (define x (+ 1 2)) (+ 1 2) 3 (define x 3) x 3 次…

(define (f a (b lazy) c (d lazy-memo)) ...) といった形で部分的に遅延評価やメモ化する遅延評価を実装する． 元となるのは4.30までで作っていた遅延評価器． まず変更した部分を書く． ;; メモ化する評価器 (define (force-it obj) (cond ((thunk? obj) (…

並びの中の式は最後まで評価されないのではないかというCy D. Fectの心配に答える． a ;; 元のeval-sequence (define (eval-sequence exps env) (cond ((last-exp? exps) (eval (first-exp exps) env)) (else (eval (first-exp exps) env) (eval-sequence (r…

前回のSICP問題4.29で遅延評価する評価器でメモ化しない場合に，する場合と比べてはるかに遅くなるプログラムの例としてフィボナッチを書きました． ただ，あまりに差が大きくてなぜそうなるのかがわからなかったので考えてみました． 評価器は最後に載せて…

メモ化しないとはるかに遅くなるプログラムの例として 再帰でフィボナッチ数列の第n項を求める手続きを定義する． (define (fib n) (let iter ((a 0) (b 1) (count n)) (if (= count 0) a (iter b (+ a b) (- count 1))))) ;; メモ化するforce-it (define (f…

引数に手続きをとる手続きを考える． (define (foo bar) (bar 'a)) 引数はすべてthunkなので(bar 'a)でbarをevalしても手続きとならない． applyでoperatorをactual-valueを使わないと手続きを引数に取る場合に困る．

遅延評価 ;;; M-Eval input: (define count 0) ;;; M-Eval value: ok ;;; M-Eval input: (define (id x) (set! count (+ count 1)) x) ;;; M-Eval value: ok ;;; M-Eval input: (define w (id (id 10))) ;;; M-Eval value: ok ;;; M-Eval input: count ;;; M…

カリー化や部分適用の話がTwitterで流れてきたのでマクロの練習として書いてみました． ;; lambda式を引数に取り，カリー化されたlambda式を返す ;; いらなかった ;; (define-syntax curry ;; (syntax-rules (lambda) ;; 修正 ;; [(_ (lambda (arg) body ...…