ときどきの雑記帖 めぐりあい電脳空間編

最新ページへのリンク
目次ページへのリンク

一つ前へ 2010年8月(中旬)
一つ後へ 2010年9月(上旬)

ホームへ

2010年08月31日

■_

9月~

■_ 我が心の68000

なんか特許ネタで Amiga がそこかしこでとりあげられてて盛り上がってました。 XOR patent killed Commodore-Amiga : programming [XCSSA] XOR patent ended CD32, and Commodore-Amiga んで、そこで見つけた History of the Amiga なんてのを斜め読みしてたら A history of the Amiga, part 1: Genesis A history of the Amiga, part 2: The birth of Amiga A history of the Amiga, part 3: The first prototype A history of the Amiga, part 4: Enter Commodore A history of the Amiga, part 5: postlaunch blues A history of the Amiga, part 6: stopping the bleeding A history of the Amiga, part 7: Game on! A history of the Amiga: Full story why the Amiga died. : programming


A history of the Amiga, part 1: Genesis
The 68000

The 68000 was an engineer's dream: fast, years ahead of its time, and easy to program. 
But it was also expensive and required more memory chips to operate, and Atari 
management didn't think that expensive computers constituted a viable market. Anyone 
who had studied the history of electronics knew that in this industry, what was 
expensive now would gradually become cheaper over time, and Jay pleaded with his 
bosses to reconsider. They steadfastly refused. 

「68000 はエンジニアの夢だった」ですか。 高速で、時代に先んじていて、プログラムが組みやすい。 反面、とても高価であり、使うのにはより多くのメモリを必要とした。

■_ Scala

読むのはやさしいが理解は難しい?

ああ、いいなあ68000。


Scala: Easier to read (and write), harder to understand? « Schneide Blog
 
Scala: Easier to read (and write), harder to understand?

There is a vivid discussion about Scala's complexity going on for some weeks now on 
the web even with a response from Martin Odersky. I want to throw my 2¢ together with 
some hopefully new aspects into the discussion.

Scala's liberal syntax rules and compiler magic like type inference and implicit 
conversions allow nicely written APIs and DSLs almost looking like prose texts. Take a 
look at APIs like scalatest and imagine the Java/Junit equivalent:

@Test def demonstrateScalaTest() {
  val sb = new StringBuilder("Scala")
  sb.append(" is cool!")
  sb.toString should be ("Scala is cool!")
  evaluating { "concise".charAt(-1) } should produce [StringIndexOutOfBoundsException]
}

There are really nice features that reduce day-to-day programming tasks to keywords or 
one-liners. Here are some examples:

// singletons have their own keyword (object), static does not exist!
object MySingleton {
  def printMessage {
    println("I am the only one")
 }
}

// lazy initialization/evaluation
lazy val complexResult = computeForHours()

// bean-style data container with two scala properties and one java-bean property with getter+setter
class Data(val readOnly: String, var readWrite: Int, @BeanProperty var javaProperty: String)

// tuples as return values or quick data transfer objects (DTO) for methods yielding multiple data objects
def correctCoords(x: Double, y: Double) = (x + 12, y * 0.5)
val (correctedX, correctedY) = correctCoords(0.37, 34.2)
println("corrected: " + correctedX + ", " + correctedY)

On the other hand there are so many features built-in that really make it hard to 
understand the code if you are not scala programmer with some experience. I like the 
differentiation between application and library code Martin Odersky himself makes in 
Programming Scala. The frameworks I have tried so far (Lift, scalatest and scala-swing) 
in Scala make your life very easy as long as you just use them. It is really a breeze 
and much more fun than using most APIs in Java for example. But when something goes 
wrong or you really want/have to understand what is going on you can have a hard time. 
This is true at least for a Scala beginner, sometimes perhaps for an pro, too.

Final Thoughts

In my opinion Scala is a very nice language that successfully combines clean object 
oriented programming with functional features. You can migrate from a pure OO-style to 
a nice hybrid “Scala-style” like many programmers did when they first used Java 
mostly with procedural style using classes only as namespaces for their static methods. 
I am quite sure that a Scala code style and best practices still have to develop. 
Programmers will need their time diving into the language and using it for their 
benefit. I hope Scala prospers and gains attention in the industry because I 
personally think it is a nice step forward compared to Java (which turns more and more 
into a mess where you need profound knowledge to fight your problems).

わたしの意見では、Scala はオブジェクト指向プログラミングと関数的な機能をきれいに
まとめた非常に nice な言語です。あなたは純粋なオブジェクト指向スタイルから
nice hybrid な“Scalaスタイル”へと migrate できます。
それは多くのプログラマーが初めて Javaを使ったときにクラスをスタティックメソッドの
ためのただの名前空間のように使いほとんど手続き型のスタイルであったのと似ています。




Regarding the complexity, which certainly exists in Scala, I only want to raise some 
questions which may be answered sometime in the future:

    * Maybe the tooling is just not there (yet)?
    * Maybe you sometimes just don't have to understand everything what's happening underneath?
    * Maybe Scala makes debugging much more seldom but harder, when something does not work out?
    * Maybe the features and power of Scala are worth learning?
    * Maybe certain features will just be banned by the teams like sometimes in Java teams
      (think of switch-case, the ?-operator, Autoboxing e.g.)?

■_ Haskelly?

Haskell的なとかいう意味でしょうか?


Defining “Haskelly” : Inside 245s

Existential Pontification and Generalized Abstract Digressions

Defining “Haskelly”

by Edward Z. Yang

At risk of sounding like a broken record, the topic of this post also sprang from 
abcBridge. John Launchbury asked a question during my presentation that got me 
thinking about API design in Haskell. (By the way, the video for the talk is out! 
Unfortunately, the second half had to be cut out due to technical difficulties, but 
you can still check out the slides.)
<
His question was this:

    You've presented this in a very imperative style, where you've got this AIG structure
    in the ABC tool, and what you've really done is given me a nicely typed Haskell typed
    interface that allows you to go in a put a new gate or grab a structure, and I'm left
    wondering, what is the reason for needing this tight tie-in with what's going on in
    that space? Here is a thought experiment: I could imagine myself having a purely
    functional data structure that is describing the data structure...and you end up with
    a functional description of what you want your graph to look like, and then you tell
    ABC to go and build the graph in one go.

I had claimed that abcBridge was a “functional API” for manipulating and-inverter 
graphs; perhaps I was lying! Is abcBridge—with its close correspondence to the 
underlying imperative code—truly “functional?” Or, if it's not functional, does it 
at least have a “Haskelly” API? (What does it even mean for an API to be Haskelly?) 
Why does the purely functional interface seem morally better than the imperative 
interface? It's a question of philosophical import as well as practical import—why do 
we prefer the functional interface which might require a more complex underlying 
implementation?

(略)

■_ 本日の巡回から

■_

いろいろあるんですよ。ええ。

2010年08月30日

■_

・センゴク外伝
激突直前

・今月の皇帝陛下
YOUNGKING OURS (ヤングキングアワーズ) 2010年 10月号 [雑誌] ロベスピエールが回想シーンで登場。 ミュラをうまく「のせる」皇帝陛下。

■_

どこで何を間違えたのか。 最初の二つだけ。


Where we went wrong - Charlie's Diary

Where we went wrong

By Charlie Stross

According to one estimate pushed by the FBI in 2006, computer crime costs US 
businesses $67 billion a year. And identity fraud in the US allegedly hit $52.6Bn in 
2004.

Even allowing for self-serving reporting (the FBI would obviously find it useful to 
inflate the threat of crime, if only to justify their budget requests), that's a lot 
of money being pumped down a rat-hole. Extrapolate it worldwide and the figures are 
horrendous ― probably nearer to $300Bn a year. To put it in perspective, it's like 
the combined revenue (not profits; gross turnover) of Intel, Microsoft, Apple, and IBM
― and probably a few left-overs like HP and Dell ― being lost due to deliberate 
criminal activity.


I'm compiling a little list, of architectural sins of the founders (between 1945 and 
1990, more or less) that have bequeathed us the current mess. They're fundamental 
design errors in our computing architectures; their emergent side-effects have 
permitted the current wave of computer crime to happen ...

わたしは 1945年から1990年の間の今のわたしたちに伝えられている founder たちの 
architectural sins をまとめました。
コンピューティングアーキテクチャにおいて彼らは根本的な設計ミスをしました。
その emergent side-effects は 
permitted the current wave of computer crime to happen ...


1) The Von Neumann architecture triumphed over Harvard Architecture in the design of 
computer systems in the late 1940s/early 1950s.


1) 1940年代終盤から1950年代初めにかけてのコンピューターシステムの設計において、フォン・
ノイマンアーキテクチャーがハーバードアーキテクチャーに勝利した。

In the Von Neumann architecture, data and executable code are stored in the same 
contiguous memory in a computer; in Harvard Architecture machines, data and code have 
separate, disjoint areas of memory and never the twain shall meet. Von Neumann 
architectures are simpler and cheaper, hence were more popular for about the first 
forty or fifty years of the computing revolution. They're also more flexible. Allowing 
data and executable code to share the same address space allows for self-modifying 
code and for execution of data as code — sometimes these are useful, but they're 
horrible security holes insofar as it permits code injection attacks to happen. There 
have been some recent moves by the likes of Intel in their more recent architecture 
iterations to permit chunks of memory to be locked to one function or the other, thus 
reducing the risk of code injection attacks — but it's too little, and much too late.

フォン・ノイマン アーキテクチャーではデータと実行可能コードはコンピューターの同一の
contiguous memory に格納されています。一方、データとコードを分割しているハーバードアー
キテクチャーではメモリの領域 (areas of memory) は disjoint されていて、両者が一緒にな
ることは決してありません。フォン・ノイマン アーキテクチャーは単純かつ安価であり、そのた
め computing revolution の最初の40~50年においてよりポピュラーなものとなりました。また、
フォン・ノイマン アーキテクチャーはフレキシブルでもありました。データと実行コードとで
同一アドレス空間の共有を許すことで自己書き換えコード (self-modifying code) やデータを
コードであるかのように実行する(execution of data as code) ことが可能となりました。これ
はそうすることが便利なこともある一面で、コードインジェクション攻撃を許してしまう 
horrible なセキュリティホールなのです。最近になって、より新しい architecture 
iterations では Intel などがchunks of memory を one function or the other (一つ以上の
関数?) に lock するのを許可することによりコードインジェクション攻撃のリスクを軽減させ
るという動きがあります。― とはいえその効果はほんのわずかなものであり、かつ、手遅れな
ものだったのです (it's too little, and much too late)。


2) String handling in C uses null-terminated strings rather than pointer-delimited 
strings. A null character (ASCII 0) denotes the end of a string (a block of adjacent 
memory cells containing one character of data each) in the C programming language's 
memory management (cough, choke) system. What if you want to write a string containing 
ASCII 0, or read or write beyond a null? C will let you. (C will not only let you 
shoot yourself in the foot, it will hand you a new magazine when you run out of 
bullets.) Overwriting the end of a string or array with some code and then tricking an 
application into moving its execution pointer to that code is one of the classic ways 
of tricking a Von Neumann architecture into doing something naughty.

2) C ではポインターで delimit される文字列ではなく null で終端される文字列を取り扱いま
す。ナルキャラクター (ASCII の 0) は C というプログラミング言語のメモリ管理システムに
おける文字列(それぞれに一つのキャラクターが収められる adjacent メモリーセルのブロック)
の終端を表すものです。 ASCII の 0 を含んだ文字列を書き出したいとか、ナルを越えて読み書
きしたいと言ったときにあなたはどうしますか? C はそれをあなたに丸投げしてしまいます(C 
はあなたに shoot yourself in the foot させる (墓穴を掘らせる?) だけでなく、弾丸を撃ち
尽くした時には新しい弾倉を手渡してさえくれるのです)。文字列や配列の終端をちょっとした
コードで上書きしてやることで、
and then tricking an application into moving its execution pointer to
that code is one of the classic ways of tricking a Von Neumann architecture
into doing something naughty.
#プログラムの「実行ポインター」を操作してやるとか何とか


In contrast, we've known for many decades that if you want safe string handling, you 
use an array — and stick a pointer to the end of the array in the first word or so of 
the array. By enforcing bounds checking, we can make it much harder to scribble over 
restricted chunks of memory.

対照的に、わたしたちは何十年も前からもしあなたが安全な文字列ハンドリングを望んでいるの
なら配列を使用し、その配列の最初のワードなどに配列の終端へのポインターを入れるようにす
べきことを知っています。境界チェックを強制することによって、restricted chunks of 
memoryを scribble over してしまうのをかなり困難なものにできます。

Why does C use null-terminated strings? Because ASCII NUL is a single byte, and a 
pointer needs to be at least two bytes (16 bits) to be any use. (Unless you want short 
strings, limited to 256 bytes.) Each string in C was thus a byte shorter than a 
pointer-delimited string, saving, ooh, hundreds or thousands of bytes of memory on 
those early 1970s UNIX machines.

なぜ C ではナル終端文字列を採用したのでしょうか? それは ASCII の NUL が1バイトであるの
に対し、ポインター一つは (256バイトまでに限定された短い文字列を望んでいたのでない限り)
何かを指し示すには少なくとも 2バイト (16ビット) の大きさが必要であったからです。これに
より C における文字列はそれぞれポインター終端の文字列よりも1バイトだけ短くなりました。
saving, ooh, hundreds or thousands of bytes of memory on those early 1970s UNIX 
machines.

(To those who might carp that C isn't really used much any more, I should reply that 
(a) yes it is, and (b) what do you think C++ is compiled to, before it's fed back to a 
compiler to produce object code?)

