La filosofía de la programación

Pensamiento lógico === buen software

La programación es la nueva alfabetización. Pero, ¿cómo escribimos buenos programas? Aquí están las preguntas recurrentes que debemos resolver:

  • ¿Cómo se nos ocurren soluciones algorítmicas a un problema?
  • Entonces, ¿cómo sabemos que la solución realmente funciona?
  • Incluso si estamos seguros de que funciona, ¿cómo le decimos a la computadora que lo ejecute?

Dato curioso: si tiene dificultades para resolver alguna de estas preguntas, en realidad está haciendo filosofía.

Para ver por qué, examinemos algunas similitudes interesantes entre la programación y el razonamiento filosófico.

El primer principio: hay que pensar mucho.

Las computadoras no hacen nada más inteligente de lo que nosotros podemos hacer; la diferencia es que lo hacen a mayor velocidad.

Pero no pueden resolver un problema real como "¿cómo llego a mi oficina desde casa?"

Un método eficaz puede (en principio) ser llevado a cabo por un ser humano sin la ayuda de ninguna maquinaria, excepto el papel y el lápiz.— The Church-Turing Thesis

El mérito de la programación aún reside en la parte de razonamiento. Es decir, traducir un problema del mundo real en instrucciones simples que una computadora pueda ejecutar.

Por supuesto, los diferentes lenguajes de programación tienen diferentes niveles de abstracciones semánticas. Un programa de Python puede ser más corto que su contraparte de C. Pero eso solo cambia la cantidad de traducciones. No podemos deshacernos del trabajo de traducción. Pero dejaremos esta discusión para más adelante.

El flujo de razonamiento de un programador

Ahora estamos mirando la descripción de algún problema. Primero podemos buscar ejemplos de insumo-producto a pequeña escala para comprender el problema:

Inducción. Necesitamos un algoritmo que pueda manejar tales ejemplos. Ahora estás haciendo inducción: generalizando principios a partir de la experiencia.

Deducción. ¿Cómo sabemos si funciona para otra entrada desconocida? Hacemos deducción para demostrar la exactitud de nuestro algoritmo.

Ontología . Tenemos que mantener los datos en la memoria de la computadora. El objetivo es hacerlos eficientes para que los procesen las computadoras. En otras palabras, ¿qué estructura de datos puede capturar mejor el flujo dinámico de mi información?

Inducción de nuevo . Luego viene la etapa final: depuración. Inducemos la parte defectuosa del programa de analizar los resultados inesperados.

Un ejemplo

Ahora examinemos el proceso anterior siguiendo este ejemplo real: encontrar el camino más corto desde el vértice A al vértice E.

Para problemas de pequeña escala, podemos resolverlos por instinto. Es muy sencillo para nosotros reconocer la solución ACE con solo mirar.

Pero, ¿qué pasa con las topologías más complejas? ¿Qué pasa con los diferentes pesos de los bordes?

Necesitamos ayuda de las computadoras. Sin embargo, no es sencillo decirle a una computadora qué hacer. Existe una brecha entre cómo piensan los humanos y cómo funciona una computadora.

El proceso

1. Generalizar principios de la experiencia: algoritmos

Para decirle a una computadora qué hacer, primero debemos idear un procedimiento algorítmico.

Las estrategias codiciosas son una forma natural de proceder. Es decir, partiendo del vértice de origen A y siguiendo el camino más corto conocido. Siga explorando nuevos vértices hasta llegar al destino E. Y, de hecho, este enfoque satisface nuestro ejemplo.

La intuición es que, a lo largo del camino más corto hacia un destino, cada nodo intermedio también se visita en el camino más corto. (Por supuesto, esta intuición asume que todos los bordes tienen pesos positivos. Esto puede no ser cierto, dependiendo de las aplicaciones. Discutiremos esto en detalle más adelante).

Entonces aquí está el procedimiento algorítmico:

  1. Algunas configuraciones: (1) guardar los vértices que hemos visitado: un conjunto ( visited), (2) recordar las distancias más cortas conocidas a cada vértice que usan solo vértices descubiertos : otro conjunto distance(u). La distancia de cada vértice es inicialmente infinita, excepto que el vértice de origen es 0.
  2. Ahora comenzamos a explorar: primero visitamos el vértice que tiene el camino más corto conocido hasta ahora, digamos que lo es u. (Inicialmente sería el vértice fuente).
  3. Cuando uestamos en el vértice , miramos alrededor de los bordes salientes. Cada arista, digamos (u,v), nos da un camino al vértice vque usa el vértice ucomo último pero solo un paso. Si alguno de ellos es de hecho un camino más corto v, o el primer camino que encontramos v, hurra, podemos actualizar nuestro conjunto de caminos más cortos ahora. De lo contrario, ignore y continúe.
  4. Hemos terminado con el vértice u, por lo que lo agregamos a nuestro visitedconjunto.
  5. Vuelve al paso 2, sigue explorando hasta que hayamos visitado todos los vértices.

