www.mikrocontroller.net

Forum: PC-Programmierung Assoziativität Links-Rechts


Autor: Daniel -------- (root)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nabend,

http://docs.roxen.com/pike/7.0/tutorial/expression...

Im Link ist eine Priorätstabelle der Operatoren dargestellt.
Was mich erst stützig machte ist die Kennzechnung:
Assoziativ von links nach rechts.

Die Assoziativität, so wie ich sie kenne, ist eine Eigenschaft
der Binären Abbildungen, sie sich wie folgt definieren lässt.

f:(a,b)->c
sei eine Abbildung von R^2 nach R

f ist assoziativ, wenn gilt f(a,f(b,c)) == f(f(a,b),c)

oder für Lisp Kenner: (f a (f b c)) == (f f(a b) c)

In dieser Darstellung gibt es wohlgemerkt keine Unterscheidung
zwischen Rechts/Links.

Die einzige Erklärung, die mir in den Sinn kommt, ist
dass die Angabe rechts/links überhaupt nichts mit der
Eigeschaft der Assoziativität an sich hat, sondern
nur eine Evaluirungsreihenfolge ist.

Also praktisch gesprochen:
int a,b,c;
a = b = c = 10;

(c=10), dann (b=c), dann (a=b)
In diesem Beispiel ist die Reihenfolge egal.
int x=0;
int a(){ if(x)return 10; return 0; }
int b(){ x=1; return 100; }
int d = a() + a() + b();

In diesem Beispiel ist die Reihenfolge nun wichtig.
Auch wenn sowas sehr sehr unschön ist.

Könnt ihr meine Vermutung bestättigen, dass diese
Links/Rechts Angabe nur diese Reihenfolge definiert?

Grüsse

ps: Eben ist mir in den Sinn gekommen, dass diese "Regel"
Parallesierung zerbrechen würde. Wäre doch schön
wenn int d = a()+b()+c(); je einer CPU a,b,c zuordnen und
parallel ausführen würde. Hmm ...

Autor: Εrnst B✶ (ernst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Könnt ihr meine Vermutung bestättigen, dass diese
> Links/Rechts Angabe nur diese Reihenfolge definiert?
Ja.

> ps: Eben ist mir in den Sinn gekommen, dass diese "Regel"
> Parallesierung zerbrechen würde. Wäre doch schön
> wenn int d = a()+b()+c(); je einer CPU a,b,c zuordnen und
> parallel ausführen würde. Hmm ...

Das geht nur bei "echten" Funktionen ( "attribute(pure)" im GCC ).
Da kann der GCC z.B a()+a() durch 2*a() ersetzen.
Automatisches Parallelisieren von Funktionen gibts afaik aber eh nur bei 
Sprachen, bei der Funktionen schon per Definition keine Seiteneffekte 
haben (SML, Haskell etc).

Näheres in der Compilerbau-Vorlesung, 1. Semester Informatik ;)

Autor: Ahem (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das, was Du da kennst, ist die "Assoziativität" im mathematischen Sinne.

Zur weiteren Erinnerung:
Bei deren Definition wird sehr wohl zwischen Rechts und Links 
unterschieden, wenn auch oft implizit.

Zur Definition wird (sei ° eine Verknüpfung) der Ausdruck
(a°b)°c = a°(b°c) verwendet, mit der Maßgabe, das, wenn dieser Ausdruck 
wahr ist, für die Operation das Assoziativitätsgesetz gilt und daraus 
folgt, das a°b°c in jeder beliebigen Reihenfolge ausgewertet werden 
darf.
Man sagt auch die Operation sei "assoziativ".

Ist ein Ausdruck hingegen nicht assoziativ, so ist er entweder links- 
oder rechts-assoziativ.

Ist ein Ausdruck, links-assoziativ so gilt:

a°b°c = (a°b)°c

Ist er rechts-Assoziativ, gilt:
a°b°c = a°(b°c)

Insofern, ist "Assoziativität" eine von drei möglichen Qualitäten eines 
Operators
1. Op ist assoziativ reso. das Assoziativitätsgesetz gilt, oder
2. Op ist links-assoziativ oder
3. Op ist rechts-assoziativ

Autor: Daniel -------- (root)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke

>Näheres in der Compilerbau-Vorlesung, 1. Semester Informatik ;)

Compilerbau ist sicher eines der Dinge, die ich faszinierend finde.
Hehe, wer hier wollte nicht schon mal einen Compiler schreiben ;)
Aber für mich als Elektrotechniker ist das leider sekundär geworden.
Das ist eine Art No Time Krankheit :-/

Tut gcc wirklich parallelisieren, wenn eine Funktion als "pure"
gekennzeichnet wird? Ich mein, ich hab 2 64bit cores, wie könnte ich
das testen? :)
Hat das wer getestet?

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Daniel -------- schrieb:

> Tut gcc wirklich parallelisieren, wenn eine Funktion als "pure"
> gekennzeichnet wird?

Wer hat die den diesen Floh ins Ohr gesetzt?

Das Attribut "pure" sagt dem Compiler, dass die betreffende Funktion 
keine Seiteneffekte hat. Was dem Compiler auch ohne Kenntnis des Codes 
dieser Funktion bestimmte Optimierungen in aufrufendem Code ermöglicht, 
die sonst nicht möglich wären.

