関数ポインタとコールバック関数

JavaScript のプログラムで、以下のようなコーディングがよく使われる。このプログラムでは、3と4を加えた結果が出てくるが、関数の引数の中に関数宣言で使われるfunctionキーワードが出てきているが、この意味を正しく理解しているだろうか？

このような (function()…)は、無名関数と呼ばれている。(=>を使った書き方はアロー関数と呼ばれている)　これは「関数を引数として渡す機能」と、「一度しか使わないような関数にいちいち名前を付けないで関数を使うための機能」であり、このような機能は、関数を引数で渡す機能はC言語では関数ポインタと呼ばれたり、新しいプログラム言語では一般的にラムダ式などと呼ばれる。

// JavaScriptの無名関数の例 3+4=7 を表示
console.log( (function( x , y ) {
                 return x + y ;
              })( 3 , 4 ) ) ; // 無名関数
console.log( ((x,y) => {
                 return x + y ;
              })( 3 , 4 ) ) ; // アロー関数

C言語の関数ポインタの仕組みを理解するために、以下のプログラムを示す。

int add( int x , int y ) {
   return x + y ;
}
int mul( int x , int y ) {
   return x * y ;
}
void main() {
   int (*f)( int , int ) ; // fは2つのintを引数とする関数へのポインタ
   f = add ;               // f = add( ... ) ; ではないことに注意
   printf( "%d¥n" , (*f)( 3 , 4 ) ) ; // 3+4=7
                 // f( 3 , 4 ) と書いてもいい
   f = mul ;
   printf( "%d¥n" , (*f)( 3 , 4 ) ) ; // 3*4=12
}

このプログラムでは、関数ポインタの変数 f を定義している。「 int (*f)( int , int ) ; 」 は、“int型の引数を2つ持つ、返り値がint型の関数”へのポインタであり、「 f = add ; 」では、f に加算する関数addを覚えている。add に実引数を渡す()がないことに注目。C言語であれば、関数ポインタ変数 f には、関数 add の機械語の先頭番地が代入される。

そして、「 (*f)( 3 , 4 ) ; 」により、実引数を3,4にて f の指し示す add を呼び出し、7 が答えとして求まる。

こういう、関数に「自分で作った関数ポインタ」を渡し、その相手側の関数の中で自分で作った関数を呼び出してもらうテクニックは、コールバックとも呼ばれる。コールバック関数を使うC言語の関数で分かり易い物は、クイックソートを行う qsort() 関数だろう。qsort 関数は、引数にデータを比較するための関数を渡すことで、様々な型のデータの並び替えができる。

#include <stdio.h>
#include <stdlib.h>

// 整数を比較するコールバック関数
int cmp_int( int* a , int* b ) {
   return *a - *b ;
}
// 実数を比較するコールバック関数
int cmp_double( double* a , double* b ) {
   double ans = *a - *b ;
   if ( ans == 0.0 )
      return 0 ;
   else if ( ans > 0.0 )
      return 1 ;
   else
      return -1 ;
}

// ソート対象の配列
int    array_int[ 5 ] = { 123 , 23 , 45 , 11 , 53 } ;
double array_double[ 4 ] = { 1.23 , 12.3 , 32.1 , 3.21 } ;

void main() {
   // 整数配列をソート
   qsort( array_int , 5 , sizeof( int ) ,
          (int(*)(const void*,const void*))cmp_int ) ;
   //     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~この分かりにくい型キャストが必要なのがC言語の面倒な所
   for( int i = 0 ; i < 5 ; i++ )
      printf( "%d\n" , array_int[ i ] ) ;
   // 実数配列をソート
   qsort( array_double , 4 , sizeof( double ) ,
          (int(*)(const void*,const void*))cmp_double ) ;
   //     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   for( int i = 0 ; i < 5 ; i++ )
      printf( "%f\n" , array_double[ i ] ) ;
}

無名関数

コールバック関数を使っていると、データを比較するだけの関数とか簡単な短い処理が使われることが多い。こういった処理を実際に使われる処理と離れた別の場所に記述すると、プログラムが読みづらくなる。この場合には、その場で関数の名前を持たない関数(無名関数)を使用する。(C++の無名関数機能は、最近のC++の文法なのでテストには出さない)

void main() {
   int (*f)( int , int ) ; // fは2つのintを引数とする関数へのポインタ
   f = []( int x , int y ) { return x + y ; } ; // add を無名関数化
   printf( "%d¥n" , (*f)( 3 , 4 ) ) ; // 3+4=7

   // mul を無名関数にしてすぐに呼び出す3*4=12 
   printf( "%d¥n" , []( int x , int y ) { return x * y ; }( 3 , 4 ) ) ;
   // メモ：C++11では、ラムダ式=関数オブジェクト
   //      C++14以降は、変数キャプチャなどの機能が追加されている。
}

C++の変数キャプチャとJavaScriptのクロージャ

JavaScript のクロージャ

JavaScriptにおいて、関数オブジェクトの中で、その周囲(レキシカル環境)の局所変数を参照できる機能をクロージャと呼ぶ。クロージャを使うことでグローバルな変数や関数の多用を押さえ、カプセル化ができることから、保守性が高まる。

// JavaScriptにおけるクロージャ
function foo() {
   let a = 12 ; // 局所変数
   console.log( (function( x , y ) {
                    return a + x + y ;  // 無名関数の外側の局所変数aを参照できる
                 })( 3 , 4 ) ) ;
}
foo() ;

C++の変数キャプチャ

C++でも無名関数などでクロージャと同様の処理を書くことができるようにするために変数キャプチャという機能がC++14以降で使うことができる。

// C++のラムダ関数における変数キャプチャ
void main() {
   int a = 12 ;
   printf( "%d\n" ,
           [a]( int x , int y ) {  // 変数キャプチャ[a]の部分
              return a + x + y ;   // 局所変数aをラムダ関数内で参照できる。
           }( 3 , 4 ) ) ;
   return 0 ;
}

