osiire’s blog

ふしぎなそふとやさん

函数プログラミングの集い 2011 in Tokyo

というタイトルの集まりが9月17日にありますので、皆様お誘いあわせの上ぜひお越しください。

函数プログラミングの集い 2011 in Tokyo

先日のこの集まりの打ち合わせの時に@ksknac氏がちらっとおっしゃっていたのが「関数型言語じゃなくて関数プログラミング」（超意訳です。しかも酔っていたので正しくないかも。）
確かに色々な機能を持つ言語を分類しても詮無い事ですし、C言語でオブジェクト指向的な事もできないわけではない訳で、特定のプログラミング手法というかスタイルがあって、それらと言語機能がかかわりあって存在しているという感じだと思えば、より正確で前向きな議論ができそうです。当然と言えば当然の話ですが、今後はこういう言い方を気をつけてしていこうかと思っている次第。

で、その関数プログラミングの手法とかスタイルとかって何なのか。もちろん定義がある訳ではないので、@kazu_yamamoto氏がよく言う"あなたの関数型の定義って何ですか"問題になります。ただ、せっかくなのでオレオレ定義についてここで晒しておきます。

  • まず一つは、関数を組み合わせることで大きな処理を作っていく方針。関数を組み合わせる一つの手法として合成や高階やモナドがあって、レキシカルスコープかつ副作用はなるべくない方が組み合わせやすい。オブジェクト指向だって個々のオブジェクトを「組み合わせて」全体の動きを作り上げますが、オブジェクトがアイデンティティを持って変化していくことが想定されている組み方とは違って、むしろアイデンティティを無くして入出力のみで組み合わせる。一言でいうとλ計算・・・と言いたいところなのだけど多値のSchemeもあるので保留。
  • もう一つは、代数的データ型を入れてパターンマッチする方針。和と積と再帰によってインバリアントのないデータ構造を構築し、パターンマッチによって分解する。オブジェクト指向的には抽象データ型が推奨な感じでしたが、むしろ場合分けもガンガン使う。

その他にもリストを多用する文化も特徴なのですが、でも後出しじゃんけん的に考えると、リストが便利というのは先の二つの手法からの当然の帰結のように思えなくもないです。C言語で配列が便利だったのはアドレスを持ったメモリを想定していたから。その因果関係と似た感じ。

