Snowmantw's Blog

Understand Y F = F ( Y F ); loose last remaining non-major friend.

Note: Seminar - a Comparison Study on Semantic Web Services and e-Business

| Comments

講者:大同大學系主任葉慶隆教授

  • ebXML - E-Business Standard
  • Web Services = WWW + XML ( in ebXML )
  • HTTP, HTML, URI 即是 WWW 的基礎,構成龐大的應用
  • XML technologies : Namespace, Schema, Transformation, Publishing, Query, Security
  • Web Service = SOAP, WSDL, UDDI: 後兩者是遠端服務呼叫的相關技術
  • 這些的問題都在於缺乏語意。XML 有清楚的文法,可是語意依然缺乏

  • ebXML 以 Web Services 做基礎,把商業程序與 IT 的職責切開,中間用介面互通
  • CPPA: 描述供應商與需求方的一堆程序與需求,即是可以提供的功能介面彼此協議
  • BPSS: 各參與角色的商業協同合作
  • Semantics Web Services Standard - WSMO 標準
  • RDF:類似關聯資料那種作法,表達關聯。而到了現代可以用 XML/HTML5 的語意功能把一個物事的關係放在文件裏面
  • Semantic Web: 現在是資料存在各種格式中,而經過映射轉換,變成比較抽象的格式,也就是 RDF ER 模型
  • 因為 RDF 的預設範圍是全球化的,因此可以很容易與其他檔案合起來協作
  • Semantics Web Services 指軟體用語意標籤,使得機械處理可以知道其所要的服務如何取得,也可以互相組裝成完整的服務
  • Choreography 是描述文件流的自動狀態機與規則語言

  • ebXML 與 WSMO 的標準關聯
  • 事實上 ebXML 所定義的 Core Components 都轉成 Semanitic 技術所可以處理的 Ontology 格式
  • CPPA – Goal || BPSS – Choreography || Abstract State Machine 可以描述各代理人參與者
  • 可以把 FSM 轉成 ASM 規則語言,類似一連串流程的語言
  • Rule-base ASM 可以取代 ebXML 的所謂 schema-based 、圖畫式的 BPMN 流程描述

  • 做這些最主要是要克服多量應用所產生格式,全球無法互通的問題,也很難在缺少語意的情況下做應用的發展
  • 關鍵字等非語意技術可以達到足夠的應用品質,在不需要的時候當然就夠了。可是重點是電腦可以更加的利用,而不像現在必須要人的介入
  • 服務的描述功能等比較抽象的規格,實際上與技術層面的函式呼叫等是有距離的

  • (私人感想):這類東西的辭彙都太多了…而且與實際的用途到底有沒有接起來
  • 我個人深切的希望這些過大與過度制式化的標準可以輕一點。讓那些有需要如此制式化的官僚與商業體系去運作他們的標準, 衝在前面的開拓者需要比較輕的工具,讓這一切用意良好的原石可以真正琢磨出價值。這種龐大的東西往往就像所謂玻璃鎚那樣(from “Better,Faster,Lighter Java”)。

Note: Computer Graphics #2

| Comments

OpenGL Programming 基本架構

座標系統詞彙

  • Clipping: 座標空間中所關注的立方區域,鏡頭唯一關注的區域
  • Viewpoint: 繪製的座標與視窗的座標映射。螢幕上的視窗系統透過 Viewpoint 提供了映射的方式
  • Project: 立體空間對視窗的投影
  • Mesh: Geometry

OpenGL 歷史

  • 繪圖的工業標準,軟硬體接軌的機制
  • 最初的版本是把硬體能作到的流程功能做成固定的功能,包括從頂點的立體物件資料,以及平面影像的像素資料, 作個別的修正後柵格化結合(頂點轉像素),最後處理到 Framebuffer
  • 第二版後把頂點轉換 (Vertex Shader) 與像素貼圖 (Fragment Shader) 程式化。之前只能設定狀態並丟給硬體作。程式化代表可以對這些過程的方式套用自己的方式, 不用一定按照預設的硬體方式作
  • 第三版引入了 Geometry Shader 。這個流程是位於 Vertex Shader 與 Fragment Shader 中間。另外則是開始有向後相容切割的概念, 即所謂 Full/Forward Compatible Context Type
  • 第四版於 Geometry Shader 前又引入兩個流程:Tessellation-Control, Tessellation-Evaluation 。前者是曲線中間可以增加點,因此更細分平滑。 從這邊看出 OpenGL 支援的越多,以前要放出去交給 CPU 運算的部份,就可以用 GPU 去算,增加效能
  • 幾何資料之後細化處理另一個好處是頂點資料可以相同數目,但效果更細緻,不會增加頻寬的需求
  • OpenGL - { OpenCL, WebGL, OpenGL ES }

