Изготовление «MiniKanren» с использованием Z3Py (2021 г.)

Реляционное / логическое программирование – это довольно круто. Это позволяет делать вещи, которые кажутся невозможными, например запускать программу в обратном направлении. Используя

Z3py , чтобы сделать много тяжелой работы, есть милый, простой и довольно мощный маленький микроканрен ты можешь сделать. Вы можете заставить его отвечать на такие запросы, как следующий: список выполнения добавляется в обратном порядке.

b 17 f0e 16 a 731760 ca8d 2013 d 272 c .

Короткие Spiel on Minikanren

Подход minikanren строит встроенный реляционный язык программирования из двух частей

  1. объединение
  2. Какой-то недетерминированный поиск

Бумага микроканрена действительно хороша, если вы можете прочитать небольшую схему http://webyrd.net/scheme- 242961 / документы / HemannMuKanren 242961. pdf . Я больше говорю и имею больше ссылок о микроканренах здесь https: //www.philipzucker.com/yet-another-microkanren-in-julia/

Недетерминированный поиск строится вокруг концепции «цели». Цель преобразует состояние в набор возможных уточненных состояний на основе утверждений цели. Другими словами, его можно смоделировать как функцию Состояние -> [State] .

Состояние поиска миниканрена описывается известными на данный момент унификациями. Объединение – это своего рода двунаправленное сопоставление с образцом. Вы берете два шаблона и просматриваете их, чтобы выяснить, какие переменные должны быть равны, или если они не могут совпадать. Я собираюсь замкнуть всю эту деталь, чтобы просто опереться на Z3. У этого есть положительный момент в том, что его не нужно реализовывать, а обратная сторона Z3 – это то, что он гораздо менее контролируемый / универсальный в том, что он возвращает, по сравнению с использованием унификации.

Термин с переменными, назовем его шаблоном, в некотором смысле представляет собой представление набора конкретных термов без переменных. Например, шаблон

 f (? A, c)  представляет  f (c, c) ,  f (бар ( z), c) ,  f (g (cons (l)), c)  и так далее.  Шаблоны представляют собой набор терминов со всеми возможными заменами терминов в переменных шаблона.  Унификация - это способ запросить пересечение этих наборов терминов. 

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

Генераторы

Мне очень нравятся генераторы питона. Вы можете сделать с ними довольно дурацкий поток управления.

Моя внутренняя модель того, что я делаю, - это состояние программы - это список утверждений Z3, а цели трансформируются в новые списки утверждений z3. Эта форма позволит выполнить более обычный поиск с чередованием канрена.

Но, используя внутреннее состояние z3 Solver с интерфейсом push / pop мы получаем выигрыш в эффективности и удобстве, но то, что осталось позади, это довольно причудливая программа с очень большим состоянием.

Выполнение

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

 s.check () == sat  для раннего отсечения этой ветви поиска с использованием возможностей решения Z3.  Когда генератор наконец умирает, решатель должен быть возвращен в исходное состояние.  Это договор, который нужно правильно реализовывать по каждой цели.  Конечно, это непростая задача, но если вы строите свои цели с помощью комбинаторов, все в порядке. 

 из  z3  Импортировать     def   экв   ( Икс,   y  ):   def  Цель (  s  ):   s  . толкать  ()   s  . Добавлять  (Икс  ==   y  )  если   s  .  проверять ()   ==  сидел :  урожай  s  .   поп   ()  возвращаться Цель  

Фактически мы можем абстрагироваться от этого, чтобы превратить произвольное утверждение z3 в цель. в основном по той же схеме. Я меняю только s.check () == sat на s.is_good () , потому что гибкость мне понадобится позже. Вы можете думать о них как об одном и том же.

   def  поднимать  (  z3assert  ):   def   res   (  s  ):   s  .  толкать ()   s  .  Добавлять (  z3assert  )  если  s  . хорошо  ():  урожай  s  .   поп   ()  возвращаться  res   def   лифт2   (  op  ):   def   res   (  Икс,   y  ):  возвращаться поднимать (  op   ( Икс,   y  ))  возвращаться  res  Импортировать  оператор   экв   знак равно  Лифт 2   (  оператор  .   __ экв __  )   

