第十三號艦隊

網路上另一個練習Coding跟Algroithm的網站，不過跟TopCoder跟一般的ACM Online Site不同，不限制語言，用任何方式都能，只需要正確答案。

第一題要列出1-999之間，三或五倍數的總和。要用熟悉的C++/Java寫不是不行，不過正好最近在練習Haskell，就用Haskell當做開端。

1
2
3
4
5
6

check x
        | (x `mod` 3 == 0) = True
        | (x `mod` 5 == 0) = True
        | otherwise = False
--- ans [1...999]
ans numbers = sum (filter check numbers)

Functional language的表達能力還真是高。

這篇講的不是什麼技術面，而是每種物件導向程式語言都會碰到的情況。如何存取物件裡面的屬性。把屬性設成公開固然是一種解法，不過這就違反了Information Hiding的原則。各種程式語言作法都不同，這邊講我比較熟悉的部份(C++/C#/Java)。

從Java開始

這次從Java開始談，是因為最單純，沒有任何取巧的空間。

1
2
3
4
5
6
7
8

class Person {
	private String name;
	private int age;
	public String getName() { return name; }
	public void setName(String name) { this.name = name; }
	public int getAge() { return age; }
	public void setAge(int age) { this.age = age; }
};

每個getter/setter都要手刻，雖然可以藉由IDE的幫助，不過還是很麻煩。同樣在JVM上的城市語言，Scala就有在這點著墨。

C++的作法

藉由原本就有的Macro幫助，可以少打幾個字。

1
2
3
4
5
6
7
8
9
10
11

#define get_set_prop(type, Name) \
public: \
        type get##Name() { return Name; } \
        void set##Name(const type& v) { Name = v; }
class Person {
        string Name;
        int Age;
public:
        get_set_prop(int, Age)
        get_set_prop(string, Name)
};

不過也只是少打幾個字而已，IDE對於的Macro的支援度不同，Code completion可能會有問題。
加上Macro天生就很難除錯，Google C++ Coding Style建議能不用Macro就不用。

C#的Property

C#的Property算是一種語法糖，不過由於編譯器的支援，簡化了遇到的問題。以下以C# 4.0的示範

1
2
3
4
5

class Person
{
    public string Name { get; set; }
    public int Age { get; set; }
}

雖然是語法糖，不過這樣表示新蜥易懂，也有很多人試著把這個特性家入到C++中，就知道這特性沒有無所謂，卻很實用。

在Imperative programming下待久了，對於Functional language的一切都是覺得很新鮮。
Learn You a Haskell for Great Good!看到中途，筆記一下一些新觀念。

List comprehension

跟數學裡面Set comprehension的表達方法很像，假設我們想要找出直角三角形中，周長小於50的三元組的數量。 (假設 a <= b <= c 且 a ^ 2 + b ^ 2 = c ^ 2)。

如果是以往的作法，大概會像這樣

1
2
3
4
5
6
7
8
9

for (int a = 1; a <= 10; a++)
#define sqr(x) (x * x)
typedef tuple<int, int, int> tuple3;
std::vector<tuple3> ans;
for (int a = 1; a <= 50; a++)   
        for (int b = a; b <= 50; b++)           
                for (int c = b; c <= 50; c++)                   
                        if ((sqr(a) + sqr(b) == sqr(c))  && ((a + b + c) < 50))
                                ans.push_back(make_tuple(a, b, c));

如果是Haskell會是這樣，不同的語言寫法會不一樣，不過這上面列的C++11實作方式還不如上面來的直覺。

1

let xs = [(a, b, c) | a <- [1..50], b <- [a..50], c <- [b..50], a ^ 2 + b ^ 2 == c ^ 2, a + b + c < 50]

Pattern Matching

這邊跟我們常知的Pattern Matching不太相同，

在C99之後，新增了一種初始化方法。可以方便的設定structure/arry的初始值。帶來了極大的靈活

在之前的時期，要初始化一個structure，只能用以下的方式。

1
2
3
4
5

typedef struct MyData {
    char *p;
    int v;
} MyData;
MyData a = { "name" , 10};

這種方式稱作Aggregate Initialization。
需要按照Type定義的方式來初始化，一旦我們修改MyData資料結構，所有用到MyData的初始化都需修改。
在C99之後，我們可以這樣做

1

MyData a = { .v = 10, .p = "name"};

這樣就可以用任何順序指定初始值了。
另一個常用的應用場合是Array，拿以下這段程式碼當範例。

1
2
3
4
5
6
7
8
9
10

enum {
    YAHOO = 0,
    GOOGLE,
    FACEBOOK
};
char *old_style_weburl[] = {
    "www.yahoo.com",        
    "www.google.com",       
    "www.facebook.com"  
};  

當我們將 FACEBOOK跟YAHOO的順序對換之後，old_style_weburl的對應關係也要跟著改變。

1
2
3
4
5

char *new_style_weburl[] = {
    [FACEBOOK] = "www.facebook.com",
    [YAHOO] = "www.yahoo.com",
    [GOOGLE] = "www.google.com"
};

這樣子不管enum裡的順序怎麼改變，new_style_weburl對應關係都能維持正確。
有興趣的可以參考Designated Initializers學到更多。

趁著Android 4.3的出現，記錄一下如何編譯一個Android環境。

首先，建立一個Android目錄。

1
2
3
4
5

$ mkdir Android && cd Android
$ mkdir bin && cd bin
$ curl https://dl-ssl.google.com/dl/googlesource/git-repo/repo > /repo
$ chmod a+x repo
$ cd ..

建立一個source的目錄存放程式碼。

1
2

$ mkdir source && cd source 
$ ../bin/repo init -u https://android.googlesource.com/platform/manifest -bandroid-4.3_r2.1

開始下載，時間很久，請耐心等待

1

$ ../bin/repo sync

建置環境

1
2
3

$ source build/envsetup.sh
$ lunch full-eng
$ make -j 4

完成之後執行開啟模擬器

1

$ emulator

如果又更多問題，可以參考官網的說明，建議在64 bits的Linux底下操作。

接續上個範例

我們將add2這個函數從demo中題取出來，建立一個math library，讓其他人使用。
提供header file跟library，header file放在include目錄底下，source code放在lib底下>
我們的header file： MyMath.h

1
2
3
4

#ifndef _MyMath_H_
#define _MyMath_H_
int add2(int, int);
#endif

實作add2.c

1
2

#include "MyMath.h"
int add2(int a, int b) { return a + b; }

重點的CMakeLists.txt部分

1

ADD_LIBRARY(mymath STATIC add2.c)

重新改寫我們的demo

1
2
3
4
5
6
7

#include <stdio.h>
#include "MyMath.h"
int main()
{
        printf("%d\n", add2(1, 1));
        return 0;
}

以及CMakeLists.txt

1
2

ADD_EXECUTABLE(demo demo.c)
TARGET_LINK_LIBRARIES(demo mymath)

目錄下的CMakeLists.txt也要跟著更新

1
2
3
4
5
6

PROJECT(CMakeDemo C)
cmake_minimum_required(VERSION 2.8)
SET(EXECUTABLE_OUTPUT_PATH ${PROJECT_SOURCE_DIR}/bin)
SET(LIBRARY_OUTPUT_PATH ${PROJECT_SOURCE_DIR}/bin)
INCLUDE_DIRECTORIES(${PROJECT_SOURCE_DIR}/include)
SUBDIRS(src lib)

在城市規模小的時候，直接寫Makefile是個比較快的解決方案，不過當規模更大，以及要跨平台的時候，CMake的優勢就出現了。

如何使用編譯參數

上面這個範例，我們是使用static library，我們假設要在編譯的時候選擇是要用static library或是shared library，該怎麼進行。

重新改寫 lib/CMakeLists.txt

1
2
3
4
5

if (ENABLE_SHAREDLIB)
ADD_LIBRARY(mymath SHARED add2.c)
else()
ADD_LIBRARY(mymath STATIC add2.c)
endif()

之後我們在產生Makefile之前下以下參數就能選擇了

1

$ cmake .. -DENABLE_SHAREDLIB=TRUE

這樣就能選擇編譯成shared librarry了。

從最簡單的範例開始

我們現在有個demo.c，裡面的程式碼如下。

1
2
3
4
5
6
7

#include <stdio.h>
int add2(int a, int b) { return a + b; }
int main()
{
	printf("%d\n", add2(1, 1));
	return 0;
}

所需要的CMakeLists.txt內容也很簡單。

1
2
3

PROJECT(CMakeDemo C)
cmake_minimum_required(VERSION 2.8)
ADD_EXECUTABLE(demo demo.c)

這樣還不如直接用gcc編譯來的快很多，不過事情總會越來越複雜。

向工業標準邁進一步

我們把執行檔放在bin，而把程式碼放到src下。
根目錄的CMakeLists.txt改成這樣。

1
2
3
4

PROJECT(CMakeDemo C)
cmake_minimum_required(VERSION 2.8)
SET(EXECUTABLE_OUTPUT_PATH ${PROJECT_SOURCE_DIR}/bin)
ADD_SUBDIRECTORY(src)

因為新增了最後一杭，所以在src底也要新增一個CMakeLists.txt。

1

ADD_EXECUTABLE(demo demo.c

這樣我們就能在bin底下看到demo了。

記錄一下在寫程式的時候，所使用過的工具 (不定其更新)

Windows

-小番茄 Visual Assist X
-Memory Leak Visual Leak Detector for Visual C++
-檔案合併和比對軟體 Araxis Merge
-Source Code 美化工具 Artistic Style
-CMake Tools for Visual Studio

Linux

• fasd
• 終端機程式： tilda for GNOME, Yakuake for KDE
• ack 加強版的grep

Mac

• Alcatraz XCode套件管理系統

最近看了Mixin之後，抒發一下自己的感想。
學過Software Engineering的，都知道DRY。如何共用程式碼就變成一門學問了。

假設我們現在有IA, IB, IC三個interface，然後有三個Concrete Class CA, CB, CC實作這三個介面
然後D, E兩個Class需要同時支援這三個interface，該怎麼做。

在C++這種支援Multiple Inheritance特性的語言，大概會是這個樣子。

1
2

class D : public CA, CB, CC {};
class E : public CA, CB, CC {};

如果CA, CB, CC的內容風馬牛不相及，這個解決方案不錯，不然的話，Diamond Problem是個很頭大的問題。

而Java等語言等只支持單一繼承，因此避掉了Diamond Problem，不過卻引來其他問題。
有兩種常見的問題，第一種是實作介面。

1
2

class D implements IA, IB, IC {};
class E implements IA, IB, IC {};

假設某個Class的實作方式需要修改，需要修改，那麼D跟E的內容都需要修改。如此一來就達不到DRY的精神了。
另一種是亂七八糟的繼承方式。

1
2
3
4
5
6
7

class PD1 extends CA {};												class PE1 extends CA {};
class PD2 extends CB {};												class PE2 extends CB {};
class PD3 extends CC {};												class PE3 extends CC {};
class PD4 extends PD1 {};												class PE4 extends PE1 {};
class PD5 extends PD2 {};												class PE5 extends PE2 {};
class PD6 extends PD3 {};												class PE6 extends PE3 {};
class D extends PD6 {};													class E extends Pe6 {}

雖然避掉的第一個問題，不過那眼花撩亂的繼承關係更麻煩了。

至於動態語言大行其道之後，Mixin提供另外一種思考模式。由於Duck Typing的支持，類與類之間沒有強烈的interface contract關係。以Ruby來說

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

module IA 
end
module IB
end
module IC
end
class D 
	include IA
  include IB
  include IC
end
class E
	include IA
  include IB
  include IC
end

mixin是一群method的集合，只要外在的class有滿足條件(Duck Typing)，這個方案可以滿足大部分的需求。

在StackOverFlow看到的一個範例。

1
2
3
4
5
6
7
8
9

struct Functor {
    template <typename T>
    void function() {}
    template <>
    void function<int>() {}
};
Functor functor;
functor.function<char>();
functor.function<int>();

同樣的code，在gcc和clang編譯失敗，不過VC可以，同樣根據StackOvewflow的說法，這是VC的一個非標準Extension。

要模擬這個方案，可以靠function overloading來做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

template <typename T>
struct DummyIdentity {
    typedef T type;
};
struct Functor {
    template <typename T>
    void function() {
        function(DummyIdentity<T>());
    }
private:
    template <typename T>
    void function(DummyIdentity<T>) {}
    void function(DummyIdentity<int>) {}
};