Proceedings of the ACM on Programming Languages, 6(OOPSLA2), 758-785

MINIKANREN es un lenguaje embebido ligero para programación lógica y relacional. Muchas de sus funcionalidades proceden de una estrategia de búsqueda distintiva, conocida como búsqueda intercalada. Sin embargo, con la búsqueda intercalada, las formas convencionales de razonar sobre la complejidad y el rendimiento de los programas lógicos se vuelven irrelevantes. Identificamos un componente clave importante, la programación, que es la responsable de que el razonamiento para MINIKANREN sea tan diferente, y presentamos una técnica semiautomática para calcular el impacto de la programación mediante la ejecución simbólica para una clase bastante amplia de programas.

49th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2012)

Scientific and Technical Journal of Information Technologies, Mechanics and Optics

Syrcose'21

TFPIE-2021

Distinguished Paper Award en el OOPSLA'21

OOPSLA

Programming and Computer Software Journal

Presentamos una nueva estrategia justa de evaluación de conjunciones para el lenguaje de programación relacional miniKanren. A diferencia de la conjunción original con un sesgo hacia la izquierda, nuestro enfoque controla el orden de ejecución de los conjuntos en función de las propiedades intrínsecas de las definiciones de las relaciones. Presentamos tanto el estudio formal de la equidad de la conjunción como la evaluación práctica, que demuestra la mejora esencial tanto en términos de rendimiento como de convergencia.

SEIM-2021

ICPP-2021

Presentamos un estudio formal de la semántica del lenguaje de programación relacional MINIKANREN. En primer lugar, formulamos una semántica denotacional que corresponde al modelo mínimo de Herbrand para programas lógicos definidos. En segundo lugar, presentamos una semántica operacional que modela la intercalación, la característica distintiva de la implementación de MINIKANREN, y demostramos su solidez y completitud con respecto a la semántica denotacional. Nuestro desarrollo permite una especificación en COQ, de la que puede extraerse un intérprete de referencia. A partir de nuestro resultado principal, también obtenemos una semántica certificada (y un intérprete de referencia) para la resolución SLD con corte y demostramos su solidez.

Presentamos un enfoque completamente declarativo para sintetizar implementaciones de construcciones de concordancia de patrones basadas en la aplicación de la programación relacional, una forma específica de programación lógica de restricciones. Nuestro enfoque se basa en representaciones relacionales tanto de la semántica de alto nivel de la concordancia de patrones como de la semántica de un lenguaje de implementación de nivel intermedio. Esta elección hace que nuestro enfoque sea, en principio, muy escalable, ya que solo tenemos que modificar la semántica de alto nivel para sintetizar la implementación de una nueva función de coincidencia de patrones. Tras la evaluación de un conjunto de pequeñas muestras, tomadas parcialmente de la literatura, podemos afirmar que nuestro marco de trabajo puede sintetizar rápidamente implementaciones óptimas. Sin embargo, tras evaluar en profundidad el estrés en una serie de puntos de referencia artificiales, hemos detectado la necesidad de realizar mejoras futuras.

Las consultas de rutas sin contexto (CFPQ) amplían las consultas de rutas regulares (RPQ) al permitir el uso de gramáticas sin contexto como restricciones para las rutas. Se están desarrollando algoritmos para CFPQ, pero J. Kuijpers et al. han llegado recientemente a la conclusión de que los algoritmos existentes no son lo suficientemente eficaces como para utilizarlos en aplicaciones reales, de modo que el desarrollo de nuevos algoritmos para CFPQ está justificado. En este trabajo, ofrecemos un nuevo algoritmo CFPQ basado en operaciones de álgebra lineal como el producto de Kronecker y el cierre transitivo y maneja gramáticas presentadas como máquinas de estados recursivos. Así, el algoritmo propuesto puede implementarse utilizando bibliotecas de alto rendimiento y hardware paralelo moderno. Además, evita el crecimiento gramatical, lo que ofrece la posibilidad de optimizar las consultas.

ADBIS 2020. Advances in Databases and Information Systems. Lecture Notes in Computer Science.

