とりあえずこれから何週間か、1日1つ以上ABCの4問題を解いていこうと思っている。 D問題は読んでから少し放置して暇なときにつらつら考えて、半日たってから実装したりしているので全然コンテスト形式は再現できていないのだが、とりあえず今は自分で問題に…

「事後参加」って変な言い回しだな。「の問題を解いてみた」が正しい・・・ abc098.contest.atcoder.jp 例によってPythonで。 第１問 abc098.contest.atcoder.jp abc098.contest.atcoder.jp 入力値二つの和、差、積のうちの最大値を出力する問題。本当に問題…

ツイッターでいろいろ流れてきて面白そうだったので競技プログラミングサイトのAtCoderで問題を解き始めている。 手始めに直近のこれをやってみた： abc099.contest.atcoder.jp コンテスト開催中に参加したわけではないのだが、とりあえずPythonで解いてみた…

LispValという再帰的なデータ型を定義して、まずコードをそのLispValとしてパースする。流れはインタプリタを作った時とまったく同じ。 インタプリタの場合はそこでevalを適用したが、コンパイラの場合はそこからSSA中間言語に変換を加えていく。 LispVal型 …

今回はHaskell初心者にとって理解が困難だといわれているMonadの話。 駆け足で頑張って抽象的な概念を理解しようとするのではなく、親しみ深い「リスト型」をモナドとして使ってみることで具体的な感覚を蓄積していこう、という考え。 >>= 前回FunctorとAppl…

「モナドとはなにか」「Applicativeとはなにか」といった抽象的な共通性の探索からはじめると挫折するのが目に見えているので、いったんそういったことは置いておいて、まずはいくつかの具体的なモナドと戯れて個別に挙動を理解していきたい。そういった具体…

LLVM IRに落とし込む前のステップとして簡略化した独自のSSA中間言語に変換しておく、という話を前回した。 その中間言語の各行を表現するデータ型がこれ： data SSA = Alloc String | Store String String | Load String String Lispと違ってこの言語は再帰…

前回に続いてLLVM IRで数字を返す方法を考える。 比較的簡単でこのような形になる： %1 = alloca i32 store i32 3, i32* %1 %2 = load i32, i32* %1 スタック上に%1という変数をalloca命令で用意する %1に3という値を代入 %1に含まれている値を一時変数%2に…

LLVM IRというのはLLVMコンパイラ・フレームワークが定義・利用する中間言語だ。 https://en.wikipedia.org/wiki/LLVM#Intermediate_representation LLVMフレームワークでは、コンパイラのFront Endはソース言語をこのIRに翻訳することに集中し、Back Endは…

とりあえず作り始めた。 github.com 基本戦略としては、まずは数値計算だけのコードをLLVM IRに変換するのを目的に： Lispコード→LispVal型データ構造→SSA IR→LLVM IR の流れでコンパイルしていく。 長期的にはLLVM IR上でLispValを表すStructを作る必要があ…

以下の記事の補足： zehnpaard.hatenablog.com 式をいじっていて気付いたのだが、不動点コンビネータを使った解は： dropWhile p = foldr (const f) undefined (repeat undefined) where f _ [] = [] f g ys@(x:xs) = if p x then g xs else ys に落とし込め…

こんなツイートが流れてきた： A complete #compiler to x86 in one page for my lecture today. pic.twitter.com/PwFl4V5czy— Joe Gibbs Politz (@joepolitz) 2018年4月11日 元となっているのは"An Incremental Approach to Compiler Construction"という論…

前回のブログの問題元は今は亡き？Monad.Reader第6号の"Getting a Fix from the Right Fold"という記事。 私が考えた答えの「失敗例」は出てくるけど、パターンマッチを使わないで遅延評価が無限リストにも効く解は出てこない。 しかし別解は非常にエレガン…

Haskellの高階関数のfoldrでdropWhileを定義せよ、という問題を見たのでやってみる。 foldr foldrの定義は以下のとおり： foldr :: (a -> b -> b) -> b -> [a] -> b foldr f e [] = e foldr f e (x:xs) = f x (foldr f e xs) 「わかってるねんで？foldrがred…

今回の変更 github.com 「ユーザによる変数定義」機能を追加する。 これはかなり大きな変更で、変数の内容を保持・評価するために、変更可能な「状態」を導入する必要がある。 Haskellだと状態をStateやSTモナドで管理することも可能（らしい）のだが、基本…

