Hatena::ブログ(Diary)

エンジニアのソフトウェア的愛情 このページをアンテナに追加 RSSフィード Twitter

2014-11-30

型システム入門

本書の中の「第3章 型無し算術式」を「第4章 算術式のML実装」ではOCamlで実装しているのですが…



Ruby

パタンマッチングをするのに pattern-match という gem を利用しています。


実装。

require 'pattern-match'

=begin
| 構文での定義          | コード内での表現  |
|-----------------------|-------------------|
| true                  | :True             |
| false                 | :False            |
| if t1 then t2 else t3 | [:If, t1, t2, t3] |
| 0                     | :Zero             |
| succ t                | [:Succ, t]        |
| pred t                | [:Pred, t]        |
| iszero t              | [:IsZero, t]      |

`Kernel.#eval` が既に存在するので、`evaluate1`, `evaluate` にしています。
=end

def isnumericval(t)
  match(t) do
    with(:Zero) { true }
    with(_[:Succ, t1]) { isnumericval(t1) } 
    with(_) { false }
  end
end

def evaluate1(t)
  match(t) do
    with(_[:If, :TRUE, t2, t3]) { t2 }
    with(_[:If, :False, t2, t3]) { t3 }
    with(_[:If, t1, t2, t3]) { [:If, evaluate1(t1), t2, t3] }
    with(_[:Succ, t1]) { [:Succ, evaluate1(t1)] }
    with(_[:Pred, :Zero]) { :Zero }
    with(_[:Pred, _[:Succ, nv1]], guard { isnumericval(nv1) }) { nv1 }
    with(_[:Pred, t1]) { [:Pred, evaluate1(t1)] }
    with(_[:IsZero, :Zero]) { :TRUE }
    with(_[:IsZero, _[:Succ, nv1]],  guard { isnumericval(nv1) }) { :False }
    with(_[:IsZero, t1]) { [:IsZero, evaluate1(t1)] }
  end
end

def evaluate(t)
  begin
    evaluate(evaluate1(t))
  rescue PatternMatch::NoMatchingPatternError
    t
  end
end

こんな感じ。

p evaluate1([:If, :TRUE, [:If, :False, :False, :False], :TRUE]) # => [:If, :False, :False, :False]
p evaluate([:If, :TRUE, [:If, :False, :False, :False], :TRUE]) # => :False
p evaluate([:Pred, [:Succ, [:Succ, :Zero]]])

それ、( ) を [ ] に置き換えただけの Lisp じゃないの? とか言われそうでそうが…言われそう…。



C++ Templateで

パタンマッチングといえば、お約束の C++ Template プログラミングです。今回もやりました。

struct True {};
struct False {};
struct Zero {};

template<typename T1, typename T2, typename T3> struct If { typedef If<T1, T2, T3> type; };
template<typename T> struct Succ { typedef Succ<T> type; };
template<typename T> struct Prev { typedef Prev<T> type; };
template<typename T> struct IsZero { typedef IsZero<T> type; };

template<bool C, typename T, typename U> struct If_;
template<typename T, typename U> struct If_<true, T, U> { typedef T type; };
template<typename T, typename U> struct If_<false, T, U> { typedef U type; };

template<typename T> struct IsNumericVal { static const bool condition = false; };
template<> struct IsNumericVal<Zero> { static const bool condition = true; };
template<typename T> struct IsNumericVal<Succ<T>> { static const bool condition = IsNumericVal<T>::condition; };

template<typename T> struct IsVal { static const bool condition = IsNumericVal<T>::condition; };
template<> struct IsVal<True> { static const bool condition = true; };
template<> struct IsVal<False> { static const bool condition = true; };

