1年前の今日、アセンブリで数十行のechoプログラムを作成しました。 それを徐々に育てて、今日ではソースコード行数がトータルで1万5千行を超えていました。 １年でたったこれだけかという気がしなくもないですが、趣味プログラムにしてはそれなりに進んだの…

50問目まで解きました。数学を使って工夫すると速く解けたりするようなものについてだけ自分の解答を書きます。 Problem 15 20x20のグリッドの左上から右下までの最短経路数を求めよ これは２項係数、 の値を計算すれば良いです。２項係数の値はパスカルの三…

8問ときました。 Problem 3 600851475143の最大素因数を求めよ 「素因数分解せよ」ではなく「最大素因数だけ求めよ」ですから素数のテーブルは作りたくないので、反復により求める事を考えます。 整数Nを素因数分解してみると となりますが、これの最小の素…

これはかなりの良門ではないでしょうか。 約数の数が500以上になる最初の三角数を求めよ三角数とは以下の式で書けるものです。 Nの素因数分解が下のようになる時 約数の個数は となります。また、互いに素な2数は指数が重複しないですから、 nが奇数なら で…

Project Euler解き始めました。自分の数学の勉強も兼ねて、できるだけプログラムでの力技の計算は避けようと思っています。どうしてもプログラミングが必要なやつは、あとでrowlで書こうと思ってます。 Problem 1 1000未満の3または5の倍数の和を求めよ 集合…

n個の対応する括弧のパターンの数を母関数を使って求めてみました。 これはid:nobsunさんが指摘なさっているようにカタラン数という数になるんですが、そういう前提知識なしで機械的に解きたいような場合に使えます。 いろんな教科書があると思いますが、私…

rowlの式として以下の定義を使う方針にしました。その為、いろいろと実装の修正を行っています。 原始式(シンボル，整数リテラル，浮動小数点数リテラル，文字列)は式である。 hがシンボル，e1,...,enが式の時 h(e1, .., en)は式である。hを式のheadと言う。…

型でのマッチングの実装を一部実装しました。 これによって関数のオーバーロードが出来るようになりました↓ print(10) # print_intが呼ばれる print("Hello World") # print_stringが呼ばれる関数定義時にはこんな感じで書きます↓ fib(n!Int): fib(n-1) + fi…

Haskellに副作用があるのか？というのは難しいテーマだと思いますが、少なくとも最適化理論での一般的な「副作用」の定義ではHaskellは全く副作用がない言語と言えると思います。 理論的に美しいという点がHaskellの設計の一番重要なところだと思うのですが…

Rowlの動的なパターンマッチエンジンの構成について書きます。 まず、インタプリタ内にfuntableという関数テーブル(関数名 × 引数の数 → 関数実体)があります。 関数の実体は 関数本体(バイトコード) 関数定義のリスト(ASTではなくコンパイルした形) からな…

