AST Object Unification

To make existing Python AST objects amenable to the unification used by miniKanren, we implement unify specializations for ast.AST types. Our implementation simply generates unevaluated Hy forms, or Hy AST, that–when evaluated–would (re)create the ast.AST objects.

hypoKanren uses multipledispatch, so augmenting the unification process is easy. This is how we’ll add support for AST objects.

(import [multipledispatch [dispatch]])
(import [hypoKanren.unify [*]])
(import [hy.models [*]])
(import [hy.contrib.walk [prewalk]])


(defmacro/g! dispatch-unify-trans [disp-type trans-func &optional [func 'unify]]
  `(do
     #@((dispatch ~disp-type object object)
        (defn unify-post-walk [~g!u ~g!v ~g!s]
          (~func (~trans-func ~g!u) ~g!v ~g!s)))
     #@((dispatch object ~disp-type object)
        (defn unify-post-walk [~g!u ~g!v ~g!s]
          (~func ~g!u (~trans-func ~g!v) ~g!s)))
     #@((dispatch ~disp-type ~disp-type object)
        (defn unify-post-walk [~g!u ~g!v ~g!s]
          (~func (~trans-func ~g!u) (~trans-func ~g!v) ~g!s)))))

(defn py-ast-to-expr [x]
  (defn -py-ast-to-expr [u]
    (setv ast-expr
          `(~(HySymbol (+ "ast." (name (type u))))
            ~@(chain.from-iterable
                (lfor f u.-fields
                      :if (hasattr u f)
                      [(HyKeyword f) (getattr u f)]))))
    ast-expr)
  (prewalk (fn [y] (if (instance? ast.AST y)
                       (-py-ast-to-expr y)
                       y))
           x))

;; Python AST expansion pre-unification
(dispatch-unify-trans ast.AST (fn [x] (py-ast-to-expr x)))

;; One is an `ast.AST` object, the other an unevaluated `ast.AST`
;; object-generating form.
(setv unify-exa-1 (unify (ast.Expr :value [])
                         `(ast.Expr :value ~(var 0))
                         {}))

;; Both are `ast.AST` objects
(setv unify-exa-2 (unify (ast.Expr :value [])
                         (ast.Expr :value (var 0))
                         {}))

(= (.get unify-exa-1 (var 0))
   (.get unify-exa-2 (var 0))
   [])

True

(unify (cons 'ast.Expr (var 0))
       (ast.Expr :value [(ast.Name :id "a")])
       {})

{(LVar 0): HyExpression([
  HyKeyword('value'),
  [HyExpression([
    HySymbol('ast.Name'),
    HyKeyword('id'),
    'a'])]])}

We will also need to unify some limited Hy AST forms; specifically, HySymbols. We will want to extract only the name part of a Hy symbol and relate that to Python ast.Names via one of the latter’s constructor arguments.

Similar to Python AST nodes, we will expand/lift/abstract HySymbols to Hy expressions that–when eval’ed–would construct them. We can only do this in very limited cases; otherwise, we could end up producing ever-expanding forms.

;; Hy AST expansion pre-unification
(defn unify-hysymbol [u v s]
  (cond
    [(= (first v) 'HySymbol)
     (print )
     (unify `(HySymbol ~(name u)) v s)]
    [True
     (unify u v s)]))

#@((dispatch HySymbol HyExpression object)
   (defn unify-post-walk [u v s]
     (unify-hysymbol u v s)))

#@((dispatch HyExpression HySymbol object)
   (defn unify-post-walk [u v s]
     (unify-hysymbol v u s)))