Теперь мы можем определить комбинаторы целей канрена disj и в сочетании для дизъюнкции (или) и союза (и). con1 в основном запускает две цели последовательно, вторая входит в сферу действия первой. disj1 выполняет две цели как бы параллельно, где они не входят в сферу действия друг друга. disj и

 в сочетании  являются многоаргументными формами для удобства.    - маленькие дурацкие обозначения для переменных Python. 

   def   con1   (  f  , грамм ):   def   res   (  s  ):  для  _  в  f   (  s  ):  если  s  .   хорошо ():   # print (s.model ())  урожай из грамм (  s  )  возвращаться  res  Импортировать  functools   def   при   (    аргументы  ):  возвращаться  functools  . уменьшать  (   con1  ,   args  )   def   disj1   (  f  , грамм ):   def   res   (  s  :   # itertools.chain ( f (s), g (s))  урожай из  f   (  s  )  урожай из грамм (  s  )  возвращаться  res   def   disj   (    аргументы  ):  возвращаться  functools  . уменьшать  (   disj1  ,   args  )   

Дополнительная функция удобства conde , который работает как схема cond , а также немного похоже на сопоставление с шаблоном.

   def   conde   (    аргументы  ):  возвращаться  disj   (   карта (  лямбда   l  :   con   (    l  ),   args  ))   

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

   def   Zzz   (   thunk_goal  ):   def   res   (  s  ):  урожай из  thunk_goal   () (  s  )  возвращаться  res   def   модель печати   (  s  ):  если  s  . хорошо  ():  Распечатать  (  s  . модель  ())  урожай  def   пустой   (  s  ):  если  Ложь:  урожай  # Как сделать его итератором?    

Наконец, нам нужен верхний уровень run функция. Здесь есть несколько вариантов. Эта версия принимает интересующие нас переменные в qs и проецирует их из модели. Это не возвращает все возможные решения запроса, только одно на каждую успешную ветвь.

   def   runq   (  qs  ,  Цель):   s   знак равно  Решатель   ()   s  . хорошо знак равно   лямбда  :   s  .  проверять  ()   ==  сидел для  _  в Цель  (  s  ):   м   знак равно  s  .  модель ()  урожай  {  q  :   м  .   eval   (  q  )  для  q  в  qs  }   

Вот базовый запрос. Нам доступна полная гибкость Z3

 Икс ,   y  знак равно   Ints   (  «ху»   )   ex_goal2   знак равно  conde   (  [eq(x,3) , eq(y,4) ]  ,   [eq(y,5) , eq(x,6) ]  )  список  (  runq   ([x,y],   ex_goal2  ))   # [{x: 3, y: 4}, {x: 6, y: 5}]   

Более сложный запрос. Обратите внимание, мне пришлось использовать Zzz комбинатор при рекурсивном вызове приложения , чтобы машина не сошла с рельсов.

 
  # Объявление списка целых чисел  Список  знак равно Тип данных ( 'Список')   # Минусы конструктора: (Int, List) -> List Список .   объявить   (  'минусы'  ,   ( 'машина',   IntSort   ()),   (  'cdr'  ,  Список ))   # Конструктор nil: List Список  .   объявить   (  'ноль'  )   # Создайте тип данных  Список  знак равно Список.  Создайте  ()   минусы  знак равно  Список .   минусы  машина знак равно  Список .  машина  cdr   знак равно Список.   cdr   ноль   знак равно Список.   ноль   def   приложение   (Икс ,   y  ,   z  ):  час знак равно   FreshInt   ()   т  знак равно   FreshConst   (Список )   res  знак равно   FreshConst   ( Список)  возвращаться  conde   (  [ eq(x, nil), eq(y,z) ],   [ eq( x, cons(h,t)), eq(z, cons(h, res)) , Zzz( lambda : appendo(t,y,res ))]  )   q  знак равно   Const   (  "q"  ,  Список)  р  знак равно  Const   ( "р",  Список )   Икс,   y   знак равно  Ints   (  «ху»  )  список (  runq   ( ,   приложение   (  q  ,  р,   минусы   (  2  ,   минусы   (  42  ,   минусы   (  17  ,   ноль  ))))))   

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

   def   run_iterative_deep   (Цель ):   s  знак равно   Решатель   ()   s  .  хорошо  знак равно  лямбда  :   s  .   num_scopes   ()   <  s  .  Максимальная глубина а также  s  .  проверять ()   ==  сидел для глубина в  itertools  . считать  (Начало знак равно   1  ):   s  .  Максимальная глубина  знак равно глубина для  _  в Цель (  s  ):  урожай  s  .  модель ()   

