在之前的《那些奇奇怪怪的編程語言》一文里，我介紹了 Esolang 的概念，以及幾種 Esolang 的例子。當然，這種事情自己動手更有意思。于是我也設計了一種編程語言，叫做 DipDup。
DipDup 是一種基于堆棧的編程語言。它的設計參考了另外兩種基于堆棧的編程語言：Underload 和 Joy。
Underload 是一種極簡主義的編程語言，由 Ais523 設計于2006年。它只有七條指令（或者是八條，如果把列表也算作一種指令的話）。除了表示輸出的S之外，都是一些簡單的堆棧操作。Underload 是圖靈完備的。如果你設計了一種基于堆棧的編程語言，想要證明它是圖靈完備的，只需要用它實現(xiàn)一下 Underload 里的這些指令就行了。
Joy 由 Manfred von Thun 設計于2001年。它不是 Esolang。除了基于堆棧（確切地說，是 Concatenative，這個詞不知道怎么翻譯）以外，它沒有太多奇怪的地方，一門普通的編程語言該實現(xiàn)的功能它都有實現(xiàn)。不過 Manfred von Thun 設計這門語言主要是出于學術用途，實際使用的人不多。
DipDup 可以看作是 Joy 的一個子集。我從 Joy 的兩百多條指令當中選取了四條：dip，dup，pop 和 cons，分別把它們記作 ^，_，! 和 :。DipDup 這個名字就是從這里來的。
DipDup 是一種基于堆棧的語言，它的每一條指令都可以看作是一個把堆棧映成堆棧的函數(shù)。把幾條指令寫成一串，相當于是函數(shù)的復合，得到的依然是一個把堆棧映成堆棧的函數(shù)。
四條指令的介紹如下：
dup
dup指的是 duplicate，復制。如果原先的堆棧是...ba（堆棧的頂端寫在右邊），執(zhí)行操作后堆棧變成...baa。在 DipDup 當中，dup寫成_。pop
不同于別的編程語言里的pop，它把堆棧頂上的東西彈出之后就扔掉了，不會返回也不會輸出。如果原先的堆棧是...ba，執(zhí)行操作后堆棧變成...b。在 DipDup 當中，pop寫成!。cons
類似于 Lisp 里的cons和 Haskell 里的:。如果原先的堆棧是...b[a]，執(zhí)行操作后堆棧變成...[ba]。在 DipDup 當中，cons寫成:。dip
這個有點復雜，不過它是 DipDup 里最關鍵的一條指令。如果原先的堆棧是...cb[a]，它會先彈出[a]和b，然后把[a]當成一個程序作用在堆棧...c上，最后把b壓回堆棧。在 DipDup 當中，dip寫成^。
除了四條指令之外，還有列表。一個列表就是把若干個指令和列表寫成一串，中間不加任何分隔符，然后用方括號 [ 和 ] 括起來。比如說，[] 就是一個列表，[[_:]_:] 也是一個列表。在程序中，列表可以看作是一個指令，其作用是把這個列表本身壓入堆棧。一個列表也可以看作是一段程序（是的，代碼即數(shù)據(jù)），或者一個函數(shù)，可以作用在堆棧上（比如說，借助 dip 指令）。
初始的堆棧由無窮多個空列表組成——采用無窮堆棧是因為我懶得處理堆棧為空的情況。在程序運行完了之后，輸出的是堆棧最頂上的東西。
舉個最簡單的例子，這是一個 Quine，它輸出的結果和程序本身一模一樣：
[_:]_:
然后問題來了：DipDup 是圖靈完備的嗎？
前面說過，要證明一個基于堆棧的編程語言是圖靈完備的，只需要用它實現(xiàn)一下 Underload 里的全部指令就行了。
除了列表之外， Underload 只有7種指令。其中 S表示輸出，對圖靈完備與否沒有影響；: 就相當于 DipDup 里的 _（dup）；! 就相當于 DipDup 里的 !（pop）；a 表示用括號把堆棧最頂上的東西括起來，這個在 DipDup 里用 []: 就能實現(xiàn)；~ 表示交換堆棧最頂上的兩個東西，相當于 Joy 里的 swap，這個在 DipDup 里可以用 []:^ 實現(xiàn)；^ 表示彈出堆棧最頂上的東西（必須是個列表），并把它作為一個程序作用在剩下的堆棧上，相當于 Joy 里的 i，這個在 DipDup 里可以用 []^! 或者 _^! 實現(xiàn)。
于是，我們只剩下一條指令沒有實現(xiàn)：*。它表示的是彈出堆棧最頂上的兩個東西（兩個都是列表；事實上，無論是 Underload 還是 DipDup，堆棧里的東西都只有列表），把它們串接成一個列表，再壓回堆棧。如果原先的堆棧是 ...[b][a]，執(zhí)行操作后堆棧變成 ...[ba]?？雌饋砼c DipDup 里的 cons 很像。但遺憾的是，這個用 DipDup 是實現(xiàn)不了的。
不過，我們可以換一條思路，先來看看 Underload 的圖靈完備性是怎樣證明的。Esolang Wiki 里給出的辦法是證明所有的 Unlambda 代碼都可以直接翻譯成 Underload。Unlambda 是一種基于組合子邏輯的 Esolang，它是圖靈完備的，因此 Underload 也是圖靈完備的。
因此，我們也可以試著把 Unlambda 翻譯成 DipDup。事實上，不需要翻譯整個 Unlambda，只需要實現(xiàn) S 和 K 這兩個組合子就夠了（當然，還需要用上 Underload 里的 ^，也就是 DipDup 里的 _^!）。它們的實現(xiàn)不算復雜：
-
K組合子
[[[!]^]:]
-
S組合子
[[[[[_]^^]^_^!_^!]::]:]
具體的推導我就不寫了。
最后附上用 Haskell 寫的解釋器：
import System.Console.Haskeline
import Text.ParserCombinators.ReadP
data Term = C Char | E Expr
type Expr = [Term]
instance Show Term where
show (C c) = [c]
show (E e) = "[" ++ show e ++ "]"
showList = (++) . concatMap show
instance Read Term where
readsPrec = const $ readP_to_S readTerm
readList = readP_to_S readExpr
readTerm :: ReadP Term
readTerm = (C <$> satisfy (`notElem` "[]")) +++ (E <$> between (char '[') (char ']') readExpr)
readExpr :: ReadP Expr
readExpr = many readTerm
data Stack = Expr :-: Stack
infixr 5 :-:
initStack :: Stack
initStack = [] :-: initStack
top :: Stack -> Expr
top (x :-: _) = x
type Func = Stack -> Stack
evalTerm :: Term -> Func
evalTerm (E e) = (e :-:)
evalTerm (C '^') = dip
evalTerm (C '_') = dup
evalTerm (C '!') = pop
evalTerm (C ':') = cons
evalTerm _ = id
evalExpr :: Expr -> Func
evalExpr = flip . foldl $ flip evalTerm
eval :: Expr -> Expr
eval = top . flip evalExpr initStack
dip :: Func
dip (x :-: y :-: s) = y :-: evalExpr x s
dup :: Func
dup (x :-: s) = x :-: x :-: s
pop :: Func
pop (_ :-: s) = s
cons :: Func
cons (x :-: y :-: s) = (E y : x) :-: s
rep :: String -> String
rep input = case [x | (x, "") <- reads input] of
[x] -> show $ eval x
_ -> error "parse error"
repl :: InputT IO ()
repl = do
minput <- getInputLine "> "
case minput of
Nothing -> return ()
Just input -> do
catch (outputStrLn $ rep input) $ \e -> outputStrLn $ show (e :: SomeException)
repl
main :: IO ()
main = runInputT defaultSettings repl
