natalという名前の何か

tcl included

Unixプログラミング

2010/06/12

use strict;
use warnings;

my @args = qw(echo hogehoge | tee /dev/tty > /dev/null);
system(@args) == 0 or die "status $?";
system("@args") == 0 or die "status $?";
exec(@args);

execは「末尾呼び出し」のように実行中のプログラムを別のプログラムに移行させる。 systemはforkしてから子プロセスでexec, 親プロセスでwaitする。 (waitpidではなく本当に文字通りwaitしているとの説もあるが理由は不明。)

Perlのexecおよびsystemは、引数が1個の場合、 例えば上のように@argsを1個の文字列"@args"にまとめた場合には (必要なら) シェルを通してコマンドを実行する。 引数が2個以上の場合はシェルを起動しないので パイプやリダイレクト等の記号は解釈されない。

2010/04/11

use strict;
use warnings;

my $dir;
opendir($dir, '.') or die "opendir(.): $!";
while (1) {
  my $s = readdir($dir);
  last if (!defined($s));
  next if ($s eq '.' || $s eq '..');
  print $s, "\n";
}
closedir($dir);

lastはbreak
nextはcontinue
eqはstringwise equal (==はnumerically equal)

2010/03/27

use strict;
use warnings;
use Socket;

sub tcp_socket {
  my $skt;
  socket($skt, PF_INET, SOCK_STREAM, scalar getprotobyname('tcp'))
      or die "socket: $!";
  return $skt;
}

sub tcp_server {
  my ($port, $address) = @_;
  my $server = tcp_socket;
  bind($server, scalar sockaddr_in($port, $address)) or die "bind: $!";
  listen($server, SOMAXCONN) or die "listen: $!";
  return $server;
}

sub tcp_client {
  my ($port, $address) = @_;
  my $client = tcp_socket;
  connect($client, scalar sockaddr_in($port, $address)) or die "connect: $!";
  return $client;
}

my $server = tcp_server(0, INADDR_ANY);
my ($port) = sockaddr_in(getsockname($server));
my $pid = fork();
if ($pid == 0) {
  close($server);

  my $client = tcp_client($port, inet_aton('localhost'));
  print $client "hello, world\n";
  close($client);

  exit;
}
print "pid=$pid\n";
my $skt;
accept($skt, $server) or die "accept: $!";
print <$skt>;
close($skt);

close($server);
$pid = wait();
print "pid=$pid status=$?\n";

サーバソケットを作るとき、ポート番号を0とすると適当な番号が割り振られる。 その番号を調べてからforkする。

子プロセスがサーバソケットを閉じても、親プロセスには影響しない。

ファイルハンドルやscalarがきもちわるいがこれはPerlの問題であり、 Unixは関係ない。

リストに代入したり、引数を与えたりするところはリストコンテキスト。 同じ関数名でもコンテキストが違えば全く別の関数になる場合がある。 scalarと明示的に書けばスカラーコンテキストになるが、 リストコンテキストを明示する書き方はない。 「デフォルトで」リストコンテキストになるように書く。 例えばmy ($port) = sockaddr_in(...);のように 左辺をリストにすることで右辺をリストコンテキストにする。

ファイルハンドルは$line = <$fh>;のように1行ずつ入力したり、 print $fh "hello\n";のように出力する。 間違えて$fhの後にカンマをつけると、 print STDOUT $fh, "hello\n";の意味になったりする。

2010/03/24

use strict;
use warnings;

my $pid = fork();
if ($pid == 0) {
  while (1) {
    print "hello\n";
    sleep(1);
  }
}
print "pid=$pid\n";
sleep(10);

kill("KILL", $pid);
$pid = wait();
print "pid=$pid status=$?\n";

forkはファイルシステムに依存しない。 実行ファイルを指定せずにプロセスを作れる。 ファイルシステムが壊れていてもプロセスを作れるかもしれない。

waitは子プロセスが終了するまでブロックする。 waitを呼ぶ前に既に子プロセスが終了している場合でも、 ゾンビプロセスが残っているので、 後から呼ばれたwaitはそのゾンビプロセスを見つけて戻る。

子プロセスが終了するとSIGCHLDが送られてくるので、 シグナルハンドラを使うやり方もあるかもしれない。

killはSIGKILLだけではなく他のシグナルを送るのにも使える。

テキストエディタを

作る。

index

