Author Topic: Brainfuck Interpreter  (Read 37709 times)

0 Members and 1 Guest are viewing this topic.

Offline Aureal

  • Newbie
  • Posts: 17
  • memes
    • View Profile
Brainfuck Interpreter
« on: July 19, 2017, 08:23:05 pm »
Well, I've written an interpreter for brainfuck, why? why not? But I've ran into a bug that I can't solve.
I don't understand the reason, but even though I included a line that wraps the data pointer to the upper bound of the data array, the program keeps subtracting 1 to it, this is crucial for loops to work. Here's the code

Code: QB64: [Select]
  1. dim shared prog(&hffff&) as string
  2. dim shared ostream       as _unsigned _byte
  3. dim shared arr(&hffff&)  as _unsigned _byte
  4. dim shared istream       as _unsigned _byte
  5. dim shared ptr           as integer
  6.  
  7.     sleep
  8.     do
  9.         select case inkey$
  10.             case ">"     : s$ = s$ + ">": cnt = cnt + 1: prog(cnt) = ">": exit do
  11.             case "<"     : s$ = s$ + "<": cnt = cnt + 1: prog(cnt) = "<": exit do
  12.             case "+"     : s$ = s$ + "+": cnt = cnt + 1: prog(cnt) = "+": exit do
  13.             case "-"     : s$ = s$ + "-": cnt = cnt + 1: prog(cnt) = "-": exit do
  14.             case "."     : s$ = s$ + ".": cnt = cnt + 1: prog(cnt) = ".": exit do
  15.             case ","     : s$ = s$ + ",": cnt = cnt + 1: prog(cnt) = ",": exit do
  16.             case "["     : s$ = s$ + "[": cnt = cnt + 1: prog(cnt) = "[": exit do
  17.             case "]"     : s$ = s$ + "]": cnt = cnt + 1: prog(cnt) = "]": exit do
  18.             case chr$(8) : if len(s$) then s$ = left$(s$, len(s$) - 1)  : exit do
  19.             case chr$(13): exec
  20.             case "v"     : for i = 1 to len(_clipboard$): prog(i + cnt) = chr$(asc(_clipboard$, i)): next: s$ = s$ + _clipboard$: exit do
  21.             case else    :
  22.         end select
  23.     loop
  24.     print s$;
  25.     _keyclear
  26.  
  27. sub exec
  28.     for i = 0 to ubound(prog)
  29.         select case prog(i)
  30.             case ">": ptr = ptr + 1
  31.             case "<": if ptr then ptr = ptr - 1 else ptr = ubound(arr) 'What the heck?
  32.             case "+": arr(ptr) = arr(ptr) + 1
  33.             case "-": arr(ptr) = arr(ptr) - 1
  34.             case ".": ostream  = arr(ptr)
  35.             case ",": arr(ptr) = istream
  36.             case "[":
  37.                 if arr(ptr) = 0 then
  38.                     for y = i to ubound(prog)
  39.                         if prog(x) = "]" then i = x + 1: exit for
  40.                     next
  41.                 end if
  42.             case "]":
  43.                 if arr(ptr) then
  44.                     for x = i to 0 step -1
  45.                         if prog(x) = "[" then i = x: exit for
  46.                     next
  47.                 end if
  48.         end select
  49.         updateOutput
  50.         updateConsole(i)
  51.     next
  52.  
  53. sub updateOutput     : print chr$(ostream): _display: cls: end sub
  54. sub updateInput      : istream = asc(inkey$)             : end sub
  55. sub updateConsole(i) : cout "dataptr           =" + str$(ptr)
  56.     cout "data    (current) ="  + str$(arr(ptr))
  57.     cout "program (current) = " + prog(i)
  58.     cout "---------------------"
  59. sub cout(s$)      : _dest _console: print s$: _dest 0 : end sub
  60.  

And here's the test program (paste with v, execute with [enter]):

Code: QB64: [Select]
  1. ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
  2.  
« Last Edit: July 19, 2017, 08:29:56 pm by Aureal »

Offline SkyCharger001

  • Newbie
  • Posts: 14
    • View Profile
