たにしきんぐダム

プログラミングやったりゲームしてます

導出に関する帰納法と項に関する構造的帰納法についてのメモ

最近TaPLを読んでいるのだけれど、いかんせん構造的帰納法に不慣れなもので、導出に関する帰納法による証明を読んだり書いたりしているうちに

  • 自分が何をしているのか
  • 何を示すことで命題を証明しようとしているのか
  • そもそも項に関する帰納法と導出に関する帰納法って何が違うんだっけ???

が分からなくなることがあった。

分かってしまった今となっては何でこんなことが分からなかったのか分からないけど、恥をしのんで自分の理解をメモしておく。メモしておかないとどうせ後でまた混乱し始めると思う。


項に関する構造的帰納法

これはTaPL3章の定理3.3.4にある通り

各項 s に対して、s の任意の直接の部分項 r に対して P (r) が成り立つとき、P (s) が証明できる
ならば、すべての s に対して P (s) が成り立つ。

つまり項 $t_1$ ... $t_n$ があって、それらの各項について $P(t_1)$ ... $ P(t_n) $ が成り立つとき、$t_1$ ... $t_n$ を直接の部分項として持つ項 $s$ について $P(s)$ が成り立つ。

例えば、TaPL 第8章の、定理8.2.4の型の一意性 (t: R1 かつ t: R2 ならば R1 = R2)

ある項のsの任意の直接の部分項rに対して、型の一意性が成り立つことを帰納法の仮定と置いて、そのとき項sについて型の一意性が成り立つことを(inversion lemmaを使いつつ)示し、それにより定理を証明している。

導出に関する帰納法

一方、定理8.3.2の進行定理の証明では、項に関する帰納法ではなく、t: T の導出に関する帰納法により定理を証明する。

項に関する帰納法が直接の部分項に着目するのに対し、導出に関する帰納法では導出木の直接の部分木(に現れる項と型の2つ組)に着目する。

各項と型の関係 s: S に対して、s: S の任意の直接の(導出木の)部分木に現れる2つ組 r: R に対して P(r: R) が成り立つとき、P(s: S) が証明できる
ならば、すべての s: S に対して P(s: S)が成り立つ

こういう感じか???

進行定理の証明では、導出木の根を導出するのに直接使われた導出規則について場合分けを行い、それぞれの場合について導出に関する帰納法を用いて定理を証明する。

例えば T-IF の場合、つまり t = if t1 then t2 else t3 (で t: T) の場合、まずinversion lemma より

  • t1: Bool
  • t2: T
  • t3: T

がわかる。ここで帰納法の仮定より、t1 は値である。もしくは t1' が存在して t1 -> t1' となる。

ここで何を示すべきかを思い出してみると、上に書いた帰納法の仮定の下で、命題: t = it t1 then t2 else t3 自体に t が値である or t' が存在して t -> t' であることを示せればよいのであった。

あとはt1が値である場合と、t1が評価される、どちらの場合でも t について命題が成り立つことを示せれば良い。

  • t1 が値ならば canonical formよりt1はtrue か false
    • true なら E-IFTRUE により if true then t2 else t3 -> t2 だし
    • false なら E-IFFALSE にょり if false then t2 else t3 -> t3
  • t1 -> t1'なら E-IF より if t1 then t2 else t3 -> if t1' then t2 else t3

よって、どちらの場合でも t' が存在して t -> t' となることが分かる。

といった具合である。


分かってしまえば何てことはないのだけれど、ここを分かったフリしたまま進んでしまうと多分何も分からないで死んでたので分かってよかったですね。

東京工業大学・情報理工学院(修士)に入学した

2017年4月から新卒で株式会社はてなに入社してフルタイムでWebアプリケーションエンジニアとして働いたのですが、2021年4月に東京工業大学情報理工学院 数理計算科学系の修士課程に入学しました。しばらくは貯金とアルバイトと学生支援機構からのローンで生活する予定です。