今回の変更 github.com 条件分岐のための構文を追加。 (if a b c)という式は、まずaを評価し、もし真ならbを、偽ならcを評価してその結果が値となる。 bとcのどちらかひとつしか評価されないのが重要なので、関数ではなく構文として定義。 実装としてはeval…

今回の変更 github.com 前回Bool値を定義できたので、=、/=、<、>などやand/orを実装する。 Functions Functionsモジュールのprimitivesにどんどん追加していく： primitives :: [(String, [LispVal] -> LispVal)] primitives = [ ... ("=", numBoolBinOp (=…

今回の変更点 github.com ブール値の追加。データ型とパーサの拡張のみ。 データ型 data LispVal = Atom String | List [LispVal] | Number Integer | Bool Bool ちゃんとshowできるようにしておく： showVal (Bool True) = "#t" showVal (Bool False) = "#f…

今回の変更点 github.com ついに四則演算の実装。入力をそのまま返すのではなく、入力を評価・変換して出力するようになり、「ちゃんとしたREPL」にちょっと近づく。 データ型とパーサ 今回は変更なし。四則演算ならAtom、List そしてNumber型だけで十分。演…

今回の変更点 github.com REPLで数字を入力するとパースエラーになる。Atom、Listに続いてNumberもパースしデータとして扱えるようにしたい。 LispValにNumber型を追加 LispValに新たにNumber型を定義し、Haskellの整数を保持させる： data LispVal = Atom S…

LISPとはそもそもLISt Processingの略なので、リストを全く扱えない状態からいち早く脱却したい。 というわけで次はリストの実装。ユーザから(a1 a2 a3)といった文字列を受けとり、List型として表現できるようにする。 gistからちゃんとしたgithub repoに変…

ここ一週間ほどHaskellを試しがてら、以下のチュートリアルをいじっていた： Write Yourself a Scheme in 48 Hours - Wikibooks, open books for an open world まずは全部通しで実装してみて、その後コードをいろいろ書き換えたり。 このチュートリアル、非…

今月は以下の本を読みたい： Thinking Functionally with Haskell （終わらせる！） プログラミングのための確率統計 証明の楽しみ 基礎編 他にもいろんな本やClojureや機械学習やギター曲や水泳にも手を出すつもりだが、とりあえず上記の3冊は終わらせる勢…

lepton著『アホでマヌケなプログラミング』を読んだ。 非プログラマ（ゆるくプログラマ志望な人？）に「プログラマの実態」を紹介する本。 著者は企業の新卒向けプログラミング研修の講師などをよく務めていたらしい。「文系卒、プログラミング経験なし」の…

Thinking Functionally with Haskell全１２章の折り返し地点に到達。第７章は最適化に関する話題。 メモリと計算量のトレードオフ Haskellの評価戦略は完全にナイーブではない： sqr (sqr (3+4)) = (sqr (3+4)) * (sqr (3+4)) = ((3+4) * (3+4)) * ((3+4) * …

最後。今までは「移動する円」がポイントだったが、今回は「移動する円の残す残像」が中心の映像になる。 inconvergent.net 前回と同様、左の円と連動して上下に動いていく円。今度は速度の線は描かず、そのかわり跡が残るようにした： Quil -L8sgTy8ZVQK2Q3…

続いてここから： inconvergent.net 過去の状態から次に移動する場所を決めていく。 まずは単純に、「現在地からあまり離れていない場所」を次の目的地に決定するパターン： Quil -L8sSIr9XEm-gow3mH4- 次に、「目的地」という概念を消して、上下方向の移動…

昔からすごく好きなジェネラティブ・アーティストのAnders Hoffのウェブサイトに、いくつかチュートリアル的な記事が載っている。 inconvergent.net ClojureとQuilで試していきたい。 まずは非常に簡単なボール一つが上下に動くもの： Quil -L8r5DqZjda9OSxY…

Exercise K 第一部 takePrefix pをリストxsに適用すると、xsの頭から連続してpを満たし続ける最も長いセグメントを返す。 takePrefix :: ([a] -> Bool) -> [a] -> [a] takePrefix nondec [1, 3, 7, 6, 8, 9] = [1, 3, 7] -- リストの先頭から上がり続ける最…

Tina Seelig『What I wish I knew when I was 20』を読んだ。 二十代前半の頃に買って読んだ本。本棚を片付けているので、とりあえず処分する前に読み直した。作者はスタンフォード大の創造性関連のプログラムの教授とのこと。 印象としては「ざ・ポジティブ…