realistic but short and simple LISP examples?

[Wroot]

cubic...@mailandnews.com (Software Scavenger) wrote in message
news:<a6789134.0112...@posting.google.com>...
> Wroot <wr...@my-deja.com> wrote in message
news:<9veuni$qlq$1...@newsmaster.cc.columbia.edu>...
>
> > Could somebody offer an example of a short (a few Kb or less) program
in
> > LISP that does something useful and that would be relatively hard and
> > time-consuming to program in C++? (aside from such built-in niceties as
>
> Give us an example of the kind of program you mean, by posting the C++
> version of it. Be sure it has clear enough comments that a non-C++
> programmer can understand what it's for, what it does, how it works,
> etc. It will be interesting to see how many Lisp versions of it you
> get in response, and how much shorter and neater most of them are than
> the C++ version.

Here's one (challenge to LISP programmers): read space or newline separated
integers from "input.dat", write out all possible permutations (one per
line) into "output.dat" (No broken "input.dat" data or unopenable
"output.dat" checking is necessary)
-------------------C++ version----------------------------
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
ifstream in("input.dat");
vector<int> L;
int n;
while(in >> n)
L.push_back(n);
ofstream out("output.dat");
sort(L.begin(), L.end());
do {
for(int i = 0; i < L.size(); i++)
out << L[i] << " ";
out << '\n';
} while(next_permutation(L.begin(), L.end()));
return 0;
}
----------------------------------------------------
If "all possible permutations" is too much to ask of LISP,
just write out the numbers in the reverse order (classic problem)

BTW, use less than 12 input values while testing, unless you want
"output.dat" to be 10Gb :)

Wroot

P.S. cubicle584, for some reason, your reply didn't make it to my news
server, but I saw it on google. Perhaps someone canceled it.
--
Please note: mail sent to wr...@my-deja.com is ignored.

[Tim Moore]

I hesitate to respond to what seems like an obvious troll, but here goes.
Some of the constructs may seem a little cryptic, but they save me time
when farting around on Usenet. Feel free to do the research to figure out what they do.
I
n article <9vgtl8$6un$1...@newsmaster.cc.columbia.edu>, "Wroot"
<wr...@my-deja.com> wrote:

>
> Here's one (challenge to LISP programmers): read space or newline
> separated integers from "input.dat", write out all possible permutations
> (one per line) into "output.dat" (No broken "input.dat" data or
> unopenable "output.dat" checking is necessary)
> -------------------C++ version---------------------------- #include
> <fstream>
> #include <algorithm>
> #include <vector>
> using namespace std;
> int main() {
> ifstream in("input.dat");
> vector<int> L;
> int n;
> while(in >> n)
> L.push_back(n);
> ofstream out("output.dat");
> sort(L.begin(), L.end());
> do {
> for(int i = 0; i < L.size(); i++)
> out << L[i] << " ";
> out << '\n';
> } while(next_permutation(L.begin(), L.end())); return 0;
> }
> ----------------------------------------------------

I see you've chosen your battle carefully in order to make use of the
STL. That's OK; we can quickly bang out permute without paying too much
attention to efficiency. The rest of your "challenge" follows quickly.
(defun permute (list)
(cond ((null list)
nil)
((null (cdr list))
(list list))
(t (loop
for element in list
nconc (mapcar #'(lambda (sublist)
(cons element sublist))
(permute (remove element list)))))))

(defun permute-stream (in-stream out-stream)
(loop
for element = (read in-stream nil in-stream)
while (not (eq element in-stream))
collect element into elements
finally (format out-stream "~{~{~A~^ ~}~%~}" (permute elements))))

(defun permute-file (in-file out-file)
(with-open-file (in-stream in-file)
(with-open-file (out-stream out-file :direction :output :if-exists :supersede)
(permute-stream in-stream out-stream))))

>If "all possible
> permutations" is too much to ask of LISP, just write out the numbers in
> the reverse order (classic problem) BTW, use less than 12 input values
> while testing, unless you want "output.dat" to be 10Gb :)

You weenie.

[Thomas F. Burdick]

Wroot <wr...@my-deja.com> writes:

> cubic...@mailandnews.com (Software Scavenger) wrote in message
> news:<a6789134.0112...@posting.google.com>...
> > Wroot <wr...@my-deja.com> wrote in message
> news:<9veuni$qlq$1...@newsmaster.cc.columbia.edu>...
> >
> > > Could somebody offer an example of a short (a few Kb or less)
> > > program in LISP that does something useful and that would be
> > > relatively hard and time-consuming to program in C++? (aside
> > > from such built-in niceties as
> >
> > Give us an example of the kind of program you mean, by posting the C++
> > version of it. Be sure it has clear enough comments that a non-C++
> > programmer can understand what it's for, what it does, how it works,
> > etc. It will be interesting to see how many Lisp versions of it you
> > get in response, and how much shorter and neater most of them are than
> > the C++ version.
>
> Here's one (challenge to LISP programmers): read space or newline separated
> integers from "input.dat", write out all possible permutations (one per
> line) into "output.dat" (No broken "input.dat" data or unopenable
> "output.dat" checking is necessary)

This is your idea of a program that "does something useful" and
doesn't just use the "built-in niceties" of the standard library?!?!

First, this does nothing useful. Second, all it does is wrap up a STL
function for use in batch processing. If you had made the program a
pipe instead, I might see the point, but even then, a Lisp programmer
wouldn't have needed to wrap it up in the first place. C++
programmers primarily use the Unix shell, so you'll need to wrap
functions up for the shell if you want to test them. Lisp programmers
primarily use the REPL, so you can just call the function directly.

Common Lisp doesn't have a vector permutator built-in. That said,
it's quite easy to build one. Here's mine that I've used maybe 3 times:

(defun map-permutations! (fn vector)
(let ((end (1- (length vector))))
(labels ((helper (start)
(if (= start end)
(funcall fn vector)
(loop for i from start to end
do (rotatef (aref vector start) (aref vector i))
(helper (1+ start))
(rotatef (aref vector start) (aref vector i))))))
(helper 0)
nil)))

;;; This just wraps it up in a syntax I prefer -- something you
;;; can't to in C++, BTW
(defmacro do-permutations! ((var vector) &body body)
`(map-permutations! #'(lambda (,var) ,@body) ,vector))

You can test it like this:

* (do-permutations! (v #(1 2 3))
(format t "~S~%" v))
#(1 2 3)
#(1 3 2)
#(2 1 3)
#(2 3 1)
#(3 2 1)
#(3 1 2)
NIL

A more reasonable example, assuming you're not just trolling, would be
to construct a simple neural network (that's not build into either
language's standard library ;)

--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'

[Kaz Kylheku]

In article <9vgtl8$6un$1...@newsmaster.cc.columbia.edu>, Wroot wrote:
>Here's one (challenge to LISP programmers): read space or newline separated
>integers from "input.dat", write out all possible permutations (one per
>line) into "output.dat" (No broken "input.dat" data or unopenable
>"output.dat" checking is necessary)

C++ spewing idiot, here is a better challenge for you. ITA software
(www.itasoftware.com) had this on their website, and I solved it, leading
to an invitation to send them my resume. The challenge appeared in a
banner advertizement on slashdot.org. Ironically, I didn't know it was
for a Lisp job until I already had some Lisp code written to solve it;
at which point I clicked on the banner ad.

Consider all possible expressions formed by combining nine nines
using addition, subtraction, multiplication and division, and
arbitrary grouping with parentheses. Here is one possible
expression:

((9 + 9) - (9 * 9)) / (9 - ((9 + 9) / 9) * 9)

here is another:

(9 + 9 - 9 * 9 * 9 / (9 + 9) + (9 * 9))

there is obviously large number of other expressions which combine 9
nines using these operators in all the possible ways. Your task is to
find the smallest positive integer which is not the value of any of
these expressions.

Let's see your C++ program which finds the result.

>If "all possible permutations" is too much to ask of LISP,

There is nothing difficult about generating permutations of a sequence.

But then, you are using someone else's algorithms library to do it,
so maybe you don't have a fscking clue what it entails.

There is nothing you can do in C++ that you cannot do in Lisp (not LISP,
by the way). Any program which can be expressed succinctly in C++ can also
be expressed even more succinctly in Lisp, because the Lisp
program won't have to contain any stupid workarounds for limitations
in the C++ type system, syntax and other braindamage. The reverse is
not the case; some Lisp programs can only be imitated by C++ programs
that are orders of magnitude larger, because they reimplement a good
proportion of common Lisp. Reimplement it badly, and reimplement it
in a way that is incompatible with everyone else's way of reinventing.

I suspect you will run into this when writing the code to solve the Nine
Nines problem above. My Lisp version is 47 physical lines.

Good luck.

>BTW, use less than 12 input values while testing, unless you want
>"output.dat" to be 10Gb :)

It's safe to assume that the people in comp.lang.lisp
know basic facts, like that the number of permutations of a sequence
of length N is the factorial of N.

[Pierre R. Mai]

Wroot <wr...@my-deja.com> writes:

> Here's one (challenge to LISP programmers): read space or newline separated
> integers from "input.dat", write out all possible permutations (one per
> line) into "output.dat" (No broken "input.dat" data or unopenable
> "output.dat" checking is necessary)

Ah, a specification in the true spirit of C/C++ (don't ever check for
errors). Well FWIW:

(defun doit ()
(with-open-file (in-stream "input.dat")
(with-open-file (out-stream "output.dat" :direction :output)
(let ((items (loop for item = (read in-stream nil in-stream)
until (eq item in-stream)
collect item)))
(with-all-permutations (set (sort items #'<))
(format out-stream "~{~A~^ ~}~%" set))))))

This makes use of the following facility for permutations on lists
(you have to include at least the macro before the doit function, if
you put everything in one file):

(defun permute (set function)
(labels ((permute-one (tail)
(if (null tail)
(funcall function set)
(loop for rest on tail do
(rotatef (first tail) (first rest))
(permute-one (rest tail))
(rotatef (first tail) (first rest))))))
(permute-one set)))

(defmacro with-all-permutations ((var items) &body body)
`(permute ,items #'(lambda (,var) ,@body)))

The code differs from the C++ version in the following:

a) The C++ STL comes with code for permutation building built-in. CL
doesn't, hence the need for the additional code. So it is 20 LoC
in C++ with STL against 8 + 12 LoC for CL.

b) The CL version doesn't produce superfluous whitespace at the end of
each line, although it can trivially be changed to do that, if
wanted, or produce more complex formats, e.g. use

(format out-stream "~{~A ~}~%" set)

to produce the C++ output, or use

(format out-stream "~{~A~^, ~}~%" set)

to produce lines like "1, 2, 3, 4", or use

(format out-stream "~{~A~^;~}~%" set)

to produce CSV files.

c) At least minimal error checking, for no added work. The C++
version silently assumes that a non-existant file means no entries,
and hence produces an empty output file. The Common Lisp version
will raise an appropriate error in that case.

