DMOJ を使ってオンラインジャッジシステムを構築する

DMOJ という OSS のオンラインジャッジシステムの環境を整えたので使い方をメモしておく。

環境はコンテナ化し、image も Docker Hub に上げたので MySQL や Redis のイメージが消されない限りは動くと思う。(動作確認は Linux 環境でのみ行っている)

github.com

元々のコードだとメールアドレスの認証が必須になっていたが、もっと雑にユーザー登録をできるようにしたかったのでメールアドレスの認証は飛ばすように変更している。(AWS SES などとつなげるのが面倒だった)

オリジナルとの変更点はこの commit
my custom · goropikari/online-judge@02a4a4a · GitHub

基本構成

GitHub で DMOJ Organization を見ると DMOJ/online-judge というのがあるがこれだけではオンラインジャッジシステムとして使うことはできない。これはあくまでフロントエンドであって実際に提出されたプログラムの正誤判定をするジャッジサーバーは DMOJ/judge-server である。よってこれら2つをつなげることでオンラインジャッジシステムとして使うことができる。 ジャッジサーバーは複数登録することができるが、提出されるプログラム数に応じてオートスケーリングするとかはなくて手動で登録するようである。 問題文や提出されたプログラムは MySQL に保存されるが、ジャッジ時に使用するテストケースはジャッジサーバーに配置するようになっている。それ以外のデータはジャッジサーバーに置くことはないせいかジャッジサーバーは MySQL と通信しない。

使い方

環境立ち上げ

とりあえず docker compose でもろもろを立ち上げる。ここで DMOJ/online-judge が動いているコンテナを web コンテナ、DMOJ/judge-server が動いているコンテナを judger コンテナと以降呼ぶこととする。

git clone https://github.com/goropikari/dmoj_docker.git
cd dmoj_docker
make run

立ち上がったら http://127.0.0.1:8080/admin にアクセスする。 user name, password はともに admin。 問題の追加やコンテストの設定はこの admin 画面から行う。

admin画面

問題を追加する

問題文を追加

Problems -> Add で問題追加画面に行く

問題追加

add problem

必須項目は以下のもの

  • Problem code:
    • ^[a-z0-9]+$ を満たす任意の文字列
  • Problem name
    • 任意の文字列。日本語でも可。
  • Problem body:
    • 問題文。MathJax も使える。inline math は ~ で囲み、display math は $$ で囲む。
  • Problem types
    • 適当にタグを作って入れる
  • Problem group
    • 適当にタグを作って入れる
  • Points
    • 点数
  • Time limit
    • 実行時間制限
  • Memory limit
    • メモリ使用量制限
  • Language
    • サポートする言語。ここでチェックを入れた言語でもジャッジサーバー側が対応していない言語では提出できない。

任意項目

  • Publicly visible
    • 追加した問題が公開されるか否かをコントロールする。コンテストの中だけで表示させたい場合はチェックを外しておく。チェックを入れるとコンテスト前から公開された状態になる。
  • Language-specific resource limits
    • 言語ごとに制約を変えることができる

テストケースを追加

入力例と期待する出力を書いたテキストファイルを zip 圧縮したものと、得点や正誤判定方法を記した init.yml を作り judger コンテナの中に配置する。 ファイル構成としては以下のよう

helloworld/  # ディレクトリ名は problem code と名前を合わせる。ここがずれると正誤判定ができない。
├── helloworld.zip
├── init.yml
└── testcases
    ├── 1.in
    └── 1.out

ここで helloworld.zip は testcases 配下を圧縮したもの。

