lambda 運算式

在先前的文件中，多少都看過 List 的 filter、map 操作時，會建立一個臨時的函式，語法為 (arg1, arg2) -> expression 的形式，這稱為 lambda 運算式。

Toy 語法

你也可以如下建立一個 lambda 運算式，並指定給變數：

max = (m, n) -> m if m > n else n
println(max(10, 3))  # 顯示 10

Toy Lang 的 lambda 運算式，-> 右邊的運算結果，就是 lambda 運算式的結果；如果有兩個以上的參數，箭號函式的參數列必須使用 () 包含起來，沒有參數的話，就只要寫 () 就可以了：

foo = () -> println('Foo')
foo() # 顯示 Foo

如果只有一個參數，那麼括號可以不用：

plusOne = n -> n + 1
println(plusOne(10)) # 顯示 11

lambda 運算式在執行時，會產生 Function 的實例，它沒有區塊形式的語法，因而只能用來撰寫簡單的小函式，對於複雜邏輯的演算，仍然必須使用 def 來定義，lambda 演算式也可以形式閉包，例如：

def foo(x) {
    return y -> x + y
} 

println(foo(10)(20)) # 顯示 30

Toy 實作

lambda 運算式其實跟 def 定義的函式沒有兩樣，不同的是它不會直接指定給某個變數，本身也沒有名稱，這可以在 expr_parser.js 中看到：

const OPERAND_PARSER = TokenableParser.orRules(
	['lambda', {
		burst([bodyTokenable, ...paramTokenables]) {
			return new Func(
				paramTokenables.map(paramTokenable => Variable.of(paramTokenable.value)), 
				new Return(EXPR_PARSER.parse(bodyTokenable)),
				"''" // anonymous
			);
		}        
	}], 
	....

那為什麼 def 被當成是個陳述，而 lambda 卻是個運算式呢？嗯！def 某些程度上來說，是一種指定陳述，也就是執行時期時建立 Function 實例後，指定給某個變數，而 lambda 運算式本身僅運算出 Function 實例。

這就可以回頭來談一個問題了，函式呼叫是運算式還是陳述句？如果函式呼叫是出現在運算式中，例如 1 + add(1, 2)，那 add(1, 2) 當成運算式是沒問題的，而像 println('Hello, World') 因為沒有傳回值，被當成陳述也是沒有問題，那如果這樣呢？

println('Hello, World')
add(1, 2) # 陳述句？運算式？
println('Hello, World')

這是 add(1, 2) 該行，會產生一個陳述節點，內含一個運算式節點，具體來說，就是一個 ExprWrapper 包裹著一個運算式節點，這可以在 line_parser.js 中看到：

['expression', {
	burst(tokenableLines, infixTokenables) {
		return new StmtSequence(
			new ExprWrapper(
				EXPR_PARSER.exprAst(infixTokenables)
			),
			LINE_PARSER.parse(tokenableLines.slice(1)),
			tokenableLines[0].lineNumber
		); 
	}
}]

ExprWrapper 因為包裹著一個運算式節點，在執行時對運算式評值完後，直接傳回環境物件就可以了，因而符合陳述句的條件，這可以在 statement.js 中看到：

class ExprWrapper extends Stmt {
	constructor(expr) {
		super(1);
		this.expr = expr;
	}

	evaluate(context) {
		const maybeContext = this.expr.evaluate(context);
		return maybeContext.notThrown(_ => context);
	}    
}

函式呼叫的實作，其實難處是在 Parser 的處理，如方才所述，函式呼叫也是一種運算式，在最簡單的情況下，也許就是 add(1, 2) 這樣，然而引數也可以是運算式，因此 add(1 + x, 3 + y) 也可以，而 add(4 + add(1, 2), 5 + add(3, 4 + add(7, 8))) 當然也要可以。

也就是說，函式呼叫是個運算式，引數本身也可以是運算式，運算式中又會有函式呼叫，因此語法上會形成巢狀結構，若要能針對這樣的情況進行剖析，光是 Regular expression 是行不通的，必須實作出有限狀態機之類的演算流程。

不過這流程會有點複雜，另一方面，Toy Lang 為了簡化 Parser 設計，採用了以行為基礎的剖析方式，而且硬是用了 Regular expression 來處理符號的辨識，甚至是…呃…判斷語法…

稍微套用一下編譯原理相關文件中的術語的話，就是 Toy Lang 將只適用在詞法分析的 Regular expression，也硬是拿來用在語法分析了，例如，1 + add(1, 2)，Regular expression 適合用來將之切割為 1、+、add、(、1、, 2 與 ) 等符號，接著應該要有語法分析器，判斷將這些符號的哪些組成，會代表著語言中規範的哪些意義，例如，在讀取 add、(、1、, 2 與 ) 之後，判定這是個函式呼叫的語法。

然而，Toy Lang 將詞法分析與語法分析混合在一起，也將 Regular expression 用在這兩個部份，因此遇到巢狀的函式呼叫，就面臨了困境。

也許就簡化 Parser 設計，專心於語法樹與語意設計來說，也不算是困境，畢竟一開始的目的，就只是做個堪用的 Parser，那麼這部份怎麼解決？

我的方式是，判斷函式呼叫時的引數列，是否有對稱括號，然而，Regular expression 無法比對任意深度的對稱括號，因而只能退而求其次，寫個函式，可以指定巢狀括號的允許深度，自動產生對應的 Regular expression，這是定義在 regex.js。

const NESTED_PARENTHESES_LEVEL = 3; 

// For simplicity, only allow three nested parentheses.
// You can change NESTED_PARENTHESES_LEVEL to what level you want.
// More nested parentheses are too complex to code, right?

function nestingParentheses(level) {
	if (level === 0) {
		return '[^()]*';
	}
	return `(?:[^()]|\\(${nestingParentheses(level - 1)}\\))*`;
}

const NESTING_PARENTHESES = nestingParentheses(NESTED_PARENTHESES_LEVEL);

const ARGUMENT_LT_REGEX = new RegExp(`\\((${NESTING_PARENTHESES})\\)`);

預設最多只允許巢狀 3 層，這已經可以寫出很難懂的函式呼叫了，有了這個方式，在剖析函式呼叫上就可以應付大多數的情況，除了運算式中有字串部份，而字串中含有 ( 或 ) 的情況，像是 println('(')，就可以輕易地破壞掉 Parser 的處理。

所幸這種情況，對大多數演算來說不常見，使用個變數也可以 workaround 這個情況：

leftP = '('
println(leftP)

實際上，在處理 List 的 [] 語法時，也採用了相同的方式，自然地，缺點也是類似。除此之外，這也影響到函式呼叫後若傳回 List，是否可以直接用 [] 指定索引的問題，例如，head(lt)[0]。

這類問題若還是基於 Toy Lang 的方式，也使用 Regular expression 來硬上，就會落入雞生蛋、蛋生雞問題，JavaScript 的 Regular expression 不支援遞迴，也就沒辦法簡單的解決這類問題。

正確的做法，還是要分離詞法分析與語法分析，因此，我就沒在這方面繼續 workaround 下去了，畢竟沒有意義，這也是土炮的價值，從問題中學到經驗，而這經驗，就等下一門語言真想實作時再來用上了。