top recent

FP

関連ページ

FP:inRuby プログラミング言語:FPsystem FP:LazyEvaluation FP:素朴な疑問

目次

  1. Functional Programming...
  2. なぜ関数プログラミングは重要か...
  3. 関数プログラミングへの招待...
  4. 関数とは何「への」関数なのか？...
  5. おなじみnishis氏もFPのページを作っていた！...
  6. 参照透明性とは...
  7. 純粋関数型言語でのGUIプログラム...
  8. よく型推論と言われますが...
  9. call-by-name, call-by-needの実装について...
  10. ObjectIO in Haskell...
  11. 関数型、OOP型、手続き型...
  12. 関数型オブジェクト指向...
  13. C言語でCurry化...
  14. ↑そのリンクのmemalignってなんなんでしょう？...
  15. C++におけるラムダ式とカリー化の実現...
  16. dW: プログラミング改善への道: 第4回 関数型プログラミング...
  17. caml for WindowsCE...

Functional Programming

関数プログラミングについてのページ

Frequently Asked Questions for comp.lang.functionalより：

Functional programming is a style of programming that emphasizes the evaluation of expressions, rather than execution of commands. The expressions in these language are formed by using functions to combine basic values. A functional language is a language that supports and encourages programming in a functional style.

[[id:943]] 2002-09-05 10:06:59

なぜ関数プログラミングは重要か

http://www.sampou.org/haskell/article/whyfp.html
『‥‥‥しかしながら、多くの場合、見過ごされる非常に重要なポイントがある。問題を解くための部品プログラムを書くとき、その問題を部分問題に分割し、部分問題を解き、その解を合成する。元の問題を分割する方法は、部分解を張り合せる方法に直接依存する。それゆえに、概念的には問題をモジュール化する能力を高めるためにはそのプログラミング言語のなかで新たな糊の類を用意しなければならない。複雑なスコープ規則や分割コンパイルの規約は事務的な詳細でしかなく、問題を分解する新しい概念的道具をあたえるものではない。

糊の重要性は、大工仕事との類比によって、正しく評価できる。椅子は、部分(座部、脚、背もたれなど)を作り、それらを正しくくっつけ合せることで容易に作ることができる。しかし、これはジョイントと木を張り合せるという能力に依存する。その能力がなければ、椅子を作る方法はひとつ木の塊からそれを彫り出す以外なく、非常に難しい作業になる。この例は、モジュール化の強大な力と正しい糊を持つことの重要性の両方を例示するものである。』

‥‥‥あれ？　既出だっけ？

[[id:897]] 2002-08-07 22:02:03

関数プログラミングへの招待

http://sky.zero.ad.jp/~zaa54437/
「Rubyで関数プログラミング」などあり。dW の「魅惑的なPython」みたいなものか？
----
「Rubyで関数プログラミング」へのコメント
FP:inRuby

[[id:916]] 2002-08-07 22:02:32

関数とは何「への」関数なのか？

Lispは「たまたま」LinkedListを引数に取る関数を書く(書けば済む／書かざるを得ない)言語だ、ということですよね？？
少なくとも、関数プログラミングすなわちList必須、というわけじゃないですよね？
- Common Lispの扱えるデータ構造は、リストのほかにベクタ、構造体、ハッシュテーブル、クラス／オブジェクト、（ついでに関数、整数、実数、分数、文字、文字列、シンボル）…、と多岐に渡ります。
-- 必須では無いが、実用上必要ということではなのでしょうか？

----
まだ勉強し始めたばかりですが、リストは関数プログラミングにおいて重要なデータ構造なんだそうです。
しかしその構造が LinkedList でなければならない、ということはないようです。
説明も抽象的な OrderedCollection とか、可変長のシーケンスとかいう位のもので、セルがどうしたとかポインタで次の要素を指しているとか、そういう実装は特に関係ないようです。
# Perl におけるリストを、その中身がどういう実装になっているかプログラマが意識しないのと同じようなものです。

----
Lsipの特徴といえばS式でしょう。
S式はプログラムというよりデータの塊というイメージが私にはあります。(このお陰か、最近にわかにLisperの間でXMLはS式の車輪の再発見という話題が盛り上がっているようですね。)

S式を一定のルールで書き換える(項書き換え、S式書き換え？)することをプログラムの実行とすることだと思います。誤解されることを気にせずに書けば、項書き換えとはS式というテキスト(文章)を一定の方法でカットし、それと同じ意味を持つ内容のS式をそこにペーストするという感じでしょうか？

[[id:934]] 2002-08-14 00:25:15

おなじみnishis氏もFPのページを作っていた！

http://isweb42.infoseek.co.jp/computer/nishis/learning/fpl/index.html
http://isweb42.infoseek.co.jp/computer/nishis/learning/fpl/stairway.html

‥‥‥って気づくの遅すぎ？

たしかに遅い

[[id:942]] 2002-08-08 23:45:11

参照透明性とは

目的ではなく手段だということがだんだん分かってきた‥‥‥。

目的：高い効率と記述性
手段：遅延評価
条件：参照透明性 == 副作用をなくす or 局所化する

