BLOG.7NOBO.ME

記事一覧

キャッシュについての雑多な話

この記事は、 ミクシィグループ Advent Calendar 2019 の20日目の記事です。 本当は全然別な話を書こうかと思っていたのですが、今朝同期が分報で↓の記事について言及していたのをみて触発され、急遽パフォーマンスに関する話をすることにしました。素敵な記事を書いてくださったリクルートの濱田さん、ありがとうございます！ Railsアプリの処理を100倍以上に高速化して得られた知見 ...

git commitを使わずにコミットを作ってみる

git commit や git commit-tree を使わずにコミットを作ってみます。 完成後のイメージ こんな感じのコミット履歴になれるようにコミットオブジェクトを手作りしていきます。 $ pwd /path/to/my-first-repository $ ls hello.txt $ cat hello.txt HELLO WORLD $ git log --oneline XX...

defでメソッドが定義される対象

def キーワードを使うとメソッドを定義できますが、実は文脈によって挙動が結構違います。 特異メソッド 誰にメソッドが追加されるかを明示している特異メソッド定義の場合は挙動がわかりやすいです。この場合は、単純に対象のオブジェクトの特異クラスにメソッドが定義されます。 hoge = "hoge" def hoge.puts_self puts self end hoge.puts_self ...

よく忘れるinclude, prepend, extend

Rubyの include, prepend, extend のどれがどれだかすぐに忘れるのでまとめました。 include Module#include は、自身の継承チェーンの「自身より後、自身のスーパークラスより前」に指定したモジュールを挿入するメソッドです。 結果として、 include したモジュールに定義されているメソッドをそのままインスタンスメソッドとして取り込むことができます。...

2019年度の草

2019年度は今まで経験したこと無い数十万行レベルの規模のサービスの開発ができたり、某OSSのバグを血眼になって必死に修正したりといろいろ経験できるものが多い一年でした。 趣味開発ではSlackのbot作ったり(使わなくなって開発停止)、Schemeのインタプリタ作ったり(飽きて開発停止)しました。 来年はもっとコード書きます。 ...

自作SchemeインタプリタでSICPをやるという夢

この記事は、 ミクシィグループ Advent Calendar 2018 の25日目の記事です。 突然ですが、みなさんは自作Scheme処理系でSICPをやりたくなったことはありますか？ 僕はあります。なのでScheme処理系を書きました。以下がその処理系のソースコードになります: genkami/YAKLD: YAKLD: Yet Another JAKLD このYAKLDは、京都大学大...

gitignore.ioを使って.gitignoreを自動生成する

.gitignoreを手動で用意したり、.gitignoreのテンプレート集をコピペする時代は終わりました。 gitignore.io 単純な使い方としては、上のサイトの検索窓に適当なワード(例: Emacsを使ってPythonのコードを書く場合、 「Emacs」「Python」等)を入力し、「Create」ボタンを押すだけで対応する.gitignoreを生成してくれます。 さらに、gi...

JQueryのhtml()とtext()の微妙な差にハマった話

jQueryの .html(), .text() はそれぞれ指定した要素の中身をHTML/テキストで取得する関数です。この両者は似たような用途で使われがちですが、取得する内容以外にも微妙な挙動の違いがあるため注意が必要です。 具体的には、 $(...) で指定した対象の要素が複数ある場合が両者で大きく異なります。 .html() については、対象の要素が複数ある場合、その先頭要素の中身のみを返...

Elixir基礎文法最速マスター

Elixirのすべての機能は紹介しきれないけど、とりあえずこれだけわかればfizzbuzzくらいは書けるでしょ程度の言語機能の一覧です。 並行処理関連の話とかは全く書いてないので注意。 リテラル 数値 整数は10進数、16進数、8進数、2進数が扱える ex(1)> 123 123 iex(2)> 0x123 291 iex(3)> 0o123 83 iex(8)> 0...

Rubyのthrow/catchとraise/rescueの違い

throw/catch throw/catchはKernelのメソッド。 # Kernel のメソッドであることがわかるように、明示的に Kernel.(...) の形で呼んでいる Kernel.catch :error do puts "hoge" Kernel.throw :error puts "fuga" end #=> hoge throwで投げることができるの...

Slack APIの基本と、簡単なbotを作るまでの流れ

SlackのAPIの使い方の一例として、「echo hogehoge」と発言したら「hogehoge」と返す簡単なbotを作るまでの流れです。 説明中に出てくるコードは基本的にGAE + Python 2.7 (無料枠で使えるバージョンがこれしかない)を想定しています。 アプリケーションの種類 Slackでアプリケーションを作成する場合、最初にアプリケーションの種類を選ぶ必要がある。 Sl...

iexでモジュールを再読み込み

recompileでプロジェクト全体を、r Module.Nameで指定したモジュールのみを再コンパイルすることができます。 以下実行例: # hoge.ex defmodule Hoge do def hoge, do: IO.puts "hogeeee" end このhoge.exをロードする。 iex(3)> c("hoge.ex") [Hoge] iex(4)> ...

以外と知らないGCCの拡張文法

