2019年12月14日 星期六

用 Qt Graphics 做一個顯示座標的工具 - 細節調整

其實這篇才是我寫文的主因,前面兩篇其實都是前言(欸),總之就是我埋頭自幹 AZ 大大吃一頓飯就寫得出來的工具,結果過程中寫得亂七八糟,有時候該出現的東西就是不出現測到頭很痛,或是測一測就進無窮迴圈後來發現是自己蠢,發了 v0.1 之後被靠北顯示怎麼這麼醜,想改又很難搜不到解法QQ。
當然最後還是搜到了,但就希望可以多寫一篇文,讓這些解法更容易被搜到,如果運氣很好真的幫到人也算功德一件,如果你真的被幫到的話,麻煩幫我這篇文章留下一個 like 然後順手按下旁邊的訂閱和小鈴鐺(醒醒這裡是 blogger 不是 youtube。

畫上座標線:

這算是一個附加功能,一般的顯示工具只要設定 Scene 的 background brush,設定一個黑色的 brush,就能畫出黑色背景了。
但如果我們要更精細的話,就要去實作 scene 或是 view 的 drawBackground 函式:
void drawBackground(QPainter *painter, const QRectF &rect)

下面是我實作的程式碼節錄,有幾個可以注意的地方:
  1. Qt 的座標系統左上角是 0,0,往右往下是 x 遞增跟 y 遞增,所以用 top 的值會比 bottom 小。
  2. 這個函式參數是一個 QPainter 跟一個 QRectF,painter 好理解就是目前作畫的對象,在這個 painter 上面作畫就會畫在背景上;QRectF 一般會認為就是現在顯示背景的矩形,不過不對,它是「現在要更新背景的範圍的矩形」。
    例如我現在顯示的 Scene 大小是 -50,-50 ~ 50, 50,但我實作滑鼠可以在 scene 上面拉一個選取的小框框,在我拉框框的時候,Qt 會判定只有這個小框框裡面的背景是需要重畫的,QRectF 就會設定到這個小框框上;其實某種程度來看這樣也對,而且更節省重畫的資源。
  3. 承上點,所以有抓到現在 scene 的大小要怎麼辦?這也是我為什麼選擇是實作 View 的 drawBackground 而不是 Scene 的,因為我可以透過 mapToScene(viewport()->rect()).boundingRect() 取得這個 View 現在顯示 Scene 的大小。
後來就是一些數學計算,在對應的座標點上呼叫 drawPoint 了,下面的 code 我有略為刪節過了,要用的話不要全抄。
void
MyViewer::drawBackground(QPainter *painter, const QRectF &rect) {
  qreal left         = rect.left();
  qreal right      = rect.right();
  qreal top         = rect.top();
  qreal bottom = rect.bottom();

  QRectF sceneRect = mapToScene(viewport()->rect()).boundingRect();
  qreal size = qMax(sceneRect.width(), sceneRect.height());
  qreal step = qPow(10, qFloor(log10(size/4)));

  qreal snap_l = qFloor(left / step) * step;
  qreal snap_r = qFloor(right / step) * step;
  qreal snap_b = qFloor(bottom / step) * step;
  qreal snap_t = qFloor(top / step) * step; 

  // print coordinate point
  for (qreal x = snap_l; x <= snap_r; x += step) {
    for (qreal y = snap_t; y <= snap_b; y += step) {
      painter->drawPoint(x, y);
    }
  }

  // print coordinate line
  painter->drawLine(qFloor(left), 0, qCeil(right), 0);
  painter->drawLine(0, qCeil(bottom), 0, qFloor(top));
  QGraphicsView::drawBackground(painter, rect);
}

不動物件:

第一個是所謂的不動物件,也就是 QGraphicsItem 透過設定了 ItemIgnoresTransformations flag,這樣這個 item 就不會受到 view 視角變化的影響。

使用情境也很單純,像是在畫面上打個 marker 或是寫上文字,如果視窗縮小就看不到就奇怪了,所以這個 marker 就要設定這個 flag,放大縮小都會顯示一樣。
改變也就是呼叫一下
setFlag(QGraphicsItem::ItemIgnoresTransformations, true);
就可以了。

要注意的是在設定了這個 flag 之後,在這個 item 裡面的位移似乎會失去效果(還是行為會變很怪,我有點忘了),一般要在一個位置例如 100, 100 畫一個正方形,我們可以用 QGraphicsRectItem,在 100, 100 的地方畫正方形;如果是 ignore transformation 的物件,我是變成在 0,0 的位置畫一個正方形,然後把物件的位置用 setPos 設定在 100, 100。
這部分當初真的弄超久,後來覺得這樣不行,把放在 dropbox 裡面的 <c++ GUI Programming With Qt 4> 拿出來翻翻,沒想到在第八章 Qt graphics 章節就講了要怎麼寫類似的東西,還有範例 code ,果然寫程式還是要多看書而不是瞎攪和,弄了好一陣子的東西其實書上的範例都寫了。

填充物:

上一篇文的最後一張圖,應該很明顯可以看到,我用 brush 填進去的東西,非常的…不均勻,一格一格的非常醜,實際運作的 code 也是,只要放大縮小填充物的就會變得不連續。
這是因為 QBrush 在填東西的時候,用固定密度在填充,不會隨著螢幕的放大縮小改變填充物的密度,要修成也只需要一行,在 paint 函式裡面加上這個:
QBrush m_brush;
m_brush.setTransform(QTransform(painter->worldTransform().inverted()));
painter->setBrush(m_brush)
把現在場景的變形反轉補償回去就可以了;這個解答出自 Stack Overflow

隨放大縮小調整長度:

同樣的是另一張圖的箭頭,在放大縮小的時候,箭頭的部分會跟著放大縮小,這是我們不想要的,因為縮太小的時候箭頭會看不到,這時候就要用到我們上篇提到的 QStyleOptionGraphicsItem,在 paint 函式裡面,可以用這個東西從 painter 的 transform 裡取得 level of detail (LOD):
qreal qScale = option->levelOfDetailFromTransform(painter->worldTransform());
qreal len = 10 / qScale;
qScale 就是目前放大值,可以用它調整我們要畫的長度 len;這個解答出自 Heresy's Space

下面列一下參考書目:
  • C++ GUI Programming With Qt 4
  • Game Programming using Qt 5 Beginner's Guide: Create amazing games with Qt 5, C++, and Qt Quick

2019年12月11日 星期三

用 Qt Graphics 做一個顯示座標的工具 - 客製化元件

上一篇我們介紹了 Scene, View, Item 的關係,這篇就來客製化一下,畢竟 Qt 的元件沒客製化功能都非常受限,預設行為幾乎什麼都沒有,這時候就是好好重溫 C++ 最美妙功能––繼承的時候了。
首先是 Scene 跟 View,都用繼承的方式建一個自己的 class,才能在裡面實作各種信號跟插槽,設計上 Scene 是 View 的 data member,View 上面接到什麼東西直接 pass 給 Scene,實作就不一一介紹,下面是一個簡單的修改列表,因為是內部用的工具就沒辦法把程式碼貼上來給大家笑了

View實作事件:

  • keyPressEvent:客製化按鍵盤的行為。
  • wheelEvent:連接到放大縮小的函式。


View實作插槽:

  • clearScene:清空畫面
  • addItem:接收讀進來的物件,往下直接呼叫 Scene 的 addItem。
  • zoomToAll 跟 zoomRect:放大縮小。


Scene 實作事件:

  • mousePressEvent/mouseMoveEvent/mouseReleaseEvent:定義滑鼠行為。


Scene 實作信號:

  • rectSelected:滑鼠事件會發出這個信號,通知 View 跟 MainWindow。
  • mouseClick:同樣用來通知 MainWindow 使用者點在哪裡。


當然我們也要客製化自己的 QGraphicsItem,當然如果要顯示的東西沒太多特別要求,只靠 Qt 提供的那些 QGraphicsXXXItem 也是 OK 的。
我記得在實作時候也有考慮過是不是繼承 QAbstractGraphicsShapeItem 就好,後來好像因為什麼原因,還是繼承 QGraphicsItem。

照著 Qt 的說明文件,要實作自己的 QGraphicsItem,重點在打造兩個函式:
QRectF boundingRect() const override
這個函式要回傳一個 QRectF,標示這個 Item 的大概位置,讓 Scene 能用它作分類跟檢索,如果設錯的話就有可能變成 item 明明在某個位置視窗卻打死不顯示它,因為 Scene 在檢索的時候就不認為這個 Item 有需要顯示。
void paint(
  QPainter *painter,
  const QStyleOptionGraphicsItem *option,
  QWidget *widget) override
Paint 就是操作 Painter 裡面的函式盡情的作畫,不過我自己是省得麻煩,都是創一個 QPainterPath 然後呼叫 Painter 的 drawPath,這樣比較簡單。
舉例來說我自己實作的一個物件是在視窗上面標上一個箭頭然後顯示文字,大略來說程式碼就是這樣:
QPainterPath path;
path.moveTo(0, 0);
path.lineTo(0, 8);
path.lineTo(5.656, 5.656);
path.closeSubpath();
path.lineTo(7.65, 18.48); // len 20, tilt 22.5
path.setFillRule(Qt::WindingFill);
QFont serif("Helvetica", 12);
path.addText(QPoint(0, 0), serif, m_text);
paint 裡再用 drawPath 把這條 path 畫出來就可以了。

Paint 的另外兩個參數 QStyleOptionGraphicsItem 和 QWidget,前者帶著顯示上要用的參數,在下篇做一些細部設定的時候會用到;後者則指向目前繪圖中的物件,通常可以不用管它,我也還不確定什麼時候會用到它。
這次實作全面採用 C++ 的新關鍵字 override,個人認為真的好用,像是上面的 boundingRect 如果沒寫 const 的話其實是在實作不同的函式,加了 override 編譯器就會跳錯誤,比較不會犯這種不容易注意到的錯。

實作 QGraphicsItem 以我們的應用這樣就夠了,如果還需要更精細的管理,可以再實作函式:
QPainterPath shape() const
這個函式用來檢查碰撞、滑鼠有沒有點在物件上等等,不實作預設就是以 boundingRect 代替。

自己幹完 QGraphicsItem 之後,整個程式也有了個樣子了,繼承自 QGraphicsItem 的物件可以直接用 addItem 塞進 Scene 裡面,下面截兩張運作起來的樣子,分別是顯示箭頭跟一個三角形的多邊形:



還有很多細部設定沒做所以看起來會有一點粗糙,下一篇預定就是要講這些細部的東西。

2019年12月5日 星期四

用 Qt Graphics 做一個顯示座標的工具

故事是這樣的,平常小弟在公司處理的東西多半是一些 polygon, line 之類的資料,除錯的時候總不能看著 gdb 印出來的 x, y 座標 debug,所以公司同仁有自幹一套 debug 的工具幫忙把這些資料畫出來;不過呢…這套工具好像在記憶體模型那邊有點問題,資料量大的時候會變超慢;畫圖是直接 call xlib,每次放大縮小都要重畫所有物件,對記憶體的負擔又更嚴重。只要 polygon 數量突破幾萬個的時候,一次的 refresh 就會花上好幾秒。

前陣子手上暫時沒其他緊急的事情,乾脆就用 Qt Graphics 重寫一個,不準在留言問我為什麼不用 nodejs 寫,MaDer 公司的工作站就沒有 nodejs。
完工後自己試了一陣發現幾十萬個物件的時候放大縮小都超流暢,不愧是 Qt Graphics,雖然程式行數比我預期的多了些,但架構比本來的東西清楚很多。
其實過程中一直參考強者我同學 AZ 大大的 QCamber,覺得 AZ大大實在太過神猛狂強溫,5-6 年前就寫得出這麼複雜的 project,我一直覺得我寫 code 的時候的整體感很不夠,都是在單一 class 裡面塗塗抹抹,小地方會動可是大架構沒辦法在一開始就訂好,後續要修改的成本就非常高。 Anyway 總之它現有個樣子了,我覺得中間碰過一些實作的問題值得記錄一下,預計可能寫個三篇左右吧。

----

首先圖形顯示的部分,使用的是 Qt 的 graphics framework,可以用來繪製大量的 2D 物件,支援選取、縮放等等,我們這裡只是要顯示而已,也不用搞得這麼複雜。
Graphics framework 裡的三個基本元件就是:
  • QGraphicsScene:場景,可以把它想成一塊巨大的畫布,可以在上面自由放上各種 item,Scene 會幫你管理物件的顯示和更新,個人經驗 Scene 負擔到 10 萬個元件左右還很流暢,上到百萬個的時候就會有點頓了(又或者是我把所有 item 都放在 scene 裡面的關係)。
  • QGraphicsItem:物件,可以想像成畫素描的時候放的那些石膏,在一個場景上擺上東西,Qt 有提供基本的幾種物件:橢圓 QGraphicsEllipseItem、路徑 QGraphicsPathItem、多邊形 QGraphicsPolygonItem、矩形 QGraphicsRectItem跟文字 QGraphicsSimpleTextItem。
  • QGraphicsView:View 是唯一可以在 Qt 的 MainWindow 畫面上出現的物件,可以把 View 想成一台相機,場景 Scene 是不動的,相機從各種角度自由取景,並把取到的景顯示出來,如果取景的尺寸比畫面還要大,跟其他的物件一樣, View 能自動出現捲軸,也可以接收畫面上的滑鼠、鍵盤事件。
只用 Qt 原生的 QGraphicsScene, QGraphicsView, QGraphicsItem 只能組出最基本的顯示工具,變化量非常少,以下就示範一個最基本的設定:
#include <QApplication>
#include <QGraphicsView>
#include <QGraphicsScene>
#include <QGraphicsRectItem>

int main(int argc, char *argv[]) {
  QApplication app(argc, argv);
  QGraphicsScene *scene = new QGraphicsScene;
  scene->setSceneRect(0, 0, 400, 400);
  scene->addItem(new QGraphicsRectItem(50, 50, 150, 100));

  QGraphicsView *view = new QGraphicsView;
  view->setScene(scene);
  view->show();

  return app.exec();
}
編譯執行就可以看到這個畫面:

反正這個設計只是一開始建來試驗用的,看一下顯示的效果,很快下一篇就會被我們拆掉了。

2019年11月16日 星期六

把一顆樹寫出來是會有多難

故事是這樣子的,之前小弟發下豪語想用 Rust PEG 寫一個 C Parser,然後…就沒有然後了。好啦當然不是,不然就不會有這篇文了。
總之最近經過一陣猛烈的攪動之後,我的 parser 能處理的文法終於接近當年在學校修 compiler 的時候所要求的 B language 了,說來慚愧,當年寫 compiler 作業的時候 parser 只是裡面一個作業,要在 2-3 週裡面寫完的,結果現在搞半天寫不出個毛,果然上班跟上學還是不一樣,在學校可以全心全意投入寫 code ,週末的時候還可以熬個夜把作業寫出來;現在上班白天要改公司的 code ,晚上回家累個半死不想寫 code 只想開卡車(欸。

本篇講到的程式碼目前還沒推到遠端上,相關的程式碼可以參考:
AST 的資料結構:cast
型別的資料結構:ctype
既然現在可以處理比較複雜的文法了,再來要做什麼?想說就像作業的要求一樣,把我們處理好的 AST 用 graphviz 寫出去,是會有多難?

整個 dump graphviz 的進入點是一個函式,接收要倒出來的 AST 跟一個 out,out 的型別是 std::io::Write 的 dyn Write,這樣不管你是要寫到 stdout, stderr 還是寫到檔案都能傳進來,介面會是一樣的,函式的實作當然就是直接了當的把該印的東西都寫出去;另外實作一個 dump_node 幫我們把寫出一個 node 給獨立出來,id 會自動不斷累加,讓 node 的編號不會重複。
fn dump_graphviz(ast: CastTop, out: &mut dyn Write) {
    writeln!(out, "Digraph AST").unwrap();
    writeln!(out, "{{").unwrap();
    writeln!(out, "label = \"AST_Graph.gv\"").unwrap();
    writeln!(out, "node{} [label = \"PROGRAM_NODE\"]", 0).unwrap();
    ast.make_node(out, &mut 0);
    writeln!(out, "}}").unwrap();
}
fn dump_node(out: &mut dyn Write, id: &mut u32, label: &str) {
    *id += 1;
    writeln!(out, "node{} [label = \"{}\"]", id, label).unwrap();
}
另外我們要實作的是 make_node,這裡很自然的就是先宣告一個 trait,AST 裡面所有的物件都要實作這個 trait ,就都有 make_node 可以用了。
trait ToGraphviz {
  fn make_node(&self, out: &mut dyn Write, id: &mut u32);
}

impl ToGraphviz for CastTop {
  fn make_node(&self, out: &mut dyn Write, id: &mut u32) {
    match self {
      CastTop::FuncDeclList(v) => {
        let cur_id = *id;
        for decl in v {
          dump_node(out, id, "DECLARATION_NODE FUNCTION_DECL");
          decl.make_node(out, id);
        }
        if *id != cur_id { // new node
          writeln!(out, "node{} -> node{} [style = bold]", cur_id, cur_id + 1).unwrap();
        }
      },
    }
  }
}

impl ToGraphviz for FuncDecl {
  fn make_node(&self, out: &mut dyn Write, id: &mut u32) {
    let parent = *id;
    dump_node(out, id, &format!("IDENTIFIER_NODE {} NORMAL_ID", "int"));
    dump_node(out, id, &format!("IDENTIFIER_NODE {} NORMAL_ID", self.fun_name));
    dump_node(out, id, "PARAM_LIST_NODE");
    dump_node(out, id, "BLOCK_NODE");

    for i in parent..*id {
      writeln!(out, "node{} -> node{} [style = {}]",
          i, i+1, if i == parent {"bold"} else {"dashed"}).unwrap();
    }
  }
}
* :本來的作業要求連結第一個 child 的必須是實線,其他的用虛線,這裡沿用
這個實作的問題顯而易見,我們的輸出的實作跟資料綁死了,所以每個 node 裡面的實作都是大費周章,而且 code 很醜。
我們要更抽象化一點,其實輸出樹的邏輯是這樣子的:先寫 child 的 node,然後是自己,回傳自己的 id 給 parent,這樣上一層的人才能畫 edge 出來。
我們實作一個 dump_children 的函式,這個函式會用現在的 id 印出現在的 parent,然後把它跟所有傳進來的 children 畫線連起來:
fn dump_children(out: &mut dyn Write, id: &mut u32, label: &str, children: &[u32]) -> u32 {
  writeln!(out, "node{} [label = \"{}\"]", id, label).unwrap();
  let mut prev = *id;
  for child in children {
    writeln!(out, "node{} -> node{} [style = {}]", prev, child,
        if prev == *id { "bold" } else { "dashed" }).unwrap();
    prev = *child;
  }
  *id+=1;
  *id-1
}
因為 Rust 函式參數沒有預設值也沒有 overload,為了方便我們可以創一個 dump_nochild 的函式,這樣比較方便:
fn dump_nochild(out: &mut dyn Write, id: &mut u32, label: &str) -> u32 {
  dump_children(out, id, label, &[])
}
現在 make_node 的實作都可以用 dump_children 或 dump_nochild 實作,先對自己的 child 們呼叫 make_node,把回傳值(也就是 child 們印完的 root)收集起來再用 dump_children 印出去就行了:
impl ToGraphviz for CastTop {
  fn make_node(&self, out: &mut dyn Write, id: &mut u32) -> u32 {
    match self {
      CastTop::FuncDeclList(v) => {
        let children : Vec<_> = v.iter().map(|n| n.make_node(out, id)).collect();
        dump_children(out, id, "PROGRAM_NODE", &children);
      },
    }
    *id
  }
}

impl ToGraphviz for FuncDecl {
  fn make_node(&self, out: &mut dyn Write, id: &mut u32) -> u32 {
    let children = [
      dump_nochild(out, id, "IDENTIFIER_NODE int NORMAL_ID"),
      dump_nochild(out, id, &format!("IDENTIFIER_NODE {} NORMAL_ID", self.fun_name)),
      dump_nochild(out, id, "PARAM_LIST_NODE"),
      dump_nochild(out, id, "BLOCK_NODE")];
    dump_children(out, id, "DECLARATION_NODE FUNCTION_DECL", &children)
  }
}
這樣看起來就好多了,不過我們還能更進一步,仔細觀察上面的 dump_children 的話,就會發現我們還能用 fold 的方式改寫:
// print node, and link with all children
fn dump_children(out: &mut dyn Write, id: &mut u32, label: &str, children: &[u32]) -> u32 {
  *id+=1;
  writeln!(out, "node{} [label = \"{}\"]", id, label).unwrap();
  children.iter().fold(*id, |mut prev, child| {
      writeln!(out, "node{} -> node{} [style = {}]", prev, child,
          if prev == *id { "bold" } else { "dashed" }).unwrap();
      prev = *child;
      prev});
  *id
}
老實說,每次我費了這麼大的工夫,把一堆本來很黃很暴力的 code 改簡單,變成最後那樣的很純很 Functional 的 code,我都會在內心懷疑個 100 遍,費這麼大功夫是真的有比較快嗎?當然在維護上可能會好一點,但 Rust compiler 能保證抽象化真的是零成本的嗎?這可能是值得好好討論的議題。

每個函式都要帶著 out 跟 id 走,很不方便,用一個 struct 把它們裝起來:
struct DumpGraphviz {
  out: Box<dyn Write>,
  id: u32
}
dump_children 跟 dump_nochild 變成 DumpGraphviz 的實作,介面變成:
fn dump_children(&mut self, label: &str, children: &[u32]) -> u32
fn dump_nochild(&mut self, label: &str) -> u32
make_node 的介面則是:
fn make_node(&self, visit: &mut DumpGraphviz) -> u32
整體就變得清爽多了。
天底下沒有新鮮事,其實我就是在實作 visitor pattern,只是還沒把 visitor 整個抽出來讓不同的 visitor 可以在這上面實作。最後輸出的成品長這個樣子:

我有個小小的體悟,就是寫程式不要妄想一步登天,除非如強者我同學 AZ 大大那樣一眼就把超大程式的架構都畫出來,而且實作起來都不會亂掉。
我上一次的實作就是衝太快,翻著 C standard 想要一開始就照著 C standard 實作,然後文法寫得亂七八糟反而連簡單的文法都會大噴射無法處理;與其如此,不如先支援基本的功能,等 parser 跟文法處理都完善之後再慢慢把其他功能加上去。
我覺得用蓋房子比喻的話,寫大程式要像西敏寺那樣的大教堂一樣,先從一個功能完整的小教堂開始,然後把小部分拆掉蓋個更大更豪華的(有看過一個動畫片在演示這個過程的,只不過沒有公開版);如果一次就想蓋個超大的教堂,最後可能弄成一團廢墟,連禮拜的功能都沒有。

2019年11月4日 星期一

從 Coscup 小談 Rust

這篇其實有點拖稿,畢竟 COSCUP 都是幾個月前的事了;這次在 COSCUP 投稿了 Rust 議程軌,覺得可以來說說對 Rust 的一點感想。Rust 從問世、正式發佈到現在也差不多要 7 年,感覺近年來有愈來愈紅的趨勢,一種社群上面看一看發現大家都用過 Rust 的感覺。

今年的 COSCUP 專門開了一個 Rust 議程軌,而且感覺議程的內容正在提升,不再是一堆語言介紹,有更多的是在介紹用 Rust 實作的資料庫、web assembly 、類神經網路的應用,可以預見 Rust 正在走出推廣階段,前往實際應用的領域。
不過我們還是要回來問,Rust 在哪裡會有<十倍生產力>?也就是在哪裡可以把東西做得比其他語言十倍好,像是要推人工智慧大家就會推 Python;要寫高效能的網路可能會用 golang,有哪個領域是非用 Rust 不可的嗎?現在有些風聲是區塊鏈的合約和交易語言,但我對這塊應用的大小有點存疑。

Rust 天生尷尬在它的定位上,它的目標是一個安全高效的系統程式語言,它也的確有潛力做到這點,但整體看來 Rust 可能是幾大系統程式語言裡數一數二複雜的,可能只輸給 C++,配上最新加上去的 Async 可能差不多就比肩了(欸。
確實 Rust 從源頭來看,受到大量函數式語言和語法的啟發,語法上看得出核心來自一個優異的語言團隊並吸收了各類語言的優點;編譯時進行的所有權確認和以 mod 為編譯單位,雖然讓 Rust 編譯慢得像烏龜,卻也大量消除程式在執行時出錯的機會,或者因為設計師<忘記>而導致的問題。
Rust 不可能是一款早期的語言,它浪費太多運算資源在編譯檢查,在 C 語言發跡的年代不會浪費資源去做那些檢查,換來的就是 Rust 編譯器數一數二的 GY 程度,這個不行那個也不行,搞得寫 code 的人跟編譯器都很累……。

我認為 Rust 要走的會是一條很艱難的道路,Rust 內建的複雜性天生就拒絕了一些簡單的應用,用 Rust 寫起來太過繁瑣了,動態語言能搞定的網路服務開發速度是第一,程式設計師上手的速度還有開發的速度來看,沒理由不用動態語言;而一些偏底層的應用,特別是對從 C/C++ 來的人來說,Rust 根本就不可理喻,明明我用 C 系列一下就可以搞定的,誰跟你在那邊 4 種 String 還有一堆 Option 要處理?一眼看穿的程式實在用不上 Rust,有人覺得 Rust 可以在嵌入式系統上挑戰 C,我看再過 100 年都不太可能。
Rust 的優勢,要來到所謂的大型系統程式才會出現,透過編譯器的強制,把一些難以檢測到的記憶體問題給挑出來,當然用 C++20 的一些特性可以做到一樣的效果,但沒有編譯的強制只靠設計師所受的教育,在大型系統下畢竟不是一個妥當的做法,畢竟設計師也是人,不可能不犯錯,或者偷懶或者忘記,一不小心就引入 C++ 的舊語法 -- 那些為了向後相容絕對不會移除的部分。

但問題就在於:大型系統幾不太可能整個重寫,更別提底層所依賴的都是經過千錘百鍊的 C/C++ 函式庫,像 Mozilla 那樣決定把瀏覽器核心整個抽換掉真的是神經勇敢,市面上的大公司哪幾家做過一樣的事?
可以預期 Rust 幾年之內,都會是用滲透的方式慢慢進到各大公司的系統當中,也許是一個新實作的子系統或是重寫某些小部分,用 FFI binding 的方式和既有的系統銜接,但要成為主流我看還要努力一段時間才行。

其實我是覺得語言比語言氣死人,不過 Rust 對 go 一直是一個大家很有興趣的話題(雖然說兩個根本是完全不同的東西),我個人滿推薦 LoWeiHang 翻譯的這篇文章

2019年9月8日 星期日

從 C 呼叫 Lua 函式

故事是這樣子的,小弟在公司裡面,主要是負責維護一個沒人在用的產品,遠觀來說這個產品滿複雜的,內建兩種不同的演算法實作,為的是要應對不同的狀況,有些狀況用第一種演算法比較快,有些用第二種。
那故事是這樣子的,我們的程式裡面有一個函式會在每筆資料結束之後,用上筆資料的結果來判斷下一次要選哪個演算法,問題是這個函式目前是直接寫在整個引擎的 C code 裡面,於是如果想要改變一下判斷的標準……sorry 重新 build,雖然公司弄了套分散編譯可以編很快但還是要幾分鐘。
上星期自己試了一下,成功把 Lua 編到公司的 code 裡面,就能把判斷邏輯寫在 Lua script 裡面,要改判斷標準只要改 Lua 就可以了;我一般聽到會這樣用的是遊戲公司,因為遊戲一樣涉及大量的邏輯判斷,例如血要扣多少之類的,而遊戲又會大量的去變動這些參數,使得彈性變得非常重要,總不能要改參數就把整個遊戲引擎全部重建構一次……說是這麼說我也不曾證實哪家公司真的這麼做就是,如果我的讀者真的是這樣搞的麻煩留個言讓我知道一下。

總之自己試過之後其實非常簡單,難怪大家都說 Lua 最厲害的就是嵌入到 C 程式當 Sup 角 ,我主要是參考這個網頁(看來是舊金山大學 CS 的課程頁面);下載 Lua 就從官網下載即可,哪一版應該是無所謂,或者是 Linux 的話安裝開發套件也 OK。
不愧是以輕量著稱的腳本語言,連 Makefile 看起來都是手寫的,直接下 Make 讓它編譯完成,雖然說我在這步被環境變數 TARGET_VAR 卡了很久,makefile 不知道為什麼自己把它加到編譯參數裡了。
再來做下面幾件事就能呼叫 Lua 函式了:

1. 引入 Lua 的標頭檔:

#include "lua.h"
#include "lualib.h"
#include "lauxlib.h"
然後在編譯的時候記得給一下 lua 標頭檔的位置,以及在連結的時候 -llua。

2. 生成 Lua state:

Lua 的 state 包含核心的函式,後面所有的函式都會需要這個 state;在 open 和 close 中間就能呼叫 Lua 函式了:
lua_State* L = luaL_newstate();
luaL_openlibs(L);
// write lua_call ... code here
lua_close(L);

3. 載入檔案,呼叫函式:

使用 luaL_dofile 打開 lua 檔案,等於是呼叫 lua 直譯器執行這個檔案,如果有直接執行的東西這時候就會有效果,像是 print("hello world") ,我們這裡只是定義變數 "add" 對應到相加的函式。
要呼叫 lua 函式,我們以函式 add 為例:
-- add.lua add function
add = function(a, b)
  return 42
end
那麼在 C 裡面就是:
luaL_dofile(L, "add.lua");
lua_getglobal(L, "add");
lua_pushnumber(L, a);
lua_pushnumber(L, b);
lua_call(L, 2, 1);  // 2 parameter, 1 return value
int sum = (int)lua_tointeger(L, -1);
lua_pop(L, 1)
簡單來說就是先用 lua_getglobal 拿到存在 global 裡面的函式 add(在 luaL_dofile 的時候建立的);把參數推到堆疊上;執行 lua_call,指定兩個參數跟一個回傳值,取出回傳值,把回傳值彈出堆疊。
如果函式有多個回傳值的話,會依序放在堆疊的 -1, -2 … 上;lua_pop 也要彈出更多值;Lua 的有一系列的函式來把東西推到堆疊上/彈出堆疊,簡單的應用,通常就是 lua_pushinteger/lua_tointeger, lua_pushnumber/lua_tonumber 來推/彈整數跟浮點數到堆疊上,詳情請參考文件

這裡只記錄最基礎的應用,實際上應該還有更複雜的應用,例如我要做決策的參數如果很多的時候該怎麼辦?或者其實我想要直接推一個 struct 進到 lua 是可以的嗎?
這兩個問題我目前都沒有答案,還有待研究,目前只知道 luajit 這個看起來好像停擺的專案有提供類似的東西,可以準備好 C 的 struct 來吃。
如果有大大們有答案的話麻煩教一下小弟,小弟現在很需要。

2019年9月4日 星期三

Rust 裡面那些 String 們

故事是這樣子的,最近把小弟自幹的編譯器加上 rust 的 llvm wrapper llvm-sys,經過一陣猛烈的攪動之後,自幹的編譯器終於可以 dump LLVM IR 了,雖然只會輸出一個空殼子…但有第一步總是好的。
不過小弟在綁定的時候遇到一個大問題,也就是 Rust 裡面的 String,到底怎麼會有這麼多種,因為寫的時候一直沒搞清楚,然後就會被編譯器噴上一臉的錯誤,覺得痛苦,於是決定來打篇整理文。
簡單來說,Rust 的 std 有四種 String,每個 String 都有動態記憶體模式跟沒有 size 資訊(不是 Sized)的靜態模式,他們是:
std::string::String <-> std::str
std::ffi:OsString <-> std::ffi::OsStr
std::path::PathBuf <-> std::path::Path
std::ffi::CString <-> std::ffi::CStr
還有一個比較少用,只能表示 ascii 128 字元組成的字串的 std::ascii::asciiExt,這裡就不介紹了。

一般的程式語言在數字型態通常都很固定,Rust 就很明確的分為 i8, i16, i32, i64 …,就偏偏字串是個大坑,因為從 ASCII 到 unicode,字串實在有太多分岐,儘管有 unicode 也不是到處適用。Rust 從設計上一開始就直接採用 utf-8 作為設計標準,原生的 String/str 就是 utf 8 字串。
可是呢,並不是所有作業系統都玩 utf8 這套,因此 Rust 有另一個使用 wtf8 的 OsString,wtf8 跟 utf8 的差異在於 wtf8 算是<格式比較差>的 utf8,會出現一些 utf8 不允許的位元組,偏偏規格沒有要求一定要完美格式,造成 windows 或 javascript 有時會出現這種格式不良的 wtf8 字串,因此 OsString ,跟專門用來表示路徑的 PathBuf 就是使用 wtf8。
有關 wtf8 請參考:https://simonsapin.github.io/wtf-8/

上面的字串都是在型態中記錄字串長度,結尾不會有 \0 字元,CString 則是最傳統的 null-terminated 字串,在呼叫 C 函式的時候,一定要用 CString 傳遞才行。
順帶一提,一般寫在 code 裡面的 let hello = "hello world" 的型態是 &'static str:生命週期為 static 的靜態字串。

知道了以上幾個區別之後,就來看看要怎麼使用它們:
String 最簡單,裡面一定要是 utf8,產生就是從 static str 產生,或者是 new 之後慢慢 push 進去:
let hello : String = String::from("hello");
let mut world : String = String::new();
world.push_str("world");
world.push('!');
OsString 是類似的,但只能從 String 轉過來(注意 String 的所有權會轉給 OsString),或者一樣 new 之後 push String 進去:
use std::ffi::{OsString, OsStr};
let oshello : OsString = OsString::from(hello);
let mut world : OsString = OsString::new();
world.push("world!");
PathBuf 其實就想成 OsString 就好,兩者也可以互相用 from 轉換:
use std::path::{PathBuf, Path};
let p1 : PathBuf = PathBuf::from(oshello)
let mut p2 = PathBuf::new();
p2.push("/dev");
上面說了,OsString 跟 PathBuf 用的是 wtf8,是 utf8 的超集,因此一般只能單向從 String 到 OsString,反向是不行的,呼叫 OsString::into_string() 得到的是 Result<String, OsString>,也就是有可能會轉失敗;或者就是用 into_lossy_string 把編碼不完整的地方變成 U+FFFD,utf8 的 replacement character。
PathBuf 則是沒有 into_string 可以用,只能先轉換成 OsString 再轉過去,我也不知道為什麼 core team 要這樣設計。

剩下的就是函式了,很有趣的是 String, OsString, PathBuf 都是動態容器,操作內容都要轉換到 str, OsStr, Path 上面去:
str 有操作字串用的 split_whitespace, starts_with 等等
OsStr 沒有任何特殊的函式XD。
Path 有很多對路徑的操作:is_absolute, parent, with_extension 等等,很多函式操作後都會得到 Path 或是 OsStr 讓你做接下來的操作。

CString 比較棘手一點,它要在 new 的時候代入 Vec<u8> (或者有實作 Into<Vec<u8>> 的型態)來建立 CString,new 會自動在後面加上 \0 ,因此這個 Vec 裡面不應該有 \0。
其實我覺得把 CString 想得 Vec<u8> 的另一種型態就好了,它本身也提供 into_bytes, as_bytes 等函式轉換成 Vec<u8> 的型態。
如果要從 String 跟 OsString 轉換過來的話,String 要用 as_bytes() 轉成 Vec<u8>,OsString 因為 unix 跟 windows 會有不同的 OsString 實作,不一定都能轉成 Vec<u8>,在 unix 要引入 std::os::unix::ffi::OsStrExt 就可以將 OsString 用 as_bytes() 轉成 Vec<u8>;Windows 則建議轉成 String 再轉成 bytes ,請參考這個網址

用上了 CString,最重要的就是要交給外部的 C 函式去用,要用 as_ptr() 取出字串部分的 pointer,得到的就是 * u8 了,有必要的話再加上 as *const i8 轉型一下。
例如我要呼叫這個函式:
LLVMPrintModuleToFile (LLVMModuleRef M, const char *Filename, char **ErrorMessage)
這個函式,我的檔案名稱是一個 OsString:
use std::ffi::{CString, CStr};
use std::os::unix::ffi::OsStrExt;
llvm::core::LLVMPrintModuleToFile(
           self.module,
            path.as_bytes().as_ptr() as *const i8,
            ptr::null_mut());
看了這麼多,簡單整理一下大概是這樣:

老實說每次只要在 Rust 裡面弄到 Path 都會弄到懷疑人生……

2019年8月28日 星期三

十年一覺 N1 夢

故事是這樣子的,8/27 剛公佈 2019 年第一次日文檢定的成績,經過了三次不合格之後,這次通過 N1 ,天氣好不用再散步可以跑步啦(什麼。


先來個有圖有真相:
配個歷年成績,一開始真的是慘不忍睹……:
2016/12:語言知識 23/60  讀解 32/60  聽解 22/60   77/180   Not Passed
2017/07:語言知識 26/60  讀解 33/60  聽解 30/60   89/180   Not Passed
2017/12:語言知識 36/60  讀解 32/60  聽解 31/60   99/180   Not Passed
2019/07:語言知識 38/60  讀解 58/60  聽解 33/60  129/180  Passed

上次就已經來到只差一分合格,理應再準備一下就可以過關,但認真應考還是太累,年初工作剛到任還在適應中,決定一口氣延一年半到今年 7 月,還很幸運的在台灣大學新的大樓應考(不過新教室有一點問題,之後再說),這次總算通過啦。
這次的準備沒有特別久,如果我沒記錯的話應該是四月初開始認真準備,不過真要說的話其實是沒多認真啦…,我覺得投的時間比之前考前都還要少,下面會提一下各區塊的準備方式,有些可能會有業配嫌疑,不過我保證沒有,反正這個小 blog 跟現在工作做的產品都沒人在意(欸:
  • 語彙、閱讀
語彙跟閱讀這次是放在一起……沒有準備,這次是從閱讀下手,在上班通勤時間陸續看了utsuki 給我的<哪啊哪啊~神去村>,還有許久以前從 BookOff 搬回來都沒看的<嫌疑犯X的獻身>,兩本都是看過中文再看日文,避免日文看不懂的狀況,一開始的單字量會比較大一點,看多頁之後就會比較順,還會發現一些作者愛用字,像是神去村作者很喜歡用うなずく;題庫只有寫一本<全攻略新日本語能力試驗N1讀解問題集>,這本我覺得題型跟真的考試的 correlation 有點大。

以這次的結果論,閱讀我覺得是有效的(我現在反而超好奇我是錯了哪題www),至少不合格的三次閱讀題寫得滿抖的,趕在最後一分鐘的時間寫完;相對的這次閱讀題看得滿順,寫完還剩 40 分鐘,我還一度以為 N1 是不是變簡單了,還回去推敲了文法排序的幾題(以結果來看效果沒有很好就是);單字的話可能效果不如預期,畢竟言語知識分數沒往上,但文法有被評為 A,所以很可能是單字被扣。
言語字彙年輕的時候可以用 anki 之類的背單字軟體,不過我是覺得老了之後有點用不起來,一直盯手機太累了,還不如輕鬆看小說,然後買個迷你記事本把不會的單字記下來,在走路的時候拿出來複習。
  • 文法
文法在自我學習上是用之前用過的兩本:<TRY!日本語能力試驗從文法掌握N2> 跟 <TRY!日本語能力試驗從文法掌握N1>,這兩本文法的好處是有附 10 篇左右含所教文法的短文跟CD,很早以前考 N2 時是自己讀,那時還是拿奇怪的文法整理手冊在背,現在看來覺得效果沒有很好,這次乾脆把 CD 倒出來,然後反覆的聽跟跟讀到熟,像是睡覺前就放一篇聽到睡著、或是在工作中重複播放,我猜兩本書的 CD 我至少聽過 50 遍以上 。

課程的話,這次是在 utsuki 推薦的 Cafetalk 上面找老師,基本上只要是日文老師都會開 JLPT 專門的課程,結算是上了 28 堂,平均下來大約一週上兩次 50 分鐘的課程;老師是用<日本語パワードリル N2>跟<日本語パワードリル N1>,寫大量的題目跟講解,基本上絕對是有練有差,有些題目用的文法是同一個,錯兩遍就記下來了;而且意外的發現自己在<選出最符合文章的文法選項>這大題非常的弱。
另外老師有用一本<日本語総まとめ N1 語彙>,裡面有整理疊字詞跟副詞,在考前背過一陣,我覺得多少是有用的。

考試結果來看至少文法的評定結果是 A,不過我個人覺得在<重組文法>這題上面,做過的練習題難度都不到真正考試的難度,Correlation 也滿高的,平常寫練習題都很順手,上場考試卻排不太出來,我也不知道該怎麼改善就是了。
  • 聽力
聽力的話…就真的是放水流了……沒有認真準備啊結果也變醬糊,考試結束就覺得跟之前比沒有脫胎換骨的感覺…還是一樣,沒 Fu,聽一聽就是會掉字,偏偏在日文掉關鍵字很致命;然後第四大題真的是我的罩門,真的不知道要回什麼,每個 3 都好像是答案……;這次的聽力還證實了我的閱讀跟聽力是連不上的,有一題聽力講了一堆 りんぎょう,我就一直在想りんぎょう 是啥……見鬼<林業>啦…,,真的是愧對我還看完神去村的小說。

準備上我是建議把字幕丟掉,小弟也是 2016 考爆之後,從 2017 的<動物朋友>開始遮字幕看動畫,至現在雖然不是內容 100% 聽得懂,像<搖曳露營>有關千元鈔票的地方就沒聽懂,但意思都能抓個大概,如<Lovelive Over the Rainbow>跟<紺青之拳>在電影院也盡量遮字幕看。
動畫之外就是把比較紅的<逃避雖可恥但有用>、<半澤直樹>、<房仲女王>的日劇,一樣看完中文之後遮字幕看日文同時跟讀、在上班重複聽上面幾部日劇,或是狂聽 NHK 之類(不過 NHK 其實重複的內容很多,像是颱風、天氣、股市一直重複,其實不算太好的素材);其他就是強者我同學 GGM 大大借我的<新日檢聽解一本搞定>,有意思意思聽過一輪。

綜觀練習狀況,我覺得這次比上次還要穩定許多,我會給的建議,也是我第二次不合格之後,在 N1 衝刺班上老師給的學習建議:
  1. 從聽開始:把字幕丟了,聽動畫、日劇跟綜藝節目,看過中文再聽一遍也可以;反正一定有足夠簡單的內容,比如說動物朋友(O。
  2. 跟讀:超痛苦,但是是讓舌頭聽話的有效方法,必要的時候像房仲女王,可以考慮用 0.8 倍速跟讀,會比較輕鬆一點。
我覺得先不管日檢,至少這兩年練下來耳朵是有變靈敏的,至少看動畫會知道在講啥,練習題會莫名的知道它想講什麼,甚至聽沒聽過的歌也能聽出一些單字,這邊引用研究好像是吊書袋,但之前看過的研究是指出:沒字幕對學語言的效果最好,有其他語言的字幕有一點效果,有字幕基本上就沒效果了(如果有人知道這個研究的話煩請讓我知道一下)。

考場上也沒什麼太大問題,就是新教室比較大,有人反應聽力的聲音不夠大聲,讓大家聽了 8 遍<天氣很好所以去散步吧>,真的很靠北……


細數從大三的時候心血來潮(?)修了日文一,到今天通過 N1,差不多也要十年了,十年間進進退退,修完日文一之後停了一年,接著修了日文二跟後續的一些進階課程;13 年 7 月第一次挑戰N3,那時候在實驗室忙得要死要活,考前一天還失眠睡不著,準備不週又完全沒睡上場考試(回想起來沒考到睡倒真是奇蹟),結果 97/180 比及格高2分浮過去了。
14 年 12 月通過N2,那次準備比較充足些,總分:107/180;後來因為兵役的關係,從 15 年到 16 年進去當個兵出來什麼都忘了,以致連續三次被 N1 壓在地上打QQ。

N1雖然及格了,但從聽說讀寫來看,也只有讀算勉強過關:
現在的口說帶有一種奇怪的口音,重音位置超奇怪,被真的會日語的人指稱她完全聽不懂我在說啥,之前參加多國語言交換咖啡,也是被一位日本人瘋狂糾正,每說一句都有文法上的錯誤,跟 Cafetalk 的老師對話也是零零落落的,他能聽得懂我想講什麼根本奇蹟;試著跟讀也是很吃力,舌頭沒辦法動這麼快的感覺。

俗話說:「N1 考過了只是剛開始」。
誠哉斯言,個人經驗來講,所謂的多益、N1,其實都是能夠訓練的,就像軟體公司面試要刷題,文法、閱讀也能透過刷題解決,這次考前文法粗估應該刷了 300-400 題吧。但除去考試,語言能力或者任何能力,除了實際上場幹架之外,有什麼是考試考得出來的呢?考過了其實什麼都沒有;不過,現下已經知道了進步的方法,剩下就是慢慢努力,務求聽說讀寫能力俱備了。

十年一覺 N1 夢,夢醒時分繼續努力。

2019年8月19日 星期一

第一次在 COSCUP 當講者就上手

故事是這樣子的,在上周結束了兩天的 COSCUP 行程,總算達成人生成就:參加 COSCUP (欸。
這次是以講者的身分去的,畢竟搶票什麼的實在是太難了,就跟搶普悠瑪一樣難,當講者好像比較簡單(True Story)。

這次準備的題目其實都是準備許久的,一個是本次 COSCUP 有開 Rust 議程軌,就把之前寫 computationbook-rust 裡面當範例的 simple language ,配上研究一小段時間的 PEG parser 挑出來,攪一攪投出去。本來這是想要去年的 MOPCON 投的,但畢竟 MOPCON 是以網路為主體,跟這 programming language 還是格格不入被拒絕了。

下面是投影片:


blog 的話,可見實作麻雀雖小五臟俱全的程式語言剖析表達文法 PEG 簡介使用 rust pest 實作簡單的 PEG simple 剖析器使用 procedence climbing 正確處理運算子優先順序幾篇。

另外一個議題則是去年 8-10 月做的 Nixie Tube Clock,COSCUP 有非常適合的硬體議程軌,老實說 Rust 議程軌我覺得不一定會上,硬體議程軌我就真的滿確定會上,畢竟講硬體的本來就少,Nixie Tube Clock 也滿完整的,果然最後就上了一場。
投影片在此:


blog 筆記總計有十篇:
0. 前言
1. 材料取得
2. 自組高壓電路
3. 驅動電路
4. 控制電路
5. 電路板基礎
6. 電路板實作 layout
7. 焊接
8. 寫 code
9. 後記

個人小小的體悟是,先不要想 COSCUP,先想著把某件事情做好,時候到了投稿自然會上;就像會上一位大大說的,因為沒搶到票決定每周用 golang 寫一個 project,52 週之後就當講者了。
這次投上的題目,無論是 PEG + programming language,還是 Nixie Tube Clock,都是一年前甚至兩年前開始的嘗試,PEG 還搞了個失敗的 C parser,blog 寫了好幾篇的題目,做到這種程度才能換到 40 分鐘的上台時間;也許現在就該來想一下要做什麼新題目了。

----

第一次參加 COSCUP ,這次真的融合了超多議程軌人超級多,據說直接突破 2000 人,大拜拜的意味滿重的,像 Pycon 這樣同時段 3 場的都很常兩場一定要選的,COSCUP 同時開 14 場議程,從一開始聽議程就不是目的了。
實際下來比較像:三分聽議程,七分面基友。
細數一下我到底遇到多少在網路上見過面的大大:像是從荷蘭遠道而來的呂行大大、台灣軟體界照世明燈郭神大大、久未見面的 jserv 大大、好高興教授大大、TonyQ 大大、在會前酒會遇見上海大殺四方的 Richard Lin 大大、曾經在高雄氣爆的時候幫我提升 Google Map 權限的 pingooo 教授大大;認識了台灣 maker 社群、Python HsinChu User Group - PyHUG。
不過我覺得比較扯的還是呂行大大,走一走每個攤位都能遇到人,真的是神猛狂強溫爽發。

記得以前參加 PyCon,總會在那邊要求自己盡量的聽,連可能不知道在講什麼的、 lightning talk 都聽完之類的,這幾年終於改掉這樣的習慣,發現時間寶貴,聽一些跟自己太遠的東西其實是浪費時間,還不如放點時間出來跟大家聊聊天,真的沒想聽的就早早離開會場沒差;網路上常講:
小孩子才做選擇,成年人當然是我全都要。
但其實,成年人才知道自己要什麼、不要什麼、有能力要什麼、沒能力要什麼,我覺得是反過來的:
成年人才做選擇,小孩子才是我全都要。

我想最後還是要感謝一些人,像是強者我同學 JJL 大大幫小弟 review 投影片;強者我同學 wmin0 大大幫小弟生出一個 Nixie Tube 的講題,這個題目應該給大大講才是。
明年希望大家也都能成為 COSCUP 講者。

2019年8月3日 星期六

Minecraft 火車站相關系統的設計

小弟玩 Minecraft 一段時間,其實一直想蓋一個大型火車站,然後連續兩次因為伺服器更新所以蓋不完XDD,不過在蓋火車站的期間,還是累積了一些火車站相關系統的設計,蓋不完還是可以介紹一下:
1. 快速向上電扶梯
2. 驗票閘門
3. 平面停開車系統
4. 礦車減速系統

快速向上電扶梯:


快速向上電扶梯其實跟火車站沒什麼關係,但就…火車站常有的東西,這版是用一組向上活塞跟向前活塞交錯推進做成,小心控制紅石信號的延遲就能把人快速的往上推。
當然其實好像沒什麼必要啦…畢竟在 Minecraft 裡面把樓梯又快又不浪費體力,而且電扶梯一堆活塞運作起來其實很吵…。

驗票閘門:

第一版:
第二版:

驗票閘門是腦洞大開做出來的,基本概念是像真的驗票閘門一樣,讓使用者必須投入指定的物品閘門才會開啟,通過之後閘門關上,不小心一口氣就設計了兩個版本:
第一種是投票之後就會開閘門
第二種使用者要從另一個 dropper 裡面取票閘門才會開,更像真實的驗票機

這部分用文字跟圖片說也說不清楚,也許最簡單的還是看影片。

系統的核心如下圖,第二個漏斗裡的東西是裝滿的,這樣使用者只能投入特定的東西(車票);比較器比較投入漏斗跟參考漏斗物品數量是否相同,就能感知<使用者是不是投入車票>這件事,利用這個信號控制漏斗下的另一個漏斗,就能夠控制每次只通過一個物品。

因為我們要求的是投入物品的漏斗,放入物品之後發出的訊號要跟參考值一樣,查一下 wiki,投入物品的漏斗的物品數量要是 22 個,參考漏斗則是 23 個,放入東西之後訊號強度會升到 2,讓比較器打開。

後來就只是基本電路的操作,把物品通過的訊號截出來設定 SR latch,過閘門的踏板重設 SR latch,藉此控制閘門活塞的動作 現在的 SR latch 除了可以用標準的 2x4 雙火把之外,也可以用雙漏斗的 SR latch 設計,如下圖所示,兩者都是 SR latch。

差別在於兩個漏斗的版本,兩個控制信號必須是 1,設定的時候短暫變為 0 來釋放漏斗內的東西;火把設計則是反過來。

平面停開車系統:


這個是很以前設計的東西,因為以前在 Minecart 上是完全不能移動的,所以一定要有一個發車的系統,最一般的就是用凹洞或凸起構成的斜面,加速鐵軌就會朝下加速,不然在平面上加速鐵軌就算有電也不會加速。
這個平面的系統利用活塞,在車子開過去之後把停車位置的背面從鐵軌換成方塊,這樣加速鐵軌就能在平面上讓車子啟動,中間要注意的只有活塞進推的時序問題;不過說起來只是為了改善使用者體驗,不然簡單斜坡就有一樣的效果了。

礦車減速系統:

當初採用減速系統是在火車站的入口,讓使用者能選擇要進站或過站不停。
其實這部是很早以前也是從 Youtube 看到的,但後來完全找不到,幸好當時有先複製一份到測試 server 裡,現在才能蓋出來。
這個系統真的是非常巧妙,利用了比較器來計時,還有將脈衝保持在一個迴圈中來讓鐵軌進到減速模式,整個就是我自己做不出來的設計(yay,所以大家還是看影片吧

目前火車站大概是有這些設計,不過話說回來現在好像也沒什麼時間可以蓋火車站了(yay。

2019年7月10日 星期三

到東京玩 B777-300ER 飛行模擬器

故事是這樣子的,因為一些個人因素,小弟會常常需要來往東京,幸好現在亞洲廉航選擇多,兩個月左右飛一次還可以承受。
在大概是今年一月回台灣的 Vanilla Air 上,看了它們的機上雜誌,內容是由 Vanilla Air 的員工介紹去東京有什麼可以玩的,裡面有一個 Skyart Japan 的介紹,還滿有趣的,服務是可以操縱貨真價實的 B777-300ER 模擬器,在擬真的機艙裡面拍照之類的。

今年六月的時候,預約了一趟飛機模擬的行程,寫篇文來介紹一下這個冷門的旅遊地點:

其實這家除了開模擬器,還有一些其他的服務,像是機師衣服出租、機艙空間出租、寵物攝影(?之類的,但這篇就專注在操縱模擬器上。
首先,這是真的 B777-300ER 的模擬器,所以玩起來其實不便宜,大家可以上官網看它的 plan 列表,最基本的體驗課程,30 分鐘要價是 11,000 JPY,最高開到 120 分鐘 36,000 JPY,有一些特別的方案,像是看富士山,雙人方案、開趴方案、四季景色方案、克服飛行恐懼症…,或者是可以附加的,像是機師制服出借、登機證、從啟動 engine 開始之類的。
順帶一提,它們是可以讓機師做模擬機訓練,像是起飛降落、惡劣天侯,我不確定是網頁(他們的網頁其實很亂,資訊太多沒有整理好)還是現場,有看到相關的規定:「如果你有機師的執照,是必須要出示的」,當然專業機師的方案會比較貴一點,比普通方案每 30 分鐘多 5,000 JPY,所以 120 分鐘就要 56,000 JPY 了。

從預約開始,他們官網有個詢問預約時間有沒有空的表單,不過我記得我填了之後也沒有人理我,直接 plan 選一選下訂比較乾脆,下訂之後就會有人來信跟你確認預約的時間,如果真的很怕訂了之後預約的時間沒空的話,也是可以去信詢問:info@skyart-japan.tokyo,寄信就真的有人會回了。

公司的地址在東京都品川区北品川6-7-29 ガーデンシティー品川御殿山,最近的車站就是品川站,走路大概要 15 分鐘,請自行參考 Google 街景,在一棟很氣派的建築物裡面。

很奇妙的我翻遍手機發現沒有他們客艙內景的照片,可能自行搭配官網的小圖,中間的桌子疑似是用引擎尾部改造而成,噢然後這個是 A320 的客艙,雖然是 A320 的客艙卻長了個 B777-300 的機頭
我們預約的方案是 1 小時的普通模擬方案,附加從停機坪發動引擎跟後推,總價是 26,000 JPY,在下訂的時候就用信用卡附款完成,模擬的時候會有一位真的機師在旁邊當副駕,可以用日文或是英文輔助駕駛,不過畢竟是在日本,一開始詢問方案的時候還是要用日文,我們 1 小時方案可以選擇的有:
* 從羽田機場起飛,繞一圈回到羽田機場降落
* 從羽田機場起飛到成田機場降落
* 從羽田機場起飛到世界上任一個機場降落,當然中間的巡航會省掉,瞬間移動到當地上空

女友選了從羽田起飛/降落三次(兩次 GA)的方案,這樣操作到最多東西。


這張應該就是羽田後推時的照片,一開始先是一位日本機師當副駕用日文帶飛,基本上什麼都不會也沒差,副駕會幫你搞定一切(好啦開引擎他會讓你開一邊),呆呆的看著他跟電腦對話就行了;上跑道飛機自己會緩速前進,正駕駛用一根桿子控制方向。

起飛之後真的能感受到模擬機的厲害,大型的建築物都是建模出來,能看到晴空塔跟迪士尼樂園,夜間飛行還可以加上煙火XDD;不過這台模擬機只有畫面,不會有真正的前後傾斜。

飛完第一圈之後,換旁邊待機的土耳其(? 機師上去,用英文帶飛。我這時跟日本機師問東問西,順便玩我女友:

Q:為什麼雷達圖上面沒有飛機?
A:喔,那只是我們沒開:(轉一個開關)飛機就顯示出來啦wwww
會顯示編號,比我們高,正在下降之類的資訊,故意飛太近的話還會有碰撞警告

Q:剛剛跟後推車的對話是真人還是錄音?
A:錄音,要的話我們也可以(轉另一個開關)機艙內開始放 ATC 跟飛機對話的錄音,好像是紐約那邊的 ATC,播下去之後真的超有實感

其他一些雜雜:
現在飛機都全自動了,三個儀表版可以設定速度、高度跟方位,高度跟方位只會影響儀錶版上的顯示,提醒你要飛到多高跟往哪裡飛,速度設下去電腦會自動接手引擎,所以會看到油門把手自己在那邊動來動去OAO,連降落都是到最後一刻才解除自動駕駛。
轉彎如果超過 35 度,會跳警告:Bank Angle ~ Bank Angle ~,其實我比較想聽 Pull Up ~ Pull Up ~,我滿好奇 35 度到底急不急… 看航跡圖的轉彎半徑都超級小,在旁邊看轉彎半徑還沒有照著航跡圖轉過 owo

總之體驗一下是滿有趣的,如果真的不知道在東京想幹啥,或者想要體驗看看開噴射飛機的話,可以到 Skyart 試試看,預約跟一進去多少需要一些日文對話能力,但我猜他們英文會話應該是能通的。
沒開飛機還是坐個駕駛座過過乾癮,這張是降落之後停在滑行道上,結束時拍的,看看這複雜的儀錶板:

2019年4月22日 星期一

第一次教召就上手

我想是這樣子的,如果你進到這個頁面,有很高的機會你是因為收到後備指揮部寄來的神祕信件,很不巧的機票又沒有訂下去,開始無助的在網路上收集各種相關資訊,或者已經到了鬼門開的前一天,要準備好收行李的時候。
其實小弟也差不多,我是在 2 月底的時候接到後備指揮部確認資料的電話,過不久通知書就寄到家裡,4/15-4/19 要被教召,看看反正就進去國軍養個肝,在那邊躲來躲去的也不是辦法,反正雖然是南部但 4 月中還不算太熱,就乖乖的去召一下保衛台灣獨立。

從拿到召訓說明書開始說起,其實召訓說明書上已經寫清楚要準備什麼了:
  • 身分證/健保卡/駕照三選一,身分證當然是最好,但只要能證明身分的都OK。
  • 私章,領薪餉用:沒帶也可以簽名所以沒差。
  • 個人所需藥品:有病就該吃藥(欸。
  • 盥洗用具:要不要用新訓那種洗頭髮洗身體二合一的看個人,教召洗澡時間比較多沒必要洗戰鬥澡;大概就是沐浴乳、洗髮精、牙膏跟牙刷,刮髮刀想帶就帶一支。
個人衣物,這部分可能是大家最想知道的?當初我有查這個查了一下:
基本上進去會領到公發的兩雙黑襪、兩件內衣、兩件內褲跟一條毛巾,我的策略就是衣服完全不洗,時間省下來看書,我是這樣帶:
  • 一套離營時穿的衣服:星期一報到的時候身上穿的衣服褲子,到營區之後就脫掉放進塑膠袋裡包好,因為天氣熱的話,星期一的衣服吸飽到營區的汗水,放到星期五會非常的臭(我服役的時候試過一次會有像大便的味道,然後我還穿那個去搭捷運回家wwww),簡單作法就是密封起來不再穿了。
  • 保暖用的外套:我是沒帶畢竟南國 4 月就不用再穿外套了。
  • 毛巾:公發的就省下來,解召前繳回去,少浪費一點資源。
  • 五件內衣:同理,不過我日常沒內衣所以就是兩件公發的穿五天這樣。
  • 五件內褲:公發的我繳回去了。
  • 五雙黑襪:公發的我繳回去,如果要自備的話建議買好一點,或是用已經穿舊的,我買了新的結果非常咬腳,覺得沒有很舒服,襪口上面一點有腫起來,雖然我不確定會不會是有跳蚤。
  • 睡覺穿的短褲:這次我忘了帶,只好都穿迷彩褲睡覺…。
衣服之外就是要帶塑膠袋裝髒衣服。

其他:
  • 書:殺時間用的(其實跟同袍哈啦也很殺時間),輕小說我就覺得不錯,小本又可以看很久,像隔壁的大兵帶了<刀劍神域 18、19>,五天下來也快看完了。
  • 充電線:如果你手機續航力不夠,應該會開放中山室讓大家在使用時間充點電,但如果保持關機手機應該不至於每天用幾小時就沒電啦。
  • 水壺:裡面會發保特瓶的腰間水壺,我自己的水壺是晚上在寢室用的。
  • A4 資料夾:裝教召令跟手機三聯單等文件,進去會發一個牛皮紙袋不過我覺得資料夾比較好用。
  • 手錶:我的手錶進去前壞掉了,體會到各種不方便,要一直跟人借錶看時間。
我這次有個第三次被召的自備延長線跟電扇,這就看個人有沒有需要了,如果是 7, 8 月也許有需要。
教召基本上沒有髮禁跟鬍子的要求,裡面也有看到染金髮跟馬尾,要不要剪三分頭的答案應該很明顯了,我是順道去剪短一些,這樣比較不會熱。
連著教召單寄到的包含一張交通兌換券,填好之後可以換台鐵的票,理論上只能換莒光但我換到自強號他也沒跟我收錢owo,而且明明薪餉的錢是來回都有算,那我去程票用換的不是變成國家補助了召員兩次車錢?

教召其實就輕鬆過就好了,稱謂從新訓的編號->部隊的姓名->各位伙伴,一開始聽到怎麼聽怎麼不習慣XD;協訓幹部對大家也很客氣,大家至少都20多歲也都成熟多了,反正大家都當過兵也知道要怎麼做,撐一下五天就過去了。雖然如此教召也不是在玩,該練的都有練,該打靶的就打 25/175 的靶,打完該擦槍的就擦槍,砲操該跳的就連跳三天。
生活上來說下課可以投飲料(我覺得軍中的販賣機一定超級賺…),可以上營站,上下午20 分鐘的下課也會有小蜜蜂販售熱食冷飲,小心不要吃胖了。
手機收繳放養機場之後,每天中午跟晚上兩次有三個時段可以用手機,我自己是覺得領手機麻煩,統一在晚上用手機。
這次的飯(不知道為什麼)很難吃,跟新訓、通校、前運隊、部隊比起來,就教召的飯最難吃,醃漬品特多,新鮮的菜很少很像伙房在省錢,偏偏炒菜又很常燒焦變臭灰搭口味,如果真的忍不住就買營站的泡麵來吃,出來之後我現在吃什麼都覺得是人間美味wwww。

其實教召跟其他人聊一下,也是不錯的體驗,每個人各有不同的退伍年次,服役時的單位也都不同,有的人真的超級操,下部隊遇到聯勇,打完之後一個月再接漢光,結束一周後開始準備聯信(名字跟順序我不確定),幸好在開打前他退了;跟我這種在部隊上做九個月文書退伍的不一樣,這次都是另外兩位下過基地的人在罩我,動作做起來超純熟的。
可能就跟這部微電影說的一樣吧:一次當兵下過聯勇,一生回憶抬頭挺胸。

這次教召小弟的公司那邊正好要發新版軟體,正在緊鑼密鼓的測試跟解 bug,我一被召就躲了五天的工作 lol,然後久違的得到一堆時間可以專心做自己的事,就把很早以前拿到的<時間管理-給系統管理員>給看完了,雖然說一次把書看完好像不是作者的本意啦XDD。
不管怎麼樣進去養個肝也不錯,出來我晚上 10 點眼皮自動變沉重,倒下去一覺到天亮,健康到肝臟都會發光呢。

2019年4月6日 星期六

自幹發光眼鏡

故事是這樣子的,去年十月跟傳說中的幣圈大佬小新大大弄完 Nixie Tube Clock,從小新大大那邊拿到一團剩餘零件,剛好裡面有一批 1206 的白光 LED,想說丟回收前還是可以利用一下,不如就來做個發光眼鏡好了。

準備材料:不要的眼鏡一副、描圖紙、1206 白光 LED、電線、強力膠、220 Ohm 電阻、供電用的 arduino、焊接工具。

首先要把 1206 發光側貼在眼鏡周邊,我試過一定要用強力膠才能黏得住,保麗龍膠跟雙面膠都無法,焊上電線之後扯 LED 的力道出乎意料的強,光電線本身的彈力就能把 LED 再扯下來,其實就算是強力膠用力扯還是會脫下來,使用上要小心一點。
註:強力膠與保麗龍膠感謝強者我室友贊助。
鏡面的部分要貼上描圖紙,才能把光擋下來做出發光的效果,當然貼上描圖紙之後眼鏡就看不到東西了…;最後是把 LED 上焊上電線,焊上之後就要特別小心別把 LED 扯下來了。
最後接上電源,記得 LED 要串聯 220 Ohm 的限流電阻,這樣發光眼鏡就完成啦。

成品:

來看看效果:
啊發光有點不均勻……不過就算了,真的要均勻就要多一點 LED 才行,至少內側也要一組,接線會變很麻煩,直接買燈條應該會簡單很多啦,連焊接都省了,但燈條就是比較貴一點就是…。
至於醜醜的電線…如果有閒的話是可以拉去後面,但有點懶得弄,總之有效果了,我們可以來玩一些東西,像是:

認真發光:

眼神閃爍(物理)
眼神高頻閃爍(物理)

好啦…其實這個東西只是來亂的,大家可以不用這麼認真XD。

2019年3月19日 星期二

維基百科上繁簡內容的修訂

故事是這樣子的,最近小弟在看 github 上一個 os 的教學,跟 jserv 大大的 mini-arm-os 有點像,都是教你從頭幹一個作業系統出來,只不過這個是幹在 X86 處理器上,某種程度上我覺得在 X86 上寫開機程式根本是各種考古,還要從 real mode 一路開上來(yay
最近剛寫好小弟第一個 X86 kernel ,結果因為在 link kernel 的時候,object 檔案的順序寫錯,害我 de 了一輪搖曳露營 OST的 bug,超白痴。

扯遠了,其實這篇是要講 wiki 的,在寫作業系統的時候不免會去查一些 wiki 資料,然後就發現某些條目充滿了中國風格的用語,當然上面選擇台灣正體也不是看不懂但就是煩,於是把過去註冊密碼忘了的 wiki 帳號找了回來,自己來做個編輯,這裡記錄一下流程,希望大家有看到類似的狀況也可以順手修正一下。
我看到的文章是這篇:X86 呼叫慣例

參考用的資料:wiki 繁簡處理說明

首先先打開上例的 X86 呼叫慣例的頁面,會發現網址的部分,其實是 zh-tw/X86调用约定,這是因為 wiki 的規定是所有的中文頁面都是同樣的內容,再用之後會提到的轉換方式,轉換為中國(zh-cn)、新加坡(zh-sg)及馬來西亞(zh-my)三種簡體中文;台灣(zh-tw)、香港(zh-hk)和澳門(zh-mo)三個繁體中文。
所以在條目上變成先佔先贏,也就是有了「X86调用约定」的頁面的話,就不能新建「X86呼叫約定」的條目,必須只能編輯這個頁面,請見繁簡轉換的條目標題
然後編輯內容也不能隨意將簡體轉成繁體或反向轉換,否則會被視為破壞;另外文中的異體字、日本漢字也都有自己的處理方式,不過這裡我們今天不會提到。

這麼做的好處,就是無論簡體或繁體都會貢獻中文的所有頁面,壞處就是用語、行文等習慣,會需要花費時間轉換,而且我很懷疑能不能轉得好,像是文字轉過去了文法卻沒法用轉換的,對編輯者來說也很麻煩,像我如果要編輯簡體先到先得的頁面,就得要用簡體編輯才行,我個人是覺得壞處是大過好處的…但總之這是現下 wiki 的政策,再怎麼智障也只能先遵循(我其實找不太到這個政策形成的過程,也許有知道的人可以補個脈絡)。

再來就要到所謂地區詞處理了,請見wiki 地區詞處理說明:例如 stack 繁體為堆疊,中國簡體則是堆栈或栈,現下 wiki 的做法就是本文一律先到先得,編輯者是簡體中文就寫簡體中文,讀者選擇台灣正體的時候,再轉換成繁體頁面。
這裡的系統畫成階層圖大概是這樣:

愈下面的地區碼針對性就愈強,指定 zh-mo 就只會在澳門繁體頁面才會轉換,但指定繁體中文就會在下面三個語言都轉換;另外 wiki 有幾個不同階層的轉換:由上而下為全域轉換、全文轉換、公共組轉換、單獨轉換來處理。

  • 全域轉換就是超暴力所有 wiki 範圍內的文字都轉換,誤殺率很高,只有非常針對絕對不會誤殺的詞才能進去,例如台灣正體轉換表的:米芝蓮=>米其林。
  • 全文轉換雷同,只是在一篇文章內通殺。
  • 公共轉換組應該是最實用的,也就是針對資訊科技,定義好一系列的對照表,這些對照表就能套用到跟資訊科技相關的文章中。
  • 單獨轉換就是用來針對固定位置的詞來做轉換

我在看到 X86调用约定的時候,就是因為沒上資訊科技的公共轉換組:IT,以致雖然是繁體頁面內容卻都是中國用語(例如標題轉換成 X86調用約定),修正方式也很簡單,在原始碼的部分加上 NoteTA 的轉換模版就好:
{{noteTA
|T=zh-hans:X86调用约定; zh-hant:X86呼叫慣例;
|G1=IT
}}

其中 T 表示標題的轉換
G1~Gn 則是引用公共轉換組,這裡引用一個 IT 的,至於你說為什麼我知道要引用這個…呃…目前我只知道從類似條目去找,或者從全部的列表裡去找(yay

其實只要加上公共轉換組,看起來就會順眼很多了,自然會有一些詞沒修正到,只能之後手動下去修,像公共轉換組只定義堆栈要轉成堆疊,但原始碼有人只寫栈就轉不過去了。
大概就是這樣,要讓 wiki 用詞跟習慣一樣,還是需要大大們多多動手做點小修改,我個人還是覺得把簡體跟繁體頁面合併滿白痴的,你看我們定義了這麼多的公共轉換組,其實連個 X86呼叫慣例都轉換不好,說到底簡體中文跟繁體中文已經不是文字上的差別,而是連文法上都有差異了吧

2019年2月12日 星期二

關於費式數列的那些事

最近費式數列實在有點紅,讓小弟忍不住也來玩一下。
費式數列給一個初學程式的人都能寫得出來,例如早年我忘了哪位大大在推坑我 python 的時候,就寫了個只要 4 行列出費氏數列的 python 程式,一方面展現 python 在大數運算上的實力,一方面展視了它的簡潔,像是 a , b = a+b, a 這種寫法。
a = b = 1
while b < 1000000000000:
  print(b)
  a, b = a+b, a
當然會寫是一回事,深入進去就沒那麼簡單了,詳細請參考這個網頁
最簡單、最直覺的遞迴寫法,但這其實是會噴射的,每次遞迴都會做重複的計算,於是計算以指數的方式成長,比如說我用 python 的 timeit 去測一個遞迴的費式數列函式,很快執行時間就會爆炸,大概到了 fib(30) 以上就會跑得很吃力了。
如果我們用單純的加法,從 1 開始往上加,其實只要進行 n 次的加法就能得到 fib(n) 了,執行複雜度為 O(n);如果再套用更快的 fast fibonacci,更可以把執行時間拉到 O(lg n) 的程度,只要 fib(94) 就超過 64 bits 的整數的情況下,用 O(lg n) 的演算法其實跟常數時間所差無幾。
不過呢,費式數列還有一個公式解呢,也就是:
$fib(n) = \frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n$
為什麼不用這個算式算呢?公式解不是常數時間嗎?

數學上來說:是的,但實際上會遇上一些問題,例如我們看看 64 bits 整數裡面最大的 fib(93) 為例,整數算的解為:
12200160415121876738
如果是 python 寫的公式解呢?
def fib(n):
    return (math.pow((1+math.sqrt(5))/2, n) - math.pow((1-math.sqrt(5))/2, n)) / math.sqrt(5)
print(int(fib(93)))
12200160415121913856
登登,問題大條了,答案不一樣。
何以致此,問題就來到浮點數的不精確問題,這時候就要先來一張經典的漫畫了:
我們在計算完 sqrt(5) 之後,只能用一個近似的值來表達結果,在 python 內預設是以雙精度浮點數在儲存,它跟真正的 sqrt(5) 還是有細微的差距,在隨後的 n 次方、除法上,這個細微的誤差都會被慢慢的放大,最終導致這個巨大的誤差。

幸好我們不是沒有解法的,參考了 C/C++ 版上,傳說中的 Schottky 大大曾經分享如何使用 gmp 或 mpfr 兩個函式庫,算出 e 到小數點下一億位pi 到小數點下一億位,這兩個 gnu 函式庫是所謂的<無限>位數的整數跟<無限>精確度的浮點數,當然他們不是真的無限,只是完全壓榨記憶體來記錄儘可能多的位數以求精確,理論上記憶體撐上去就能把精確度逼上去,只是有沒有那個必要就是,像是把一些無理數算到一億位(欸。
究竟這個函式庫有多麼的強大呢?我們可以來寫個簡單的,例如來算個黃金比例,只要這樣就結束了:
mpfr_t phi;
unsigned long int precision, x=5;
uint64_t digits = DIGITS;

precision = ceill((digits+1)*logl(10)/logl(2));
mpfr_init2(phi, precision);
mpfr_sqrt_ui(phi, x, MPFR_RNDN);
mpfr_add_ui(phi, phi, 1.0, MPFR_RNDN);
mpfr_div_ui(phi, phi, 2.0, MPFR_RNDN);
mpfr_printf("%.10000Rf\n", phi);
mpfr_clear(phi);
唯一要注意的是 mpfr 內部用的 precision 是以 2 進位為底,所以我們在十進位需要的精確度,要先換算為 2 進位的位數,再來就能直接算出 phi 啦,試著算過 50000 位數再對個網路上找的答案,數字是完全一樣的。
這個 library 算得非常快,一百萬位的 phi 也是閃一下就出來了,一億位在我的 64 bit Linux, 2 GHz AMD Ryzen 5 需時 37s,相比 e, pi 這類超越數,phi 只需要 sqrt(5) 真的是非常簡單的了。

扯遠了拉回來,如果我們要用 mpfr 這個函式庫,利用公式解來算 fib(93),要怎麼做呢?
fib(93) 到底有多少位數呢?我們可以用 2^n 作為 F(n) 的上界,最後所需的位數至少就是 ceill(n*log(2)),相對應的我們運算中的浮點數精確度的要求,2^n 這個上界有點可恥粗糙但有用,頂多會浪費點記憶體,最後除出來的小數點後面多幾個零而已,如果能套用更精確的上界當然更好。
mpfr 的函式庫設計精良,呼叫上非常直覺,這段程式碼其實就是寫公式解,應該滿好懂的,程式碼在此。有了這個就可以亂算一堆 fib 了,基本上要算費式數列第一億項 fib(100,000,000) 也是 OK 的(好啦我不保證答案是對的XD,至少 fib(10000) 是對的)。

But,人生最厲害的就是這個 But,公式解真的有比較快嗎?
我個人認為答案是否定的,我們同樣可以用 fast-fibonacci 搭配 gmp 函式庫來計算,因為都是整數的運算可以做到非常快,我的測試程式碼在此

同樣是計算 fib(100,000,000):
formulafib.c: 57.39s user 2.04s system 97% cpu 1:01.09 total
fastfib.c: 4.70s user 0.20s system 75% cpu 6.524 total
O(lg n) 的 fast-fibonacci 遠比<O(1)>的公式解來得快。
問題就在於,到了所謂的大數區域,本來我們假定 O(1) 的加法、乘法都不再是常數時間,而是與數字的長度 k (位元數)有關。而上面我們有提到,基本上可以用 2^n 作為費式數列的上界,也因此費式數列的數字長度 k ~= n,加法、乘法複雜度就會視實作方式上升到 O(n) 跟 O(n^2) 或 O(n lg n) 左右。
在 fast-fibonacci,我們需要做 lg n 次的 iteration,每次三個乘法兩個加減;公式解雖然沒有 iteration,但需要計算兩次次方運算,也等於是 lg n 次的乘法跟加法,然後還有除法,我們運算的又不是整數而是浮點數,這又需要更多的成本,一來一往之間就抵消了公式解直接算出答案的優勢了。

在通常的應用上以及現今電腦的實作,我們還是可以假設整數的加減乘都能在近乎常數時間內結束,這樣我們才能好好討論資料結構與演算法的複雜度,進而把複雜度學好。費氏數列的問題在於,在數字小不用考慮運算複雜度的時候,公式解和 O(lg n) 的 fast-fibonacci 看不出差異,等到 n 終於大到看得出 O(lg n) 跟 O(1) 的差異時,已經要把運算複雜度納入考量了。
理論上我們當然可以假設有個計算模型,無論有多少位的數字,無論浮點數有多少精確度要求,四則運算與次方都能在常數時間內結束,這時公式解就能來到 O(1),但這樣的假設不像停機問題假設的萬能機器,在學術討論上看來不太有意義。
利用 gmp, mpfr 這樣的函式庫,插滿記憶體甚至把硬碟當記憶體來用、把記憶體當 cache 用,浪費幾個星期跟一堆電力,我們可以把無理數算到小數點下一億位、十億位,這是前人們精心為我們建的巨塔,可是數字還是無窮無盡,站在巨塔上反而才看得出我們跟無限有多麼遙遠,誠然人腦可以透過思考一窺數學之奧妙,但不代表我們能超脫數學的嚴格限制浮空而起,妄想記錄無限,我認為是對數學的一種褻瀆。

看了這麼多碎碎念大家想必也累了,總而言之本文透過兩個實作,讓大家體會一下所謂 O(1) 公式解並不一定是 O(1),背後一定有對應的成本;還有就是把費式數列算到一億位真的有點爽,不過我想是沒什麼公司在實務上有在賣 fibonacci 相關的產品啦,除非你想像日本一樣出個寫滿 e, pi 到一百萬位的書讓人當亂數表來用。

2019年1月24日 星期四

閱讀程式碼的心得

許久以前曾經看過這篇,由傳說中在 appier 大殺四方的 PCMan 大神寫的閱讀程式碼教學

最近剛好因為小弟的工作上,也會需要在有一點點規模的程式庫裡面穿梭,雖然都在打混還是累積了一點點心得,在這裡分享一下,當然小弟還是遠不如傳說中的 PCMan 啦,大家從我這裡連過去上面的文章,看完就可以關掉回家了(誒
如果你還是想加減看一下,小弟比較熟的是 C/C++ 系的靜態語言,寫網頁什麼的小弟就不擅長了;然後個人的經驗是有極限的,例如 Linux Kernel 那種規模的 code 我就從來沒有弄懂過QQQQ。

1. 開 code 之前,先把專案編譯,跑起來:


編不起來的 code 就是垃圾,要怎麼知道你改的程式有沒有問題?要怎麼看到你的修改有發生實際效果?編不起來這一切都沒用,所以從網路上載了個 project 下來,第一步一定是先看說明文件把專案編起來或跑起來。
通常網路專案要不是 autotool 就是用 Cmake,個人是覺得 autotool 的機率還是高一點點,但通常都是下個 autoconf 再接 configure 就能生出 Makefile 了。

2. 看 code 是最後一步,先從高層次理解程式在做什麼:


這是工作一陣子之後的心得,原始碼最底層是一個很細緻層次的東西,例如模擬一個 x,y 的座標值,然後往上一層一層建構線、面、一群面的組合、一群組合的參考/一群組合的陣列參考等等,上層會用高層次在操作,把下面的實作都隱藏起來。
理解高層次的程式在幹嘛,遠比從低視角去理解實作重要(雖然 low angle 拍出來的照片比較香(炸)),沒理解想法跟目的之前,直接看程式碼是沒有意義的,看到函式做一個 loop,可是為什麼要 loop,在 loop 什麼?沒理解想法,連看著處理中的資料無法分辨對錯的時候,就只是看一堆無意義的資料飛過去而已。
比如說最近跟著強者我同學 JJL 大大在看 verilator 這個 project,這個 project 會把 verilog 吃進來,模擬的 C++ 送出去,verilator 發大財,直接進到 src 資料夾會看到滿滿的 V3xxxx 的檔案,但只要緊抓上面的概念,其實大部分都是 AST 的檔案,verilog 會先被 parse 成 AST,由程式對 AST 進行一些處理變形,再把成果寫出去;所以說至少會有 AST node 跟走訪 AST 的程式,從這點抓下去八九不離十了。
理解高層次的程式比較困難,一般函式至少會有註解,可以註記這個函式的功能,但高層次想法是一個比較難表述的東西,通常也不會訴諸文字,只會記在開發者的腦袋裡面,如果能有一個人帶領的話通常效率會快很多。

3. 調校好工具:


工具上的投資非常值得,好的工具能省下極大的時間,要不要用 IDE 個人沒什麼信仰,一般我都是用 vim,這部分請參考幾篇拙作:用 Vundle 安裝 vim 插件,還有用 ctags 幫助跳轉,Ctags 的程式碼跳轉是一定要的,效率直接天上飛。
終端機也是一個值得好好投資的工具,我一般工作都會開 5 個終端機的分頁,前三個用來編輯 code,第四個用來編譯(因為 C 專案通常程式碼跟編譯的 top 不會是同一個目錄),第五個用來執行程式(對因為通常程式碼、編譯跟執行檔不會是同一個目錄),用 Alt+12345 可以很快速的在分頁間切換,到 Alt+6 我覺得就太遠了。
至於多螢幕,我覺得有幫助但有限,最大的用處是在撰寫投影片跟筆記的時候,可以把 powerpoint 跟 word 拉到另一個螢幕去,跟 code 來回對照會快很多,但單純閱讀程式碼的時候是用不上的。
另外一些 shell 相關的部分,請參考拙作<那些在工作上看到的各種東西>的工具部分:

4. 邊看邊做點筆記:


說真的大型專案有些都會到很噁心的地步,還會有一些積非成是的地方,命名不佳的地方,可能當初寫好、修改,改到後來就沒人敢改了。
最近遇到還有印象的是這樣:我們會依序分解,一條線 x、x 的其中一個端點 S、S 的兩個端點 X1, X2,分別傳進去給函式 A, B, C 做處理,但函式 A 裡面 S 在 x 的 index 跟函式 C 裡面 X1 的 index,變數竟然都用 index,然後在函式 A, B 裡面,都用 i 變數來 pass 給下層的函式,變成裡面的 index。
搞到後來到底 index, i 在哪裡代表什麼都一團糟,這裡就很適合簡單畫個表格記錄一下;要隨手 refactor 一下也是可以,但在大型又缺乏維護的專案下,refactor 有可能會花很多時間,這部分就要自己取捨了。

5. 順手做點修改?


參照上一點,做點變數修改、加些註解,幫助自己理解程式碼是 OK 的;但要記得,一定要沉住氣,不要去改一些枝微末節的東西。
例如有些專案會是悲劇性的空白 tab 混用的狀態,這就不要改了,第一個這個會引發比無限之戰更慘烈的信仰之戰,第二是這種大範圍的修改很浪費時間;第三這種修改很難進入主線,設定一下 tab 的寬度讓程式碼排版回到容易看的狀態就好。
如果有一些區塊很難讀懂,可以用 vim 的 = 在區塊內做重新排版(雖然我覺得這個功能爛掉的機會滿大的)
再來是 syntax sugar,例如自從 C++11 的 range-based loop 出來之後,看到舊式的 iterator based loop 都會覺得癢癢的,是不是該順手改過去?個人認為是不需要。
syntax sugar 的本意就是:更易讀或表達更簡單的文法,本質上無關乎背後的實作,所以你動了手一方面對程式其實沒半點影響,通常 iterator-based 的 loop 也不會影響閱讀跟理解,還不如把精力省下來看懂程式想做什麼。

要知道大型或是正式的 project ,review 機制完善之後所有的修改都會需要審核,沒事沒頭沒尾的送一個修了一堆東西的 Pull Request 被接受的機率都很低,另外 syntax sugar 等級的 refactor 其實根本不影響程式效能,真正架構上、想法上的 refactor 才會,記住程式開發最浪費時間的東西就是程式人的腦袋,不要浪費時間在低層次的修改上面,專注在高層次的程式流程上。
大型的專案通常都橫跨十幾年,會有老舊語法跟 legacy code 是很正常的事情,我現在做的專案裡面還有 K&R C 的 parameter style 勒,就像下面這種:
int foo(bar, qux)
int bar,
stNode qux { … }
反正編譯器還支援的狀況下留著也沒差,我敢打賭這種 code 還會在公司的程式裡留 10 年以上;記得 syntax sugar 只能加在熱咖啡裡,咖啡冷了就不要浪費精力加糖,想辦法換杯新咖啡比較重要。

6. 從 main 下手:


不知道從哪裡開始,我個人的經驗是從 main 下去最快。
main 通常(通常就是有例外啦)會保留最多高層次的程式邏輯跟想法,如果在 main 裡面看到低層次的操作那也是滿抖的。
以 verilator 為例,main 位於 verilator.cpp,整個結構其實很單純:剖析傳進來的參數,讀檔,process,將結果 dump 出來。process 裡面就是對 verilog AST 進行處理的各個 visitor 呼叫,trace 一下就能清楚整個程式的大體流程了。
當然這個規則無法一體適用就是了,具體還是要看各 project 的架構,我也看過最上層是一套虛擬機的專案,實作功能都拆分為給這個虛擬機執行的函式,這時候進入點就變成各函式而不是 main 了。

以上大概就是幾個工作到現在累積的看原始碼心得,小弟班門弄斧,希望各位看倌大大有什麼意見都能多多回饋給小弟。

2019年1月12日 星期六

省錢是好事嗎

故事是這樣子的,最近有一位很紅的藝人 BBB 拍了高雄市拍了一部 MV,他的宣傳詞是這樣寫的:「BBB 自掏腰包為高雄拍攝的MV『來去高雄』,懇求大家幫助負債累累的高雄市政府不用花任何一毛宣傳費,就可以讓大家湧入高雄拚觀光!達到宣傳高雄的最大效果,請大家努力、用力的轉發分享MV,靠全民的力量達到最大成效!」
剛好最近,政府宣佈因為上半年的稅收有盈餘,同樣也引發一番爭辯,畢竟現在中華台北還有這麼多債務,稅收有多是不是應該先還債?對照組正好是台北市市長,在第一任任期中主打政績即是償還市府負債。

這一連串看完突然有一點感想,跟之前看書的心得結合一下來寫篇文章。

當然我本文無意支持或反對現下政府將稅金盈餘退,或者 BBB 的影片是好是壞有效無效,純粹就貼文背後的精神來評論。
我覺得這篇貼文剛好非常傳神的傳達了兩個概念:
1. 負債累累的高雄市政府需要幫助。
2. 不花政府一毛錢就是讚,大家要多鼓勵。
相對應到退稅議題上面,就是:
1. 負債累累的政府不應該再退稅。
2. 政府不該亂花錢,應該努力減少負債。
說起來有點華國人老一輩刻苦經營儲蓄的精神。

我們常被教導/認為的省錢就是好,負債就是壞,真的嗎?

假設我們地方政府一年歲入是 400 億元,而台北捷運第一期的工程就花了 4000 億,很明顯的如果政府是無法一口氣開工所有的捷運,而必須分年編列預算分年開工;相對的政府可以借債,一口氣先借 4000 億元把捷運蓋完,然後分年的慢慢還債。雖然後者利率會造成多一些成本,可是早點同時開工的話,可以在土地還便宜的時及早徵收,儘早擺脫交通黑暗期,減少道路車禍傷亡,這些都是獲利。
用個更簡單的例子,為何長輩當年都會貸款買房呢?負債不是不好嗎?更別提那個時候借錢利率高得嚇人呢。但借錢買房卻有它的道理在,可以更早享用住房,在房子便宜的時候先買,負債+房子也可能比滿手現金來得保值。
或者再簡單一點,假設今天持有台GG的股票,每年有 2% 的收益,而銀行的利率是 1%,請在「沒有負債沒有股票」跟「欠銀行 100 萬但有等值的台GG股票」兩者間做選擇,前者沒有負債,但以賺錢來看後者才是好的。

上面幾個例子,都在說明省錢是好負債是壞的概念,其實不一定正確,重點要看錢灑出去會換到什麼資產回來,然後評估那個資產合不合理。
我第一次意識到這個觀念,在之前閱讀<21世紀資本論>時裡面的一小段:「殖民時期英法兩國持有的國外資產和帶來的收益,足以使他們承受貿易赤字同時仍有收益……汲汲營營堅守貿易順差本身沒有任何意義,持有資本的根本目的就是能在不工作的狀況下,繼續消費、累積資本」。
同樣的,所有的資產應該要攤開來看,堅守黑字不是絕對,有錢無債只意味著持有「錢」這個資產,而放棄其他可能更高報酬,拿債滾錢的選擇;畢竟長期來看,隨著通膨錢這個資產可能是最沒價值的(你也可以說錢最不值錢XD),所謂保值,就是在比哪個資產價值流失得比錢還慢;政府可以把錢換成火車、航廈、或者乾脆一點換成未來的小孩也可能更賺,至少他們有機會在未來滾出更多小孩。

當然:省錢是好、負債是錯這是個很鐵的概念,直覺上來說很像真的,強者我同學台大財金系畢業一樣逃不過這觀念的束縛(雖然我私心認為他不是不懂,只是戴著有色眼鏡所以反對啦)。

另外一句:省錢是好的嗎?
同樣不盡然。
比如說,如果省錢很重要,為什麼我每天不走路回家呢?因為我搭公車 15 元車程大概 40 分鐘;走路 0 元大概 2-3 小時,搭公車多出來的時間,我可以多寫幾行程式多看一些書,都能比省下的公車錢更有生產力,在這裡,省錢意味著失去時間這項隱形的成本。
花錢可以換到一些隱形的東西,像是請老師是換他的經驗,買珍奶是換舌尖的快樂,或者那個讓人津津樂道的笑話:一個美國工程師拿一半的薪水請三個印度工程師,把工作都包給他們做,自己上班就可以爽爽過,買工程師是換自己的時間。
就像非常早非常早,當我剛被 Free Software 傳教的時候,都會有一段時間覺得為什麼不要整個社會、政府機關改用 Libre Office 就好了?作業系統全部換 Linux 啊,不是超省錢?碰久一點之後就會發現,要對應世界上這麼多、每個都不同規格的硬體,不像 Mac 筆電因為規格全是硬性規定,Windows 雖然沒事出點包然後使用上被大家幹到翻,在穩定、方便、統一規格上仍然把其他 Mac/Linux 壓在地上打,如果加上 Office 系列產品那又更不得了。
Window 可能要錢,但它有 Microsoft 在背後支持,有 bug 會幫你修,全系列的相容性他們會注意,花錢買得到服務;Linux 是免費的,但它沒有客戶支援,沒有相容性支援,整個體驗加上去可能是負的。
所以才有那句諺語:免費的最貴,不收錢表示它有缺點讓它不夠格收錢,那你看得透那個缺點嗎?花不花錢不是重點,重點是花了錢會換到什麼?權衡利弊,省不是一切。

事實上若綜觀國際商場的現況,諸如共享單車、網購平台、叫車服務等,這幾年都出現透過灑大錢補助來吸引使用者,負債買下市佔率,及早建立規模優勢排除競爭者的手法(當然排除之後活不活得下去是另一回事),這跟做好自己產品吸引消費者上門的手法大相競庭。
HTC 不就是一個血淋淋的例子,作為最早推出智慧型手機的廠商,後來卻慢慢在行銷、通路的資源戰上被對手壓了過去?
堅守省錢少舉債思維的中華台北,宛若二戰時日本拿全民精英射手對付美軍機槍的手法,賺到省下來的小利卻不一定擋不過人家用資源硬推出來的優勢,平常都稱讚中國狼性中國小確幸,來到行銷廣告的時候,眼下就來個標準的範例了,果然還是老話一句:一隻手指指著別人的時候,四隻手指指著自己。
啊不過話說回來我打了這麼多,個人資產配置還是都以現金為主,果然是:一隻手指指著別人的時候,四隻手指指著自己,啊哈哈哈…嗚嗚(誒。

落落長說了一堆不相干的東西,我想可以整理兩個 take-away:
  • 負債不是壞事,重點是要看負債換來什麼;錢只是資產的一個表現,要看整體資產是否有所增長,或者有機會成長。
  • 省錢不是好事,重點是花錢能換來什麼?能不能換到時間、方便、穩定、機會?省錢必有成本,你有沒有意識到呢?

2019年1月6日 星期日

用 PEG 寫一個 C parser 續

自從去年十月把 nixie tube clock 完工之後,好像都在耍廢之類的,結果 11/12 月兩個月都沒有發文,其實這兩個月裡面,有的時間都在改之前寫的 C parser,其實整體完成度愈來愈高了,今天發個文來整理一下到底做了啥。
這次做了幾個改變,主要的修正就是加上 expression, declaration, statment 的處理,也學到不少東西,這裡一一列一下:

macro

這是要對應之前寫的 parse_fail,本來 parse_fail 的用意,就是在剖析出錯的時候,把程式終結掉,然後丟一點錯誤訊息出來;本來我的實作是一個函式,利用 unreachable! 丟出錯誤:
fn parse_fail(pair: Pair<Rule>) -> ! {
  let rule = pair.as_rule();
  let s = pair.into_span().as_str();
  unreachable!("unexpected rule {:?} with content {}", rule, s)
}
這樣的實作會有個問題,在程式終止之後的位置一律都會在 parse_fail 這個函式裡,而不是真正出錯的剖析函式,要除錯必須開 stack trace 才能做到。為了避免這個狀況,我們改用 macro 實作 parse_fail,這樣 unreachable! 就會在出錯的位置展開,在終止程式的時候給出正確的位置。
關於 macro 小弟在很早的時候有寫過一篇貧乏的介紹文,改起來也很簡單,把原本作為函式參數傳進來的 pair,由 macro 的 $x:expr 取代,然後用 $x 取代本來 code 裡面所有的 pair,如下文:
macro_rules! parse_fail {
  ( $x:expr ) => {
    {
      let rule = $x.as_rule();
      let s = $x.into_span().as_str();
      unreachable!("unexpected rule {:?} with content {}", rule, s)
    }
  }
}
這樣所有程式裡的 parse_fail(pair) 就會自動開展成下面的三行程式碼了。

另外有一個要注意的是,假設我 parse_fail 的 macro 寫在模組的 helper.rs 裡面,那麼在寫模組的 lib.rs 時,mod helper 要在所有其他 mod 之前,並加上 #[macro_use] 修飾,這跟 rust 模組的編譯流程有關,macro 是跟順序有關的,在 mod helper 之後這個 parse_fail 的 macro 才有定義,後面的 mod 才能使用這個 macro,詳細可以參考這篇

如果想讓使用 extern crate 的人也能使用這個 macro,就要在定義 macro 的時候在前面加上 #[macro_export] 的標籤,每個 macro 都需要單獨 export 才行。

處理 expression 的正確姿勢:

如果有看上一篇,會看到我用 PEG 套件 pest 的 precedence climbing 的功能來完成對 expression 的剖析,但其實那是不完整的,原因在於我們把的做法是把 expression 直接導向 unary_expr (op_binary unary_expr)* 的組合,這樣我們看到 expression,把它展開來就可以得到一大串 unary_expr 跟 op_binary 交錯的序列,把這串東西丟進 precedence climbing 裡面就能建好 expression tree 了。
但實際上的 C 語言比這還要複雜,expression 下面還有 assignment expression,conditional expression 等等,這些 expression 是必須存在的,例如在變數 decl 的地方就會需要 assignment expression,我們本來的寫法把 assignment expression 等等都抹掉了要怎麼辦?把它們加回去要怎麼讓本來的 precedence climbing 的 code 還能正確運作?
後來發現的正確處理方法是這樣的,在文法的部分要把 assignment expression 等東西加回去,裡面用到的三元運算子 ?: ,assignment operator =, +=, -= 等等都從 op_binary 裡面排除,像是這樣:
logicalOR_expr = _{ unary_expr ~ (op_binary ~ unary_expr)* }
conditional_expr = _{ logicalOR_expr ~ ( op_qmark ~ silent_expression ~ op_colon ~ conditional_expr)? }
assignment_expr = _{ (unary_expr ~ op_assign)* ~ conditional_expr }
silent_expression = _{ assignment_expr ~ (op_comma ~ assignment_expr)* }
expression = { assignment_expr ~ (op_comma ~ assignment_expr)* }
原本的 expression 現在只剩 logicalOR_expr,其他的都要拉出來自立條目,讓其他的文法如 declaration 能使用它,但同時都使用 _{} 讓剖析後他們不會吐一個 node 出來,這樣看到 expression 之後,展開來仍然是一串 unary_expr 跟 operator 交錯的序列。

這樣做的好處是 precedence climbing 仍然可以沿用,所有的 operator 都算在 expression 頭下,壞處是我們必須依文法去調整一些文法要不要吐出 node,現在的實作在有兩個特例:
一個是如上面所示,conditional expression 的規定是 logical_OR_expression ? expression : conditional_expression,有一個 expression 在裡面,這會違反我們的假設:把 expression 展開來看都會是 unary_expr 跟 operator 的組合,因此我們要加上一個特別的 silent_expression 在剖析完之後不會生成 expression node ,而是完全展開。

另一個剛好是反過來的狀況,在 C 的 initializer 文法(6.7.9)是這樣定的:
initializer -> assignment_expression | "{" initializer-list "}"
但…我們的 assignment_expression 是不存在的,如果 initializer 真的剖析為 assignment_expression,展開 initializer 只會得到「一團 unary_expr 跟 operator 的組合」,會跟 initiailizer-list 搞在一起,所以反過來我新增了一個 initializer_expr,把 assignment expression 封起來:
initializer_expr -> assignment_expression
initializer -> initializer_expr | "{" initializer-list "}"
這樣拿到 initializer 就能放心展開,再看內容物是 initializer_expr 或 initializer-list 來決定下一步,如果是 initializer_expr 就能放心的丟給 precedence climbing 去建 expression 了。

上面兩個例子都沒什麼道理可言,基本上就是見招拆招,大致就是兩條好像在說廢話的規則:
  1. 會展開的 rule 裡面出現這團 rule 的開頭,則開頭的 rule 代換成自動展開的版本。
  2. 會展開的 rule 跟其他 rule 並列,要再多包一層不會展開的版本。

! tag for = and ==

在這次修改之前都沒什麼機會用到 ! tag,也就是 PEG 裡的 Not predicate,這次在處理更複雜的 expression 遇到,某些狀況 = 的優先權高過 == 以致 == 先被剖析成 = 了。
這時候 op_assign_eq 就要改為:
op_assign_eq = { "=" ~ !"=" }
來確保 = 之後沒有接著其他的 =。

comment

comment = _{ "/*" ~ (!"*/" ~ any)* ~ "*/" | "//" ~ (!"\n" ~ any)* ~ "\n" }
comment 也是這次的修改之一,同樣利用了 ! 的特性,上面兩條其實都滿直覺的:
開頭是 /* 再來只要不是 */ 的內容,就可以匹配任何字元;開頭是 // 再來只要不是換行就可以匹配任何字元。
這兩個例子都使用了 Not predicate,功能很類似 C 裡面的 peek,偷看一下後面的東西而不消耗任何東西。

Hidden grammar:

這點比較不是程式的問題,而是 C 規格的問題,注意以下這些都符合 C grammar,但在工作上千萬別這麼寫,大概有十成的機率你會被電到天上飛
  • volatile, restrict, const 隨便加,加幾個都沒關係
  • 其實可以不用 type,這是符合文法的,gcc 在這裡會直接給你一個 int。
  • 也可以宣告型別,儲存類型什麼的,最後…沒變數。
所以可以寫像是:
int const volatile const volatile const volatile const volatile const volatile const;
const * restrict restrict restrict a;
說真的,看到這樣寫 code 我也會把人電到天上飛,其實我也不知道為什麼 C grammar 要允許這樣的文法就是,看到 gcc 編譯過我差點笑死。

現在離大致完成還有一個最大的難關,就是 declaration 那邊還有 struct, union, enum 等著處理,文法上是還好,更大的問題是不知道怎麼寫轉出來的 AST,之前我大部分都參考強者我學長 suhorng 大大的 haskell 實作,或者參考一些 LLVM 的 IR 實作…當然是沒辦法到 LLVM 那麼複雜啦QQ。
總之最近進度嚴重卡關,這才是我為什麼在這裡打住寫篇文的原因(誒。

自己自幹 AST,配上最近工作上做的一些改動,讓我有了下面這個體會:
資訊源自於數學,本身是無窮的,正如數線上有無數的正整數,無窮的有理數,比無窮更無窮的無理數;數學這個「概念」本身就有無限的資訊
但有了電腦一切就不一樣了,我們只有有限的位元能夠近似數學的概念,所以就有了取捨。
用 64 位元可以表示到 18446744073709551615,大約是 10^19,於是 10^19 -> ∞ 的資訊就被捨去了;同理我們決定浮點數用 IEEE 754 表示,有些小數就是無法表示,無窮的資訊對上有限資源,其間的差距令人絕望。

就如我們把 C code parse 成 AST,AST 裡面要保留多少資訊?像我這樣基本上只保留了簡單的 AST node,隨便建顆樹而已;LLVM 的 IR 就是許多嚴僅設計的物件,保留程式語言的繼承關係跟內部的屬性設計,在處理上就有更多能運用的資訊。
工作上需要的是用電腦處理幾何的資訊,像是點、線、四邊形,那麼一個線段的物件要儲存什麼資訊?可以用起點終點來表示一條線,基於效率跟空間考量,我們可能可以存一下線段是不是垂直的、水平、甚至是不是斜上跟斜下,但要不要存一個 double 的斜率呢?這就要看平常是不是很常需要算斜率了。存更多的東西自然可以方便做些處理,但線段更新時也要更新更多的資訊。

捨去是面對資訊時的必要,資訊工程處理的問題一直都不是資訊太少而是資訊太多,而要捨去什麼資訊、保留什麼,這不是科學而是技藝,這些都不是數學,不會有一個標準的答案,而是視需求去選擇,需要經驗、工具、模擬、除錯、測試……用實驗跟說理得到一個最佳近似的解;正如大學學系的名字:資訊<工程>學系。