Perl 的 Regular Expression 的強度:NP-complete

這篇稍微偏 CS 理論一些...

以前在學校學 Formal language 的時候會帶出 Grammer、Language、Automaton 三個項目,就像是維基百科上的條列:

裡面可以看到經典的 Regular expression 會被分到 RG/RL/FSM 這三塊。

前幾天看到 gugod 寫的「[Perl] 以正規表示式來定義文法規則」這篇,裡面試著用 Perlregular expression (perlre) 建構「遞歸下降解析器」 (Recursive descent parser)。

Recursive descent parser 可以當作是 CFG 的子集合,而 CFG 對應到的語言是 CFL,另外他對應到的自動機是 PDA

我們已經知道 perlre 因為支援一堆奇怪的東西 (像是 backreference 或是 recursive pattern),所以他能接受的 language 已經超過 RL,但我很好奇他能夠做到什麼程度。

用搜尋引擎翻了翻,查到對 PCRE 的分析 (這是一套與 Perl regular expression 語法相容的 library):「Which languages do Perl-compatible regular expressions recognize?」。

在裡面有人提到「The true power of regular expressions」這篇文章,裡面給了一個在 PTIME 演算法,將 3SAT 轉換到 PCRE 裡解,這證明了 PCRE 是 NP-hard;另外也很容易確認 PCRE 是 NP,所以就達成了 NP-complete 的條件了...

本來一直以為 PCRE 只是 CFG/CFL/PDA 而已,沒想到這麼強,NPC 表示大多數現有的演算法都可以轉成 PCRE 形式放進去跑... XD

第五堂:「Command-line Environment」

這個系列是從『MIT 的「The Missing Semester of Your CS Education」』這邊延伸出來的,這邊講的是「Command-line Environment」這篇。

開始聊之前先看一下其他的東西,我注意到這系列文章有簡體中文 (這裡,已經翻完) 與繁體中文 (這裡,還有幾篇還沒翻完) 的版本了,如果讀英文會比較累的人可以參考看看。

這堂講 command line 下的各種事情,感覺起來比起前面硬不少。

首先就先開始講 signal,各家系統的 signal 應該還是有些微差異,可以參考各家的 signal(7) (在 command line 下用 man 7 signal 可以列出來)。

這邊講的 signal 都比較通用,像是 SIGKILL 的殺傷力,SIGTERMSIGQUIT,然後有提到 SIGHUP,但 SIGHUP 的設計慣例是拿來重讀設定檔好像就沒提到了...

接下來就帶過 tmux,只大概講了一下概念 (sessions、windows、panes) 與用法。

然後講 shell 的 alias 對於打造環境的幫助,以及 dotfiles 的設計。

後面講 SSH 的應用,然後還提到了兩個不同方向的 port forwarding。

這些對於初學者來說應該蠻有幫助的,第一次打造自己的 shell environment 的過程應該還蠻有趣的?(已經是很久前了...)

第四堂:「Data Wrangling」

有陣子沒寫了,來還個債...

這個系列是從『MIT 的「The Missing Semester of Your CS Education」』這邊延伸出來的,這邊講的是「Data Wrangling」這篇。

這篇是在講 pipe 的用法,在講這些工具之前,其實有個很重要的概念應該要說明 (但沒有在這篇文章裡被提到),也就是 Unix philosophy,這個哲學是指 unix 環境下的工具,都會設計成只做好一件事情。

而要怎麼把這些工具串起來,最常見的就是 pipe,你可以在文章裡看到 grepsedsort 這些工具的用法,以及怎麼用 pipe 串起來。

這邊剛好也可以提一下,利用 pipe 可以把不同功能打散到不同的 process 上,剛好也可以稍微利用到現在常見的多 CPU 的環境。

另外上面因為提到了 grep,文章內花了不少篇幅在講 Regular expression 這個在 CS 課程裡面也是重要的基礎。

會放這種篇幅長度,一方面是 Regular expression 的實用性很高,另外一方面,學術上與自動機理論中的 DFANFA 都有關,算是學習計算理論的起點:

然後後面就有提到 AWK 這個工具,這邊要注意的是,雖然可以用 Perl 之類的工具作到類似的事情 (而且更強大),但 AWK 有被放到 POSIX 標準裡,所以在各種作業系統內幾乎都一定會出現,加上語法算是簡單,學起來還是很有幫助...

然後再最後面的段落冒出一個 gnuplot 畫個圖,以及示範 xargs 這種神器要怎麼用 (這邊會更建議看一下 manpage,可以配合 find 之類的工具用,並且平行化同時處理)。

然後最後示範了 binary data 怎麼處理。

第三堂:「Editors (Vim)」

這個系列是從『MIT 的「The Missing Semester of Your CS Education」』這邊延伸出來的,這篇文章講第三堂課「Editors (Vim)」,這篇也是我決定要連載的原因 (身為 Vim 愛好者的偏好)。

這邊講的是 Vim 而不是標準的 vi (這個對於初學者應該不太容易遇到了),相較起來親民一些...

從基本的操作開始說,模式的切換,插入刪除移動類的與區塊選取類的都有提到。

