Lambda calculus - Wikipedia
Lambda calculus (also written as λ-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. Untyped lambda calculus, the topic of this article, is a universal model of computation that can be used to simulate any Turing machine (and vice versa). It was introduced by the mathematician Alonzo
ラムダ計算の勉強のしかた、プログラム意味論 - きしだのHatena
先日のエントリで手続きを記述するという側面と、式を記述するという2つの側面があるということを書きました。 プログラムの理論とはなにか そして、手続きの性質として代表的な、アルゴリズムについての勉強のしかたについてまとめてみました。 アルゴリズムの勉強のしかた そこで、今回は、式を記述するという側面の勉強のしかたと、あとこの分野は自分でもまだ全然勉強してなかったので、これからどういう本を読もうと思っているかをまとめてみます。 プログラム意味論 プログラムは必ずプログラム言語、少なくとも記号で記述します。*1 そこで、プログラムの勉強という点では、どのように動くかというアルゴリズムの勉強だけではなく、どのように書けるか、書いたものにどのような性質があるのかということも知る必要があります。 例えば、2005年あたりからRubyのような動的型付け言語が流行りだし、Javaなどの静的型付けの言語との
ラムダ計算 λ...
► 2022 (2) ► 10月 (1) ► 2月 (1) ► 2021 (51) ► 11月 (2) ► 10月 (2) ► 9月 (4) ► 8月 (4) ► 7月 (4) ► 6月 (4) ► 5月 (3) ► 4月 (10) ► 3月 (7) ► 2月 (4) ► 1月 (7) ► 2020 (155) ► 12月 (7) ► 11月 (10) ► 10月 (8) ► 9月 (8) ► 8月 (11) ► 7月 (21) ► 6月 (19) ► 5月 (14) ► 4月 (20) ► 3月 (13) ► 2月 (10) ► 1月 (14) ► 2019 (293) ► 12月 (11) ► 11月 (12) ► 10月 (24) ► 9月 (29) ► 8月 (27) ► 7月 (36) ► 6月 (40) ► 5月 (24) ► 4月 (35) ► 3月 (42) ► 2月 (6
チャーチ数とラムダ計算 - sirocco の書いてもすぐに忘れるメモ
検索していたら、きしだのはてな・おとうさん、ぼくにもYコンビネータがわかりましたよ！ という記事にめぐり逢って面白かったので Scheme 写経してみました。 ラムダ関数の表記 ラムダ関数は λx.x のように表記します。 λx.x λx.x*2(λx.x*2)y という関数は xの部分をyでおきかえると (λx.x*2)y → y * 2 となります。これを簡約といいます。 ;; scheme (lambda(x) x) ;=> #<closure #f> ((lambda(x) x) 2) ;=> 2 # ruby lambda{|x| x} #=> #<Proc:0xb77e75a4@(irb):1> lambda{|x| x}.call(2) #=> 2 -- Haskell > (\x -> x) 2 -- => 2 > :t (\x -> x) -- => (\x -> x)
おとうさん、ぼくにもYコンビネータがわかりましたよ！ - 2009-04-09 - きしだのはてな
やっと、Yコンビネータが何を意味するものなのか、どういう意義があるのかがわかりました。 名前を使わず再帰ができますよ！というだけのものじゃなかったのですね。 まずλありき 関数の話をしたいのです。 そのとき、いちいち hoge(x) = x * 2 としてhogeを・・・、とか名前をつけて話を進めるのがめんどうなので、関数を値としてあらわすと便利ということで、λという値を定義するのです。 そうすると、上のhoge関数なんかはλ(x)(x*2)などとあらわせますが、引数をあらわすのに()を使うといろいろまぎらわしいので、 λx.x*2 のように表記します。 というのがλ。 このとき、λになにかわたされたら、引数としてあらわされる部分を単純におきかえます。 (λx.x*2)y とあったら、xの部分をyでおきかえて (λx.x*2)y → y * 2 となります。λの引数部分を与えられた引数で置
404 Blog Not Found:TuringとChurchの狭間で
2006年04月16日13:53 カテゴリMath書評/画評/品評 TuringとChurchの狭間で The Emperor's New Mind Roger Penrose [邦訳:皇帝の新しい心] なんでひげぽんが反復がすぐにわからなかったかを憶測すると、「変数とは代入すべきもの」、という手続き型言語の呪縛が思い立つ。ひげぽんは別にがっかりする必要はない。hyukiさんさえそれに引っかかっていたんだから。 その証拠を、以下にお見せする。 [結]2005年8月 - www.textfile.org sub fix { my $G = shift; return $G->( sub { my $x = shift; return fix($G)->($x); } ); } これはPerlで実装した不動点関数で、全く問題なく動く。しかし、hyukiさんも知らぬ間に一つ「反則」を犯しているこ
今日から始めるJava8 - Taste of Tech Topics
こんにちは id:cero-t です。 「なんとやらは風邪をひかない」と言われているところ 先日、インフルエンザに掛かってしまいまして。 重ね着＋多段布団＋電気毛布２枚のコンボで一気に悪寒を吹き飛ばし、 一日で熱を下げたものの、感染予防のために出社を控えたために時間でき、 ちょっとJava8などと戯れていました。 そう、今日はJava8の話題です。 今年の秋に正式リリースが予定されているJavaSE8ですが、 OpenJDKのサイトでは、既にEarly Access版を入手することができます。 JDK8 : http://openjdk.java.net/projects/jdk8/ ダウンロード : http://jdk8.java.net/download.html 1/31に、マイルストーン6がリリースされ Feature Complete となりました。 名前からすると 全機能開発
Practical Scheme
Shiro Kawai 11/20/2000初出、3/29/2002更新 Cに慣れたプログラマがSchemeのコードを見て面食らうことのひとつは、 無名の関数やローカル関数の多用だろう。 特に実行効率に敏感なプログラマにとっては「関数呼出しは高価」 という感覚が染み着いているため、 至るところに散りばめられたlambdaに眉をひそめてしまうようだ。 しかしSchemeにおいては、 コード上に関数が書いてあるからといって 実行時にスタックフレームの生成やレジスタの退避などのオーバヘッドが起こるとは限らない。 例えば関数の最後に別の関数を呼び出す末尾呼び出し(tail call) はただのjumpインストラクションに置き換え可能だ。 ここでは、Cプログラマを対象に、 lambdaで生成される関数群が実際にどのように実行され得るのかを書いてみたい。 (なお、Schemeの規格ではlambdaフォ
Rubyのblock、Proc、lambdaを理解する - このブログは証明できない。
新年おめでとうございます。2009年の最初のネタはプログラミングのネタにすることにしました。 Rubyについてのステキなエントリーがあったので、紹介します。 no title 私は翻訳能力がないばかりか、リーディング能力も貧相です。ぜひ、原文を読んでみてください。 はじめに Rubyのblock、Proc、lambdaはパワフルですが、解りにくい。Rubyはクロージャを使う方法が4つあって、それぞれチョットずつ違います。ここでは、そのへんを解説したいと思います。 Block もっとも簡単で、かつRubyっぽいと言えば、Blockですね。 array = [1, 2, 3, 4] array.collect! do |n| n ** 2 end puts array.inspect # => [1, 4, 9, 16] 何が起こっているか？ まず、block付きでArrayの"collect
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://dspace.mit.edu/bitstream/handle/1721.1/6091/AIM-379.pdf?sequence=2