zip -j helloworld.zip testcases/*

zip を作った後は testcases は必要ないので消してしまっても良い。ただ、あとからテストケースに変更したりすることを考えるとそのまま残しておいたほうが良いとは思う。

init.yml

archive: helloworld.zip
test_cases:
- {in: 1.in, out: 1.out, points: 100}

これを judger コンテナの /home/judge/problems に配置する。

docker compose cp helloworld judger:/home/judge/problems

または

cp -r helloworld problems # problems を bind mount しているので docker cp でコピーしなくてもよい

これでジャッジできる準備が整った。 問題ページ (http://127.0.0.1:8080/problem/helloworld) に行き、Judge のところに ExampleJudge が表示されていれば設定は正しく行われている。(設定は正しいはずなのに Judge server が出てこないことがある。そのときは init.yml に改行を入れるなりすると認識されたりする)

得点は init.yml に書いたものでなく、問題を追加するときに設定した得点が表示される。init.yml に書いた得点は問題を解いたときに得られる得点ではなく、得点の重み付けと考えたほうがよいらしい。

例えば、問題の得点が 100 点で、init.yml が以下のようだったとする。

archive: helloworld.zip
test_cases:
- {in: 1.in, out: 1.out, points: 100}
- {in: 2.in, out: 2.out, points: 100}

このとき、1ケース目だけ正答すると 50 点獲得できるといった具合である。

判定方法を指定しなかった場合は、出力が期待するものと一致するかで正誤判定される。ただし末端改行の有無は正誤判定に影響しない。

その他の判定方法や部分点の設定方法などは公式サンプルがあるのでそちらを参考のこと。

docs/problem_examples at fcf7921050fa5d2fdca4a4c3440a7824f0ad38a1 · DMOJ/docs · GitHub

Submit solution から適当な言語を選んでプログラムを提出するとジャッジサーバーで判定される。

余談

利便性はあまり高くないと思うので詳しくは紹介しないが、問題ページにある Edit test data をクリックして遷移するページでもテストケースを追加できる。 上記同様に zip を作りアップロード -> Submit とすると Input file, Output file を選べるようになる。単に zip をアップロードしただけでは選択することはできない。

コンテスト作成

Admin 画面 -> Contests -> Add から情報を入力してコンテストを作成する。

Publicly visible にチェックをいれないと指定した人にしかコンテストが見れなくなってしまうのでそこだけ注意すればあとは必須項目を入れていくだけなので特段迷うところはないと思われる。

PROBLEMS の項目で OUTPUT PREFIX LENGTH OVERRIDE という謎の項目があるが、これは WA だったときに実際に出力されたものの頭 n 文字を表示するという項目である。入力をそのまま出力されるとテストケースがバレるので基本的には 0 のままにしておくのがよい。

保存した後にコンテストページにいくと、コンテストが生えていることが確認できる。

期限を過ぎた後は Virtual Contest として参加できるようにもなっている。

対応言語を追加する(失敗)

  • judge.yml に runtime 追加
  • Executor 作成
  • language_all.json に新しい言語を追加

とすれば行ける気がするが、system call 制限などでうまく追加できなかった。(Julia, Crystal を試して挫折した)

既存 runtime のものでも、judge.yml の設定が悪いのか使えない言語がある (特に JVM 系) ので正直何をしたらちゃんと動くのかコードをちゃんと追っていないので全くわからない。

github.com

Database Design and Implementation を Go で実装した

DBMSフルスクラッチで作る Database Design and Implementation: Second Edition1 を読みながら、この本で作る DBMS(SimpleDB) を Go で実装しました。始めてからちょうど5ヶ月くらいかかりました。

去年も DBMS を自作していましたが、当時は DBMS の理論を学ばずに「この SQL が投げられたときにこういう結果を返すにはこういう実装にすればとりあえずそれっぽい動きをしてくれそう」という感じに実装していて理論的なところは何も学んでいませんでしたが、今回はちゃんと本に沿って実装したので理論・実装を体系だって学べました。

github.com

私はこの本を Riki Otaki さんの「自作DBMSとおすすめ書籍2」という記事で知りました。

自作コンパイラ、自作 OS に関する書籍は数多あれど自作 DBMS の本も存在していたのか!いつかやりたいなぁと思いつつ当時はペーパーバック版が6000~7000円くらいしたのでとりあえず欲しい物リストに入れるだけで放置していました。Springer の本は為替とか関係なく急に高くなったり安くなったりしますが、あるとき3600円弱まで下がったのでそのタイミングで買いました。

元実装Java ですが、私は Java の書き方をよく知らないので Go で実装しました。やる前は class のない Go で書きなおすのは結構辛いかもしれないと思っていましたが、元実装では継承などをあまり使っていなかったので Go に書き直すのでも特別難しいという感じはしませんでした。

元実装と変えたところとして11章でやる JDBC の実装は行わず、代わりに Go の標準ライブラリである database/sqlPostgreSQL wire protocol に対応しました。 自作 DBMS に使いやすい CLI mode を実装するのは結構大変なのでそちらに注力したくない場合は PostgreSQLMySQL などのメジャーな DBMSプロトコルに乗っかるとすでにあるものを使い回せるのでおすすめです。ただし MySQLプロトコルはパケットの構造が複雑で parse するの面倒なので個人的には PostgreSQLプロトコルのほうがおすすめです。10種類くらいのパケット構造が理解できればとりあえず psql とは通信できます。

goropikari.hatenablog.com

この本の良いところ

標準ライブラリのみで実装されている

サードパーティ製のライブラリを使ったほうが実装が楽になる部分はおそらくたくさんあった(parser とか)と思いますが、それらを使うと動く仕組みがブラックボックス化して理解できた気になれないので、自作〇〇をするときは極力標準ライブラリのみで実装したいというのが私の趣味なのですが、この本の実装は標準ライブラリのみで実装されているので曖昧なところが出ずに実装できたのはよかったです。

フルスクラッチ実装

大学の講義の課題で作る DBMS だとある程度型が出来上がっているところに足りないパーツを実装するといった穴埋め方式がよくあると思います。穴埋め方式の利点として重点を置きたい場所に集中できるという点がありますが、逆に自分で作っていない部分はブラックボックスに感じてしまいます。自分で実装していない部分も読めばいいかもしれませんが、それらのコードは講義のレベルを超えるから学生には実装させなかったりしているので読んで理解するというのもなかなか骨の折れる作業です。この本は穴埋め方式でなくフルスクラッチ方式だったのでこのパーツは一体何をしているのか?という疑問を持たずに進めることができました。

この本の辛いところ

元実装のコードが読みづらい

マジックナンバーが出てきたり、副作用のある method が多くコードだけを読んでいると結構辛いなというところが多々ありました。package が循環参照している箇所もあり、全体的な構成としてわかりづらさを感じました。

この本を進めている途中で UC Berkeley CS186 の課題の RookieDB という DB の存在を知りましたがこちらのほうが読みやすく、アーキテクチャも良さそうに見えました(隣の芝生が青く見えただけかもしれません)

Lock manager RookieDB の Lock manager

Overview - CS186 Projects

12章以降写経だけでは作ったものが動かない

内容が理解できずともとりあえず写経すれば動いていた11章までとは打って変わって、12章以降は本に載っている実装を写経するだけではパーツが結合されない部分が出てきます。

12章では index を実装しますが、UPDATE, INSERT, DELETE のときに index に更新をかける処理は入る一方、SELECT のときに index を使うようにする修正は入らないのでこの時点で index を使った SELECT に対応させたい場合は自分で実装する必要があります。幸い15章の実装で index を使った SELECT ができるようになりますが、一方でその実装だとそれまで使えていた view が使えなくなります。

13章では集約関数や GROUP BY に対応するためのコードを書きますが、これだけでは動かなくて自力で Lexer, Parser に修正を加える必要があります。こちらは index のときと違い後半の章が終わっても結合されません。

14章も書いただけでは結合されず、15章の実装をすると結合されます。

一応15章までたどり着くと13章を除き色々解決されますが、12章はじめから15章終わりまでには140ページ近くあるので、そこまでモチベを落とさないようにするのはなかなか大変だなぁと思い、私は合間合間で独自修正を入れました。

おわりに

以前、自作 DBMS 界隈では有名な CMU の講義動画 を見て、講義の課題である DBMS 実装をやろうと思ったものの講義の序盤の方で早々に挫折した経験がありますが、この本は無事に終わらせることができました。私同様 CMU の講義が難しいと感じた方はこの本で勉強してみると良いかもしれません。


  1. 第2版は2020年出版ですが、「現在主流の HDD の容量は 40 GB」みたいなことが書かれていて第1版と変わっているのかな?と思うところはありました。

  2. 現在はブログは閉じられてしまったようです。Internet Archive では閲覧可(2022/8/7)

Go のカバレッジ計測結果を GitHub Pages にデプロイする

github.com

coveralls や codecov を使わずにローカルでもカバレッジを見たい、ついでにそれをそのまま GitHub Pages をつかって見れるようにしたいと思ったのでやってみたログ。

Go 標準機能のカバレッジレポートをデプロイする

Go の標準機能の範疇でやる設定は以下のよう

site ディレクトリに HTML を生成して、それをそのまま GitHub Pages に持っていく

# Makefile
.PHONY: coverage
coverage:
  go test -cover ./... -coverprofile=coverage.out
  go tool cover -html=coverage.out -o site/gocoverage.html
# .github/workflows/pages.yml
name: GitHub Pages

on:
  push

jobs:
  deploy:
    runs-on: ubuntu-20.04
    concurrency:
      group: ${{ github.workflow }}-${{ github.ref }}
    steps:
      - uses: actions/checkout@v3

      - name: Set up Go
        uses: actions/setup-go@v3
        with:
          go-version: 1.18

      - name: coverage
        run: make coverage

      - name: Deploy
        uses: peaceiris/actions-gh-pages@v3
        with:
          github_token: ${{ secrets.GITHUB_TOKEN }}
          publish_dir: ./site

実際に生成されるページはこんな感じ

https://goropikari.github.io/lcov_pages_sample/gocoverage.html

LCOV を使う

Go 標準のカバレッジツールで生成される HTML は見やすくないので LCOV を使うようにする場合は以下のよう

# Makefile
SHELL = /bin/bash

ROOT_DIR = $(shell pwd)
GOBIN = $(ROOT_DIR)/bin
export PATH := $(ROOT_DIR)/bin:$(PATH)

.PHONY: tools
tools:
  GOBIN=$(GOBIN) go install github.com/jandelgado/gcov2lcov@v1.0.5

.PHONY: coverage
coverage:
  # lcov
  go test -cover ./... -coverprofile=coverage.out
  bin/gcov2lcov -infile=coverage.out -outfile=coverage.lcov
  genhtml coverage.lcov -o site
  # go coverage
  go tool cover -html=coverage.out -o site/gocoverage.html
name: GitHub Pages

on:
  push

jobs:
  deploy:
    runs-on: ubuntu-20.04
    concurrency:
      group: ${{ github.workflow }}-${{ github.ref }}
    steps:
      - uses: actions/checkout@v3

      - name: Set up Go
        uses: actions/setup-go@v3
        with:
          go-version: 1.18

      - name: lcov
        run: sudo apt-get update && sudo apt-get install -y lcov

      - name: tools
        run: make tools

      - name: coverage
        run: |
          percent=$(make coverage | grep lines | sed -r 's/[^0-9]*(.*\.[0-9]*)%.*/\1/' | sed -e 's/%/%25/')
          int=${percent%.*}
          if [ $int -gt 90 ]; then
            curl -o site/coverage.svg https://img.shields.io/badge/coverage-${percent}%25-green
          elif [ $int -gt 75 ]; then
            curl -o site/coverage.svg https://img.shields.io/badge/coverage-${percent}%25-yellow
          else
            curl -o site/coverage.svg https://img.shields.io/badge/coverage-${percent}%25-red
          fi

      - name: Deploy
        uses: peaceiris/actions-gh-pages@v3
        with:
          github_token: ${{ secrets.GITHUB_TOKEN }}
          publish_dir: ./site

