I ported the unifier posted by Norvig in Common Lisp to Clojure...
original lisp here: http://norvig.com/paip/unify.lisp
from the paip directory it also uses code in patmatch and auxfns
files.
this revealed some things that I don't particularly care for in
Clojure, and some things I'm clearly unsure how to correctly
implement, so I would appreciate review and feedback on this code as
an exercise, but also because it's going to go into heavy use soon.
(There are some helper functions that are just there to make porting
Norvig's code easier, also to raise the level of abstraction -
arguably I shouldn't have used contains? and had another helper like
Norvig did.)
major questions
1. this is ugly: (and (seq? x) (not (empty? x))) in common lisp you
just use consp is there no equivalent in clojure? there is (seq x)
but that barfs if it's given a symbol. The loss of the cleanness of
iterating/recursing until you hit nil is unfortunate (it made for some
elegant lisp code)
2. there are self calls and mutual calls throughout - which could
create a stack problem. advice for how to get around this?
specifically calls like the following seem hard to fix, or at least I
don't know the "duh" way to do it (I always just let my lisp compiler
do all the work for me)
;inside of occurs-check:
(or (occurs-check var (first x) bindings)
(occurs-check var (next x) bindings))
2'. I'm to understand that next is now preferred to rest? (which is an
unfortunate name at least for my lisp mind, since it seems like it
should be returning an element instead of rest - but I'll learn
eventually)
minor questions:
a. what's the preferred indenting style for cond?
b. is def the correct way to introduce constants and thread safe
places to bind over?
c. is that the correct / best / preferred way to set default values
for the optional parameter in unify?
EXAMPLES:
> (unify '(a b) '(a b))
{}
> (unify '?a '(b))
{?a (b)}
> (unify '(?a ?b) '((q) ?b))
{?a (q)}
>(unify '(?a ?b) '(b))
nil
> (unify '(?a ?b) '(?b))
nil
CODE:
(defn variable? [x]
"Is x a variable (a symbol beginning with `?')?"
(and (symbol? x)
(= (nth (name x) 0) \?)))
(def fail nil)
(def no-bindings {})
(def *occurs-check* true) ;"perform the occurs check?"
(defn extend-bindings [var val bindings]
(assoc bindings var val))
(defn lookup [var bindings]
(get bindings var))
(declare unify unify-variable occurs-check)
(defn unify
"See if x and y match with given bindings."
([x y] (unify x y no-bindings))
([x y bindings]
(cond
(= bindings fail) fail
(= x y) bindings
(variable? x) (unify-variable x y bindings)
(variable? y) (unify-variable y x bindings)
(and (seq? x) (not (empty? x)) (seq? y) (not (empty? y)))
;(and (seq x) (seq y)) ;this is consp in Norvig's code
(unify (next x) (next y)
(unify (first x) (first y) bindings))
true fail)))
(defn unify-variable [var x bindings]
"Unify var with x, using (and maybe extending) bindings."
(cond (contains? bindings var)
(unify (lookup var bindings) x bindings)
(and (variable? x) (contains? bindings x))
(unify var (lookup x bindings) bindings)
(and *occurs-check* (occurs-check var x bindings))
fail
true
(extend-bindings var x bindings)))
(defn occurs-check [var x bindings]
"Does var occur anywhere inside x?"
(cond (= var x) true
(and (variable? x) (contains? bindings x))
(occurs-check var (lookup x bindings) bindings)
(and (seq? x) (not (empty? x)))
;(seq x) ;consp would be nice here instead of the above
(or (occurs-check var (first x) bindings)
(occurs-check var (next x) bindings))
true false))
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