トランザクション処理

トランザクション処理とは、相互に依存関係にある複数の処理を矛盾なく処理することであり、データベースでは、ACID特性(原子性,一貫性,隔離性,耐久性)がもとめられる。この時、直列化可能(様々な順序で処理できるかもしれないけど、矛盾しない結果となる処理順序が存在すること)であることが求められる。

例えば、以下のように、50万円のデータがあった時、入金処理と出金処理がほぼ同じタイミングで開始された場合、入金処理が終わらないうちに、出金処理が開始されると、以下の例では入金処理が無視されてしまう。

上記のような問題が発生しないようにするには、以下のように、入金処理の時点で他の更新処理を排除するLOCK処理を行い、入金データの書き込みを終えた時点でUNLOCK処理を行う、排他処理が重要となる。(ロックされている間は、アクセスを禁止する。)

排他処理の実装方法

排他処理を実現する方法としては、ロック(Lock)、セマフォ(Semaphore)、ミューテックス(Mutex)が使われる。

ロックの例としては、C言語では flock() 関数が有名。(後述のロッキング方式/悲観的制御を参照)

• C言語でのファイルロック(共有ロック,排他ロックの機能あり)
• 共有ロック：他のプロセスの読み込みは許可するけど、書き込みは禁止。
• 排他(占有)ロック：他のプロセスの読み込みも書き込みも禁止する。
• 使い終わったらアンロック。

セマフォの例としては、カウンタセマフォが使われる。

• 対象資源を使用中のプロセスの数を表す、カウンタを使う。
• 初期値0の状態は、だれも使っていない状態。
• 対象資源を使う時にカウントアップ、使い終わったらカウントダウンする。

ミューテックスは、セマフォの使用中/開放状態を 0,1 で管理するようなもの。

ロックはファイルに対して使うもので、セマフォやミューテックスは、プロセスやスレッド間の同期に使うことが多い。

同時実行制御

複数のトランザクションによるデータアクセスで、トランザクション処理を直列化可能にすることを、同時実行制御と呼ぶ。この方式には、2つの方法がある。

1. ロッキング方式(悲観的制御)
   先行するトランザクションは、データにロックをかけ、他のトランザクションを一時的に排除する方式。後発の処理はアンロックされるまで待たされることことから、これが処理効率の低下となる。
   • ロッキング方式では、ロックをかける大きさ(粒度)が大きいと、待ち処理が発生する可能性が高い。一方で、粒度を小さくしようとすると、ロックの判定が難しくなり効率が低下する可能性も出てくる。
     
   • ロックの種類
     ロックには、読み出し中心のデータと書き込みで更新のかかるデータでは、ロックのかけ方が異なる。例えば、読み出し中のデータは値が変化しないことから、同じタイミングで読み出し処理が発生しても、待たせる必要は無い。
     この時、データを読み出す際にかける共有ロック(Read Lock)と、書き込みの際にかけるロック占有ロック(Write Lock)がある。
   • 2相ロッキングプロトコル
     トランザクションのロックの操作は、ロックをかける操作が続く成長相と、ロックを解除する操作が続く縮退相に分けて行うことが多い。これを2相ロッキングプロトコルと言う。
2. 時刻印方式/タイムスタンプ方式(楽観的制御)
   データの競合の発生頻度が低い場合には、ロッキング方式は待ち処理時間が無駄となるため、同時アクセスを許す方式。ただし、あとで処理の発生した時間(タイムスタンプ)を確認し不都合が判明した場合は、処理の記録をもとにロールバックしてやり直す方式。

デッドロック

複数のトランザクションの実行時には、相互の関係から、処理がうまく進まない場合も発生する。(お互いが相手の処理をロックする状態で、ロック解除が発生しない。)

このような状態をデッドロックと呼び、この状態が発生すると処理が停止してしまうこともある。このような状態は、避けられない場合もあるが、どの処理が何を使うのか、どのデータはどの処理の終了を待っているのかといった資源の状態をグラフ理論で表現したもの資源グラフをで表現し、グラフが巡回するようであれば、デッドロックが発生する可能性がある。

グラフ理論(Wikipedia)

前述の資源グラフをコンピュータで扱う場合には、グラフ理論が用いられる。グラフ理論では、ノード間の接続に方向の概念が無い物は無向グラフと呼ぶ。また、ノードの接続関係は隣接行列で表現する。行と列がそれぞれノードに対応付け経路が存在する場所を1で表す。データベースの資源グラフのような方向性がある場合は有向グラフと呼び、始点(行)と終点(列)の経路がある所を1で表す。

ここまでの授業では、プログラムを動かすうえでアルゴリズムとデータ構造を中心に話をしてきた。しかしプログラムの中で利用しているデータがどういったメモリで管理されているのかを正しく理解する必要がある。そこで、局所変数のようなデータを保存するためのスタック領域と、new 命令で確保されるヒープ領域についてその使われ方などについて理解する。

C言語やJavaでのメモリ領域(静的領域とスタック領域)

C言語では、データ領域は、定数領域、静的変数領域、スタック領域、ヒープ領域 で構成される。また、変数にはスコープという変数が使える範囲がある。

定数領域は、値が変化しないデータが保存される。

静的変数領域は、プログラムが起動したときに確保され、プログラム終了と共にデータが消される。

スタック領域は、関数が呼び出される時に確保され、関数を抜ける時にデータが消される。関数の引数や関数の局所変数などは、この領域に保存される。

#include <stdio.h>

int x = 123 ;            // 静的大域変数
const int y = 234 ;      // 静的大域変数(定数) 再代入不可

void foo() {
    int b = 345 ;        // 動的局所変数
    b++ ;
    printf( "%d %d\n" , x , b ) ;
}