(C はもはやそれほど使われてはいないだろうと carp するかもしれない人たちには
わたしはこう返すべきでしょう
(a) yes it is,
そして
(b) what do you think C++ is compiled to,
before it's fed back to a compiler to produce object code?)

■_ だめだこりゃ

K&R を百回音読してもらわないと(笑) (C には値渡ししかないと明記されています)


アルゴリズムの授業で、C言語のポインタ渡しを参照渡しと教えられたのですが - Yahoo!知恵袋

アルゴリズムの授業で、C言語のポインタ渡しを参照渡しと教えられたのですが

例えば、

int functionA(int i){
return i ^ (-1);
}

void functionB(int* pi){
*i ^= -1;
}
という関数があるのですが、後者の引数はポインタですから"ポインタ渡し"
これを学校で、それぞれ"値渡し""参照渡し"と習ったのですが、間違いですよね?

// C++
void functionC(int& ri){
i ^= -1;
}

が参照渡しで、C言語では参照はない筈なのですが

規格ではどうなっているのでしょうか?

先生に訊いても、「ポインタが実体を示しているのなら参照だ」であったり「(参照という概念
の)定義の仕方云々」と、C言語の仕様では定められていないような回答だったのですが

補足
    *i ^= -1;
    ⇒*pi ^= -1;

    i ^= -1;
    ⇒ri ^= -1;

    と読み換えお願いします
    いや多分通じるんでしょうが、凡ミス・・・

    ***********

    やはりいくつかのサイトに書かれているとおり、参照渡しの呼称が間違いでしたか
    ポインタ渡しでは、ポインタ演算が出来てしまいますからねえ・・・

ベストアンサーに選ばれた回答


>>これを学校で、それぞれ"値渡し""参照渡し"と習ったのですが、間違いですよね?
C言語では数学程厳密に決まっているわけではありませんが
「言語理論」の言葉とすれば、先生の言うのが正しいと思う。
只参照渡しを実現するとき
(1)露骨にポインタで実現する、まあ、ポインタそれ自身の値渡しと呼べなくもないが!!!
(2)参照演算子&として見せる
(3)C#のように、こっそり隠して実現する
実現方法が色々ある、と考えた方が分かりやすいのでは???

質問した人からのコメント

    * 皆さん回答ありがとうございます

      >>アセンブリ
      アセンブリレベルでは同一のソースを吐くようですが、
      最適化の際には違う挙動を示すそうですね

      >>参照渡しを実現するとき
      こういう考え方なら確かに・・・
      ですが、C言語の仕様においては、という会話だったので

      情報の教師に聞いたところ~という回答をもらったが、納得できない、これはどういう意
      味を持つのか?という質問は稚拙で大人げないと思われるのか・・・
幼稚園ではない。

先生を持ち出さず、純粋に質問しよう。


俗に参照渡しと呼ばれていますが、実際にはポインタ値の値渡しです。
本当に参照渡しなのはC++やC#などに実装されているものの方だけです。Javaは値渡しと参照渡
しが基本型かオブジェクト型かで切り替ります。

【追記】
アセンブラレベルの実装で比べれば、Cのポインタ値による俗に言う参照渡しとC++の参照渡しは
似た処理をしているんですけどね。
    
あなたが正しい。

Cには、値渡ししかない。
Cで参照渡しと言われているのは俗にそう呼んでいるだけ。

教師(講師)がそれをちゃんと説明しない(出来ない)のは問題。

あちゃー(笑) Javaも値渡ししかしないというのは言語仕様にあるのに。

■_ 誤訳?

Perl のスレッドで。


Perlについての質問箱 44箱目 
342 デフォルトの名無しさん [sage] 2010/08/30(月) 00:35:43 ID: Be:
    perl ベスト プラクティスの280、281ページでわからないことがあります。
    以下のコードに対する注釈で
    「この正規表現は、monkeyとマッチするが、その場合にマッチするはずの変則的な複数形はmoneyである」
    となっている理由がわかりません。
    どこが原因で、moneyがマッチしてしまうのでしょうか?

    #変則的な複数形のテーブル
    my %irregular_plural_of = (
    'child' => 'children',
    'brother' => 'brethren',
    'money' => 'monies',
    'mongoose' => 'mongooses',
    'ox' => 'oxen',
    'cow' => 'kine',
    'soliloquy' => 'solioquies',
    'prima donna' => 'prime donne',
    'octopus' => 'octopodes',
    'tooth' => 'teeth',
    'toothfish' => 'toothfish',
    );

    次に続きます 

343 342 [sage] 2010/08/30(月) 00:42:24 ID: Be:

    #変則的な複数形のパターンマッチ
    my $has_irregular_plural = qr{
    child | brother | mongoose
    | ox | cow | monkey
    | soliloquy | prima donnna | octopus
    | tooth(?:fish)?
    }xms;

    #複数形の組み立て
    while (my $word = <>) {
    chomp $word;
    if ($word =~ m/\A ($has_irregular_plural) \z/xms) {
    print $iregular_plural_of{$word}, "\n";
    }
    else{
    print form_regular_plural_of{$word}, "\n";
    }
    } 

344 デフォルトの名無しさん [sage] 2010/08/30(月) 01:15:01 ID: Be:
    日本語の訳が変なだけじゃねーの(英文読んでないけど)。
    「マッチパターンとテーブルを別々に用意したら(コピペしたら)、
    タイポが紛れ込むから止めときな」
    って例でmoney(monkey=typo)を使ってるだけ。

    当たり前だがmoneyは、その例での
    m{\A ($has_irregular_plural) \z}xms
    にはマッチしない。 

345 デフォルトの名無しさん [sage] 2010/08/30(月) 01:15:32 ID: Be:
    >>342
    >「この正規表現は、monkeyとマッチするが、その場合にマッチするはずの変則的な複数形はmoneyである」
    これは「このコードを書いた人間がマッチすることを期待しているのはmoneyであるはずだが、
    実際にはミスタイプによりmonkeyがマッチしてしまう」ってことじゃないの?
    同じ単語をハッシュを作るときと正規表現パターンを作る時とで2回ずつ書くのは無駄だし、
    たとえばmoneyと書くべきところを片方だけmonkeyと書いてしまうような間違いをする確率を増やしてしまうので、
    こういう書き方はやめましょう、って話だと思うんだが。 

346 デフォルトの名無しさん [sage] 2010/08/30(月) 01:17:41 ID: Be:
    コピペじゃねえ。各自別々にタイプしたら、だな。 

347 デフォルトの名無しさん [sage] 2010/08/30(月) 02:31:17 ID: Be:
    なるほど、納得しました。
    ありがとうございました。 

原文を調べてみたところ、こんなんでした。

The regular expression shown matches 'monkey',  but the particular irregular noun it's 
supposed to match in that case is 'money'.  The regex also matches 'primadonna' 
instead of 'prima donna',  because the /x flag makes the intervening space non-significant
within the regex.
  

訳文が 342 の書いたそのままかどうかは分からないけど、誤訳っぽい気が。

■_ 書評無理

arton さんの紹介でオライリー様より献本御礼献本をいただきました。
JavaによるRESTfulシステム構築

Java は正直アウェー(縁がないわけではないんですが、少なくともRESTがどうのという レイヤーでは使ってません。というかそっちはそもそもあまり縁がない)だし、 すでにきしださんが書評を書かれていますが (2010-08-21 - きしだのはてな)、 まあできるだけ。

きしださんの書評にもあるとおり、 Java で REST な Web サービスを構築するための API であるところの JAX-RS というものについての本です。おわり。 ではあまりにあまりなのでもうちょっとがんばると。

@Path("/customers")
public class CustomerResouce {

    @GET
    @Path("{id}")
    @Produces("application/xml")
    public Customer getCustomer(@PathParam("id") int id) {
      Customer cust = findCustomer(id);
      return cust;
    }

    @POST
    @Consumers("application/xml")
    public void createCustomer(Customer cust) {
       …
    }
}

プログラムはこんな感じになります。 監訳者あとがきに JAX-RS層はアノテーションを読み取り必要なときに必要なオブジェクトの必要なメソッドを呼び出します。 とあるように、@なんとか が引き金(というのだろうか)となって、裏でいろいろやってくれるというわけですね。 @ をつかったこの記法とアノテーションを活用した手法は、 見た目はともかく面白いやり方だなあとは感じました。

自分があまり詳しくないのでどの程度おすすめしてよいのかわかりませんが、 詳しく仕様も記載されていますし、 この JAX-RSを使ったりする人には must buy なものではないでしょうか。

最後に重箱の隅。


p13
この場合、数千もの製品に関する情報を私たちのクライアントに送り返すことになったら問題が
生じる可能性がある。私たちのサービスは過負荷に陥るかもしれないし、またクライアントはダ
ウンロードを終わらせるために永遠に待ち続けることになるかもしれない。


p84
キーと値ペアはコロン文字で区切られ、キーと値の境界はコンマにより区切られる。

  

前者は何を永遠に待ち続けるのか不明瞭な気がするし、 後者の「コロン文字」はその後の「コンマ」に「文字」がついてないのもあって なにか違和感が。原文にはおそらく colon character とかなっていたのでしょうけど 訳文に反映させないでもいいんじゃないかなあと思いました。

■_

2010年08月29日

■_

みっかめ
挫けた ○| ̄|_

それはそれとして関係者の皆様方お疲れ様でした。 おっと、アンケートに答えておかねば。

■_ よくある質問

どう答えろとw


スレッドを立てるまでもない質問雑談スレ41 
639 仕様書無しさん [] 2010/08/29(日) 07:34:33 ID: Be:
    どうしてもJAVAあるいはC++を、全くのゼロから学ばなければいけない状態になった場合、
    戦力として活躍できるくらいの力をつけられるようになるのは、何ヶ月後くらいになるんでしょうか?
    JavaのほうはAndroidアプリケーションの開発、C++のほうはPCゲーム開発という想定でお願いします。 

640 仕様書無しさん [] 2010/08/29(日) 08:20:09 ID: Be:
    >>639
    個人差がありすぎて回答は無理だと思います。
    とりあえず、あなたにプログラマの適性があるかどうかFizzBuzzで解いてみてはどうでしょう。
    現場的には、戦力化に何ヶ月も掛かる人を押し付けられても迷惑です。 

641 仕様書無しさん [sage] 2010/08/29(日) 09:55:42 ID: Be:
    >>639
    一週間から二年の間位じゃないかな 

■_ reddit に訊け

プログラミング言語の選択のお話。


Help in choosing a programming language - Stack Overflow

I am a student of std.7 and learning GW-BASIC in school. BASIC doesn't suit my needs 
and other languages will start from std.9

I can't wait that long (I'm sick of BASIC). I am trying to choose some other good 
programming languages. (I know this question is silly)

Desktop Application Programming and Web app design are my main goals. I don't want to 
learn many languages one by one and then choose one. I just want to stick to one or 
two. I don't want to go learning languages one by one. Which of these fit my goal? [It 
can also have a GUI option] :

    * C
    * C++
    * Python
    * Visual Basic
    * Any other?? [PHP,JS,Java,etc...]

Please help me since I am totally confused! Which languages are good for database 
programming and which languages can be interpreted with both an active and inactive 
internet connection? Also list good books,ebooks and tutorials for those languages
Python is usually a recommended programming language for beginners.

It's syntax is easy to get a grip on, and it has built-in libraries for everything you 
can imagine, including GUI libraries, which should be handy when you want to focus on 
desktop development.

Just as an example, the following lines of code will pop up a simple window:

from Tkinter import *
root = Tk()
w = Label(root, text="Hello, world!")
w.pack()
root.mainloop()

For web development, you have multiple web frameworks to get you started with web apps, 
such as Django and CherryPy.

Again, just as an example to show how easy it can be to run a simple web app, the 
following code in CherryPy will start a simple "hello world" web server:

import cherrypy

class HelloWorld(object):
    def index(self):
        return "Hello World!"
    index.exposed = True

cherrypy.quickstart(HelloWorld())

On the programming side, it supports multiple programming paradigms: you can learn not 
only object-oriented programming, but also the basics of functional programming (even 
though Python is NOT a functional language).

If you're into Python, check out:

    * http://stackoverflow.com/questions/2876337/how-should-i-go-about-learning-python
    * http://stackoverflow.com/questions/81584/what-ide-to-use-for-python

(If the IDE thread gives you a headache, you might just want to use PyScripter)

