Kann Microcontroler ein Programm für mich selber schreiben?

**PICture** · 29.10.2005, 19:27

Hallo!
Theoretisch gesehen wenn ich ein Augangdata und Zieldata eigebe, müsste ein MC durch probieren allen Kombinationen von allen Befehlen ein Program, das die Aufgabe löst, selbst finden. Hat schon jemand mit sowas experimentiert?
Ich bin dankbar für jeden Beitrag im voraus.
MfG

**PasstScho** · 29.10.2005, 20:12

Hi,
Es ist theoretisch möglich das Programm per Zufall berechnen zu lassen. Aber wenn man sich jetzt mal überlegt dass es bei z.B.:einem Atmega32 2^16000 Möglichkeiten gibt(ein befehl hat 2Byte?), sieht es doch recht schlecht aus, die alle zu berechnen, in den µC zu laden und zu testen.
Wenn der PC die generiert und auch gleich testet, ist das natürlich schon um einiges schneller, aber wenn du dir die Zahl 2^16000 mal ausrechnest wirst du ganz schnell merken dass du viel schneller selber programmieren lernst, als dass du ein einziges lauffähiges Programm errechnest...

Eine viel bessere Methode für dein Problem sind neurolane Netze.
Damit kann man etwas machen wie du es willst, allerdings ist das nicht besonders einfach und braucht viel wissen und Glück.
Man kann neuronale Netze erstellen, die man mit Paaren von Ein und Ausgansdaten trainieren kann.
Im Idealfall klappt das aber nicht immer einwandfrei...
MfG Alex

**PICture** · 29.10.2005, 20:41

Hallo PasstScho!
Das war mir von Anfang an klar, das es nicht einfach ist. Wenn man aber z.B einen PIC12xxx nimmt, der nur 35 Befehle hat, sieht es mit der Zeit schon besser aus. Ich möchte selber ein bischen damit experimentieren und von einfachsten "Programmen" anfangen. z.B. einzelnen bit aus einer Speicherstelle in eine andere zu kopieren. So ein Befehl gibt es nicht und das ganze ist bloss 3 Byte lang. Ich denke nicht an sehr kompliezierte Programme, sondern ganz kurze, die man dann selber zusammensetzt.

**ragnar** · 29.10.2005, 21:50

PasstScho hats schon angedeutet:
Der Suchraum ist viel zu groß.

Beispiel:
Ein einfacher PIC hat 12 (oder 14?) bit Befehlslänge. Das sind zwar nur 35 Befehle, aber die Operanden müssen ja auch probiert werden. Das sind also schon mal 2^12 Möglichkeiten nur um einen einzigen Befehl abzuarbeiten. Soll das ganze jetzt aber den ganzen Speicher füllen, dann sind das (Anzahl_Befehle)^(Programmspeicher). Angenommen unser PIC hat 2kByte Speicher. Dann müssten wir also (2^12)^2048 verschiedene Programme testen.

Mal zum Vergleich:
Ein RSA-Schlüssel der im Moment als sicher gilt, hat 2048 bit. Dieser gilt als sicher, da man 2^2048 Möglichkeiten ausprobieren müssten um ihn zu knacken. Diese 2^2048 Möglichkeiten sind um _Größenordnungen_ kleiner als die Zahl oben.

Dann bleibt noch das Problem, das entstehende Programm zu überprüfen. Das ist leider auch nur mit starken Einschränkungen möglich (maximale Laufzeitbeschränkung) und braucht auch wieder viel Rechenpower.

Mal abgesehen davon
- wie willst du die Ausgangs/Zielbedinungen definieren ?
- wie willst du die Programme simulieren ?
- wenn du nur kleine Codesequenzen generieren willst, warum schreibst du die nicht einfach selber ?

Fazit:
So wie du dir das vorstellt kann es leider nicht gehen. Rechne dir nur mal aus wieviele Möglichkeiten du ausprobieren musst, um dein 3-Byte Programm oben zu berechnen.

Georg

**PICture** · 29.10.2005, 22:58

Hallo ragnar!
Das stimmt alles. Ich habe nichts gerechnet, weil das eine von den "verrückten" Ideen ist. Aber das lässt sich auch lösen, wenn man das alles am PC macht und nur das Programm zum ausprobieren, entweder in ein PIC brennt oder mit MPLAB simmuliert. Das schaut schon besser aus, oder?
MfG

**uwegw** · 29.10.2005, 23:47