void bar( int a ) {
    int b = 456 ;        // 動的局所変数
    static int c = 789 ; // 静的局所変数
    x++ ; b++ ; c++ ;
    printf( "%d %d %d\n" , x , b , c ) ;
    foo() ;
}

int main() {
    int z = 890 ;        // 動的局所変数
    bar( z ) ;
    bar( z ) ;
    printf( "%d\n" , z ) ;
    return 0 ;
}

// 実行結果
// 124 457 790
// 124 346
// 125 457 791
// 125 346
// 890

大域変数は混乱の元

以下のようなプログラムでは、foo() を実行すると”0 1 2″ と表示され、main の中で foo() を3回呼び出しているので、”012,012,012″と表示されると勘違いするかもしれない。しかし、xが大域変数(Javaでは大域変数は無いけど)であるため、foo() の処理の中で x=3 となっているため、mainの中では、2回目のループが動かないため、”0 1 2″と表示されるだけである。

こういったように、誰もが使える変数を、どこからでも呼び出せる状態にしておくとプログラムの間違いが発生しやすい。

// C言語での大域変数の問題
int x ;
void foo() { // 0 1 2 と出力
   for( x = 0 ; x < 3 ; x++ )
      printf( "%d\n" , x ) ;
}
int main() {  // 0 1 2 を出力する処理を 3回繰り返すと 0 1 2,0 1 2,0 1 2 と出力される?
   for( x = 0 ; x < 3 ; x++ )
      foo() ;
   return 0 ;
}

// Javaでの大域変数の問題
public class Main {
    public static int x = 0 ; // 静的クラス変数
    public static void foo() { // 0 1 2 と出力
        for( x = 0 ; x < 3 ; x++ )
            System.out.println( x ) ;
    }
    public static void main(String[] args) throws Exception {
        for( x = 0 ; x < 3 ; x++ ) // 0 1 2 を出力する処理を 3回繰り返すと 0 1 2,0 1 2,0 1 2 と出力される?
            foo() ;
    }
}

こういう場合は、正しく局所変数を用いて、関数内でのみ使う変数 x を宣言すれば、上記のような間違いを防ぐことができる。関数内で宣言される変数は関数に入る度にメモリを確保し、関数を抜ける時にメモリ領域が消される。

// C言語での大域変数の解決のために局所変数を使う
void foo() { // 0 1 2 と出力
   int x ;
   for( x = 0 ; x < 3 ; x++ )
      printf( "%d\n" , x ) ;
}
int main() {  // 0 1 2 を出力する処理を 3回繰り返す
   int x ;
   for( x = 0 ; x < 3 ; x++ )
      foo() ;
   return 0 ;
}

// Javaでの大域変数の解決のために局所変数を使う
public class Main {
    public static void foo() { // 0 1 2 と出力
        int x ;
        for( x = 0 ; x < 3 ; x++ )
            System.out.println( x ) ;
    }
    public static void main(String[] args) throws Exception {
        int x ;
        for( x = 0 ; x < 3 ; x++ ) // 0 1 2 を出力する処理を 3回繰り返す
            foo() ;
    }
}

一方で、関数が呼び出された回数を確認したい…という用途であれば、下記のように大域変数を使うこともあるが、これだと x を間違って使われる可能性がある。

int x = 0 ;
void foo() {
   x++ ;
   printf( "%d\n" , x ) ;
}
int main() {
   foo() ;
   foo() ;
   return 0 ;
}

このために、C言語では静的局所変数というのがある。関数内で static で宣言された変数は、その関数の中でしか使えないが、プログラムが起動した時に変数領域が作られ初期化され、プログラムが終了した時にデータ領域が消される。

void foo() {
   static int x = 0 ;
   x++ ;
   printf( "%d\n" , x ) ;
}
int main() {
   foo() ;
   foo() ;
}

Javaでは、プログラムの中でデータが間違ってアクセスされることを防ぐために、大域変数という考え方は存在しない。その代わりにクラス内で共通に利用できる変数ということで、静的なクラス変数が用いられる。static なクラス変数は、クラスがロードされた時点でメモリに確保され、プログラム終了まで保持される。

public class MyClass {
    public static int count = 0; // クラス変数

    public static void main(String[] args) {
        MyClass.count++; // インスタンスを作らずにアクセス
        System.out.println(MyClass.count);
    }
}

スタック領域

スタック領域は、ここまでに述べた様に「関数を呼び出す際にメモリ領域が確保・初期化され、関数が終わるとメモリ領域は消される。

以下のような main から bar() , foo() が呼び出される処理では、

1. 関数呼び出し時には、戻り番地の保存、実引数の確保が行われ、
2. 関数に入った時点で局所変数の領域が確保される。
3. 関数が終わると、実引数・局所変数の領域が消され、スタックから取り出された戻り番地に処理を移行する。

このような関数呼び出しでは、最後(Last)に確保した変数が最初(First)に忘れればいいというデータなので、Last In First Out の スタック構造が使われる。

ヒープ領域

リスト処理のようなプログラムでは、データを覚える領域は、関数が終わった後も使われる領域なので、局所変数のように「関数が終わったらそのデータの場所が不要になる」といったLast In First Out のようなスタックで管理することは難しい。

データを確保したメモリがどの時点まで使われるのか解らない場合、スタック構造を使うことはできない。こういったデータは、ヒープメモリ(ヒープ領域)を用いる。

C言語であれば、ヒープメモリの場所の確保には malloc() 関数が用いられ、不要となった時に free() 関数でメモリの開放が必要である。free() を忘れたプログラムが、ずっと動いた状態になると再利用されないメモリ領域が発生(メモリリーク)し、その領域が大量になると、他のプログラムに悪影響がでてくる。(最悪、仮想メモリの利用でスワッピングが多発するかもしれない)

#include <stdio.h>
#include <stdlib.h>

struct A {        // class A {
    int data ;    //    int data ;
} ;               // }

