Translate


2020/2/3

怪怪的程式語言名稱:Brainfuck

若您覺得文章寫得不錯,請點選網誌上的廣告,來支持小編,謝謝。

最近在 ptt Gossiping 版的jserv 的一篇回文
https://www.ptt.cc/bbs/Gossiping/M.1555612071.A.14C.html

得知 Brainfuck 也是個程式語言,於是小編自己也來寫一個 Brainfuck interpreter。先來了解 Brainfuck 的指令吧。

Brainfuck指令說明
============底下文字從 https://en.wikipedia.org/wiki/Brainfuck 節錄出來:============
CharacterMeaning
>increment the data pointer (to point to the next cell to the right).
<decrement the data pointer (to point to the next cell to the left).
+increment (increase by one) the byte at the data pointer.
-decrement (decrease by one) the byte at the data pointer.
.output the byte at the data pointer.
,accept one byte of input, storing its value in the byte at the data pointer.
[if the byte at the data pointer is zero, then instead of moving the instruction pointer forward to the next command, jump it forward to the command after the matching ] command.
]if the byte at the data pointer is nonzero, then instead of moving the instruction pointer forward to the next command, jump it back to the command after the matching [ command.
brainfuck指令與C語言對照表:
brainfuck commandC equivalent
(Program Start)char array[30000] = {0};
char *ptr=array;
>++ptr;
<--ptr;
+++*ptr;
---*ptr;
.putchar(*ptr);
,*ptr=getchar();
[while (*ptr) {
]}
============以上文字從 https://en.wikipedia.org/wiki/Brainfuck 節錄出來:============
其中,[ 與 ] 這兩個指令需要注意有巢狀的情況,而測試的 Brainfuck 程式碼如下:

hello.bf (https://github.com/pablojorge/brainfuck/blob/master/programs/hello.bf)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
+++++ +++++             initialize counter (cell #0) to 10
[                       use loop to set the next four cells to 70/100/30/10
    > +++++ ++              add  7 to cell #1
    > +++++ +++++           add 10 to cell #2 
    > +++                   add  3 to cell #3
    > +                     add  1 to cell #4
    <<<< -                  decrement counter (cell #0)
]                   
> ++ .                  print 'H'
> + .                   print 'e'
+++++ ++ .              print 'l'
.                       print 'l'
+++ .                   print 'o'
> ++ .                  print ' '
<< +++++ +++++ +++++ .  print 'W'
> .                     print 'o'
+++ .                   print 'r'
----- - .               print 'l'
----- --- .             print 'd'
> + .                   print '!'
> .                     print '\n'

費式數列 fibonacci.bf (https://github.com/pablojorge/brainfuck/blob/master/programs/fibonacci.bf)
1
2
3
4
5
6
7
8
9
>++++++++++>+>+[
    [+++++[>++++++++<-]>.<++++++[>--------<-]+<<<]>.>>[
        [-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-
            [>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>>
    ]<<<
]
This program doesn't terminate; you will have to kill it.
Daniel B Cristofani (cristofdathevanetdotcom)
http://www.hevanet.com/cristofd/brainfuck/

圓周率 pi.bf (https://copy.sh/brainfuck/prog/yapi.b)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
[ yet another pi calculation program in bf

  Just like for pi16.b the accuracy of the result depends on the cellsize:
 
   - using  8 bit cells causes an overflow after 4 digits
   - using 16 bit cells causes an overflow after 537 digits
   - using 32 bit cells causes an overflow after several millions of digits
  
  It's about ~38 times shorter than pi16.b, ~364 times faster and works with
  not-wrapping (bignum) implementations. 
 
  by Felix Nawothnig (felix.nawothnig@t-online.de) ]

>  +++++ +++++ +++++ (15 digits)

[<+>>>>>>>>++++++++++<<<<<<<-]>+++++[<+++++++++>-]+>>>>>>+[<<+++[>>[-<]<[>]<-]>>
[>+>]<[<]>]>[[->>>>+<<<<]>>>+++>-]<[<<<<]<<<<<<<<+[->>>>>>>>>>>>[<+[->>>>+<<<<]>
>>>>]<<<<[>>>>>[<<<<+>>>>-]<<<<<-[<<++++++++++>>-]>>>[<<[<+<<+>>>-]<[>+<-]<++<<+
>>>>>>-]<<[-]<<-<[->>+<-[>>>]>[[<+>-]>+>>]<<<<<]>[-]>+<<<-[>>+<<-]<]<<<<+>>>>>>>
>[-]>[<<<+>>>-]<<++++++++++<[->>+<-[>>>]>[[<+>-]>+>>]<<<<<]>[-]>+>[<<+<+>>>-]<<<
<+<+>>[-[-[-[-[-[-[-[-[-<->[-<+<->>]]]]]]]]]]<[+++++[<<<++++++++<++++++++>>>>-]<
<<<+<->>>>[>+<<<+++++++++<->>>-]<<<<<[>>+<<-]+<[->-<]>[>>.<<<<[+.[-]]>>-]>[>>.<<
-]>[-]>[-]>>>[>>[<<<<<<<<+>>>>>>>>-]<<-]]>>[-]<<<[-]<<<<<<<<]++++++++++.

自然數 e.bf (http://www.hevanet.com/cristofd/brainfuck/e.b)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
[e.b -- compute e
(c) 2016 Daniel B. Cristofani
http://brainfuck.org/]

>>>>++>+>++>+>>++<+[  
  [>[>>[>>>>]<<<<[[>>>>+<<<<-]<<<<]>>>>>>]+<]>-
  >>--[+[+++<<<<--]++>>>>--]+[>>>>]<<<<[<<+<+<]<<[
    >>>>>>[[<<<<+>>>>-]>>>>]<<<<<<<<[<<<<]
    >>-[<<+>>-]+<<[->>>>[-[+>>>>-]-<<-[>>>>-]++>>+[-<<<<+]+>>>>]<<<<[<<<<]]
    >[-[<+>-]]+<[->>>>[-[+>>>>-]-<<<-[>>>>-]++>>>+[-<<<<+]+>>>>]<<<<[<<<<]]<<
  ]>>>+[>>>>]-[+<<<<--]++[<<<<]>>>+[
    >-[
      >>[--[++>>+>>--]-<[-[-[+++<<<<-]+>>>>-]]++>+[-<<<<+]++>>+>>]
      <<[>[<-<<<]+<]>->>>
    ]+>[>>>>]-[+<<<<--]++<[
      [>>>>]<<<<[
        -[+>[<->-]++<[[>-<-]++[<<<<]+>>+>>-]++<<<<-]
        >-[+[<+[<<<<]>]<+>]+<[->->>>[-]]+<<<<
      ]
    ]>[<<<<]>[
      -[
        -[
          +++++[>++++++++<-]>-.>>>-[<<<----.<]<[<<]>>[-]>->>+[
            [>>>>]+[-[->>>>+>>>>>>>>-[-[+++<<<<[-]]+>>>>-]++[<<<<]]+<<<<]>>>
          ]+<+<<
        ]>[
          -[
            ->[--[++>>>>--]->[-[-[+++<<<<-]+>>>>-]]++<+[-<<<<+]++>>>>]
            <<<<[>[<<<<]+<]>->>
          ]<
        ]>>>>[--[++>>>>--]-<--[+++>>>>--]+>+[-<<<<+]++>>>>]<<<<<[<<<<]<
      ]>[>+<<++<]<
    ]>[+>[--[++>>>>--]->--[+++>>>>--]+<+[-<<<<+]++>>>>]<<<[<<<<]]>>
  ]>
]

This program computes the transcendental number e, in decimal. Because this is
infinitely long, this program doesn't terminate on its own; you will have to
kill it. The fact that it doesn't output any linefeeds may also give certain
implementations trouble, including some of mine.

C語言程式碼:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <stdlib.h>
#include <stdio.h>

static int cells[30000] = {0};
unsigned int dp = 0;      // data pointer

void bfExe(char *cmds)
{
    int i, nestedLoop, curCmd;

    for(i = 0; cmds[i] != 0; i++)
    {
        curCmd = cmds[i];
        switch(curCmd)
        {
        case '>':
            ++dp;
            break;
        case '<':
            --dp;
            break;
        case '+':
            ++cells[dp];
            break;
        case '-':
            --cells[dp];
            break;
        case '.':
            putchar(cells[dp]);
            break;
        case ',':
            cells[dp] = getchar();
            break;
        case '[':
            if(!cells[dp])
            {
                nestedLoop = 1;
                while(nestedLoop)
                {
                    i++;
                    if(cmds[i] == '[') nestedLoop++;
                    if(cmds[i] == ']') nestedLoop--;
                }
            }
            break;
        case ']':
            if(cells[dp])
            {
                nestedLoop = 1;
                while(nestedLoop)
                {
                    i--;
                    if(cmds[i] == ']') nestedLoop++;
                    if(cmds[i] == '[') nestedLoop--;
                }
            }
            break;
        }
    }
}

int main(int argc, char* argv[]) {
    if(argc < 2) exit(1);
    FILE *f = fopen(argv[1], "r");
    fseek(f, 0, SEEK_END);
    long fsize = ftell(f);
    fseek(f, 0, SEEK_SET);

    int *bfCmd = malloc(fsize + 1);
    fread(bfCmd, 1, fsize, f);
    fclose(f);
    bfCmd[fsize] = 0;

    bfExe(bfCmd);
    return 0;
}

而在 stackoverflow 上有高手寫了底下的C程式碼(https://stackoverflow.com/questions/9147357/brainfuck-interpreter):
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
#include <stdlib.h>
char m[9999], *n[99], *r = m, *p = m + 5000, **s = n, d, c;
main()
{
   for (read(0, r, 4000); c = *r; r++)
          c - ']' || (d > 1 ||
          (r = *p ? *s : (--s, r)), !d || d--), c - '[' || d++ ||
          (*++s = r), d || (*p += c == '+', *p -= c == '-', p += c == '>',
          p -= c == '<', c - '.' || write(2, p, 1), c - ',' || read(2, p, 1));
}

C語言果然很特別!!!

底下為其他語言實作出來的 brainfuck interpreters 與模擬實驗資料。
https://github.com/pablojorge/brainfuck

2020/1/15

簡易 Python 問答機器人(Simple Python QA Robot)

若您覺得文章寫得不錯,請點選網誌上的廣告,來支持小編,謝謝。

本篇文章會以一個簡易問答機器人來了解底下的 Python 相關知識:變數、字串、函數、字典、if/if else/if elif else 判斷式、for 迴圈。


聊天機器人程式架構
儲存問題與答案的 quiz 串列。
兩個主要函數:sendMsg 函數、readMsg 函數。

變數(Variables)
底下用非很精準的解釋,畢竟變數和容器還是不一樣的觀念
變數可看成容器,而容器有很多種,例如罐子、紙箱、寶特瓶、水桶、背包、鉛筆盒等。

但若是有30個人都帶著一模一樣的罐子容器時,那要怎麼辨別這個罐子是誰的啊?!
所以就給這些罐子一個獨一無二的名稱!開始來命名囉!

「豬頭罐子」、「空罐子」、「軟罐子」、「硬罐子」、「無敵罐子」、「我的罐子」、「你的罐子」、「不說話罐子」、「機器人罐子」、「腳罐子」、「黑罐子」、「紅罐子

可以亂命名嗎?!好像不給個規則會產生一些怪怪的名稱。在程式語言裡,變數是有命名規則的,大多的程式語言通常會有底下兩個規則:
  • 第一個字必須是英文字母(大小寫字母皆可)或是底線字元「_」不可以是數字或其他符號
  • 第一個字之後的其他字必須是英文字母(大小寫字母皆可)、底線字元「_」或是數字不可以使用其他符號

而 Python 提供的容器(Data Types)有底下幾種:
  • 文字容器(Text Type):字串(string)。
  • 數字容器(Numeric Types):整數(int)、浮點數(float)、複數(complex)。
  • 序列容器(Sequence Types):串列(list)、元組(tuple)、range(小編不知道要如何翻成中文)。
  • 映射容器(Mapping Type):字典(dict)。
  • 集合容器(Set Types):可變集合(set)、不可變集合(frozenset)。
  • 布林容器(Boolean Type):布林(bool)。
  • 二元容器(Binary Types):位元組(bytes)、位元組陣列(bytearray)、memoryview(小編不知道要如何翻成中文)。。
Python 變數的使用方式如下:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
# 宣告一個變數 n ,並將 n 設成整數 3
n = 3

# 宣告一個變數 f ,並將 f 設成浮點數 3.3
f = 3.3

# 宣告一個變數 c ,並將 c 設成複數 1 + 2j
c = 1 + 2j

print(n)  # 印出變數 n 的值
print(f)  # 印出變數 f 的值
print(c)  # 印出變數 c 的值


函式(Functions) 此部分可參考 Python 函數(Functions) 一文
在解釋函式是什麼之前,先來看看Scratch程式設計裡的一些積木:
在Scratch裡,每一個積木都是一個函式,而且都已被分類了,例如上圖中的動作外觀音效等積木。讀者也可以在 code.org 玩玩Artist https://studio.code.org/s/course3/stage/5/puzzle/1 與 Bee https://studio.code.org/s/course3/stage/6/puzzle/1,幫助了解什麼是函式。Python 函式的樣子如下:
1
2
3
4
5
# 函式的框架
def yourFunction(para1, para2):
    '''
        your function code is here
    '''

1
2
3
4
def 函數名稱( 參數列 ):
   "函數說明"
   程式碼
   return [運算式(Expression)]

例子:
1
2
3
4
5
6
7
8
9
# 兩數的加法
def sumWith(a, b):
    return (a+b)

# 宣告變數 a ,並將呼叫 sumWith(3, 4) 的結果 (3 + 4) 指定給變數 a。
a = sumWith(3, 4)

# print 也是函式,印出變數 a 的內容
print(a)

字串(String)
Python 的字串是以單引號 (single quotation marks) 或是雙引號 (double quotation marks),所包圍的文字。

而多行字串可用三個雙引號來表示,底下皆為 Python 的字串範例:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
'這是單引號字串'
"這是雙引號字串"
s = "How are you?"
a = 'Fine, and you?'

"""
這是
多行
字串
"""


字典(Dictionary)
下圖為 Dictionareis 的示意圖:


Python 字典範例:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
# 建立英漢字典對照表
d = {
    'python': '蟒蛇',
    'ruby': '紅寶石',
    'dictionary': '字典',
    'English': '英文',
    'Chinese': '中文',
    'apple': '蘋果',
    'dog': '狗',
    'cat': '貓',
    'sun': '太陽'
    }

if/if else/ if elif else 判斷式
判斷式 if 的語法。
if 語法
1
2
if 判斷條件:
  程式碼...

if/else 語法
1
2
3
4
if 判斷條件:
  程式碼...
else:
  程式碼...

if/elif/else 語法
1
2
3
4
5
6
if 判斷條件1:
  程式碼...
elif 判斷條件2:
  程式碼...
else:
  程式碼...

Python判斷式範例:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
# 考試成績結果判斷
holanScore = 59
if holanScore < 60:
  print("版主考試不及格啦!")

holanScore = 60
if holanScore >= 60:
  print("版主考試及格了!")
else:
  print("版主考試不及格啦!")

holanScore = 61
if holanScore >= 90:
  print("版主不就好棒棒!!!")
elif holanScore >= 70:
  print("版主考試及格啦!")
else:
  print("版主考試有通過嗎?")

串列(List)  此部分可參考 Python 串列(或陣列?)結構 一文。
先來認識什麼是串列。下圖為 Lists 的示意圖:

  

這是什麼意思呢?請繼續看下圖
請把串列先想成有很多格子的容器,每個格子都有自己的編號(又稱索引值),但此容器有個限制條件:每一個格子只能放一樣東西。所以上圖中,第 0 格放了什麼?第 3 格放了什麼?第 9 格放了什麼?OK,了解此概念後,來看一下 Python串列的語法:[expression, ... ]。先這樣子解讀「把東西放在中括號[]內,用 , 逗號(是英文的逗號)來區隔每一個東西。」所以上圖就可以寫成:
myTreasure = ['dog', 'cat', 'penguin', 'sun', 'mouse', 'tree', 'rose', 'diamond', 'snake', 'chair']


串列的每一格當成是哆啦A夢的百寶袋,因為 Python 串列的每一格就像百寶袋一樣,雖然一格只能放一樣東西,但此東西是可以是已經裝好東西的一個容器



for迴圈(for loop) 此部分可參考 Python 重複式迴圈語法一文
for loop 語法如下:
1
2
3
4
5
for 變數 in 序列:
    程式碼第1行
    程式碼第2行
    ...etc
    程式碼第n行

for loop範例:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
import string
# 列出小寫英文字母
for lowCase in string.ascii_lowercase:
    print(lowCase, end=',')

print()

# 列出大寫英文字母
for upCase in string.ascii_uppercase:
    print(upCase, end=',')

計分功能(Scoring)
在這個程式裡,使用了 cnt 變數來記錄玩家答對了幾題。

範例程式:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
def sendMsg(msg):
    print(msg)

def readMsg():
  return input()

welcome = "嗨!您好!接下來會問您幾個腦筋急轉彎的問題。 " \
          "相信您一定可以表現很好。"
sendMsg(welcome)

quiz = [
    {
  "question": "台灣現任總統是誰?",
  "answer": "蔡英文"
 },
 {
  "question": "什麼地方的路最窄",
  "answer": "冤家路窄"
 },
 {
  "question": "書店買不到什麼書?",
  "answer": "遺書"
 },
 {
  "question": "借什麼可以不還?",
  "answer": "借過"
 },
 {
  "question": "右手永遠抓不到什麼?",
  "answer": "右手"
 },
 {
  "question": "什麼樣的河人們永遠也渡不過去?",
  "answer": "銀河"
 },
 {
  "question": "什麼東西越擦越小?",
  "answer": "橡皮擦"
 },
 {
  "question": "一加一等於多少?",
  "answer": "不三不四"
 },
 {
  "question": "一口咬掉牛尾巴,是什麼字?",
  "answer": "告"
 },
 {
  "question": "上海的南京路,來往最多的是什麼人?",
  "answer": "中國人"
 }

]


cnt = 0    # 答對題數
for q in quiz:
    sendMsg(q["question"])
    response = readMsg()
    if response == q["answer"]:
        sendMsg("答對了!")
        cnt += 1
    else:
        sendMsg("答錯了!正確答案是 %s" % 
                      q["answer"])
      
sendMsg("您答對了 %d 題。" % cnt)

if cnt < 2:
    sendMsg("請加油!")
# Add elif and else
elif cnt < 4:
    sendMsg("不錯喔!")
else:
    sendMsg("真厲害!")


程式執行結果:


思考與程式練習:如何增加這個問答機器人在判斷玩家的回答的改善機制(人工智慧)?例如在回答「借什麼可以不還?」時,「借過」與「借光」是同義詞,這兩個詞都要算對。