(封面圖片由 flickr 用戶 ∁ormullion 製作,以 CC0 授權釋出到公領域)
幾年前,科幻作家姜峯楠的短篇小說《你一生的故事》改編成了電影《異星入境》。故事中提到沙皮爾-沃爾夫假說,沙皮爾-沃爾夫假說認為,語言決定了人的世界觀與認知能力。
雖然假說終究是假說,但在寫程式時,用不同的方式描述問題,常常可以幫助我們改變看問題的角度。
大家老是說 JavaScript 的函數是一級函數 (first-class function) ,到底把函數傳來傳去,可以給我們怎樣的新觀點?
今天有一張 CSV ,內容是:
Death Stranding, 1790, Kojima Productions Grand Theft Auto V, 1299, Rockstart North Valheim, 318, Iron Gate AB
我們可以很方便地用正規表達式 (regular expression) 一行一行處理:
const [, name, price, developer] = /s*([^,]*)\s*,\s*(\d*)\s*,\s*([^,]*)\s*/.exec(line); const result = { name, price, developer };
但正規表達式常常得按需求重寫。有沒有什麼方法能做出一種可以組合的工具,來幫我們處理字串?
如果我們只關心輸入和輸出,那一個 parser 可以簡單看成一個「吃字串、吐出結果和剩下的字串」的函數。
用 TypeScript 描述起來長這樣:
type Option<T> = T | undefined; type Parser<T> = (input: string) => [Option<T>, string];
我們可以這樣實作一個函數,幫我們生出「取得某個字串 s 的 parser 」:
const str : (s: string) => Parser<string> = (s) => (input) => { if (input.startsWith(s)) return [s, input.slice(s.length)]; return [, input]; };
要是成功看見了字串 s ,就會得到 s 和剩下來的字串。要是沒拿到 s ,則會得到 undefined 和原封不動的 input 。
用起來像這樣:
let result: Option<any>; let rest: string = ''; const foo = str("foo"); [result, rest] = foo("foobar"); console.log(result, rest); // "foo", "bar"
為了要處理 "Death Stranding" 和 1790 這種字串,還得做出可以處理英文字的 parser 跟可以處理數字的 parser 。
先準備一個可以處理特定範圍內的字元的 range :
const range : (begin: number, end: number) => Parser<string> = (begin, end) => (input) => { let i = 0; while(i < input.length) { const code = input.charCodeAt(i); if (code < begin || end < code) break; ++i; } if (i === 0) return [, input]; return [input.slice(0, i), input.slice(i)]; };
接著就能做出處理英文的 word parser 和處理數字的 digits parser :
const word = range("A".charCodeAt(0), "z".charCodeAt(0)); [result, rest] = word("foobar2000"); console.log(result, rest); // "foobar", "2000" const digits = range("0".charCodeAt(0), "9".charCodeAt(0)); [result, rest] = digits("1984DEC10"); console.log(result, rest); // "1984", "DEC10"
為了要處理任意數量的英文字,還需要一個「能串起數個 parser 」的 seq :
const seq : <T, U>(pa: Parser<T>, pb: Parser<U>) => Parser<[T, U]> = (pa, pb) => (input) => { const [a, rest0] = pa(input); if (a === undefined) return [, input]; const [b, rest1] = pb(rest0); if (b === undefined) return [, input]; return [[a, b], rest1]; };
實作 seq 時,可以注意到,我們常常判斷 parser 跑完後的結果是成功還是失敗。
如果有一組函數,可以幫我們處理這件事,讓 parser 失敗時,自動傳回 [, input] ,其他時候再交給我們判斷,組合 parser 的時候就更輕鬆了。
這樣的一組函數通常叫做 pure 和 bind :
const pure : <T>(x: T) => Parser<T> = (x) => (input) => [x, input]; const bind : <T, U>(pa: Parser<T>, f: (x: T) => Parser<U>) => Parser<U> = (pa, f) => (input) => { const [a, rest] = pa(input); if (a === undefined) return [, input]; const pb = f(a); return pb(rest); };
接著可以用 pure 和 bind 做看看後面會用到的 seq3 和 seq5 :
const seq3 : <T, U, V>(pa: Parser<T>, pb: Parser<U>, pc: Parser<V>) => Parser<[T, U, V]> = (pa, pb, pc) => bind(pa, (a) => bind(pb, (b) => bind(pc, (c) => pure([a, b, c])))); const seq5 : <T, U, V, W, X>(pa: Parser<T>, pb: Parser<U>, pc: Parser<V>, pd: Parser<W>, pe: Parser<X>) => Parser<[T, U, V, W, X]> = (pa, pb, pc, pd, pe) => bind(seq3(pa, pb, pc), ([a, b, c]) => bind(seq(pd, pe), ([d, e]) => pure([a, b, c, d, e])));
有時候我們也想直接替換結果,所以我們還會準備一個給 parser 用的 map :
const map : <T, U>(pa: Parser<T>, f: (x: T) => U) => Parser<U> = (pa, f) => (input) => { const [a, rest] = pa(input); if (a === undefined) return [, input]; return [f(a), rest]; };
現在我們可以一次串起好幾個 parser 了:
const fullname = seq3(word, str(" "), word); [result, rest] = fullname("Isaac Huang"); console.log(result, rest); // ["Isaac", " ", "Huang"],
我們還需要一種用來取「零個或一個東西」的 parser ,才好做出組合任意數量 parser 的函數:
const zeroOrOne : <T>(pa: Parser<T>) => Parser<[] | [T]> = (pa) => (input) => { const [a, rest] = pa(input); if (a === undefined) return [[], input]; return [[a], rest]; };
接著就能做出將一個 parser 重複很多次的 many :
const many : <T>(pa: Parser<T>) => Parser<T[]> = (pa) => bind(zeroOrOne(pa), (xs) => xs.length === 0 ? pure(xs) : bind(many(pa), (ys) => pure([...xs, ...ys])));
還有靠一個 parser 分隔另外一個 parser 的 sepBy :
const skip : <T, U>(pa: Parser<T>, pb: Parser<U>) => Parser<T> = (pa, pb) => bind(pa, (a) => bind(pb, (_) => pure(a))); const skipFirst : <T, U>(pa: Parser<T>, pb: Parser<U>) => Parser<U> = (pa, pb) => bind(pa, (_) => bind(pb, (b) => pure(b))); const sepBy : <T, U>(pa: Parser<T>, pb: Parser<U>) => Parser<T[]> = (pa, pb) => bind(zeroOrOne(pa), (xs) => xs.length === 0 ? pure(xs) : bind(many(skipFirst(pb, pa)), (ys) => pure([...xs, ...ys])));
現在我們可以處理不定數量英文單字的產品名稱和開發商名稱了:
const concat = (xs: string[]) => xs.join(""); const spaces = map(many(str(" ")), concat); const productName = map(sepBy(word, spaces), (xs) => xs.join(" ")); const developerName = productName; [result, rest] = productName("Valheim, 318"); console.log(result, rest); // "Valheim", ", 318" [result, rest] = productName("Death Stranding, 1790"); console.log(result, rest); // "Death Stranding", ", 1790"
也可以處理價格:
const price : Parser<number> = map(digits, (str) => parseInt(str, 10));
把這些 parser 串起來,就成了 product parser :
const comma = skip(str(","), spaces); const product = map( seq5(productName, comma, price, comma, developerName), ([product, _, price, __, developer]) => ({ product, price, developer }), ); const newline = str("\n"); const productList = sepBy(product, newline);
再處理斷行:
const newline = str("\n"); const productList = sepBy(product, newline);
至此就完成了我們的 CSV parser :
const csv = `Death Stranding, 1790, Kojima Productions Grand Theft Auto V, 1299, Rockstart North Valheim, 318, Iron Gate AB`; [result, rest] = productList(csv); console.table(result);
弄了半天,竟然只能做到幾行正規表達式就能做的事!
但在過程中,我們可以看見怎樣靠型別來描述複雜的行為,也見識到怎麼組合小工具來做出更複雜的工具。
這些製作 parser 的函數,都是一個個「靠自己的參數,就能把事情做完」的函數,像這樣不捕捉外界其他值的函數,又被稱為組合子 (combinator) ,本文正是帶大家實作了簡單的 parser combinator 。
未來有機會介紹 FormEditor 計算欄位時,我們還會看到它們的身影。
網友 Rein 指出,我漏掉了 comma 的實作,也忽略了 product name 之間的空白。也指出我並沒有按標準處理 CSV 。目前已經修正 comma 和 product name 的實作。若要好好處理標準的 CSV ,得對大規模修改本文,故維持原樣。
謝謝他讀得如此細心,並給出回饋。