Easy-ISLispのコンパイラ

  • 0
    いいね
  • 0
    コメント

    はじめに

    Easy-ISLispのためのコンパイラを開発しています(FAST計画といいます)。平成29年8月頃をめどにリリースの予定です。仕様、問題点などを書き留めておこうと思います。

    基本的アイディア

    萩谷先生などのGCLを参考にしています。ISLispコードを等価なCコードに変換し、GCCによりオブジェクトファイルを生成します。これを動的にリンクすることによりISLisp処理系に読み込んでいます。関数の内部定義はGCCの拡張機能を利用しています。このためlabels、flet構文のスコープに制限があります。

    コンパイル方法

    起動時に-cオプションを使ってコンパイラを読み込んおくか、あるいはload関数でコンパイラを読み込みます。コンパイラのソースはcompiler.lspです。コンパイル済みのものはcompiler.oとなっています。

    (compile-file filename) でコンパイルを開始します。filenameは文字列で与えます。compile-file関数はLispファイルを基にC言語によるファイルを生成します。さらにGCCを起動し、動的リンクオブジェクトを生成します。

    セルフコンパイル

    (compile-file "compiler.lsp")とするだけです。compiler.oというオブジェクトファイルが生成されています。以後は eisl -c compiler.o としてコンパイル済みのものを読み込みます。コンパイルが高速になります。

    コンパイル済みのファイルのload

    通常のLispファイルと同様にload関数で読み込みます。識別子がo(オー)の場合には、load関数は動的リンクの処理をします。

    小整数の即値化

    インタプリタのEISLでは小整数も含めてすべてにつきセルオブジェクトを生成していました。このためにすぐにGCが起動し高速化は困難でした。コンパイラでは -999999999 ~ 999999999 までの整数は即値化をし、セル消費をしないようにしています。この結果、竹内関数やフィボナッチ数列の計算はかなり高速化することができました。

    > (load "tarai.o")
    T
    > (time (tarai 12 6 0))
    Elapsed Time(second)=0.068000
    <undef>
    > (time (fib 40))
    Elapsed Time(second)=1.194000
    <undef>
    > 
    
    

    末尾再帰最適化

    ISLisp規格では末尾再帰最適化は要請されていません。しかし、Schemeと同様に末尾再帰を繰り返しに置き換えるコードを生成しています。次の程度であればスタックも消費しませんし、速度もまずまず高速です。

    (defun foo (n)
      (if (= n 0)
          t
          (foo (- n 1))))
    
    > (load "test.o")
    T
    > (foo 1000000000)
    T
    > (time (foo 1000000000))
    Elapsed Time(second)=1.789000
    <undef>
    > 
    

    コンパイラのための拡張機能

    コンパイラのために次の関数を独自拡張しました。

    (subrp x) xが組み込み関数である場合にt、そうでなければnil
    (macrop x) xがマクロである場合にt、そうでなければnil
    (system str) str文字列をOSで実行する。GCC起動のため
    (freedll) 直前に動的リンクしたファイルをリンク解除する。
    (fixnump x) 小整数の場合にt、そうでなければnil
    (longnump x) LONGNUMの場合にt、そうでなければnil
    (bignump x) BIGNUMの場合にt、そうでなければnil
    (readed-array-list x)  #2a((1 2)(3 4))のような定数の配列をリスト((1 2)(3 4))に変換する。
    (ignore-toplevel-check x) 引数としてtを渡すとdefclassなどのトップレベルチェックを外す、nilを渡すと元に戻してチェックをする。
    (self-introduction) Linux系ならばlinuxシンボル、Windowsならwindowsシンボルを返す。
    コンパイラがOSの種類によって動作を変えるため。

    (get-method x) 名前xの包括関数のmethodをすべて取り出す。
    (get-method-body x) method x の実体を取り出す。
    (get-method-priority x) method x の優先順位を取り出します。
    整数値であり次のようになっています。
    AROUND 11
    BEFORE 12
    PRIORITY 13
    AFTER 14

    これらは包括関数のコンパイルに使います。包括関数はインタプリタでいったん、すべてのmethodを整理、保存した後においてその実体を取り出し、SUBRに変換します。

    (format stream string)
    string中にシングルクォートが2つ続いていた場合に独自の動作をします。連続したシングルクォートの間の文字列に対しては~%などの特殊文字制御を無視します。また、連続した2つのシングルクォートは1つのダブルクォートに変換されます。これはLispコードをCコードに変換し文字列ストリーム中にプールし、最後にファイルに出力する関係上、必要になったものです。

    > (format (standard-output) "''hello~% world~A ''")
    "hello~% world~A "NIL
    > 
    
    

    スコープの制約

    以下はM.Hiroiさんのページからの引用コードです。これはISLisp仕様を満たした正しいコードです。

    (defun iota (n m)
      (for ((m m (- m 1))
            (a nil (cons m a)))
           ((< m n) a)))
    
    

    FASTのfor構文では、これが意図通りに動作しません。変数部の(m m (- m 1)) で第1番目のmはforで使う変数であり、第2番目は引数として与えられたmです。for構文はこれを初期値としますが、そのスコープはforの外側を見ています。FASTはC言語に変換しており、Cのスコープはそのようになっていません。FASTでは次のように書いてください。

    (defun iota (n m)
      (for ((m1 m (- m1 1))
            (a nil (cons m1 a)))
           ((< m1 n) a)))
    
    

    labels flet の制約

    C言語では関数内に局所関数を定義することはできないこととなっています。GCCは拡張機能によりこれが可能となっています。静的スコープの動作を確保しつつ速度を稼ぐのにこの拡張機能を使いました。しかし、スコープがLispのものとは異なります。

    lambdaの実装

    lambdaは本来、無名関数なのですが、Cの関数にするために敢えて名前を付けています。compile-fileのファイル名+自然数をその名前としています。静的スコープにするためには自由変数を保持しておく必要があります。これはGCLの方式をヒントにしました。保持しておかなければならない自由変数をリストにしてlambdaの関数名シンボルに紐つけてあります。lambda本体でアクセスするときにはnthで行っています。

    lambdaの制約

    lambda式のネストは3重までです。それ以上はエラーとなります。

    以下はM.Hiroiさんのページからの引用コードです。これはISLisp仕様を満たした正しいコードです。

    (defun id-search (start goal)
      (labels ((dfs (limit path)
                 (if (= limit (length path))
                     (if (eq (car path) goal)
                         (print (reverse path)))
                   (for-each
                    (lambda (x)
                      (if (not (member x path))
                          (dfs limit (cons x path))))
                    (cdr (assoc (car path) adjacent))))))
        (for ((limit 1 (+ limit 1)))
             ((= limit 7))
             (format (standard-output) "----- ~D -----~%" limit)
             (dfs limit (list start)))))
    

    FASTコンパイラでは、これがコンパイルできません。lambdaはトップレベルにおいて名前をもったC関数として生成されます。lambdaの中で局所定義関数のdfsを呼び出しています。生成されたlambdaに相当するC関数からはCの局所定義関数として生成したdfsを参照することができません。

    そこで、このような場合には下記のようにlabelsを使わないで書いてください。

    (defun id-search (start goal)
      (for ((limit 1 (+ limit 1)))
           ((= limit 7))
           (format (standard-output) "----- ~D -----~%" limit)
           (dfs limit (list start))))
    
    (defun dfs (limit path)
      (if (= limit (length path))
          (if (eq (car path) goal)
              (print (reverse path)))
          (for-each
            (lambda (x)
              (if (not (member x path))
                  (dfs limit (cons x path))))
            (cdr (assoc (car path) adjacent)))))
    

    block return-fromでの制限

    タグシンボルはその関数内でのスコープとなっています。しかし、FASTでは同じタグシンボルは他の関数においても同じものと扱われてしまい、意図した動作になりません。当面、異なる関数でblockを使う場合には、異なるシンボルを割り当ててください。

    追記、上記は私のISLisp仕様の理解不足からくるものです。block return-fromはレキシカルです。インタプリタ、コンパイラともに修正しました。ver0.66で直ります。

    包括関数での制約

    以下はM.Hiroiさんのページからの引用コードです。これはISLisp仕様を満たした正しいコードです。

    (defgeneric hash-func (k))
    
    (defmethod hash-func ((s <string>))
      (for ((i 0 (+ i 1))
            (a 0))
           ((>= i (length s)) a)
           (setq a (+ (* a 8) (convert (elt s i) <integer>)))))
    
    
    

    method定義では引数名は包括関数を定義したときと異なる名前を付けても正しく動作する必要があります。インタプリタはその通りになっています。コンパイラの方は簡単にするために引数の名前を同じにしないといけないという制約があります。α変換をすればできるのだとは思うのですが、簡単に済ませることにしました。次のように記述する必要があります。

    (defgeneric hash-func (k))
    
    (defmethod hash-func ((k <string>))
      (for ((i 0 (+ i 1))
            (a 0))
           ((>= i (length k)) a)
           (setq a (+ (* a 8) (convert (elt k i) <integer>))
    
    

    C言語ソースとの混在

    ISLispの関数記述中にC言語ソースを挿入できる機能を独自拡張しています。GCCの豊富なライブラリを簡便にISLispから使いたいためのものです。以下は単純なサンプルです。

    (c-include "<stdio.h>")
    
    (defun 1+ (n)
      (c-lang "N+1"))
    
    > (compile-file "test.lsp")
    initialize
    pass1
    pass2
    compiling 1+ 
    finalize
    invoke GCC
    T
    > (load "test.o")
    T
    > (1+ 3)
    4
    > 
    
    

    このようにCでの記述を混在できます。これを利用してラズパイのWiringPIを呼び出すとか、socketを呼び出す関数をLisp関数として記述することができます。CFFIに拠らないため、簡単にCとリンクできます。

    用意してある関数は下記のものです。
    (c-include x) #includeを挿入します。 例 (c-include "")
    (c-define x y) #defineを挿入します。 例 (c-define "MAXINT" "999999999")
    (c-lang x) c言語ソースを挿入します。 例 (c-lang "a = a+1;")
    (c-option x) コンパイルオプションを追加します。 例(c-option "-lwinmm")
    いずれの関数もインタプリタにおいては無視されます。

    下記はWindowsのAPIを利用してMidi回線をオープンする関数の記述例です。

    (c-include "<windows.h>")
    (c-include "<mmsystem.h>")
    
    (c-option "-lwinmm")
    
    (c-define "MIDIMSG(status,channel,data1,data2)"
              "( (DWORD)((status<<4) | channel | (data1<<8) | (data2<<16)) )")
    
    (c-lang "HMIDIOUT hMidiOut;")
    
    (defun midi-out-open ()
      (c-lang "midiOutOpen(&hMidiOut, MIDI_MAPPER, 0, 0, CALLBACK_NULL);" )
      t)
    
    

    ソースコード、実行ファイル

    ソースコードは拙作「ISLisp制作キット」の付録としてアップロードしてあります。不具合検出をしつつ、定期的にバージョンアップをしています。
    https://www.amazon.co.jp/dp/B01IMUKOHS

    無償配布の実行ファイルは下記にアップロードしてあります。コンパイラのソースとコンパイル済みのコンパイラも付属しています。
    http://eisl.kan-be.com/library/easyislisp.html

    現状でアップしてあるのはver0.63で、まだ開発途上のものです。また、拙作の学習用プログラム開発環境BabbageにはWindows版のver0.63を同梱しています。いずれも竹内関数やフィボナッチ数列程度のものであればコンパイル、動作は可能です。ILOSオブジェクトシステムなどを含めて、より完成度を上げたものを平成29年8月にアップロードの予定にしています。

    Babage
    http://eisl.kan-be.com/babbage.html