Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Introducción a Generic Programming

No description
by

Fernando Pelliccioni

on 1 April 2016

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Introducción a Generic Programming

Introducción a Generic Programming
Historia
Generic Programming
¿Qué es Generic Programming?
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
.

Haciendo el algoritmo Genérico
El primer algoritmo
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
Alexander Stepanov
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.
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).

...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
Papiro de Rhind (fragmento).

Escrito alrededor de 1650 a. C.
por un escriba egipcio llamado
Ahmes.

El primer algoritmo
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...
Antiguo Egipto
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.
XLI * LIX = ?
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.
1a = a
(n+1)a = na + a
(1)
(2)
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?
Multiplicación en C++
int multiply0(int n, int a) {
if (n == 1) return a;
return multiply0(n-1, a) + a;
}
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)
Multiplicación en C++
multiply0 no es bueno cuando
n
es un número grande, ya que debemos hacer n-1 sumas.
a + a + a + ... + a
(n - 1) veces
¿Cómo podemos mejorarlo?
Multiplicación Egipcia
El algoritmo descripto por Ahmes, conocido por los antiguos matemáticos griegos como "
Multiplicación Egipcia
", se basa en la siguiente reflexión:
4a = ((a + a) + a) + a
= (a + a) + (a + a)
Esta optimización depende de la ley
asociatividad
de la suma:
a + (b + c) = (a + b) + c
Multiplicación Egipcia
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
.
Multiplicación Egipcia
a = 59
x
n = 41
Multiplicación Egipcia
a = 59
x
n = 41
41 59
20 118
10 236
5 472
2 944
1 1888
n a
dividir por 2
duplicar
Multiplicación Egipcia
a = 59
x
n = 41
41 x 59 =
59 + 472 + 1888
= 2419
41 59
20 118
10 236
5 472
2 944
1 1888
n a
dividir por 2
duplicar
(sólo el cociente de la división entera, se descartan el resto).
41 59

n a
dividir por 2
duplicar
41 x 59 = (1 x 59) + (8 x 59) + (32 x 59)
Multiplicación Egipcia en C++
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;
}
Helper code
bool odd(int n) { return n & 0x1; }
int half(int n) { return n >> 1; }
Multiplicación Egipcia en C++
¿Cuántas sumas se hacen usando multiply1?
f(
n
) = log2(
n
) + (ν(
n
) - 1)
Si f(n) es la función para determinar el número de sumas efectuadas por multiply1 dado un entero n, entonces:


Siendo ν(
n
) la cantidad de
n
impares en la tabla.
Descargo (disclaimer)
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.


La búsqueda del algoritmo óptimo escapa esta presentación, así que quedará para otro Meetup.
Multiplicación Egipcia en C++
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...
Primer paso hacia la genericidad...
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
;
}
Primera versión (parcialmente) genérica
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 de A
Requerimientos Sintácticos de A
¿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=)
Requerimientos Semánticos de A
¿Qué significan esas operaciones?
Nuestro requerimiento principal es que la operación + sea
asociativa
:
Para todo a, b, c perteneciente a A:
a + (b + c) = (a + b) + c
Más requerimientos Sintácticos de A
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.
Requerimientos Formales de A:
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.
¡Gracias!
Fernando Pelliccioni
componentsprogramming.com/
@ferpelliccioni
fpelliccioni@gmail.com
Requerimientos Formales de A:
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
.
Conmutatividad:
a + b = b + a
Conmutatividad y concatenación de Strings
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.
"hello" + "world" != "world" + "hello"
Esto viola una práctica estándar en matemática, lo cual no es una buena idea.
Requerimientos de N
Requerimientos Sintácticos de N
N
debe ser un
regular type
que además implemente:
half
odd
== 0
== 1
Requerimientos Semánticos de N
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 ...
En C++, ¿qué tipos satisfacen estos requerimientos?: Hay varios: uint8_t, int8_t, ..., uint64_t, ... Y el
Concept
que estos satisfacen es denominado
Integer.
Semigrupo aditivo no-conmutativo en C++
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)
Versión genérica (totalmente)
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;
}
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.
¿Fin?
¡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.
Marcamos la interacción entre los tipos de datos:
Bibliografía y Referencias
Ú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
Full transcript