** Brainfuck Interpreter Contest ** [abgeschlossen]

@TyRoXx
Das Spiel läuft noch über eine Woche. Wenn Du wirklich nicht mehr daran arbeiten willst kannst Du es ja hier posten. Aber was erwartest Du von der Kritik? Seine Tricks kann zur Zeit niemand Preis geben.

EDIT: Vergiss es. Hab Draveres Nachtrag zu spät gelesen.

TyRoXx

Na, dann poste ich es hier eben nicht.
Ich dachte, so ein Austausch würde die Sache interessanter machen.

Programmiere zwar kein C#, aber das ist interessant zu lesen, bin gespannt!

Dravere

TyRoXx schrieb:

Na, dann poste ich es hier eben nicht.
Ich dachte, so ein Austausch würde die Sache interessanter machen.

Austausch kann man am Schluss machen. Du nimmst den Leuten doch die ganze Spannung. Ich will selber auf diese Tricks kommen. Das ist hier aktuell ein Wettbewerb und keine Teamarbeit! Sonst kann man es ja gleich vergessen.

Wieso soll man einen Wettbewerb machen, wenn alle am Ende dieselbe Lösung einreichen?

Grüssli

hustbaer

Genau.

Wenn es Interesse gibt kann ein Austausch gerne nach Ende des Contest hier stattfinden.

Wäre auch interessant ob wir aus den abgegebenen Lösungen was noch kürzeres gebastelt bekommen.

Auch kann jeder der will dann gerne die ganzen Tricks erklären die verwendet wurden, sofern sie nicht offensichtlich sind.

hustbaer

µ schrieb:

Ein Band mit 2^16 Feldern reicht, ja?

Japp, steht so in den Vorgaben.

µ schrieb:

Stellst Du noch ein Testsystem für die Rahmenbedingungen zur Verfügung?

Falls ich Zeit habe.
Ist aber schwierig auch nur ne halbwegs gute Testabdeckung zusammenzubekommen. Je nach Code könnte es vorkommen dass nur eine bestimmte Kombination aus Faktoren das Fehlverhalten triggert. Und alle Kombinationen aus Bandposition/Programmposition/Schleifen-Schachteltiefe/Zellenwert abzudecken ist so-gut-wie unmöglich (und auf jeden Fall unpraktikabel).

Falls jemand von euch Zeit & Lust hat weitere Test-Cases zu schreiben, z.B. auch welche die gezielt auf bestimmte Rahmenbedingungen checken, wäre ich sehr froh.

Idealerweise so posten wie volkard es vorgezeigt hier hat, damit es jeder schnell ausprobieren kann, und ich es schnell integrieren kann:
http://www.c-plusplus.net/forum/p2116659#2116659
(Danke @volkard BTW!)

volkard

Der Interpreter kann Programme bis einschliesslich 2^20 Zeichen verarbeiten.
Der Speicher der Brainfuck-Maschine ("das Band") hat 2^16 oder mehr Zellen.
Jede Zelle kann eine vorzeichenbehaftete Zahl speichern, Wertebereich mindestens 16 Bit (-32768 ... 32767).

Soweit ok.
Aber daraus eine Verschachtelungstiefe von 2^19 abzuleiten, ist übertrieben. Das macht man in anderen Programmiersprachen auch nicht.
Sie muß ausreichend sein für alle einigermaßenh sinnvoll zu erwartenden Programme. Das heißt 99 reicht. Und 9 reicht nicht.

hustbaer

volkard schrieb:

Aber daraus eine Verschachtelungstiefe von 2^19 abzuleiten, ist übertrieben. Das macht man in anderen Programmiersprachen auch nicht.
Sie muß ausreichend sein für alle einigermaßenh sinnvoll zu erwartenden Programme. Das heißt 99 reicht. Und 9 reicht nicht.

Da in den Regeln nix zum Thema Verschachtelungstiefe steht, aber steht ein Interpreter muss jedes korrekte BF-Programm verarbeiten können, kann man die Regeln IMO nur so auslegen, dass auch eine Verschachtelungstiefe von bis zu 2^19 verarbeitet werden muss.

