カリー・ハワード同型対応入門
takuro.onishi@gmail.com II 2009 6 4 11 • Figure: H.B.Curry (1900-82) Figure: W.A.Howard (1926-) • 1934 1958 • 1968 • • • • • • • • • • • • • • • • • • • • 3.6 (an)n (an)n (an)n 3.5.1 (an)n (an)n 3.5.2 (an)n (an)n (an)n • ( 1980, pp. 26-27) • ABCD ABCD ABCD 4 A, B, C, D ABCD ABCD ABCD n 4 n 2 n 4 m n = 4m n = 2 × 2m k = 2m n = 2k n 2 n 4 n 2 • • • • ⇒ • • 19 • • • Figure: G.Frege (1848-1925) • 1879
再帰的な構造のデータの同値性判定はどうしたらいいか - 貳佰伍拾陸夜日記
数日前にTwitterで, JavaScriptのオブジェクトに対する===の挙動が初心者には難しいみたいな話を見かけた. 発端や周辺の議論をちゃんと追いかけてないからとくに出典は貼らない. たぶん元々の話は「へぇ, こういう挙動なんだ, 簡単ではないね」くらいの話だったのかもしれない. 自分のタイムラインの観測範囲では「そうだそうだ, (参照の同一性ではなく)同値性にしとけばいいのに」と思っている人もそれなりにいそうに見えた. 個人的にも同値性が簡単に確認できるとよい気はするものの, 「なんでそうしないんだ, オブジェクトの中身を確認していくだけだろ!」みたいな簡単な話ではないことも知っているため, 以下のようなツイートをしたのだった. JavaScriptのオブジェクトの同値性、再帰的な構造とか作るとぜんぜん自明じゃないんだよなぁ。リンクの構造は違うけどプロパティを辿ったときのパスはど
Implementing functional languages: a tutorial - Microsoft Research
This book gives a practical approach to understanding implementations of non-strict functional languages using lazy graph reduction. The book is intended to be a source of practical labwork material, to help make functional-language implementations `come alive’, by helping the reader to develop, modify and experiment with some non-trivial compilers. The unusual aspect of the book is that it is mea
現代のオブジェクト指向の class の割れ窓化と宣言的プログラミング
オブジェクト指向には、カメラがやっとついたころのガラケーのイメージがある - きしだの Hatena の件。基本的には同意。ただちょっと切り口が違うので自分の意見を言っておく。ただ、このテーマで何度か書こうとして失敗していて、今回も成功しているとはいえない。 宣言的プログラミングの時代 現代の主流は「宣言的プログラミング」であると思っている。これはリソースの宣言と、その状態遷移の手続きや振る舞いの付与が中心にある。 宣言型プログラミング - Wikipedia その代表的な例がフロントエンドの React と、バックエンドの k8s で、どちらも時系列に基づいた状態の宣言と、フレームワーク側による状態遷移処理、 Reconcillation(調停) が基礎にある。 フロントエンドとバックエンドという両極端な世界で、この変化が起きたのがこの時代を反映したものであると思う。 例えば、jQuer
Command Line Interface Guidelines
Contents Command Line Interface Guidelines An open-source guide to help you write better command-line programs, taking traditional UNIX principles and updating them for the modern day. Authors Aanand Prasad Engineer at Squarespace, co-creator of Docker Compose. @aanandprasad Ben Firshman Co-creator Replicate, co-creator of Docker Compose. @bfirsh Carl Tashian Offroad Engineer at Smallstep, first e
マルチスレッド・プログラミングの道具箱
まえがき クラウド上の仮想サーバから手元のスマートフォンまで、いまや複数のCPUコアを搭載するマルチコアはどこにでもある環境になりました。ハードウェア側が並列(Parallel)・並行(Concurrent)処理に向けて急速に進化する一方で、ソフトウェア側つまりプログラミング言語の進化はさほど追い付いていません。並行処理記述の手軽さを求めた Go言語 や、マルチスレッド処理の安全性を重視する Rust言語 などが登場してはいるものの、「普通にプログラムを記述するだけで複数CPUコア環境で高速に走るプログラミング言語」は遠い夢物語のままです。 モダンなプログラミング言語や並列・並行処理ライブラリは、複雑で難解なマルチスレッド処理を直接記述しなくてすむよう、安全性・利便性の高い抽象化レイヤを提供します（例：Go言語のgoroutineとchannel、Rust言語の Rayonライブラリ）。し
プログラミングコンテストでの乱択アルゴリズム
前編 (平衡二分探索木編) はこちら http://www.slideshare.net/iwiwi/2-12188757
競プロerのための群論 (swapと順列と対称群) - little star's memory
お知らせ Zennに移植しました。今後こちらの記事は更新されず、Zennの方のみ更新します。 zenn.dev この記事では競技プログラミングと群論に関する解説をします。競技プログラミングの問題を群論という立場から見ることで、新たな視点を得ることができるようになると思います。また、群論の入門にもなればいいなと思っています。 swapと順列 競技プログラミングの問題に、swapと順列は多く登場します。swapとは、2つの要素を入れ替える操作のことです。例えば、次のような問題があります。 第二回全国統一プログラミング王決定戦予選 C - Swaps (問題ページ) $ N $ 要素からなる2つの整数列 $ A_1,\ldots,A_N $ および $ B_1,\ldots,B_N $ が与えられます。以下の操作を $ N-2 $ 回まで(0回でもよい)行うことで、1以上 $ N $ 以下のすべ
精進について - kyopro_friends’ diary
サーバルだよ！ 競プロの精進について書くよ。 精進の仕方や、精進に対する考え方はいろいろあるから、あくまで私の意見だと思って読んでね。 ■3行でまとめて ・復習が大事。解けた問題も解けなかった問題も、解説やいろんな子の実装を見てみる ・典型を身につけるのは大事。ABCは解説ACでもいいので解く ・写経はできればしない。一回自分で書いてみてから他の子の実装をパクる ■モチベーションについて レートがついて他の子と競う以上、やっぱりレートが下がると面白くないよね……。 私も最近は下がってこそないけど全然上がらなくて面白くないよ……。 モチベーションが低いときに無理してコンテストに出ても成績は悪くなりがちだから、そういう気分のときはしばらくコンテストに出ないというのももちろんありだよ。 だけど、私には「コンテストに出て悔しい思いをして、解けなかった問題をちゃんと復習する」って方が合ってるから、で
プログラミング言語の習熟 - steps to phantasien
C++ を書いていると、数年のブランクがあるにもかかわらず妙な安心感がある。自分は間違っていない、というと語弊があるが、自分の間違っている程度を自分はわかっている、というような。コードの質もなんとなく高い気がする。 仕事で Android アプリの Java を書いているときはそこまでの confidence を感じない。そこそこだろうとは感じている。 Python とか JS を書いていると、我ながらこのコードはダメだなと思う。しかしどう良くしていいか検討もつかない。似たような話を前に書いた気がする。 最近のモダンメインストリーム言語、すなわち Go, Swift, Rust, TS とか全然使えない。Kotlin は Better Java として使っている範囲ではそこそこだと思いつつ、Kotlin を活かしている感じはない。 自分は学生時代、 C++ の習得に莫大な時間を費やした。学
Goodbye, Clean Code — Overreacted
It was a late evening. My colleague has just checked in the code that they’ve been writing all week. We were working on a graphics editor canvas, and they implemented the ability to resize shapes like rectangles and ovals by dragging small handles at their edges. The code worked. But it was repetitive. Each shape (such as a rectangle or an oval) had a different set of handles, and dragging each ha
すべてのプログラマーが試すべき挑戦的なプロジェクト
Austin Z. Henleyのブログより。 更新12/14: この投稿は、Hacker NewsとRedditに関する多くの議論に拍車をかけました。 提案されたプロジェクトのいくつかを収集し、この投稿の最後にリストに入れました。 私はよくサイドプロジェクトを始めたいが、何を作るべきか分からない多くの学生やプロの開発者と話します。以下は、私に多くを教えてくれたいくつかのソフトウェアプロジェクトです。実際、それらは何度も作ることができ、毎回新しいことを学ぶことができるので素晴らしいです。従って、何を作るのか分からない場合、または新しいプログラミング言語またはフレームワークを学びたい場合は、私は次のいずれかから始めます。 テキストエディタ 2Dゲーム - スペースインベーダー コンパイラ - Tiny BASIC ミニ・オペレーティング・システム スプレッドシート (難しい!) ビデオゲーム
AtCoderで青色になるまでにやったこととプログラマー35歳定年説 - kusano_k’s blog
https://atcoder.jp/users/kusano はい。 みんな「AtCoderで○色になるまでにやったこと」みたいなタイトルで、右肩上がりのレートのグラフとともに楽しそうな記事を書きやがって。 こちとら2年かけてジワジワとレートが下がり、とうとう下の色に変わってしまった。 これがやりたかっただけなので、競技プログラミング力の向上に繋がる有益な話は、この記事にはほとんど無い。 解答を清書してブログに解説記事を書くというのはオススメだけど。 私と競技プログラミング 「○色になるまで」という記事には、いつ頃から競技プログラミングを始めて、○○年頃には何をしていたか、みたいなことを書くものらしい。 Cマガ電脳クラブ 今の競技プログラミングとはちょっと違うけれど、「Cマガ電脳クラブ」が最初だろうか。 今は無きC MAGAZINEという雑誌があり、その中の「Cマガ電脳クラブ」というコー
AtCoderで赤になるまでにしたこと - てんぷらのぷらはC++のぷら
赤コーダーになりました！！！！ チュートリアル修了！！！！！ pic.twitter.com/WMPzYqnfrL — てんぷら (@tempura_cpp) September 21, 2019 ひとつの到達点なので。 自己紹介 ・京都大学理学研究科M2(数学系) ・公立高校出身 ・ぎりぎり数オリ勢(春合宿参加1回で数オリ勢名乗るのおこがましい) ・競技プログラミングも含めてプログラミングを始めたのは2018年1月から(当時B4) したこと 問題を解いた Solved By tempura0224 TopCoder: 19 CodeForces: 432 AtCoder: 1076 AOJ: 181 yukicoder: 95 Sum: 1803 https://t.co/JyHa0kaQ4F — てんぷら (@tempura_cpp) September 23, 2019 1800問く
Programming Idioms
Show me an idiom Looking for something? Search 300+ idioms
Cの可変長引数とABIの奇妙な関係 - Qiita
printf に関する以下のツイートが流行っていました。 上のツイートでは割とあっさり説明されていますが、amd64 SysV ABIでこの現象が起こる理由にはもっと深遠なものがあると思うので、可変長引数とからめて説明してみたいと思います。 前提条件として「ABI」「可変長引数」「non-prototyped関数」の知識が必要なのでそこから説明します ABIとは ABI (Application Binary Interface) とは、機械語レベルでのインターフェースのことです。 機械語そのもののルールはISA (Instruction Set Architecture) によって規定されていますが、たとえばC言語の「関数呼び出し」などの概念を機械語でどのように表現するかについては規定していません。そのルールを定めたのがABIです。したがって、ISAとABIはおよそ1対多の関係にあります
過去のブーム（並列プログラム）の現状を考える
みんな割と未来の予言はよくするが、あんまりその結果を振り返らんよなぁ。 現在のディープラーニングのブームをどう捉えるか、というか、 プログラマのキャリアという点でどう接していくか、を考えるにあたり、 過去のブームを考えてみるのは良いんじゃないか、という気がした。 最近並列GCや並行GCの章を読んでいて、 一昔前の大きなブームとしてはParallel computingがあったなぁ、と思い出した。 ということでこの事について、専門にしてなかった部外者プログラマの目にどう映ったかを記しておきたい。 なお、「XXXだと言われていた」はあんまりソースとかを確認したりはしてません。 なんとなく自分はそう聞いていた気がしたしそう思ってた、程度のものです。 かつて思っていたことと当時の状況 Parallel computingはだいたい10年くらい前の時点ではその後の大きなトレンドとして明らかに存在して
『微分可能プログラミング』はどこから来たのか - bonotakeの日記
はじめに（8/3追記） この記事を一旦書いたあと、重要な追加証言が得られたため、追記修正しています。結論もやや変わっていますが、現時点のほうがより正確です。 本編：ここから ディープラーニングが現在これだけ流行っている1つの要因は、TensorFlowやPyTorchなどのフレームワークが非常に便利だからです。ニューラルネットワークの設計、訓練、そして分類などの推論がフレームワークを使えばとても簡単に行なえます。 普通に使っている人達は、これらのフレームワークを『ツール』あるいは『ライブラリ』だとみなしていると思います。でも実際のところ、これらはプログラミング言語です。より正確に言えば、すべてのディープラーニングフレームワークはディープラーニング計算用DSL（Domain-Specific Language、ドメイン特化言語）と見なせます。このDSLは大抵、Pythonなど他の汎用言語への
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
競技プロ的なアルゴリズムのスライドのまとめ Wiki - yukicoder
AtCoder Problems