From: Jim Meehan
Subject: "Lisp poems"
Date: 
Message-ID: <1992Feb27.132506.17179@src.dec.com>
I agree that a competition of "powerful Lisp programs" is pretty silly.
But it's fun to look at short, elegant programs, in any language.  They
often reveal surprising subtleties.

Dan Friedman once told me that he was thinking about assembling a
collection of "Lisp poems".  I don't know that he ever got around to
doing it, but I think that's exactly the right metaphor, so let's do
that on the net instead of arguing about power.  This is not a poetry
contest (ugh), just poems submitted by poets for your amusement,
edification, etc.  In this endeavor, minor revisions, like removing
that extra CONS from the Transpose function, are clearly improvements,
while concerns about efficiency or exceeding call-arguments-limit are
clearly less important.

Some poems are long, some are short.  (Some poems rhyme, this one
don't.)  Some are deep but useless; the self-reproducing function comes
to mind.  Some are long, beautiful epics, but many of those will exceed
the boredom-threshold of net-readers.

Some are funny.  I wrote one in the pre-Common Lisp days that took
a PROG-form and altered it in place so that conditional branches and
GO-forms were spliced into their targets.  I called it a "lambda-graph",
since it allowed you to eliminate PROG and GO altogether.  E.g., the sequence
    ... (cond (a b c) (d e))  f g ...
became
    ... (cond (a b c f g ...) (d e f g ...))
Likewise for GO.  It did amazing things to the stack.  (Well *I* thought
it was funny.)

--Jim
From: Antti Karttunen
Subject: Re: "Lisp poems"
Date: 
Message-ID: <1992Mar4.223115.8379@mits.mdata.fi>
In article <······················@src.dec.com> ······@src.dec.com (Jim Meehan) writes:
>I agree that a competition of "powerful Lisp programs" is pretty silly.
>But it's fun to look at short, elegant programs, in any language.  They
>often reveal surprising subtleties.
>
>Dan Friedman once told me that he was thinking about assembling a
>collection of "Lisp poems".  I don't know that he ever got around to
>doing it, but I think that's exactly the right metaphor, so let's do
>that on the net instead of arguing about power.  This is not a poetry
>contest (ugh), just poems submitted by poets for your amusement,
>edification, etc.  In this endeavor, minor revisions, like removing
>that extra CONS from the Transpose function, are clearly improvements,
>while concerns about efficiency or exceeding call-arguments-limit are
>clearly less important.
>
>Some poems are long, some are short.  (Some poems rhyme, this one
>don't.)  Some are deep but useless; the self-reproducing function comes
>to mind.  Some are long, beautiful epics, but many of those will exceed
>the boredom-threshold of net-readers.

Here's one "poem":
 
(defun rewerse (lista)
       (cond ((null (cdr lista)) lista)
              (t (cons (car (rewerse (cdr lista)))
                        (rewerse (cons
                                   (car lista)
                                   (rewerse (cdr (rewerse (cdr lista))))))))))

(Double-w is for avoiding conflict with the name reverse).
However, it's not mine, but from one tutorial article giving examples
of multiply recursive functions in Lisp. I would be glad to know
where this function appeared first time, and who invented it.

To count how many calls of rewerse are needed to reverse a list of
n arguments, you can use the following function, which is recursive
itself (not the optimal solution):

(defun rewerse-count (n)
       (cond ((lessp n 2) 1)
              (t (add1 
                   (+ (* 3 (rewerse-count (sub1 n)))
                           (rewerse-count (- n 2))
                   )
                 )
              )
       )
)

Results from n=0 onward should be these:
1 1 5 17 57 189 625 2065 6821 22529 74409 ...
And think about how many waste cons-cells it produces.
But beautiful anyway. I posted an article about the similar Forth word
and about the metamagical consequences of it to the comp.lang.forth.
(See articles with the subjects: Mysterious recursive word in Forth and
MYSTERY recursive definition).

>
>Some are funny.  I wrote one in the pre-Common Lisp days that took
>a PROG-form and altered it in place so that conditional branches and
>GO-forms were spliced into their targets.  I called it a "lambda-graph",
>since it allowed you to eliminate PROG and GO altogether.  E.g., the sequence
>    ... (cond (a b c) (d e))  f g ...
>became
>    ... (cond (a b c f g ...) (d e f g ...))
>Likewise for GO.  It did amazing things to the stack.  (Well *I* thought
>it was funny.)

I have also thought of implementing GO in interpreter with some kind of
"precompiler" which browses the progn's and replaces destructively
every GO with pointer to the corresponding label (and label stripped
away of course). Problem is that in some cases, like 
(if (something-is-p something) (go somewhere) ...) there must be inserted
one surplus progn between, and that of course grows the stack, which
is not very good idea with the idiot loops. Probably I should unwind
the stack at some point.


>
>--Jim

-- 
Antti J. Karttunen       Time to edit the .signature again! Here is my slogan:
······@mits.mdata.fi     "Mee pihaas sy|m{{n sun lihaas!" (M. Perusj{tk{).