c++ - ¿Qué significa asociatividad de izquierda a derecha?

glm github

Question

Estoy confundido acerca de la definición de asociatividad de izquierda a derecha y de derecha a izquierda. También los he visto llamados asociatividad izquierda y asociatividad derecha y me gustaría saber cuál corresponde a cuál.

Sé que se relaciona con el orden en que se realizan las operaciones con la misma precedencia, como si a = x * y * z significa a = x * (y * z) o a = (x * y) * z. No sé cuál es asociativa de izquierda a derecha y cuál asociativa de derecha a izquierda.

He intentado buscarlo en Google, pero todo lo que he podido encontrar son tablas de la asociatividad de los diferentes operadores en c ++. Mirar todos los ejemplos me ha confundido más.

Lo que también me confunde aún más es que:

glm::vec4 transformedVector = translationMatrix * rotationMatrix * scaleMatrix * originalVector;

preforma primero la multiplicación de la matriz de escalamiento, seguida de la matriz de rotación seguida de la traslación. En este ejemplo, las matrices son todas de tipo glm :: mat4 y los vectores son de tipo glm :: vec4. ¿Es esta asociatividad de izquierda a derecha o de derecha a izquierda? ¿Es esto lo mismo que la multiplicación normal o la multiplicación de tipos glm es diferente?

Answer 1

La asociatividad de izquierda a derecha de un operador significa que el lado derecho del operador no debe tener ningún operador de mayor precedencia (prioridad), pero puede tener la misma prioridad. Si hay algún operador de mayor prioridad en el lado derecho de nuestro operador, primero tenemos que resolverlo. Ejemplo:

x = 2 + 3 * 3;

Aquí, para el operador + (asociatividad de izquierda a derecha), el lado derecho contiene un operador *, que es de mayor prioridad que el operador +, por lo que primero tenemos que resolverlo.

x = 2 + 9;
x = 11;

Answer 2

La respuesta más simple y no-tl; dr encontré:

En la mayoría de los lenguajes de programación, los operadores de suma, resta, multiplicación y división son asociativos a la izquierda , mientras que los operadores de asignación, condicional y exponencial son asociativos a la derecha .

gracias a: http://www.computerhope.com/jargon/a/assooper.htm

Answer 3

Normalmente lees de izquierda a derecha. Normalmente haces matemáticas de izquierda a derecha. Esto es asociatividad de izquierda a derecha y es más común.

La mayoría de la gente resolverá

x = 23 + 34 + 45

agrupándolo

x = (23 + 34) + 45

esto es asociatividad de izquierda a derecha. Puedes recordarlo porque lees y haces matemáticas de izquierda a derecha.

Además, en matemáticas no importa demasiado. Siempre se obtiene el mismo resultado de cualquier manera. Esto se debe a que la suma es asociativa . Decir que una operación es asociativa significa que la asociación de izquierda a derecha y de derecha a izquierda es lo mismo. Además, en la programación sigue siendo importante debido a los desbordamientos y la aritmética de punto flotante (pero no para los enteros de tamaño normal en ningún lenguaje razonable), por lo que cuando tiene un error a las 2 AM con grandes números y uso discreto de a+b y b+a , recuerda en qué orden ocurrió la adición.

En tu ejemplo:

glm::vec4 transformedVector = translationMatrix * rotationMatrix * scaleMatrix * originalVector

Conceptualmente, te abalanzas desde el lado derecho, ya que ahí es donde estás actuando. Sin embargo, en C ++, * normalmente es asociativa de izquierda a derecha y no es posible anular esto . glm puede manejar esto de varias maneras: puede acumular un caché de cosas para multiplicar esperando que llegue el vector final, luego hacer la multiplicación de derecha a izquierda. También puede (más probablemente) usar el teorema del álgebra de que la multiplicación de matrices es totalmente asociativa, y simplemente multiplicar de izquierda a derecha, luego asegurar al lector en la documentación que es lo mismo que pensar que de derecha a izquierda. Sin embargo, debe comprender la implementación porque, como se explicó anteriormente , importa de qué manera la implementación elige multiplicar los números de punto flotante .

Para completar, considera la resta. ¿Qué es a - b - c ? Aquí realmente importa si se trata de asociativo izquierdo o derecho. Por supuesto, en matemáticas lo definimos como b (a - b) - c , pero algún lenguaje de programación extraño puede preferir que la resta sea asociativa correcta, y tomar a - b - c para significar siempre a - (b - c) . Es mejor que esta lengua extranjera tenga una página de documentación que especifique que - es asociativo por derecho, porque es parte de la especificación de la operación, no es algo que se pueda decir simplemente al ver el uso del operador.

Answer 4

Puedes ver eso en las siguientes palabras:

Cuando combinamos operadores para formar expresiones, el orden en el que se aplicarán los operadores puede no ser obvio. Por ejemplo, a + b + c puede interpretarse como ((a + b) + c) o como (a + (b + c)). Decimos que + es asociativo a la izquierda si los operandos se agrupan de izquierda a derecha como en ((a + b) + c). Decimos que es asociativo por la derecha si agrupa los operandos en la dirección opuesta, como en (a + (b + c)).

AV Aho y JD Ullman 1977, p. 47

Answer 5

Un operador de infijo (o más generalmente el tipo de expresión que tiene subexpresiones izquierda y derecha no cerradas) se deja asociativo si en el uso anidado de este operador (tipo de expresión) sin paréntesis explícitos, los paréntesis implícitos se colocan a la izquierda. Como * es asociativo a la izquierda en C ++, a*b*c significa (a*b)*c . En el caso de un anidamiento más profundo, aparece un grupo de paréntesis implícitos en el extremo izquierdo: (((a*b)*c)*d)*e .

