massa142's blog

くり返す このポリリズム

「まつもとゆきひろ 言語のしくみ」を読んだ

まつもとゆきひろ 言語のしくみ

まつもとゆきひろ 言語のしくみ

発売直後に買ったまま積読してあった「まつもとゆきひろ 言語のしくみ」を読み終えた。

Streemの言語デザインを決めていくなかで、次のことが詳しく説明されていてとても勉強になった。

個人的には、比較対象としてPythonがよく登場しており嬉しかった。

ただ自分はC言語スキルが乏しいので、Streemの実装に関してはわからないところが多々あった。C言語について詳しくなった時に改めて読み直したい。

github.com

また、MatzがStreemのコンカレンシーモデルをRuby3に取り込もうとしてたのは知らなかった。Ruby3の話や実際に採用されたコンカレンシーモデルのGuildについてはRebuildでも話してたので、もう一度聞きなおそう。

この本のおかげで、プログラミング言語の言語デザインというものにとても興味が持てた。普段使っているPythonやGo、JavaScriptに関してはもっと深く知りたいと思え、自分が使ったことがないプログラミング言語も新たに学びたいという意欲がかきたてられてよい。

※ 自分にもっと技術力があれば、「自分も新しいプログラミング言語をデザインしてみよう」と思えたのかもしれない。

合わせて聞きたい

合わせて読みたい

読書メモ

第1章 さあ、どんな言語を作ろう

  • バーチャルマシン
    • システムバーチャルマシン - ハードをソフトでラップ
    • プロセスバーチャルマシン - ソフトで実現したCPU
  • CPUとメモリとメモリキャッシュについて
  • 構文木インタープリタを命令列に変換して、連続したメモリ領域に格納
  • Ruby1.9から「YARV」(Yet Another Ruby VM)が導入
  • Rubyの初期設計のときに、Pythonを意識していたことが書いてあって面白い
  • Pythonは"普通"過ぎた
  • 変数名・継承・エラー処理・イテレーター
  • 他の言語と比べながらの解説でわかりやすい

