¿Cómo leer y aprender "El arte de la programación informática (TAOCP)"?

¡Ay, Dios! "El arte de la programación informática" citó el comentario del famoso Wang Yin sobre TAOCP: Hace tiempo que quería escribir una opinión sobre El arte de la programación informática de Knuth. No esperaba encontrar un TAOCP similar sobre Knuth tan pronto como entré a Amazon. Creo que la mayoría de las personas que afirman haber leído o comprado su libro simplemente lo usan como una especie de derecho a fanfarronear o como decoración. Mi compañero de clase frente a mí compró un juego de tres libros nuevos de tapa dura hace unos años, que costaron más de 200 yuanes. Pero él nunca miró. Lo tomé prestado, leí algunas páginas y luego lo dejé allí sin leer. ¿Cómo puedo tener tiempo para verlo implementar una lista enlazada simple usando lenguaje de máquina con 6 bits por byte? Un día, un compañero de estudios entró y vio el conjunto de libros en mi estantería. Mostró una sensación de asombro: "¡Excava! ¡Hermano mayor! ¡Eres tan increíble! ¡De hecho, leíste un libro tan profundo que me quedé atónito!" Bueno, no está mal. Este conjunto de libros hará que la gente me mire con admiración cuando lo coloquen en la estantería. Probablemente eso es lo que realmente le hace a mucha gente. Otros pueden ayudar a deificar este conjunto de libros y al mismo tiempo deificarse a sí mismos. Por ejemplo, puede decir: "¡Si alguien ha leído El arte de la programación informática de Don Knuth, lo contrataré!" más informado que la persona promedio que ha leído el libro. Sea un poco más alto. Se dice que Bill Gates hizo esto. Dudo que lo haya leído él mismo. Una de las razones por las que odio este libro es que Knuth lo escribió deliberadamente en el lenguaje de máquina de un procesador llamado MIX. Aunque diseñó un nuevo procesador MMIX en la nueva versión del libro, fue un cambio de sopa pero no de medicina. Creía que un libro de programación informática "atemporal" no debería utilizar lenguajes de alto nivel porque fácilmente quedarían obsoletos. Pero se equivocó. El lenguaje de máquina es precisamente lo que tiene más probabilidades de quedar obsoleto. Basta ver cuántas marcas de procesadores actualizados existen ahora. De hecho, existen lenguajes de muy alto nivel en el mundo que no han quedado obsoletos desde la década de 1960 hasta la actualidad. Predigo que MMIX será eliminado en un futuro próximo. Lo curioso es que MMIX agrega una "M" a MIX, que significa Millennium. La monografía al respecto también se llama MMIXware: una computadora RISC para el tercer milenio. Dentro de mil años o incluso dentro de cien años o unas pocas décadas, no está claro si las computadoras seguirán siendo circuitos integrados binarios o no. Además, este procesador en realidad está tomado de otros procesadores como RISC II, Sparc y similares. , no hay una gran innovación. Imprimió el programa de simulación del procesador en papel y lo vendió diciendo: "Un programa excelente debe ser tan fácil de leer como una buena novela. Un programador excelente ganará el Premio Pulitzer en el futuro. Está bien escribir una pequeña parte introductoria". de la informática en lenguaje de máquina, pero usarlo para escribir un libro completo fácilmente haría que los lectores se perdieran el bosque por los árboles. Uno de los fenómenos más comunes al ver TAOCP es: "¡Guau! Entonces este programa se puede escribir así, pero no sabes por qué está escrito así". Aunque se pueden conocer algunas razones subyacentes, los lectores nunca comprenderán los principios más fundamentales. Es como ver cada píxel de una imagen con claridad, pero no reconocer que la imagen es en realidad un conocido. Puedes ver claramente dónde puede moverse cada pieza del tablero de ajedrez, pero no puedes ganar el juego. Dijkstra dijo que la ciencia de la computación no debería llamarse "ciencia de la computación", al igual que la cirugía no debería llamarse "ciencia del cuchillo". Pero ¿qué tiene esto que ver con Knuth? Su libro se llama El arte de... Hablemos de su cheque... Mucha gente tomó el cheque de Knuth como algo para lucirse. Una vez vi una foto de un cheque de Knuth colgada en la página de inicio de un profesor de Cambridge. ¿El cheque de Knuth realmente sirve para presumir? Déjame decirte que los errores que encontré fueron solo errores tipográficos. No esperaba que me diera un cheque. ¿Quién le dijo que podía escribir Millennium como Millenium si no tenía cuidado al escribir? ¡Ey! Cuando reuní suficiente dinero para pagar una comida, quise ir al Banco de China para cobrarlo y prepararme para cambiar el dinero por una gran comida. Pero el empleado del banco me dijo que tenían que enviar el cheque de regreso a los Estados Unidos para obtener el efectivo. ¡El costo de hacerlo era mucho más alto que el valor del cheque en sí! Entonces Knuth me hizo algunas promesas vacías. ¡Maldición! Debería haberlo pensado hace mucho tiempo, ¿por qué no transfirió dinero a la tarjeta de crédito de todos en lugar de usar algo obsoleto como un cheque? Obviamente sintió que nadie cobraría el cheque con su firma, e incluso lo enmarcó como un recuerdo. Hmmm... Supongo que estás siendo despiadado~ Está bien, es tanto tiempo. Echemos un vistazo a la reseña de este libro escrita por otra persona. Elefante blanco, esto realmente expresa lo que siento acerca de este conjunto de libros. (Pero no estoy de acuerdo con algunas de las opiniones del revisor, como "La notación O (n) es suficiente".

) ¡Espero que haya comentarios públicos sobre los artículos en el futuro! La historia de Dan Friedman (4) - C311 Cuando me transfirieron por primera vez a IU desde Cornell, Dan Friedman me pidió que tomara su clase de posgrado en lenguaje de programación B521. Usé la excusa de que había tomado un curso de lenguaje de programación en Cornell para no tomar su clase. Friedman me llamó a su oficina, me pidió que me sentara a su lado y me dijo amablemente: "Wang Yin, sé que has tomado este tipo de clases en Cornell. También sé que Cornell es una escuela mucho mejor que IU. . Pero el método de enseñanza de cada profesor es diferente. Deberías venir a mi clase. Mis amigos y yo somos profesores aquí, no porque nos guste esta escuela, sino porque nuestros familiares y amigos están aquí "más tarde, porque el tiempo coincidió con el curso. B522 de Amr Sabry (mi tutor actual), él hizo arreglos especiales para que yo asistiera al curso de pregrado C311, pero tomé el crédito del curso de posgrado. Más tarde descubrí que básicamente no había diferencia en el contenido de los dos cursos, excepto que los estudiantes de posgrado tenían más tareas. En la primera clase, dijo algo que todavía recuerdo: ""The Little Schemer" y "Essentials of Programming Languages" son los libros de texto de referencia para esta clase, pero nunca hablo del contenido de mis libros en clase. "Tan pronto Cuando comencé, descubrí que este curso era muy diferente de lo que aprendí en Cornell. Aunque hay algunos conceptos, como cierre y CPS, que aprendí en Cornell, en su clase vi un lado completamente diferente de estos conceptos, tanto es así que sentí que en realidad no entendía estos conceptos en absoluto antes. ! Esto se debe a que cuando Cornell aprendió estas cosas, solo las usaba para la tarea, pero en la clase de Friedman las usé para lograr objetivos prácticos, así que realmente me di cuenta de la connotación y el valor de estos conceptos. Un ejemplo es que, unas semanas después de iniciado el curso, comenzamos a escribir un intérprete para ejecutar programas Scheme simples. Luego realizamos la transformación CPS en este intérprete, introducimos variables globales como "registros" (registro) y convertimos la continuación generada por CPS en una estructura de datos (es decir, una pila). Lo que obtenemos es una máquina abstracta, que es esencialmente equivalente a una unidad central de procesamiento (CPU) o una máquina virtual (como una JVM) en una máquina real. ¡Así que “inventamos” la CPU desde cero! A partir de aquí, entendí realmente la naturaleza de los registros, pilas, etc., y por qué los necesitamos. Sólo entonces comprendí realmente por qué la arquitectura de von Neumann fue diseñada así. Más tarde, nos pidió que leyéramos un artículo de su buen amigo Olivier Danvy, que describía cómo derivar diferentes tipos de modelos de máquinas abstractas a partir de varios intérpretes mediante la transformación CPS. Esta fue la primera vez que sentí el tremendo poder de la teoría del lenguaje de programación en el mundo real y también me hizo comprender que las máquinas no son la esencia de la informática. Las máquinas se pueden implementar utilizando cualquier tecnología viable, como circuitos integrados, láseres, cuánticos, moléculas, genes... Pero no importa qué material se utilice como máquina, la semántica que queremos expresar, es decir, la esencia de la informática, permanece sin cambios. Y estos no son todos los contenidos de mi C311. En la segunda mitad del semestre, comenzamos a aprender miniKanren, un lenguaje de programación lógica que diseñó para la enseñanza. Este lenguaje es similar a Prolog, pero elimina muchas de las deficiencias de Prolog y se vuelve más fácil de entender. El libro de texto es "El intrigante razonado" que nos entregan de forma gratuita. ¡Al final del libro, en dos páginas, está la implementación de todo el lenguaje miniKanren! Aprendí relativamente rápido y luego comencé a modificar la implementación, rediseñando algunas partes y luego agregando algunas características que quería. Este tipo de enseñanza me dio la capacidad de diseñar lenguajes lógicos, en lugar de ser simplemente un usuario. Esto es algo que es imposible de hacer cuando se aprende Prolog, porque la complejidad de la implementación de Prolog hará imposible que los principiantes comiencen y solo podrán permanecer en la etapa de usuario. Tengo mucha suerte de haberlo escuchado y haber tomado esta clase; de ​​lo contrario, no estaría donde estoy hoy. ¿Quién es el verdadero experto en lenguajes de programación? Knuth dijo una vez algo similar: "Si no entiendes TAOCP, no seas programador". Siempre es aclamado como el "dios de la informática" y habla de literatura en sus discursos. , el arte, Dios y la religión, dando a la gente una repentina sensación de misterio. Siempre decía que los programadores deberían aprender lenguaje de máquina, no lenguaje de alto nivel, porque las máquinas son la verdad inmutable. Pero Knuth analizó esta cuestión no desde una perspectiva científica, sino desde su propia parcialidad personal.

