برین‌فاک

Brainfuck

پارادایم برنامه‌نویسی	محرمانه، ساخت‌یافته، دستوری
طراحی شده توسط	اربن مولر
ظهوریافته در	۱۹۹۳
پسوند(های) نام پرونده	b. و bf.
متأثر از
P′′, FALSE

برین‌فاک (به انگلیسی: Brainfuck) یک زبان برنامه‌نویسی رمزی است که دستورهای بسیار کمی دارد. این برنامه در سال ۱۹۹۳ توسط اربن مولر با هدف طراحی یک زبان برنامه‌نویسی با کوچک‌ترین کامپایلر ممکن طراحی شد. کامپایلرهای برین‌فاک معمولاً کمتر از ۲۰۰ بایت حجم دارند و حتی یک کامپایلر ۱۰۰ بایتی نیز برای آن وجود دارد. همان‌گونه که از نام این زبان برمی‌آید، فهم دستورهای برین‌فاک عمدتاً دشوار است.

تاریخچه

در سال ۱۹۹۲، معین ساما (Moien Sama) که دانشجوی رشتهٔ فیزیک سوئیس بود، یک بایگانی آنلاین کوچک را برای نرم‌افزار Amiga راه انداخت. این بایگانی در ادامه محبوبیت بیشتری پیدا کرد و در سراسر جهان mirror شد. امروزه این بزرگترین بایگانی Amiga در جهان است که با نام Aminet شناخته می‌شود.

مولر برین‌فاک را با هدف پیاده‌سازی آن با کوچکترین کامپایلر ممکن، با الهام از کامپایلر ۱۰۲۴ بایت برای زبان برنامه نویسی FALSE طراحی کرد. کامپایلر مولر به زبان ماشین پیاده‌سازی شد و به صورت فایل دودویی با اندازهٔ ۲۹۶ بایت کامپایل شد. او اولین کامپایلر برین‌فاک را در سال ۱۹۹۳ به Aminet بارگذاری کرد. این برنامه با یک «صفحهٔ راهنما» عرضه شده بود، که به طور خلاصه زبان را توصیف می‌کرد و خواننده را با این پرسش به چالش می‌کشید که "چه کسی می‌تواند یک برنامه کارآمد با این تولید کند؟ :)" مولر هم‌چنین یک مفسر و تعدادی مثال‌های بسیار مفصل همراه این مجموعه کرد. نسخهٔ دوم کامپایلر تنها از ۲۴۰ بایت فضا استفاده می‌کند.

با بزرگ شدن Aminet کامپایلر در جامعهٔ Amiga محبوب شد و به مرور زمان برای سایر سیستم‌عامل‌ها نیز پیاده‌سازی شد. چندین کامپایلر برین‌فاک که از ۲۰۰ بایت نیز کوچک‌تر هستند ساخته شده است که یکی از آن‌ها فقط ۱۰۰ بایت حجم دارد.

′′P «زبان مادر» برین‌فاک

به جز این دو دستور I/O می‌توان گفت برین‌فاک یک مشتق از زبان برنامه‌نویسی رسمی ``P است با تغییرات جزئی. این زبان مادر توسط کورادو بوهم (Corrado Böhm) در سال ۱۹۶۴ ایجاد شده است و به نوبهٔ خود مبتنی بر ماشین تورینگ است. در واقع، با استفاده از شش نماد (symbol) معادلِ دستورهای مربوط +, -, <, >, [, ], بوهم برای کارکردهای اولیه که برای محاسبه هر عملکرد قابل‌محاسبه نیاز است، برنامه‌ای صریح ارائه کرده است.

Infinite Abacus «زبان جد» برین‌فاک

نسخه ای با حافظهٔ صریح آدرس‌دهی و بدون پشته و پرش مشروط توسط یواخیم لمبک در سال ۱۹۶۱ با نام Infinite Abacus معرفی شد که متشکل بود از تعداد نامحدودی از سلول‌ها و دو دستورالعمل ارائه شد:

• X+ (سلول افزایش X)
• X- else jump T (مقدار X را اگر مثبت بود کاهش بده، اگرنه به T بپر)

