Can anyone write this recursion for simple regexp more beautifullyand clearly than the braggarts

[Seebs]

If you tell me you know about this stuff I'll just take your word for
it (because I don't) but I would otherwise have thought that a fair
proportion of the power use during talk goes on the radios and the
screen. During standby, everything is in a low-power nearly-off mode
for more than 95% of a 24hr day. Could the CPU being able to shut
down in half the time really have a dramatic effect?

I'm not a real expert, but in general, CPU usage is a noticeable power
drain, and cutting it down makes a very big difference.

Keep in mind that, on a modern "phone", much of the time is spent not
talking but also not in standby. I don't know how much the radio runs
during an hour spent playing Bejeweled, but I'd guess not much -- but the
CPU is running at least several times a second.

Keep in mind that there's all sorts of options for reducing power usage; for
instance, you can scale back your clock speed, and on at least some hardware,
that lets you run at a lower voltage too, producing dramatic power savings.

So let's say you're playing Bejeweled, and you have two implementations.
And one of them requires the CPU to be in its full-speed mode, and one can
be done with the CPU running at half speed. That might well make a
substantial difference in power usage over the course of an hour or two.

I don't think I can say much else at this time. I do have the strong
impression that, on modern embedded-oriented chips, reducing the time it takes
to complete tasks translates fairly directly to reduced power consumption,
which is a very big deal.

-s

 

[Nick Keighley]

In

[...] Our thoughts shape our language, but
our language also shapes our thoughts - one of Hofstadter's
"strange loop" mutual recursions.

sounds like a good argument for learning multiple langauges
with different paradigms!  If we have multiple ways of thinking
then we can tackle a bigger spectrum of problems. And have a
larger collection of tools of tools for addressing them.

Very much so, which is why I may yet persevere with Lisp despite an
unpromising start.

you could try scheme it's smaller and simpler and designed as a
teaching
language. There are compiled versions as well if you really cannot
sacrifice speed.

 

[Nicolas Neuss]

Thus, this whole language advocacy thing is a bit daft. Those who
(knowledgably) advocate Lisp have presumably used it for a long time
and liked it. Those who (knowledgably) advocate C have presumably used
C for a long time and liked it.

But now comes a difference: Those who "advocate" Lisp usually have also
quite some experience in C (at least, that's the case for me).

These two different languages have very different characteristics, and
we tend to be drawn to lanugages that have the characteristics we
want.

I think this is very true. If you do not "fit" to the (Common) Lisp way
of thinking it can be a painful and futile experience. But this should
be relatively easy to find out by looking at some online books
(e.g. http://gigamonkeys.com/book/ or http://mitpress.mit.edu/sicp/).

How futile, then, to try to argue a programmer into changing his
favourite language, whatever that language may be.

At least, one should be very careful about this (I have also dissuaded
people from trying Lisp for their specific problem). It can cost a lot
of time until someone is productive in another language even if that
language has objective benefits.

Nicolas

 

[Nicolas Neuss]

In <[email protected]>, Nicolas
Neuss wrote:
[...]

If one uses a good Common Lisp implementation (especially one which
compiles to native code, as e.g. CMUCL/SBCL, Allegro CL, or
Lispworks), fI would expect that for most code the results for
equivalent code are not worse than C by a factor of 2 or maybe 3.

<cough, splutter> Er, okay, I think I'll put Lisp back on the shelf.
Look, it isn't dirty or anything. Thanks for your time, but I was
looking for something a little sportier. I mean, I knew it would be
slower, but a factor of TWO?

Please note my wording of "equivalent code". This arises when you have
some C program and want to do the same thing with Common Lisp. The
picture changes if you turn to tasks which exploit the dynamicity of
Lisp, and can not easily be done in C.

As an example consider the task of reading function definitions from a
file which are then evaluated many times in a numerical procedure (say
integration). In CL, this can be done by

1. reading the expression from a stream,

2. using the infix package for converting it to list syntax (if it
should be already in Lisp syntax you don't need the infix package,
but can simply use the standard CL read function),

3. compiling the function (the compiler is available also at runtime),

4. and then using that compiled function within the integration routine.

And the following piece of code does precisely that:

(in-package :cl-user)
(require :infix)

(defun integrate (f a b n)
(declare (type double-float a b)
(type fixnum n)
(type (function (double-float) double-float) f))
(let ((h (float (/ (- b a) n) 1.0d0)))
(declare (type double-float h))
(declare (optimize speed))
(* h (loop repeat n
for x of-type double-float from a by h sum
(funcall f x) of-type double-float))))

(defun integrate-input (a b n &key (stream *standard-input*))
(loop for input = (read-line stream nil)
while (and input (string/= input ""))
for source = `(lambda (x)
(declare (type double-float x)
(optimize speed))
,(infix:string->prefix input))
do
(format t "integral(~A,~F,~F)=~F~%" input a b
(integrate (compile nil source) a b n))))

You could interactively use it as follows:

(integrate-input 0.0 1.0 10000000) <-- user input

x^^3 <-- user input

[some compilation output which could be suppressed]
integral(x^^3,0.0,1.0)=0.24999994987310878 <-- output

cos(x)*exp(pi*x) <-- user input

[some compilation output which could be suppressed]
integral(cos(x)*exp(pi*x),0.0,1.0)=5.116088668778863 <-- output

And using a CL implementation which generates native code, e.g. SBCL,
every answer is calculated really fast, because optimized machine code
was used.

Maybe you could do similar things with C in a non-standard way by
dynamical linking with freshly compiled binary code. But in CL, this
whole process of reading and compiling a piece of code is standard and
reasonably fast. Therefore, also calling the above function on a batch
file containing very many function definitions would be reasonably fast.

So, in conclusion, if you could provide an equivalent code in C (please
try!), I think that I could easily choose the number of function
definitions in the batch file and the number of integration points so
that your program would work much slower than the CL version (and not
only by a factor of 2 or 3!).

Nicolas

 

[Ben Bacarisse]

Power consumption for the current round of processors is
approximately linear with clock speed. Code implemented
with better algorithms or more efficient compilers ca be run
at lower clock speeds or can shut the cpu down a greater
percentage of time. A side effect is reduced EMI.

The numbers are significant. I know a cell phone company
that extended battery life by 40% by re-compiling with a
different compiler.

Presumably when its running and doing something that uses the CPU? I
can't see how my phone could use 40% less battery since only a gross
programming error could account for it using an significant amount
power for the CPU for most of the day.

 

[Pascal J. Bourguignon]

You lost me. Why do it again if you've already done it?

I am reminded of a friend of mine who works for Oracle. His team had a
visitor one day (early 1990s), a C++ compiler vendor who was touting
his product. He spent about an hour presenting a model of three-phase
commit in C++, through which my friend's team sat with patience but
increasing incredulity. Eventually, the vendor noticed their
expressions, and asked what was wrong. "Have I screwed up?" he wanted
to know. (He'd designed the 3PC model himself and had been quite
proud of it up until then.) "No no no, it's not that at all", they
reassured him. He'd got a few bits wrong here and there but nothing
major. But... "we've DONE all this, in C, YEARS ago. Took us ages.
Cost a lot of money. And now you want us to do it AGAIN?"

Yes, and there's a perfectly good reason to do it again!

If it took them ages to implement it, it is probably a complex and
unmaintenable implementation. With a language of a higher level, they
could probably implement it much more simply (as indicated by the
fact that it was presented to them in a single-hour presentation).
Therefore they would now have an implementation that is much more
maintainable, and with much fewer hidden bugs.

 

[Alessio Stalla]

You lost me. Why do it again if you've already done it?

The point is not doing it again; the point is that the cited factor of
2 to 3 applies to code that is more or less the same in C and in Lisp
(with different syntax of course). There are problems you can solve
efficiently in Lisp which are painfully hard to solve efficiently in
languages without a compiler available at runtime. The same applies,
e.g., to Erlang and problems involving heavy concurrency, Prolog and
logic-based problems, etc.

 

[Pillsy]

you could try scheme it's smaller and simpler and designed as a
teaching language. There are compiled versions as well if you really
cannot sacrifice speed.

You'll probably sacrifice about the same amount of speed with compiled
Scheme as you will with compiled Common Lisp; if your reaction upon
learning that CL code usually runs about half as fast as equivalent C
code is, "Damn, that's way too SLOW!"[1] it's unlikely that either one
is really going to appeal to you.

Also, it's not unheard of for Lisp to actually be faster than C, often
because it allows you to do things that are very awkward in C much
more easily. You can do a lot with closures and you can do a lot more
with Lisp macros[2].

Cheers, Pillsy

[1] My reaction was, "Damn that's FAST!" but there the chief
competitor was Python. Python's a fine language, but not so speedy.

[2] To paraphrase Mark Twain, the difference between Lisp macros and C
macros is like the difference between lightning and a lightning bug.

 

[Nick Keighley]

Presumably when its running and doing something that uses the CPU?  I
can't see how my phone could use 40% less battery since only a gross
programming error could account for it using an significant amount
power for the CPU for most of the day.

well even if you're doing nothing (not making any calls) your phone
isn't quite doing nothing. It needs to keep track of which cell it's
in which means at least listening to the nearby base-stations. If you
move about it may need to tell system which cell it's moved to (this
is called "registration"). This is so the system knows where to find
you when someone calls you.

 

[Walter Banks]

Presumably when its running and doing something that uses the CPU? I
can't see how my phone could use 40% less battery since only a gross
programming error could account for it using an significant amount
power for the CPU for most of the day.

What it essentially did was optimize the number of processor
cycles that was needed to accomplish each task. At the risk
of starting another GCC vs the rest thread, GCC was the original
compiler. The performance improvement is consistent with
the high end of GCC compilers vs processor specific commercial
compilers. There were minimal coding changes, just enough to
port the code between compilers.

Even if the processor was running for 2% of the total time saving
40% of the cycles will improve the battery life by an apparent
40%.

We once did a compiler that optimized for power consumption
that was primarily used for data loggers. In it we profiled the
instruction set and the off chip vs on chip memory accesses. The
compiler used this information as part of instruction selection and
data allocation. The power saving for a battery operated device
were significant. In one project we implemented, the combination
of algorithmic changes and compiler changes moved the battery
life from 9 to 14 months.

Regards,

 

[Nick Keighley]

The point is not doing it again; the point is that the cited factor of
2 to 3 applies to code that is more or less the same in C and in Lisp
(with different syntax of course). There are problems you can solve
efficiently in Lisp which are painfully hard to solve efficiently in
languages without a compiler available at runtime. The same applies,
e.g., to Erlang and problems involving heavy concurrency, Prolog and
logic-based problems, etc.

For instance I've seen a C++ application that processes some
statistics
and it needs to calculate derived values from the initial input.

So there's a specification with things in like

D1 = B1 + B2 + B3
D2 = D1 * 15_MINUTES / 100

etc. (ie. derived count is the sum of input count 1 plus input count
2.
Yo! Cobol).

As the spec was a bit volatile they implemented a calculator in C++.
Hence the equations could be loaded from a file and processed. The
file was human readable enough to be verified by application experts
without them learning C++.

A simple Domain Specic Langauge. Of course you've had to implement
an interpreter in C++, which isn't hard for something as simple as
this
but would have been trivial and *more efficient* in a compiled Lisp

 

[Alessio Stalla]

For instance I've seen a C++ application that processes some
statistics
and it needs to calculate derived values from the initial input.

So there's a specification with things in like

    D1 = B1 + B2 + B3
    D2 = D1 * 15_MINUTES / 100

etc. (ie. derived count is the sum of input count 1 plus input count
2.
Yo! Cobol).

As the spec was a bit volatile they implemented a calculator in C++.
Hence the equations could be loaded from a file and processed. The
file was human readable enough to be verified by application experts
without them learning C++.

A simple Domain Specic Langauge. Of course you've had to implement
an interpreter in C++, which isn't hard for something as simple as
this
but would have been trivial and *more efficient* in a compiled Lisp

That's a perfect example of a problem where Lisp can give a
competitive advantage. This advantage is much reduced - perhaps even
non-existent - when the problem is completely known in advance and has
no dynamic aspects. The conjecture many Lisp programmers believe in -
also jokingly expressed in Greenspun's 10th rule - is that most
complex applications do involve at least some dynamic aspects, and
usually those are the most difficult to get right, so having a
language with powerful metaprogramming facilities, dynamic typing,
runtime evaluation and compilation, etc. can be a win.

Alessio

 

[Richard Tobin]

1. reading the expression from a stream,

2. using the infix package for converting it to list syntax (if it
should be already in Lisp syntax you don't need the infix package,
but can simply use the standard CL read function),

3. compiling the function (the compiler is available also at runtime),

4. and then using that compiled function within the integration routine.

While this is one of the great advantages of a language like Lisp,
it reintroduces the sort of security issues you might have thought
you'd escaped by not having to worry about buffer overflows and
the like. Without safeguards, the expression can do *anything*,
such as deleting files.

-- Richard

 

[Ben Bacarisse]

What it essentially did was optimize the number of processor
cycles that was needed to accomplish each task. At the risk
of starting another GCC vs the rest thread, GCC was the original
compiler. The performance improvement is consistent with
the high end of GCC compilers vs processor specific commercial
compilers. There were minimal coding changes, just enough to
port the code between compilers.

Even if the processor was running for 2% of the total time saving
40% of the cycles will improve the battery life by an apparent
40%.

At the risk of appearing ignorant, I have to say that I can't see how
this could be so. This would be self-evident if nothing but the CPU
used power, but when the CPU is running for 2% of time, surely the
battery is being drained 100% of the time by other things (the radio
receiver would be significant, I would image).

We once did a compiler that optimized for power consumption
that was primarily used for data loggers. In it we profiled the
instruction set and the off chip vs on chip memory accesses. The
compiler used this information as part of instruction selection and
data allocation. The power saving for a battery operated device
were significant. In one project we implemented, the combination
of algorithmic changes and compiler changes moved the battery
life from 9 to 14 months.

That seems natural, but presumably the CPU and memory access were the
main uses of power to begin with.

 

[Ben Bacarisse]

well even if you're doing nothing (not making any calls) your phone
isn't quite doing nothing. It needs to keep track of which cell it's
in which means at least listening to the nearby base-stations. If you
move about it may need to tell system which cell it's moved to (this
is called "registration"). This is so the system knows where to find
you when someone calls you.

Obviously. Are you saying that halving (say) the number of cycles
used for this intermittent background activity will give 40% more
battery life or just that is will have some effect? I have no problem
with the latter; it the huge effect from optimising intermittent
activity I am having trouble understanding.

 

[Seebs]

Presumably when its running and doing something that uses the CPU? I
can't see how my phone could use 40% less battery since only a gross
programming error could account for it using an significant amount
power for the CPU for most of the day.

Well, that's sort of the point -- most of the time, it's not using significant
power. (Note the HUGE gap between talk time and standby time...) So reducing
the power consumption of the times when it is using power is very close to
reducing overall power consumption by a comparable amount...

-s

 

[Seebs]

At the risk of appearing ignorant, I have to say that I can't see how
this could be so. This would be self-evident if nothing but the CPU
used power, but when the CPU is running for 2% of time, surely the
battery is being drained 100% of the time by other things (the radio
receiver would be significant, I would image).

bring_radio_to_full_power();
do_something_cpu_intensive();
reduce_radio_to_partial_power();

-s

 

[Alessio Stalla]

While this is one of the great advantages of a language like Lisp,
it reintroduces the sort of security issues you might have thought
you'd escaped by not having to worry about buffer overflows and
the like.  Without safeguards, the expression can do *anything*,
such as deleting files.

Sure, in general you cannot use this technique freely with untrusted
input, however in the case of the integrator the source to be compiled
comes from a trusted user, and this is the case in a broad number of
applications with some sort of integrated language. Also, writing a
sandbox in Common Lisp is not hard at all, although afaik no one has
published one as a library. If only I had infinite time... *sigh*

Alessio

 

[Stanislaw Halik]

While this is one of the great advantages of a language like Lisp,
it reintroduces the sort of security issues you might have thought
you'd escaped by not having to worry about buffer overflows and
the like. Without safeguards, the expression can do *anything*,
such as deleting files.

That's why only certain symbols are typically allowed inside
user-specified expressions.

 

[Walter Banks]

At the risk of appearing ignorant, I have to say that I can't see how
this could be so. This would be self-evident if nothing but the CPU
used power, but when the CPU is running for 2% of time, surely the
battery is being drained 100% of the time by other things (the radio
receiver would be significant, I would image).

Most cell phones are pretty aggressive over power use. I believe that
that most shuts down their receivers for a significant percentage of
the time. They periodically wake up and check for data packets.

I am pretty sure of the numbers.

Regards,

Walter..