実際に生成されるページはこんな感じ

https://goropikari.github.io/lcov_pages_sample/index.html

README に貼り付ける用のこんな badge coverage も欲しかったので shields.io から画像をダウンロードして、それを GitHub Pages 用の branch に一緒にデプロイしてます。

↓のように raw content のリンクを README に貼り付けておけばとりあえずそれっぽくなります。

[![coverage](https://raw.githubusercontent.com/goropikari/lcov_pages_sample/gh-pages/coverage.svg)](https://goropikari.github.io/lcov_pages_sample/)

VSCode Remote Container 間を 172.17.0.1 経由で通信する

TL;DR

~/.config/Code/User/settings.json

"remote.localPortHost": "allInterfaces"

を追加すると 172.17.0.1 でコンテナ間の通信ができる。

github.com

Remote Container だと 172.17.0.1 で他のコンテナに接続できない

普通に Docker を使っているときはコンテナの中から他のコンテナへのアクセスは 172.17.0.1 を使えばできました。

# コンテナ1
$ docker run --rm -p 9000:9000 python:3 python -m http.server 9000
172.17.0.1 - - [23/Feb/2022 06:59:03] "GET / HTTP/1.1" 200 -

# コンテナ2
$ docker run --rm alpine/curl http://172.17.0.1:9000
  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                 Dload  Upload   Total   Spent    Left  Speed
100   987  100   987    0     0   647k      0 --:--:-- --:--:-- --:--:--  963k
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Directory listing for /</title>
</head>
<body>
<h1>Directory listing for /</h1>
<hr>
<ul>
<li><a href=".dockerenv">.dockerenv</a></li>
<li><a href="bin/">bin/</a></li>
<li><a href="boot/">boot/</a></li>
<li><a href="dev/">dev/</a></li>
<li><a href="etc/">etc/</a></li>
<li><a href="home/">home/</a></li>
<li><a href="lib/">lib/</a></li>
<li><a href="lib64/">lib64/</a></li>
<li><a href="media/">media/</a></li>
<li><a href="mnt/">mnt/</a></li>
<li><a href="opt/">opt/</a></li>
<li><a href="proc/">proc/</a></li>
<li><a href="root/">root/</a></li>
<li><a href="run/">run/</a></li>
<li><a href="sbin/">sbin/</a></li>
<li><a href="srv/">srv/</a></li>
<li><a href="sys/">sys/</a></li>
<li><a href="tmp/">tmp/</a></li>
<li><a href="usr/">usr/</a></li>
<li><a href="var/">var/</a></li>
</ul>
<hr>
</body>
</html>

Remote Container を2つ立ち上げて同じようにすると Connection refused になってしまいました。 172.17.0.1 だとつながりませんが、コンテナに割り振られた IP address である 172.17.0.2 だと接続できました。

# remote container 1
vscode ➜ /workspaces/exp $ python -m http.server 8000
Serving HTTP on 0.0.0.0 port 8000 (http://0.0.0.0:8000/) ...

# remote container 2
vscode ➜ /workspaces/exp_ubuntu $ curl http://172.17.0.1:8000
curl: (7) Failed to connect to 172.17.0.1 port 8000: Connection refused

vscode ➜ /workspaces/exp_ubuntu $ curl http://172.17.0.2:8000
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Directory listing for /</title>
</head>
<body>
<h1>Directory listing for /</h1>
<hr>
<ul>
<li><a href=".devcontainer/">.devcontainer/</a></li>
</ul>
<hr>
</body>
</html>

ちなみにローカルから Remote Container で動かしているコンテナにはアクセスできます。 これがアクセスできるなら 172.17.0.1 からも接続できそうなものですができません。

# remote container 1
vscode ➜ /workspaces/exp $ python -m http.server 8000
Serving HTTP on 0.0.0.0 port 8000 (http://0.0.0.0:8000/) ...
127.0.0.1 - - [23/Feb/2022 07:20:40] "GET / HTTP/1.1" 200 -

# ローカル
~ $ curl http://localhost:8000
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Directory listing for /</title>
</head>
<body>
<h1>Directory listing for /</h1>
<hr>
<ul>
<li><a href=".devcontainer/">.devcontainer/</a></li>
</ul>
<hr>
</body>
</html>

違い

ss 使って remote container の場合とそうでない場合を比較してみます。

# remote container で python -m http.server 8000 を動かした場合
$ ss -atn
State  Recv-Q Send-Q Local Address:Port    Peer Address:Port Process
LISTEN 0      511        127.0.0.1:8000         0.0.0.0:*
...

# docker run --rm -p 8000:8000 python:3 python -m http.server 8000 で動かした場合
$ ss -atn | grep 8000
LISTEN    0      4096         0.0.0.0:8000        0.0.0.0:*           
LISTEN    0      4096            [::]:8000           [::]:*

remote container だと 127.0.0.1 になっていて 0.0.0.0 でない。どうやらここが原因のようです。

調べてみると VSCode 側の設定でデフォルトだと 0.0.0.0 でなく localhost で listen する設定になっているとのこと。

stackoverflow.com

設定を変えると無事に remote container 間で 172.17.0.1 経由で通信することができました。

# remote container 1
vscode ➜ /workspaces/exp $ python -m http.server 8000
Serving HTTP on 0.0.0.0 port 8000 (http://0.0.0.0:8000/) ...
127.0.0.1 - - [23/Feb/2022 08:20:34] "GET / HTTP/1.1" 200 -

# remote container 2
vscode ➜ /workspaces/exp_ubuntu $ curl http://172.17.0.1:8000
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Directory listing for /</title>
</head>
<body>
<h1>Directory listing for /</h1>
<hr>
<ul>
<li><a href=".devcontainer/">.devcontainer/</a></li>
</ul>
<hr>
</body>
</html>

Python 風の自作言語を作ってみた

最近 Crafting Interpreters という interpreter を作る本を読んでいて、とりあえず本通りにやって Lox という言語の tree-walk interpreter を作りました。 作り終わって、この手の言語処理系を作る本では大抵ブロックを { } で表現するけれど Python のようにインデントでブロックを表現する言語の場合、Lexer, Parser はどう作ればよいのかなという疑問が生じました。また文末の ; もなくしてみたいと思い Lox interpreter の実装を元に自作言語に挑戦してみました。

元実装は Java 製でしたが私は Java でのテストの書き方をよく知らないので Go で書きなおしました。

ちなみに、Python のようにインデントでブロックを表現することを Off-side rule というらしいです。

github.com

文法

とりあえずまずは完成形をば。作った言語の文法は以下のような感じです。Python 風味なのはインデントをブロックとして扱っているくらいで、あとはもとの Lox 言語を踏襲しています。 keyword も Python と同じにすればより Python 風になったと思いますが、あくまで  off-side rule の言語の処理系が作りたいのであって、Python 処理系を作りたいわけではなかったのでそこはあまりこだわりませんでした。

// declare variable
var x = 10; // terminal ';' is optional

var こんにちは = "Hello World"
print(こんにちは) // => Hello World

// if statement
if expr:
  statements
elseif expr:
  statements
else:
  statements

// while loop
while expr:
  statements

// for loop
for var i = 0; i < 5; i = i + 1:
  print(i)

// function
fun fib(n):
  if n <= 1:
    return n
  return fib(n-1) + fib(n-2)

// closure
fun makeCounter():
  var i = 0
  fun count():
    i = i + 1
    return i
  return count

var counter = makeCounter()
print(counter()) // => 1
print(counter()) // => 2

// class
// there is no class variable
class Hoge:
  pass

class Hoge:
  hoge(x, y):
    pass

class Hoge:
  init(x, y):
    this.x = x
    this.y = y

class Hoge:
  piyo(x, y):
    print(x + y)

var h = Hoge()
h.name = "hoge piyo" // instance variable can define anytime
print(h.name) // => hoge piyo

// inheritance
class A:
  method():
    return "a"

class B(A):
  method():
    return "b"
  methodA():
    return super.method()

class C(B):
  pass

print(C().methodA()) // => a

// include another file
include "another.tlps" // path is relative path from the file which describe include statement

// indentation can be used for if branch, loop body and function body
var x = 1
  var y = 1  // indentation error

インデントをブロックとして扱う

手始めに Python の挙動を調べてみました。 今まで Python を書くときはスペース4つで表現してきたものの、2つでも書けるしこの辺の個数に何か制限はあるのかな?と。 試してみるとスペースが1つだろうが3つだろうが深さのレベルさえ同じならば個数に依存しなさそうということがわかりました。 スペース2個が { に対応するとかだったら話が簡単なのになと思っていたのですが的が外れました。

インデントをブロックとして扱う方法を自力では思いつかなかったので調べてみると以下の記事を見つけました。

lemniscus.hatenablog.com

行頭の空白の数の増減をスタックで管理しながら INDENT ({ に相当) だったり DEDENT (} に相当)を Token として生成すると。なるほど確かにその方法だと空白の数に制限をかけずに済みそうです。またこの方式から unindent does not match any outer indentation level という error は Lexer の時点で出すのが良さそうということもわかりました。

/tmp $ cat ex.py
def hoge():
    x = 1
  y = 2

/tmp $ python ex.py
  File "/tmp/ex.py", line 3
    y = 2
         ^
IndentationError: unindent does not match any outer indentation level

この情報から実際に実装してみたのがこの辺。Go の標準ライブラリには stack がなさそうだったので slice 使って自作しました。

https://github.com/goropikari/tlps/blob/423b76f03000e26273d74e52180f73b41fcce4cd/scanner.go#L232-L268

ブロックが使えるところに制限をかける

Python の場合、下記のプログラムの例のようにブロックを使える部分には制限があります。

/tmp $ cat ex.py
x = 1
  y = 2

/tmp $ python ex.py
  File "/tmp/ex.py", line 2
    y = 2
IndentationError: unexpected indent

Python の言語仕様を参考に自作言語では if や def のように : を使うものはブロックとして NEWLINE INDENT statements DEDENT を使うという制限をかけました。

block:
    | NEWLINE INDENT statements DEDENT 
    | simple_stmt

Python のブロック 10. Full Grammar specification — Python 3.9.7 documentation

また、ブロックを parse するときは for のブロックなのか if のブロックなのかということを区別するタグをつけるようにしました。ブロックが許されていないところでブロックが作られた場合は None というタグをつけました。そして interpreter がそのブロックオブジェクトを評価するときに None ならばエラーで落とすという仕様にしました。interpreter の処理を書いている途中で評価するときでなく parse 時点でエラーで落としてよかったなと思いましたが、まぁいいかととりあえずそのままにしました。

tlps/parser.go at 423b76f03000e26273d74e52180f73b41fcce4cd · goropikari/tlps · GitHub

ブロックを使うところに制限をかけてみると if, else に加えて elif のようなものもないと、if 文がネストの深い書き方になってしまうことに気付きました。

if (aaa) {
  xxx
} else if (bbb) {
  yyy
} else if (ccc) {
  zzz
}

: のあとにはブロックがくるとしたせいで、{} を使った↑と等価なことをしたい場合、↓のような書き方を強いることになってしまいました。 elif のような keyword を追加するか、else if xxx: のような書き方を許し else のあとに : がくるか if が来るかを判定する方法の2種類が考えられましたが、いろいろな言語が elif のような keyword を持っているのでそちらに合わせました。(Julia が好きなので elseif にしましたが)

if aaa:
  xxx
else:
    if bbb:
      yyy
    else:
      if ccc:
        zzz

文末の ; をなくす

元々の Lox 言語は print 123; のように文末を ; で終えるようになっていたのでこれを省略できるようにしてみました。簡単のために文は複数行にはならないと言う制限をかけ、; の代わりに \n を文の区切りとして使うことにしました。 元々の Lox 言語はスペースや \n といったいわゆる空白文字はすべて無視する仕様だったのでまずは \n を意味のある文字として Token にすることにしました。

ただ全ての \n を意味のあるものとする必要はなく、空白行の \n (コメントだけの行も含めて)は無視していいというか残したままだと parser 側の処理が面倒になりそうだったので無視するようにしました。

文末の ; を省略するのはこの程度の対応で実現することができました。

tlps/scanner.go at 423b76f03000e26273d74e52180f73b41fcce4cd · goropikari/tlps · GitHub

さいごに

インデントを使ってブロックを表現するにはどうしたらいいのかという疑問から初めた自作言語ですが、当初の目的以上に学ぶことが多くやってみてよかったです。

今 crafting interpreters の後半の VM を作る章を読み始めたところなので、読み終わったら自作言語の処理系も VM 方式にしてみたいと思います。