A Proposal for an Interactive Shell Based on a Typed​ Lambda Calculus

Presented (non-peer reviewed):
* IPSJ SIGPRO 2020-4-(3)
* https://sigpro.ipsj.or.jp/pro2020-4/program/

Paper (arXiv):
* https://arxiv.org/abs/2104.03678

Source code on GitHub:
* https://github.com/kekyo/Favalon

Abstract:
The paper presents Favalon, a functional programming language built on the premise of a lambda calculus for use as an interactive shell replacement. Favalon seamlessly integrates with typed versions of existing libraries and commands using type inference, flexible runtime type metadata, and the same techniques employed by shells to link commands together. Much of Favalon's syntax is customizable via user-defined functions, allowing it to be extended by anyone who is familiar with a command-line shell. Furthermore, Favalon's type inference engine can be separated from its runtime library and easily repurposed for other applications.

Transcript

1. A Proposal for an Interactive Shell Based on a Typed Lambda Calculus IPSJ SIGPRO 2020-4-(3) Kouji Matsui / 松井 幸治 (k@kekyo.net) The Open University of Japan /放送大学大学院 文化科学研究科 IPSJ SIGPRO 2020-4-(3)
2. Agenda 1. シェルシステムの課題 2. 研究の概要 3. 静的型付けの方法 4. 型による拡張と連携 5. まとめ IPSJ SIGPRO 2020-4-(3) Kouji Matsui 2
3. 3 IPSJ SIGPRO 2020-4-(3) Kouji Matsui
4. シェルシステムの課題 Bash等の既存のシェルシステムの特徴 ⚫ 理解しやすく、簡便に記述出来る構文 ⚫ コマンドの組み合わせが容易に可能 ⚫ 即時実行可能 ⚫ インタラクティブ性 4 echo "abc def ghi" | wc IPSJ SIGPRO 2020-4-(3) Kouji Matsui
5. シェルシステムの課題 Bash等の既存のシェルシステムの特徴 5 シェルシステム 簡便な構文 コマンド連携 即時実行 インタラクティブ性 IPSJ SIGPRO 2020-4-(3) Kouji Matsui
6. シェルシステムの課題 解決出来ない、又は難しい課題 6 シェルシステム 簡便な構文 コマンド連携 即時実行 インタラクティブ性 複雑な処理の実現 バイトストリーム コード検査 サードパーティ ライブラリ利用 メタデータ利用 IDE連携 バイナリ生成 課題(1) 課題(2) IPSJ SIGPRO 2020-4-(3) Kouji Matsui
7. シェルシステムの課題 解決出来ない、又は難しい課題 (1) ⚫ 複雑な処理をシェルシステム内だけで実現することは難しい ⚫ シェルではなく、他の処理系を使う ⚫ バイトストリーム前提の連携 ⚫ データ構造の検査は行われない ⚫ コードの事前検査が難しい ⚫ インタプリタ言語 ⚫ 静的型システムではない 7 IPSJ SIGPRO 2020-4-(3) Kouji Matsui
8. シェルシステムの課題 解決出来ない、又は難しい課題 (2) ⚫ 第三者が作成したスクリプトの流用 ⚫ スクリプトファイルをコピーして準備 ⚫ リッチなテキストエディタ環境の整備 ⚫ 文脈に基づく自動的な構文の色付け ⚫ インラインヘルプ、サジェスト機能 ⚫ コマンドの意味を解釈した自動補完 ⚫ 自動補完スクリプトは手動で記述 ⚫ スクリプトのコンパイル ⚫ 高速化や、デプロイの単純化 8 IPSJ SIGPRO 2020-4-(3) Kouji Matsui
9. シェルシステムの課題 解決出来ない、又は難しい課題 9 シェルシステム 簡便な構文 コマンド連携 即時実行 インタラクティブ 複雑な処理の実現 バイトストリーム コード検査 サードパーティ ライブラリ利用 メタデータ利用 IDE連携 バイナリ生成 本研究の注視部分 課題(1) 課題(2) IPSJ SIGPRO 2020-4-(3) Kouji Matsui
10. 研究の概要 既存のシェルシステムと同様に振る舞う言語処理系を考え、ラ ムダ計算に基づく静的型付け処理を導入する方法を模索した。 ⚫ 静的型付けを行うことで、既存のコマンドとメソッドや関数 を、型検査を行いつつシームレスに連携させることが出来る。 ⚫ コマンドや演算子を関数と見立て、統一した手法で連携、拡 張することが出来る。 ⚫ 実際に機能するかどうか、シェルシステムを実装して確認す る。 10 IPSJ SIGPRO 2020-4-(3) Kouji Matsui
11. 研究の概要 11 シェルシステム 簡便な構文 コマンド連携 即時実行 インタラクティブ 複雑な処理の実現 バイトストリーム コード検査 ライブラリ活用 型システム 静的型検査 IPSJ SIGPRO 2020-4-(3) Kouji Matsui
12. 研究の概要 12 シェルシステム 簡便な構文 コマンド連携 即時実行 インタラクティブ ライブラリ活用 型システム 静的型検査 幅広い応用を可能にする (.NETライブラリを使用) ラムダ計算を基礎として 柔軟な記述を可能にする 型検査で静的解析 型情報を取得可能 IPSJ SIGPRO 2020-4-(3) Kouji Matsui
13. 13 IPSJ SIGPRO 2020-4-(3) Kouji Matsui
14. echo "abc def ghi" | wc 静的型付けの方法 ⚫ トークン(単語)のうち、識別子を関数として扱う: 14 echo関数 文字列 wc関数 パイプライン演算子(関数) IPSJ SIGPRO 2020-4-(3) Kouji Matsui
15. 静的型付けの方法 ⚫ トークン(単語)のうち、識別子を関数として扱う: 15 識別子 関数定義 (疑似) 型 echo echo(string sentence): string string -> string | (パイプライン演算子) | a:τ0 f:τ0 ->τ1 : τ1 τ0 -> (τ0 -> τ1 ) -> τ1 wc wc(string words): string string -> string echo "abc def ghi" | wc ⚫ (τ0 -> τ1 ) = echo = (string -> string) ⚫ τ0 = string, τ1 = string 型推論にて、 型変数τ0を導出 IPSJ SIGPRO 2020-4-(3) Kouji Matsui
16. 静的型付けの方法 ⚫ トークン(単語)のうち、識別子を関数として扱う: 16 ((echo "abc def ghi") |) wc echo "abc def ghi" | wc (| (echo "abc def ghi")) wc 初期の解釈 中置演算子を入れ替えて 関数とみなす IPSJ SIGPRO 2020-4-(3) Kouji Matsui
17. 静的型付けの方法 ⚫ すべてのトークンを関数として扱う: 17 wc (echo "abc def ghi") : string(1) function: | a:τ0 f:τ0 -> τ1 = f(a) : τ0 -> (τ0 -> τ1 ) -> τ1 | (echo "abc def ghi") wc パイプライン演算子の疑似定義: 型を保ってaとfを入れ替える関数 下段のように推論出来る 結果は静的に型検査されている IPSJ SIGPRO 2020-4-(3) Kouji Matsui string(0) -> string(1) string -> string(0)
18. 18 IPSJ SIGPRO 2020-4-(3) Kouji Matsui
19. 型による拡張と連携 19 ⚫ 本研究の言語処理系を.NETランタイム上に構築。 ⚫ .NETの既存の資産(ライブラリ)を活用する事を考える。 ⚫ ライブラリはOOPによる実装が行われている。 ⚫ クラス、構造体にメソッドが定義されている。 ⚫ メソッドは以下の構造を持つ: IPSJ SIGPRO 2020-4-(3) Kouji Matsui メソッド 関数定義 (疑似) 型 Convert.ToInt32 Convert.ToInt32(string value): int string -> int Convert.ToInt32 Convert.ToInt32(string value, IFormatProvider fp): int string -> IFormatProvider-> int メソッドのオーバーロード（多重定義） メソッドの関数型で区別される
20. 型による拡張と連携 20 ⚫ .NETライブラリの型を型推論の計算に使用し、ラムダ計算 全体で型推論が機能するようにする。 echo "12345" | Convert.ToInt32 Convert.ToInt32(echo "12345") IPSJ SIGPRO 2020-4-(3) Kouji Matsui string(0) -> τ1 string -> string(0) 型 string -> int string -> IFormatProvider -> int 戻り値の型のバリエーション τ1 : int | IFormatProvider -> int 数値型を返すメソッドを選択 (ConstantTerm)
21. 型による拡張と連携 21 ⚫ 外部コマンド、.NETライブラリの使用、又は両方の組み合 わせの、どの方法でも同じ記法を使える。 ⚫ 静的型検査が行われる。 echo "12345" | Convert.ToInt32 IPSJ SIGPRO 2020-4-(3) Kouji Matsui echo "abc def ghi" | wc
22. 型による拡張と連携 22 ⚫ 適用する型によって、構造的な意味のあるデータを連携させる ことが出来る。 コマンド 関数定義 (疑似) 型 cat cat(string file): string string -> string cat cat(string file): TextReader string -> TextReader cat cat(string file): Stream string -> Stream cat "sample.csv" ⚫ 外部コマンドは、オーバーロード定義を持ち得る。 文字列の列挙 (n行) 文字列 バイト ストリーム IPSJ SIGPRO 2020-4-(3) Kouji Matsui
23. 型による拡張と連携 23 ⚫ CSVファイルの集計操作を行う: 行列構造を担保しながら計算 1. 各行の先頭カラムを抽出 2. 一意化する cat "sample.csv" | pcsv | Enumerable.ElementAt 0 | Enumerable.Distinct 文字列をCSVとみなし、パースして 行列構造に変換する関数 行列の型付けされた式 IPSJ SIGPRO 2020-4-(3) Kouji Matsui
24. 型による拡張と連携 24 ⚫ 構造を持ったデータを型付けしつつ、連携させることが出来る。 cat "sample.csv" | pcsv | Enumerable.ElementAt 0 | Enumerable.Distinct IPSJ SIGPRO 2020-4-(3) Kouji Matsui 関数/メソッド 疑似関数定義 型 pcsv pcsv(TextReader tr): seq string[] TextReader -> seq string[] Enumerable.ElementAt ElementAt(this seq τ0 xs, int index): τ0 int -> τ0 -> seq τ0 Enumerable.Distinct Distinct(this seq τ0 xs): τ0 seq τ0 -> seq τ0 m個文字列のシーケンス (m個×n行) n個文字列 nd 個文字列 (出力) シェルがフォーマットする 文字列 (テキスト)
25. 25 IPSJ SIGPRO 2020-4-(3) Kouji Matsui
26. まとめ 26 シェルシステム 簡便な構文 コマンド連携 即時実行 インタラクティブ ライブラリ活用 型システム 静的型検査 幅広い応用を可能にする (.NETランタイムを使用) ラムダ計算を基礎として 柔軟な記述を可能にする 型検査で静的解析 型情報を取得可能 IPSJ SIGPRO 2020-4-(3) Kouji Matsui
27. 今後の展望 課題の解決と、実用レベルへの磨き上げ 27 シェルシステム 簡便な構文 コマンド連携 即時実行 インタラクティブ 複雑な処理の実現 バイトストリーム コード検査 サードパーティ ライブラリ利用 メタデータ利用 IDE連携 バイナリ生成 課題(1) 課題(2) IPSJ SIGPRO 2020-4-(3) Kouji Matsui ソースコード: https://github.com/kekyo/Favalon
28. 28 IPSJ SIGPRO 2020-4-(3) Kouji Matsui