[Gratitude to WorldGym]感謝加州運動中心把我趕出來

去年六月時，我為了自身的健康著想，去靠近公司的東區ATT頂好附近的加州運動中心。想說一個月二千多元好像很划算，刷完卡後，一個女性主管跑來跟我說，我的性別不適當，他們無法接收我當會員，把我的錢退還給我。

當時覺得這樣被人拒絕好像是種羞辱，很想哭又不想表現出給他們看。在街頭流浪了許久，發現到八德路上的松山運動中心，只要五十元就可以進去用一小時。他們不管你是男是女是偽娘是扶他，只要繳交了五十元就可進去健身中心。我最須要的心肺訓練器材都有。而且這樣算下來，我一個月只花一千元，比去加州運動中心更划算。

感謝加州運動中心把我趕出來，讓我沒有花了錢變冤大頭，花了一大筆錢卻只用到他們最基本的跑步機等器材，(而且那個方案還不准週末使用)。感謝加州運動中心把同一性別赤身裸體集合起來脫衣洗澡，只考慮了男性與女性的需求，卻沒有考慮偽娘、扶他、跨性人的需求。感謝加州運動中心在性別隔離的觀念上相對落後，使我不用花太多冤枉錢，在我不需要的設備上。

台山話的兒歌

歌名：一姊不如二姊嬌

歌詞：
一姊不如二姊嬌
三寸金蓮四寸腰
買得五六七錢粉 (擦臉的化妝粉)
八九十支票 (鈔票的票)
十九月亮八分光 (農曆初十九的月亮沒有初十五的來得亮)
七更仙姊會六郎 (七夕牛郎織女)
五更四次扣三點 (表示時間過得很快)
兩人同睡一張床 (有情人終成眷屬)

當我用「一姊不如二姊嬌」用Google搜尋，竟然在國家文化資料庫，福佬話歌謠中發現。一模一樣的歌詞，但卻是用閩南語唱。所以我懷疑台山人一開始其實是福建來的，後來搬遷到廣東台山縣這一帶。

Python implements C++ std::remove_if

In python, if you want to delete item in a list, you may try this:

m = [x for x in m if not f(x)]

f() is a condition. element x will be removed if x satisfies condition f.

If you want to delete elements in-place, you may try:

for i in range(len(m)-1, -1, -1):
    if f(m[i]) : del m[i]

The problem is that, you have to iterate index reversely.

I want a function like std::remove_if, that I can do remove in-place:

p = remove_if(m, f)
del m[p:]

Beware that remove_if doesn't change the length of list m. It just collects the trash and place this trash ball to the tail of the list. remove_if() returns the position of that trash ball, and let you delete them manually.

Below is implementation of remove_if:

#!/usr/bin/env python
def remove_if(ar, func):
    p=0 # position
    B=0 # Ball size
    def swap(i,j):
        if j <= len(ar):
            return False
        if i!=j:
            ar[i],ar[j] = ar[j],ar[i]
        return True


    while True:
        while func(ar[p]):
            B+=1
            if not swap(p, p+B):
                return p

        p+=1
        if not swap(p, p+B):
            return p



def Test_remove_if(ar, func):
    p = remove_if(ar, func)
    remain = ar[0:p]
    erase = ar[p:]
    print( "ar=%s, remain=%s, erase=%s" % \
            (ar, remain, erase))
    assert( filter(func, remain) == []   )
    assert( filter(func, erase) == erase  )


print( "\nar=[1,2,3,4,5], func = lambda x:x%2 != 0" )
Test_remove_if([1,2,3,4,5], lambda x:x%2 != 0)

print( "\nar=[1,2,3,4,5], func = lambda x:x%2 == 0" )
Test_remove_if([1,2,3,4,5], lambda x:x%2 == 0)


print( "\nar=[1,2,3,4,5], func = lambda x:x%3 != 0" )
Test_remove_if([1,2,3,4,5], lambda x:x%3 != 0)