- 参照透明である
-- ⇒ どこから計算してもいいじゃん
--- ⇒ 必要ない式は評価しないで置いとこう
--- ⇒ 枝分かれするところは別スレッドで並列評価しよう
ってなことを処理系がやってくれるということですね。
#SHIMADA

----

参照透明性とは、あるモノの参照先が何時も同じということだと思います。
"関数名+引数"という文字列の参照先は一定、同じ値と考えることも出来るのでは？

参照透明性があると色々おいしい思いが出来ます。
大半が#SHIMADAの書いた内容と重複しているのは勘弁してください。

-外延性(関数の中身を取替えれること？高い効率？)
-遅延実行できる(時も場所も選ばないから)
-副作用が無くなる(その代り、IO関係の記述が出来ない？)
-デバッグが楽

もっと他にも美味しいところが在ると思いますが・・・・

誰か偉い人フォローしてください。お願いします。

[[id:969]] 2002-08-14 00:45:49

純粋関数型言語でのGUIプログラム

http://sky.zero.ad.jp/~zaa54437/programming/clean/CleanBook/part1/Chap5.html
「Concurrent Cleanで関数プログラミング -- 第一部第五章《対話型プログラム》」

‥‥‥むつかすい。頭が破裂しますた。いやまじで。--SHIMADA

- っていうかガードの "|" の代わりに "#" がある部分、どういう意味なのかどこにも書いてないぞ！！（←逆ギレ

-Chap5の中に、さわりは書いてあるようです。しかし私は良く理解できませんでした。
-- >　入れ子通用範囲を使用すると、関数CopyFileは、もう少しエレガントに書くことができる。ファイルシステムの様々な「バージョン」に対して名前を発明する必要は無い。このバージョンは、前の関数と構文的にのみ異なっているに過ぎないということに注意。ファイルシステムの様々なバージョンは依然として存在するが、全てのバージョンは同じ名前を持っている。'#'定義の通用範囲は、どのバージョンが使用されているかを決める。

-「ジョジョの奇妙な言語」かと思いますた。(world) --ばしを
----
サイトマスターから直メールで4.3.5に書いてあると教えてもらいました。Σ(-o-;)

"#" は "let" の別名だそうです。
……逆切れしてすみません。

#SHIMADA

[[id:985]] 2002-08-17 00:56:24

よく型推論と言われますが

知らない人から怪しげな代物と見られる元のような気がして。
今日書店で立ち読みした「プログラミング言語ML」という本では「型演繹」と書かれてあって、こっちのほうがいいのに、と思いました。

# SHIMADA

-私は、型の単一化というほうが判りやすいのでは？と思います。適当な型を与えておき、文脈から適当な型から具体的な型に特定していくというものですから。

[[id:990]] 2002-08-18 23:24:36

call-by-name, call-by-needの実装について

http://www.is.titech.ac.jp/~kando9/kuno_zemi/ModernCompilerImplementation/15_Functional/15_FunctionalProgramingLanguage.html
とても参考になる。

[[id:998]] 2002-08-17 00:43:08

ObjectIO in Haskell

http://haskell.cs.yale.edu/ObjectIO/
Concurrent Clean からの移植だそうな。

ペーパーによると環境渡しスタイルだそうです。
- よく読んだら全然違いました。(;_;) Clean では 一意性型づけシステムに基づく明示的な環境渡しスタイルでGUIオブジェクトの状態遷移を取り扱うが、Haskellではモナドスタイルのmutable variableによって状態遷移を取り扱うことで移植を可能とした。…でした。

[[id:1012]] 2002-08-21 23:18:51

関数型、OOP型、手続き型

#OOP_group といってるけどひょっとして Ruby 特有かも知れない…

この例題ではイテレータを使う解を思い付かなかったんですが、再帰ではすっきり書けるものがイテレータで書けないということもあるのでしょうか。

#!/usr/local/bin/ruby
require "FP.rb"

def FP_group(n, l)
if l.to_a == [] then []
else
FP.cons(FP.take(n, l), FP_group(n, FP.drop(n, l)))
end
end

def OOP_group(n, l)
tmp = []
tmp << l.slice!(0..(n-1)) until l == []
return tmp
end

def PROC_group(n, l)
tmp = []
while l.size > 0
tmp.push(l[0..(n-1)])
l = l[n..-1]
end
return tmp
end

if __FILE__ == 'group.rb'
p FP_group(3, (1..12).to_a)
p OOP_group(3, (1..12).to_a)
p PROC_group(3, (1..12).to_a)
end

結果：
[[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]]
[[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]]
[[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]]

# SHIMADA


