Introducing 

Prezi AI.

Your new presentation assistant.

Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.

Loading…
Transcript

a + b = b + a

Introducción a Generic Programming

El primer algoritmo

Papiro de Rhind (fragmento).

Escrito alrededor de 1650 a. C.

por un escriba egipcio llamado

Ahmes.

Multiplicación Egipcia

El primer algoritmo

Multiplicación Egipcia en C++

El papiro contiene una serie de problemas matemáticos y en él también se encontró el primer algoritmo que se conoce, un algoritmo para multiplicación rápida...

La optimización nos permite hacer a + a sólo una vez y así reducir el número de sumas.

La idea consiste en ir dividiendo por 2 (half) a n e ir duplicando a a.

Para demostrar el algoritmo, Ahmes mostró la siguiente tabla para multiplicar a = 59 por n = 41.

int multiply1(int n, int a) {

if (n == 1) return a;

int res = multiply1(half(n), a + a);

if (odd(n)) res = res + a;

return res;

}

Pero..., nuestro multiply1 sólo funciona para enteros (sí porque "somos egipcios").

¿Pero qué pasaría si quisiéramos escribirlo

para números reales?

Aquí es donde Generic Programming entra en juego...

Antiguo Egipto

Multiplicación

Multiplicación en C++

Supongamos que los Egipcios, hace 4.000 años, contaban con computadoras y con el lenguaje de

programación C++.

¿Cómo hubieran implementado el algoritmo de multiplicación?

Informalmente multiplicación significa agregar algo así mismo un número de veces.

Formalmente, podemos definirlo separándolo en dos casos: multiplicar por 1, y multiplicar por un número más grande que 1.

Los egipcios no usaban notación posicional en su sistema de numeración, tampoco tenían forma de representar el cero.

Entonces multiplicar era un proceso muy difícil. Imaginen multiplicar dos números grandes usando algo parecido a los números Romanos.

Multiplicación Egipcia

a = 59 x n = 41

n a

Helper code

Multiplicación Egipcia en C++

Descargo (disclaimer)

n a

Multiplicación en C++

Multiplicación Egipcia

n a

(1)

1a = a

El algoritmo descripto por Ahmes, conocido por los antiguos matemáticos griegos como "Multiplicación Egipcia", se basa en la siguiente reflexión:

  • multiply0 no es bueno cuando n es un número grande, ya que debemos hacer n-1 sumas.

41 59

int multiply0(int n, int a) {

if (n == 1) return a;

return multiply0(n-1, a) + a;

}

¿Cuántas sumas se hacen usando multiply1?

4a = ((a + a) + a) + a

= (a + a) + (a + a)

dividir por 2

duplicar

a + a + a + ... + a

XLI * LIX = ?

41 59

20 118

10 236

5 472

2 944

1 1888

(2)

(n+1)a = na + a

Esta optimización depende de la ley asociatividad de la suma:

(n - 1) veces

dividir por 2

duplicar

  • Las dos líneas se corresponden con las ecuaciones (1) y (2)
  • n y a deben ser positivos >0 (recordemos que estamos programando en un C++ "Egipcio" de hace 4.000 años)

dividir por 2

duplicar

a + (b + c) = (a + b) + c

Si f(n) es la función para determinar el número de sumas efectuadas por multiply1 dado un entero n, entonces:

  • ¿Cómo podemos mejorarlo?

41 59

20 118

10 236

5 472

2 944

1 1888

Si bien el método de Multiplicación Egipcia implica una optimización importante, el código anterior dista de ser óptimo.

Primero, porque hace llamados a función de forma recursiva y por otras cuestiones.

bool odd(int n) { return n & 0x1; }

int half(int n) { return n >> 1; }

(sólo el cociente de la división entera, se descartan el resto).

f(n) = log2(n) + (ν(n) - 1)

41 x 59 = 59 + 472 + 1888 = 2419

La búsqueda del algoritmo óptimo escapa esta presentación, así que quedará para otro Meetup.

41 x 59 = (1 x 59) + (8 x 59) + (32 x 59)

Siendo ν(n) la cantidad de n impares en la tabla.

¿Qué es Generic Programming?