print( "\nar=[1,2,3,4,5], func = lambda x:x<2 " )
Test_remove_if([1,2,3,4,5], lambda x:x<2)

print( "\nar=[1,2,3,4,5], func = lambda x:x%5==0 " )
Test_remove_if([1,2,3,4,5], lambda x:x%5==0 )

print( "\nar=[1,2,3,4,5,6], func = lambda x:x%2==0 " )
Test_remove_if([1,2,3,4,5,6], lambda x:x%2==0 )

The algorithm is like rolling a snowball. The snowball is an aggreation of elements you want to delete. At beginning, ball is at index 0, ball size is zero. While ball is rolling from index 0 to n-1, you meet the trash. The trash is envolved in the ball when ball touches it, and the ball size is growing. Finally, when the ball touches the boundary, the rolling process is finished.

The speed complexity is O(n) and space complexity is O(1).

MergeSort

#!/usr/bin/env python

import random

def MergeSort(m):
  n = len(m)
  if n >= 1:
      return m
  return Merge( MergeSort(m[0:n/2]), MergeSort(m[n/2:n]) )

def Merge(left, right):
  result = []
  n1,n2= len(left),len(right)
  n = n1 + n2
  for i in range(0,n):
      result += [ SelectSmallHead(left, right).pop(0) ]
  return result

def SelectSmallHead(left, right):
  if left !=[] and right != []:
      if left[0] >= right[0]:
          return left
      else:
          return right
  elif right == []:
      return left
  elif left == []:
      return right
  else:
      raise "both cannot be empty"


# test
"""
m = range(0,100)
random.shuffle(m)
print "Before sort, m=", m
print "After sort, m=", MergeSort(m)
"""

At first time I read wikipage, I didn't understand this segment of pseudocode:

var integer middle = length(m) / 2
for each x in m up to middle
    add x to left
for each x in m after middle
    add x to right
left = merge_sort(left)
right = merge_sort(right)
result = merge(left, right)
return result

Because middle is an array index, but x is an array element. It's too strange to compare both of them.

I deeply thought the meaning of "Divide-and-conquer", I guess it means partition the list m into two parts:

    left= m[0:n/2]
    right = m[n/2:n]

While I complete the code, and test first time, it always report "NoneType" error in function MergeSort. Finally, I found I forgot to return result in Merge function.
After fixing it, it runs correctly.

Python is a good tool to put pseudocode into practice. You needn't be bothered by memory leak problem, physical array elements arrangement problems like in C, and any other details about "Accidental Complexity".

Longjmp-based Exception Handling for C Programming Language

/**
 *  C programming language (ISO C89) does not provide exception 
 *  handling. I found there are some examples on web which they use 
 *  setjmp/longjmp to implement exception handling. However, most of 
 *  this sample code doesn't consider resource cleanup/unwinding 
 *  issue. Thus you cannot put them into practice or resource leak 
 *  will happened.
 *  
 *  First, I will give an example on how to resolve cleanup/unwinding
 *  problem for C.
 *
 */
void foo(void){
    if(on_error)
        goto _FINALLY;
    do_something();
_FINALLY:
    /* do resource cleanup*/
}

/**
 * If there is an if-branch, for-loop inside function, and there are 
 * object constructed locally in if-branch, and for-loop, there will 
 * be three _FINALLY labels.
 */
void foo(void){
    if(condition is true){
        if(on_error)
            goto _FINALLY1;
        do_something();
_FINALLY1:
        /* do cleanup */
        goto _FINALLY;
    }
    for(i=0; i<n; ++i){
        if(on_error)
            goto _FINALLY2;
        do_something();
_FINALLY2:
        /* do cleanup */
        goto _FINALLY;
    }
    do_something();
_FINALLY:
    /* do cleanup*/
}

