Si quisiera ser sarcástico, podría decir que los lenguajes de programación son sistemas formales, por lo que se "basan" en ellos mismos, o más pragmáticamente, "se basan" en sus predecesores. Por desgracia, esta es probablemente la afirmación más acertada. Los paradigmas de programación no están definidos formalmente, ni siquiera claramente. Peter Van Roy ofrece una noción de "paradigma" mucho más matizada y rigurosamente definida .
Los lenguajes funcionales y lógicos suelen agruparse en una categoría más amplia denominada lenguajes "declarativos". En la práctica, estos tienden a tener vínculos más claros y estrechos con los sistemas formales de la lógica/matemáticas, aunque las variantes "impuras" debilitan estos vínculos de manera significativa. Esto incluye los lenguajes funcionales y su relación con el cálculo lambda. Este ejemplo se ha convertido en una especie de piedra de toque, ya que el cálculo lambda ha demostrado ser mucho más importante de lo que se pretendía en un principio. Tiene aplicaciones a la lógica, la topología, la teoría de categorías, la lingüística y, por supuesto, la informática. Si nos limitamos a la informática, a menudo se utiliza en la semántica formal (especialmente en la semántica denotativa) como base para entender lenguajes de programación arbitrarios, no sólo funcionales. También está bastante claro que los lenguajes funcionales "puros", como Haskell o Agda, son en realidad poco más que variantes azucaradas de cálculos lambda tipados.
Los lenguajes de programación lógica están, por supuesto, relacionados con la lógica formal y el álgebra relacional. Desgraciadamente, Prolog ha dominado por completo la mentalidad de la comunidad de programadores lógicos, y está lejos de ser un lenguaje lógico "puro". Se basa en un fragmento muy débil de la lógica de primer orden llamado cláusulas de Horn y en un procedimiento de búsqueda de pruebas de la lógica clásica. Alejándose de la lógica clásica, Lambda Prolog fue capaz de expandirse a un fragmento mucho mayor de la lógica: las fórmulas hereditarias de orden superior de Harrop. Esto permite que algunas características, por ejemplo, los módulos, se manejen de forma lógica en contraposición a la forma ad-hoc en que se manejan en Prolog. Muchas de las características no lógicas de Prolog ("impurezas"), como afirmar/retirar, se eliminaron en Lambda Prolog, convirtiéndolo en una encarnación mucho más pura de la programación lógica. En una dirección diferente, Datalog se basa en un más débil lógica que Prolog, pero también deja de lado muchas de las características no lógicas de Prolog y tiene conexiones muy estrechas con la teoría de modelos finitos. Lo que necesita un sistema formal para servir de lenguaje de programación lógica se ha plasmado en el concepto de lenguaje de programación lógico abstracto . Podría decirse que un Prolog puro idealizado podría servir para la programación lógica un papel similar al del cálculo lambda para la programación funcional.
El contraste con los lenguajes declarativos son los lenguajes imperativos. A menudo se dice que se basan en las máquinas de Turing, pero esto no tiene mucho sentido, ya que muy poco de la teoría o la práctica se relaciona con las máquinas de Turing. No existe un cálculo "fundacional" generalmente aceptado para esta clase de lenguajes, a no ser que se trate del cálculo lambda. Sin embargo, ha habido intentos de crear tales cálculos fundacionales. Cabe destacar: El de Abadi y el de Cardelli $\sigma$ -cálculo para la programación orientada a objetos; el muy reciente libro de Marc Bender Cálculo de asignaciones para la programación imperativa en general; y el muy pragmático Peso pluma Java para lenguajes OO basados en clases tipo Java. Ninguno de ellos tiene el reconocimiento y mucho menos la importancia del cálculo lambda.
En el caso de los lenguajes de programación orientados a objetos, existe quizás una base más convincente y fundamental, aunque este punto de vista sea idiosincrásico. En mi opinión, muchas decisiones tomadas en los lenguajes orientados a objetos pueden justificarse relacionándolas con el $\pi$ -cálculo . Cuando se programa en el crudo $\pi$ -cálculo, surgen muchos patrones de tipo OO. Sin embargo, un argumento más convincente proviene de la "no transformación" del $\pi$ -cálculo que lleva al azul y al cálculos azules profundos . Este último se conecta directamente con el $\lambda$ -, $\pi$ -, y $\sigma$ -calculi. Por supuesto, el $\pi$ -es un cálculo para la computación concurrente y muchos lenguajes OO no son concurrentes. Sin embargo, históricamente ha habido muchos vínculos entre la programación concurrente y la programación orientada a objetos, en particular el paso de mensajes.