OpenGL APIs

  • 針對每個 OS 與視窗系統的接軌
  • GLU 是比起硬體平台上更抽象的,GLUT 則是跨平台的 Toolkit
  • 命名慣例:gl 代表 OpenGL 提供的功能;glu 代表 GLU 提供
  • GL - GLU || OS/Window System - GLX,AGL,WGL :前者提供繪圖,後者提供輔助視窗必要的功能。GLUT 則是跨兩者
  • gl.h 一直維持在 OpenGL 1.1 ;因此額外功能需要用 glext.h 去增加。但因為硬體實做不一致,所以該函式庫要作手動連結等。而 glee.h 就是自動處理的函式庫
  • OpenGL 資料型別自訂浮點數等是因為要跨平台

GLUT and Application

  • 應用結構:主函式中的主迴圈,然後透過事件處理函式去作各功能
  • 應用中都用 GLUT 設定顯示模式(如 RGB)、建立視窗、顯示事件分派函式、鍵盤事件分派函式…最後是呼叫 GLUT 的主迴圈功能
  • GLUT 做好視窗的建立與模式後,還需要作 OpenGL 本身的設定。包括設定色彩深度與開啟對應狀態等
  • GLUT 的顯示分派函式是用函式指標註冊進 glutDisplayFunc 中。這部份當有顯示需求時就會被呼叫
  • glutSwapByffers: 前景與背景 Buffer 。後面畫完交換到前面用,也就是繪製與顯示是分開的,除非該 Buffer 被推到前面
  • 要繪製通常是先清除再顯示。因此在其他的函式中作繪圖,若是之後又執行到有清除的函式,就會沒有顯示效果
  • glFlush 是強制把繪圖指令都送出。因為 GPU/CPU 溝通上可能有同步的問題,可能 GPU 還沒畫完 CPU 就在執行下一步了。因此會用這個
  • glBeginglEnd 中間的各指令就是用來畫的繪製區間
  • glutIdleFunc 動畫時可用。因為若是沒有事件,就只有 Idle 事件
  • glutPostRedisplay 則是產生一個事件,注意 Post 。執行後,下次進入主事件迴圈時會有一個待處理的顯示事件,因此動畫就可以順著用顯示的函式處理

Elementary Rendering

幾何元件

  • OpenGL 有支援幾種基本幾何元件
  • 繪製時要注意頂點順序左下開始逆時針
  • glVertex3fv 為例,命名如下
    • gl: OpenGL 前綴
    • 3: 維度,影響有多少參數
    • f: 傳入資料型別
    • v: 有的話則是傳入陣列(Vector)
  • 新的寫法不再用 glBegin 等方式描述,而是使用 Buffer 相關的方式
  • Buffer 化的表示法是用一個叫做 Display List 的概念去存,然後繪圖的時候直接畫出來

  • 可以用一些函式作狀態與特色的設定、開閉等
  • OpenGL 座標以左下角作零點,所以滑鼠座標可能要反轉

遞迴範例:碎形

  • 以基本三角形的三邊中點作遞迴,做出的三角形繼續作遞迴

Note: Compiler Design #2

| Comments

