it-swarm-es.com

Medida de potencia distinta a la completitud de Turing

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

La completitud de Turing significa que un lenguaje es lo más poderoso posible en lo que puede generar (lo que básicamente significa que puede hacer cualquier cosa que no esté basada en el tiempo en el mundo real). Entonces, si queremos definir una medida más fuerte de poder, 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?

18
Casebash

La noción que estás 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, digamos, el programa A en el idioma X y el programa B en el idioma Y, y si realiza un cambio local a A, eso requiere un cambio global a B , entonces X es más expresivo que Y.

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

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

Para responder a su otra pregunta: puede decir que Java es más expresivo que Assembly porque puede agregar una nueva clase a su programa Java, y luego obtener el beneficios del polimorfismo al hacer que otras partes de su programa llamen a sus métodos sin modificación global. El manejo de excepciones es otro ejemplo donde Java es más expresivo que Assembly: simplemente necesita escribir un solo throw para transferir el control a la pila. En un nivel más elemental, también puede agregar una nueva instrucción case cerca del comienzo de un switch y no tendrá que preocuparse por volver a calcular cualquier salto compensado a mano.

25
Macneil

Si entiendo correctamente su pregunta, no obstante, está buscando algo que sea relativamente mensurable 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 que se usa 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 estás buscando algo más subjetivo, diría qué divertido es. Los programadores tienden a ser personas que quieren que se resuelvan los problemas, por lo que un lenguaje de programación que sea divertido de usar para los programadores será inevitablemente el que resolverá la mayoría de los problemas. Esta medida toma 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 más amplia gama 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 el programador realmente interactúa.

6
Timwi

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 cualquier programa que pueda implementarse usando una máquina de Turing. Resulta que casi todos los lenguajes de programación son Turing completo.

Lo que probablemente esté buscando 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 existe, si es útil. Fundamentalmente, diferentes lenguajes de programación son mejores para expresar soluciones a diferentes tipos de problemas.

EDITAR

Para explicarlo claramente, 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 trata en parte de lo fácil que es escribir programas sucintos para abordar problemas particulares. Pero también existe una medida considerable de lo fácil que es leer y escribir los programas. Es una especie de "belleza". Lo sabré cuando lo vea, pero no me pida que lo defina.

La simple comparación de los recuentos de caracteres no le da una medida adecuada de expresividad. De lo contrario, podría hacer que un lenguaje sea más expresivo comprimiendo el código fuente ... y eso es una tontería. De hecho, no conozco ninguna medida objetiva de expresividad, y sospecho firmemente que no existe. Lo que efectivamente hace que la característica sea inútil y poco interesante.

1
Stephen C

Definiría cuán poderoso es un lenguaje por lo productivo que puedes ser con él. Mucha gente tiende a hablar de productividad en términos de escribir código rápidamente, pero dado que la mayor parte 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 está escrito por alguien. más. Los lenguajes más potentes son los más fáciles de leer y mantener.

1
Mason Wheeler