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

MINIKANREN은 논리 및 관계형 프로그래밍을 위한 경량 임베디드 언어입니다.많은 유용한 기능은 인터리빙 검색이라는 독특한 검색 전략에서 비롯됩니다.그러나 인터리빙 검색을 사용하면 논리 프로그램의 복잡성과 성능에 대한 기존의 추론 방식이 무의미해집니다.우리는 MINIKANREN에 대한 추론을 매우 상이하게 만드는 중요한 핵심 구성 요소인 스케줄링을 식별하고, 합리적으로 폭넓은 프로그램 클래스에 대한 심볼 실행을 통해 스케줄링 영향을 추정하는 반자동 기법을 제시합니다.

49회 ACM SIGPLAN 프로그래밍 언어의 원리에 관한 심포지엄 (POPL 2012)

Scientific and Technical Journal of Information Technologies, Mechanics and Optics

Syrcose'21

TFPIE-2021

OOPSLA'21 우수 논문상

OOPSLA

Programming and Computer Software Journal

우리는 관계형 프로그래밍 언어 miniKanren에 대한 새롭고 공정한 접속사 평가 전략을 제시합니다.원래의 왼쪽 편향 접속사와 달리 우리의 접근 방식은 관계 정의의 고유한 속성을 기반으로 접속 실행 순서를 제어합니다.우리는 접속사 공정성에 대한 공식적인 연구와 실제 평가를 모두 제시하며 성능과 수렴 측면에서 본질적인 개선을 보여줍니다.

SEIM-2021

ICPP-2021

우리는 관계형 프로그래밍 언어 MINIKANREN의 의미론에 대한 공식적인 연구를 제시합니다.먼저 명확한 논리 프로그램에 대한 최소 Herbrand 모델에 해당하는 표기 의미론을 공식화합니다.둘째, MINIKANREN 구현의 특징인 인터리빙을 모델링하는 운용 의미론을 제시하고, 표기 의미론과 관련한 그 건전성과 완전성을 입증합니다.우리의 개발 내용은 참조 인터프리터를 추출할 수 있는 COQ 사양에 의해 뒷받침됩니다.또한 얻은 주요 결과로부터 잘라낸 SLD 해상도에 대한 인증된 의미론(및 참조 인터프리터)을 도출하고 그 건전성을 증명합니다.

제약 논리 프로그래밍의 특정 형태인 관계형 프로그래밍의 적용을 기반으로 패턴 일치 구조 구현을 합성하는 완전한 선언적 접근 방식을 제시합니다.우리의 접근 방식은 패턴 일치의 상위 수준 의미론과 중간 수준 구현 언어의 의미론 모두의 관계형 표현을 기반으로 합니다.패턴 일치 새 기능의 구현을 합성하기 위해 상위 수준의 의미론을 수정하기만 하면 되므로 이 선택은 원칙적으로 우리의 접근 방식을 매우 확장 가능하게 만듭니다.기존 문헌에서 부분적으로 가져온 일련의 작은 샘플들에 대해 평가한 결과, 우리의 프레임워크가 최적의 구현을 신속하게 합성할 수 있는 것으로 나타났습니다.그러나 여러 인공 벤치마크에 대한 심층 스트레스 평가에서는 향후 개선이 필요함을 보여주었습니다.

컨텍스트 자유 경로 쿼리(CFPQ)는 컨텍스트 프리 문법을 경로에 대한 제약 조건으로 사용할 수 있도록 함으로써 정규 경로 쿼리(RPQ)를 확장합니다.CFPQ를 위한 알고리즘이 활발히 개발되고 있지만 J. Kuijpers 등은 최근에 기존 알고리즘이 실제 응용에 사용하기에 성능이 충분하지 않다는 결론을 내렸습니다.따라서 CFPQ를 위한 새로운 알고리즘의 개발 필요성이 대두됩니다.본 논문에서는 Kronecker 곱과 전이적 폐쇄와 같은 선형 대수 연산을 기반으로 하는 새로운 CFPQ 알고리즘을 제공하고 재귀적 상태 머신으로 표현되는 문법을 처리합니다.따라서 제안된 알고리즘은 고성능 라이브러리와 최신 병렬 하드웨어를 사용하여 구현할 수 있습니다.또한 쿼리 최적화 가능성을 제공하는 문법 증가를 방지합니다.

ADBIS 2020. Advances in Databases and Information Systems. 컴퓨터 과학 강의 노트.

