λ計算とは コンピュータの人気・最新記事を集めました - はてな
まず無限個の変数が与えられているとする。変数は通常x, yなどど記述される。変数から出発し、次の操作を繰り返して得られるものをλ式と呼ぶ。 λ抽象 λ式Mと変数xから、式λx. Mを生成する操作。これは、変数xに引数を受け取り、値Mを返す関数を意図する。Mに含まれる変数xはこのλにより束縛されるという。ただし、すでに束縛されているものは除く。 関数適用 二つのλ式M, Nを並べて結合した式MNを作る操作。これは式Mが表す関数に引数としてNを与えることを意図する。 またλ抽象や関数適用の範囲を明確にするために括弧を用いる。 例: (λx. xx)(λx. xx),λf.(λx.(f (x x)) λx.(f (x x)))
突発簡単チュートリアル２：λ計算の操作的意味論 - sumiiのブログ
（5/24追記：「λ式とは何か」「β簡約とは何か」あたりは前提知識としています。その部分については、自己引用ですみませんが授業のレジュメや、はてなキーワードのyoriyukiさんによるλ計算についてのエントリなどをば。） ちょー間が空いてしまいましたが、突然再開。λ式 M ::= x | λx.M | M1 M2 の操作的意味論というと、 (λx.M1)M2 → [M2/x]M1 M1→M1'ならばM1 M2 → M1' M2 M2→M2'ならばM1 M2 → M1 M2' M→M'ならばλx.M → λx.M' という帰納的定義によるsmall-step reductionが「普通」です。プログラミング言語を意識して、閉じた式かつ（たとえば）call-by-valueに限ると V ::= λx.M M ::= V | x | M1 M2 (λx.M)V → [V/x]M M1→M1'なら
ラムダ計算の勉強のしかた、プログラム意味論 - きしだのHatena
先日のエントリで手続きを記述するという側面と、式を記述するという2つの側面があるということを書きました。 プログラムの理論とはなにか そして、手続きの性質として代表的な、アルゴリズムについての勉強のしかたについてまとめてみました。 アルゴリズムの勉強のしかた そこで、今回は、式を記述するという側面の勉強のしかたと、あとこの分野は自分でもまだ全然勉強してなかったので、これからどういう本を読もうと思っているかをまとめてみます。 プログラム意味論 プログラムは必ずプログラム言語、少なくとも記号で記述します。*1 そこで、プログラムの勉強という点では、どのように動くかというアルゴリズムの勉強だけではなく、どのように書けるか、書いたものにどのような性質があるのかということも知る必要があります。 例えば、2005年あたりからRubyのような動的型付け言語が流行りだし、Javaなどの静的型付けの言語との
「ラムダ計算」を独学で学習するための，講義ノートやPDFのリンク集 （復習用の問題付き） - 主に言語とシステム開発に関して
講義ノートの目次へ ラムダ計算は，コンピュータ・サイエンスの重要な１分野。 「λ」を使って各種の関数を記述し，λどうしの計算方法を習得すれば・・・ HaskellやF#などの関数型言語を習得するために役立つ。 プログラミングにおいて，関数についての理解を深めることができる。 複雑なアルゴリズムを簡易に記述して，挙動や性質を予測することができる。 計算機科学の，より深い専門的な話題を理解するための足がかりを得られる。 などのメリットがある。 下記に，独学でλ計算を勉強するための， 入門レベルの講義ノートやWebページを掲載する。 読みやすい便利なもの・わかりやすいものから，応用的なものへと並べてある。 質の高いものだけを精選し，わかりづらい資料は除外してある。 ラムダ計算の概要 ラムダ計算の基礎 ラムダ計算の応用 復習のための問題（入門レベル） ※λ計算を利用した計算量・計算複雑性・計算可能
もしもラムダの中で例外が発生したら（前編） - Taste of Tech Topics
ある日、 id:cero-t がJJUGの重鎮たちと話している中で、とある宿題をもらいましたとさ。 「Java8のラムダの中で例外が発生したら、どうなるんだろう？」 こんにちは、アキバです。 もう皆さんはJava8を使ってみましたか？ とりあえずインストールしてみた人！ ・・はーい (おまえか という冗談はさておき、 今回は、id:cero-t に代わって私が冒頭のお題を調べてみました。 1. SerialStreamで動かしたラムダで例外が発生したら まずは、小手調べにシングルスレッドの場合を見てみましょう。 検査例外が発生するようなコードをラムダに書いてみると、コンパイルエラーになります。 こんなコードです。 try (BufferedWriter writer = Files.newBufferedWriter(Paths.get(W_FILENAME))) { // writer.
「関数型Ruby」という病(6) - 関数合成と文脈、Proc#liftとProc#>=、そしてモナ - ( ꒪⌓꒪) ゆるよろ日記
前回から一年以上が経過しているけど、最近lambda_driver.gemに機能を追加したので、そのことについて書こうと思う。 Rubyで、モナ……っぽい関数合成を実装した話だ。 Rubyで関数合成とかしたいので lambda_driver.gem というのを作った - ( ꒪⌓꒪) ゆるよろ日記 関数合成 関数合成については以前に書いたので、こちらを見て欲しい。 「関数型Ruby」という病(2) - 関数合成 Proc#compose - ( ꒪⌓꒪) ゆるよろ日記 おさらいをしておくと、関数合成とは、 関数gと関数fから、g(f(x))という関数hを新たに作り出すことだ。 (g ∘ f)(x) = g(f(x)) 関数gと関数fの合成関数g ∘ fに引数xを渡した結果は、関数gにf(x)の結果を渡したものと等しい。つまり、このような操作である。 f = lambda{|x| x + 1
Java 8を関数型っぽく使うためのおまじない - きしだのHatena
やあ、３月に延期になったとはいえ、Java 8リリースが具体化してきましたね。 もうこれで、Lambdaがはずれるとかいうことはなさそうです。 ところで、Java 8で関数型っぽいことができるようになってうれしいのですが、ちょっと記述が冗長です。ということで、短く書けるおまじない考えてみました。 Function型 さて、まずはJava 8で標準で入ったFunction型をみてみましょう。パッケージ名まで含めるとjava.util.funciton.Functionです。 こんな感じで使います。 Function<String, String> enclose = s -> "[" + s + "]"; Genericsでの型指定の最初が引数、あとが戻り値の型です。ここではStringをとってStringを返す関数としてencloseを定義しています。 これを呼び出そうとすると、こんな感じ
[C#][ラムダ式][LINQ][式木] 匿名メソッドとラムダ式の違い (プログラミング C# - 翔ソフトウェア (Sho's))
この記事では、匿名メソッドとラムダ式の意味の違いについて考えてみたい。 ■ 同じように使える匿名メソッドとラムダ式 匿名メソッドとラムダ式は、同じように使うことができる場面が多い。 例えば、以下のようなデリゲートを引数にとるメソッドがあったとして、 using System; using System.Collections.Generic; static class Enumerable { // 述語に基づいて値のシーケンスをフィルター処理 public static IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) { foreach (var item in source) { if (predicate(item)) yield
Church numerals と Lambda Calculus アルゴリズムとデータ構造入門 補足
Church Numerals と Lambda Calculus アルゴリズムとデータ構造入門 補足 後半は佐藤雅彦先生に教えてもらいました. SICP Exercise 2.4 〜 Exercise 2.6 誤解を恐れずに大雑把にいうと, λ計算では名前つきのシンボル (名前付きの手続き) による再帰呼出しや special form が使えないところが Scheme と違うところです. そのため, λ計算を Scheme で行うためにはいろいろな工夫が必要となります. そのポイントは closure (閉包) と呼ばれる構造です. 自然数 n の Church numeral を c(n) とすると, c(n) f x = (f ... (f x)), ただし, f は n 回出現. となることを利用します. まず, c0 と successor を定義します. (SICP Ex.
Combinator Birds
((S(K((S((SK)K))(K((S(K(S((SK)K))))K)))))((S(K((S(K((S(KS))K)))((S(KS))K))))((S(K(S((SK)K))))K)))
F#入門
コンビネータ ラムダ計算の親戚みたいな理論として、コンビネータ理論がありますが このページの趣旨は、理論的なことはさておき コンビネータを使って遊んでみようというものです。 例えばコンビネータを使うと 「引数の順序を入れ替えたり、入れ替えて適用する」 といったことができます。 なお、ここではλ式について少し知識があることを仮定しています。 最初にコンビネータとは何かというと 「自由変数を含まないλ式」、と定義されています。 自由変数とはλ式において束縛されていない変数のことで letによる関数定義をλ式の定義とみなすと 引数が束縛変数、 既に定義されてる識別子が自由変数 になります。 コンビネータに関する本として スマリヤンの本「To mock a mocking bird」 (邦題：数学パズル ものまね鳥をまねる―愉快なパズルと結合子論理の夢の鳥物語) は有名です。 この本の楽しいところ
Y Combinatorを直感的に理解。しようと試みる。 - このブログは証明できない。
id:yuji1982さんのエントリ。 Y Combinatorが凄すぎる！ - yuji1982の日記 なにこれ。Y Combinatorすげぇ！意味わからん。 今朝、妻からメールが来ました。 静かに歩く犬は犬じゃない。私の夢に出てきたフレーズ。 意味わからん。でも、それ以上にY Combinator意味わからん。 普通にフィボナッチ数を計算するプログラムは、こうですよね。 static int fib(int n) { if (n < 2) { return n; } else { return fib(n - 1) + fib(n - 2); } } これを、C#のクエリ式で書くと。 static int fib(int num) { Func<int, int> f = null; f = n => (n < 2) ? n : f(n - 1) + f(n - 2); return
Y コンビネータって何？ - IT戦記
このエントリの 親友へ。ブログを書こう。 - IT戦記 y がブログを始めたみたいなので、読んでみた。 で、最新のエントリを読んでみたら、 Y コンビネータというものについて書いてあったので、 Y Combinatorが凄すぎる！ - yuji1982の日記 Y コンビネータって何ってところから、自分でもいろいろ考えてみた。 結局なんなのかさっぱり分からなかったんですが、自分が考えたことをまとめておく まず、フィボナッチ数を求める fib を定義する var fib = function(n){ return (n <= 2) ? 1 : (arguments.callee(n-1) + arguments.callee(n-2)); }; fib(10); おお！ JS すげー！名前は n しか使ってねーよ！ めでたし、めでたし。。。。じゃなくて！ JS が素晴らし過ぎて話が終わってしま
C++のテンプレートでラムダ計算と型推論 - 貳佰伍拾陸夜日記
C++のテンプレートを, コンパイル時に走るプログラムを記述するための言語だと思うと, この言語はチューリング完全なので, 当然ラムダ計算のインタプリタを実装できるし, そのラムダ計算の項の型を推論することもできる. できるからと言って馬鹿みたいにやってしまったという話. ソースコードは末尾. テンプレートメタプログラミング テンプレートをプログラミング言語だと思うと, 構文はともかく, 副作用がなく関数(っぽいもの)を淡々と定義してパターンマッチして再帰呼出しして, という感じでとても関数型っぽい. 関数と返り値 テンプレートメタプログラミングではテンプレートクラスを関数だと思って使う. そして返り値はtypedefして返す. たとえば任意の型S, Tを受け取って前者を返す関数firstは template<typename S, typename T> struct first { t
ラムダ計算基礎文法最速マスター - 貳佰伍拾陸夜日記
ラムダ計算は, 多くのプログラミング言語, とくに関数型言語の原形になっています. ラムダ計算について理解しておくことは, 多くのプログラミング言語の習得に役立つでしょう. ラムダ計算はチューリング完全で, 計算能力としてはふつうのプログラミング言語と同じです. ラムダ計算で計算を書く訓練をしておくことは, 任意の計算を関数のみを使って(他の制御構文を用いずに)書くときに役立ちます. ふつうに書いたら煩雑な処理を, 関数型言語のやり方で書くとすっきりすることが多々あり, コードを自由自在に書くためには必須の考え方と言えるでしょう. 項 ラムダ計算の式を項(term)と言います. 項は変数, 抽象, 適用のいずれかです. 変数 変数(variable)はふつう1文字で書きます. 変数には関数内の束縛変数(bound variable)か自由変数(free variable)かという区別があり
カリー化 != 部分適用 - kmizuの日記
最近、ネット上でカリー化に関する記事を読んでいると、特にGroovy界隈でカリー化に関して誤解がまかり通っているようなので(特に実用的なGroovy: カレー化クロージャーによるファンクショナル・プログラミングはひどい。そもそも、Groovyの標準ライブラリ自体がカリー化を行うための関数ではないものにcurryとか付けてるから仕方無いのかもしれんが)、一言言っておく。 カリー化というのは、Groovyで言うと、 def add = {x, y -> x + y} のように、xとyという複数の引数を取って値を返す関数を def add = {x -> {y -> x + y}} //間違ってパースできないコードになっていたので修正(12/17) のように、一つの引数xをとって、「yを引数にとって値を返す関数」を値として返すような関数に変換すること、あるいは最初からそのように表現することを言う
d.y.d. 文字コード＆ベイズ推定
12:21 06/05/28 うたひめ 先日の記事に書いたように KOKIA にハマりまして、 とりあえず片っ端から聴いてみることにしました。まずは 1st アルバムの 『songbird』 から … …４曲目の "白い雪" ヤバい。超ヤバい。なんだこれ。ツボすぎる。 ベスト盤を聴いたとき感じた揺らぎなく落ち着いた歌唱力的な曲を期待して聴きはじめたら、 予想外の声質の歌が飛び込んできてびっくりしました。もちろん抜群に巧いのに かわりはないんですが、ずっと儚げな、ガラス細工みたいなイメージの、ああ、その、 つまり白い雪みたいな雰囲気の綺麗な声で。その声と奇跡的にマッチしたメロディ。 すごいなあ。９曲目の "ありがとう…" もベスト盤でのリテイクと比べて同じ印象で、 Amazonのreview で TenderBerry さんという方が近いことを書いておられました。 しかし書いてて自分の語彙の
翻訳:プログラミング言語Unlambda
このページでは、Unlambda公式サイトの翻訳を試みます。 http://www.madore.org/~david/programs/unlambda/ 基本的に超訳です。 訳の正しさは全く保証されません。 訳のおかしい部分は多数あります。 翻訳元サイトの許可を取ったりはしていません。 無認可です。 まだ翻訳途中です。 しかし、途中でへばりました。すみません。 プログラミング言語Unlambda Unlambda: 関数型言語の悪夢がやってくる (訳注: この訳は、 http://hw001.gate01.com/eggplant/tcf/unlambda/ から貰いました。) 目次 プログラミング言語Unlambda目次Unlambdaワールドの最新情報イントロダクションUnlambdaとは何かUnlambdaはどういう姿をしているのかUnlambdaのルールその他の難読化プログラミ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
More preview enhancements for Windows Azure AD Premium - Active Directory Blog - Site Home - TechNet Blogs