Brainfuck BAT Interpreter
The simplicity of the Brainfuck language generates many implementations of its execution. At Habré there were already interpreters and compilers in various programming languages, even Bash . It seemed to me that it was unfair to bypass another command processor. Namely batch files of the WindowsNT family, they are batch files. When writing this interpreter, the goal was set to implement everything only in the built-in “language” of the console.
Windows command processor has many limitations. Here are just some of them:
In the end, we get the specification for the language:
I would like to thank the author of the implementation of arrays on batch file. Without his code, writing a Brainfuck interpreter would be difficult.
As well as Robo habrauser for tips on code optimization.
')
The full text of the interpreter is here: http://pastebin.com/KZXUuz48
The program uses the following global variables:
After initializing the variables and filling the “memory” with zeros, we read the file with the program. In the process of reading, a multi-line program is spliced into one line. Subsequently, during the execution of the Brainfuck program, all non-“dictionary” characters will be ignored. All characters after * to the end of the line will be ignored. This will give an opportunity to write “beautifully” designed programs. Sample program:
All the above actions are performed with just two lines of the batch file.
Those who wish can add all non-dictionary characters from the program.
Next begins the main cycle of the interpreter. Here everything is quite transparent.
The operation code is read by the pointer cp . Next, the classic if ... else we fall on the appropriate subroutine. If the character is not from the “language dictionary”, then it will be ignored. Next, increase the cp counter and make the transition to the beginning of the cycle.
To emulate the chr () function, it is necessary to read a symbol from the char variable from the position corresponding to the code of this symbol.
Directly cut the character will not succeed. Those. design
There is a design
This function (: echochr) uses another interesting solution: text output without a newline.
The echo command always adds a newline to the output. In this case, it does not fit. Fortunately, there is an opportunity to bypass this restriction:
That is, we use input from the nul device in the set / p command to emulate the echo command.
This solution may provide some more interesting pieces that can be seen on the forum, the link to which is given below.
A warning:
Everything works very slowly regardless of the performance of the computer. Microsoft took care that owners of slow computers did not envy the owners of fast computers.
The code was tested on Windows XP, Windows Vista, Windows 7.
In my opinion, there is not enough material for a separate article, so I will post it here. For it directly concerns an increase in the speed of the interpreter presented here.
During the work on the interpreter, a constant spawning of the child processes of the command processor cmd was noticed. And the overall speed is small. It's all about calling the call function. We read a help:
Therefore, it is worth remembering that cmd will be launched for each subroutine call via call , which takes some time.
A simple test that does the same thing. But in the first case, directly, in the second, through a subprogram call.
As they say, comments are superfluous.
Therefore, I refused to use the implementation of arrays through subroutines and rewrote the interpreter code. As a result, the speed of work has increased by more than 15 times!
Actually, the optimized interpreter itself http://pastebin.com/MDbVJXsE
Brainfuck Dialect Specification
Windows command processor has many limitations. Here are just some of them:
- Because the characters " < " and " > " are used to redirect I / O to use them as commands in the brainfuck language will lead to an unnecessary complication of the code. Therefore, replace them with similar in spelling " ( " and " ) ".
- The ability to display text and enter data from the keyboard is limited.
In the end, we get the specification for the language:
- The memory represents a ring buffer.
- The output is limited to the first 127 characters of the code page with the exception of non-printable characters and some characters that caused an error when the batch file was running. The latter have been replaced by the character " . ". The space is replaced by the " _ " character.
- "Key words" of the language:
- ")" - move to the next memory location
- "(" - go to the previous memory location
- “+” - to increase the value of the cell by one
- "-" - reduce the value of the cell by one
- “,” - read the value in the cell from the standard input device. Currently not implemented
- "." - print the value of the cell on the standard output device
- "[" - start the cycle. if the value of the current cell is not 0 and go to the next command. Otherwise go to] considering the nesting
- “]” - the end of the cycle. Continue the loop if the value of the current cell is not 0
I would like to thank the author of the implementation of arrays on batch file. Without his code, writing a Brainfuck interpreter would be difficult.
As well as Robo habrauser for tips on code optimization.
')
Interpreter description
The full text of the interpreter is here: http://pastebin.com/KZXUuz48
The program uses the following global variables:
- mp (memory pointer) - a pointer to the current memory cell
- cp (command pointer) - pointer to the current command being executed
After initializing the variables and filling the “memory” with zeros, we read the file with the program. In the process of reading, a multi-line program is spliced into one line. Subsequently, during the execution of the Brainfuck program, all non-“dictionary” characters will be ignored. All characters after * to the end of the line will be ignored. This will give an opportunity to write “beautifully” designed programs. Sample program:
+++++++++[ * while mem[0]<=9 { )+++++ * mem[1]+=5 (-] * } ). * print chr(mem[1]) All the above actions are performed with just two lines of the batch file.
set bf_prog= FOR /F "eol=c delims=*" %%I IN (%work_file%) DO SET bf_prog=!bf_prog!%%I Those who wish can add all non-dictionary characters from the program.
Next begins the main cycle of the interpreter. Here everything is quite transparent.
The operation code is read by the pointer cp . Next, the classic if ... else we fall on the appropriate subroutine. If the character is not from the “language dictionary”, then it will be ignored. Next, increase the cp counter and make the transition to the beginning of the cycle.
:work set cop=!bf_prog:~%cp%,1! if "%cop%" == "+" ( call :array get mem %mp% tmp set /a tmp += 1 if "!tmp!" == "256" set tmp=0 call :array set mem %mp% !tmp! ) else if "%cop%" == "-" ( call :array get mem %mp% tmp set /a tmp -= 1 if !tmp! LSS 0 set tmp=255 call :array set mem %mp% !tmp! ) else if "%cop%" == ")" ( set /a mp +=1 if !mp! == %maxmem% set mp=0 ) else if "%cop%" == "(" ( set /a mp -=1 if !mp! == -1 set /a mp=%maxmem% - 1 ) else if "%cop%" == "," ( call :comma ) else if "%cop%" == "." ( call :array get mem %mp% tmp call :Echochr !tmp! ) else if "%cop%" == "[" ( call :array get mem %mp% tmp if "!tmp!" == "0" ( call :skip1 ) ) else if "%cop%" == "]" ( call :array get mem %mp% tmp if "!tmp!" NEQ "0" ( call :skip2 ) ) set /a cp += 1 if %cp% == %bf_len% goto :exit goto :work Description of some interesting solutions
To emulate the chr () function, it is necessary to read a symbol from the char variable from the position corresponding to the code of this symbol.
:echochr rem . , cmd "." set char=".#$...'()*+,-./0123456789.....?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]._`abcdefghijklmnopqrstuvwxyz{.}~_" if %1==10 echo. if %1==13 echo. if %1==32 <nul set /p strTemp="_" if %1 GTR 32 ( set /a code=%1 - 32 for /f %%t in ('cmd /c "echo %%char:~!code!,1%%"') do <nul set /p strTemp="%%t" ) exit /b 0 Directly cut the character will not succeed. Those. design
set t=%char:~%code%,1% or set t=%char:~!code!,1% will give an error. The problem is that string processing functions require specifying as a number, but not as a variable. For example: set t =% char: ~ 5.1% cuts a character out of line 1 starting at the 5th position. But in no way can you directly transfer the contents of a variable (in our case, code ) to the set command. You can get around this by using the execution time binding. Which works only in the if or for commands. Therefore, you have to call a copy of the command processor with the echo %% char command : ~! Code!, 1 %% (where the contents of the code are transmitted as a number) and intercept the output with the for / f construct.There is a design
set t=!char:~%code%,1! , but in this case it works out incorrectly. Because There are not so many output operations, it was decided to sacrifice execution speed for the sake of speed of development and debugging of the program.This function (: echochr) uses another interesting solution: text output without a newline.
The echo command always adds a newline to the output. In this case, it does not fit. Fortunately, there is an opportunity to bypass this restriction:
<nul set /p strTemp="%~1" That is, we use input from the nul device in the set / p command to emulate the echo command.
This solution may provide some more interesting pieces that can be seen on the forum, the link to which is given below.
Conclusion
++++[)++++++++)++++++++++++++++++)++++++++++++++++) ++++++++++++++++++++)+++++++++++++++++++++++++(((((-] ))+.(.))))++++++++.+++.+++++++.-----------------. ((((.)-.)+.+.)++.(-.(.).+.). A warning:
Everything works very slowly regardless of the performance of the computer. Microsoft took care that owners of slow computers did not envy the owners of fast computers.
The code was tested on Windows XP, Windows Vista, Windows 7.
Links
- Post of the author of the implementation of arrays: http://habrahabr.ru/blogs/crazydev/75951/
- The forum where several ideas were peeped: http://forum.script-coding.com/viewforum.php?id=12
- Here the features of the solutions used in the batch file are explained: http://rsdn.ru/article/winshell/NTCommandProcessor.xml
About optimizing the speed of the bat-files
In my opinion, there is not enough material for a separate article, so I will post it here. For it directly concerns an increase in the speed of the interpreter presented here.
During the work on the interpreter, a constant spawning of the child processes of the command processor cmd was noticed. And the overall speed is small. It's all about calling the call function. We read a help:
CALL .
:
CALL :
, ,
.
. ,
CALL, .
GOTO /? GOTO :EOF,
.
Therefore, it is worth remembering that cmd will be launched for each subroutine call via call , which takes some time.
A simple test that does the same thing. But in the first case, directly, in the second, through a subprogram call.
@echo off setlocal ENABLEDELAYEDEXPANSION ENABLEEXTENSIONS echo %time% - start test1 set a=0 for /l %%i in (1,1,1000) do set /aa=!a!+1 echo %a% echo %time% - end test1 echo -------------- echo %time% - start test2 set a=0 for /l %%i in (1,1,1000) do call :m1 echo %a% echo %time% - end test2 goto :eof :m1 set /aa=%a%+1 exit /b /0 As they say, comments are superfluous.
Therefore, I refused to use the implementation of arrays through subroutines and rewrote the interpreter code. As a result, the speed of work has increased by more than 15 times!
Actually, the optimized interpreter itself http://pastebin.com/MDbVJXsE
Source: https://habr.com/ru/post/123034/
All Articles