久々にプログラミングのブログっぽい記事ですね
最近こういう記事書いてませんでしたが、情報系の学部に行ったことあってバリバリプログラミングしてます☺️
で、授業の一つに実験と称してC言語とSchemeとアセンブリに関する課題をひたすら解き続ける授業があるんですけど、その課題の中に暇な人用に発展課題っていうのがあるんですね
他の課題は「こういう入力を受け取ったらこういう出力をしろ」みたいな感じでまあ平和なんですが、発展課題の内容が
「CPUシミュレーターを作れ」
「シェルを作れ」
「Schemeの処理系を作れ」
「謎のソートアルゴリズムを実装しろ」
と、ガバガバ難易度という…
僕はそんなに暇じゃないんですけど、こんな課題を見せられたらやりたくなっちゃいますよね？！
ということで一番面白そうなSchemeの処理系を作る課題をやってみることにしました
本当はシェルもやってみたいんですが、システムコールにあまり詳しくないので、とりあえずパスということで…
にしてもSchemeを始めて学んだ授業で処理系を作れって本当めちゃくちゃすぎませんか(T_T)
実は僕、いつもだったらこういう課題に挑戦してても完成する保証がないからブログにしないんですよね(経過をブログに載せろっていう)
しかし、今回はすでにプロトタイプ的なのを作ってあります！
で、その試作版の仕様に限界を感じてきたので、新しく改良したものを作ってみようっていう寸法です
じゃあまずプロトタイプ版の仕様を説明…の前に軽くSchemeを紹介しておきますね
(define (fact n) (if (< n 1) 1 (* n (fact (- n 1)))))
これがSchemeのコードなんですが、カッコがめっちゃ多いですよね
初見だと見づらすぎる
上のプログラムは階乗を計算するfactっていう関数を定義していて、このコードの後に(fact 10)と書くと10!が計算されます
基本的には(関数 変数1 変数2 ...)っていう書式ですね
なので例えば1 + 2を計算するときは(+ 1 2)と書いて、これが3に変換されるイメージです
Schemeはいわゆる関数型言語というものですが、今まで関数型言語に触れてこなかった僕には新鮮であるとともに結構扱いづらいです
遅延評価や、いずれまた話題に上がると思いますがcall/ccなんていうキングクリムゾン並に意味不明な関数が出てきたりで、処理系を作るのもなかなか難しいです
そもそも今回はC言語で作るという課題なんですが、C言語とSchemeは処理の流れがなかなか違うんですよね*1
C++ならともかくCで書かなきゃいけないとか苦行かな
まあそんなわけで試行錯誤しながらプロトタイプを作ってたわけですが、さすがに衝動的に書きすぎて少し限界が出てきたっていうわけですね
プロトタイプ版ではまずコードをパーサーでObj型のツリーみたいなのに変換して、それを上から読んで処理していくっていう方式でした
例えば(+ 1 2)だったら
[Expression]
[Symbol]+
[Number]1
[Number]2という感じです
これ自体はなかなかいいアイディアだったと思うんですけど、これを読み込んで処理する関数の設計が少しまずかったです(一応言っておくとSchemeはいろいろな処理系があるのでこのやり方はダメ！みたいなのはないっす、自分的に書きづらくなってきただけです)
そもそもこれがSchemeをSchemeたらしめる！というものに「末尾呼び出しの最適化」や「継続」というものがあるんですが、当然これらを最初から前提にしてプログラミングしていかないと詰むし、しかも実装が結構難しかったりします
「末尾最適化」も「継続」も絶対ググってもらった方が早いですが軽く説明すると、
末尾最適化
例えば関数Aから関数Bを呼び出すと、関数Bが終わって関数Aの続きを処理できるように関数Aの内容をどっかに保存しておく必要があります
でも、関数Aの残りの処理がC言語でいうreturnだけだったら、わざわざ続きを保存しないで、関数Bの処理結果を直接returnしちゃえばいいですよね
これを末尾呼び出しの最適化といって、上のfact関数も末尾最適化されるように書き換えることができます
継続
どのサイトを見ても「継続は禅問答」みたいなこと書いてあって？？？ってなります
僕の理解してる範囲で説明すると、例えば(* 1 (+ 2 3))みたいなコードがあった時に、(+ 2 3)を計算して「５」という結果が出た時点で、まだその「５」を１と掛ける処理、つまり(* 1 5)の部分が残っていますよね、こういうのを継続って言います
要するにある処理をした時の続きの処理のことです
処理中にどこかでぶったぎれば、当然続きの処理があるわけですが、この続きの処理を保存して、後でまた再開するという化け物じみた関数があります
それがさっきから何度も出てきたcall/cc(call-with-current-continuation)関数です
まあこんな感じです
Schemeの式ってカッコが何個も連なってて、中にあるカッコから順々に処理していくのですごい再帰関数で実装しやすそうですよね
プロトタイプ版ではまさに再帰関数で処理していくようにしたんですが、そもそもC言語の方で再帰をしちゃうと末尾最適化が実現しにくくなっちゃう＆ウマミが減るんですよね
ましてや継続に関しては完全に考えてなかったので、プロトタイプ版からcall/ccを実装するには今までの再帰関数の流れを覚えておいていつでも再開できるような処理をする必要があるという無茶苦茶な感じに…
実際call/ccは実装が難しくて、処理系によってはcall/ccを実装してないものも割とあるっぽいです
じゃあどうやって実装するんだって話ですが、ここによると大きく２パターンあるみたいです
一つ目はプログラミング言語をスタックで処理して、call/ccが呼ばれた段階でスタックをコピー、再開するときに貼り付けするという要領
二つ目はCPS変換というものを用いてあらかじめSchemeのコードを変換しておく、そうすればcall/ccはお手軽に実装できるらしい
CPS変換とかいうのはちょっとよく分からない(ｻﾝﾄﾞｳｨｯﾁﾏﾝ)なので、スタックでやっていこうと思いましたが、いろいろ考えているうちに木構造のスタックにすればいいんじゃ？という発想に至りました
上の方で出てきたプロトタイプ版のObjのツリー構造にパーサーが変換してくれるアレです
さらにこの方法をとればガベージコレクターとも相性が良く、わざわざコピーせんでも良くなりそうです
というわけで改良版の実装に移りたいですが、とりあえず明日１限あるんでもう寝ますね😊
てか今考えてみたらプロトタイプ版はガベージコレクションせずにゴリ押そうと思ってた時点で無理があったな…
