Interface 2020年5月号の読書メモ。

第1部と第2部のみ記載、第3部はRustとGoの説明。

第1部　進化を続けるプログラミング言語の世界

• プログラミング言語の分類
  • 分類その1　コンパイル言語 vs 非コンパイル言語
    • コンパイル言語はAOTコンパイラを用いる言語
      • 代表例としてはC言語やJavaなど
    • 非コンパイル言語はJITコンパイラやインタプリタを用いる言語
      • 代表例としてはPythonやRubyなど
  • 分類その2　型のある言語 vs 型のない言語
    • 型とは、intやfloat、文字列といったデータ型のことを指す
    • 型のある言語とは、強い静的型付けを行う言語のこと
    • 静的型付けとは、コンパイル時にあらゆる変数の型を決定すること
    • 強いとは、コンパイル時に行われる型検査で、型の安全性が保証されること
      • 2つの変数が同じ型を持つと判定されたら、実行時のその2つの変数の間で代入が行われても、型の不一致によるエラーは発生しないことが保証されている
    • C言語は静的だが弱い型を持つ言語
    • Javaは強い静的型付けを行う言語
  • 分類その3　手続き型 vs 関数型
    • 手続き型とは、命令を順に並べることでプログラムを作る言語
      • C言語、Javaなど
    • 関数型とは、プログラムの基本単位が式と関数であり、関数の入力(引数)と出力(返り値)をつなぐことでプログラムを作る言語
      • Haskell、Elixirなど
  • 分類その4　ウェブ・フロントエンド系言語かそうでないか
    • 1~3は機能的な分類であるが、4は応用用途による分類
    • ウェブ・クライアントとして、ブラウザ上で動くことを前提としたプログラミング言語
    • 代表例はJavaScriptやTypeScriptなど

第2部　プログラミング言語＆コンパイラの基礎知識

• プログラミング言語の実行方式による分類
  • コンパイラ(一括翻訳)型
    • テキストで記述したプログラムを一括翻訳(コンパイル)し、コンピュータ上で実行できるバイナリ形式にして実行する
    • プログラムの実行前に、CPUが実行できる命令に変換するため、オーバーヘッドがない
    • プログラムを修正するたびにコンパイルする必要がある
    • 代表例：C、Fortran、Ada、Rust
  • インタプリタ(逐次翻訳)型
    • テキストで書かれたプログラムを逐次読み出して解釈してコンピュータを動かす
    • 逐次、テキストで記述されたプログラムを読み出して解釈するため、実行時のオーバヘッドが大きい
    • 手軽にプログラムを変更して実行確認できる
    • 代表例：Python、Ruby、Perl、Bash
  • 中間言語・仮想マシン
    • インタプリタ型の言語で、速度面の改善のために一度中間言語や仮想マシンを介して動く形式を採用している場合もある
    • コンパイラ型の言語で、LLVMのようにCコンパイラで、LLVM IRのようなコンピュータに依存しない中間言語を利用できる処理系も存在する
    • 代表例：Java
• 機械語からアセンブリ言語、高級言語の登場、現在主流の言語までの歴史的な経緯
• 原点となる概念
  • リスト構造、ラムダ式をベースにして関数型言語の基となったLISP
  • メッセージをベースにした純粋なオブジェクト指向を実現したSmalltalk
  • 一番普及した手続き型言語C
• C言語の大きな特徴
  • 手続き型の高級言語としての側面
    • 構造化、モジュール化、タイプチェックの厳格な言語仕様により、アルゴリズムを読みやすく、保守しやすく記述可能
  • 汎用のマクロ・アセンブラとしての側面
    • OSを記述するために、実コンピュータ・ハードウェアに適合してプログラムを効率的に走らせるための良いコードに変換することを目的としている
    • CPUの演算に依存する仕様はあえて緩やかな規定になっている