Las expresiones regulares se utilizan en las rutas de propiedades SPARQL para consultar gráficos RDF. Sin embargo, las expresiones regulares solo pueden definir la clase más limitada de lenguajes, es decir, los llamados «lenguajes regulares». Los lenguajes sin contexto son una clase más amplia que incluye todos los lenguajes regulares. No existen expresiones sin contexto para definirlos, por lo que es necesario escribir gramáticas. Proponemos una extensión de las expresiones regulares, llamadas «expresiones recursivas», para complementar la definición de un subconjunto de lenguajes sin contexto. El objetivo de nuestro trabajo es, por tanto, proporcionar operadores sencillos que permitan definir lenguajes lo más parecidos posible a los lenguajes sin contexto.

ADBIS, TPDL and EDA 2020 Common Workshops and Doctoral Consortium

The European Conference on Object-Oriented Programming (ECOOP)

La consulta de rutas sin contexto (CFPQ) se suele utilizar para el análisis de datos estructurados en gráficos en distintos ámbitos. Es vital desarrollar algoritmos altamente eficientes para CFPQ, ya que el tamaño de los datos de entrada suele ser grande. Mostramos cómo reducir la evaluación CFPQ a la resolución de sistemas de ecuaciones matriciales sobre R, un problema para el que existen soluciones de alto rendimiento. Además, demostramos la aplicabilidad de nuestro enfoque al análisis de datos del mundo real.

Actas del 2020 ACM SIGMOD International Conference on Management of Data

El objetivo de este trabajo es presentar la modificación del algoritmo de Valiant, cuya principal ventaja es que puede dividir la tabla de análisis sintáctico en capas sucesivamente calculadas de submatrices disjuntas en las que cada submatriz de la capa puede procesarse de forma independiente. Además, nuestro planteamiento se adapta fácilmente al problema de emparejamiento de cadenas.

Actas del Institute for System Programming

Un estudio reciente ha demostrado que la aplicabilidad de los algoritmos de consulta de rutas sin contexto (CFPQ) con semántica de consulta relacional integrados con bases de datos de gráficos es limitada debido al bajo rendimiento y al elevado consumo de memoria de las soluciones existentes. En este trabajo, implementamos un algoritmo CFPQ basado en matrices utilizando bibliotecas apropiadas de alto rendimiento para álgebra lineal y lo integramos con la base de datos de gráficos RedisGraph. Además, introducimos un nuevo algoritmo CFPQ con semántica de consulta con una única ruta que nos permite extraer una ruta encontrada para cada par de nodos. Por último, presentamos la evaluación de nuestros algoritmos para ambas semánticas, lo que demuestra que la implementación de CFPQ basada en matrices para la base de datos Redis-Graph es lo suficientemente eficaz para analizar datos del mundo real.

GRADES-NDA'20: Actas del 3rd Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)

41st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2020)

41st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2020)

Aunque la utilización de la GPU permite acelerar los cálculos en órdenes de magnitud, la gestión de la memoria sigue siendo un cuello de botella, por lo que a menudo es complicado alcanzar el rendimiento deseado; y de ahí que se empleen diferentes optimizaciones de memoria para utilizarla de forma más eficaz. Proponemos un enfoque que automatiza la gestión de la memoria utilizando la evaluación parcial, una técnica de transformación de programas que permite precalcular, optimizar e incrustar en el código los accesos a datos, lo que ahorra transacciones de memoria. Tras evaluar de forma empírica el enfoque, vemos que el programa transformado podría ser hasta 8 veces más eficiente que el original en el caso de la implementación del algoritmo de correspondencia de patrones de cadenas sencillas en CUDA C.

PPoPP '20: Actas del 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Proceedings of ISP RAS

Se sabe que la consulta de rutas con gramáticas conjuntivas no se puede decidir. Existe un algoritmo para la consulta de rutas con gramáticas conjuntivas lineales que proporciona una sobreaproximación del resultado, pero no existe ningún algoritmo para gramáticas conjuntivas arbitrarias. Proponemos el primer algoritmo para la consulta de rutas con gramáticas conjuntivas arbitrarias, que está basado en matrices y nos permite aplicar de forma eficiente técnicas de computación GPGPU y otras optimizaciones para operaciones matriciales.

