関数型言語ML(SML, OCaml, etc.), Part 5

関数型言語ML(SML, OCaml, etc.), Part 5 at TECH

1:デフォルトの名無しさん
07/08/05 14:49:54
関数型言語MLについて語るスレッドです。

MLは、確固とした理論的背景を持つ言語でありながら、
現実的なソフトの開発にも使用できる実用性を備えた言語です。
また、プログラミングの初心者が最初に学習する言語としても優れています。

総本山
Standard ML URLﾘﾝｸ(www.smlnj.org)
Objective Caml URLﾘﾝｸ(caml.inria.fr)

前スレ
関数型言語ML(SML, OCaml, etc.), Part 4
ｽﾚﾘﾝｸ(tech板)

2:デフォルトの名無しさん
07/08/05 14:50:33
■リンク集
URLﾘﾝｸ(lang.x0.com)

■チュートリアル
Standard ML
URLﾘﾝｸ(www-2.cs.cmu.edu)
URLﾘﾝｸ(www.dcs.napier.ac.uk)
URLﾘﾝｸ(www.dcs.ed.ac.uk)
URLﾘﾝｸ(yk.i.hosei.ac.jp)
URLﾘﾝｸ(www.summa.jp)
Objective Caml
URLﾘﾝｸ(www.csc.vill.edu)
URLﾘﾝｸ(www.sato.kuis.kyoto-u.ac.jp)
URLﾘﾝｸ(www.biocaml.org)
URLﾘﾝｸ(www.ocaml.jp)

■過去スレ
関数型言語ML(SML, OCaml, etc.), Part 4
ｽﾚﾘﾝｸ(tech板)
関数型言語ML(SML, OCaml, etc.), Part 3
ｽﾚﾘﾝｸ(tech板)
let t = 関数型プログラミング言語ML 2
ｽﾚﾘﾝｸ(tech板)
関数型プログラミング言語ML
URLﾘﾝｸ(pc5.2ch.net)
ＭＬ！！！！！！
URLﾘﾝｸ(pc.2ch.net)

3:デフォルトの名無しさん
07/08/06 02:14:50
まぁ乙

このまま消滅かと思ったぜ

4:デフォルトの名無しさん
07/08/09 22:55:07
まさか前スレが既にdat落ちしているとは。MLな人はあんまり2chやらんのかな

5:デフォルトの名無しさん
07/08/09 23:08:49
そりゃ、メイリングリストに登録している人は、
2chなんか見ずに、そっちで発言するだろう。

6:デフォルトの名無しさん
07/08/09 23:09:33
>>4
落ちたのは 1000 行ったからだよ
住人が少ない訳じゃないと思う

7:デフォルトの名無しさん
07/08/14 09:24:59
なんという過疎。

8:デフォルトの名無しさん
07/08/14 09:39:03
リストのお尻だけを除去する処理って

List.rev (List.tail (List.rev list))

でいいのかな

9:デフォルトの名無しさん
07/08/14 10:00:42
let aaa a = match a with [] -> a | x :: y -> x

10:デフォルトの名無しさん
07/08/14 11:12:38
駄目じゃん>>9

[1; 2; 3] から [1; 2] をとりたいんだ

11:デフォルトの名無しさん
07/08/14 18:15:08
>>9
let cut_tail list =
let r = List.rev list in
match r with
| [] -> []
| _::y -> List.rev y

こんな感じ？

12:デフォルトの名無しさん
07/08/14 18:17:33
アンカーミスorz
>>8だった

13:デフォルトの名無しさん
07/08/14 18:46:51
let init xs = List.take ((List.length xs) -1 ) xs

これもありじゃね？と思ったけどopen ExtListしないとList.takeが使えないという罠が。

14:デフォルトの名無しさん
07/08/14 18:59:25
let init xs = let (xs, _) = List.fold_right (fun x (xs, t)-> if t then (x::xs, true) else ([], true)) xs ([], false) in xs;;

15:デフォルトの名無しさん
07/08/14 19:37:57
で、どれが一番効率が良いの

16:デフォルトの名無しさん
07/08/14 20:16:37
論理型と比較するとこの場合は関数型の弱点がでてる。
cut_tail([A],[]).
cut_tail([A|R1],[A|R2]) :- cut_tail(R1,R2).

17:デフォルトの名無しさん
07/08/14 22:00:39
let cut_tail lst =
　let rec loop acc = function
　　　x::[] -> List.rev acc
　　| x::xs -> loop (x::acc) xs
　　| _ -> failwith "error"
　in
　loop [] lst;;

18:デフォルトの名無しさん
07/08/16 14:43:29
λ山
URLﾘﾝｸ(wwwfun.kurims.kyoto-u.ac.jp)

19:デフォルトの名無しさん
07/08/16 14:59:47
関数型言語の聖地だな

20:デフォルトの名無しさん
07/09/09 09:54:15
保守

21:デフォルトの名無しさん
07/09/13 07:07:52
人こねえええ

アレゲ系の人もOCaml触らないし、というか最近Haskellの記事もあんまり見かけない気がしなくもない。
ブーム下火？
やっぱり研究者のおもちゃなの？

ビミョーに流行のScalaって明示的に型を書かなきゃなので嫌いなんだけど
あそこまでしてオブジェクト指向する必要ってあるのか
もちろんJavaとの相互運用性に優れてるのは分かるが

22:デフォルトの名無しさん
07/09/16 14:45:13
OCamlやSMLで多倍長の浮動小数点を扱うライブラリって無いの？
多倍長整数はあるのに…

23:デフォルトの名無しさん
07/09/22 11:59:23
ちょっと思いついたんだけど、これ↓便利かも。

# let ($+) f g x =
　　match g x with
　　　None -> None
　　| Some x' -> f x';;
val ( $+ ) : ('a -> 'b option) -> ('c -> 'a option) -> 'c -> 'b option =
<fun>
# let down i =
　　if i < 10 then None
　　else Some (i - 1);;
val down : int -> int option = <fun>
# (down $+ down $+ down $+ down) 12;;
- : int option = None
#

一旦Noneになったらその後の処理が実行されないなんて、なんかmaybeモナドっぽくね？
# だから？って言われりゃそれまでだけどｻ。

24:デフォルトの名無しさん
07/09/25 21:37:29
OCamlでSTMできるライブラリが登場してまっせー
URLﾘﾝｸ(cothreads.sourceforge.net)

25:デフォルトの名無しさん
07/09/27 11:50:09
λってなに？って聞かれたらなんて答えればいいの

