SKILL for the Skilled: Sorting With SKILL++

EDA SKILL

By Jim Newton on May 3, 2011

(この記事は、SKILL for the Skilled: Sorting With SKILL++の超訳です)

前回までのSKILL for the Skilledコラムでは、SKILL++の関数内ローカルな関数、高階関数、レキシカルスコープの特徴を見てきた。このコラムでは、さらに実践的な例をお見せした。

Functions are first class -- 第1級関数

SKILL言語では、関数は第1級のオブジェクトである。すなわち、関数は動的に生成され、関数自体を他の関数の引数として渡すことができる。次からの例で、関数を生成する関数をどうやって書くか、また、なぜそれが必要になるか、ということについて示そう。

Review of the SKILL sort function -- SKILLでのsort関数を振り返る

SKILLに組み込まれているsort関数は二つの引数を取る。最初の引数はソートされるべきリストで、2番目の引数は、二つの値をどのように比較するか、と言うことを示した比較関数である。比較関数は、TRUEもしくはFALSEを返す関数である。sort関数で指定する比較関数は、二つの引数を取り、この二つの値でどちらが優先されるべきか、と言うのを判定し、Boolean値を返す関数である。この比較関数には、SKILLのビルトイン関数が使える他、ユーザ定義の関数を使用することもできる。5.1の例は、比較関数にSKILLのビルトイン関数であるalphalesspを使用した例である。この例では、文字列のリストがアルファベット順にソートされる。

Sorting with built-in sort predicates -- 述語関数にビルトイン関数を用いた時のソーティング

