brainfuck-Compiler TMP style

Bashar

Brainfuck-Interpreter gibts auch hier: http://www.c-plusplus.net/forum/292057

314159265358979 schrieb:

Kann man die Threads bitte trennen?

Ja, bitte.

Bashar schrieb:

Brainfuck-Interpreter gibts auch hier: http://www.c-plusplus.net/forum/292057

Gibts da denn einen in C++? Ist doch C#

314159265358979

Und schon hab ich ein Ziel für Heute Nacht: Ein TMP-BF-Interpreter, also ein Interpreter im Compiler.

314159265358979 schrieb:

Und schon hab ich ein Ziel für Heute Nacht: Ein TMP-BF-Interpreter, also ein Interpreter im Compiler.

Hä? Kannstes nochmal erklären?

314159265358979

Anstatt wie bei camper, das BF-Programm zur Laufzeit auszuführen, wird das Programm bei mir bereits zur Compilezeit ausgeführt.

Ethon

Wie willste in-/output zur Compilezeit machen?

314159265358979

template <unsigned char...>
struct memory
{};

:p

Ethon

Also nur 'pseudo'.
Trotzdem interessant, mach mal.

Ethon schrieb:

Also nur 'pseudo'.
Trotzdem interessant, mach mal.

Was gibts eig. noch interessantes in der Richtung? Hab da grad voll Bock drauf

Swordfish

Hacker schrieb:

[...] Hab da grad voll Bock drauf

Lustmolch!

314159265358979

Hacker schrieb:

Ethon schrieb:

Also nur 'pseudo'.
Trotzdem interessant, mach mal.

Was gibts eig. noch interessantes in der Richtung? Hab da grad voll Bock drauf

Unendlich viel. Schreib nen Mathe-Parser. Schreib einen Mergesort für Wert-Parameter. etc.

Ethon

Wenn jemand mit TMP-Durchblick Lust auf ein interessantes Projekt hat, ich habe da gerade eine Idee (die sogar sinnvoll anwendbar ist), aber mir fehlt es etwas an Hintergrundwissen. Also wenn jemandem langweilig ist ...

314159265358979

Sag halt. :p

Ethon