Programming and Computer Software

BMC Bioinformatics

Actas del 19th International Conference on Formal Methods in Computer-Aided Design, FMCAD 2019

33rd European Conference on Object-Oriented Programming (ECOOP 2019)

El algoritmo basado en la multiplicación de matrices propuesto recientemente para la consulta de rutas sin contexto (CFPQ) descarga las partes más críticas para el rendimiento en la multiplicación de matrices booleanas. Así, es posible alcanzar un rendimiento alto de CFPQ con hardware y software paralelos modernos. En este artículo, presentamos los resultados de comparar de forma empírica el rendimiento de diferentes implementaciones de este algoritmo tanto en datos del mundo real como en datos sintéticos para los peores casos.

Actas del 2nd Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)

El teorema de Bar-Hillel afirma que los lenguajes sin contexto se cierran por intersección con un conjunto regular. Este teorema tiene una demostración constructiva y, por tanto, da una justificación formal de la corrección de los algoritmos para las aplicaciones mencionadas anteriormente. La mecanización del teorema de Bar-Hillel, por tanto, es tanto un resultado fundamental de la teoría del lenguaje formal como una base para la implementación certificada de los algoritmos para aplicaciones. En este trabajo, presentamos la mecanización del teorema de Bar-Hillel en Coq.

Logic, Language, Information, and Computation

Proponemos una forma de combinar gramáticas formales y redes neuronales artificiales para el procesamiento de secuencias biológicas. Las gramáticas formales codifican la estructura secundaria de la secuencia y las redes neuronales se ocupan de las mutaciones y el ruido. A diferencia de la forma clásica, cuando se utilizan gramáticas probabilísticas para el modelado de estructuras secundarias, proponemos utilizar gramáticas arbitrarias (no probabilísticas), lo que simplifica la creación de gramáticas. En lugar de modelar la estructura de toda la secuencia, creamos una gramática que solo describe características de la estructura secundaria. A continuación, utilizamos el análisis sintáctico basado en matrices para extraer características: el hecho de que alguna subcadena pueda derivarse de algún elemento no terminal es una característica. A continuación, utilizamos una red neuronal densa para procesar las características.

Actas del 12th International Joint Conference on Biomedical Engineering Systems and Technologies - BIOINFORMATICS

Uno de los problemas de analizar datos de gráficos es buscar rutas específicas. Estas consultas suelen realizarse mediante una gramática formal que describe el etiquetado de aristas permitido para las rutas. Se dice que una consulta de ruta se calcula utilizando la semántica de consulta relacional si se evalúa a triple (A,v1,v2), por lo que existe una ruta de v1 a v2 de forma que las etiquetas de las aristas de esta ruta forman una cadena derivable del elemento no terminal A. Nos centramos en los lenguajes booleanos que utilizan gramáticas booleanas para describir el etiquetado de las rutas. Aunque sabemos que la consulta de rutas utilizando semántica de consulta relacional y gramáticas booleanas no se puede decidir, en este trabajo proponemos un algoritmo de consulta de rutas en gráficos acíclicos que utiliza semántica de consulta relacional y gramáticas booleanas y aproxima la solución exacta. Para lograr un mejor rendimiento en comparación con el algoritmo sencillo, las clases de gráficos se limitaron a gráficos acíclicos.

Actas del Institute for System Programming

Actas del 2019 miniKanren and Relational Programming Workshop

SEIM-19

Actas preliminares del 13 rd Spring/Summer Young Researchers’ Colloquium on Software Engineering (SYRCoSE 2019), 29-31 de mayo de 2019 – Saratov, Federación Rusa

Actas del 2019 miniKanren and Relational Programming Workshop

Actas del 2019 miniKanren and Relational Programming Workshop

Programming and Computer Software

Abstract ampliado en TyDe 2018 (en ICFP).