int main() {
    struct A * ptr = (struct A*)malloc( sizeof( struct A ) ) ;
    // ptr = new A ;

    ptr->data = 123 ;
    // ptr.data = 123 ;
    
    free( ptr ) ;
    // Javaでは free() は不要
    return 0 ;
}

共有の発生したデータの扱い

C言語では、ヒープメモリの管理するには色々と複雑なことが発生する。

例えば、以下のようなリストの和集合のプログラムをC言語とJavaで示す。

このプログラムでは、リスト a, b の和集合を c に代入している。また、不要となったリストを捨てるために list_free() という関数を作成している。ただし Java では、不要となったメモリ領域の開放は不要だが、C言語との対比のために next に null を代入する処理で代用してある。

#include <stdio.h>
#include <stdlib.h>

struct List {
    int          data ;
    struct List* next ;
} ;

struct List* newListNode( int x , struct List* p ) {
    struct List* ans = (struct List*)malloc( sizeof( struct List ) ) ;
    if ( ans != NULL ) {
        ans->data = x ;
        ans->next = p ;
    }
    return ans ;
}

void list_print( struct List* p ) {
    for( ; p != NULL ; p = p->next )
        printf( "%d " , p->data ) ;
    printf( "\n" ) ;
}
int find( struct List* p , int key ) {
    for( ; p != NULL ; p = p->next )
        if ( p->data == key )
            return 1 ;
    return 0 ;
}
struct List* list_union( struct List* a , struct List* b ) {
    struct List* ans = a ;
    for( ; b != NULL ; b = b->next )
        if ( !find( a , b->data ) )
            ans = newListNode( b->data , ans ) ;
    return ans ;
}
void list_free( struct List* p ) {
    if ( p != NULL ) {
        list_free( p->next ) ;
        printf( "*%d " , p->data ) ;
        free( p ) ;
    }
}
int main(void){
    struct List* a = newListNode( 11 , newListNode( 22 , NULL ) ) ;
    struct List* b = newListNode( 11 , newListNode( 33 , NULL ) ) ;
    
    struct List* c = list_union( a , b ) ;
    list_print( a ) ;
    list_print( b ) ;
    list_print( c ) ;
    
    list_free( c ) ;
    list_free( b ) ;
    list_free( a ) ;
    
    return 0 ;  // free(): double free detected in tcache 2
                // Aborted (core dumped)
}

• C言語でリストの和集合

import java.util.*;

class ListNode {
    int      data ;
    ListNode next ;
    ListNode( int x , ListNode p ) {
        this.data = x ;
        this.next = p ;
    }
}

public class Main {
    public static void list_print( ListNode p ) {
        for( ; p != null ; p = p.next )
            System.out.print( p.data + " " ) ;
        System.out.println() ;
    }
    public static boolean find( ListNode p , int key ) {
        for( ; p != null ; p = p.next )
            if ( p.data == key )
                return true ;
        return false ;
    }
    public static ListNode list_union( ListNode a , ListNode b ) {
        ListNode ans = a ;
        for( ; b != null ; b = b.next )
            if ( !find( a , b.data ) )
                ans = new ListNode( b.data , ans ) ;
        return ans ;
    }
    public static void list_free( ListNode p ) {
        if ( p != null ) {
            list_free( p.next ) ;
            System.out.print( "*" + p.data + " " ) ;
            p.next = null ;
        }
    }
    public static void main(String[] args) throws Exception {
        ListNode a = new ListNode( 11 , new ListNode( 22 , null ) ) ;
        ListNode b = new ListNode( 11 , new ListNode( 33 , null ) ) ;
        
        ListNode c = list_union( a , b ) ; // 33,11,22
        
        list_print( a ) ;
        list_print( b ) ;
        list_print( c ) ;
        
        list_free( c ) ; System.out.println() ;
        list_free( b ) ; System.out.println() ;
        list_free( a ) ;
    }
}

• Javaでリストの和集合

このプログラムを実行すると、c には和集合のリストが出来上がるが、33の先のデータは a とデータの一部を共有している。

この状態で、リスト全体を消すための list_free(c); list_free(b); list_free(a); を実行すると、list_free(c) の時点で a の先のリストは解放されている。このため、list_free(a) を実行すると、解放済みのデータ領域をさらに解放する処理が行われるが、すでに存在していないデータを消す処理が実行できない。

C言語のプログラムを動かすと、プログラム実行時にエラーが発生する。しかし、Java で書かれた「ほぼ同様」のプログラムは問題なく動作する。

参照カウンタ法

上記の問題は、a の先のリストが c の一部とデータを共有しているために発生する。この解決方法として簡単な方法では、参照カウンタ法が用いられる。

参照カウンタ法では、データを参照するポインタの数をデータと共に保存する。

• データの中にポインタ数を覚える参照カウンタを設け、データを生成した時に１とする。
• 処理の中で共有が発生すると、参照カウンタをカウントアップする。
• データを捨てる際には、参照カウンタをカウントダウンし、0になったら本当にそのデータを消す。

// 参照カウンタの説明用プログラム
class ListNode {
   int          refc ; // 参照カウンタ
   int          data ; // データ
   ListNode     next ; // 次のポインタ
   ListNode( int x , ListNode p ) {
      this.refc = 0 ;
      this.data = x ;
      this.next = p ;
   }
} ;

