(wat-aro)

無職から有職者にランクアップしました

scheme

OSXにGaucheのHEADをインストール

GaucheのHEADをインストールするにはリリースされた最新のGaucheが必要です. ここにはまりました. なぜか最新版の0.9.4でもビルドできなかったのでbrewでインストールしてから後で消しています. make install の後にbrew uninstall gaucheをすると必要なu…

Scheme修行のtryについて

Scheme修行作者: Daniel P. Friedman and Matthias Felleisen,元吉文男,横山晶一出版社/メーカー: オーム社発売日: 2011/06/15メディア: 単行本(ソフトカバー)購入: 3人 クリック: 46回この商品を含むブログ (10件) を見る p89の欄外で補足されているtryに…

Schemeでクイックソート

先日の納会でソートの話が少し出たのでクイックソートを書いてみました. 書きやすいのでGaucheで. まず普通に書いてみます. (define (quick lst) (if (null? lst) '() (let ((first (car lst))) (append (quick (filter (lambda (x) (< x first)) lst)) (…

プログラミング初心者がSICP(計算機プログラムの構造と解釈)を読んでみた

読む前の状態と動機 読み始めた時点でプログラミング歴約1年 もうひとつのscheme入門でプログラミングに入門するも,高階関数で挫折. Ruby本二冊,Rails Tutorialを二周. 他読み始めたけど途中で飽きた本が何冊か. 仕事(非IT)が忙しく,プログラミング…

SICP 問題 5.50

4.1節の超循環評価器を5.5で作った翻訳系でコンパイルする. 問題5.50 – SICP(計算機プログラムの構造と解釈)その302 : Serendip - Webデザイン・プログラミング http://himoiku.cocolog-nifty.com/blog/2008/07/sicp550_f385.html ここを参考にしました.…

SICP 問題 5.49

compileとassembleを機械計算として持ち,REPLを行うレジスタ計算機を設計する. はじめ,assembleを命令列の上でやる方法がわからずに,compile-and-assembleという手続きを作り, それを機械演算として登録してRCEPLを実装したが, 問題5.49 – SICP(計算…

SICP 問題 5.48

ECEVALのrepl上でコンパイル出来るようにする. これで動くかなって思ったら動いた. ただトレースした命令列を見ると, apply-dispatchからprimitive-procedureにジャンプせずに先頭に戻っている. なぜそうなるのかわからない. ;; 環境を拡張してprimitiv…

SICP 問題 5.47

コンパイルした手続きから積極制御評価器で定義した手続きを使えるようにする. (define (compile-procedure-call target linkage) (let ((primitive-branch (make-label 'primitive-branch)) (compiled-branch (make-label 'compiled-branch)) (compound-br…

SICP 問題 5.46

5.45と同様に今度はフィボナッチ数列の計算でそれぞれ比べる. gosh> (define fib ;;一回目以外は省略 (make-machine (list (list '< <) (list '- -) (list '+ +)) '(controller (assign continue (label fib-done)) fib-loop (test (op <) (reg n) (const 2…

SICP 問題 5.45

コンパイルした階乗計算,積極制御評価器の階乗計算,特殊目的計算機のプッシュ数,最大スタック深さを調べて比較する. まずはコンパイルしたものから gosh> (compile-and-go '(define (factorial n) (if (= n 1) 1 (* (factorial (- n 1)) n)))) (total-pu…

SICP 問題 5.44

基本手続きの名前を含む式の正しいコードを翻訳するため,翻訳時環境を調べるようにする. (cond ((self-evaluating? exp) (compile-self-evaluating exp target linkage)) ((variable? exp) (compile-variable exp target linkage ct-env)) ((quoted? exp) …

SICP 問題 5.43

内部定義を吐き出してコンパイルする. まず4.16で作ったscan-out-definesがこれ. (define (scan-out-defines body) (define (split-defines proc-body defines non-defines) (cond ((null? proc-body) (cons (reverse defines) (reverse non-defines))) ((…

SICP 問題 5.42

compile-variableとcompile-assignmentを文面アドレスを使った検索に対応 (define (compile-variable exp target linkage ct-env) (let ((address (find-variable exp ct-env))) (end-with-linkage linkage (if (eq? address 'not-found) (make-instruction-…

SICP 問題 5.41

翻訳時環境に対する変数の文面アドレスを返す手続きfind-variableの実装 (define (find-variable var ct-env) (define (env-loop frame-address env) (define (scan variable-address frame) (cond ((null? frame) (env-loop (+ frame-address 1) (enclosing…

SICP 問題 5.40

翻訳時環境を維持し,compile-lambda-bodyで拡張するように変更する. (define (compile-lambda-body exp proc-entry ct-env) ;; ct-envを追加 (let ((formals (lambda-parameters exp))) (append-instruction-sequences (make-instruction-sequence '(env p…

SICP 問題 5.39

文面アドレスと実行時環境とり値を検索するlexical-address-lookupと 値を変更するlexical-address-set!を実装する. ;;; 文面アドレスを使って変数の値を探す (define (lexical-address-lookup lex-add r-env) (let ((frame (frame-values (list-ref r-env …

SICP 問題 5.38d

+と*について任意個の被演算子の式が使えるように拡張する. ここに書いた手続きを変更もしくは追加する. 3つ以上の引数の時はarg1に畳み込んで計算していく. (define (compile-open-code exp target linkage ct-env) (cond ((= (length exp) 3) (compile…

SICP 問題 5.38c

元のcompileによる出力と5.38abでcompile-open-codeを追加したコンパイラの出力を比べる. 命令列が約半分になっている. compile-open-codeを追加したコンパイラの出力 ((env) (val) ((assign val (op make-compiled-procedure) (label entry1) (reg env)) …

SICP 問題 5.38ab

+ - * = はopen-codeとして (reg val (op +) (reg arg1) (reg arg2)) の形で処理できるようにする. (define (open-code? exp) (memq (car exp) '(= * - +))) (define (compile exp target linkage) (cond ((self-evaluating? exp) (compile-self-evaluating…

SICP 5.5.5 翻訳系

schemeの式をレジスタマシンのシミュレータの命令列に翻訳するコード. 理解するためにコメントを出来るだけつけた (load "./eval.scm") ;;; make-branchのための手続き (define label-counter 0) (define (new-label-number) (set! label-counter (+ 1 labe…

SICP 問題 5.37

preservingを修正して常にsaveとrestoreをさせ,修正前と後を比較する. 修正前 (define (preserving regs seq1 seq2) (if (null? regs) (append-instruction-sequences seq1 seq2) (let ((first-reg (car regs))) ;first-regが (if (and (needs-register? s…

SICP 問題 5.36

本文の被演算子の適用順はoperandをreverseしてから連結していくので右から左になっている. これを左から右に変更する. ;;; 最初のreverseをなくす (define (construct-arglist operand-codes) (if (null? operand-codes) (make-instruction-sequence '() …

SICP 問題 5.35

本文の図5.18 の翻訳出力の例から翻訳前の式を導く. 答え (compile '(define (f x) (+ x (g (+ x 2)))) 'val 'next) 実行結果(整形済み) ((env) (val) ((assign val (op make-compiled-procedure) (label entry12) (reg env)) (goto (label after-lambda1…

SICP 問題 5.34

反復的階乗手続きをコンパイルし,再帰版との本質的な違いを示せ. 反復的階乗手続きの内容を説明する. (compile '(define (factorial n) (define (iter product counter) (if (> counter n) product (iter (* counter product) (+ counter 1)))) (iter 1 1…

SICP 問題 5.33

以下の2つの翻訳結果を比較してその相違を説明する. (compile '(define (factorial n) (if (= n 1) 1 (* (factorial (- n 1)) n))) 'val 'next) (compile '(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1))))) 'val 'next) 一つ目を出力して…

SICP 問題 5.32

a: 演算子が記号である場合の組み合わせの式を別のクラスと認識し,そういう式を最適化する. operatorがvariableであればenvをsaveしない. ev-application (save continue) (assign unev (op operands) (reg exp)) (assign exp (op operator) (reg exp)) (…

SICP 問題 5.31

どのタイミングで以下の式を評価する際にどのタイミング何を退避して復帰するか (f 'x 'y) 'x 'yはシンボルなのでこれ以上の評価が必要ないので 何も退避しなくてよい. ((f) 'x 'y) 'x 'yがシンボルなので上と同じく退避の必要ない. (f (g 'x) y) fを評価…

SICP 問題 5.30b

primitive-procedure のエラーもECEVAL上で扱えるようにする. まず基盤のschemeから手続きを登録するときに事前チェックするように変更する. もしエラーになるような引数が与えられた時には('failed . 'hoge-syntax-error)を返す. primitive-applyでvalに…

SICP 問題 5.30a

評価プロセスでのエラーをschemeでなくecevalで捕まえてREPLを継続する. ;;; 5.2 で実装したシミュレータ.トレース機能追加済み. ;;; 初めてassignするレジスタを登録していくタイプ (load "./register-machine-simulator.scm") ;;; 4.1で実装した評価器 …

SICP 問題 5.29

a: n≧2の時のfib(n)を計算するのに必要なスタックの最大深さのnを使った式を与えよ. b: 同じ条件でfib(n)のプッシュの総数を求める ;;; EC-Eval input: (define (fib n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))) (total-pushes = 3 maximum-depth …