Generic Programming

Haciendo el algoritmo Genérico

Primer paso hacia la genericidad...

Versión genérica (totalmente)

Las ideas de Stepanov, son ideas provenientes de la matemática y aplicadas a la programación. Particularmente provienen de una rama de la matemática llamada Álgebra Abstracta (ideas desarrolladas a partir del siglo XIX).

Marcamos la interacción entre los tipos de datos:

¿Fin?

template <NonCommutativeAdditiveSemigroup A, Integer N>

A multiply_semigroup(N n, A a) {

// precondition: n > 0

if (n == 1) return a;

A res = multiply_semigroup(half(n), a + a);

if (odd(n)) res += a;

return res;

}

Generic Programming es una manera de programar que se centra en el diseño de algoritmos y estructuras de datos para que funcionen de forma más general, pero..., sin pérdida de eficiencia.

int multiply1(int n, int a) {

if (n == 1) return a;

int res = multiply1(half(n), a + a);

if (odd(n)) res = res + a;

return res;

}

¡No!

El código puede seguir extendiéndose para soportar valores de n = 0 y luego para valores de n < 0.

Pero para ello no nos alcanzan los Semigrupos y vamos a necesitar requerimientos más fuertes, usando otras estructuras algebraicas, como Monoides y Grupos.

Luego, se puede seguir extendiendo el algoritmo abstrayendo la operación a realizar, de + a *.

Pero hemos ido muy lejos en esta presentación... quedará (si les gustó) para un próximo Meetup.

Requerimientos de A

Requerimientos de N

Primera versión (parcialmente) genérica

Requerimientos Semánticos de A

Requerimientos Sintácticos de A

Más requerimientos Sintácticos de A

Requerimientos Sintácticos de N

¿Qué significan esas operaciones?

Nuestro requerimiento principal es que la operación + sea asociativa:

Tuvimos que hacer explícita la pre-condición de que n debe ser mayor a 0, ya que ya no estamos trabajando con el "C++ Egipcio", ahora nuestros enteros incluyen al 0 y los negativos.

Hay más requerimientos sintácticos que están implícitos en el copy-constructor y el operador de asignación, pero no voy a detallarlos aquí, pero...

Tenemos un nombre especial para los tipos que satisfacen estos requerimientos (usuales): regular types.

Definición: Un regular type T es un tipo en el cuál las relaciones entre la construcción, la asignación y la igualdad son las mismas que para los tipos built-in (primitivos), como int.

¿Qué operaciones podemos hacer con "cosas" que sean de tipo A?...

Pueden:

  • Ser sumados (C++: operator+)
  • Pasados por valor (C++: copy-constructor)
  • Asignados (C++: operator=)

Para todo a, b, c perteneciente a A:

a + (b + c) = (a + b) + c

N debe ser un regular type que además implemente:

  • half
  • odd
  • == 0
  • == 1

template <typename A, typename N>

A multiply(N n, A a) {

if (n == 1) return a;

A res = multiply(half(n), a + a);

if (odd(n)) res = res + a;

return res;

}

Requerimientos Semánticos de N

Requerimientos Formales de A:

  • even(n) => half(n) + half(n) = n
  • odd(n) => even(n - 1)
  • odd(n) => half(n - 1) = half(n)
  • Axioma:

n = 1 v half(n) = 1 v half(half(n)) = 1 v ...

  • Debe ser un Regular Type.
  • Debe proveer + asociativa.

En Álgebra Abstracta, las estructuras algebraicas que tienen una operación binaria asociativa, son llamadas Semigrupos.

Entonces podemos decir que A es un Semigrupo, cuya operación es la adición.

Semigrupo aditivo no-conmutativo en C++

Conmutatividad y concatenación de Strings

Requerimientos Formales de A:

Conmutatividad:

Por muchos siglos el símbolo "+" ha sido usado, por convención, como una operación conmutativa (y también asociativa).