GCCの文法拡張のうち、個人的に使ったことのなかったものをまとめました。 文を式として扱う 複文を括弧で括ることによって、その複文を式として扱うことができます。この際、最後の文の実行結果がそのままその式の値となります。RubyやElixirみたいな感じの挙動。 int main() { for (int i = 1; i <= 100; i++) { cha...

WordPressで独自のpost typeを定義する

PHPもWordPressも全然知らないのにたまに触らないといけない状態が来てしまってつらい。 WordPressの投稿は、「通常の投稿」「固定ページ」などのように複数の種類に分けられています。この投稿の種類のことを、post type(投稿タイプ?)と呼ぶようです。今回はこ のpost typeを新たに登録する必要に迫られたので、行ったことのメモを残しておきます。 お試し環境構築 vers...

【2018年版】MacBookを買ったら入れるべきアプリと初期設定

新しいMacBook Airを手に入れたので、最初にインストールしたものとか初期設定とかをまとめておきました。これさえあればそれなりに使えるようになるはず……。 Firefox Rustを応援したいのでFirefox派です。 公式からダウンロード Google日本語入力 公式からダウンロード 入力ソース大量にあってもあんまり使わないので、Google日本語入力の英数とひらがなの2種類だけ...

Haskellで二重数を使って自動微分

二重数とは 複素数の兄弟のようなものに、二重数というものがあります。二重数は実数の集合 \(\mathbb{R}\) に新しい元 \(\epsilon~(\epsilon^2 = 0)\) を追加したものです。 二重数を用いると、例えば \[(x + \epsilon) = x + \epsilon\] \[(x + \epsilon)^2 = x^2 + 2x\epsilon\] \[(x...

Ectoを初めて使ってみたので基本的な書き方とかメモ

Ectoの使い方がなんとなく分かってきたので、Ectoを使ってデータベースの操作を行っていくための大まかな流れをメモしておきます。それぞれの機能の詳細には触れないので、そのあたりは公式のドキュメントなりを読むといいと思います。 最初の設定 新しいアプリケーションecto_exampleを作ります。 $ mix new ecto_example 生成されたファイルを、以下のように書き換えてい...

"alias Hoge.{A, B}"の"{A, B}"って何だ?

Elixirでは普段何気なくalias Hoge.{A, B}みたいに書いていますが、このaliasにしか出てこないHoge.{A, B}という構文は文法的にどういう意味になっているのでしょうか? quoteして構文木を見てみると、Hoge.{A, B}はHoge.{}/2という関数呼び出しに相当する構文らしいということがわかります。 iex(11)> quote do Mod.func...

GNU Make 基礎文法最速マスター

これを書いていたらMakefileに関する知識がついてしまったので、ここにまとめておきます。 基本的な構文 makefileの基本的な構文は以下のようなものである: target1 target2 ... targetN: dep1 dep2 ... depM cmd1 cmd2 ... cmdK target1, …, targetNをそれぞれターゲットという。ターゲットとは、...

Makefile"のみ"でFizz Buzz

Fizz Buzzを変態的な環境で書こうという試みは世界中で行われており、MakefileによるFizz Buzzも例外ではありません。適当にググってみたところ、既存のMakefileによるFizz Buzzを謳ったコードは以下の3箇所で見つかりました。 FizzBuzz - Rosetta Code 時代遅れひとりFizzBuzz祭り　make編（gmakeでもpmakeでも書いてみ...

コラッツの予想

過去のブログ(現在閉鎖済み)を供養していた所，ちょっとおもしろい問題が出てきたので掲載します． コラッツ列とは，与えられたnから始まり以下のようなルールで定義される数列です． collatz 1 = 1 : [] collatz n | even n = n : collatz (n `div` 2) | otherwise = n : collatz (3 * n + 1) 実際...

Contモナドとcall/cc

前回: モナドから始めない継続入門 Contモナドを実装する 前回で継続の説明と継続渡しを暗黙的に行うContモナドが作れたので，今回はcall/ccの実装を行います． call/ccとは 継続の代名詞であるSchemeには，call-with-current-continuation略してcall/ccという関数があります．この関数は「引数として渡された関数に，現在の継続を渡...

Jekyllで下書き管理

あまり知られていないようですが，実はJekyllには下書き管理機能があります． サイトのルートに_draftsディレクトリを作っておくと，その中に入っている.md等のファイルをJekyllは下書きと認識します． これらの下書きファイルは，_config.ymlに show_drafts: true を設定するか，--draftsオプション付きでJekyllを起動することで通常の記事と同様...

Contモナドを実装する

モナドから始めない継続入門 上の記事では，モナドの登場しない継続の説明を書きましたが，今回はこのとき使った継続をContモナドというモナドに変換していきます． 前回定義したaverage3CPSの定義を見直してみましょう．この関数は，3つの引数x, y, zの平均を継続に渡す関数でした． module Cont where addCPS :: Num a => a -> a -...

モナドから始めない継続入門

Twitterのどこかで「Contモナドを使わない継続の説明を書いてくれ」みたいな話を目にしたので書きました． この記事は，以下のような方を対象に書かれています． Haskellはなんとなく使える．モナドもなんとなくわかる． 息をするように新しいモナドを定義したりはできない． 継続が何かは全く分からない．Schemeとかを使ったこともない． 継続とは Haskell(に限ら...

『プログラミングElixir』日本語版以降のElixirの進化

『プログラミングElixir』の日本語版はElixir 1.2を想定して書かれていますが，現在の最新版は1.6.0-rc.1となり，そこそこバージョンが上がってしまっています． そこで，これらのバージョン間での違いを雑にまとめました． なお，書いている人はElixir初心者なので，説明不足や表記の間違いなどあればコメントなりプルリクなりでご報告ください． 文法の変更 変数名とatomのUn...

魔法のおまじない: alias __MODULE__

Elixirではネストされたモジュールとその親の間には何の関係もないので，ネストしたモジュール内でそのモジュール自身を参照するときは，いちいち頭からモジュール名を全部打っていかないといけません． defmodule Game.User do defstruct [:name, :level] def new(name, level) do # %User{...} ではダメ ...

iexで履歴を表示する

iexというようりはErlang側の問題らしいです． Erlang/OTP 20以降 以下のオプションを渡すことで、履歴を保存することができます． $ iex --erl "-kernel shell_history enabled" また、環境変数EAL_AFLAGSに同様の値を設定することでも，同様の結果を得ることができます． export ERL_AFLAGS="-kernel s...

京都のおいしいコーヒー

この記事は、 ミクシィ18新卒 Advent Calendar 2017 の23日目の記事になります。 あれ、23日目…？？？今日は一体何日……？？？？ 大遅刻ですね。非常に申し訳ないです :bow: :bow: :bow: :bow: 今回は こんなことを書いてしまったので、プログラミングからは一旦離れ、京都のおいしいコーヒーが飲める店でも紹介したいと思います。 京都に来る機会があ...

人工知能がはじき出した、最高にインスタ映えする画像はこれだ！！

この記事は、 ミクシィ18新卒 Advent Calendar 2017 の22日目の記事になります。(1日遅れましたごめんなさい) 皆さん、インスタ映え、してますか？ Instagramは近年女子大生を中心に大流行している、ユーザーが画像を気軽に投稿できるタイプのSNSです。 近頃は「インスタ映え」というワードも至る所で聞かれるようになり、観光地なども「インスタ映え」を重視したスポットなど...

GaucheでEmacsのnadviceみたいなことができるやつを作った

nadviceとは? Emacsでアスペクト指向プログラミング的なことをできるようにするためのライブラリです。 アスペクト指向というのは聞き慣れない言葉かもしれませんが、nadviceを使うだけなら難しくはありません。簡単に言うと、任意の関数の実行前後に好きな処理を挟むことができるライブラリです。 (defun hello-world () (print "Hello, world!")...

Trampが起動時に失敗してコケるのを防ぐ

ある日、trampを使ってサーバー上のファイルを書き換えた後にemacsを終了させ、再起動しようとすると、以下のようなエラーが出てしまうようになりました。 Tramp failed to connect. If this happens repeatedly, try ‘M-x tramp-cleanup-this-connection’ Tramp failed to connect...

MacでBitVisorをビルド(Docker編)

Mac上でBitVisorをビルドする方法として、考えられるのは以下のような方法があります Mac上で環境を整えて頑張ってビルド これはかなり茨の道です。できることはできるようですが、BitVisor自体のソースコードを弄ったりする必要があり、割と面倒です。 Linuxをデュアルブートしてそっちでビルド Linuxメインで使ってる人なら問題無いでしょうが、Macメインの人はビルドのたび...

Haskellで型を明示的に適用する

GHC8からの機能として、多相的な関数fに対してf @Tとすることで明示的に型を指定することができるようになりました。 この機能はTypeApplicationsという名前で提供されています。 Prelude> :set -XTypeApplications Prelude> :t show show :: Show a => a -> String Prelude&g...

テトリスの盤面の評価関数

ふと思い立って、テトリスを自動で解くAIを書いてみました。 最初はαβ法でやってみようと思ったのですが、ブロック1つに対して置き場所の候補が3〜40通りくらいあり、探索空間がアホみたいに広くなってしまったため断念。とりあえず探索の深さを1だけにして、評価関数だけで攻めていく方針でやっています。 テトリスの場合はゲームとしてかなり単純なので、あまり深く先読みをしなくてもうまくやればうまくいきそう...

ライフゲームを改良しました

去年くらいに作ったライフゲームを更新しました。具体的な更新内容は以下の通り Angular1からRiotへの置き換え 大量のDOMを重ねてゲーム画面を描画していたのを、<canvas>にまとめた サンプルの盤面の追加 UIをマシにする スマホ対応 ちなみにゲーム自体にはこちらからアクセスできます。 ライフゲームって何？って方は以下の説明を読むといいかもしれ...

SVMの理論的な話

前提 この記事では以下のものについては成り立つと仮定します。 Lagrange関数を用いて導出した双対問題の解が、元の最適化問題の解に一致すること(強双対性定理) KKT条件を満たす値が、元の最適化問題の解に一致していること この2つについてはそのうち勉強していきたいと思います。 SVMとは SVM(サポートベクターマシン)とは二値分類器の一つで、分離平面と訓練データの間の距離の...

Emacsで楽々絵文字入力 :joy_cat:

Jekyllにjemojiを追加したのはいいですが、:smile:みたいな絵文字の名前を全部覚えているわけではないので、絵文字の入力が面倒です :cry: そんなときは、emoji-cheat-sheet-plusというプラグインが便利です :blush: このプラグインは、絵文字のグラフィカルな一覧を表示して絵文字入力を支援してくれるものです :hatched_chick: インストールは...

親要素の高さを子のfloatしている要素に合わせる

つい先ほどまで、このサイトのタグ一覧は画面幅が狭い時に悲惨なことになっていました。 この原因は、タグ一覧にfloatされているliタグを使っていることです。 現在のタグ一覧の部分は以下のような構成になっています。 <div.tag-list> <ul> <li>タグ名</li> </ul> </div&gt...

Q-learningで効率的に動く車を探す

前回に引き続き、マルコフ決定問題を解いていきます。 前回は状態遷移確率がわかっているものであるとして計算をしていましたが、現実は必ずしも遷移確率がわかるとは限りません。 そのような場合に、前回の評価関数 \(Q_{t}(i, k)\) の漸化式を少し変え、確率の推定を行わずにその場のノリで \(Q_t\) を更新していく方法が取られることがあります。 このような学習方法を直接法といいます。 ...

Github Pagesが更新されなくなった

昨日あたりから突然、Github Pagesが更新されなくなりました。 以下のURLにアクセスしてリポジトリの設定を見てみると… https://github.com/username/username.github.io/settings 以下のようなシンプルな説明だけが出ていました。 Your site is having problems building: Page bui...

88%の適合率でドル円の値上がりを予測するプログラムを書いた

タイトルは釣りです。 FXに関しては全くの初心者ですが、適当に分析してみたらなんとなくそれっぽい結果が出てきたので紹介したいと思います。 機械学習の勉強のついでにFXの価格予測でもやって一儲けできたら一石二鳥だなーと思い、一番簡単な分類方法として、ドル円が値上がりするかどうかが線形分離できないか試してみました。 今回は線形分離用のアルゴリズムの中でも最も簡単な部類に入る、パーセプトロンを使っ...

ocamloptの謎のエラー「wrong file naming」

次のような2つのファイルを用意します。 (* mymodule.ml *) let hello () = print_endline "hello" (* hoge.ml *) let () = MyModule.hello () これをビルドしようとすると、以下のようなエラーが出ます。 $ ocamlfind ocamlopt mymodule.ml hoge.ml File "ho...

型レベルでFizz Buzz

GHC.TypeListにはNatというkindが定義されており、自然数のリテラルをkindがNatである型として利用することができます。 また、基本的な計算(+, -, *, ~)や、比較(==, CmpNat)なども用意されているので、型レベルFizz Buzzくらいなら比較的簡単に書けてしまいます。 -- TypeFizzBuzz.hs {-# LANGUAGE KindSign...

QEMUのuser mode network内のパケットをキャプチャする

QEMUにはパケットをキャプチャしてくれる機能があるので、オプションを足すだけで簡単にできます。 $ qemu -net nic,model=e1000 -net dump,file=/path/to/hoge.pcap -net user あとは吐かれたファイルをWiresharkなりで適当に解析すればok ...

人と違うC言語のコードを書く方法ベスト3

C言語は大学の講義などでも使われることが多く、あまりプログラミングを知らない人でもそれなりに読めてしまうので、面白くありません。 そこで、ここでは一歩差をつけた通っぽいコードを書くために必要なテクニックを3つ紹介したいと思います。 第3位: コンマ演算子を乱用する ,は左と右の式を評価し、右の式の結果を返す演算子です。これを使わなくていいところで使うことによって、意味の分からないコードにするこ...

キャラクターなんとか機 Web版を更新しました

キャラクターなんとか機 Web版 5年前に作ったっきり全く更新もせずに放置していたので、Python2.5が使えなくなり動かなくなっていたのを直しました。 とはいっても、ほとんど何もせずに使っているPythonのバージョンを上げただけです。 それ以外にもいろいろと古い部分が残っているので、暇な時にでも作り直したいと思ってます(ただし優先度は低い)。 ...

Emacs25から追加されたalist-get

むしろ今までなかったのか (setq lunch-price-alist '((hamburger . 500) (curry . 800) (sushi . 1200))) (assq 'curry lunch-price-alist) ;; => (curry . 800) (alist-get 'sushi lunch-price-al...

Macで$HOSTNAMEとhostnameを一致させる

Macでのホスト名の設定は2種類あるようです。 1つめが$HOSTNAMEに保存されている値。こちらは、システム設定→共有から変更できます。 もう一つがhostnameコマンドの表示する値。Emacsの(system-name)もこちらを表示します。こちらの方のホスト名は以下のコマンドで変更することができます。 $ sudo scutil --set HostName NEW_HOST_NA...

CSSで文字のはみ出した部分を「…」で省略する

今までは左側のRecent Postsの部分の記事タイトルを文字数指定で切り落としていたのですが、CSSでも同様のことができるみたいです。しかも文字数じゃなくて幅を超えた分だけ省略できるので、見た目も綺麗 <p id="box"> 寿限無寿限無五劫の擦り切れ海砂利水魚の水行末雲来末風来末食う寝る処に住む処藪ら柑子の藪柑子パイポパイポパイポのシューリンガンシューリンガンのグーリンダイグ...

Github Pages + Jekyllな環境でRSS

使う人いなさそうだけど無いとなんとなく不安なRSSフィードをこのサイトにも追加しました。 Github Pagesなのでプラグインを使わず、Jekyll管理下のxmlファイルを使ってテンプレートから自動的にフィードの生成をしています。 ちなみに参考にしたのは以下のリポジトリ。 snaptortoise/jekyll-rss-feeds: Templates for rendering RSS...

簡潔データ構造: Bit Vector (たぶんその1)

高速にアクセスができ、かつ理論上最も効率よくデータを圧縮した場合と同程度に小さなデータ構造のことを簡潔データ構造といいます。 今回は簡潔データ構造のうち、最も基本的なものの一つであるBit Vectorについて紹介したいと思います。 Bit Vector Bit Vectorは文字通り1ビットの値の列で、通常は以下の2種類の操作について考えます。 \( rank(B, x) \) : ...

Twitterのアイコンを寿司にする

Twitterのアイコンが丸くなってしまったので、昔ながらの寿司に戻す方法を紹介します。 Firefoxの場合 1. Greasemonkeyをインストールする まずはGreasemonkeyをインストールします。 インストールボタンを押して再起動すれば準備完了です。 2. スクリプトを追加する 再起動が終わればFirefoxの右上にキモい猿みたいなアイコンが出てくると思うので、そ...

逆FizzBuzzをHaskellで解いてみた

逆FizzBuzz問題というのがあるらしいです。 逆FizzBuzz問題 (Inverse FizzBuzz) - 猫とC#について書くmatarilloの雑記 簡単に言うとFizzBuzzの逆関数を求める問題ですね。 Haskellで解いてみました。 -- FizzBuzzInv.hs import Data.Maybe (catMaybes) import Data.Function ...

破壊的変更を隠蔽するDiffArray

HaskellのArrayは要素の更新を行うたびに配列全体のコピーが発生するので、頻繁な書き換えには向いていません。 -- ArrayTest.hs import Control.Monad import Data.Array.IArray import System.IO.Unsafe import System.Random randomVals :: Random a => Int...

ブログにDisqusのコメント欄を設置した

方法自体はいろいろな所に書かれていますし、特に今更説明する必要もないでしょう。 Disqus コメント欄があるとたまに間違えたことを書いたときに偉い人が集まってきて指摘してくれるので便利です。 ...

はてなブログからGithub Pagesに移行しました

タイトルの通りです。 サイトのレイアウトとかは今後少しずつなんとかしていこうかと思います。 ちなみに移行の方法についてですが、はてなブログからエクスポートしたMovable type形式のファイルを、以下のスクリプトにかけて大量のjekyll用htmlファイルに変換しました。 #!/usr/bin/env python # -*- coding: utf-8 -*- import sys,...

Gaucheでセッターを定義する

Gaucheではデータ構造の特定の値を変更するのに、 (set! (~ vector i) 10) とか (set! (cdr pair) ()) とかできてしまうのが不思議だったので、方法を調べてみました。まずは例として、以下のようなクラスを作ってみます。 (define-class <temperature> () ([celsius :init-keyword :celsi...

PFDSを読む: Binomial Heap

Binomial Heapとは、Binomial Treeというデータ構造を使って作られるヒープです。ここで、Binomial Treeとは、以下のようなデータ構造です。 rankが0であるBinomial Treeは、ただ1つのノードからなるシングルトン r > 0 について、rankがrであるBinomial Treeはr個の子を持ち、それらのrankはそれぞれ0, 1, ..., r ...

【重要】MacBookを手に入れたら真っ先にインストールするべき最強アプリn選

いい加減研究室で貰ったMacBookの環境設定をしたくなってきたので、とりあえず必要と思われるものとその入手先をメモっておきます。 完全に自分用メモ。 日本語入力しようとしたら勝手に変換される謎機能 邪魔なので消します。 ここのライブ変換のチェックをはずせばOK スペルチェック無効化 環境設定→キーボード→ユーザー辞書にあるいらなそうなチェックを消す ...

githubにssh接続できない

githubのアカウントを作りなおしたついでにssh-keygenし直したら、何故かgithubに繋がらなくなってしまいました。 $ git push -u origin master Warning: Permanently added the RSA host key for IP address '192.30.253.112' to the list of known hosts. si...

PFDSを読む: Weight-biased Leftist Heap

inkar-us-i.hatenablog.comこちらの記事でLeftist Heapの紹介をしましたが、今回はその亜種であるWeight-biased Leftist Heapを紹介します。 このデータ構造はほとんどLeftist Heapと同様ですが、rankのかわりに要素数が左に偏るようになります。すなわち、 根の部分が常に最小値となる 全てのノードについて、その左側の子の要素数は、...

PFDSを読む: Leftist Heapの実装

inkar-us-i.hatenablog.comこの記事ではLeftist Heapについて語るだけで終わっていたので、今回はバリバリ実装していきます。 その前に、Leftist Heapの定義のついてのおさらいをしておきましょう。 Leftist Heapとは、以下の性質をもつ二分木です。 根の部分が常に最小値となる 全てのノードについて、そのノードの左側の子のrankは、右側の子のra...

さくらVPSでシリアルコンソールからログインできない

さくらVPSのサーバーに標準で用意されているUbuntuをインストールしてシリアルコンソールを起動してみたところ、なぜかログインできない問題が発生。 デフォルトで用意されているユーザー名がubuntuなの知りませんでした、というオチでした。 ...

Leftist Heapの性質

Leftist Heapは、純粋関数型的にヒープを操作するために用いられるデータ構造です。Leftist Heapは要素が左に偏っている二分木として実装されます。 データ構造自体は以下のように単純に構成できます。 type 'a heap = | E | T of 'a * 'a heap * 'a heap ただし、このデータ構造は以下のような制約を持ちます。 let rank = f...

PFDSを読む: 二分木の改良

長年積んでたPFDSを読み始めることにしました。 積んでる間に邦訳が出たらしいのですが、とりあえず気にしない方針で。まずは単純な二分木 module type SET = sig type elt type set val empty : unit -> set val insert : elt -> set -> set val ...

正規表現エンジン制作入門(2): いろいろなDFA

オートマトンの単位を落としてしまいましたが、正規表現エンジンは作っていきたいと思います。前回定義したDFAを思い出してみましょう。inkar-us-i.hatenablog.comDFAは状態を持ち、入力された文字によってその状態を変えていく機械でした。この図はsが初期状態であり、文字'0'を受け取れば状態aに、'1'を受け取れば状態bに、'2'を受け取れば状態cに遷移し、bが受理状態であるオー...

rsyncでポート番号を指定する

本当は正規表現エンジンについての話を書きたかったのですが、最近まとまった時間が取れないので関係ないことを書きます。タイトルの通り。 $ rsync -e "ssh -p 12345" hoge@fuga.com:/foo/bar/baz/ /piyo/rofi/ これでok ...

Coqで型クラスで群論

群論に関する定義をするのであれば、型クラスを使うのが一番うまくいくと思います。 Class Group G := { gunit : G; gadd : G -> G -> G; ginv : G -> G; gadd_unit_l : forall g : G, gadd gunit g = g; gadd_unit_r : for...

Coqで型クラスでモナド

Haskell大好きなので、モナドを実装できそうな言語があればとりあえず実装してしまう癖があります。 Coqでモナド使うほどのことを書くのか、と言われればアレですが。 Class Monad (M : Type -> Type) := { point {A : Type} : A -> M A; bind {A B : Type} : M A -> (A -...

Coqで型クラス

Coqにも型クラスがあるらしいです。 Class Ord a := { le : a -> a -> bool }.これでleというメソッドを持つ型クラスOrdを定義できます。インスタンス定義は以下のように行います。 Fixpoint le_nat (n m : nat) : bool := match n, m with | O, O => tru...

Elmの型関連が弱すぎてつらい

inkar-us-i.hatenablog.comここでやたらElm推してるみたいな書き方をしてしまいましたが、僕自身はそんなにElm好きではありません。 型クラスがない Elmには型クラスが無いため、まともに多相的な関数を書くことはできません。 例えば、Elmには至る所でモナディックな処理が出てきます。 -- Maybeモナド Just 3 |> Maybe.an...

Elm始めてみました。

Elmという言語を一ヶ月ほど触ってみたので、この言語の特徴などを紹介したいと思います。 Elmとは http://elm-lang.org/この言語はざっくりと言うと、「JavaScriptにコンパイルされる、純粋関数型でHaskellっぽい文法の言語」です。 純粋関数型 ElmはHaskellと同様に純粋関数型(と通常はみなすことができる)言語です。基...

implicit parameterによる型クラスの罠

Scalaの型クラスは暗黙引数の受け渡しにより行われるため、スコープごとに同一な型クラスの別なインスタンス実装を使うことができます。 例えば、以下のような比較を行う型クラス、Cmpを考えてみましょう。 trait Cmp[A] { def eq(x : A, y : A) : Boolean def lt(x : A, y : A) : Boolean } これに対して、例えばIntであ...

Smith-Waterman法で配列の局所アラインメントを求める

今度は局所アラインメントを求めます。 前回の大域アラインメントと違って、今度は最も一致度の高い部分文字列を求めるアルゴリズムになります。 type alignment = char option list let maximums_by (key : 'a -> 'b) (lst : 'a list) : 'a list = let rec loop max_val maxs xs ...

Needleman-Wunsch法により配列の大域アラインメントを求める

アラインメントとは、2つの配列s, tに欠損記号「-」を挿入して、出来る限り2つの一致度が高くなるように並べたものです。 例えば、2つの文字列"ABCD"と"ACDE"があったとき、これは1つめの文字列から'B'を削除して末尾に'E'を挿入たものだと考えるのが自然でしょう。この時の2つの文字列のアラインメントは、それぞれ"ABCD-"と"A-CDE"となります。アルゴリズム自体の説明は「Need...

OCamlの値の比較について

OCamlには2種類の値の比較方法があります。 ==, != これらの演算子は、右辺と左辺が全く同一のオブジェクトであるかを判定します。==という名前は大抵の言語で使われているので、つい癖で値の比較に使用してしまいそうですが、この演算子はむしろSchemeのeq?, Pythonのisに近いものです。関数型らしいコードを書く上では使うことはほとんど無いでしょう。流...

OCamlのmatch文とbegin..end

OCamlにはオフサイドルールは無いので、例えばmatch文をネストした時に、 let rec zip xs ys = match xs with | x :: xs' -> match ys with | y :: ys' -> (x, y) :: zip xs ys | [] -> [] | [] ...

教養としてCOBOLに触れてみる

教養として一度くらいCOBOLに触れてみなければダメなんじゃないかと思ったので、COBOL入門としてFizz Buzzを書いてみました。コードはこちら。 000010 IDENTIFICATION DIVISION. this 000020 PROGRAM-ID. FIZZBUZZ. ...

Prologでしょぼい型推論器みたいなものを作る

Prologの練習です。 以下で定義される簡単な式の型を推論し、その値を評価します。 * 数値はint型 * t, nilはbool型 * XがT型、YがU型のとき、ペアX & YはT & U型 * FがT -> U型、XがT型のとき、関数適用F $ XはU型組み込み関数はadd, eq, and, neg, car, cdr, identity, applyの8種類を用意...

Prologならではのソートアルゴリズム

簡単な問題なら問題をPrologの言葉で書いてやるだけで勝手に解けてしまうのが、Prologのすごい所です。 例えばソートに関しても、(計算量とかの話に目を瞑ってしまえば)こんなに簡単に書くことができるようになります。 % sort.pl % remove(X, L, M) : リスト L から要素 X を先頭から1つ削除したものが M である remove(X, [X | L], L). r...

Coqで代数的データ型の各要素についての等式を得る

前提 C x y z = C x' y' z から x = x', y = y', z = z' を導くためのタクティックが用意されています。 injection 等式 H : C x y z = C x' y' z' についてinjection Hをすると、ゴールをx = x' -> y = y' -> z = z' -> (元のゴール)という形に書き換えてくれます。 Go...

Coqで等式の左右を入れ替える

タイトルの通りです。eq_reflをdestructしていい感じにやるような方法でも解けることは解けます。 Goal forall (T : Type) (x y : T), x = y -> y = x. Proof. intros T x y H. (* H : x = y *) destruct H. (* Goal: x = x *) reflexivity. Qe...

Coqのintrosでパターンマッチング

destructは以下のような代数的データ型 Inductive T : Type := | C1 : x11 -> x12 -> ... -> T | C2 : x21 -> x22 -> ... -> T ... | Cn : xn1 -> xn2 -> ... -> T.の値xに対して、 destruct x as [x11 x22 ....

Ubuntuで最新のnode.jsを使う

Ubuntuの標準のリポジトリに入っているnode.jsがバージョン4.1くらいなので、新しめの文法を使おうとすると割とつらいものがあります。github.comNodeSourceという便利なものをどこかの誰かが用意してくれているので、これを使いましょう。これを使うと各ディストリで好きなバージョンのnode.jsが使えるようになります。 $ sudo curl -sL https://deb....

Amazon Dash Buttonが届いたのでとりあえずツイートボタンにしてみた

ついに我が家にもAmazon Dash Buttonが届きました。そのまま使うのも面白くないので、npmのdash-buttonというライブラリを使ってツイートボタンにしてみたいと思います。github.com 注意: dash-buttonはES2015の新文法をバリバリ使っているので、比較的新しめのnode.jsじゃないと動きません。この記事での動作環境は6.9.4ですが、それでもasync...

Quineの書き方

inkar-us-i.hatenablog.com前回の記事で書き初めと称してQuineを書きましたが、実は僕自身Quineを書くのは初めてでした。 書き始める前はQuineは何をやってるかわからない黒魔術にしか見えませんでしたが、実際に書いてみると意外と楽にできることがわかったので、そのコツのようなものをメモしていきたいと思います。Quineには、大きく分けて2種類が存在します。 eval...

書き初めQuineを書きました

皆様、明けましておめでとうございます。 新年早々インフルエンザに罹り、意図せず寝正月を送っていたのですが、そろそろ体調がよくなってきたので書き初めでもしてみようかと思います。 eval(x="c=($)=>String.fromCharCode($);q=c(34);b=c(92);s=c(59);n=c(10);sp=c(32);hs=c(3\ 5############);p...

さよならインクルードガード

タイトルは嘘です。ある程度経験のあるCプログラマーなら、 #ifndef HOGEHOGE_H #define HOGEHOGE_H .... #endif /* HOGEHOGE_H */ といった定型文をおそらく数百回は書いたことがあるでしょう。 これらを省略するため[要出典]に、#pragma onceというディレクティブが各処理系により提供されています。#pragma onceが書か...

JavaでMapの初期化を行う方法いろいろ

Javaの面倒臭さの一つに、Mapリテラルが存在しないというものがあります。普通にMapを使おうとすると、 import java.util.*; class MapLiteralExample { public static void main(String[] args) { Map<String, Integer> hogeMap = new Hash...

プログラミング初心者が最初に選ぶべき言語73選

これからプログラミングを始めようとする人にとって、最初の壁となるのが「プログラミング言語の種類が多すぎて、どの言語を勉強すればいいかわからない」ということだと思います。 今日はそんなプログラミング初心者のために、選ぶべき言語をたった73種類に厳選しました。入門書を買う時などの参考にしてください。 Java 言わずとしれたプログラミング言語。一度コードを書いてしまえばWindo...

アドホックな多相性の実現方法いろいろ

inkar-us-i.hatenablog.com 先日OCamlのFunctorという新たな多相性の実現方法を学んだので、せっかくなので各言語のアドホック多相性についてまとめてみたいと思います。クラスとその継承ではなく、アドホックな方法で多相を実現する手段はいくつかありますが、その根本にあるアイデアはすべて同じです。以下では、例としてどの言語でも、「同値比較のできる型tについて、tのリストから...

機械学習でAV女優かどうかを判定するプログラムを作った

AV女優判定機タイトルの通りです。 Gaucheの練習 & 機械学習の勉強として作ってみました。 ナイーブベイズを用いて、ユーザーの直近の発言内容からそのユーザーが「AV女優、一般男性、一般女性、bot」のうちどれに最も近いかを判定します。このように、AV女優のIDを入れるとかなりの高確率でAV女優であると判定してくれます。ち...

SWI-Prologを始めてみる

長いこと積んであった『Prolog Programming for Artificial Intelligence』を少しずつ読み始めることにしたので、現在使っているUbuntuにSWI-Prologをインストールすることにしてみました。 $ sudo apt install swi-prolog実行はprologコマンドでできます。 $ prolog Welcome to SWI-Prolog...

OCaml初心者が戸惑いそうな謎記号一覧

^(キャレット) ^は文字列連結の演算子です。 # "hoge" ^ "fuga";; - : string = "hogefuga" +., -., *., /. 浮動小数点数同士の演算には、元の演算の記号の後にドットが付きます。Schemeと同じですね。 # 3.0 +. 4.0;; - :...

Gaucheのwriteのバグ(?)を発見した

全角スペースはwriteでは||で囲われずに普通に表示されるのに、readでは半角スペースと同一の扱いでスキップされます。 gosh> (with-output-to-string (^() (write '|　|))) ; 全角スペース "　" gosh> (call-with-input-string "|　|" read) ; ||で囲わ...

nginxで特定のパスを別なポートにリダイレクトする

一般的にはリバースプロキシというらしいです。 Railsで作ったものを12345番ポート、Yesodで作ったものを12346番ポート、Playで作ったものを12347番ポートで公開して、 example.com/railsでexample.com:12345, example.com/yesodでexample.com:12346, example.com/playでexample.com:12...

apacheのポート番号を変更する

apacheのポート番号を12345に変えたいとします。まずは/etc/apache2/sites-available/000-default.confの <VirtualHost *:80> ... </VirtualHost>を <VirtualHost *:12345> ... </VirtualHost>に変更します。次に、/etc/apa...

CGIの仕様

とある理由からGaucheでCGIとかいう謎なことをしなければならなくなったので、ここにメモしておきます。 メソッドは環境変数REQUEST_METHODに保存される。 GETパラメータは環境変数QUERY_STRING、POSTのボディは標準入力。ただし、GET/POSTパラメータはGaucheではcgi-mainの引数の引数に渡される GETパラメータがhoge=fugaという形式ではな...

ApacheでCGIを動かす

今更CGI、と思うかもしれませんが、諸般の事情によりCGIを実行せざるを得ない状況に陥ってしまったので、ここにその方法をメモしておきます。 CGIのモジュールが読み込まれているか確認 少なくともUbuntuのapache2では、cgi_moduleはデフォルトでは読み込まれていません。 モジュールを有効化するには、/path/to/mods-enabled/にモジュールのシン...

Coqのsplit, left, rightについてもう少し詳しく

inkar-us-i.hatenablog.com上の記事でandを証明するためにsplit, orを証明するためにleft, rightを使えばいいと書きましたが、実はこれらのタクティックはもう少し一般的に作られています。 split splitはandのみではなく、コンストラクタがC : X1 -> X2 -> .. -> Xn -> Pという形の任意のゴールPに対して扱...

Coqで「任意のxについて…」「あるxが存在して…」を扱う

Coqで「任意のxについて…」を表すforall xは、xを受け取って残りの命題の証明を返す関数となっています。 Definition prop_1 : forall (x : nat), x = x := fun x => eq_refl x.また、「あるxが存在して…」を表すexists xは、以下のようなデータ型として定義されています。 Inductive ex (A:Type)...

Coqで「…かつ…」、「…または…」を扱う

連言「かつ」、選言「または」を表すandとorは、Coqでは次のようなデータ構造として定義されています。 Inductive and (A B:Prop) : Prop := conj : A -> B -> A /\ B where "A /\ B" := (and A B) : type_scope. Inductive or (A B:Prop) : P...

Coqで定理の証明中に補題を示す

assertタクティックを使うと、証明の途中で他の補題を証明できます。 Goal forall P Q R : Prop, P -> (P \/ Q -> R) -> R. Proof. intros P Q R H1 H2. (* H1 : P *) (* H2 : P \/ Q -> R *) (* 先にP -> Rを示す *) ...

Coqで前提や定理を適用して証明する

ゴールが前提や既にある定理そのものである場合が、証明の一番簡単なパターンです。 前提がゴールそのものである場合 assumptionを使うと、前提にあるゴールと全く同じ命題をそのまま適用してくれます。 Goal forall P : Prop, P -> P. Proof. intros. (* P : Prop, H : P *) assumption. Qe...

Coqで数学的帰納法を行う

数学的帰納法を行いたい場合は、基本的にelimかinductionのどちらかのタクティックを利用します。 elim こちらが最も基本的な帰納法です。elim x.とすることで、xについての帰納法を行うことができます。 例えば、以下のコードでは直接to_zero n = 0を示すのではなく、ゴールをto_zero 0 = 0と、 forall n0, to_zero n0 = ...

Coqでデータ型に対して条件分岐を行う

証明中にデータ型に対して条件分岐を行うためには、case, case_eq, destruct等を使います。 とりあえず普通に条件分岐をする caseは普通の条件分岐です。例えばb : boolに対してcase b.とすると、b = trueである場合とb = falseである場合の2つに分かれ、それぞれの場合に対して証明を行うことで証明終了となります。 (* negb は ...

Coqで定理の特定の項だけを書き換える

rewriteやsimplを使って定理を書き換えようとすると、どうしても思ったとおりに書き換えがいかないことがあります。 (* 結合法則と交換法則を使って、3つの項を入れ替える *) Goal forall (T : Type) (op : T -> T -> T), (forall x y z : T, op (op x y) z = (op x (op y z)))...

Coqで既存の定理、定義に従って計算する。

定義に従って計算する 定義に従って計算するには、simpl, compute, unfoldが使えます。 simpl.はゴールの式をいい感じに簡単にしてくれるのに対し、compute.はとりあえず式展開します。また、unfoldは定義の左辺から右辺に書き換えます。 Fixpoint fact (n : nat) : nat := match n with | O ...

Coqで前提の矛盾から定理を証明する

矛盾を導く方法は何通りかあります。 すでに前提にFalseがある場合。 まずは一番基本的な方法から。既に前提にFalseがある場合です。 Falseの定義は、以下のようになっています。 Inductive False := (* コンストラクタが1つもない *).従って、前提にP : Falseがある場合、destruct P.してしまえばその瞬間にPのすべてのケースについて...

Gaucheで文字列のシーケンシャルアクセス

Gaucheでそこそこサイズの大きい文字列へのシーケンシャルアクセスをしたい場合の注意点です。例として、以下のURLにある『吾輩は猫である』の文書中に、何回「猫」という文字が出てくるかを調べてみましょう。http://www.aozora.gr.jp/cards/000148/card789.html#download $ wget http://www.aozora.gr.jp/cards/...

Gaucheでロード時定数を作る

Gaucheには元々ロード時定数という機能はありませんが、マクロを使ってうまいこと頑張ると作ることができます。 ;; ロード時定数を保存するためのモジュール (define-module *constant-table*) ;; モジュール module の中で expr を評価し、 *constant-table* に保存 ;; この位置にある式を保存された値の読み出しに置き換える。 (de...

Basic認証の方法を理解する

Basic認証は数あるHTTPの認証方法の中でも最も簡単なものです。認証方法は、ユーザー名とパスワードをコロンで繋いだものをbase64でエンコードし、Authorizationヘッダの値に"Basic (先ほど作った文字列)"をセットするだけです。アホみたいに簡単なので、不慣れなGaucheでも2分くらいで実装することができました。 (define (basic-auth user passw...

Gaucheでクラスのフィールド名を変数に束縛する。

HaskellでいうNamedFieldPunsのようなものです。 クラスのインスタンスと、スロット名のリストを渡すことによって、スロット名と同名の変数にスロットの値を束縛するマクロを書きました。使用例は記事の下の方にあります。 ;; macro let-slots (((slot-name ...) expr) ...) body ... ;; インスタンスexprのスロットslot-name...

Schemeと各括弧

多くのScheme処理系では、角括弧[]が通常の括弧()と同一視されます。 この角括弧の使いどころについてまとめてみました。 角括弧は使うな まず始めに結論から書くと、今後書くSchemeのコードでは、角括弧は使用しない方が良いでしょう。というのも、R7RS*1における角括弧の扱いは、 [ ] { } Left and right square a...

Gaucheでソースコードのあるパスを取得

きちんと ./configure && make && make install するようなプログラムでもない限り、ソースコードを適当にどこかから引っ張ってきて、そこから $ gosh ./main.scm するだけでとりあえず動くようにできたほうが楽な場合はよくあります。 しかし、Gaucheでそれをやろうとした場合は色々な問題が……。 ソースコードからの相対パスでload ...

Gaucheで#を返す

ジェネレーターを自作する場合なんかに#<eof>を返したくなる場合がありますが、以外とググッても方法が出てきません。R6RSの(eof-object)を使えば簡単に生成できます。 ;; 1からnまでの数を返すgeneratorを返す (define (gen n) (define i 0) (^() (if (<= n i) (eof-object...

Schemeにおける「多値」という概念について

inkar-us-i.hatenablog.comこの記事で少しだけ多値について紹介しましたが、この頃はまだよく存在意義がわかっていませんでした。 そもそも多値とは？ 大雑把に説明すると、valuesとかhoge&fuga関数を呼んだ時に値が複数返ってくるアレです。 (values 3 2 1) ;; => 3 2 1 (※注: リストではなく、あくまで値が複数ある) ...

Gaucheで値の比較

値の比較に使用する関数は通常eq?, eqv?, equal?の3種類あるのですが、それらの使い分けが曖昧だったのでまとめてみました。 eq? (eq? x y) はxとyが全く同じオブジェクトであるか(=メモリ上の同じ位置にあるか)どうかを判定します。Pythonのisに近いやつですね。 gosh> (eq? 1 1) ; 数値の比較結果は処理系依存らしい。Gauch...

Gaucheでデバッグ

Gauche Users’ Reference: Top上のサイトを見る限り、printfデバッグ的なことをするためには#?= #?,の2つの構文が使えるようです。とりあえず#?=の使用例。 gosh> (define (foo x) (+ x 1)) foo gosh> #?=(foo 3) #?="(standard input)":21:(foo...

Gaucheでreturn文

return文のようなものは比較的簡単に作れますが、念の為覚え書き。値を返したい位置の継続を受け取って、returnするかわりにその継続に戻り値を渡します。 (use gauche.collection) ;; xsとysのすべての要素が等しければ#t, そうでなければ#f (define (vector-equal? xs ys) (if (not (eq? (vector-length...

coq-modeとproofgeneralでcoq環境を作る

EmacsでCoqを扱う場合、proofgeneralというものを使うのが一般的らしいです。 $ sudo apt-get install coq proofgeneral Ubuntuの場合はどちらもaptのリポジトリに入っているので、上のコマンドを打つだけでインストールは完了です。 (load-file "/usr/share/emacs/site-lisp/proofgener...

Gaucheに継続を「実装」する

/2016/09/01/200000.htmlinkar-us-i.hatenablog.com上の記事でしっかりしたモナドが作れたので、これを使って継続を実装します。 (define (cont-return x) (^(cont) (cont x))) (define (cont-bind x f) (^(cont) (x (^(xval) ((f xva...

Gaucheでモナド その3

/2016/08/27/200000.htmlinkar-us-i.hatenablog.com上の記事で作ったモナドはグローバルなスタックに現在のモナドを積むというものでしたので、mlet*の終了と同時に現在使用しているモナドに関する情報が消滅してしまい、実際の評価が後で行われるStateモナドのようなモナドを作ることはできませんでした。そこで、今回はScalaライクに暗黙引数を使ってモナドを...

libraryとexecutable両方を含むcabalパッケージを作る

cabal initした時に「libraryとexecutable、どっちのパッケージにする？」みたいなことを聞かれるので、今まで1つのパッケージにはlibraryとexecutableのどちらか一方しか含むことができないと思っていました。.cabalにlibrary:とexecutable:の両方を書けば、普通に両方を含むようなパッケージも作ることができます。 name: ...

Pythonにおける弱参照

Pythonにも弱参照は存在するらしく、weakrefというモジュールで提供されています。 >>> import weakref >>> class A(object): pass ... >>> a = A() # ... (*) >>> ptr = weakref.ref(a) >>> ptr()...

stackでプロファイリングを有効にしてビルドする

以下のようにオプションを渡せば、stackでもプロファイリングを有効にしてビルドすることができます。 $ stack build --executable-profiling --library-profiling --ghc-options="-fprof-auto -rtsopts" あと、実行時にも1つハマりどころがあります。ビルドしたバイナリをRTSオプションを付けて...

ようやくstackを使い始めた話

レポートの提出期限間際にcabalの依存関係がぶっ壊れて大変な思いをしたので、ようやく重い腰を上げてstackを使い始めてみることにしました。 インストール インストール方法とかはだいたいこの辺を参照しました。stack/install_and_upgrade.md at master · commercialhaskell/stack · Git...

Gaucheでモナド その2

inkar-us-i.hatenablog.comこのときはGauche歴半日くらいだったんで中置演算子とか定義してて微妙な感じの構文だったので、もう少しLispらしいモナドを書いてみました。 (define *monad-stack* '()) (define (push-monad! monad) (set! *monad-stack* (cons monad *monad-stack...

Emacs Lispにおける関数の扱い

他の人のEmacs Lispの設定を眺めていて気づいたのですが、(add-hook hoge-hook XXXX)のXXXX部分にlambdaを入れる場合、 (lambda () ...) と普通に書く人と、 '(lambda () ...) みたいにクオートして書く人と、 #'(lambda () ...) みたいな謎クオートする人がいますよね。このへんのうち、実際どのやり方が正しくてどれが間...

CPSとSSA

SSA(Static Single Assignment form, 静的単一代入)とは、一つの変数についての代入文がプログラム中で一度しか現れないような書き方のことを指します。 Scalaでいうと、すべての変数がvalになっているようなものですね。プログラムをこの形式に変換することによって、データフロー解析がやりやすくなるらしいです。 実は、少し前までちょっとした言語処理系を書いていたので(こ...

CPS変換についての覚え書き

CPS(継続渡しスタイル)とは、関数自体に「その後の処理」を引数として渡してしまうような書き方です。例: ;; 点(x . y)のノルムを求める (define (norm x y) (sqrt (+ (expt x 2) (expt y 2)))) (norm 1 1) ; => 1.414... ;; normのcps版 (define (norm/cps x y cont) ...

Ook!はSchemeである

Ook!のソースも、括弧で括ればただのS式ですよね。 ;; ook.scm (define *mem-size* 10000) (define *mem* (make-vector *mem-size* 0)) (define *ptr* 0) (define (inc-ptr!) (inc! *ptr*)) (define (dec-ptr!) (dec! *ptr*)) (define (...

Gaucheのコメントいろいろ

なんか今更な気もしますが……。 行コメント セミコロン(;)から行末まではコメントとみなされます。セミコロンの数にも作法があるみたいです。 ;;; モジュール自体の説明とか、大きなコードブロックの説明 ;;; ;;; このモジュールはフィボナッチ数を生成するジェネレーターを提供するなんやかんやです。 (use gauche.generator) ;; 次にくる同じインデン...

multi-termで快適なキー操作

multi-termで作業してると、「単にシェルとして扱いたい場合」と「シェルの出力を編集したい場合」とでほしいキーバインドが異なる場合があります。例えば、C-aにterm-send-rawを割り当てているとして、普通にコマンドを打っているとき $ sl ./hoge/fuga/fo# ここでコマンド名間違えてることに気づく ここでC-aを押した時、期待しているカーソルの戻り位置は $ sl ....

dynamic-wind

R5RSではdynamic-windという面白い関数が定義されています。 (dynamic-wind before thunk after) dynamic-windはまずbeforeを呼び出し、その次にthunkを、最後にafterを呼び出します。試しに以下のようなプログラムを実行してみましょう。 (define *outer-cont* #f) (let ((message (call/c...

Gaucheの複素数

gosh> 1+3i 1.0+3.0i gosh> i *** ERROR: unbound variable: i gosh> 2i *** ERROR: unbound variable: |2i| この書き方キモくないですか？複素数なんて特定の用途にしか使わないし、別に複素数リテラルとか用意しなくても gosh> (complex 3 5) 3.0+5.0i みたい...

Gaucheで手続き以外のオブジェクトも呼び出し可能にする

object-applyというメソッドを定義すると、手続き以外の任意のデータ型をあたかも関数であるかのように呼び出すことができます。 ;; (数 数)を(* 数 数)にする (define-method object-apply ((x <number>) (y <number>)) (* x y)) (define x 5) (3 x) ; => 15 以前...

Gaucheでパラメータを定義する

Gaucheには、グローバル変数の代わりに使用できるパラメータというオブジェクトが存在します。 パラメータの作成 (define x (make-parameter 3)) (x) ; => 3 (x 100) ; xの値を100に設定 (x) ; => 100 典型的な使い方としては、特定の関数が使用するデフォルトの値を設定する場合などに使えます...

Gaucheで優先度付きキュー

Gaucheの練習。実は何気に優先度付きキューの実装は初めてだったので、ツリーを配列で管理したほうが楽ということを知らずに若干手こずりました。 (define-class <priority-queue> () ((queue-vector :init-keyword :queue-vector :accessor queue-vector) (size :init-key...

Gaucheでリスト内包表記

srfi-42には、リスト内包表記に関するマクロが定義されています。 (use srfi-42) ;; Haskellでいう ;; [i * 2 | i <- [0, 1, 2, 3, 4]] (list-ec (: i '(0 1 2 3 4)) (* i 2)) ; => (0 2 4 6 8) ;; iの値の範囲の指定もできる (list-ec (: i 0 5) (* i...

パターンマッチでTextを1文字ずつ処理する

PatternSynonymsのいい感じの実用例が思いついたので。 {-# LANGUAGE PatternSynonyms, OverloadedStrings, ViewPatterns #-} import Data.Text pattern c :+ cs <- (uncons -> Just (c, cs)) このパターンを定義することで、先頭文字がcで残りがcsである...

Gaucheで構造体を定義する

クラスほど大したことをしなくても良い場合、define-record-typeというマクロを使うことでより簡単な構造体を定義することができます。 (define-record-type point #t #t x y) (define p (make-point 3 4)) (point? p) ; => #t (point-x p) ; => 3 (point-y p) ; =&...

Gaucheで関数の実行時間を測定する

gauche.timeのtime-this関数を使うと、指定した関数の実行にどれくらい時間がかかるのかを測定することができます。 (time-this 実行回数 実行する関数) 例として、クラスを使った場合と、ベクタを適当にラップした型に対してアクセスするのとで、どの程度実行に差が出るのかを調べてみたいとします。 (use data.random) (use gauche.time) (def...

Pythonで代数的データ型とパターンマッチ

PythonでHaskellっぽい代数的データ型とパターンマッチをできるようにするためのメタクラスです。 まあこれも余り用途はなさそうですけど。 def AlgTypeMeta(*names): class _AlgTypeMeta(type): def __new__(metacls, name, bases, methods): def in...

Pythonでsealedクラス

とくに意味も用途もないけど何となく思いついたので作ってみました。sealedクラスとはScalaの機能で、別モジュールからの継承をできなくさせる機能です。 # sealed.py class SealedException(Exception): pass class SealedMeta(type): def __init__(self, name, bases, meth...

Gaucheで多値を受け取る

複数の値を返す場合、それらの値をリストやペアにしてもよいのですが、通常、Schemeでは多値というものを利用します。 gosh> (min&max 2 4 3 1 5) 1 5 このmin&maxは、与えられた引数のうち最小値と最大値を返す多値関数です。他にも、商と余りを返すquotient&remainder等もあります。 gosh> (quotient&remai...

ImplicitParamをConstraintとして扱う

=>の左側に来るものはすべてConstraintなので、暗黙引数をConstraintとして扱うこともできます。 {-# LANGUAGE ConstraintKinds, ImplicitParams #-} type Showable t = ?show :: t -> String print' :: Showable t => t -> IO () print' a...

Gaucheでデータ型の簡単な表現を定義する

例として、以下のようなクラスを用意します。 (define-class <person> () ((name :init-keyword :name) (age :init-keyword :age) (pref :init-keyword :pref))) このようなクラスのインスタンスを作成してみます。 (define taro (make <person&...

Cabalで静的ファイルをパッケージに含める

YourPackage.cabalに data-dir: dirname data-files: *.txt img/*.pngのように記述すると、dirname以下のdata-filesに指定したファイルがインストール時にコピーされます。また、これらのファイルにアクセスするためのPaths_YourPackage という名前のモジュールが自動生成され、 realpath...

Gaucheでパーセプトロンを作った

Gaucheの練習。 パーセプトロンは簡単に作れる割に何となく学習してくれた感があって面白いです。 ;; perceptron.scm (use gauche.collection) ;; xがしきい値を超えているかを判定する関数 (define (sig x) (if (<= x 0) 0 1)) ;; 最終的な結果を出力するためのニューロン (define-class <...

named let

Gauche(に限らずほぼすべてのLISP)では、letは次のようなシンタックスシュガーとなっています。 (let ((hoge hoge-value) (fuga fuga-value)) (some-function hoge fuga)) ;; ↓展開後 ((lambda (hoge fuga) (some-function hoge fuga)) hoge...

Gaucheにおけるモナド的パターン

Maybeモナド的なパターンはand-let*を使うことで処理することができます。 (define (maybe-add maybe-a maybe-b) (and-let* ((a maybe-a) (b maybe-b)) (+ a b))) (maybe-add 3 2) ; => 5 (maybe-add #f 5) ; ...

Gaucheでn-queen問題

Gaucheの練習。 任意のnに対してn-queen問題を総当りで解きます。 ;; 横x, 縦yマス目の位置のクイーンを(x . y)で表す (define (x queen) (car queen)) (define (y queen) (cdr queen)) (define (queen-at x y) (cons x y)) ;; queenがqueensのうち、1つでも取れるものがあ...

Gaucheでパターンマッチ

util.matchモジュールを使えば、GaucheでもHaskellのようなパターンマッチを行うことができます。 リテラルに対するパターンマッチ リテラルに対するパターンは、そのリテラルを直接書けばOKです。 (use util.match) (define (fact n) (match n (0 1) (n (* n (fact ...

ジェネリック関数を定義する

Gaucheでは、アドホックに多相を実現する手段としてジェネリック関数が用意されています。 ;; 足し算 (define (add x y) (+ x y)) (add 3 2) ; => 5 ;; ベクターも足し算したくなった (define (vector-add xs ys) (vector-map + xs ys)) (vector-add #(1 2 3) #(4 5 6)) ...

Gaucheでクラスの作成

どうやらGaucheにもクラスは存在するようで、継承やアクセサの設定など、基本的なクラスに関する操作は行うことができます。 クラスの定義 (define-class <animal> ; クラス名 () ; 親クラスのリスト ()) ; スロット一覧 (define-class &...

Gaucheでハノイの塔

Gaucheの練習。n個のハノイの塔の解き方を表示するプログラムです。 各板の大きさは数値として表され、数値が大きい方が大きい板となっています。 また、見やすさのため表示する際はリストの逆順(右のほうが塔の上側)となっています。 (use gauche.array) ;; n個のハノイの塔の解き方を表示する。 (define (hanoi n) (define towers (array ...

M-x termのシェルの色をテーマに合わせる

まずはテーマの配色を調べます。自分の環境(Ubuntu)では /usr/share/emacs/24.5/etc/themes にテーマのソースコードがあったので、まずはそれを開いて配色を確認します。 (deftheme misterioso "Predominantly blue/cyan faces on a dark cyan background.") (let...

型クラス自体を型として扱う

ConstraintKinds拡張を使うと、型定義の=>の左辺にくる制約そのものを型として扱うことができるようになります。 {-# LANGUAGE ConstraintKinds #-} -- ConstraintKinds拡張がなければこのような定義はできない type MyShow t = Show t -- typeで定義した制約を=>の左辺に書ける myShow :: MyS...

継続でモナド

Haskellの>>=は実質継続渡しみたいなものなので、継続をうまいこと使えばSchemeにもモナドが実装できるはず(？）とりあえずMaybeモナドを実装してみました。 (define (empty-stack) '()) (define (empty-stack? stack) (null? stack)) (define-syntax push! (syntax-rules () ...

モナドで擬似マルチタスク

継続のことばかり考えていたらなんとなく思いついてしまったので載せておきます。 {-# LANGUAGE GADTs #-} module Concurrent where import Control.Monad import Control.Monad.IO.Class import Data.Either data ConT m b where Done :: m b -> ...

Emacs24.4以降でmulti-term.elを動かす

そろそろシェルもEmacs上で動かそうかなと思い立ったのでmulti-term.elをインストールしてみましたが、実行すると以下のようなエラーが発生して動きませんでした。 Symbol's function definition is void: ad-advised-definition-p どうやらad-advised-definition-pはEmacs24.4で廃止されたらしいので、自...

Emacsで快適なウィンドウ操作を行う

Emacsのウィンドウ周りが結構不便だったので、いい感じに簡単に操作できる関数を書いてみました。まずは1つめ。 ;; 空気を読んでいい感じにウィンドウを分割してくれるやつ (defun split-window-automatically () (interactive) (if (> (window-width) (* 2.5 (window-height))) (s...

Scheme始めました

某友人の影響でLispに目覚めてしまったので、とりあえずGaucheの勉強を始めることにしました。 (とは言っても授業でコンパイラ作ったりCPU作ったりしてて結構忙しいので、Gauche自体の勉強はかなりゆっくりになると思いますが)なぜ数あるLisp方言やScheme方言の中からGaucheを選んだかと言うと、Lisp方言の中では比較的モダンな設計のSchemeの中でも、Gaucheが一番Com...

Haskellで辞書リテラルや集合リテラルを扱う

OverloadedLists拡張を有効化すると、通常のリストリテラルの型が[a]からforall t. IsList t => tになります。IsList型クラスはGHC.Extsで定義されており、以下のような定義になっております。 class IsList l where type family Item l :: * fromList :: [Item l] -> l f...

独自のkindを定義する

DataKinds拡張を有効にすると、独自のkindを定義することができるようになります。 data Nat = Z | S Nat 通常これは「値コンストラクタZとSからなる型Nat」が定義されますが、DataKinds拡張が有効になっている場合、この型Natと値コンストラクタZ, Sが、それぞれkindと型コンストラクタに「昇格」します。すなわち、型Zと型S (n :: Nat)からなる新た...

Haskellで独自のパターンを定義

Scalaではunapplyメソッドを定義することにより独自のパターンを定義できますが、実はHaskellでも似たようなことができます。PatternSynonyms拡張を有効化することで、既存のパターンについてのエイリアスのようなものを定義することができます。 {-# LANGUAGE PatternSynonyms #-} pattern x :-> y = (x, y) この拡張を...

Scala的な型クラスをHaskellで作る

Scalaの型クラスはHaskellの型クラスとは全くの別物ですが、HaskellでもImplicitParams拡張を使うことによってScalaの型クラスのようなものを利用できるようになります。 ImplicitParams このマイナーな拡張を有効化すると、関数に対して暗黙的に引数を渡すことができるようになります。 暗黙引数を受け取る関数は以下のように定義します。 -- ...

gunfoldの型を読み解く

まず最初に、Data型クラスのその他のメソッドについて見てみましょう。 >>> :t toConstr toConstr :: Data a => a -> Constr toConstrは、値から値コンストラクタの情報を得るための関数です。 data Dish = Sushi { fish :: String } | Curry { isChi...

Data.Dataのgfoldlの型を読み解く

Data.Data.Data型クラスを使うと、Typeableと同様に非常に一般的な関数を書くことができるようになります。前回のTypeableは値の型情報を取得するだけでしたが、Dataのメソッドを用いると代数的データ型の任意のフィールドにアクセスするといったようなことができるようになります。また、DataもDeriveDataTypeable拡張を利用することにより、任意の型に対してderi...

Typeableを使ってみる

Data.Typeable.Typeableを使うと、TemplateHaskell無しでも非常に一般的な関数を書くことができるようになります。型クラスData.Typeableのインスタンスは、typeOfという関数を使うことによって型情報を取得することができます。 >>> :m +Data.Typeable >>> typeOf (3 :: Int) In...

getter, setterの定義

Scalaでは「hoge_=(x)」という形のメソッドを定義すると、「hoge = x」という形でそのメソッドへのアクセスができます。 class Coffee( private var country_ : String, private var roast_ : String, private var grind_ : String ) { def country = cou...

ScalaFX: TaskとService

JavaFXでは別スレッドで作業を行うためにTaskとServiceという2つのクラスを提供しています。 ScalaFXでも同名のクラスは用意されているのですが、そのコンストラクタの定義を見てみると new Task(delegate: javafx.concurrent.Task[T]) new Service(delegate: javafx.concurrent.Service[T]) と...

SBTで外部のプライベートGitリポジトリを参照する

SBTには、Mavenリポジトリに登録されていないようなプロジェクトも依存関係に追加することができるという便利機能があります。使い方は以下の通り lazy val root = (project in file(".")). settings( // ... ).dependsOn(uri("git://some-git-repository.com...

独自パターンマッチを定義する。

Scalaでは、unapply, unapplySeqメソッドを定義することによって、任意の型に対して独自で後付けのパターンマッチを定義することができます。 unapply 何らかの値Oに対して、O.unapply(x)はパターンマッチに成功したら Some( (x1, x2, x3, ..., xN) ) を返し、x match { case O(x1, x2, ..., ...

定数(に見えるもの)の定義いろいろ

Scalaでは、例えばInt型の値xを定義するのにも次のような複数の方法があります scala> val x: Int = 3 scala> lazy val x: Int = 3 scala> def x: Int = 3 今回はこれらの違いについてメモしておきます。 valでの定義 これが一番一般的な定義の方法です。 val x: Int = 3 という...

Null, Nothing, Any

Any Scalaでは全てのクラスはAnyのサブクラスとなります。そのため、任意のAny型の変数には任意の型の値を代入することができます。 Anyのサブクラスとして、任意のプリミティブな値を表す型であるAnyValと、任意の参照型を表すAnyRefの2種類が存在します。 Null Nullは全ての参照型のサブクラスであり、単一の値nullのみを持ちます。...

ScalaFXでデフォルトのCSSが見当たらない

ScalaFXの練習として、とりあえず公式にあるサンプルを写経していた所、次のような現象に遭遇しました。問題になったコードは以下の通り。ほぼ下記のサイトのコードそのままです。 http://www.scalafx.org/docs/faq_TableView_with_Custom_cell/ import scalafx.application.JFXApp import scalafx.a...

Scalaのtrait

traitとは 具体的な実装を持たないようなクラスをScalaではtraitと呼びます。Javaでいうinterfaceのようなもの。 abstract classとの使い分けは、abstract classが「それが何であるか」を指定するのに対し、traitでは「それがどういった振る舞いをするか」を記述するためにあると思っています。 基本的な使い方 J...

ScalaFXを触ってみる

ScalaFXについてのまとまったドキュメントが見当らないので(JavaFXのドキュメント見ろってことなのかな?)、ScalaFXに触っていく過程で分かったことを少しずつ書いていこうと思います。 とりあえずHello World まずはとりあえず「Hello, World!」と書かれたウィンドウを表示するプログラムです。 ソースはほぼ公式のサンプルのコピペ import sc...

VagrantでWordPress環境を手軽に構築

Vagrantというものを使うと、設定ファイルに記述された構成の仮想マシンを簡単に構築することができます。これを使うことで、例えば本番環境と同様の構成のテスト環境を用意したり、ということが簡単にできるようになります。 VirtualBox, Vagrantのインストール VagrantはVirtualBoxを使って動いているようなので、とりあえず以下のサイトからVirtual...

Googleの各種APIの取得から利用まで

まずは以下のリンクからGoogle Developers Consoleにログインします。Google Cloud Platform APIキーの取得などは、サイドメニューの「API Manager」から行います。初めて利用する場合、サイドメニューのAPI Managerをクリックすると「プロジェクトを作成する」に飛ばされるので、プロジェクト名などを適当に決めた後利用規約に同意してプロジェクトを...

Parse error: parse error, expecting `','' or `';''

先ほど友人が引っかかってたエラーです。 エラーの内容自体は大したことないものですが、恐ろしくググラビリティが低そうなのでこちらに纏めておきます。起きたエラーは以下の通り: class MyClass { private $hoge = 'abc' . 'def'; ... } 実行しようとすると、 Parse error: parse error, expecting `','...

JavaにOptionalは必要だったのか

大学の授業で初めてJavaに触れて思ったことです。 Javaに関しては全くの初心者なので、見当違いのことを言ってたらごめんなさい。 Functional Interface Java 8以降にはFunctional Interface(訳語は関数型インターフェース、かと思いきやコンパイラ内のメッセージでは機能インターフェースとか呼ばれていたりするのでよく分からない)という機能...

PHPの文字列が無駄にお節介を焼きすぎて怖いという話

最近必要に迫られてPHPを触りはじめました。ゆくゆくはWordPressプラグインとか作れるようになりたいですね。本題。 1 if ("1" == 1) { echo "ほげ" . PHP_EOL; } else { echo "ふが" . PHP_EOL; } 実行すると、「ほげ」と出力されます。ま...

SBTのインストールから、簡単なプロジェクトができるまで

バイトとかでScalaに触ったことはあるけど、そういえば自分で1からプロジェクト作ったことは無かったなぁと思ったので。 インストール 各々の環境に合わせて。僕はMacなんでbrew使いました。 $ brew install sbt とりあえず実行 $ sbt console と打てばとりあえず対話型実行環境を作ってくれますが、実行するとカレントディレ...

pyenvで入れたpythonでwxPythonが動かない

wxPythonで作ったGUIアプリを動かしてみようとした所、次のようなエラーが。 This program needs access to the screen. Please run with a Framework build of python, and only when you are logged in 原因は--enable-frameworkオプションをつけずにPythonが...

Bing Search APIで遊ぶ

諸事情で検索機能が必要になったので、検索系のAPIの中で一番手軽に扱えそうな(とは言ってもそれほど差はありませんが)Bing Search APIを使ってみました。 APIキーの取得 まずは以下のサイトにアクセスします。 http://datamarket.azure.com/dataset/bing/search 5000トランザクション/月までなり無料で利用できるので、適...

Pyenvとvirtualenvで環境の管理

『エキスパートPythonプログラミング』でPythonに対する知識がほぼ止まっていたのですが、どうやら最近は(かなり前から?) 「pyenv」なる便利コマンドで簡単にバージョンの切り替えを行うことができるようです。 インストール $ brew install pyenv pyenv-virtualenv コマンドは環境に応じて適宜読み替えてください。 インストール完了後に...

Twitterのふぁぼマークを寿司にする

Twitterのふぁぼマークがハートになってしまったので、昔ながらの寿司アイコンに戻す方法を書いておきます。(Google Chromeのみ) 1. Stylebotをインストール StylebotというChromeの拡張機能をインストールします。 https://chrome.google.com/webstore/detail/stylebot/oiaejidbmkiecgbjeifoej...
にマッチする記事はありません。