distanceahora puede decirnos las distancias globales más cortas, porque se usa para mantener las distancias más cortas utilizando solo los nodos visitados. Y todos los vértices se visitan cuando finaliza el algoritmo.

Acabamos de reinventar el algoritmo de Dijkstra. Por supuesto, existen muchos otros algoritmos para encontrar el camino más corto. Pero el punto es que necesitamos un procedimiento algorítmico para resolver el problema.

2. Validar los principios generales por deducción

¿Cómo nos aseguramos de que los principios del algoritmo sean correctos? Podemos aumentar nuestra confianza probando el principio con más ejemplos de entrada o, de manera más efectiva, podemos encontrar una prueba matemática rigurosa.

Como una proposición a priori en filosofía, la corrección de un algoritmo es independiente de su ejecución. En otras palabras, las pruebas no pueden garantizar la exactitud de los algoritmos. Necesitamos probarlo.

Aquí está el flujo básico de la prueba:

1. Para todos los vértices visitados, encontramos los caminos más cortos.

2. Se visita el destino.

3. Por tanto, encontramos el camino más corto hasta el destino.

¿No te parecen algo familiares? Me gusta esto:

1. Todos los hombres son mortales.

2. Sócrates es un hombre.

3. Por tanto, Sócrates es mortal.

De hecho, esto es silogismo, una forma clásica de razonamiento deductivo. Esto es más o menos lo que están haciendo los lógicos.

Otro hecho histórico interesante: el concepto formal de computación fue planteado por primera vez por los lógicos en la década de 1930. Necesitaban saber si ciertos problemas lógicos son realmente solucionables (para evitar perder el tiempo resolviendo algo irresoluble). Para responder a eso, se les ocurre la noción de computabilidad.

Más tarde, en 1936, Alonzo Church y Alan Turing desarrollaron la definición formal de Computabilidad, de forma independiente, al mismo tiempo. Este artículo ofrece una revisión histórica de la computación.

La exactitud de la conclusión depende de las dos primeras premisas. En nuestra prueba, la segunda premisa es trivial, ya que nuestro algoritmo está visitando literalmente todos los nodos. Sin embargo, demostrar la primera premisa, que encontramos el camino más corto cuando visitamos un nodo, necesita algo de trabajo.

La inducción matemática puede ayudar. En realidad, es una de las técnicas más útiles para demostrar la exactitud de muchos otros algoritmos.

El flujo general es el siguiente. Primero, si un algoritmo funciona en la entrada 0, y segundo, si el hecho de que funcione en la entrada nimplica que también funciona en la entrada n+1 , entonces funciona para todas las entradas mayores o iguales a 0. En este punto, puede garantizar la exactitud de su algoritmo.

Para simplificar, lo referiré a esta nota de clase para obtener la prueba completa de este algoritmo de búsqueda de ruta.

Tenga en cuenta que no debemos confundir inducción matemática e inducción filosófica. Según la definición filosófica, la inducción matemática es un proceso de razonamiento deductivo, porque su corrección está contenida en sí misma, sin observaciones externas.

La lección es: cuando se nos ocurre un algoritmo, debería poder manejar todos los casos de ejecución posibles.

En la práctica, pasar por la demostración matemática rigurosa puede no ser la estrategia más eficiente. Pero al menos queremos considerar tantos casos de ejecución como sea posible, especialmente los contradictorios. Esta práctica mejoraría la solidez de nuestro código.

Es posible que haya notado que, en nuestro algoritmo de búsqueda de ruta de ejemplo, no funciona si el peso del borde es negativo. Puede encontrar el motivo en esta nota de clase. Para manejar un gráfico de peso negativo, puede utilizar el algoritmo Bellman-Ford.

3. El problema de la ontología: estructura de datos

Hasta ahora nos convencimos de que tenemos un algoritmo correcto. Pero esta es solo la mitad de la batalla.

La siguiente pregunta es, ¿cómo alimentamos la información en las computadoras? A los seres humanos les gusta la información visualizada, como gráficos o histogramas. Pero las computadoras de hoy solo manejan bits binarios.

Necesitamos crear una estructura de datos que contenga la información esencial. Y debería ser eficiente que un programa se procese al mismo tiempo.