;; Example 5.1
(sort (list "this" "is" "a" "list" "of" "words")
      'alphalessp)
  ==> ("a" "is" "list" "of" "this" "words")

前回の記事で見たように、もしSKILL++で書いているならば、alphalesspの関数名をそのまま渡してやればよい。

;; Example 5.2
(inScheme
  (sort (list "this" "is" "a" "list" "of" "words")
        alphalessp))
  ==> ("a" "is" "list" "of" "this" "words")

これから先の記事には、全て(inScheme ...)が付いていると思って欲しい。

Implementing SKILL++ sort predicates -- SKILL++での比較関数の実装

sort関数の述語比較関数は、関数オブジェクト(ファンクタ)かもしれない。実際、SKILLでは、いつかのオブジェクトが関数オブジェクトである。alphalesspのように、関数としてすでに存在しているか、もしくは、自動的にロードされるようなシンボルはcallable(ファンクタ？)である。また、lambdaによって作られる関数オブジェクトもcallable(ファンクタ)である。

グローバル関数は、procedureもしくはdefunを使用して、定義することができる。また、以前の例で見たように、fletやlabelsを使用して、関数をローカルに定義することもできる。また、lambdaを使って無名関数を作ることもできる。

例5.3のコードは、ファイルサイズを比較するfileLenghtLessp関数を定義している。

;; Example 5.3
(defun fileLengthLessp (f1 f2)
  (lessp (fileLength f1)
         (fileLength f2)))

例5.4は、fileLengthpが呼ばれた時と同様のことを行う無名関数である。この関数を動かす場合、変数に値をダイレクトに挿入するか、sort関数の引数として渡してやる場合のように、値をパッシングしてやる必要がある。

;; Example 5.4
(lambda (f1 f2)
  (lessp (fileLength f1)
         (fileLength f2)))

5.5, 5.6, 5.7の例では、ファイル名のリストをファイルサイズに応じてソートする方法である。SKILLには、ファイルサイズを返すビルトイン関数はあるが、ファイルサイズを比較するビルトイン関数はない。しかしながら、例5.3のfileLengthLessp関数をsort関数の引数とすることで可能である。

;; Example 5.5
(sort (getDirFiles ".")
      fileLengthLessp)

例5.6のように、無名関数を使うこともできる。

;; Example 5.6
(sort (getDirFiles ".")
      (lambda (f1 f2)
         (lessp (fileLength f1)
                (fileLength f2))))

また、例5.7のように、flet関数を使用してもできる。

;; Example 5.7
(flet ((lesspFileLength (f1 f2)
         (lessp (fileLength f1)
                (fileLength f2))))
  (sort (getDirFiles ".")
        lesspFileLength))

Reversing the sort order -- 逆順ソート

さらに二つの例を見てみよう。例5.8は、文字列のリストを降順に並べる方法である。

;; Example 5.8
(sort list_of_strings
      (lambda (a b)
         (greaterp (strlen a)
                   (strlen b))))

例5.9はリストのリストを要素数の降順に並べる方法である。

;; Example 5.9
(sort list_of_lists
      (lambda (a b)
         (greaterp (length a)
                   (length b))))

Components of the sort predicate -- ソートの述語関数

上であげた5.6, 5.8, 5.9のコードは同じような構造をしている。比較関数を抜き出して見てみよう。

  • test: 関係性を表す関数。例えば、数値の大小を比較するgreaterp, lesspやアルファべティックに文字を比較するalphalesspなどである。
  • key: 比較したいものから要素値を抜き出す関数。例えば、length, strlen, fileLength, identity.

The identity function

後ほど必要となるidentity関数をここで定義しておく。この関数は、引数をそのまま返す単項の関数である。例5.10で定義しているidentity関数は、加法に対しては0を返す関数、乗算に対しては、1を返す関数と言うように働く。

;; Example 5.10
(defun identity (x)
  x)

Higher order functions -- calculating a sort predicate: 高階関数 -- ソート述語関数を返す

SKILL++を使って、ソート関数に渡す比較関数を返す関数を作ることができる。SKILL++を使えば、関数を返す関数を作ることは容易である。

;; Example 5.11
(defun genCmpFunction (@key (test lessp)
                            (key  identity)) ;; see example 5.10
   (lambda (A B)
      (test (key A)
            (key B))))

例5.11で定義されるgenCmpFunctionは、キーワード引数?test, ?keyを使って呼び出され、ソート関数に適用できる関数を返す関数である。すなわち、sortの述語関数になる比較関数を返す関数である。引数のnameとkeyは標準的すぎて、混乱させてしまうかもしれない。例5.12に使用例を示す。デフォルトでは、keyにはidentity関数が、testにはlessp関数がセットされている。

Using the higher order function -- 高階関数を使う

この述語関数生成関数を使用することで、sort関数をより汎用的なものにできる。例5.5, 5.6, 5.7を書き換えたのが以下のコードである。

;; Example 5.12

;; reimplementation of example 5.6
;; sort a list of file names by increasing file size
(sort (getDirFiles ".")
      (genCmpFunction ?key fileLength))

;; reimplementation of example 5.8
;; sort a list of strings by decreasing string length
(sort list_of_strings
      (genCmpFunction ?key strlen
                      ?test greaterp))

;; reimplementation of example 5.9
;; sort a list of sub-lists by decreasing list length
(sort list_of_lists
      (genCmpFunction ?key length
                      ?test greaterp))

Reimplementing the sortcar function -- sortcar関数の再実装

もし、SKILLにsortcar*1ビルトイン関数がないとしても、次の例のように簡単に実装することができる。

;; Example 5.13
(defun sortcar (list predicate)
  (sort list
        (genCmpFunction ?test predicate
                        ?key car)))

Sorting objects from the Cadence Database -- Cadenceデータベースのオブジェクトをソートする

genCmpFunctionは、様々なクライテリアに従って、データベースをソートするための述語関数を生成することができる。例5.14では、Virtuoso Layoutのシェープ図形をtop edge*2の座標値順でソートするための関数である。

;; Example 5.14
(sort (geGetEditCellView)->shapes
      (genCmpFunction ?test greaterp
                      ?key  topEdge))

例5.15では、回路図中のインスタンスをアルファベット順に並べるための関数である。この例では、?key引数にdb-instanceの名前を取得するための無名関数を割り当てている。

;; Example 5.15
(sort (geGetEditCellView)->instances
      (genCmpFunction ?test alphalessp
                      ?key (lambda (i) i->name)))

Review

この記事では、以下のコンセプトについて概観した。

  • SKILLビルトインsort関数
  • 文字列をアルファベット順にソートする方法(例5.1, 5.2)
  • ファイルサイズに応じてファイル名をソートする方法(例5.5, 5.6, 5.7)
  • ソート述語関数を返す関数(例5.11)
  • ソート述語生成関数を用いて、sortcarを実装する方法
  • 高階関数を使用して、文字列やデータベースをソートする方法

To Be Continued

次の記事では、Virtuosoでの高階関数の使用例を示したい。例えば、セルの中にあるピン図形を時計回り順に並べたりする方法、である。さらに、genCmpFunctionを拡張して、2番目、3番目のソートクライテリアを与えられるようにする予定である。

Jim Newton

*1:リストのリストを第1要素順に並べ替える

*2:おそらく左端のこと