Discussion:
A "killer" macro
(too old to reply)
B. Pym
2024-09-08 04:08:51 UTC
Permalink
could fit on one page of Prolog. Better still, when I ran the new
code against the old code for the same inputs (given 7 cards,
evaluate, and return the best 5 card hand), it "disagreed" with the
old code on about 5 hands out of several million randomly generated
hands, and spit out different solutions for those hands. When I
analyzed the differences, I found that the Prolog solution was correct
in those cases. It was due to a few hard-to-find bugs in the old
solution, which was to be expected simply because that code was much
longer and more complex. So the new Prolog solution, because of its
simplicity, was also more correct, and uncovered bugs in the old
solution.
To illustrate the conciseness of the Prolog solution, here is the code
quad(A,B,C,D,E,F,G) :- permutation([A,B,C,D,E,F,G],[X,X,X,X,_,_,_]).
That's it - one line of code, and the input doesn't even need to be
sorted beforehand, as the old solution's input did, so I get to remove
an unnecessary sort.
That the code is concise doesn't mean that it is not grossly
inefficient. The mindless Prolog solution may have to generate
5040 permutations to determine that there are not four of a
kind.

Gauche Scheme

(use gauche.collection) ;; group-collection

(define (quad? lst)
(= 4 (apply max (map length (group-collection lst)))))

(quad? '(A B C D E F G))
===>
#f

(quad? '(A B A D A A G))
===>
#t

Don't have "group-collection"? Use an association list.

(define (quad? cards)
(let ((al '()))
(dolist (c cards) (ainc! al c))
(> (apply max (map cdr al)) 3)))

Both of these solutions have got to be more efficient
than the Prolog code.

It seems to me that association lists are not used enough
in Lispy languages. The languages don't provide enough
functions for dealing with them.

Here's the macro for "ainc!".

(define-syntax ainc!
(syntax-rules ()
[(_ alist key val func default)
(let ((pair (assoc key alist)))
(if pair
(set-cdr! pair (func val (cdr pair)))
(set! alist (cons (cons key (func val default)) alist))))]
[(_ alist key val func)
(ainc! alist key val func 0)]
[(_ alist key val)
(ainc! alist key val +)]
[(_ alist key)
(ainc! alist key 1)]))
Kaz Kylheku
2024-09-08 04:39:34 UTC
Permalink
Post by B. Pym
could fit on one page of Prolog. Better still, when I ran the new
code against the old code for the same inputs (given 7 cards,
evaluate, and return the best 5 card hand), it "disagreed" with the
old code on about 5 hands out of several million randomly generated
hands, and spit out different solutions for those hands. When I
analyzed the differences, I found that the Prolog solution was correct
in those cases. It was due to a few hard-to-find bugs in the old
solution, which was to be expected simply because that code was much
longer and more complex. So the new Prolog solution, because of its
simplicity, was also more correct, and uncovered bugs in the old
solution.
To illustrate the conciseness of the Prolog solution, here is the code
quad(A,B,C,D,E,F,G) :- permutation([A,B,C,D,E,F,G],[X,X,X,X,_,_,_]).
That's it - one line of code, and the input doesn't even need to be
sorted beforehand, as the old solution's input did, so I get to remove
an unnecessary sort.
That the code is concise doesn't mean that it is not grossly
inefficient. The mindless Prolog solution may have to generate
5040 permutations to determine that there are not four of a
kind.
Gauche Scheme
(use gauche.collection) ;; group-collection
(define (quad? lst)
(= 4 (apply max (map length (group-collection lst)))))
(quad? '(A B C D E F G))
===>
#f
(quad? '(A B A D A A G))
===>
#t
Don't have "group-collection"? Use an association list.
(define (quad? cards)
(let ((al '()))
(dolist (c cards) (ainc! al c))
(> (apply max (map cdr al)) 3)))
Both of these solutions have got to be more efficient
than the Prolog code.
It seems to me that association lists are not used enough
in Lispy languages. The languages don't provide enough
functions for dealing with them.
Here's the macro for "ainc!".
(define-syntax ainc!
(syntax-rules ()
[(_ alist key val func default)
(let ((pair (assoc key alist)))
(if pair
(set-cdr! pair (func val (cdr pair)))
(set! alist (cons (cons key (func val default)) alist))))]
[(_ alist key val func)
(ainc! alist key val func 0)]
[(_ alist key val)
(ainc! alist key val +)]
[(_ alist key)
(ainc! alist key 1)]))
You're using the primitive destructuring of syntax-rules to
simuliate optional parameters.

TXR Lisp:

(defmacro ainc (alist key : (val 1) (func '+) (default 0))
(with-gensyms (pair ap)
^(placelet ((,ap (read-once ,alist)))
(iflet ((,pair (assoc ,key ,ap)))
(rplacd ,pair (funcall ,func ,val (cdr ,pair)))
(set ,ap (acons ,key (funcall ,func ,default) ,ap))))))

Hygienic macros are idiotic. The software engineering problem they
address (accidental shadowing) is easily vanquished by shadowing
warnings in the compiler, which are trivial to implement.

Only problem is that shadowing warnings are incapable of generating
years of publishable academic papers; and that is where hygienic
macros come in.

1> (defmacro dirty-macro (form) ^(let ((x 42)) ,form))
dirty-macro
2> (let ((x 73)) (dirty-macro x))
42

Oops! But:

3> (with-compile-opts (:error shadow-var)
(compile-toplevel '(let ((x 73)) (dirty-macro x))))
** expr-3:2: let: variable x shadows local variable
** during evaluation of form (compile-toplevel '(let ((x 73))
(dirty-macro
x)))

When there is no shadowing, there is no hygiene problem.

Hygienic maros work via complicated renaming schemes that mess
with the entire program.

The intelligent coder fixes his compiler to detect the rare shadowing
situation, so the build fails. He manually renames something to fix
the issue, and moves on. It's just not publishable in a journal.
--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @***@mstdn.ca
Loading...