「ほっ」と。キャンペーン

とりとめのないことを書いております。
by tempurature
カテゴリ
全体
プログラミング
scheme
verilog
未分類
以前の記事
2016年 04月
2016年 03月
2016年 02月
2016年 01月
2015年 12月
2015年 11月
2015年 10月
2015年 09月
2015年 08月
2015年 07月
2015年 06月
2015年 03月
お気に入りブログ
PHPで競技プログラミング
メモ帳
最新のトラックバック
ライフログ
検索
タグ
人気ジャンル
ブログパーツ
最新の記事
情報処理技術者試験 お疲れ様..
at 2016-04-17 18:55
基本情報技術者試験 平成27..
at 2016-04-14 04:48
基本情報技術者試験 平成27..
at 2016-04-13 23:03
苦い薬(ハーブ、サプリメント..
at 2016-04-09 14:03
「おバカ度チェックリスト」を..
at 2016-03-24 09:54
外部リンク
ファン
記事ランキング
ブログジャンル
画像一覧
<   2015年 11月 ( 15 )   > この月の画像一覧
【Haskell】少しいじりました
象さんの本に

factorial :: (Integral a) => a -> a
factorial 0 = 1
factorial n = n * factorial (n - 1)

と書いてあったので、

fib :: (Integral a) => a -> a
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

と入力して、ghciで、map fib [1..100]を実行すると、驚くほどの遅さ。

だけれども、gaucheでも(fib 100)はフリーズしてしまった。で、アルゴリズムをよく見てみると、木再帰になっているではないか!!

ということで書きなおしてみました。

fib2 :: (Integral a) => a -> a
fib2 0 = 1
fib2 1 = 1
fib2 2 = 2
fib2 n = head (fibLoop (n-2) [2,1,1])
fibAppend [a,b,_] = (a+b) : [a,b]
fibLoop n l = if (n == 0) then l else fibLoop (n-1) (fibAppend l)

map fib [1..100]が一瞬で出力されました。めでたしめでたし(これはひどい)

[PR]
by tempurature | 2015-11-30 23:20 | プログラミング
lispに疲れたのでhaskellでも。
schemeは何でも自分で作れるのがいいのですが、何でも自分で作らないといけないのが疲れます。Common Lispでは多少緩和されるのでしょうけれども、括弧とMITスタイルの長ったらしい名前には正直辟易させられるところがあります。

書店でやたら異彩を放つHaskellの書籍は、SICP同様原著が読めるようです。


で、その姉妹本でErlangを扱うのもあるのですが、それはなんと日本語訳をWeb上で読むことができます。



Haskellはシェルスクリプトに似た文法なのが、心を和ませます。

ただ、schemeもCommon LispもOCamlもHaskellもWindows版がヘボだから物凄く辟易させられるのですけれども。その点ではracketは優秀すぎる。非英語圏の人はracketを使うべき。


[PR]
by tempurature | 2015-11-30 22:09 | プログラミング
プログラミング言語の相関図(?)
lispはJoel本に感化されて始めました。とはいえ、Common Lispではなく、Schemeとracketですけど。On Lisp読みたいけど、実際にCommon Lispを触っている人でも結構敬遠しているみたいですね。

私の頭のなかでは、プログラミング言語はアセンブラ・Ada・Lispを頂点とする三角形の中に収まっていると考えています。

c0364169_22490450.png
なんとなく書いてみた相関図です。Lispは、コンピュータの歴史の中では最も古い言語の1つと言われており、ある意味コード効率が最高です。つまり、アセンブラとLispの間にはコード効率という軸があると考えます。また、プログラミング言語には、信頼性という軸もあるらしく、それがアセンブラ・Adaの辺を成していると考えました。

上図から、コード効率を求めるならば動的型付けを、信頼性を求めるならば静的型付けを選択すべきであることがわかります。

Adaと他の言語群との間に大きな空白がありますが、ここには細々としたマイナー言語が入ると思われます。Adaがまだそれほどクローズアップされていないので、その近辺の言語にもスポットライトが当たっていないということだと思います。

さて、私たちはどの言語を選択すべきなのでしょうか?適材適所というのが現実的な解ですが、プログラミング言語を習得する上で、マルチパラダイムは敬遠したほうがいいように思います。マルチパラダイムといえばJavaやPythonが思いつきますが、とってつけたようなオブジェクト指向や関数型指向の機能にはとんでもない深遠な意味が含まれているので危険なのです。むしろ、その考え方の源流となった言語を習得すべきでしょう。私の中でおすすめなのが、アセンブラ・Bシェル・scheme・haskell・Eiffelです。F#・D・Adaはマルチパラダイムなので非常に危険です。

C、Java、Pythonを習得すべきでないというのではなく、これらの言語はコーディングするときに使う言語なのです。

[PR]
by tempurature | 2015-11-29 23:44 | プログラミング
男女比1:1の「正直女子さんぽ」というのはいかがなものかと
今日の昼、「正直女子さんぽ」という番組が放映されていました。
11/28の出演者は、ずんの2人、柳原可奈子、松岡茉優の4人だと思うのですが、ずんの2人ばかりがしゃべっていました。TVなんて無料なんだから文句言うなよという考え方もあるかと思いますが、それにしても最近の番組はやる気ないのが多いように思います。

女子3人、オカマ1人くらいの比率だったらまだご愛嬌で済ませられると思うのですが、これではあまりにも名が体をなしていないというか。何かにつけ何か言いたくなるのは歳のせいなのですかね。

[PR]
by tempurature | 2015-11-28 14:26
OS本の章末問題を解く(2)
前回の記事、「OS本の章末問題を解く(1)」で作成したプログラムをCygwinで実行してみました。改変なしにgccのコンパイルを通すことができました。

結果としては、play_child関数を10000回呼び出すのに35.5秒かかりましたので、プロセス生成のオーバーヘッドは3.55msです。

Ubuntuで実行したときと比べると、3.55ms/55.6us=83.8倍の時間がかかっています。Linuxの他のディストリビューションやBSD系OSで実行してみるともっと面白い結果が得られるかもしれません。また、VisualStudioのプロセス関数だともっと速いのかもしれないです。


[PR]
by tempurature | 2015-11-28 14:13 | プログラミング
OS本の章末問題を解く(1)
「オペレーティングシステム入門」並木美太郎著、サイエンス社 の第4章章末問題、問題1を解きました。

【問題1】UNIX系OS(たとえばLinux)において、fork, wait, exitシステムコールを用いてプロセスを生成してみよ。プロセス生成のオーバヘッドを示せ。

【ヒント】Linuxのfork, wait, exitをmanしてみる。

【解答】(※間違っているかもしれません)

Ubuntu 15.0をvirtual box上で動かしました。Ubuntuのfork, wait, exitに関するmanページは全部英語なので全部読むことはしませんでした。man waitにそれらしいソースコードがあったので、適当にシュリンクしました。

[ソースコード]

/*
 *   fork-wait-exit sample
 */

#include <sys/wait.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>

void die(const char* str) {
  perror(str);
  exit(EXIT_FAILURE);
}

//#define DEBUG(str) printf("%s\n", str);
#define DEBUG(str) ;

void play_child() {
  pid_t cpid, w;
  int status;

  DEBUG("play_child: start");
  cpid = fork();
  switch (cpid) {
    case -1:
      die("fork");
    case 0: /* child */
      DEBUG("Hello, world. I'm a child.");
      exit(0);
    default: /* parent */
      if (wait(EXIT_SUCCESS) == -1)
        die("wait");
      DEBUG("play_child: end");
      return;
  }
}

int main() {
  int i;
  for (i = 0; i < 1000000; i++)
    play_child();
}

[実行結果]

$ time ./a.out

real 0m55.569s
user 0m1.100s
sys 0m17.508s

今回試験した環境では、55.6s / 1,000,000回 = 55.6usで、プロセスを1つ生成するごとに55.6us秒かかると考えられます。


[PR]
by tempurature | 2015-11-25 00:43 | プログラミング
【racket】テキストエディタ画面を作成する
racketでテキストエディタ画面を表示するプログラムを作成しました。

c0364169_23311554.png
フォントは「MS ゴシック, 12pt」です。racketでフォントを設定するのは、苦労しましたがなんとかできました。

racoでコンパイルすると、exeファイルを作成してくれますが、実行ファイルのサイズが9MBにもなってしまいました。

【ソースコード】

#lang racket

(require racket/gui)

; definitions

(define *app-name* "textbox")

; body

(define style-list (new style-list%))
(define delta (make-object style-delta% 'change-size 12))
(send delta set-face "MS Gothic")
(send style-list new-named-style "Standard"
      (send the-style-list basic-style))
(define my-standard-style (send style-list find-named-style "Standard"))
(send my-standard-style set-delta delta)

(define frame (new frame% [label *app-name*] [width 300] [height 300]))
(define canvas (new editor-canvas% [parent frame]))
(define text (new text%))
(send text set-style-list style-list)
(send canvas set-editor text)

(send frame show #t)

[PR]
by tempurature | 2015-11-23 23:39 | scheme
【Gauche】rangeのテストコードを書いてみた
プログラミングGaucheの10章がユニットテストのトピックだったので、rangeのテストコードを書いてみました。手書きで書けば10分で済んだものの、横着してスクリプトで書いたので、3〜4時間かかってしまいました。

【テストコードを出力するスクリプト】

#!/bin/sh -f

function p { # in case of Cygwin Bsh -> Windows Gauche
  printf "%s" "$1"
  shift
  while [ -n "$1" ]; do
    printf " %s" "$1"
    shift
  done
  printf "\r\n"
}

function test_range {

  ITEM='range('$1
  if [ -n "$2" ]; then ITEM=$ITEM', '$2; fi
  if [ -n "$3" ]; then ITEM=$ITEM', '$3; fi
  ITEM=$ITEM')'

  PYINP='python3 -c '"'"'print(list('$ITEM'))'"'"

  PYOUT=`echo $PYINP | sh`
  SCHOUT='(list '`echo $PYOUT | sed -r 's/(\[|\]|,)//g'`')'

  SCHINP='(range '"$1"
  if [ -n "$2" ]; then SCHINP=$SCHINP' '"$2"; fi
  if [ -n "$3" ]; then SCHINP=$SCHINP' '"$3"; fi
  SCHINP=$SCHINP')'
  
  p '(test* "'$ITEM' [Python 3.4 Documentation]"'
  p '       '$SCHOUT
  p '       '$SCHINP')'
  p ''

}

p ";; -*- coding: shift_jis -*-"
p ""
p "(use gauche.test)"
p '(test-start "range.scm")'
p ""
p '(load "./range")'
p ""
test_range 10
test_range 1 11
test_range 0 30 5
test_range 0 10 3
test_range 0 '-10' '-1'
test_range 0
test_range 1 0
p ""
p "(test-end)"

【出力されたテストコード】

;; -*- coding: shift_jis -*-

(use gauche.test)
(test-start "range.scm")

(load "./range")

(test* "range(10) [Python 3.4 Documentation]"
       (list 0 1 2 3 4 5 6 7 8 9)
       (range 10))

(test* "range(1, 11) [Python 3.4 Documentation]"
       (list 1 2 3 4 5 6 7 8 9 10)
       (range 1 11))

(test* "range(0, 30, 5) [Python 3.4 Documentation]"
       (list 0 5 10 15 20 25)
       (range 0 30 5))

(test* "range(0, 10, 3) [Python 3.4 Documentation]"
       (list 0 3 6 9)
       (range 0 10 3))

(test* "range(0, -10, -1) [Python 3.4 Documentation]"
       (list 0 -1 -2 -3 -4 -5 -6 -7 -8 -9)
       (range 0 -10 -1))

(test* "range(0) [Python 3.4 Documentation]"
       (list )
       (range 0))

(test* "range(1, 0) [Python 3.4 Documentation]"
       (list )
       (range 1 0))


(test-end)

[PR]
by tempurature | 2015-11-19 21:25 | scheme
UNIXでテキスト編集とプログラム実行を交互に高速に行うには?
まず、私はvi派です。emacsだと何でもできることはわかっているのですが、あのデフォルトのいけてなさとモッサリ感がいやなので使ってないです。

テキスト編集とプログラム実行を交互に行う場合、すぐ思いつくルーチンとしては、

(1) viで編集、上書き保存して終了、プログラム実行、vi起動、を繰り返す
(2) 2つターミナルを開いて、一方でviを開き、一方でプログラム実行を行う

の2つがあると思います。(1)の長所としては、省スペースなのと、マウスを使わなくともよいというのがあります。(2)では、プログラムの実行結果をすぐ参照できるというのがあります。

では、もっといい方法はないのでしょうか?
vi上でコマンドを入力できるみたいなので、とりあえずそれをやってみました。

:!./hogehoge.sh

こうすると、viの編集画面からシェルスクリプトの画面に1度切り替わってコマンドを実行し、ポーズします。

さらにvimであれば、この:!./hogehoge.shを他のコマンドにエイリアスすることもできます。

:command R !./hogehoge.sh

このエイリアスによって、以下のコマンドでコマンドを実行できます。

:R

このことによって、(1)よりも高速にコマンドを実行することができそうです。ただ、実際やってみたところ、:Rとタイプするのはあまり楽ではない(エイリアスの1文字目は大文字でなければならない)のと、コマンドを実行するたびにポーズするので、あまり(1)と変わらないと思いました。

Cygwinのvimがいけてないだけかもしれませんけれども… うーん


[PR]
by tempurature | 2015-11-19 06:25 | プログラミング
pythonで迷走してみる
Gauche版rangeのテストを行うために、pythonを久しぶりに動かしてみました。
それで思ったのは、色々な言語を触っている人にとってインタプリタはとても有用だということです。

$ python
Python 2.7.10 (default, Jun  1 2015, 18:05:38)
[GCC 4.9.2] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> range 1 2
  File "<stdin>", line 1
    range 1 2
          ^
SyntaxError: invalid syntax
>>> (range 1 2)
  File "<stdin>", line 1
    (range 1 2)
           ^
SyntaxError: invalid syntax
>>> range(1 2)
  File "<stdin>", line 1
    range(1 2)
            ^
SyntaxError: invalid syntax
>>> range(1, 2)
[1]
>>> for i in range(1, 10): print(i)
... ;
  File "<stdin>", line 2
    ;
    ^
SyntaxError: invalid syntax
>>> for i in range(1, 10): print(i)
...
1
2
3
4
5
6
7
8
9

[PR]
by tempurature | 2015-11-19 04:32 | プログラミング