Ich hätte nichts dagegen die Regeln dahingehend anzupassen. Obwohl ich als Limit dann eher 255 oder besser gleich 1023 vorschalgen würde - 99 kommt mir ein wenig wenig vor. Nicht dass ich ernsthaft mit BF Programmen rechne die tiefer als 99 schachteln. Man könnte vielleicht sagen, es ist mir "aus Prinzip zu wenig"

@all:
Falls sich genügend Leute für eine dahingehende Änderung aussprechen, hab ich kein Problem damit die Regeln nachträglich in diesem Punkt anzupassen.

Dravere

hustbaer schrieb:

Falls jemand von euch Zeit & Lust hat weitere Test-Cases zu schreiben, z.B. auch welche die gezielt auf bestimmte Rahmenbedingungen checken, wäre ich sehr froh.

RunTest("Krank", "+" + new String('[', 524287) + "-" + new String(']', 524287), "", "");

Grüssli

PS: Mist, mein aktuelles Programm übersteht den Test nicht

TyRoXx

hustbaer schrieb:

Falls sich genügend Leute für eine dahingehende Änderung aussprechen, hab ich kein Problem damit die Regeln nachträglich in diesem Punkt anzupassen.

Dann schreib noch dazu, dass byte als Zahlentyp auch in Ordnung ist, weiter als 255 wird wohl kaum ein Programm jemals zählen. Und 2^16 Zellen sind doch völlig übertrieben! 640 cells ought to be enough for anybody.

volkard

TyRoXx schrieb:

hustbaer schrieb:

Falls sich genügend Leute für eine dahingehende Änderung aussprechen, hab ich kein Problem damit die Regeln nachträglich in diesem Punkt anzupassen.

Dann schreib noch dazu, dass byte als Zahlentyp auch in Ordnung ist, weiter als 255 wird wohl kaum ein Programm jemals zählen. Und 2^16 Zellen sind doch völlig übertrieben! 640 cells ought to be enough for anybody.