Cuando vio que el desarrollo de lenguajes como Fortran, Lisp, ALGOL, Pascal, C, C++ y Java parecía no tener fin, no comprendió los principios inmutables. No es una persona fuerte en el diseño de lenguajes de programación. Es muy posible que no comprenda en absoluto el cálculo lambda y la teoría de tipos; de lo contrario, no habría diseñado un lenguaje tan desorganizado como TeX. La calidad de la composición tipográfica TeX es comprensible, pero en 1978 todavía usaba el alcance dinámico, que durante mucho tiempo había sido odiado por los expertos en lenguajes de programación, junto con otros diseños de mala calidad, lo que indica su falta de comprensión de la teoría del lenguaje de programación. De hecho, TeX contiene un lenguaje de extensión completo de Turing porque Knuth adoptó la sugerencia de Guy Steele (el inventor de Scheme), pero Knuth no lo diseñó bien. Knuth sentía que las máquinas eran la verdad inmutable, por lo que insistió en escribir TAOCP en lenguaje de máquina. Pero como el lenguaje de máquina carece de abstracción, los programadores no pueden centrarse en el problema real. Usar lenguaje de máquina para describir algoritmos hará que un problema originalmente simple parezca profundo y difícil de entender, como si el libro nunca estuviera terminado. ¿Cuántas personas han visto realmente TAOCP? Me temo que la mayoría de la gente comprará este conjunto de libros y simplemente los colocará en sus estanterías para lucirlos. Mientras alguien diga que el lenguaje de máquina es demasiado difícil de entender, esta gente dirá que no eres lo suficientemente inteligente para ser programador. De hecho, nunca lo han visto ellos mismos. Mucha gente, incluido Dijkstra, hace tiempo que se da cuenta de que las máquinas no son la esencia de la informática. Dijo: "La informática es un nombre equivocado porque no es la ciencia de las computadoras, al igual que la cirugía no es la ciencia de los cuchillos". Y esta es una verdad que casi todos los expertos en lenguajes de programación comprenden. A sus ojos, esto ya no es un rumor ni una opinión personal, sino un hecho que puede demostrarse mediante la lógica. Las personas que realmente entienden la naturaleza de la informática pueden diseñar hardware completamente nuevo para satisfacer las necesidades semánticas, en lugar de estar controlados por el diseño del procesador. Incluso pueden ir más allá de los circuitos integrados y utilizar otras tecnologías para construir máquinas. Todo esto muestra que la informática es en realidad independiente de la máquina. No importa si tienes malas ideas, pero si insistes en describir las malas ideas como buenas, obstaculizarás el desarrollo de la historia. No niego las importantes contribuciones de Knuth y Ritchie a los algoritmos, la composición tipográfica y los sistemas operativos, pero dado que ellos y sus admiradores a menudo engañan al público sobre cuestiones relacionadas con el lenguaje, siento la necesidad de señalar algunas de sus limitaciones. Linus Torvalds, Guido van Rossum, Eric Raymond y Paul Graham también suelen hacer comentarios sobre el lenguaje, que muchas personas consideran edictos, pero en realidad hay pocas ideas en sus comentarios. De hecho, lo que quiero decir es que la mayoría de los ídolos que adoran los programadores no son verdaderos expertos en lenguajes de programación. Espero que no piensen que esto es alarmista. De hecho, estas son cosas que la mayoría de los científicos informáticos de talla mundial saben desde hace muchos años.