比較特別的是他用黑板畫 Finite-state machine 來解釋不同的按鍵操作會切換到不同的模式,應該說這不愧是給 CS 學生上的課?

另外補充一下,用搜尋引擎搜一下 vim cheatsheet,沒事可以看一下 (回憶一下),算是蠻好用的。

第二堂:「Shell Tools and Scripting」

這個系列是從『MIT 的「The Missing Semester of Your CS Education」』這邊延伸出來的,這篇文章講第二堂課「Shell Tools and Scripting」。

這堂有點像是第一堂的延伸,在講更多 shell 的操作與工具,然後說明 shell script 怎麼寫。

開頭就先說明有 function,然後講了不少 magic variable,像是 $0$1$9,而 $@$# 也提到了 (但居然沒提到 $*),然後再來是 $$!!$_

然後提到 true 與 false,接著就講條件 || 與 && 了。後面就開始講 shell 裡面的 for 與 if,基本上到這邊已經能寫不少東西了?

後面就介紹更多工具...

第一堂:Course overview + the shell

這個系列是從『MIT 的「The Missing Semester of Your CS Education」』這邊延伸出來的,這篇文章講第一堂課「Course overview + the shell」。

前面大概講一下這 11 堂各一個小時的課大概是什麼,後面就開始講 shell 下的操作了。

先講了一些基本指令 (date & echo),然後提到了環境變數 $PATH,接著就講目錄結構與 ls,然後就順便提到 man 可以拿來查說明,接著是講 redirect 與 pipe 以及 root 權限的特殊性 (以及 sudo)。

在課程最後面的這個範例,你第一眼看不會想到是第一堂課就可以教完的東西,但的確是結合了上面提到的所有東西,可以細細品味一下:

$ echo 1 | sudo tee /sys/class/leds/input6::scrolllock/brightness

MIT 的「The Missing Semester of Your CS Education」

MIT 推出的短期課程,在 CS 相關科系裡面不會教,但是如果學過的話會讓你的 CS 學習過程有很不一樣的改變:「The Missing Semester of Your CS Education」。

整個主軸是偏應用為主,其中花了很多篇章在講 CLI 下的工具,這點從每堂課的標題就可以看出來:

1/13: Course overview + the shell
1/14: Shell Tools and Scripting
1/15: Editors (Vim)
1/16: Data Wrangling
1/21: Command-line Environment
1/22: Version Control (Git)
1/23: Debugging and Profiling
1/27: Metaprogramming
1/28: Security and Cryptography
1/29: Potpourri
1/30: Q&A

我自己快速讀過去的時候發現,雖然這是入門課程,但我還是從裡面抓到了一些以前沒有關注的關鍵字 (像是 Python debugger pdb 與 profiling 相關的操作)。

接下來應該會開個連載來寫一下心得與感想...

CMU 推出 Product Management 的課程

CMUCS (Computer Science) 發的新聞稿:「Carnegie Mellon Offers New Master's Degree in Product Management」。

副標也清楚寫出是一年的課程:

One-Year Program Turns Computer Professionals Into "CEOs of the Product"

除了 CMU CS 外,也結合了 CMU 的 Tepper Business School 一起開:

A joint program of the university's School of Computer Science (SCS) and Tepper School of Business, the Master of Science in Product Management (MSPM) program will start January 2018.

另外一個不同角度的 Product Management。

用 php-cs-fixer 自動將程式碼以 PSR-2 規則修正

PHP Coding Standards Fixer 是在不破壞相容性的情況下,將 PHP 的程式碼往 PSR-2 的方向修正。

安裝的方式很簡單,直接抓下來:

wget http://cs.sensiolabs.org/get/php-cs-fixer.phar -O php-cs-fixer
chmod a+x php-cs-fixer

看是要丟到 /usr/local/bin 下,還是丟到自己的目錄裡都可以。

裝完後就玩:

php-cs-fixer fix foo.php

如果 PHP 程式碼有進版本控制系統,在執行後就可以用 diff 看看改了什麼。

也可以對整個目錄修正:

php-cs-fixer fix foo/

預設是 PSR-2 以及一些作者自訂的規則,如果要強制只用 PSR-2 的話可以用 --level=psr2

By default, all PSR-2 fixers and some additional ones are run.

有一些要注意的地方是,php-cs-fixer 因為是在不破壞相容性的前提下修正的,所以有些 method naming 的規則就無法修。不過比起手動修正 legacy code,可以省下不少時間...

回新竹參加婚宴...

塞車塞到爆炸 (坐客運還遇到前一台發車的車子拋錨,乘客在高速公路上換到我坐的這台車...),然後就遲到快一個小時了... +_+ (圖片就是抛錨的三重客運 XD)

抛錨的三重客運

星期五先去天瓏TCP/IP Illustrated, Volume 1,結果到現場發現沒精裝本,只有 Volume 2 有精裝本...

書本身的故事就不講了 (當天兩位新人解釋了老半天 XD),下面是請 Blake 學長頒獎的照片:

婚宴後先跑去交大門口的土地公廟拜拜,然後發現二餐改建中,就整群人跑到資工系系計中... (發現都不太認識了 XD)

系計中新機房整理的真不錯啊,而且機房冷氣超冷,跟以前比起來舒服多了...