Medida de poder que no sea la integridad de Turing

18

Originalmente intenté preguntar esto en StackOverflow, pero fue demasiado subjetivo :-(. Estoy interesado en los métodos para definir el poder de los lenguajes de programación. Turing es completo, pero está casi universalmente satisfecho. Lo que sería bueno es definir un medida de poder que discrimina entre los lenguajes de programación que realmente se usan. Por ejemplo, ¿alguien puede proponer un método no subjetivo que discrimine entre ensamblador y Java?

La integridad de Turing significa que un lenguaje tiene el máximo poder en lo que puede generar (lo que significa que puede hacer cualquier cosa que no esté basada en el tiempo en el mundo real). Entonces, si queremos definir una medida de poder más fuerte, debemos adoptar otro enfoque. Se sugirió brevedad en la pregunta original, pero esto no es fácil de definir en absoluto. ¿Alguien tiene alguna otra sugerencia?

Casebash
fuente

Respuestas:

24

La noción que está buscando se llama expresividad y Matthias Felleisen tiene una definición matemáticamente rigurosa:

" Sobre el poder expresivo de los lenguajes de programación "

www.ccs.neu.edu/scheme/pubs/scp91-felleisen.ps.gz (versión PostScript)

La intuición detrás de la idea es que si tiene dos programas equivalentes en dos idiomas diferentes, por ejemplo, el programa A en el lenguaje X y el programa B en el lenguaje Y, y si realiza un cambio local en A que requiere un cambio global en B , entonces X es más expresivo que Y.

Un ejemplo que ofrece Felleisen es la asignación: en los lenguajes de programación de Scheme, puede eliminar el operador de asignación y aún tener un lenguaje completo de Turing. Sin embargo, en un idioma tan restringido, agregar una característica que se localizaría si se permitiera la asignación requeriría un cambio global al programa sin asignación.

Mi discusión ha simplificado algunos detalles, y debería leer el documento en sí para la cuenta completa.

Para responder a su otra pregunta: puede decir que Java es más expresivo que el ensamblado porque puede agregar una nueva clase a su programa Java y luego obtener los beneficios del polimorfismo haciendo que otras partes de su programa llamen a sus métodos sin modificación global. El manejo de excepciones es otro ejemplo en el que Java es más expresivo que el ensamblado: simplemente necesita escribir una sola throwdeclaración para transferir el control a la pila. En un nivel más elemental, también puede agregar una nueva casedeclaración cerca del comienzo de a switchy no tendrá que preocuparse por volver a calcular manualmente las compensaciones de salto.

Macneil
fuente
¡Muchas gracias! ¡Esto es exactamente lo que estaba buscando!
Casebash
6

Si entiendo su pregunta correctamente, no obstante, está buscando algo que sea relativamente medible y no solo una decisión subjetiva. Si es así, personalmente favorecería la cantidad de tiempo necesario para resolver cualquier problema en particular (promediado sobre todos los problemas y todos los programadores). En esta medida, es posible que deba considerar no solo el lenguaje en sí, sino también el marco / API utilizado con él. La sintaxis sucinta es un factor muy pequeño: uno mucho más importante es que la funcionalidad más comúnmente requerida es fácilmente accesible.

Si buscas algo más subjetivo, diría lo divertido que es . Los programadores tienden a ser personas que quieren que se resuelvan los problemas, por lo que un lenguaje de programación divertido para los programadores inevitablemente será el que resolverá la mayoría de los problemas. Esta medida tiene en cuenta que diferentes personas tienen diferentes preferencias sobre cómo usar las cosas, por lo que el "mejor" lenguaje de programación será el que resulte más atractivo para la gama más amplia de programadores. Sin embargo, es posible que deba considerar no solo el lenguaje de programación y la API aquí, sino también el entorno (IDE), que es, por supuesto, con lo que realmente interactúa el programador.

Timwi
fuente
Yo diría que medir el tiempo empleado también es subjetivo. ¿Qué programador se tomó el tiempo? Si prueba los tiempos de ambos idiomas con el mismo programador, ¿qué idioma conocía mejor? Hay formas estadísticas de lidiar con esto, pero una persona no puede hacerlo sola.
John Fisher
1
@John: El hecho de que algo solo pueda analizarse estadísticamente no significa que sea subjetivo.
David Thornley
@David: Ese no era realmente mi punto. El punto era que sin un estudio preexistente, el autor de la pregunta no podría comparar el "poder" de los idiomas que le importaban, dejándolo subjetivo cuando no se analiza estadísticamente en un grupo grande.
John Fisher
1

Definiría cuán poderoso es un lenguaje por lo productivo que puede ser con él. Mucha gente tiende a hablar sobre la productividad en términos de escribir código rápidamente, pero dado que la mayoría del ciclo de vida de un programa es mantenimiento, no desarrollo, una mejor medida es la facilidad con la que puede leer y depurar el código, especialmente cuando alguien lo ha escrito más. Los lenguajes más poderosos son los que son más fáciles de leer y mantener.

Mason Wheeler
fuente
2
La dificultad con esto es que conocer un idioma lo hace más fácil para quien lo conoce. Entonces, esta medida se vuelve subjetiva.
John Fisher
1

Necesita definir mejor su terminología.

La integridad de Turing no se trata de "poder" en el sentido en que probablemente te refieres. Más bien se trata de computabilidad; es decir, si un lenguaje dado puede expresar algún programa que pueda implementarse usando una máquina Turing. Resulta que casi todos los lenguajes de programación están completos.

Probablemente lo que busca es una medida de lo que se conoce como "expresividad" del lenguaje de programación. No estoy seguro de si existe tal medida, o si es así, si es útil. Básicamente, los diferentes lenguajes de programación son mejores para expresar soluciones a diferentes tipos de problemas.

EDITAR

Solo para explicarlo, los lenguajes de programación no tienen una propiedad conocida como "poder". Existe un concepto comúnmente conocido como "expresividad" o "poder expresivo" de un lenguaje de programación. La expresividad se debe en parte a lo fácil que es escribir programas concisos para abordar problemas particulares. Pero también hay una medida considerable de lo fácil que es leer y escribir los programas. Es algo así como "belleza". Lo sabré cuando lo vea, pero no me pidas que lo defina.

Simplemente comparar los recuentos de caracteres no te da una medida adecuada de expresividad. De lo contrario, podría hacer que un lenguaje sea más expresivo al comprimir el código fuente ... y eso no tiene sentido. De hecho, no conozco ninguna medida objetiva de expresividad, y sospecho firmemente que no existe ninguna. Lo que efectivamente hace que la característica sea inútil y bastante poco interesante.

Stephen C
fuente
1
Sé que la integridad de Turing se trata de computabilidad. Sabemos que existen medidas menores en la escala de computabilidad, como las máquinas de estados finitos. Pero no podemos utilizar la computabilidad para definir un nivel de potencia por encima de esto, como Turing completo es máximamente poderoso en términos de computabilidad
Casebash
@Casebash: aún no has dicho qué es "poder".
Stephen C
2
¡Eso es porque no lo sé y ese es el objetivo de esta pregunta!
Casebash el
Entonces, ¿cuál es el punto de tu respuesta? Debería haber sido un comentario.
reinierpost
@reinerpost: el objetivo de mi respuesta es explicar en detalle que la pregunta no tiene sentido y por qué. Básicamente, la pregunta es "Hay algo llamado 'poder expresivo': no ​​sé qué es, pero ¿podría decirme cómo medirlo?". Y el meollo de mi respuesta es que el "poder expresivo" es un concepto / propiedad mal definido, y DEFINITIVAMENTE no es medible / cuantificable. (Y es claramente una Respuesta y no un comentario. ¿Quizás simplemente no entendiste lo que estoy tratando de decir?)
Stephen C