はてなブックマーク

言語実装 Advent Calendar 2022の１日目の記事として書いた。 Lisp Advent Calendar 2022でも枠が空いていたのでダブル投稿。 プログラミング言語を実装してみたい！と思ったらまずは簡単なLispインタプリタから始めるというのは一つの王道だと思う。 複雑な構文解析は要らず最低限の再帰下降法パーサで手に入る構文木を、そのまま再帰的な関数で実行していくtree walking評価器。メモリ確保もヒープにそのまま置いていって、メモリ解放は実装言語のGCに任せるなりプログラムの終了時までやらなかったり。そんなインタプリタを作る経験から得られるものは非常に大きく、どんなプログラマでも一回は試してみてもいいのではないか？と思っている。（個人的な感想です） そんな簡易Lispを実装してみて沼にハマってしまい、より精緻な言語処理系を作りたいと思ったとする。その時点で：

自分で実装している型システムに再帰型をつけたくてiso-recursive typesで検索していたらwasm garbage collectorのGitHubレポジトリで行われている侃侃諤諤な議論を見つけて読み漁っていた。 その中で見つけたのがwasmの中心的な人物であるAndreas RossbergがwasmのGC proposalを試すために書いた実験的なコンパイラWaml： github.com Rossbergはwasmのreference interpreterを実装したりしている。ML界隈ではF-ing Modulesや1MLなどのモジュール関連の研究やstandardにできるだけ忠実なSMLのレファレンス実装HaMLetなどで有名。 このWamlはwasmのGC proposalがちゃんとした言語処理系のコンパイル先として必要な機能を備えているか評価するために、できるだけ

OCamlのDiscuss掲示板を眺めていたらこんなプロジェクトについての言及があった： github.com Malfunction is a high-performance, low-level untyped program representation, designed as a target for compilers of functional programming languages. OCamlコンパイラの中間表現であるLambda言語（とほぼ同等のもの）を受け取り、OCamlバイトコードかnativeコードへのコンパイルをしてくれるようだ。 （追記：バイトコードにコンパイルできるというのは間違い。実際にはOCamlコンパイラとは別なLambda言語インタプリタがある） Lambda IRはOCamlコンパイラにフラグを渡すと出力してくれる。以前少し調べていくつか記事

Graydon Hoareが2019年にカナダのブリティッシュ・コロンビア大学でコンパイラ関連のゲスト講義した時の資料21 compilers and 3 orders of magnitude in 60 minutes - a wander through a weird landscape to the heart of compilationを読んだら大変面白かったのでメモ。 作者 Graydon HoareはMozillaでRustを開発したことで有名。その後Rustの開発もMozillaも離れて（というかRustの開発からは2013年に離れたようだ）、一時期AppleでSwift開発チームに所属していたらしい。（ソース：Reddit: I wonder, why Graydon Hoare, the author of Rust, stopped contributing in