- 再帰とイテレータで何を対比してるのかいまひとつ意味不明ですが，再帰と繰り返しってとらえていいなら木のトラバーサルなんか典型的では．
-- 再帰的な構造だから再帰的なアルゴリズムで考えるのは簡単．
-- 繰り返しで処理しようとしても最初からそういう仕掛けがあるのでない限り無理．....無理じゃないか．でも実質自分でスタック管理して再帰を繰り返しに展開するだけなのでめんどうな割に益はない．
- これってお題「カレンダーを作る」 (プログラミング:企画もの:お題１)ででてきますよね。自分はおもいっきり手続き型で書いてました。(^^
- 再帰にするとtmp変数が必要なくなる＆再利用できる関数を＊必然的に＊書く事になる‥‥‥つうことなのかな。#ばしを

[[id:1026]] 2002-08-22 23:40:03

関数型オブジェクト指向

すべてのオブジェクトがimmutableで破壊的操作が存在しない？
-CLOSなんかそういう分類に入るのでしょうか。
-- CLOS はふつうに mutable object が基本のはず．
# SHIMADA

[[id:1027]] 2002-08-22 10:27:14

C言語でCurry化

http://nicosia.is.s.u-tokyo.ac.jp/pub/essay/hagiya/h/curry

（lazy-programming-MLより）

[[id:1067]] 2002-08-28 22:32:21

↑そのリンクのmemalignってなんなんでしょう？

動的に函数もどきを作ってる風に見えますが。
----
↓解説ありがとうございます。
ところで確保したメモリはその後どうなるんでしょう？
あの例だとその後直ぐ終了するので問題になりませんが、
ほっとくとリークするのかな・・・。
上位の関数にclosureを返すのが目的だから、allocaみたいに
スタックに取るわけにもいかないし、curryが返したclosureは
後でfreeする必要有り、ですよね？

機種依存とはいえ、C言語でclosureを使える事は
大きなメリットと感じました。(開放の手間を考えても。)
----
SunOSのmanpageによると
void *memalign(size_t alignment, size_t size);

memalign() allocates ``size'' bytes on a specified ``alignment''
boundary, and returns a pointer to the allocated block. The
value of the returned address is guaranteed to be an even
multiple of alignment. Note: the value of alignment must be
a power of two, and must be greater than or equal to the
size of a word.
だそうです。
メモリブロックを確保してマシンコードを埋め込んでるみたいですね。--SHIMADA

[[id:1128]] 2002-09-04 23:17:51

C++におけるラムダ式とカリー化の実現

http://www.tietew.jp/cppll/archive/2651
http://www.sun-inet.or.jp/~yaneurao/intensive/spt1.html
----
「4.カリー化」のコードは
何度も呼び出せるっていうのは一体…。引数がなければ値を返す、あればクロージャを返すという関数みたいだけど。
これもカリー化っていうの？--SHIMADA

curry_add(1)(2)(4)
みたいなのはそれっぽく見えますが。ちゃんとした定義はどんなだったっけか？--有野

C++のテンプレートって全然分からないんですが、
curry_add(1)(2)() は int を返すけど curry_add(1)(2) は Curry_add を返すような気がしなくもないです。
-うーん、勘違いのような気もしてきた。C++は分からん‥‥‥。
Scheme 版はScheme:手続きのcurry化 に詳しい議論があります。--SHIMADA
-↑から更に http://www.cs.oberlin.edu/classes/dragn/labs/combinators/combinators11.html も。
----
続き。
カリー化の定義、というのじゃないですが、

(curry_add 1) => (lambda (x) (+ 1 x))
((curry_add 1) 2) => ((lambda (x) (+ 1 x)) 2) => 3

となるべきで、1が返るのは変ですよね。（＜ C++の場合）
引数の数が決まっているのが普通じゃないかなー。--SHIMADA

[[id:1094]] 2002-09-04 16:32:20

dW: プログラミング改善への道: 第4回 関数型プログラミング

http://www-6.ibm.com/jp/developerworks/linux/020315/j_l-road4.html
こちらは Perl を使っている。

扱っている内容自体は結局 map と grep は便利ですよ、という以上のものではない感じ。そういう意味では「魅惑的なPython」の方が詳しい。

"Schwartzian変換" というのが必殺技として紹介されているけど、同等のコードが「プログラミング言語Awk」には
awk-oneliner | sort | awk-oneliner2
という組み合わせの一行野郎として紹介されているのであまりインパクトを感じなかったっす。

----
『関数型プログラミング (FP) は、「アプローチ」「ソリューション」「宗教」のいずれにもなる可能性をもっています。単にプログラマーの秘密兵器の1つに過ぎないのですから、私としては「宗教」以外のものであってほしいと願っています。 』
激しく同意。--SHIMADA

うーん、問題解決のみの事を言うならちと私の考えとは違うかなぁ。
私は問題の本質に近づく為のツール的側面もあると考えます。
楽に解決する為だけの物では無く、問題が何かを知る為の手段。
知った結果解決可能でない事もあると思いますし。--有野

そうですね。まだFPの考え方をちゃんと習得したわけではないのですが、問題の解決方法ではなく問題のあり方を考える、という感覚はありますね。
脳ミソの別の箇所を使っている感じ。--SHIMADA

[[id:1103]] 2002-09-02 23:29:22

caml for WindowsCE

というのがあるらしい。
SMLは本があるけど caml はまだよく分からない。

[[id:1186]] 2002-09-15 14:01:37

top recent

HashedWiki version 3 beta
SHIMADA Keiki