Estructura genérica de datos Descripción Idioma

Question

Me pregunto si existe algún lenguaje declarativo para describir arbitrariamente el formato y la semántica de una estructura de datos, que se puede compilar a una implementación específica de esa estructura en cualquiera de los idiomas de destino. Es decir, algo así como un genérico data definition language pero orientado a describir estructuras de datos arbitrarios como vectores, listas, árboles, etc., y la semántica de las operaciones en esas estructuras. Lo pregunto porque tenía una idea para una implementación factible de este concepto, y me pregunto si vale la pena y, en consecuencia, si ya se hizo antes.

Otra pregunta un poco más abstracta: ¿hay alguna diferencia real entre la especificación normativa de una estructura de datos (lo que hace) y su implementación (cómo lo hace)? Más específicamente, debe separar implementaciones de los mismos requisitos considerarse diferentes estructuras?

Answer 1

Si le apetece, una combinación de XML con XSLT podría describir una estructura de datos y proporcionar una definición coincidente en prácticamente cualquier idioma si lo desea. Nunca intenté demostrarlo formalmente, pero mi primera suposición sería que las expresiones S son un superconjunto de XML (diferencias sintácticas de módulo).

Al menos en teoría, sí hay (o al menos puede haber) diferencias entre una descripción de lo que hace una estructura de datos y cómo lo hace. Para un ejemplo obvio, podría describir una asignación genérica de claves a valores, que podría usar una implementación basada en tablas hash, listas de omisión, árboles de búsqueda binarios, etc. Se trata principalmente de describirlo a un nivel suficientemente alto de abstracción para permitir diferencias en la implementación. Si incluye demasiados requisitos (complejidad, pedidos, etc.), puede descartar rápidamente muchas implementaciones.

Answer 2

Existen enfoques para ese tipo de cosas en las lógicas dinámicas, que intentan capturar la semántica de los programas. Sin embargo, el significado en términos de la lógica dinámica es en términos de condiciones previas y posteriores y es independiente de la implementación real de la lista.

Estas estructuras de datos están intrínsecamente ligadas a la implementación, ya que la única diferencia entre una lista vinculada y una matriz es específicamente cómo se presenta en la memoria.

Para esto, hay un lenguaje de definición de datos genérico --- cualquier lenguaje de programación de alto nivel - C, C++, java - que especifica esto. Cualquiera de ellos es tan genérico como el otro, ya que dentro de este contexto cualquiera de ellos podría compilarse para el otro.

Answer 3

Puede que le interesen los idiomas de serialización de especificación/datos de mensajería, como los Buffers de Protocolo de Google y ASN.1. Es un sesgo ligeramente diferente de lo que está buscando, pero en la misma línea.

Ambas son formas de declarar mensajes genéricos para las comunicaciones. El protocolo almacena las especificaciones de mensaje "compilar" a diferentes idiomas, pero el protocolo central es coherente. ASN.1 tiene múltiples utilidades de compilación diferentes, así como diferentes representaciones de protocolo que permanecen lógicamente consistentes con diferentes implementaciones literales. Mire XER, PER contra BER por ejemplo.

Me encantaría un lenguaje de especificación que simplemente se centrara en el diseño binario empaquetado simple contra una estructura de memoria lógica. Puede ser que las estructuras simples de C sean la forma común más simple de expresar esto. Esperaba que ASN.1 tuviera alguna forma de llegar a eso, pero después de mirarlo un poco, ASN.1 PER está cerca, pero no del todo.

Editar: Apache Thrift y Capn' Proto también pueden ser interesantes.