d) If we elide the sorting step, then the given code will work for all
readable CL objects. With the sorting step the code works for
everything that is acceptable to #'<, i.e. all CL numeric types
except for complex numbers. Again you get useful error messages at
runtime if you violate that condition.

e) Since we use the CL reader, comments, read-time conditionals and
even read-time evaluation work as expected.

Of course the whole exercise is just silly, and doesn't show any of
CL's strengths, but who cares...

Regs, Pierre.

> #include <fstream>
> #include <algorithm>
> #include <vector>
> using namespace std;
>
> int main() {
> ifstream in("input.dat");
> vector<int> L;
> int n;
> while(in >> n)
> L.push_back(n);
> ofstream out("output.dat");
> sort(L.begin(), L.end());
> do {
> for(int i = 0; i < L.size(); i++)
> out << L[i] << " ";
> out << '\n';
> } while(next_permutation(L.begin(), L.end()));
> return 0;
> }

--
Pierre R. Mai <pm...@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein

[Wroot]

t...@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) wrote:

> This is your idea of a program that "does something useful" and
> doesn't just use the "built-in niceties" of the standard library?!?!
>
> First, this does nothing useful. Second, all it does is wrap up a STL

> If you had made the program a pipe instead, I might see the point

It's the same, even 2 lines simpler. Since you know what STL is, I'll
refrain from pasting the code.

> C++ programmers primarily use the Unix shell, so you'll need to wrap
> functions up for the shell if you want to test them. Lisp programmers
> primarily use the REPL, so you can just call the function directly.

$ grep tfb /etc/passwd
tfb:x:555:555:Thomas F. Burdick,,,:/home/tfb:/usr/bin/clisp ?

> A more reasonable example, assuming you're not just trolling, would be
> to construct a simple neural network (that's not build into either
> language's standard library ;)

What do you mean by simple neural network? One that doesn't learn? (Product
of weight matrix and input vector with non-linear function applied to each
element of the result? I'll bet it's equally easy in C++ and Lisp with C++
version being much faster) Could you give more precise specs?

Anyways, if you mean backprop, IIRC according to one of the comp.ai FAQs,
C++ is actually the language of choice for this. I think what it said was
"it's *only* about 200 lines in C++". What I was asking in the OP was "what
are the things that Lisp is better suited for compared to C++".

Wroot
P.S. If I were trolling, I would have cross-posted to comp.lang.c++. Why
would you accuse me of something like this?

[Wroot]

Kaz Kylheku wrote:

Puhleeze... You think you know this elementary fact and it makes you unique
enough to call others "idiots"?! How do you think I got the 10Gb number?

12! * 12 * 2 / 1024^3 ~ 10.7 (12! lines, 12 elements per line, 2 bytes per
element, 1024^3 bytes per Gb) Lighten up, kid.

Wroot
P.S. Speaking of nine 9s, did you *SOLVE* the problem (as opposed to just
writing a program to solve it)

[Erik Naggum]

* Wroot <wr...@my-deja.com>

| Here's one (challenge to LISP programmers)

Have you considered downgrading your arrogance to a reasonable level?

Here is a challenge for you. Write a function that accepts an expression
and a list of values for the variables and returns the lambda expression
applied to these values. (To reduce the complexity of the task when
accepting an expression from the user, you may assume that a compiler is
available in the function compile, so this is _not_ about making an
evaluator.) Call the function you write apply.

For extra bonus points, write an evaluator using the apply function you
just wrote, which evaluates all arguments of an expression before calling
the function with the values collected from that evaluation. Call this
function eval.

For even more extra bonusp points, write a function read that accepts a
character stream and returns the next expression the user has supplied on
that stream. Match it with a function write that accepts an object of
any kind and produces a character stream suitable for read and humans.

If you have time, write a simple loop which calls read to obtain an
expression from the user, then calls eval to obtain the result of
evaluating it, and finally calls write to show the user this result.

If you complete all this, you have what every Common Lisp programmer gets
for free when he starts up his Common Lisp system. Please think through
the challenge before you dismiss any of this as trivial. Basically, a
major part of the Lisp language follows from the decision to make this
interactive loop work correctly. Note that in Common Lisp these
functions are available from the get go with the names I have suggested.

If you still think you have any business coming here with "challenges",
please consider your own reaction to an ignorant splut who came up to you
and "challenged" you do to something he had just learned. _I_ find it on
par with a stupid kid who has just learned a bad word and tries to get
adults to say it so he can snicker.

///
--
The past is not more important than the future, despite what your culture
has taught you. Your future observations, conclusions, and beliefs are
more important to you than those in your past ever will be. The world is
changing so fast the balance between the past and the future has shifted.

[Kaz Kylheku]

In article <9vhalm$fn2$1...@newsmaster.cc.columbia.edu>, Wroot wrote:
>Kaz Kylheku wrote:
>
>> In article <9vgtl8$6un$1...@newsmaster.cc.columbia.edu>, Wroot wrote:
>>>BTW, use less than 12 input values while testing, unless you want
>>>"output.dat" to be 10Gb :)
>>
>> It's safe to assume that the people in comp.lang.lisp
>> know basic facts, like that the number of permutations of a sequence
>> of length N is the factorial of N.
>
>Puhleeze... You think you know this elementary fact and it makes you unique
>enough to call others "idiots"?! How do you think I got the 10Gb number?

What ``others''? How many of you are there?

I didn't propose any connection between this basic fact regarding
permutations, and calling you an idiot. You are now practising creative
reading comprehension.

Apparently, *you* think you are unique in knowing this factoid, otherwise
why would you deem it necessary to include that warning? Do you think
people are so stupid that they can't estimate for themselves how large
the output will be? If you want a group of people to take you seriously,
you have to take them seriously.

I used the phrase ``C++ spewing idiot'' because the article you wrote
is a pitifully naive apology for an idiotic library that is part of an
idiotic programming language, and because that you appear believe that
that generating permutations of a vector's elements is some kind of hot
computational problem that is out of the reach of the Lisp programming
language.

I wrote a permutation-generating program in elementary school, eighth
grade or thereabouts. Hand-assembled 6502 machine language on an
Apple II+. This is not exactly something that you can use to showcase
the capabilities of a programming language.

>Wroot
>P.S. Speaking of nine 9s, did you *SOLVE* the problem (as opposed to just
>writing a program to solve it)

What's the difference? The program isn't intelligent enough to be
credited with the solution independently of its author.