• Cコンパイラ
  • GCC
    • 現存するほぼすべてのCPUに対応しており、特定のCPUによらずに開発されている
      • 特定のCPUの最適化は、個別のCPUに特化したコンパイラ(Intel C Compilerなど)と比べて性能面で劣る
    • 汎用コンパイラとして、C++、Objective-C、Go、Fortran、Adaなどの言語に対応
  • LLVM
    • GCCはGPLライセンスのため、商用向けにコンパイラの各機能を個別にモジュールとして新しいコンパイラ・ツールを開発するには使いにくい
    • LLVMはコンパイラの各機能をモジュール化し、BSDライセンスでリリースされた
      • 現在は条件付きApache Licenseとなっている
    • JavaのようなCPUに依存しないビット・コードを作成し、それからターゲットCPU向けに翻訳する仕組み
    • 移植しやすく、コンパイルの各段階で最適化、高速化、デバッグ・ツールの研究開発が進んでいるため、さまざまなコンパイラ・ツールが開発されている
• モダン・コンパイラLLVMの基礎知識
  • LLVMがどのようにコンパイラ開発を変えたか
    • LLVM中間言語(LLVM IR)により、コンパイラ開発の揚力を大幅に削減できる
      • 中間言語がないと、各高級言語に対して、各機械語へコンパイルするための実装は、「高級言語の数×機械語の数」となる
      • 中間言語を挟むことで、各高級言語について、中間言語へコンパイル、中間言語から機械語へのコンパイルのみを実装すればよく、「高級言語の数+機械語の数」の実装でよくなる
      • 最適化のアルゴリズムも中間言語で実装するため、再利用が可能
      • 機械語依存の最適化を実装する場合、高級言語とは独立して実装可能
  • ライセンス
    • LLVMを用いて作ったソフトウェアを使用、複製、変更、複合、公開、配布、再使用権許諾、売却を許す。ただし、
      • LLVMの再配布をする際に同じライセンスを提示しなければならない
      • LLVMを用いて作ったソフトェアをLLVM開発者の名でプロモーションしてはならない
    • GPLライセンスのように、企業が再配布する際にはソースコードを公開しなければならないといったことが発生しない
  • 構造
    • LLVMを基盤とするコンパイラが、高級言語を機械語へ翻訳する処理手順
      1. 任意の高級言語からLLVM IRへの翻訳を行うフロントエンド
      2. LLVM IRからLLVM IRへの最適化または計装(検査用のコード挿入)のためのコード変換を行うミドルレンジ
      3. LLVM IRから任意の機械語への翻訳、CPUアーキテクチャ依存の最適化を行うバックエンド
    • フロントエンド
      • C言語の場合、字句解析、構文解析、意味解析を実装し、最適化前のLLVM IRのコードを生成する
      • Clangを用いたLLVM IR出力例
        • clang -S -emit-llvm main.c -o main.ll
    • ミドルレンジ
      • LLVM IRで最適化を行う
      • optというLLVM IRの変換ツールがある
        • 実行例：opt -S -O3 main.ll
      • optツールは、Passと呼ばれる静的解析およびコード変換のモジュールを複数動作させるための道具
        • Passの依存関係を踏まえながら、複数回同じPassが実行されないように静的解析で得られた情報を管理する
        • -O3フラグで実行されるPassは250個以上
    • バックエンド
      • LLVM IRからCPUアーキテクチャの機械語へ翻訳する
      • x86、ARM、MIPS、PowerPCなどに対応
      • 実行例
        • llc mail.ll -o main.asmでLLVM IRからアセンブリ・コードへ変換
        • clang main.asm -o fooでアセンブリコードを実行可能バイナリへ変換
          • アセンブラはClangに内蔵
    • LLVM IRの主要な特徴
      1. SSA(Static Single Assignment)形式：1つの変数が1度しか定義されない性質
      2. 型安全：アセンブリ・コードと違い型が定義されており、狭義の型安全性を持つ
    • optツールが使うPassモジュールの自作
      • データ・フロー解析を実装する
      • 詳細は書籍を参考