原稿遺失,補記一些重點


  • Lexeme: 語法剖析的元素
  • 語法剖析出來的 Token 代表 key/value ,即是該 Lexeme 屬於那一類 Token ,其值為何
  • Identifier 就是一大類 Token 。而如 IntegerConstant 那樣,可能會有很多類中有很多種值
  • Keyword/Reserved Word 差異:前者有先定義但可重載;後者不可重載

  • Formal Language 就是研究這些 Lexeme 對應到的類別之間關係
  • 單字構成字串,字串符合文法者稱之句子。所有(有可能無限可數)句子構成語言
  • Formal Language 的規則確保所建構出來的語言,針對任意字串都是可決定其是否為句子的
  • Regexp 用以從文法建構出句子;而 Compiler 則是從句子辨認出文法

  • 自動狀態機分為確定與不確定。兩者的差異在於其中的狀態移轉,是否存在同輸入而多個可能移轉的狀態
  • 確定的版本,雖然可以允許有多個結束狀態,但一定要在輸入全部使用完畢時達到結束狀態,才算完成
  • 不確定者,其遇到輸入有多個可能移轉時,要「執行」全部可能的移轉。而只要其中一個到達結束狀態時輸入也剛好完畢,就算成功
  • 前者所述,如果其中一個移轉到達結束狀態,但輸入還未完畢,其他可移轉者要繼續移轉

Note: Seminar - Location Service Protocols for Vehicular Ad Hoc Networks Abstract

| Comments

演講人:世新大學 許智順教授

  • 車載通訊網路的研究
  • MANET, VANET, VANET+Coast Location Service Protocols
  • MANET 是比較早出現的。與 VANET 不太一樣
  • Location Service 是指知道別人位置並以知通訊
  • 基本的車子需要有各種感測器,然後把這些感測器的訊息連接到處理中心,再與伺服器連結
  • Ad Hoc Network :車載隨意網路,包括車間通訊與 Roadside 基地台。放在道路旁邊,負責與網際網路作通訊
  • 也可以在距離過遠時,以車間通訊作中介,間接的連上Roadside 基地台
  • V2V, V2R 就是這兩種網路。OBU 是車載單元,RSU 是基地台單元

  • 一個重點是支援智慧型的運輸系統

  • GPCR 在知道目的地時,使用貪婪策略往一個個最靠近之節點作一步步導航往前。這問題是有可能有突出的分岔節點造成有一部份是要往回走,浪費該分枝
  • GPSR 因此是先到交叉點,然後在交叉點再做決策
  • Geocast 是指把訊息送到特定區域。這邊有像網路那種 Unicast, Boardcast。只是 Geocast 加上了地理區域的概念。現在是要傳給該區域中的所以節點
  • 例如可以將事故位置的資訊傳給在附近位置的車輛

  • MANET 的協定介紹

  • GLS 是把地理區域化成小方格,小格又成大格,因此 Location Server 會去以「比該小格 Id 大,又離其最近的小格中 Sever 作為挑選」
  • 對該大格以外的其他格,就只要一大格選一個 Location Server ,該使用者就可以以遠近決定減少或增加使用的 Location Server 密度
  • 如果都以小格為單位,這樣一個使用者使用的 Location Server 過多,更新資料時成本過大
  • 每個 Location Server 都會有目前知道位置資訊的節點。每一個 Location Server 會往外查詢直到取得了想要取得的資訊

  • 另一種是超級節點概念:車節點中有些是超級節點,因此以線為準,線中間的超級節點負責其周圍所有的通訊與資訊更新。如果其中子節點有必要與其他節點作溝通, 就可以透過這樣的線圖作網路線方式的傳遞

  • HLLS:歷史資訊為準。如果要傳訊息到某個目的地,節點會以初始狀況為基準,紀錄其經過路線,往其路線上剛好有的節點做成傳送路線

  • HLS:階層概念,做成六腳蜂格網路。然後以階層為主一層層往上往外傳。只要該網格中有點,該點就會被臨時挑出作為中介點。這樣每一層區域擴大,點每層只有一個。 但這樣每個節點都必須知道其他節點的更新情況。而詢問訊息相反,是從自己開始往最高層一路降下去傳到基本網格,才到節點

  • VANET 與 MANET 差別在於,前者是車輛,後者大部分是行人(Mobile Device)。VANET 維持連線方面更困難,但車輛會以道路形狀為主,所以比較規則

  • VNAET 協定介紹

  • VLS 是學之前 GLS 一樣切網格。網格現在會增加是否有道路的資訊,即是以該格內的道路中選一點作為該格中 Locaton Server 的調整位置
  • 這邊所謂 Location Server 是以車節點為主,因此有無道路很重要

  • Cache-Based 的則利用各時間點 T-delta 與零點位置的差異作資訊擴散。也就是隨著移動,大致會知道其附近資訊的車輛節點,這會逐漸形成擴散的圖。 也就是每個節點會按照移動時更新周圍節點,而隨著方向相反的節點資訊比較舊,移動前方向的資訊比較新,形成有方向差異的節點群,因此資訊的發送就會逐漸逼近目標。找到後建立了 Routing

  • RLSMP:一樣把區域切成不同格,各格構成叢集。叢集中間則是該叢集中的節點位置資訊。要知道資訊時,則向該區域中間的節點 LSC 詢問,更新也一起往中間送

  • Location Server 面對著密度與成本的背反。因此需要找到一個最有效率的方式佈署 Location Server

  • 假設在程式中,每個車輛都有導航與傳訊的能力,會先切成方格,然後也有階層
  • 差異在於 Locatin Server 分成 Local Location Server 與 Dedicated Location Server 。前者會是目前所在位置的 Location Server ,因此節點可以就近詢問
  • Dedicated Location Server 則是按照區域分群,選定該區域節點應該被哪個 Location Server 服務
  • 所以分群的概念也是很重要的
  • 而還可以以 Cost Functions 計算,看要分多少群,以及要有多少台 Location Server
  • 透過 Local/Dedicated Location Server 作道路為主的 MST 計算就可以找到通訊路線

  • 更新資訊的時間是很重要的:計算更新與不更新,何者成本高,因此歷史資訊會很重要

  • 也就是預估未知與實際位置不準的差異
  • 最主要就是提出了 Cost 為主的考量,在 Update 方面勝過既有的方案,但 Query 比較不如
  • 另外就是以現代的條件,有如此模組的車輛可能不夠形成可用的網路

