From mboxrd@z Thu Jan  1 00:00:00 1970
From: bakul@bitblocks.com (Bakul Shah)
Date: Fri, 16 Feb 2018 15:49:35 -0800
Subject: [TUHS] lisp challenge
In-Reply-To: Your message of "Fri, 16 Feb 2018 14:28:35 -0800."
 <20180216222835.GC27574@mcvoy.com>
References: <20180216210114.GA27574@mcvoy.com>
 <20180216220524.3B9A4156E80B@mail.bitblocks.com>
 <20180216222835.GC27574@mcvoy.com>
Message-ID: <20180216234950.67D80156E9AD@mail.bitblocks.com>

On Fri, 16 Feb 2018 14:28:35 -0800 Larry McVoy <lm at mcvoy.com> wrote:
> On Fri, Feb 16, 2018 at 02:05:09PM -0800, Bakul Shah wrote:
> > 
> > If you want to do more of an apples to apples comparison, you
> > should pick a brand new problem not known to be solved in
> > either C or Lisp so that both sides start at the same point!
> 
> Nope.  It's my challenge and it stands as I stated it.  People said
> I was wrong when I said Lisp was perceived as slow.  I picked a 
> perfectly reasonable example of a common problem (text processing),
> gave a benchmark, gave a pointer to how the C program was made fast,
> and asked for a lisp program that even comes close.

By issuing this challenge you automatically "win" as no one is
going to take up your challenge and spend the kind of time
that was needed to optimize GNU grep.  Very clever of you! But
if you are serious, it is only fair that both sides start with
a clean slate.

Here's a somewhat related problem: Consider trees with zero or
more integers as leaves.  For example, ((1 2)3(4 (5 () 6))).
A file contains 0 or more such trees.  Write a tree-grep to
find and print trees with matching fringes. For example:

.*3.*5.* matches the above tree
.*(3).* doesn't as there is no subtree with 3 as its sole leaf
.*(.*2)[2,3].* also matches
.*(.*2.+).* doesn't as 2 is the last leaf and we want at least one more
.*(4#(.*().*).*).* matches -- (4...) contains (.*().*) 0 or more levels down.

. is any, * is 0 or more, + is 1 or more, # is like ** in zsh.
[...] is used to specify alternatives.  e.g {0-5,11-23, 99-}.
Assume unsigned ints.

#(5.*) says there is some subtree with 5 as the first leaf.

Syntax needs to be refined to be able to exactly specify
the shape one wants.

For extra credit also generate a tree-sed!

> I'm more than willing to be wrong, that's how I learn.  But the proof
> here is to show up with a pure lisp grep that is fast as the C version.
> I'm no lisp expert, not by any stretch, but I've never seen a lisp
> program that out performed a well written C program.

http://www.ffconsultancy.com/ocaml/ray_tracer/languages.html

Has a comparison of several languages used for implementing
raytracing. Harrop's graph is weird but for 32bit word
machines Stalin comes close to g++ results.