I realize that this is off topic to c.l.lisp as it has nothing to do
with lisp world domination, Python, Ruby, or Discommodiously
Defenestrated Toad (DDT) Consulting...
I've started playing with adding DCGs to Allegro Prolog (sexp Prolog?
sexp logic?) by way of learning about DCGs. I should probably learn
about them first before I try to add them. <shrug> I have a very
simple example working with the following code but I know that it is
buggy. I thought I'd put this out there to see if anyone was interested
in commenting on it or improving it.
(defmacro ---> (&rest term)
`(<-- ,@(rewrite-dcg-term term)))
(defmacro --> (&rest term)
`(<- ,@(rewrite-dcg-term term)))
(defun rewrite-dcg-term (term)
(let ((arg-rest (gensym "?REST/")))
(labels
((lemma (clause-1 clause-2 rest-clauses arg-1 arg-2 result)
(cond ((null clause-1) result)
((dcg-nonterminal-p clause-2)
(let ((next-clause-1 clause-2)
(next-clause-2 (car rest-clauses))
(next-rest-clauses (cdr rest-clauses)))
(lemma next-clause-1 next-clause-2 next-rest-clauses
(next-arg-1 arg-1 arg-2)
(next-arg-2 rest-clauses)
(let ((arg-2/rest (or arg-2 arg-rest)))
(cons `(,@clause-1 ,arg-1 ,arg-2/rest)
result)))))
((dcg-terminal-p clause-2)
(let ((next-clause-1 (car rest-clauses))
(next-clause-2 (cadr rest-clauses))
(next-rest-clauses (cddr rest-clauses)))
(lemma next-clause-1 next-clause-2 next-rest-clauses
(next-arg-1 arg-1 arg-2)
(next-arg-2 next-clause-2)
(let ((arg-2/rest
(or (and rest-clauses arg-2)
arg-rest)))
(cons `(,@clause-1 ,arg-1
(,@(car clause-2) . ,arg-2/rest))
result)))))
(t (error "~S is neither nonterminal nor terminal."
clause-2))))
(next-arg-1 (arg-1 arg-2) (or arg-2 arg-1))
(next-arg-2 (clause) (if clause (gensym "?LIST/") arg-rest)))
(when (dcg-terminal-p (car term))
(error "DCG term ~S must start with a nonterminal clause. ~
Head clause is terminal ~S."
term (car term)))
(destructuring-bind (clause-1 clause-2 &rest rest-clauses) term
(if (and (dcg-nonterminal-p clause-1) (dcg-terminal-p clause-2)
(null rest-clauses))
;; <frown> Special case handling here is fugly...
`((,@clause-1 (,@(car clause-2) . ,arg-rest) ,arg-rest))
(as nreverse
(lemma clause-1 clause-2 rest-clauses
(gensym "?LIST/") nil
'())))))))
(defun dcg-terminal-p (x)
"Corresponds to < x > in BNF. [x] in Prolog. ((x)) in sexp
Prolog."
(and (listp x) (listp (car x)) (null (cdr x))
(every #'atom (car x))))
(defun dcg-nonterminal-p (x)
(and (listp x) (symbolp (car x))))
;;; Some examples elided for brevity
(defparameter *ex7*
'((move) (step) (move)))
(defparameter *ex8*
'((step) ((up))))
(defparameter *ex9*
'((step) ((down))))
(defparameter *ex10*
'((s) ((a)) ((b))))
This works with one of the really simple examples.
USER> (rewrite-dcg-term *ex7*)
((MOVE #:?LIST/375 #:?REST/374) (STEP #:?LIST/375 #:?LIST/376)
(MOVE #:?LIST/376 #:?REST/374))
USER> (rewrite-dcg-term *ex8*)
((STEP (UP . #:?REST/377) #:?REST/377))
USER> (rewrite-dcg-term *ex9*)
((STEP (DOWN . #:?REST/378) #:?REST/378))
USER> (---> (move) (step))
MOVE
USER> (--> (move) (step) (move))
MOVE
USER> (---> (step) ((up)))
STEP
USER> (--> (step) ((down)))
STEP
USER> (?- (move (down down up) ()))
Yes
No.
; No value
USER> (?- (move (down up down) ()))
Yes
No.
; No value
USER> (?- (move ?s ()))
?S = (UP)
?S = (DOWN)
?S = (UP UP)
?S = (UP DOWN)
?S = (UP UP UP)
?S = (UP UP DOWN)
?S = (UP UP UP UP)
?S = (UP UP UP DOWN).
No.
; No value
However, I know that is doesn't work for another simple example.
USER> (rewrite-dcg-term *ex10*)
((S #:?LIST/438 (A . #:?REST/437)) ((B) #:?LIST/438 #:?REST/437))
USER>
On 23 Cze, 21:58, Damien Kick <····@earthlink.net> wrote:
> I realize that this is off topic to c.l.lisp as it has nothing to do
> with lisp world domination, Python, Ruby, or Discommodiously
> Defenestrated Toad (DDT) Consulting...
>
> I've started playing with adding DCGs to Allegro Prolog (sexp Prolog?
> sexp logic?) by way of learning about DCGs. I should probably learn
> about them first before I try to add them. <shrug> I have a very
> simple example working with the following code but I know that it is
> buggy. I thought I'd put this out there to see if anyone was interested
> in commenting on it or improving it.
>
> (defmacro ---> (&rest term)
> `(<-- ,@(rewrite-dcg-term term)))
>
> (defmacro --> (&rest term)
> `(<- ,@(rewrite-dcg-term term)))
>
> (defun rewrite-dcg-term (term)
> (let ((arg-rest (gensym "?REST/")))
> (labels
> ((lemma (clause-1 clause-2 rest-clauses arg-1 arg-2 result)
> (cond ((null clause-1) result)
> ((dcg-nonterminal-p clause-2)
> (let ((next-clause-1 clause-2)
> (next-clause-2 (car rest-clauses))
> (next-rest-clauses (cdr rest-clauses)))
> (lemma next-clause-1 next-clause-2 next-rest-clauses
> (next-arg-1 arg-1 arg-2)
> (next-arg-2 rest-clauses)
> (let ((arg-2/rest (or arg-2 arg-rest)))
> (cons `(,@clause-1 ,arg-1 ,arg-2/rest)
> result)))))
> ((dcg-terminal-p clause-2)
> (let ((next-clause-1 (car rest-clauses))
> (next-clause-2 (cadr rest-clauses))
> (next-rest-clauses (cddr rest-clauses)))
> (lemma next-clause-1 next-clause-2 next-rest-clauses
> (next-arg-1 arg-1 arg-2)
> (next-arg-2 next-clause-2)
> (let ((arg-2/rest
> (or (and rest-clauses arg-2)
> arg-rest)))
> (cons `(,@clause-1 ,arg-1
> (,@(car clause-2) . ,arg-2/rest))
> result)))))
> (t (error "~S is neither nonterminal nor terminal."
> clause-2))))
> (next-arg-1 (arg-1 arg-2) (or arg-2 arg-1))
> (next-arg-2 (clause) (if clause (gensym "?LIST/") arg-rest)))
> (when (dcg-terminal-p (car term))
> (error "DCG term ~S must start with a nonterminal clause. ~
> Head clause is terminal ~S."
> term (car term)))
> (destructuring-bind (clause-1 clause-2 &rest rest-clauses) term
> (if (and (dcg-nonterminal-p clause-1) (dcg-terminal-p clause-2)
> (null rest-clauses))
> ;; <frown> Special case handling here is fugly...
> `((,@clause-1 (,@(car clause-2) . ,arg-rest) ,arg-rest))
> (as nreverse
> (lemma clause-1 clause-2 rest-clauses
> (gensym "?LIST/") nil
> '())))))))
>
> (defun dcg-terminal-p (x)
> "Corresponds to < x > in BNF. [x] in Prolog. ((x)) in sexp
> Prolog."
> (and (listp x) (listp (car x)) (null (cdr x))
> (every #'atom (car x))))
>
> (defun dcg-nonterminal-p (x)
> (and (listp x) (symbolp (car x))))
>
> ;;; Some examples elided for brevity
>
> (defparameter *ex7*
> '((move) (step) (move)))
>
> (defparameter *ex8*
> '((step) ((up))))
>
> (defparameter *ex9*
> '((step) ((down))))
>
> (defparameter *ex10*
> '((s) ((a)) ((b))))
>
> This works with one of the really simple examples.
>
> USER> (rewrite-dcg-term *ex7*)
> ((MOVE #:?LIST/375 #:?REST/374) (STEP #:?LIST/375 #:?LIST/376)
> (MOVE #:?LIST/376 #:?REST/374))
> USER> (rewrite-dcg-term *ex8*)
> ((STEP (UP . #:?REST/377) #:?REST/377))
> USER> (rewrite-dcg-term *ex9*)
> ((STEP (DOWN . #:?REST/378) #:?REST/378))
> USER> (---> (move) (step))
> MOVE
> USER> (--> (move) (step) (move))
> MOVE
> USER> (---> (step) ((up)))
> STEP
> USER> (--> (step) ((down)))
> STEP
> USER> (?- (move (down down up) ()))
> Yes
>
> No.
> ; No value
> USER> (?- (move (down up down) ()))
> Yes
>
> No.
> ; No value
> USER> (?- (move ?s ()))
> ?S = (UP)
>
> ?S = (DOWN)
>
> ?S = (UP UP)
>
> ?S = (UP DOWN)
>
> ?S = (UP UP UP)
>
> ?S = (UP UP DOWN)
>
> ?S = (UP UP UP UP)
>
> ?S = (UP UP UP DOWN).
>
> No.
> ; No value
>
> However, I know that is doesn't work for another simple example.
>
> USER> (rewrite-dcg-term *ex10*)
> ((S #:?LIST/438 (A . #:?REST/437)) ((B) #:?LIST/438 #:?REST/437))
> USER>
I'm not a real prolog guy... also I'm not at a computer with a lisp on
it... in fact I'm an american at a european computer running windows
vista in Polish mode so I'm totally confused about everything (where
is backquote? why did the image on the screen just turn sideways?), so
don't expect a very cogent response this time ;-)
there seems to me to be an inherant problem with what your doing: too
many damned parenthesis! ;-) prolog has the whole goal, goal(a,b)
{normal-prolog-goal}, [terminal-symbol] syntax thing going for it. you
would have to use (goal), ((terminal-symbol)), I-don't-even-know-what-
for-normal-prolog-goals syntax to use your DSGs w/ the lisp-embedded
prolog. really, how often do you see people use list-initial list
syntax outside of a LET or a DO clause? (the arguments of asserta/
assertz/etc don't count because their meant to take bundles of clauses
from the <--/<- macros) there's a reason for this: ugly syntax!
also, I can only speculate what could be wrong with REWRITE-DCG-TERM
(since I have no way to run it at the moment), but replacing the CARs
and CADRs with DESTRUCTURING-BIND's would make your code less
complicated and refactoring it less error prone (also IMHO replacing
the COND with IF* is a good idea)
of course, this line from DCG-TERMINAL-P
(cons `(,@clause-1 ,arg-1 (,@(car clause-2) . ,arg-2/rest))
result)))))
sends up some more immediate red flags...
anyways, perhaps a useful/cool thing to do would be to turn the lisp-
embedded prolog into prolog-embedded-lisp-embedded-prolog ;-) via a
preparser that transformed a nice prolog-y syntax into a proper lisp-
interoperable one, so you could write
(foo a c) :- (bar a b), (baz b c).
bar --> ((dog))
(baz dog) --> ((cat))
etc etc
this would make all the parenthesis easier to handle... (wouldn't a
similar preparser for dystel's distributed emacs lisp or a sexp erlang
be so cool?)
----------------------------------
so... here's a question for YOU prolog guy: what does it mean to have
a body-initial cut
(<-- (foo a c) ! (bar a b) (baz b c))
I'm reading a paper on the train that does this and I don't have a
computer to try it on...
I'm guesing so the head doesn't try to unify more than once?
take care
Nick
········@gmail.com writes:
> there seems to me to be an inherant problem with what your doing: too
> many damned parenthesis! ;-) prolog has the whole goal, goal(a,b)
> {normal-prolog-goal}, [terminal-symbol] syntax thing going for it. you
> would have to use (goal), ((terminal-symbol)), I-don't-even-know-what-
> for-normal-prolog-goals syntax to use your DSGs w/ the lisp-embedded
> prolog. really, how often do you see people use list-initial list
> syntax outside of a LET or a DO clause? (the arguments of asserta/
> assertz/etc don't count because their meant to take bundles of clauses
> from the <--/<- macros) there's a reason for this: ugly syntax!
Parser is a solved problem (see the Dragon Book). Therefore we just
don't care. If you want another syntax, then specify it and have your
favorite parser generator compile it.
Oh, and if you don't have time to read the Dragon Book, here is a
lisper who has read it and will be happy to implement any syntax you
want, for a fee... ;-)
--
__Pascal Bourguignon__ http://www.informatimago.com/
Pascal Bourguignon wrote:
> ········@gmail.com writes:
>> there seems to me to be an inherant problem with what your doing: too
>> many damned parenthesis! ;-) prolog has the whole goal, goal(a,b)
>> {normal-prolog-goal}, [terminal-symbol] syntax thing going for it. you
>> would have to use (goal), ((terminal-symbol)), I-don't-even-know-what-
>> for-normal-prolog-goals syntax to use your DSGs w/ the lisp-embedded
>> prolog.
I hadn't thought about the sexp-logic equivalent of
"{normal_prolog_goal}". I suppose that I could also use something like
the following:
(---> (nonterminal) ([] terminal) ({} normal-sexp-logic))
With (macrolet (([] ...) ({} ...)) ...) having been inserted into the
expansion. But I really think that syntax is the least of my worries.
> Parser is a solved problem (see the Dragon Book). Therefore we just
> don't care. If you want another syntax, then specify it and have your
> favorite parser generator compile it.
This reminds me of a lame joke.
<blockquote cite="http://www.sonoma.edu/Math/faculty/falbo/jokes.html">
A physicist and engineer and a mathematician were sleeping in a hotel
room when a fire broke out in one corner of the room. Only the engineer
woke up he saw the fire, grabbed a bucket of water and threw it on the
fire and the fire went out, then he filled up the bucket again and threw
that bucketfull on the ashes as a safety factor, and he went back to
sleep. A little later, another fire broke out in a different corner of
the room and only the physicist woke up. He went over measured the
intensity of the fire, saw what material was burning and went over and
carefully measured out exactly 2/3 of a bucket of water and poured it
on, putting out the fire perfectly; the physicist went back to sleep. A
little later another fire broke out in a different corner of the room.
Only the mathematician woke up. He went over looked at the fire, he saw
that there was a bucket and he noticed that it had no holes in it; he
turned on the faucet and saw that there was water available. He, thus,
concluded that there was a solution to the fire problem and he went back
to sleep.
</blockquote>
> Oh, and if you don't have time to read the Dragon Book, here is a
> lisper who has read it and will be happy to implement any syntax you
> want, for a fee... ;-)
"You needn't worry about your reward. If money is all that you love,
then that's what you'll receive. Your friend's quite a mercenary. I
wonder if he really cares about anything--or anybody."
As I continue to try to move myself past the half-damaged introduction
to Lisp that I got back in college, I've found that Norvig's Prolog in
PAIP has been my favorite pedagogical examples of Lisp as the
programmable programming language. <sigh> And I should have gone back
to look in PAIP before I even started. Chapter 20, "Unification
Grammars". nallen05 will be happy to see that Norvig uses a bit more
syntax than I was trying to do. He writes Prolog's
s(Sem) --> np(Subj), vp(Pred), {combine(Subj,Pred,Sem)}.
as
(rule (s ?sem) --> (np ?subj) (vp ?pred)
(:test (combine ?subj ?pred ?sem)))
and
verb --> [sleeps].
becomes (if I understand correctly)
(rule (verb) --> (:word sleeps))
<blush> And I find the symbol PROLOG::RULE already in Allegro. So, on
the remote chance that anyone might still be reading, just to give
myself a chance to dig myself into some other holes (and because I've
already written a lot of the following text)... I thought it would be
good to introduce some test suites for rewriting DCG terms.
(defmacro ---> (&rest term)
`(<-- ,@(rewrite-dcg-term term)))
(defmacro --> (&rest term)
`(<- ,@(rewrite-dcg-term term)))
(defun rewrite-dcg-term (term) ...)
(defmacro dcg-test (dcg-term rewrite-term)
(with-gensyms (terms ?terms)
` (cons ',dcg-term
#'(lambda (,terms)
(prolog
(lisp ,?terms ,terms)
(= ,?terms ,rewrite-term)
(lisp (return-from prolog ',rewrite-term)))))))
(defmacro define-dcg-tests (test-fn tests-var &body forms)
(with-gensyms
(tests dcg-term expect-fn term-rewrite result passes fails)
` (progn
(defparameter ,tests-var
(list ,@(mapcar #'(lambda (form)
`(dcg-test ,(car form) ,(cdr form)))
forms)))
(defun ,test-fn (&optional (,tests ,tests-var))
(loop for (,dcg-term . ,expect-fn) in ,tests
for ,term-rewrite = (rewrite-dcg-term ,dcg-term)
for ,result = (cons ,dcg-term ,term-rewrite)
if (funcall ,expect-fn ,term-rewrite)
collect ,result into ,passes
else collect ,result into ,fails
finally (return (values ,fails ,passes)))))))
(define-dcg-tests test-rewrite-dcg-term *test-rewrite-dcg-term-data*
(((move) (step))
((move ?list/1 ?rest)
(step ?list/1 ?rest)))
(((move) (step) (move))
((move ?list/1 ?rest)
(step ?list/1 ?list/2)
(move ?list/2 ?rest)))
(((step) ((up)))
((step (up . ?rest) ?rest)))
(((step) ((down)))
((step (down . ?rest) ?rest)))
(((n) (n1) ((t2)) (n3) ((t4)))
((n ?list/1 ?rest)
(n1 ?list/1 (t2 . ?list/2))
(n3 ?list/2 (t4 . ?rest))))
;;; Not yet sure about the macroexpansions of the following as I
;;; don't find example of the rewrite from DCG terms to simple
;;; Prolog terms in the book.
(((s) ((a)) ((b)))
((s (a b . ?rest) ?rest)))
(((s) ((a)) (s) ((b)))
((s (a . ?list/1) ?rest)
(s ?list/1 (b . ?rest)))))
I liked the idea of having macros generate code which called out into
Prolog to test the results of the lisp macroexpansion. But it doesn't
seem to be working the way that I expected it to work. I mean, the
macroexpansion looks correct to me.
(PROGN (DEFPARAMETER *TEST-REWRITE-DCG-TERM-DATA*
(LIST
(DCG-TEST ((MOVE) (STEP))
(((MOVE ?LIST/1 ?REST) (STEP ?LIST/1 ?REST))))
(DCG-TEST ((MOVE) (STEP) (MOVE))
(((MOVE ?LIST/1 ?REST) (STEP ?LIST/1 ?LIST/2)
(MOVE ?LIST/2 ?REST))))
(DCG-TEST ((STEP) ((UP))) (((STEP (UP . ?REST) ?REST))))
(DCG-TEST ((STEP) ((DOWN)))
(((STEP (DOWN . ?REST) ?REST))))
(DCG-TEST ((N) (N1) ((T2)) (N3) ((T4)))
(((N ?LIST/1 ?REST) (N1 ?LIST/1 (T2 . ?LIST/2))
(N3 ?LIST/2 (T4 . ?REST)))))
(DCG-TEST ((S) ((A)) ((B))) (((S (A B . ?REST) ?REST))))
(DCG-TEST ((S) ((A)) (S) ((B)))
(((S (A . ?LIST/1) ?REST)
(S ?LIST/1 (B . ?REST)))))))
(DEFUN TEST-REWRITE-DCG-TERM
(&OPTIONAL (#:TESTS/4036 *TEST-REWRITE-DCG-TERM-DATA*))
(LOOP FOR (#:DCG-TERM/4037 . #:EXPECT-FN/4038) IN #:TESTS/4036
FOR #:TERM-REWRITE/4039 =
(REWRITE-DCG-TERM #:DCG-TERM/4037) FOR #:RESULT/4040 =
(CONS #:DCG-TERM/4037 #:TERM-REWRITE/4039) IF
(FUNCALL #:EXPECT-FN/4038 #:TERM-REWRITE/4039) COLLECT
#:RESULT/4040 INTO #:PASSES/4041 ELSE COLLECT
#:RESULT/4040 INTO #:FAILS/4042 FINALLY
(RETURN (VALUES #:FAILS/4042 #:PASSES/4041)))))
But I find that I seem to be getting different results if I query with
?- versus using PROLOG in a lisp function.
USER> (car *test-rewrite-dcg-term-data*)
(((MOVE) (STEP))
. #<Function (:INTERNAL (:TOP-LEVEL-FORM "dcg.lisp" 4883) 0) @
#x110d002a>)
USER> (defparameter *x* *)
*X*
USER> (rewrite-dcg-term (car *x*))
((MOVE #:?LIST/4020 #:?REST/4019) (STEP #:?LIST/4020 #:?REST/4019))
USER> (as macroexpand-1
'(dcg-test ((move) (step))
((move ?list/1 ?rest) (step ?list/1 ?rest))))
(CONS '((MOVE) (STEP))
#'(LAMBDA (#:TERMS/4021)
(PROLOG (LISP #:?TERMS/4022 #:TERMS/4021)
(= #:?TERMS/4022
((MOVE ?LIST/1 ?REST) (STEP ?LIST/1 ?REST)))
(LISP
(RETURN-FROM PROLOG
'((MOVE ?LIST/1 ?REST) (STEP ?LIST/1 ?REST)))))))
T
USER> (?- (lisp ?terms (rewrite-dcg-term (car *x*)))
(= ?terms ((move ?list/1 ?rest) (step ?list/1 ?rest))))
?TERMS = ((MOVE ?LIST/4033 ?REST/4032) (STEP ?LIST/4033 ?REST/4032))
?LIST/1 = ?LIST/4033
?REST = ?REST/4032
No.
; No value
USER> (funcall (cdr *x*) (rewrite-dcg-term (car *x*)))
NIL
I would've thought that the function in (CDR *X*) would give the same
result as the interactive query via ?-. Or, if I do the following, I'm
getting an entirely different result, an ERROR.
USER> (ignore-errors
(funcall #'(lambda (terms)
(prolog
(lisp ?terms terms)
(= ?terms
((move ?list/1 ?rest)
(step ?list/1 ?rest)))
(lisp
(return-from prolog
'((move ?list/1 ?rest)
(step ?list/1 ?rest))))))
(rewrite-dcg-term (car *x*))))
NIL
#<UNDEFINED-FUNCTION @ #x10d145e2>
USER> (describe (second /))
#<UNDEFINED-FUNCTION @ #x10d145e2> is an instance of
#<STANDARD-CLASS UNDEFINED-FUNCTION>:
The following slots have :INSTANCE allocation:
FORMAT-ARGUMENTS (PROLOG::DE-LIST)
PLIST NIL
NAME PROLOG::DE-LIST
FORMAT-CONTROL ···@<attempt to call `~s' which is an undefined
···········@>"
; No value
USER>
I suppose that this could just be a bug in Allegro? It's probably
something I'm doing, though...
Damien Kick <·····@earthlink.net> writes:
> Pascal Bourguignon wrote:
>> Oh, and if you don't have time to read the Dragon Book, here is a
>> lisper who has read it and will be happy to implement any syntax you
>> want, for a fee... ;-)
>
> "You needn't worry about your reward. If money is all that you love,
> then that's what you'll receive. Your friend's quite a mercenary. I
> wonder if he really cares about anything--or anybody."
Don't worry, it's not money I love, it's running my computer and
keeping my ASDL up. Unfortunately, there are people who wants money
to go on providing me with shelter, eletricity and connectivity. The
fools, they don't realize we're on the verge of singularity, and that
money will soon become useless!
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
On Jun 29, 1:43 am, Pascal Bourguignon <····@informatimago.com> wrote:
> Damien Kick <····@earthlink.net> writes:
> > Pascal Bourguignon wrote:
> >> Oh, and if you don't have time to read the Dragon Book, here is a
> >> lisper who has read it and will be happy to implement any syntax you
> >> want, for a fee... ;-)
>
> > "You needn't worry about your reward. If money is all that you love,
> > then that's what you'll receive. Your friend's quite a mercenary. I
> > wonder if he really cares about anything--or anybody."
>
> Don't worry, it's not money I love, it's running my computer and
> keeping my ASDL up. [...]
The correct answer is <voice of="Mark Hamill">I care.</voice>