ちなみに、8月に開催する現場で活かす関数型プログラミング(F#編)でもこういった考え方に沿って具体例と一緒に解説する流れです。

この夏はICFPもあるし、関数プログラミングを広く知ってもらえる夏になると幸いです。

レイジーリスト

OCamlでもレイジーリストは便利ですねー。参考のために、某案件で使うために書いたレイジーリストの実装を書いておきます。バグがあったら某案件のプログラムもバグっていると言うことなので、痛いです。ぜひご報告をお願いします。tail-recursiveとかも一応考えたはず。メモリ効率やスピードは計ってないです。ごめんなさい。

本格的に使いたい人はOCaml Batteries Includedを入れると便利関数が多くて幸せになれますよ！
http://thelema.github.com/batteries-included/hdoc/BatLazyList.html

(**
  lazy list
 
  @author IT Planning Inc.
  @version $Id$
*)

(*   
   Copyright (c) 2007 IT Planning inc. All Rights Reserved.
 
   Permission is hereby granted, free of charge, to any person obtaining
   a copy of this software and associated documentation files (the
   "Software"), to deal in the Software without restriction, including
   without limitation the rights to use, copy, modify, merge, publish,
   distribute, sublicense, and/or sell copies of the Software, and to
   permit persons to whom the Software is furnished to do so, subject to
   the following conditions:
   
   The above copyright notice and this permission notice shall be
   included in all copies or substantial portions of the Software.
   
   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
   IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
   CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
   TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
   SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*)

let (!$) x = Lazy.force x

type 'a seq = Nil | Cons of 'a * 'a t
and 'a t = 'a seq Lazy.t

let empty = lazy Nil

let zero = lazy Nil

let return x = lazy (Cons(x, lazy Nil))

let rec map f l = 
  lazy begin
    match !$l with
      | Nil -> Nil
      | Cons (x, xs) -> Cons (f x, map f xs)
  end

(* Be careful! All elements will be evaluated. *)
let rec foldl f v l = 
  match !$l with
      Nil -> v
    | Cons(x, xs) -> foldl f (f v x) xs
        
(* Be careful! All elements will be evaluated. not tail-recursive. *)
let rec foldr f v l = 
    match !$l with
        Nil -> v
      | Cons(x, xs) -> f x (foldr f v xs)

let rec (++) s1 s2 = 
  match !$s1 with
      Nil -> s2
    | Cons (hd, tl) -> lazy (Cons (hd, tl ++ s2))

(* 早速 concatがtail-recursiveじゃなかったバグが見つかったので修正 *)
let rec concat l = 
  lazy begin
    match !$l with
      Nil -> Nil
    | Cons(x, xs) ->
        !$(x ++ (concat xs))
  end

let bind s f = concat (map f s)

let rec filter f l = 
  lazy begin 
    match !$l with
        Nil -> Nil
      | Cons(x, xs) ->
          if f x then 
            Cons(x, filter f xs)
          else
            !$(filter f xs)
  end

let rec filter_map f l = 
  lazy begin 
    match !$l with
        Nil -> Nil
      | Cons(x, xs) ->
          match f x with
              Some v -> Cons(v, filter_map f xs)
            | None -> !$(filter_map f xs)
  end

let guard c = if c then return () else zero

(* Be careful! All elements will be evaluated. *)
let reverse s =
  let rec rev acc l = 
    match !$l with
        Nil -> acc
      | Cons (hd, tl) -> rev (Cons (hd, lazy acc)) tl
  in
  lazy (rev Nil s)

let rec take n l =
  lazy begin
    match n, !$l with
      | 0, _ -> Nil
      | n, Nil -> Nil
      | n, Cons (x, xs) -> 
          Cons(x, take (n-1) xs)
  end

let rec of_list = function
    [] -> empty
  | hd :: tl -> lazy (Cons (hd, of_list tl))

let rec unfold f x =
  lazy begin
    match f x with
        Some (a, b) -> 
          Cons (a, unfold f b)
      | None -> Nil
  end

let rec take_while f l = 
  lazy begin
    match !$l with
        Nil -> Nil
      | Cons(x, xs) ->
          if f x then 
            Cons(x, take_while f xs)
          else
            Nil
  end

let rec drop_while f l =
  lazy begin
    match !$l with
        Nil -> Nil
      | Cons(x, xs) as l -> 
          if f x then 
            !$(drop_while f xs)
          else 
            l
  end

let rec zip x y =
  lazy begin
    match !$x with
        Nil -> Nil
      | Cons(x, xs) ->
          match !$y with
              Nil -> Nil
            | Cons(y, ys) ->
                Cons((x,y), zip xs ys)
  end

let hd = function | lazy Nil -> failwith "hd" | lazy (Cons (x, xs)) -> x
let tl = function | lazy Nil -> failwith "tl" | lazy (Cons (x, xs)) -> xs
let cons x xs = lazy (Cons(x, xs))

(* Be careful! All elements will be evaluated. *)
let rec iter f l =
  match !$l with
      Nil -> ()
    | Cons(x, xs) -> 
        f x;
        iter f xs

ひとりごと

@keigoi氏がうちの会社にいてくれているおかげで、ビジネスについても考える機会が多くなった。そこで自分の中の二つの矛盾する希望に気づいた。

  • 私はコンピューターの技術的な面に興味が強く、その応用そのものやビジネスのやり方には正直あまり興味がない。むしろ世界人類が今後どのような技術を必要としていて、その発展に私が何らかの形で寄与でき、その成果を身の回りに還元できるなら望外の喜びだと思っている。具体的には、今後100年、コンピューターシステムが社会インフラとして存在感を増すと思われる中で、各所でひどいシステムを沢山見てきた私としては、システム作りが少しでもまともになって欲しい、そのための一つの方向性として、今はソフトウェアを数学的な抽象と結びつけることが必須だと思っているし、そのために静的型付け関数型言語が良いと思っているし、より具体的にGUIプログラミングをもっと良くしたいと思っている。私に出来ることなどないのかもしれないけど、だからといって別に諦めるつもりはない。ライフワークという奴に近い。
  • 一方で、私はともかく、一緒に働いている仲間には、表舞台で活躍して、その結果としてより余裕のある生活を送ってもらえるようになってもらいたいと希望している。もちろん表舞台を希望しない人もいるかもしれないから、そこは自由だけど、どちらにしても、もっとよい給料と環境を用意してあげたい。

この二つの希望は、たぶんベクトルが60度以上は違う。ベクトルの違う事を同時にやると、その和の絶対値は短くなる。

この不都合を明確に文章として意識はしていなかったけど、無意識に問題視していて、ベクトルの違いを少しでも小さくするために、より良いシステム開発をして納品する/良くなると思う技術を宣伝する事で利益をあげる事業に取り組んできたのだと思う。我ながら何の工夫もない戦略ではある。

今後うちの会社がどのようなビジネスを目指すのか、どういう活動をしていくのか、よく相談して（3人しかいないので）全員が力を発揮できる形を作っていく必要がある。

追記：気づいたとか意識したというより、普通に知ってたんだけど、特に向き合おうとしなかったという方が正しいか。

Concurrent MLのイベントをモナドにするだけでこんなに便利。

非同期な通信もまとめて扱える。F#の非同期ライブラリっぽい。すごい。

module E = Ccell.Event

let async_http_get host =
  E.future http_get host

let counter =
  let open E in
  perform
    r <-- async_http_get "www.itpl.co.jp";
    urls <-- return (grep_url r);
    rs <-- sequence (List.map async_http_get urls);
    return (List.fold_left count_lines 0 rs)

let _ =
  print_int (E.sync counter);
  flush stdout

名古屋近辺で型推論本が欲しい！という方は私に連絡下さい

名古屋近辺でコミケ行けなかったけど、@pi8027氏と@mayahjp氏執筆の型推論本（ラムダプラス+)は欲しかった！という方は私に連絡（twitter(DM含む)、メール、コメントなど）下さい。@pi8027氏のご厚意で、まとめて発注出せる段取りになりました。1月4日23時59分まで受け付けたいと思います。