But what you are getting at is that it's not an analytic solution, but a
brute force solution; that is true, so be it. I saw in the problem
statement a little Lisp hacking opportunity for a rainy afternoon,
because that's what I was predisposed toward seeing at that time.

Say, how is the C++ version coming along?

In the real world, there are deadlines. So, let's say you have until
Tuesday, 00:00 UTC. That is ample, given that the Lisp solution was
hacked in a few hours. The world won't always grant you extensions
to accomodate the productivity-squandering programming language you
are using.

[Wroot]

Kaz Kylheku wrote:

> In article <9vhalm$fn2$1...@newsmaster.cc.columbia.edu>, Wroot wrote:
>>P.S. Speaking of nine 9s, did you *SOLVE* the problem (as opposed to just
>>writing a program to solve it)
>
> What's the difference?

Did you get an integer number as an answer? Yes or no?

*If* "yes", how about this: I wouldn't want to give you the answer,
especially that you might not even know it, but I'll post THE SUM OF ALL
DIGITS here *this* Sunday on the condition that you publicly promise that,
in case mine coincides with the sum of all digits of your answer or turns
out to be the correct one otherwise, you will start a new thread in this NG
with the subject "Wroot is the greatest" in which you will apologize for
your being an ass and a bigot (literally and succinctly). How does this
sound?

Wroot

> In the real world, there are deadlines. So, let's say you have until
> Tuesday, 00:00 UTC. That is ample, given that the Lisp solution was
> hacked in a few hours. The world won't always grant you extensions
> to accomodate the productivity-squandering programming language you
> are using.

[Fernando Rodríguez]

On Sun, 16 Dec 2001 04:26:45 GMT, k...@ashi.footprints.net (Kaz Kylheku) wrote:

>Consider all possible expressions formed by combining nine nines
>using addition, subtraction, multiplication and division, and
>arbitrary grouping with parentheses. Here is one possible
>expression:
>
> ((9 + 9) - (9 * 9)) / (9 - ((9 + 9) / 9) * 9)
>
>here is another:
>
> (9 + 9 - 9 * 9 * 9 / (9 + 9) + (9 * 9))

Are you sure that's a good Lisp vs C++ challenge? It's more like a
mathematical puzzle...

Something that forces you to struggle bypassing C++'s static type system would
be IMHO a better example. You can even add some multiple inheritance for extra
suffering. };-)

For the OP: This C++ book is _full_ of great examples of things which are
trivial in CL, but atrocious monstruosities in C++.

Generative Programming: Methods, Tools, and Applications
by Krzysztof Czarnecki, Ulrich Eisenecker

PS: I remember reading about a shias religious celebration were people would
slap their heads until they bleed. This is very similar to what the authors of
that book are doing...

--
Fernando Rodríguez
frr at wanadoo dot es
--

[Fernando Rodríguez]

On Sun, 16 Dec 2001 05:57:42 -0500, Wroot <wr...@my-deja.com> wrote:

>*If* "yes", how about this: I wouldn't want to give you the answer,
>especially that you might not even know it, but I'll post THE SUM OF ALL
>DIGITS here *this* Sunday on the condition that you publicly promise that,

The correct sum could still be obtained from the wrong list of values...

BTW, I wonder if there's an analytical solution to the problem, or the more
general n nines one... Totally useless, of course, but interesting. ;-)

>in case mine coincides with the sum of all digits of your answer or turns
>out to be the correct one otherwise, you will start a new thread in this NG
>with the subject "Wroot is the greatest" in which you will apologize for
>your being an ass and a bigot (literally and succinctly). How does this
>sound?

I sounds like you should both calm down. :-)

[Kaz Kylheku]

In article <9vhun7$qk3$1...@newsmaster.cc.columbia.edu>, Wroot wrote:
>Kaz Kylheku wrote:
>
>> In article <9vhalm$fn2$1...@newsmaster.cc.columbia.edu>, Wroot wrote:
>>>P.S. Speaking of nine 9s, did you *SOLVE* the problem (as opposed to just
>>>writing a program to solve it)
>>
>> What's the difference?
>
>Did you get an integer number as an answer? Yes or no?

Yes, of course.

>*If* "yes", how about this: I wouldn't want to give you the answer,
>especially that you might not even know it, but I'll post THE SUM OF ALL

Imbecile, if you had been paying due attention, you might have noticed
that at the outset I made the following claim: I sent the answer and
the code to the software company which posed the problem, and obtained
an affirmative answer. You can confirm that I did so by asking them,
if you wish.

>DIGITS here *this* Sunday on the condition that you publicly promise that,

I don't care about the answer; the challenge here is to produce a C++
solution. For all anyone knows, you could get the answer using a Lisp program.

Tell me you are only pretending to not understand the point of this!

>in case mine coincides with the sum of all digits of your answer or turns
>out to be the correct one otherwise, you will start a new thread in this NG
>with the subject "Wroot is the greatest" in which you will apologize for
>your being an ass and a bigot (literally and succinctly). How does this
>sound?

Bigot about what? You're the one who barged in here with your
C++ bigotry.

I happen to develop in C++ for a living; I understand its strengths
and limitations.

See? A programming language can be so many different things to different
people. It can pay one man's bills, and give another the occasion to
act like a jackass on Usenet under a childish pseudonym.

[Coby Beck]

"Wroot" <wr...@my-deja.com> wrote in message

news:9vhalm$fn2$1...@newsmaster.cc.columbia.edu...

>
> Wroot
> P.S. Speaking of nine 9s, did you *SOLVE* the problem (as opposed to just
> writing a program to solve it)
> --

LOL! A troll and a maroon!

[Wroot]

I knew you didn't have the balls to accept. A real man can admit it when he
is wrong. You aren't one. You called me an idiot, and offered to solve this
little problem you spent several hours writing a lisp program for. I
offered you a way to compare answers on the spot.

My advice to you: see shrink and, also, go back to school, kiddo. Maybe
they'll teach you some respect for people who are smarter than you.

Wroot

[Kaz Kylheku]

In article <9vit7e$gte$1...@newsmaster.cc.columbia.edu>, Wroot wrote:
>I knew you didn't have the balls to accept. A real man can admit it when he
>is wrong. You aren't one. You called me an idiot, and offered to solve this

A real man posts under his real name. Is it written on your driver's
license that you are named Wroot? Assuming you are old enough to have one.

Would you care to unmask yourself of your pseudonym?

>little problem you spent several hours writing a lisp program for. I
>offered you a way to compare answers on the spot.

You are in no position to offer anything, other than the working C++
program. I'm not interested in comparing numeric answers, so you might
as well know that the solution to the puzzle is 195. I already have a
program that computes it, so I'm not in a contest with you.

This is simply an opportunity for you to defend the technical claims
you made about the superiority of C++, thereby saving some face.

[Gareth McCaughan]

Kaz Kylheku wrote:

> C++ spewing idiot, here is a better challenge for you. ITA software
> (www.itasoftware.com) had this on their website, and I solved it, leading
> to an invitation to send them my resume. The challenge appeared in a
> banner advertizement on slashdot.org. Ironically, I didn't know it was
> for a Lisp job until I already had some Lisp code written to solve it;
> at which point I clicked on the banner ad.
>
> Consider all possible expressions formed by combining nine nines
> using addition, subtraction, multiplication and division, and
> arbitrary grouping with parentheses. Here is one possible
> expression:

[etc]

> there is obviously large number of other expressions which combine 9
> nines using these operators in all the possible ways. Your task is to
> find the smallest positive integer which is not the value of any of
> these expressions.

[...]

> I suspect you will run into this when writing the code to solve the Nine
> Nines problem above. My Lisp version is 47 physical lines.

Ha. The one I just wrote is 21 lines, including one blank line
and 4 comment-only lines. Nyaaah!

I reckon it could probably be done in about 60 (non-blank, non-
-comment) lines of C++ using the STL, but it would take me a factor
of 4 longer to do it than it did in Lisp. Of course, if you
measure productivity in LoC per unit time then C++ would come out
almost as good as Lisp on this exercise. :-)

--
Gareth McCaughan Gareth.M...@pobox.com
.sig under construc

[Thomas F. Burdick]

Wroot <wr...@my-deja.com> writes:

> t...@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) wrote:
>
> > This is your idea of a program that "does something useful" and
> > doesn't just use the "built-in niceties" of the standard library?!?!
> >
> > First, this does nothing useful. Second, all it does is wrap up a STL

[...]

> > If you had made the program a pipe instead, I might see the point
>
> It's the same, even 2 lines simpler. Since you know what STL is, I'll
> refrain from pasting the code.

