Re: Building Unification Table - tranforming prolog like notation into lisp notation

On Jan 29, 6:22 pm, Madhu <enom...@xxxxxxxx> wrote:
* Marco Antoniotti Wrote on Tue, 29 Jan 2008 05:30:12 -0800 (PST):
| On Jan 29, 11:49 am, Slobodan Blazeski wrote:
|> There is one case that I didn't quite understand . Ok let me show you
|> the source of this problem. I'm trying to implement Alin Suciu's Yet
|> another efficient unification algorithm (4 pages). It's described
|> in:http://arxiv.org/PS_cache/cs/pdf/0603/0603080v1.pdfhere's an
|> implementation in chttp://paste.lisp.org/display/54935 The question
|> above is simplified from step 1/ page 1 of the paper. The notation
|> problem comes from tranlating prolog notation into lisp notation.

|> The original notation : p(Z,h(Z,W),f(W)) p(f(X),h(Y,f(a)),Y)
|> Lisp notation: (p Z (h Z W) (f W)) (p (f X) (h Y (f a)) Y)
|
| This is already wrong in ANSI Common Lisp. It will work in Franz
| "Modern" setup but then you will loose other people. Your notation
| turns out to be (P Z (H Z W) (F W)) inside the CL environment. Prolog
| uses (as you may know) capitalized symbols for logical variables.
| You do not have that capability in CL. Hence you *must* resort to
| something like
|
| (p ?z (h ?z ?w) (f ?w))

Or you could just use symbols with lowercase names as |a|:

(defun var-p (symbol)
"Check if SYMBOL is of Suciu's type VAR. Our CL convention is variables are
upper case lisp symbols."
(upper-case-p (elt (symbol-name symbol) 0)))

(deftype variable-term () '(satisfies var-p))

(defun str-p (symbol)
"Check if SYMBOL is of Suciu's type STR. Our convention is that constants
and functors are lower case lisp symbols."
It more Prologish but harder to impose convetion to || the STRs.
Usually there's fewer variables
than STRs. Also the unification list may come from some other
computation, in order to cope with our convention programmer would
have to travel the whole list andlowercase all the symbols.
It's probably better to stick with ? for practical reasons.
(lower-case-p (elt (symbol-name symbol) 0)))

(deftype constant-term () '(satisfies str-p))

;; Here is a quickly done stack based solution for the problem Slobodan
;; originally posted. the iter based solution posted elsewhere in this
;; thread just hurt my eyes too much

;; it should be trivial to convert this function to a stack based one:
(defun principal-term (x)
"Returns the main-functor or variable or constant"
(etypecase x
(cons (main-functor (car x)))
(atom x)))

(defstruct composite-term str indices)

(defun slobodan (x &aux stack result
(var-table (make-hash-table))
(str-alist nil)
(counter 0))
(flet ((rec (item)
(cond ((atom item)
(etypecase item
(composite-term
(push (cons (composite-term-str item) counter) str-alist)
(push (list (composite-term-str item)
counter
(mapcar (lambda (x)
(setq x (principal-term x))
(cond ((str-p x)
(cdr (assoc x str-alist)))
((var-p x)
(gethash x var-table))))
(composite-term-indices item)))
result)
(incf counter))
(variable-term
(unless (gethash item var-table)
(setf (gethash item var-table) counter)
(push (list item counter nil) result)
(incf counter)))
(constant-term
(push (cons item counter) str-alist)
(push (list item counter nil) result)
(incf counter))))
(t
(assert (atom (car item)))
(assert (str-p (car item)))
(push (make-composite-term :str (car item)
:indices (cdr item))
stack)
(loop for elem in (cdr item) do (push elem stack))))))
(assert (= (length x) 2))
(rec (car x))
(rec (cadr x))
(loop while stack do (rec (pop stack)))
(nreverse result)))

* (slobodan '((|p| Z (|h| Z W) (|f| W)) (|p| (|f| X) (|h| Y (|f| |a|)) Y)))

=> ((Y 0 NIL) (|a| 1 NIL) (|f| 2 (1)) (|h| 3 (0 2)) (X 4 NIL) (|f| 5 (4))
(|p| 6 (5 3 0)) (W 7 NIL) (|f| 8 (7)) (Z 9 NIL) (|h| 10 (9 7))
(|p| 11 (9 10 8)))

--
Madhu
Cool solution something like I started to write,just if I made it
work. You didn't pasted the definition of main-functor, could you
please post solution on lisp paste you ca annotate iter based solution
at http://paste.lisp.org/display/54994 for comparasion.

thanks
Slobodan
.

Relevant Pages

  • Re: Building Unification Table - tranforming prolog like notation into lisp notation
    ... ;; Here is a quickly done stack based solution for the problem Slobodan ... (defstruct composite-term str indices) ... (push (cons (composite-term-str item) ...
    (comp.lang.lisp)
  • Re: Is it wise to push all-in early in a tournament?
    ... The best times to make a push play ... But why call when you can push and take down a nice pot when your opponent ... But remember that if this "big bet" is a significant portion of your stack, ... I consider it my goal in any tournament to do the latter as much as ...
    (rec.gambling.poker)
  • Re: Is it wise to push all-in early in a tournament?
    ... whether or not the rest of the table is splashing chips around. ... I may push more than I want to and you may be more conservative than ... Do I want to play this opponent after the flop? ... push at anytime and I may not want to risk my stack on a suckout when I ...
    (rec.gambling.poker)
  • Virtual machine: assembly instructions
    ... push; Push the address of the first variable onto the stack ... itof: convert integer to float ... If top+1 of int stack is less than top; push true else push false ...
    (comp.programming)
  • Re: Using C and Assembly code: 64Bit Calling convention
    ... RSP holds 1210 at this point. ... 0's local stack area. ... you start to push or move anything onto the stack. ... The only exception from this rule ...
    (comp.lang.asm.x86)