¿Hay una medida objetiva de la complejidad de un lenguaje de programación en términos de sintaxis y semántica, no cuán complejo es el uso del lenguaje?Complejidad de los lenguajes de programación
He leído muchos comentarios subjetivos pero poco análisis riguroso.
Tenga una mirada en Denotational semantics y operational semantics:
semántica denotacional es una aproximación a la formalización de los significados de los lenguajes de programación mediante la construcción de los objetos matemáticos (llamados denotaciones) que describen los significados de las expresiones de las lenguas.
Los semántica operacional para un lenguaje de programación describe cómo un programa válido se interpreta como secuencias de pasos de cálculo. Estas secuencias son el significado del programa. En el contexto de los programas funcionales, el paso final en una secuencia de terminación devuelve el valor del programa. (En general, puede haber muchos valores de retorno para un solo programa, porque el programa podría ser no determinista, e incluso para un programa determinista puede haber muchas secuencias de cálculo ya que la semántica puede no especificar exactamente qué secuencia de operaciones llega a ese valor).
El complejo lenguaje que se debe usar es completamente subjetivo.
Por otro lado, las preguntas sobre qué tan compleja es la semántica del lenguaje se pueden responder, pero solo si se comparan con otros idiomas. Sin embargo, estos no son necesariamente útiles. Por ejemplo, le daría a Smalltalk una complejidad semántica de 1 y C++ una complejidad de 9. Sin embargo, apuesto a que el navegador en el que está leyendo esto está escrito en en C++, no en Smalltalk.
Si existe una medida tan objetiva, probablemente sea casi inútil evaluar la utilidad o el costo de utilizar un idioma determinado para un fin determinado. Te ayudaría a descartar espacios en blanco o brainfuck, pero eso se puede hacer con la misma facilidad sin gastar recursos en una medida tan objetiva: observando subjetivamente el código fuente y dándote cuenta de que nunca querrás trabajar seriamente con él.
La mayoría de los lenguajes van a tener muchos aspectos positivos y negativos que deberías sopesar con respecto al objetivo que intentas alcanzar y las condiciones que se deben cumplir.
No se olvide de INTERCAL. –
Estoy seguro que SOÍ necesitaba un comentario sobre el voto a favor. Gente, si no te gusta una respuesta, explica por qué. – eyelidlessness
La mejor medida que he visto de un idioma es la probabilidad de que una cadena aleatoria sea un programa válido. Perl es un idioma que ocupa un lugar destacado en esta escala, Ada ocupa un lugar bastante bajo.
Lo que significa esta métrica significa es otro problema por completo.
La jactancia orgullosa del editor de TECO era que cualquier cadena de caracteres cuando se trata como un comando haría algo. Esta es una de las muchas razones por las que no ve muchos usuarios de TECO en estos días. –
La razón para esto es si el primer (¿o uno de los primeros?) Tokens es __END__ y CUALQUIER COSA producida después de eso es un programa válido de Perl. Solo esto tiene a Perl a la cabeza para tener una porción de secuencias infinitas que son programas válidos. –
@Neil: Emacs comenzó su vida como un front-end TECO, por lo que vive en espíritu. –
No tengo claro si la complejidad es incluso un término bien definido cuando se aplica a un lenguaje de programación.
Si por "objetivo" que quiere decir "cuantitativa", que se puede pedir a preguntas tales como
¿Qué tan grande es una gramática no ambigua?
¿Qué tan grande es una gramática yacc en funcionamiento?
Dado que casi ningún idioma tiene una semántica formal, es difícil hacer estudios cuantitativos. Sin embargo, usted podría pedir
Excepto por curiosidad, no está claro para mí que esta pregunta valga la pena preguntar — es difícil imaginar respuestas útiles.
Puede agregar el número de cruces de AST requeridos y otras métricas de traducción. –
Como regla general , más dinámico y abstraído la sintaxis o la semántica o la aplicación son, cuanto más complejo es el idioma (no usar como ha afirmado).
Por lo tanto, Java es un lenguaje más complejo que C, porque:
Podría argumentar Python más simple que Java sobre esta base, porque es un modelo de objeto, aunque complejo, es simple en términos de reducción en una forma más simple. La facilidad con que una sintaxis dada puede ser traducida a una forma más simple desde una perspectiva de tiempo y cálculo también puede ser un ángulo.
un lenguaje como Lisp, por otro lado, algunos podrían argumentar es difíciles de usar pero muy simple. Lo mismo ocurre con cosas como Haskell.
se pudiera medir la complejidad en una de las siguientes maneras, pero no está completa:
Hay toneladas de formas. Puede medir la complejidad computacional del proceso de compilación para una sintaxis dada.
No todos estos ejemplos son ciertos. Algunos modelos de objetos son muy complejos, pero muy rápidos porque usan una base rápida. El yo puede ser un ejemplo.
Lenguaje de BNF es una medida aproximada - sólo por el gusto :-)
Unos pocos ejemplos,
Estos son agradables. ¿Hay alguna legible en alguna parte para Haskell? –
Kennedy, consulte este sitio http://www.hck.sk/users/peter/HaskellEx.htm –
Agregó Ada's. Siéntase libre de retirarlo si no quiere que su lista crezca, Nick. –
Me encanta Project Euler por evaluar esto. :)
Las dos cosas más fáciles de ver son las cantidades de símbolos definidos y palabras clave/palabras reservadas, y la cantidad de producciones en su BNF.
Otra cosa que podría observar, para los idiomas que los tienen, es el tamaño relativo de sus documentos de estándares. Algunos argumentarían que no todos los documentos estándar están escritos en el mismo nivel, sin embargo.
Creo que si nos fijamos en el área de la prueba de corrección, encontrará un análisis más detallado de la complejidad semántica. Los sistemas como CSP (y, en menor medida, Lambda Calculus) están diseñados para ser tratables mediante análisis. Cuanto más cerca está un lenguaje de ser una expresión del sistema formal subyacente, más simple es desde un punto de vista semántico.
El contraejemplo sería algo así como el lenguaje de programación C. No es posible averiguar qué hace realmente un programa C, sin saber qué sistema operativo y hardware se ejecutará.
Como otros usuarios publicaron, las palabras clave son una medida objetiva de cuán complejo puede ser un lenguaje de programación. La gramática/sintaxis describiría cuán compleja puede ser la estructura del código (combinaciones de palabras clave permitidas). Existen métricas de código relacionadas con la calidad del software para medir qué tan complejo es un fragmento de código.
La complejidad semántica me parece más difícil de medir. Está relacionado con el poder expresivo (cuanto mayor sea el nivel del lenguaje de programación, mayor será el poder expresivo). No veo el punto de tratar de comparar diferentes soluciones implementadas en diferentes idiomas para medir su poder expresivo (es decir, utilizando las implementaciones de problemas del proyecto de Euler = soluciones). El problema en sí y cada paradigma del lenguaje de programación pueden sesgar la comparación.
En el caso de lenguajes de programación de alto nivel, supongo que la cantidad de implementaciones posibles para un problema específico (desde un punto de vista abstracto) es una buena medida de la complejidad semántica.
En el caso de lenguajes de programación de bajo nivel, podría ser interesante ver cómo los lenguajes de especificación generan código (encontrar una implementación = solución para el problema dado). Sin embargo, debido a la abstracción limitada, esta medida parece estar estrechamente relacionada con las métricas del código de calidad del software.
Como puede ver, la abstracción y la complejidad semántica son más difíciles de automatizar (generar una implementación = solución dada la especificación). Ahí es donde entra el conocimiento, la inteligencia y la psicología del programador (AI no ha llegado a este punto).
Primero debe definir la 'complejidad del idioma'. –
Supongo que la complejidad de la implementación en lugar de utilizar –
Escribí un Q/A en cstheory SE sobre este mismo tema (si lo leo bien). Busque el cociente de Kolmogorov para medir la elegancia o la concisión del lenguaje de programación, la capacidad que tiene un lenguaje de programación para simplificar el complejo. – theDoctor