public class Main {
   public static ListNode copy( ListNode p ) {
      p.refc++ ;  // 共有が発生したら参照カウンタを増やす。
      return p ;
   }
   // 集合和を求める処理
   public static ListNode list_union( ListNode a , ListNode b )
   {
      ListNode ans = copy( a ) ;
      //             ~~~~~~~~~共有が発生するのでrefc++
      for( ; b != null ; b = b.next )
         if ( !find( ans , b.data ) )
            ans = new ListNode( b.data , ans ) ;
      return ans ;
   }
   public static void list_del( ListNode p ) {  // 再帰で全廃棄
      if ( p != null
           && --(p.refc) <= 0 ) {    // 参照カウンタを減らし
         //   ~~~~~~~~~~
         list_del( p.next ) ;        // 0ならば本当に消す
         free( p ) ;
      }//~~~~~~~~~ Javaでは存在しない関数(説明用) 
   }
   public static void main(String[] args) throws Exception { 
      ListNode a = new ListNode( 11 , new ListNode( 22 , null ) ) ;
      ListNode b = new ListNode( 11 , new ListNode( 33 , null ) ) ;
      ListNode c = list_union( a , b ) ;

   // a,b,cを使った処理

   // 処理が終わったのでa,b,cを捨てる
   list_del( c ) ;
   list_del( b ) ;
   list_del( a ) ;
}

ただし、Java ではこういった処理を記述しなくても、内部で参照カウンタ法を実行しているため、このような処理を書く必要はない。

unix i-nodeで使われている参照カウンタ

unixのファイルシステムの基本的構造 i-node では、1つのファイルを別の名前で参照するハードリンクという機能がある。このため、ファイルの実体には参照カウンタが付けられている。unix では、ファイルを生成する時に参照カウンタを1にする。ハードリンクを生成すると参照カウンタをカウントアップ”+1″する。ファイルを消す場合は、基本的に参照カウンタのカウントダウン”-1″が行われ、参照カウンタが”0″になるとファイルの実体を消去する。

以下に、unix 環境で 参照カウンタがどのように使われているのか、コマンドで説明していく。

$ echo a > a.txt
$ ls -al *.txt
-rw-r--r-- 1 t-saitoh t-saitoh 2 12月 21 10:07 a.txt
          ~~~ # ここが参照カウンタの値
$ ln a.txt b.txt      # ハードリンクでコピーを作る
$ ls -al *.txt
-rw-r--r-- 2 t-saitoh t-saitoh 2 12月 21 10:07 a.txt
-rw-r--r-- 2 t-saitoh t-saitoh 2 12月 21 10:07 b.txt
          ~~~ # 参照カウンタが増えているのが分かる
$ rm a.txt            # 元ファイルを消す
$ ls -al *.txt
-rw-r--r-- 1 t-saitoh t-saitoh 2 12月 21 10:07 b.txt
          ~~~ # 参照カウンタが減っている
$ ln -s b.txt c.txt   # シンボリックリンクでコピーを作る
$ ls -al *.txt
-rw-r--r-- 1 t-saitoh t-saitoh 2 12月 21 10:07 b.txt
lrwxrwxrwx 1 t-saitoh t-saitoh 5 12月 21 10:10 c.txt -> b.txt
$ rm b.txt            # 元ファイルを消す
$ ls -al *.txt
lrwxrwxrwx 1 t-saitoh t-saitoh 5 12月 21 10:10 c.txt -> b.txt
$ cat c.txt           # c.txt は存在するけどその先の実体 b.txt は存在しない
cat: c.txt: そのようなファイルやディレクトリはありません

コンパイラの処理の流れ

構文の構造を表すために、2分木を使うという話をこの後に行うが、その前にコンパイラが機械語を生成するまでの処理の流れについて説明をする。

Cコンパイラのソース
　　↓
プリプロセッサ (#define,#includeなどの処理)
　　↓
コンパイラ
・字句解析(ソースコードをトークンに切り分ける)
・構文解析(トークンから構文木を生成)
・最適化(命令を効率よく動かすために命令を早い命令に書き換え)
・コード生成(構文木から中間コードを生成)
　　|
　　|　リンカでライブラリと結合
　（+）←---ライブラリ
　　↓ 
　機械語

バイトコードインタプリタ

通常、コンパイラとかインタプリタの説明をすると、Java がコンパイラとか、JavaScript はインタプリタといった説明となる。しかし、最近のこういった言語がどのように処理されるのかは、微妙である。

(( Java の場合 ))
foo.java (ソースコード)
　↓       Java コンパイラ
foo.class (中間コード)
　↓
JRE(Java Runtime Engine)の上で
中間コードをインタプリタ方式で実行

あらかじめコンパイルされた中間コードを、JREの上でインタプリタ的に実行するものは、バイトコードインタプリタ方式と呼ぶ。

ただし、JRE でのインタプリタ実行では遅いため、最近では JIT コンパイラ(Just-In-Time Compiler)により、中間コードを機械語に変換してから実行する。

また、JavaScriptなどは(というか最近のインタプリタの殆どPython,PHP,Perl,…は)、一般的にはインタプリタに分類されるが、実行開始時に高級言語でかかれたコードから中間コードを生成し、そのバイトコードをインタプリタ的に動かしている。

しかし、インタプリタは、ソースコードがユーザの所に配布されて実行するので、プログラムの内容が見られてしまう。プログラムの考え方が盗まれてしまう。このため、変数名を短くしたり、空白を除去したり(…部分的に暗号化したり)といった難読化を行うのが一般的である。

字句解析と構文解析

トークンと正規表現(字句解析)

字句解析でトークンを表現するために、規定されたパターンの文字列を表現する方法として、正規表現(regular expression)が用いられる。

((正規表現の書き方))
選言　　　  「abd|acd」は、abd または acd にマッチする。
グループ化　「a(b|c)d」は、真ん中の c|b をグループ化
量化　　　　パターンの後ろに、繰り返し何回を指定
　　　　　　? 直前パターンが0個か1個
　　　　　　　「colou?r」
　　　　　　* 直前パターンが0個以上繰り返す
　　　　　　　「go*gle」は、ggle,gogle,google
　　　　　　+ 直前パターンが1個以上繰り返す
　　　　　　　「go+gle」は、gogle,google,gooogle

正規表現は、sed,awk,Perl,PHPといった文字列処理の得意なプログラム言語でも利用できる。こういった言語では、以下のようなパターンを記述できる。

[文字1-文字2...] 文字コード1以上、文字コード2以下
　　　　　　「[0-9]+」012,31415,...数字の列
^　　　　　行頭にマッチ
$　　　　　行末にマッチ
((例))
[a-zA-Z_][a-zA-Z_0-9]* C言語の変数名にマッチする正規表現

• 情報処理技術者試験で出題された正規表現の問題と解説

構文とバッカス記法

言語の文法(構文)を表現する時、バッカス記法(BNF)が良く使われる。

((バッカス記法))
<表現> ::= <表現1...> | <表現2...> | <表現3...> | ... ;

例えば、加減乗除記号と数字だけの式の場合、以下の様なBNFとなる。

((加減乗除式のバッカス記法))
<加算式> ::= <乗算式> '+' <乗算式>    【要注意】わざと間違っている部分あり
          | <乗算式> '-' <乗算式>
          | <乗算式>
          ;
<乗算式> ::= <数字> '*' <乗算式>
          | <数字> '/' <乗算式>
          | <数字>
          ;
<数字>   ::= [0-9]+
          ;

上記のバッカス記法には、間違いがある。”1+2+3″を正しく認識できない。どこが間違っているだろうか?

このような構文が与えられた時、”1+23*456″と入力されたものを、“1,+,23,*,456”と区切る処理が、字句解析である。

また、バッカス記法での文法に合わせ、以下のような構文木を生成するのが構文解析である。

　　＋
　／　＼
１　　　＊
　　　／　＼
　　23　　　456

2項演算と構文木

演算子を含む式が与えられたとして、古いコンパイラではそれを逆ポーランド変換して計算命令を生成していた。しかし最近の複雑な言語では、計算式や命令を処理する場合、その式(または文)の構造を表す2分木(構文木)を生成する。。

　　　＋
　　／　＼
　１　　　＊
　　　　／　＼
　　　２　　　３

演算子の木のノードで、末端は数値であることに注目し、右枝・左枝がNULLなら数値(data部にはその数値)、それ以外は演算子(data部には演算子の文字コード)として扱うとして、上記の構文木のデータを作る処理と、その構文木の値を計算するプログラムを示す。

import java.util.*;

class ExpTreeNode {
    String      op_val ;
    ExpTreeNode left ;
    ExpTreeNode right ;
    
    ExpTreeNode( String op , ExpTreeNode l , ExpTreeNode r ) {
        this.op_val = op ;
        this.left   = l ;
        this.right  = r ;
    }
    ExpTreeNode( String val ) {
        this.op_val = val ;
        this.left   = null ;
        this.right  = null ;
    }
}

public class Main {
    public static int eval( ExpTreeNode p ) {
        if ( p.left == null && p.right == null ) {
            return Integer.parseInt( p.op_val ) ;
        } else {
            int l_val = eval( p.left) ;
            int r_val = eval( p.right ) ;
            switch( p.op_val ) {
            case "+" : return l_val + r_val ;
            case "*" : return l_val * r_val ;
            }
            return -1 ; // error
        }
    }
    public static void main(String[] args) throws Exception {
        ExpTreeNode top =
            new ExpTreeNode( "+" ,
                             new ExpTreeNode( "1" ) ,
                             new ExpTreeNode( "*" ,
                                              new ExpTreeNode( "2" ) ,
                                              new ExpTreeNode( "3" ) ) ) ;
        
        System.out.println( eval( top ) ) ;
    }
}

• 2分木による構文木(Paiza.io)

オブジェクト指向を使った構文木(テスト範囲外)

前述の2分木を用いた構文木では、式を構成する「整数値」の式、「式 演算子 式」の演算式の二つのパターンを、無理やり１つのクラスで扱っていた。整数値と演算子の文字列の違いがあるため、数値も文字列で保存したものを parseInt() で数値に変換している。

こういった、大きくは式と分類できるけど、数値を表す式、演算子からなる式と異なるデータの場合、Java では、オブジェクト指向プログラミングの抽象クラスと仮想関数のテクニックを用いる。式を表現する基底クラス ExpNode から、数値を表す ExpNodeInteger , 演算子からなる式を表す ExpNodeOperator を派生させ、式の値を求める際には、各クラスに応じた計算処理を行う仮想関数 eval() を使って処理を行っている。

import java.util.* ;

// 抽象基底クラス
abstract class ExpNode {
    abstract public int eval() ;
}

// 整数で具体化
class ExpNodeInteger extends ExpNode {
    int  value ;
    
    ExpNodeInteger( int i ) {
        this.value = i ;
    }
    // 仮想関数
    public int eval() {
        return this.value ;
    }
}

// 演算子で具体化
class ExpNodeOperator extends ExpNode {
    String  op ;
    ExpNode left ;
    ExpNode right ;
    
    ExpNodeOperator( String s , ExpNode l , ExpNode r ) {
        this.op    = s ;
        this.left  = l ;
        this.right = r ;
    }
    // 仮想関数
    public int eval() {
        int l_val = this.left.eval() ;
        int r_val = this.right.eval() ;
        switch( this.op ) {
        case "+" : return l_val + r_val ;
        case "*" : return l_val * r_val ;
        }
        return -1 ;
    }
}

public class Main {
    public static void main(String[] args) throws Exception {
        ExpNode top =
            new ExpNodeOperator( "+" ,
                                 new ExpNodeInteger( 1 ) ,
                                 new ExpNodeOperator( "*" ,
                                                      new ExpNodeInteger( 2 ) ,
                                                      new ExpNodeInteger( 3 ) ) ) ;

        System.out.println( top.eval() ) ;
    }
}

データをO(log N)で検索するための2分探索木以外の2分木のデータ構造について解説を行う。

意思決定木

意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹介。

   ((意思決定木の例:小さい子供が発熱した時))
　　　　　　　38.5℃以上の発熱がある？
　　　　　　no／　　　　　　　　　＼yes
　　　元気がある？　　　　　　　　むねがひいひい？
　yes／　　　　＼no　　　　　　no／　　　　　＼yes
様子をみる　氷枕で病院　　解熱剤で病院　　速攻で病院

このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。これは2分木と同じである。左右に枝のあるものは質問であり、yesの枝もnoの枝もない末端は最終決断を表す。このようなデータ構造は意思決定木と呼ばれ、質問と決断の処理は以下のように記述ができる。

import java.util.* ;
import java.util.Scanner ;

class TreeNode {
    String qa ;
    TreeNode    yes ;
    TreeNode    no ;
    
    TreeNode( String s , TreeNode y , TreeNode n ) {
        this.qa  = s ;
        this.yes = y ;
        this.no  = n ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner( System.in ) ;
        TreeNode top =
            new TreeNode( "38.5℃以上の発熱がある?" ,
                          new TreeNode( "胸がひぃひぃ?" ,
                                        new TreeNode( "速攻で病院" ,   null , null ) ,
                                        new TreeNode( "解熱剤で病院" , null , null ) ) ,
                          new TreeNode( "元気がある?" ,
                                        new TreeNode( "様子をみる",    null , null ) ,
                                        new TreeNode( "氷枕で病院",    null , null ) ) ) ;
        TreeNode p = top ;
        while( p.yes != null || p.no != null ) {
            System.out.println( "Question:" + p.qa ) ;
            if ( sc.nextInt() == 1 ) {
                System.out.println( "yes" ) ;
                p = p.yes ;
            } else {
                System.out.println( "no" ) ;
                p = p.no ;
            }
        }
        System.out.println( "Answer:" + p.qa ) ;
    }
}

• 意思決定木(Paiza.io)

struct Tree {
   char *qa ;
   struct Tree* yes ;
   struct Tree* no ;
} ;
struct Tree* dtree( char *s ,
                    struct Tree* l , struct Tree* r )
{  struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->qa = s ;
      n->yes = l ;
      n->no = r ;
   }
   return n ;
}
void main() {
   struct Tree* p =
      dtree( "38.5℃以上の発熱がある?" ,
             dtree( "胸がひぃひぃ?" ,
                    dtree( "速攻で病院",  NULL,NULL ) ,
                    dtree( "解熱剤で病院",NULL,NULL ) ) ,
             dtree( "元気がある?" ,
                    dtree( "様子をみる",  NULL,NULL ) ,
                    dtree( "氷枕で病院",  NULL,NULL ) ) ) ;
   // 決定木をたどる
   struct Tree* d = p ;
   while( d->yes != NULL || d->no != NULL ) {
      printf( "%s¥n" , d->qa ) ;
      scanf( "%d" , &ans ) ;
      // 回答に応じてyes/noの枝に進む。
      if ( ans == 1 )      // yesを選択
         d = d->yes ;
      else if ( ans == 0 ) // noを選択
         d = d->no ;
   }
   // 最終決定を表示
   printf( "%s¥n" , d->qa ) ;
}

• decision-tree.cxx

---

2分木の応用として次週以降に式の表現の説明を行うけど、その前に計算式の一般論の説明を行う。

逆ポーランド記法

一般的に 1*2 + 3*4 と記載すると、数学的には演算子の優先順位を考慮して、(1*2)+(3*4) のように乗算を先に行う。このような優先順位を表現する時に、()を使わない方法として、逆ポーランド記法がある。

演算子の書き方には、前置記法、中置記法、後置記法があり、後置記法は、「2と3を掛ける、それに1を加える」と捉えると、日本語の処理と似ている。

中置記法 1+2*3
前置記法 +,1,*,2,3
後置記法 1,2,3,*,+　　# 1と「2と3をかけた値」をたす。

後置記法は、一般的に逆ポーランド記法(Reverse Polish Notation)とも呼ばれ、式をコンピュータで実行する際の処理と似ている。

演算子の右結合・左結合

例えば、”1/2*3″という式が与えられたとする。この結果は、1/6だろうか？3/2だろうか？

一般的な数学では、優先順位が同じ演算子が並んだ場合、左側から計算を行う。つまり”1/2*3″は、”(1/2)*3″を意味する。こういった左側の優先順位が高い演算子は左結合の演算子という。

ただしC言語やJavaでは、”a = b = c = 0″ と書くと、”a = (b = (c = 0))” として扱われる。こういった代入演算子は、 右結合の演算子である。

理解度確認

以下の式を指定された書き方で表現せよ。

逆ポーランド記法 1,2,*,3,4,*,+ を中置記法で表現せよ。
中置記法 (1+2)*3-4*5 を逆ポーランド記法で表現せよ。

以前の情報処理技術者試験では、スタックの概念の理解の例題として、逆ポーランド記法への変換アルゴリズムのプログラム作成が出題されることが多かったが、最近は出題されることはなくなってきた。

2分探索木にデータを追加

前回の2分探索木では、基本的な説明ということで、木の生成では直接木構造を生成していた。しかし、本来であれば、扱うデータに応じて木を生成することが求められる。

Javaの場合

以下の Javaのプログラムの関数 entry( … ) では、再帰を使いながら、value を追加した木を返す関数で記述した。

import java.util.*;

class BTreeNode {
    int       data ;
    BTreeNode left ;
    BTreeNode right ;
    
