前回のコードにLetによる変数束縛を追加する。 gist.github.com コードの追加としては2行のみと非常に短い。 型 変更なし 式 追加するのはLetだけ： type exp = ... | ELet of string * exp * exp ELet(変数、変数を束縛する式、本体の式）という構成になっ…

前回のSTLC+Boolに自然数と関連する機能を追加していく。 gist.github.com 型 TNatという自然数を表す型を追加： type ty = ... | TNat 式 三種類の式を追加： type exp = ... | ENat of int | EAdd of exp * exp | EIsZero of exp 自然数リテラルを表すENat…

前回のSTLCにBool型と関連する式を追加してみる： gist.github.com まずは型にTBoolを追加： type ty = ... | TBool 式にTrue, FalseとIf式を追加： type exp = ... | ETrue | EFalse | EIf of exp * exp * exp If式はcondition式、if-true-branch式、if-fal…

前回Simple Boolからはじめると書いたのだが、よく考えると単純型付きラムダ計算（STLC）ではじめるのが当然な筋な気がしてきた。 ので急遽Simple BoolからBoolを取っ払ってSTLCだけをまずみてみる： gist.github.com 定義されるものとしては 「型」を表す型…

最近は言語処理系に関してまったく手を動かしていなかった＆ブログに何も書いていなかったので練習がてら・・・ Types and Programming Languagesには非常にたくさんの型システムの実例と関連したOCamlコードが載っている。ただし多くは写経したらそのまま実…

「関数型プログラミングが主流になりつつある」という話が（またしても）ツイッターで出ていた。LINQやらReactやらを引き合いに出した英語記事が議論の引き金のようだ。その話題の一部として「そもそも何をもって関数型プログラミングと呼んでいるのだ？」と…

前回に続きJOSSについて。今回は「オブジェクト指向」の名付け親、Smalltalkの設計者などで知られるアラン・ケイがJOSSに影響を受けたらしい、という話。 ACMインタビュー 私がJOSSという言語を意識し出したのはアラン・ケイの2004年のACMインタビューを読ん…

JOSSという言語とプログラミング環境があった、らしい。 en.wikipedia.org 初出は1963年、LISPの5年後でBASICの1年前である。RANDコーポレーションのJOHNNIACマシンを数学者が対話的に扱うための言語とシステムで、開発者はCliff Shaw。以前ブログで取り上げ…

気づいたらブログを更新しないまま6月が過ぎてしまった。 記事を書く上での自分の中の期待値とコストが増大していき、下書きで数千文字書いた時点で終わりが見えなくなってしまって放置する。そういうケースが３〜４本出てくると徒労感が募って手が出なくな…

逆説的でキャッチーなフレーズ「Worse is Better」の原点であるRichard GabrielのThe Rise of "Worse is Better"を再読したのでメモ。 概要 The Rise of "Worse is Better"は1989年にRichard Gabrielが書いた「Lisp: Good News, Bad News, How to Win Big」…

こういうツイートがあった Python君さぁ… pic.twitter.com/HDdQrSO8yp— not (@not_522) May 25, 2022 「まあ大体IEEE 754のせい」でほぼ終わる話ではあるのだけど、少し深掘りもしたのでちょびっと備忘録メモ。 問題を（少し順番を変えた上で）再掲すると： …

ツイッターでPythonの文法の話題が盛ん（三角関数と同じで周期的に話題になる）で、個人的にはあまり同意できない意見も多いのだがなかなか面白いトピックもある。 例えば以下のようなコード： fs = [] for i in range(5): fs.append(lambda: i) for f in fs…

ここ数年インターネットを徘徊していて見つけた「傑作論文集」をブックマークして部分的につまみ食いしたりしてきた。 自分用の備忘録として＆他の人にも有用かもしれない、ということで記事にしておく。 計算機科学全般 書籍だが、MIT出版の出しているIdeas…

John Backusという計算機科学者には大きな功績が三つある： IBMでFORTRANの開発を提案・主導したこと 構文の形式的な定義を可能とするBackus-Naur FormをALGOLの開発のために提案したこと チューリング賞受賞講演で、FORTRANのような命令型プログラミングか…

（注：あの頃というのは私が多感だった2000年代のことである） 最近マイクロソフトのRaymond Chenの「マイクロソフト社員がIBMに出向していた時に文化の違いに辟易してコーヒーメーカーに関して小さな反抗をした」というものブログ記事を見た。 devblogs.mic…

プログラミング言語理論の最初期の金字塔の一つ、The Next 700 Programming Languagesを読み直したので論文メモ。これは過去に何回か読み直している個人的にも非常に思い入れのある論文。論文メモ書きたいなとここ数ヶ月ずっと思っていた。 背景 The Next 70…

かなり前に、DijkstraとWirthがAPLの話をIversonから聞いて「俺たちの目が黒いうちはこんな言語は絶対流行らせない」と言ったという話をどこかで読んだ気がしていてソースを探していたのだけど、なかなか見つからずに残念に思っていた。 DijkstraがAPLのこと…

Graydon Hoareが2019年にカナダのブリティッシュ・コロンビア大学でコンパイラ関連のゲスト講義した時の資料21 compilers and 3 orders of magnitude in 60 minutes - a wander through a weird landscape to the heart of compilationを読んだら大変面白か…

時々ツイッターで俎上に上がる言説として「プログラミング言語は一つ学んだら大体全部同じ」という話と「お前HaskellやLisp見ても同じことが言えるの？」、そして「いやHaskellやLispだってそこまで違うわけじゃない」という一連の流れがある。 これで思い出…

Graham HuttonのHaskellを使ったプログラミング言語意味論のチュートリアル論文Programming Language Semantics - It's Easy as 1,2,3を読んだのでメモ。 HuttonはOCamlでMonadic Parserを作ってみる（前編） - Arantium Maestumの元ネタである「Programming…

ポール・グレハムの記事の一つにWhat Makes Lisp Different?というものがある： www.paulgraham.com ポール・グレハムらしくよく書かれていて、C言語などと比較した場合のLispの特徴をうまく捉えているように思う。 その中の一つが Recursion. Recursion exi…

John McCarthyの1960年に発表された論文Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part Iのメモ。 背景 「Artificial Intelligence」という用語の名付け親であるMcCarthyが、自身が助手らと作ったLISP言語を世に出し…

前回の記事でも紹介したOlin ShiversのT Programming Languageに関する回顧録で It had a big influence on Andrew Appel, at Princeton, who subsequently adopted a lot of the ideas in it when he and Dave MacQueen's group at Bell Labs built the SML…

CPS形式のコンパイラIRについて調べていてORBITというコンパイラについての話が出てきたので、1986年に出た論文ORBIT: An Optimizing Compiler for Schemeを読んでみた。 ORBITはGuy SteeleのRABBITというScheme Compilerから「CPS形式をIRとして使う」とい…

前回はSubstitution関連で少し寄り道したが、今回こそはPrincipal Type Schemes for Functional Programsの中核である type inference Robinson's unification algorithm algorithm W の話。 type inference For assumptions A, expressions e and type-sche…

前回「type inference、Robinson's unification, algorithm Wを見ていく」と書いたが、その前にsubstitutionについてつらつらと考えてみたい。 S is a substitution of types for type variables, often written [τ_1/α_1,...,τ_n/α_n] or [τ_i/α_i] とある…

Abstract machines for programming language implementationを読んだのでメモ。 どのようなAbstract Machineがどのようなプログラミング言語の実装に使われてきたのか、というサーベイ。2000年に書かれており筆頭著者はHaskell界隈ではそれなりに知られてい…

型推論のためのAlgorithm Wを実装するため、DamasとMilnerのPrincipal Type Schemes for Functional Programsを読んでいる。 重要そうな概念としては expression type/type-scheme substitution instance/generic instance assumption assertion closure typ…

少し前にTwitterで「面接で『なんで1byteって8bitsになっているのか？』と聞くといい」というツイートが話題になっていた。 それを見た時は「まあ8bitsだとは限らないよね、現在主流のアーキテクチャがそうなってるだけで」と思っただけで終わったのだが。 …

A正規化について非常に参考にさせてもらっているMatt Mightのブログ記事で A later transformation to continuation-passing style (like that in Appel's book) is also simplified if transforming from A-Normal Form. とあるので、これまでのA正規化され…