Befunge

Befunge
Utvecklare Chris Pressey
Dök först upp 1993 ( 1993 )
Hemsida catseye .tc /node /Befunge-93 .html
Influerad av
Forth , FALSK

Befunge är ett tvådimensionellt stackbaserat , reflekterande , esoteriskt programmeringsspråk . Det skiljer sig från konventionella språk genom att programmen är ordnade på ett tvådimensionellt rutnät. "Pil"-instruktioner riktar styrflödet åt vänster, höger, uppåt eller nedåt, och slingor konstrueras genom att styrflödet skickas i en cykel. Det har beskrivits som "en korsning mellan Forth och Lemmings ".

En värdig följeslagare till INTERCAL ; en datorspråkfamilj som undkommer den kvotiska begränsningen av linjärt kontrollflöde och omfattar programräknare som flyger genom flera dimensioner med exotiska topologier.

— Jargongfil

Historia

Språket skapades ursprungligen av Chris Pressey 1993 för Amiga , som ett försök att skapa ett språk som är så svårt att kompilera som möjligt. Observera att p tillåter självmodifierande kod . Ändå har ett antal kompilatorer senare skrivits. Ett antal tillägg till den ursprungliga "Befunge-93"-specifikationen finns också, framför allt Funge-98, som utökar konceptet till ett godtyckligt antal dimensioner och kan vara flertrådade, med flera instruktionspekare som arbetar samtidigt på samma utrymme. Befunge-förlängningar och varianter kallas Fungeoids eller bara Funges .

Befunge-93-specifikationen begränsar varje giltigt program till ett rutnät med 80 instruktioner horisontellt och 25 instruktioner vertikalt. Programexekvering som överskrider dessa gränser "omsluter" till en motsvarande punkt på andra sidan av rutnätet; ett Befunge-program är på detta sätt topologiskt ekvivalent med en torus . Eftersom ett Befunge-93-program bara kan ha en enda stack och dess lagringsarray är avgränsad, är Befunge-93-språket inte Turing-komplett (dock har det visat sig att Befunge-93 är Turing Complete med obegränsad stackordstorlek). Den senare Funge-98-specifikationen ger Turing fullständighet genom att ta bort storleksbegränsningarna på programmet; snarare än att svepa runt vid en fast gräns, följer rörelsen av en Funge-98 instruktionspekare en modell som kallas "Lahey-space" efter dess upphovsman, Chris Lahey. I denna modell beter sig nätet som en torus av ändlig storlek med avseende på omslag, samtidigt som det låter sig förlängas på obestämd tid.

Etymologi

Ordet Befunge kommer från ett skrivfel i en diskussion på nätet, där ordet "före" var avsett. [ citat behövs ]

Kompilering

Som sagt var designmålet för Befunge att skapa ett språk som var svårt att kompilera. Detta försöktes med implementeringen av självmodifierande kod ('p'-instruktionen kan skriva nya instruktioner till spelfältet) och ett flerdimensionellt spelfält (samma instruktion kan exekveras i fyra olika riktningar).

Ändå har dessa hinder till viss del övervunnits och Befunge-kompilatorer har skrivits med lämpliga tekniker.

Bef2c-kompilatorn som ingår i standardbefunge-93-distributionen använder gängad kod : varje instruktion kompileras till en kodavsnitt av C-kod, och kontroll flödar genom kodavsnitten precis som den gör i en Befunge-tolk (det vill säga villkorat av värdet av några "riktningsregister"). Detta resulterar inte i en betydande fördel jämfört med en bra tolk. Observera att bef2c-kompilatorn inte är korrekt eftersom den inte hanterar vare sig 'p' eller strängläge, men det skulle inte vara omöjligt att göra det (även om C-språket kanske inte är väl lämpat för detta).

Betty-kompilatorn, till exempel, behandlar alla möjliga raka instruktioner som ett underprogram, och om en 'p'-instruktion ändrar det underprogrammet, kompileras det underprogrammet om. Detta är en intressant variant av just-in-time kompilering , och det resulterar i en mycket bättre fördel jämfört med en tolk, eftersom många instruktioner kan exekveras i inbyggd kod utan att fatta ingripande beslut i "riktningsregistret".

Exempel på Befunge-93-kod

Tekniken att använda pilar för att ändra kontrollflödet demonstreras i slumptalsgeneratorprogrammet nedan. Befunge-instruktionspekaren börjar i det övre vänstra hörnet och kommer att gå till höger om den inte omdirigeras. Efter pilarna runt, ? instruktioner skickar instruktionspekaren i slumpmässiga kardinalriktningar tills pekaren träffar en siffra och skjuter den till stapeln. Sedan navigerar pilarna till . för att mata ut siffran från stacken och återföra pekaren till den första riktningsslumpvisaren. Det finns inget @ för att avsluta det här programmet, så det producerar en oändlig ström av slumptal från 1 till 9. 

 
  
  
   
  
  
   
      v>>>>>v  12345  ^?^  >  ?  ?^  v?v  6789  >>>>  v  ^  .  <