Muchos lenguajes de programación (Ej: C++, Rust, Go-lang, C#, Java, Python, Ruby, JS, ...) usan el símbolo "+" para concatenar strings, que es una operación no-conmutativa.

En C++, a los tipos que satisfacen el requerimiento de ser un semigrupo aditivo no-conmutativo los agrupamos bajo el Concept llamado NonCommutativeAdditiveSemigroup.

En C++ un Concept es un conjunto de requerimientos sobre los tipos de datos.

Tal como vimos, los requerimientos pueden ser sintácticos y semánticos. (Además también incluyen requerimientos en cuanto a complejidad computacional)

Por lo tanto podemos estar tentados en llamarlo Semigrupo Aditivo. Pero por convención, se asume que los Semigrupos Aditivos también son conmutativos.

No queremos imponer este requerimiento a nuestro algoritmo, ya que no necesitamos que nuestros tipos sean conmutativos. Así que vamos a decir que nuestro tipo A es un Semigrupo aditivo no-conmutativo (noncommutative additive semigroup).

Esto quiere decir que la propiedad conmutativa no es requerida, pero no significa que no esté permitida. O sea, que un Semigrupo aditivo (conmutativo) es también un Semigrupo aditivo no-conmutativo.

En C++, ¿qué tipos satisfacen estos requerimientos?: Hay varios: uint8_t, int8_t, ..., uint64_t, ... Y el Concept que estos satisfacen es denominado Integer.

"hello" + "world" != "world" + "hello"

Esto viola una práctica estándar en matemática, lo cual no es una buena idea.

...de Concreto a Abstracto...

Las estructuras algebraicas (abstracciones) que aparecieron en el Álgebra Abstracta (Grupos, Monoides, Semigrupos, ...), provinieron de los resultados concretos en una de las ramas más antiguas de la matemática, la Teoría de Números.

Al igual que en matemática, en Generic Programming se recomienda empezar con algo concreto, entenderlo, para luego averiguar cuáles serán las abstracciones correctas.

Emmy Noether

Bibliografía y Referencias

¡Gracias!

  • Últimos libros de Alexander Stepanov:

Elements of Programming, by Alexander Stepanov and Paul McJones

http://www.amazon.com/Elements-Programming-Alexander-A-Stepanov/dp/

From Mathematics to Generic Programming, by Alexander Stepanov and Daniel Rose

http://www.amazon.com/Mathematics-Generic-Programming-Alexander-Stepanov/dp/0321942043

  • Papiro de Ahmes/Rhind

https://es.wikipedia.org/wiki/Papiro_de_Ahmes

http://mathworld.wolfram.com/RhindPapyrus.html

  • Algoritmo de multiplicación rápida:

The Art of Computer Programming, Vol 2 (Seminumerical Algorithms), 3rd Ed., by Donald Knuth.

4.6.3 Evaluation of Powers, page 461

http://www.amazon.com/Computer-Programming-Volumes-1-4A-Boxed/dp/0321751043

From Mathematics to Generic Programming, 1st Ed., by Alexander Stepanov and Daniel Rose

Chapter 2, The first algorithm

  • Álgebra Abstracta

https://es.wikipedia.org/wiki/%C3%89variste_Galois

https://es.wikipedia.org/wiki/Emmy_Noether

http://mathworld.wolfram.com/Semigroup.html

Fernando Pelliccioni

componentsprogramming.com/

@ferpelliccioni

fpelliccioni@gmail.com

Historia

Alexander Stepanov

  • Matemático y programador nacido en la Unión Soviética, emigrado a los Estados Unidos.

  • Viene elaborando las ideas detrás de Generic Programming junto con Dave Musser y otros colaboradores desde hace más de 35 años.

  • Implementación en distintos lenguajes: Scheme, Ada, C++, ...

Alexander Stepanov

  • Trabajó en Bell Labs

Ken Thompson y Dennis Ritchie en una DEC PDP-11

Bjarne Stroustrup

Standard Template Library (STL)

Es la implementación de las ideas de Stepanov y Musser en el lenguaje C++.

Si bien STL se asocia al uso de templates en C++, los templates son herramientas que permiten a C++ soportar Generic Programming y es importante conocer como trabajan, pero...

Generic Programming no es un conjunto de herramientas sino que es es una actitud sobre cómo programar.

Learn more about creating dynamic, engaging presentations with Prezi