---
robots: noindex, nofollow
tags: 計算欄位
---

# FormEditor 欄位內計算功能開發心得

## 需求

FormEditor 一直想要有類似 Excel 或 monday 那樣的計算功能。

2020 年三月得知這個需求後，本來打算安排實習生做。因為這個功能很好拆分，可以先完成語言設計，再和 FormEditor 整合在一起。事實上語言本身並不難做，反而花了很多時間調整 FormEditor 的結構才整合成功。

## FormEditor

FormEditor 是 Vital BizForm 雲端智慧表單的核心功能，它提供了一個精簡、清爽、現代化的互動表單。可以製作自己的表頭、表格欄位，表格欄位可以水平分割或是垂直分割。還有多欄位表格可以用。欄位可以是文字、數字、下拉選單、單選清單、多選清單、日期、圖片，或是串接 CRM 資料。

這次實作的計算功能，讓使用者可以在網頁介面中，自行輸入我們定義的語言、引用文字或數字欄位中的值，並保留空間，以便未來處理更多不同類型的欄位。

## 語法

要怎麼設計計算欄位呢？

在 2015 年左右，我參加了朋友辦的 Workshop ，在那個 Workshop 中，認識到個一種精簡的程式語言，叫做 λ-calculus ， λ 演算。

它的核心概念很簡單，從 JS 的角度來看就是說我們這個語言只有三個東西：值、函數、和把值應用到函數上這件事。於是程式就成了一個由這三種東西構成的樹（或者是圖，如果你共用了樹的節點的話）。再配上兩種規則：改名字的規則、和應用值到函數上怎麼化簡（reduce）的規則，我們就能做計算了。

這裡說的計算，更像是不斷套用剛剛提到的規則，把一棵語法樹，變成另一棵較小的樹。這個過程叫做 tree reduction （或是 graph reduction ）。

從這個角度出發，在設計 FormEditor 計算欄位時，先考慮的是「怎麼描述語法樹」，接著再決定「怎麼化簡這棵樹」，然後我們就有一個能動的語言了。

於是設計此語言時，不是先寫下 BNF 才實作，反而是邊寫 parser ，邊寫 unit test 來決定它的行為。

語法有：

* `<empty>`
* `<paren>`
* `<num>`
* `<str>`
* `<boolean>`
* `<list>`
* `<subscript>`
* `<error>`
* `<field>`
* `<list-field>`
* `<func>`
* `<binary>`

### 項 (term)

項 (term) 是求值的終點，所有的計算欄位最後都該算出一個項。

* `<empty>`
* `<num>`
* `<str>`
* `<boolean>`
* `<list>`
* `<error>`

`<empty>` 表示什麼都沒有，遇到空的輸入時，就會得到 `<empty>` 。

`<num>` 和 `<str>` 對應到兩種欄位類型，數字欄位與文字欄位，也可以表示直接輸入的值，例如 `123` 或 `"John"` 。

`<list>` 用來表示好幾個計算結果，通常一開始是多欄位的值，因為多欄位是一種一個名稱對應到許多有序的值的欄位。如果 `<list>` 裡面都是無法再求值的 term ，那它自己也算是個 term 。

`<error>` 則是用來表示和計算欄位有關的任何錯誤，包含 parsing 錯誤與 evaluation 錯誤。

### Redex

Redex 指的是可化簡的表達式 (reducible expression) ，表示還可以求值的表達式。

* `<paren>`
* `<subscript>`
* `<field>`
* `<list>`
* `<list-field>`
* `<func>`
* `<binary>`

`<paren>` 表示 `()` ，用來調整四則運算時的優先權。

如果 `<list>` 內還有著可以求值的 redex ，那它也是個 redex 。

`<subscript>` 用來表示 `list[3]` 中的 `[3]` ，用來從 `<list>` 中取值。

`<field>` 表示參考另外一個欄位的值。

`<list-field>` 表示參考另外一個多欄位的值。

`<func>` 表示套用一個函數 (function application) 。

`<binary>` 表示一個二元計算，例如 `a + b` 。

### 實作

第一個實作的模組是語法模組， `syntax.js` 。