La integración transparente de un lenguaje específico del dominio para la especificación de consultas de rutas sin contexto (CFPQ) en un lenguaje de programación general, así como la comprobación estática de errores en las consultas, pueden simplificar mucho el desarrollo de aplicaciones que utilicen CFPQ. Se puede utilizar LINQ y ORM para la integración, pero tienen problemas de flexibilidad: la descomposición de consultas y la reutilización de subconsultas son un reto. Es posible que adaptar la técnica de combinadores de analizadores sintácticos para la consulta de rutas resuelva estos problemas. Los combinadores de analizadores sintácticos convencionales procesan entradas lineales y la biblioteca Trails es la única que se sabe que aplica esta técnica para la consulta de rutas. Demostramos que es posible crear combinadores de analizadores sintácticos generales para CFPQ que admitan gramáticas sin contexto arbitrarias y gráfcos de entrada arbitrarios. Implementamos una biblioteca de estos combinadores de analizadores sintácticos y demostramos que es aplicable a tareas realistas.

Actas del 9th ACM SIGPLAN International Symposium on Scala

NTV SPbSTU

GRADES-NDA '18 Actas del 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)

18th International Symposium on Trends in Functional Programming

Actas del 20th International Symposium on Principles and Practice of Declarative Programming

Actas del ML/OCAML 2016

40th ACM/IEEE International Conference on Software Engineering, ICSE 2018

NTV SPbSTU

Existen varias soluciones para CFPQ, pero la forma de proporcionar una representación estructural del resultado de la consulta que resulte práctica para el procesamiento y la depuración de respuestas sigue siendo un problema abierto. En este trabajo proponemos una técnica de análisis sintáctico de gráficos que permite construir dicha representación con respecto a una gramática dada en tiempo y espacio polinómicos para una gramática sin contexto y un gráfico arbitrarios. El algoritmo propuesto se basa en el algoritmo de análisis sintáctico LL generalizado, mientras que las soluciones anteriores se basan principalmente en los algoritmos CYK o Earley, lo que reduce la complejidad temporal en algunos casos.

Actas del 13th Central & Eastern European Software Engineering Conference in Russia (CEE-SECR '17)

Proceedings of ISP RAS

arXiv

The European Conference on Object-Oriented Programming (ECOOP)

Actas del 2017 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation

St. Petersburg State Polytechnical University Journal. Computer Science. Telecommunications and Control Systems

Izvestia vuzov. North Caucasus Region. Technical Sciences, 2017, No. 4, páginas 5-12

Actas del Institute for System Programming

arXiv

Presentamos una técnica de análisis sintáctico de un conjunto regular de cadenas de entrada. Este problema es relevante para el análisis de lenguajes embebidos en cadenas cuando un programa anfitrión genera cláusulas de lenguaje embebido durante la ejecución. Nuestra técnica se basa en una generalización del algoritmo RNGLR, que, de forma inherente, nos permite construir una representación finita del bosque de análisis sintáctico para un conjunto regularmente aproximado de cadenas de entrada. Esta representación puede utilizarse posteriormente para análisis semánticos y transformaciones en el contexto de la reingeniería, el mantenimiento del código, la comprensión de programas, etc. El enfoque en cuestión implementa el análisis sintáctico relajado: las cadenas no reconocidas en el conjunto de aproximación se ignoran sin detección de errores.

Perspectives of System Informatics

Systems and Means of Informatics

META 2016 Fifth International Valentin Turchin Workshop on Metacomputation

SEIM-16

NTV SPbSTU 4 (224)

Systems and Means of Informatics

Science of Computer Programming

Actas del 11th Central & Eastern European Software Engineering Conference in Russia

Actas del 9th International Andrei Ershov Memorial Conference on Perspectives of System Informatics

Actas del 10th Central and Eastern European Software Engineering Conference in Russia 2014

Actas del 10th Central and Eastern European Software Engineering Conference in Russia

Actas del 9th Central & Eastern European Software Engineering Conference in Russia

Workshop on ML

Actas del 2010 East-West Design & Test Symposium

Actas del 6th International Andrei Ershov Memorial Conference on Perspectives of System Informatics

Workshop on Multiparadigm Programming with Object-Oriented Languages

System Informatics

System Programming

System Programming

Actas del European Conference on Software Maintenance and Reengineering, CSMR 995802, pp. 177-185

Actas del 4th International Andrei Ershov Memorial Conference on Perspectives of System Informatics

Automated Reengeneering of Programs, Saint Petersburg