template<typename T> struct Eval1 { typedef T type; };
template<typename T2, typename T3> struct Eval1<If<True, T2, T3>> { typedef T2 type; };
template<typename T2, typename T3> struct Eval1<If<False, T2, T3>> { typedef T3 type; };
template<typename T> struct Eval1<Succ<T>> { typedef typename Succ<typename Eval1<T>::type>::type type; };
template<> struct Eval1<Prev<Zero>> { typedef Zero type; };
template<typename T> struct Eval1<Prev<Succ<T>>> { typedef typename If_<IsNumericVal<T>::condition, T, Prev<Succ<T>>>::type type; };
template<typename T> struct Eval1<Prev<T>> { typedef typename Prev<typename Eval1<T>::type>::type type; };
template<> struct Eval1<IsZero<Zero>> { typedef True type; };
template<typename T> struct Eval1<IsZero<Succ<T>>> { typedef typename If_<IsNumericVal<T>::condition, True, False>::type type; };

template<typename T> struct Eval { typedef typename Eval<typename Eval1<T>::type>::type type; };

ここで次の式を評価コンパイル)すると…

typedef typename Eval<If<True, If<False, False, False>, True>>::type t6;

これ以上評価のできないところまで評価が進みFalseが得られます。

error: no type named 'type' in 'Eval<False>'

ちゃんと「False評価は存在しません」と表示されています(爆)。




…。

ごめんなさいごめんなさい。今回はここで力尽きました。

2014-10-26

remoute: true で post する

Railsremote: true を指定した任意のリンクでPOSTしたい時の話。

必要に迫られて探した結果、こんな感じになりました。


POSTしたとき、data-paramsの値がパラメータとして送られるようです。

そしてdata-paramsは、CoffeeScript を使い .data('params', 送りたいデータ)で設定できる模様。


これらを踏まえて。


Gemfile
# 追加
gem 'haml-rails'
gem 'redcarpet'

config/routes.rb
  # 追加
  get 'markdown/index'
  post 'markdown/markup'

app/controllers/markdown_controller.rb
class MarkdownController < ApplicationController
  def markup
    source = ActiveSupport::JSON.decode(params[:source])
    render json: {html: Redcarpet::Markdown.new(Redcarpet::Render::HTML).render(source)}
  end
end

app/views/markdown/index.html.haml
#markdown
  %p= text_area_tag :source, '', cols: 100, rows: 10
  %p= link_to 'markdown to html', markdown_markup_path, remote: true, method: :post, id: 'convert'
  %p= text_area_tag :target, '', cols: 100, rows: 10

app/assets/javascripts/markdown.js.coffee
$(document).on 'ready page:load', ->
  $('#convert').click ->
    $(this).data('params', {'source': JSON.stringify($('#source').val())})

$(document).on 'ajax:success', '#markdown', (xhr, data, status) ->
  $('#target').val(data['html'])

こんな感じ

/markdown/index にアクセスして表示されたフォームの上の欄にMarkdownで記述し、リンクをクリックするとしたの欄にHTMLの内容が表示されます。


f:id:E_Mattsan:20141026122410p:image

2014-09-28

型システムの学習に手を出します

今月は、3年ぶりになるXP祭りに参加してきました。さらに初めてとなるRubyKaigiに参加してきました。

外の、「ちょっとした身内の集まり」の規模を超えたイベントに参加したのは、2年ぶりぐらいになります。

このところ、体力低下、気力低下、意識低下、等々に悩まされていましたが、久々にイベントに参加して気がついたのは「栄養不足」でした。栄養が不足していたら、そりゃぁいろいろ低下するよね、という感想。

ただし、ストレスで食べる量が増えたせいで4kg体重が増えました。腸疾患を抱えている身としては、食べて太れるというのは実はありがたいこと。でも+4kgの体重というのは、体力のない身には厳しい。というわけで、増えたときの倍の時間はかかりましたが-3kg(元の体重から+1kg)まで到達しました。もう少し落とした方が身体の取り回しは楽そうです。


閑話休題

イベントの話は、またいずれかの機会に語りたいのですが、今回はそっちの話ではなくて。


型システム入門 プログラミング言語と型の理論

会社の同僚に「読書会やろう!」とそそのかされて、購入してきました。

数ページを斜め読みしただけですが、わくわくしてきます。こういう話題を社内でできるがうれしい。

問題はどこまで理解できるか見当もつかないところ。


アンダースタンディングコンピュテーション

時を同じくしてジュンク堂RubyKaigi店で購入したのがこちら。