在這個模組中，我們直接把 JavaScript 函數當成「值的構造函數 (data constructor) 」用，而不經過 class 的 `new` 關鍵字。例如下面的 `Num` 會幫你生出個 `<num>` 節點：

export const Num = (value) => ({
  type: NodeType.NUMBER,
  value: value,
});

可以用的構造函數有： `Empty`, `Paren`, `Num`, `Str`, `Bool`, `List`, `Subscript`, `Err`, `Field`, `ListField`, `Func` 和 `Binary` ，和上面的語法一一對應著。

parser 模組就叫做 `parser.js` ，在寫 parser 時，我們靠 [parsimmon][parsimmon] 這個 parser combinator 函式庫，幫我們以小 parser 組合出大 parser 。雖然有這樣的組合能力，但為了方便，有些小 parser 還是靠 regular expression 處理它的輸入。

從 parser 程式碼，我們可以整理出 BNF ：

<expr> ::= <subscript>
        |  <binary>
        |  <func>
        |  <field>
        |  <list-field>
        |  <num>
        |  <str>
        |  <empty>

<empty> ::= <optional-whitespaces>

<str> ::= <parsimmon-string>

<num> ::= <parsimmon-number>

<bool> ::= "true" | "false" | "TRUE" | "FALSE"

<subscript> ::= <subscript-base> "[" <num> "]"

<subscript-base> ::= "(" <binary> ")"
                  |  <subscriptable>

<subscriptable> ::= <func>
                 |  <field>
                 |  <list-field>
                 |  <str>

<field> ::= "{" <symbol-without-spaces-and-right-brace> "}"

<list-field> ::= "[" <symbol-without-spaces-and-right-bracket> "]"

<paren> ::= "(" <expr> ")"

<func> ::= <symbol> "(" <expr-list> ")"

<expr-list> ::= <expr>
             |  <expr> "," <expr-list>

<binary> ::= <mul-div-ops>
          |  <mul-div-ops> ("+" | "-") <binary>

<mul-div-ops> ::= <non-binary>
               | <non-binary> ("*" | "/") <mul-div-ops>

<non-binary> ::= <subscript>
              |  <func>
              |  <field>
              |  <list-field>
              |  <num>
              |  <str>
              |  <paren>

## 語境

當 FormEditor 切換到可以執行計算欄位的模式時（例如編輯時的預覽模式、撰寫模式），會以 FormEditor 的內部資料製作出計算語境 (context) 。

例如我們有三個欄位 `title`, `summary`, `empty` ， `title` 存著 `"foo"` ， `summary` 中存著 `42` ， `empty` 中啥都沒放，那會得到這樣的語境：

{
  'title': {
    info: Cell.Field(),
    expr: Str('foo'),
  },
  'summary': {
    info: Cell.Field(),
    expr: Num(42),
  },
  'empty': {
    info: Cell.Field(),
    expr: Empty(),
  },
};

如果我們有一個欄位叫 `formula` ，裡面放著 `{title} + {summary}` ，會得到這樣的語境：

{
  'title': {
    info: Cell.Field(),
    expr: Binary('+', Field('title'), Field('summary')),
  },
};

如果我們有個多欄位叫做 `foobar` ，裡面有兩個欄位，放著兩個數字 `41` 和 `42` ，會得到這樣的語境：

{
  'title': {
    info: Cell.ListField(2),
    expr: List([Num(41), Num(42)]),
  },
};

語境中的 `info` 現在用來表示這個欄位是單欄位還是多欄位，求值 (evaluate) 時我們需要這個資訊。

FormEditor 內部將單欄位、多欄位原型、多欄位本身分別存在三個不同的地方。單欄位在 `dataBox.fields_description` 、多欄位原型在 `dataBox.form_description` 、預覽模式中，從多欄位原型生出來的欄位在 `dataBox.listrow_discription` 。

在計算公式程式碼最上層的 `index.js` 中， `contextFromDataBox` 函數會幫我們從 `dataBox` 生出計算語境。每次公式更新都要呼叫它。同一個檔案中也暴露了其他函數，方便我們只更新部分計算語境，但在此不詳細說明。

FormEditor 多欄位資料是從單欄位改出來的，得另外整理，才能得出 `displayName` 和欄位間的關係。整理多欄位資料用的函數位於 FormEditor 的 `utils` 資料夾中。