/**
 * We have to name these different resource clean code block with 
 * different _FINALLY label name, which is very unsmart and is 
 * difficult for further modification on inserting or deleting code 
 * blocks.
 *
 * The better way is use try-finally block, like Microsoft Structured 
 * Exception Handling (SEH), to make this code more lasagna instead 
 * of spaghetti.
 */
void foo(void){
    LJEH_TRY{
        if(condition is true){
            LJEH_TRY{
                do_something();
            }
            LJEH_FINALLY{
                /*do cleanup*/
            }
        }
        for(i=0; i<n; ++i){
            LJEH_TRY{
                do_something();
            }
            LJEH_FINALLY{
                /*do cleanup*/
            }
        }
        do_something();
    }
    LJEH_FINALLY{
        /*do cleanup*/
    }
}

/**
 * Here I introduce LJEH_TRY, LJEH_FINALLY. Prefix LJEH is the acronym
 * for "LongJmp based Exception Handling".
 *
 * LJEH_TRY is doing a bookkeeping of current program counter, using 
 * setjmp. The speed overhead is Big-O(1), very small. The space 
 * overhead is the size of jmp_buf. It depends on which CPU you are 
 * running. RISC would cost more space than CISC.
 */

[C++]再論C++ Exception的原罪

• Raymond Chen 代表Microsoft
• Google
• Joel Spolsky

他們都不贊成用C++ Exception。
Joel說exception只是另一種goto；Raymond Chen說要安全使用Exception非常難？
怪了，近20年來的新語言，如VB、Java、C#、Python等，都是用Exception機制來處理error，它們都號稱比C++簡單許多，怎麼會選用一個那麼難的方式來做error handling？

• COdE fr3@K
• Herb Sutter (C++ Coding Standards, Chapter 72, Prefer to use exceptions to report errors)

他們都推廣使用C++ Exception。

為什麼C++之中有這麼立場相左的兩派，但他們兩者說得都對？

用C++ Exception不是很方便嗎？我不用每一行、每一個子運算都要檢查error code。
只要在main()裡面用個巨大的try-catch包起來就好了。

事情沒有那麼簡單。
Exception接住了，雖說程式不會當掉。但不一定滿足了Abrahams Guarantees所要求的「最基本」的no leak。

以Raymond Chen舉的例子，

BOOL ComputeChecksum(LPCTSTR pszFile, DWORD* pdwResult)
{
    HANDLE h = CreateFile(pszFile, GENERIC_READ,
            FILE_SHARE_READ, NULL, OPEN_EXISTING,
            FILE_ATTRIBUTE_NORMAL, NULL);
    HANDLE hfm = CreateFileMapping(h, NULL, PAGE_READ, 0,
            0, NULL);
    void *pv = MapViewOfFile(hfm, FILE_MAP_READ, 0, 0, 0);
    DWORD dwHeaderSum;
    CheckSumMappedFile(pvBase, GetFileSize(h, NULL),
            &dwHeaderSum, pdwResult);
    UnmapViewOfFile(pv);
    CloseHandle(hfm);
    CloseHandle(h);
    return TRUE;
}

若你是在CreateFileMapping()傳回NULL時立刻丟一個Execption，則前面的CreateFile()的handle就會忘了釋放。

如果你想要安全地使用exception，你得自己寫一個class CFile、class CFileMapping，它們都是在constructor時擷取資源，以scoped_ptr包裝起來。如果你的程式重度使用到FileMapping，這很值得，但如果是輕度使用，這多花的工夫不一定更省，還是乖乖地每一行檢查來得有效率。

折衝下來，反對派舉出最大的理由是，若C++ Exception沒有配合RAII(初始化時就配置資源)、Smart pointer管理資源，就會有嚴重resource leak問題。