主に programming environment や program comprehension みたいな、ソフトウェア工学プログラミング言語(実装より)の間くらいのところ研究しようと考えています。

  • もともとプログラミング支援ツール(formatter, linter, IDE, etc...)を作るのが好きで、趣味でScalaIDEやformatterやその基盤システムの開発を細々とお手伝いしていた。
  • そこらへんのコミュニティや海外カンファで、企業や大学に所属してプログラミング支援ツールをフルタイムで作っている人と会話しているうちに、そういうツール作るの専門にしていきたいなという気分になってきた。
  • 思い切って一度大学院でプログラミング環境の研究しつつ、あわよくばキャリアチェンジしよう思い、大学院に入学することにした。
    • (仕事はいつでもできるが、大学に入学して収入が激減したときの打撃は人生が進めば進むほど大きくなりそうだし、仕事しながら大学院いくほどのバイタリティはない)
  • できれば卒業後は開発支援ツール作る仕事に就きたいとぼんやり思っているが、卒業後のキャリアとかはまだ一切考えていない...
    • 突然2000万円くらい天から降ってきたりしない限りは博士課程にそのまま進学する予定はありません。

今後もScalaとかのツール開発に参加しつつ、研究でもプログラマの生産性を向上させる便利システムを作っていきたいですね。

Scala3 Interactive Compiler API で遊んでみる

この記事は Scala Advent Calendar 2020 - Qiita 18日目の記事です。

完全に自分用のメモなのですが、コンパイラ周辺ツールの Scala3 対応に備えて、dotty の interactive compiler API の使い方を一部学んでみたのでその学習メモを残しておく。

今回試したコードは以下のリポジトリにまとまっていますが、このブログでは試行錯誤した過程を書いていこうと思います。今回は使い方だけ見たけど次はどう実装されてるかまで読んでいきたい。

github.com

もうちょっと雑なやつ dotty tools で遊んでみる - tanishiking-pub

また使い方を勉強するにあたっては dotty language server を参考にしました。 dotty/DottyLanguageServer.scala at eddd4da41ac14057edf4db6f9a24de6f768dbbb3 · lampepfl/dotty

(dotty language server はあくまで参考実装という感じで、将来的には変わらず intellij-scala と metals が scala3 対応を頑張っていく感じになるんではなかろうか? dotty-language-server は最低限の機能は備えているが、実プロジェクトで利用するにはいろいろと機能が不足している割に暫く手が入ってないので (要出典))

dotty tools の主なエンドポイントは InteractiveDriver というクラス

project を作る

sbt console で遊んでみよう。まずは砂場とするプロジェクトを作る

// project/plugins.sbt
 addSbtPlugin("ch.epfl.lamp" % "sbt-dotty" % "0.4.6")
// build.sbt
val dottyVersion = "3.0.0-M2"

lazy val root = project
  .in(file("."))
  .settings(
    name := "dotty-interactive-playground",
    version := "0.1.0",

    scalaVersion := dottyVersion,

    libraryDependencies ++= List(
      "org.scala-lang" %% "scala3-compiler" % scalaVersion.value,
      "io.get-coursier" % "interface" % "1.0.1",
      "com.lihaoyi" %% "pprint" % "0.6.0",
    )
  )

このproject内で sbt console を実行してみる。

InteractiveDriver の instantiate

 scala> import dotty.tools.dotc.interactive.InteractiveDriver
 
// まずは InteractiveDriver クラスを instantiate
// InteractiveDriver にはコンパイラに与える classpath やコンパイラオプションを与える。
// とりあえず何も与えずにインスタンス化しようとしてみる
 scala> val driver = new InteractiveDriver(List.empty)
 dotty.tools.dotc.MissingCoreLibraryException: Could not find package scalaShadowing from compiler core libraries.
 Make sure the compiler core libraries are on the classpath.

なるほど、scala3-libraryclasspath を与えないと死ぬようになってるのか

The official standard library for Scala 3.0 is the Scala 2.13 library. Not only the source code is unchanged but it is even not compiled and published under 3.0. It could be, but it would be useless because, as we have seen, a Scala 3.0 module can depend on a Scala 2.13 artifact. https://scalacenter.github.io/scala-3-migration-guide/docs/compatibility.html#the-scala-standard-library