## 求值

求值基本上就是不斷重複「找到可以求值的表達式 (expression) ，得出結果 (term) 」，直到無法繼續下去。在 FormEditor 中我們用到一種叫做 löb 的函數，幫我們把準備好的語境，映射成方便求值用的函數。為了要完成這件事，我們得先準備一個為計算語境設計的 `map` 函數：

function contextMap(ctx, f) {
  let result = {};
  for (let key in ctx) {
    const { info, expr } = ctx[key];
    result[key] = { info, expr: f(expr, info) };
  }
  return result;
}

就像 `Array` 的 `map` 會把 `f` 應用在所有的元素上， `contextMap` 也會把 `f` 應用在計算語境內所有的表達式上。而且 `f` 除了 expression 本身外，還可以得到欄位資訊 `info` 。

再準備 JavaScript 版的 löb function ：

function contextLoeb(ctx) {
  let results;
  const go = (f) => () => f(results);
  results = contextMap(ctx, go);
  return results;
}

它的作用是把整個語境交給自己的每一個內容物。

最後將它們組合起來，就會得到我們的求值函數：

export function run(exprTable) {
  const table = validate(exprTable); // 檢查語境合不合法
  let ctx = contextMap(table, construct); // 把 evaluation rules 應用到計算語境上
  ctx = contextLoeb(ctx); // 計算所有的依賴和引用關係
  return contextMap(ctx, x => x()); // 得出計算結果
}

求值的時候，先靠一個 `contextMap` 把，用 `construct` 函數，把每個表達式都變成一個 「根據語境來求值的函數」，再用 `contextLoeb` 把這些函數應用在整個語境的求值結果 上。

最後再用一次 `contextMap` ，把每個求值函數都跑一次，就得到求值完成的語境了。

之所以最後還要跑一次，是因為 JavaScript 是一個嚴格 (strict) 求值的語言，得多墊一層 函數，避免它過早求值導致程式卡死。

再來我們關心的是怎麼寫那個 `construct` 函數。

### 對項 (term) 求值

對一般項求值很無腦，基本上就是直接傳回它自己。 `()` 其實不算是個 term ，他還得把裡面的東西拿出來。

之所以特別為括號準備一種語法，是為了之後繪製到畫面上的時候可以保留括號，但又不必留太多關於原始公式的資訊。

function construct(expr, info) {
  switch (expr.type) {
    // 略
    case NodeType.EMPTY: return () => expr;
    case NodeType.PAREN: return () => expr.expr;
    case NodeType.NUMBER: return () => expr;
    case NodeType.STRING: return () => expr;
    case NodeType.ERROR: return () => expr;
    // 略
    default: return () => Err('FormFormula.Eval.UnknownExpression');
  }
}

對 list 求值也不難，對 list 內裝的表達式求值後，再放回 list 中就好了。用索引取值的時候，會先檢查求出來的表達式是不是 list ，是的話再拿出裡面裝的東西。

function construct(expr, info) {
  switch (expr.type) {
    // 略
    case NodeType.LIST: return (ctx) =>
      List(expr.values
        .map(v => construct(v, info))
        .map(thunk => thunk(ctx)));
    case NodeType.SUBSCRIPT: return (ctx) => {
      let result = construct(expr.value, info)(ctx);
      if (result.type === NodeType.STRING) {
        return Str(result.value[expr.index]);
      } else if (result.type === NodeType.LIST) {
        const target = result.values[expr.index];
        return target || Err('FormFormula.Eval.IndexOutOfBound', expr);
      } else {
        return Err('FormFormula.Eval.NotSubscriptable', result);
      }
    }
    // 略
  }
}

### 對欄位參考求值

對 field 和 list field 求值時，可以看到 löb 的威力。 löb 讓我們可以存取整個計算語境 `ctx` ，於是我們可以靠 `expr.name` 取得其他欄位內的表達式。

在操作 FormEditor 時，我們希望當一個多欄位引用另外一個單欄位的值時，會自動把那個單欄位的值放到每一個欄位中，於是此時會看 `info` 來檢查現在正在求值的欄位是不是多欄位。如果是，那當被參考的欄位為單欄位時，就會自動按欄位數量生出 list 。如果是多欄位，則不做事，反正多欄位內的 list 在顯示時會被展開到每個欄位中。