第2章 新言語「Streem」の設計と実装

  • 2-1 抽象的コンカレントプログラミング

    • 並列(Parallel)
      • 複数の処理を同時に行う
    • 並行(Concurrent)
      • 少なくとも見かけ上は複数の処理を同時に行う
    • プロセス
      • 「実行中のプログラム」のことを表す
      • それぞれのメモリー空間が独立
      • メモリー空間全体を複製することから、forkによるプロセス発生のコストは高い
        • Cow(Copy on Write)などで効率化しているけど
      • プロセス間通信も難しい
    • スレッド
      • 一つのプログラムの中でメモリー空間を共有しつつ、複数の制御の流れを実現
      • 整合性を維持する排他的制御(Mutex)が面倒
      • 結局システムコール呼び出しはコストになる
        • 特権命令が実行できるカーネル空間への切り替え
        • 膨大なCPU命令数
        • スタック領域としてのメモリー割り当て
    • アクターモデル
      • 非同期のメッセージをやり取りできるアクターという独自の制御の流れを持った存在
    • Erlang
      • Ericssonが開発したの知らなかった
      • Erlangのプロセスがアクターに相当
        • OSのプロセスと紛らわしい
    • Go
      • goroutine
      • メッセージ送信の対象はchan(チャネル)オブジェクト
    • Clojure

  • 2-2 新言語「Streem」とは

    • 「Stream」から名前変わってたの知らなかった
    • 21世紀のシェルスクリプト
      • 軽量なコンカレント実行
        • 一つのプロセスの中でCPU数に応じたスレッドを生成して、それらが交代で実行を引き受ける
      • コンカレント実行における競合状態の削除
        • すべてのデータをイミュータブルに
      • 計算モデル
        • シェルの実行モデルを参考に、抽象度が高い計算モデルを導入
        • そのぶん表現の自由度は下がる

  • 2-3 文法チェッカーをまず作る

    • 供給者・消費者パターン
    • ラウンドロビンパターン
    • 放送パターン
    • 集約パターン
    • 要求・応答パターン

  • 2-4 イベントループ

    • イベント処理を行うライブラリ

      • libevent
      • libev
      • libuv

    • I/Oイベントの検出

      • ブロックを回避するために、ファイルディスクリプターにデータが届いていることを確認する必要
      • select
      • epoll(Linux)
      • kqueue(BSD系OS)
    • 文法衝突みたいなうまくいかなかった話が面白い

  • 2-5 マルチスレッドとオブジェクト

    • マルチコアの実装が難しいのがわかる
    • 優先度付きキューのアルゴリズム面白い
    • ガーベージコレクション
      • libgc

    glibのメモリ管理でlibgc(boehm gc)を使う方法

    libgcは、GC_INIT()を最初によび、以下メモリ確保でGC_MALLOCなどをmallocの代わりに使うことで、freeしなくてもガーベージコレクタが機能するプログラミングを行えるライブラリです。

  • 2-6 キャッシュとシンボル

    • マルチコアではL1キャッシュは各コアが独立にもっていて、L2とL3は複数コアで共有することが多い
    • ‘There are only two hard things in Computer Science: cache invalidation and naming things.’ - Phil Karlton
    • 『"Don’t guess, measure!（推測するな、計測せよ！）”』
    • Rubyのシンボル

    https://docs.ruby-lang.org/ja/2.3.0/class/Symbol.html

    Rubyの内部実装では、メソッド名や変数名、定数名、クラス名など の`名前'を整数で管理しています。これは名前を直接文字列として処理するよりも 速度面で有利だからです。そしてその整数をRubyのコード上で表現したものがシンボルです。 シンボルは、ソース上では文字列のように見え、内部では整数として扱われる、両者を仲立ちするような存在です。 名前を管理するという役割上、シンボルと文字列は一対一に対応します。 また、文字列と違い、immutable (変更不可)であり、同値ならば必ず同一です。

    • Pythonは文字列をインターン化することで性能解決
      • Pythonは文字列がイミュータブルなため
    • シンボルごみ問題
      • GCする必要あり
      • 「弱い参照」(参照はしているがガーベージコレクション保護の対象にならない参照)

  • 2-7 AST(抽象構文木)に変換

    • 構文木のままトラバースして実行するのは性能が良くない
      • メモリー空間を飛び飛びにアクセスするためキャッシュ効率が悪い
      • VMのバイトコードに変換して連続的に解釈するのが望ましい

  • 2-8 ローカル変数と例外処理

    • ローカル変数の実装
      • 関数のコンパイル時にローカル変数ごとに個別のインデックスを割り当て
      • この配列がスタック
    • クロージャー
      • 関数オブジェクト(無名関数)に外側のスコープの変数が「閉じ込められている」
    • CやGoは明示的エラーチェック
      • コンカレントプログラミングと相性が悪い
    • 例外安全性が大事になる
    • SwiftのOptionalおしゃれ
      • Java8でも便利だった思い出

第3章 オブジェクト指向機能を設計する

  • 3-2 Streemのオブジェクト指向

    • Namespaces are one honking great idea
    • Python・JavaScriptはLisp-1
    • RubyやSmalltalkはLisp-2
    • StreemはLisp-1.5
      • 関数名を直接指定したときには関数への参照
      • 「.」を使ったメソッドチェーン形式では引数のないメソッド呼び出し

  • 3-3 Streem文法再訪

    • Lisp-2
      • メソッドキャッシュによる高速化
      • ネームスペースに分散した関数を総称的に扱うのが得意でない

  • 3-4 パターンマッチ

    • 末尾再帰化でスタックの無駄遣いを解決

第4章 Streemオブジェクトを実装する

  • 4-1 ソケットプログラミング

    • そもそもソケットとは

  • 4-3 オブジェクト表現とNaN Boxing

    • CPython: オブジェクトへの参照は構造体へのポインタ
      • 単純ポインタ法
      • 構造体へのアクセス最速
      • オブジェクトへの割り当てが大量になる
    • CRuby・Emacs Lisp: ビットに型情報を詰め込み、整数の値など一部の値を参照に直接埋め込む
      • Tagged Pointer法
      • メモリ効率Up
    • mruby・Lua: オブジェクトへの参照は構造体
      • シンプル & 移植性の高さ
      • メモリ効率Down
    • V7: NaNの浮動小数点でオブジェクト表現

  • 4-4 ガーベージコレクション

    • トレース法
      • 「生きている」オブジェクトを確実に検出
      • 処理時間が長い
      • マークアンドスイープ法 / コピー法
    • 世代別GC
      • 「若い」オブジェクトを重点的にスキャン(マイナーGC)
      • 旧世代領域から新世代領域への参照はリメンバーセットで管理（write barrier）
      • 全ての領域をスキャンするフルGC(メジャーGC)
      • 実行時間を短くできるが、最大停止時間は変わらない
    • インクリメンタルGC
      • 処理を細切れにして少しずつ実行
      • 世代別GCと同様んひライトバリアを使用
      • 実行時間は長くなるが、最大停止時間は抑えられる
    • リファレンスカウント法
      • オブジェクトの解放を局所的に判断できる
      • 停止時間も短くなる
      • 循環参照を持つオブジェクトを解放できない
      • 並列処理と相性が悪い
    • 例えば GC を止める・Ruby ウェブアプリケーションの高速化
    • Dismissing Python Garbage Collection at Instagram

第5章 ストリームプログラミングを強化する

  • 5-1 パイプラインプログラミング