Then I would see the point of writing the program, if for some reason
you wanted to use this STL function from the command line. But it's
still not a program that "does something useful" nor does it do a
thing except use one of the "built-in nicities" of the C++ STL. It
doesn't even sort-of fit your criteria.

> > C++ programmers primarily use the Unix shell, so you'll need to wrap
> > functions up for the shell if you want to test them. Lisp programmers
> > primarily use the REPL, so you can just call the function directly.
>
> $ grep tfb /etc/passwd
> tfb:x:555:555:Thomas F. Burdick,,,:/home/tfb:/usr/bin/clisp ?

No, when I'm doing Unix administration, I use a Unix shell. When I'm
writing C++ code, I tend to spend almost all of my time looking at an
editor, a Unix command line, and gdb. When I write Lisp, I tend to
spend almost all of my time looking at an editor and the REPL. I
would have no desire whatsoever to use the Unix command line wrt my
program I'm developing.

> > A more reasonable example, assuming you're not just trolling, would be
> > to construct a simple neural network (that's not build into either
> > language's standard library ;)
>
> What do you mean by simple neural network? One that doesn't learn? (Product
> of weight matrix and input vector with non-linear function applied to each
> element of the result? I'll bet it's equally easy in C++ and Lisp with C++
> version being much faster) Could you give more precise specs?

Why do you bet this? I thought you were interested in learning Lisp,
and wanted to see a small example program that might show it off. I
was merely trying to suggest a direction in which to go. Wasn't this
your orignal post?

I'm trying to understand what it is that people like about LISP and
whether I should learn it. (I'm interested in AI)

Could somebody offer an example of a short (a few Kb or less)
program in LISP that does something useful and that would be
relatively hard and time-consuming to program in C++? (aside from

such built-in niceties as arbitrary-precision arithmetic please)

It seems that since that time, you've developed a lot of concrete
ideas about what is and is not possible in Lisp and C++.

> Anyways, if you mean backprop, IIRC according to one of the comp.ai FAQs,
> C++ is actually the language of choice for this. I think what it said was
> "it's *only* about 200 lines in C++". What I was asking in the OP was "what
> are the things that Lisp is better suited for compared to C++".
>
> Wroot
> P.S. If I were trolling, I would have cross-posted to comp.lang.c++. Why
> would you accuse me of something like this?

Because you sure sound like it. Most cross-posts *are* trolls, but
not all trolls are cross-posters. You're posting from a
pseudo-anonymous account, and you don't seem to have the slightest
desire to see Lisp as a useful tool. You've gone from asking for help
in seeing why Lisp is cool to carefully contriving situations where
you can feel smug about using C++ instead. And in a single day, no
less. Until you show some evidence of having tried to understand why
intelligent people would use Lisp, I'm going to assume you're just
here trolling.

[Bruce Hoult]

In article <slrna1q8eu.hf0....@g.local>,
Gareth.M...@pobox.com wrote:

> > I suspect you will run into this when writing the code to solve the Nine
> > Nines problem above. My Lisp version is 47 physical lines.
>
> Ha. The one I just wrote is 21 lines, including one blank line
> and 4 comment-only lines. Nyaaah!
>
> I reckon it could probably be done in about 60 (non-blank, non-
> -comment) lines of C++ using the STL

I don't know how you're doing it in CL, but I'm disappointed because I
can do it in 23 lines of *Perl* (17 if you don't count lines with only a
brace or the Unix #! line) and Perl doesn't even have support for
fractions!!

bruce@k7:~/programs/perl > cat nineNines.pl
#!/usr/bin/perl
my @nums = ({},{"9/1" => 9});
sub gcd {my ($a,$b)=@_; $a?gcd($a<=$b?($a,$b%$a):($b,$a)):$b};
for (my $n=1;$n<=9;++$n){
for (my $p=1;$p<=$n/2;++$p){
for my $a (keys %{$nums[$p]}){
for my $b (keys %{$nums[$n-$p]}){
"$a $b" =~ m!(-*\d+)/(-*\d+) (-*\d+)/(-*\d+)!;
map {my ($a,$b)=@{$_};
($a,$b) = (-$a,-$b) if $b<0;
my $g=gcd(abs($a),$b);
$nums[$n]{$a/$g."/".$b/$g} = 9 if $b;
}([$1*$4+$2*$3,$2*$4], [$1*$4-$2*$3,$2*$4], [$2*$3-$1*$4,$2*$4],
[$1*$3,$2*$4], [$2*$3,$1*$4], [$1*$4,$2*$3]);
}
}
}
for (my $i=0;;++$i){
next if $nums[$n]{"$i/1"};
print "Smallest integer that can't be made from $n nines is $i\n";
last;
}
}
bruce@k7:~/programs/perl > time ./nineNines.pl
Smallest integer that can't be made from 1 nines is 0
Smallest integer that can't be made from 2 nines is 2
Smallest integer that can't be made from 3 nines is 1
Smallest integer that can't be made from 4 nines is 4
Smallest integer that can't be made from 5 nines is 13
Smallest integer that can't be made from 6 nines is 22
Smallest integer that can't be made from 7 nines is 33
Smallest integer that can't be made from 8 nines is 103
Smallest integer that can't be made from 9 nines is 195

real 0m31.510s
user 0m31.470s
sys 0m0.040s

[Bruce Hoult]

In article <bruce-172C16....@news.paradise.net.nz>, Bruce
Hoult <br...@hoult.org> wrote:

> In article <slrna1q8eu.hf0....@g.local>,
> Gareth.M...@pobox.com wrote:
>
> > > I suspect you will run into this when writing the code to solve the
> > > Nine
> > > Nines problem above. My Lisp version is 47 physical lines.
> >
> > Ha. The one I just wrote is 21 lines, including one blank line
> > and 4 comment-only lines. Nyaaah!
> >
> > I reckon it could probably be done in about 60 (non-blank, non-
> > -comment) lines of C++ using the STL
>
> I don't know how you're doing it in CL, but I'm disappointed because I
> can do it in 23 lines of *Perl* (17 if you don't count lines with only a
> brace or the Unix #! line) and Perl doesn't even have support for
> fractions!!

OK, now 13 lines of CL. Pointers on how to better use CL appreciated --
I don't like how much this conses with the nconc, but the dolist is so
convenient:

(setq nums (make-array '(10)))
(dotimes (i 10) (setf (aref nums i) (make-hash-table)))
(setf (gethash 9 (aref nums 1)) t)
(dotimes (n 10)
(loop for p from 1 to (/ n 2) do
(loop for a being the hash-keys of (aref nums p) do
(loop for b being the hash-keys of (aref nums (- n p)) do
(dolist (i (nconc (list (+ a b) (- a b) (- b a) (* a b))
(if (/= a 0) (list (/ b a)))
(if (/= b 0) (list (/ a b)))))
(setf (gethash i (aref nums n)) t)))))
(format t "With ~D nines, can't make ~D~%" n
(loop for i from 1 unless (gethash i (aref nums n)) do (return i))))

-- Bruce

[Siegfried Gonzi]

"Fernando Rodríguez" wrote:

> Are you sure that's a good Lisp vs C++ challenge? It's more like a
> mathematical puzzle...
>
> Something that forces you to struggle bypassing C++'s static type system would
> be IMHO a better example. You can even add some multiple inheritance for extra
> suffering. };-)
>
> For the OP: This C++ book is _full_ of great examples of things which are
> trivial in CL, but atrocious monstruosities in C++.

The problem with templates (and C++ libraries) actually is, that
they are not really platform and especially compiler-independent.
I did never figure out why most of the templates with the native
Macintosh C/C++ compiler MPW do not work.
It seems that the Micrsoft Visual C++ compiler is better in this
respect (I could at least assume it thanks to my new Windows XP
notebook).

Or take the new Template-Numerical-Library (TNT) which
incorporates things like lu-factorization and therelike
(interestingly, this official libraray is 10 times too slow
compared to normal C). I would not pay for it that it will run
with all C++ compilers.

What has this all to do with Common Lisp? It is a big plus that
Common Lisp does not show all the before-mentioned weakness. I
really appreciate this fact every day more and more.

A few weeks ago I have been a fanatic Clean fellow. I am not
a programmer for my living (academia...) but I have to use the
computer and numerical simulations for my PhD in climatoly. Okay,
what are the reasons, why I now believe Clean is not useful for
my work (I have to emphasize, that I can speak only for myself):

a) It is nearly ridiculous, that one in Clean is forced to write
floating-point numbers always with a precision of 16 places. There is
no direct way, e.g. to write in a precision-formatted way to a file.
Yes I have a second-hand (thanks to Fabien T.) library which
can perform at least formatted single-precision output. But this
second hand library does not always work as required.

b) Absolutely no control over numbers. A floating-point number is a
double-precison representation and an integer-number is a 32byte number.
You cannot say to Clean that you want your calculation with
single-precision, for example. Absolutely no way to round to a specific
precision.

c) No way of exception handling. And this is really severe, because
you cannot print-out intermediate results; there is one starting-
point and one ending-point. In bigger programs, debugging is awfull.