Note: Cmake Learning #1

| Comments


  • 如果要尋找系統中有沒有特定函式庫,首先要確定有該函式庫的模組。可用 cmake --help-module-list 協助尋找是否該模組存在
  • 如果有該模組,可以用 find_package 命令去找。注意該命令給定的名字必須符合前述搜尋模組給的名字,而不是系統中套件名稱。例如
     # Find GLUT package in system. 
     # Not system package name like "freeglut3-dev".
     find_package (GLUT REQUIRED) 
  • 如果要作不符合條件即中斷 Cmake 執行,可以使用 message(FATAL_ERROR "<message>") 的方式印出錯誤後中止執行。 例如前述尋找系統套件,找不到就可以用這種方式報錯離開

  • target_link_library 是該 Cmake 所針對的編譯單元,需要連結哪些函式庫
  • add_library 則是把該編譯單元包成函式庫,兩者目的相關方向相反
  • target_link_library 可以指定編譯器連結參數,例如
     # Require compiler compiling with these arguments.
     target_link_libraries(CGHW1 -lGL -lglut -lGLU)
  • 這邊的連結參數會影響產生的 Makefile 中所下參數,所以是必要的
  • include_directory 是指定該次編譯尋找引入檔的目錄路徑(不知道非 C 類是否適用這概念?)
  • add_subdirectory 則是指定要遞回進子目錄,先作該 CMake 再回來
  • 有些屬性要自己隨著目錄結構而設定,例如 IMPORTED_LOCATION 就關係到產生函式庫後擺放檔案的位置

  • Cmake 2.8 還是需要在 else 這個關鍵字後面接上條件的樣子。不能如前面那樣省略,而是必需變成 else(<condition>)
  • 推薦使用所謂 “Out-of-source Build” ,將建置目錄與原始碼目錄分開
  • Cmake 執行時指定目錄,會自動找尋其中是否有 CMakeLists.txt 並利用執行
  • Cmake 範例的結構中,看起來是每個模組或其他編譯單元的目錄中都各有一個 CMakeLists.txt ,整個專案再一個。 例如「Cmake 入門」中的範例:
    lib1/
        src/
            app/
                CMakeLists.txt
                main.c
            calc/
                CMakeLists.txt
                calc.c
                calc.h
    CMakeLists.txt

Note: Yesod Web Framework #1

| Comments

