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 のセマンティクスに関する正式な研究について紹介します。まず初めに、限定的な論理プログラムの最小エルブランモデルに対応する表示的意味論を定式化します。次に、MINIKANREN 実装の弁別的機能であるインターリーブをモデル化する操作的意味論について説明し、表示的意味論に関する健全性と完全性を実証します。私たちの開発は、リファレンスインタープリターを抽出できる COQ 仕様に基づいています。また、主要な結果からは、カット規則を用いた SLD 解決の証明された意味論 (およびリファレンスインタープリター) を引き出し、その健全性を実証します。

リレーショナルプログラミング (具体的な形の制約論理プログラミング) の適用に基づいて、パターンマッチングコンストラクト実装の統合に対する完全な宣伝的アプローチを紹介します。私たちのアプローチは、パターンマッチングの高水準意味論および中間実装言語の意味論の関係表現に基づいています。この選択肢を選ぶことによって、パターンマッチングの新機能の実装を統合するには、高水準の意味論を変更することのみが必要となるため、原理上は、とてもスケーラブルなアプローチとなります。既存の文献から部分的に抽出した一連の小さなサンプルを評価した結果、私たちのフレームワークは最適な実装をすばやく統合できることが分かっています。ただし、数多くの人工的なベンチマークに対して徹底的なストレス評価を実施した結果、今後改善を加えていく必要性があることも明らかになっています。

文脈自由パスクエリ (CFPQ) を使用すると、文脈自由文法がパスの制約として使用されることを許可することによって、通常のパスクエリ (RPQ) を拡張できます。CFPQ のアルゴリズムの開発は積極的に行われていますが、J. Kuijpers et al. は最近、既存のアルゴリズムは実際のアプリケーションで使用できるほど高性能なものではないと判断しています。そのため、CFPQ の新アルゴリズムの開発は妥当であるとされています。この論文では、クロネッカー積や推移閉包のような線形代数演算に基づき、再帰的状態のマシンとして提示される文法を処理する、新しい CFPQ アルゴリズムについて説明します。したがい、提案するアルゴリズムは、高性能ライブラリおよび最新の並列ハードウエアを使用することによって実装できます。さらに、文法の拡大を避けられるため、クエリを最適化できる可能性も生まれます。

ADBIS 2020. Advances in Databases and Information Systems. コンピューターサイエンスの講義資料。

RDF グラフに対してクエリを実行するには、SPARQL のプロパティパスに正規表現を使用します。ただし、正規表現は、正規言語と呼ばれる最も制限の多い種類の言語しか定義できません。文脈自由言語は、すべての正規言語が含まれた、より広範な種類の言語です。それを定義できる文脈自由表現が存在しないため、文法を書く必要があります。私たちは、文脈自由言語のサブセットの定義を支えるために、再帰表現という、正規表現を拡張したものを提案します。したがい、私たちの取り組みは、言語の定義を文脈自由言語に限りなく近づける、シンプルな演算子を提供することを目的としています。

2020 年度 ADBIS、TPDL、EDA 主催共同ワークショップおよび博士課程コンソーシアム

The European Conference on Object-Oriented Programming (ECOOP)

さまざまな分野でグラフ構造データ解析に幅広く使用される文脈自由パスクエリ (CFPQ)。入力データは通常、サイズが大きいため、CFPQ には高性能のアルゴリズムを開発することが極めて重要です。CFPQ 評価を R 上で行列方程式を解決するシステムに単純化する (高性能なソリューションが存在する問題) 方法を紹介します。また、実際のデータ解析における、私たちのアプローチの適用性も実証します。

2020 年度 ACM SIGMOD 主催データ管理に関する国際カンファレンスの議事録

この論文では、解析テーブルを独立したサブマトリックスが順番に計算されていく複数のレイヤーに分割し、各レイヤーの各サブマトリックスを個別に処理できる可能性を主な利点とする、バリアントのアルゴリズム修正を紹介します。また、私たちのアプローチは、文字列マッチングの問題に簡単に適応できます。

Institute for System Programming の議事録