とあるように、scala3の標準ライブラリは2.13のライブラリを利用しているため、scala3-libraryclasspath に加えて、scala2.13 の標準ライブラリのクラスパスも与えて

scala-libraryclasspath ってどこにあるんだっけ? - sbt の依存に dotty-libraryが含まれている場合 sbt show runtime:fullClasspath で依存しているライブラリのclasspathが分かるのでコピペできる

scala> val classpaths = Seq(
  "/Users/tanishiking/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/org/scala-lang/scala3-library_3.0.0-M2/3.0.0-M2/scala3-library_3.0.0-M2-3.0.0-M2.jar",
  "/Users/tanishiking/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/org/scala-lang/scala-library/2.13.4/scala-library-2.13.4.jar"
)

scala> val driver = new InteractiveDriver(List("-classpath", classpaths.mkString(java.io.File.pathSeparator)))
val driver: dotty.tools.dotc.interactive.InteractiveDriver = dotty.tools.dotc.interactive.InteractiveDriver@4123624c

もしくは別にこんなことしなくても coursier の fetch API で必要なライブラリを取得してきて、そのクラスパスをInteractiveDriverに食わせてやる

import coursierapi.{Fetch, Dependency}
import java.nio.file.Path

val fetch = Fetch.create()

import scala.jdk.CollectionConverters._

fetch.addDependencies(
  Dependency.of("org.scala-lang", "scala3-library_3.0.0-M2", "3.0.0-M2")
)

val extraLibraries: Seq[Path] = fetch
      .fetch()
      .asScala
      .map(_.toPath())
      .toSeq

val driver = new InteractiveDriver(
   List(
     "-color:never",
     "-classpath",
     extraLibraries.mkString(java.io.File.pathSeparator)
   )
)

InteractiveDriver を使っていろんなコードを interactive に解析してみよう

コンパイルを実行する

val uri = new URI("file:///virtual")

driver.run(uri, "object X { }")

pprint.log(driver.openedFiles)
// LinkedHashMap(file:///virtual -> /virtual)

pprint.log(driver.openedTrees(uri))
//  List(
//    SourceTree(
//      tree = TypeDef(
//        name = X$,
//        rhs = Template(
//          constr = DefDef(
//            name = <init>,
//            tparams = List(),
//            vparamss = List(List()),
//            tpt = TypeTree[TypeRef(ThisType(TypeRef(NoPrefix,module class scala)),class Unit)],
//            preRhs = Thicket(trees = List())
//          ),
//          parentsOrDerived = List(
//            Apply(
//              fun = Select(
//                qualifier = New(
//                  tpt = TypeTree[TypeRef(ThisType(TypeRef(NoPrefix,module class lang)),class Object)]
//                ),
//                name = <init>
//              ),
//              args = List()
//            )
//          ),
//          self = ValDef(
//            name = _,
//            tpt = SingletonTypeTree(ref = Ident(name = X)),
//            preRhs = Thicket(trees = List())
//          ),
//          preBody = List()
//        )
//      ),
//      source = /virtual
//    )
//  )

エラーがあるコードを与えてみる

val sourceParital = "object X { def x = 1.toSt } "
val uriPartial = new URI("file:///partial")
val diag = driver.run(uriPartial, sourceParital)
pprint.log(diag)
// List(
//   class dotty.tools.dotc.reporting.Diagnostic$Error at /virtual:[19..21..25]: value toSt is not a member of Int - did you mean (1 : Int).toInt?,
//   class dotty.tools.dotc.reporting.Diagnostic$Info at ?: 1 error found
// )

エラーが帰ってきた。しかし openedTree には error symbol っぽいものを使ってエラー回復したと思われる部分的な構文木が登録されている。これのおかげで部分的なコードでも補完とかnavigationが実行できるわけだね

pprint.log(driver.openedTrees(uriPartial))
// Mode.Interactive makes parser error resillient using <error> symbol?
// ...
// preBody = List(
//       DefDef(
//         name = x,
//         tparams = List(),
//         vparamss = List(),
//         tpt = TypeTree[dotty.tools.dotc.core.Types$PreviousErrorType@752771a8],
//         preRhs = Select(qualifier = Literal(const = ( = 1)), name = toSt)
//       )
//     )

