読者です 読者をやめる 読者になる 読者になる

さんぽみち

なにか思いついたときとかに気まぐれに更新されます。

Haskellの勉強 その2 : genN, genPhiN

はじめに

 先日までとブログの編集方法を変えて Markdown という書き方に変えました。
 Markdown では直接 HTML を埋め込むことができるので楽です!
 しかしその弊害として、文字に色を付けるのが少し面倒になりました。。。
 前の記事が過剰に色づけしてる感はあったので、これからはほんとに強調したい箇所のみに色を付けることにします。

 それでは今日こそ HaskellRSA暗号を実装していきます。
 処理の簡単な関数を扱って、Haskell の基本的な文法を押さえていきます。

書き方

 実装していくに当たり、Haskell と僕の大好きな C# を比較しながら書いていきます。
 しかし、違う言語間である(しかも設計思想も全然違う!)ため、記法やものの呼び方が違います。  そこで、比較をしやすくするためにこれをどう呼んでどう書くかを示しておきます。

関数

 C# は純オブジェクト指向言語であり、関数という概念がありません。
 そこで Haskell と合わせるために以下の条件を満たす C# の静的メソッドを関数と呼ぶことにします。
  ・メソッド呼び出し時の引数が同じであれば必ず同じ戻り値を返す。
 また、この条件のことを "参照透過性"*1 といいます。

変数

 Haskell では変数へ一度値を代入すると、再代入することができません。
 C# の readonly なイメージですね。
 このため、変数*2へ値を代入することを "束縛する" といいます。
 これは HaskellC# で使い分けることとします。

命名規則

 Haskell での関数及び束縛数の命名は、シンボルの先頭が小文字でなければならないため、Camel 記法*3 または Snake 記法*4しか許されません。
 C# では関数名は Pascal 記法*5、変数名は Camel 記法が推奨されます。
 他にもそれぞれの言語で命名規則が違うことや、そもそも片方の言語にしか存在しない概念への命名などがあります。
 これらについては、それぞれの言語で推奨・強制させられる記法で命名していきます。
 見出しで関数名などを使う場合は、Haskell の記法に合わせることにします。

実装内容

 本エントリでは、鍵生成の
  ・ 法となる整数 n の計算 : genN
  ・ φ(n) の計算 : genPhiN
を実装します。
 また、処理内容が簡単なので Haskell の基本的な構文をメインに書きたいと思います。

実装

genN

Haskell

  ---------------
  --  n = p * q
  ---------------
  genN :: (Integer, Integer) -> Integer
  genN primes = p * q
    where
      (p, q) = primes

C#

  ///<summary>法を生成する</summary>
  ///<param name="primes">二つの素数</param>
  ///<returns></returns>
  public static long GenN(long[] primes)
  {
    long p = primes[0];
    long q = primes[1];
    return p * q;
  }

 Haskell を見ると、

  genN :: (Integer, Integer) -> Integer

という謎の記述があります。
 これは C言語でいうプロトタイプ宣言のようなもので、引数と戻り値の型を明示しています。*6
 読み方は、

genN 関数は (Integer, Integer) から Integer を作る

あたりでいいと思います。
 (Integer, Integer) は Tuple(タプル)といい、複数の値をセットにして扱いたい場合に使う型です。
 要素数は任意で型も好きな型をセットにできますが、必ず固定長でなければなりません。
 これを頭に入れて読んでみると、
\begin{align*} f:{T}→{S} \end{align*} などの記法と似ていて直観的ですね!

 次に具体的な実装を。

  genN primes = p * q

 Hakell の関数は、変数へ式を束縛するといった考え方であるため、左辺に関数名(変数名)と引数を半角スペースで区切って、右辺に計算の定義を書きます。
 この時、他言語でよくある引数を囲む丸括弧はありません。
 つまりこの式は、

genN 関数は、primes を受け取って p と q を乗じた結果を返す。

と読めます。
 この p と q とは何者でしょうか?

 この続きを見てみると、

      where  
        (p, q) = primes  

と、p, q に関する定義っぽいがあります。
 この where 句は、関数内でのみ使える変数や関数を定義できます。
 関数内のみから見えるブロックであるというイメージで多分大体あっています。

 その下では、タプルをばらして束縛することで中身を取り出してます。
 こうすることで、p と q を別々の変数として扱うことができるようになります。

 つなげて読んでみると、

関数 genN は、primes を受け取って p と q を乗じた結果を返す。
ただし、p は primes の先頭要素、 q は primes の第二要素である。

あたりが語順及び意味的にしっくりくると思います。

 一応 C# との比較もしてみます。

 C# では、"{}" を使って関数用のブロックを準備していますね。
 言葉にすると、

p へ primes[0] を代入する。次に q へ primes[1] を代入する。  
返すのは、 p と q を乗じた結果である。

となり、手続的な定義方法であることがわかります。

genPhiN

Haskell

  -------------------------------------------
  --    φ(n) = lcm(p - 1, q - 1)
  -------------------------------------------
  genPhiN :: (Integer, Integer) -> Integer
  genPhiN (p, q) = lcm (p - 1) (q - 1)