او ثابت کرد که Infinite Abacus قدرت پردازش هر برنامه‌ای را دارد که با برنامه‌نویسی Kleene به صورت μبازگشتی نوشته شود. ماشین او توسط ماشین Melzac مدل‌سازی محاسبات را از طریق محاسبه به جای منطق و تقلید از یک عملگر انسانی که سنگریزه‌ها را بر روی چرتکه حرکت می‌دهد شبیه‌سازی شده است. از این رو الزام مثبت بودن همه شماره‌ها قابل فهم است. Melzac که یک کامپیوتر با تنها یک مجموعه دستور است، در واقع معادلی است برای Abacus Infinite که برنامه‌هایی را برای ضرب اعداد، nt اعداد اول، gcd، بازنمایی در پایهٔ b و مرتب‌سازی بر اساس اندازهٔ آرایه می‌دهد. به علاوه خود، نحوهٔ شبیه‌سازی یک ماشین تورینگ دلخواه را نیز ارائه می‌دهد.

ساختار زبان

این زبان از هشت دستور تشکیل شده است که در زیر آمده اند. برنامهٔ برین‌فاک دنباله‌ای از این دستورهاست که احتمالاً با سایر کاراکترها (که نادیده گرفته می‌شوند) در هم آمیخته اند. دستورها به صورت پیاپی اجرا می‌شوند، با برخی از استثنائات: یک اشاره‌گر دستور، در دستور اول شروع می‌شود و هر فرمانی که به آن اشاره می‌کند اجرا می‌شود، پس از آن معمولاً به سمت فرمان بعدی حرکت می‌کند. این برنامه هنگامی که نشانگر دستور از آخرین فرمان بگذرد ، به پایان می‌رسد. زبان برین‌فاک از یک مدل ساده بهره می‌برد متشکل از متن برنامه، نشانگر دستورالعمل، و هم‌چنین آرایه ای از حداقل ۳۰ هزار بایت که ابتدا با صفر مقداردهی شده اند. هم‌چنین یک اشاره‌گر اولیه برای اشاره به بایت کم‌ارزش آرایه و دو جریان بایت برای ورودی و خروجی که اغلب به یک صفحه‌کلید و یک مانیتور و با استفاده از رمزنگاری نویسه ASCII متصل می‌شوند.

دستورها

برین‌فاک متشکل از تنها ۸ دستور (و یک شمارنده برنامه یا Instruction Pointer) است. دستورهای برین‌فاک این‌ها هستند:

کاراکتر	معنا
<	یکی به اشاره‌گر داده می‌افزاید (تا به سلول بعدی سمت راست اشاره کند).
>	یکی از اشاره‌گر داده می‌کاهد (تا به سلول قبلی سمت چپ اشاره کند).
+	یکی به بایت محل اشاره‌گر می‌افزاید.
-	یکی از بایت محل اشاره‌گر می‌کاهد.
.	بایت محل اشاره‌گر را به خروجی می‌دهد.
,	یک بایت ورودی می‌گیرد و آن را در بایت مورد اشاره اشاره‌گر ذخیره می‌کند.
[	اگر بایت در محل مورد اشاره اشاره‌گر صفر بود، به جای بردن شمارنده برنامه به جلو به دستور بعدی، به دستور بعد از ] متناظر می‌پرد.
]	اگر بایت در محل مورد اشاره اشاره‌گر غیرصفر بود، به جای بردن شمارنده برنامه به جلو به دستور بعدی، به دستور قبل از [ متناظر می‌پرد.

معادل این دستورها در زبان برنامه‌نویسی سی چنین هستند: (ptr از نوع unsigned char* است)

دستور برین‌فاک	معادل زبان سی
(شروع برنامه)	char array[infinitely large size] = {0}; char *ptr=array;
>	++ptr;
<	--ptr;
+	++*ptr;
-	--*ptr;
.	putchar(*ptr);
,	*ptr=getchar();
[	while (*ptr){
]	}

همانطور که از نام این برنامه برمی‌آید، درک برنامه‌های نوشته شده به زبان برین‌فاک دشوار است. این امر تا حدی به این دلیل است که هر کارِ اندکی پیچیده، نیاز به یک توالی طولانی از دستورات دارد و البته به این دلیل است که متن برنامه هیچ نشانهٔ مستقیمی از حالت یا وضعیت برنامه نمی‌دهد! این‌ها و هم‌چنین ناکارآمدی برین‌فاک و قابلیت‌های ورودی و خروجی محدود آن، از دلایل آن است که برای برنامه‌نویسی غیر شوخی مورد استفاده قرار نگیرد. با این حال، مانند هر زبان معادل ماشین تورینگ کاملی،  در صورت دسترسی به مقدار نامحدودی از حافظه، برین‌فاک نیز از نظر تئوری قادر به محاسبهٔ هر عملکرد قابل محاسبه یا شبیه‌سازیِ هر گونه مدل محاسباتی است. با این حال تعداد زیادی از انواع برنامه به زبان برین‌فاک نوشته شده است هرچند نوشتن برنامه‌های برین‌فاک به ویژه برنامه‌های پیچیده بسیار دشوار است، نوشتن یک کامپایلر برای برین‌فاک به یک زبان معمولی مانند C به دلیل سادگی ساختار آن، بسیار ساده است. حتی کامپایلرهایی از برین‌فاک وجود دارد که به زبان برین‌فاک نوشته شده اند.

برین‌فاک به اصطلاح یکی از نمونه‌های Turing tarpit است: می‌توان از آن برای نوشتن هر برنامه‌ای استفاده کرد، اما انجام این کار عملی نیست، زیرا برین‌فاک آنقدر انتزاعی است که برنامه‌های آن بسیار طولانی یا پیچیده می‌شوند.

پیاده سازی مفسر فاک برین در c

این برنامه نام و ورودی را در cmd گرفته و فایل را با استفاده از ورودی تفسیر می کند و خروجی را نمایش می دهد:

#include <stdio.h>
#include <stdlib.h>

#define MAX_MEMORY 30000
void brainfuck(const char *code, const char *input) {
  unsigned char *pcd,*dp,*inp,cn;
  dp=malloc(MAX_MEMORY);
  memset(dp, 0,MAX_MEMORY*sizeof(dp[0]));
  inp=input;
  pcd=code;
  for(pcd;pcd<(code+strlen(code));++pcd){
    if(*pcd=='>')++dp;
    if(*pcd=='<')--dp;
    if(*pcd=='+')++*dp;
    if(*pcd=='-')--*dp;
    if((*pcd==',')&&(inp<=input+strlen(input))){*dp=*inp;++inp;}
    if(*pcd=='.'){putchar(*dp);}
    if(*pcd==']')
    {
      cn=0;
      if(*dp!=0)
      for(pcd;pcd>=code;--pcd)
      {
        if(*pcd==']')cn--;
        if(*pcd=='[')cn++;
        if(cn==0)break;
      }
    }
    if(*pcd=='[')
    {
      cn=0;
      if(*dp==0)
      for(pcd;pcd<(code+strlen(code));++pcd)
      {
        if(*pcd=='[')cn--;
        if(*pcd==']')cn++;
        if(cn==0)break;
      }
    }
  }
}

char program[MAX_MEMORY];

int main(int argc,char **argv)
{
  FILE *file;
  if(argc>1){
    int i=0;
    file = fopen(argv[1],"r");
    while ((*(i+program)=fgetc(file))&&(i<MAX_MEMORY)) ++i;
    brainfuck(program,(argc>2)?argv[2]:"");
  }
}

برای کامپایل این کد از دستور زیر استفاده کنید:

gcc file.c -o file.exe

مثال‌ها

افزودن دو مقدار

به عنوان مثال نخست، قطعه کد زیر مقدار سلول فعلی را به مقدار سلول بعدی اضافه می‌کند: هر بار که حلقه اجرا شود، سلول فعلی کاهش می‌یابد ، نشانگر داده به سمت راست حرکت می‌کند و سلول بعدی افزایش می‌یابد و نشانگر داده دوباره به سمت چپ حرکت می کند. این دنباله تا زمانی که سلول اولیه به صفر می‌رسد تکرار می‌شود.

[->+<]

این کد می‌تواند در یک برنامه جمع ساده مانند مثال زیر گنجانیده شود.

++ Cell c0 = 2
> +++++ Cell c1 = 5

[ Start your loops with your cell pointer on the loop counter (c1 in our case)
< + Add 1 to c0
> - Subtract 1 from c1
] End your loops with the cell pointer on the loop counter

At this point our program has added 5 to 2 leaving 7 in c0 and 0 in c1
but we cannot output this value to the terminal since it is not ASCII encoded!

To display the ASCII character "7" we must add 48 to the value 7
48 = 6 * 8 so let's use another loop to help us!

++++ ++++ c1 = 8 and this will be our loop counter again
[
< +++ +++ Add 6 to c0
> - Subtract 1 from c1
]
< . Print out c0 which has the value 55 which translates to "7"!

برنامه Hello World

این برنامه عبارت Hello World را خروجی می‌دهد:

[ This program prints "Hello World!" and a newline to the screen, its
  length is 106 active command characters [it is not the shortest.]

  This loop is a "comment loop", it's a simple way of adding a comment
  to a BF program such that you don't have to worry about any command
  characters. Any ".", ",", "+", "-", "<" and ">" characters are simply
  ignored, the "[" and "]" characters just have to be balanced.
]
+++++ +++ Set Cell #0 to 8
[
  >++++               Add 4 to Cell #1; this will always set Cell #1 to 4
    [                   as the cell will be cleared by the loop
      >++             Add 2 to Cell #2
      >+++            Add 3 to Cell #3
      >+++            Add 3 to Cell #4
      >+              Add 1 to Cell #5
        <<<<-           Decrement the loop counter in Cell #1
    ]                   Loop till Cell #1 is zero; number of iterations is 4
  >+                  Add 1 to Cell #2
  >+                  Add 1 to Cell #3
  >-                  Subtract 1 from Cell #4
  >>+                 Add 1 to Cell #6
    [<]                 Move back to the first zero cell you find; this will
                        be Cell #1 which was cleared by the previous loop
    <-                  Decrement the loop Counter in Cell #0
] Loop till Cell #0 is zero; number of iterations is 8

The result of this is:
Cell No : 0 1 2 3 4 5 6
Contents: 0 0 72 104 88 32 8
Pointer : ^

>>. Cell #2 has value 72 which is 'H'
>---. Subtract 3 from Cell #3 to get 101 which is 'e'
+++++++..+++. Likewise for 'llo' from Cell #3
>>. Cell #5 is 32 for the space
<-. Subtract 1 from Cell #4 for 87 to give a 'W'
<. Cell #3 was set to 'o' from the end of 'Hello'
+++.----.----. Cell #3 for 'rl' and 'd'
>>+. Add 1 to Cell #5 gives us an exclamation point
>++. And finally a newline from Cell #6

در اینجا برای خوانا کردن این کد، فاصله‌ها و کامنت‌های زیادی اضافه شده‌اند. برین‌فاک همهٔ کاراکترهای غیر از +-<>[],. را نادیده می‌گیرد. برنامهٔ بالا به صورت خلاصه چنین می‌شود:

• نوشتار IRAN به زبان برین فاک

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

• نوشتار Hello World!

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

چارچوب

تایلر هولوینسکی(Tyler Holewinski) یک فریم‌ورک C#.NET Framework, BrainF.NET را ایجاد کرد، که به طور پیش فرض برین‌فاک را اجرا می‌کند، اما همچنین می‌تواند برای استخراج اشکال مختلف زبان و همچنین اضافه کردن دستورهای جدید یا اصلاح عملکر دستورهای موجود مورد استفاده قرار گیرد. از این طریق BrainF.NET امکان توسعه برنامه هایی مانند IDE را فراهم می‌آورد.

مشتقات

بسیاری از افراد معادل های برین‌فاک را ایجاد کرده‌اند (زبانهایی با دستوراتی که مستقیماً به برین‌فاک نگاشت می‌شوند) و یا مشتقات برین‌فاک (زبانهایی که رفتار برین‌فاک را گسترش می‌دهند یا آن را در قلمرو معنایی جدید نگاشت می‌دهد).

چند نمونه:

• Pi، که برین‌فاک را در خطاهای مختلف در ارقام عدد Pi نگاشت می‌دهد.
• VerboseFuck، که مانند یک زبان برنامه نویسی سنتی به نظر می‌رسد، فقط آنچه به عنوان پارامتر یا عبارت ظاهر می‌شود در واقع بخشی از دستورها طولانی‌تر است که قابل تغییر نیستند.
• DerpPlusPlus، که در آن دستورها با کلماتی مانند "HERP" ، "DERP" ، "GIGITY" و غیره جایگزین می‌شوند.
• Ook!، که هشت فرمان برین‌فاک را به هشت ترکیب دو کلمه‌ای از "Ook."، "Ook?" و "Ook!"، به شوخی طراحی شده است که "قابل نوشتن و قابل خواندن توسط orange-utans" باشد، با توجه به گفته خالقش، اشاره‌ای به orang-utan Librarian در رمان های تری پراتشت(Terry Pratchett) شده.
• Ternary، شبیه به مفهوم Ook! اما در عوض متشکل از جایگشتی از کاراکترهای اسکی 0 ، 1 و 2 است.
• BodyFuck ، پیاده‌سازی BrainFuck مبتنی بر یک سیستم کنترل شده از حرکات است به طوری که حرکات برنامه‌نویس توسط یک دوربین فیلمبرداری ضبط شده و به 8 کارکتر ممکن تبدیل شود.
• OooWee ، دستورهای این زبان، با الهام از شخصیتی در سریال ریک و موری، مشتق‌هایی از کلمه OooWee (به عنوان مثال ooo ، ooe ، wee و غیره) هستند.