completion の実行

Completions.completion を使って、指定したポジションで completion API を実行してみる。さっきのコードの 1.toS のところで補完を実行してみよう。

import dotty.tools.dotc.interactive.{InteractiveDriver, Interactive, Completion}
import dotty.tools.dotc.util.{Spans, SourcePosition}
import dotty.tools.dotc.core.Contexts._



val pos = new SourcePosition(
  driver.openedFiles(uriPartial),
  Spans.Span(sourceParital.indexOf(".toSt") + ".toS".length) // run completion at "1.toS"
)
val completions = Completion.completions(pos)(using driver.currentCtx.fresh.setCompilationUnit(driver.compilationUnits.get(uriPartial).get))
pprint.log(completions)
// (
//   21,
//   List(
//     Completion(label = "toShort", description = "=> Short", symbols = List(method toShort)),
//     Completion(label = "toString", description = "(): String", symbols = List(method toString))
//   )
// )

toStringtoShort が補完された

find definition

次は定義ジャンプなんかを実装するために利用する Definition.findDefinition を使って、あるシンボルの定義元を探す機能を利用してみる。

val sourceDefinition = "object Definition { def x = 1; val y = x + 1 }"
val uriDefinition = new URI("file:///def")
driver.run(uriDefinition, sourceDefinition)
given ctx as Context = driver.currentCtx

val pos = new SourcePosition(driver.openedFiles(uriDefinition), Spans.Span(sourceDefinition.indexOf("x + 1")))
val path = Interactive.pathTo(driver.openedTrees(uriDefinition), pos)

// Feeding path to the pos, and return definition's tree
val definitions = Interactive.findDefinitions(path, pos, driver)
pprint.log(definitions)
// List(
//   SourceTree(
//     tree = DefDef(
//       name = x,
//       tparams = List(),
//       vparamss = List(),
//       tpt = TypeTree[dotty.tools.dotc.core.Types$PreviousErrorType@6b6b68d0],
//       preRhs = Select(qualifier = Literal(const = ( = 1)), name = toSt)
//     ),
//     source = /partial
//   ),
//   SourceTree(
//     tree = DefDef(
//       name = x,
//       tparams = List(),
//       vparamss = List(),
//       tpt = TypeTree[TypeRef(ThisType(TypeRef(NoPrefix,module class scala)),class Int)],
//       preRhs = Literal(const = ( = 1))
//     ),
//     source = /def
//   )
// )

本来欲しいのは後者だけだったのだけれど、他所の compilation unit で定義した x も引いてきてしまったが、とりあえず定義元のコードの構文木を取得することができた。

おまけ parser で遊んで見る

scala> import dotty.tools.dotc.core.Contexts._

scala> given Context = (new ContextBase).initialCtx
lazy val given_Context: dotty.tools.dotc.core.Contexts.Context

scala> import dotty.tools.dotc.parsing.Parsers

scala> import dotty.tools.dotc.util.SourceFile

scala> val parser = new Parsers.Parser(SourceFile.virtual("<meta>", "class X {} extends Base;"))
val parser: dotty.tools.dotc.parsing.Parsers.Parser = dotty.tools.dotc.parsing.Parsers$Parser@175db8b0

scala> parser.parse()
val res1: dotty.tools.dotc.ast.untpd.Tree = PackageDef(Ident(<empty>),List(TypeDef(X,Template(DefDef(<init>,List(),List(),TypeTree,EmptyTree),List(),ValDef(_,EmptyTree,EmptyTree),List(EmptyTree)))))

Scala の開発環境構築 2021

f:id:tanishiking24:20201203004828p:plain
特に意味はないけどおしゃれかなと思って貼ったスクショ

Scala Advent Calendar 2020 - Qiita 3日目です