Conj и Disj Канрена против And и Or в Z3

Меня поразило сходство программирования Z3 и программирования макросов / программирования времени компиляции. Python в использовании Z3py - это метаязык макроуровня для Z3. Иногда у вас есть выбор, выполнять ли вычисления в слое Python или в слое Z3. Вы хотите определить функцию z3 или использовать функцию Python на метауровне для определения возведения в степень? Вы хотите использовать записи Python или Z3 для ваших типов данных? Вы можете использовать приемы частичной оценки, чтобы сделать как можно больше на уровне Python. Однако эти два слоя не являются полностью взаимозаменяемыми. В Python отсутствуют возможности решения / вывода / обратимости, как в Z3, а в Z3, в частности, отсутствует рекурсия и итерация в полную силу.

Запросы Z3 в определенном смысле негибкие. Похоже, вам нужно определить фиксированную вселенную, по которой Z3 будет искать. Двумя основными обходными путями этого ограничения являются использование квантификаторов и, соответственно, механизмов с фиксированной точкой, для обоих из которых ваш пробег может варьироваться.

Вероятно, желательно использовать Z3 И / Или по возможности смещать disj / con. Z3 будет выполнять поиск намного лучше, чем мой мусор, и он уменьшает количество push / pop.

Количественное определение Z3 добавляется для сравнения

Вы можете определить добавить с помощью квантификаторов. Это полное определение. Однако использование квантификаторов с использованием обычного механизма решения в Z3 обычно означает, что он не сможет вернуть модель, потому что он не может в целом выяснить, удовлетворяет ли она всему количественному определению (количественная оценка в некотором смысле утверждает бесконечное число формулы, что в целом сложно проверить). Решатели с фиксированной точкой

https: //rise4fun.com/z3/tutorialcontent/fixedpoints может сделайте что-нибудь с этим, но это когда-нибудь для другого поста.

  из  z3  Импортировать    # Объявление списка целых чисел Список знак равно  Тип данных  ('Список' )   # Минусы конструктора: (Int, List) -> List  Список.   объявить   (  «минусы»  ,   ('машина' ,   IntSort   ()),   (  'cdr'  ,  Список))   # Конструктор nil: List  Список .   объявить   (  'ноль'  )   # Создайте тип данных Список знак равно  Список .   Создайте ()   минусы   знак равно Список.   минусы  машина знак равно  Список . машина  cdr  знак равно   Список.   cdr   ноль   знак равно Список.   ноль   добавить   знак равно  Функция   (  "приложение"  ,  Список,  Список ,  Список )   q  знак равно   Const   (  «q»  ,  Список )  рзнак равно   Const   ("р"  ,  Список)   l   знак равно  Const   (  «л»  ,  Список)  час знак равно   Инт   ( "час")   т   знак равно  Const   (  «т»  ,  Список )   append_def  знак равно   [    ForAll([l],   добавить   (  ноль  ,   l  )   ==   l  ) ,  Для всех ([h,t,l],   добавить   (  минусы   ( час,   т  ),   l  )   ==   минусы   (час ,   добавить   (  t  ,   l  )  ))  ]   s  знак равно   Решатель   ()   s  . Добавлять  (  append_def  )   s  . Добавлять   (  добавить   (  q  , р )   ==   минусы   (   2  ,   минусы   (  58  ,   минусы   (  17  ,   ноль  )))  )   s  .  проверять ()   # не возвращает   

Почему цитаты вокруг миниканрена?

Семейство Канрен обычно использует какой-либо полный поиск, чередуя ветви дерева поиска. Поскольку я злоупотребляю механизмом push / pop z3, удобнее всего использовать поиск в глубину, который является неполным. В этом смысле то, что мы имеем здесь, на самом деле не Канрен.

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

Биты и помпы

Используйте это для анализа достижимости программ (циклов while и т. Д.).

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

Сравните и сравните с Z3 встроенные решатели с фиксированной точкой, такие как BMC и Spacer.

Использовать ядро ​​unsat для обратного перехода?

Как выполнить полный поиск с чередованием в стиле миниканрен?

Комбинирование логического программирования с ограничениями / smt - это совсем не новость. Он идет под названиями CLP (программирование логики ограничений) и CHC (условные предложения рог).

https://www.youtube.com/watch?v=KsC_9_-NuQg

Leave a comment

Your email address will not be published. Required fields are marked *