정규식은 SPARQL 속성 경로에서 RDF 그래프를 쿼리하는 데 사용됩니다.그러나 정규식은 정규 언어라고 하는 가장 제한된 언어 클래스만 정의할 수 있습니다.컨텍스트 자유 언어는 모든 정규 언어를 포함하는 더 넓은 클래스입니다.이를 정의하는 컨텍스트 자유 표현이 없으므로 문법을 작성해야 합니다.컨텍스트 자유 언어의 하위 집합 정의를 지원하기 위해 재귀 표현식이라고 하는 정규 표현식의 확장을 제안합니다.따라서 연구 목표는 가능한 한 컨텍스트 자유 언어에 가까운 언어 정의를 허용하는 간단한 연산자를 제공하는 것입니다.

ADBIS, TPDL 및 EDA 2020 공통 워크숍 및 박사 컨소시엄

The European Conference on Object-Oriented Programming (ECOOP)

컨텍스트 자유 경로 쿼리(CFPQ)는 다양한 영역에서 그래프 구조의 데이터 분석에 널리 사용됩니다.일반적으로 입력 데이터의 크기가 크기 때문에 CFPQ를 위한 고효율 알고리즘을 개발하는 것이 중요합니다.고성능 솔루션이 존재하는 문제인 R에 대한 행렬 방정식 시스템을 해결하기 위해 CFPQ 평가를 단순화하는 방법을 보여줍니다.또한 실제 데이터 분석에 우리의 접근 방식이 얼마나 적용 가능한지 보여줍니다.

2020 ACM SIGMOD 데이터 관리 국제 컨퍼런스 논문집

이 논문은 Valiant의 알고리즘 수정을 제시하는 것을 목표로 합니다. 주요 이점은 레이어의 각 부분 행렬이 독립적으로 처리될 수 있는 분리된 부분 행렬의 연속적으로 계산된 레이어로 구문 분석 테이블을 분할할 수 있다는 것입니다.또한 이 접근 방식은 문자열 일치 문제에 맞게 쉽게 수정됩니다.

Institute for System Programming 논문집

최근 연구에 따르면 그래프 데이터베이스와 관계형 쿼리 의미론을 통합한 컨텍스트 자유 경로 쿼리(CFPQ) 알고리즘은 기존 솔루션의 낮은 성능과 높은 메모리 소비로 인해 적용 가능성이 제한적입니다.이 연구에서는 선형대수학에 적합한 고성능 라이브러리를 사용하여 행렬 기반 CFPQ 알고리즘을 구현하고 이를 RedisGraph 그래프 데이터베이스와 통합합니다.또한 각 노드 쌍에 대해 하나의 발견된 경로를 추출할 수 있는 단일 경로 쿼리 의미론을 사용하는 새로운 CFPQ 알고리즘을 도입합니다.마지막으로, Redis-Graph 데이터베이스에 대한 행렬 기반 CFPQ 구현이 실제 데이터 분석에 충분한 성능을 발휘한다는 것을 보여주는 두 의미론에 대한 알고리즘 평가를 제공합니다.

GRADES-NDA'20: 그래프 데이터 관리 경험 및 시스템(GRADES) 및 네트워크 데이터 분석(NDA)에 관한 3회 공동 국제 워크숍 논문집

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

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

GPU 활용을 통해 계산 속도를 수십 배로 높일 수 있지만 메모리 관리는 여전히 병목 현상으로 남아 있어 원하는 성능을 얻는 데 어려움을 겪는 경우가 많습니다.따라서 메모리를 보다 효과적으로 사용하기 위해 다양한 메모리 최적화가 활용됩니다.데이터 액세스를 사전 계산, 최적화 및 코드에 포함시켜 메모리 트랜잭션을 절약할 수 있는 프로그램 변환 기법인 부분 평가를 활용하여 메모리 관리를 자동화하는 접근 방식을 제안합니다.우리의 접근 방식에 대한 경험적 평가에 따르면 CUDA C 순진한 문자열 패턴 일치 알고리즘 구현의 경우 변환된 프로그램이 원래 프로그램보다 최대 8배 효율적일 수 있음을 보여줍니다.

PPoPP '20: 병렬 프로그래밍의 원리 및 실행에 관한 25회 ACM SIGPLAN 심포지엄 논문집

ISP RAS 의회록

결합 문법을 사용한 경로 쿼리는 결정 불가능한 것으로 알려져 있습니다.결과의 과대 근사치를 제공하는 선형 결합 문법을 사용한 경로 쿼리 알고리즘이 있지만 임의의 결합 문법을 위한 알고리즘은 없습니다.우리는 임의의 결합 문법을 사용한 경로 쿼리에 최초의 알고리즘을 제안합니다.제안된 알고리즘은 행렬 기반이며 GPGPU 컴퓨팅 기술과 행렬 연산에 대한 기타 최적화를 효율적으로 적용할 수 있습니다.

Programming and Computer Software

BMC Bioinformatics