ポール・グレハムの記事の一つにWhat Makes Lisp Different?というものがある： www.paulgraham.com ポール・グレハムらしくよく書かれていて、C言語などと比較した場合のLispの特徴をうまく捉えているように思う。 その中の一つが Recursion. Recursion existed as a mathematical concept before Lisp of course, but Lisp was the first programming language to support it. (It's arguably implicit in making functions first class objects.) こうある通り、私も今まで深く考えたこともなく「プログラミングにおける再帰はLispが由来」と考えていたのだが、前回の記事を書く

先日こういうツイートがあった： Haskellとかの関数型言語を使用しているプログラマの皆様にお聞きしたいんですけど、「関数名 引数 引数 ...」みたいな関数呼び出し構文って見にくくは無いですか？「関数名(引数, 引数, ...)」に慣れたこちらからすると、丸括弧が無いからコード中のどこが関数呼び出しなのかパット見で把握しにくい。— sounisi5011/プログラム (@sounisi5011Prog) February 22, 2022 「見にくくは無いですか？」と聞かれると、個人的には「全然大丈夫です」と答えざるを得ないのだが、次のツイートに関しては考えさせられた： 数式でも函数には丸括弧を使ってるのに、どこのタイミングで丸括弧が消失したのかわからないし、その選択をした理由も思いつかない。— sounisi5011/プログラム (@sounisi5011Prog) February

純粋関数型Lisp方言であるLispKit LispのインタプリタとSECD抽象機械の機械語へのコンパイラを作成する。 タネ本はHendersonの「Functional Programming - Application & Interpretation」で、この本に載っているISWIMやPASCALのコードを大体なぞるようにPythonで書いていく。（最近出た「コンパイラー原理と構造ー」でもSECDマシンへのコンパイルの話題が出ているらしいがまだ届いていないので未確認・・・） 例によって長くなるので複数の記事に分ける。 流れとしては以下のようになる： LispKit Lispの紹介　（本記事） パーサとAST インタプリタ 前編 後編 SECD抽象機械の実装　1 2 3 SECD機械語へのコンパイラ SECD抽象機械ガベージコレクション LispKit Lisp LispKit Lis

OCaml4.08でシンタックスシュガーとしてlet*、let+、and+などの構文が新たに導入された。 詳細については jobjo.github.io がわかりやすかった。 直接モナドやApplicativeをサポートする構文というよりは、 let (let*) x f = g x f などと好きに定義すれば let* x = a in h x が脱糖されて g a (fun x -> h x) になる、ということのようだ。モナドだったらlet (let*) x f = bind x f、Applicativeだったらlet (let+) x f = map f xにすればうまくいく。 let (let+) x f = map f x let (let*) x f = bind x f let+ x = a in g x (* desugars to map (fun x -> g x)

Write Yourself a Scheme in 48 Hoursの最後の二章をやっていく。入出力と標準ライブラリ作成。 第九章：入出力 stdin, stdoutやファイルに対する入出力を実装する。 github.com 例によって「Haskellだとモナドが出現していろいろ型を頑張らないといけないけどOCamlだから・・・」という案件。 HaskellではIOモナド型のために新しいIOFunc式を用意したりしているが、OCamlだと普通に今まで通りPrimitiveFuncに放り込んでいける。 type expt = (* 省略 *) | PortIn of in_channel | PortOut of out_channel と入出力用のchannelをラップしたPortIn/PortOut式は用意する。あとはIoモジュールでそれを使う関数を定義し、primitives.mlで

OCamlでパーサを書く場合 lexerをocamllexで書く そのlexerを受け取るparserをmenhirで書く というのが最近の鉄板のようだ。 let lexbuf = Lexing.from_channel stdin in let exp = Parser.f Lexer.f lexbuf in print (eval exp) というような流れ。 ocamllexもmenhirも構文が普通のOCamlではなく、いったん独自構文で書かれた.mll/.mlyファイルを両ツールでOCamlの.mlに変換してから普通のOCamlモジュールとして使う。 なので長らくぱっと見どうやってocamllex製のlexerが返すトークンに対して任意の変換を行ってからmenhir製のparserに渡せばいいのか、イメージが湧かなかった。 しかし実際にやってみたら拍子抜けするほど簡単。 パースし

ツイッターで100 Days Of Codeというチャレンジがたまに流れていて、面白そうだったのでやってみた。今年も終わりに近づいているので今更ながら振り返ってみる。 100 Days Of Code概要 ルールは簡単： なるべく毎日１時間以上、業務外のコードを書く githubに載せる twitterで進捗をつぶやく 途中で風邪をひいて寝込んだりいわゆるライフイベントが発生したりして合計で５日ほど空いてしまったが、８月１４日にはじめて１１月２６日に終わった。 積ん読していた本をある程度消費したい、という欲求もあり、100日間基本的に本に載っているコードや演習問題、オンラインのチュートリアルなどをやって過ごした。自前のプロジェクトを立ち上げたりしなかったのですこし寂しい気もする。近いうちに自作言語に手を出したい。 やったこと（というか読んだ本） Essentials of Programm

時には昔の話をしようか、ということでPeter LandinのSECDマシンについて。Lisp Advent Calendar 2018 23日目の記事。 はじめに 最近、長らく積読してたThe Architecture of Symbolic Computersという本を読んでいる。 There is a revolution looming in computer science … the basic von Neumann model of computing, which has ruled unchallenged for the last 40 years, is encountering not one but several potentially heavy weight challengers. … Achieving ... (the book's) ... goa

前回に続いてCSSの話。 Reagent/Hiccupを使ってHTML/DOMをedn形式で定義しているのだから、できればCSSも同じくednで定義したい！という末期症状な人間のために、gardenというライブラリが存在している。 github.com Hiccupと同じように、Clojureのデータ構造であるVectorとMapでCSSを定義できる。最近は生のCSSで書くのではなく、より表現力の高いPreprocessorなどを使って記述するケースが増えているようだが、そのようなPreprocessorよりもさらに強力なClojureのデータ構造処理の機能や関数化・データ再利用がすべて使えるというのは一つの強みである。 個人的にはそういったまっとうな理由よりも「どうせだったら全部ednで書こう」という思いのほうがgarden導入の強い動機になっているが。 今回は最低限gardenを使うた

昔からProcessingがやりたかったのだけど、なかなかいい機会がなく放置していた。 しかし、ClojureでもProcessingをベースにしたQuilというライブラリがあることを知り、どうせClojureを勉強しているのだから、と早速使ってみた。 基本中の基本だとこんな感じ。 (defn setup[] (q/background 255)) (defn draw [] (q/rect 0 0 10 10)) (q/defsketch example :setup setup :size [100 100] :draw draw) 表示される画像がこれ： なんとなく、やってることの割にはコードが多くてあまりいい印象じゃない。パワポでやった方が早いし・・・ しかし、コードでやることですぐあらわれるメリットとしては、要素を定義していってドンドン組み合わせていけること。 というわけでdra