I need to collect all the atoms from a given input (atom/list/tree)
under below constraints:
a. Atoms should be collected in reverse order -right to left
b. Atom should be assigned an index the way I find them in the tree -
right to left that increments by one for each successive element
encountered
c. Atom should have a list of all indexes belonging to a list if it's
a first atom in that list, nil otherwise
>x
((x 0 nil))
>(g x)
((x 0 nil) (g 1 (0)))
>(g x a)
((a 0 nil) (x 1 nil) (g 2 (0 1)))
>(f x (g t 2) (y 2))
((2 0 nil) (y 1 (0)) (2 3 nil) (t 4 nil) (g 5 (3 4)) (x 6 nil) (f 7 (1
5 6)))
thanks
Slobodan
Slobodan Blazeski <·················@gmail.com> writes:
Sounds suspiciously like homework to me ;)
> I need to collect all the atoms from a given input (atom/list/tree)
> under below constraints:
> a. Atoms should be collected in reverse order -right to left
> b. Atom should be assigned an index the way I find them in the tree -
> right to left that increments by one for each successive element
> encountered
> c. Atom should have a list of all indexes belonging to a list if it's
> a first atom in that list, nil otherwise
1. Keep a counter of unique atoms encountered.
2. Use a hash table to map indices to atoms
3. Use recursive descent and make sure to have the recursive call be
before actually doing anything with the current value.
> >x
> ((x 0 nil))
>
> >(g x)
> ((x 0 nil) (g 1 (0)))
>
> >(g x a)
> ((a 0 nil) (x 1 nil) (g 2 (0 1)))
>
> >(f x (g t 2) (y 2))
> ((2 0 nil) (y 1 (0)) (2 3 nil) (t 4 nil) (g 5 (3 4)) (x 6 nil) (f 7 (1
> 5 6)))
--
Thomas A. Russ, USC/Information Sciences Institute
On Jan 29, 2:39 am, ····@sevak.isi.edu (Thomas A. Russ) wrote:
> Sounds suspiciously like homework to me ;)
If I don't pass my AI intro with Lisp course I won't be able to play
football anymore 8.-(, please help me sir, the team depends on me.
On Jan 29, 1:18 am, Maciej Katafiasz <········@gmail.com> wrote:
>
> You didn't specify the rules precisely.
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.pdf
here's an implementation in c http://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)
What'c conversion from lisp's ((f) a) into prolog-like notation?
cheers
Slobodan
On Jan 29, 11:49 am, Slobodan Blazeski <·················@gmail.com>
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.pdf
> here'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
(with-logical-variables (z w) (do-something-with '(p z (h z w) (f
w))))
> What'c conversion from lisp's ((f) a) into prolog-like notation?
The only semi-reasonable (an probably not even that) conversion is
F(a)
note that F is a predicate variable. Other possibility is [f, a].
The problem is that Prolog terms have a very clear syntax and the
semantics of '(f)' in any side-effect free functional language is that
of a constant (i.e. a 0-arity functional or predicate term.
Cheers
--
Marco
On Jan 29, 2:30 pm, Marco Antoniotti <·······@gmail.com> wrote:
> > 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))
Don't worry I'll use traditional ? question mark prefix for the
variables. I don't use modern image.
>
> > What'c conversion from lisp's ((f) a) into prolog-like notation?
>
> The only semi-reasonable (an probably not even that) conversion is
>
> F(a)
>
> note that F is a predicate variable. Other possibility is [f, a].
> The problem is that Prolog terms have a very clear syntax and the
> semantics of '(f)' in any side-effect free functional language is that
> of a constant (i.e. a 0-arity functional or predicate term.
>
> Cheers
> --
> Marco
I was thinking of adding list as argument to every predicate just in
order to stay consistent thus:
p(Z,h(Z,W),f(W)) |-> (list p ?Z (list h ?Z ?W) (list f ?W)) and
keeping consistency with lists that have a list as first argument
(list (list a)) . Thus making a rule that all lists start with an
atom.
cheers
Slobodan
On Jan 29, 4:13 pm, Slobodan Blazeski <·················@gmail.com>
wrote:
>
> I was thinking of adding list as argument to every predicate just in
> order to stay consistent thus:
> p(Z,h(Z,W),f(W)) |-> (list p ?Z (list h ?Z ?W) (list f ?W)) and
> keeping consistency with lists that have a list as first argument
> (list (list a)) . Thus making a rule that all lists start with an
> atom.
You *do* realize that that is *exactly* what CL-UNIFICATION does. :)
Cheers
--
Marco
On Jan 29, 7:31 pm, Marco Antoniotti <·······@gmail.com> wrote:
> > I was thinking of adding list as argument to every predicate just in
> > order to stay consistent thus:
> > p(Z,h(Z,W),f(W)) |-> (list p ?Z (list h ?Z ?W) (list f ?W)) and
> > keeping consistency with lists that have a list as first argument
> > (list (list a)) . Thus making a rule that all lists start with an
> > atom.
>
> You *do* realize that that is *exactly* what CL-UNIFICATION does. :)
Do you hold a patent?
Slobodan
On Jan 29, 7:31 pm, Marco Antoniotti <·······@gmail.com> wrote:
> > I was thinking of adding list as argument to every predicate just in
> > order to stay consistent thus:
> > p(Z,h(Z,W),f(W)) |-> (list p ?Z (list h ?Z ?W) (list f ?W)) and
> > keeping consistency with lists that have a list as first argument
> > (list (list a)) . Thus making a rule that all lists start with an
> > atom.
>
> You *do* realize that that is *exactly* what CL-UNIFICATION does. :)
Seriously now, if I change 4th line from below from Maciej solution
into this
(iter (for (item . more-p) on (nreverse (cons 'list item/s)))
I got :
(collect '(((p)) X))
((X 0 NIL) (P 1 NIL) (LIST 2 (1)) (LIST 3 (2)) (LIST 4 (3 0)))
Is this what cl-unification does?
Maciej is it too much hassle to add two remaining columns VAR/STR and
ARITY, and put index in front. I need some time to grok your solution:
For VAR/STR you can use below functions if you want:
(defun var? (x) ; Variables are symbols prefixed with question mark
(and (symbolp x) (eq (char (symbol-name x) 0) #\?)))
(defun var-str (x) ;
(if (var? x) 'var 'str))
Arity represent the length of the list.
According to LIST added notation mentioned above only list *could*
have arity greater than 0.
(collect '((p 1) ?x))
((0 ?X VAR 0 NIL) (1 1 STR 0 NIL) (2 P STR 0 NIL) (3 LIST STR 2 (2 1))
(4 LIST 2 (3 0)))
thanks
Slobodan
From: Maciej Katafiasz
Subject: Re: Building Unification Table - tranforming prolog like notation into lisp notation
Date:
Message-ID: <fno2b8$1jm$5@news.net.uni-c.dk>
Den Tue, 29 Jan 2008 11:22:18 -0800 skrev Slobodan Blazeski:
> Maciej is it too much hassle to add two remaining columns VAR/STR and
> ARITY, and put index in front. I need some time to grok your solution:
> For VAR/STR you can use below functions if you want: (defun var? (x) ;
> Variables are symbols prefixed with question mark
> (and (symbolp x) (eq (char (symbol-name x) 0) #\?)))
>
> (defun var-str (x) ;
> (if (var? x) 'var 'str))
>
> Arity represent the length of the list. According to LIST added notation
> mentioned above only list *could* have arity greater than 0.
> (collect '((p 1) ?x))
> ((0 ?X VAR 0 NIL) (1 1 STR 0 NIL) (2 P STR 0 NIL) (3 LIST STR 2 (2 1))
> (4 LIST 2 (3 0)))
I have annotated my paste with a new version
(http://paste.lisp.org/display/54994#1), it seems to be working correctly
for the example you gave.
Cheers,
Maciej
On Jan 29, 9:29 pm, Maciej Katafiasz <········@gmail.com> wrote:
> Den Tue, 29 Jan 2008 11:22:18 -0800 skrev Slobodan Blazeski:
>
> > Maciej is it too much hassle to add two remaining columns VAR/STR and
> > ARITY, and put index in front. I need some time to grok your solution:
> > For VAR/STR you can use below functions if you want: (defun var? (x) ;
> > Variables are symbols prefixed with question mark
> > (and (symbolp x) (eq (char (symbol-name x) 0) #\?)))
>
> > (defun var-str (x) ;
> > (if (var? x) 'var 'str))
>
> > Arity represent the length of the list. According to LIST added notation
> > mentioned above only list *could* have arity greater than 0.
> > (collect '((p 1) ?x))
> > ((0 ?X VAR 0 NIL) (1 1 STR 0 NIL) (2 P STR 0 NIL) (3 LIST STR 2 (2 1))
> > (4 LIST 2 (3 0)))
>
> I have annotated my paste with a new version
> (http://paste.lisp.org/display/54994#1), it seems to be working correctly
> for the example you gave.
>
> Cheers,
> Maciej
Thanks, after looking at the actual unification algorithm it needs
unification table and indices of both expressions.I modified collect
http://paste.lisp.org/display/54994#2 to accept two arguments and
return unification table, index of second and index of first
expression. Also I keep terms into a structure for easier bookkeeping.
You can test it with adding below before values to see that it return
the correct table as in paper
(loop for key being the hash-keys of table
using (hash-value value)
do (print (list key (term-functor value)
(term-type value)
(term-arity value)
(term-components value))))
; consing ;list is deliberately removed for easier comparasion with
paper's table for errors
Considering that indexes are natural numbers anyway do you think that
I should use adjustable vector instead of hash-table?
I want to understand and simplify the description of the algorithm,
now it looks sort of C-ish.
cheers
Slobodan
From: Madhu
Subject: Re: Building Unification Table - tranforming prolog like notation into lisp notation
Date:
Message-ID: <m3prvkfswo.fsf@robolove.meer.net>
* 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.pdf here'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."
(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
On Jan 29, 6:22 pm, Madhu <·······@meer.net> 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
From: Madhu
Subject: Re: Building Unification Table - tranforming prolog like notation into lisp notation
Date:
Message-ID: <m3lk68foiq.fsf@robolove.meer.net>
* Slobodan Blazeski
Wrote on Tue, 29 Jan 2008 10:22:58 -0800 (PST):
| On Jan 29, 6:22 pm, Madhu wrote:
[...]
|> ;; 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
Done too quickly. There are errors,
[...]
|| 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.
That was a typo: s/main-functor/principal-term. it should read:
|> (defun principal-term (x)
|> "Returns the main-functor or variable or constant"
|> (etypecase x
(cons (principal-term (car x)))
|> (atom x)))
I think there is another problem with the function if the same name is
used for a functor and a constant : I used a single alist to keep track
of both constant-terms names and composite-term main-functor names ->
counter-index. I should probably use 2 separate alists, str-alist for
constants and a fun-alist for composite terms. The lambda in the mapcar
would need to be modified to look up the counter. Modifications inline:
|> (defun slobodan (x &aux stack result
|> (var-table (make-hash-table))
|> (str-alist nil)
(fun-alist nil)
|> (counter 0))
|> (flet ((rec (item)
|> (cond ((atom item)
|> (etypecase item
|> (composite-term
(push (cons (composite-term-str item) counter)
fun-alist)
|> (push (list (composite-term-str item)
|> counter
|> (mapcar (lambda (x)
|> (cond
((consp x)
(cdr (assoc
(principal-term x)
fun-alist)))
((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)))
I'll have to think about the correctness of this a bit more before i'm
convinced. So I'll defer posting to lisppaste :)
--
Madhu
From: Maciej Katafiasz
Subject: Re: Building Unification Table - tranforming prolog like notation into lisp notation
Date:
Message-ID: <fnnrvc$1jm$4@news.net.uni-c.dk>
Den Tue, 29 Jan 2008 22:52:47 +0530 skrev Madhu:
> * (slobodan '((|p| Z (|h| Z W) (|f| W)) (|p| (|f| X) (|h| Y (|f| |a|))
> Y)))
The function main-functor is undefined.
[Condition of type undefined-function]
Cheers,
Maciej
On 29 Jan, 10:49, Slobodan Blazeski <·················@gmail.com>
wrote:
> On Jan 29, 2:39 am, ····@sevak.isi.edu (Thomas A. Russ) wrote:> Sounds suspiciously like homework to me ;)
>
> If I don't pass my AI intro with Lisp course I won't be able to play
> football anymore 8.-(, please help me sir, the team depends on me.
>
> On Jan 29, 1:18 am, Maciej Katafiasz <········@gmail.com> wrote:
>
>
>
> > You didn't specify the rules precisely.
>
> 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.pdf
> here'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)
> What'c conversion from lisp's ((f) a) into prolog-like notation?
>
> cheers
> Slobodan
The concept of efficient w.r.t. unification can be misleading.
It can refer to the O(n) growth in time taken in relation to
the complexity of the input. But 'more efficient' in this sense
does not always mean 'faster' in the programmer's sense if the
basic algorithm is a heavy user of resources. A slow growing
but slow algorithm can in practice be beaten by a fast-growing
but fast algorithm in all but the worse cases. An anecdotal
remark by Professor Tony Cohn many years ago on the Martelli-Montanari
algorithm was exactly to this effect - that M-M turned out to be
actually slower for most cases than the standard approach. I've not
verified that.
This is not to put you off, because ascertaining the facts about
this sort of thing *does* require exactly the empirical approach you
are taking. Bon voyage.
Mark
On Jan 29, 3:09 pm, Mark Tarver <··········@ukonline.co.uk> wrote:
> The concept of efficient w.r.t. unification can be misleading.
> It can refer to the O(n) growth in time taken in relation to
> the complexity of the input. But 'more efficient' in this sense
> does not always mean 'faster' in the programmer's sense if the
> basic algorithm is a heavy user of resources. A slow growing
> but slow algorithm can in practice be beaten by a fast-growing
> but fast algorithm in all but the worse cases. An anecdotal
> remark by Professor Tony Cohn many years ago on the Martelli-Montanari
> algorithm was exactly to this effect - that M-M turned out to be
> actually slower for most cases than the standard approach. I've not
> verified that.
>
> This is not to put you off, because ascertaining the facts about
> this sort of thing *does* require exactly the empirical approach you
> are taking. Bon voyage.
>
> Mark
I've have such experiences with c++ STL, it guarantees certain
complexity like O(logn) but also sometimes goes with huge constant
that renders them virtually useless under certain circumstences.
Sometimes the streightforward way is the best way, but you never know
untill you try it.
Actually in complex programs it's more about implementation than
algorithm, there was a story that certain algorithm was of O(n^3) but
only in 0.01% of cases, the rest 99.99% were lightning fast, and
programmer didn't even think twice finding a better solution, the
concentrated on memoizing the slow results and let the unlucky
customers go figure up why the systems hates them.
The beauty in the modular design in to have both implementations under
the hood and gain knowledge what can they do under real life
curcumstances.
cheers
Slobodan
From: Maciej Katafiasz
Subject: Re: Building Unification Table - tranforming prolog like notation into lisp notation
Date:
Message-ID: <fnnakh$t4b$3@news.net.uni-c.dk>
Den Tue, 29 Jan 2008 02:49:20 -0800 skrev Slobodan Blazeski:
> On Jan 29, 1:18 am, Maciej Katafiasz <········@gmail.com> wrote:
>>
>> You didn't specify the rules precisely.
>
> 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.pdf here's an
> implementation in c http://paste.lisp.org/display/54935 The question
> above is simplified from step 1/ page 1 of the paper.
I see. I've read the relevant bit, and changed the code to follow the
description. The behaviour you want that was missing from your original
description is:
d. Items that aren't atoms shouldn't be indexed, but their first elements
should be referenced by their parent's index list
e. Atoms should be collected uniquely -- all but first occurence
shouldn't produce entries in the result list, and references inserted
into parents' index lists should be indexes of the first occurence.
Now I get this, running the example as given in the paper:
> (collect '((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)))
If you read it side-by-side with the table in the paper, you can see the
result is identical.
Cheers,
Maciej
(defun collect (item/s)
(let ((counter -1)
(vars (make-hash-table))
ticker-fn
get-ticks-fn)
(labels ((tick (&optional idx)
(funcall ticker-fn idx))
(get-ticks ()
(funcall get-ticks-fn))
(count* ()
(incf counter))
(has (item)
(gethash item vars))
(record (item idx)
(setf (gethash item vars) idx))
(make-ticker ()
(let (ticks
(old-ticker ticker-fn)
(old-get get-ticks-fn))
(setf ticker-fn
(lambda (&optional idx)
(let ((c (or idx (count*))))
(push c ticks)
c)))
(setf get-ticks-fn
(lambda ()
(setf ticker-fn old-ticker
get-ticks-fn old-get)
;; Push ourselves to the parent
(tick (car ticks))
(cdr ticks)))))
(collect* (item/s more-p compound-p)
(cond
((atom item/s)
(if (and (not compound-p)
(has item/s))
;; Non-unique occurence -- only record
;; ourselves, but don't output anything
(null (tick (has item/s)))
(progn
(unless compound-p (record item/s (count*)))
(list
(list item/s (tick (has item/s))
(unless more-p (get-ticks)))))))
((listp item/s)
(make-ticker)
(prog1
(iter (for (item . more-p) on (nreverse item/s))
(appending (collect* item more-p (not more-
p)))))))))
(make-ticker)
(collect* item/s nil nil))))
On Jan 29, 2:44 pm, Maciej Katafiasz <········@gmail.com> wrote:
Maciej could you please repost your code in lisp paste http://paste.lisp.org/
I'm unable to compile it? Are you missing something or something wrong
with the paste.
Compilation aborted due to error in (SUBFUNCTION (LABELS COLLECT*)
COLLECT):
In a call to LENGTH: MORE-P is not of type SEQUENCE.
BTW your use of labels looks like a heavy wizardry, I've never tried
more than 2 local functions. It has a WOW effect.
cheers
Slobodan
From: Maciej Katafiasz
Subject: Re: Building Unification Table - tranforming prolog like notation into lisp notation
Date:
Message-ID: <fnnhen$1jm$1@news.net.uni-c.dk>
Den Tue, 29 Jan 2008 07:05:23 -0800 skrev Slobodan Blazeski:
> On Jan 29, 2:44 pm, Maciej Katafiasz <········@gmail.com> wrote:
>
> Maciej could you please repost your code in lisp paste
> http://paste.lisp.org/ I'm unable to compile it? Are you missing
> something or something wrong with the paste.
No. You need to (use-package :iterate) (forgot to mention), but otherwise
it's completely standalone.
Lisppaste:
http://paste.lisp.org/display/54994
It's got one change compared to my post, I removed spurious PROG1 use
which I forgot to clean up.
> Compilation aborted due to error in (SUBFUNCTION (LABELS COLLECT*)
> COLLECT):
> In a call to LENGTH: MORE-P is not of type SEQUENCE.
Do you have ITERATE imported? If you don't, you'll get that error.
> BTW your use of labels looks like a heavy wizardry, I've never tried
> more than 2 local functions. It has a WOW effect.
Oh, it's just a bunch of operations defined on shared state, so it's very
handy to define them with LABELS. It could be split out, but they'd have
to carry around their state around with them, which is ugly. If you look
at the functions, they're mostly very small, so it's pure convenience to
avoid saying FUNCALL a lot. The only non-trivial ones are COLLECT* (which
does the traversal) and MAKE-TICKER (ticker takes care of recording the
references to sub-clauses for the parent). These are the actual
workhorses.
Cheers,
Maciej
On Jan 29, 4:41 pm, Maciej Katafiasz <········@gmail.com> wrote:
>
> Do you have ITERATE imported? If you don't, you'll get that error.
I missed that, everything is cool now.
>
> > BTW your use of labels looks like a heavy wizardry, I've never tried
> > more than 2 local functions. It has a WOW effect.
>
> Oh, it's just a bunch of operations defined on shared state, so it's very
> handy to define them with LABELS. It could be split out, but they'd have
> to carry around their state around with them, which is ugly. If you look
> at the functions, they're mostly very small, so it's pure convenience to
> avoid saying FUNCALL a lot. The only non-trivial ones are COLLECT* (which
> does the traversal) and MAKE-TICKER (ticker takes care of recording the
> references to sub-clauses for the parent). These are the actual
> workhorses.
>
> Cheers,
> Maciej
I've never encountered such style, prefer to keep my functions global
for separate testing but it makes sense what you say to keep state in
them, I'll study this a bit.
thanks again
Slobodan
From: Maciej Katafiasz
Subject: Re: Building Unification Table - tranforming prolog like notation into lisp notation
Date:
Message-ID: <fnnj4i$1jm$3@news.net.uni-c.dk>
Den Tue, 29 Jan 2008 07:57:04 -0800 skrev Slobodan Blazeski:
> I've never encountered such style, prefer to keep my functions global
> for separate testing but it makes sense what you say to keep state in
> them, I'll study this a bit.
It's actually very common. It's often called closure weaving (or closure
web), because you close over the interesting state/ops and let the
compiler figure out how to pass it around. Notice how I employ that
technique to make keeping track of references easy, on each level, you
only have to call TICK, and it'll automatically push into the right list.
It can also be very efficient, smart use of closures is one of the
reasons packages such as CL-PPCRE can match or surpass optimised native
implementations in performance.
Cheers,
Maciej
Den Mon, 28 Jan 2008 12:37:08 -0800 skrev Slobodan Blazeski:
> I need to collect all the atoms from a given input (atom/list/tree)
> under below constraints:
> a. Atoms should be collected in reverse order -right to left b. Atom
> should be assigned an index the way I find them in the tree - right to
> left that increments by one for each successive element encountered
> c. Atom should have a list of all indexes belonging to a list if it's a
> first atom in that list, nil otherwise
You didn't specify the rules precisely. From the examples you gave, I
inferred that you want non-atom items to be counted and their indexes
collected, but items themselves not recorded to the output list. Ie.
> (x (y))
((y 0 nil) (x 2 (1)), and not ((y 0 nil) (x 0 nil))
>>(f x (g t 2) (y 2))
> ((2 0 nil) (y 1 (0)) (2 3 nil) (t 4 nil) (g 5 (3 4)) (x 6 nil) (f 7 (1 5
> 6)))
If my guess was correct, then this example is incorrect, it should've
been:
((2 0 nil) (y 1 (0)) (2 3 nil) (t 4 nil) (g 5 (3 4)) (x 7 nil)
(f 8 (2 6 7)))
Code below. Names with * are there because of clashes with CL and
ITERATE, respectively. That prompts a style question: aside from the
clash, is it good style to FLET FUNCNAME inside FUNCAME's definition (as
opposed to FLETting FUNCNAME-HELPER or similar)?
It's written recursively, so if you have really deep trees, it might be
unsuitable. But it's pretty fast, on my machine it collects 100M+ items
in under 0.1s.
Cheers,
Maciej
(defun collect (item/s)
(let ((counter -1)
ticker-fn
get-ticks-fn)
(labels ((tick ()
(funcall ticker-fn))
(get-ticks ()
(funcall get-ticks-fn))
(count* ()
(incf counter))
(make-ticker ()
(let (ticks
(old-ticker ticker-fn)
(old-get get-ticks-fn))
(setf ticker-fn
(lambda ()
(let ((c (count*)))
(push c ticks)
c)))
(setf get-ticks-fn
(lambda ()
(setf ticker-fn old-ticker
get-ticks-fn old-get)
;; CDR to avoid collecting extra indexes for
;; terminal elements
(nreverse (cdr ticks))))))
(collect* (item/s more-p)
(cond
((atom item/s)
(list (list item/s (tick) (unless more-p (get-ticks)))))
((listp item/s)
(make-ticker)
(prog1
(iter (for (item . more-p) on (nreverse item/s))
(appending (collect* item more-p)))
(tick))))))
(make-ticker)
(collect* item/s nil))))