FMCAD 2019, CAD(Computer-Aided Design)의 형식적 방법에 관한 19회 국제 컨퍼런스 논문집

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

컨텍스트 자유 경로 쿼리(CFPQ)를 위해 최근에 제안된 행렬 곱셈 기반 알고리즘은 성능에 가장 중요한 부분을 부울 행렬 곱셈으로 오프로드시킵니다.따라서 최신 병렬 하드웨어와 소프트웨어를 통해 CFPQ의 고성능을 달성할 수 있습니다.이 논문에서는 최악의 경우에 대해 실제 데이터와 합성 데이터 모두에서 이 알고리즘의 다양한 구현에 대한 경험적 성능을 비교하고 그 결과를 제공합니다.

그래프 데이터 관리 경험 및 시스템(GRADES) 및 네트워크 데이터 분석(NDA)에 관한 2회 공동 국제 워크숍 논문집

Bar-Hillel 정리는 컨텍스트 자유 언어가 정규 집합과의 교차점에서 닫혀 있다고 말합니다.이 정리는 건설적인 증명을 가지고 있으며, 따라서 위에서 언급한 응용에 대해 알고리즘의 정확성에 대한 형식적 정당성을 제공합니다.따라서 Bar-Hillel 정리의 기계화는 형식 언어 이론의 근본적인 결과이자 응용 알고리즘의 인증된 구현을 위한 기초입니다.이 연구에서는 Coq의 Bar-Hillel 정리에 대한 기계화된 증명을 제시합니다.

Logic, Language, Information, and Computation

우리는 생물학적 서열 처리를 위해 형식 문법과 인공 신경망을 결합하는 방법을 제안합니다.형식 문법은 서열의 2차 구조를 인코딩하고 신경망은 돌연변이와 노이즈를 처리합니다.고전적인 방식과 달리 확률적 문법이 2차 구조 모델링에 사용될 때는 문법 생성을 단순화하는 임의의(확률적이지 않은) 문법을 사용할 것을 제안합니다.전체 시퀀스의 구조를 모델링하는 대신 이차 구조의 특성만 설명하는 문법을 만듭니다.그런 다음 행렬 기반 구문 분석을 사용하여 특성을 추출합니다. 일부 하위 문자열이 일부 비터미널에서 파생될 수 있다는 사실도 하나의 특성입니다.그런 다음 조밀한 신경망을 사용하여 특성을 처리합니다.

12회 생체의학 공학 시스템 및 기술에 관한 국제 공동 컨퍼런스 - BIOINFORMATICS 논문집

그래프 데이터 분석이 가진 문제 중 하나는 특정 경로를 쿼리한다는 것입니다.이러한 쿼리는 일반적으로 경로의 허용된 에지 라벨링을 설명하는 형식적 문법을 통해 수행됩니다.경로 쿼리는 삼중(A,v1,v2)으로 평가되는 경우 v1에서 v2까지의 경로가 있고 이 경로의 가장자리에 있는 레이블은 비터미널 A에서 파생할 수 있는 문자열을 형성하도록 관계형 쿼리 의미론을 사용하여 계산된다고 합니다. 우리는 부울 언어에 중점을 두고 부울 문법을 사용하여 경로 레이블 지정을 설명합니다.관계형 쿼리 의미론과 부울 문법을 이용한 경로 쿼리는 결정 불가능한 것으로 알려져 있지만, 본 연구에서는 관계형 쿼리 의미론과 부울 문법을 사용하여 정확한 해에 근접하는 비순환 그래프에 대한 경로 쿼리 알고리즘을 제안합니다.기본 알고리즘과 비교하여 더 나은 성능을 얻기 위해 고려되는 그래프 클래스는 비순환 그래프로 제한되었습니다.

Institute for System Programming 논문집

2019 miniKanren 및 관계형 프로그래밍 워크숍 논문집

SEIM-19

13회 춘계/하계 소프트웨어 공학에 관한 젊은 연구자 콜로키움(SYRCoSE 2019) 예비 논문집, 2019년 5월 29-31일 – 러시아 연방 사라토프

2019 miniKanren 및 관계형 프로그래밍 워크숍 논문집

2019 miniKanren 및 관계형 프로그래밍 워크숍 논문집

Programming and Computer Software

TyDe 2018(ICFP)에서 확장된 초록.