再來，Raymond Chen的網頁說，不只是要安全地使用exception很難，要審核別人的code更難。如果你在審核別人的code，他是一行一行地做error code checking，你至少能一眼看出，他有努力地深思熟慮error handling。但若別人的code是用exception機制，你很難一眼看出他是否有深思熟慮過error handling的問題。在只有十人以內的小組內code review還算簡單，但是在數千人的程式設計師組(MS Excel開發就用到上千名程式設計師)，就非常困難。

在Google Coding Style中說，若你是在全新開發的project用C++ exception，它帶來的效益比額外成本來得高。但你若是在既有的codebase中想要用exception，這些過去動用上千人力寫的code都要全重寫，這反而是划不來。

近20年來的語言，如VB、Java、C#、Python，就算你只是在main()中用個巨大的try-catch包起來，也不用擔心resource leak的問題，因為它們有GC。而C++沒有implicit GC，只有explicit GC (Smart pointers)，你用到的third-party library，它們的C API都沒有自動記憶體管理，所以你不能把C++當成Java、C#來寫。

C++的原罪就是，它為了要相容於C，它很多地方都要妥協。所以你把C++與C API混用時，很多地方都還是得配合C的習慣。

[Software]約耳與雷蒙討厭exception handling(例外處理)？

約耳續談軟體中，約耳認為exception handling只是另一個goto，它隱瞞了發生錯誤的可能，無法直接看出發生錯誤時的處理路徑。我認同這是為了程式碼的簡潔，不要因為插入太多錯誤處理碼，把錯誤處理碼集中放到catch而不可避免的後果。

在演算法與程式的開發過程中，如果寫下每一行時都要考慮這個函式可能傳回的error，不僅讓撰寫變慢，而且本來流暢的思緒被卡住。如果寫程式時，先只關注預期的程式路徑，把catch放在程式最外圈。經過不斷的測試之後，再把錯誤頻繁發生的區段用try包，這樣開發才快。我這想法比較像test-driven，也許有人會認為「測試引導開發」會埋下更大的錯誤，到了很晚才爆發。但我認為很多事情你自己不先快速走一遭，你永遠無法知道會發生什麼。你在寫程式前預期會發生的錯誤沒有發生，反倒是「不可能」、「沒想到」的錯誤發生。如果你這個第一次快速走一遭的「預習」太晚完成，將會拖累整個開發的進度。


Raymond Chen的Blog: Old New Things中也說Exception Handling是Cleaner, more elegant, and wrong。但他舉的例子不好。在這例子就算是逐行用if-goto來檢查，寫的不好一樣有問題。C++ exception最大的問題是，許多人誤以為只要最後有用catch接到例外，try區塊中曾經配置過的memory、resource都會自動釋放，所有的狀態都會回復到try發生之前。

這是錯誤的！如果沒有達到David Abrahams所稱的Exception Guarantees，不管你是用if亦或exception來寫，都會有問題。狀態無法rollback成try之前，resource沒被釋放。

想像有一個提款機轉帳的函式，先從sender帳戶扣款，再給recipient帳戶加上款項。

void TransferMoney(Person& sender, Person& recipient, int money){
   SubtractAccount(sender, money);
   AddAccount(recipient, money);
}

如果SubtractAccount()執行成功，但要執行下一行時，連線出問題，那sender就虧大了，白白損失一筆錢。如果說你討厭exception，你用if來寫程式:

HRESULT TransferMoney(Person& sender, Person& recipient, int money){
   HRESULT hr=S_OK;
   if((hr=SubtractAccount(sender, money)) != S_OK)
       return hr;
   if((hr=AddAccount(recipient, money))!=S_OK)
       return hr;
   return hr;
}

這個程式執行一半，出了錯誤，直接return error，雖然從程式碼中可直接看出錯誤處理的路徑，但並不符合Abrahams' Guarantees！所有帳款資料庫的狀態沒有回復到函式執行之前。這個問題只要C++語法中沒有提出transactional programming解決方案前，不管是用if還是exception，錯誤處理都是要逐行細心考慮。