流れが来ています。


しっかり笹田さんのサインも頂いてきました。

f:id:E_Mattsan:20140928205040j:image:w360


数理言語学事典

もう一つジュンク堂RubyKaigi店で購入した、事典。

考えてみると、ターゲットはどのあたりなのか、なかなか難しい書籍です。

まるで、あちこちをつまみ食いして半端な知識のわたしのために用意されたようにも思える一冊。

数理言語学事典

数理言語学事典



9月は再起動の月。

2014-08-09

いかにして表計算の列名をつくるか・特別篇

Haskellでたわむれていると。 id:nobsun さんが実に軽快な解法をコメントに残してくださいました。

colns = concat cns where cns'@(_:cns) = [""] : [[c:ns | c <- ['A'..'Z'], ns <- nss] | nss <- cns' ]

Qiita では、さらにエレガントな解を展開されていますので、ぜひそのシンプルなコードを見てみてください。


[Char] と [String] から [String]

A〜Zの並びをかけ合わせるためにわたしが取った方法は、文字列のリストのリストに sequence適用するというものでした。

Prelude> sequence [ [ "A", "B", "C" ], [ "A", "B", "C" ] ]
[["A","A"],["A","B"],["A","C"],["B","A"],["B","B"],["B","C"],["C","A"],["C","B"],["C","C"]]

(A〜Zの文字を使うと結果が大きくなってしまうため、A〜Cの文字で説明しています。以下同様)


ただし、これだと生成されるのは文字列のリストのリストになってしまいます。

そのためリストの各要素(文字列のリスト)を連結してやる必要がありました。

Prelude> map concat $ sequence [ [ "A", "B", "C" ], [ "A", "B", "C" ] ]
["AA","AB","AC","BA","BB","BC","CA","CB","CC"]

この方法をリスト内包表記で書き換えると、おおよそ次のようになります。

Prelude> [ concat [x, y] | x <- [ "A", "B", "C" ], y <- [ "A", "B", "C" ] ]
["AA","AB","AC","BA","BB","BC","CA","CB","CC"]

ここで String の連結のために concat [x, y] としていますが、xChar であれば x:y と書くことができます。

また x に文字を取り出すのであれば x <- [ "A", "B", "C" ]x <- ['A'..'C'] と書けばよいことになります。

Prelude> [ x:y | x <- ['A'..'C'], y <- [ "A", "B", "C" ] ]
["AA","AB","AC","BA","BB","BC","CA","CB","CC"]

自分の内包表記に自分を使う

y の値を取り出しているリスト [ "A", "B", "C" ] は、上の式の [ "A", "B", "C" ][""] に置き換えることで得ることができます。

 [ x:y | x <- ['A'..'C'], y <- [""] ]
["A","B","C"]

これを cns_0 と置くと、

Prelude> let cns_1 = [ x:y | x <- ['A'..'C'], y <- cns_0 ]
Prelude> cns_1
["A","B","C"]

先ほどの式を cns_2 とすると、

Prelude> let cns_2 = [ x:y | x <- ['A'..'C'], y <- cns_1 ]
Prelude> cns_2
["AA","AB","AC","BA","BB","BC","CA","CB","CC"]

となります。

cns_0 = [""] とし、f s = [ x:y | x <- ['A'..'C'], y <- s ] とすれば、

cns_0 = [""]
cns_1 = f cns_0 = ["A","B","C"]
cns_2 = f cns_1 = ["AA","AB","AC","BA","BB","BC","CA","CB","CC"]
...

となり、[ cns_1, cns_2 ] というリストを得たいばあい、f[ cns_0, cns_1 ] の要素を次々に適用して得られる値をリストにすればよいことになります。

Prelude> [ [ x:ns | x <- ['A'..'C'], ns <- nss] | nss <- [ cns_0, cns_1 ] ]
[["A","B","C"],["AA","AB","AC","BA","BB","BC","CA","CB","CC"]]

つまり [ cns_1, cns_2, ... ] というリストを得たいばあい、f[ cns_0, cns_1, ... ] の要素を次々に適用して得られる値をリストにすればよく、これはつまり得たいリストの先頭に cns_0 を付加したリストになります。

