著作權申明：本文為博主窗戶(Colin Cai)原創，歡迎轉帖，如要轉貼，必須注明原文網址 http://www.cnblogs.com/Colin-Cai/p/11601046.html 作者：窗戶 QQ/微信：6679072 E-mail：[email protected]
詭異的代碼
看看這段代碼，很明顯，是列舉出100以內所有的質數，類似這樣的程式我們從學程式開始寫過很多，
再仔細看看，這種“語言”似乎有點像我們學過的其他語言，但似乎并沒見過，語法有那么一點點古怪？！
哦！看到了，原來是一段Python!
上面代碼的執行結果是
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
再想想，這段程式本身就是一堆函陣列成，全都是Python的函式，而且全都作為run函式的引數，甚至引數的引數這樣呼叫執行，好詭異的代碼！如果想想這個如何實作的，怕是有點費腦子吧，
面向程序的積木編程
目前少兒編程很流行，世面上有很多平臺，最有名的要數Scratch，其他很多的少兒教育平臺大都是模仿Scratch的思路，
上面是生成100以內質數的Scratch程式，在代碼堆里打滾的我們，即使從沒有見過Scratch，很快也會發現上述這樣的積木和我們的C語言、Python等常見的面向程序的程式看起來區別不是很大，于是，我們很快就可以使用Scratch進行編程，
Scrach抽象出了變數、各種算術運算，抽象除了程序式(命令式)編程所用到的順序、回圈、條件分支；甚至于Scratch還可以造積木，這一定程度上模擬了函式的意義，而且積木還可以遞回；但Scratch下沒有break、continue，這在一定程度下使得程式更難編了一些，另外，Scratch甚至模擬了訊息(或者說信號)觸發這樣的抽象，目的可能是為了使編程更加有趣味性，
理論上，積木編程當然也可以支持break、continue等，甚至可以goto，
最普通的實作
本文不打算花太多篇幅來進行前端設計的描述，盡管是一個很復雜的話題，不過設計思路可以簡單的說一下，
首先，我們為每一種積木建模，無論是Python還是JavaScript，我們都可以用class來描述，可以事先實作一個積木的基類，屬性里可以有積木的尺寸，圖片資訊等等，方法可以有包括圖片的加載，而具體的每一種積木則可以繼承于基類，當然，繼承里還可以再加一層，比如我們可以給積木分一個類，比如計算類、運行結構類、資料類、輸出類、輸入類……積木類里可能包含著其他的積木物件，比如對于運算來說，可能是別的兩個積木甚至更多的積木的參與，另外，每個積木也可以有一個resize或者reshape這樣的方法，因為形狀可能與它包含的其他積木物件是相關的，當然，還得需要move這樣的方法，
其次，我們要為當前所有的積木建模，可以抽象出block(用來表示一段積木拼成的程式)和block_list(用來表示所有的block)這樣的類，block也有split/joint等方法，用于block的分裂、拼接，
滑鼠拖動積木，可以對應于以上各種物件的操作，
block_list里記錄了所有的積木，以及積木與積木之間的連接關系，其實這些關系對于語言編譯、解釋來說，正是第一步parser希望得到的結果，現在這些資訊雖然不是通過語言編譯得到，而是通過前端操作得到，但是資訊都完備了，那么可以直接使用這種連接關系一步一步得到最終的結果，這種方式應該是最正常的一種方式，
使用開發語言
于是，最簡單的實作可以是各個block映射成當前所用編程語言，再使用編程語言的eval函式來實作，很多語言都有eval函式，所以這個幾乎不是什么問題，
比如假設我們的Scratch是用Python寫的，Scratch寫的質數程式可以挨個積木來翻譯，得到以下Python代碼：
var["i"] = 2 while not (var["i"]>10): var["k"] = sqrt(var["i"]) var["j"] = 2 while not ((var["i"]>var["j"]) or ((var["i"]%var["j"])==0)): var["j"] += 1 if (var["i"]>var["k"]): say(str(var["i"])+"是質數", 1) var["i"] += 1
然后再在Python里實作該實作的函式即可，比如這里的say函式，
以上的實作更為簡單直接，實際上的確世面上是有商業軟體是這么做的，特別是有的在線少兒編程教育，希望學生從積木編程過渡到具體計算機語言(一般還是Python、JavaScript)的學習，會給一個積木編程和具體計算機語言之間的對應，對于教育而言，這應該是一個挺不錯的想法，但是這個也有一定的問題，因為這種對應學習一般也會做語言到積木方向的映射，這個本身就要做對語言的parser，并且積木編程和具體語言編程很難做到完全合理的對應關系，特別是Python、JavaScript還支持面對物件、函式式編程，基本這些已經很難用積木的方式來表示了，
再者，也不好教授單步、斷點這樣的除錯手段，而對于上一種的方式，卻很容易做到支持這些除錯方式，
再造一種語言
像上面一樣，還是依次把積木映射成字串，只是，不用原生的程式語言，而是再造一種語言，
比如，上面的語言，可能被映射為以下這樣的形式：
until >(i,100) set(k,sqrt(i)) set(j,2) until or(>(j,k),=(%(i,j),0)) add(j,1) end if >(j,k) echo(concatent(i,"是質數")) end add(i,1) end
上面的形式看起來基本全是函式呼叫形式，雖然與普通的寫法不一樣，但是因為沒有了中綴運算式，語法決議全是函式，因為函式的表示非常簡單，基本上數括號就行，于是很容易區分函式名和各個引數，很明顯使用遞回很容易實作此處的函式呼叫，乃至自己寫一個堆疊來決議都很簡單，關鍵字此處只有until、if、end，從而可以很方便的做個解釋器，
特別的，既然自己給出語言的解釋器，自然可以很容易的添加單步、斷點，
當然，真的映射為帶中綴運算式的自然也可以，只是解釋器難度稍大一點罷了，
Scratch采用的是另外一種相似的方式，它將所有的資料用json來封裝，而描述上述代碼格式的是用如下一段陣列，
[["whenGreenFlag"], ["setVar:to:", "i", "2"], ["doUntil", [">", ["readVariable", "i"], "100"], [["setVar:to:", "k", ["computeFunction:of:", "sqrt", ["readVariable", "i"]]], ["setVar:to:", "j", "2"], ["doUntil", ["|", [">", ["readVariable", "j"], ["readVariable", "k"]], ["=", ["%", ["readVariable", "i"], ["readVariable", "j"]], "0"]], [["changeVar:by:", "j", 1]]], ["doIf", [">", ["readVariable", "j"], ["readVariable", "k"]], [["say:duration:elapsed:from:", ["concatenate:with:", ["readVariable", "i"], "是質數"], 1]]], ["changeVar:by:", "i", 1]]]]
這段json的決議方式可以與上述全函式的方式高度一致，自然也是高度一致的處理手段，
當然，我們也可以類似下面這樣使用中綴運算式
until i>100 k=sqrt(i) j=2 until j>k or i%j==0 j+=1 end if j>k echo(i,"是質數") end i+=1 end
中綴運算式涉及到運算子的優先級問題，處理起來相對比較復雜一些，當然，我們也可以使用LEX/YACC來寫parser，這樣會方便很多，linux下LEX一般使用flex，YACC一般使用bison，不過既然這里的語言基本上只是做中間語言來使用，那么做成這樣基本是沒有必要，
圖計算
細致的讀者應該可以想到，既然為圖形界面建模的程序中，所有的積木之間的關系已經是一個圖結構，而編程語言的編譯，目的就是為了把編程語言變換成圖結構，既然圖結構現在已經有了，生成中間代碼看上去不過是多轉了一道彎而已，那我們是不是可以利用這個圖結構直接計算呢?
實際上，當然，我們是完全可以通過圖結構來做計算的，例如如下這樣的流程圖，我們的資料結構中蘊含著流程圖的每一條邊(圖是有向圖，從而邊有方向)以及節點意義，程式員顯然都有直接計算的直覺，
資料結構示意大致如下：
Node:
A : i<=1
B(Switch) : i<100
C : 列印i
D : i<=i+1
Entrance:
A
Edge:
A->B
B(False)->C
C->D
D->A
B(True)->End
內部DSL式建構
所謂內部DSL，則是以宿主語言為基礎構建一種屬于自己的特定語言，這就意味著，新的語言實際上依然是宿主語言，只是在宿主語言基礎上構造了很多其他的限制東西，比如讓其看起來非常類似于完全獨立的語言，這是一種完全不同于前面設計的方法的設計，
而我們也都知道，Lisp特別擅長干設計DSL的事情，特別是Scheme，有多種手段可以設計，比如我們可以用宏(Macro)，Lisp的宏遠比C語言的宏要強大太多，雖說宏是文字替換，但Lisp的宏支持遞回，我們完全可以用Lisp的宏來做反復遞回替換，于是我們可以用非常靈活的方式替換我們的語法樹，甚至語法樹可以用宏被替換的“面目全非”，Scheme還有神一樣的continuation，大部分DSL可以設計為面向程序的方式，而continuation就可以很方便的為面向程序的流控制來建模，以上兩個就已經可以讓Scheme為所欲為了，記得以前網上有個QBasic的Scheme實作就是利用的這個，而我們當然也可以再來考慮更一般的Scheme程式設計，利用算子中的閉包傳遞，我們一樣可以設計出好的內部DSL，
我們這里并不打算用Scheme或者別的Lisp來講解，這里依然用我們常用的宿主語言來，比如Python，Python其實是一種抽象度極高的語言，它比Scheme少的東西在我看來也就宏和continuation，再有就是尾遞回沒有優化，
我們考慮以下這樣的一段程式，
repeat 3 ( repeat 4 ( display("=") ) newline() display("test") newline() ) display("The end") newline()
雖然，也許我在此并沒有說明這段程式的意思，身經百戰的你應該早已想出本程式的輸出可能是
====
test
====
test
====
test
The end
這里repeat n (...)就代表著把括號里面的內容執行n遍，而display函式則是把后面的內容列印出來，newline函式就是換行，這是一個最簡單的DSL了，但是在這個原理的基礎上我們其實可以做比如畫畫之類的程式，因為一般意義上的教孩子編程所用的畫畫不會構造過于繁瑣的圖形，從一開始就可以思考出整體如何畫，于是利用回圈就可以了，而不需要用到判斷(然而復雜意義上的圖畫可能不是這樣，可能是不斷的根據當前所畫內容決定之后所添加內容，這可能就得需要判斷)，
Scratch中畫圖程式示例如下：
結果就是畫個正六邊形如下：
和上述的DSL基本是一致的，
但既然是想在Python上做內部DSL，我們就得想一種方法嵌入到Python中，最自然的就是將之前的程式改寫就是如下：
run( repeat(3, repeat(4, display("=") ), newline(), display("test"), newline() ), display("The end"), newline() )
既然沒有Scheme的Macro和Continuation，Python以上的方式也就是函式呼叫方式，只是把格式排了一下，加上縮進，從而比較容易看出語意，
接下去考慮的就是具體如何實作：
我們先從display開始，第一個直覺是display和Python的print是一樣的，
于是我們就這樣設計了：
def display(s): print(s)
看起來我們平常的單個display都OK了，然而很快我們就意識到如同repeat(2, display("test"))這樣的程式無法正常作業，因為display列印之后并沒有產生別的影響，repeat自然無從知道display的動作，從而無法把它的動作復制，
從而display需要一點影響才能正常作業，一個方法就是通過變數傳遞出來，這是一個有副作用的手段，很多時候應該盡量去避免，于是，我們只考慮從display回傳值來解決問題，也就是display函式需要回傳display和display的引數的資訊，newline也需要回傳包含newline的資訊，repeat也要回傳repeat以及它所有引數的資訊，
最容易想到的當然是用字串來表示上述資訊，
def display(a): return "display " + a def newline(): return "newline"
然后我們再接著寫repeat，
from functools import reduce def repeat(times, *args): s = "repeat " + str(times) + '\n(\n' for arg in args: s += reduce(lambda a,b:a+b,map(lambda x:' '+x+'\n',arg.split('\n'))) s += ")" return s
我們運行一下
print(repeat(2, display("test")))
得到
repeat 2
(
display test
)
突然意識到，這樣不對啊，如此繼續下去，run函式完全成了一個語言的解釋器，這和我們之前討論的完全一樣，那我們就不回傳字串，回傳tuple、list之類的資料結構呢？換湯不換藥，還是那么回事，沒有什么新意，
閉包構建
回避不了回傳值要包含函式和函式引數的問題，只是，我們可以采用別的方式來做到，也就是閉包，
所謂閉包，是一種算子，把函式的引數資訊封進另外一個函式，最侄訓傳這個函式，以下舉一個簡單的例子就應該很明白了，
def addn(n): def f(x): return x+n return f
或者用lambda，上述寫成
addn = lambda n:lambda x:x+n
使用的時候，比如我想得到一個函式，回傳輸入數得到加1的結果，那么addn(1)就是我所需要的函式，
addn就是一個閉包，
按照這個思路，我們先想想run函式如何寫，run的引數是一系列按先后順序要發生動作的函式，那么run只是按順序執行這些函式，
def run(*args): for arg in args: arg()
然后，我們試圖撰寫display和newline，代碼可以如下：
def display(s): def f(): print(s, end="") return f def newline(): def f(): print("") return f
我們發現使用run、display、newline可以讓運行結果完全隨我們的想法，
接下來就是repeat，
比如repeat(3, display("a"), newline()), 實際上應該是回傳一個函式其執行結果是回圈三次執行display("a")和newline()回傳的函式，雖然開始有點拗口，但代碼并不太復雜：
def repeat(times, *args): def f(): for i in range(times): for arg in args: arg() return f
于是，到此為止，最簡單的只包含repeat、display、newline的DSL就已經完成了，
我們運行設計之初的代碼，的確得到了想要的結果，
升級思路
上面的這個DSL實在太簡單了，它雖然有回圈，但是沒有引入變數，自然也就沒有引入運算，也不會有條件分支，
那么一切都從變數支持開始，變數意味著面向程序的程式在運行的程序中，除了程式當前運行的位置之外，還有其他的狀態，我們之前repeat、display、newline回傳的函式都是沒有引數的，這樣除了創造有副作用的函式，否則無法攜帶其他狀態轉變的資訊，
于是我們可以考慮用一個字典來代表程式中所有變數的狀態，然后讓所有的閉包最終都回傳帶一個以這樣的表示變數的字典為引數的函式，
于是這種情況下，run函式應該這樣寫：
def run(*args): var_list={} for arg in args: var_list = arg(var_list)
上面的run_list就是我們所需要的代表所有變數的字典，
在此基礎上，我們可以構造用來設定變數的函式和獲得變數的函式：
def set_value(k, v): def f(var_list): var_list[k] = to_value(v, var_list) return var_list return f def get_value(k): return lambda var_list : var_list[k]
重寫display和newline，回傳函式的引數中當然應該添加var_list，雖然兩者不是與變數直接關聯，但也似乎只需要保證把var_list直接回傳，以確保run以及別的閉包呼叫的正確即可，
def display(s): def f(var_list): print(s, end="") return var_list return f def newline(): def f(var_list): print("") return var_list return f
然而，我們實際上并未細想，display后面接的如果是常量的話，上述的實作并沒有錯誤，但如果不是常量呢？比如display(get_value("i"))，get_value("i")是一個函式，上述的print顯然不能把希望列印的值列印，
于是我們按理應該在此判斷一下display的引數s，如果是函式，應該先求值一下再列印，
def display(s): def f(var_list): if type(s)==type(lambda x:x): print(s(var_list),end="") else: print(s, end="") return var_list return f
上述判斷s的型別是函式，也可以使用
from types import FunctionType
isinstance(a, FunctionType)
上述我們可以測驗一段代碼
run( set_value("i", 1), repeat(3, display(get_value("i")), newline() ) )
運行結果是
1
1
1
與我們想象的一致，從而基本驗證其正確性，
當然，這還只是拋磚引玉一下，并沒有涉及到計算、條件分支、條件回圈以及continue、break，乃至于goto，甚至于變數作用域、函式等，甚至于，在這個模式上我們甚至還可以加上除錯模式，加入單步、斷點等除錯手段，
對于具體做法此處不再展開，讀者可以自行思考，
開頭的程式
引入的東西相對于文中多一些，我們現在終于也有了一點眉目，程式代碼詳細如下面檔案中所示，恕不細說，
少兒編程教育的思考
一個致力于少兒編程教育的朋友跟我聊天，說到新接手的一個班，雖然之前都在另一少兒編程平臺下學習了近一年，但卻連最基本的編程邏輯都不懂，雖然少兒編程教的一般是面向程序的編程，可是班上沒有一個小朋友可以理解流程圖這個東西，質數判斷本應是個很簡單的問題(當然，我們先不深入的看待此問題)，然而甚至于他在班上把詳細的程序描述清楚了，小朋友也會按照程序用紙筆來判斷，可是一上程式全班沒有一個人可以寫出來，這位朋友很生氣，覺得連流程圖都不納入教學體系是個很過分的事情，因為流程圖是面向程序編程的基本抽象，小朋友最終連這么簡單的程式都編不出來只能說明之前的教學簡直就是應付，甚至欺騙，
而我倒是跟他大談或許教學目的該為如何教會小朋友一步步學會自己制作少兒編程工具，當然可能是針對對編程非常感興趣的孩子，現實是，這樣的孩子少，可以這樣教的老師也少，從而無法產生合理的商業利益，于是，如何教好更多的孩子才是他所認為的教育之重，
我一向認為老師教學生，不是復制自己，而是教會學生思考的方法，孩子學會思考的方法遠比手把手的做個老師的克隆更強，獨立做出一個程式，即使再爛，其價值遠超過老師全力指導下寫的高深程式，
于是，還是應該把目光放回到我們目前教學的工具上，如何讓孩子真正的理解程式，倒未必一直要從純數學出發，也不需要什么高深演算法，什么函式式編程，先掌握面向程序的精髓吧，讓孩子可以自由的產生想法，再由想法變成代碼，時機成熟了，再告訴孩子，某些東西可以有，比如演算法，比如各種編程范式，當年日本圍棋，超一流棋手的搖籃木谷道場，老師對于學生不按老師的想法行棋都是要懲罰的，然而六大超一流棋手風格各異，并沒有按照老師的手段來行棋，換句話說，教育中，傳承是根，但挖掘潛力才更為重要，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/137173.html
標籤：其他
上一篇：C語言雙指標之盛最多水的容器