Foundation.hs

  • Foundation.hs 提供載入資源,以及變成內部資源參照值的函式。
  • 該檔案中有分為 Route 、基本核心、儲存機制、認證等界面可以自訂,以此定義出應用本身所需要的各資源模組
  • Route 是呼叫特定函式,載入 Route 檔案並建立出 AppRoute
  • 基本核心包括 Session 後端組件、如何渲染頁面 Widget 、Static 檔案設定等
  • Widget 應該說是子頁面,最終要併到 default-layout-wrapper 這種 Wrapper 的樣板檔中
  • RenderMessage 是用來把一些預設訊息渲染出來,包括處理 i18n 之類議題的設定 Type Class

Application.hs

  • 此檔案將建立整個應用
  • Handler 也是註冊在這邊。Cabal 檔裡也要記得增加
  • 其中 makeFoundation 與 makeApplication 將會分別建立資源參照與 WAI 應用,而後者會相依前者。
  • makeApplication 另外還會被 main 函式所直接呼叫
  • mkYesodDispatch 會建立應用實體,是繼 mkYesodData 所建立好資料後,繼續接手的程式。這個函式也是實際上會建立 YesodSite 的函式。
  • 從目前看到的只能說 mkYesodDispatch 建立網站本身,makeApplication 建立整個 WAI 應用。( WAI: Web Server 與 Application 的介面^1 )

Note: Computer Graphics #1

| Comments

  • Shading 是指在面與線的基礎上增加了光線與材質的交互作用層
  • Texture 則是加在表面呈現出材質的效果
  • Framebuffer 記憶體將儲存運算後的資料,然後顯示器朝之要這些資料並畫出來
  • Framebuffer 如何更新是重點之一
  • Model-Rendering-Animation 是三個領域
  • Pixel 對記憶體就是位元組。比如 4 Bytes 對應到 32 萬色的一個像素
  • 如果沒有 Shading ,每個面都會同色同光。加上去後才有光影立體的感覺
  • Shadow 與 Reflection 則是後面的工作

  • Rendering Pipline :平行處理
  • 轉換觀點:Transformation ,去以相機為準變換整個影像
  • Transformer –> Clipper –> Projector –> Rasterizer –> Pixels
  • Transformer 是幾何轉換
  • Clipper 把不在視覺中的物體遮掉不顯示
  • Rasterizer 從幾何轉換成像素觀點(從平面頂點變為描述哪些像素要被填滿)
  • Shading 還在後面。不過為了效率,會在過程中作

  • Global Illumination :全環境中的光線軌跡。包括散射之類的議題。
  • 物理光學以外,還有一種是繪圖風格的渲染方式

  • 課程會把 OpenGL 核心功能實做一次
  • 根據老師的提醒,OpenGL 矩陣存到記憶體順序是 Column Major 。代表順序是從左上開始往下數,最後面是最右下。因此
    M[16] == {0,1,2,3,4,5,6,7}

    [ 0  4
      1  5
      2  6
      3  7 ]

FWD: I Feel Sorry for Computer Science Departments

| Comments

這篇文章講述了作者 Mark Engelberg 覺得目前 (美國?) 的 CS 教育,遠不夠讓一個人從四年的大學教育去專精於 CS 領域。

重點摘錄:CS 教育應該要從大學以前就開始,因為四年遠不夠讓人專精於 CS 領域。尤其是大學以前的數學教育, 都強調於微積分相關的學習,這應該要被扭轉成教導離散數學為重心。另外也要提供學生及早開始接觸 programming 的機會。

Colleges have 4 years to try to instill some meaningful level of 
expertise in students, but that's simply not enough time.

這個問題對 CS 系所來講是嚴肅的抉擇問題:到底課程要專注在我們認為一個 CS 人應該有修為這個遠景上, 還是教學專注在職業會用到的技能上?

... do we focus on foundational skills and the big picture of 
what computer science is all about, or do we focus on technical training to 
try to produce graduates who have skills with immediate appeal to companies? 

作者還提到公司為何會對學校失望:他們希望雇用的是剛好可以勝任該職務技能的人。但因為這個目標無法達成, 所以它們轉找最「聰明」的人,也就是可以最快上手的人。但對 CS 這門學科而言,類似於學位這樣的指標也很難切合這樣的要求。 雖然畢業名校這點,對於它們想要尋找有天賦之人比較有幫助。