Prelude> let cns' = [""]:[ [ x:ns | x <- ['A'..'C'], ns <- nss] | nss <- cns' ]
Prelude> take 4 cns'
[[""],["A","B","C"],["AA","AB","AC","BA","BB","BC","CA","CB","CC"],["AAA","AAB","AAC","ABA","ABB","ABC","ACA","ACB","ACC","BAA","BAB","BAC","BBA","BBB","BBC","BCA","BCB","BCC","CAA","CAB","CAC","CBA","CBB","CBC","CCA","CCB","CCC"]]

このリストの要素を連結し先頭の空文字列を削除すれば、最終的に欲しかった文字列のリストが得られることになります。

Prelude> let colns = tail $ concat cns' where cns' = [""]:[ [ x:ns | x <- ['A'..'C'], ns <- nss] | nss <- cns' ]
Prelude> take 39 colns
["A","B","C","AA","AB","AC","BA","BB","BC","CA","CB","CC","AAA","AAB","AAC","ABA","ABB","ABC","ACA","ACB","ACC","BAA","BAB","BAC","BBA","BBB","BBC","BCA","BCB","BCC","CAA","CAB","CAC","CBA","CBB","CBC","CCA","CCB","CCC"]

いかにして先頭の要素を落とすか

tail 関数を使って。

Prelude> tail [1,2,3]
[2,3]

パタンマッチングを使って。

Prelude> let h:t = [1,2,3]
Prelude> h
1
Prelude> t
[2,3]

パタンマッチングを使って(元の値も使いたいとき)。

Prelude> let a@(h:t) = [1,2,3]
Prelude> h
1
Prelude> t
[2,3]
Prelude> a
[1,2,3]

2014-08-05

いかにして表計算の列名をつくるか・補遺・その補遺

おさらい。


最終形態

先日、Haskellで無限長配列を生成する例を挙げました。

再掲。

import Data.List(group)

column_names_ :: [String] -> [String]
column_names_ ss = ss ++ (map concat $ sequence [column_names_ ss, ss])

column_names :: [String]
column_names = column_names_ $ group ['A'..'Z']
drop 20 $ take 30 column_names
    -- => ["U","V","W","X","Y","Z","AA","AB","AC","AD"]

ほぼ同じ方法でRubyで書いた例も挙げました。

こんな感じ。

([*'A'..'Z'] + [*'A'..'Z'].product([*'A'..'Z']).map(&:join)).first(30).drop(20)
    # => ["U", "V", "W", "X", "Y", "Z", "AA", "AB", "AC", "AD"]


ここで。実は。Rubyのばあい、連結などということをしなくても実現できること、その後に知りました。

こんな感じ。

[*'A'..'ZZ'].first(30).drop(20)
    # => ["U", "V", "W", "X", "Y", "Z", "AA", "AB", "AC", "AD"]

演算子..メソッドsuccが定義されていれば利用できるため、加えて'Z'の次は'AA'と定義されているため、'A'から'ZZ'までを範囲として扱うことができることになるわけです。

ただ[*'A'..'ZZ']という書き方をすると、範囲を配列に変換してしまうので、小さい範囲しか必要でなくても配列全体を生成してしまいます。


これも、配列に変換せず、範囲式のまま扱うことで解決することができるのでした。

こんな感じ。

('A'..'ZZ').first(30).drop(20)
=> ["U", "V", "W", "X", "Y", "Z", "AA", "AB", "AC", "AD"]

おおざっぱな計算をすると、1桁から14桁までの文字列を利用できれば、263を表現するに充分なので、次のようなメソッドを用意すればだいたいにおいて事足りることになります。

# start 番目の文字から length 個の文字を配列として取得する
def column_names(start, length)
  ('A'..'ZZZZZZZZZZZZZZ').first(start + length).drop(start)
end
column_names(0, 10)
    # => ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J"]
column_names(20, 10)
    # => ["U", "V", "W", "X", "Y", "Z", "AA", "AB", "AC", "AD"]


結論

Rubyを使いましょう。



…そんな感じで。