d) The case you have got a function B, which is called by function A,
BUT you do not actually use it (the function A), but you want to use B
with slightly different types, the compiler will complain, that B in A
does not match (even one does not use A). This is the reason why a Clean
programmer often is sitting 8 hours infront of his computer (running
Clean) but only for watching the screen and not typing something useful
in, because he is desperately afraid of Clean's notorious (and in most of
the cases not very informative) compiler complaints.

e) And the biggest problem: Array types and Clean's unique array type
concept (BELIEVE me, C's post-fece error is a pleasure to experience
compared to Clean's unique array concept). There are many array types in
Clean:

e.g. the 2 dimensional real ones:

!*{#*{Real}}, !{{Real}}, !*{#{#Real}}, !{#*{#Real}}, !{!{!Real}},
{#*{Real}}, {{Real}}, *{#{#Real}}, {#*{#Real}}, {{Real}},...

not enough the confusion, you cannot always pass every array to every type.
And array update (in-place) is *only* allowed in unique ones, but this is
often trial-and-error, because you get the wildest compiler errors that
often an unique array is expected but it is not deliverd. And as a programmer
your last chance is to copy the array. AND without any unique informations
one cannot update arrays!
This often absolutely destroys the concept of passing higher-order functions
(which have got as types unique-arrays), because you have then to copy the
array in order to fullfill the array concept. BUT sometimes you may pass
(and the compiler will not complain) arrays as functions, but I haven't
figured out when and why and there is absolutely no documentation discussing
the problem in depth.

f) Files are handeld the same way as unique array ones. I swear you: it is
a nightmare. I get pearls on my forehead when I think that I have
to re-use (addmittedly, a very tiny code base) Clean code (which I am writing for
my PhD). But I will leave Clean programming as soon as possible.

g) And sometimes the compiler produces side-effects (yes!) when updating arrays.
The underlying Clean concept has to be very complicated and error prone.

I write my experience here, because I often read in the computer-language
wars that Common Lispers, C++ victims... are ignorant to new innovations,
but when new innovation actually means that one has to experience the
abovementioned nightmares I think the ignorants are on the right way.

I have been exposed to two programming-language shocks in my life:

- Forth
- Clean

(I did not forget to mention C/C++; C++ is only complicated and maybe
one can learn it in 210 years of hard training, but C++ is not shocking).
I really contemplate to use Allegro Common Lisp for my future PhD work.
The development environment for Windows is really fantastic and even
for students is the expense of updating the license every 60 days
affordable. And when one holds his PhD he can easily buy (wages for
Postdocs are surely better) the complete package.

Corman Lisp shows also a good environment and Roger Corman is surely a very
talented programmer and profi but Corman Lisp is not really useful for
large floating-point arrays.

S. Gonzi

[Kaz Kylheku]

In article <sVYS7.9925$ip4.1...@news2.calgary.shaw.ca>, Kaz Kylheku wrote:
>In the real world, there are deadlines. So, let's say you have until
>Tuesday, 00:00 UTC.

Well, the deadline is only a few minutes away as I write this.

Will we see code, or is Wroot a pure troll?

It's possible to generate the list of values of all possible expressions
of N nines by combining the values of expressions of K nines (woof!) and
N - K nines over all operators and all relevant values of K. If N is 1,
the only expression possible is 9, and If N is 2, the expressions are
(+ 9 9), (- 9 9), (/ 9 9) and (* 9 9). All else follows by combination; for
N = 3, combine the N=1 and N=2 results in every possible way, and so on.

This approach should be a piece of cake in C++; an hour's work at
most.

My Lisp solution actually generates expressions, and evaluates them.
storing only the top level results into a hash table for the purpose of
finding the least positive integer that is not in the list. My reason
for doing the puzzle in the first place was to explore this technique.

That solution is not such a piece of cake in C++.

[Ed L Cashin]

Wroot <wr...@my-deja.com> writes:

> I knew you didn't have the balls to accept. A real man can admit it when he
> is wrong. You aren't one. You called me an idiot, and offered to solve this
> little problem you spent several hours writing a lisp program for. I
> offered you a way to compare answers on the spot.
>
> My advice to you: see shrink and, also, go back to school, kiddo. Maybe
> they'll teach you some respect for people who are smarter than you.

This newsgroup is weird. Lisp seems to be a drug that makes smart
people mean and dumb people mean.

--
--Ed Cashin integrit file-verification system:
eca...@terry.uga.edu http://integrit.sourceforge.net/

Note: If you want me to send you email, don't munge your address.

[Gareth McCaughan]

Bruce Hoult wrote:

[I said:]

> > > Ha. The one I just wrote is 21 lines, including one blank line
> > > and 4 comment-only lines. Nyaaah!
> > >
> > > I reckon it could probably be done in about 60 (non-blank, non-
> > > -comment) lines of C++ using the STL
> >
> > I don't know how you're doing it in CL, but I'm disappointed because I
> > can do it in 23 lines of *Perl* (17 if you don't count lines with only a
> > brace or the Unix #! line) and Perl doesn't even have support for
> > fractions!!

It'll be a little shorter in Perl because of autovivification,
which approximately makes up for the lack of fractions.

> OK, now 13 lines of CL. Pointers on how to better use CL appreciated --
> I don't like how much this conses with the nconc, but the dolist is so
> convenient:

[SNIP]

That's almost identical to my solution. :-) Oh, I forgot
to mention that two of my 16 (or, if you prefer, 21) lines
were FORMATs to keep track of what the program's doing as
it goes.

The other difference is that I wrote a bunch of (setf (gethash ...))
forms explicitly rather than a dolist. This hurt me less than it
would have hurt you because I didn't bother saving a factor of 2
by only looping half way up in the next-to-outer loop.

[Bruce Hoult]

In article <slrna1ssdq.qn6....@g.local>,
Gareth.M...@pobox.com wrote:

> The other difference is that I wrote a bunch of (setf (gethash ...))
> forms explicitly rather than a dolist. This hurt me less than it
> would have hurt you because I didn't bother saving a factor of 2
> by only looping half way up in the next-to-outer loop.

Actually, that's probably better than mine. 4 lines for four operators,
vs four lines for all the nconc/dolist stuff. The only cost is that you
end up doing a+b and a*b twice, but that's only two out of eight
operations wasted, and you get to save all the consing and loop overhead.

Is there a better way to set up the array of hashes at the start? Perl
is *so* convenient for that. OTOH, all those $$$ make me go blind.

I was also wondering if there was an easy way to bind a variable to
(aref nums n) in the loop that controls n, but I couldn't immediately
find one better than "and h = (aref nums n) then (aref nums n)", which
is no improvement. I didn't want to use a separate line for a "let".

-- Bruce

[Joe Schaefer]

Bruce Hoult <br...@hoult.org> writes:

> In article <bruce-172C16....@news.paradise.net.nz>, Bruce
> Hoult <br...@hoult.org> wrote:

[...]

> > I don't know how you're doing it in CL, but I'm disappointed because
> > I can do it in 23 lines of *Perl* (17 if you don't count lines with
> > only a brace or the Unix #! line) and Perl doesn't even have support
> > for fractions!!
>
> OK, now 13 lines of CL. Pointers on how to better use CL appreciated
> -- I don't like how much this conses with the nconc, but the dolist
> is so convenient:
>
> (setq nums (make-array '(10)))
> (dotimes (i 10) (setf (aref nums i) (make-hash-table)))
> (setf (gethash 9 (aref nums 1)) t)
> (dotimes (n 10)
> (loop for p from 1 to (/ n 2) do

IIRC, Your original Perl solution finished on your box at around 30s.
How does the CL version compare? The reason I ask is because when I
ran the perl code you posted, my box took about 200 seconds to finish
it. But by farming out the inner loops to C I got the runtime down to
under 20s. This reduced the Perl to about a dozen lines at the expense
of ~3 hours and ~80 lines of C [1].

If your CL solution is "too slow", I'm wondering what sort of
strategies people might recommend to try and accelerate it.
Recoding slow parts of a perl script in C is a common technique, and
in this case I got a 10-fold increase without "too" much extra
effort. Can something similar also be done for the CL version?

[1] - the script wound up looking like

#!/usr/bin/perl -w
use strict;

use Inline "C"; # source follows __C__ marker after end-of-script
sub generate; # (\%\%) returns a list of rationals generated by
# operating on each pair of argument keys

my $N = shift || 9;
my @nums = ({},{"$N/1" => undef}); # ignore hash values

for my $n (1 .. $N) {
@{ $nums[$n] }{ generate $nums[$_], $nums[$n-$_] } = () for 1..$n/2;

$_ = 1; ++$_ while exists $nums[$n]{"$_/1"};
print "Smallest integer that can't be made from $n $N\'s is $_\n";
}

__END__

__C__
/* ... 50 lines of code to implement rational arithmetic in C
and convert to/from hash key strings ... */

void generate (SV *a, SV *b) {
HV *h = SvRV(a), *k = SvRV(b);
rat_t *r, *s; /* rat_t = struct { ``%ld ; %lu'' } */
I32 i,j;

Inline_Stack_Vars;
Inline_Stack_Reset;

if (SvTYPE(h) != SVt_PVHV || SvTYPE(k) != SVt_PVHV)
croak ("[generate(a,b)] error: args must be hash refs!");

setup_keys(h, r, i);

if (h != k)
setup_keys(k, s, j);
else /* avoid repetiton */
s=r, j=i;

if (!r || !s) { /* setup/malloc failed */
if (r) free(r);
if (s && s != r) free(s);
return;
}

for ( --i ; i>=0 ; --i) { /* XXX: original inner loops */
int m = j;
for (--m ; m>=0 ; --m)
rat_gen(r[i],s[m]); /* PUSH rationals back to Perl */
}

free(r);
if (h != k) free(s);

Inline_Stack_Done;
}

--
Joe Schaefer

[Bruce Hoult]

In article <m3sna95...@mumonkan.sunstarsys.com>, Joe Schaefer
<joe+u...@sunstarsys.com> wrote:

> > > I don't know how you're doing it in CL, but I'm disappointed because
> > > I can do it in 23 lines of *Perl* (17 if you don't count lines with
> > > only a brace or the Unix #! line) and Perl doesn't even have support
> > > for fractions!!
> >
> > OK, now 13 lines of CL.
>

> IIRC, Your original Perl solution finished on your box at around 30s.
> How does the CL version compare?

Right. 31.5 seconds. As it turns out, in CMUCL on the same machine the
Lisp runs in +/- one second of the Perl. CMUCL puts out about a million
GC status messages, which might be slowing it down (not sure how to turn
those off).

> The reason I ask is because when I ran the perl code you posted,
> my box took about 200 seconds to finish it.

Mine was a 700 MHz Athlon running Linux. Just tried the Perl on an 867
MHz MacOS X machine and it took 29.2 seconds there. And on the 266 MHz
G3 PowerBook I'm typing this on it takes 86.2 seconds. I don't have CL
on the Macs. You're using a Pentium 100 or something?

> But by farming out the inner loops to C I got the runtime down to
> under 20s. This reduced the Perl to about a dozen lines at the expense
> of ~3 hours and ~80 lines of C [1].

Gads! You can actually read obfuscated Perl code!! You have my
admiration.

> If your CL solution is "too slow", I'm wondering what sort of
> strategies people might recommend to try and accelerate it.

Declaring some variable types would help. So would hand-expanding the
nconc/dolist stuff.

> Recoding slow parts of a perl script in C is a common technique, and
> in this case I got a 10-fold increase without "too" much extra
> effort. Can something similar also be done for the CL version?

I should probably do a Dylan version. It'll be near identical to the
CL, but a bit more wordy (lots of lines with just 'end' instead of
'))))' in the Lisp). Dylan is designed to compile better than Lisp can,
but a) Lisp is pretty good too, and b) we're probably all at the mercy
of the quality of the runtime library hash table implementation.

-- Bruce

[Bruce Hoult]

In article <bruce-9BF494....@news.paradise.net.nz>, Bruce
Hoult <br...@hoult.org> wrote:

> > IIRC, Your original Perl solution finished on your box at around 30s.
> > How does the CL version compare?
>
> Right. 31.5 seconds. As it turns out, in CMUCL on the same machine the
> Lisp runs in +/- one second of the Perl.

A tidy-up (thanks to Paul Foley) reduces the CL to 21.6 seconds, a 47%
speed increase.

(let ((nums (make-array 10
:initial-contents (loop repeat 10 collect (make-hash-table)))))

(setf (gethash 9 (aref nums 1)) t)

(loop for n below 10 as h = (aref nums n) do
(loop for p from 1 to (floor n 2) do

(loop for a being the hash-keys of (aref nums p) do
(loop for b being the hash-keys of (aref nums (- n p)) do

(setf (gethash (+ a b) h) t (gethash (* a b) h) t
(gethash (- a b) h) t (gethash (- b a) h) t)
unless (zerop b) do (setf (gethash (/ a b) h) t)
unless (zerop a) do (setf (gethash (/ b a) h) t))))
(format t "~&With ~D nines, can't make ~D" n
(loop for i from 1 unless (gethash i h) do (return i)))))

-- Bruce

[Bruce Hoult]

In article <bruce-E1F709....@news.paradise.net.nz>, Bruce
Hoult <br...@hoult.org> wrote:

> In article <bruce-9BF494....@news.paradise.net.nz>, Bruce
> Hoult <br...@hoult.org> wrote:
>
> > > IIRC, Your original Perl solution finished on your box at around 30s.
> > >
> > > How does the CL version compare?
> >
> > Right. 31.5 seconds. As it turns out, in CMUCL on the same machine
> > the Lisp runs in +/- one second of the Perl.
>
> A tidy-up (thanks to Paul Foley) reduces the CL to 21.6 seconds, a 47%
> speed increase.

Ooops.

I just found that CMUCL doesn't compile things by default. So the
previous time was for interpreted code. After..

(defun nineNines ()
<previous code>)

(compile 'nineNines)

(time (nineNines))

... we now get ...

Evaluation took:
2.18 seconds of real time
2.13 seconds of user run time
0.05 seconds of system run time
[Run times include 0.23 seconds GC run time]
0 page faults and
10954632 bytes consed.

So that's ten times faster for compiled code than for interpreted.
Without declarations.

-- Bruce

[Thomas F. Burdick]

Bruce Hoult <br...@hoult.org> writes:

> In article <bruce-9BF494....@news.paradise.net.nz>, Bruce
> Hoult <br...@hoult.org> wrote:
>
> > > IIRC, Your original Perl solution finished on your box at around 30s.
> > > How does the CL version compare?
> >
> > Right. 31.5 seconds. As it turns out, in CMUCL on the same machine the
> > Lisp runs in +/- one second of the Perl.
>
> A tidy-up (thanks to Paul Foley) reduces the CL to 21.6 seconds, a 47%
> speed increase.

This seemed insanely slow to me [you did compile it, right?], so I
tried it myself.

(defun nines ()
(declare (optimize (speed 3) (safety 1)))

> (let ((nums (make-array 10
> :initial-contents (loop repeat 10 collect (make-hash-table)))))
> (setf (gethash 9 (aref nums 1)) t)
> (loop for n below 10 as h = (aref nums n) do

;; start [*]

> (loop for p from 1 to (floor n 2) do
> (loop for a being the hash-keys of (aref nums p) do
> (loop for b being the hash-keys of (aref nums (- n p)) do
> (setf (gethash (+ a b) h) t (gethash (* a b) h) t
> (gethash (- a b) h) t (gethash (- b a) h) t)
> unless (zerop b) do (setf (gethash (/ a b) h) t)
> unless (zerop a) do (setf (gethash (/ b a) h) t))))

;; end [*]

> (format t "~&With ~D nines, can't make ~D" n
> (loop for i from 1 unless (gethash i h) do (return i)))))
>
> -- Bruce

This is all on a 500 MHz Celeron. First, here's a transcript of the
best Perl time I got, of 5 runs:

[noc@malatesta tmp]$ time ./foo.pl

Smallest integer that can't be made from 1 nines is 0
Smallest integer that can't be made from 2 nines is 2
Smallest integer that can't be made from 3 nines is 1
Smallest integer that can't be made from 4 nines is 4
Smallest integer that can't be made from 5 nines is 13
Smallest integer that can't be made from 6 nines is 22
Smallest integer that can't be made from 7 nines is 33
Smallest integer that can't be made from 8 nines is 103
Smallest integer that can't be made from 9 nines is 195

real 1m16.517s
user 1m15.260s
sys 0m0.310s

I compiled the file containing NINES, loaded it, ran the GC, and
here's what I got:

With 9 nines, can't make 195
Evaluation took:
8.74 seconds of real time
7.92 seconds of user run time
0.4 seconds of system run time
[Run times include 1.32 seconds GC run time]
12 page faults and
10968552 bytes consed.

Since a fair amount of that time was spent in the GC, I wrapped the
area of the function I marked with "start [*]" and "end [*]" in an
ext::without-gcing form, so the GC would only run between the major
iterations, and saved a little more time:

* (time (nines))
Compiling LAMBDA NIL:
Compiling Top-Level Form:

With 0 nines, can't make 1
With 1 nines, can't make 1
With 2 nines, can't make 2
With 3 nines, can't make 1
With 4 nines, can't make 4
With 5 nines, can't make 13
With 6 nines, can't make 22
With 7 nines, can't make 33
[GC threshold exceeded with 3,501,600 bytes in use. Commencing GC.]
[GC completed with 1,555,664 bytes retained and 1,945,936 bytes freed.]
[GC will next occur when at least 3,555,664 bytes are in use.]

With 8 nines, can't make 103
[GC threshold exceeded with 9,783,712 bytes in use. Commencing GC.]
[GC completed with 3,714,504 bytes retained and 6,069,208 bytes freed.]
[GC will next occur when at least 5,714,504 bytes are in use.]

With 9 nines, can't make 195
Evaluation took:
7.86 seconds of real time
7.24 seconds of user run time
0.36 seconds of system run time
[Run times include 0.65 seconds GC run time]
0 page faults and
10978104 bytes consed.
NIL

Incidentally, CLISP also kicked the pants off Perl:

[9]> (time (nines))

With 0 nines, can't make 1
With 1 nines, can't make 1
With 2 nines, can't make 2
With 3 nines, can't make 1
With 4 nines, can't make 4
With 5 nines, can't make 13
With 6 nines, can't make 22
With 7 nines, can't make 33
With 8 nines, can't make 103
With 9 nines, can't make 195
Real time: 9.871542 sec.
Run time: 9.6 sec.
Space: 13839052 Bytes
GC: 22, GC time: 5.01 sec.
NIL

[Kenny Tilton]

Bruce Hoult wrote:

> So that's ten times faster for compiled code than for interpreted.
> Without declarations.

Good work. But no one would worry about the performance of X if the
performance of X did not matter, and if it matters, we need to optimize
X to the max. so...

.../with/ declarations? :)

Hey, where'd Wrootmeister go? I am thinking that was a Lisper just
trying to stir up their fellow Lispers. The trollishness was a bit over
the top to be convincing.

kenny
clinisys

[Bruce Hoult]

In article <xcv6675...@conquest.OCF.Berkeley.EDU>,

t...@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) wrote:

> Bruce Hoult <br...@hoult.org> writes:
>
> > In article <bruce-9BF494....@news.paradise.net.nz>, Bruce
> > Hoult <br...@hoult.org> wrote:
> >
> > > > IIRC, Your original Perl solution finished on your box at around
> > > > 30s.
> > > > How does the CL version compare?
> > >
> > > Right. 31.5 seconds. As it turns out, in CMUCL on the same machine
> > > the
> > > Lisp runs in +/- one second of the Perl.
> >
> > A tidy-up (thanks to Paul Foley) reduces the CL to 21.6 seconds, a 47%
> > speed increase.
>
> This seemed insanely slow to me [you did compile it, right?], so I
> tried it myself.

No, I simply didn't realize that I had to! I've only previously done
things in CMUCL where speed didn't matter, and the only previous
compiler I used that had an interactive REPL (Functional Developer, nee
Harlequin Dylan) automatically compiles everything before running it.

> (defun nines ()
> (declare (optimize (speed 3) (safety 1)))

This "declare" line has absolutely no effect on the speed. 2.18 seconds
of wallclock time either way.

-- Bruce

[Jochen Schmidt]

Bruce Hoult wrote:

You can switch off GC-Messages by (setf *gc-verbose* nil)

What makes me curious is that above code runs on my Duron 800 (256MB Ram) in
2.72 seconds! (I have stuffed the code in a function named FOO)
The output is the following:

(let ((*gc-verbose* nil)) (time (foo)))

Compiling LAMBDA NIL:
Compiling Top-Level Form:

With 0 nines, can't make 1
With 1 nines, can't make 1
With 2 nines, can't make 2
With 3 nines, can't make 1
With 4 nines, can't make 4
With 5 nines, can't make 13
With 6 nines, can't make 22
With 7 nines, can't make 33

With 8 nines, can't make 103
With 9 nines, can't make 195

Evaluation took:
2.72 seconds of real time
2.47 seconds of user run time
0.07 seconds of system run time
[Run times include 0.34 seconds GC run time]
1 page fault and
10938232 bytes consed.

ciao,
Jochen

[Raymond Wiker]

Bruce Hoult <br...@hoult.org> writes:

On my work machine (Pentium III at 666 MHz), using SBCL, I got
around 6.5 seconds. Adding a (declare (speed 3) (compilations-speed 0)
(safety 0) and "fixnum" declarations for p, a and b got that down to
about 0.7 seconds.

--
Raymond Wiker Mail: Raymon...@fast.no
Senior Software Engineer Web: http://www.fast.no/
Fast Search & Transfer ASA Phone: +47 23 01 11 60
P.O. Box 1677 Vika Fax: +47 35 54 87 99
NO-0120 Oslo, NORWAY Mob: +47 48 01 11 60

Try FAST Search: http://alltheweb.com/

[Bruce Hoult]

In article <864rmp6...@raw.grenland.fast.no>, Raymond Wiker
<Raymon...@fast.no> wrote:

> On my work machine (Pentium III at 666 MHz), using SBCL, I got
> around 6.5 seconds. Adding a (declare (speed 3) (compilations-speed 0)
> (safety 0) and "fixnum" declarations for p, a and b got that down to
> about 0.7 seconds.

a and b aren't fixnums. Are you sure you got the right answers?

-- Bruce

[Christophe Rhodes]

Bruce Hoult <br...@hoult.org> writes:

> In article <slrna1ssdq.qn6....@g.local>,
> Gareth.M...@pobox.com wrote:
>
> > The other difference is that I wrote a bunch of (setf (gethash ...))
> > forms explicitly rather than a dolist. This hurt me less than it
> > would have hurt you because I didn't bother saving a factor of 2
> > by only looping half way up in the next-to-outer loop.
>
> Actually, that's probably better than mine. 4 lines for four operators,
> vs four lines for all the nconc/dolist stuff. The only cost is that you
> end up doing a+b and a*b twice, but that's only two out of eight
> operations wasted, and you get to save all the consing and loop overhead.
>
> Is there a better way to set up the array of hashes at the start?

[ (setq nums (make-array '(10)))

(dotimes (i 10) (setf (aref nums i) (make-hash-table)))

(setf (gethash 9 (aref nums 1)) t) ]

(setq nums (map-into (make-array '(10)) #'make-hash-table))

will save you one line :)

Cheers,

Christophe
--
Jesus College, Cambridge, CB5 8BL +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)

[Raymond Wiker]

Bruce Hoult <br...@hoult.org> writes:

Oops... you're right; they're not fixnums, and I got the wrong
results. Declaring a and b as "rational" instead of "fixnum" gives me
the right result, and better speed as well (0.46 seconds).

[Pierre R. Mai]

Bruce Hoult <br...@hoult.org> writes:

> Lisp runs in +/- one second of the Perl. CMUCL puts out about a million
> GC status messages, which might be slowing it down (not sure how to turn
> those off).

* (describe 'ext:*gc-verbose*)

*GC-VERBOSE* is an external symbol in the EXTENSIONS package.
It is a special variable; its value is T.
Special documentation:
When non-NIL, causes the functions bound to *GC-NOTIFY-BEFORE* and
*GC-NOTIFY-AFTER* to be called before and after a garbage collection
occurs respectively. If :BEEP, causes the default notify functions to beep
annoyingly.

So try

(setq ext:*gc-verbose* nil)

Regs, Pierre.

--
Pierre R. Mai <pm...@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein

[Bruce Hoult]

In article <86zo4g6...@raw.grenland.fast.no>, Raymond Wiker
<Raymon...@fast.no> wrote:

> > a and b aren't fixnums. Are you sure you got the right answers?
>
> Oops... you're right; they're not fixnums, and I got the wrong
> results. Declaring a and b as "rational" instead of "fixnum" gives me
> the right result, and better speed as well (0.46 seconds).

That's pretty fast.

I did a Dylan version:

begin
let nums = make(<vector>, size: 10);
for (i from 0 to 9) nums[i] := make(<equal-table>) end;
nums[1][fraction(9,1)] := #t;
for (n from 1 to 9)
let h :: <equal-table> = nums[n];
for (p from 1 to floor/(n,2))
for (a :: <fraction> in nums[p].key-sequence)
for (b :: <fraction> in nums[n - p].key-sequence)
h[a + b] := #t; h[a * b] := #t;
h[a - b] := #t; h[b - a] := #t;
unless (a.num.zero?) h[b / a] := #t end;
unless (b.num.zero?) h[a / b] := #t end;
end
end
end;
for (i from 1, while: element(h, fraction(i,1), default: #f))
finally format-out("With %d nines, can't make %d\n", n, i);
end
end
end

That's 21 lines with 7 lines of noisewords (begin/end). With Gwydion
d2c it takes 1.9 seconds on the same machine on which CMUCL takes 2.18
seconds. Without the declarations of h, a and b it takes 2.8 seconds.
The rest of the time is wasted in our extremely sucky implementation of
hash tables which is doing GF dispatch up the wazoo.

I've been playing with a better implementation of hash tables for a
while but it's not done & checked in to cvs yet, so it doesn't count :-)
And it would take real work to get as fast as your SBCL (whatever that
is) results. Especially for a user-defined datatype in a standard hash
table.

Unfortunately, since Gwydion doesn't have fractions I needed another 47
lines of support code. Well I guess I'll put a cleaned up and more
complete version into the Gwydion libraries sometime soon, in which case
Gwydion *will* support fractions... :-)

define class <fraction> (<number>)
sealed slot num :: <integer>,
required-init-keyword: n:;
sealed slot den :: <integer>,
required-init-keyword: d:;
end <fraction>;

define sealed method initialize
(f :: <fraction>, #key n :: <integer>, d :: <integer>)
=> ();
let g = gcd(n.abs, d.abs);
if (d < 0) g := -g end;
unless (g = 1) f.num := truncate/(n,g); f.den := truncate/(d,g) end;
end;

define sealed domain make (singleton(<fraction>));

define inline method fraction(n :: <integer>, d :: <integer>)
make(<fraction>, n: n, d: d);
end;

define sealed inline method \+(a :: <fraction>, b :: <fraction>)
fraction(a.num * b.den + a.den * b.num, a.den * b.den);
end;

define sealed inline method \-(a :: <fraction>, b :: <fraction>)
fraction(a.num * b.den - a.den * b.num, a.den * b.den);
end;

define sealed inline method \*(a :: <fraction>, b :: <fraction>)
fraction(a.num * b.num, a.den * b.den);
end;

define sealed inline method \/(a :: <fraction>, b :: <fraction>)
fraction(a.num * b.den, a.den * b.num);
end;

define sealed inline method \=(a :: <fraction>, b :: <fraction>)
=> res :: <boolean>;
a.num = b.num & a.den = b.den;
end;

define inline method equal-hash
(key :: <fraction>, initial-state :: <hash-state>)
=> (id :: <integer>, state :: <hash-state>);
values(merge-hash-ids(key.num, key.den, ordered: #t), initial-state);
end method equal-hash;

[Michael Parker]

Bruce Hoult wrote:

> I just found that CMUCL doesn't compile things by default. So the
> previous time was for interpreted code. After..
>
> (defun nineNines ()
> <previous code>)
>
> (compile 'nineNines)
>
> (time (nineNines))
>
> ... we now get ...
>
> Evaluation took:
> 2.18 seconds of real time
> 2.13 seconds of user run time
> 0.05 seconds of system run time
> [Run times include 0.23 seconds GC run time]
> 0 page faults and
> 10954632 bytes consed.
>
> So that's ten times faster for compiled code than for interpreted.
> Without declarations.

For those of you who might be pining for the good old days,
my XL1200 took 43.06 secs compiled.
0.967 secs processing sequence breaks
0.892 secs in the storage system
Consing not measured due to GC flip

[Kent M Pitman]

Michael Parker <des...@pdq.net> writes:

> > Evaluation took:
> > 2.18 seconds of real time
> > 2.13 seconds of user run time
> > 0.05 seconds of system run time
> > [Run times include 0.23 seconds GC run time]
> > 0 page faults and
> > 10954632 bytes consed.
> >
> > So that's ten times faster for compiled code than for interpreted.
> > Without declarations.
>
>
> For those of you who might be pining for the good old days,
> my XL1200 took 43.06 secs compiled.
> 0.967 secs processing sequence breaks
> 0.892 secs in the storage system
> Consing not measured due to GC flip

For those of you confused about why we pine for the good old days, it is
not raw processor power. The LispM was quite competitive in its time, but
even now, much slower that it is, it still has so many friendly UI features
no one's ever bothered to copy that I pull it out and use it for some kinds
of work because it's "fast enough" for editing (who really cares if they
type a key and then it takes 5 microseconds or 5000 to do the command as
long as it's ready to take the next command when you need it) and often
still even "fast enough" for debugging... Kinds of things I still miss:

* Meta-X Source Compare

Don't tell me m-x diff or whatever is equivalent until you've got all
the options the LispM did. It let you type 2 keys after you invoked
it to say what quantity (B = Buffer (prompted for), F = File (prompted
for), R = region (chosen one first time used, prompted for by recursive
edit if two regions needed), K or c-Y = top of kill ring,
P or m-Y = second on kill ring. Bit-decoded numeric arguments to control
ignoring case and/or leading whitespace. I don't see diff doing any of
this.

* Integrated Source Compare

Some people have suggested the lispm was a source compare server of sorts,
but what I mean is that every command in the world offered some way to
get at source compare. = in dired, for example. Mail reader had ways
to source compare referenced messages. Typing c-x c-s in emacs to save
file if it said "written by someone else" would prompt to let you see the
diffs before making you say if you wanted to overwrite, and on and on.

* File system with real file-system-level file versions

* Possibilities Buffers

multiple fingers into intermediate state of suspended commands so you
could abort a tags search if you saw something more interesting and
resume it later after stacking another on top of it. I often had these
stacked dozens high

* Complex undo/redo

Including things like undo/redo within region and a way of getting a list
of prior changes so you could only undo certain ones

* Complex command re-execution ("the new yank system")

c-Y (yank last kill), c-sh-Y (yank last kill matching string),
c-m-Y (yank last command), c-m-sh-Y (yank last command matching), etc.
allowing access to prior kills and commands in listable/rotatable/searchable
fashion

* Integrated source and patch system

m-X start patch, m-X finish patch

* Dynamic Windows (the system from which CLIM was created)

integrated into the listeners for debugging. more powerful than CLIM
actually. including presentation debuggers and such.

* Integrated network file system

so that any file operation can be done for any file on the internet

* Customizable and abstract network services

Not just low-level abilities like open-socket but high-level things like
find-path-to-service-on-host where you can ask for an abstract service
and it will choose among available media, protocols, and services to
figure out how best to satisfy things

Even after not having been upgraded in almost 10 years, other than light
patches i've done just for fun, I find my lispm still performs acceptably
and offers me these and more useful things.

Smart and fast are incomparable sometimes.

[Bruce Hoult]

In article <sfwpu5b...@shell01.TheWorld.com>, Kent M Pitman
<pit...@world.std.com> wrote:

> For those of you confused about why we pine for the good old days,
> it is not raw processor power. The LispM was quite competitive in
> its time, but even now, much slower that it is, it still has so
> many friendly UI features no one's ever bothered to copy that I pull
> it out and use it for some kinds of work because it's "fast enough"

I agree with everything you say, but the question is "where is the
source code, and why hasn't someone released it?"

I'm sick to death of incredibly nifty things disappearing along with the
companies that created them. Or, often worse, with the company
continuing and just the project or product getting cancelled and being
sat on, presumably to prevent competitors from getting a leg up.

I've got a lot of points of disagreement with RMS, but the thing that
makes me put time and effort into improving Gwydion Dylan is that at the
end of the day it's something good that No One Can Ever Take Away From
Me.

-- Bruce

[Peter S. Housel]

Bruce Hoult <br...@hoult.org> writes:
> That's 21 lines with 7 lines of noisewords (begin/end). With Gwydion
> d2c it takes 1.9 seconds on the same machine on which CMUCL takes 2.18
> seconds. Without the declarations of h, a and b it takes 2.8 seconds.
> The rest of the time is wasted in our extremely sucky implementation of
> hash tables which is doing GF dispatch up the wazoo.
>
> I've been playing with a better implementation of hash tables for a
> while but it's not done & checked in to cvs yet, so it doesn't count :-)
> And it would take real work to get as fast as your SBCL (whatever that
> is) results. Especially for a user-defined datatype in a standard hash
> table.
>
> Unfortunately, since Gwydion doesn't have fractions I needed another 47
> lines of support code. Well I guess I'll put a cleaned up and more
> complete version into the Gwydion libraries sometime soon, in which case
> Gwydion *will* support fractions... :-)

It has them already. See src/d2c/runtime/dylan/ratio.dylan for the
implementation.

-Peter-