fetburner.core

コアダンプ

Coqで証明付きのマージソートを書く

この記事はTheorem Prover Advent Calendar 2016の4日目のために書かれました。

少し季節外れの記事になりますが、前期はプロ演A[^1]の季節でしたね。
僕のTLでもC言語の課題に苦しめられた学部生のツイートが良く回ってきましたが、 とりわけ彼らが苦戦していたのはマージソートを書く課題のようでした。
面白そうなので僕もCoqで実装してみましょう。 もちろん、証明付きで。

続きを読む

二分探索に証明を付ける

二分探索は言わずと知れた探索アルゴリズムですが、 実際に実装しようとすると無限ループしたり正しい答えが得られなかったりする事も多いのではないでしょうか。

そこで、ここではCoqで二分探索を実装し、正当性の証明を行いました。

続きを読む

OCamlで車輪を再発明する

最近研究でCoqぐらいしか書いてないので、リハビリがてらAtCoderで 開かれるコンテストにOCamlで参加して遊んでます。 僕は個人的な趣味もあってOCamlを使う際は専ら言語処理系を書いていましたが、 競技プログラミングでは全く関係ない題材を扱う必要があるので新鮮な感じですね。

それに伴って有名なアルゴリズムもいくつか実装したので、 ここではそういうアルゴリズムをMLではどう書いたのか紹介したいなと思います。

続きを読む

SMLでコンパイラを書いた

このエントリはML Advent Calendar 2015言語実装 Advent Calendar 2015の20日目の記事です。 言語実装 Advent Calendar 2015の19日目の記事はh_sakuraiさんのJavaのサブセットコンパイラの作成でした。

続きを読む

型推論の健全性の証明

このエントリはTheorem Prover Advent Calendar 2015言語実装 Advent Calendar 2015の11日目の記事です。 言語実装 Advent Calendar 2015の10日目の記事はkeenさんのリージョンについてでした。

続きを読む

手続き型言語OCaml

この記事はML Advent Calendar8日目の記事として書かれました。 7日目の記事はでこれきさんのfoldみぎひだりです。

Standard MLOCamlをはじめとしたML系の言語は関数型言語として有名ですが、参照、配列、例外といった副作用を伴う機能も扱う事ができます。 また、ML系の言語で手続き的に書いたからと言ってその言語の魅力が損なわれるわけではなく、 強い静的型付け、型推論やparametric polymorphismなどの恩恵を受けられるので、むしろ良く設計された手続き型言語のように映る事でしょう。 積極的にMLで手続き的な処理を書いていこうな。

続きを読む