Re: Brainfuck Interpreter
« Reply #1 on: July 20, 2017, 09:00:35 am »
make ptr an unsigned integer and underflow/overflow will cause a wrap-around instead of a crash. (you won't need to handle them manually)

Offline Petr

  • Forum Resident
  • Posts: 1720
  • The best code is the DNA of the hops.
    • View Profile
Re: Brainfuck Interpreter
« Reply #2 on: July 20, 2017, 10:11:18 am »
Hello. I think it's going to be 13-20 code lines. The minimum value for cnt is 1 to fix this, you must first assign the field value and then increase the cnt index.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Brainfuck Interpreter
« Reply #3 on: July 23, 2017, 03:28:12 am »
This is 2nd time I've seen talk of this, this month, so I checked out Rosetta Code and did a double translation.
Code: QB64: [Select]
  1. 'BF translation.bas for QB64 fork (B+=MGA) 2017-07-23
  2. ' BF in QB.bas for SmallBASIC 0.12.9 (B+=MGA) 2017-07-22
  3. ' I just translated some QB code from Rosetta to SmallBASIC
  4. ' and tested a couple of programs Hello World, Goodbye World
  5. ' count down also found at Rosetta Code
  6. '======================================================================
  7. ' QB64 has excellent Help wiki, thanks to all who put that together!
  8. '======================================================================
  9. _TITLE "Brainf***, Rosetta Code - Quick Basic translation to SB then to QB64 (fork)"
  10. 'for directory stuff
  11. CONST ListMAX% = 20
  12. COMMON SHARED dirList$()
  13. COMMON SHARED DIRCount% 'returns file count if desired
  14.  
  15. memsize% = 20000
  16. DIM memory%(memsize%)
  17. instChars$ = "+-<>.,[]" 'valid characters
  18. loadDirList "bf*.txt"
  19.  
  20.     ptr% = 0 'memory pointer
  21.     source$ = ""
  22.     CLS
  23.     IF DIRCount% THEN
  24.         FOR i% = 1 TO DIRCount%
  25.             PRINT i%, dirList$(i%)
  26.         NEXT
  27.     ELSE
  28.         PRINT "Sorry, no bf*.txt files found."
  29.         SLEEP
  30.         END
  31.     END IF
  32.     PRINT: INPUT "Enter line number of BF Filename you desire "; ln%
  33.     IF ln% < 1 OR ln% > DIRCount% THEN END
  34.     filename$ = dirList$(ln%)
  35.  
  36.     OPEN filename$ FOR INPUT AS #1
  37.     DO
  38.         LINE INPUT #1, FLINE$
  39.         source$ = source$ + FLINE$
  40.     LOOP UNTIL EOF(1)
  41.     CLOSE #1
  42.  
  43.     IF LEN(source$) < 1 THEN
  44.         PRINT "No source code to BF."
  45.         SLEEP
  46.         END
  47.     END IF
  48.  
  49.     'let's clean the code up, check bracket balance
  50.     bktCnt% = 0
  51.     code$ = ""
  52.     FOR i% = 1 TO LEN(source$)
  53.         char$ = MID$(source$, i%, 1)
  54.         'check to see if this is a valid instruction character
  55.         IF INSTR(instChars$, char$) THEN
  56.             code$ = code$ + char$
  57.             'count brackets
  58.             IF char$ = "[" THEN bktCnt% = bktCnt% + 1
  59.             IF char$ = "]" THEN bktCnt% = bktCnt% - 1
  60.         END IF
  61.     NEXT
  62.  
  63.     IF bktCnt% THEN 'mismatched brackets
  64.         PRINT "Uneven brackets"
  65.         SLEEP
  66.         END
  67.     ELSE
  68.         PRINT "Code:": PRINT code$: PRINT: PRINT "Output:"
  69.     END IF
  70.     'clear last if any
  71.     ERASE memory%
  72.     DIM memory%(memsize%)
  73.     inLine$ = "" 'input buffer
  74.     FOR i% = 1 TO LEN(code$) 'loop through the code
  75.         instruction$ = MID$(code$, i%, 1) 'get the instruction we're on
  76.         SELECT CASE instruction$
  77.             CASE "+"
  78.                 memory%(ptr%) = memory%(ptr%) + 1
  79.             CASE "-"
  80.                 memory%(ptr%) = memory%(ptr%) - 1
  81.             CASE "."
  82.                 PRINT CHR$(memory%(ptr%));
  83.             CASE ","
  84.                 IF inLine$ = "" THEN LINE INPUT inLine$ 'buffer input
  85.                 inChar$ = LEFT$(inLine$, 1) 'take the first char off the buffer
  86.                 inLine$ = MID$(inLine$, 2) 'delete it from the buffer
  87.                 memory%(ptr%) = ASC(inChar$) 'use it
  88.             CASE ">"
  89.                 ptr% = ptr% + 1
  90.                 IF ptr% > memsize% THEN
  91.                     PRINT "Memory pointer out of range"
  92.                     SLEEP
  93.                     END
  94.                 END IF
  95.             CASE "<"
  96.                 ptr% = ptr% - 1
  97.                 IF ptr% < 0 THEN
  98.                     PRINT "Memory pointer out of range"
  99.                     SLEEP
  100.                     END
  101.                 END IF
  102.             CASE "["
  103.                 IF memory%(ptr%) = 0 THEN
  104.                     bktCnt% = 1 'count the bracket we're on
  105.                     i% = i% + 1 'move the code pointer to the next char
  106.                     WHILE bktCnt% <> 0
  107.                         'count nested loops till we find the matching one
  108.                         IF MID$(code$, i%, 1) = "]" THEN bktCnt% = bktCnt% - 1
  109.                         IF MID$(code$, i%, 1) = "[" THEN bktCnt% = bktCnt% + 1
  110.                         i% = i% + 1 'search forward
  111.                     WEND
  112.                 END IF
  113.             CASE "]"
  114.                 IF memory%(ptr%) <> 0 THEN
  115.                     bktCnt% = -1 'count the bracket we're on
  116.                     i% = i% - 1 'move the code pointer back a char
  117.                     WHILE bktCnt% <> 0
  118.                         'count nested loops till we fine the matching one
  119.                         IF MID$(code$, i%, 1) = "]" THEN bktCnt% = bktCnt% - 1
  120.                         IF MID$(code$, i%, 1) = "[" THEN bktCnt% = bktCnt% + 1
  121.                         i% = i% - 1 'search backwards
  122.                     WEND
  123.                 END IF
  124.         END SELECT
  125.     NEXT
  126.     PRINT: PRINT: INPUT "Press y for yes to do another "; yes$
  127.     IF yes$ <> "y" THEN END
  128.  
  129. ' modified function from Help files
  130. SUB loadDirList (spec$)
  131. CONST TmpFile$ = "DIR$INF0.INF"
  132. STATIC Ready%, Index%
  133. IF NOT Ready% THEN REDIM dirList$(ListMAX%): Ready% = -1 'DIM array first use
  134. IF spec$ > "" THEN 'get file names when a spec is given
  135.     SHELL _HIDE "DIR " + spec$ + " /b > " + TmpFile$
  136.     Index% = 0: dirList$(Index%) = "": ff% = FREEFILE
  137.     OPEN TmpFile$ FOR APPEND AS #ff%
  138.     size& = LOF(ff%)
  139.     CLOSE #ff%
  140.     IF size& = 0 THEN KILL TmpFile$: EXIT SUB
  141.     OPEN TmpFile$ FOR INPUT AS #ff%
  142.     DO WHILE NOT EOF(ff%) AND Index% < ListMAX%
  143.         Index% = Index% + 1
  144.         LINE INPUT #ff%, dirList$(Index%)
  145.     LOOP
  146.     DIRCount% = Index% 'SHARED variable can return the file count
  147.     CLOSE #ff%
  148.     KILL TmpFile$
  149. ELSE IF Index% > 0 THEN Index% = Index% - 1 'no spec sends next file name
  150.  

I think the interpreter is probably easier to write than a program. Very interesting subject!

Included in zip are some short programs to get a directory listing in files list.
* BF translation.zip (Filesize: 617.76 KB, Downloads: 395)
« Last Edit: July 23, 2017, 03:32:22 am by bplus »

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: Brainfuck Interpreter
« Reply #4 on: July 23, 2017, 07:40:37 am »
Thanks for keeping us posted bplus. I was going to respond over at the "other" forum but didn't because... reasons... namely all of my posts need to be approved first. Still waiting for a few posts (from days ago) to make it past the admin over there. No telling what a PG-13 site would do with a title like BrainFuck. Ya know, the same place that throws me ads for mail-in Thai brides. Very child-friendly as a concept.
You're not done when it works, you're done when it's right.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Brainfuck Interpreter
« Reply #5 on: July 23, 2017, 01:05:01 pm »
Thanks for keeping us posted bplus. I was going to respond over at the "other" forum but didn't because... reasons... namely all of my posts need to be approved first. Still waiting for a few posts (from days ago) to make it past the admin over there. No telling what a PG-13 site would do with a title like BrainFuck. Ya know, the same place that throws me ads for mail-in Thai brides. Very child-friendly as a concept.

"The Lords work in mysterious ways." - (This is definitely NOT from the Bible)

Since translating this crazy little interpreter, I am very curious now how one might go about making up a program that does anything like print "Hello World!". I did offer it up as a challenge at two other forums, because I have only the tiniest clue from reading Wiki on subject. I would like to pursue this further. An IDE? Modifications to plug-in "subroutines"?

I hope Aureal is also intrigued and that I haven't hi-jacked his thread.

Offline Aureal

  • Newbie
  • Posts: 17
  • memes
    • View Profile
Re: Brainfuck Interpreter
« Reply #6 on: July 23, 2017, 10:28:43 pm »
Hi, bplus, actually, I might do something else with this, I do have some experience on writing many tools for weird things : D (please note my "suite" for the Chip8, including a disassembler, emulator, and assembler!)

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Brainfuck Interpreter
« Reply #7 on: July 23, 2017, 11:24:03 pm »
After reading more, I too have another idea to go at this sort of thing.

Offline eoredson

  • Newbie
  • Posts: 55
  • Let the Farce be with you!
    • View Profile
    • Oredson QB45 Files At Filegate
Re: Brainfuck Interpreter
« Reply #8 on: July 24, 2017, 12:17:27 am »
If you are serious about writing your own interpreter, you should look at the attached file:

Erik.
* SICK64D1.ZIP (Filesize: 393.85 KB, Downloads: 355)

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Brainfuck Interpreter
« Reply #9 on: July 24, 2017, 01:34:09 pm »
If you are serious about writing your own interpreter, you should look at the attached file:

Erik.

Thanks Erik, I will check this out!

You might like this:
http://www.thejoyfulprogrammer.com/qb64/forum/showthread.php?tid=814&rndtime=1500917497749477912


To All,

I am pursuing this topic mainly in a PL called SmallBASIC (one word BASIC in all CAPs) an Interpreter only , NOT MS Small Basic (2 words last word not all caps).

Here (SmallBASIC Forum):
https://smallbasic.sourceforge.io/?q=node/1743

Here (Retrogamecoding.org in board where any Basic is welcome):
http://retrogamecoding.org/board/index.php?topic=592.0

Here (The QB64 Edition, a sub forum of [banned user]):
http://www.thejoyfulprogrammer.com/qb64/forum/showthread.php?tid=948&rndtime=1500919068149440136

I will pursue here too but first I want to see what Aureal is up to!  :)