    BTreeNode( int x , BTreeNode l , BTreeNode r ) {
        this.data  = x ;
        this.left  = l ;
        this.right = r ;
    }
}
public class Main {
    public static void print_tree( BTreeNode p ) {
        // 木構造をわかりやすくするために()をつけて表示
        if ( p != null ) {
            System.out.print( "(" ) ;
            print_tree( p.left ) ;
            System.out.print( p.data ) ;
            print_tree( p.right ) ;
            System.out.print( ")" ) ;
        }
    }
    public static BTreeNode entry( BTreeNode p , int value ) {
        if ( p == null ) {
            return new BTreeNode( value , null , null ) ;
        } else {
            if ( p.data == value )
                ; // 何もしない
            else if ( p.data > value )
                p.left = entry( p.left , value ) ;
            else
                p.right = entry( p.right , value ) ;
            return p ;
        }
    }
    public static void main(String[] args) throws Exception {
        BTreeNode top = null ;
        top = entry( top , 42 ) ;
        top = entry( top , 27 ) ;
        top = entry( top , 72 ) ;
        top = entry( top , 13 ) ;
        top = entry( top , 38 ) ;
        top = entry( top , 64 ) ;
        top = entry( top , 81 ) ;
        print_tree( top ) ; System.out.println() ;
    }
}
// 動作結果
// (((13)27(38))42((64)72(81)))

• 2分探索木へのデータの追加(Paiza.io)

しかしながらこのプログラムでは、以下のように小さい順序でデータを与えると、右に伸びる木が作られてしまう。