以下の記事の「ブロックローカルで関数定義を再定義できる」という仕組みには問題がありましたのでやめることにしました。 何か別の形で矛盾なく同様の機能が使えるようにしたいと思います。 fib(n): fib(n-1) + fib(n-2) fib(0): 0 fib(1): 1 print_int(fib…

自分はコンパイラの実装言語にはパターンマッチがあると楽だと思っているのでrowlにもパターンマッチエンジンを実装しています。以下の論文を参考にしています。 http://portal.acm.org/citation.cfm?id=507641&dl= これまで変数パターン、Dontcareパターン…

とはいってもx86の機械語を生成するのではなく、VMのバイトコードを生成するやつを作りました。x86のJITアセンブラは次の世代で作る予定です。 このJITアセンブラは現在実装中のインタプリタに内蔵するJITコンパイラで用います。 以下はフィボナッチを計算す…

リンカが問題なく動くようになったので、ようやく次の処理系(rowl1)作りを開始しました。 レキサはこれまでと同じく状態遷移図を手で作成しました。rowl2の開発時にはレキサの自動生成が出来るくらい、言語が高級になっていると良いなぁと思っています。現在…

一か月ほど本業に専念していましたが、Rowlの開発を再開しました。 結構忘れているところがあるので、これまでの経過をまとめます。これまで実装したものの一覧は下図。 問題1: 機能不足 アセンブリ言語で実装したrowl0は機能が貧弱すぎて、次のステップで一…

ベンチマーク用途を目的としてRubyで書いたレイトレーサーを公開します。http://github.com/nineties/raytracer以下をPart3まで実装したものです。 http://www.devmaster.net/articles/raytracing_series/part1.phpPPM形式の画像を生成するので適当に変換し…

コンパイラの実装言語にあると良い機能でJavaでAST(抽象構文木)作るのが大変だという話に触れたのだけれども、実は自分の知らない良いやり方があるのではないかと思ってClojureなどJavaで実装された処理系のソースを覗いてみました。 結論：やっぱり大変。 C…

S式からbrainfuckのコードを自動生成するプログラムを書いてみました。 コード生成が目的ではなくて単にできるだろうかと気になったのでやってみました。gaucheを使いました。 brainfuck インタプリタをスタックマシンっぽく使って動作します。 変数が使える…

純粋関数型言語の処理系を作ってみることにした (その3 : Mark-1 G-machine)の続き。教科書P94-P97まで。 http://github.com/nineties/puref/commit/4cd5d92a5f02468929bc2dd2ddafbd363251c86cMark-2 G-machineでは遅延評価を行う為の準備として、Update/Pop…

純粋関数型言語の処理系を作ってみることにした (その2)の続き。 今日は教科書の第3章P75-P94(Mark1: A MINIMAL G-MACHINE)の実装をしました。 現状では関数適用しかできません。遅延評価はまだ扱っていなくて、次回Mark2で扱うことになると思います。 ただ…

こんなのを見つけたのだけど http://code.google.com/p/brainfuckos/ 中が空っぽでがっかりしたので、自分で何か作ってみようかと思った。 はっきり言ってめんどくさすぎるので続きはやりませんが、こんなの作ってみました。 .code16 .equ SCREEN, 0xb800 .e…

ファイル入出力とか可変長配列とかrowlVMのプリミティブが充実してきたので、現在はrowl-core言語で次期rowl1コンパイラの実装をしています。 ところが、メモリマネージャのないスクリプト言語であるrowl-coreは大量にメモリを消費する為ついに限界がきまし…

純粋関数型言語の処理系を作ってみることにしたの続き。 先週末はちょっと忙しかったので毎週日曜日の予定がずれてしまいました。 今日はPretty Printerを作りました。G-machineは次回に回します。 http://github.com/nineties/puref/commit/9295d96e1e0adb7…

メモリマネージャがちゃんと動きました。GCも今のところ大丈夫っぽいです。 ということで、エラトステネスの篩を実装してみました。次期コンパイラ実装専用のDSLなので可読性が低いのは勘弁してください。 (fun main () ( (sieve 200000) (exit 0) )) (fun s…

プログラミング言語の高級化はえてしてプログラムを複雑化し最適化を阻害してしまいます。 rowlの開発ではこのトレードオフについて神経質になろうと思っています。 最適化の基本 最適化には命令数削減・並列化・パイプライン最適化・レジスタ割り当て・スケ…

構造体とか配列とかどんな言語にも大体あるものは除きます。あくまで私の主観です。 lex/yacc/gperfなどのツール 特にyaccがないと複雑な言語のパースは大変。 バリアント 構文木の表現に一番適していると思う。 パターンマッチ コンパイラ内部はパターンマ…

関数型言語というと型システムなどフロントエンド部に注目が集まりやすいと思いますが、私はバックエンドの実装に興味があります。 そこで小さな純粋関数型言語の処理系を作ることにしました。名前は安直ですがpurefにします。方針 勉強用の実装 飾りは付け…

構文木は教科書7ページに書いてあります。非常にシンプルです。Haskellのような複雑な言語も構文糖衣を取り除くと,同様の言語まで単純化されます。そんなバカなと思う人は,GHCのソースのghc/compiler/coreSyn/CoreSyn.lhsを読んでみて下さい。 レキサ/パーサ…

C言語のソースをcppにかけると生成されるディレクティブの意味。 # 1 "/usr/include/math.h" 1 3 4 最初の数字はファイルの行番号で、末尾の数字は 1 : includeを開始して新たなファイルに移る (ENTERフラグ) 2 : includeを終了して元のファイルに戻る (LEAV…

今日ふと高校時代に電卓遊びにハマっていた事を思い出したので、メモしておきます。√のない計算機でNの平方根を求めたい場合は [N(数字)][M+]と押したあと [MR][x][MR][-][N][/][2][/][MR][M-]を繰り返します。 Nのm乗根の場合は [N][M+]と押したあと [MR][x…