LoginSignup
20
10

More than 5 years have passed since last update.

@raviqqe

Goで本質的に並列な関数型言語つくった

Last updated at Posted at 2018-07-04

その名はCloe

TL;DR

  • 本質的に並列な関数型スクリプト言語を作った
  • 計算の並列度を部分的に変更可
  • データ競合は一切起こらない（副作用は例外）
  • 開発言語はGo
  • GILなんて要らなかった

ソースコード・ドキュメンテーション

例

Hello, world!

#!/usr/bin/env cloe

(print "Hello, world!")

HTTPサーバ

#!/usr/bin/env cloe

(import "http")

(def (handler request)
  ((@ request "respond") "Hello, world!"))

(let requests (http.getRequests ":8080"))

..(map handler requests)

背景

世の中に色々なプログラミング言語がありますが、これぞ理想の言語！みたいなのは中々出会えません。理由としては、

  • 設計がボトムアップ
    • 他の古い言語を改善することで新しい言語を作る
    • 例：機械語 -> アセンブリ -> C -> C++ -> Rust
  • 理想の言語って何？
    • 考えることが多い：構文、セマンティクス、型システム、パラダイム（オブジェクト指向、関数型等）
    • そんなもの設計できたら苦労しない
  • そもそもドメイン毎に最適なプログラミング言語が違う

ということで以下の点に注目してプログラミング言語を設計・実装しました。

  • レスポンシブなプログラム（後述）が簡単に書けるようにする
  • トップダウンで設計
    • 理想の言語について考えるのは諦める
    • 理想のプログラムのモデルを先に考える
    • それを実現する言語を設計
  • 並列・並行処理もほぼ自動化
    • データ競合とか面倒なのもランタイムで隠したい
  • 簡単な言語仕様

理想のプログラム

言語の設計をする前に、レスポンシブなプログラムとして理想的なモデルをまず先に考えました。

レスポンシブ性

レスポンシブなプログラムとは応答性の良いプログラムを表します。プログラムがある時点である入力を与えられたとき、なるべく速く出力を返したいわけです。例でいうと、タイピングゲームでユーザがキーを押したとき瞬時に画面に結果を反映できれば、応答性が良いということになります。

モデル

一言で言うと、プログラムの入力をプログラムが行う行動に変換する一つの関数としてプログラムを表現し、各行動を並列に評価することでレスポンシブなプログラムの実行を実現しています。より詳細な説明はこちら。

実装・ランタイム

ホスト言語

実装はGo言語で行いました。Goの良い点は、そこそこ速くて、並列処理が簡単に書けて、言語仕様が簡単なところです。ちょっとスクリプト言語実装しようかなみたいな場合にオススメです。

ランタイム

ランタイムのベースはHaskellとその並列処理ライブラリです。関数型言語的な特徴としては、遅延評価で純粋関数を使ったプログラミングが基本となっており、ここもHaskellとよく似ています。ここでは詳しく書きませんが、アカデミックには並列グラフ簡約と呼ばれる方法でプログラムの実行を行っています。プログラムをDAGとして表現し、そのグラフの各部分を並列に評価することで本質的に並列なプログラムの実行が可能になります。データ競合は基本的にこの処理の中でしか起こらないので、プログラマは並列処理に関わるデータコラプションやデッドロック等に気を使うことがありません。

また、計算の並列度はparとseqという関数によって自由に変えられるようになっています。前者は引数を全て並列に評価し、後者は引数を順々に評価します。

型システム

基本的にJSONに関数が加わったような型システムで動的型付けです。静的型付けでないのは、自分が型推論の処理を書けないからです。関数の宣言の仕方や引数の渡し方はPythonを参考にしてあります。

パフォーマンス

現在のところ、これについて書きたくないレベルで遅いです。1万件のクイックソートで約1.2秒かかっているので何とかしたい。ただ最適化の余地はかなり残っているので今後改善していく予定です。改善策としては、

  • VM化
    • 現在はAST的なものを関数実行の度にトラバース
  • ビルトイン関数をなるべくGoで書く
  • 関数内での無駄なメモリ割当を防ぐ
    • 遅延処理をいいことに余計な関数まで呼んでいる
  • その他ヒープ割当の削減
    • クイックソートのベンチマークを見てもGCでかなりの時間を取られている

等を考えています。

今後

流石にGoで開発していると色々自由が効かなくて困ったりします。Cでのユニオンはインターフェースで実現しないといけなかったり、最適化の点で様々な制限があります。本当はRustで書きたいのですが、Rustはまだ非同期プログラミングのサポートが弱いです。最近async/await構文がnightlyビルドにやっと入りましたが、メソッド等にはまだ使えません。Rustで書くとしてもおそらくそれらの機能が安定してからになると思います。

また、標準ライブラリももう少し充実させてスクリプト言語として常用できるレベルにはしたいです。JavaScriptのFlow的なものを作って静的型エラー解析できたら面白いかなーとも思います。前述したようにパフォーマンスも今後改善していく予定です。

まとめ

  • 並列・並行なプログラミング言語つくった
  • 副作用を除きデータ競合無し
  • ランタイムはHaskellを参考
  • つくろうオレオレ言語

オレオレ言語自分も作りたい！みたいな人の参考になればと思います。

20
10
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
20
10