ホーム » 2019 » 11月 » 13

日別アーカイブ: 2019年11月13日

2019年11月
« 10月   12月 »
 12
3456789
10111213141516
17181920212223
24252627282930

最近の投稿(電子情報)

アーカイブ

カテゴリー

ポインタの先には何がある?

学生さんから「ポインタの先には何があるの?」との質問があった。

私が「そのポインタの型のデータ」と答えると、さらに「ポインタはメモリの場所。でもメモリには int や char や double といった色んなデータがある。そんな色々なデータの中からデータを取り出すんだから、そこにはどんなデータが入っているのか判らないとデータを取り出せないんじゃ?」と疑問をぶつけてきた。

なるほど、本当の疑問点が見えてきた。

最近のPython等の動的型付け言語の場合

# ポインタの質問だから、C言語の場合を答えればいいんだけど…

最近の Python , PHP といった変数が型を持たない「動的型付け言語」は、まさに質問の通り。データを取り出すためには、型の情報が必要。こういう言語は、基本型以外のデータはすべて参照型(要はポインタ)なので、変数の指し示す先には型情報とそのデータがペアで保存されているので、その型情報をみてデータを取り出している。

C言語の場合(静的型付け言語)

C言語では、ポインタは単なるメモリの場所を表すだけ。ポインタの先にはデータがある。(だからデータしかないって!)

メモリからデータを読み出すときに、int 4byte で取り出すのか、 double 8byte で取り出すかどうやってわかるの?と思うかもしれないけど、そのポインタの変数がどういう型へのポインタで定義されているかプログラムを読めばわかる。それに従って取り出せばいい。こういう言語は「静的型付け言語」という。

となると「じゃあ int のデータを char として読めるの?」と思うかもしれないけど「読めるよ!」

#include <stdio.h>
int main() {
   // 型を偽って参照するのは間違いの元なので型のチェックは厳格。
   //   だから 以下の様なヤバイことをする時は、型キャスト で
   //   だますことが定番。
   int x = 0x41424344 ; 
   char* p = (char*)( &x ) ; // int型の場所をchar型にする 
   printf( "%c\n" , *p ) ;

   // int型は4バイト、次のアドレスは?
   int y[] = {
      0x11223344 , 0x12345678 ,
   } ;
   printf( "%p %p\n" , y , y + 1 ) ; 
   int *r = y + 1 ;
   printf( "%04d\n" , *r ) ; // 12345678 が表示

   // intの1byteとなりをintとして読める?
   int *q = (int*)((char*)( &y ) + 1) ;
   printf( "%04x\n" , *q ) ; // 処理系によってはメモリエラー

   // ポインタは番地を表す数値だよね?
   //  0x100番地のデータは読める?
   int* s = (int*)0x100 ;
   printf( "%d\n" , *s ) ; // Segmentation Fault.

   return 0 ;
}

さて、上記のプログラムをみてどう思った?

C言語って自由奔放で、やばくね? — ポインタなんか使えるからだよね、そう思うんなら Java 使え。ポインタなんか使えないから。

でも型宣言が面倒なんだよねPython, Ruby などの動的型付けな言語使え。

でも変数参照でいちいち型情報しらべる言語って遅くね? — あるよ。「型推論」。型を明記しなくても、プログラムの文脈から型を推論してくれる静的型付け言語。Go , Swift , Kotlin…といった、今 流行りのプログラム言語がソレ。最新のJavaやC++も型推論機能が使えるようになってるよ。んで、今話題の中学生が作ったプログラム言語 Blawn も、型推論の言語!すげーな。

演算子と2分木による式の表現

2分木の応用として、式の表現を行うけどその前に…

逆ポーランド記法

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

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

中置記法 1+2*3
前置記法 +,1,*,2,3
後置記法 1,2,3,*,+

後置記法は、一般的に逆ポーランド記法(Reverse Polish Notation)とも呼ばれ、式を機械語の命令に置き換える際に役立つ。

理解度確認

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

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

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

逆ポーランド式の実行

この逆ポーランド記法で書かれた式から結果を求めるプログラムは以下のように記述できる。このプログラムでは式を簡単にするため、数値は1桁の数字のみとする。

// 単純な配列を用いたスタック
int stack[ 10 ] ;
int sp = 0 ;

void push( int x ) {
   stack[ sp++ ] = x ;
}
int pop() {
   return stack[ --sp ] ;
}

// 逆ポーランド記法の計算
int rpn( char* p ) {
   for( ; *p != '\0' ; p++ ) {
      if ( isdigit( *p ) ) {
         //         ~~(A)
         // 数字はスタックに積む
         push( *p - '0' ) ;
      } else if ( *p == '+' ) {
         // 演算子+は上部2つを取出し
         int r = pop() ;
         int l = pop() ;
         // 加算結果をスタックに積む
         push( l + r ) ;
      } else if ( *p == '*' ) {
         // 演算子*は上部2つを取出し
         int r = pop() ;
         int l = pop() ;
         // 乗算結果をスタックに積む
         push( l * r ) ;
      }//~~~~~~~~~~~~~(B)
   }
   // 最終結果がスタックに残る
   return pop() ;
}