Also, da muss ich etwas weiter ausholen.
Ich schreibe gerne Hacks für Spiele, die im Speicherbereich eines anderen Prozesses laufen, also per DLL-Injection. Nun benutze ich Linux und mache das auch mit Windows-Programmen, per Wine. Nun ist es aber so, dass unter Windows manche Funktionen gänzlich andersaufgerufen werden müssen ( http://en.wikipedia.org/wiki/X86_calling_conventions ), auch wenn der GCC da helfen kann, es funktioniert nicht immer. Die dreckige Lösung: Inline Assembler.

Jetzt dachte ich mir, es wäre nett diese Calling-Conventions direkt in C++ zu definieren (Der Nte Integer/Float Parameter kommt in Register X), sollte zur Compilezeit kein Problem sein. Und dann damit und mit AsmJit ( http://code.google.com/p/asmjit/ ) zur Compilezeit Wrapperfunktionen bauen, in etwa so habe ich mir das vorgestellt:

typedef calling_convention<RCX, RDX, R8, R9> windows_64;
typedef calling_convention<RDI, RSI, RDX, RCX, R8, R9> system_v_amd64;
auto malloc_wrapper = system_v_amd64::wrap_call<windows_64, void*, std::size_t>(&std::malloc);
void* ptr = malloc_wrapper(123);

Habe mir dazu schon einiges an Gedanken gemacht, leider macht mein mangelndes Können in Sachen TMP immer wieder alles kaputt.

314159265358979

Und ich habe keine Ahnung von Calling Conventions.

@Hacker: Hier mal eine schnell hingefrickelte Version eines "normalen" BF-Interpreters.

#include <iostream>

void bf_run(char const* codeptr, unsigned char* memptr)
{
	while(*codeptr)
	{
		switch(*codeptr)
		{
		case '.':
			std::cout << static_cast<char>(*memptr);
			break;

		case ',':
			std::cin.read(reinterpret_cast<char*>(memptr), 1);
			break;

		case '>':
			++memptr;
			break;

		case '<':
			--memptr;
			break;

		case '+':
			++*memptr;
			break;

		case '-':
			--*memptr;
			break;

		case '[':
			++codeptr;

			while(*memptr)
				bf_run(codeptr, memptr);

			while(*codeptr && *codeptr != ']')
				++codeptr;

			break;

		case ']':
			return;

		default:
			break;
		}

		++codeptr;
	}
}

int main()
{
	// Hello, World!\r\n
	char const source[] =
	"++++++++++"
	"["
	">+++++++>++++++++++>+++>+<<<<-"
	"]"
	">++."
	">+."
	"+++++++."
	"."
	"+++."
	">++."
	"<<+++++++++++++++."
	">."
	"+++."
	"------."
	"--------."
	">+."
	">."
	"+++.";

	unsigned char memory[1024] = {};

	bf_run(source, memory);
}

http://ideone.com/EVnTV

camper

314159265358979 schrieb:

*push*

Na, wie siehts aus? :p

Mach ich, wenn mir mal wieder langweilig genug ist.

Wenn du Probleme zum Lösen brauchst, hab ich ein paar (Schwierigkeitsgrad variiert, und einige Lösungen sind bekannt):

Jedes Pack-Problem lässt sich in ein Problem mit Indexlisten (eine Templateklasse, deren Templateargumente ein einziges Pack aus Integern darstellen) umformulieren, also stelle ich die Probleme auch so:

1. Erstelle eine Templatemetafunktion, die aus einer Indexliste zwei Listen erzeugt, in der jeweils die erste und die zweite Hälfte der Indizes enthalten ist F<0,1,2,3> -> <0,1>, <2,3>
2. Erstelle eine Templatemetafunktion, die aus einer Indexliste zwei Listen erzeugt, in der jeweils die erste N und der Rest der Indizes getrennt werden F<<0,1,2,3,4,5>,2> -> <0,1>, <2,3,4,5>
3. Erstelle eine Templatemetafunktion, die das letzte Element zurückgibt: F<0,1,2,3> -> 3
4. Erstelle eine Templatemetafunktion, die das N-te Element zurückgibt: F<<5,6,7,8>,2> -> 7
5. Erstelle eine Templatemetafunktion, die zwei Listen mischt, so dass die Elemente aus beiden Listen jeweils abwechseln: F<<0,1,2,3>,<6,7,8,9>> -> <0,6,1,7,2,8,3,9>
6. Erstelle eine Templatemetafunktion, die zwei Listen mischt, so dass jedes Element der einen Liste mit jedem der anderen Liste verknüft, Bonuspunkte, wenn die Verknüpfung selbst ein Parameter ist
z.B. F<<0,1,2>, <10,11,12>> -> <0+10,0+11,0+12,1+10,1+11,1+12,2+10,2+11,2+12>
7. Erstelle eine Templatemetafunktion, die eine Liste erzeugt, in der die Elemente der ersten Liste sooft wiederholt werden, wie das korrespondierende Element der zweiten Liste vorgibt
F<<0,1,2>,<3,1,2>> -> <0,0,0,1,2,2>

Die Lösung sollte optimal in Hinblick auf Tiefe der rekursiven Instantiierung, algorithmische Komplexität und Speicherverbrauch sein. Bonuspunkte, wenn diese Kriterien gleichzeitig vorliegen (es kann durchaus mehrere Lösungen je nach Schwerpunkt geben).

314159265358979 schrieb:

@Hacker: Hier mal eine schnell hingefrickelte Version eines "normalen" BF-Interpreters.

#include <iostream>

void bf_run(char const* codeptr, unsigned char* memptr)
{
	while(*codeptr)
	{
		switch(*codeptr)
		{
		case '.':
			std::cout << static_cast<char>(*memptr);
			break;

		case ',':
			std::cin.read(reinterpret_cast<char*>(memptr), 1);
			break;

		case '>':
			++memptr;
			break;

		case '<':
			--memptr;
			break;

		case '+':
			++*memptr;
			break;

		case '-':
			--*memptr;
			break;

		case '[':
			++codeptr;

			while(*memptr)
				bf_run(codeptr, memptr);

			while(*codeptr && *codeptr != ']')
				++codeptr;

			break;

		case ']':
			return;

		default:
			break;
		}

		++codeptr;
	}
}

int main()
{
	// Hello, World!\r\n
	char const source[] =
	"++++++++++"
	"["
	">+++++++>++++++++++>+++>+<<<<-"
	"]"
	">++."
	">+."
	"+++++++."
	"."
	"+++."
	">++."
	"<<+++++++++++++++."
	">."
	"+++."
	"------."
	"--------."
	">+."
	">."
	"+++.";

	unsigned char memory[1024] = {};

	bf_run(source, memory);
}

http://ideone.com/EVnTV

Schnell-hingefrickelt...
Nicht Turing-Vollständig, aber abgesehen davon - kannst du Schleifen verschachteln? Und nebeneinander stehen können sie auch? :p

hustbaer

Bei der Gelegenheit...

Hier findet man sehr hübsche, schnelle und vor allem übersichtlich implementierte BF Interpreter:

http://www.c-plusplus.net/forum/p2120628#2120628

314159265358979

@camper: Beispiel 1:

template <typename, typename, int, int>
struct split_half_impl;

template <int HA, int... TA, int HB, int... TB, int NA, int NB>
struct split_half_impl<intlist<HA, TA...>, intlist<HB, TB...>, NA, NB>
	: split_half_impl<intlist<HA, TA..., HB>, intlist<TB...>, NA + 1, NB - 1>
{};

template <int HA, int... TA, int HB, int... TB, int N>
struct split_half_impl<intlist<HA, TA...>, intlist<HB, TB...>, N, N>
{
	typedef intlist<HA, TA...> first;
	typedef intlist<HB, TB...> second;
};

template <typename>
struct split_half;

template <int H, int... T>
struct split_half<intlist<H, T...>>
	: split_half_impl<intlist<H>, intlist<T...>, 1, sizeof...(T)>
{};

Wie lieg ich so?

(Für leere Listen sowie Listen mit ungerader Anzahl an Elementen hab ich mir die Implementierung erstmal erspart.)

Hacker schrieb:

Ethon schrieb:

Also nur 'pseudo'.
Trotzdem interessant, mach mal.

Was gibts eig. noch interessantes in der Richtung? Hab da grad voll Bock drauf

Hab grad einen Vortrag zu genau dem gleichen Thema gehört. Dort wurde ein Haskell Interpreter zur compile-Zeit gebaut: http://cppnow.org/files/2012/04/Sinkovics.Porkoláb.pdf