(unify 'a `(HySymbol ~(var 0)) {})

{(LVar 0): 'a'}

Call-expression Goals

Next, we create the miniKanren goals that encapsulate the relationships between simple Hy and Python AST forms. In particular, we’ll limit ourselves to only variable reference and function call forms.

(defn listo [l]
  "A goal stating that `l` is a list."
  (conde
    [(== l []) s#]
    [(fresh [lcar lcdr]
            (== l (cons lcar lcdr))
            (listo lcdr))]
    [s# u#]))

The first AST relation is a simple one between HySymbols and ast.Names. This is where the HySymbol unification implemented above is used.

(defn hy-py-symbolo [hy-ast py-ast]
  "A goal relating Hy and Python AST symbol/name objects (e.g. variable and
 function references)."
  (fresh [symbol-name py-ctx]
         (== hy-ast `(HySymbol ~symbol-name))
         (== py-ast `(ast.Name :id ~symbol-name
                               :ctx (ast.Load)))))

Some Python ast.AST types have fields consisting of lists containing other ast.AST objects (e.g. the ast.Call expressions below). We need a goal that enforces a relation between the Hy and Python AST forms of each element in such lists.

(defn lapplyo [func l-in l-out]
  "A goal that applies the goal `func` between all elements in lists `l-in` and
 `l-out`."
  (conj+
    (listo l-in)
    (conde
      [(fresh [lcar lcdr lout-car lout-cdr]
              (== l-in (cons lcar lcdr))
              (func lcar lout-car)
              (lapplyo func lcdr lout-cdr)
              (== l-out (cons lout-car lout-cdr)))]
      [(== l-in [])
       (== l-out l-in)])))

Finally, we create a goal for the AST of call expressions like func(x, y, z) and (func x y z).

(defn hy-py-callo [hy-ast py-ast]
  "A goal relating call expressions in Python and Hy AST."
  (fresh [hy-op hy-args py-op py-args]
         ;; Hy AST form
         (== (cons hy-op hy-args) hy-ast)
         ;; Py AST form
         (== py-ast `(ast.Expr :value
                               (ast.Call :func
                                         ~py-op
                                         :args
                                         ~py-args
                                         :keywords
                                         [])))
         ;; These two must be related symbols
         (hy-py-symbolo hy-op py-op)
         ;; The arguments are related lists containing more of each AST type.
         (lapplyo hy-py-asto hy-args py-args)))

(defn hy-py-asto [hy-ast py-ast]
  "A goal for a 'branching' relation between multiple types of forms and their
 corresponding Python AST."
  (conde
    [(hy-py-symbolo hy-ast py-ast)]
    [(hy-py-callo hy-ast py-ast)]))

(setv hy-ast-exa `(print x y z))
(setv py-ast-exa (. (hy-compile hy-ast-exa "__console__") body [0]))
(.format "hy_ast_exa = {}\npy_ast_exa = {}"
         hy-ast-exa
         (astor.dump py-ast-exa))

hy_ast_exa = HyExpression([
  HySymbol('print'),
  HySymbol('x'),
  HySymbol('y'),
  HySymbol('z')])
py_ast_exa = Expr(value=Call(func=Name(id='print'), args=[Name(id='x'), Name(id='y'), Name(id='z')], keywords=[]))

(setv rel-res (run 1 [py-ast] (hy-py-asto hy-ast-exa py-ast)))
(setv ast-res (get rel-res 0 0))
ast-res

HyExpression([
  HySymbol('ast.Expr'),
  HyKeyword('value'),
  HyExpression([
    HySymbol('ast.Call'),
    HyKeyword('func'),
    HyExpression([
      HySymbol('ast.Name'),
      HyKeyword('id'),
      'print',
      HyKeyword('ctx'),
      HyExpression([
        HySymbol('ast.Load')])]),
    HyKeyword('args'),
    HyExpression([
      HyExpression([
        HySymbol('ast.Name'),
        HyKeyword('id'),
        'x',
        HyKeyword('ctx'),
        HyExpression([
          HySymbol('ast.Load')])]),
      HyExpression([
        HySymbol('ast.Name'),
        HyKeyword('id'),
        'y',
        HyKeyword('ctx'),
        HyExpression([
          HySymbol('ast.Load')])]),
      HyExpression([
        HySymbol('ast.Name'),
        HyKeyword('id'),
        'z',
        HyKeyword('ctx'),
        HyExpression([
          HySymbol('ast.Load')])])]),
    HyKeyword('keywords'),
    HyList()])])

(setv rel-res (run 1 [hy-ast] (hy-py-asto hy-ast py-ast-exa)))
(setv ast-res (get rel-res 0 0))
ast-res

[HyExpression([
  HySymbol('HySymbol'),
  'print']), HyExpression([
  HySymbol('HySymbol'),
  'x']), HyExpression([
  HySymbol('HySymbol'),
  'y']), HyExpression([
  HySymbol('HySymbol'),
  'z'])]