More often than not, the knowledge gained from a CS education is 
viewed by companies as being so insufficient as to be almost irrelevant – nevertheless, 
graduating from a well-known school can be seen as a kind of proxy for the kind of 
drive and innate smarts they really are looking for.

作者又講到其他系所應該也會有這類問題。但在這點上, CS 到底有何不同?作者認為最關鍵的一點在於 其他學科的知識多少從小學就開始接觸,但 CS 所要學習的卻缺席於大學以前的教育中。

How do other departments solve this problem? 

Well, many domains are able to leverage the significant number of years
that students have already invested in grade school in English, math, and science.

以數學為例,很不幸的是,作者認為 CS 最重要的是離散數學,但這卻與大學以前的教育方針相反。 作者還提到學習微積分其實與 CS 最迫切需要的數學是最無關的科目。而對大學以前的教育卻往往強調在微積分相關的學習上。

Calculus, the pinnacle of grade school math education as it is currently structured, 
is the least relevant type of math for computer scientists. 

Computer scientists need a strong background in Discrete Math and these topics are poorly 
covered in grade school, if at all.

同時在作者心中,即使在教育很好的地區,對於讓學生提早接觸 programming 的機會也是非常貧乏的

... most places probably have it much worse in terms of providing 
kids with early exposure to programming.

要解決這個問題,很明顯的,只有提供更長遠的解決方式。這包括延長大學的畢業年限,或是相反, 讓程式設計相關的課程提早深入大學以下的學制中。

Once the problem has been laid bare like this – four years provides insufficient 
preparation for a career in computer science – it is obvious that there are only 
a couple long-term solutions.

One possibility is to extend the duration of CS education, 
another possibility is to incorporate more CS topics and exposure to 
programming into the grade school curriculum.

作者也提到為何要迫切提高程式設計的專精度:他認為程式設計將是社會上很重要的一種基礎技能,提高整體程式水平將可以使社會受益

I think a strong case can be made that our society would benefit from more CS in grade school

並且在 TED 大會上,另一位人士也提到了提高離散數學的重要性

Arthur Benjamin makes the case in his TED talk that discrete math (logic, statistics, etc.) 
is far more relevant to most walks of life than, say, calculus.

不過作者最後講了,即使我們都做到了這點,另一個更難的問題:尋找更多夠格的老師,要怎樣解決?

... how do you go about finding and recruiting qualified teachers? 

我想對於老是喊著資訊國力之類的政府,應該要抉擇:軟體產業需要更多的投入與堅持。 也許我們應該減少專注於,或說實在一點是排擠於大學、高中課程中非程式軟體相關的科目。 除非我們學制也要開始建構真正的技術類學習,分於普通學習之途。

然而更重要的應該是並認清硬體方式的生產有其極限, 而軟體產業可能是未來一大重點。然而軟體產業絕非如硬體那樣砸錢砸人數,以及其他資本就可以搞定。 畢竟大規模的「擴產」對軟體而言可能反是阻力。加上軟體的開發牽涉到台灣企業與政府最缺乏的耐心與人本思維, 要成熟可能是忍受虧損或無收入一段長時間後才能看到成果。 且對軟體設計者不能像硬體那樣靠著工業製造甚至軍隊的管理方式對待。

這些種種可能都是習慣於生產製造思維的政府與工業會被迫殘酷的轉型,或是殘酷的死亡之絆腳石。

Reading: Applying Hardware Testing Concepts to Software

| Comments

這篇文章講述作者 Dodgy_Coder 自己測試 GUI 程式的經驗, 他覺得軟體的測試在時間長度的概念上可以借鑒硬體的測試概念分三種時間相關的測試概念

  1. 短:功能性測試,包括 Unit Testing 與 Integration Testing。這邊可以除去絕大部分的問題。
  2. 中:用來測試與減少隨機錯誤。隨機錯誤不太可能完全清除,但可以儘量減少、消除到機率合乎標準
  3. 長:將軟體執行到超乎一般時間的長,用來測試諸如記憶體洩漏、效能下降等問題。

作者自己的經驗是他的程式一般只會開半小時,他故意開著兩個小時作測試, 然後在第一個小時時就發現了記憶體洩漏與效能下降的問題,並修正之。

其他概念可以上作者文章看;他那張引自 wikipedia 的圖還蠻好的

Bathub curve about testing