本文使用 Zhihu On VSCode 創(chuàng)作并發(fā)布

[TOC]

前言

寒假時(shí)沉迷C++模板元編程，寫(xiě)了個(gè)簡(jiǎn)單的Scheme元循環(huán)求值器。可以用類似Scheme的語(yǔ)法寫(xiě)出這樣的C++模板代碼：

_<lambda, _<V(pred), V(lst)>,_<letrec, _<_<V(iter), _<lambda, _<V(lst)>,_<cond,_<_<is_null, lst>, B(false)>,_<_<pred, _<car, lst>>, B(true)>,_<elsee, _<iter, _<cdr, lst>>>>>>>,_<iter, lst>>>

等價(jià)的Scheme代碼是這樣的：

(lambda (pred lst)(letrec ((iter (lambda (lst)(cond((null? lst) #f)((pred (car lst)) #t)(else (iter (cdr lst)))))))(iter lst)))

可以在運(yùn)行時(shí)輸出表達(dá)式的值：

/* mutual recursive 1* (letrec* (* (even? (lambda (n)* (if (eqv? n zero)* #t* (odd? (sub1 n)))))* (one 1)* (odd? (lambda (n)* (if (eqv? n zero)* #f* (even? (sub1 n)))))* (sub1 (lambda (n) (- n one)))* (zero (sub1 one)))* (even? 12))*/ using expr = eval<_<letrec,_<_<V(is_even), _<lambda, _<V(n)>,_<iff, _<is_eq, n, V(zero)>,B(true),_<V(is_odd), _<V(sub1), n>>>>>,_<V(one), N(1) >,_<V(is_odd), _<lambda, _<V(n)>,_<iff, _<is_eq, n, V(zero)>,B(false),_<is_even, _<V(sub1), n>>>>>,_<V(sub1), _<lambda, _<V(n)>, _<sub, n, one>>>,_<V(zero), _<sub1, one>>>,_<is_even, N(12)>> >; runtime<expr>::output(std::cout) << std::endl; // #t

還有一些簡(jiǎn)單的例子：

/* mutual recursive 2* (letrec* ((fs (cons* (lambda (n)* (if (eqv? n 0)* #t* ((cdr fs) (- n 1))))* (lambda (n)* (if (eqv? n 0)* #f* ((car fs) (- n 1)))))))* ((car fs) 12))*/ using expr = eval<_<letrec,_<_<V(fs), _<cons,_<lambda, _<V(n)>,_<iff, _<is_eq, n, N(0) >,B(true),_<_<cdr, fs>, _<sub, n, N(1)>>>>,_<lambda, _<V(n)>,_<iff, _<is_eq, n, N(0) >,B(false),_<_<car, fs>, _<sub, n, N(1)>>>>>>>,_<_<car, fs>, N(12)>> >; runtime<expr>::output(std::cout) << std::endl; // #t /* dot* (let* (* (head (lambda (head . tail) head))* (head 1 2 #f))*/ using expr = eval<_<let,_<_<V(head), _<lambda, _<V(head), dot, V(tail)>, head>>>,_<head, N(1), N(2), B(false)>> >; runtime<expr>::output(std::cout) << std::endl; // 1 // (flat-map list (list 1 2) (list 3 4)) using expr = eval<_<flat_map, list, _<list, N(1), N(2) >, _<list, N(3), N(4)>> >; // interleave runtime<expr>::output(std::cout) << std::endl; // (1 3 2 4)

當(dāng)然求值的結(jié)果也可以在編譯期使用，只是懶得實(shí)現(xiàn)了（畢竟本質(zhì)玩具……而且C++編譯期計(jì)算用constexpr函數(shù)就足夠了）。

代碼以及詳細(xì)的介紹位于https://github.com/Light-of-Hers/CCTV

寫(xiě)完后就忘了這茬事了……

這學(xué)期修了胡振江老師的PL課，突然想起了自己寫(xiě)的這個(gè)玩具，便寫(xiě)下此文記錄一下。

語(yǔ)法元素

• 用變參模板來(lái)表示scheme中的列表(list)。
• 用普通類來(lái)表示不攜帶其他信息的token，比如關(guān)鍵詞(keyword)、標(biāo)識(shí)符(identifier)等。
• 用模板類來(lái)表示攜帶額外信息的token，比如字面量(literal)：number、boolean等。
• 用模板類來(lái)表示denotable value，比如pair、closure等。

其中l(wèi)ist和token是用戶可見(jiàn)的，為了方便用戶的書(shū)寫(xiě)：

• keyword提前聲明好，這樣用戶可以直接寫(xiě)lambda來(lái)表示scheme中的lambda。
  • 部分keyword和C++的keyword沖突，做了一些修改，如用iff表示if。
• 表示list的模板名取為_(kāi)，這樣用戶就可以用_<a, b, c>來(lái)表示scheme中的(a b c)。
• 用一個(gè)macro來(lái)聲明代表identifier的普通類：#define V(x) struct x，這樣用戶可以用V(abc)來(lái)表示標(biāo)識(shí)符abc了。而且同一個(gè)標(biāo)識(shí)符只要用該宏生成一次（同名類只需聲明一次），之后的使用可以不再套個(gè)宏了。
• 用宏N(n)來(lái)表示number字面量n，用B(b)來(lái)表示boolean字面量b。

考慮到keyword、identifier、denotable value等都用類來(lái)表示，故使用繼承結(jié)構(gòu)來(lái)進(jìn)行區(qū)分：

• lang
  • keyword
    • lambda, iff, ...
  • value
    • pair_value
      • pair
    • atom_value
      • null_atom
        • null
      • number_atom
        • number
      • boolean_atom
        • boolean
      • procedure_atom
        • closure
        • primitive

所有沒(méi)有繼承自lang的類都視為identifier。

表達(dá)式求值

C++的模板可以進(jìn)行pattern match，因此求值函數(shù)大部分時(shí)候?qū)懫饋?lái)還是蠻輕松的，就不多說(shuō)了。

不過(guò)因?yàn)镃++模板運(yùn)算是pure functional的，就導(dǎo)致letrec的實(shí)現(xiàn)稍微費(fèi)了點(diǎn)心思。

r6rs和racket的letrec的是借助side effect（let/let*和set!的語(yǔ)法糖）實(shí)現(xiàn)的，而用C++模板實(shí)現(xiàn)side effect不太現(xiàn)實(shí)（讓我用state passing style來(lái)實(shí)現(xiàn)side effect的話還不如要side effect……）。

fix-point組合子倒是很好的解決方案，不過(guò)當(dāng)時(shí)我還沒(méi)有這方面知識(shí)……因此想了個(gè)稍顯古怪但還挺不錯(cuò)的解決方案：

• 將environment-frame分類為normal-frame和recurse-frame（前者表示lambda和let等普通的綁定生成的frame，后者表示letrec生成的frame）：
  • 每個(gè)frame都有一個(gè)前驅(qū)frame的引用，一個(gè)identifier以及其綁定的value。
  • 一個(gè)recurse-frame還有一個(gè)標(biāo)記來(lái)表示前驅(qū)frame是否和該frame由同一個(gè)letrec的bindings生成。
• 求值letrec的bindings時(shí)，按照l(shuí)et*的規(guī)則進(jìn)行，只是生成的frame為recurse-frame。
• 對(duì)environment進(jìn)行l(wèi)ookup時(shí)，若匹配到一個(gè)recurse-frame （其所在letrec所生成frame中的最下游frame為），且其綁定的value為包含一個(gè)closure ，綁定的environment為，則：
  • 若的前驅(qū)frame 為所綁定的frame的祖先，即，則返回一個(gè)新的closure ，只有綁定的environment與不同，為。
  • 否則，直接返回。

后記

謹(jǐn)以此紀(jì)念寒假的摸魚(yú)時(shí)光。

總結(jié)

以上是生活随笔為你收集整理的编程实现算术表达式求值_用魔法打败魔法：C++模板元编程实现的scheme元循环求值器...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。