はてなブックマーク

この記事は言語実装 Advent Calendar 2020の16日目の記事です。 Prologに慣れていない人のためにPrologでの単相の型システムを示し、線形型システムであるSystem-Fo(Fポップ)およびアフィン型システムSystem-Fa(Fアフィン)を実装例を示します。 アフィン型システムというとRustのオーナーシップの型システムが近いのですが、Rustのような型システムの本質的部分を取り出して実装したものがアフィン型システムです。難解な型システムの数式は嫌がらせのように感じるかもしれませんが、Prologを使えば実際に動かせるのでより理解しやすいものになっているはずです。 1. 単相型システムとlet多相型システム まずは、Prologで単純な型推論を作ってみます: % simple.pl :- op(500,yfx,$),op(600,xfy,:),op(600,xf

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article?

:- op(1200,xfx,ならば). :- op(1000,xfy,かつ). :- op(750,xfx,[の環境で]). :- op(720,xf,[の要素]). :- op(700,xfx,が). :- op(700,xfx,[を評価すると,の型は]). :- op(20,xf,[で関数適用,が変数,が整数]). :- op(10,xfx,[を]). term_expansion(A ならば B,B:-A). A,B ならば A かつ B. integer(A) ならば A が整数. atom(A) ならば A が変数. B is A ならば A が B. A が (_,A) の要素. A が E の要素 ならば A が (E,_) の要素. % 評価規則 I が整数 ならば _ の環境で I を評価すると I. E の環境で T1 を評価すると V1 かつ E の環境で T2 を

概要 プログラミング言語を簡単に作ることはPrologが有用であることを示し、Prologの使い方を説明し、実際にPrologを使って簡単な文法定義を行い、インタプリタを作り、型検査器を作ります。構文定義には正規木文法の定義ライブラリを示します。 todo: パーサ作る必要もないことも書く BNFの読み方を説明する 自然演繹の読み方を説明する Prologのアリティについて説明する 1. はじめに プログラミング言語は、プログラマが１度は作ってみたいと夢見るものの１つです。しかし、なかなか簡単に作れるものではありません。一体どうすれば簡単に言語を作ってみることができるのでしょうか？ 以下のような四則演算の言語(図1)を考えましょう: \small \begin{array}{c} \begin{array}{ll} \text{構文}\\ \begin{array}{lcll} t & :

これは ML Advent Calendar 2017 の 4日目の記事です。VS Code も絡むのでそっちにも登録してしまいましたｗ はじめに MLを使いならば、操作敵意味論を理解しなくてはならない。 操作敵意味論を理解するには、論理型言語を理解しなくてはならない。 MLでPrologを実装できれば論理型言語を理解していると言ってよいはずだ。 論理型言語の動作を理解するためにはデバッガがあると便利なはずだ。 しかし、デバッガを作るノウハウが我々にはない。 よって、我々はOCamlによるデバッガを作るサンプルを作成することにしたのである。 1. VS コードのデバッガサンプル(PHPバージョン) これは簡単なアセンブラ言語を作ってそのデバッガを作るサンプルプロジェクトである。 通常は、TypeScriptでDebug Extensions を書くのですが、簡単な標準入出力で VS Cod

この記事はhttp://qiita.com/advent-calendar/2015/english_translation の18日目の記事です。 今日は、翻訳の量をこなす事は難しい事に付いて書きたいと思います。 漫画とイラストは違います。アニメーションとイラストも違います。 イラストは描けても、漫画を描くのは難しいんです。何が違うのかというと量が違います。 1枚絵はより完璧な絵を描く事が出来ます。でもですよ、、、例えばモナリザのクォリティで漫画やアニメを作る事を考えてみてください。 そりゃ無理ってもんが有りますよね。。。 長い文章を理解するにあたってすべてを逐一正確に翻訳するのは大変です。 自分はよく、適当に翻訳した文章を置いておいたりします。そういう文章をくその山と呼ぶ人もいます。でもそのくその山も作るのは大変なのです。そして、くその山を読むだけでも何となく把握出来る物が有るのも事実

はじめに 言語を作る場合には BNF があり操作的意味や型付け規則を定義してあると説得力が増します。シークエント計算の推論規則は長方形に収めることが出来るので、２次元的に図として書くにはとても便利な記述方法です。しかし、読み書きするには、よく知られている処理系がないのでなかなか覚えることが出来ない人も多いのではないでしょうか？ \begin{array}{lr} 評価 & \bbox[3px,border:1px solid black]{\;t \longrightarrow t} \\[-30px] \hspace{250px} \\[-30px] \end{array} \\ \begin{array}{cr} \dfrac{ t_1 \longrightarrow t_1' }{ t_1\;t_2 \longrightarrow t_1'\;t_2 } & \text{(E-App

バッカスナウア記法の説明はたくさん存在しています。しかし、プログラミング言語を作ろうとしている人にとっても、なんだかめんどくさいなぁと思う人は多いように感じます。正規表現はそんなに嫌いじゃないけどBNFは嫌だ。言語を作るのは楽しいけど、仕様書くのはめんどくさい。そんな人も多いと思います。正規表現は歴史を知らずにつくり方を知らずに使っている人も多いでしょう。歴史的経緯は置いておいて、正規表現の拡張としてBNFを捉えればそんなに難しくないと思えるようになるのではないかと思い、この文章を書きました。 正規表現 プログラミング言語を作るのであれば、正規表現は知っていたほうが良いでしょう。 正規表現は、文字列操作をする上で便利な記法です。 Webブラウザ上でもJavaScriptを使って簡単に試すことができます。 たとえば、整数は以下のように表すことができます。

はじめに 以前、Rust0.7でコンパイラを作成してみたのですが、Rust0.11までバージョンが上がり、動かなくなってしまいました。開発中の言語の変更なので仕方ないのですが、Rustを参考にしたいのに、使い方が良くわからないと困るのでRust0.11に対応してみました。 エラーワーニング対策 マクロ、use,EAddという大文字で始まる関数を許可する為に以下のアトリビュートを使います。 #![feature(macro_rules)] #![feature(globs)] #![allow(non_snake_case_functions)] メイン関数 以前、~aと書いていた、~はboxと書くようになりました。boxと書くとヒープに値を取り、ポインタを持つようになります。 println!は出力マクロですが、{}に引数を展開します。 interp::evalがインタプリタで、virtu

#include <stdio.h> void print_i(int i) { printf("%d\n", i); } int main() { print_i(1); } この辺をコンパイルしてみると、こんなのが作れます。 %rax %rbx %rcx %rdx %rdi %rsi %rsb %rbp 等の64bitのレジスタがあります。%raxはアキュムレータと呼ばれます。x86_64の呼び出し規約では関数の返り値が%raxに入れる事になっています。 引数も、6個くらいまでは、レジスタで渡すようになっています。それ以上の場合はスタックに積んで渡します。 x86の場合は呼び出し規約にも寄りますが、基本的にレジスタ数が少ないのでスタックに引数を積んで呼び出す事になります。 ; プログラムのエリアの始まり .section __TEXT,__text,regular,pure_instr

はじめに 昨今のプログラミング言語では型が重要だってことは間違いない。 そして、型理論がその一翼を担っている。 しかし、型理論ってのはそれ専用の記法で書かれている。 焦るとまったく分けの分からない物と目に映るだろう。 例えば以下の式を見よう。 Γ |- t1 : T1 -> T2 Γ |- t2 : T1 -------------------------------------- Γ |- t1 t2 : T2 この式の意味は、t1の型がT1->T1でt2の型がT1の時、関数t1にt2を適用した値の型はT2になるという意味である。 と、書かれても訳の分からない事が書かれていると思うはずだ。 分かっている人からすると正しくない文章だとなるだろう。 なぜ、正しくないのか？ なぜ、難しいのか？ 難しいと感じるという事 実のところは難しいというのは、実は必要なら覚えるが必要でなさそうだから覚える