nano.PNG
* nano.PNG (Filesize: 186.79 KB, Dimensions: 1255x554, Views: 511)
« Last Edit: July 24, 2017, 02:01:11 pm by bplus »

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Brainfuck Interpreter
« Reply #10 on: July 27, 2017, 07:55:28 am »
Hi Erik,

It's epic! Awesome!

But I only skimmed as I have another little one in the works. 2nd mod since BF, BQ (Be Quicker) 1st mod, EIN (Everything Is Number) 2nd mod (Smaller than my Nano?). BF taught me stuff! but I've tossed the ptr and incrementors of memory locations :)

I noticed mention of DOS, does it work in Windows? dumb question?

Also if it does work in Windows, do I need QB64? ;)

A cool thing I caught, I think, was assembler or machine code capable? or did i misread in skim.

Can QB64 do that?

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: Brainfuck Interpreter
« Reply #11 on: March 06, 2020, 05:59:34 pm »
Bump. Status on this?
You're not done when it works, you're done when it's right.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Brainfuck Interpreter
« Reply #12 on: March 06, 2020, 07:23:38 pm »
Bump. Status on this?

Hmm... Aureal, no sign of him in long time, you have Erik's SICK in Library and my QB64 version of Nano is either at Walter's or [abandoned, outdated and now likely malicious qb64 dot net website - don’t go there] (if not here somewhere else). I did rework Nano with another parser but still stuck on very limited String manipulation and no arrays... QB64 is way more interesting!

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: Brainfuck Interpreter
« Reply #13 on: March 06, 2020, 07:25:16 pm »
Oh wait NANO!

That was a fun period though. Want to dust it off?
You're not done when it works, you're done when it's right.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Brainfuck Interpreter
« Reply #14 on: March 06, 2020, 07:37:04 pm »
Oh wait NANO!

That was a fun period though. Want to dust it off?

:) Yeah sure, like we haven't stirred up enough stuff already. Are you on vacation or something?