Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2008-07-18

Getting Started in *LISP (12)

| 20:38 | Getting Started in *LISP (12) - わだばLisperになる を含むブックマーク はてなブックマーク - Getting Started in *LISP (12) - わだばLisperになる

こちらも放置しておりました、*Lispのチュートリアル。

同じく細かく進めて行くことにしました。

3.3 Communication Operators

データをCPU間でやりとりすることを"コミュニケーション"と表現することにする。

コミュニケーションには2種類あって、ルータコミュニケーションと、グリッドコミュニケーションがある。

3.3.1 Router Communication - General-Purpose Data Exchange

CM(コネクションマシン)では、各CPUは接続されていて、互いに通信ができるネットワークを持つ。これをルータと呼ぶらしい。

各プロセッサには、番地があるので、(self-address!!で取得可能)、これを利用してデータを特定のプロセッサ間で通信できる。

3.3.2 The Router Communication Opetators of *Lisp

ルータコミュニケーションに使用するオペレータには

  • *pset

あるプロセッサからデータを対象のプロセッサに送信する。パラレル動作。

  • pref!!

あるプロセッサが対象のプロセッサよりデータを取得。パラレル動作。

の2種類がある。

;; *pset

*number-of-processors-limit*
;==> 256

(*let (data)
  (*pset :no-collisions
         (self-address!!) ;送信元番地
         data             ;格納場所
         (-!! *number-of-processors-limit* ;着信番地
              (self-address!!)
              1))
  ;; 表示
  (ppp data))
;>>> 255 254 253 252 251 250 249 248 247 246 
;==>NIL

*psetは、(*pset combiner source-pvar dest-pvar send-address-pvar ...)という形式

  • 上の例の場合、自分の番地を値として送信。
  • dataは格納されるpvar
  • (-!! 〜)の部分は、送信先アドレス

つまり、255番プロセッサが、255という値を、0番プロセッサに送信、結果として、pvarの0番目に255が格納される。

次回3.3.3より再開

SERIESでツリーマッチング

| 01:36 | SERIESでツリーマッチング - わだばLisperになる を含むブックマーク はてなブックマーク - SERIESでツリーマッチング - わだばLisperになる

独習 Scheme 三週間 Teach Yourself Scheme in Fixnum Daysでは、ジェネレータを使うことによって、2つのツリーをflattenして比較するよりも効率の良いツリーマッチングを実現しているわけなのですが、SERIESは遅延評価なので効率良く似たようなことができるだろうということで色々考えてみました。

(same-fringe? '(1 (2 3)) '((1 2) 3))
(same-fringe? '(1 (2 3)) '(1 2 3))
;=> T

(same-fringe? '(1 (2 3)) '((1 2) 3 4))
;=> nil

;; コード
(use-package :series)
(series::install) ;#Mや、#Z等のリーダーマクロを使うため

;; 1
(defun same-fringe? (tree1 tree2)
  (let ((t1 (scan-lists-of-lists-fringe tree1))
        (t2 (scan-lists-of-lists-fringe tree2)))
    (and (collect-and (#Mequal t1 t2))
         (= (collect-length t1) (collect-length t2)))))

;; 2 割と無理やりにgeneratorを使ってみたもの
(defun same-fringe? (tree1 tree2)
  (let ((t1 (scan-lists-of-lists-fringe tree1))
        (t2 (scan-lists-of-lists-fringe tree2)))
    (let ((g1 (generator t1))
          (g2 (generator t2))
          (limit (max (collect-length t1) (collect-length t2))))
      (loop :repeat limit :always (equal (next-in g1) (next-in g2))))))

1は、割と普通に書いてみました。SERIESは基本的に短い方に長さが揃えられてしまうので、長さを計っています。長さを計らなければ、無限リストにも対応できますが、今度は、(1 2 3 .....)と、(1 2 3)の場合で真が返ってしまいます。

2は、オリジナルがジェネレータ使用ということで、generatorを使ってみたのですが、いまいちです。

そもそも、collect-lengthを使ってしまった時点で駄目な気がしますが、どうやったら良いんでしょうー。

CLで学ぶ「プログラミングGauche」 (9.1)

| 00:05 | CLで学ぶ「プログラミングGauche」 (9.1) - わだばLisperになる を含むブックマーク はてなブックマーク - CLで学ぶ「プログラミングGauche」 (9.1) - わだばLisperになる

「プログラミングGauche」をCLで演習してみていましたが、2ヶ月も放置してしまいました。

どうも一回の内容を長くしてしまうと億劫になってしまうようなので、細切れに行くことに方針変更しました。

9.1 集合

このセクションで登場するmemberですが、CLでは、memberは、比較の為の関数を:testで指定できるので、srfi-1拡張相当です。

デフォルトでは、eqlが比較に使われます。

また、keyが取れて、

member
(member 'bar '((foo) (bar) () (baz)) :key #'car)
;=> ((BAR) NIL (BAZ))

のようなこともできます。

(defparameter *inventory* '(cookie dagger))

(member 'cookie *inventory* :test #'equal)

(defun has-item? (item)
  (member item *inventory*))
delete

srfi-1のdeleteに相当するものは、CLでは、removeになります。

また、同じ機能で引数リストを破壊的に変更するものにdeleteがあります。

(remove 1 '(1 2 1 2 1 2 1 2))
;=> (2 2 2 2)

itemを取り除く上限の個数も標準で指定できます。

(remove 1 '(1 2 1 2 1 2 1 2) :count 1)

;=> (2 1 2 1 2 1 2)

[練習問題]

CLのremoveは、この問題のように全く削除要素がみつからなかった場合に、与えられた引数をそのまま返しても良いということになっています。

CLHS: Function REMOVE, REMOVE-IF, REMOVE-IF-NOT...

逆にいえば、この仕様だとremoveの結果を破壊することの安全が保証されていないので破壊する場合は、リストをコピーしてやる必要があります。

(defun delete-1 (item lst test)
  (if (endp lst)
      ()
      (let ((tail (delete-1 item (cdr lst) test)))
        (if (funcall test item (car lst))
            tail
            (if (eq (cdr lst) tail)
                lst
                (cons (car lst) tail))))))

(let ((data (list 1 2 3 4 5)))
  (eq data (delete-1 0 data #'equal)))
;=> T
代入

Gaucheのset!に相当するものは、setfか、setqになります。

また、Schemeの命名規則では、名前の最後に!が付くと破壊的操作となりますが、CLの場合、CL以前のLISPの色々な命名規則が混っていますので、いまいち統一感に欠けます。

nconc、nreverse等、nが付いたり、remove系に対してのdelete系というのが主なところです。

ゲスト



トラックバック - http://cadr.g.hatena.ne.jp/g000001/20080718