とりとめのないことを書いております。
by tempurature
カテゴリ
全体
プログラミング
scheme
verilog
未分類
以前の記事
2016年 04月
2016年 03月
2016年 02月
2016年 01月
2015年 12月
2015年 11月
2015年 10月
2015年 09月
2015年 08月
2015年 07月
2015年 06月
2015年 03月
お気に入りブログ
PHPで競技プログラミング
メモ帳
最新のトラックバック
ライフログ
検索
タグ
人気ジャンル
ブログパーツ
最新の記事
情報処理技術者試験 お疲れ様..
at 2016-04-17 18:55
基本情報技術者試験 平成27..
at 2016-04-14 04:48
基本情報技術者試験 平成27..
at 2016-04-13 23:03
苦い薬(ハーブ、サプリメント..
at 2016-04-09 14:03
「おバカ度チェックリスト」を..
at 2016-03-24 09:54
外部リンク
ファン
記事ランキング
ブログジャンル
画像一覧
タグ:scheme ( 11 ) タグの人気記事
【scheme/racket】rangeのかわりにiotaを使う
pythonでは、range関数が用意されており、等差数列のシーケンス(リストではない!)を素早く作ることができます。

>>> range
<class 'range'>
>>> range(5)
range(0, 5)

racketでは、pythonのrangeと似たrange関数が用意されています。

> (range 5)
'(0 1 2 3 4)
> (list? (range 5))
#t

schemeでは、SRFI 1のiota関数がそれに該当します。ただし、仕様は異なります。
iota関数はracketでもモジュールをロードすることで使用することができます。


※0から(n-1)の数を並べる

#lang racket
(require srfi/1)

> (range 5)
'(0 1 2 3 4)
> (iota 5)
'(0 1 2 3 4)


※mから(n-1)の数を並べる

> (range 1 11) ; 1から(11-1)までの整数を列挙
'(1 2 3 4 5 6 7 8 9 10)
> (iota 10 1) ; 1から10個の整数を列挙
'(1 2 3 4 5 6 7 8 9 10)


※mからstep刻みに等差数列を並べる

> (range 3 12 4) ; 初項3、公差4での等差数列で、12よりも小さいもの
'(3 7 11)
> (iota 3 3 4) ; 初項3、公差4、項数3の等差数列
'(3 7 11)
> (range 3 -12 -4) ; 初項3、公差-4の等差数列で、-12よりも大きいもの
'(3 -1 -5 -9)
> (iota 4 3 -4) ; 初項3、公差-4、項数4の等差数列
'(3 -1 -5 -9)

> (range 1 5 0.5)
'(1 1.5 2.0 2.5 3.0 3.5 4.0 4.5)
> (iota 8 1 0.5)
'(1 1.5 2.0 2.5 3.0 3.5 4.0 4.5)

!!注意!! pythonのrange関数は整数のみを受け付けます。

> (range 0+i 3+i 0+i)
[Error]
> (iota 3 0+i 1+i)
'(0+1i 1+2i 2+3i)

range関数では複素数の等差数列を作ることができませんでしたが、iota関数ではできました。


[PR]
by tempurature | 2015-12-13 02:32 | scheme
GaucheをWindowsで使う
Gaucheの本家では、WindowsにおいてはGaucheをEmacs環境上で使用することを強く推奨しています。けれども私はEmacsが嫌いです。

以下では私なりのGauche環境を紹介します。

i) Widowsインストーラパッケージ(msi)でGaucheをインストールする
ii) Cygwinをインストールする
iii) .bashrc等に「alias go='gosh -i -I .'」の一行を追加する
iv) Gaucheのソースコードを作成・編集する時は、「notepad <filename>」とCygwinのコマンドラインに入力する
v) Gaucheのソースコードの先頭に必ず「;; -*- coding: shift_jis -*-」を追加する
vi) goshで変な動作になったらすぐ[Ctrl+C]で抜ける

