Document

4. 合成データ：構造体
プログラミング論I
本日の内容
• 単純データと合成データ
• 構造体(合成データの一種)
– 構造体の定義：構造(構成要素など)の鋳型を準備
– 構造体の使用
• コンストラクタ：構造体の定義にあうデータを生成する
• セレクタ：構造体の内容を参照する
– 構造体データを使うプログラムの設計法
• 様々なデータとその区別
様々なデータ
• 単純データ
– 数値、ブール値、シンボル、文字列、…
• 合成データ：複数要素で1つのデータを構成
– 構造体 (structure) ：固定数の要素で1つのデータ
• 2次元平面座標（x,y座標）、名簿の一人分の項目数、 …
– リスト(後日説明)：不定数の要素で1つのデータ
• 窓口の行列の人数、 …
構造体の例
• 複数の要素から1つのデータを構成する例
2次元平面座標
名簿データ
例 x座標3, ｙ座標4の点
例名前：山田、年:19、住所：伊都
posn
x
y
personal_info
構造体の名前
name
age
address
要素データ(フィー
ルド)の並び
様々なフィールド(要素データ)を持つ構造データ
→ プログラマが定義可能
構造体データを扱う道具立て
様々な構造体を扱う道具立て
– 各構造体の定義
– 個々の構造体データの実体を作るコンストラクタ
– 構造体データから各フィールド値を選ぶセレクタ
例えば二次元平面上の点を扱う場合
– 定義：二次元平面上の座標は何で構成される？
• 座標はx 座標と y 座標で定まる．値は数値． (x, y)
– コンストラクタ：定義にあう二次元平面上の点を作る
• 各点の要素の具体的データ（例えば(1, 3) (5, 12) など)を与え
構造体データを生成
– セレクタ：ある点の座標データの値を調べる
• どの点のどの要素(x座標か y座標)かを，指定して参照
(1, 3)のx座標の値 1． (1,3)のy座標の値 3 を取り出す．
構造体の定義(一般形)
様々な構造体があり得る→問題に合わせて定義
固定数のフィールド(属性値)を持つあらゆるオブジェクトを表現
構造体名フィールド名の並び
(define-struct
c
(s1
…
sn) )
上記の定義の実行によって
– 個々の構造体データの実体を作るコンストラクタ：
make-c (構造体名の前に make-をつける)
– 構造体データから各フィールド値を選ぶセレクタ：
c-s1 … c-sn (構造体名とフィールド名を - でつなぐ)
が使えるようになる
構造体の定義例： posn 型構造体
2次元平面座標 posn は x, y 座標値から構成
構造体名フィールドの並び
(define-struct posn (x y) )
posn
x
y
座標データ
フィールド
• 上記の定義によって
– コンストラクタ： make-posn
– セレクタ： posn-x posn-y
が使えるようになる
(DrRacketではposn型定義は基本構造体として元から準備済)
例題1. posn構造体
• 以下のような点
の生成や参照
の例
y
4
(define-struct posn (x y))
ただし、
DrRacketでは posn は基本的な組込みの構造体として
最初から定義済なのであらためて定義しなくてよい
点a (3,4)
点 (3,4) を作る
点 (3,4) の x 座標値を選ぶ
3
x
点 (3,4) の y 座標値を選ぶ
点 (3,4) を作り a という名前にする
点a の x 座標値を選ぶ
点a の y 座標値を選ぶ
C言語の場合
// (define-struct posn (x y))
typedef struct{
int x;
int y;
} posn;
//(define a (make-posn 3 4))
posn a; // posn型の変数a
a.x=3; // a.x == (posn-x a)
a.y=4; // a.y == (posn-y a)
C言語の場合
(define-struct personal_info (name age address))
(define a
(make-personal_info “Matsuzaka” 33 “Fukuoka”))
(personal_info-name a) => “Matsuzaka”
#define _CRT_SECURE_NO_WARNINGS
typedef struct{
#define <string.h>
personal_info a;
char name[20];
strcpy(a.name,“Matsuzaka”);
int age;
a.age=33;
char address[128];
strcpy(a.address,“Fukuoka”);
} personal_info;
練習
(define b (make-posn 12 5))
(posn-x b) (posn-y b)
(define-struct
personal_info (name(12,5)
age address))
• 二次元平面上の点b
について
(define
SBF-1 (make-personal_info “Matsuzaka" 33 “Fukuoka"))
– コンストラクタで点bの構造体データを生成せよ
(personal_info-name
SBF-1)x座標と
(personal_info-age
SBF-1)
– セレクタで点bの
y座標を参照せよ
(personal_info-address SBF-1)
• 個人情報がname(文字列), age(数字), address(文字
列) からなるとき、その構造体を personal_info
という名前で定義せよ
– そのコンストラクタは何か
– そのセレクタは何か
personal_info 型構造体
名簿データpersonal_info 型構造体を定義
– personal_info は name, age, address から構成
構造体名
フィールド名の並び
(define-struct personal_info (name age address))
上記の定義によって以下が使えるようになる
– コンストラクタ make-personal_info personal_info
– セレクタ
name
• personal_info-name
フィールド
• personal_info-age
• personal_info-address
age
address
合成データの関数の
プログラム設計法
プログラム設計法：合成データの関数
合成データを扱う関数向けにプログラム設計法を拡張
• データの解析と定義:
• 処理対象がN個の特性を持つ → N個のフィールドの構造体を導入
• フィールドがどの種のデータを含むか仕様記述するデータ定義
• Purpose:プログラムの目的を理解、機能の概要を記述
• Contract, Header, Statement:
• Example:プログラムの振る舞いを「例」で記述．
• Template:ヘッダと可能な全セレクタ式を列挙した本体を構成
• 複合データを扱う関数は複合データの構成要素を使い結果を計算
• 各セレクタ式は適切なセレクタを構造データパラメータに適用
• Body Definition:プログラムの定義本体を具体化する
• Test:検査を通じた誤り（エラー）の発見
例題：原点からの距離
二次元平面上の点の，原点までの距離を求める
関数 distance_to_0 を作る
点 (3, 4)
のデータ
5
distance_to_0
入力
入力は点を表すデータ
出力
出力は数値
プログラム設計法：データの解析と定義
処理対象がN個の特性を持つならNフィールドの構造体を導入 →
今回，点は2つの座標値を持つので2つのフィールドの構造体
(define-struct posn (x y))
可能な限り正確に posn構造体データ定義の仕様を記述:
–
–
後にデータ定義に対応した関数テンプレートを作成
フィールドがどのような種類のデータを含むか?
注：DrRacket
では定義済
posn型の構造体を生成するにはコンストラクタを使う:
(make-posn num1 num2) ここで num1 num2は数値
この構造体データの例:
(make-posn 3 4)
(make-posn 12 5)
プログラム設計法： Contract, Header
Contract の定式化のために使うことができるもの
• numberや symbolのような不可分データのクラス名
• posn のようなデータ定義で導入した名前
;; distance_to_0: posn -> number
(define (distance_to_0 a_posn) … )
プログラム設計法：テンプレート
本体より先にまずテンプレートを設計
• ヘッダと，可能な全セレクタ式を列挙した本体を記述。
• 各セレクタ式は適切なセレクタを入力の構造体データ
に適用したもの
–
(関数が入力の構造体データの要素を使う計算をすることを反映)
入力は posn 型構造体のデータ a_posn
• セレクタは2つ： posn-x posn-y
;; distance_to_0: posn
(define (distance_to_0
… (posn-x a_posn)
… (posn-y a_posn)
-> number
a_posn)
…
… )
セレクタ posn-xでposn 型構造体の入力データ a_posn
のx 座標フィールド値の取得、y座標フィールド値も同様
プログラム設計法： Example
二次元平面上の点の，原点までの距離を求める
(distance_to_0 (make-posn 3 4))
;; 期待される値 5
(distance_to_0 (make-posn 12 5))
;; 期待される値 13
プログラム設計法：本体定義
基本演算や他の関数を使い答を計算する式を定式化
– 利用可能なデータは入力、セレクタ式の結果
テンプレート：
(define (distance_to_0 a_posn)
… (posn-x a_posn) …
… (posn-y a_posn) … )
x座標値
y座標値
セレクタで参照した値を二乗して
本体定義：
加算し平方根を求める
(define (distance_to_0 a_posn)
(sqrt
(+ (sqr (posn-x a_posn))
(sqr (posn-y a_posn)))))
distance_to_0 関数
x の2乗と y の2乗を加え平方根を求める
;; distance_to_0: posn -> number
;; compute the distance of a posn to the origin
;; (distance_to_0 (make-posn 3 4)) = 5
(define (distance_to_0 a_posn)
(sqrt
(+ (sqr (posn-x a_posn))
(sqr (posn-y a_posn)))))
セレクタ posn-xでposn 型構造体の入力データ a_posn の
x 座標フィールド値を取得、 y 座標フィールド値も同様
x 座標値の2乗と y座標値の2乗を加え平方根を求めている
プログラム全体（例）
(define-struct posn (x y))
(define a-posn (make-posn 3 4))
;; distance_to_0: posn -> number
(define (distance_to_0 a-posn)
(sqrt
(+ (sqr (posn-x a_posn))
(sqr (posn-y a_posn)))))
;; test
> (distance_to_0 a-posn)
5
#include <stdio.h> C言語の場合
#include <math.h>
typedef struct{ int x; int y; } posn;
// sqr: double -> double
double sqr(double x){ return x*x; }
// distance_to_0: posn -> double
double distance_to_0(posn a){
return sqrt(sqr(a.x)+sqr(a.y));
}
// test
void main(){
posn a;
a.x=3; a.y=4;
printf(“%f”, distance_to_0(a));
}
練習
前述の personal_info 構造体について
– 構造体 personal_info 型のデータ a-person の年
齢(age)が20以上ならば true を，20未満なら false
を出力する関数 check-age1 を作成せよ。
– 構造体 personal_info 型のデータ a-person の年
齢(age)が20以上ならば「‘Adult」を，20未満なら
「’Clild」を出力する関数 check-age2 を作成せよ。
様々なデータとその区別
データの種類として構造体が加わった
•
•
•
•
数:数値情報の表現;
ブール値:真か偽であるか;
記号: 記号情報の表現;
構造体: 合成データの表現
様々なデータを処理する関数は
• 数と構造体の双方を含む場合、
• 異なる複数種類の構造体を含む場合、
などデータを区別する必要がある
述語(Predicate) ：データの特定の形式を判断する演算
•
•
•
•
•
number?
boolean?
symbol?
string?
struct?
値が数なら true 違えば falseを返す
同様にブール値かどうか
同様にシンボルかどうか
同様に文字列かどうか
同様に構造体かどうか
また構造体にもさまざまな定義があるのでその区別も必要
構造体 posn に対する posn? や personal_info の personal_info?
これまでの Scheme
Scheme も自然言語同様に語彙と文法を持つ言語 (構造体の追加)
語彙
文法：語彙を用いてプログラム(式
と定義)を作る規則
•変数：関数と値の名前
定義
•キーワード： (変数には使用不可)
–define define-struct cond else • 関数定義
– (define (関数名変数並び) 式)
•定数
–単純値：数, ブール値, シンボルなど
• 変数定義
–合成値：構造体(固定要素数)
•プリミティブ演算：
–四則演算子：+ - * /
–比較演算子：< <= > >= =
–データ特性の判定： even? symbol?
– (define 変数名式)
• 構造体定義
(define-struct
構造体名 (フィールド並び))
式
number? struct? …
• 変数
–論理演算子：and or not
• 定数
–構造体演算(コンストラクタ,セレクタ)
• プリミティブ演算の適用
–その他の演算子： abs remainder
quotient max min sqrt expt log • 定義した関数の適用
sin cos tan asin acos atan など
• 条件式
課題
課題1
構造体 posn のデータ a_posn の x 座標の値が 0 と 10
の間にある場合に限り true を返し，範囲外の場合には
false を返すような関数 xwithin を作成せよ。
また点 a (3,4) と点 b (12, 5) に対する実行結果はどうな
るか。
– 但し，x = 0 あるいは x = 10 のときには false を返すこと．
– ヒント：次の空欄を埋めなさい
(define (xwithin a_posn)
(cond
[
[else
]
]))
解答例
(define-struct posn (x y))
;; xwithin: posn -> true or false
;; (xwithin (make-posn 3 4)) => true
;; (xwithin (make-posn 12 5)) => false
(define (xwithin a_posn)
(cond
[(and (< 0 (posn-x a-posn))
(< (posn-x a-posn) 10)) true]
[else
false]))
;; 以下と同じ
(define (xwithin a_posn)
(and (< 0 (posn-x a-posn)) (< (posn-x a-posn) 10)))
課題2
構造体 personal_info 型のデータ a-person
の年齢(ageフィールド)が20以上ならば名前(name
フィールドの文字列) を，20歳未満なら匿名を表
す文字列 "anonymous" を出力する関数 checkname1 を作成せよ。
入力は personal_info構造体
出力は文字列（string）
check-name1
入力
出力
(make-personal_info "Ken" 18 "Ropponmatsu") ⇒ "anonymous"
(make-personal_info "Bill" 20 "Hakozaki") ⇒ "Bill"
解答例
(define-struct personal_info (name age address)
(define (check-name1 a-psn)
(cond
[(<= 20 (personal_info-age a-psn))
(personal_info-name a-psn)]
[else “anonymous”]))
;; test
(check-name1
(make-personal_info “Matsuzaka” 33 “Fukuoka”))
=> “Matsuzaka”
課題3
構造体 personal_info 型のデータ a-person
のageフィールドの値が，引数として与えられるあ
る年齢の値と一致するならば，名前(name フィー
ルドの値) を，一致しなければ“failed” を出力
する関数 check-name2 を定義せよ。
入力は personal_info構造体
のデータと年齢(数)
出力は文字列（string）
check-name2
入力
出力
(make-personal_info "Ken" 18 "Ropponmatsu") と 20 ⇒ "failed"
(make-personal_info "Bill" 20 "Hakozaki") と 20 ⇒ "Bill"
解答例
(define-struct personal_info (name age address)
(define (check-name2 a-psn an-age)
(cond
[(= an-age (personal_info-age a-psn))
(personal_info-name a-psn)]
[else “failed”]))
;; test
(check-name1
(make-personal_info “Matsuzaka” 33 “Fukuoka”) 33)
=> “Matsuzaka”
課題4. 複素数の計算
• Scheme では複素数の計算もできる
足し算 (1+2i) + (3+4i) → 4+6i
引き算 (5+7i) – (3+4i) → 2+3i
かけ算 (1+2i) ×(3+4i) → -5+10i
割り算 (-5+10i) / (3+4i) → 1+2i
（分母の通分）
(-5+10i)/(3+4i)
=(-5+10i)*(3-4i)
/((3+4i)*(3-4i))
=(25+50i)/25
=1+2i
課題4. 複素数の計算
複素数データの表現と演算を独自に作ってみる：
実数部を r ，虚数部を i とする複素数データ comp
• 以下の ? を埋めてみる
– データ定義は (define-?????? comp (?
?))
– コンストラクタは ????-comp
– セレクタは comp-? と, comp-?
• このcompを使い複素数の加減乗除comp+ compcomp* comp/ を定義し以下を実行してみる
(comp+
(comp(comp*
(comp/
(make-comp
(make-comp
(make-comp
(make-comp
1 2) (make-comp 3
5 7) (make-comp 3
1 2) (make-comp 3
-5 10) (make-comp
4))
4))
4))
3 4))
(+ 1+2i 3+4i) →4+6i
(- 5+7i 3+4i) →2+3i
(* 1+2i 3+4i) →-5+10i
(/ -5+10i 3+4i)→ 1+2i
と同等の計算
解答例
(define-struct comp (r i)
(define (comp+ c1 c2)
(make-comp (+ (comp-r c1) (comp-r c2))
(+ (comp-i c1) (comp-i c2))))
(define (comp- c1 c2)
(make-comp (- (comp-r c1) (comp-r c2))
(- (comp-i c1) (comp-i c2))))
(define (comp* c1 c2)
(make-comp (+ (* (comp-r c1) (comp-r c2))
(* -1 (comp-i c1) (comp-i c2)))
(+ (

Download Report