2017年6月24日土曜日

The Rust Programming Language 2nd 6日目 struct

![](https://doc.rust-lang.org/book/second-edition/]
Apache License Version 2.0

Chapter 4. Understanding Ownership

4.3 Slices

ownershipを持たないデータ型にsliceがある.sliceによってheapデータの一部分のreferenceを得られる.

String Slices

string sliceStringの一部へのreferenceであって,

let s = String::from("hello world!");
let hello = &s[0..5];
let world = &s[6..11];

という形をしている.&s[i, j]sの左からi番目からj-1番目までへのreferenceで,sのheapのi番目へのポインタと長さをスタックにしたデータである.

sの最後まで含んだsliceを作るときは,&s[i..]と,終端を省略できる.sをまるごとsliceにするときは,単に&s[..]と書く.String型のsliceを&strと書く.
&Stringを引数として,それに初めて空白が現れるまでの文字列のsliceを返す関数first_word()を実装する.

src/main.rs

fn first_word(s: &String) -> &str {
  let bytes = s.as_bytes();

  for (i, &iter) in bytes.iter().enumerate() {
    if item == b' ' {
      return &s[0..i];
    }
  }
  &s[..]
}

String Literals Are Slices

let s = "Hello, world!";
としたとき,sはどこかにあるimmutableな“`”Hello, world!”へのsliceである.

String Slices as Parameters

fn first_word(s: &String) -> &str {
はStringのreferenceしか引数に取れないが,文字列リテラルがStringのsliceであることを考えれば,同時に文字列リテラルを引数に取れるようにfirst_wordを改良できる.

src/main.rs

fn first_word(s: &str) -> &str {
  let bytes = s.as_bytes();

  for (i, &item) in bytes.iter().enumerate() {
    if item == b' ' {
      return &s[0..i];
    }
  }
  &s[..]
}

fn main() {
  let my_string = String::from("hello world!");
  let word_1 = first_word(&my_string[..]);            // my_string[..]はslice

  let my_string_literal = "hello, world";   
  let word_2 = first_word(&my_string_literal[..]);    // my_string_literal[..]はSlice
  let word_3 = first_word(&my_string_literal);        // my_string_literalはすでにslice

  println!("first_words is: {}, {}, {}", word_1, word_2, word_3);
}

shell

    Finished dev [unoptimized + debuginfo] target(s) in 0.0 secs
     Running `target/debug/ownership`
first_words is: hello, hello,, hello,

Other Slices

Array型にもsliceを考えられる.

let a = [1, 2, 3, 4, 5];
let slice = &a[1..3];

この場合sliceは“`&[i32]”’型となる.

Chapter 5. Structs

structはプログラマが定義できるデータ型で,オブジェクト指向言語におけるクラスのような概念である.タプルと同様に異なった型の変数をその中に持つことが出来るが,それぞれの変数に名前をつけることが出来るから,変数の個数を増減させるとき,いちいち変数のインデックスを考えなくて良い.

structを定義するには,struct 名前 { 名前1: 型1, ...}と書く.例えば

struct User{
  username: String,   // &strにしなかった理由は次節
  email: String,
  sign_in_count: u64,
  active: bool,
}

によって簡易的なユーザーアカウントのstructが定義できる.
structを実際に使うには,名前 { key: value, ...}とすれば,そのstructのinstanceを生成できる.必ずしもすべての値を指定する必要はない.

let user1 = User {
  email: String::from("hoge@fuga.com"),
  username: String::from("hogefuga"),
  active: true,
};

さらに,user1.emailのようにして,具体的な値を読み出せる.

Ownership of Struct Data

structが,他の変数が持っているheapへのreferenceを保持することは可能だが,それにはlifetime(chap.10)の導入が必要なので,この章ではstructの持つデータはreference以外とする.

An Example Program

四角形の面積を計算するプログラムを作る.

src/main.rs

struct Rectangle {
    length: u32,
    width: u32,
}

fn main() {
    let rect1 = Rectangle { length: 50, width: 30 };

    println!(
        "The area of the rectangle is {} square pixels.",
        area(&rect1)                                        // rect1をborrow
    );
}

fn area(rectangle: &Rectangle) -> u32 {                     // structのborrowも&名前
    rectangle.length * rectangle.width
}

shell

     Running `target/debug/rectangle`
The area of the rectangle is 1500 square pixels.

Adding Useful Functionality with Derived Traits

上のプログラムで,main内にprintln!("rect1 is {}", rect1);とすると,コンパイルエラーが生じる.これはprintln!({}, rect1)とすると,println!はrect1をDisplayという仕組みで表示しようとするが,structには,Displayによって何を表示するか明示されていないために起こる.ここで,println!("rect1 is {:?})とし,プログラム先頭に#[derive(Debug)]と書けば,rect1のすべてを表示してくれる.

shell

     Running `target/debug/rectangle`
rect1 is Rectangle { length: 50, width: 30 }

Method Syntax

Methodはfunctionに似た機能で,structに付属する.methodの最初の引数は必ずselfであり,selfとはそのmethodを呼び出したstructのinstanceのことである.

Defining Methods

structを定義したブロックと平行して,impl struct名{ fn …}としてmethodを定義できる.例えば

src/main.rs


#[derive(Debug)]
struct Rectangle {
  length: u32,
  width: u32,
}

impl Rectangle {
  fn area(&self) -> u32 {
    self.length * self.width
  }
}

fn main() { 
  let rect1 = Rectangle { length: 50, width: 30};
  println!{
    "The area of the rectangle is {} square pixels",
    rect1.area()
  };
}

shell

     Running `target/debug/rectangle`
The area of the rectangle is 1500 square pixels

このようにRectangleというstruct上のmethod, areaを定義できた.
methodによってinstanceのデータを変化させたいときは,methodの引数を&mut selfとする.ownershipを移してしまい時は単にselfとすればよい.

Methods with More Parameters

self以外に引数をもつmethodもfunctionの要領で定義できる.
他のRectangleを引数にとって,selfが他のRectangleを内側に含むことが出来るか否かを返す関数can_holdを定義する.

src/main.rs

fn main() {
  let rect1 = Rectangle {length: 50, width: 30};
  let rect2 = Rectangle {length: 40, width: 10};
  let rect3 = Rectangle {length: 45, width: 60};

  println!("Can rect1 hold rect2? {}", rect1.can_hold(&rect2));
  println!("Can rect1 hold rect3? {}", rect1.can_hold(&rect3));
}

// struct Rectangle 略

impl Rectangle {
  fn area(&self) -> u32 {
    self.length * self.width
  }

  fn can_hold(&self, other: &Rectangle) -> bool {
    self.length > other.length && self.width > other.width
  }
}

shell

     Running `target/debug/rectangle`
Can rect1 hold rect2? true
Can rect1 hold rect3? false

Associated Functions

implにおいて,selfを引数に取らない関数も定義できる.こうして定義された関数をassociated functionという.String::fromはassociated functionの一つである.associated functionはよくconstructor, すなわちそのstructの新しいinstanceを生成するために実装される.たとえば

impl Rectangle {
  fn square(size: u32) -> Rectangle {
    Rectangle { length: size, width: size}
  }
}

は正方形を生成するassociated functionで,
lket sq = Rectangle::square(3)などとして呼ぶ.

OpenStax Calculus 01日目

Creative Commons Non-Commercial ShareAlike (CC BY-NC-SA) 4.0 license

Volume 2. Chapter 4. Introduction to differential equations

4.1 Basics of Differentail Equations

General Differential Equations

未知のがあって,その微分との方程式という方程式が与えられたとき,これをdifferential equation(微分方程式)という.をその微分方程式の解という.

Example 4.1

の解である.

Definition

微分方程式があるとき, ならばであるとき,をこの微分方程式のorder(階数)という.

General and Particular Solutions

がある微分方程式の解であるとき,としても,もとの微分方程式は成立する.このように,がそれぞれのにどんな値を取らせてももとの微分方程式の解となり,微分方程式の解が常にに適当なたちを代入すれば表現できるとき,をもとの微分方程式のgeneral solution(一般解)という.

Initial-Value Problems

階微分方程式は一般に無限個の解をもつが,個以上の初期値が与えられると,その解はただ一つに定まる.定まった解をparticular solution(特殊解)という.微分方程式と初期値が与えられたとき特殊解を求める問題をinitial-value problem(初期値問題)という.

Example 4.5


を解く.

右辺にを代入するとに等しくなるから,.すなわち
以上より解は

4.2 Direction Fields and Numerical Methods

Creating Direction Fields

の解の振る舞いを図示するため,平面上のあらゆる点(現実的には適当に等間隔においた点)におけるの値を,その点を始点とした矢印の傾きとして,平面を矢印でうめつくしたものをdirection field(方向場)という.方向場の矢印に沿った滑らかな曲線は無限に存在して,その曲線のそれぞれがの解である.
enter image description here
enter image description here

Definition

の解で,と書けるものをequilibrium solution(平衡解)という.
ならであり,を解けば平衡解が得られる.
さらに,平衡解はという直線にどう近づいていくかによって,いくつかに分類できる.

Definition

という微分方程式にという平衡解があるとすと,
1. があって, 任意ので,初期値問題
の解がに収束するとき,
asymtotically stable solutionであるという.
2. 上の初期値問題で,解がに収束しないとき,
asymptotically unstable solutionという.
3. 上のどちらでもないとき,asymptotically semi-stable solutionであるという.

Example 4.8 Stability of an Equilibriumm solution


として,平衡解を見出して分類せよ.
Solution.
enter image description here

方向場はfig. 4.12
平衡解はとわかる.という直線の上下で矢印はの方向を向いているから,はasymptotically stable solution. という直線の下で,矢印はから離れる方向を向いているから,asymptotically unstable. という直線の上で矢印はから離れる方向を向いていて,下でに向かう方向を向いているから,asymptotically semi-stable solutionである.

Euler’s Method

Theorem 4.1 Euler’s Method


という初期値問題で,十分小さいを固定して

によって離散的な近似解を得る方法をEuler’s methodという.

4.3 Separable Equations


と書けるような常微分方程式をSeparable Equationという.Separable equationは簡単に解ける.

Problem-Solving Strategy: Separation of Variables

  1. となるがあるとき,そのは定数解である.
  2. であるについて,

    と書ける.
  3. 両辺を積分する.
  4. 可能なら,積分でできた等式をで解く.
  5. 初期値が定められているなら,その初期値を満たすように積分定数を調整する.

Example 4.11


を解く.
1. これはを満たさないので,解でない.
2.
3. 両辺を積分して,

4. 整理して,

さらにについて解くことは出来るが,だいたいここまで書けば十分.初期値問題の場合もこの式に初期値を入れたほうが見通しがいい.
5. を代入して,

2017年6月23日金曜日

Basic Analysis (Jiri Lebl) 26日目 縮小写像と不動点定理

CC BY-NC-SA 3.0

Chapter 7. Metric Spaces

は距離空間とする.

7.6 Fixed point theorem and Picard’s theorem again

fixed point theorem(不動点定理)をcontraction mapping(縮小写像)の場合に証明する.

Definition

をfixed point(不動点)に持つ

7.6.1 Fixed point theorem

Definition 7.6.1

contraction(or contractive map)である
-Lipschitz写像

Theorem 7.6.2 (Contraction mapping principle or Fixed point theorem)

は空でない完備距離空間で,は縮小写像とする.このときは不動点を唯一つ持つ.
proof.

とする.として無限点列が定まる.
 
が必ず成立する.したがってなら

故に,はCauchy列である.完備性から,に収束する.はcontractionだから-Lipschitzだから連続.連続性よりが成立し,の不動点.
さらに,の不動点であると仮定するとき,
が成立する.から,.距離の公理から,.一意性が示せた.

7.6.2 Picard’s theorem

この節では,距離空間は, の組を考える.この距離空間は完備である.
fixed point theoremを使って,古典的なPicard’s theoremを証明する.

という微分方程式で,初期値が与えられているとき,であるを考える.簡単のため,とか,とか書くことにする.Picard’s theoremは,Lipschitz連続性の過程のもとで,の近くで,述べたようなが存在することを主張している.

Theorem 7.6.3 (Picard’s theorem on existence and uniqueness)

はcompact区間とする.の内部として,が連続で,第二変数についてLipschitz連続である,すなわちがあって,

が成立する.
このとき,と微分可能な,があって,

が成立する.

proof.

としてよい.はcompactで,は連続だから,は有界.なるがある.なるについて,

とするとであって

とすると,は閉集合.
proof. (Exercise 7.6.1)

が距離で成立するなら,に一様収束するということ.
一様収束する連続関数列は連続だから,. よって成立.

a,はcompleteだから,はcompact.


とする.が連続なら,の関数として連続である.
proof. (Exercise 7.6.2)

とする. なるについて,

よって示せた.

に,で抑えられるから,

とすると,
したがって.
よってからへの写像と考えられる.
が縮小写像と示す.に,

ゆえに

から,確かに縮小写像.
Theorem 7.6.2からなるがただ一つ存在し,

微積分学の基本定理から,で,である

7.6.3 Exercises

Exercise 7.6.4

とする.
a) は縮小写像であることを示せ
b) 不動点を見つけ,一意であることを示せ.
答案.