Följande kod är ett exempel på klassikern "Hello World!" program . Först skjuts bokstäverna "olleH" på stapeln som ASCII -nummer. Dessa plockas sedan från stapeln i LIFO- ordning och matas ut som texttecken för att ge "Hej". Ett mellanslag är tecken nummer 32 i ASCII, som här är konstruerat genom att multiplicera 4 och 8, innan det matas ut som text. Den återstående koden matar sedan ut "World!" på liknande sätt, följt av ASCII-tecken 10 (ett radmatningstecken som flyttar utmatningsmarkören till en ny rad). 

              
  
          

 >  v  v  ,,,,,  "Hej"  <  >  48  *  ,  v  v  ,,,,,,  "Världen!"  <  >  25  *  ,  @

Följande kod är en lite mer komplicerad version. Den lägger till ASCII-tecknet 10 (ett radmatningstecken ) till stacken och trycker sedan "!dlrow ,olleH" till stacken. Återigen LIFO- beställning att "H" nu är toppen av stapeln och kommer att vara den första som skrivs ut, "e" är andra, och så vidare. För att skriva ut tecknen går programmet in i en loop som först duplicerar det översta värdet på stacken (så nu skulle stacken se ut som " \n !dlrow ,olleHH"). Sedan kommer "_"-operationen att poppa det duplicerade värdet och gå åt höger om det är en nolla, annars vänster. (Detta förutsätter en kompatibel tolk som "returnerar" 0 när en tom stack öppnas.) När den går till vänster, dyker den upp och skriver ut det översta värdet som ett ASCII- tecken . Den duplicerar sedan nästa tecken och går tillbaka till "_"-testet, fortsätter att skriva ut resten av stacken tills den är tom och så nästa värde som visas är 0, vid vilken punkt "@" avslutar programmet. 

 
                  
                     >  25  *  "!dlrow ,olleH"  :  v  v  :,  _@  >  ^

Befunge-93 instruktionslista

0-9 Tryck detta nummer på stapeln
+ Tillägg: Poppa a och b , tryck sedan på a + b
- Subtraktion: Poppa a och b , tryck sedan b - a
* Multiplikation: Poppa a och b , tryck sedan a * b
/ Heltalsdivision: Poppa a och b , tryck sedan b / a , avrundat mot 0.
% Modulo: Poppa a och b , tryck sedan på resten av heltalsdivisionen av b / a .
! Logisk NOT: Pop ett värde. Om värdet är noll, tryck 1; annars tryck på noll.
` Större än: Pop a och b , tryck sedan 1 om b > a , annars noll.
> Börja röra dig åt höger
< Börja flytta vänster
^ Börja röra dig uppåt
v Börja röra dig nedåt
? Börja röra dig i en slumpmässig kardinalriktning
_ Pop ett värde; flytta åt höger om värde=0, annars vänster
| Pop ett värde; flytta ner om värde=0, annars upp
" Starta strängläge: tryck varje teckens ASCII-värde hela vägen upp till nästa "
: Dubblettvärde på toppen av stacken
\ Byt två värden på toppen av stapeln
$ Plocka upp värde från högen och släng det
. Pop-värde och utdata som ett heltal följt av ett mellanslag
, Popvärde och utdata som ASCII-tecken
# Bridge: Hoppa över nästa cell
sid Ett "put"-anrop (ett sätt att lagra ett värde för senare användning). Poppa y , x , och v , ändra sedan tecknet vid ( x , y ) i programmet till tecknet med ASCII - värde v
g Ett "get"-samtal (ett sätt att hämta data i lagring). Poppa y och x , tryck sedan på ASCII-värdet för tecknet på den positionen i programmet
& Be användaren om ett nummer och tryck på det
~ Be användaren om ett tecken och tryck på dess ASCII-värde
@ Avsluta programmet
(Plats) No-op. Gör ingenting

De flesta endimensionella programmeringsspråk kräver viss syntaktisk distinktion mellan kommentarstext och källkod – även om den distinktionen kan vara lika trivial som Brainfucks regel att alla tecken som inte finns i uppsättningen +-[]<>,. är en kommentar. Språk som Lisp och Python behandlar strängar som kommentarer i sammanhang där värdena inte används. På liknande sätt, i Befunge, finns det ingen kommentarsyntax: för att bädda in dokumentation i koden dirigerar programmeraren helt enkelt kontrollflödet runt "kommentar"-området, så att texten i det området aldrig exekveras.

Se även

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Befunge&oldid=1126812755 "