void main() {
   printf( "%d\n" , rpn( "123*+" ) ) ;
}

逆ポーランド記法の式の実行は、上記のようにスタックを用いると簡単にできる。このようなスタックと簡単な命令で複雑な処理を行う方法はスタックマシンと呼ばれる。Java のバイトコードインタプリタもこのようなスタックマシンである。

Cプログラママニア向けの考察

上記のプログラムでは、int r=pop();…push(l+r); で記載しているが、

push( pop() + pop() ) ;

とは移植性を考慮して書かなかった。理由を述べよ。

最初の関数電卓

初期の関数電卓では複雑な数式を計算する際に、演算子の優先順位を扱うのが困難であった。このため、HP社の関数電卓では、式の入力が RPN を用いていた。(HP-10Cシリーズ)

2項演算と構文木

演算子を含む式が与えられたとして、それを保存する場合、演算式の2分木で扱うと都合が良い。

   +
  / \
 1   *
    / \
   2   3

演算子の木のノードで、末端は数値であることに注目し、右枝・左枝がNULLなら数値(data部にはその数値)、それ以外は演算子(data部には演算子の文字コード)として扱うとして…

struct Tree {
   int  data ;
   struct Tree* left ;
   struct Tree* right ;
} ;
struct Tree* tree_int( int x ) // 数値のノード
{
   struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->data = x ;
      n->left = n->right = NULL ;
   }
   return n ;
}
struct Tree* tree_op( int op , // 演算子のノード
                   struct Tree* l , struct Tree* r ) {
   struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {     // ~~~~~~~~~~~~~~~~~~~~~(C)
      n->data  = op ;
      n->left  = l ;
      n->right = r ;
   }
   return n ;
}
// 与えられた演算子の木を計算する関数
int eval( struct Tree* p ) {
   if ( p->left == NULL && p->right == NULL ) {
      // 数値のノードは値を返す
      return p->data ;
   } else {
      // 演算子のノードは、左辺値,右辺値を求め
      // その計算結果を返す
      switch( p->data ) {
      case '+' : return eval( p->left ) + eval( p->right ) ;
      case '*' : return eval( p->left ) * eval( p->right ) ;
      }              // ~~~~~~~~~~~~~~~(D)      ~~~~~~~~(E)
   }
}

void main() {
   struct Tree* exp =  // 1+(2*3) の構文木を生成
      tree_op( '+' ,
               tree_int( 1 ) ,
               tree_op( '*' ,
                        tree_int( 2 ) , tree_int( 3 ) ) ) ;
   printf( "%d¥n" , eval( exp ) ) ;
}

理解度確認

  • 上記プログラム中の(A),(B),(C),(D)の型を答えよ。

const char*s, char* const sの違い

専攻科実験のサンプルコードで、警告がでたことについて質問があったので説明。

(( サンプルコード sample.cxx ))
#include <stdio.h>
void foo( char* s ) {
  printf( "%s¥n" , s ) ;
}
int main() {
  foo( "ABC" ) ;
  return 0 ;
}

(( コンパイル時の警告 ))
$ g++ sample.cxx
test.cxx:6:6: warning: conversion from string literal
      to 'char *' is deprecated
      [-Wc++11-compat-deprecated-writable-strings]
  foo( "abcde" ) ;
       ^
1 warning generated.

警告を抑止する “-Wno-…” のオプションをつけて “g++ -Wno-c++11-compat-deprecated-writable-strings sample.cxx” でコンパイルすることもできるけど、ここは変数の型を厳格にするのが鉄則。

この例では、引数の “ABC” が書き換えのできない定数なので、const キーワードを付ければよい。ただし、宣言時の const の付け場所によって、意味が違うので注意が必要。

void foo( char const* s ) { // const char* s も同じ意味
   *s = 'A' ; // NG ポインタの先を書き換えできない
   s++ ;      // OK ポインタを動かすことはできる
}
void foo( char *const s ) {
   *s = 'A' ; // OK ポインタの先は書き込める
   s++ ;      // NG ポインタは動かせない
}
void foo( char const*const s ) {
   *s = 'A' ; // NG ポインタの先を書き換えできない
   s++ ;      // NG ポインタは動かせない
}

const を書く場所は?

int const x = 123 , y = 234 ; の場合、yは定数だろうか?

(( おまけ ))
#include <stdio.h>
int main() {
  int const x = 123 , y = 234 ; // x は定数だけど yは定数?
  x++ ; // 予想通りエラー
  y++ ; // yも定数なのでエラー
  int const s = 345 , const t = 456 ; // sもtも明らかに定数っぽい
  //                  ^ここで文法エラー

  // おまけのおまけ
  char* s , t ;   // s は文字へのポインタ、t は文字
  char  *s , *t ; // s は文字へのポインタ、t も文字へのポインタ
  return 0 ;
}