26:デフォルトの名無しさん
07/09/27 13:04:40
関数です、と。
でもプロシージャではありません、とでもいっておく。

27:デフォルトの名無しさん
07/10/01 02:47:24
前に、どっかのスレで lambdaの由来を読んでから、
λって言葉に対する、引っかかりがなくなったというか
λって言葉に対して、意味を求めなくなった。

>λってなに？
ギリシャ文字を記号として使っている。

何を表す記号かというと、次の人が答えてくれる。
(私が、頓珍漢な事を書いてるのでなければ)

28:デフォルトの名無しさん
07/10/01 07:53:20
Calandar モジュールってあるじゃん
あれで今日の日付を取得すると、月がまだ９月なんだよね
だれか英語で切る人、報告してやってくれないか
俺は無理

29:デフォルトの名無しさん
07/10/01 07:56:24
Ｔｉｍｅｚｏｎｅのセット間違いだったよ、ゴメン

30:デフォルトの名無しさん
07/10/05 15:43:24
久しぶりにocamlのuser's manualを眺めてた。そんな事もできるのかーという構文発見。

其の1　ローカルモジュール
#let module A = struct let add x = x + 1 end in A.add 3;;
- : int = 4

其の2　開いて閉じる
#type t = [ `A of int | `B of bool];;
type t = [ `A of int | `B of bool ]
# type u = private [< t > `A];;
type u = private [< t > `A ]

private row応用範囲広すぎ。

31:デフォルトの名無しさん
07/10/06 16:01:07
えらいひとに質問です。
let f = function `A -> () | `B -> ();;
let g = function `C -> () | `D -> ();;

があったときに、これら2つを使って、「パターンマッチを使わず」に
h : [<`A|`B|`C|`D] -> ()

を合成する方法はありますか？
めっちゃ頭を絞ったんですが分からないのです。

何がやりたいのかというと、polymorphic variantを引数に取る任意の2つの関数を、
うまいこと合成したいのです。

32:31
07/10/06 16:07:01
あ、もちろん、`A,`B,`C,`Dを直接パターンマッチするのでなければ、match構文やfunction構文は使っても良いです。

そのような関数の型はどうなるのかを考えるために、ためしに、

let comp : (('a -> unit) -> (g:'b->unit) -> (['a|'b] -> unit)) = ();;

というのを考えてみましたが、['a|'b] のところで、
The type 'a is not a polymorphic variant type
と怒られてしまいます…

>>30みたいなことができたら良かったんですけどね。

33:デフォルトの名無しさん
07/10/06 17:36:35
パターンマッチの合成かー、私も一度悩んだことあるなー。
その時の結論は結局「無理」。fやgの引数に取る多相バリアントが閉じてなければ、
#let ($+) f g x =
　try g x with Match_failure -> f x;;
val ( $+ ) : ('a -> 'b) -> ('a -> 'b) -> 'a -> 'b = <fun>
#f $+ g;;
- : _[> `A | `B | `C | `D ] -> unit = <fun>
で合成できるけど、せっかくの型安全が台無し。
えらいひと回答plz.

34:31
07/10/07 00:33:08
おぉっ、なるほど。確かにそれっぽくなってますね。ありがとうございます。
あの後、似たようなことをやろうとしてダメだったんですが、よく考えたら[<`A|`B]->unitのようにclosedになってた気がします。

ただおっしゃる通り、f $+ gに`A..`D以外のバリアントが来た時に、g側がMatch_failureを投げてくれる関数でないとfが動いてくれないし、
f側はf側で想定外のバリアントをどうハンドリングするのかが問題っすね。

curry-howard的には、
((AまたはBならばX) かつ (CまたはDならばX)) ならば ((Aまたは...またはD) ならば X)
なので、そういう関数があっても良さそうなもんですが、
問題が多相バリアントなのでよくわからんです。

助けてえらいひと…

35:デフォルトの名無しさん
07/10/07 02:05:42
>>30
其の1を上手く使った例としてp4ckのpa_openinを挙げておく。
便利。

36:デフォルトの名無しさん
07/10/07 04:51:57
P4ckのpa_openinとpa_recordsくらいはそろそろ標準の構文に入れて欲しい。

37:デフォルトの名無しさん
07/10/11 00:01:52
第15回型からプログラムを当てる
URLﾘﾝｸ(itpro.nikkeibp.co.jp)

連載も既に15回を数え、そろそろ仕事方面に走り出している件について。

38:デフォルトの名無しさん
07/10/11 02:17:37
この人floatを浮動小数と書くけど、正しくは浮動小数点数じゃないのかな?
何が固定か浮動かっていうと小数点がだよね。

39:デフォルトの名無しさん
07/10/11 02:26:10
口語と文語だとでも思っておけば……

あっ、文章を書いてるんだっけｗ

40:デフォルトの名無しさん
07/10/11 11:13:42
>>37
これのどこが「数理科学的バグ撲滅方法論」なの？

41:デフォルトの名無しさん
07/10/12 02:24:58
Job Announcement
URLﾘﾝｸ(groups.google.com)

あのJane Streetが東京オフィスでOCamlハッカーを募集している！10月3日のメールだ！
我こそはという人材はいまがチャンスだ！！
（あぁ、私がもう10才若ければ……）

42:デフォルトの名無しさん
07/10/12 23:01:48
誰？

43:デフォルトの名無しさん
07/10/14 12:37:47
既出かもしれんけど

開発環境WideStudio/MWT
URLﾘﾝｸ(www.widestudio.org)

C++, Java, Perl, Python, Rubyのほかに…
OCamlも使える(3.09-2以降)らしい。ちょっと驚き。

44:デフォルトの名無しさん
07/10/14 21:35:57
OCamlerが主要開発者だから普通だろ

45:デフォルトの名無しさん
07/10/16 00:47:52
しらんがな

46:デフォルトの名無しさん
07/10/17 01:56:40
Java の Scripting API で、OCaml が使える。
OCamlScripting
URLﾘﾝｸ(ocamlscripting.x9c.fr)

47:デフォルトの名無しさん
07/10/17 18:19:21
そういう紹介だけ、とかありがたくもないし、ＭＬ見てたら誰でも知ってることなんだよね
いい加減うざい
使ってみたら～だった、ぐらいまで踏み込んでるならまだしも。

48:デフォルトの名無しさん
07/10/17 21:49:42
>>47
こういうハイレベルな人が「人こねえええ」を招くんだろうね。
私は紹介だけでも十分うれしいですよ。

49:デフォルトの名無しさん
07/10/17 23:00:50
>>40
別にバグを撲滅させようとしてるわけじゃない
研究さえできりゃそれでいいっていうスタンスだからな

50:デフォルトの名無しさん
07/10/18 13:02:16
>>48
むしろそんなハイレベルな人が2chを見ていることに驚くわけだが
MLとかいちいち粘着に全部読んでないし。

51:デフォルトの名無しさん
07/10/18 13:06:30
つーかどんだけ偏狭なんだと

52:デフォルトの名無しさん
07/10/18 20:09:23
URLﾘﾝｸ(caml.inria.fr)

53:デフォルトの名無しさん
07/10/18 22:44:11
preprocessor-pretty-printer-puricure

54:デフォルトの名無しさん
07/10/23 18:35:26
URLﾘﾝｸ(www.amazon.co.jp)

55:デフォルトの名無しさん
07/11/09 19:36:46
あああいつもrecを書き忘れる

56:デフォルトの名無しさん
07/11/09 19:38:07
なんでrecなんてかかなきゃいけないんだy

57:デフォルトの名無しさん
07/11/09 23:30:30
マジレス。
let f x=x in let f x=f x+1 in f 0

とかが書けてしまうので、OCamlのプログラムなので、let recと明示的に再帰していると言ってやらなきゃならんのでは。
Haskellだとこうはならんすよね

58:55
07/11/10 02:37:55
>57 ありがとうございます。
ちょっと取り乱しました

59:デフォルトの名無しさん
07/11/11 11:01:35
MLでも今のletとlet recの仕様を入れ替えれば、こんな面倒はなくなる。
その場合let recだと変だから、let outerくらいにすればよい（どうせほとんど使われない）。

60:デフォルトの名無しさん
07/11/12 22:53:05
SMLでは再帰関数定義にはval recとfunが使えます。

61:デフォルトの名無しさん
07/11/12 23:46:56
このスレではOcaml派：SML派はどんくらいなんだろうな。
まぁOcaml派8割越えなんだろうけどな...

62:デフォルトの名無しさん
07/11/13 00:18:01
SML は良い実装が無いから…

63:デフォルトの名無しさん
07/11/13 09:08:14
SML#に期待

64:デフォルトの名無しさん
07/11/13 19:42:13
Native Thread 使えないから期待出来ないよ

何で日本の言語屋さんってハードウェアのトレンドを理解してないんだろう…
並列化は OS の仕事だとか言ってる人も居るし…

65:デフォルトの名無しさん
07/11/13 21:10:47
何でハードウェア屋さんって言語のトレンドを理解してないんだろう…

66:デフォルトの名無しさん
07/11/13 21:15:29
>>65
それは実状と異なるからナンセンス。

67:デフォルトの名無しさん
07/11/13 22:57:16
何で言語屋さんとハードウェア屋さんって、コミュニケーションを取らないんだろう…
情報交換はOS屋の仕事だとか言ってる人も居るし…

68:デフォルトの名無しさん
07/11/13 23:06:28
それ日本だけだから日本発の処理系以外は大丈夫

69:デフォルトの名無しさん
07/11/14 02:35:21
こうして実用環境はすべてC言語
（およびC言語上に構築された動的言語（笑））
とUNIXから逃れられないのでした。完。

70:デフォルトの名無しさん
07/11/14 05:50:33
まあでもJoCamlがErlangより速いって結果もあるし、こういう型付きコンパイルによる効率向上とCより格段に高い信頼性からいって、OCamlもけっこう捨てたもんじゃないとおもうよ
URLﾘﾝｸ(eigenclass.org)

71:デフォルトの名無しさん
07/11/22 22:30:33
Microsoftの新プログラミング言語「F＃」，Visual Studioへの搭載目指す
URLﾘﾝｸ(itpro.nikkeibp.co.jp)

>「ML」という初期の関数型プログラミング言語をベースに，
>プログラミング言語「C＃」や「Haskell」，リレーショナ
>ル・データベース操作技術「LINQ」の要素を含んでいる。

ITProよ。そこはどう譲ってもHaskellじゃなくて、OCamlだろっ！！

72:デフォルトの名無しさん
07/11/22 22:35:30
遅延評価とか Haskell 的なものって無いよねぇ確か F# に

73:デフォルトの名無しさん
07/11/23 14:06:06
>>64
頭古すぎw

74:デフォルトの名無しさん
07/11/23 14:32:03
>>73
並列化は OS の仕事だというのが?
確かに時代錯誤的だよね

75:デフォルトの名無しさん
07/11/23 14:39:12
ハードウェアに特化しすぎた奴は全部死滅しただろ。
トランスピュータ＋オッカムとか、コネクションマシン２＋C*/*Lispあたり。

求められているのはハードウェアにベッタリしすぎない抽象化されたモデル。

76:デフォルトの名無しさん
07/11/23 14:59:15
>>75
抽象化自体は良いよ。ただ、ハードの資源を使い切れない様な抽象化では
意味が薄い。ハードの制約を無視した抽象化は単なる机上の空論だよね。

何年も前からトランジスタ数の増大に比較して CPU の性能が伸びない事、
CPU の速度向上に Memory が付いて来れない事が問題になっている。
現状としては業界を上げてマルチコア、メニーコア、ハードウェアマルチ
スレッディングに移行している。途中で VLIW みたいな寄り道もしたけど、
現在製造されているプロセッサの多くが既にマルチコアに意向済み。

そんな中で、いかにスレッドを簡単に扱えるか、スケーリングする GC を
実装出来るかは言語の設計と処理系の実装には結構重要なポイントで、
テーマとしては新規性はあまり無いかもしれないけど、逆に言えば本来
あって当たり前の機能なんだよね。自動並列化とか CAS とかも。

まあ最低限、ネイティブスレッドくらいは扱える様な処理系があると良いね。

77:デフォルトの名無しさん
07/11/23 15:05:21
ネイティブ・スレッドって結論が馬鹿すぎる。

それから関数型言語と並列化の文献は山のようになるので、
英語でもちゃんと読んでやってください。

78:デフォルトの名無しさん
07/11/23 15:08:03
>>77
それを馬鹿だという奴は現実が見えてないだけだよ。
並列化の研究が沢山あるのは知ってるよ。じゃあどれだけの
実装が残ったのかという話。

79:デフォルトの名無しさん
07/11/23 15:10:04
今後のハード技術は
スレッドが使いづらい方向に行くと思うぞ

80:デフォルトの名無しさん
07/11/23 15:10:48
有益でないから残らない。
関数型言語はErlangなど残っている方。

81:デフォルトの名無しさん
07/11/23 15:14:30
>>79
どちらかというとスレッドが無いとやってられない方向へ向かってる

82:デフォルトの名無しさん
07/11/23 15:18:45
有益でない言語は残らない。

83:デフォルトの名無しさん
07/11/23 15:24:09
つまりMSにとって有益な言語が残るってことだな

84:デフォルトの名無しさん
07/11/23 15:33:41
Haskell は STM とか頑張っているんだがのう
SML はダメッポス

85:デフォルトの名無しさん
07/11/23 16:14:00
STM?

86:デフォルトの名無しさん
07/11/23 16:18:31
>>84
URLﾘﾝｸ(haskell.g.hatena.ne.jp)

元の処理系に並列化の基盤が無いと、
こういう実験にも使えないのよね

87:デフォルトの名無しさん
07/11/23 16:46:40
間違えた。>>86 は >>85 向け。

88:85
07/11/23 16:59:39
さんきゅう

89:79
07/11/23 18:29:22
スレッドが使いづらい方向に行くっていう意見は、たぶん俺がハード屋で
性能/消費電力/発熱に苦しんでるからかも。

SMPコアには既に限界を感じてる。

ASMPコアで無駄な回路を減らせば、まだまだ上を狙える。
遅延評価・非同期実行（イベント同期）をナチュラルに行なえる言語だと
ハード・ソフトの両面からグッと最適化が効く。

スレッドはSMPと相性がいいかもしれんが、
でもASMPにはマッチしないと思う。

90:デフォルトの名無しさん
07/11/23 18:32:00
スレッド←→遅延評価・非同期実行（イベント同期）
って反対概念でもないよね?

91:デフォルトの名無しさん
07/11/23 18:39:20
>>89
ASMP でも汎用コアが複数あったり、SMP と言っても特殊用途の
コプロ積んでたりするもんじゃないの?

どう転んでもスレッドの重要性は当分は覆らないと思うけどなあ。

92:デフォルトの名無しさん
07/11/23 22:38:05
>>90
確かに。お互いに実現可能なものを持ってるしね。

スレッドはハード層にCPUとしての機能と性能を要求してくるけど、
本当にそんなに大げさな物が必要なのかなーって思ってる。

OS層にはマルチタスク要求があるからスレッドは有益だけどさ。

アプリ層でスレッドを使うときって、
　・CPU複数使って速く処理する
　・ブロッキング処理を非ブロッキング処理にする

こういうのを言語がサポートしてないからじゃない？
（ライブラリじゃなくて言語仕様ね）

それにスレッドっていうキーワードを使って作られたものって、
DSP,SIMD,コプロ等々の存在を無視する気がする。
┌───────┐
│　関数　　　　　　　　　　　　　　　｜
├──┐　　　　　　　　　　　　　｜
｜　ｽﾚｯﾄﾞ　｜　　　　　　　　　　　　　｜
├──┴─┬────┤
｜　CPU　　　　｜DSP,SIMD,コプロ｜
└───┴────┘

言語にはネイティブスレッドを要求するより
こんなものの→（Scatter/Gather、Map/Reduce、遅延評価、イベント同期）
シームレスでポータビリティな仕様と、実装の最適化を要求して欲しい。

93:デフォルトの名無しさん
07/11/23 23:05:28
>>92
結局 CPU 複数使って速く処理するにはスレッドが必要なんだぜ。
何でそんなにスレッドを嫌がるのかは知らんけど、現実には
コプロや SIMD があってもスレッドは必須だよ。

94:デフォルトの名無しさん
07/11/23 23:27:35
話がかみ合ってないな

95:デフォルトの名無しさん
07/11/23 23:38:17
はぐらかしてるだけに見えるけど

96:デフォルトの名無しさん
07/11/24 00:04:53
＞CPU　複数使って速く処理するにはスレッドが必要
違う。
手続き言語andスレッド　によって速い処理を行おうとするから
複数のCPUを要求されている。

でもスレッドじゃ
　　DSP,SIMD,コプロ
この辺をうまく使っていけない。

極論だけど、関数言語がソフトウェアの主流なら
クロックを使わない論理回路で作ったチップにも需要が出るから
そういうのも作るもん。

97:デフォルトの名無しさん
07/11/24 00:15:20
>>96
違うっていうけどさ、元々違う話をしてるんだから当たり前だよ。
俺は現実世界にある CPU をどう有効に使えるかにしか興味無いよ。
そしてその為にはスレッドを使うのが一番の近道。

それにスレッドと SIMD やコプロは排他的な存在じゃないから。

98:デフォルトの名無しさん
07/11/24 00:35:01
>>96
>手続き言語andスレッド�によって速い処理を行おうとするから
>複数のCPUを要求されている。

これは違うよな。プログラマはスレッドなんて別に使いたくない。
シングルコアで高性能の CPU が作れないっていうから、仕方なく
ソフトウェアを並列化してるだけ。DSP も一緒。

99:デフォルトの名無しさん
07/11/24 00:47:23
各CPUにコードをロードさせておいてから、
データばらまいて、関数に突っ込んで、出力を集計すればいいじゃん。

ってこれはMap/Reduceだよな。

100:デフォルトの名無しさん
07/11/24 01:04:45
何だよ、素人か。

101:デフォルトの名無しさん
07/11/24 23:28:42
言語はマルチスレッドをサポートすべき?
│
├CPUシングルスレッド性能は打ち止めだからこれからはマルチスレッドスレッドだよ
│├マルチスレッドをどうにかするのは言語の仕事だよ
││├とりあえずスレッドとロックサポートすればいいよね (古典派)
││├ロックしないよ (モダン派)
││├プロセスは言語の基本だよ (並列言語派)
│││└おっぱいおっぱい (ぱい計算ってうまいの?)
││└マルチスレッドは実装屋の仕事だよ
││
│├マルチスレッドをどうにかするのはOSの仕事だよ
││├1つのプロセス中では並列度上がらないよ
││└小さいプロセスいっぱい作るよ (forkできればそれでいい派)
││
│├CPUごとに仮想マシン割り当てるから問題無いよ
││
│└コプロの命令もメインプロセッサの命令に見せかけるからやっぱスレッドだよ (Intel)
│
├マルチスレッドよりも大切なものがあるよ
│├SMPは限界。処理ごとに回路作るよ
│├高性能処理はベクタマシンだろ。常考 (ベクタ派)
││└GPUを計算に利用しようぜ (新ベクタ派)
│├他マシンとの通信こそ重要だよ (クラスタ派)
│└機械語レベルでなんとかなるよ (スーパースカラ派・コードモーフィング派)
│
└並列こそ計算の本質だよ。データフローマシン最高 (逐次処理は諸悪の根源だよ派)

102:デフォルトの名無しさん
07/11/25 00:13:28
っあらゆるテクニックを使って速く動くように裏で最適化してよ（何も考えたくない派）

103:デフォルトの名無しさん
07/11/25 14:48:34
クラスタ以外は、下へ行けば行くほど現実解から遠ざかっているなw

104:デフォルトの名無しさん
07/11/25 20:21:12
ていうかアプリによってどれがいい違ってくるよね

105:デフォルトの名無しさん
07/11/25 20:24:02
アプリレベルじゃない話も混ざっているみたいだけど
例えば fork を使うと良いアプリってどんなの?

106:デフォルトの名無しさん
07/11/25 20:28:36
ネットワークサービス系はforkがいいと思う。
セキュリティを考えると、
同じプロセスで走らせたくない処理が多い。

107:デフォルトの名無しさん
07/11/25 20:45:54
ネットワークサービス系って一般的にはスレッドプールを作るイメージだけど、
具体的にはどんなアプリを想定してるの?

108:デフォルトの名無しさん
07/11/26 11:28:12
>>84
manticoreがあるでしょ > SML

>>101
> 言語はマルチスレッドをサポートすべき?

関数型言語の場合は、semanticsをどうするかが一番の論点で、
(関数型言語でなくていいことは、他の言語でやればいいし、実際行なわれている)
言語に並列処理能力を持たせるべきかどうかってのは、設問としておかしい。
持たせるとしたらどういう風なものがいいか、研究が行なわれ続けている。

109:デフォルトの名無しさん
07/11/26 12:02:18
>>108
＞関数型言語の場合は、semanticsをどうするかが一番の論点
そーそー、それそれ。
関数型言語にはそういう力があるんだから。

>>92の一番最後に書いたここの部分ね。
＞シームレスでポータビリティな仕様

CがUNIXの力になって
LLがWebアプリの力になったように
関数型言語が並列処理分野の力になると思うんだけど。

今のスレの流れって
なんだかWebアプリの話をしてるときに
C実装レイヤーのことを話してるみたいな気がする。

110:デフォルトの名無しさん
07/11/26 12:04:09
>>108
>関数型言語でなくていいことは、他の言語でやればいい
それはおかしいだろ。
例えばすごく関数型向きなアプリケーションを作ろうとしていて、
たまたま一ヶ所並列計算が必要だと分かったら、それだけで
関数型言語が選択肢から外れるってのは問題だと思わないか？
同じ論法で、汎用言語なら、良く使われる機構は一通りカバーしておくべき。

111:デフォルトの名無しさん
07/11/26 15:39:16
あなたが知らないだけです。

112:デフォルトの名無しさん
07/11/26 20:41:03
>>111
そういうのは例え 2ch でもどうかと思うよ。

manticore ってこれか。まだ実装は公開されてないのね。

URLﾘﾝｸ(manticore.cs.uchicago.edu)

113:デフォルトの名無しさん
07/11/26 22:17:20
>>86
それ、最初の方でoperaionalにSTMの意味を説明しているけど、
それはSTMの実装の一つを紹介している(ことになっている)だけで、
STMは必ずしもそういう実装になる必要はないので読む時には気をつけて。
TMはdatabaseやdistributed computingでよく使われるモデル。

並列処理抽象化のために、実装がいくつも考えられて、
モナド親和性の高いモデルを採用している。

114:デフォルトの名無しさん
07/11/27 14:11:41
CML(URLﾘﾝｸ(cml.cs.uchicago.edu))とOCamlのThreadsライブラリの事もたまには思い出してあげてください。

115:デフォルトの名無しさん
07/11/27 20:54:51
CML って所謂 Green Thread だと思ってた
ちゃんと "Concurrent" に動くの?

116:デフォルトの名無しさん
07/11/28 08:03:00
スケジューラがユーザ空間に(も)ないと、
関数型言語っぽい面白いことができない。

CML→manticoreって人がいるね。

117:デフォルトの名無しさん
07/11/28 23:15:14
せっかく新生した JoCaml のことも思い出してあげてください

118:デフォルトの名無しさん
07/11/28 23:20:30
OCaml はもう良いじゃん...

119:デフォルトの名無しさん
07/11/28 23:29:28
>>114
coThreadライブラリ(URLﾘﾝｸ(cothreads.sourceforge.net))は無視ですか、そうですか。

120:デフォルトの名無しさん
07/11/30 01:25:15
プログラミング in OCaml ~関数型プログラミングの基礎からGUI構築まで~
と
入門OCaml ~プログラミング基礎と実践理解~
どっちがいい？

121:デフォルトの名無しさん
07/11/30 11:09:15
立ち読みして決めろ

122:デフォルトの名無しさん
07/12/01 00:27:53
お前らの感想を言え

123:デフォルトの名無しさん
07/12/01 13:42:43
>>122
昨日発売される本の即日レビューなんて無茶いうな。

　　　入門OCaml
必要なことは大体書いてあるので、基礎的なことは十分できるようになった。
　短所としては、よくあることだけど、ちょっと複雑な機能を説明するときに
複雑な例で解説してる場所がある、とか。そのぶん実用例の確認にはいいんかな。
そういう部分は自分で簡単なもの作ってみて理解するしかない。
　まだ勉強中だけどスレッドやらパーサやらCGIやらの使用例とかあるし
本格的に使うつもりなら買っといていいんじゃないっかな。

あとこの本が無ければSML#とか知らなかった。

124:デフォルトの名無しさん
07/12/01 16:26:55
SML#の本、欲しい

125:デフォルトの名無しさん
07/12/01 17:36:49
>>116
>CML→manticoreって人がいるね。

manticoreってもう使えるの?

126:デフォルトの名無しさん
07/12/01 20:45:42
>>120
どちらかといえば、前者。

127:デフォルトの名無しさん
07/12/02 00:09:43
>>125
>>116は研究者/開発者

128:デフォルトの名無しさん
07/12/02 01:04:45
>>119
正直無駄にHaskell-STM風にモナド前提なのを何とかして欲しい。

129:デフォルトの名無しさん
07/12/02 08:05:45
無駄に？

130:デフォルトの名無しさん
07/12/02 12:32:54
Poly/ML が 5.1 でネイティブスレッドを使える様になっているね
polyml.5.1/libpolyml/processes.cpp 内で pthread 関連の関数を
呼び出しているみたい

Poly/ML を使っている人はこのスレには居ないかな...

131:デフォルトの名無しさん
07/12/02 21:46:29
使ってるよ。
自作のコードはStandard ML系の処理系のほとんどでひととおり動作チェックする。

132:130
07/12/02 22:23:23
今日久々に Poly/ML 見てみたんだけど、結構進化してるよね。
イメージベースの環境から、オブジェクトファイルを吐いて
実行ファイルを生成出来る様に変わっているし、スレッドは
カーネルスレッドをサポートしているし、FFI は C の構造体
を扱えるし、Intel Mac も Solaris もサポートしているし、
あと欲しいのは UNICODE のサポートくらい。

Standard ML 処理系では最強なんじゃないかな。

133:デフォルトの名無しさん
07/12/03 09:37:00
誰かocaml-ssl ってのビルドできた人いますか（0.4.2）

URLﾘﾝｸ(sourceforge.net)

134:デフォルトの名無しさん
07/12/06 00:06:44
SML のソースコードを沢山読んでみたいのですが、
Perl でいう CPAN みたいなのはありませんか?

135:デフォルトの名無しさん
07/12/06 08:34:33
つ URLﾘﾝｸ(www.cs.princeton.edu)

136:デフォルトの名無しさん
07/12/06 09:02:46
ありがとうございます！

137:デフォルトの名無しさん
07/12/07 12:11:14
>>2
>URLﾘﾝｸ(yk.i.hosei.ac.jp)

だいぶ今更かもしれないけど、これ無くなってしまっているね。
欲しい人は今のうちに Web Archive から頂いておいた方が良いかも。

138:デフォルトの名無しさん
07/12/08 02:59:37
>133
Cygwin 上で特に patch なしでビルドできてるけど。何ぞ問題が？

139:デフォルトの名無しさん
07/12/08 16:52:38
過疎っているので、Python スレにあったお題でコードを書いてみました。
"行頭の空白文字列を nbsp に変更するプログラム"

fun replaceWhite file =
　　let fun repLn lst =
　　　　　　　　case hd lst of
　　　　　　　　　　#" " => [#"&", #"n", #"b", #"s", #"p", #";"] @ repLn(tl lst)
　　　　　　　　| #"¥t" => [#"&", #"n", #"b", #"s", #"p", #";",
　　　　　　　　　　　　　　　　　　　　　#"&", #"n", #"b", #"s", #"p", #";",
　　　　　　　　　　　　　　　　　　　　　#"&", #"n", #"b", #"s", #"p", #";",
　　　　　　　　　　　　　　　　　　　　　#"&", #"n", #"b", #"s", #"p", #";"] @ repLn(tl lst)
　　　　　　　　| _ => lst
　　　　　　fun replace out =
　　　　　　　　case TextIO.inputLine out of
　　　　　　　　　　NONE => ()
　　　　　　　　| SOME ln => ((print o String.implode o repLn o String.explode) ln;
　　　　　　　　　　　　　　　　　　　　　　replace out)
　　in (replace o TextIO.openIn) file
　　end;

140:デフォルトの名無しさん
07/12/08 16:56:47
もういっちょ。
"フィボナッチ数を 0 から 35 まで表示するプログラム"

fun fibloop () =
　　let fun fib n = if n < 2 then n else fib(n-1) + fib(n-2)
　　　　　　fun loop 36 = ()
　　　　　　　　| loop cnt = (print(Int.toString(fib(cnt)) ^ "¥n");
　　　　　　　　　　　　　　　　　　　　　　loop (cnt + 1))
　　in loop 0
　　end;

141:デフォルトの名無しさん
07/12/08 21:30:26
次スレを立てる時は >>2 の SML の所にこれを追加して欲しいな
SML を勉強していて一番参考になった

URLﾘﾝｸ(www.geocities.jp)
URLﾘﾝｸ(sml.sourceforge.net)

142:デフォルトの名無しさん
07/12/08 23:42:59
>>137
旧研究室サーバにあった。
URLﾘﾝｸ(133.25.16.150)

143:デフォルトの名無しさん
07/12/10 00:42:45
>>139
...正規表現のライブラリって無いのですか？
いくら静的型付けとはいえ、スクリプト系の言語に比べてかなり冗長で、
いまいちSMLを勉強する気にならないのですが...。

144:デフォルトの名無しさん
07/12/10 03:21:09
取り敢えず Moscow ML には正規表現ライブラリがバンドルされている
みたいだけど、他もあるんじゃないかな。正規表現を使わなくとも
Vector で書いたらコード量は大分少なくなると思う。

まあそんな事は誰でも簡単に調べられる事だし、勉強する気にならない
のであれば他の事をした方が良いと思うよ。自由ってそういう事でしょ。
面白いと思ってすぐに手を動かせる人間が自分で色々探求して行く一方で、
そうじゃない人がいても別に誰も強制したりなんかしない。

そもそも >>139 は SML を勉強し始めて一日目の人間が書いたコード
だから参考にしない方が良いでしょう…

145:デフォルトの名無しさん
07/12/10 09:43:10
>>144
3行でおｋ

146:デフォルトの名無しさん
07/12/10 18:12:49
>>145
俺の
コードに
文句言うな

147:デフォルトの名無しさん
07/12/10 21:34:29
>>144
一日目でそれだけ書ければすごいよ。

148:デフォルトの名無しさん
07/12/10 22:13:04
>>145
3 行 x 80 桁ではこれが限界ですた…

fun r () = let open TextIO String Char val c = (valOf o input1) stdIn; in case c
of #" " => print "＆nbsp;" | #"¥t" => print "＆nbsp;＆nbsp;＆nbsp;＆nbsp;" | #"¥n" =>
print "¥n" | _ =>((print o toString)c;(print o valOf o inputLine)stdIn);r() end;

149:デフォルトの名無しさん
07/12/12 20:07:08
OCamlで
('a -> 'a) -> 'a
という型のY-combinatorを定義することは出来るのでしょうか。
let fix = fun f -> (fun x -> f (fun y -> x x y)) (fun x -> f (fun y -> x x y))
や
let rec fix f = f(fun x -> fix f x)
はどうしても、
(('a -> 'b) -> 'a -> 'b) -> 'a -> 'b
という型になってしまいます。(遅延評価をするHaskellでは問題なく書けるのですが)
これだと,TAPLのP144にある,以下の相互再帰が型エラーで書けません。
let ff ieio =
{iseven =
(fun x ->
if x=0 then true
else ieio.isodd (x-1));
isodd =
(fun x ->
if x=0 then false
else ieio.iseven (x-1))}

let r = fix ff

150:デフォルトの名無しさん
07/12/13 02:27:16
パターンマッチのある言語で正規表現って必要なんだろうか。
メタランゲージなんだから、そのまま書き下した方がスッキリする。

151:デフォルトの名無しさん
07/12/13 08:08:58
関数型言語のパターンマッチでまだ A.*B 相当とか書けないよね。

152:デフォルトの名無しさん
07/12/13 08:45:20
>>150
正規表現並にconciseな表現ができればね

153:デフォルトの名無しさん
07/12/13 08:58:43
正規表現そのものだと、バックトラックが必要になるからまずいです。

154:デフォルトの名無しさん
07/12/13 17:18:34
中置文字について何かまとめた。トリビア的なものだけど。（OCaml 3.09.2）

頭文字
　　=<>@^&+-*/$%　　どこでも大丈夫
　　|　　二文字以上なら頭文字可
後続文字
　　~　　二文字以上なら頭文字にできるが、頭に使うと前置しかできなくなる。
　　!　　頭文字にすると前置のみに。
　　.:?　　後続文字のみ使用可

155:デフォルトの名無しさん
07/12/15 00:37:16
(* ^ o ^ *)

156:デフォルトの名無しさん
07/12/15 00:39:32
神経を逆撫でするコメントだな

157:デフォルトの名無しさん
07/12/17 12:32:42
with-open-file (fun ch -> fprintf ch "aaa")

みたいなのって標準ライブラリにある？

158:デフォルトの名無しさん
07/12/17 21:14:55
俺も欲しいけど、エラーの扱いとかどうなるんだろ

159:デフォルトの名無しさん
07/12/18 20:20:46
中でfinallyつかえばいいんじゃないかな。

160:デフォルトの名無しさん
07/12/22 10:35:14
ocamlにfinallyなんてないだろ

161:デフォルトの名無しさん
07/12/22 16:22:00
Javaプログラマは夢見るSuccubus
finally かなり例外に依存して生きているの

162:デフォルトの名無しさん
07/12/22 17:32:45
何だ OCaml には finally があるのかと思った
また OCaml 限定の話かよとスルーしてたのに

163:デフォルトの名無しさん
07/12/27 23:00:37
>>149
OCamlでは
('a -> 'a) -> 'a
という型のY-combinatorは定義出来ません。
HaskeiiはLazy evaluationなので、例で書いているように出来るのですが、
OCamlはEager evaluationなので、argumentをすぐに評価しようとするので、それをお書きになったような形で避けるとにコンビネータではなくなってしまいます。
これを避けるにはLazy モジュールを使用してﾅﾝﾁｬｯﾃ遅延評価で解決します。そうすればコンビネータとして扱うことが出来ます。

同様のことはモナドにも言えて、ﾅﾝﾁｬｯﾃ・モジュールを使用すると解決することがあります。

MLのＹコンビネータの書き方はLittle MLerの巻末に書いてあるのでご覧下さい。

164:デフォルトの名無しさん
07/12/28 17:21:19
>>149 >>163

factの実装方法を２通り紹介しておく。

チューリングの賢人鳥
let rec turing's_sage f x = f (turing f) x;;
turing's_sage (fun f x -> if x = 0 then 1 else x * (f (x-1))) 5;;

カリーの雲雀
let lark x (`M y) = x (fun z -> y (`M y) z);;
let curry's_sage f x = lark f (`M (lark f)) x;;
curry's_sage (fun f n -> if n = 0 then 1 else n * (f (n-1))) 5;;

どっちの方法も
- : int = 120
と返ってくる。

165:デフォルトの名無しさん
07/12/28 19:10:27
>>164
スマリヤンの「ものまね鳥」だね。SKIコンビネータ入門にいいよね。
ほかにもJAYとかOWLとか出てきた希ガス。

166:デフォルトの名無しさん
07/12/28 21:22:48
論理学の問題ならCoqを使ってコードを作ればいいんじゃねえか？

URLﾘﾝｸ(coq.inria.fr)

167:デフォルトの名無しさん
07/12/28 21:39:17
(つд⊂)ｺﾞｼｺﾞｼ(;ﾟдﾟ) 論理学の問題

168:デフォルトの名無しさん
07/12/29 00:08:29
Coq is the specification language.

Interactive Theorem Proving And Program Development
by Coq'art: The Calculus Of Inductive Constructions

これ系統の参考文献にこれもいいかも。

TAPL : Types and Programming Languages

169:デフォルトの名無しさん
07/12/29 00:24:27
>>167
数理論理学とコンピュータ・プログラムの間には深い関連性がある。

Ａ．近代論理学の開祖であるフレーゲの概念記法を出発点とするゲンツェンの自然演繹
Ｂ．チャーチの型付きラムダ計算

２つのモデルはカリー・ハワード対応によって同型として対応付けられる。
つまり、論理学の問題と言っているのは、実はコンピュータ・プログラムの問題と言っているのと同じなのだ。
QED.

170:デフォルトの名無しさん
07/12/29 00:51:12
Coq見てみたけどﾜｶﾗﾝｗ

OCaml-Nagoyaの次の本はCoqだな。決定。

171:デフォルトの名無しさん
07/12/29 19:25:22
WindowsのCoqIDEが動かないな。固まったよｗ

172:デフォルトの名無しさん
07/12/30 00:47:12
>>171
うごくよ。
てかProofGeneralが亡くなってる。

173:デフォルトの名無しさん
08/01/01 02:06:59
>>169
その同型になるのは、１階の述語論理のこと？

174:デフォルトの名無しさん
08/01/01 13:37:59
カテゴリカル・コンビネータ理論

175:デフォルトの名無しさん
08/01/01 13:45:05
一階述語論理にカリー・ハワード同型対応で対応するのは、一般の関数型言語で使われている型理論とはだいぶ異なる型理論です。

176:デフォルトの名無しさん
08/01/01 14:36:17
高階述語論理をカリー・ハワード対応させるとどうなるんですか？

177:デフォルトの名無しさん
08/01/01 15:55:45
>>176
どうしたいん？

178:デフォルトの名無しさん
08/01/01 16:07:39
Curry-Howardの対応の依存型（dependent type）があると、高階述語論理を表現することができる。
高階述語論理があれば、「∀f. --- 任意の関数 f について…」という扱いが可能になったり、「関数や述語に関する量化（∀∃）が可能な論理」を構成できる。

179:デフォルトの名無しさん
08/01/01 16:19:56
型付きλ計算の世界では、「値の世界」と「型の世界」の間に明確な分離があり、型の定義中に値が出現するといったことはありません。
しかし、依存型(dependent type)を導入するとこの制限が取り払われて、型が値を持てるようになります。
依存型は単純な型付きλ計算よりもはるかに強力で、うまく使えばリストの長さや配列の境界チェックなどさまざまに応用できます。
しかし強力さの一方で型チェックは複雑になり、一般の依存型では型チェックが停止しない場合もあります。
例えば、基本的には型の部分で計算ができるので、そこに無限ループするような項を入れておけば止まらなくなります。
Curry-Howard Isomorphism により、依存型は述語論理と等価な記述力を持つことになります。
したがって、依存型をつけたλ計算の体系を考えることで、論理式の証明を記述したり、その正しさを検査することが可能になるわけです。

OCAMLのCoq では、単純なλ計算ではなく帰納的に定義された型(Inductive types)を使えるように拡張した
Calculus of Inductive Construction というものに依存型を導入し、システムの根幹としています。

180:デフォルトの名無しさん
08/01/01 16:26:17
最低でも、一階述語論理系を構成できる程度は理解し、その上で、

直観主義論理，Matin-Loefの型理論、依存型算譜言語

の3つをプログラムの基礎として最低限おさえておけ。

181:デフォルトの名無しさん
08/01/01 17:11:13
Curry-Howard Isomorphism をトポスの言葉で表現するとどうなるんですか？

182:デフォルトの名無しさん
08/01/01 17:37:52
>>181
おとなしくシミロン嫁

183:デフォルトの名無しさん
08/01/01 17:40:00
グロタンのEGA/SGA嫁

184:デフォルトの名無しさん
08/01/01 17:41:40
知ってどしたいん？ん？

185:デフォルトの名無しさん
08/01/01 17:47:24
シミロンとは・・・

圏論による論理学―高階論理とトポス
清水義夫

URLﾘﾝｸ(www.amazon.co.jp)

186:デフォルトの名無しさん
08/01/01 18:09:02
>>182
シミロン読んでるんですが、高階論理をトポスに対応させて
いるところを Curry-Howard 同型と考えていいわけですか？

187:デフォルトの名無しさん
08/01/01 18:26:11
>>186
まあそうなんだけど、関数に対応するものがトポスの射になってる。

普通の集合論では、「はじめに一者あり」である。存在論的な形になっていて、その一者（実は、空）から、すべての存在が生成される。
では、Mac Lane が指摘した、論理学ではどうなるか。

ところが関数型の場合、「はじめに働きあり」である。なんじゃそりゃ、と思うかもしれない。
普通の集合論では、関数は、集合の一種（つまり、グラフ）として定義される。
でもこちらは、逆に、関数から集合を定義しようということなのだ。

この関数概念を一般化したのがシミロンのトポスの射。

188:デフォルトの名無しさん
08/01/01 18:31:40
Grothendieckは位相空間 X より X 上の層全体のなす圏(トポスになる) がより本質的だと考えた。
彼はこの考えを、エタールコホモロジーのアイデアとともに得た。

189:デフォルトの名無しさん
08/01/01 18:34:39
>>187
解説ありがとうございます。
ちょっと外出してきますのでまたのちほど。
すみませんです。

190:デフォルトの名無しさん
08/01/01 18:36:07
シミロンでやってるのはGrothendieckのオリジナルとは違って、
Kripke-Joyalの意味論での手続きによって集合論的論理式をトポスの対象と射についての言明として解釈したもの。

191:デフォルトの名無しさん
08/01/01 18:47:05
実数の体系の持つ超越的な性格は集合論の初期から様々な数学者の嫌悪の的となった。
実数を定めるのに便利な集合論的定式化はやがて多くの数学者に受け入れられるようになったが、
20世紀初めに論理学者のブラウワーは直観主義とよばれる、具体的に構成できるようなものだけを認める論理の体系をつくった。
彼はそこで実数について通常の数学におけるものとは著しく異なった結論を導きだせることを示した。
これにはKripke-Joyalの層の意味論によって現代的な解釈が与えられる。

シミロンのやってることを実行するとこんな風に実数の扱いなどがもっとブラウワー的に出来るようになります。

192:デフォルトの名無しさん
08/01/01 18:49:58
ただしCoqではKripke-Joyalの意味論は扱えないのでこのスレの趣旨からは外れますね。
つづきは数学板で質問してください。

193:デフォルトの名無しさん
08/01/01 19:10:59
λ式は、どのプログラマにとっても役立つ新たなツールです。最近ではVisual Basic 2008にも実装されました。

元々、Visual Basic 2008 (以前のコード名は "Orcas") にλ式が追加されたのは、LINQ (Language Integrated Queries) をサポートするためです。
これは、Visual Basic でのデータプログラミングを可能にするものです。

λ式を使用すると、プログラムの柔軟性が向上することがわかります。
λ式は、関数内で定義される呼び出し可能なエンティティであり、何の制約もなく利用でき、
したがって、λ式を関数から返したり他の関数に渡したりできるからです。

λ計算（lambda calculus）は、理論計算機科学や数理論理学における、関数の定義と実行を抽象化した計算体系であるλ算法とも言う。
関数を文字λ)を使った式によって表記する。アロンゾ・チャーチとスティーヴン・コール・クリーネによって1930年代に考案されたものです。
1936年にチャーチはλ計算を用いて一階述語論理の決定可能性問題を否定的に解いた。
λ計算は「計算可能な関数」とはなにかを定義するために用いられることもある。

λ計算は1つの変換規則（変数置換）と1つの関数定義規則のみを持つ、最小の（ユニバーサルな）プログラミング言語であるということもできる。
ここでいう「ユニバーサルな」とは、全ての計算可能な関数が表現でき正しく評価されるという意味である。
これは、λ計算がチューリングマシンと等価な数理モデルであることを意味している。
チューリングマシンがハードウェア的なモデル化であるのに対し、λ計算はよりソフトウェア的なアプローチをとっている。

λ計算は計算の意味論や型理論など、計算機科学のいろいろなところで使われており、特にLisp、ML、Haskellといった関数型プログラミング言語の理論的基盤として、
その誕生に大きな役割を果たしたが、とうとうVisual Basicにまで搭載されたことで、今後、その重要性は益々増大するだろう。

次ページ