lambda 運算式

December 20, 2021

在先前的文件中,多少都看過 Listfiltermap 操作時,會建立一個臨時的函式,語法為 (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 下去了,畢竟沒有意義,這也是土炮的價值,從問題中學到經驗,而這經驗,就等下一門語言真想實作時再來用上了。