Mit Parallelisierung hat das nichts zu tun.

Autor: Daniel -------- (root)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Ahem

> Zur Definition wird (sei ° eine Verknüpfung) der Ausdruck
> (a°b)°c = a°(b°c) verwendet, mit der Maßgabe, das, wenn dieser Ausdruck
> wahr ist, für die Operation das Assoziativitätsgesetz gilt und daraus
> folgt, das a°b°c in jeder beliebigen Reihenfolge ausgewertet werden
> darf.
> Man sagt auch die Operation sei "assoziativ".


a ° b ° c ° d =>

((a ° b) ° c) ° d  # linksasso
(a ° (b ° c)) ° d  #
a ° ((b ° c) ° d)  # .. und alles inbetween
a ° (b ° c) ° d))  #
a ° (b ° (c ° d))  # rechtsasso

gibt 5 Kombinationen.
Gilt zusätzlich Kommutativität so werden es 24 ;)

Auch wenn es keine Seiteneffekte gibt, dann beeinflusst
die Klammerung doch das Ergebnis, oder?
Wenn ° ganz allgemein ist.

Wenn ° = + gilt, dann ist Klammerung egal, aber + ist
kommutativ, und diesem Umstand verdanken wir dann die Ergebnisgleichheit
(bei egal welcher Klammerung).

Autor: Daniel -------- (root)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@A.K

Ich hab's gerade verstanden. Wenn es pure ist, dann ist f(4)
egal an welcher Stelle und egal zur welchen Zeit bringt immer das 
gleiche,
darum muss Compiler es entweder einmal zur Compilezeit oder die
Laufzeitumgebung zur Laufzeit berechnen, je nachdem halt.

Da aber der Pfad während der Laufzeit, der zuerst auf f(4) trifft,
nicht von vorne rein bekannt ist, muss Laufzeitumgebung irgendeine
Form von "Gedächntnis" mitschleppen.

Naja aber warum soll Parallelisierung ausgeschlossen werden?
Das sind doch orthogonale Konzepte.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Daniel -------- schrieb:

> Da aber der Pfad während der Laufzeit, der zuerst auf f(4) trifft,
> nicht von vorne rein bekannt ist, muss Laufzeitumgebung irgendeine
> Form von "Gedächntnis" mitschleppen.

So läuft das m.W. nicht. Der Compiler wird im Normalfall eine einzelne 
Funktion betrachten die f() aufruft, ggf. noch irgendwelche 
Zwergfunktionen mit bekanntem Code die er inlined, und wird auf dieser 
Basis entscheiden wann und wie oft er f() aufruft. Ohne "pure" muss er 
das da tun wo es im Quellcode drinsteht, mit "pure" kann er damit 
flexibler umgehen und kann auch mit globalen Variablen besser umgehen 
weil er weiss das f() die nicht verwendet. Da merkt sich keine Laufzeit 
irgendwas.

Mal vorausgesetzt er kennt den Code der Funktion f() nicht. Wenn doch, 
kann er u.U. gleich das Ergebnis einsetzen, aber wenn den Code kennt, 
dann kriegt er i.A. auch selber schon raus, ob die "pure" ist oder 
nicht. Es geht also um den Fall, dass er den Code von f() im aufrufenden 
Kontext nicht kennt.

> Naja aber warum soll Parallelisierung ausgeschlossen werden?
> Das sind doch orthogonale Konzepte.

Nur hat GCC mit SMP und automatischer Verteilung der Laufzeitarbeit auf 
mehrere Cores reinweg garnix am Hut. Das ist immer noch dein Job, in 
C/C++/C# jedenfalls.

Autor: Ahem (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ehrlich gesagt, weiss ich nicht worauf Du hinauswillst.

Erst schriebst Du:
>Was mich erst stützig machte ist die Kennzechnung:
>Assoziativ von links nach rechts.
Das haben wir geklärt.

Was jetzt?

Du rechnest da irgendwelche Kombinationen vor und bald kommt noch die 
Temperatur und die Farbe dazu, oder was :-) Das ist wirklich nicht böse 
gemeint, aber worauf willst Du hinaus?

Das Grundproblem ist, das der Compiler als (hoffentlich) 
deterministisches Gebilde sich für eine Auswertungsreihenfolge 
entscheiden muss, selbst wenn der Operator das im mathematischen Sinne 
nicht erfordern würde.
(OK. Das gilt nur für Feld-, Wald- und Wiesen-Compiler, aber bleiben wir 
erstmal bei denen).

Daher gibt es diese Tabellen. Das ist alles.

Autor: Daniel -------- (root)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Ahem

Ja, die eigentliche Frage ist geklärt. Danke dafür an alle Beteiligte.

Ich neige nur manchmal dazu etwas abzugleiten, wenn mir dazwischen
etwas einfällt.

Autor: Εrnst B✶ (ernst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Daniel -------- schrieb:
> Ich neige nur manchmal dazu etwas abzugleiten, wenn mir dazwischen
> etwas einfällt.

Macht ja nix, ist ja ein interessantes Thema.
Und automatisches parallelisieren durch den C-Compiler kommt sicher auch 
bald.
Intel forscht in die Richtung (oder kann der ICC kann das schon? schon 
länger nicht mehr nachgeschaut...), die wollen schließlich auch Gründe 
zum Verkauf ihrer Sechzehn-Ender liefern.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.