最近の研究では、既存のソリューションの効果が低く、そのメモリ消費量も多いために、リレーショナルクエリのセマンティクスがグラフデータベースと統合された、文脈自由パスクエリ (CFPQ) のアルゴリズムの適用性は限られていることが分かりました。今回の取り組みでは、線形代数に適切な高性能ライブラリを使用することによって、マトリックスベースの CFPQ アルゴリズムを実装し、RedisGraph グラフデータベースと統合します。また、ノードの各ペアごとに見つかったパスを 1 つ抽出できる、シングルパスクエリのセマンティクスを用いた新しい CFPQ アルゴリズムを紹介します。最後に、両方のセマンティックスにおける私たちのアルゴリズムの評価結果を説明し、Redis-Graph データベースに対してマトリックスベースの CFPQ を実装することが実際のデータ解析に十分であることを証明します。

GRADES-NDA'20: 第 3 回 Graph Data Management Experiences & Systems (GRADES) および 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)

GPU を利用すれば演算処理を桁違いに高速化できる一方で、メモリの管理がボトルネックであることは変わらず、必要なパフォーマンスを実現できないことが課題となっています。したがい、メモリをより効果的に使用できるよう、異なるメモリ最適化手法が活用されます。私たちは、部分的な評価を用いたメモリ管理を自動化するアプローチ、つまりデータへのアクセスが事前に処理し、最適化し、またコードに組み込むことによって、メモリの使用量を節約するプログラム変換技法を提案します。私たちのアプローチの経験的評価を実施した結果、CUDA C のナイーブ法を用いた文字列パターンマッチングのアルゴリズムの実装においては、変換されたプログラムが元のプログラムよりも最大 8 倍も効率的であることが分かっています。

PPoPP '20: 第 25 回 ACM SIGPLAN 主催並列プログラミングの原則および慣行に関するシンポジウムの議事録

ISP RAS の議事録

論理積の文法を用いたパスクエリは、決定不能なものとして知られています。論理積の線形的な文法を用いてパスクエリを実行するためのアルゴリズムがあり、過度に近似した結果が得られます。しかし、論理積の任意の文法についてはアルゴリズムがありません。論理積の任意の文法を用いたパスクエリについては初となるアルゴリズムを提案します。提案するアルゴリズムは、マトリックスをベースにしており、マトリックス演算に対して GPGPU コンピューティング技法とその他の最適化手法を効率的に適用できるものです。

Programming and Computer Software

BMC Bioinformatics

第 19 回 コンピューター支援設計の形式手法に関する国際カンファレンス FMCAD 2019 の議事録

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

最近提案された文脈自由パスクエリ (CFPQ) のマトリックス乗算をベースにしたアルゴリズムによって、最もパフォーマンスクリティカルな部分がブールマトリックスの乗算にオフロードされます。したがい、最新の並列ハードウェアやソフトウェアによって、CFPQ の高性能を実現することが可能になります。この論文では、実際のデータと最悪のケースの合成データの両方に対してこのアルゴリズムを異なる形で実装した際のパフォーマンスを比較した結果を発表します。

第 2 回 Graph Data Management Experiences & Systems (GRADES) および Network Data Analytics (NDA) の共同国際ワークショップの議事録

バーヒレルの定理は、文脈自由言語は、通常セットとの交点で終了するとしています。この定理には構成的証明があるため、上述したアプリケーションのアルゴリズムは正しいとする正式な根拠が提供されます。したがい、バーヒレルの定理の機械化は、形式言語理論の基本的な結果であると同時に、アプリケーションのアルゴリズムの証明された実装でもあります。この取り組みでは、Coq を使ってバーヒレルの定理の機械化された証拠を提示します。

Logic, Language, Information, and Computation

形式文法と生物学的配列処理用の人工ニューラルネットワークを組み合わせる方法を提案します。形式文法が配列の二次構造をエンコードする一方で、ニューラルネットワークはミューテーションとノイズに対処します。従来のやり方とは対照的に、私たちは、二次構造のモデル化に確率的文法が使用される場合に、文法の作成を簡素化する、任意の (確率的ではない) 文法の使用を提案します。配列の全体的な構造をモデル化する代わりに、二次構造の機能のみを説明する文法を作成します。そして、マトリックスベースの解析機能を使うことによって、機能を抽出します。一部の非端子から部分文字列を一部抽出できることは 1 つの機能です。その後、緻密なニューラルネットワークを使って機能を処理します。

第 12 回医用生体工学システムおよびテクノロジーに関する国際共同カンファレンスの議事録 - BIOINFORMATICS