Ist wie beim richtigen Programmieren.
Um auf die Verschachtelungstiefe zu kommen, muß Du hier 99 mal eine Schleife schreiben. Also 99 verschachtelte Schleifen muß der Programmierer reingeschrieben haben. ++[->[[+,.->[[ und so weiter bis 99, aber nicht wieder ] dazwischen. Das entspräche auch 99 Funktionen, die sich gegenseitig aufrufen. Das habe ich noch nicht erlebt.
Das hat überhaupt nichts zu tun mit einem kleinen Zahlentyp, den kann ich mit einfachen Schleifen sprengen. Ebenso die Feldgröße.

Die 2^19-Forderung verhindert effektiv, daß man rekursive Ansätze verwenden kann, also den BF-Stack auf den uns zur Verfügung stehenden Maschinbenstack abbildet. So, wie wir den BF-Speicher auf unseren Maschinenspeicher leicht abbilden können, der wurde ja nicht umsonst auf so wenig beschränkt.

hustbaer

volkard schrieb:

Die 2^19-Forderung verhindert effektiv, daß man rekursive Ansätze verwenden kann, also den BF-Stack auf den uns zur Verfügung stehenden Maschinbenstack abbildet. So, wie wir den BF-Speicher auf unseren Maschinenspeicher leicht abbilden können, der wurde ja nicht umsonst auf so wenig beschränkt.

Das stimmt, daran hab' ich nicht gedacht.

Was schreiben denn andere Sprach-Standards für minimale Callstack-Tiefe vor, z.B. der C oder C++ Standard?

TyRoXx

Hmm, ich bin noch nicht richtig überzeugt. Es gibt unendlich viele Möglichkeiten, ein ineffizientes Programm zu schreiben, und die rekursiven Schleifen mit dem eingebauten stack overflow sind nur eine davon.
Wenn überhaupt sollte das Verschachtelungslimit höher liegen, mindestens bei 2^10. Das müsste C# doch schaffen, oder?

hustbaer schrieb:

µ schrieb:

Stellst Du noch ein Testsystem für die Rahmenbedingungen zur Verfügung?

Falls ich Zeit habe.
Ist aber schwierig auch nur ne halbwegs gute Testabdeckung zusammenzubekommen. Je nach Code könnte es vorkommen dass nur eine bestimmte Kombination aus Faktoren das Fehlverhalten triggert. Und alle Kombinationen aus Bandposition/Programmposition/Schleifen-Schachteltiefe/Zellenwert abzudecken ist so-gut-wie unmöglich (und auf jeden Fall unpraktikabel).

Es geht um die Rahmenbedingungen und ich hätte mir das so vorgestellt: Aus z.B. Volkards "Sieben"-Progrämmchen baut man zur Laufzeit mit dem Stringbuilder ein Programm mit >= 2^20 Zeichen.
Die Verarbeitung des char Zeichensatzes prüft man, indem man jedes nicht-Bf Zeichen in ein anderes Programm einbaut. Bleiben die Negativen Bandsymbole. Da reicht eigentlich ein kleiner Zähler: -[+]+++++++++++++++++++++++++++++++++++++++++++++++++.
Hier muss '1' rauskommen. Wenn '0' da steht hat man die Schleifenbedingung nur für Zahlen >= 0 korrekt geprüft und die negativen Zahlen vergessen. So wie ich vorhin.

Ich kann am Sonntag vielleicht was bauen und dann hier veröffentlichen.

TyRoXx schrieb:

Wenn überhaupt sollte das Verschachtelungslimit höher liegen, mindestens bei 2^10. Das müsste C# doch schaffen, oder?

C# wirft bei 12k oder 13k rekursiven Aufrufen ohne Übergabeparameter eine StackOverflowException. Zumindest auf meinem System.

Ich schließe mich an: Im Sinne rekursiver Funktionen sollten wir die Verschachtelungstiefe auf 1024 begrenzen.

volkard

hustbaer schrieb:

Was schreiben denn andere Sprach-Standards für minimale Callstack-Tiefe vor, z.B. der C oder C++ Standard?

C++
Nesting levels of compound statements, iteration control structures, and selection control structures [256].
Nesting levels of parenthesized expressions within a full-expression [256].

volkard

TyRoXx schrieb:

Hmm, ich bin noch nicht richtig überzeugt. Es gibt unendlich viele Möglichkeiten, ein ineffizientes Programm zu schreiben, und die rekursiven Schleifen mit dem eingebauten stack overflow sind nur eine davon.

Aber [ und ] müssen zueinanderpassen, wie { und } oder ( und ) in C#. Wo kannst Du Dir in einem C#-Programm mehr als 99 Verschachtelungen von () oder {} denken? WOhlgemerkt, daß wären welche, die der Programmierer alle getippt hat! Es hat nichts damit zu tun, daß man tiefe "rekursive Schleifen" programmieren kann.

Hier geht es nur um die Frage, wie tief ein Compiler absteigen können muß, um ein Stück Code zu verarbeiten.

TyRoXx schrieb:

Wenn überhaupt sollte das Verschachtelungslimit höher liegen, mindestens bei 2^10. Das müsste C# doch schaffen, oder?

Ja, egal. 2^10, 2^8, 99, es ist praktisch kein Unterschied. Wenn man einen Wert davon schafft, hat man es vermutlich so allgemein programmiert, daß es leicht für andere Werte umgefrickelt werden kann.

hustbaer

OK.
Dann würde ich 256 vorschlagen.

Dravere

hustbaer schrieb:

Dann würde ich 256 vorschlagen.

Habe ich nichts dagegen. Ist aber natürlich blöd, während dem laufenden Contest noch Änderungen nachzureichen. Aber gut ... so extrem schlimm auch wieder nicht, ist ja auch nicht ein extrem wichtiger Contest

Grüssli

hustbaer

Ja, ist doof. Andrerseits ist das Argument von volkard gut, dass man in C# auch keine Callstack-Tiefe von 1<<19 hinbekommt.

Ich warte einfach noch was die anderen Teilnehmer schreiben.

Die anderen von TyRoXx vorgeschlagenen Änderungen mach' ich auf jeden Fall nicht, die wären etwas zu krass.