Continuemos con nuestro ejemplo de búsqueda de caminos. Una ruta es una lista ordenada. Pero es irritante lidiar con él, en comparación con un número entero. Tenga en cuenta que en nuestro algoritmo tenemos que encontrar la ruta más corta de nuestro conjunto de rutas descubiertas. Y luego iterar hasta el final. Parece que tenemos que dedicar una matriz o memoria para almacenar cada ruta.

¿Podríamos hacerlo mejor? Tenga en cuenta que en una ruta válida, las apariciones consecutivas de elementos deben corresponder a un borde en el gráfico. Pero ya tenemos la información del borde y es la misma para todas las rutas. ¿Por qué no podemos deshacernos de esta información redundante?

Bueno, podemos deshacernos de la lista. Resulta que para obtener el camino más corto, el paso intermedio es determinar cuál es el siguiente salto al que debe ir. Todo lo que necesitamos para recuperar la ruta más corta desde la fuente A hasta cualquier nodo objetivo es solo el gráfico en sí, y la distancia más corta desde A hasta cada nodo.

Una representación visual está en la imagen de arriba. Esta representación es eficiente en la memoria. También es más eficiente que el programa lo procese.

Así es como construye el camino más corto usando solo el vector de distancia. Comience desde el vértice de destino y una ruta vacía. Busque vértices intermedios a través de los bordes entrantes. Elija el que tenga el valor más bajo en distance. Agréguelo al comienzo del camino. Repetir hasta llegar a la fuente. Este truco en realidad tiene una notación formal, llamada retroceso.

Los filósofos buscan la verdad eterna. Y los programadores quieren descubrir la estructura de datos precisa que mejor captura la dinámica de la información. Como puede ver en el ejemplo de búsqueda de ruta, todo lo que necesita para dar una ruta más corta es solo un vector, que le indica las distancias más cortas a cada vértice. Esto es válido para cualquier gráfico, independientemente del número de vértices o aristas.

4. Proposición a posteriori: depuración

La mayoría de los programadores han pasado por este razonamiento muchas veces. Apuesto a que esta es una de las partes más difíciles y que requieren más tiempo de cualquier tarea de programación.

Por ejemplo, las fallas de segmentación en programas C a menudo son causadas por referencias de puntero nulo. Aprendí esto después de lidiar con toneladas de fallas de segmentación de C / C ++. Por supuesto, hay casos más sutiles que se relacionan con los hábitos de programación personales.

El siguiente ejemplo es un error de sintaxis cometido por un programador. La condición if debería haber sido is_float==1, pero el programador confundió el operador igual lógico con un operador de ==evaluación =. Esto aún pasará la verificación del compilador, porque cualquiera de las dos tiene la sintaxis correcta.

if (is_float = 1) { // do something}

Este es un proceso de razonamiento inductivo. Su diagnóstico de depuración solo tiene sentido si ha observado suficientes ejecuciones del programa.

Aquí es donde entra en juego el valor de la práctica. Independientemente del tipo de técnicas que esté aprendiendo, debe recopilar suficientes datos prácticos. De lo contrario, no tendría suficiente experiencia para realizar la inducción.

Debes estar atento a los patrones recurrentes en tus códigos de errores. Cuando encuentra un error, arreglarlo no es suficiente. Necesita un análisis de causa-efecto adicional en su propia práctica de programación. Pregúntese: ¿esta parte de mis hábitos de programación es particularmente vulnerable a este tipo de errores?

Entonces, ¿por qué importa?

La programación no se trata solo de escribir código, es una forma sistemática de razonamiento. Porque el código, o las instrucciones, es solo un medio para un fin. Con el desarrollo de la técnica de síntesis de programas, es posible que ni siquiera se moleste en escribir código y depurar usted mismo. Todo lo que importa es si puede decirle a la computadora qué hacer.

Como primer paso para mejorar sus habilidades de programación, este artículo revela el patrón de razonamiento subyacente que quizás ni siquiera reconozcamos cuando estábamos programando. La mayoría de nosotros confiamos en la reflexión automática y subconsciente para terminar la mayoría de nuestras tareas diarias. Pero, ¿de dónde viene la mejora? Primero viene de notar alguna falacia o errores que cometimos en nuestro proceso de razonamiento.

Para obtener consejos prácticos, recomiendo este artículo sobre cómo pensar como un programador y este libro sobre el mismo tema pero con más detalles.

Referencias

  • Computación, cuestiones filosóficas sobre. Matthias Scheutz.
  • La tesis de Church-Turing.
  • Piense como un programador: Introducción a la resolución creativa de problemas. V. Anton Spraul.