ここ2,3年の間にScalaの開発ツールチェーンは進化を続けていて、Scalaの開発体験はめちゃくちゃ良くなってきています。例えば、数年前だと

  • IDEは基本的にIntelliJ一択、vimとかemacsで開発環境作れなくもないけどかなり大変
  • IntelliJの型チェックがうまく行かなくて、ちょっと複雑なコード書くとコンパイルは通るのに画面が真っ赤になる
  • コンパイルが遅い(インクリメンタルビルドしても遅い)

という感じだったのですが、現状はかなり改善されていて

  • IntelliJ 以外にも metals という Language Server がかなり使いやすくなっていてあらゆるエディタで簡単にScalaを書けるようになった
  • IntelliJ も metals コンパイラ(正確にはビルドサーバー)から直接コンパイルエラーを受け取るのでコンパイル通るのに真っ赤とかはない
  • Scalaコンパイラ自体は少しずつ早くなってる。
    • sbtのincremental compilerの改善が劇的で、sbtを立ち上げっぱなしにしている場合はかなり開発効率が良い
    • フルビルドはやっぱり時間かかる

基本的に OSX / VSCode での環境構築方法を書いていきます。InttelliJ の構築もそのうち書きたい

まだ2020年だけどもうすぐ2021年だし2021年ってタイトルにしちゃった。


Java のインストール

とりあえずJava11を入れておけば良いと思います。Javaディストリビューションはいろいろあるけどローカルなら何でも良いんじゃないんですかね? oracle とか adoptopenjdk とかで

brew

$ brew cask install java11
# ~/.zshrc なんかに
export JAVA_HOME=`/usr/libexec/java_home -v 11`
$ java -version

してなんか出てればOK

HomebrewでインストールできるJDKまとめ(2019年11月時点) - Qiita

java のバージョン切り替え


sbt のインストール

scala の主流なビルドツールである sbt - The interactive build tool をダウンロードします

$ brew install sbt
  • ここでダウンロードするsbtのバージョンはそんなに気にしなくて良いです
  • ここでダウンロードするsbtはlauncher、プロジェクト毎の設定で実際に利用するsbtのバージョンを指定できる

新しくsbtのプロジェクトを作る

$ sbt new scala/hello-world.g8
[info] welcome to sbt 1.4.4 (AdoptOpenJDK Java 11.0.9)
[info] set current project to tanishiking (in build file:/Users/tanishiking/src/github.com/tanishiking/)
[info] set current project to tanishiking (in build file:/Users/tanishiking/src/github.com/tanishiking/)

A template to demonstrate a minimal Scala application

name [Hello World template]: hello

Template applied in /Users/tanishiking/src/github.com/tanishiking/./hello

hello ディレクトリ以下に以下のようなプロジェクトが出来ます。