Good luck!
Do not focus on languages, but on Programming Paradigms. After you've learned a 
language that conforms to a paradigm, a little effort is required to learn another 
language that conforms to the same paradigm (and it will consists in learning the 
syntax properly, some library etc at the depth level you'd like).

Programming is about solving problems, and you can do this with different approaches, 
and each approach supports different paradigms and each language can conform to 
multiple paradigms.

I'd suggest to start with C or Python as Imperative Programming languages and then you 
can move to the Object Oriented Paradigm using Python as well. The imperative paradigm 
is one of the simplest to learn (since it conforms to the Operational approach, the 
one most used by humans to solve problems everyday and reflects how the machines work 
at lower levels), the object oriented one will be easier to understand. You say that 
BASIC does not suit your needs, I recognize that it is not so good and maybe learning 
it at school bothers you but you shall define your goals more programmatically : P

And learning more than one language in sequence based on needs is far better than 
stick to those learned at once forever, you might end like the teacher who is trying 
to make BASIC enter your life

Well for desktop development, C++ with Qt is a good choice. Python is a good second 
choice.

If you are designing a web application that works with databases, like MySQL, go with 
something like PHP.
Python is definitely the choice for a first language when you want to do desktop or 
console programming. It's well-structured and it has lots of things built in, 
including a pretty decent set of GUI features.

Web Applications result in a lot more controversy, and it depends to some extent what 
you want to do. PHP is in more places on the web than probably any other language 
anymore, due in large part to the popularity gained in the late '90s and early 2000s. 
So if you want a job in web development, it's good to know your way around PHP.

In a couple years, the answers may change. So in answer to your question, it's less 
about picking a particular language and more about learning first what a computer 
programming language can do for you, and second what are the commonalities and 
differences among them, and third how to select a language given a task.

The very worst thing for a programmer is to know only one language. But the second 
worst thing is early exposure to BASIC -- at least in it's classic form with line 
numbers, goto statements, and a distinct lack of structuring capacity like 
user-definable functions.

Still, Python is a good start. Learn it, and it will make your BASIC better.

Python 大人気。 しかしいずれはやるにしても Cから始めるのは…どうなんだ?

■_ どうやって見つけるんだろう

質問自体はありふれた類のものと思いますが。


正規表現で不正文字 | OKWave

PHPのプログラムで入力チェックを行っています。
入力された文字が不正の場合「@,<,>,\,-,_」、
エラーにさせようとしているんですが
参考サイトがなかなか見つかりません。

どこか良いサイトご存じの方よろしくお願い致します。

http://www.kiyori.co.jp/system/?p=523
自分が見つけたサイトですが、うまくエラーになりませんでした。

投稿日時 - 2010-08-29 10:37:43

どう書いたのがちょっと気になったり。 しかし「参考サイト」ってどんなのをお望みなんだろうか。

んで、この質問主が見つけたというサイトの説明を見ると…


不正な文字チェック(C#) – キヨリシステム

    /// <summary>
    /// 不正な文字のチェック(セキュリティ対策)
    /// 意図的にエスケープさせて任意のSQL実行をさせないため
    /// </summary>
    /// <param name=”strData”>チェックするデータ</param>
    /// <param name=”strName”>項目名</param>    /// <returns>エラーメッセージ</returns>
    public static string CheckInvalidChar(string strData, string strItemName)
    {
        // 正規表現検索用
        Regex reg;
        // 正規表現検索結果
        Match match;

        // 正規表現指定用文字列
        string tag_regex = “”;
        // 通常 会社名、人名などに使われないはず
        // 不正な文字 = ‘%' , ‘_' , ‘\' , ‘/' , ‘*' , ‘.' , ‘?' など
        tag_regex += "[%_\\\\/\\.\\*\\?]";

        // フォーマットチェック
        reg = new Regex(tag_regex, RegexOptions.IgnoreCase | RegexOptions.Compiled | RegexOptions.Singleline);
        // データの正規表現照合
        match = reg.Match(strData);
        if (match.Success)
        {
            // マッチしたらエラー
            return strItemName + “に不正な文字が含まれています。”;
        }

        return "";
    }

(略)

だからブラケットの中身で余計なエスケープ入れるの止めて○| ̄|_ スラッシュまでエスケープしているし。

それと、C# なら @"" 文字列使えばエスケープを二重にする必要もなくなるのに なんというか二重にどうにかしたいサンプル。

■_ Modern な Perl とは

なんか開きっぱなしのタブに残ってた。


blog | Perlgeek.de :: What is "Modern Perl"?
Thu, 12 Aug 2010
What is "Modern Perl"?

These days you often hear term Modern Perl, as something new(ish), and much improved 
over the old ways.

But what is it exactly? Well, there's no proper definition, but here is what that term 
means to me:

It's a set of tools, ideas and attitudes that help you to write better Perl programs, 
and allows you to have more fun while writing them.

Here are some aspects of Modern Perl

    * Testing: Most modern Perl modules have extensive test suites, that make 
      development sane and robust

    * Some built-ins now come with safer forms: the three-argument form of open() 
      allows you to open files safely with arbitrary characters in them, without any
      extra precautions. Lexical file handles make things safer and easier too.

    * use strict; use warnings;

    * Proper OO: with Perl 6 and with Moose in Perl 5, we have good object systems, 
      that require less low-level fiddling than the standard Perl 5 object system

    * Following Best Practices

    * (For open source projects) Liberally handing out commit privileges. The source 
      is stored in a version control system anyway, so low-quality changes or vandalism
      can simply be reverted (but that doesn't happen often in practice).

    * Caring about marketing: do tell people that you built something cool and useful

    * Small handy modules such as List::Util and Try::Tiny

    * Development tools such as Devel::Cover and Devel::NYTProf

All of these techniques help to write scalable Perl programs by making proper 
encapsulation much easier, or by avoiding common errors, identifying performance 
bottlenecks etc.

■_ んで

grep の話。とりあえずの結論(これからの方針)てのが このメールの内容っぽい。


What to learn from the BSD grep case [Was: why GNU grep is fast]

  Hi all,

there are some consequences that we can see from the grep case. Here I'd 
like to add a summary, which raises some questions. All comments are 
welcome.

1, When grep entered -CURRENT and bugs were found I immediately got kind 
bug reports and sharp criticism, as well. According to my understanding, 
-CURRENT is for development and it's fine to expose new pieces of work 
there but now I'm in doubt about that because of complaining people. On 
the other hand, an earlier version of BSD grep has been in the ports 
tree for a very long time and users reported some problems, which have 
been fixed but still, there is a lot of bugs there which haven't been 
reported that time. If users don't volunteer to test new pieces of code 
on a volunteer basis, somehow we have to make them test it, so I think 
committing BSD grep to -CURRENT was a good decision in the first round.

2, This issue also brought up some bottlenecks and potential 
optimization points (like memchr() and mmap), which other softwre may 
benefit from. This is another reason to let such pieces of work in. But 
unfortunately, this means that noone profiled another utilities because 
these bottlenecks remained undiscovered. Neither did I. It's a lesson 
that we have to learn from this particular case.

3, Because of point 2, we need more content to developers-handbook to 
help development with such ideas and best practices. It has been also 
raised on another list that our end-user documentation isn't that shiny 
and cool that it used to be and actually, developers-handbook has never 
been "finished" to be more or less complete. If someone looks at it, it 
looks like a sketch, not a book. I'll see if I can write a section on 
profiling.

4, We really need a good regex library. From the comments, it seems 
there's no such in the open source world. GNU libregex isn't efficient 
because GNU grep uses those workarounds that Mike kindly pointed out. 
Oniguruma was extremely slow when I checked it. PCRE supports Perl-style 
syntax with a POSIX-like API but not POSIX regex. Google RE2 is the same 
with additional egrep syntax but doesn't have support for standard POSIX 
regexes. Plan 9 regex only supports egrep syntax. It seems that TRE is 
the best choice. It is BSD-licensed, supports wchar and POSIX(ish) 
regexes and it is quite fast. I don't know the theoretical background of 
regex engines but I'm wondering if it's possible top provide an 
alternative API with byte-counted buffers and use the heuristical 
speedup with fixed string matching. As Mike pointed out the POSIX API is 
quite limiting because it works on NUL-terminated strings and not on 
byte-counted buffers, so we couldn't just do it with a POSIX-conformant 
library but it would be nice if we could implement it in such a library 
with an alternative interface.

わたしたちには本当に優れた正規表現ライブラリが必要です。
寄せられたコメントによれば、そういったものはオープンソース世界にはないようです。
GNU libregex は効率的ではありません。それは、Mike が親切にも解説してくれた
ワークアラウンドの数々を使っているからです。鬼車はわたしがチェックしたときには
とんでもなく遅い (extermerly slow) なものでした。PCRE は Perl 形式の構文を
POSIXライクなAPIでサポートしていますが、POSIX regex をサポートしていません。
Google RE2 は同様に additional egrep 構文ではありますが、標準の POSIX regex
のサポートがありません。Plan 9 regex は egrep 構文だけのサポートです。
TRE がどうやら最善の選択肢のように思えます。
TRE はBSDライセンスで、wchar と POSIX(風の)正規表現をサポートしており
とても高速です。わたしは正規表現エンジンの技術的な背景がわかりませんが、
バイトカウントつきの altternative API だとか固定文字列マッチングを使った
ヒューリスティックな高速化ができればよいのにと思っています。
Mile が指摘したように、POSIX API はそれがNUL終端された文字列に対して動作する
ものであり、バイトカウントされたバッファーに対するものではないので
非常に限定されたものです。このため、POSIX-confromant なライブラリを使うことが
できませんが、alterntive なインターフェースを持ったライブラリをわたしたちが
実装できればとてもよいことになるでしょう。

Gabor

鬼車ってそんなに遅かったっけ? 小迫さん結構ベンチマークで気を配ってたと思うんだけど。

■_ 本日の巡回から

■_

また本の感想書き忘れたよ ○| ̄|_

2010年08月28日

■_

ふつかめ デジカメ忘れてでかけてしまったでござる○| ̄|_

三回催されたサイン会(それぞれ別の本が対象)全部に並んだりしたわけですが、 台湾から来た人(たぶん)があおきさんに熱く語って写真を撮っていったのが印象に残りました。 本も買ってサインをもらいたいけど本が高くて買えないとか言ってたような。 円高の影響なんですかね。これも。

第一回、第二回あたりと比べると日本国外から来たであろう人とか、 女性がだいぶ増えているような気がしました。 国外からといえば、あるセッションでわたしの前の席に座っていたちょっと年を召したご夫妻は なんかよかったなあ。 夫婦そろってこういうイベントにくるとか。 夫婦で同じ職業(プログラマー)だったりするんだろか。

■_ あとでかく

ねむい。あそいく観たらとっとと寝よう。 三日目はどうするかは起きてから決める!(笑)

■_ 本日の巡回から

2010年08月27日

■_

・RubyKaigiいちにちめ
ちょっとまとめている余裕がががが 1日目感想 - I am Cruby! Just another Ruby porter, 2010-8-c RubyKaigi2010 1日目 - HsbtDiary(2010-08-27) rake:money拡大版@Ruby会議2010 ~Rubyエンジニアと企業の幸せな関係~ 日本Ruby会議2010‐ニコニコ動画(9)

つくばエクスプレスは速かった!

■_ このネタまだ引っ張ります


【レポート】GNU grepが高速な理由 | エンタープライズ | マイコミジャーナル

(略)

Mike Haertel氏の紹介する内容はgrep(1)の実装のみならず、高速な文字列処理を実現するひと
つの方法として参考になる。紹介されているGNU grep高速さの秘訣は次のとおり。

   1. GNU grepは入力バイトのすべてをチェックするようなことは避けている。
   2. GNU grepはバイトごとに適用する操作を極力最小限に減らしている。
   3. GNU grepはBoyer-Mooreアルゴリズムとルックアップテーブルを使って一致しない場合に
      は処理を飛ばしている。
   4. GNU grepはBoyer-Mooreアルゴリズムの内部ループを展開するとともに、展開時にループ
      終了テストが必要ない場合にはBoyer-Mooreデルタテーブルエントリを活用している。
   5. GNU grepのBoyer-Mooreアルゴリズムの実装にはAndrew Hume氏およびDaniel Sunday氏の
      論文"Fast String Searching [PDF]"が参考になる。
   6. GNU grepは低レベルUNIX入力システムコールを使って不要なデータのコピーを避けている。
   7. GNU grepは改行コード区切りでデータを取得しないことで高速化を実現している。
   8. GNU grepは大きなバッファにまとめてデータを読み込み、その領域内でBoyer-Mooreアル
      ゴリズムを使った検索を実施している。
   9. GNU grepではread(2)の代わりにmmap(2)を使って不要なコピーを減らす実装も提供してお
      り(--mmap)、こちらの方がさらに高速に動作する。

具体的にどの辺のコードがどれに対応しているのかってまとめてみようかしらん。 まあ 3 あたりは昨日書いたのとかぶるんですけど。

■_ Pascalの三角形ふたたび

さすが Perl だ書き方がいくらでもあるぜ。的な。


Journal of masak (6289)

Idiomatic Perl 6 [ #40516 ]

So, I wrote a program to generate Pascal's triangle. The first ten rows of the 
triangle, at least. It only used simple features of Perl 6, such as scalars, nested 
arrays, and for loops.

十段のPascalの三角形を、Perl 6のスカラー、ネストした配列、for ループなどの
単純な機能だけを使って書いてみました。

my $ELEMENTS = 10;
my @pascal = [1];

for 1 .. $ELEMENTS - 1 {
    my @last = @pascal[ * - 1 ].list;

    my @current;
    push @current, @last[0];
    for 0 .. @last - 2 {
        push @current, @last[$_] + @last[$_ + 1];
    }
    push @current, @last[ * - 1 ];

    push @pascal, [@current];
}

say @pascal.perl;

In fact, save for simple mechanically substitutable differences, it could have been a 
Perl 5 script. In fact, with a bit of manual array allocation, it could have been a C 
script. That's OK; there's a tolerance in the Perl community of writing code that 
looks like it was thunk in some other language.

But I've heard that Perl 6 is great at doing things with operators. For example, the Z 
operator, which interleaves two lists, seems to be able to help me write my push 
statements more succinctly:

二つのリストを interleave する Z 演算子は push のところを書く手助けになって
くれそうです。

my $ELEMENTS = 10;
my @pascal = [1];

for 1 .. $ELEMENTS - 1 {
    my @last = @pascal[ * - 1 ].list;

    my @current;
    for (0, @last) Z (@last, 0) -> $left, $right {
        push @current, $left + $right;
    }

    push @pascal, [@current];
}

say @pascal.perl;

The parentheses before and after the infix:<Z> aren't necessary, because the Z 
operator has looser precedence than comma. They're just shown here to make your eyes 
accustomed to reading this construct.

上記の、infix<Z>の前後にあるカッコは実は不要です。
それはこのZ演算子はカンマよりもさらに低い優先順位を持っているからです。
ここでのカッコは、この式を読むときに把握しやすくするためのものです。

In fact, now that only the addition is performed in the inner loop, I might as well 
use the Z+ operator, which does this for me.

さて、内側のループでは単に加算をしているだけなので、その仕事をしてくれる Z+
演算子も使えます。


my $ELEMENTS = 10;
my @pascal = [1];

for 1 .. $ELEMENTS - 1 {
    my @last = @pascal[ * - 1 ].list;

    my @current = 0, @last Z+ @last, 0;

    push @pascal, [@current];
}

say @pascal.perl;

Now as the remaining loop shrinks to a size I can take in all at once, I see a bit 
more clearly what I'm doing: I'm building each new list from the previous one. I could 
feed the previous list into a named function to get the current one:

my $ELEMENTS = 10;
my @pascal = [1];

sub next-list(@p) {
    [0, @p Z+ @p, 0]
}

for 1 .. $ELEMENTS - 1 {
    my @last = @pascal[ * - 1 ].list;

    my @current = next-list(@last);

    push @pascal, @current;
}

say @pascal.perl;

Or I could just feed it into a in-place anonymous sub.

my $ELEMENTS = 10;
my @pascal = [1];

for 1 .. $ELEMENTS - 1 {
    my @last = @pascal[ * - 1 ].list;

    push @pascal, (sub (@p) { [0, @p Z+ @p, 0] }).(@last);
}

say @pascal.perl;

But why even a sub? Perl 6 has a lighter construct, namely a "pointy block" 
(also known as a "closure" or a "lambda"). It doesn't participate 
in the call stack, and it's slightly easier to write.

my $ELEMENTS = 10;
my @pascal = [1];

for 1 .. $ELEMENTS - 1 {
    my @last = @pascal[ * - 1 ].list;

    push @pascal, (-> @p { [0, @p Z+ @p, 0] }).(@last);
}

say @pascal.perl;

Let's look at what the code does. Seed with one element. Calculate the next element 
based on the previous one. Stop at some point.

But that's exactly what the series operator does. The one that's written with three 
dots. We have a starting value, a way to get from one value to the next (our code 
block above), and a stopping value.

Well actually, we don't have the stopping value. But that's OK, since the series 
operator is lazy. So if we only request the first 10 values, it won't loop forever 
giving us the rest of the list.

my @pascal := do [1], -> @p { [0, @p Z+ @p, 0] } ... *;

say @pascal[^10].perl;

(The extra do required because of a shortcoming in Rakudo.)

以下略

■_ 本日の巡回から

2010年08月26日

■_

・ダムエー
ここに来てオリジン休載とは。アナウンスあったっけ?

・アフタ
なぜか近くのコンビニで扱ってない。 本屋で買ってもいいんだけど重いからなあアフタヌーン。

・RubyKaigi
てけとーに。

■_ 絶版?


あそびにいくヨ! 守礼皇19号
50 風の谷の名無しさん@実況は実況板で [sage] 2010/08/24(火) 19:53:02 ID:XX+zKssP0 Be:
    今7話見た。
    先生が読んでいるのは「中性子星」(ラリー・ニーブン、ハヤカワ文庫SF、絶版)で
    中性子星表面に住む知的生命体チーラが出てくるのは「竜の卵」(ロバート・L・
    フォワード、ハヤカワ文庫SF、絶版)だ。
    ぬるいぞスタッフ。 

191 風の谷の名無しさん@実況は実況板で [sage] 2010/08/26(木) 02:19:19  ID:O91z4JgG0 Be:
    >>50
    ちょっと待て、どっちも絶版なのかよ!

    マジでSF(ていうか出版全体)冬の時代だ…。
    「ストライクウィッチーズ」の元ネタの一つになった
    ポール・アンダースン『大魔王作戦』も絶版だし。

ノウン・スペースシリーズあらかた駄目だったりして?

■_ で

GNU grep ですが、2.5 から 2.6 で正規表現エンジンが変わっているようです。 2.5までは GNU regex 0.12 と呼ばれていたものでしたが、 現在は glibc に収められているそれになっています。 前者の GNU regex 0.12 には長い長い物語があるのですが、 それは今回は割愛します。


 C:\Users\hoge\prog\src\grep-2.6.3\lib のディレクトリ

2010/03/20  17:54           112,499 regcomp.c
2010/02/04  17:00             3,009 regex.c
2010/02/04  17:00            25,834 regex.h
2010/02/04  01:08           131,276 regexec.c
2010/02/04  01:08            48,587 regex_internal.c
2010/02/04  01:08            24,221 regex_internal.h

この辺が関連するファイルになります。


2008/02/28  16:24           249,671 regex.c
2007/06/29  03:57             1,726 regex.h

2.5.3 だとこんな感じ。ちょっといじってて大きさが変わってますが。

それはさておき、BM法を正規表現マッチングに応用ということでふと思い出したのが fastmap です。これは昔からあるものですが、新しい方から

/* -*- buffer-read-only: t -*- vi: set ro: */
/* DO NOT EDIT! GENERATED AUTOMATICALLY! */
/* Extended regular expression matching and search library.
   Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 Free
   Software Foundation, Inc.
   This file is part of the GNU C Library.
   Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.

(略)

int
re_compile_fastmap (bufp)
    struct re_pattern_buffer *bufp;
{
  re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
  char *fastmap = bufp->fastmap;

  memset (fastmap, '\0', sizeof (char) * SBC_MAX);
  re_compile_fastmap_iter (bufp, dfa->init_state, fastmap);
  if (dfa->init_state != dfa->init_state_word)
    re_compile_fastmap_iter (bufp, dfa->init_state_word, fastmap);
  if (dfa->init_state != dfa->init_state_nl)
    re_compile_fastmap_iter (bufp, dfa->init_state_nl, fastmap);
  if (dfa->init_state != dfa->init_state_begbuf)
    re_compile_fastmap_iter (bufp, dfa->init_state_begbuf, fastmap);
  bufp->fastmap_accurate = 1;
  return 0;
}
#ifdef _LIBC
weak_alias (__re_compile_fastmap, re_compile_fastmap)
#endif

static inline void
__attribute ((always_inline))
re_set_fastmap (char *fastmap, bool icase, int ch)
{
  fastmap[ch] = 1;
  if (icase)
    fastmap[tolower (ch)] = 1;
}

これだけ見せられてもなにがなにやらというところだと思いますが、 要は、fastmap['A'] のようなものを条件にしたがってフラグを立てたり立てなかったりするのですね。

/* Helper function for re_compile_fastmap.
   Compile fastmap for the initial_state INIT_STATE.  */

static void
re_compile_fastmap_iter (regex_t *bufp, const re_dfastate_t *init_state,
			 char *fastmap)
{
  re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
  Idx node_cnt;
  bool icase = (dfa->mb_cur_max == 1 && (bufp->syntax & RE_ICASE));
  for (node_cnt = 0; node_cnt < init_state->nodes.nelem; ++node_cnt)
    {
      Idx node = init_state->nodes.elems[node_cnt];
      re_token_type_t type = dfa->nodes[node].type;

      if (type == CHARACTER)

これはちょっと複雑なので割愛。

で、正規表現関数のエントリ(いくつかあるんですがそれはそれ)。

int
regcomp (preg, pattern, cflags)
    regex_t *_Restrict_ preg;
    const char *_Restrict_ pattern;
    int cflags;
{
  reg_errcode_t ret;
  reg_syntax_t syntax = ((cflags & REG_EXTENDED) ? RE_SYNTAX_POSIX_EXTENDED
			 : RE_SYNTAX_POSIX_BASIC);

  preg->buffer = NULL;
  preg->allocated = 0;
  preg->used = 0;

  /* Try to allocate space for the fastmap.  */
  preg->fastmap = re_malloc (char, SBC_MAX);
  if (BE (preg->fastmap == NULL, 0))
    return REG_ESPACE;

  syntax |= (cflags & REG_ICASE) ? RE_ICASE : 0;

  /* If REG_NEWLINE is set, newlines are treated differently.  */
  if (cflags & REG_NEWLINE)
    { /* REG_NEWLINE implies neither . nor [^...] match newline.  */
      syntax &= ~RE_DOT_NEWLINE;
      syntax |= RE_HAT_LISTS_NOT_NEWLINE;
      /* It also changes the matching behavior.  */
      preg->newline_anchor = 1;
    }
  else
    preg->newline_anchor = 0;
  preg->no_sub = !!(cflags & REG_NOSUB);
  preg->translate = NULL;

  ret = re_compile_internal (preg, pattern, strlen (pattern), syntax);

と、fastmap を始めとしてごちゃごちゃ設定しておいてから本命を呼び出すと。

コンパイル部分はちとややこしいことになっているので以後は省略。

/* Searches for a compiled pattern PREG in the string STRING, whose
   length is LENGTH.  NMATCH, PMATCH, and EFLAGS have the same
   mingings with regexec.  START, and RANGE have the same meanings
   with re_search.
   Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
   otherwise return the error code.
   Note: We assume front end functions already check ranges.
   (START + RANGE >= 0 && START + RANGE <= LENGTH)  */

static reg_errcode_t
re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch,
		    eflags)
    const regex_t *preg;
    const char *string;
    int length, start, range, stop, eflags;
    size_t nmatch;
    regmatch_t pmatch[];
{
  reg_errcode_t err;
  const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
  int left_lim, right_lim, incr;
  int fl_longest_match, match_first, match_kind, match_last = -1;
  int extra_nmatch;
  int sb, ch;
#if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
  re_match_context_t mctx = { .dfa = dfa };
#else
  re_match_context_t mctx;
#endif
  char *fastmap = (preg->fastmap != NULL && preg->fastmap_accurate
		   && range && !preg->can_be_null) ? preg->fastmap : NULL;
  RE_TRANSLATE_TYPE t = preg->translate;

#if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
  memset (&mctx, '\0', sizeof (re_match_context_t));
  mctx.dfa = dfa;
#endif

  extra_nmatch = (nmatch > preg->re_nsub) ? nmatch - (preg->re_nsub + 1) : 0;
  nmatch -= extra_nmatch;

  /* Check if the DFA haven't been compiled.  */
  if (BE (preg->used == 0 || dfa->init_state == NULL
	  || dfa->init_state_word == NULL || dfa->init_state_nl == NULL
	  || dfa->init_state_begbuf == NULL, 0))
    return REG_NOMATCH;

#ifdef DEBUG
  /* We assume front-end functions already check them.  */
  assert (start + range >= 0 && start + range <= length);
#endif

  /* If initial states with non-begbuf contexts have no elements,
     the regex must be anchored.  If preg->newline_anchor is set,
     we'll never use init_state_nl, so do not check it.  */
  if (dfa->init_state->nodes.nelem == 0
      && dfa->init_state_word->nodes.nelem == 0
      && (dfa->init_state_nl->nodes.nelem == 0
	  || !preg->newline_anchor))
    {
      if (start != 0 && start + range != 0)
	return REG_NOMATCH;
      start = range = 0;
    }

  /* We must check the longest matching, if nmatch > 0.  */
  fl_longest_match = (nmatch != 0 || dfa->nbackref);

  err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,
			    preg->translate, preg->syntax & RE_ICASE, dfa);
  if (BE (err != REG_NOERROR, 0))
    goto free_return;
  mctx.input.stop = stop;
  mctx.input.raw_stop = stop;
  mctx.input.newline_anchor = preg->newline_anchor;

ここに至るまで dfa を作るためにあーだこーだやってるわけですね。

  err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
  if (BE (err != REG_NOERROR, 0))
    goto free_return;

  /* We will log all the DFA states through which the dfa pass,
     if nmatch > 1, or this dfa has "multibyte node", which is a
     back-reference or a node which can accept multibyte character or
     multi character collating element.  */
  if (nmatch > 1 || dfa->has_mb_node)
    {
      /* Avoid overflow.  */
      if (BE (SIZE_MAX / sizeof (re_dfastate_t *) <= mctx.input.bufs_len, 0))
	{
	  err = REG_ESPACE;
	  goto free_return;
	}

      mctx.state_log = re_malloc (re_dfastate_t *, mctx.input.bufs_len + 1);
      if (BE (mctx.state_log == NULL, 0))
	{
	  err = REG_ESPACE;
	  goto free_return;
	}
    }
  else
    mctx.state_log = NULL;

  match_first = start;
  mctx.input.tip_context = (eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
			   : CONTEXT_NEWLINE | CONTEXT_BEGBUF;

  /* Check incrementally whether of not the input string match.  */
  incr = (range < 0) ? -1 : 1;
  left_lim = (range < 0) ? start + range : start;
  right_lim = (range < 0) ? start : start + range;
  sb = dfa->mb_cur_max == 1;
  match_kind =
    (fastmap
     ? ((sb || !(preg->syntax & RE_ICASE || t) ? 4 : 0)
	| (range >= 0 ? 2 : 0)
	| (t != NULL ? 1 : 0))
     : 8);

  for (;; match_first += incr)
    {
      err = REG_NOMATCH;
      if (match_first < left_lim || right_lim < match_first)
	goto free_return;

      /* Advance as rapidly as possible through the string, until we
	 find a plausible place to start matching.  This may be done
	 with varying efficiency, so there are various possibilities:
	 only the most common of them are specialized, in order to
	 save on code size.  We use a switch statement for speed.  */
      switch (match_kind)
	{
	case 8:
	  /* No fastmap.  */
	  break;

	case 7:
	  /* Fastmap with single-byte translation, match forward.  */
	  while (BE (match_first < right_lim, 1)
		 && !fastmap[t[(unsigned char) string[match_first]]])
	    ++match_first;
	  goto forward_match_found_start_or_reached_end;

	case 6:
	  /* Fastmap without translation, match forward.  */
	  while (BE (match_first < right_lim, 1)
		 && !fastmap[(unsigned char) string[match_first]])
	    ++match_first;

ここで fastmapの出番。マッチする部分文字列の頭を探して無関係なものを読み飛ばします。 正規表現を見ればマッチする文字列の先頭に来る可能性のある文字というのはわかりますから、 それで fastmap を設定しておいてこういう場で使うと。

	forward_match_found_start_or_reached_end:
	  if (BE (match_first == right_lim, 0))
	    {
	      ch = match_first >= length
		       ? 0 : (unsigned char) string[match_first];
	      if (!fastmap[t ? t[ch] : ch])
		goto free_return;
	    }
	  break;

	case 4:
	case 5:
	  /* Fastmap without multi-byte translation, match backwards.  */
	  while (match_first >= left_lim)
	    {
	      ch = match_first >= length
		       ? 0 : (unsigned char) string[match_first];
	      if (fastmap[t ? t[ch] : ch])
		break;
	      --match_first;
	    }
	  if (match_first < left_lim)
	    goto free_return;
	  break;

例によって、マルチバイト文字のときは苦労が増えます。

FreeBSDの方をちょっと見てみたんですが、

[base] View of /head/lib/libc/regex/engine.c
http://svn.freebsd.org/viewvc/base/head/lib/libc/regex/engine.c?revision=197246&view=markup

/*-
 * Copyright (c) 1992, 1993, 1994 Henry Spencer.
 * Copyright (c) 1992, 1993, 1994
 *      The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Henry Spencer.

                       for (dp = start+g->mlen-1; dp < stop;) {
                               /* Fast skip non-matches */
                               while (dp < stop && charjump[(int)*dp])
                                       dp += charjump[(int)*dp];

                               if (dp >= stop)
                                       break;

                               /* Greedy matcher */
                               /* We depend on not being used for
                                * for strings of length 1
                                */
                               while (*--dp == *--pp && pp != mustfirst);

                               if (*dp == *pp)
                                       break;

                               /* Jump to next possible match */
                               mj = matchjump[pp - mustfirst];
                               cj = charjump[(int)*dp];
                               dp += (cj < mj ? mj : cj);
                               pp = mustlast;
                       }

               /* figure out what it matched */
               switch (OP(m->g->strip[ss])) {
               case OEND:
                       assert(nope);
                       break;
               case OCHAR:
                       sp += XMBRTOWC(NULL, sp, stop - start, &m->mbs, 0);
                       break;
               case OBOL:
               case OEOL:
               case OBOW:
               case OEOW:
                       break;
               case OANY:
               case OANYOF:
                       sp += XMBRTOWC(NULL, sp, stop - start, &m->mbs, 0);
                       break;
               case OBACK_:
               case O_BACK:
                       assert(nope);
                       break;
               /* cases where length of match is hard to find */
               case OQUEST_:

なんかやってますね。ちょっと追いかけるか。

■_ Pascal の三角形

Perl 6で。


blog | Perlgeek.de :: Pascal's Triangle in Perl 6
Pascal's Triangle in Perl 6

Permanent link

Today on IRC, Larry Wall showed this piece of Perl 6 code, which he wrote for Rosetta Code:

sub pascal { [1], -> @p { [0, @p Z+ @p, 0] } ... * };
say pascal[^10].perl
# output (reformatted for easy readbility):
# ([1],
#  [1, 1],
#  [1, 2, 1],
#  [1, 3, 3, 1],
#  [1, 4, 6, 4, 1],
#  [1, 5, 10, 10, 5, 1],
#  [1, 6, 15, 20, 15, 6, 1],
#  [1, 7, 21, 35, 35, 21, 7, 1],
#  [1, 8, 28, 56, 70, 56, 28, 8, 1],
#  [1, 9, 36, 84, 126, 126, 84, 36, 9, 1])

That's Pascal's triangle, generated in one line of Perl 6.

The ... is the series operator, which generates lists by feeding the previous value(s) 
(here always one array) to the generating block on its left, until it reaches the goal 
on the right (in this case "whatever", which means it returns a lazy, 
infinite list).

So for example if the previous item was the array [1, 2, 1], the code block evaluates 
0, 1, 2, 1 Z+ 1, 2, 1, 0.

ですから、先の例でひとつ前のアイテムが [1. 2. 1] という配列だったとすると
コードを評価した結果は 0, 1, 2, 1 Z+ 1, 2, 1, 0 となります。


Z is the zip operator, Z+ is pairwise addition (ie adding the pairs that the zip 
operator produced). In our example that leads to 0+1, 1+2, 2+1, 1+0 or 1, 3, 3, 1.

Z は zip 演算子で、Z+ は pairwise addition (zip演算子が生成するペアを加算) です。
わたしたちの例では 0+1, 1+2, 2+1, 1+0 、つまり 1, 3, 3, 1 となります。

It takes a while to get used to the meta operators and the series operator, but once 
you've understood them, you can do pretty neat things with them.

なんと謎めいた sub pascal { [1], -> @p { [0, @p Z+ @p, 0] } ... * };

■_ 本日の巡回から

■_

fastmap のところはもうちょっと詳しく書かないといけないかなあ。

2010年08月25日

■_

GNU grep はなぜ速いのかネタは意外に広まっている予感。

インターフェースの今月発売の号を買った。

■_ The History of Python: Why Python's Integer Division Floors

スピード最優先で。 たぶんあの人も訳すだろうし。


The History of Python: Why Python's Integer Division Floors

Why Python's Integer Division Floors
(なぜ Python の整数除算はFloorなのか)

I was asked (again) today to explain why integer division in Python returns the floor 
of the result instead of truncating towards zero like C.

今日わたしは、なぜ Python の整数除算は C のようにゼロ方向に丸めたものではなく
その結果の floor を返すのですかと(繰り返し)尋ねられました。

For positive numbers, there's no surprise:
正の数であれば、驚くことは何もありません:

>>> 5//2
2

But if one of the operands is negative, the result is floored, i.e., rounded away from 
zero (towards negative infinity):

けれどもオペランドの一つが負の数であった場合、その結果は floor されます。つまり、ゼロ
から離れる(負の無限大)方向に丸められるのです

>>> -5//2
-3
>>> 5//-2
-3

This disturbs some people, but there is a good mathematical reason. The integer 
division operation (//) and its sibling, the modulo operation (%), go together and 
satisfy a nice mathematical relationship (all variables are integers):

これは一部の人を disturb しましたが数学的に良い理由がありました。整数除算演算子 // と
その sibling である剰余演算子 % は一緒になって nice な数学的関係(すべての変数が整数)
を満足したのです。

a/b = q with remainder r

a/b = q と remainder r は

such that

次のような関係になります

b*q + r = a and 0 <= r < b

(assuming a and b are >= 0).
a、bの両方が0以上であることを仮定しています


If you want the relationship to extend for negative a (keeping b positive), you have 
two choices: if you truncate q towards zero, r will become negative, so that the 
invariant changes to 0 <= abs(r) < otherwise, you can floor q towards negative 
infinity, and the invariant remains 0 <= r < b. [update: fixed this para]

二つの選択肢があります。もしあなたがゼロの方向へqを丸めるのなら、r は負になるでしょう。
そうすると 0 <= abs(r) < に対するinvariant な変更です。そうではなく、負の無限大
方向へ向かって qのfloorを取ることもできますがこの場合 0 <= r < b が invariant な
ままです。
[update: fixed this para]



In mathematical number theory, mathematicians always prefer the latter choice (see e.g. 
Wikipedia). For Python, I made the same choice because there are some interesting 
applications of the modulo operation where the sign of a is uninteresting. Consider 
taking a POSIX timestamp (seconds since the start of 1970) and turning it into the 
time of day. Since there are 24*3600 = 86400 seconds in a day, this calculation is 
simply t % 86400. But if we were to express times before 1970 using negative numbers, 
the "truncate towards zero" rule would give a meaningless result! Using the 
floor rule it all works out fine.

数学的な数値理論 (mathematical number theory) からいえば、数学者は常に後者の選択肢を好
みます( Wikipedia http://en.wikipedia.org/wiki/Modulo_operation を参照してください)。
Python の場合わたしは同じ選択をしました。なぜなら、a の符号が重要でないときに modulo 
操作を行うようないくつかの興味深いアプリケーションがあったからです。1970年から開始した
数値である POSIX timesamp を考えてみましょう。さて一日は 24×3600 で86400秒ありますから、
この計算は単純に t % 86400 となります。しかしもし 1970 年以前を負の数値を使って表現し
ようとしたときに、the "truncate towards zero" rule would give a meaningless 
result!“ゼロ方向への丸め”規則では意味のない結果が出てしまうことになるのです! floor 
ルールを使うことでこれらすべてがうまくいったのです。


Other applications I've though of are computations of pixel positions in computer 
graphics. I'm sure there are more.


For negative b, by the way, everything just flips, and the invariant becomes:

ところで負の bに対してはすべてがちょうど反対になって、invariant becomes します:


0 >= r > b.

So why doesn't C do it this way? Probably the hardware didn't do this at the time C 
was designed. And the hardware probably didn't do it this way because in the oldest 
hardware, negative numbers were represented as "sign + magnitude" rather 
than the two's complement representation used these days (at least for integers). My 
first computer was a Control Data mainframe and it used one's complement for integers 
as well as floats. A pattern of 60 ones meant negative zero!

ではなぜ C はこのやり方にしなかったのでしょうか?おそらく、C が設計された当時のハードウ
ェアがそのようにしていたのでしょう。そしてそのハードウェアがその方式を採用していたのは
たぶん、最古のハードウェアでは負の数値は (少なくとも整数に対して)今日広く用いられてい
る2の補数による表現ではなく  "sign + magnitude" で表現していたからでしょう。
わたしが初めて使ったコンピューターは Control Data のメインフレームでこれは浮動小数点数
と同様に整数も1の補数を使っていました。
A pattern of 60 ones meant negative zero!


Tim Peters, who knows where all Python's floating point skeletons are buried, has 
expressed some worry about my desire to extend these rules to floating point modulo. 
He's probably right; the truncate-towards-negative-infinity rule can cause precision 
loss for x%1.0 when x is a very small negative number. But that's not enough for me to 
break integer modulo, and // is tightly coupled to that.

knows where all Python's floating point skeletons are buried (Python の浮動小数点数の 
skeltons がどこに埋まっているのかをしっている)という人物である Tim Peters はこの規則を
浮動小数点数の modulo にも拡張するというわたしの希望 (desire) に対していささかの懸念を
表明しました。おそらく彼は正しく、truncate-towards-negative-infinity ルールは xが非常
に小さな負の数であったときにx % 1.0 で presision loss (精度を失う?)を起こす可能性があ
ります。けれどもそれはわたしにとっては integer modulo を壊すほどには充分でないので、// 
が tightly coupled to that.

PS. Note that I am using // instead of / -- this is Python 3 syntax, and also allowed 
in Python 2 to emphasize that you know you are invoking integer division. The / 
operator in Python 2 is ambiguous, since it returns a different result for two integer 
operands than for an int and a float or two floats. But that's a totally separate 
story; see PEP 238.

PS.
わたしが / ではなく // を使っていたのに注意してください。これは Pyton 3 の構文ですが、
Python 2 を
and also allowed in Python 2 to emphasize
that you know you are invoking integer division.
Python 2 における / 演算子は曖昧です。
それは、二つの整数オペランドのときと、一つの整数と一つの浮動小数点数もしくは二つの浮動
小数点数がオペランドのときとで異なる結果を返すからです。しかしそれは完璧に別のお話です。
PEP 238を参照してください。

ねみー。

■_ 本日の巡回から

■_

grep ネタをまとめている余裕がなっしんg。

2010年08月24日

■_

なんでこんなに時間がないのだ

The art of ~ というタイトルの本が邦訳されると アートオブ ~ なタイトルになってしまう現象について。

■_ redditに訊け

正規表現を改良視してくれというお願い。


Any way to improve this regular expression? - Stack Overflow

Hi guys - I'm kinda a newbie at regular expressions, so would appreciate a bit of peer 
feedback on this one. It will be heavily used on my site, so any weird edge cases can 
totally wreak havoc. The idea is to type in an amount of an ingredient in a recipe in 
whole units or fractions. Due to my autocomplete mechanism, just a number is valid too 
(since it'll pop up a dropdown). These lines are valid:

1
1/2
1 1/2
4 cups
4 1/2 cups
10 3/4 cups sliced

The numeric part of the line should be its own group so I can parse that with my 
fraction parser. Everything after the numeric part should be a second group. At first, 
I tried this:

^\s*(\d+|\d+\/\d+|\d+\s*\d+\/\d+)\s*(.*)$

This almost works, but "1 1/2 cups" will get parsed as (1) (1/2 cups) 
instead of (1 1/2) and (cups). After scratching my head a bit, I determined this was 
because of the ordering of my "OR" clause. (1) satisfies the \d+ and (.*) 
satisfies the rest. So I changed this to:

^\s*(\d+\/\d+|\d+\s*\d+\/\d+|\d+)\s*([a-z].*)$

This almost works, but allows weirdness such as "1 1/2/4 cups" or "1/2 3 cups".
So I decided to enforce a letter as the first character after a valid numeric
expression:

^\s*(\d+\/\d+|\d+\s*\d+\/\d+|\d+)\s*($|[a-z].*)$

Note I'm running this in case-insensitive mode. Here's my questions:

   1. Can the expression be improved? I kinda don't like the "OR" list for 
      number, fraction, compound fraction but I couldn't think of a way to allow whole 
      numbers, fractions, or compound fractions.

   2. It would be extra nice if I could return a group for each word after the numeric 
      component. Such as a group for (10 3/4), a group for (cups) and a group for
      (sliced). There can be any number of words after. Is this possible?

Oh oops, missed one more case.. The amount can be expressed in decimal. So I've added 
one more OR clause: ^\s*(\d+\/\d+|\d+\s*\d+\/\d+|\d+|\d*\.\d)\s*($|[a-z].*)$


Well, it appears to me that you don't need OR conditions at all (but see below).

For the numeric bit, you could get away with:

\d+(\s+\d+/\d+)

which would handle all those fractional values.

I would still keep your decimal separate with an OR clause since it's likely to 
complicate things. So I think you could probably get away with something like:

^\s*((\d+\s)?(\d+/\d+)?|\d+(\.\d+)?)\s*([a-z].*)?$
 |   |                  |           |  |
 |   |                  |           |  +--- start of alpha section.
 |   |                  |           +------ optional white space.
 |   |                  +------------------ decimal (nn[.nn])
 |   +------------------------------------- fractional ([nn ][nn/nn])
 +----------------------------------------- optional starting space.

although that allows for an empty fractional amount so you may be better off with what 
you've got (whole, fractional and decimal in separate OR clauses).

I prefer the ([a-z].*)?$ construct to ($|[a-z].*)$ myself but that may just be an 
aversion on my past to have multiple line end markers in my RE :-)

But, in all honesty, I think you may be trying to swat a fly with a thermo-nuclear 
warhead here.

Do you really need to restrict what gets entered. I've seen recipes that call for a 
pinch of salt and a handful of sultanas. I personally think you may be being to 
restrictive in what you'll allow. I would have a free-form field for quantity and a 
drop-down for food-type (actually I would probably just allow free-form for the lot 
unless I was offering the ability to search for recipes based on what's in the fridge).
I believe that this regex should do what you want:

/^\s*(\d+ \d+\/\d+|\d+\/\d+|\d+)\s*(.*)/

For matching the specific words you should just do a split on whitespace after the 
parsing. There are some thing you don't want to do with regexes ;)

まあ、なかなか効率の良いものを書くのは大変ということで。

■_

んで。 昨日わたしもちょっと触れた話題ですが。


インテル・AMDのCPUアーキテクトが明かす: GNU grep が速い理由 - karasuyamatenguの日記

GNU grepの元祖作者がFreeBSDハッカーをschoolしている。

http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html

FreeBSD対GNU grepのパフォーマンスを議論していると思われるとことに「俺はgrepの初代作者
だ」と名乗って現われた男がいる。

履歴書(http://duckytech.com/resume.pdf)を見ると、GNU coreutilsに貢献した後、インテルや
AMDでCPUアーキテクトを勤めている男だ。これは話を聞いた方がよさそうだ。

FreeBSDユーザでもある彼はリストを観閲していたらたまたまGNU対BSDのgrep論争に当ってしま
ったようだ。BSDのリストにGNU grepの秘密を解く。

    * 技1: 全ての入力バイトを見ないから速い
    * 技2: 見るバイトに関しては極力少ないインストラクションを実行するから速い

GNU grepは有名な「Boyer-Mooreアルゴリズム」を使っている。これはターゲット文字列の最後
のキャラクタをテーブルと照合し、できるだけ無用とわかったインプットと飛ばしていうものだ。

(Boyer-Mooreって言えば教科書には出ているが実用例はあまり見ないアルゴリズムだ。しかも、
固定文字列のためのテクニックだと思っていたものが正規表現に使われているのはちょっと以外
だった。)

(略)

「正規表現にBMを使う」ってのは違うような気が。 このオリジナルオーサー氏が現状の GNU grep について言っているのか、 自分がこのようにコーディングしたのかに言及しているのかによもよるんですが、 現状でいうと、BMは使ってはいるけど検索対象が固定文字列(正規表現のメタ文字がない)が ひとつだけのときとかかなり限定されている場面だと思います。

とはいえ

why GNU grep is fast
GNU grep uses the well-known Boyer-Moore algorithm, which looks first for the final 
letter of the target string, and uses a lookup table to tell it how far ahead it can 
skip in the input whenever it finds a non-matching character.

GNU grep also unrolls the inner loop of Boyer-Moore, and sets up the Boyer-Moore delta 
table entries in such a way that it doesn't need to do the loop exit test at every 
unrolled step. The result of this is that, in the limit, GNU grep averages fewer than 
3 x86 instructions executed for each input byte it actually looks at (and it skips 
many bytes entirely). 

とかあるしなあ。

static size_t
EGexecute (char const *buf, size_t size, size_t *match_size, int exact)
{
  register char const *buflim, *beg, *end;
  char eol = eolbyte;
  int backref, start, len;
  struct kwsmatch kwsm;
  size_t i;
#ifdef MBS_SUPPORT
  char *mb_properties = NULL;
#endif /* MBS_SUPPORT */

#ifdef MBS_SUPPORT
  if (MB_CUR_MAX > 1 && kwset)
    mb_properties = check_multibyte_string(buf, size);
#endif /* MBS_SUPPORT */

  buflim = buf + size;

  for (beg = end = buf; end < buflim; beg = end)
    {
      if (!exact)
	{
	  if (kwset)
	    {
	      /* Find a possible match using the KWset matcher. */
	      size_t offset = kwsexec (kwset, beg, buflim - beg, &kwsm);
	      if (offset == (size_t) -1)
		{
#ifdef MBS_SUPPORT
		  if (MB_CUR_MAX > 1)
		    free(mb_properties);
#endif
		  return (size_t)-1;
		}
	      beg += offset;
	      /* Narrow down to the line containing the candidate, and
		 run it through DFA. */
	      end = memchr(beg, eol, buflim - beg);
	      end++;
#ifdef MBS_SUPPORT
	      if (MB_CUR_MAX > 1 && mb_properties[beg - buf] == 0)
		continue;
#endif
	      while (beg > buf && beg[-1] != eol)
		--beg;
	      if (kwsm.index < kwset_exact_matches)
		goto success;
	      if (dfaexec (&dfa, beg, end - beg, &backref) == (size_t) -1)
		continue;
	    }
	  else
	    {
	      /* No good fixed strings; start with DFA. */
	      size_t offset = dfaexec (&dfa, beg, buflim - beg, &backref);
	      if (offset == (size_t) -1)
		break;
	      /* Narrow down to the line we've found. */
	      beg += offset;
	      end = memchr (beg, eol, buflim - beg);
	      end++;
	      while (beg > buf && beg[-1] != eol)
		--beg;
	    }
	  /* Successful, no backreferences encountered! */
	  if (!backref)
	    goto success;
	}
      else
	end = beg + size;

      /* If we've made it to this point, this means DFA has seen
	 a probable match, and we need to run it through Regex. */
      for (i = 0; i < pcount; i++)
	{
	  patterns[i].regexbuf.not_eol = 0;
	  if (0 <= (start = re_search (&(patterns[i].regexbuf), beg,
				       end - beg - 1, 0,
				       end - beg - 1, &(patterns[i].regs))))
	    {
	      len = patterns[i].regs.end[0] - start;
	      if (exact)
		{
		  *match_size = len;
		  return start;
		}
	      if ((!match_lines && !match_words)
		  || (match_lines && len == end - beg - 1))
		goto success;
	      /* If -w, check if the match aligns with word boundaries.
		 We do this iteratively because:
		 (a) the line may contain more than one occurence of the
		 pattern, and
		 (b) Several alternatives in the pattern might be valid at a
		 given point, and we may need to consider a shorter one to
		 find a word boundary.  */
	      if (match_words)
		while (start >= 0)
		  {
		    if ((start == 0 || !WCHAR ((unsigned char) beg[start - 1]))
			&& (len == end - beg - 1
			    || !WCHAR ((unsigned char) beg[start + len])))
		      goto success;
		    if (len > 0)
		      {
			/* Try a shorter length anchored at the same place. */
			--len;
			patterns[i].regexbuf.not_eol = 1;
			len = re_match (&(patterns[i].regexbuf), beg,
					start + len, start,
					&(patterns[i].regs));
		      }
		    if (len <= 0)
		      {
			/* Try looking further on. */
			if (start == end - beg - 1)
			  break;
			++start;
			patterns[i].regexbuf.not_eol = 0;
			start = re_search (&(patterns[i].regexbuf), beg,
					   end - beg - 1,
					   start, end - beg - 1 - start,
					   &(patterns[i].regs));
			len = patterns[i].regs.end[0] - start;
		      }
		  }
	    }
	} /* for Regex patterns.  */
    } /* for (beg = end ..) */
#ifdef MBS_SUPPORT
  if (MB_CUR_MAX > 1 && mb_properties)
    free (mb_properties);
#endif /* MBS_SUPPORT */
  return (size_t) -1;

 success:
#ifdef MBS_SUPPORT
  if (MB_CUR_MAX > 1 && mb_properties)
    free (mb_properties);
#endif /* MBS_SUPPORT */
  *match_size = end - beg;
  return beg - buf;
}

size_t offset = kwsexec (kwset, beg, buflim - beg, &kwsm); の kwexec の中身でBM使ってたりするんですが、 そのほかの dfaexec や re_search、re_match では使ってないと思います (後ろ二つは glibc の regex です)。

kwset.c

/* Compute the shift for each trie node, as well as the delta
   table and next cache for the given keyword set. */
char *
kwsprep (kwset_t kws)
{
  register struct kwset *kwset;
(略)

  /* Check if we can use the simple boyer-moore algorithm, instead
     of the hairy commentz-walter algorithm. */
  if (kwset->words == 1 && kwset->trans == 0)
    {
      /* Looking for just one string.  Extract it from the trie. */
      kwset->target = obstack_alloc(&kwset->obstack, kwset->mind);
      for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i)
	{
	  kwset->target[i] = curr->links->label;
	  curr = curr->links->trie;
	}
      /* Build the Boyer Moore delta.  Boy that's easy compared to CW. */
      for (i = 0; i < kwset->mind; ++i)
	delta[(unsigned char) kwset->target[i]] = kwset->mind - (i + 1);
      kwset->mind2 = kwset->mind;
      /* Find the minimal delta2 shift that we might make after
	 a backwards match has failed. */
      for (i = 0; i < kwset->mind - 1; ++i)
	if (kwset->target[i] == kwset->target[kwset->mind - 1])
	  kwset->mind2 = kwset->mind - (i + 1);
    }
  else
    {
      /* Traverse the nodes of the trie in level order, simultaneously
	 computing the delta table, failure function, and shift function. */
      for (curr = last = kwset->trie; curr; curr = curr->next)
	{
	  /* Enqueue the immediate descendents in the level order queue. */
	  enqueue(curr->links, &last);
(略)

  /* Fix things up for any translation table. */
  if ((trans = kwset->trans) != 0)
    for (i = 0; i < NCHAR; ++i)
      kwset->delta[i] = delta[(unsigned char) trans[i]];
  else
    for (i = 0; i < NCHAR; ++i)
      kwset->delta[i] = delta[i];

  return 0;
}

#define U(C) ((unsigned char) (C))

/* Fast boyer-moore search. */
static size_t
bmexec (kwset_t kws, char const *text, size_t size)
{
  struct kwset const *kwset;
  register unsigned char const *d1;
  register char const *ep, *sp, *tp;
  register int d, gc, i, len, md2;

  kwset = (struct kwset const *) kws;
  len = kwset->mind;

  if (len == 0)
    return 0;
  if (len > size)
    return -1;
  if (len == 1)
    {
      tp = memchr (text, kwset->target[0], size);
      return tp ? tp - text : -1;
    }

  d1 = kwset->delta;
  sp = kwset->target + len;
  gc = U(sp[-2]);
  md2 = kwset->mind2;
  tp = text + len;

  /* Significance of 12: 1 (initial offset) + 10 (skip loop) + 1 (md2). */
  if (size > 12 * len)
    /* 11 is not a bug, the initial offset happens only once. */
    for (ep = text + size - 11 * len;;)
      {
	while (tp <= ep)
	  {
	    d = d1[U(tp[-1])], tp += d;
	    d = d1[U(tp[-1])], tp += d;
	    if (d == 0)
	      goto found;
	    d = d1[U(tp[-1])], tp += d;
	    d = d1[U(tp[-1])], tp += d;
	    d = d1[U(tp[-1])], tp += d;
	    if (d == 0)
	      goto found;
	    d = d1[U(tp[-1])], tp += d;
	    d = d1[U(tp[-1])], tp += d;
	    d = d1[U(tp[-1])], tp += d;
	    if (d == 0)
	      goto found;
	    d = d1[U(tp[-1])], tp += d;
	    d = d1[U(tp[-1])], tp += d;
	  }
	break;
      found:
	if (U(tp[-2]) == gc)
	  {
	    for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)
	      ;
	    if (i > len)
	      return tp - len - text;
	  }
	tp += md2;
      }

  /* Now we have only a few characters left to search.  We
     carefully avoid ever producing an out-of-bounds pointer. */
  ep = text + size;
  d = d1[U(tp[-1])];
  while (d <= ep - tp)
    {
      d = d1[U((tp += d)[-1])];
      if (d != 0)
	continue;
      if (U(tp[-2]) == gc)
	{
	  for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)
	    ;
	  if (i > len)
	    return tp - len - text;
	}
      d = md2;
    }

  return -1;
}

  

■_ んで、

スレッドを追いかけるとこういう流れに

why GNU grep is fast
Garrett Wollman wollman at hergotha.csail.mit.edu
Sun Aug 22 15:26:20 UTC 2010

In article <86k4nikglg.fsf at ds4.des.no> you write:
>Mike Haertel <mike at ducky.net> writes:
>> GNU grep uses the well-known Boyer-Moore algorithm, which looks
>> first for the final letter of the target string, and uses a lookup
>> table to tell it how far ahead it can skip in the input whenever
>> it finds a non-matching character.
>
>Boyer-Moore is for fixed search strings.  I don't see how that
>optimization can work with a regexp search unless the regexp is so
>simple that you break it down into a small number of cases with known
>length and final character.

The common case of regexps used in the "grep" utility (and, for
obvious reasons, universal in the "fgrep" utility) is fixed-length
search strings.  Even non-fixed-length regexps typically consist of
one one or two variable-length parts.  Matching a completely
variable-length regexp is just hard, computationally, so it's OK for
it to be slower.  There are other tricks you can do, such as
turning the anchors ^ and $ into explicit newlines in your search --
"^foo" is a very common regexp to search for, and it's really a
fixed-string search for "\nfoo" which is entirely amenable to the B-M
treatment.  You just have to remember that a matched newline isn't
part of the result.

The GNU regexp library also uses the Boyer-Moore (or is it
Boyer-Moore-Gosper?) strategy.

-GAWollman

The GNU regexp library also uses the Boyer-Moore (or is it Boyer-Moore-Gosper?) strategy. あれ? 勘違いしてたかしらん ○| ̄|_

■_ 本日の巡回から

■_

活動限界 ○| ̄|_

2010年08月23日

■_

・センゴク
奇襲失敗を逆手に取る。のかなあ。

クレイモア

■_ ハッシュテーブルの大きさ

この問題、衝突が発生しやすくなるとかいう話にもっていこうとしているのかな。


ハッシュ関数についての質問です。 - Yahoo!知恵袋
ハッシュ関数についての質問です。

bloomfield_i7さん

ハッシュ関数についての質問です。

ハッシュ関数 H(x) = x mod m で整数キーの集合を格納する場合、
mを2のべき乗となる数に選んだ場合に予想される問題点を述べよ。
という問題があるのですが、回答がわかりません><;
どなたかご教授願います。 

衝突の頻度はテーブルのサイズよりむしろハッシュ関数の質(性質?)によるところが大きい とかなんとか何年か前に読んだような記憶が(鶏頭モード炸裂)。 Hash table - Wikipedia, the free encyclopedia それっぽい記述はないなあ。

■_ Perl で Lisp

まあ awk で書いた人もいたらしいしねえ。


Perl with a Lisp - bugsplat

Perl with a Lisp

Sunday, 22 August 2010 around 2 o'clock PM

(略)


I've chosen to write this first implementation in perl. I know perl pretty well but 
more importantly I don't know lisp very well at all. I've done a little elisp hacking, 
but not much. I certainly don't know how all of the pieces fit together quite yet. 
This first post is really more about getting the fundamental data structure and 
list-manipulation routines and the reader down. Later posts will elaborate on eval and 
friends, as well as closures, scoping, and perl interop.

Perl を良く知っていたので(そして Lispの動作は良く知らなかったので)、Perl で
実装してみることにしました。
第一回目の今回は、データ構造と基本的なリスト操作のルーチンをつくります。
それとリーダー。 eval だのなんだのは次回以降のポストで。

Data Structure

Lisp represents most things fundamentally in terms of what's known as a cons cell. 
This is some sort of object that has two slots for other objects, be they primitives 
or other cons cells. Being a good little modern perl programmer, I've chosen to 
implement this as a small Moose-based class:

Lisp はほとんどのデータ構造をコンスセル (cons cell) として知られているもので
表現しています。
good little modern perl プログラマーである私は Moose ベースのクラスを使うよ


package Cell;

use Moose;

use overload
    'bool' => sub { return !shift->is_nil() },
    'fallback' => 1
;

has 'car'    => (is => 'rw');
has 'cdr'    => (is => 'rw');
has 'is_nil' => (is => 'ro', default => 0);

1;

Using Moose, we define an object with two read-write slots named car and cdr. This is 
due entirely to historical precident: car is the first element in the pair, cdr is the 
second. is_nil is there to allow us to define a fixed nil value later on. The overload 
allows us to use a Cell in a boolean context. Anything that doesn't have is_nil set is 
true;

二つの read-write スロットを持ったオブジェクト

Fundamental Functions
基本関数

Now that we've got the data structure done, let's define a few fundamental functions 
to work with it.

our $NIL = Cell->new(is_nil => 1);
sub nil
{
    return $NIL;
}

our $T = "t";
sub t
{
    return $T;
}

sub equal
{
    my ($a, $b) = @_;
    return t if $a eq $b;
    return nil;
}

Notice how $NIL is just hanging out there. It's the only Cell that will ever have 
_is_nil set. We return the reference to the singleton from the nil function. t is the 
opposite. We just return the atom t. equal exploits perl's built-in comparison 
operator eq to compare two things.

Now, the good stuff. List manipulation:
リスト操作関数を定義

sub cons
{
    my ($thing, $list) = @_;
    return Cell->new(car => $thing, cdr => $list);
}

sub list
{
    reduce { cons($b, $a) } (nil, reverse @_);
}

sub car
{
    my $thing = shift;
    confess "Argument to car must be a list"
        unless ref($thing) && ref($thing) eq 'Cell';
    return defined($thing->car()) ? $thing->car() : nil;
}

sub cdr
{
    my $thing = shift;
    confess "Argument to cdr must be a list"
        unless ref($thing) && ref($thing) eq 'Cell';
    return defined($thing->cdr()) ? $thing->cdr() : nil;
}

cons creates new Cells, setting their car and cdr as appropriate. The list function is 
a pure convenience thing to make setting up singly-linked lists easy. car and cdr do a 
small amount of error checking and call out to the given Cell's car() and cdr() 
methods.

Functions also defines some functions that will be used later, as well as some things 
that can walk lists and trees made from cons cells and do something with them. It 
implements a list_string function which will be imported as the (print) function, once 
we have symbol tables and function importing defined.

There are a bunch of tests for these functions in 01_list_manipulation.t.

Reader
以下略

What's your personal code kata? Have you written a lisp before? Have any tips for me?
blog comments powered by Disqus
© Pete Keen

■_

GNU grep は早い。それはなぜか。という話なんですが。


why GNU grep is fast

Hi Gabor,

I am the original author of GNU grep.  I am also a FreeBSD user,
although I live on -stable (and older) and rarely pay attention
to -current.

However, while searching the -current mailing list for an unrelated
reason, I stumbled across some flamage regarding BSD grep vs GNU grep
performance.  You may have noticed that discussion too...

Anyway, just FYI, here's a quick summary of where GNU grep gets
its speed.  Hopefully you can carry these ideas over to BSD grep.

#1 trick: GNU grep is fast because it AVOIDS LOOKING AT EVERY INPUT BYTE.

#2 trick: GNU grep is fast because it EXECUTES VERY FEW
INSTRUCTIONS FOR EACH BYTE that it *does* look at.

GNU grep uses the well-known Boyer-Moore algorithm, which looks
first for the final letter of the target string, and uses a lookup
table to tell it how far ahead it can skip in the input whenever
it finds a non-matching character.

(略)

Summary:

- Use Boyer-Moore (and unroll its inner loop a few times).

- Roll your own unbuffered input using raw system calls.  Avoid copying
  the input bytes before searching them.  (Do, however, use buffered
  *output*.  The normal grep scenario is that the amount of output is
  small compared to the amount of input, so the overhead of output
  buffer copying is small, while savings due to avoiding many small
  unbuffered writes can be large.)

- Don't look for newlines in the input until after you've found a match.

- Try to set things up (page-aligned buffers, page-sized read chunks,
  optionally use mmap) so the kernel can ALSO avoid copying the bytes.

The key to making programs fast is to make them do practically nothing. ;-)

Regards,

	Mike

BM法 ってUTF-8でも多バイト文字の文字列には効果が薄くなるんじゃ とかいう話題を昔出したような記憶が。 それはおいといても、locale を多バイト文字のものにすると 検索速度が2桁3桁のレベルで低下するとかいうレポートが絶えないしねえ。

GNU Grep and Out Of The Box Thinking -- Why GNU Grep Is So Fast (Boyer–Moore String Search Algorithm) : programming

■_ 無欲で強欲なバックトラック

Just another Ruby porter, 2010-8-c
[Ruby] 超欲張り無欲マッチ

この無欲マッチの話は結局バックトラックを抑制すればいいので、

/_(\{.+?\})\\mrm\{([CHP])\}_(\{.+?\})

を

/_(?>\{.+?\})\\mrm\{([CHP])\}_(\{.+?\})

とすればいける。 正規表現 - Rubyリファレンスマニュアルによると(?>)は超欲張りマッチということなので、
合わせ技で「超欲張り無欲マッチ」となる。
何を言ってるのかよくわからんが。

マニュアルによればなくなるかもしれないので使用禁止なのが痛い。 

++ とか ** のノリで ++? みたいなメタ文字が必要?

とはいえ、この「超欲張り無欲マッチ」の「バックトラック」動作がなんか引っかかるんだけど 眠いので良くわからない。

…続く?

■_ 本日の巡回から

2010年08月22日

■_

・例によって
記憶違いをしていたばかりか、よりによって逆方向にうっすら覚えていたという。 まあ Twitter / nari3: 「偽ポインタ」は思いつかなかったなー。今度から使わせ ... こういうのが引き出せたのだからいいとしよう(いいのか?)

Island Life
逆で、問題が出たのは32bitアーキテクチャ。

4GBの空間を目一杯使うようなプログラムだと、ランダムな32bit整数が
有効な領域を指すポインタと誤認される確率がとても高くなるということ。 

ありがとうございます。 冷静に考えれば見当がつきそうなものですがなぜ逆に覚えていたんだろう。

・リモコン


たった3年で・・・ « maclalala2
2007年までのスマートフォンをみるとゾッとするね。

これを見て連想されるのは今のTVやDVDデッキ類のリモコン。あれは技術屋が自分で使う事を考
えてつくった結果。「ふつうの人」が使う事をまったく考えていない。

アップルが次に出してくるのはTVでは?ってウワサされているけど、ぜひ革新的にシンプルなリ
モコンコントローラというのを出して欲しい。

昨年末に引いたケーブルテレビの STB のリモコンを良く使うのですが、 これがまたボタンがやたらとたくさんある代物なのですね。 わたしはともかくとしても、 両親が予期せぬところを押してしまってモードを変えてしまうのか何なのか 「なんか変になったからなおしてくれ」と云われることが度々。 とりあえず地上波とNHK BSのチャンネルだけ選択できればいいので、 もっとボタンの少ないやつお願い ○| ̄|_

■_

おわらねーーーー

Poetic License to Kill. - The Five Minute Introduction to Using Smalltalk-Style Traits Instead of Inheritance
Current Mood:
    thoughtful thoughtful

5分で分かる
Smalltalk スタイルの traits

Smalltalk-style traits are beginning to gain more traction outside of Smalltalk, but
there still seems to be a lot of misunderstanding about them. This is a ridiculously
quick and language-agnostic description of traits and how they work. Much of the
background is simply ignored and it's taken for granted that you understand the
conceptual problems with inheritance (both single and multiple).

Smalltalk スタイルの traits は beginning to gain more traction outside of Smalltalk で
すが、大きく誤解されているように見受けられます。このドキュメントは traits とそれがどの
ように働くのかについての ridiculously quick で language-agnostic な解説です。背景の多
くはただ単に無視されていて、あなたが理解している単一継承および多重継承両方共にある 
conceptual な問題と受け止められています。

# ばかばかしいほど、途方もなく
# agnostic 不可知論者

Cross-cutting concerns

When presenting alternatives to inheritance, there are a couple of things to keep in
mind. First, the core problem with inheritance as commonly used is that it tends to
tightly couple class responsibility with code reuse. A Person class is likely
responsible for the person's name and birthdate. The fact that it has save() and
update() methods is likely a convenience. For example (all examples are pseudo-code):

継承に代わるものを考えたとき、心に留めておくべきいくつかのことがらがあります。第一に、
一般的な用法としての継承に関する core の問題とは、コードの再利用により密に結びついた
二つのクラスの responsiblity に行き着きます。Person クラスというものはその人 (person) 
の名前と誕生日に対して responsible なようなものですが、実際にはそのクラスは 
save() や update() という便利であろうメソッドを持っています。
たとえば(すべての例がそうですが擬似コードを使っています):


    ORM orm .= new(list,of,connection,parameters);
    orm.save(person);

    // versus
    person.save();

In the examples above, you can see that you don't need to have a save() method
directly on the Person class. However, many find it convenient. In fact, it's
convenient enough that ...

先の例では save()メソッドを Person クラスが直接持つ必要はないことを理解できましたが、
しかしそれがあることが便利であることにも気がつきました。実際には次のようにできることは
とても便利なのです


    person.save();
    order.save();
    journal.save();
    session.save();


In that example, we have a bunch of objects which are saved. We don't know and don't
care how they're saved, but it's a good bet that most of those items are not related
by inheritance (aside from a base "Object" or "UNIVERSAL" class,
or whatever your language of choice uses). Behaviours which unrelated classes might
implement are often referred to as "cross-cutting concerns" because many
classes, regardless of their relation to each other, might want to implement them.

この例ではセーブされたオブジェクトの bunch をわたしたちは扱っています。わたしたちはこ
れらのオブジェクトがどのようにセーブされるのかを知りませんし、気にする必要もありません。
しかし、継承には関係がないこれらのアイテムの大部分にとってセーブできるのはよいことです
(ベース“オブジェクト”もしくは“UNIVERSAL”クラス、はたまたあなたの好きなその言語での
該当するもの)。クラス群に関係ない振る舞いは、しばしば "cross-cutting concerns"
と見られるものとして実装されるかもしれません。それは多くのクラスがそれらそれぞれとの関
係とは無関係に振る舞いを実装することが求められるかも知れないからです。

Examples of cross-cutting concerns are:

cross-cutting concerns の例には以下のようなものがあります:


    * Object persistence (ORMs)
      オブジェクトの永続性
    * Logging
      ログ記録
    * Serialisation/deserialisation
      シリアライズ/逆シリアライズ
    * Memory allocation
      メモリー割り当て
    * Synchronisation
      同期処理


Declarative statements
(宣言文)

The next problem which often comes up is code which looks declarative, but really
isn't. For example, I used to be the administrative coordinator for a luxury furniture
company. However, 25% of my time, I was also their only software developer (it was my
first programming job). How might this be modelled?

頻繁に話題に上っている次の問題は宣言的に見えるコード (code which looks declarative) で
すが、実際には宣言ではありません。たとえばわたしは luxury furniture company 
(豪華家具の会社?) むけの administrative coordinator でしたが、
にも関わらず自分の時間の 25%では単なるソフトウェア開発者でもあったのです 
(わたしの最初のプログラミング関係の仕事でした)。これはどのよう
にモデル化すればよいのでしょうか?


class AdminCoordinator isa OfficeGrunt, Programmer { ... }


So far nothing looks too unusual. We've inherited from the two jobs I had. What
happened, though, if I finished all of my office paper work and had 50% of my time
left over for programming? Simply put: I had to stand there and twiddle my thumbs
because I was paid a higher hourly rate when programming (I don't believe this was
legal, but I needed the programming experience) and thus wasn't allowed to exceed 25%
of my time working as a programmer. Thus, both OfficeGrunt and Programmer might have
their own salary() methods. Which one gets called? That could be a compile-time error
due to ambiguity (Eiffel does this and I recommend looking at how it works), a runtime
error, or it might simply call the salary() method from OfficeGrunt because that's the
one you've inherited from first.

それほど unnusual なものには見えません。わたしたちはわたしが持っていた二つの仕事を受け
継いでいました。にもかかわらず、もしわたしが自分の officeでの paper workをすべて終えて
いて、なおかつ自分のプログラミングのための時間が 50% も残っていたしたら起こったことは
なんでしょうか? Simply put: I had to stand there and twiddle my thumbs
なぜならわたしはプログラミングに対してはより高額な給与を得ていて自分の時間のうち 25% 
を超えてはプログラマーとして働くことを許されませんでした(これが合法だとは信じられませ
んが、わたしにはプログラミングの経験が必要だったのです)。したがって、OfficeGrunt と 
Programmmer の両方がそれぞれ固有の salary() メソッドを持っているかもしれません。さてで
はどちらが呼び出されるのでしょうか?これはコンパイル時のエラー(Eiffel はこれを行います。
これがどのように働いているのかを調べてみるのをお勧めします)、もしくは実行時エラーとな
る可能性があります。さもなければ OfficeGrunt からの salary() メソッドの呼び出しだけで
もエラーになります。なぜなら、それはあなたが最初から継承していたものだからです。



Mixins don't solve the problem here (note that Scala traits are basically mixins and
also fail to solve this) because they actually have a "last wins" rule and
the Programmer.salary() method would be called instead. In Ruby, for example, we might
have this:

mixin はここではこの問題を解決しません(Scala の traits は基本的にはmixins であり、同様
にこの問題の解決には失敗してしまうということに注意してください)。なぜなら mixin には
"last wins" ルールというものがあって、Programmer.salary() メソッドが呼ばれる
ようになってしまうからです。たとえば Ruby では次のようになるでしょう:

    class AdminCoordinator
        include OfficeGrunt
        include Programmer
        # more code here
    end

If you were to call the ancestors method on AdminCoordinator, you would see something
like this:

もしあなたが AdminCoordnator の先祖のメソッド (ancestors method) を
呼び出したならば、次のような結果を見ることになるでしょう:

    irb(main):026:0> AdminCoordinator.ancestors
    => [AdminCoordinator, Programmer, OfficeGrunt, Object, Kernel]

In short, you might think that mixins "mix in" the methods into your class,
but they actually just diddle the inheritance hierarchy and this causes some
frustrating issues.

手短に言うと、mixins とはクラスにそのメソッドを "mix in" 
(入れ込む、混ぜ込む) するものだと考えているかもしれませんが、
しかし mixin は実際には継承階層を単に diddle (だます、ごまかす、ペテンにかける) 
だけでなので、欲求不満の種となってしまいます。

Ultimately the problem is that mixins, like inheritance, rely on the order in which
things are declared, but let's step back and think about my job at that furniture
company.

結局のところは継承のような mixin が、宣言の順番に依存している点に問題がありますが、
step back してわたしの仕事について考えてみましょう。

    * Ovid worked at the furniture company as both an office grunt and a programmer.
      Ovid は家具会社で Office grunt 兼プログラマーとして働きました。

    * Ovid worked at the furniture company as both a programmer and an office grunt.
      Ovid は家具会社でプログラマー兼 Office grunt として働きました。

You'll note that both of those sentences declare something about me while reordering
some terms. The order of those terms does not matter. This is what
"declarative" code is about; it makes a declaration and the order in which
it declares things does not matter.

この両方のセンテンスともがわたしに関する何かを declare していることに気がつくでしょう。
一部の terms が並べ替えられていますがそういった terms の順序は重要ではありません 
(does not matter)。それが "declarative" code is about; 
であるということなのです。コードを declaration とし、その declares things の
順序を重要でなくするということです。


Solving this with Smalltalk-style traits
(この問題をSmalltalk形式の traitsで解決する)


Smalltalk-style traits, also known as "roles" (particularly in the Perl
world), are declarative and cleanly separate class responsibility and code reuse.
We'll start calling them roles because the term "trait" is rather overloaded
in the programming world.

Smalltalk スタイルの traits は(特に Perl 方面で) “roles”として知られているもので、ク
ラスの responsibility とコードの再利用を declarative かつ cleanly に分割したものです。
わたしたちはこれを role と呼ぼうと考えています。なぜなら “trait”という用語はプログラ
ミング世界においては overloaded されすぎているからです。


A role does several things (a bit of hand-waving here):
role はいくつかのことがら (a bit of hand-waving here) を行います


    * It might provide behaviour (methods)
      role は振る舞いを提供するかもしれません

    * It might require behaviour (acting sort of like an interface)
      role は振る舞いを要求するかもしれません

    * Any conflicts (duplicate methods) must be resolved at compile-time
      すべての衝突 (重複したメソッド) はコンパイル時に解決されなければなりません。

A role might look like a Ruby mixin or a partial class.
Here is how the "Programmer" role might look:

ある role は Ruby の mixin 、あるいはパーシャルクラスのように見えるかもしれません。
次の例は“プログラマー”のrole がどのように見えるかというものです:


    role Programmer {
        // something, even another role, must implement this
        // 他の role であっても、実装していなければならないなにか
        requires int seniority();

        // here's a method we provide
        // わたしたちが提供するコード
        method salary(float hours_worked) {
            return hours_worked * (12 + ( this.seniority() / 10 ) );
        }
    }

And when composed into a class:
そしてクラスに集成した場合:

    class AdminCoordinator
      isa Employee
      does OfficeGrunt, Programmer {
        int seniority; // we should fail at compile time without this
                       // because Programmer requires it
                       // プログラマーが要求しているのだからこれがないのならコンパイル時に
                       // 失敗させるべき
    }

But that should fail at compile time because OfficeGrunt also has a salary method and
roles do not allow you to get away with this ambiguity. Roles should allow you to
exclude conflicting methods. Let's say that company policy requires that a person
always get paid the highest salary amongst their several roles. The code might look
like this:

しかしこれはコンパイル時に失敗すべきです。なぜなら OfficeGrunt も salary メソッドを持
っているのにも関わらず roles はその曖昧さ (ambiguity) を解決していないからです。roles 
はメソッドの衝突をあなたが exclude (除外、排除、追い出す) するのを可能にすべきなのです。
ある人が常に いくつかの roles の中でもっとも高額のサラリーを支払われることを企業のポリ
シーが要求しているとしてみましょう。するとそのコードは次のようになるでしょう:

    class AdminCoordinator
      isa Employee
      does
        OfficeGrunt -salary,  // exclude the salary method  salaly メソッドを exclude する
        Programmer
    {
        int seniority;
    }

However, in my case, my salary had to be distributed across the different tasks I was
doing, so we need each of those methods. In this case, we can rename them.

しかしわたしのケースでは、わたしが行っているのと異なるタスクをまたがってわたしのサラリ
ーは distribute されなければなりません。ですからわたしたちにはこれらのメソッドそれぞ
れが必要なのです。今回のケースではリネームができます。

    class AdminCoordinator
      isa Employee
      does
        OfficeGrunt salary -> grunt_salary,
        Programmer  salary -> programmer_salary
    {
        int seniority;
        method salary(float hours) {
            return
              this.grunt_salary(.75 * hours)
              +
              this.programmer_salary(.25 * hours);
        }
    }

Note that absolutely nothing in the above is dependent on the order in which the roles 
are consumed. There is also no ambiguity present.

先の例では roles が消費された (consumed) 順序に依存することはabsolutely に nothing だ
ということに注意してください。あいまいさも存在していません (There is also no ambiguity 
present)。

What now?

There is, unfortunately, a bootstrapping problem with roles. On at least one Smalltalk
project mailing list, I saw the lead developers veto using roles (traits) because
other people were not using them. Surprisingly, it's the Perl community which has
embraced them wholeheartedly. We use them extensively at the BBC on the PIPs project.
PIPs is the central metadata repository for the BBC and as you might imagine for the
world's largest broadcaster, there's a huge codebase managing the metadata. Almost all
of this code is in Perl and we started using roles in an attempt to simplify our code.

残念なことに、roles にはブートストラップ問題 (bootstrapping problem) が存在しています。
少なくとも一つの Smalltalk プロジェクトのメーリングリストにおいてわたしは lead deveoper
たちがother people were not using them という理由によってroles (traits) の使用に対して
拒否権を発動したのを見ました。
Surprisingly, it's the Perl community which has embraced them wholeheartedly.
We use them extensively at the BBC on the PIPs project.
PIPs is the central metadata repository for the BBC
and as you might imagine for the world's largest broadcaster,
there's a huge codebase managing the metadata.
Almost all of this code is in Perl and we started using roles in an attempt to simplify our code.

# veto → 拒否権は強すぎ?


Aside from the "nobody uses them" argument (one which will erode with time),
others argue that the problems which roles address may not be real. I've heard this
multiple times and I don't understand it. First, working on large-scale code bases
tends to magnify problems which might not even be noticed in small projects. Second,
even the briefest of internet searches reveal plenty of problems with people trying to
shoehorn everything into some inheritance model and dealing with the resultant bugs.
Of course, the fact that there's been forty years of arguing over how to implement
inheritance properly (even single inheritance!) should indicate that something is
amiss.

"nobody uses them" (誰も使っていない) という時間とともに erode (腐食する、浸
食される、壊れる) するであろう主張を別にすれば、roles が対処しているという問題について
のその他の主張は may not be real (受け入れられない?) です。わたしはこれを何度も聞いて
いますが理解していません。第一に large-scale code bases で作業することは、小規模プロジ
ェクトでは気付かれれもしないであろう問題を誇張 (magnify) してしまう傾向にあります。第
二に、internet searches の briefest  でさえ、some inheritance model にすべてを押し込め 
(shoehorn) ようとする試みについてのplenty of problems とその結果として生じるバグとの関
係を暴露してしまいます。40年以上にわたって主張されてきた適切な継承の実装というものがそ
れがたとえ単一継承であったとしても should indicate that something is amiss
というのが事実なのです。

#よくわからん

This has been a ridiculously short introduction to roles and I've omitted many things
I would have liked to include. Though there's a strong formal background behind them,
they are very easy to use and once understood, map very cleanly to developer's
understanding of their task at hand. Unfortunately, it's very much a "chicken and
egg" problem on encouraging wider adoption of them. If they're available in your
programming language of choice, I encourage you to start using them on smaller, less
critical projects to better understand how they can make your projects easier to
understand and manage.

このアーティクルは roles に対する ridiculously short introduction で、
I would have liked to include な many things をわたしは省略してしまいました。
Though there's a strong formal background behind them,
they are very easy to use and once understood, 
map very cleanly to developer's understanding of their task at hand. 
残念なことに、traits (や roles、あるいはそれに類するもの) を広く採用するのを推進するに
あたっての問題はまったくもって“鶏と卵”の問題です。
もしあなたの  programming language of choice で traits などが使えるのなら、
traits などがあなたのプロジェクトをどのように
easier to understand and manage にするのかがよりよく理解できるであろう、
小さくて less critical なプロジェクトから使ってみることをわたしはお勧めします

最後までいけるとふんだんだがなあ _| ̄|○

■_ call by

今日は Rubyスレで!


Ruby 初心者スレッド Part 37 
919 デフォルトの名無しさん [sage] 2010/08/22(日) 15:09:41 ID: Be:
    メソッドおよび関数の引数渡しについて質問です。
    RubyでFixnumクラスを引数にした場合、値渡しになっているようです。

    def foo(x); x.div(2); end

    a = 10
    foo(a)
    pp a -> 10

    一方で、StringクラスやArrayクラスを引数にすると参照渡しになっています。

    def bar(x); x.push('world');end

    b = ["hello"]
    bar(b)
    pp b -> ["hello", "world"]


    「プログラミングRuby 第2版」を読んでいるのですが、参照渡し・値渡しに関する記述は
    特に見つからず、どういうルールで引数が渡されるのかよくわかりません。
    Rubyではクラスによって値渡しになるか、参照渡しになるかが自動的に決まるのでしょうか?
    明示的に値渡し、参照渡しを指定する書き方はありますか?
    よろしくお願いします。

920 デフォルトの名無しさん [sage] 2010/08/22(日) 15:20:56 ID: Be:
    Fixnumは実装の都合で値渡しになる。2^32-1 か 2^64 -1 までの整数だな。
    あとはtrue、false、nilか。

    Cが分かるなら、どういうビット表現になってるか調べてみてもいいかも。



921 デフォルトの名無しさん [sage] 2010/08/22(日) 15:24:01 ID: Be:
    divメソッドって非破壊でしょ
    その例じゃ値渡しなのかわからない 

922 デフォルトの名無しさん [sage] 2010/08/22(日) 15:28:22 ID: Be:
    def foo(n); n += 1; puts n; end
    => nil
    irb(main):028:0> x = 1; puts x; foo(x); puts x
    1
    2
    1
    => nil
    irb(main):026:0> x = 2**64-1; puts x; foo(x); puts x
    18446744073709551615
    18446744073709551616
    18446744073709551615
    => nil
    irb(main):027:0> x = 2**64; puts x; foo(x); puts x
    18446744073709551616
    18446744073709551617
    18446744073709551616

    ありゃりゃ。

923 デフォルトの名無しさん [sage] 2010/08/22(日) 15:31:21 ID: Be:
    n += 1 も n = n + 1 で、要は再代入だから意味ないな。
    整数に破壊的メソッドって何かあったっけ?

924 デフォルトの名無しさん [sage] 2010/08/22(日) 15:43:20 ID: Be:
    たしか>>920の言う実装の都合により無いよ
    無理やりFixnumクラスに破壊的メソッドを定義して試すと
    >>919の言う値渡しにはなっていないことが分かる
    irb(main):001:0> class Fixnum;attr_accessor :bar;end
    => nil
    irb(main):002:0> def foo(x); x.bar = 1;end
    => nil
    irb(main):003:0> a = 10
    => 10
    irb(main):004:0> a.bar = 10
    => 10
    irb(main):005:0> foo(a)
    => 1
    irb(main):006:0> a.bar
    => 1 

925 919 [sage] 2010/08/22(日) 16:24:38 ID: Be:
    なるほど。実は全部参照渡しだけど、Fixnumは破壊的メソッドを持っていないので
    呼び出された側で呼び出し側のオブジェクトの値を変更することができないということですか。

926 デフォルトの名無しさん [sage] 2010/08/22(日) 16:46:41 ID: Be:
    初心者スレなんだっけ

    Rubyの人は、Integerクラスをクラスとかメソッドとかの説明には使わないんだ
    扱いが特殊だから 

927 デフォルトの名無しさん [sage] 2010/08/22(日) 17:01:09 ID: Be:
    immutableなので状態を気にしなくても
    まあまず問題は起こらない 

928 デフォルトの名無しさん [sage] 2010/08/22(日) 17:26:02 ID: Be:
    どこに 1 というデータが入ってるんですかという問に答えられないので嫌 

929 デフォルトの名無しさん [sage] 2010/08/22(日) 19:25:01 ID: Be:
    >>919
    Rubyではクラスによって値渡しになるか、参照渡しになるかが自動的に決まるのでしょうか?


    プリミティブ以外は全部参照 

930 デフォルトの名無しさん [sage] 2010/08/22(日) 19:46:04 ID: Be:
    Javaかよ!

931 デフォルトの名無しさん [sage] 2010/08/22(日) 20:10:08 ID: Be:
    Rubyのは、いわゆる参照の値渡しなんじゃね? 

932 デフォルトの名無しさん [sage] 2010/08/22(日) 20:18:32 ID: Be:
    実装の話をすると、ほとんどのオブジェクトは内部的には構造体になっていて、普段は
    ポインタのやりとりで扱ってる。
    Fixnumなんかは、ちょっとした細工を行うことで、整数値自体を、普通のポインタなら
    絶対に取らないポインタ値に変換して、ポインタと見なせる形で受け渡ししている。

933 デフォルトの名無しさん [sage] 2010/08/22(日) 20:25:57 ID: Be:
    >>931
    それがいわゆる参照渡しなんじゃね? 

■_ 本日の巡回から

あそびにいくヨ! 守礼皇18号 
734 風の谷の名無しさん@実況は実況板で [sage] 2010/08/22(日) 20:53:12 ID:5vlsciAw0 Be:
    湿っぽい空気にしたまま去るのもあれ何でネタ提供
    通常型のアシストロイドの予約始まってる
    http://www.chara-ani.com/details.aspx?prdid=B10801334

    で、うにゃ-くんとうなーたんはまだですか? 

欲しい。が。んーむ

■_ あ

arton さんから献本をいただいたのにまだ途中までしか読んでない。 割り込み要因が多すぎるかも。

2010年08月21日

■_

徒然。


Just another Ruby porter, 2010-8-b
コンビニ] ポイントカードはお持ちではないですか?

近所のコンビニの店員に「お持ちですか?」派と「お持ちではないですか?」派がいて困る。
派と言っても「ないですか?」派は一人しかいないんだけど、
もう口が「いいえ」になってるのに「ないですか?」と続けられると
「い、にゃい」とかわけのわからない受け答えになったり。

店員が尋ねるこのパターンですが、 「ポイントカードはいいですか?」 「ポイントカードは大丈夫ですか?」 と訊かれて固まったことが何回か。 特に後者は不思議な言い回しだと思うんだけど、使ってる人もそれなりにいるっぽい。

■_ GC 本読書会

at 新宿某所。 読書会なのに肝心な本を忘れてきた人がいました。


アルゴリズム編6
保守的 GC conservative GC

GCの種類
  保守的GC 
  正確なGC

保守的GCとは?
 ポインタと非ポインタとを識別できないGCのこと

不明瞭なルート
 レジスター
 コールスタック
 グローバル変数領域

たとえばコールスタックに積まれている変数の中身
(ビットパターン)だけをみてそれがポインターかどうか判断できるか?

ポインタと非ポインタの識別
  潜在的にポインタの可能性があるもの

正しくアラインメントされた値か?
ヒープ内を指しているか?
  オブジェクトはヒープに置かれるのだから
オブジェクトの先頭を指しているか?

ポインタのような非ポインタ
  ポインタっぽければポインタにしとけ→「保守的な姿勢」

#shiro さんが shibuya.lisp あたりで 64bit アーキテクチャでは
#ポインター/非ポインターの誤判定が増えたという話をされたような
#覚えがあるけど詳細思い出せず。
#ポインターじゃないものをポインターに判定して回収されないゴミが
#増えるという話だったかなあ?
#たぶんこれ。↓
#本を読む 「Shibuya.lispテクニカルトーク#3」観覧
#Conservative GCの限界
#
#    * Boehm GC
#          o Cのポインタに見えたらポインタにする
#          o hashtableのchainedでfalse pointerになりがち
#だいぶ記憶と違うな ○| ̄|_ 不明瞭なデータ構造 union { long n; void *ptr; } ambigous_data; ↑のような構造体がメモリ上にあったとき、さあそれはポインターか否か? メリット 処理系がGCに依存しない デメリット ポインタと非ポインタに識別する際にコストがかかる ポインタの誤識別によるヒープの圧迫 使用できるGCアルゴリズムが制限される 不明瞭なデータ構造を明瞭にするために 領域を分けて 正確なGC exact GC ポインタと非ポインタを正しく識別できるGC 「正確なルート」 →作る手法は様々だが 言語処理系が援助している 詳しくは 実装編で タグ付け ポインタの値が必ず最下位2ビットが0→非ポインタとの識別に利用する Ruby → 最下位ビットが立ってたら FIXNUM レジスタ、スタックなどをルートとしない VMを使っている場合にはVM上のコールスタックを使うとか ポインタの誤判定がなくなる 言語処理系がGCに対してなんらかの援助をしないといけない 実装に負担 赤くなったJava 間接参照 ハンドラ経由のオブジェクト参照 ルートとオブジェクトの間にハンドラが一枚挟まる 間接参照でオブジェクトを扱うと、 参照先のオブジェクトを移動してもハンドラの内容を書きかえればOK メリット コピーGCを実装可能に デメリット アクセス速度低下 129p にあるハンドラとは? 「ハンドル」がならんだものではなかろうか? 「ハンドラー」はたとえば割り込み処理をする「割り込みハンドラー」とか。 むかーーしのWindowsやMac(Classic)でのプログラミング メモリ領域のハンドルを確保→使うときにはその領域を「ロック」 6.6 MostlyCopyingGC Bartlett が Scheme→Cトランスレータのために公案 不明瞭なルートから指されているオブジェクト以外をコピーするGC 前提条件 ルートは不明瞭なルート 不明瞭なデータ構造は持たない →オブジェクト内のフィールドのポインタ/非ポインタを正しく判定できる オブジェクトサイズは任意 32ビットCPU (他に適用できないわけではない) ヒープ構造 一定サイズのページに区切られる アロケーション チャンクのサイズや割り当てるオブジェクトサイズによって動作が異なる 使用ページ内に充分な空きがある/ない ページサイズを超えるような大きなオブジェクト CONTINUEDフラグを設定 CONTINUEDページにオブジェクトを割り当てない理由 総ページの半数を超えるページが「使用中ページもしくは追加予定のページ」 となったら mostly_copying() 呼び出し p137~p139 図 Errataあり。 二刷でなおってます konozamaのおかげで二刷でした 図13 X、Y,Dが回収されていません →MostlyCopyingGCの特色 mostly_copying() 「十分に大きな値」とは? promote_page() ・ヒープ内のものであるか ・ページの番号が$current_spaceと同じか ・ページにはOBJECTフラグがついているか CONTINUEDなページに割り当てを許さない理由 ページごとにフラグ必要 page_scan() copy() メリット コピーGCのメリット デメリット コピーGCの + ルートから参照されたオブジェクトを持つページ内の、 すべてのオブジェクトが生きていると見なされてしまう 6.7ブラックリスト 保守的GCのデメリットの一つ ポインタの誤識別 → 本来ゴミなオブジェクトが生き延びてしまう に対処 Boehm のブラックリスト ポインタの誤識別による被害 ブラックリスト→要注意アドレス一覧 ブラックリスティング アロケーション 要注意アドレスにアロケーションするオブジェクトを限定 小さなオブジェクト 子オブジェクトを持たないオブジェクト メリットデメリット 保守的GCの、ヒープの圧迫が軽減 オブジェクトアロケート時にブラックリストのチェックが必要 ・保守的GCを採用した場合、 ゴミが溜まっていってどうしようもならなくなったりしない? → GC を持っている処理系は一日一回再起動すべき ---- 保守的GCここまで -- 世代別GC オブジェクトに「年齢」の概念を導入 GCを一回生き延びたオブジェクトは一歳 新世代オブジェクトと旧世代オブジェクト マイナーGC/メジャーGC (小規模/大規模) 旧世代オブジェクトに対するGCは頻度を下げる (ゴミになりにくいから)。 昇格(殿堂入り) マークスイープGCやコピーGと併用するための手法 Ungarの世代別GC 図1 ヒープ領域の構成 新世代領域 $new_start 生成領域 $suvivor1_start 生存領域 $suvivor2_start 旧世代領域 $old_start 記憶集合 $rs メリット 新世代オブジェクトを重点的にGCすることで時間を短縮 記憶集合 旧世代オブジェクトから新世代オブジェクトへの参照を記録しておくためのもの ライトバリア 旧世代オブジェクトを記憶集合へ記録しておくために利用 三点チェック 参照元が旧世代オブジェクトか ポインタ更新後の参照先オブジェクトは新世代オブジェクトであるか 参照元オブジェクト オブジェクトの構造 年齢 コピー済みフラグ 記憶集合への記録済み付フラグ 図6 アロケーション new_obj() コピーGCのそれとほぼ同じ。$new_freeは生成領域のチャンクの先頭を指す マイナーGC 生成領域が一杯になったらマイナーGC起動 年齢チェック→promote() forwarding コラム 生存領域があふれたら? メジャーGC 特筆することないよ ただしメジャーGCにコピーGCを使うと利用可能な領域がさらに小さくなるよ→現実的でない メリット スループットの改善 マイナーGCによって時間的コストが低く抑えられる ミューテーターの最大停止時間を短縮するために→トレインGC デメリット 前提が崩れると… ・マイナーGCにかかる時間が増大 ・メジャーGCが頻発 逆効果になる可能性 生成領域→生存領域 →旧世代領域 一回生き延びた さらに生き延びた #自分がいる会社の製品で使ってますという話が。 ヘッダー領域の大きさってどのくらいだろう? 「昇格」するのに必要なマイナーGCの回数ってどう決めるの? いきなり旧世代領域にオブジェクトを格納させたい。ちょー重要なオブジェクトとか。 7.5 世代間の参照を記録する方法 記憶集合を使うとメモリ領域の使用効率がよろしくない 記憶集合に代わる方法 カードマーキング 旧世代領域を一定サイズごとに分割 (カード) カードに対応するマークビットを用意 メリットデメリット ページマーキング カードのサイズをページと同じサイズにする (ページ→仮想記憶のページングのあれ) ダーティビット メモリ保護機能を利用 ページ→4KiB (64ビット環境では?) 7.6 複数世代管理GC 新生代から旧世代へと昇格するオブジェクトを少なくするkとode GCの時間を減らすのが世代別GC。 → 世代の数を増やしたらどうか? あまり増やすと… 二世代もしくは三世代がベスト? (二世代って要するにふつーの世代別GCでしょ?) 真ん中の世代ではマークアンドスイープ? グローバル変数あまり作るな 旧世代に持って行くなフラグ欲しいね 7.7 トレインGC 世代別GCにおけるメジャーGCで利用 メジャーGCでの停止時間の増大を抑制 旧世代領域を一定サイズに分割 車両 列車 (→トレイン) #章の構成がえぐい #メリットデメリットの解説なしにコードの説明 #トレインてなに~ # 同族をまとめるためのもの? マイナーGC 新世代領域が一杯になったら発動 copy() new_car() 「引数がNULLだったら、一つの車両から成る新たな列車を作ります」 to_car() minor_gc() to_car = new_car(NULL) メジャーGC 先頭列車の先頭車両をGC対象とする major_gc() to_car = new_car(NULL) ← 新しい列車の生成 reclaim_train() scan_rs() 回収できる領域が少なくない? → GCによる停止時間が短いよ! ライトバリア write_barrier() new_objとnew_objが属する列車・車両 後ろの車両から前の車両への参照のみを記録→なぜでしょうか? この章は図が少ない? メリット Ungarの世代別GCに代表される世代別GCの問題 一度のメジャーGCでは「車両」を対象とする →ミューテーターの最大停止時間の増大を抑制 循環したゴミも回収できる 複数空間コピー法 ゴミをなすオブジェクト群すべてがいつかは同じ列車に配置される →列車ごと回収できる デメリット トレインGCのライトバリアはUngarの世代別GCにおけるライトバリアよりも 実行時のオーバーヘッドが大きい。 →スループットに劣る 車両よりも大きなオブジェクトはどうするの? 車両、列車はどのくらいの数ができるの?

次回の日程は未定でござんす。

■_ What are the best languages for getting into functional programming? - Quora

関数型言語に入門したいのだけどどの言語がいいのですか?


What are the best languages for getting into functional programming? - Quora

Quora

On a meta-note, a great way to get into the general concept of functional programming 
is to dabble in several languages so that the abstract patters come into the 
foreground.

Adam Smith • Insert a dynamic date here

Cannot add comment at this time.
 
Answer Summary
 
Many people think Haskell is the best language for getting into functional programming. 
The community is good and it takes functional programming "to its logical conclusion."

多くの人が Haskell を関数型プログラミングを理解するのに最適な言語であると考えています。
そのコミュニティは良く、

Scheme also deserves special mention, due to its long history as a teaching language, 
and the correspondingly rich quality of its instructional materials.

Other choices (bold for choices with > 1 person supporting them):

    * F#
    * Clojure

    * Scala
    * OCaml/SML
    * Erlang


If you want to plumb the depths of FP theory and experience FP beauty, Haskell is the 
best language.  There are plenty of books, an active IRC channel and excellent mailing 
lists.

If you want to dip your little toe in the FP waters, Scala and OCaml (or F#) offer a 
gentler way to approach FP.  Scala is more OO and OCaml is more ML/FP flavored.  
Clojure is also an excellent choice and has the best concurrency primitives around.

If you're doing it for the purpose of learning, get thee to Haskell. It takes the 
paradigm to its logical conclusion.

I found Haskell very frustrating at first. I think my mistake was spending too much 
time writing code. I've gotten more as a newbie from reading good Haskell than writing 
my own bad Haskell; the blog entries written by engineers from Galois Inc. are often 
enlightening: http://www.galois.com/blog/

When you settle down to writing code, you'll find there are a lot of compile errors, 
and they're all type errors. This is frustrating too, at first, until you have the 
"Haskell Experience": that once your program compiles, it works. Just ... 
works. Sure, you might have reversed the operands to division somewhere, but those are 
the sorts of bugs that are left; no more bugs of the form, "Oh, you have to 
sandwich calls to snark.foo() between calls to blark.openFooWindow() and 
blark.closeFooWindow(), but they only nest one deep, and we've already opened the 
window sometimes here, so...". It challenges my preconceptions about where bugs 
come from, and how much automated tools can help; for instance, SQL injection attacks 
are compile errors in reasonable Haskell programs, because user-input strings are of a 
different type than SQL queries.

I am still a journeyman at Haskell, but I am amazed that it is simultaneously among 
the most concise, beautiful, and high-performing languages. It shows that large 
improvements in software notation are possible.

Start with Scheme.  I write Haskell 14 hours per day, but I think Scheme is the best 
place to start.

一日あたり14時間Haskellで書いていたけど Scheme の方が入門にはいいと思った

Depending on where you're coming from, Haskell likely introduces a whole bunch of 
concepts at once, which makes it tough to master them all.  Scheme is a good place to 
become comfortable with higher-order programming without having to think about type 
classes, monads, and strictness annotations.  Plus, the best intro programming 
textbook uses Scheme and is available online: http://htdp.org/.  If you're an 
experienced programmer, it may seem elementary at first, but it will get interesting 
if you stick with it.

After that, go learn Standard ML for the module system and Haskell for the purity.  
And have fun!


"I write Haskell 14 hours per day, but I think Scheme is the best place to start."

Awesome.


Haskell and OCaml are great languages, but they introduce a lot more than functional 
programming. That's actually a positive feature, but if someone wants to learn *just* 
functional programming to start Scheme is the best bet.

I'd also say "learn Haskell right after Scheme" is another great 
recommendation and I've yet to execute on that myself (I went off to Common Lisp, 
OCaml, Scala and a bit of Clojure).

best languages for getting into functional programming? : programming

■_ 根深い誤解

ああ、つっこみの書き込みしたい


Pythonのお勉強 Part39 
6 デフォルトの名無しさん [] 2010/08/21(土) 18:54:51 ID: Be:
    とあるゲームを作成しており、二次元配列に盤面の状態を保持しています。
    REDO機能を実装するため、すべて盤面の状態を保持しておきたいのですが、
    再帰関数の引数に二次元配列を渡すと、参照渡しになっているため
    関数の呼び出し先で状態を書き換えると上書きされてしまいます。

    この場合、値渡しにすればよいと思うので、copyモジュールの
    deepcopy()を使おうと思っていますが、ほかに何か方法はありますでしょうか?

    よろしくお願いいたします。 

47 デフォルトの名無しさん [sage] 2010/08/21(土) 19:12:23 ID: Be:
    そもそも参照渡ししかないんだってw
    なんでdeepcopyじゃダメなの? 

48 デフォルトの名無しさん [sage] 2010/08/21(土) 19:16:49 ID: Be:
    >>47
    モジュールを使う以外に、標準的なやりかたがあるのかなあと思いまして。
    ありがとうございました! 

49 デフォルトの名無しさん [sage] 2010/08/21(土) 22:17:21 ID: Be:
    >>> a = [[1, 2, 3], [4, 5, 6]]
    >>> [x[:] for x in a]
    [[1, 2, 3], [4, 5, 6]]
    こんな感じでコピーして渡せばいいはず。一次元配列のほうが楽だけどな 

「『値渡し』しかない」なんだがねえ。

■_ 本日の巡回から


一つ前へ 2010年8月(中旬)
一つ後へ 2010年9月(上旬)

ホームへ


Copyright (C) 2010 KIMURA Koichi (木村浩一)
この文書の無断転載はご遠慮ください(リンクはご自由にどうぞ)。

メールの宛先はこちらkbk AT kt DOT rim DOT or DOT jp