另外要注意的是，現在 field 和 list field 在功能上並沒有分別，之所以分兩種語法，除了為了畫面顯示之外，也保留空間，以便未來設計師修改 list field 的行為。

function construct(expr, info) {
  switch (expr.type) {
    // 略
    case NodeType.FIELD: return (ctx) => {
      const cell = ctx[expr.name];
      if (!cell || typeof cell.expr !== 'function') {
        return Err('FormFormula.Eval.FieldNotFound', expr);
      }
      const term = cell.expr(ctx);
      // 如果當前表達式在多欄位內，且引用了單欄位的值，則按欄位數量創造一個 list
      if (
        info.type === CellType.LIST_FIELD &&
        cell.info.type === CellType.FIELD
      ) {
        return List(range(info.count).map(() => term));
      }
      return term;
    }
    case NodeType.LIST_FIELD: return (ctx) => {
      const cell = ctx[expr.name];
      if (!cell || typeof cell.expr !== 'function') {
        return Err('FormFormula.Eval.ListFieldNotFound', expr);
      }
      const term = cell.expr(ctx);
      // 如果當前表達式在多欄位內，且引用了單欄位的值，則按欄位數量創造一個 list
      if (
        info.type === CellType.LIST_FIELD &&
        cell.info.type === CellType.FIELD
      ) {
        return List(range(info.count).map(() => term));
      }
      return term;
    }
    // 略
  }
}

### 對函數與二元運算子求值

原生函數 (primitive functions) 和二元運算子 (binary operators) 定義在獨立的 `functionTable` 中，放在 `primitives.js` 。

雖然它們都是以 JavaScript 實作的，但我們並不直接把值傳給 JavaScript 函數，而是把表達式傳過去，讓這些原生函數決定該怎麼處理。

這樣做的好處是，當未來引進不同的語法，例如 date 或是 currency 時，可以擴展我們的原生函數，而不被 JavaScript 奇怪的自動轉型影響。也可以實現兩個 list 相加之類的功能。

function construct(expr, info) {
  switch (expr.type) {
    // 略
    case NodeType.FUNCTION: return (ctx) => {
      const func = functionTable[expr.name];
      if (typeof func !== 'function') {
        return Err('FormFormula.Eval.FunctionNotFound', expr);
      }
      // 對參數求值
      const args = expr.args.map((e) => construct(e, info)(ctx));
      let errs = [];
      for (let arg of args) {
        if (arg.type === NodeType.ERROR) errs.push(arg);
      }
      if (errs.length) {
        return errConcat(errs);
      }
      return func.call(undefined, args);
    }
    case NodeType.BINARY: return (ctx) => {
      const func = functionTable[expr.name];
      if (typeof func !== 'function') {
        return Err('FormFormula.Eval.OperatorNotFound', expr);
      }
      const left = construct(expr.left, info)(ctx);
      const right = construct(expr.right, info)(ctx);
      let errs = [];
      if (left.type === NodeType.ERROR) errs.push(left);
      if (right.type === NodeType.ERROR) errs.push(right);
      if (errs.length) {
        return errConcat(errs);
      }
      return func.call(undefined, left, right);
    }
    // 略
  }
}

`primitives.js` 也包含了這些原生函數顯示在 FormEditor 公式編輯器裡的說明。

## 環狀引用分析

FormEditor 計算公式中，不存在使用者定義的函數，所以我們可以假設當用戶沒有寫出循環參考的公式時，計算公式一定會終止。

要偵測存不存在循環參考，我們先搜集每個表達式中參考到的欄位 (field) 名稱：

function collectFields(expr) {
  switch (expr.type) {
    case NodeType.PAREN:
      return collectFields(expr.expr);
    case NodeType.LIST:
      return expr.values.reduce((acc, arg) => acc.concat(collectFields(arg)), []);
    case NodeType.SUBSCRIPT:
      return collectFields(expr.value);
    case NodeType.FIELD:
      return [expr];
    case NodeType.LIST_FIELD:
      return [expr];
    case NodeType.FUNCTION:
      return expr.args.reduce((acc, arg) => acc.concat(collectFields(arg)), []);
    case NodeType.BINARY:
      return [...collectFields(expr.left), ...collectFields(expr.right)];
    default:
      return [];
  }
}

