Спасибо. И вам тоже, @GabrielFallen, давно хотел взяться за Z3 :)

еще можно петерссона глянуть

https://www.classes.cs.uchicago.edu/archive/2011/spring/22620-1/papers/pettersson92.pdf Pettersson, "A term pattern-match compiler inspired by finite automata theory"

Доброго всем дня. Здесь периодически возникают обсуждения применимости графовых БД как "бэкенда" для статического анализа. Мы с коллегами сделали очередной шаг, делающий, как минимум, эксперименты в этой область чуть более приятными. Теперь можно взять настоящую графовую БД (RedisGraph) и задавать к ней КС и регулярные запросы на настоящем Cypher. Образ с соответсвущей сборкои RediGraph-а: https://hub.docker.com/r/simpletondl/redisgraph Небольшая статья: https://edbt2021proceedings.github.io/docs/p48.pdf  Да, это академическая поделка и наверняка есть много косяков. Но вдруг кому-то хочется поэкспериментировать. А если у кого-то есть чёткое понимание, что было бы здоарово взять вот этот граф, задать к нему такой-вот КС запрос и посмотреть, что получится — это вообще круто. Будет чертовски любопытно поставить такой эксперимент.

Если что есть работы по этой теме, напр joern (source-level graph)/bjoern (binary-level). Не знаю правда в каком они состоянии, но ресерчеры в частности с ним пару багов в ядре линуха нашли емнип

Ага. Вообще, много чего есть. И даже поверх neo4j делали разные вещи. Просто нормальных кс запросов пока не видел. А они существенно возможности повышают. Ну, в теории по крайней мере :)

@true_grue помнится, вы задавались соответствующий вопросом про использование графовых БД в бэкэндах компиляторов...

а что за "кс-запросы"?

Контекстно-Свободные запросы. Запросы в виде КС-грамматики, определяющей что именно в графе нужно поматчить.

а, ясно
в neo4j же есть cypher & gremlin, там вполне должен быть context-free, нет?

Чтобы в Cypher можно было выразить КС, надо немного постараться и реализовать расширение его синтаксиса, которое до недавнего времени было только в виде предложения по улучшению языка. Мы это для RedisGraph-овского парсера и остального query engine сделали. Потому там теперь Cypher позволяет такие запросы писать. В Neo4j этого расширения пока нет. В gremlin, кажется, тоже. Понятно, что необходимые алгоритмы можно и руками поверх хранилища сделать, но это иногда менее удобно.

Если интересно, то вот это расширение: https://github.com/thobe/openCypher/blob/rpq/cip/1.accepted/CIP2017-02-06-Path-Patterns.adoc

вот это сложновато оказалось, не очень подробно алгоритм расписан. Хотелось бы увидеть самую тупую работающую реализацию, а неоптимальность выхлопа это пустяки

Увы, у меня не КС-запросы, а нечто в духе frequent subgraphs mining. В остальном пока хватает Datalog и Souffle/Z3.

There's a recent new Zulip server for the TYPES community at https://typ.zulipchat.com/

Typical topics include: typed, untyped, or polymorphic lambda calculus; type checking, inference, and reconstruction; subtyping, dependent types, calculus of constructions, the lambda cube; linear logic, the Curry-Howard correspondence; recursive types; adequate and fully abstract models; domain theory; category theory; term reduction, normalization, confluence; abstract data types; type systems for object-oriented, concurrent, distributed, and mobile programming.

Просто жена сегодня подарила))

Уильям Вульф (William Wulf) - исследователь в области компиляторов, сотрудничавший со знаменитой компанией DEC. Вульф - создатель раннего оптимизирующего компилятора языка BLISS и один из авторов классической книги The Design of an Optimizing Compiler (1975).

После работы над BLISS команда Вульфа переключилась на амбициозный проект PQCC (Production-Quality Compiler-Compiler Project), в рамках которого шла работа над универсальным компилятором компиляторов, целью которого было порождение всех этапов компилятора для новых архитектур из декларативных описаний - актуальной проблемы для DEC, продававшей разнородные платформы (семейства PDP и VAX, позже - Alpha).

Статья Compilers and Computer Architecture (1981) - выводы из этой работы. В ней Вульф указывает, что экономику разработки новых архитектур нельзя рассматривать без стоимости разработки сопутствующего компилятора. То есть дизайн набор инструкций нельзя создавать без учета будущих компиляторов.

Исходя из этих наблюдений Вульф предлагает принципы разработки компьютерных архитектур общего назначения:

1. Регулярность (regularity) - должен быть один способ делать что-либо, и он должен быть применим везде (например, ADD работает для всех регистров и типов данных).

2. Ортогональность (orthogonality) - аспекты архитектуры должны обсуждаться независимо, без взаимного влияния (режим адресации, к примеру, не должен влиять на выбор примитивов).

3. Композиционность (composability) - в регулярной и ортогональной архитектуре можно соединить различные аспекты произвольным образом (каждая из инструкций поддерживает работы с любым регистром и режимом адресации).

От базовых принципов статья переходит к принципам-следствиям: вопросам адресации, выбора примитивов, отклонения от принципов. Интересный вывод касается поддержки примитивов, специфичных для конкретных языков высокого уровня: "In many cases these turn out to be more trouble than they are worth".

Это очень интересная и по-прежнему актуальная статья от одного из известнейших специалистов по компиляторам своей эпохи. Пересказывать ее полностью нет смысла, остается только рекомендовать интересующимся темой компьютерных архитектур и неотделимой от нее темой разработки компиляторов.

Compilers and Computer Architecture (1981) -  статья

https://en.wikipedia.org/wiki/William_Wulf - автор

https://en.wikipedia.org/wiki/BLISS - известнейшая работа автора

https://en.wikipedia.org/wiki/The_Design_of_an_Optimizing_Compiler - классическая книга автора

#bliss #pqcc #architecture #isa #history

Как по русски statement?

стейтмент

😉