    // 不均一な木ができる場合
    public static void main(String[] args) throws Exception {
        BTreeNode top = null ;
        top = entry( top , 13 ) ;
        top = entry( top , 27 ) ;
        top = entry( top , 38 ) ;
        top = entry( top , 42 ) ;
        top = entry( top , 64 ) ;
        top = entry( top , 72 ) ;
        top = entry( top , 81 ) ;
        print_tree( top ) ; System.out.println() ;
    }
    // 動作結果
    // (13(27(38(42(64(72(81)))))))

このような不均一な木が生成されてしまうと、本来であればデータ探索の処理時間は O( log N ) であるが、最悪の状態では O( N ) となってしまう。

AVL木

こういった偏った木が生成されてしまった時には、以下のような処理を加えると、不均一な状態を改善できる。

depth() 関数は与えられた木の深さを求める関数であり、左枝と右枝が大きく違う場所で 木の右回転を行う rotate_right() を実行する。

public class Main {
    public static int depth( BTreeNode p ) { // 木の深さを求める
        if ( p == null ) {
            return 0 ;
        } else {
            int l = depth( p.left ) ;
            int r = depth( p.right ) ;
            if ( l > r )
                return 1 + l ;
            else
                return 1 + r ;
        }
    }
    public static BTreeNode rotate_right( BTreeNode p ) {
        BTreeNode q = p.left ;      //      p
        BTreeNode r = q.right ;     //    ／ ＼
        q.right = p ;               //   q
        p.left  = r ;               // ／ ＼
        return q ;                  //      r
    }
    public static void main(String[] args) throws Exception {
        BTreeNode top = null ;
        top = entry( top , 86 ) ;
        top = entry( top , 53 ) ;
        top = entry( top , 92 ) ;
        top = entry( top , 11 ) ;
        top = entry( top , 65 ) ;
        top = entry( top , 22 ) ;
        // 不均一な状態を確認
        print_tree( top ) ;
        System.out.println() ;
        System.out.println( "p.left=" + depth( top.left ) ) ;
        System.out.println( "p.right=" + depth( top.right ) ) ;
        // top の右回転を実行
        top = rotate_right( top ) ;
        // 改善された状態を確認
        print_tree( top ) ;
        System.out.println() ;
        System.out.println( "p.left=" + depth( top.left ) ) ;
        System.out.println( "p.right=" + depth( top.right ) ) ;
    }
}

• AVL木と右回転(Paiza.io)

上記のプログラムでは、左枝が3段で右枝が1段であり不均一な状態となっている。

そこで、最上段の86の左枝を上に移動させるように枝の繋ぎ方を rotate_right() により変更している。実際には、繋ぎ変えを左回転させる処理も作る必要がある。

このように、木の枝の深さが不均一な場所で、このような処理を加えて均一化を図った木構造は AVL 木と呼ぶ。

AVL木は、考案した Velski と Landis の名前が由来(Adelson-Velskii and Landis’ tree)

2分ヒープ(binary heap)

2分探索木では、１つのノードにつき2つのポインタを持ち、データ1件あたりのメモリの使用量が多い。通常の「配列の先頭から昇順にデータを並べる2分探索法」では、途中にデータを挿入する場合、データを後ろにずらす必要があるため、O(N)の処理時間を要する。

これらの問題の解決法の１つとして、2分ヒープがある。左右に均一に成長している2分探索木で、上から番号を以下の様に振ると、i番目のデータの左の枝は 2×i+1 番目、右の枝は 2×i+2 番目であることが判る。

このような順序で配列にデータを保存する方法が2分ヒープである。この方式ならアルゴリズムの説明は省略するが、入れるべきノードの場所でのデータの入れ替えで実現できるため O( log( N ) )で挿入が可能となる。

import java.util.*;

public class Main {
    public static int find_heap( int[] array , int idx , int key ) {
        while( idx < array.length ) { if ( array[ idx ] == key ) return idx ; // 見つかった else if ( array[ idx ] > key )
                idx = idx*2 + 1 ;
            else
                idx = idx*2 + 2 ;
        }
        return -1 ; // 見つからなかった
    }
    public static void main(String[] args) throws Exception {
        int[] a = { 53 , 11 , 86 , 10 , 22 , 65 , 92 } ;
        System.out.println( find_heap( a , 0 , 22 ) ) ;
    }
}

• 2分ヒープ(Paiza.io)

レポート課題

以下のようなデータを扱う2分探索木のプログラムを作成せよ。以下の箇条書き番号の中から、(出席番号 % 3+1)のデータについてプログラムを作ること。

1. 名前(name)と電話番号(phone)
2. 名前(name)と誕生日(year,mon,day)
3. 名前(name)とメールアドレス(mail)

プログラムは以下の機能を持つこと。

• 1行1件でデータを入力し、2分木に追加できること。
• 全データを昇順(or降順)で表示できること。
• 検索条件を入力し、目的のデータを探せること。

レポートでは、(a)プログラムリスト,(b)その説明,(c)動作検証結果,(d)考察 を記載すること。