グラフデータ解析では、具体的なパスに対してクエリを実行する際に問題が生じます。そのようなクエリは通常、許可されているパスのエッジラベリングについて説明する形式文法を使って実行されます。パスクエリは、v1 から v2 へのパスがあり、またそのパスのエッジ上のラベルが非端子から得られる文字列を形成するといったかたちで 3 段階 (A、v1、v2) に評価される場合は 、リレーショナルクエリセマンティクスを使って計算されると言われています。私たちは、ブール文法を使ってパスのラベルについて説明するブール言語に焦点を当てています。リレーショナルクエリセマンティックスとブール文法を使ったパスクエリは、決定不能とされていますが、今回の取り組みでは、リレーショナルクエリセマンティックスとブール文法を用いるパスクエリアルゴリズムを非周期グラフに対して使用することを提案し、的確なソリューションに近づけます。ネイティブのアルゴリズムよりも優れたパフォーマンスを達成するために、グラフの検討されるクラスは非周期のグラフに限定されます。

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 主催 Scala に関する国際シンポジウムの議事録

NTV SPbSTU

GRADES-NDA' 18: 第 1 回 ACM SIGMOD 主催 Graph Data Management Experiences & Systems (GRADES) および Network Data Analytics (NDA) の共同国際ワークショップの議事録

18th International Symposium on Trends in Functional Programming

第 20 回宣言プログラミングの原則および慣行に関する国際シンポジウムの議事録

2016 年度 ML/OCAML の議事録

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

NTV SPbSTU

CFPQ 向けのソリューションはいくつかありますが、回答処理およびデバッグに役立つ実用的なクエリ結果を構造的に表現する方法は未だ解決されていません。この論文では、任意の文脈自由文法およびグラフの多項式時間および空間において指定される文法に関連して、既述の実用的な表現を生み出すことを可能にする、グラフ解析技法を提案します。提案するアルゴリズムは、一般化された LL 解析アルゴリズムに基づいています。前のソリューションは、大部分が CYK もしくはアーリー法を用いたアルゴリズムに基づいており、一部のケースで時間計算量を削減するものでした。

第 13 回中央・東ヨーロッパソフトウェアエンジニアリングカンファレンス (ロシア) (CEE-SECR ’17) の議事録。

ISP RAS の議事録

arXiv

The European Conference on Object-Oriented Programming (ECOOP)

2017 年度 ACM SIGPLAN 主催部分的評価およびプログラム処理に関するワークショップの議事録

サンクトペテルブルク工科大学ジャーナル。Computer Science. テレコミュニケーションおよびコントロールシステム

Izvestia vuzov. North Caucasus Region. Technical Sciences, 2017, No.4、5-12ページ

Institute for System Programming の議事録

arXiv

入力文字列の通常のセットの構文解析技法を紹介します。この問題は、ホストプログラムが実行時に組み込み言語で構成される句を生成するタイミングで実行される文字列組み込み言語の解析に関連したものです。私たちの技法は、RNGLR アルゴリズムを汎化することに基づいています。それを使用することで、本質的には、定期的に近似される一連の入力文字列に対するパースフォレストの有限表示を構築することができます。この表示は、リエンジニアリングやコードメンテナンス、プログラム理解などのコンテキストで行うセマンティックスの解析や変換においてさらに活用できます。対象のアプローチには、緩和解析が用いられます。近似セット内の認識されない文字列は無視され、エラーも検出されません。

Perspectives of System Informatics

Systems and Means of Informatics

2016 年度第 5 回 META 主催メタコンピューテ―ションに関する国際 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 回中央・東ヨーロッパソフトウェアエンジニアリングカンファレンス (ロシア) の議事録

機械学習のワークショップ

2010 年度 East-West デザイン & テストシンポジウムの議事録

第 6 回システム情報科学に関する国際 Andrei Ershov メモリアルカンファレンスの議事録

オブジェクト指向言語を使ったマルチパラダイムプログラミングのワークショップ

System Informatics

System Programming

System Programming

ソフトウェアメンテナンスおよびリエンジニアリングに関する欧州カンファレンスの議事録、CSMR 995802、pp. 177-185

第 4 回システム情報科学に関する国際 Andrei Ershov メモリアルカンファレンスの議事録

Automated Reengeneering of Programs, Saint Petersburg