컨텍스트 자유 경로 쿼리(CFPQ)를 범용 프로그래밍 언어로 지정하기 위한 도메인별 언어의 투명한 통합과 쿼리 오류의 정적 검사는 CFPQ를 사용하는 애플리케이션 개발을 크게 단순화할 수 있습니다.LINQ 및 ORM을 통합에 사용할 수 있지만 유연성 문제가 있습니다. 즉, 쿼리 분해 및 하위 쿼리 재사용이 어렵습니다.경로 쿼리를 위한 파서 조합기 기술의 적용으로 이러한 문제를 해결할 수 있습니다.기존의 파서 조합기는 선형 입력을 처리하며 Trails 라이브러리만 경로 쿼리에 이 기술을 적용하는 것으로 알려져 있습니다.임의의 컨텍스트 자유 문법과 임의의 입력 그래프를 지원하는 CFPQ용 일반 파서 조합기를 생성할 수 있음을 입증합니다.이러한 파서 조합기의 라이브러리를 구현하고 실제 작업에 적용할 수 있음을 보여줍니다.

9회 ACM SIGPLAN 스칼라 국제 심포지엄 논문집

NTV SPbSTU

GRADES-NDA '18 그래프 데이터 관리 경험 및 시스템(GRADES) 및 네트워크 데이터 분석(NDA)에 관한 1회 ACM SIGMOD 공동 국제 워크숍 논문집

18th International Symposium on Trends in Functional Programming

20회 선언적 프로그래밍의 원칙과 활용에 관한 국제 심포지엄 논문집

ML/OCAML 2016 논문집

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

NTV SPbSTU

CFPQ에 대한 몇 가지 솔루션이 있지만 응답 처리 및 디버깅에 실용적인 쿼리 결과의 구조적 표현을 제공하는 방법은 여전히 미해결 과제입니다.본 논문에서는 임의의 컨텍스트 자유 문법과 그래프를 위해 다항식 시간과 공간에서 주어진 문법과 관련해 이러한 표현을 구축할 수 있는 그래프 파싱 기법을 제안합니다.이전 솔루션은 대부분 CYK 또는 Earley 알고리즘을 기반으로 하지만 제안된 알고리즘은 일반화된 LL 파싱 알고리즘을 기반으로 하므로 경우에 따라 시간 복잡도를 줄여줍니다.

13회 중앙 및 동유럽 소프트웨어 공학 러시아 컨퍼런스(CEE-SECR '17) 논문집

ISP RAS 의회록

arXiv

The European Conference on Object-Oriented Programming (ECOOP)

부분 평가 및 프로그램 조작에 관한 2017 ACM SIGPLAN 워크숍 논문집

St. Petersburg State Polytechnical University Journal. Computer Science. 통신 및 제어 시스템

Izvestia vuzov. North Caucasus Region. Technical Sciences, 2017, 4호, 5-12페이지

Institute for System Programming 논문집

arXiv

정규 입력 문자열 세트의 구문 분석 기술을 제시합니다.이 문제는 호스트 프로그램이 런타임에 임베디드 언어의 절을 생성할 때 문자열 임베디드 언어 분석과 관련이 있습니다.채택된 기법은 RNGLR 알고리즘의 일반화를 기반으로 하며, 이를 통해 본질적으로 정규 근사된 입력 문자열 세트에 대한 구문 분석 포리스트의 유한 표현을 구성할 수 있습니다.이 표현은 리엔지니어링, 코드 유지 관리, 프로그램 이해 등의 맥락에서 의미론적 분석과 변환에 추가적으로 활용될 수 있습니다.문제의 접근 방식은 완화된 구문 분석을 구현합니다. 근사치 집합에서 인식되지 않는 문자열은 오류 감지 없이 무시됩니다.

Perspectives of System Informatics

Systems and Means of Informatics

META 2016 메타컴퓨팅에 관한 5회 국제 Valentin Turchin 워크숍

SEIM-16

NTV SPbSTU 4 (224)

Systems and Means of Informatics

Science of Computer Programming

11회 중앙 및 동유럽 소프트웨어 공학 러시아 컨퍼런스 논문집

9회 시스템 정보학의 관점에 관한 국제 Andrei Ershov 기념 컨퍼런스 논문집

2014년 10회 중앙 및 동유럽 소프트웨어 공학 러시아 컨퍼런스 논문집

10회 중앙 및 동유럽 소프트웨어 공학 러시아 컨퍼런스 논문집

9회 중앙 및 동유럽 소프트웨어 공학 러시아 컨퍼런스 논문집

ML 워크숍

2010 동서 설계 및 테스트 심포지엄 논문집

6회 시스템 정보학의 관점에 관한 국제 Andrei Ershov 기념 컨퍼런스 논문집

객체 지향 언어를 사용한 다중 패러다임 프로그래밍 워크숍

System Informatics

System Programming

System Programming

소프트웨어 유지 관리 및 리엔지니어링에 관한 유럽 컨퍼런스 논문집, CSMR 995802, pp. 177-185

4회 시스템 정보학의 관점에 관한 국제 Andrei Ershov 기념 컨퍼런스 논문집

Automated Reengeneering of Programs, Saint Petersburg