Forum: PC-Programmierung Assoziativität Links-Rechts


von Daniel -. (root)


Lesenswert?

Nabend,

http://docs.roxen.com/pike/7.0/tutorial/expressions/operator_tables.xml

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:
1
int a,b,c;
2
a = b = c = 10;

(c=10), dann (b=c), dann (a=b)
In diesem Beispiel ist die Reihenfolge egal.
1
int x=0;
2
int a(){ if(x)return 10; return 0; }
3
int b(){ x=1; return 100; }
4
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 ...

von Εrnst B. (ernst)


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 ;)

von Ahem (Gast)


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

von Daniel -. (root)


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?

von (prx) A. K. (prx)


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.

von Daniel -. (root)


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).

von Daniel -. (root)


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.

von (prx) A. K. (prx)


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.

von Ahem (Gast)


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.

von Daniel -. (root)


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.

von Εrnst B. (ernst)


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.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.