3年ぶりに更新します。この３年間にも(途中1年以上別の事をやっていましたが)自作の言語とその処理系の開発は続けていました。そろそろ紹介記事を書き始めようと思います。ホームページは既にありますが、こちらは昨年の夏から更新していないので内容が古く…

現在2カ月の短期滞在研究でアメリカに来ています。一人での海外滞在は初めてです。 さて、その滞在初日から貴重な経験をしたので記録を残しておきます。 日本でもニュースになったらしいシカゴのブリザード(スノーマゲドン)に捕まりました。 (Chicago Tribun…

以下の記事でPythonやRubyの末尾再帰関数をループに変換する手法が「末尾再帰最適化」や「末尾呼び出し最適化」として紹介されているのですが、これらの用語を使うのは間違いです。 紹介されている手法(動的束縛を利用して制御フローを変形する手法)自体は大…

今日は80まで。このところ、数学を使う問題が沢山で面白いですね。 ピタゴラス数とブロコット木 Problem75 簡単には 1,500,000以下のLで a^2 + b^2 = c^2 かつ a + b + c = L を満たす自然数a,b,cの組がちょうど一組となるようなLの個数を求めよ という問題…

久々にProject Eulerやりました。まだrowlは使える段階にないので、Rubyつかってます。 このあたりから数論の問題がいろいろ出てきて面白かったです。 ぺル方程式(Problem 66) 簡単には Dが平方数でない整数の時 x^2 - Dy^2 = 1 の整数解を求めよ という問題…

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の開発ではこのトレードオフについて神経質になろうと思っています。 最適化の基本 最適化には命令数削減・並列化・パイプライン最適化・レジスタ割り当て・スケ…