a)
に, . から,たしかに縮小写像.
b)
とし,によってを定める.その極限とすると,である.
これが不動点であることは実際に関数に代入すれば示せる.また,も不動点であるとすると,
から,.したがって不動点は一意である.

Exercise 7.6.10

は縮小写像で, である距離空間とする.このときは定数であることを示せ.
答案.

この距離関数のもとでが収束する あるがあって,.したがってその極限はの元であって,ゆえにこの距離空間は完備である.は縮小写像だから,Theorem 7.6.2(fixed point theorem)から,は不動点をただ一つもつ.
の不動点とする.すなわち.
は縮小写像だから,に,
が成立する.は離散距離だから,ならばすなわちが成立する.
したがって確かに.すなわちは定数.

The Rust Programming Language 2nd 5日目 Ownership 2

![](https://doc.rust-lang.org/book/second-edition/]
Apache License Version 2.0

Understanding Owenership

4.2 References and Borrowings

ある関数にheap構造の変数を引数として渡すと,その変数をその関数の外でまた利用するには,わざわざ関数の返り値としてその変数を受け取らなければならなかった(前節).referenceという機能によって,そうした手間をかけずにすむ.
&記号によってreferenceを実現する.

src/main.rs

fn main() {
  let s1 = String::from("hello");                     
  let len = calculate_length(&s1);                  // 引数に&をつける

  println!("The length of '{}' is {}. ", s1, len);

}

fn calculate_length(s: &String) -> usize{           // 引数の型名に&をつける
  s.len()
}

shell

Finished dev [unoptimized + debuginfo] target(s) in 0.70 secs
 Running `target/debug/ownership`
The length of 'hello' is 5.

referenceではownershipが移動しないので,reference変数がスコープから出てしまっても,もとの変数がスコープの中にある限り,もとの変数とそれが持つポインタの指すメモリは消えない.

Mutable References

referenceとして得た変数を関数の中で変更するには,もとの変数がmutableであり,関数を呼ぶときもmutable,また呼ばれた関数も,その引数がmutableであると明示しなければならない.

src/main.rs

fn main() {
  let mut s = String::from("hello");  // 最初の変数宣言時にmutと明示
  change(&mut s);                     // 変化させる関数を呼ぶときもmutと明示

  println!("{}", s);
}

fn change(some_string: &mut String){  // 引数がmutと明示
  some_string.push_str(", world");
}

shell

Finished dev [unoptimized + debuginfo] target(s) in 0.34 secs
 Running `target/debug/ownership`
hello, world

ただし,mutable referenceはある変数について同じスコープ内に同時に1つしか存在できない.これはコンパイル時のdata races(データ競合)を防ぐためである.data raceとは,変数が以下の3つの振る舞いをすることである.
1. 2つ以上のポインタが同時に同じデータにアクセスする.
2. 少なくとも1つのポインタがデータを書き込もうとしている.
3. データへのアクセスをsynchronizeする機構がない.
mutable referenceをたかだか1つにすることでdata raceが起こらなくなる.

{}によって新しいスコープを作り,

  • src/main.rs*
fn main() {
  let mut s = String::from("hello");
  {
    let r1 = &mut s;  // ただちに破棄される
  }
  let r2 = &mut s;    // すでにr1は破棄されているからdata raceは生じない
}

何もしないが,コンパイルできる.

mutableなreferenceがあるなら,その変数へのreferenceはimmutable含め唯一つ.
一方で,mutableでないreferenceならいくつあっても良い.
src/main.rs

fn main() {
  let mut s = String::from("hello");

  let r1 = &s;      // immutable
  let r2 = &s;      // immutable
  let r3 = &s;      // mutable
  // let r = mut &s // ERROR!
}

何もしないが,コンパイルできる.7行目のコメントを外すとコンパイルエラー

2017年6月22日木曜日

Basic Analysis (Jiri Lebl) 25日目 連続関数


title :Basic Analysis (Jiri Lebl) 24日目
tags: [数学]


CC BY-NC-SA 3.0

7.4 Completeness nad compactness

7.4.3 Exercises

Exercise 7.4.12

は完備な距離空間とする.
がcompact
は閉集合であり,任意のに,が成立するようにを選べる.
この命題を証明せよ.(このようなをtotally boundedという.)

答案.


は明らかにのopen coverであって,のcompact性から有限被覆を選べるから,成立.

の要素からなる点列がの要素に収束する部分列を持つことを言えば良い.
とする.として,とできるようにを選べる.たちのなかで,の点が無限子あるものを一つ選んで,そのとする.さらに,となるようにを選べて,を被覆するたちのなかでの点が無限子あるものを選んで,とする.これを繰り返して,が作れる.に属するうち,添字が最小でそれ以前に部分列に加えられていないの要素を選んで,部分列を作れる.任意のに,をみたすが存在して,ならばが成立するから,この部分列はCauchy列で,の完備性から収束する.その極限をとすると,は閉集合だから,である.
(Lebesgue covering lemmaを使えば一発だった)

7.4.13

に絶対値距離を入れる.のopen coverで,Lebesgue covering lemmaの結論が成立しなようなものを見つけろ.

答案.
Lebesgue covering lemma: は距離空間で,であり,の任意の点列がの要素に収束する部分列を持つなら,のopen cover を与えられたとき,任意のに,を選べばがなる立つようなが存在する.

とすると,を被覆するが,いかなるを考えても,とすると,なら

7.5 Continuous functions

7.5.1 Continuity

Definition 7.5.1

がそれぞれ距離空間で,とする.
で連続である

以後,この節でははともに距離空間とする.

Proposition 7.5.2

で連続
に収束する任意のについて,.
proof. 略

Example 7.5.3

を,

とする.
に収束するについて,Prop 2.5.5から

7.5.2 Copmactness and continuity

連続写像は必ずしも閉集合を閉集合に移さないが,compact集合はcompact集合に写す.

Lemma 7.5.4

は連続写像とする.がcompactなら,もcompactである.
proof.

の任意の点列はと書ける(一意とは限らない).はcompactだから,収束する部分列がある.連続性より,の極限をとすると,.したがって,の任意の点列がの点に収束する部分列を持つことがわかった.すなわちはcompactである.

Theorem 7.5.5

はcopmact距離空間とする.が連続とすると,は有界で,最大値と最小値を持つ.
proof.

はcompactだから,もまたcompact.はcompactかつ有界である.特に,の完備性からが成立する.よって成立.

7.5.3 Continuity and topology

Lemma 7.5.6

で連続である
の任意の近傍について,の開近傍を含む.
proof. 略

Theorem 7.5.7

が連続である なる任意の開集合に,は開集合.

7.5.4 Uniform continuity

Definition 7.5.9

がuniformly continuous

Theorem 7.5.10

が連続で,がcompactならば,は一様連続.

proof.

とする.すべてのに,があって, ならばが成立する.を被覆するが,はcompactだから,Lebesgue covering lemmaから,あるがあって,任意のが成立する.
で,ならば,であり,.三角不等式から

The Rust Programming Language 2nd 4日目 Ownership 1

![](https://doc.rust-lang.org/book/second-edition/]
Apache License Version 2.0

Understanding Owenership

ownership(所有権)はRustの最大の特徴で,メモリを安全に扱うことを可能にしている.
この章ではサンプルコードに rust fn main() はいちいち書かないことにする.

4.1 What is Ownership?

The Stack and the Heap

stackとheapはプログラムから見た仮想メモリの構造.あるいはOSから見た物理メモリの管理方法.
stackはデータを読み込んだ順に積み上げ(push),その逆順に読み込まれ,読み込まれた値を削除する(pop).

stackから値を取り出すとき,取り出す値をいちいち検索しなくて良い(検索できない)うえstackのデータはすべて同じビット長なので,stackは高速.プログラムが関数を呼ぶとき,その引数とローカル変数はstackにpushされて,関数が実行し終わるとそれらはpopされる.
一方,コンパイル時にはbit長がわからなないデータや,bit長が変わるデータのときは,heapを使う.heapにデータを入れようとすると,OSは空いているメモリの一部をheapのために割り当てて,そのメモリの番地(ポインタ)をプログラムに渡す.これをallocationという.stackにpushすることはallocationとは呼ばない.heapへのアクセスは,ポインタを経由しなければならないので,stackよりも遅い.heapを使うときは,heap上のデータの複製を最小限にし,使わなくなったデータは削除して,メモリ空間を開けなければならない.

Ownership Rules

  1. Rustの変数はそれぞれownerという変数を持っている.
  2. それぞれの変数について,同時に複数のownerは存在できない.
  3. ownerがスコープから出ると,その変数はRustのdrop関数によって削除される.

The String type

コンパイル時にすでに決まっている文字列はstring literalと言ってstackに保存されるが,ユーザーからの入力を受け付けるなどするため,コンパイル時に決まっていない文字列はString型といって,heapに保存される.

Ways Variables and Data Interact: Move

変数がheapであるときはRust特有のmoveという現象によって,他の言語では起こらないエラーが出る.
s1という変数は

という形をしていて,ポインタ,長さ,最大長さのデータがスタックとしてあって,さらにポインタの先に具体的なデータが存在する.ここでs2 = s1としたとき,複製されるのはポインタ,長さ,最大長さのデータだけで,具体的なデータは使いまわされる.

enter image description here
さらに,スコープから出たs1s2を削除しようとして,同じポインタを二度dropしようとすると,衝突が起こって脆弱性につながる.そこでRustはs2=s1を発行した時点でs1は無効な変数であると考え,s1のスタックを削除する.
これは同時に,Rustは自動的には”深い”コピーを作らないということでもある.

fn main() {
  let s1 = String::from("hello");   // Stringはheap
  let s2 = s1;

  println!("s1 = {}", s1);
  println!("s2 = {}", s2);
}

shell

error[E0382]: use of moved value: `s1`
 --> src/main.rs:5:23
  |
3 |   let s2 = s1;
  |       -- value moved here
4 |
5 |   println!("s1 = {}", s1);
  |                       ^^ value used here after move
  |
  = note: move occurs because `s1` has type `std::string::String`, which does not implement the `Copy` trait
  ```

#### Ways Variables and Data Interact: Clone
深いコピーを作りたいときには```clone()```を使う.
*src/main.rs*
```rust
fn main() {
  let s1 = String::from("hello");   // Stringはheap
  let mut s2 = s1.clone();          // hardcopy


  s2.push_str("_world!");
  println!("s1 = {}", s1);
  println!("s2 = {}", s2);
}




<div class="se-preview-section-delimiter"></div>

shell

Finished dev [unoptimized + debuginfo] target(s) in 0.35 secs
 Running `target/debug/ownership`
s1 = hello
s2 = hello_world!




<div class="se-preview-section-delimiter"></div>

Stack-Only Data: Copy

integerやfloatのような,heapを使わず,stackだけに保存されるデータ型では,常に深いコピーが行われる.
src/main.rs

fn main() {
  let x = 5;
  let y = x;

  println!("the value of x is: {}", x);
  println!("the value of y is: {}", y);
}




<div class="se-preview-section-delimiter"></div>

bash

Finished dev [unoptimized + debuginfo] target(s) in 0.29 secs
 Running `target/debug/ownership`
the value of x is: 5
the value of y is: 5




<div class="se-preview-section-delimiter"></div>

Ownership and Functions

関数の引数に変数を与えるときも,moveの特性に注意しなければならない.

src/main.rs

fn main() {
  let s = String::from("hello");
  takes_ownership(s);                         // この時点でsは失効

  let x = 5;
  makes_copy(x);

  println!("{}", s);                          // ここでsは参照できない.
}

fn takes_ownership(some_string: String) {
  println!("{}", some_string);
}

fn makes_copy(some_integer: i32) {
  println!("{}", some_integer);
}




<div class="se-preview-section-delimiter"></div>

shell

error[E0382]: use of moved value: `s`
 --> src/main.rs:7:18
  |
3 |   takes_ownership(s);
  |                   - value moved here
...
7 |   println!("{}", s);
  |                  ^ value used here after move
  |
  = note: move occurs because `s` has type `std::string::String`, which does not implement the `Copy` trait

error: aborting due to previous error

error: Could not compile `ownership`.

To learn more, run the command again with --verbose.

Basic Analysis (Jiri Lebl) 24日目 completeとcompact

CC BY-NC-SA 3.0

7.4 Completeness nad compactness

は距離空間とする.

7.4.1 Cauchy sequences and completeness

Definition 7.4.1

Cauchy列である

Proposition 7.4.2

距離空間の収束列はCauchy列である.
proof.

に収束するなら,点列の収束の定義から

を満たすが存在する.

Definition 7.4.3

Complete(完備)である
の任意のCauchy列がの点に収束する.

Proposition 7.4.4

にユークリッド距離を入れた距離空間は完備である.
proof. 略

7.4.2 Completeness

Definition 7.4.5

について,compact(コンパクト)である
をみたす開集合族があるとき,有限個を取り出してとなるようにできる.

Proposition 7.4.6

がコンパクトであるとき,は有界かつ閉集合である.
proof. 略

Lemma 7.4.7 (Lebesgue covering lemma)

とする.の任意の点列がの点に収束する部分列を持つとする.のopen coverとすると,任意のに,となるを選べるようなが存在する.
proof.

対偶によって示す.どのをとっても,任意のをみたさないようにを選べると仮定する.
どのにも,となるようなは存在する.よってなるがある.をみたすをとる.かつならば

が成立.すなわち. よっては収束する部分列を持ち得ない.

Theorem 7.4.8

がcompact の任意の点列がの点に収束する部分列を持つ.
proof.


対偶法を用いる.
とする.で,たかだか有限個のが成立するようなが存在すると仮定する.このとき

が成立する.つまりのopen coverである.
から有限個を取り出すと,その和集合は有限集合となって,を被覆できない.これは矛盾.


仮定のもとで,open cover をとる.Lemma 7.4.7から,任意のとなるを選べるが存在する.
と,をみたすをとる.であれば,有限な被覆をみつけたことになる.そうでないとき,があって,をみたすがあって,である.これを無限回繰り返せるとき,無限列が得られる.
は,が成り立つから,Cauchy列でない.したがってはcompactでない.

Proposition 7.4.10

がcompactでが閉集合ならはcompact.
proof. 略

Theorem 7.4.11 (Heine-Borel)

が有界かつ閉集合ならはcompact
proof. 略

2017年6月20日火曜日

The Rust Programming Language 2nd 3日目 変数,基本型,関数

https://doc.rust-lang.org/book/second-edition/
Apache License Version 2.0

Common Programing Concepts

多くの言語に共通する機能がRustではどう実現されているか

3.1 Variables and Mutability

bash

cargo new --bin variables

で実験するプロジェクトを作る.
Rustでは,変数はデフォルトではimmutableである.つまり,一度変数に値を代入するとその後変更できない.

src/main.rs

fn main() {
  let x = 5;
  println!("The value of x is: {}", x);
  x = 6;
  println!("The value of x is: {}", x);
}

cargo runでビルドして実行してみると,

error[E0384]: re-assignment of immutable variable `x`
 --> src/main.rs:4:5
  |
2 |     let x = 5;
  |         - first assignment to `x`
3 |     println!("The value of x is: {}", x);
4 |     x = 6;
  |     ^^^^^ re-assignment of immutable variable

とエラーが出る.こうして,Rustはプログラマが予期しない代入を防いでいる.

しかし,いちいち新しい変数を用意するのは不便なときもある.そこで
src/main.rs

fn main() {
  let mut x = 5;
  println!("The value of x is: {}", x);
  x = 6;
  println!("The value of x is: {}", x);
}

とすると,

   Compiling variables v0.1.0 (file:///home/ren/Projects/variables)
    Finished dev [unoptimized + debuginfo] target(s) in 0.34 secs
     Running `target/debug/variables`
The value of x is: 5
The value of x is: 6

このようにletによる変数宣言と同時にmutによって変数をmutableにすることが出来る.

3.2 Differences Between Variables and Constants

定数とimmutableな変数は似ているが,いくつか違いがある.
1. immutable変数はmutによってmutableにできる.
2. 定数にはプログラムのどこからでも参照できる.
3. 定数はプログラム実行時に計算される値は代入できない.つまり,コンパイル時に決定される値しか代入できない.

Shadowing

新しい変数をすでにある変数と同じ名前で宣言することをshadowingという.このとき,新しい変数ははじめの変数をshadowしているといい,はじめの変数は新たな変数にshadowされたという.

src/main.rs

fn main() {
  let x = 5;
  let x = x + 1; // shadow 1回目
  let x = 2 * x; // shadow 2回目

  println!("The value of x is: {}", x);
}

shell

ren@ren-ThinkCentre-Edge72:~/Projects/variables$ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.0 secs
     Running `target/debug/variables`
The value of x is: 12

mutableな変数でも,宣言したあとで型を変えることはできない(静的型付).

src/main.rs

fn main() {
  let mut spaces = "  "; // 右辺は文字列
  spaces = spces.len();  // 右辺は整数の2
}

shell

ren@ren-ThinkCentre-Edge72:~/Projects/variables$ vim src/main.rs

   Compiling variables v0.1.0 (file:///home/ren/Projects/variables)
error[E0308]: mismatched types
 --> src/main.rs:3:14
  |
3 |     spaces = spaces.len()
  |              ^^^^^^^^^^^^ expected &str, found usize
  |
  = note: expected type `&str`
             found type `usize`

変数名を型を変えながら使いまわしたいとき,shadowingが有効.

Data Types

Rustは静的型付言語だが,変数宣言時に型を指定しなくても,コンパイラが推測してくれる.しかし,プログラマが型を指定しなければならない場合もある.

Scalar Types

整数,浮動小数点数,真理値,文字は長さが固定されている変数であり,scalarという.

Integer Types (自然数型)

自然数型は符号のあるなしとビット長によっての10種類がある.ビット長は8, 16, 32, 64, そしてアーキテクチャ依存のsize長がある.符号付きならi,符号なしならuを頭につけて,ビット長を尾につけてその型を指定できる.例えば符号なし32bitなら u32 である. Rustのデフォルトはi32で,64bit CPUでもこれが最も早く処理できることが多い.

src/main.rs

fn main() {
  let x:i32 = 2147483648;     // i32だとオーバーフローする値
  println!("x is {}", x);
}

shell

Compiling variables v0.1.0 (file:///home/ren/Projects/variables)
warning: literal out of range for i32
--> src/main.rs:2:13
|
2 |     let x = 2147483648;
|             ^^^^^^^^^^
|
= note: #[warn(overflowing_literals)] on by default

 Finished dev [unoptimized + debuginfo] target(s) in 0.32 secs
  Running `target/debug/variables`
x is -2147483648 

オーバーフローする値を代入しても,オーバーフローしないような型にしてくれるわけではない.コンパイルエラーにはならず,コンパイル時に警告される.

Floating-Point Types (浮動小数点数型)

小数点以下が表現できる.32bit長(f32)と64bit長(f64)があるが,速さはほとんど同じなので64bit長がよく使われる.

Numeric Operations

算術的演算はpythonと同じ記法で行える.しかし,自然数と浮動小数点数の演算を直接行うことはできない.

src/main.rs

fn main() {
  let a = 3;
  let b = 3.0;
  let c = a + b;
  println!("int plus float: {}", c);
}

shell

Compiling variables v0.1.0 (file:///home/ren/Projects/variables)
error[E0277]: the trait bound `{integer}: std::ops::Add<{float}>` is not satisfied
--> src/main.rs:4:13
|
4 |     let c = a + b;
|             ^^^^^ the trait `std::ops::Add<{float}>` is not implemented for `{integer}`
|
= note: no implementation for `{integer} + {float}`

error: aborting due to previous error

error: Could not compile `variables`.

To learn more, run the command again with --verbose.

The Boolean Type

真理値はboolによって指定できて,truefalseの値だけを取る.
型を指定せずとも,truefalseを宣言時に代入すれば,コンパイラがbool型と推測する.

The Character Type

1文字を表現できるスカラー型はcharで,内部ではUnicodeを保持する.

Compound Types

長さが2以上ある変数の型.tuplearrayがある.

Grouping Values into Tuples

必ずしも共通でない型の値たちを一つの変数に代入する型.カッコでくくり,コンマで要素を区切る.タプル定義でも型推測は行われるが,プログラマが型を指定することも出来る.タプルの要素を取り出す方法は2つある.
1. pattern matching: タプルの長さと同じ個数の変数にタプルを代入し,求めたい要素の入っている変数にアクセスする
2. index: タプルの一番左の要素を0として,求めたい変数のインデックスがiなら,tupple.iでアクセスできる.

src/main.rs

fn main() {
  let tup = (500, 6.4, 1);
  let typed_tup: (i32, f64, u8) = (500, 6.4, 1);
  let (x, y, z ) = tup;
  println!("The value of y is: {}", y);           // pattern matchingによるアクセス

  println!("The value of y is: {}", typed_tup.1); // indexによるアクセス
}

shell

Compiling variables v0.1.0 (file:///home/ren/Projects/variables)
 ~ 略 (一度も使っていない変数があると怒られる) ~ 
Finished dev [unoptimized + debuginfo] target(s) in 0.43 secs
 Running `target/debug/variables`
The value of y is: 6.4
The value of y is: 6.4

Arrays

tuppleと違って,すべての要素が同じ型でなければならない.また,長さは固定である.定義するときは’[ ]’でくくって、コンマで要素を区切る.arrayもtuppleのようなインデックスが振られているが,アクセスするにはarray[i]と書く.arrayの長さに反するインデックスでアクセスしようとすると,コンパイルエラーは起きないが実行時にpanicする.

src/main.rs

fn main() {
  let a = [1, 2, 3, 4, 5];
  let index = 10;
  let element = a[index];

  println!("The value of element is: {}", element);
}

shell

Compiling variables v0.1.0 (file:///home/ren/Projects/variables)
 Finished dev [unoptimized + debuginfo] target(s) in 0.33 secs
  Running `target/debug/variables`
thread 'main' panicked at 'index out of bounds: the len is 5 but the index is 10', src/main.rs:4
note: Run with `RUST_BACKTRACE=1` for a backtrace.

3.3 How Functions Work

新しくfunctionsプロジェクトを作る.
関数はfn <関数名>() {}で定義され,{}の中身が実際に実行される.2つ以上関数をつくって,片方からもう片方の関数を利用することが出来る.

src/main.rs

fn main() {
  println!("Hello, world!");

  another_function();
}  

fn another_function() {
  println!("Another function.");
}

shell

Compiling functions v0.1.0 (file:///home/ren/Projects/functions)
 Finished dev [unoptimized + debuginfo] target(s) in 0.36 secs
  Running `target/debug/functions`
Hello, world!
Another function.

Function Parameters

関数の引数は,fn name () {}()の中で指定する.引数の名前だけでなく,型も同時に指定しなければならない.

src/main.rs

fn main() {
  another_function(1, 2);
}

fn another_function(x:i32, y) {  // yの型を指定していない.
  println!("x is {}", x);
  println!("y is {}", y);
}

shell

Compiling functions v0.1.0 (file:///home/ren/Projects/functions)
error: expected one of `:` or `@`, found `)`
--> src/main.rs:6:29
|
6 | fn another_function(x:i32, y) {
|                             ^ expected one of `:` or `@` here

error[E0425]: cannot find value `y` in this scope
--> src/main.rs:8:25
|
8 |     println!("y is {}", y);
|                         ^ did you mean `x`?

error: aborting due to 2 previous errors

error: Could not compile `functions`.

Statements and Expressions

Rustはepxressionベースの言語である.statementとexpressionの違いは,後者が返り値を返すが,前者はそうでないという点である.
変数宣言や関数定義はstatementであるから,返り値を返さない.よって

let x = (let y = 6);

はコンパイルできない.
一方で,expressionはプログラムの大半を占めている.

fn main() {
  let x = 5;      // 5自体はexpressionで,5を返す. expressionはstatementの一部になれる.

  let y = {
    let x = 3;    
    x + 1         
  };              // {}はexpression

  println!("The value of y is: {}", y);  // マクロはexpression
}

最後に;のない行はexpressionであり,;を加えるとstatementになる.

Functions with Return Values

関数はfn name () -> type {}によって返り値を返すようにすることが出来る.返される値は,{}の中の最後のexpressionの値である.
src/main.rs

fn five() -> i32 {
  4;   // このステートメントは特に何もしない.
  5    // これが{}の中の最後のexpressionだから,これの返り値がfive()の返り値になる.
}

fn main() {
  let x = five();
  println!("The value of x is: {}", x);
}

shell

Compiling functions v0.1.0 (file:///home/ren/Projects/functions)
 Finished dev [unoptimized + debuginfo] target(s) in 0.34 secs
  Running `target/debug/functions`
The value of x is: 5

返り値が返されると定めた関数にepxressionがない場合,コンパイルエラーになる.

src/main.rs

fn plus_one(x:i32) -> i32 {
  x + 1;
}

fn main() {
  let x = plus_one(5);
  println!("The value of x  is: {}", x);
}

shell

Compiling functions v0.1.0 (file:///home/ren/Projects/functions)
error[E0308]: mismatched types
--> src/main.rs:1:27
|
1 |   fn plus_one(x:i32) -> i32 {
|  ___________________________^
2 | |   
3 | |   x + 1;
4 | | }
| |_^ expected (), found i32
|
= note: expected type `()`
          found type `i32`
help: consider removing this semicolon:
--> src/main.rs:3:8
|
3 |   x + 1;
|        ^

error: aborting due to previous error

error: Could not compile `functions`.

To learn more, run the command again with --verbose.

Control Flow

条件分岐とループ

if expression

if condition_1 {codeblock_1} else if condition_2 {codeblock_2} … else {codeblock_0}
condition_1から順にconditionがtrueか調べられ,condition_kがtrueならcodeblock_kが実行され,すべてのconditionがfalseなら,codeblock_0が実行される.elseがない場合,何も実行されない.codeblockたちをifのarmと呼ぶことがある.conditionは,評価するとBoolを返すexpressionでなければならない.

src/main.rs

fn main() {
  let number = 3;
  if number < 5 {
    println!("condition was true");
  } else {
    println!("condition was false");
  }
}

shell

Compiling branches v0.1.0 (file:///home/ren/Projects/branches)
 Finished dev [unoptimized + debuginfo] target(s) in 0.35 secs
  Running `target/debug/branches`
condition was true

Using if in a let statement

ifはexpressionなので,letを使った変数宣言の右辺に置くことが出来る.
src/main.rs

fn main() {
  let condition = true;
  let number = if condition {
    5
  } else {
    6
  };

  println!("The value of number is: {}", number);
}

shell

Compiling branches v0.1.0 (file:///home/ren/Projects/branches)
 Finished dev [unoptimized + debuginfo] target(s) in 0.34 secs
  Running `target/debug/branches`
The value of number is: 5

ここで,変数numberにはconditionの真偽によって{5}, {6}のコードブロックの返り値が代入されるが,このコードブロックたちの返す値の型が異なっていると,numberの型が推測できず,コンパイルエラーになる.
src/main.rs

fn main() {
  let condition = true;
  let number = if condition {
    5
  } else {
    "six"
  };

  println!("The value of number is: {}", number);
}

shell

Compiling branches v0.1.0 (file:///home/ren/Projects/branches)
error[E0308]: if and else have incompatible types
--> src/main.rs:3:16
|
3 |     let number = if condition {
|  ________________^
4 | |       5
5 | |     } else {
6 | |         "six"
7 | |       };
| |_______^ expected integral variable, found &str
|
= note: expected type `{integer}`
          found type `&str`

error: aborting due to previous error

error: Could not compile `branches`.

Repetition with Loops

Rustはloop,while,forの3種類のループを実装している.

Repeating Code with loop

明示的にbreakされるまでループを続ける.

src/main.rs

fn main() {
  loop {
    println!("again!");
  }
}

shell

again!  # 無限ループ

Conditional Loops with while

ループ中毎回条件を評価し,条件がfalseになったらループを中断する.
src/main.rs

fn main() {
  let mut number = 3;
  while number != 0 {
    println!("{}", number);
    number = number - 1;
  }
  println!("LIFTOFF!!!");
}

shell

Compiling branches v0.1.0 (file:///home/ren/Projects/branches)
 Finished dev [unoptimized + debuginfo] target(s) in 0.35 secs
  Running `target/debug/branches`
3
2
1
LIFTOFF!!!

Looping Through a Collection with for

tupplearrayの要素ごとに処理を実行したいとき,forが使える.また,決まった回数ループしたい場合,Range型にforを使って実現できる.

src/main.rs

fn main() {
  for number in (1..4).rev() { 
    println!("{}!", number)
  }
  println!("LIFTOFF!!!");
}

shell

Compiling branches v0.1.0 (file:///home/ren/Projects/branches)
 Finished dev [unoptimized + debuginfo] target(s) in 0.38 secs
  Running `target/debug/branches`
3!
2!
1!
LIFTOFF!!!

Summary (練習)
1. 華氏を摂氏に変換するプログラムを書け.
2. n番目のフィボナッチ数を計算するプログラムを書け

  1. src/main.rs
use std::io;

fn main() {
  println!("Input F temperature!");
  let mut f = String::new();
  io::stdin().read_line(&mut f).expect("Failed to read line.");
  let f: f64 = f.trim().parse().expect("Please type a number!");

  let c = (f - 32.0) * 5.0 / 9.0;
  println!("Fahrenheit {} is Celsius {}", f, c);
}

shell

Finished dev [unoptimized + debuginfo] target(s) in 0.0 secs
 Running `target/debug/branches`
Input F temperature!
911
Fahrenheit 911 is Celsius 488.3333333333333
  1. src/main.rs
use std::io;

fn main() {
  println!("Input integer n!");
  let mut  n = String::new();
  io::stdin().read_line(&mut n).expect("Failed to read line.");
  let n: u32 = n.trim().parse().expect("Plase type an intger!");

  let ans = fibb(n);
  println!("The kth fibbonacci number is: {}", ans);

}

fn fibb(k: u32) -> u32 {
  let ans:u32 = if k == 1 {
   1 } else if k == 2 {
   1 } else { fibb(k-1) + fibb(k-2)};

  ans
}

shell

Finished dev [unoptimized + debuginfo] target(s) in 0.0 secs
 Running `target/debug/branches`
Input integer n!
12
The kth fibbonacci number is: 144