$ tree
.
|-- build.sbt
|-- project
|   `-- build.properties
`-- src
    `-- main
        `-- scala
            `-- Main.scala
  • build.sbt
  • project/build.properties
    • sbt.version=1.4.3 みたいなのが書かれてるはず。ここで利用するsbtのバージョンを指定するよ
    • ルートディレクトリで sbt を起動するとここに書かれてるバージョンのsbtがダウンロードされる

sbt を立ち上げてみる

$ sbt
[info] [launcher] getting org.scala-sbt sbt 1.4.3  (this may take some time)...
...
...
[info] welcome to sbt 1.4.3 (AdoptOpenJDK Java 11.0.9)
[info] loading project definition from /Users/tanishiking/src/github.com/tanishiking/hello/project
[info] loading settings for project hello from build.sbt ...
[info] set current project to hello-world (in build file:/Users/tanishiking/src/github.com/tanishiking/hello/)
[info] sbt server started at local:///Users/tanishiking/.sbt/1.0/server/baf7ac7b489b491bdcaa/sock
[info] started sbt server
sbt:hello-world>
sbt:hello-world> compile
[info] compiling 1 Scala source to /Users/tanishiking/src/github.com/tanishiking/hello/target/scala-2.13/classes ... update 0s
[success] Total time: 3 s, completed Dec 2, 2020, 9:42:12 PM
sbt:hello-world> run
[info] running Main
Hello, World!
[success] Total time: 0 s, completed Dec 2, 2020, 9:42:18 PM
  • sbt は $ sbt compile のように shell から実行することも出来ますが、開発中は sbt は立ち上げっぱなしにしておくことが推奨されています
  • なぜなら
    • sbt を起動するたびにJVMが起動することになるので時間かかる
    • sbt は起動している限り同じ同じScalaコンパイラが利用されるので、compileを繰り返すことでScalaコンパイラJITが温まっていって高速にコンパイルが動くようになっていく

REPL を立ち上げてみる

sbt を起動して、そこから console と打ってみましょう

sbt:hello-world> console
[info] Starting scala interpreter...
Welcome to Scala 2.13.3 (OpenJDK 64-Bit Server VM, Java 11.0.9).
Type in expressions for evaluation. Or try :help.

scala>

sbt console からなら sbt でダウンロードした依存ライブラリも import 出来たりするので便利


vscode のセットアップ

最近のScalaIDE

という感じになっています。metals は scalameta という Scala の解析ツールセットをベースにしたLanguage Server Protocol 実装で IntelliJ Scala に次ぐシェアを誇る (https://scalacenter.github.io/scala-developer-survey-2019/) 開発ツールです。

scalameta.org

先程のディレクトリでVSCode を立ち上げ

$ code .

f:id:tanishiking24:20201202222158p:plain
vscode の extension から metals を検索してダウンロード

ダウンロードが完了したら build.sbt*.scala ファイルを開いてみましょう。以下のようなポップアップが出てくるので Import build を押して暫くお待ち下さい。

f:id:tanishiking24:20201202222538p:plain
Import build を押してください

これでセットアップ完了です

間違えて Import build しそこねた人は VSCode のコマンドパレットを開いて > metals: Import build を実行してね。

pro tip

なんかIDEがcomopletionとか返してくれなくなったときは一度 .metals.bloop というディレクトリを削除してVSCodeを再起動しましょう。(IDEのサーバー安定させたいと思っている)


コードフォーマット

scalameta.org を使いましょう

  • CLI / sbt plugin / IDE から使えるようになってるけど基本的には sbt plugin か IDE から使うのが個人的におすすめ
  • プロジェクトルートに .scalafmt.conf を作って version=2.7.4 とか書いてください

VSCode からやる場合

  • VSCode のコマンドパレットを開いて > Format Document を実行してみましょう。開いているファイルに対してフォーマットが実行されます。
  • .scalafmt.conf が存在しない場合は以下のようなポップアップが出てくるので Create '.scalafmt.conf' を押して勝手にファイルを作ってもらったりしましょう。
  • VSCodeFormat On Save を有効にすると save 時に勝手にフォーマットしてくれるようになる

f:id:tanishiking24:20201202222939p:plain
コードフォーマット

sbt から使う場合

  • scalameta/sbt-scalafmt: sbt plugin for Scalafmt を使いましょう
  • project/plugins.sbt に以下のように書いて sbt を起動します
    • 紛らわしいのですが、sbt-scalafmt のバージョンと、上に書いた scalafmt のバージョンは完全に独立しています。sbt-scalafmt は scalafmt 本体をダウンロードしてきて、それを使ってフォーマットを実行するやつ
addSbtPlugin("org.scalameta" % "sbt-scalafmt" % "2.4.2")

sbt を立ち上げ以下のコマンドを打つことで全てのファイルをフォーマットする

sbt:hello-world> scalafmtAll

詳しくは

https://scalameta.org/scalafmt/docs/installation.html#task-keys


Linter

Scala ってデファクトな感じの Linter がないんですよね

一応カスタマイズしやすくて将来的に Scala3 との互換性も保たれそうな Linter(Refactoring tool) としては scalafix が有望、他には WartRemover とかかなぁだけど、そんなに使われてる印象ない

scalacenter.github.io

www.wartremover.org


Worksheet 機能を使ってみよう

コマンドパレットから New Scala File を選び、Worksheets を選ぶ。

f:id:tanishiking24:20201203003822p:plain

xxx.worksheet.sc というファイルができるので、そこに適当な scala スクリプトを書いてみよう。以下のような感じでコメントに評価結果が表示される。

f:id:tanishiking24:20201203004057p:plain