• Lua
• MzScheme
• JavaScript
• フォント (2008/2/20)
  • OpenGLの例 (2008/2/27)
  • GLUT + MzScheme (2008/3/29)
  • GLUT + MzScheme (2) (2008/4/20)
  • gap buffer (2008/7/7)
  • abbrev (略称展開) (2008/8/15)
• Arc
  • インストール
  • ラムダ計算プログラム (2008/2/6)
    • 使い方
    • ラムダ計算について
  • 相互再帰たらいまわし関数をつくるYコンビネータのようなもの (2008/4/10)
• メモ

Lua

• LCSとdiff (2008/7/30)
• Luaでパーサジェネレータを作る (2008/9/11)
• LuaからC言語のモジュールをロードする (2008/9/24)

MzScheme

• MzSchemeのlex.ss (2008/4/1)
• MzSchemeのyacc.ss (2008/4/2)
• クリップボード (2008/5/29)

JavaScript

• ブラウザでλ計算 (2008/3/8)

フォント

OSやライブラリを気にせず簡単に読み書きできるフォントファイルを作る。

JISX0213(所謂第3,4水準漢字)用bdfフォントのページ
から

• K14-2004-1.bdf.gz
• A14.bdf.gz

を取ってくる。
なぜ14ドットか、なぜ1面だけか、気にしてはいけない。

gzip -d K14-2004-1.bdf.gz A14.bdf.gz

gzipコマンドを使わなくてもブラウザで直接閲覧できるようだが、 bdfは次のようなテキスト形式。
ていうか一般にはどうなっているか知らない。
……
STARTCHAR 名前
……
ENCODING 文字コード
……
BITMAP
16進数
……
16進数
ENDCHAR
……
用途にもよるが、簡単なプログラムで使うにはもっと単純な形式がいい。
例えば '!' のデータは
!0000181818181010100000181800
という1行だけでいい。
そのような形式に変換するプログラムを書いてみよう。

半角

ASCIIの図形文字は94個。

   00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
