brainfuck-Compiler TMP style

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

314159265358979

..

314159265358979

Hey camper, sag doch mal was!

@Ethon: Ich finde deine Projektidee zwar interessant, aber ich kann damit immer noch nicht wirklich viel anfangen. Wie und wozu verwendet man sowas?

314159265358979 schrieb:

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.

So, mit dem Mathe-Parser bin ich praktisch fertig. Mergesort für Wertparameter - was ist daran so "aufregend" (ich habe glaub' ich nicht ganz verstanden was gefragt ist)?

314159265358979

Zeig doch mal her den Matheparser.

314159265358979 schrieb:

Zeig doch mal her den Matheparser.

Wenn du sicher bist, dass dein Magen das aushält... ich mach grad nen neuen Post.

http://ideone.com/O77pp

Den Dingensda am Anfang hab ich gebastelt, da mir die Reihenfolge der Speicherfreigabe (und der Destruktor-aufrufe) herzlich egal ist und ich keine lust hab es selbst zu machen... ( boost::ptr_set o. ä. hab ich ja nicht ^^)

314159265358979

Mal abgesehen, dass man da jetzt noch viel verbessern kann: Was hat das mit TMP zu tun?

314159265358979 schrieb:

Mal abgesehen, dass man da jetzt noch viel verbessern kann: Was hat das mit TMP zu tun?

Nein, es ist ein normaler Parser. Aber TMP werd ich jetzt auch mal versuchen Ich wusste nicht, dass du einen TMP wolltest ^^

Aber wie soll ich output zur Compile-Zeit machen? Ein static_assert(0, "..."); oder wie...?

Ah nee, ich werd mich wohl mit boost::mpl auseinandersetzen müssen...

314159265358979

Was willst du denn da ausgeben? Du brauchst doch nur eine Zahl als Ergebnis.

std::cout << eval<'2', '+', '2'>::value;

Oder so ähnlich.