再來設計一個函數 `walk` ，可以從特定欄位開始，檢查計算過程中，這個欄位會看到哪些其他欄位：

function walk(ctx, field, seen) {
  const cell = ctx[field.name];
  if (!cell) return seen;
  const fields = collectFields(cell.expr).filter(fld => !seen[fld.name]);
  let current = {...seen};
  for (let fld of fields) {
    current[fld.name] = true;
  }
  return fields.reduce(
    (acc, fld) => objectConcat(acc, walk(ctx, fld, current)),
    current,
  );
}

最後可以檢查某個欄位是否參考到自己：

export function checkCycle(ctx, name) {
    const seen = walk(ctx, Field(name), {});
    return !!seen[name];
}

未來只要修改 `collectFields` ，就能支援新的語法。

## 整合

### 修改事件傳遞方式

原本 FormEditor 在欄位被修改後，會直接觸發全域回呼 (callback) 函數來通知外部程式。但為了加上計算公式，我們希望欄位被修改後，能在 FormEditor 的 UI 結構中傳遞，最後再通知外界。這樣過程中我就可以監聽從下往上傳的事件，決定什麼時候該更新計算公式。

欄位本身位在 `FormFieldType.vue` ，從這邊開始，靠 Vue 的 `$emit` 來把欄位資訊往上傳。

礙於目前 FormEditor 的結構，在往上傳的過程中，我們會在事件裡添加一些資訊，最後在 `App.vue` 的 `HandleChange` 與 `HandleInput` 中，再讓 Vuex 修改 store 中的計算語境。

另外因為 FormEditor 是靠 `v-model` 對資料做雙向綁定，在更新計算結果時，會再次觸發修改事件。為了避免大規模修改架構，我們另外做了一個 debounce 16ms 的 `debouncedEmit` 來把最後的計算結果往外界傳。

### 儲存原始碼與計算結果

欄位資訊通常叫做 field info ，每個欄位都可以選擇自己的型態，後端服務支援的欄位型態有：

* `text`
* `textarea`
* `number`
* `dropdown`
* `radio`
* `checklist`
* `date`
* `datetime`
* `image`
* `signature`
* `custom`

我們這幾次添加的新欄位通通都屬於最後的 `custom` 型態。

新型態有：

* `related`
* `autofill`
* `formula`

為了區分它們，現在把這些新型態放在 `fieldInfo.value[0]` 中。

為了封裝這件事，我們提供了自定義的 setter 和 getter ：

export function getType(fieldInfo) {
  return fieldInfo.type === FieldInfoType.CUSTOM
    ? fieldInfo.value[0]
    : fieldInfo.type;
}

export function setType(fieldInfo, type) {
  switch (type) {
    case FieldInfoPseudoType.RELATED:
    case FieldInfoPseudoType.AUTOFILL:
    case FieldInfoPseudoType.FORMULA:
      fieldInfo.type = FieldInfoType.CUSTOM;
      fieldInfo.value[0] = type;
      return;
    default:
      fieldInfo.type = type;
      return;
  }
}

### 呈現計算結果

計算結果仍是表達式，我們要把它轉成人類好讀的格式。要把表達式轉成字串不難：

export function print(expr) {
  switch (expr.type) {
    case NodeType.EMPTY: return '';
    case NodeType.PAREN: return `(${print(expr.expr)})`;
    case NodeType.NUMBER: return `${expr.value}`;
    case NodeType.STRING: return expr.value;
    case NodeType.BOOLEAN: return `${expr.value}`.toUpperCase();
    case NodeType.LIST: return `[${expr.values.map(print).join(', ')}]`;
    case NodeType.SUBSCRIPT: return `${print(expr.value)}[${expr.index}]`;
    case NodeType.ERROR: return `error: ${expr.message}`;
    case NodeType.FIELD: return `{${expr.name}}`;
    case NodeType.LIST_FIELD: return `[${expr.name}]`;
    case NodeType.FUNCTION: return `${expr.name}(${expr.args.map(print).join(', ')})`;
    case NodeType.BINARY: return `${print(expr.left)} ${expr.name} ${print(expr.right)}`;
    default: return '?';
  }
}