C#

  ///<summary>φ(n)を生成する</summary>
  ///<param name="p">素数</param>
  ///<param name="q">pと異なる素数</param>
  ///<returns>φ(n)</returns>
  public static long GenPhiN(long p, long q)
  {
    long gcd = Multiplication.GcdEx(p - 1, q - 1)[0];
    return (p - 1) * (q - 1) / gcd;
  }

 さっきは説明のために回りくどい書き方をしましたが、今度は素直な実装です。
 まずは Haskell から見ます。
 これ以降は、注目するべきことがない場合は関数宣言について触れません。

  genPhiN (p, q) = lcm (p - 1) (q - 1)

 lcm 関数を呼び出していますが、この関数は整数型を二つ渡すとその最小公倍数を求めて返してくれます。
 標準で準備されていたのでこれをそのまま使い、結果を返すだけですね。

 さっきと違うのはタプルの受け取り方。
 タプルはわざわざ where 句の中で展開する必要はなく、展開した状態で扱いたいのであればこのような書き方が楽です。

 次に C# を見てみます。

    long gcd = Multiplication.GcdEx(p - 1, q - 1)[0];
    return (p - 1) * (q - 1) / gcd;

 こちらは、標準では最小公倍数を求める関数が準備されていないため、自分で実装しています。
 ここで呼び出されている GcdEx 関数は後で作る関数で、今は最大公約数を得る関数だと思ってください。
 ここで最小公倍数 lcm(n, m) は、最大公約数 gcd(n, m) を用いて

\begin{align*} lcm(n, m)=\frac{nm}{gcd(n, m)} \end{align*}

と表すことができましたね!
 これと同じことを行っているだけです。
 ただ、これはライブラリに準備されていなかった*7だけの話であり、想定している言語の使用用途が違うだけであり、考え方の違いとは言えないですね。。。

考察

 genPhiN 関数からは面白い差は見当たりませんでしたが、genN 関数では言語間での思想の違いを見つけることができたと思います。

 Haskell では、
  どんな値が返ってくるのか
に着目して定義する対し、C# では、
  どうやって値が返ってくるのか
に着目していると考えられます。

 ここで、後からソースを読み返す時を考えてみてください。
 Haskell の場合は、どんな値が返ってくるかを先に教えてもらい*8、付随する情報を必要に応じて階層的に読んでいくといった手順で関数を読むことができます。
 C# の場合は、先頭から最後まで読まなければその戻り値が何を意味するかが分かりません。
 だから、HaskellC# に対して、関数単位では可読性が高い言語であるといえるかなぁと思います。

 ただし、C# の手続的な定義方法を否定しているわけではなくて、そもそも Haskell には参照透過性という重たい制約があります。
 これのおかげで、関数内は値を加工する以外の処理はないという前提のもとにソースを読むことができるだけです。
 これに対し C# では、インスタンスのフィールドやメソッドにアクセスする可能性があります*9
 そのため、着目しなければならない対象が戻り値だけでないので手続を全て把握しなければなりません。
 そういった前提で作られているため、C# では処理を順番に定義していく方法が合っているんだと感じました。

おわりに

 今回のエントリを書いていて、文法は言語の思想を顕著に表すものなのだと改めて実感できました。
 また、新しい言語に触れるという行為は、自分が使うすべての言語に対して理解が深まるとこちらも再確認できました。
 みなさんも、怖がらず積極的に新しい言語に触れてみてください。
 プログラミング言語は怖くないです、友達です!!

参考

7shi様(2015) Haskell 超入門 - Qiita

 学習の際にちょこちょこお世話になってます。
 基本的なことが丁寧にまとめられており、例も多くてわかりやすいです。

rikunora様(2012) RSAのひ・み・つ - 小人さんの妄想

 RSA暗号について記述されていますが、特にオイラーの定理についてで参考とさせて頂きました。
 φ(n)が最小公倍数でいい理由が納得できました。

あくあのーと様(2014) はてなブログで高速に記事を書けるMarkdown記法チートシート - No Hack No Life

 Markdown について参考にさせて頂きました。
 HTML との対応も書かれており、CSSを適用したいときにどのタグを使うと行けそうか判断しやすかったです。
 ちなみに前まではこれの 見たままモード を使っていました。

xxxx7様(2015) Easy Copy MathJax

 LaTeX での記述方法について参考にさせていただきました。
 綺麗にまとめられており見やすいです。

*1:言い換えると、関数は状態を持たないとも言える。

*2:変わらないから変数っていうのはおかしいと感じるかもしれない。
 だが、評価されるまで値が定まらない数であるため変数と呼ばせてもらう。

*3:先頭の単語を小文字にしてそれ以降の単語は大文字とする記法。 (ex) fooBar

*4:全ての単語は小文字で、単語間を '_' (アンダースコア)で区切る記法。 (ex) foo_bar

*5:先頭の単語から大文字で、それ以降も大文字とする記法。 (ex) FooBar

*6:Haskell では引数と戻り値の型が自明である場合は型推論されるため、基本的にこの宣言は不要である。
 だが、学習中は型を意識したいためなるべく明示する。

*7:.Net 4.0から多倍長整数型である System.Numeric.BigInteger 構造体が実装された。
 この中には、GreatestCommonDivisor メソッドが定義されている。

*8:関数定義の手前で定義する let 句も存在する。
 しかし、こちらを用いても定義と関数が行う計算を区別していることに変わりはない。

*9:というか、アクセスしないならクラスメソッドにして欲しい。