(iv)でnotepadを使うのは、改行コードがCR+LFであることを保証するためです。(i)でCygwin上でGaucheをコンパイルしないのは、それが素人には難しいからです。また、コマンドプロンプト上でgoshを起動しても、日本語が文字化けします。(iii)のおまじないで、Gaucheがracket並に使い勝手が良くなるはずです。

以上です

【2015.11.22 追記】
上記の設定だと、(char-alphabetic? #\あ)が#tになる不具合があります。
Cygwinの代わりにgit Bashで試しても同じでした。

ちなみに、コマンドプロンプトとPowershellでは、(char-alphabetic? #\あ)が#fとなり正しいのですが、ターミナルの文字コードをutf-8にできないのでgoshの文字化けを解消できないです。


[PR]
by tempurature | 2015-11-11 22:48 | scheme
カメとウサギのアルゴリズム、もしくは・・・
Exercise 3.19について他の人の解答を見てみると、メモリ消費量を抑えつつ線形時間で完了するやり方があるということで、うならされました。

私の考えたdepthを使ったやり方は、リストをカントールの証明のように操作する方法ですが、それだとリスト長(もしくは無限ループの大きさ)に対して2乗オーダで計算時間が増えます。

Barry Allisonさんのコードでは「カメとウサギのアルゴリズム」として紹介されていた方法ですが、最初このコードを読んでも何をやっているのかわかりませんでした。

その方法は、リストの先頭から、1歩ずつ進むポインタ(カメ)と2歩ずつ進むポインタ(ウサギ)を同時に動かしてやるやり方なのですが、直感的にはカメとウサギがどんどん離れていくのでうまくいかないように思えます。

しかし、循環リストの構造としては、L = (a1 ... an b1 ... bm b1 ... bm b1 ...)というような構造をしていて、2つのポインタがanより後ろにあれば、ポインタの距離がmの整数倍の条件で一致するという特徴があります。

なので、カメポインタで必ず1歩は進むようにすればとっととanよりも先に進むことができ、カメポインタとウサギポインタの距離を常に離していくことで距離mを同時に探索することもできるということです。アタマいい〜

以下は私がアレンジした「カメとウサギのアルゴリズム」のコードです。
(optional lineの行はあってもなくてもいいです)

(define (cycle? lst)
  (define (go-downstairs walker runner)
    (cond ((null? runner) #f)
          ((null? (cdr runner)) #f)
          ((eq? runner walker) #t)
          ;((eq? (cdr runner) walker) #t) <- optional line ->
          (#t (go-downstairs (cdr walker) (cddr runner)))))
  (and (not (null? lst))
       (not (null? (cdr lst)))
       (go-downstairs lst (cddr lst))))


[PR]
by tempurature | 2015-08-26 00:59 | scheme
SICP Exercise 3.18, 3.19の解答
Exercise 3.18は循環リストを判別せよという問題、Exercise 3.19はメモリを一定以上消費しないようにそれを実装せよという問題でした。

; Exercise 3.18

(define (check-circulation lst)
  (define (get-next tadpole)
    (cond ((null? (cdr tadpole)) #f)
          ((memq (cadr tadpole) (car tadpole)) #t)
          (#t (cons (cons (cadr tadpole) (car tadpole))
                    (cddr tadpole)))))
  (define (iter tadpole)
    (if (pair? tadpole) (iter (get-next tadpole)) tadpole))
  (iter (cons '() lst)))

; Exercise 3.19

(define (find elem lst depth)
  (cond ((<= depth 0) #f)
        ((null? lst) #f)
        ((eq? elem lst) #t)
        (#t (find elem (cdr lst) (- depth 1)))))
(define (infinite-loop? lst)
  (define (go-downstairs lst node depth)
    (cond ((null? node) #f)
          ((find node lst depth) #t)
          (#t (go-downstairs lst (cdr node) (+ depth 1)))))
  (go-downstairs lst lst 0))


[PR]
by tempurature | 2015-08-25 23:15 | scheme
SICP Exercise 3.17 の解答
この問題のヒントが気に入らなくて、別回答を考えました。

(define (flatten lst)
  (cond ((null? lst) '())
        ((not (list? lst)) '())
        (#t (append (list lst)
                    (flatten (car lst))
                    (flatten (cdr lst))))))
(define (filter proc lst)
  (cond ((null? lst) '())
        ((proc (car lst)) (cons (car lst) (filter proc (cdr lst))))
        (#t (filter proc (cdr lst)))))
(define (uniq lst)
  (define (iter res rest)
    (if (null? rest)
        res
        (let ((current (filter (lambda (x) (eq? x (car rest)))
                               (cdr rest))))
          (if (null? current) (iter (cons (car rest) res) (cdr rest))
                              (iter res (cdr rest))))))
  (iter '() lst))
(define (count-pairs x)
  (length (uniq (flatten x))))

[PR]
by tempurature | 2015-08-23 15:13 | scheme
とあるSICP 3章の環境の説明図の簡単なバージョン
SICPで⦿⦿(ニップルマーク?)が出てきた時、最初これの意味がわかりませんでした。なのでSICPの説明図より簡単な場合について作図してみました。合ってなかったらごめんなさい。

c0364169_21311784.png

<ソースコード>

(define (add a b) (+ a b))
(define (make-add-proc a)
(define (dispatch b) (add a b))
dispatch)
(define add-10 (make-add-proc 10))


[PR]
by tempurature | 2015-08-22 21:31 | scheme
SICP ex.3.9の代わりに変なコード書いてみた
問題3.9が例のごとく面倒な作図問題で、環境の話はDr. RacketをREPLしているうちになんとなく理解していたので、応用問題を自分で考えました。

Q. 自分自身を書き換える手続きを定義せよ。

A.
(define (f x) #f)
(let* ((f1 (lambda () #f))
(f2 (lambda () (set! f f1) 2)))
(set! f1 (lambda () (set! f f2) 1))
(set! f f1))

または
(define (f)
  (define (f1) (set! f f2) 1)
  (define (f2) (set! f f1) 2)
  (f1))


[PR]
by tempurature | 2015-08-15 23:26 | scheme
どうしてracketは流行らないのか?
私のより新しい意見はこちらになります。



racketは、PLTというグループが開発するlisp系言語です。racketはもともとPLT schemeという名前で、scheme実装の1つでしたが、schemeとCommon Lispを踏まえた新しいlispを作るという目標のもとに分化しました。

racketの1番の特徴は、windows, macOS, linuxで使えるGUIベースの開発環境 Dr. Racketであり、Common Lisp, Schemeではこれほど簡単に導入することができる環境は私の知る限りではないです。

とはいえ、日本ではracketはほとんど知られておらず、アメリカでもCommon Lisp, Schemeほどの人気はない言語です。

現在私が知る限りにおいて、なぜracketが流行っていないのかを考えてみます。


< 1 > racketの実装は実行速度が遅い

lispのコミュニティの中では、schemeに比べてracketの実行速度が遅いという評判です。実際そうなのか私自身把握しているわけでなないですが、そういう書き込みは見ています。

< 2 > 枯れた言語ではない

C, scheme, Common Lispなどは古い言語なので、ドキュメントやライブラリが充実しています。また、仕様変更が頻繁におこらないので、レガシー資産を使うことができ、また、自分の書いたコードを10年後にも使えるだろうという安心感もあります。

pythonやphpなどは人気のある言語ですが、現在も言語の仕様変更が行われているのでコードの寿命が短いという問題があります。racketも生まれたばかりの言語なので同様の問題が発生します。

< 3 > lispの慣用とは異なる

racketはschemeとほぼ同じような言語仕様ですが、scheme, Common Lispとは相容れないような違いがあります。

・識別子(identifier)は大文字と小文字を区別する

scheme, Common Lispでは大文字・小文字を区別しないので、lisperが大文字の名前と小文字の名前を使っているracketコードを見ると混乱します。

・文字コードはunicode

schemeやCommon Lispでは独特の文字列処理体系を持っていますが、racketではpythonやDに似たunicodeによる文字列処理を行っています。

これらの特徴は、lispを他の言語と併用しようと考えた場合には長所となります。racketはモダン言語の1つとしてのポテンシャルは持っていると思います。

< 4 > 実装の種類が少ない

scheme, Common Lispは商用、非商用の実装が多数あり、実行速度や拡張機能などのニーズで色々な実装を試すことができます。racketはPLTで配布している実装だけなので、素人向けではありますが、プロ向けではないのだと思います。



racketはscheme, Common Lispに比べて日本語の情報が少ないですが、導入の手軽さでは群を抜いており、GUI, webサーバー, 3Dグラフィックスのライブラリも一通り揃ってますので、趣味のプログラミング用途では一押しです。

racketが有用であるかどうかは難しいところですが、racketの日本語の情報を提供することで、多くの人が言語に関してより正しい選択ができるようにしていけたらと考えています。


[PR]
by tempurature | 2015-07-26 16:08 | scheme
SICPに対する批判
SICPについてのおもしろい批判をされている方がいらっしゃったのであげておきます。


私もOCaml興味あったんですけど、一週間くらいでできるのであればやってみたいなと。


[PR]
by tempurature | 2015-07-05 15:28 | scheme
【racket】星型を描く
c0364169_00445226.png
#lang racket/gui

(define x-size 300)
(define y-size 300)
(define (intersection-point line1 line2)
  (define d1 (map - (second line1) (first line1)))
  (define d2 (map - (second line2) (first line2)))
  (define norm-d2 (sqrt (foldr + 0 (map * d2 d2))))
  (define n2 (map (lambda (x) (/ x norm-d2)) (list (second d2) (- (first d2)))))
  (define (inner-* p1 p2) (foldr + 0 (map * p1 p2)))
  (define param1 (/ (inner-* (map - (first line2) (first line1)) n2) (inner-* d1 n2)))
  (map + (first line1) (map (lambda (x) (* param1 x)) d1)))
(define (regular-polygon n)
  (define angles (map (lambda (m) (* 2.0 pi (/ m n))) (range 0 n)))
  (map (lambda (phi) (list (sin (- phi)) (cos (- phi)))) angles))
(define (shift x y) (lambda (p) (map + p (list x y))))
(define (magnify x y) (lambda (p) (map * p (list x y))))
(define pentagon (map (shift (/ x-size 2) (/ y-size 2))
                      (map (magnify (/ x-size 2) (/ (- y-size) 2)) (regular-polygon 5))))
(define intersection-index-pairs
  (map (lambda (n) (map (lambda (m) (remainder (+ n m) 5)) '(0 2 1 4))) (range 0 5)))
(define intersections
  (map (lambda (pair) (intersection-point (list (list-ref pentagon (first pair))
                                                (list-ref pentagon (second pair)))
                                          (list (list-ref pentagon (third pair))
                                                (list-ref pentagon (fourth pair)))))
       intersection-index-pairs))
(define lines
  (append (map (lambda (n) (append (list-ref pentagon n) (list-ref intersections n))) (range 0 5))
          (map (lambda (n) (append (list-ref intersections n)
                                   (list-ref pentagon (remainder (+ n 1) 5)))) (range 0 5))))

(define target (make-bitmap x-size y-size))
(define dc (new bitmap-dc% [bitmap target]))
(send dc set-pen "blue" 1 'solid)
(for-each (lambda (line) (send dc draw-line (first line) (second line) (third line) (fourth line)))
     lines)
(send target save-file "star.png" 'png)

[PR]
by tempurature | 2015-07-01 00:45 | scheme