auch der PC wäre dazu viel zu langsam. man kann damit ja auch schließlich RSA nicht schneller als in tausenden von jahren durch ausprobieren knacken, selbst mit den schnellsten großrechnern.

**SprinterSB** · 29.10.2005, 23:58

Worum geht es dir denn?
Ob das prinzipell irgendwie geht oder hast du eine konkrete Aufgabe?

Solche Abbildungen wie du sie beschreibst müssen zB von Compilern gelöst werden, etwas ein Datum von a nach b verschieben. Schon das ist alles andere als einfach!

Wie macht man das am besten? Codegröße? Laufzeit? Wo liegen die Daten? im internen Ram? im Flash? extern? sind die Daten gecacht? in Registern? sind es Konstanten? ist die Konstante dem Compiler bekannt? wird das Datum später nochmals benötigt oder nicht mehr gebraucht? greift man in den Speicher besser indirekt oder direkt (falls möglich)?, wie ist die Abhängigkeit zu anderen Daten? kann der Befehl an eine andere Stelle im Befehlsstrom eingefügt werden, um eine Pipeline besser zu nutzen? braucht man Register zum Zwischenspeichern? welche und wieviele? Welche Nebeneffekte gibt es (Statusänderung, etc?) Wird das Datum durch das Bewegen verändert (kann zB passieren, wenn es in Floating-Point-Register gespeichert wird)?

Das sind nur einige Aspekte für ein 'normales' Bewegen von Daten, noch gar nicht mal algebraische/logische Operationen.

In GCC wird so was nach anderen Zwischenstufen nach RTL (Register Transfer Language) übersetzt. Zu anderen Compilern kann ich nichts sagen, weil man da nicht in die Quelle sieht. Die RTL beschreibt algebraisch, was im Programm abgeht, und zwar auf einer schon recht niedrigen, registernahen Ebene. Die Instruktionen, die ein Target versteht, werden in RTL formuliert und mit einem Assembler-Template versehen, das angibt, welcher Assembler-Schnippsel diesem Code entspricht. Dabei geht GCC davon aus, daß es einen bestimmten Mindest-Befehlsvorrat auf einem Target gibt. Andere Befehle sind optional und als Goodie zufügbar, um dichteren Code zu bekommen. Diese RTL-Beschreibungen (wie der Rest vom GCC auch) sind natürlich alle handgemacht, also nicht automatisch generiert.
Es gibt auch Bestrebungen, Compiler automatisch generieren zu lassen. Die Idee ist, daß die Hardwarehersteller die Spezifikation ihrer Controller in einer Form zur Verfügung stellen, die dazu heran gezogen werden kann. Das ist alles noch Forschung; wie weit man da ist, hab ich Momentan nicht den Überblick. Aber auf absehbare Zeit werden menschengeschriebene Code-Generatoren mit Abstand die besseren sein.

Für deinen konkreten Fall '1 Bit verschieben' gewinnt auf jeden Fall Brain 1.0.
Und lass mich raten. '1 Bit verschieben' ist auf einem PIC gar nicht lösbar. Um das realisieren zu können, brauchst du bestimmt ein Zwischenspeicher, in dem du rumwutzen darfst -- auch wenn der nur 1 Bit groß ist.

Als Suchbegriffe werden dich
- compiler generator
- compiler creator
- denotational semantics
- attribute grammar

zu Seiten führen, die dein Frage in der einen oder anderen Weise berühren.
Ist aber meist starker Tobak

Als Startpunkt:
David W. Krumme, David H. Ackley: A Practical Method for Code Generation Based on Exhaustive Search. 185-196 Electronic Edition (DOI: 10.1145/806994), 1982

**PICture** · 30.10.2005, 00:55

Hallo SprinterSB!
Vielen Dank für Deine ausfürliche und fachliche Erklärung. Jetzt sehe ich, dass Die Idee wirklich verrückt und nicht realisierbar ist.
Somit möchte ich mich bei allen, die mein Wissen in dem Bereich wesentlich erweitert haben, herzlich bedanken.
MfG

**AxelM** · 30.10.2005, 01:33

Hi...
Also ich bin nicht der µC Experte, aber wenn du interesse an solchen dingen hast, solltest du dir mal etwas über fuzzy-logic besorgen. Das ist extreem spannend. Wie das natürlich mit einem µC zu lösen ist kann ich leider nicht sagen... aber da schau mal bei amazon... oder hab ich dich da falsch verstanden?