比較特別的是要把表達式呈現在網頁上這件事。如果直接把表達式轉成巢狀的 HTML DOM 元素，雖然好寫，但是無法讓瀏覽器幫我們自動換行。

於是我們在計算欄位的 `token.js` 中準備了顯示用的資料結構 `Token` ，在轉換成 HTML DOM 元素前，得先把表達式轉換成 `Token` 陣列，這樣才能把它從左自右畫出來：

export function printTokens(expr) {
  switch (expr.type) {
    case NodeType.EMPTY:
      return [];
    case NodeType.PAREN:
      return [
        LeftParen(),
        ...printTokens(expr.expr),
        RightParen(),
      ];
    case NodeType.NUMBER:
      return [Num(expr.value)];
    case NodeType.STRING:
      return [Str(expr.value)];
    case NodeType.BOOLEAN:
      return [Bool(expr.value)];
    case NodeType.LIST:
      return [
        LeftBracket(),
        ...expr.values.reduce((acc, e, i) => {
          const tokens = printTokens(e);
          if (i !== expr.values.length - 1) {
            return [...acc, ...tokens, Comma()];
          }
          return [...acc, ...tokens];
        }, []),
        RightBracket(),
      ];
    case NodeType.SUBSCRIPT:
      return [
        ...printTokens(expr.value),
        LeftBracket(),
        Num(expr.index),
        RightBracket(),
      ];
    case NodeType.ERROR:
      return [Err(expr.message, expr.payload)];
    case NodeType.FIELD:
      return [Field(expr.name)];
    case NodeType.LIST_FIELD:
      return [ListField(expr.name)];
    case NodeType.FUNCTION:
      return [
        Func(expr.name),
        LeftParen(),
        ...expr.args.reduce((acc, e, i) => {
          const tokens = printTokens(e);
          if (i !== expr.args.length - 1) {
            return [...acc, ...tokens, Comma()];
          }
          return [...acc, ...tokens];
        }, []),
        RightParen(),
      ];
    case NodeType.BINARY:
      return [
        ...printTokens(expr.left),
        Op(expr.name),
        ...printTokens(expr.right),
      ];
    default:
      return [];
  }
}

程式比 `print` 長一點，但一樣是分別處理各種表達式，再把結果接起來。

## 未來發展

由於此語言的 syntax, parser, printer 都像教科書一樣分開實現，要擴充並不難。不直接以 JavaScript 實現原生函數讓我們有機會加上針對不同欄位型態設計的運算子與函數。

`Boolean` 常數正是同事 Ryan 加上去的，他還加上了 `>`, `<`, `=` 運算子，和 `IF` 函數。最近又實作了 `&` 運算子，讓計算欄位的行為和 Excel 公式相似。

未來也許能對日期欄位求範圍、對貨幣欄位套用不同的四捨五入行為。

Microsoft 的 Cali Intelligence 發表了 [LAMBDA: The ultimate Excel worksheet function][lambda-excel] ，宣布 Excel 未來會支援使用者自己定義的 lambda function ，我們的小語言也許可以引用他們研究過程中的部分成果。

## 參考資料

先前公開過簡化後的計算欄位說明，可以看到一開始的設計思路：

* [簡易計算欄位](https://hackmd.io/@gsscsid/form-editor-formula)
* [簡易計算欄位 - Parsing](https://hackmd.io/@gsscsid/form-editor-formula-2)

如果想瞭解 löb 和 möb 是怎麼運作的，還可以讀讀 [Löb and möb: strange loops in Haskell][loeb-moeb] 和 [Löb and möb in JavaScript][loeb-moeb-javascript] 。

[parsimmon]: https://github.com/jneen/parsimmon
[loeb-moeb]: https://github.com/quchen/articles/blob/master/loeb-moeb.md
[loeb-moeb-javascript]: https://rufflewind.com/2015-04-06/loeb-moeb-javascript
[lambda-excel]: https://www.microsoft.com/en-us/research/blog/lambda-the-ultimatae-excel-worksheet-function/