De manera equivalente, esto significa que la regla de producción sintáctica para este operador es recursiva por la izquierda (lo que significa que la sub-expresión de la izquierda tiene la misma categoría sintáctica de la que esta regla es una producción, de modo que la misma regla (el mismo operador) se puede usar directamente para forme esa subexpresión; la subexpresión en el otro extremo tiene una categoría sintáctica más restrictiva, y usar el mismo operador allí requeriría paréntesis explícitos). En C ++, una producción para la expresión multiplicativa (sección 5.6 en el Estándar) lee la expresión mutliplicativa * pm-expresión , con la expresión multiplicativa a la izquierda.

En consecuencia, en un uso anidado sin paréntesis explícitos, el operador situado más a la izquierda toma sus vecinos inmediatos como operandos, mientras que las otras instancias toman como operando a la izquierda el resultado de la expresión formada por todo a su izquierda.

Lo admito, he estado presionando esto un poco (demasiado lejos). Mi punto en que en ninguna parte arriba aparece la palabra "correcto", ni hay ningún movimiento involucrado; La asociatividad es una materia sintáctica y por lo tanto estática. Es importante donde van los paréntesis implícitos, no en el orden en que uno los escribe (de hecho, uno no lo hace en absoluto, o de lo contrario serían explícitos). Por supuesto, para la asociatividad a la derecha, simplemente reemplaza cada "izquierda" por la "derecha" arriba.

En conclusión, no puedo ver ninguna razón válida por la que uno deba llamar a esta asociatividad (o agrupación) de izquierda a derecha, pero el hecho es que las personas lo hacen (incluso el Estándar lo hace, aunque es perfectamente redundante dado que las reglas de sintaxis explícitas también son dado).

La confusión viene de explicar esto, como se hace a menudo, diciendo que (en ausencia de paréntesis explícitos) los operadores se realizan de izquierda a derecha (respectivamente de derecha a izquierda para los operadores asociativos por la derecha). Esto es engañoso porque confunde la sintaxis con la semántica (ejecución), y también es válido solo para operaciones con evaluación ascendente (todos los operandos se evalúan antes que el operador). Para operadores con reglas de evaluación especiales es simplemente incorrecto. Para los operadores && (y) y || (o) la semántica es evaluar primero el operando izquierdo y luego el operador mismo (es decir, decidir si el operando izquierdo o derecho producirá el resultado), seguido posiblemente por la evaluación del operando derecho. Esta evaluación de izquierda a derecha es totalmente independiente de la asociatividad: los operadores resultan ser asociativos por la izquierda, probablemente porque todos los operadores binarios sin asignación son, pero (c1 && c2) && c3 (con paréntesis redundantes donde ya estarían implícitamente implícitos be) tiene una ejecución equivalente a c1 && (c2 && c3) (concretamente, ejecuta las condiciones de izquierda a derecha hasta que uno devuelve false y devuelve eso, o si ninguno devuelve true ), y no puedo imaginar un compilador razonable que genere un código diferente para los dos casos En realidad, me parece que la agrupación de la derecha sugiere más cómo se evalúa la expresión, pero realmente no hace ninguna diferencia; lo mismo vale para or .

¿Esto es aún más claro para el operador condicional (ternario) ? ... : ? ... : . Aquí se aplica la asociatividad, porque hay subexpresiones abiertas en ambos lados (véase mi oración inicial); ¿El operando del medio está encerrado ? y : y nunca requiere paréntesis adicionales. De hecho, este operador se declara de derecho asociativo, lo que significa que c1 ? x : c2 ? y : z c1 ? x : c2 ? y : z c1 ? x : c2 ? y : z debe leerse como c1 ? x : (c2 ? y : z) c1 ? x : (c2 ? y : z) lugar de como (c1 ? x : c2) ? y : z (c1 ? x : c2) ? y : z (los paréntesis implícitos están a la derecha). Sin embargo, con los paréntesis implícitos los dos operadores ternarios se ejecutan de izquierda a derecha ; La explicación es que la semántica del operador ternario no evalúa primero todas las sub-expresiones.

Volviendo al ejemplo de su pregunta, asociatividad a la izquierda (o agrupación de izquierda a derecha) significa que su producto de vector de matriz se analiza como ((M1*M2)*M3)*v . Aunque matemáticamente es equivalente, es prácticamente imposible que esto se ejecute como M1*(M2*(M3*v)) , aunque sea más eficiente. La razón es que la multiplicación de punto flotante no es verdaderamente asociativa (solo aproximadamente), ni tampoco es la multiplicación de matriz de punto flotante; el compilador por lo tanto no puede transformar una expresión en la otra. Tenga en cuenta que en ((M1*M2)*M3)*v no se puede decir cuál de las matrices se aplica primero a un vector, porque ninguna de ellas es: la matriz de los mapas lineales compuestos se calcula primero, y la matriz se obtiene Aplicado al vector. El resultado será aproximadamente igual al de M1*(M2*(M3*v)) en el que se aplica M3 , luego M2 y finalmente M1 . Pero si quieres que sucedan cosas así, tienes que escribir esos paréntesis.

Answer 6

a = (x * y) * z es de izquierda a derecha y a = x * (y * z) es de derecha a izquierda.

La multiplicación matricial de glm se asocia de izquierda a derecha porque sobrecarga al operador * . El tema aquí es sobre el significado de las multiplicaciones matriciales en términos de transformaciones geométricas, en lugar de la asociatividad matemática.