20 SP !  "  #  $  %  &  '  (  )  *  +  ,  -  .  /
30 0  1  2  3  4  5  6  7  8  9  :  ;  <  =  >  ?
40 @  A  B  C  D  E  F  G  H  I  J  K  L  M  N  O
50 P  Q  R  S  T  U  V  W  X  Y  Z  [  \  ]  ^  _
60 `  a  b  c  d  e  f  g  h  i  j  k  l  m  n  o
70 p  q  r  s  t  u  v  w  x  y  z  {  |  }  ~  DEL

まずはRubyで書く。

i = open('A14.bdf')
o = open('ascii.txt', 'wb')
while s = i.gets
  s.chomp!
  if /^ENCODING ([0-9]+)$/ =~ s
    c = $1.to_i
    next if c <= 32 || 127 <= c
    s = i.gets
    s.chomp!
    while /^BITMAP$/ !~ s
      s = i.gets
      s.chomp!
    end
    o.putc(c)
    s = i.gets
    s.chomp!
    while /^ENDCHAR$/ !~ s
      s.downcase!
      o.print s
      s = i.gets
      s.chomp!
    end
    o.print "\n"
  end
end
i.close
o.close

ここからが本題。
なぜSchemeやCommon Lispで書かないのか。
決して書けないわけではない。
MzSchemeならこう書ける。 (MzScheme以外の処理系で実行しないでください)

(let ((i (open-input-file "A14.bdf"))
      (o (open-output-file "ascii.txt")))
  (do ((s (read-line i) (read-line i)))
    ((eof-object? s))
    (set! s (regexp-match #rx"^ENCODING ([0-9]+)$" s))
    (when s
      (let ((c (string->number (cadr s))))
        (when (and (< 32 c) (< c 127))
          (do ((s (read-line i) (read-line i)))
            ((regexp-match #rx"^BITMAP$" s)))
          (write-char (integer->char c) o)
          (do ((s (read-line i) (read-line i)))
            ((regexp-match #rx"^ENDCHAR$" s) (newline o))
            (display (string-downcase s) o))))))
  (close-input-port i)
  (close-output-port o))

ソースファイルをmake_ascii.scmとして

mzscheme --script make_ascii.scm

とすればスクリプトとして実行できる。

書いてみて気になったのは、変数を導入するたびに
letといくつかの括弧を書かなければならないこと。
インデントも深くなる。
あと、正規表現が標準化されていない。
自分で使うだけなら非標準でもいいが、
ソースを人に見せるとき躊躇する。布教できない。普及しない。
それなら「実装が仕様を決める言語」のほうがかえって良いんじゃないか。

全角

JIS漢字は94×94の表になっている。
この表には第三水準までしか収まりきれない。
第四水準は「第二面」にある。が、面倒なので無視することにした。

文字コードはASCIIの図形文字 (94種類) を2バイト並べたもの。
大雑把に言うとこれに0x8080を足せばEUC-JPになる。
Shift_JISは複雑。

i = open('K14-2004-1.bdf')
o = open('kanji.txt', 'wb')
while s = i.gets
  s.chomp!
  if /^ENCODING ([0-9]+)$/ =~ s
    c = $1.to_i
    s = i.gets
    s.chomp!
    while /^BITMAP$/ !~ s
      s = i.gets
      s.chomp!
    end
    o.putc(c / 256 + 128)
    o.putc(c % 256 + 128)
    s = i.gets
    s.chomp!
    while /^ENDCHAR$/ !~ s
      s.downcase!
      o.print s
      s = i.gets
      s.chomp!
    end
    o.print "\n"
  end
end
i.close
o.close

注：MzScheme以外で実行しないでください

(let ((i (open-input-file "K14-2004-1.bdf"))
      (o (open-output-file "kanji.txt")))
  (do ((s (read-line i) (read-line i)))
    ((eof-object? s))
    (set! s (regexp-match #rx"^ENCODING ([0-9]+)$" s))
    (when s
      (let ((c (string->number (cadr s))))
        (do ((s (read-line i) (read-line i)))
          ((regexp-match #rx"^BITMAP$" s)))
        (write-byte (+ 128 (quotient c 256)) o)
        (write-byte (+ 128 (modulo c 256)) o)
        (do ((s (read-line i) (read-line i)))
          ((regexp-match #rx"^ENDCHAR$" s) (newline o))
          (display (string-downcase s) o)))))
  (close-input-port i)
  (close-output-port o))

OpenGLの例

上で作ったフォントファイルを利用する例。

半角文字をクリックすると対応する区の漢字を表示。
右クリックで終了。というようなプログラムを作る。

GLUTによる「手抜き」OpenGL入門
を参考にした。
別のことをやりたいときはinit, display, mouse
を書き換えるだけでいい。

main.h

見れば分かる

main.c

resizeで座標変換の設定。
何もしなければ左上が (-1,1) 右下が (1,-1) になる。
(0,0) が左上で (w,h) が右下になるように変換する。
mainは初期化してイベントループに入るだけ。
このときascii.txtとkanji.txtをロードする。
ウインドウのサイズと位置はコマンドライン引数で指定できる。例えば

main.exe -geometry 640x480+0+0

とすると幅が640で高さが480で位置が (0,0) となる。

font.c

load_ascii, load_kanji

フォントファイルを読んで配列に書き込む。
リロードしてもよい。

ascii, kanji

文字コードに対応するビットマップデータへのポインタを返す。

magic numberがたくさん出てくるが、パラメータ化すると分かりにくいと思う。

test.c

このファイルを差し替えるだけで色々なものが作れる。
glPixelStoreiは
ビットマップデータを配列に格納するときの流儀を設定する。
glBitmapの引数は

1. 幅
2. 高さ
3. ラスタ位置 (glRasterPosで指定) のx座標の補正
4. ラスタ位置のy座標の補正
5. 描画後のラスタ位置をx方向に移動する量
6. 描画後のラスタ位置をy方向に移動する量
7. ビットマップへのポインタ

である。

コンパイル

MacとWindowsで動作確認した。
実行するときはascii.txtとkanji.txtを忘れないように。

Windows

コンパイラを手に入れるのが少し面倒。
手っ取り早いのはGHCとか。HaskellコンパイラだがCコンパイラにもなる。
現時点の最新版のインストーラはghc-6.8.2-i386-windows.exeだが
これを使うと簡単だった。
PATHを通すのも自動でやってくれてOpenGLやGLUTも最初から入っている。

ghc test.c main.c font.c -lglut32 -lopengl32

実行時にglut32.dllが必要になるかもしれない。
GLUT for Win32のページにある。
定番のBorland C++無償版を使いたい人はdllだけでなくヘッダなども自分で入れる。

Mac OS X

1. #include <GL/glut.h>を
   #include <GLUT/glut.h>に直す
2. Terminalでコンパイル

   cc -framework OpenGL -framework GLUT test.c main.c font.c
   

Arc

インストール

Windowsの場合。他は省略。

MzScheme

MzScheme の version 352 が必要。最新版ではArcが動かない。
インストーラを起動すると

To uninstall, simply remove the folder.

と書いてあるので覚えておく。

インストール後すぐにコマンドプロンプトを起動して

mzscheme

……としても多分使えない。
MzScheme.exe の場所を登録する必要がある。
たとえば C:\Program Files\MzScheme\MzScheme.exe なら
環境変数 PATH に C:\Program Files\MzScheme
を追加する。詳細は省略。

Arc

これは arc0.tar をダウンロードして展開して実行するだけ。

tar -x -f arc0.tar
cd arc0
mzscheme -f as.scm

tar.exe を持ってない人は
全然関係ないが Windows版のTeX のインストーラ (texinst*.zip) だけ取ってくるとその中に入っていたりする。

ラムダ計算プログラム

使い方

ソースをArcのソースと同じところに置く。
ファイル名は lambda.arc とする。

Arcを起動して lambda.arc をロードすると beta や beta* などが使える。

(beta expr)

１回だけ最外簡約する。
expr におかしな部分があるとその部分は nil になる。

(beta* expr)

正規形になるまで最外簡約を続ける。

テスト用のデータを使った例。

arc> (load "lambda.arc")
nil
arc> testdata
((lambda x (x x)) (((lambda s (lambda k (lambda x ((x s) k)))) (lambda x (lambda
 y (lambda z ((x z) (y z)))))) (lambda x (lambda y x))))
arc> (beta* testdata)
((((lambda s (lambda k (lambda x ((x s) k)))) (lambda x (lambda y (lambda z ((x
z) (y z)))))) (lambda x (lambda y x))) (((lambda s (lambda k (lambda x ((x s) k)
))) (lambda x (lambda y (lambda z ((x z) (y z)))))) (lambda x (lambda y x))))
(((lambda gs1434 (lambda gs1435 ((gs1435 (lambda x (lambda y (lambda z ((x z) (y
 z)))))) gs1434))) (lambda x (lambda y x))) (((lambda s (lambda k (lambda x ((x
s) k)))) (lambda x (lambda y (lambda z ((x z) (y z)))))) (lambda x (lambda y x))
))
((lambda gs1436 ((gs1436 (lambda gs1437 (lambda gs1438 (lambda gs1439 ((gs1437 g
s1439) (gs1438 gs1439)))))) (lambda x (lambda y x)))) (((lambda s (lambda k (lam
bda x ((x s) k)))) (lambda x (lambda y (lambda z ((x z) (y z)))))) (lambda x (la
mbda y x))))
(((((lambda s (lambda k (lambda x ((x s) k)))) (lambda x (lambda y (lambda z ((x
 z) (y z)))))) (lambda x (lambda y x))) (lambda gs1440 (lambda gs1441 (lambda gs
1442 ((gs1440 gs1442) (gs1441 gs1442)))))) (lambda gs1443 (lambda gs1444 gs1443)
))
((((lambda gs1445 (lambda gs1446 ((gs1446 (lambda x (lambda y (lambda z ((x z) (
y z)))))) gs1445))) (lambda x (lambda y x))) (lambda gs1440 (lambda gs1441 (lamb
da gs1442 ((gs1440 gs1442) (gs1441 gs1442)))))) (lambda gs1443 (lambda gs1444 gs
1443)))
(((lambda gs1447 ((gs1447 (lambda gs1448 (lambda gs1449 (lambda gs1450 ((gs1448
gs1450) (gs1449 gs1450)))))) (lambda x (lambda y x)))) (lambda gs1440 (lambda gs
1441 (lambda gs1442 ((gs1440 gs1442) (gs1441 gs1442)))))) (lambda gs1443 (lambda
 gs1444 gs1443)))
((((lambda gs1440 (lambda gs1441 (lambda gs1442 ((gs1440 gs1442) (gs1441 gs1442)
)))) (lambda gs1451 (lambda gs1452 (lambda gs1453 ((gs1451 gs1453) (gs1452 gs145
3)))))) (lambda gs1454 (lambda gs1455 gs1454))) (lambda gs1443 (lambda gs1444 gs
1443)))
(((lambda gs1456 (lambda gs1457 (((lambda gs1451 (lambda gs1452 (lambda gs1453 (
(gs1451 gs1453) (gs1452 gs1453))))) gs1457) (gs1456 gs1457)))) (lambda gs1454 (l
ambda gs1455 gs1454))) (lambda gs1443 (lambda gs1444 gs1443)))
((lambda gs1458 (((lambda gs1459 (lambda gs1460 (lambda gs1461 ((gs1459 gs1461)
(gs1460 gs1461))))) gs1458) ((lambda gs1454 (lambda gs1455 gs1454)) gs1458))) (l
ambda gs1443 (lambda gs1444 gs1443)))
(((lambda gs1462 (lambda gs1463 (lambda gs1464 ((gs1462 gs1464) (gs1463 gs1464))
))) (lambda gs1443 (lambda gs1444 gs1443))) ((lambda gs1465 (lambda gs1466 gs146
5)) (lambda gs1443 (lambda gs1444 gs1443))))
((lambda gs1467 (lambda gs1468 (((lambda gs1443 (lambda gs1444 gs1443)) gs1468)
(gs1467 gs1468)))) ((lambda gs1465 (lambda gs1466 gs1465)) (lambda gs1443 (lambd
a gs1444 gs1443))))
(lambda gs1469 (((lambda gs1470 (lambda gs1471 gs1470)) gs1469) (((lambda gs1465
 (lambda gs1466 gs1465)) (lambda gs1443 (lambda gs1444 gs1443))) gs1469)))
(lambda gs1469 ((lambda gs1472 gs1469) (((lambda gs1465 (lambda gs1466 gs1465))
(lambda gs1443 (lambda gs1444 gs1443))) gs1469)))
(lambda gs1469 gs1469)
(lambda gs1469 gs1469)

ラムダ計算について

ラムダ計算はプログラミング言語のようなものだが
実際に動くプログラムを書くのには向かない。
プログラムを研究するための単純で純粋なモデルとして重要。

ラムダ式

プログラムはデータを入力するとデータを出力する。
データの形式には色々なものが考えられるが
ラムダ計算の場合はラムダ式を入出力する。

関数と引数

プログラム自体も一種のデータである。
入出力データの形式とプログラムの形式は同じとは限らないが、
ラムダ計算では全く同じ形式。
形式は同じだが、一方は関数としもう一方は引数として区別する。

ベータ変換

プログラム＝関数∈ラムダ式。
入力データ＝引数∈ラムダ式。
出力は？
関数と引数をペアにしただけのものを出力されても嬉しくない。

実際には、関数と引数のペアをベータ変換したものを出力する。
ちなみに、２つのラムダ式のペアもまたラムダ式であり (後述?)、
ベータ変換はラムダ式を変換する規則として定義される。

実引数と仮引数

単に引数といえば実引数のこと。
仮引数は関数を表記するために使う変数で、
ベータ変換の際に実引数で置き換えられる。

ラムダ式の前に仮引数の宣言を入れたものが関数を表す。
具体的には (lambda x M) のように書く。
ここで x は変数で M はラムダ式である。

引数に「実」と「仮」があるように、
関数にも

• (lambda x M) の形のラムダ式
• (M N) のペアの左側にあるラムダ式

という２通りの解釈があり得る。

定義

ラムダ式

• 変数はラムダ式である
• M と N がラムダ式ならば (M N) はラムダ式である
• x が変数で M がラムダ式ならば (lambda x M) はラムダ式である

ベータ変換

以下で M[x:=N] は代入を表す (後述)。

• x が変数で M と N がラムダ式ならば
  ((lambda x M) N) → M[x:=N] はベータ変換である
• M → N がベータ変換で x が変数ならば
  (lambda x M) → (lambda x N) はベータ変換である
• M → N がベータ変換で P がラムダ式ならば
  (M P) → (N P) はベータ変換である
• M → N がベータ変換で P がラムダ式ならば
  (P M) → (P N) はベータ変換である

代入

• x[x:=N ...] = N
• x[y:=N ...] = x[...]
• x[] = x
• (M N)[...] = (M[...] N[...])
• (lambda x M)[...] = (lambda y M[x:=y ...])
  ただし y は他のラムダ式に現れない変数

メモ

• arc1
• arc2
• 2-3 tree
• 連絡用スレ