跳轉至內容

1L_a/扁平化 1L_a 程式設計

來自華夏公益教科書,自由的教科書

建立 1L_a 程式的一種方法是先編寫相應的 Brainf*** 程式,然後將其轉換為 1L_a。因此,是時候引入一種新的語言,扁平化 1L_a,它介於 1L_a 和 Brainf*** 之間。

Brainf*** 及其最小化版本

[編輯 | 編輯原始碼]

如你所知,Brainf*** 是一種眾所周知的、一維的程式語言。與 1L_a 一樣,它也有 DP 和 IP,但 DP 只能在一行上移動,並且 DP 在字元陣列上移動,而不是位陣列上移動。它是圖靈完備的,並且有 8 個指令。以下是這些指令

指令 操作
> 將 DP 向右移動
< 將 DP 向左移動
+ 增加 DP 指向的記憶體單元的值
- 減少 DP 指向的記憶體單元的值
. 輸出 DP 指向的字元
, 輸入一個字元並將其儲存在 DP 所在的單元格中
[ 如果 DP 所在的單元格為 0,則跳過匹配的 ]
] 如果 DP 所在的單元格為 0,則跳回匹配的 [

然而,作為圖靈陷阱(只包含少數指令且圖靈完備的語言),8 個指令有點太多了。因此,我們可以建立具有更少指令的 Brainf*** 等效語言。

如果可以在 Brainf*** 中實現該語言中的每個指令,並且可以在該語言中實現 Brainf*** 中的每個指令,那麼我們稱該語言為 Brainf*** 等效語言。

很明顯,我們可以透過對位陣列(如 1L_a!)而不是字元陣列進行操作,將 Brainf*** 減少到 7 個指令,這樣 + 和 - 指令就變成一個指令:切換操作,表示為 @。可以使用強大的流程控制來模擬字元陣列,但這會很笨拙,我太懶了,不想這樣做。幸運的是,已經有人替我們做好了這件事。

Brainf*** The new language
--------- ----------------
>         >>>>>>>>>
<         <<<<<<<<<
+         >>>>>>>>[<]@>[@>]<<<<<<<<<[@]
-         @>>>>>>>>@[<@]>[>]<<<<<<<<<[@]
[         @[>>>>>>>>@[<@]>[>]<<<<<<<<<[@]>>>>>>>>[<]@>[@>]<<<<<<<<<@[@
]         >>>>>>>>>@<<<<<<<<<]>>>>>>>>>[<<<<<<<<<@>>>>>>>>>@]<<<<<<<<<]
.         >.<
,         >,<

我們稱這種語言為 Boolf***。由於 Brainf*** 是圖靈完備的,並且可以將任何 Brainf*** 程式轉換為 Boolf*** 程式,因此 Boolf*** 也是圖靈完備的。

華夏公益教科書