BrainF*** Interpreter in Batch

[Aacini]

The core idea of Brainf*ck compilers is to be very small programs; for this reason most of they generate very inefficient executable code. However, anyone of them may serve for the purpose of prove this point. You just need to get any BF compiler that generate executable code for Windows OS and use it to run the Hanoi Tower BF program. Look for they at the link provided in the first post of this thread, or google for "**censored** compiler windows". EDIT In google you may use the complete Brainf*ck word, instead of "**censored**".

Antonio

[dbenham]

Great ideas Antonio - consolidating consecutive identical ops into one op with a count does make a huge performance difference, and storing the matching loop address with the loop op is elegant.

I've re-factored your code with the following substantive changes.

- The input routine is now locale independent, and it also can differentiate between <Ctrl-C> and <LF>! Now all byte values from 0x01 to 0xFF can be entered via the keyboard. Only 0x00 is impossible.

- The artificial memory array boundary of 4095 has been removed. The array is now (virtually) unbounded on both the left and the right.

- Removed the outer FOR /F loop from the code parser. This dramatically speeds the parsing process. I don't understand why you thought it necessary to read the code one line at a time instead of going directly to one character at a time.

- Removed all output during the initialization phase. I might add it back in the future, with an option for silent mode.

- Explicitly undefine lastOp before parsing, and undefine all m[ before running... just in case.

- I verify that all 256 character files are length 1. If any file is missing or the wrong length, then I rebuild all character files.

- I highly optimized the character generation process to use parallel processing. It's a lot more code, but it generates the files much faster.

- Added the repetition loop for the input routine. This seems a little silly when getting input from the keyboard. But it may be important when the interpreter is expanded to support redirected/piped input. I have some ideas on how to do this.

- Removed the feature that sets the returned ERROLEVEL to the value at the memory pointer upon termination. I don't believe that is part of the spec. My version sets ERRORLEVEL to 0 upon normal termination, and 1 if the program was aborted via <Ctrl-Break>.

- Output <LF> as <LF> instead of <CR><LF>

EDIT: Fixed a silly bug dealing with renamed .chr files

Code: Select all

:: BF.BAT - BrainF*** interpreter in Batch
::
:: Usage:
::
::   bf sourceFile
::
:: The memory array consists of unsigned bytes. Increment and decrement
:: operations simply rollover when the limits are exceeded.
::
:: The memory array is unbounded both to the left and right
::
:: In theory, the code pointer can range from 1 to 2147483647,
:: and the memory pointer can range from -2147483648 to 2147483647.
:: But performance will become unbearable long before those limits are
:: reached.
::
:: BF.BAT can only read input from the keyboard. Input will fail
:: if data is piped into BF.BAT or if stdin is redirected to a file.
::
:: The <Enter> key is read as <CR>
:: All other inputs are normal.
::
:: Any byte value (except 0x00) may be entered by holding down the <Alt> key
:: and entering a decimal code on the numeric keypad.
::
:: The only way to enter <LF> is via <Alt> and the numeric keypad.
::
:: BF.BAT was developed by the following DosTips users:
::   Antonio Perez Ayala (aka Aacini)
::   Dave Benham         (aka dbenham)
::
:: This version was derived from Aacini's version 2.0
::
:: Development efforts can be traced at
:: http://www.dostips.com/forum/viewtopic.php?f=3&t=5751


@echo off
setlocal EnableDelayedExpansion
if "%~1" equ ":run" goto :run
 
:: Validate parameters
if "%~1" equ "" >&2 echo Usage: %~N0 filename.ext&exit /b 1
if not exist "%~1" >&2 echo File not found: %1&exit /b 1

:: Parse the code and for each op, store the op followed by a number
:: For [ and ] the number represents the address of the matching loop boundary
:: For all other ops the number represents the repeat count for that op.
set "operators=+-<>.,[]"
set /a ip=sp=count=0
set "lastOp="
for /f %%b in ('cmd /U /C type %1^|find /V ""') do (
  if "!operators:%%b=!" neq "%operators%" (
    if "!lastOp!" equ "%%b" (
      set /a count+=1
    ) else (
      if defined lastOp (
        set /a ip+=1
        set code[!ip!]=!lastOp! !count!
        set "lastOp="
        set "count=0"
      )
      if "%%b" equ "[" (
        set /a "ip+=1, sp+=1"
        set /a "stack[!sp!]=ip"
      ) else if "%%b" equ "]" (
        for %%s in (!sp!) do (
          set /a ip+=1, sp-=1
          set "code[!ip!]=] !stack[%%s]!"
          set "code[!stack[%%s]!]=[ !ip!"
        )
      ) else (
        set "lastOp=%%b"
        set "count=1"
      )
    )
  )
)
if %count% gtr 0 (
  set /a ip+=1
  set "code[!ip!]=%lastOp% %count%"
)

:: Error if unbalanced brackets
if %sp% neq 0 >&2 echo ERROR: Unbalanced brackets&exit /b 1

:: Create character files if they don't already exist
set "needChars="
for /l %%N in (0 1 255) do for %%F in (%%N.bf.chr) do if "%%~zF" neq "1" set "needChars=1"
if defined needChars call :genAllChr

:: Initialize memory to undefined (equivalent to 0)
for /f "delims==" %%A in ('set m[ 2^>nul') do set "%%A="

:: Define CR to hold <CarriageReturn> for use in input routine
for /f %%A in ('copy /Z "%~dpf0" nul') do set "CR=%%A"

:: Define SUB to hold <0x1A>
for /f "delims=" %%A in (26.bf.chr) do set "SUB=%%A"

:: Establish line one of input routine for this locale
set "line1="
for /f "delims=" %%L in (
  'echo .^|xcopy /w "%~f0" "%~f0" 2^>nul'
) do if not defined line1 set "line1=%%L"
set "line1=!line1:~0,-1!"

:: Launch the interpreter
cmd /c "%~f0" :run&&exit /b 0||exit /b 1


:run  - This is the main interpreter loop
set /a "ip=1, mp=0"
for /l %%. in () do for %%I in (!ip!) do for /F "tokens=1-3" %%A in ("!mp! !code[%%I]!") do (
  if        "%%B" equ "+" (
    set /a "m[%%A]=(m[%%A]+%%C)&255"
  ) else if "%%B" equ "-" (
    set /a "m[%%A]=(m[%%A]-%%C)&255"
  ) else if "%%B" equ ">" (
    set /a "mp+=%%C"
  ) else if "%%B" equ "<" (
    set /a "mp-=%%C"
  ) else if "%%B" equ "[" (
    if not defined m[%%A] set "ip=%%C"
    if "!m[%%A]!" equ "0" set "ip=%%C"
  ) else if "%%B" equ "]" (
    if defined m[%%A] if "!m[%%A]!" neq "0" set "ip=%%C"
  ) else if "%%B" equ "." for /l %%N in (1 1 %%C) do (
    if defined m[%%A] (
      if "!m[%%A]!" equ "26" (set /p "=!SUB!" < NUL) else type !m[%%A]!.bf.chr
    ) else type 0.bf.chr
  ) else if "%%B" equ "," for /l %%N in (1 1 %%C) do (
    set "key="
    set "CtrlC=1"
    for /f "delims=" %%K in (
      'xcopy /w "%~f0" "%~f0" 2^>nul'
    ) do if not defined key (
      setlocal disableDelayedExpansion
      set "key=%%K"
    ) else set "CtrlC="
    setlocal enableDelayedExpansion
    if defined CtrlC (
      endlocal&endlocal
      set "m[%%A]=3"
    ) else if "!key!" equ "!line1!" (
      endlocal&endlocal
      set "m[%%A]=10"
    ) else if "!key:~-1!" equ "!CR!" (
      endlocal&endlocal
      set "m[%%A]=13"
    ) else (
      >key.txt.tmp echo(!key:~-1!
      endlocal&endlocal
      for /f "delims=." %%K in ('findstr /lg:key.txt.tmp *.bf.chr') do set "m[%%A]=%%K"
    )
  ) else exit
  set /a ip+=1
)


:genAllChr
::This code creates 256 1 byte files, one for each possible byte value.
::This is encoded in a macro way to be called asynchronously with start cmd /c
::Teamwork of carlos, penpen, aGerman, dbenham, einstein1969
::Tested under Win7 and XP
setlocal disableDelayedExpansion
set ^"genchr=(^
for /l %%N in (%%A !cnt! 255) do (^
  if %%N equ 26 (^
    copy /y nul + nul /a 26.bf.chr /a ^>nul^
  ) else (if %%N geq 35 if %%N leq 126 if %%N neq 61 (^
    ^<nul set /p "=!ascii:~%%N,1!" ^>%%N.bf.chr^
  ))^&^
  if not exist %%N.bf.chr (^
    makecab /d compress=off /d reserveperdatablocksize=26 /d reserveperfoldersize=%%N %%A.tmp %%N.bf.chr ^>nul^&^
    type %%N.bf.chr ^| ((for /l %%n in (1 1 38) do pause)^>nul^&findstr "^^" ^>%%N.temp)^&^
    ^>nul copy /y %%N.temp /a %%N.bf.chr /b^&^
    del %%N.temp^
  )^
))^&^
del %%A.tmp^"
del /f /q /a *bf.chr >nul 2>&1
set "ascii=                                   #$%%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
set /a cnt=number_of_processors
if %cnt% lss 1 set cnt=1
if %cnt% gtr 256 set cnt=256
set /a "end=cnt-1"
for /l %%A in (0 1 %end%) do (
  type nul >%%A.tmp
  if %%A equ %end% (
    cmd /q /v:on /c "%genchr%"
  ) else (
    start "" /b cmd /q /v:on /c "%genchr%"
  )
)
:genAllChr.check
for /l %%N in (0 1 %end%) do if exist %%N.tmp goto :genAllChr.check
exit /b

Dave Benham

[einstein1969]

I have re-tested the new version, with little modification at tests:

Parsing:
dbenham BF 14:41:22,88 - 14:51:35,93 elapsed 61305 cs
aacini BF 15:08:24,65 - 15:19:22,80 elapsed 65815 cs

Run:
dbenham BF about 55 cycles/s
aacini BF about 49 cycles/s

I think that is possible double ( or more) the run speed using DISK instead of ENVIRONMENT.

einstein1969

[dbenham]

That is highly dependent on the performance characteristics of the storage media. It would simply die on my shared network drives at work

I did a quick test, storing the code in files, one op/count per file, instead of in environment variables. I didn't bother storing the memory in files.

I tested (very crudely) both the Towers of Hanoi, as well as Sierpinski triangle.

The Towers of Hanoi never finished in either case. But the file based version seemed to be running perhaps more than 10 times faster.

But the Sierpinski triangle was around 30% slower using the file based version.

I think that by the time the bf program becomes large enough to make the file based version advantageous, the program will still be too slow to be practical. (As if brainf*** is ever practical)


Dave Benham

[einstein1969]

That is highly dependent on the performance characteristics of the storage media. It would simply die on my shared network drives at work

I did a quick test, storing the code in files, one op/count per file, instead of in environment variables. I didn't bother storing the memory in files.

I tested (very crudely) both the Towers of Hanoi, as well as Sierpinski triangle.

The Towers of Hanoi never finished in either case. But the file based version seemed to be running perhaps more than 10 times faster.

But the Sierpinski triangle was around 30% slower using the file based version.

I think that by the time the bf program becomes large enough to make the file based version advantageous, the program will still be too slow to be practical. (As if brainf*** is ever practical)


Dave Benham

I'm doing a brainstorm. It came to my mind that maybe the implementation should dynamically switch from Environment mode to the (local) disk mode. I'm reminded of the Oracle X$ tables and when I was performance tuning and perhaps implement a small in-memory(ENV) cache might help (LRU or other). Maybe even a prefetch mechanism or something like that.

I have not studied your code enough ...

EDIT:
I have resolved/correct the link of Sierpinski triangle

einstein1969

[Aacini]

I've re-factored your code with the following substantive changes.

- The input routine is now locale independent, and it also can differentiate between <Ctrl-C> and <LF>! Now all byte values from 0x01 to 0xFF can be entered via the keyboard. Only 0x00 is impossible.

Thanks! I included your new input routine in my code. Just a comment: Ctrl-J does nothing (it should insert a <LF>, right?) and Ctrl-Z insert a lowcase "t" letter. Note: my new laptop have NOT the Alt-digits method to enter characters, so I can not test this via any other method...

- Removed the outer FOR /F loop from the code parser. This dramatically speeds the parsing process. I don't understand why you thought it necessary to read the code one line at a time instead of going directly to one character at a time.

I need individual lines to enter debug information. Details below.

- Explicitly undefine lastOp before parsing, and undefine all m[ before running... just in case.

Well... It is highly unlikely that any variable named m[ may normally exist, right? However, undefine all variables may speed up the program a little. I do that in my new version; I just keep PATH and the parsed code.

- I verify that all 256 character files are length 1. If any file is missing or the wrong length, then I rebuild all character files.

Again, you should not expect that any file with the right name have the wrog contents, unless the user had deliberately changed it. However, in this case, how do you know that a file with the right name and length have the right contents? As easy as: ren 10.bf.txt other.txt & ren 32.bf.txt 10.bf.txt & ren other.txt 32.bf.txt.

- I highly optimized the character generation process to use parallel processing. It's a lot more code, but it generates the files much faster.

Well, these files should be generated just once...

- Added the repetition loop for the input routine. This seems a little silly when getting input from the keyboard. But it may be important when the interpreter is expanded to support redirected/piped input. I have some ideas on how to do this.

Note that two input operations in sequence without processing of the first character have no sense because the second input destroy the first character, so I assumed this will never happen.

- Removed the feature that sets the returned ERROLEVEL to the value at the memory pointer upon termination. I don't believe that is part of the spec. My version sets ERRORLEVEL to 0 upon normal termination, and 1 if the program was aborted via <Ctrl-Break>.

You are right! The specs don't mention this point, it is just my personal preference.

- The artificial memory array boundary of 4095 has been removed. The array is now (virtually) unbounded on both the left and the right.

- Output <LF> as <LF> instead of <CR><LF>

Because of its origins, Brainf*ck language have several details not entirely specified that had lead to several discussions in the respective forums. One of the points that seems to be universally accepted is that output an Ascii character 10 (a LineFeed) cause the cursor to go to the beginning of the next line, that is, produce a <CR><LF> pair, that in Unix/Linux world is know as NewLine character: "\n". Another point of discussion is the input of Enter key: the original BF compiler load a 10 instead of 13. Most, although not all, BF programs assume this result, so in many cases is simpler that the BF compiler/interpreter return a 10, than modify the numerous existent programs that expect a 10 instead of a 13. I have this behaviour in my own BF interpreter, and I suggest to everyone to adopt it.

There are other points that cause problems and that can only be partially solved via a particular point of view when developing a BF interpreter/compiler; for example, the size of the cells (usually byte), the behaviour when a cell overflow/underflow, the number of elements in the memory tape, the behaviour of the pointer when overflow/underflow, etc. This is my point of view:

The original purpose of BF language was/is to develop a compiler, that is, to generate a series of instructions in machine language code. In my opinion, the behavior of a BF program must be the same of the behavior of the equivalent program when it is written in assembly language. As far as I know, all processors perform arithmetic operations in binary base, so if a byte have a zero and it is decremented, the result is 255, and vice versa. There are not negative values per se, but negative values may be managed via complement of 2. The same point apply to pointer registers: there are not negative values and pointers are usually bounded to the memory range allocated for the tape. If the whole addressable memory range has been allocated, then pointers automatically wrap-around at the ends of the memory area.

I think that these problems arise when people started to develop BF compilers in other languages (like BASIC) that are not compliant with the behavior of the underlying CPU...

_________________________________________________________


I modified my BF interpreter in several points, that are described in the code under "Version 2.1". The most important new feature is the ability to save the parsed version of a BF program in a file, so it may be reloaded later. This way, a large program may be parsed just once and then executed several times more quickly. However, a perhaps more important additional benefit of this feature is that it makes understandable a BF program! All BF programs, but particularly the large ones, are a chaotic collection of characters with no indication of what they does. The "parsed version" of a BF program contain a much more readable version of the program that may serve as base for its study. You may insert comments in this file preceded by "//" characters to make it more clear. If you want to insert a complete line of comments, that is, not placed at right side of the original code, put a ";" in the first character of the line. You may even modify the parsed version of the code and run it, or locate the point in the original BF program where certain instructions are located. This is easily achieved because the parsed version also include the original lines as comments.

As an example of this feature, this is the original dbenham's program that display each value read via "," (input) command:

Code: Select all

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

... and this is its parsed version with comments of my own:

Code: Select all

;[1]  ++++++++++++++++++++++++++++++++>
"code[1]=+ 32"          // m[0]=32 (space)              |m[0]|m[1]|m[2]|m[3]|m[4]|
"code[2]=> 1"           // m[1]                         | SP |
;[2]  ++++++++++++++++++++++++++++++++++++++++>>
"code[3]=+ 40"          //     =40 (left paren)         | SP | "("|
"code[4]=> 2"           // m[3]
;[3]  +++++++++++++++++++++++++++++++++++++++++>
"code[5]=+ 41"          //     =41 (right paren)        | SP | "("|    | ")"|
"code[6]=> 1"           // m[4]
;[4]  ++++++++++<<
"code[7]=+ 10"          //     =10 (new line)           | SP | "("|    | ")"| NL |
"code[8]=< 2"           // m[2]
;[5]  +
"code[9]=+ 1"           //     =1 to enter the next loop
;[6]  [,<<.>.>.>.>.<<-------------]
"code[10]=[ 24"         // while m[2]
   "code[11]=, 1"       //    input m[2]                | SP | "("|char| ")"| NL |
   "code[12]=< 2"       //    m[0]
   "code[13]=. 1"       //    show Space
   "code[14]=> 1"       //    m[1]
   "code[15]=. 1"       //    show "("
   "code[16]=> 1"       //    m[2]
   "code[17]=. 1"       //    show the char read
   "code[18]=> 1"       //    m[3]
   "code[19]=. 1"       //    show ")"
   "code[20]=> 1"       //    m[4]
   "code[21]=. 1"       //    new line
   "code[22]=< 2"       //    m[2]
   "code[23]=- 13"      //    m[2]-=13, =zero if key read was Enter
"code[24]=] 10"         // endwhile

I like this!

Code: Select all

@echo off
setlocal EnableDelayedExpansion
if "%~1" equ ":runCode" goto %1

rem bf.bat: Brainf*ck interpreter in Batch
rem Antonio Perez Ayala

rem Version 1.1: - Bug fixed in arithmetic overflow
rem              - Full support of 256 Ascii characters in "." (output) command

rem Version 2:   - Change "goto" main loop by a "while" one
rem              - No define memory tape array.
rem              - Optimize groups of the same + - > < . commands in a single one
rem              - Use Dave Benham's code for "," (input) command

rem Version 2.1: - Small bug fixed when "*" or "~" characters appear in the input file
rem              - Delete *all* variables, excepting the parsed program code and "PATH"
rem              - Optimize "[-]" loop as m[%mp%]=0
rem              - Optimize "[-]+++..." or "[-]---..." constructs as m[%mp%]=N or m[%mp%]=-N
rem              - Save/load a "parsed-version" of the input file that include source lines as comments
rem                For precise line numbering, don't leave empty lines: just put a / in first character
rem                May be a maximum of 4 comment lines between lines with code
rem                Additional comments may be inserted *in the parsed file* starting they with //

if "%~1" equ "" echo Usage: %~N0 filename.ext & goto :EOF
if exist "%~PN1.bp" (
    echo A parsed version of this file exists
    choice /M "Do you want to load it "
    if !errorlevel! equ 1 (
        set /P "=Loading parsed file." < NUL
        for /F "usebackq delims=/" %%a in ("%~PN1.bp") do set %%a
        goto Ascii
    )
)
if not exist "%~1" echo File not found: %1 & goto :EOF

set "operators=+-<>.,[]"
set "lastOp="
set /A ip=0, sp=0, count=0, numLine=0, maxLevel=0
set /P "=Parsing file." < NUL
for /F "usebackq delims=" %%a in ("%~1") do (
   set /A numLine+=1, nextIp=ip+2
   if !nextIp! equ 2 set nextIp=1
   set nextLine[!nextIp!]=!numLine!
   for /F "delims=" %%b in ('cmd /U /C echo "%%a"^| find /V ""') do (
      if "!operators:%%b=!" neq "%operators%" if "%%b" neq "*" if "%%b" neq "~" (
         if "!lastOp!" equ "%%b" (
            set /A count+=1
         ) else (
            if defined lastOp (
               for %%i in (!ip!) do set "oper=!code[%%i]!"
               set /A ip+=1
               if "!oper!" equ "= 0" (
                  if "!lastOp!" equ "+" (
                     set /A ip-=1
                     set "lastOp=="
                  ) else if "!lastOp!" equ "-" (
                     set /A ip-=1
                     set "lastOp=="
                     set "count=-!count!"
                  )
               )
               set "code[!ip!]=!lastOp! !count!"
               set "lastOp="
               set count=0
            )
            if "%%b" equ "[" (
               set /A ip+=1, sp+=1
               set stack[!sp!]=!ip!
               if !sp! gtr !maxLevel! set maxLevel=!sp!
            ) else if "%%b" equ "]" (
               set /A numOpers=ip-stack[!sp!]
               for %%i in (!ip!) do set "oper=!code[%%i]!"
               if "!numOpers! !oper!" equ "1 - 1" (
                  set /A ip-=1
                  set "code[!ip!]== 0"
               ) else (
                  set /A ip+=1
                  for %%s in (!sp!) do (
                     set "code[!ip!]=] !stack[%%s]!"
                     set "code[!stack[%%s]!]=[ !ip!"
                  )
               )
               set /A sp-=1
            ) else (
               set "lastOp=%%b"
               set count=1
            )
         )
      )
   )
   set /P "=." < NUL
)
if %count% gtr 0 (
   set /A ip+=1
   set "code[!ip!]=%lastOp% %count%"
)
echo/
if %sp% neq 0 echo ERROR: Unbalanced brackets & goto :EOF

set /P "=Saving parsed file." < NUL
set "spaces="
for /L %%i in (1,1,%maxLevel%) do set "spaces=!spaces!   "
set /A numLine=0, margin=0
< "%~1" (for /L %%i in (1,1,%ip%) do (
   if defined nextLine[%%i] (
      for /L %%j in (1,1,5) do if !numLine! neq !nextLine[%%i]! (
         set /A numLine+=1, mod=numLine %% 10
         set "line="
         set /P line=
         echo ;[!numLine!]  !line!
         if !mod! equ 0 set /P "=." < NUL > CON
      )
   )
   if "!code[%%i]:~0,1!" equ "]" set /A margin-=3
   for %%m in (!margin!) do echo !spaces:~0,%%m!"code[%%i]=!code[%%i]!"
   if "!code[%%i]:~0,1!" equ "[" set /A margin+=3
)) > "%~PN1.bp"

:Ascii
echo/
set /P "=Creating Ascii tables." < NUL
type nul > t.tmp
set "options=/d compress=off /d reserveperdatablocksize=26"
for /L %%i in (0,1,255) do (
   if not exist %%i.chr call :genchr %%i
   set /A mod=%%i %% 16
   if !mod! equ 0 set /P "=." < NUL
)
set "options="
del t.tmp temp.tmp
echo/

echo Running.
cmd /Q /C "%~F0" :runCode
exit /B %errorlevel%

:runCode
set zVar=0
for /F "delims==" %%v in ('set') do (
   set "zVar=%%v"
   if "!zVar:~0,5!" neq "code[" if /I "!zVar!" neq "PATH" set "!zVar!="
)
rem Define CR to hold <CarriageReturn> for use in input routine
for /F %%a in ('copy /Z "%~F0" NUL') do set "CR=%%a"
rem Define SUB to hold <0x1A>
for /F "delims=" %%a in (26.chr) do set "SUB=%%a"
rem Establish line one of input routine for this locale
set "line1="
for /F "delims=" %%a in ('echo .^|xcopy /W "%~F0" "%~F0" 2^>NUL') do if not defined line1 set "line1=%%a"
set "line1=!line1:~0,-1!"
rem Start run code cycle
set /A ip=1, mp=0
for /L %%? in () do for %%i in (!ip!) do for /F "tokens=1-3" %%a in ("!mp! !code[%%i]!") do (
   if        "%%b" equ "+" (
      set /A "m[%%a]=(m[%%a]+%%c) & 255"
   ) else if "%%b" equ "-" (
      set /A "m[%%a]=(m[%%a]-%%c) & 255"
   ) else if "%%b" equ "=" (
      set "m[%%a]=%%c"
   ) else if "%%b" equ ">" (
      set /A "mp=(mp+%%c) & 4095"
   ) else if "%%b" equ "<" (
      set /A "mp=(mp-%%c) & 4095"
   ) else if "%%b" equ "[" (
      if not defined m[%%a] ( set ip=%%c
      ) else if "!m[%%a]!" equ "0" set ip=%%c
   ) else if "%%b" equ "]" (
      if defined m[%%a] if "!m[%%a]!" neq "0" set ip=%%c
   ) else if "%%b" equ "." (

      for /L %%i in (1,1,%%c) do (
         if defined m[%%a] (
            if        "!m[%%a]!" equ "10" (
                echo/
            ) else if "!m[%%a]!" equ "26" (
               set /P "=!SUB!" < NUL
            ) else (
               type !m[%%a]!.chr
            )
         ) else (
            type 0.chr
         )
      )

   ) else if "%%b" equ "," (

      set "key="
      set "CtrlC=1"
      for /F "delims=" %%K in ('xcopy /W "%~F0" "%~F0" 2^>NUL') do if not defined key (
         setlocal DisableDelayedExpansion
         set "key=%%K"
      ) else set "CtrlC="
      setlocal EnableDelayedExpansion
      if defined CtrlC (
         endlocal & endlocal
         set "m[%%a]=3"
      ) else if "!key!" equ "!line1!" (
         endlocal & endlocal
         set "m[%%a]=10"
      ) else if "!key:~-1!" equ "!CR!" (
         endlocal & endlocal
         set "m[%%a]=13"
      ) else (
         > key.txt.tmp echo(!key:~-1!
         endlocal & endlocal
         for /F "delims=." %%K in ('findstr /LG:key.txt.tmp *.chr') do set "m[%%a]=%%K"
      )

   ) else del key.txt.tmp 2>NUL & exit !m[%%a]!

   set /A ip+=1
)


:genchr
REM This code creates one single byte. Parameter: int
REM Teamwork of carlos, penpen, aGerman, dbenham
REM Tested under Win2000, XP, Win7, Win8
if %~1 neq 26 (
   makecab %options% /d reserveperfoldersize=%~1 t.tmp %~1.chr > nul
   type %~1.chr | ( (for /l %%N in (1,1,38) do pause)>nul & findstr "^" > temp.tmp )
   >nul copy /y temp.tmp /a %~1.chr /b
) else (
   copy /y nul + nul /a 26.chr /a >nul
)
exit /B

Antonio

[einstein1969]

With the new version I have tested the Hanoi Tower (Big file) and Sierpinski triangle (small file)

These are results:

Hanoi.bf

Parsing file:
dbenham BF 14:41:22,88 - 14:51:35,93 elapsed 61305 cs (old result)
aacini BF 17:06:43,16 - 17:16:18,57 elapsed 57541 cs

Loading parsed file:
aacini BF 17:38:31,51 - 17:39:05,96 elapsed 3445 cs

Saving parsed file
aacini BF 17:16:18,59 - 17:17:52,29 elapsed 9370 cs

Run:
dbenham BF about 55 cycles/s (old result)
aacini BF about 59 cycles/s

Triangle.bf

Parsing file:
dbenham BF 17:52:39,35 - 17:52:39,59 elapsed 24 cs
aacini BF 17:41:46,55 - 17:41:48,98 elapsed 243 cs

Loading parsed file:
aacini BF 18:08:33,67 - 18:08:33,70 elapsed 3 cs

Saving parsed file:
aacini BF 17:41:48,99 - 17:41:49,05 elapsed 6 cs

Run:
dbenham BF about 800 cycles/s
aacini BF about 750 cycles/s

For speed UP (especially big file) :

- Don't parse to env. Parse to local disk or keep the env small.
- The save parsed file phase could be avoided? (merged with parsing phase)
- For run: keep the env small (implement caching). Implement "pipeling".

einstein1969

[einstein1969]

I have implemented the tip for keep small environment.
The result is very good.

The code is quite versatile and can be used in many other programs.

I have modified the last dbenham version for now.

Hanoi.bf

Parsing file:
dbenham BF 14:41:22,88 - 14:51:35,93 elapsed 61305 cs (old result)
aacini BF 17:06:43,16 - 17:16:18,57 elapsed 57541 cs
dbenham BF optimized about 3600-4000 cs

Loading parsed file:
aacini BF 17:38:31,51 - 17:39:05,96 elapsed 3445 cs

Saving parsed file
aacini BF 17:16:18,59 - 17:17:52,29 elapsed 9370 cs

Run:
dbenham BF about 55 cycles/s (old result)
aacini BF about 59 cycles/s
dbenham BF optimized about 800-1100 cycles/s

For Triangle.bf the time is the same that not optimized version! Look at previous post.

the code: search "Speed up portion" for the changes.

Code: Select all

:: BF.BAT - BrainF*** interpreter in Batch
::
:: Usage:
::
::   bf sourceFile
::
:: The memory array consists of unsigned bytes. Increment and decrement
:: operations simply rollover when the limits are exceeded.
::
:: The memory array is unbounded both to the left and right
::
:: In theory, the code pointer can range from 1 to 2147483647,
:: and the memory pointer can range from -2147483648 to 2147483647.
:: But performance will become unbearable long before those limits are
:: reached.
::
:: BF.BAT can only read input from the keyboard. Input will fail
:: if data is piped into BF.BAT or if stdin is redirected to a file.
::
:: The <Enter> key is read as <CR>
:: All other inputs are normal.
::
:: Any byte value (except 0x00) may be entered by holding down the <Alt> key
:: and entering a decimal code on the numeric keypad.
::
:: The only way to enter <LF> is via <Alt> and the numeric keypad.
::
:: BF.BAT was developed by the following DosTips users:
::   Antonio Perez Ayala (aka Aacini)
::   Dave Benham         (aka dbenham)
::
:: This version was derived from Aacini's version 2.0
::
:: Development efforts can be traced at
:: http://www.dostips.com/forum/viewtopic.php?f=3&t=5751


@echo off
setlocal EnableDelayedExpansion
if "%~1" equ ":run" goto :run

:: Validate parameters
if "%~1" equ "" >&2 echo Usage: %~N0 filename.ext&exit /b 1
if not exist "%~1" >&2 echo File not found: %1&exit /b 1

:: Speed up portion : prepare
if not exist %tmp%\bf md %tmp%\bf
del /q %tmp%\bf
copy %1 %tmp%\bf >nul
pushd %tmp%\bf
 

:: Parse the code and for each op, store the op followed by a number
:: For [ and ] the number represents the address of the matching loop boundary
:: For all other ops the number represents the repeat count for that op.
set "operators=+-<>.,[]"
set /a ip=sp=count=0
set "lastOp="

:: Speed up portion : other speed up for big files
cmd /U /C type %1|find /V "" >tmp.bf
for /f %%b in (tmp.bf) do (

  :: Speed up portion : empty environment at 1% frequency
  if "!random:~-2!"=="00" for /F "delims==" %%v in ('2^>nul set code[') do (>%%v echo !%%v!&set %%v=)

  if "!operators:%%b=!" neq "%operators%" (
    if "!lastOp!" equ "%%b" (
      set /a count+=1
    ) else (
      if defined lastOp (
        set /a ip+=1
        set code[!ip!]=!lastOp! !count!
        set "lastOp="
        set "count=0"
      )
      if "%%b" equ "[" (
        set /a "ip+=1, sp+=1"
        set /a "stack[!sp!]=ip"
      ) else if "%%b" equ "]" (
        for %%s in (!sp!) do (
          set /a ip+=1, sp-=1
          set "code[!ip!]=] !stack[%%s]!"
          set "code[!stack[%%s]!]=[ !ip!"
        )
      ) else (
        set "lastOp=%%b"
        set "count=1"
      )
    )
  )
)
if %count% gtr 0 (
  set /a ip+=1
  set "code[!ip!]=%lastOp% %count%"
)
:: Speed up portion : empty environment from code[ , final part.
for /F "delims==" %%v in ('2^>nul set code[') do (>%%v echo !%%v!&set %%v=)

:: Error if unbalanced brackets
if %sp% neq 0 >&2 echo ERROR: Unbalanced brackets&exit /b 1

:: Create character files if they don't already exist
set "needChars="
for /l %%N in (0 1 255) do for %%F in (%%N.bf.chr) do if "%%~zF" neq "1" set "needChars=1"
if defined needChars call :genAllChr

:: Initialize memory to undefined (equivalent to 0)
for /f "delims==" %%A in ('set m[ 2^>nul') do set "%%A="

:: Define CR to hold <CarriageReturn> for use in input routine
for /f %%A in ('copy /Z "%~dpf0" nul') do set "CR=%%A"

:: Define SUB to hold <0x1A>
for /f "delims=" %%A in (26.bf.chr) do set "SUB=%%A"

:: Establish line one of input routine for this locale
set "line1="
for /f "delims=" %%L in (
  'echo .^|xcopy /w "%~f0" "%~f0" 2^>nul'
) do if not defined line1 set "line1=%%L"
set "line1=!line1:~0,-1!"

:: Launch the interpreter
cmd /c "%~f0" :run&&exit /b 0||exit /b 1


:run  - This is the main interpreter loop
set /a "ip=1, mp=0"
for /l %%. in () do for %%I in (!ip!) do (

 :: Speed up portion : empty environment at 0.1% frequency
 if "!random:~-3!"=="000" for /F "delims==" %%v in ('2^>nul set code[') do set %%v=
 if not defined code[%%I] (<"code[%%I]" set/p "code[%%I]=")

 for /F "tokens=1-3" %%A in ("!mp! !code[%%I]!") do (
  if        "%%B" equ "+" (
    set /a "m[%%A]=(m[%%A]+%%C)&255"
  ) else if "%%B" equ "-" (
    set /a "m[%%A]=(m[%%A]-%%C)&255"
  ) else if "%%B" equ ">" (
    set /a "mp+=%%C"
  ) else if "%%B" equ "<" (
    set /a "mp-=%%C"
  ) else if "%%B" equ "[" (
    if not defined m[%%A] set "ip=%%C"
    if "!m[%%A]!" equ "0" set "ip=%%C"
  ) else if "%%B" equ "]" (
    if defined m[%%A] if "!m[%%A]!" neq "0" set "ip=%%C"
  ) else if "%%B" equ "." for /l %%N in (1 1 %%C) do (
    if defined m[%%A] (
      if "!m[%%A]!" equ "26" (set /p "=!SUB!" < NUL) else type !m[%%A]!.bf.chr
    ) else type 0.bf.chr
  ) else if "%%B" equ "," for /l %%N in (1 1 %%C) do (
    set "key="
    set "CtrlC=1"
    for /f "delims=" %%K in (
      'xcopy /w "%~f0" "%~f0" 2^>nul'
    ) do if not defined key (
      setlocal disableDelayedExpansion
      set "key=%%K"
    ) else set "CtrlC="
    setlocal enableDelayedExpansion
    if defined CtrlC (
      endlocal&endlocal
      set "m[%%A]=3"
    ) else if "!key!" equ "!line1!" (
      endlocal&endlocal
      set "m[%%A]=10"
    ) else if "!key:~-1!" equ "!CR!" (
      endlocal&endlocal
      set "m[%%A]=13"
    ) else (
      >key.txt.tmp echo(!key:~-1!
      endlocal&endlocal
      for /f "delims=." %%K in ('findstr /lg:key.txt.tmp *.bf.chr') do set "m[%%A]=%%K"
    )
  ) else exit
  set /a ip+=1
 )
)


:genAllChr
::This code creates 256 1 byte files, one for each possible byte value.
::This is encoded in a macro way to be called asynchronously with start cmd /c
::Teamwork of carlos, penpen, aGerman, dbenham, einstein1969
::Tested under Win7 and XP
setlocal disableDelayedExpansion
set ^"genchr=(^
for /l %%N in (%%A !cnt! 255) do (^
  if %%N equ 26 (^
    copy /y nul + nul /a 26.bf.chr /a ^>nul^
  ) else (if %%N geq 35 if %%N leq 126 if %%N neq 61 (^
    ^<nul set /p "=!ascii:~%%N,1!" ^>%%N.bf.chr^
  ))^&^
  if not exist %%N.bf.chr (^
    makecab /d compress=off /d reserveperdatablocksize=26 /d reserveperfoldersize=%%N %%A.tmp %%N.bf.chr ^>nul^&^
    type %%N.bf.chr ^| ((for /l %%n in (1 1 38) do pause)^>nul^&findstr "^^" ^>%%N.temp)^&^
    ^>nul copy /y %%N.temp /a %%N.bf.chr /b^&^
    del %%N.temp^
  )^
))^&^
del %%A.tmp^"
del /f /q /a *bf.chr >nul 2>&1
set "ascii=                                   #$%%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
set /a cnt=number_of_processors
if %cnt% lss 1 set cnt=1
if %cnt% gtr 256 set cnt=256
set /a "end=cnt-1"
for /l %%A in (0 1 %end%) do (
  type nul >%%A.tmp
  if %%A equ %end% (
    cmd /q /v:on /c "%genchr%"
  ) else (
    start "" /b cmd /q /v:on /c "%genchr%"
  )
)
:genAllChr.check
for /l %%N in (0 1 %end%) do if exist %%N.tmp goto :genAllChr.check
exit /b

EDIT: Small change in parsed phase

einstein1969

.

[einstein1969]

I have added the test of the JWinslow23 version

Triangle.bf

Parsing file:
JWinslow23 BF about 100 cs
dbenham BF 17:52:39,35 - 17:52:39,59 elapsed 24 cs
Aacini BF 17:41:46,55 - 17:41:48,98 elapsed 243 cs
dbenham BF optimized about 25 cs
JWinslow23 BF optimized about 180 cs

Prepare memory:
JWinslow23 BF about 300 cs
JWinslow23 BF optimized about 800 cs

Loading parsed file:
Aacini BF 18:08:33,67 - 18:08:33,70 elapsed 3 cs

Saving parsed file:
Aacini BF 17:41:48,99 - 17:41:49,05 elapsed 6 cs

Run:
JWinslow23 BF about 75-100 cycles/s
dbenham BF about 800 cycles/s
Aacini BF about 750 cycles/s
dbenham BF optimized about 800 cycles/s
JWinslow23 BF optimized about 130-140 cycles/s

Hanoi.bf

Parsing file:
JWinslow23 BF about 126600 cs
dbenham BF 14:41:22,88 - 14:51:35,93 elapsed 61305 cs (old result)
Aacini BF 17:06:43,16 - 17:16:18,57 elapsed 57541 cs
dbenham BF optimized about 3600-4000 cs
JWinslow23 BF optimized about 10400 cs

Prepare memory:
JWinslow23 BF about 17400 cs
JWinslow23 BF optimized about 800 cs

Loading parsed file:
Aacini BF 17:38:31,51 - 17:39:05,96 elapsed 3445 cs

Saving parsed file
Aacini BF 17:16:18,59 - 17:17:52,29 elapsed 9370 cs

Run:
JWinslow23 BF about 5-6 cycles/s
dbenham BF about 55 cycles/s (old result)
Aacini BF about 59 cycles/s
dbenham BF optimized about 800-1100 cycles/s
JWinslow23 BF optimized about 140-160 cycles/s

einstein1969

[Aacini]

@dbenham:

I think this code execute an unmatched ENDLOCAL if the user press Ctrl-C:

Code: Select all

    set "key="
    set "CtrlC=1"
    for /f "delims=" %%K in (
      'xcopy /w "%~f0" "%~f0" 2^>nul'
    ) do if not defined key (
      setlocal disableDelayedExpansion
      set "key=%%K"
    ) else set "CtrlC="
    setlocal enableDelayedExpansion
    if defined CtrlC (
      endlocal&endlocal
      set "m[%%A]=3"
    ) else if "!key!" ...

In this case this point does not matter, but in other scenarios it may cause problems if an environment is improperly released. I slightly modified previous code this way:

Code: Select all

      set "key="
      set "CtrlC=1"
      setlocal DisableDelayedExpansion
      for /F "delims=" %%K in ('xcopy /W "%~F0" "%~F0" 2^>NUL') do (
         if not defined key (set "key=%%K") else set "CtrlC="
      )
      setlocal EnableDelayedExpansion
      if defined CtrlC (
         endlocal & endlocal
         set "m[%%a]=3"
    ) else if "!key!" ...

@einstein1969:

Implementing Demand paging memory-management in Batch? Crazy idea... But implement it in order to achieve a faster execution? This is the second most crazy idea I lately heard! (the first one was to develop a Brainf*ck interpreter in a Batch file). Usually the paging code insert some overhead so the code becomes slower, but it seems that the most important point in this case is to keep the environment as small as possible. Your "optimization" method is somewhat strange. Do you empty the environment at random intervals? The funny thing is that it works!

In order to develop a better optimization scheme based on keep the environment small, we need a way to identify and isolate code sections, so complete sections that will no longer be used for a while can be deleted, and complete sections that will be used can be reloaded in a more eficient way than line by line.

The version 3 of my BF interpreter allows to identify common code segments that are reused at several places, extract one of them in a "subroutine" and replace all repeated sections by an invocation of the just created subroutine. This subdivision instantly decrease the size of the executable code in a factor that may be important, and that usually increase as the original code is larger. Each subroutine is stored in a file, so it may be completely loaded in just one FOR /F loop. The program below use a very simple optimization approach: each subroutine is loaded before it is executed if its code is not defined, and the whole code (excepting the main program) is deleted each time that a first-level subroutine returns to the main program. However, this version also allows to get data that may be used to implement and test different optimization schemes. For example, keep small subroutines and delete the big ones, or keep the most frequently called subroutines and delete the rest, etc. You may also trace the subroutine tree used by all subroutines in a program and assemble "modules" that keep the subroutines used by everyone, and delete the rest, etc.

EDIT 2014-07-17: I fixed the bug related to loops placed immediately after a previous one, so Version 3 may correctly process TowerOfHanoi.b program now.

Code: Select all

@echo off
setlocal EnableDelayedExpansion
if "%~1" equ ":runCode" goto %1

rem bf.bat: Brainf*ck interpreter in Batch
rem Antonio Perez Ayala

rem Version 3:   - Minor mod in Dave Benham's input routine
rem              - Define subroutines from common code segments and modify the code to call they,
rem                parse each subroutine into its own file
rem                and load subroutine code on demand / delete all subs code on return from 1st-level subroutines
if "%~1" equ "" echo Usage: %~N0 filename.ext & goto :EOF
set "dir=%~PN1"
if exist "%dir%\sub0.bp" (
    echo A parsed version of this file exists
    choice /M "Do you want to use it "
    if !errorlevel! equ 1 goto Ascii
)
if not exist "%~1" echo File not found: %1 & goto :EOF


rem Phase I: Identify common subroutines, define they and shrink the code accordingly

set "input="
set "operators=+-<>.,[]"
set /A sp=0, sub=0
rem Initialize the main program
set "block[0]="
set discardNextBlock[0]=True
rem Initialize "[-]" subroutine (set m[%mp%]=0)
set "subTable[1][0]=-"
set /P "=Extracting subroutines." < NUL
for /F "delims=" %%b in ('cmd /U /C type "%~1" ^| find /V ""') do (
   if "!operators:%%b=!" neq "%operators%" if "%%b" neq "*" if "%%b" neq "~" (
      if "%%b" equ "[" (
         rem Start a new code block, don't include starting "["
         set /A sp+=1
         set "block[!sp!]="
         set "len[!sp!]=0"
      ) else if "%%b" equ "]" (
         rem Close this block
         for %%s in (!sp!) do (
            set "block=!block[%%s]!"
            set "block[%%s]="
            set "len=!len[%%s]!"
            set "len[%%s]="
         )
         set /A sp-=1
         if not defined discardNextBlock[!sp!] (
            rem Search this block in the subroutine table
            set "subNum="
            for /F "tokens=3* delims=[]=" %%i in ('set subTable[!len!] 2^>NUL') do (
               if "!block!" equ "%%j" set subNum=%%i
            )
            if not defined subNum (
               rem Define a new subroutine with this block
               set /A sub+=1, subNum=sub
               set "subTable[!len!][!sub!]=!block!"
               set /P "=." < NUL > CON
            )
            rem Get the length of this number (4 digits max)
            for /L %%i in (0,1,3) do if "!subNum:~%%i,1!" neq "" set len=%%i
            rem Replace this block by its subroutine number ("call") in the nesting code
            for %%s in (!sp!) do set "block[%%s]=!block[%%s]!!subNum!" & set /A len[%%s]+=len+1
         )
         set discardNextBlock[!sp!]=True
      ) else (
         rem Normal operator: insert it in current block
         for %%s in (!sp!) do (
            set "block[%%s]=!block[%%s]!%%b"
            set /A len[%%s]+=1
            set "discardNextBlock[%%s]="
         )
         if "%%b" equ "," set input=True
      )
   )
)
echo/
if %sp% neq 0 echo ERROR: Unbalanced brackets & goto :EOF
rem Delete subroutine "[-]" (special case)
set "subTable[1][0]="
rem Transfer main program code to "subroutine 0"
set "subTable[0][0]=!block[0]!"
set "block[0]="


rem Phase II: Parse subroutines into their own files

set /P "=Parsing subroutines." < NUL
if not exist "%dir%" (md "%dir%") else del /Q "%dir%\*.*"
set "digits=0123456789"
for /F "tokens=3* delims=[]=" %%i in ('set subTable[') do (
   rem Initialize values for *each* subroutine
   set "sub="
   set "lastOp="
   set /A ip=1, count=0
   ( rem Start of redirected block
   for /F "delims=" %%b in ('cmd /U /C set /P "=%%j" ^<NUL ^| find /V ""') do (
      if "!lastOp!" equ "%%b" (
         set /A count+=1
      ) else (
         if defined lastOp (
            set /A ip+=1
            echo "s%%i[!ip!]=!lastOp! !count!"
            set "lastOp="
            set count=0
         )
         if "!digits:%%b=!" neq "%digits%" (
            rem Digit: assemble subroutine name
            set "sub=!sub!%%b"
         ) else (
            if defined sub (
               rem Insert subroutine call
               set /A ip+=1
               if !sub! equ 0 (echo "s%%i[!ip!]== 0") else echo "s%%i[!ip!]=C !sub!"
               set "sub="
            )
            set "lastOp=%%b"
            set count=1
         )
      )
   )
   if defined sub (
      set /A ip+=1
      if !sub! equ 0 (echo "s%%i[!ip!]== 0") else echo "s%%i[!ip!]=C !sub!"
   )
   if defined lastOp (
      set /A ip+=1
      echo "s%%i[!ip!]=!lastOp! !count!"
   )
   rem Insert "[" and "]" at begin and end of subroutines
   if %%i neq 0 (
      set /A ip+=1
      echo "s%%i[1]=[ !ip!"
      echo "s%%i[!ip!]=] 1"
   )
   rem Be sure that subroutine code ends here (insert "return")
   set /A ip+=1
   echo "s%%i[!ip!]="
   rem End of redirected block
   ) > "%dir%\sub%%i.bp"
   set /P "=." < NUL
)

:Ascii
echo/
set /P "=Creating Ascii tables." < NUL
type nul > t.tmp
set "options=/d compress=off /d reserveperdatablocksize=26"
for /L %%i in (0,1,255) do (
   if not exist %%i.chr call :genchr %%i
   set /A mod=%%i %% 16
   if !mod! equ 0 set /P "=." < NUL
)
set "options="
del t.tmp temp.tmp
echo/

echo Running.
cmd /Q /C "%~F0" :runCode
exit /B %errorlevel%

:runCode
rem Delete *all* environment variables, excepting "dir", and "Path" if input routine will be used
if defined input (for %%a in (xcopy.exe) do set "Path=%%~DP$Path:a") else set "Path="
for /F "delims==" %%v in ('set') do if "%%v" neq "dir" if /I "%%v" neq "Path" set "%%v="
if defined Path (
   rem Define variables for input routine
   for /F %%a in ('copy /Z "%~F0" NUL') do set "CR=%%a"
   for /F "delims=" %%a in (26.chr) do set "SUB=%%a"
   for /F "delims=" %%a in ('echo .^|xcopy /W "%~F0" "%~F0" 2^>NUL') do if not defined line1 set "line1=%%a"
   set "line1=!line1:~0,-1!"
)
rem Read main program code and start run cycle
for /F "usebackq delims=/" %%a in ("%dir%\sub0.bp") do set %%a
set /A nSub=0, ip=2, ps=0, mp=0
set "tk[0]=0 0"

for /L %%? in () do for /F "tokens=1,2" %%i in ("!nSub! !ip!") do for /F "tokens=1-3" %%a in ("!mp! !s%%i[%%j]!") do (
   if        "%%b" equ "+" (
      set /A "m[%%a]=(m[%%a]+%%c) & 255"
   ) else if "%%b" equ "-" (
      set /A "m[%%a]=(m[%%a]-%%c) & 255"
   ) else if "%%b" equ "=" (
      set "m[%%a]=%%c"
   ) else if "%%b" equ ">" (
      set /A "mp=(mp+%%c) & 4095"
   ) else if "%%b" equ "<" (
      set /A "mp=(mp-%%c) & 4095"
   ) else if "%%b" equ "[" (
      if not defined m[%%a] ( set ip=%%c
      ) else if "!m[%%a]!" equ "0" set ip=%%c
   ) else if "%%b" equ "]" (
      if defined m[%%a] if "!m[%%a]!" neq "0" set ip=%%c
   ) else if "%%b" equ "." (

      for /L %%i in (1,1,%%c) do (
         if defined m[%%a] (
            if        "!m[%%a]!" equ "10" (
                echo/
            ) else if "!m[%%a]!" equ "26" (
               set /P "=!SUB!" < NUL
            ) else (
               type !m[%%a]!.chr
            )
         ) else (
            type 0.chr
         )
      )

   ) else if "%%b" equ "," (

      set "key="
      set "CtrlC=1"
      setlocal DisableDelayedExpansion
      for /F "delims=" %%K in ('xcopy /W "%~F0" "%~F0" 2^>NUL') do (
         if not defined key (set "key=%%K") else set "CtrlC="
      )
      setlocal EnableDelayedExpansion
      if defined CtrlC (
         endlocal & endlocal
         set "m[%%a]=3"
      ) else if "!key!" equ "!line1!" (
         endlocal & endlocal
         set "m[%%a]=10"
      ) else if "!key:~-1!" equ "!CR!" (
         endlocal & endlocal
         set "m[%%a]=13"
      ) else (
         > key.txt.tmp echo(!key:~-1!
         endlocal & endlocal
         for /F "delims=." %%K in ('findstr /LG:key.txt.tmp *.chr') do set "m[%%a]=%%K"
      )

   ) else if "%%b" equ "C" ( rem Call subroutine %%c:
      rem If the subroutine code is not defined, load it
      if not defined s%%c[1] for /F "usebackq delims=/" %%v in ("%dir%\sub%%c.bp") do set %%v
      rem Push return address in the "stack"
      set /A ps+=1
      set "tk[!ps!]=!nSub! !ip!"
      rem Jump to the subroutine
      set /A nSub=%%c, ip=0

   ) else ( rem Subroutine ends
      rem Pop return address from the "stack"
      for %%s in (!ps!) do for /F "tokens=1,2" %%x in ("!tk[%%s]!") do set /A nSub=%%x, ip=%%y
      set "tk[!ps!]="
      set /A ps-=1
      rem If return to main program, delete code of all subroutines, excepting main program
      if !ps! equ 0 for /F "delims==" %%v in ('set s') do (
         set "v=%%v"
         if "!v:~0,3!" neq "s0[" set "%%v="
      )
      rem If main program ends, end run
      if !ps! equ -1 del key.txt.tmp 2>NUL & exit !m[%%a]!

   )

   set /A ip+=1
)


:genchr
REM This code creates one single byte. Parameter: int
REM Teamwork of carlos, penpen, aGerman, dbenham
REM Tested under Win2000, XP, Win7, Win8
if %~1 neq 26 (
   makecab %options% /d reserveperfoldersize=%~1 t.tmp %~1.chr > nul
   type %~1.chr | ( (for /l %%N in (1,1,38) do pause)>nul & findstr "^" > temp.tmp )
   >nul copy /y temp.tmp /a %~1.chr /b
) else (
   copy /y nul + nul /a 26.chr /a >nul
)
exit /B

This Batch file will fail if the BF program have this wrong code: "[any loop][...]". This code have no sense, because after exit from first loop it will not enter to the second one, unless the second loop is used to clear the current cell: "[any loop][-]", but this is also meaningless, because at that point the current cell is zero already! This type of code indicate that the program was not originally written in BF, but perhaps it was translated from another source, like TowerOfHanoi.b (in my opinion, this is cheating). If you want to test TowerOfHanoi.b in my BF interpreter Version 3 (or any BF program, for that matter), be sure to first replace all "][-]" segments by just "]".

EDIT 2014-07-17: I fixed previous problem in my BF interpreter Version 3; the corrected code is above.

Antonio

[dbenham]

@einstein1969:

Implementing Demand paging memory-management in Batch? Crazy idea... But implement it in order to achieve a faster execution? This is the second most crazy idea I lately heard! (the first one was to develop a Brainf*ck interpreter in a Batch file). Usually the paging code insert some overhead so the code becomes slower, but it seems that the most important point in this case is to keep the environment as small as possible. Your "optimization" method is somewhat strange. Do you empty the environment at random intervals? The funny thing is that it works!

@einstein1969 -I totally agree with Aacini. I never would have thought to randomize the code paging, and I'm amazed that it works

In order to develop a better optimization scheme based on keep the environment small, we need a way to identify and isolate code sections, so complete sections that will no longer be used for a while can be deleted, and complete sections that will be used can be reloaded in a more efficient way than line by line.

The version 3 of my BF interpreter allows to identify common code segments that are reused at several places, extract one of them in a "subroutine" and replace all repeated sections by an invocation of the just created subroutine. This subdivision instantly decrease the size of the executable code in a factor that may be important, and that usually increase as the original code is larger. Each subroutine is stored in a file, so it may be completely loaded in just one FOR /F loop. The program below use a very simple optimization approach: each subroutine is loaded before it is executed if its code is not defined, and the whole code (excepting the main program) is deleted each time that a first-level subroutine returns to the main program. However, this version also allows to get data that may be used to implement and test different optimization schemes. For example, keep small subroutines and delete the big ones, or keep the most frequently called subroutines and delete the rest, etc. You may also trace the subroutine tree used by all subroutines in a program and assemble "modules" that keep the subroutines used by everyone, and delete the rest, etc.

I like your thinking. I haven't traced how you identify subroutines (pages), but I'm thinking that the best paging scheme would be to keep the most recently used pages, and discard the page that hasn't been used for a "long" time, even if it was used frequently. But page management logic could get fairly complex, requiring significant code. The interpreter loop runs fastest when the amount of code in the loop is minimized. If page faults are kept to a minimum, then it would probably be better to detect a page fault within the loop, but then CALL out to a :subroutine to handle the remainder of the page management.

@dbenham:

I think this code execute an unmatched ENDLOCAL if the user press Ctrl-C:

Code: Select all

    set "key="
    set "CtrlC=1"
    for /f "delims=" %%K in (
      'xcopy /w "%~f0" "%~f0" 2^>nul'
    ) do if not defined key (
      setlocal disableDelayedExpansion
      set "key=%%K"
    ) else set "CtrlC="
    setlocal enableDelayedExpansion
    if defined CtrlC (
      endlocal&endlocal
      set "m[%%A]=3"
    ) else if "!key!" ...

In this case this point does not matter, but in other scenarios it may cause problems if an environment is improperly released. I slightly modified previous code this way:

Code: Select all

      set "key="
      set "CtrlC=1"
      setlocal DisableDelayedExpansion
      for /F "delims=" %%K in ('xcopy /W "%~F0" "%~F0" 2^>NUL') do (
         if not defined key (set "key=%%K") else set "CtrlC="
      )
      setlocal EnableDelayedExpansion
      if defined CtrlC (
         endlocal & endlocal
         set "m[%%a]=3"
    ) else if "!key!" ...

No, my code is correct. The XCOPY command always has at least one line of output, so the SETLOCAL is always executed exactly once. The Ctrl-C flag is only cleared if there are two or more lines of output. That being said, I like your idea of moving the SETLOCAL before the loop... it is less obfuscated.

This Batch file will fail if the BF program have this wrong code: "[any loop][...]". This code have no sense, because after exit from first loop it will not enter to the second one, unless the second loop is used to clear the current cell: "[any loop][-]", but this is also meaningless, because at that point the current cell is zero already! This type of code indicate that the program was not originally written in BF, but perhaps it was translated from another source, like TowerOfHanoi.b (in my opinion, this is cheating). If you want to test TowerOfHanoi.b in my BF interpreter Version 3 (or any BF program, for that matter), be sure to first replace all "][-]" segments by just "]".

No, putting a loop immediately after the close of another loop is a safe way to embed comments containing op codes. It is frequently used by many brainF*** geeks. (brainF*** developer just doesn't seem to be an appropriate term). The only restriction to such comments is that they not contain unbalanced square brackets.


Well I've been busy myself taking on some other design considerations.

My version 3 focuses on the following:

1) Command line options

I won't describe them here. Read the opening code comments for a description of all the command line options.

2) Code parsing optimization

- Like einstein1969, I also had the realization that use of a temp file can dramatically increase the main parsing loop performance. In addition, I use FINDSTR to screen for op codes instead of screening within the loop.

- I collapse [-] into a single 0 op, which sets the value to zero at the current memory address.

- I treat a loop as a comment if it appears at the beginning, or immediately after the close of another loop. Comment loops are simply discarded.

- I added support for the often used # op extension, which is an instruction to show the current state ( ip address and value, mp address and value(s) )

- I detect whether input was used (important for interpreter optimization)

3) Interpreter optimization

The more code that resides within the interpreter loop, the slower it gets. The code to get input is the most complex code within the interpreter, but many bf programs never use input. So I decided to convert my interpreter into a dynamically defined simple macro. I only include code that is needed. If input is not required, then I don't include the code in the interpreter macro. This provided a large performance boost for the triangle.

Another alternative would be to implement the input routine as a CALLed :subroutine. This would also dramatically increase the loop performance. The overhead of using CALL for interactive input is a non-issue.

Even if I were to use the CALL technique for input, my many command line options still make it worthwhile to dynamically define my interpreter.

To do list

- Add an option to get input from a file instead of the keyboard. (I'll use the FC technique to read each byte of input - probably via pre-processing)

- Implement my own version of code paging

- Implement memory paging

- Add an option to measure and display the number of execution cycles (both logical and physical), and number of page faults (both code and memory)

Here is my version 3

Code: Select all

::BF.BAT - BrainF*** interpreter in Batch, dbenham version 3.0
::
:: Usage:
::
::   bf sourceFile [-option [value]]...
::
:: Options
::
::   -z           = <Ctrl-Z> terminates keyboard input (forces EOF).
::
::   -e Value     = EOF value: Sets value read into memory upon End-Of-File.
::                  Default is no change to memory.
::
::   -ee          = terminate with Error if attempt is made to read past EOF.
::
::   -eo          = terminate with Error if +/- results in Overflow.
::
::   -em          = terminate with Error if < yields a negative Memory address.
::
::   -ea          = terminate with Error on Any fault. Same as -ee -eo -em
::
::   -s           = Silent mode. Don't print initialization messages or elapsed
::                  times.
::
::   -d Filename  = Dump the parsed op codes to Filename.
::                  Use con to print to screen.
::
::   -m Filename  = write the interpreter Macro to Filename.
::                  Use con to print to screen.
::
::   -t           = Trace mode: Show op address/value, memory address/value
::                  each cycle.
::
::   -# Count     = Enables # op: Show current state. Count specifies the number
::                  of values to display before and after the current address.
::
::   -p           = Parse only.
::
::
:: The memory array consists of unsigned bytes. Increment and decrement
:: operations simply wrap when the limits are exceeded unless -eo is specified.
::
:: The memory array is unbounded both to the left and right. If -em is specified
:: then the array is unbounded to the right only.
::
:: In theory, the code pointer can range from 0 to 2147483647,
:: and the memory pointer can range from -2147483648 to 2147483647.
:: But performance will become unbearably long before those limits are
:: reached.
::
:: BF.BAT can only read input from the keyboard. Input will fail
:: if data is piped into BF.BAT or if stdin is redirected to a file.
::
:: The <Enter> key is read as <CR>
:: All other inputs are normal.
::
:: Any byte value (except 0x00) may be entered by holding down the <Alt> key
:: and entering a decimal code on the numeric keypad.
::
:: The only way to enter <LF> is via <Alt> and the numeric keypad.
::
:: This code was written by Dave Benham (aka dbenham)
:: with major contributions from Antonio Perez Ayala (aka Aacini).
::
:: This version was derived from Aacini's version 2.0
::
:: Development efforts can be traced at
:: http://www.dostips.com/forum/viewtopic.php?f=3&t=5751

@echo off
:: Rentry point when running the bf program
if "%~1" equ ":run" ( rem
  %bfInterpreter%
)

:: Clear environment except for critical standard values
setlocal disableDelayedExpansion
for /f "eol== delims==" %%V in ('set^|findstr /rc:"^[^=]*!"') do set "%%V="
set "preserve= TEMP TMP PATH PATHEXT COMSPEC PRESERVE "
setlocal enableDelayedExpansion
for /f "eol== delims==" %%V in ('set') do (
  if defined %%V if "!preserve: %%V =!" equ "!preserve!" set "%%V="
)
set "preserve="

:: Validate parameters
if "%~1" equ "" >&2 echo Usage: %~N0 filename.ext&exit /b 1
if not exist "%~1" >&2 echo File not found: %1&exit /b 1

:: Define options
set options=-d:"" -s: -z: -e:"" -m:"" -ee: -eo: -em: -ea: -t: -#:"" -p:

:: Set option defaults
for %%O in (%options%) do for /f "tokens=1,* delims=:" %%A in ("%%O") do set "%%A=%%~B"

:loop Parse the option arguments
if not "%~2"=="" (
  set "test=!options:*%~2:=! "
  if "!test!"=="!options! " (
    echo Error: Invalid option %~2
    exit /b 1
  ) else if "!test:~0,1!"==" " (
    set "%~2=1"
  ) else (
    set "%~2=%~3"
    shift /2
  )
  shift /2
  goto :loop
)

:: Begin macro defnitions --------------

:: Define LF to contain a linefeed (0x0A) character
set ^"LF=^

^" The above empty line is critical - DO NOT REMOVE

:: define a newline with line continuation
set ^"\n=^^^%LF%%LF%^%LF%%LF%^^"

set showTime=(%\n%
  set "t2=^!time^!"%\n%
  for /f "tokens=1-4 delims=:.," %%a in ("^!t1: =0^!"^) do set /a "t1=(((1%%a*60)+1%%b)*60+1%%c)*100+1%%d-36610100"%\n%
  for /f "tokens=1-4 delims=:.," %%a in ("^!t2: =0^!"^) do set /a "t2=(((1%%a*60)+1%%b)*60+1%%c)*100+1%%d-36610100"%\n%
  set /a "tDiff=t2-t1"%\n%
  if ^^!tDiff^^! lss 0 set /a tDiff+=24*60*60*100%\n%
  set /a "s=tDiff/100, f=tDiff+100"%\n%
  echo   Elapsed time = ^^!s^^!.^^!f:~-2^^! s%\n%
^)

if defined -ea (
  set -eo=1
  set -em=1
  set -ee=1
)

if defined -eo (
  set "inc=set /a m[%%A]+=%%C&if ^!m[%%A]^! gtr 255 >&2 echo ERROR: Overflow at ip=%%I mp=%%A&exit 1"
  set "dec=set /a m[%%A]-=%%C&if ^!m[%%A]^! lss 0 >&2 echo ERROR: Overflow at ip=%%I mp=%%A&exit 1"
) else (
  set inc=set /a "m[%%A]=(m[%%A]+%%C)&255"
  set dec=set /a "m[%%A]=(m[%%A]-%%C)&255"
)

if defined -em (
  set "leftError=&if ^!mp^! lss 0 >&2 echo ERROR: Invalid memory access at ip=%%I mp=%%A&exit 1"
)

if defined -t set "trace=echo  c[%%I]=^!c[%%I]^!   m[%%A]=^!m[%%A]^!"

if defined -e set ^"setEOF=set "m[%%A]=!-e!"^"

if defined -z (
  set "ifNotEOF=if not defined EOF ("
  set ifSub=else if "^!key:~-1^!" equ "^!SUB^!" (%\n%
      endlocal^&endlocal%\n%
      set EOF=1%\n%
      !setEOF!%\n%
    ^)
  if defined -ee (
    set "elsePastEOF=) else (>&2 echo ^!LF^!ERROR: Read past EOF at ip=%%I mp=%%A&exit 1)"
  ) else if defined -e (
    set "elsePastEOF=) else (!setEOF!)"
  ) else set "elsePastEOF=)"
)

set getInput=else if "%%B" equ "," (!ifNotEOF! for /l %%N in (1 1 %%C) do (%\n%
    set "key="%\n%
    set "CtrlC=1"%\n%
    setlocal disableDelayedExpansion%\n%
    for /f "delims=" %%K in (%\n%
      'xcopy /w "%~f0" "%~f0" 2^^^^^>nul'%\n%
    ^) do if not defined key (set "key=%%K") else set "CtrlC="%\n%
    setlocal enableDelayedExpansion%\n%
    if defined CtrlC (%\n%
      endlocal^&endlocal%\n%
      set "m[%%A]=3"%\n%
    ^) else if "^!key^!" equ "^!line1^!" (%\n%
      endlocal^&endlocal%\n%
      set "m[%%A]=10"%\n%
    ^) else if "^!key:~-1^!" equ "^!CR^!" (%\n%
      endlocal^&endlocal%\n%
      set "m[%%A]=13"%\n%
    ^) !ifSub! else (%\n%
      ^>key.txt.tmp echo(^^!key:~-1^^!%\n%
      endlocal^&endlocal%\n%
      for /f "delims=." %%K in ('findstr /lg:key.txt.tmp *.bf_chr'^) do set "m[%%A]=%%K"%\n%
    ^)%\n%
  ^) !elsePastEOF!^)

if defined -# (

  set #=#

  set #Parse=else if "%%b" equ "#" (%\n%
        set /a "ip+=1, #Found=1"%\n%
        set "c[^!ip^!]=#"%\n%
      ^)

  if !-#! equ 0 (
    set #Exec=else if "%%B" equ "#" (%\n%
    set /a next=ip+1%\n%
    for %%N in (^^!next^^!^) do echo  c[%%N]=^^!c[%%N]^^!  m[%%A]=^^!m[%%A]^^!%\n%
  ^)
  ) else set #Exec=else if "%%B" equ "#" (%\n%
    set /a next=ip+1, m1=mp-!-#!, m2=mp-1, m3=mp+1, m4=mp+!-#!%\n%
    for %%N in (^^!next^^!^) do set "msg=c[%%N]=^!c[%%N]^!  mp=%%A: "%\n%
    for /l %%N in (^^!m1^^! 1 ^^!m2^^!^) do set "msg=^!msg^!| ^!m[%%N]^! "%\n%
    set "msg=^!msg^!< ^!m[%%A]^! >"%\n%
    for /l %%N in (^^!m3^^! 1 ^^!m4^^!^) do set "msg=^!msg^! ^!m[%%N]^! |"%\n%
    echo  ^^!msg^^!%\n%
  ^)

)

:: End macro definition ------------------

:: Create character files if they don't already exist
if not defined -s (
  echo ----------------------------
  echo Begin Initialization
  echo Testing ASCII character files.
)
set "needChars="
for /l %%N in (0 1 255) do for %%F in (%%N.bf_chr) do if "%%~zF" neq "1" set "needChars=1"
if defined needChars (
  if not defined -s (
    echo Creating ASCII character files...
    set "t1=!time!"
  )
  call :genAllChr
  if not defined -s %showTime%
)

:: Parse the code and for each op, store the op followed by a number.
:: For [ and ] the number represents the address of the matching loop boundary
:: For all other ops the number represents the repeat count for that op.
:: Optionally treats # as an additional show state op code with constant count.
:: Optimization collapses [-] into special 0 op (no count).
:: Detects if input is not used so getInput can be removed from interpreter loop.
:: Treats loops at beginning or immedieately following ] as comments (ignores them)
if not defined -s (
  <nul set /p "=Parsing code."
  set "parseProgress=set /a n=(n+1^^)%%500&if ^!n^! equ 0 <nul set /p "=.""
  set "t1=!time!"
)
for %%C in (+ - "<" ">" . "," #) do set "comment%%~C=0"
set /a ip=comment]=-1, sp=count=comment=0, comment[=1
cmd /u /c type %1|find /v ""|findstr "[+\-<>.,[\]!#!]" >src.bf_tmp
for /f %%b in (src.bf_tmp) do ( %parseProgress%
  if !comment! gtr 0 (
    set /a comment+=!comment%%b!
  ) else if "!lastOp!" equ "%%b" (
    set /a count+=1
  ) else (
    if defined lastOp (
      set /a ip+=1
      set c[!ip!]=!lastOp! !count!
      set "lastOp="
    )
    if "%%b" equ "[" (
      if defined comment (set /a comment+=1) else (
        set /a "ip+=1, sp+=1"
        set /a "stack[!sp!]=ip"
      )
    ) else if "%%b" equ "]" for %%s in (!sp!) do for %%i in (!ip!) do (
      2>nul set /a "1/^!(%%i-stack[%%s]-^!(1+!c[%%i]!))" && (
        set /a "c[!stack[%%s]!]=0, ip-=1, sp-=1"
        set "c[%%i]="
      ) || (
        set /a ip+=1, sp-=1
        set "c[!ip!]=] !stack[%%s]!"
        set "c[!stack[%%s]!]=[ !ip!"
      )
      set "comment=0"
    ) %#Parse% else (
      set "comment="
      set "lastOp=%%b"
      set "count=1"
      if "%%b" equ "," set inputRequired=1
    )
  )
)
if defined lastOp (
  set /a ip+=1
  set "c[!ip!]=%lastOp% %count%"
)
if not defined -s (
  set "t2=!time!"
  echo(
  %showTime%
)

:: Error if unbalanced brackets
if %sp% neq 0 >&2 echo ERROR: Unbalanced brackets&exit /b 1
if defined comment if "%comment%" neq "0" >&2 echo ERROR: Unbalanced brackets&exit /b 1

:: Dump the parsed op codes
if defined -d (
  for /l %%N in (0 1 !ip!) do set c[%%N]
) >!-d!

:: Undefine getInput and/or #Parse if not needed
if not defined inputRequired set "getInput="
if not defined #Found set "#Exec="

:: Define CR to hold <CarriageReturn> for use in input routine
for /f %%A in ('copy /Z "%~dpf0" nul') do set "CR=%%A"

:: Define SUB to hold <0x1A>
for /f "delims=" %%A in (26.bf_chr) do set "SUB=%%A"

:: Establish line one of input routine for this locale
set "line1="
for /f "delims=" %%L in (
  'echo .^|xcopy /w "%~f0" "%~f0" 2^>nul'
) do if not defined line1 set "line1=%%L"
set "line1=!line1:~0,-1!"

:: Create final interpreter macro
set bfInterpreter=^
set /a "ip=mp=0"%\n%
for /l %%. in () do for %%I in (^^!ip^^!) do for /F "tokens=1-3" %%A in ("^!mp^! ^!c[%%I]^!") do (!trace!%\n%
  if        "%%B" equ "+" (%\n%
    !inc!%\n%
  ) else if "%%B" equ "-" (%\n%
    !dec!%\n%
  ) else if "%%B" equ "0" (%\n%
    set "m[%%A]=0"%\n%
  ) else if "%%B" equ ">" (%\n%
    set /a "mp+=%%C"%\n%
  ) else if "%%B" equ "<" (%\n%
    set /a "mp-=%%C"!leftError!%\n%
  ) else if "%%B" equ "[" (%\n%
    if not defined m[%%A] set "ip=%%C"%\n%
    if "^!m[%%A]^!" equ "0" set "ip=%%C"%\n%
  ) else if "%%B" equ "]" (%\n%
    if defined m[%%A] if "^!m[%%A]^!" neq "0" set "ip=%%C"%\n%
  ) else if "%%B" equ "." for /l %%N in (1 1 %%C) do (%\n%
    if defined m[%%A] (%\n%
      if "^!m[%%A]^!" equ "26" (set /p "=^!SUB^!" ^<nul) else type ^^!m[%%A]^^!.bf_chr%\n%
    ) else type 0.bf_chr%\n%
  ) !getInput! !#Exec! else exit 0%\n%
  set /a ip+=1%\n%
)

:: Print out the finalized brainF*** interpreter macro
if defined -m >!-m! echo bfInterpreter=!lf!!bfInterpreter:%%=%%%%!


if not defined -s (
  echo Initialization complete
  echo ============================
  set t1=%time%
)

if defined -p exit /b 0

:: Launch the interpreter
cmd /v:on /c "%~f0" :run&&(call )||(call)

if not defined -s (
  set t2=%time%
  echo(
  echo ============================
  %showTime%
)
exit /b %errorlevel%

:genAllChr
::This code creates 256 1 byte files, one for each possible byte value.
::This is encoded in a macro way to be called asynchronously with start cmd /c
::Teamwork of carlos, penpen, aGerman, dbenham, einstein1969
::Tested under Win7 and XP
setlocal disableDelayedExpansion
set ^"genchr=(^
for /l %%N in (%%A !cnt! 255) do (^
  if %%N equ 26 (^
    copy /y nul + nul /a 26.bf_chr /a ^>nul^
  ) else (if %%N geq 35 if %%N leq 126 if %%N neq 61 (^
    ^<nul set /p "=!ascii:~%%N,1!" ^>%%N.bf_chr^
  ))^&^
  if not exist %%N.bf_chr (^
    makecab /d compress=off /d reserveperdatablocksize=26 /d reserveperfoldersize=%%N %%A.tmp %%N.bf_chr ^>nul^&^
    type %%N.bf_chr ^| ((for /l %%n in (1 1 38) do pause)^>nul^&findstr "^^" ^>%%N.temp)^&^
    ^>nul copy /y %%N.temp /a %%N.bf_chr /b^&^
    del %%N.temp^
  )^
))^&^
del %%A.tmp^"
del /f /q /a *bf.chr >nul 2>&1
set "ascii=                                   #$%%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
set /a cnt=number_of_processors
if %cnt% lss 1 set cnt=1
if %cnt% gtr 256 set cnt=256
set /a "end=cnt-1"
for /l %%A in (0 1 %end%) do (
  type nul >%%A.tmp
  if %%A equ %end% (
    cmd /q /v:on /c "%genchr%"
  ) else (
    start "" /b cmd /q /v:on /c "%genchr%"
  )
)
:genAllChr.check
for /l %%N in (0 1 %end%) do if exist %%N.tmp goto :genAllChr.check
exit /b

Dave Benham

[Aacini]

@dbenham: Yes, I now realized that your code for input routine is right (it does NOT execute an unmatched ENDLOCAL). Precisely the trick is that when XCOPY is cancelled with Ctrl-C, it just output one line instead of more!

This Batch file will fail if the BF program have this wrong code: "[any loop][...]". This code have no sense, because after exit from first loop it will not enter to the second one, unless the second loop is used to clear the current cell: "[any loop][-]", but this is also meaningless, because at that point the current cell is zero already! This type of code indicate that the program was not originally written in BF, but perhaps it was translated from another source, like TowerOfHanoi.b (in my opinion, this is cheating). If you want to test TowerOfHanoi.b in my BF interpreter Version 3 (or any BF program, for that matter), be sure to first replace all "][-]" segments by just "]".

No, putting a loop immediately after the close of another loop is a safe way to embed comments containing op codes. It is frequently used by many brainF*** geeks. (brainF*** developer just doesn't seem to be an appropriate term). The only restriction to such comments is that they not contain unbalanced square brackets.

Yes, you are right about embedded comments, but what do you think of "[any loop][-]" code? TowerOfHanoi.b have 227 of such constructs. As the author indicated, TowerOfHanoi.b was originally written in a high level language and then translated to BF. I call this cheating! Anyway, I need to insert your elimination of second [...] loop in my program.

I like this phrase: "brainF*** geeks. (brainF*** developer just doesn't seem to be an appropriate term)". I hope that brainf*ck geeks do NOT know about this thread. The goal of that people is to write every time smaller BF compilers, but here we are writting every time larger BF Batch file interpreters!

I think of an optimization trick about the memory tape: delete the current cell every time that it becomes zero. This way, the "[" and "]" tests just need to include the "if defined m[%%a]..." part and we may remove the "if !m[%%a]! equ 0 ...". This trick also eliminate the need of paging the memory tape (as long as a BF program does not use larger amounts of memory cells).

I used Eric Bosman's Mandelbrot.b program to test my BF interpreter. After I completed my Version 2.1 I left Mandelbrot.b running as the only process in my laptop for a little more than 14 hours and then cancelled it. I just get this output:

Code: Select all

A parsed version of this file exists
Do you want to use it [S,N]?S

Creating Ascii tables.................
Running.
AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDEGF¨Desea terminar el trabajo por lotes (S/N)? ¨Desea terminar el trabajo por lotes (S/N)? 

That is, just the first 79 characters of the first line; this program show lines with 120 characters each.

Last night, after I posted my new Version 3, I left the same program running under the same conditions. After about almost two hours less time, I cancelled it and get this output:

Code: Select all

A parsed version of this file exists
Do you want to use it [S,N]?S

Creating Ascii tables.................
Running.
AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDEGFFEEEEDDDDD¨Desea terminar el trabajo por lotes (S/N)? ¨Desea terminar el trabajo por lotes (S/N)? 

That is, 10 characters more. If we take into account that the additional characters represent larger recursive levels than previous characters and that the new version run for less time, this means that Version 3 run much faster than Version 2.1. A precise timing test must be completed.

I am planning a modification in the subroutine-based optimization scheme that I hope will give better results!

Antonio

PS - Where is Sierpinski triangle program?

[einstein1969]

@Aacini,dbenham

The routine that empty the env is not complete random. It use the Law_of_large_numbers

This explain why is use this method.

This code:

Code: Select all

@echo off & setlocal EnableDelayedExpansion

for /F "Tokens=1 delims==" %%v in ('set') do if /I NOT %%v == USERPROFILE set "%%v="

set C=0

>t0.dat echo !time!

For /L %%N in (1,1,30000) do (

   ::Do some work
   set /a A=A+2+A/2

   if !random:~-2! equ 00 (
      for /F "Tokens=1 delims==" %%v in ('set A') do set "%%v="
      set /a C+=1
   )

)

set t1=!time!
set/p"t0="<t0.dat

for /F "tokens=1-8 delims=:.," %%a in ("!t0: =0!:!t1: =0!") do set /a "a=(((1%%e-1%%a)*60)+1%%f-1%%b)*6000+1%%g%%h-1%%c%%d, a+=(a>>31) & 8640000"
echo %t0% - %t1% Elapsed %a%

echo Counter=!C!

is similar at this:

Code: Select all

@echo off & setlocal EnableDelayedExpansion

for /F "Tokens=1 delims==" %%v in ('set') do if /I NOT %%v == USERPROFILE set "%%v="

set C=0

>t0.dat echo !time!

For /L %%N in (1,1,30000) do (

   ::Do some work
   set /a A=A+2+A/2

   if %%N gtr !N! (
        set /a N+=100
        for /F "Tokens=1 delims==" %%v in ('set A') do set "%%v="
        set /a C+=1
   )

)

set t1=!time!
set/p"t0="<t0.dat

for /F "tokens=1-8 delims=:.," %%a in ("!t0: =0!:!t1: =0!") do set /a "a=(((1%%e-1%%a)*60)+1%%f-1%%b)*6000+1%%g%%h-1%%c%%d, a+=(a>>31) & 8640000"
echo %t0% - %t1% Elapsed %a%

echo Counter=!C!

I have tested and the first code is slightly slower but produce better result.

One note

this istruction:

Code: Select all

for /F "Tokens=1 delims==" %%v in ('set') do if /I NOT %%v == USERPROFILE set "%%v="

empty the complete env but leave the userprofile variable.
In my test if i remove this variable the time to complete the task DOUBLES!

Can someone explain why? (tested on windows 7 32bit )

EDIT: @Aacini, the triangle is here:

Code: Select all

http://esoteric.sange.fi/brainf*ck/bf-source/prog/

change the * with u.

einstein1969

[einstein1969]

...
This Batch file will fail if the BF program have this wrong code: "[any loop][...]". This code have no sense, because after exit from first loop it will not enter to the second one, unless the second loop is used to clear the current cell: "[any loop][-]", but this is also meaningless, because at that point the current cell is zero already! This type of code indicate that the program was not originally written in BF, but perhaps it was translated from another source, like TowerOfHanoi.b (in my opinion, this is cheating). If you want to test TowerOfHanoi.b in my BF interpreter Version 3 (or any BF program, for that matter), be sure to first replace all "][-]" segments by just "]".

Antonio

I have substitute but there is a problem:

Code: Select all

E:\x264\provini>bf_aacini_3.cmd hanoi_mod.bf
Extracting subroutines................................................................................................................................
......................................
Parsing subroutines...................................................................................................................................
....................................
Creating Ascii tables.................
Running.
←[H←[2J←[2;27HTowers of Hanoi in Brainf*ck←[3;15HWritten by Clifford Wolf <http://www.clifford.at/bfcpu/>Impossibile trovare il file \x264\provini\han
oi_mod\sub260.bp.
←[14;^CTerminare il processo batch (S/N)? s
Terminare il processo batch (S/N)? s

but... it is possible reinsert the sub [-]? For testing scope.

and... I want identify this code in the hanoi.bf It's possible?

Code: Select all

macro delay()
{
   var a = 200;
   while (a) {
      var b = 200;
      while (b) {
         var c = 100;
         while (c) c -= 1;
         b -= 1;
      }
      a -= 1;
   }
}

There is not necessity to DELAY...

einstein1969

[Aacini]

You must substitute all "][-]" constructs. TowerOfHanoi have some constructs that are in separated lines, like this one:

Code: Select all

............................ [any loop]
[-]................

That are not replaced by Notepad, and at least one case of

Code: Select all

............................ [any loop][
-]................

You must search for these cases visually...

Antonio

PS - I will fix this problem in the next version

EDIT:

Code: Select all

macro delay()
{
   var a = 200;
   while (a) {
      var b = 200;
      while (b) {
         var c = 100;
         while (c) c -= 1;
         b -= 1;
      }
      a -= 1;
   }
}

How do you know that this code exists in Hanoi.bf? I don't think that the a=200 be achieved via 200´s ++++...., but surely via the multiplication of two factors. What are these? Are two or three factors? And the number 100?