But Lisp is *SLOW* Compared to C/C++
Satan - The Evil 1
After reading the "Lisp in the Real World" thread I have
the following opinion :) to raise and would be interested
to hear some other "non-religious" opinions regarading
Lisp compared to languages such as C/C++ in the area of
application speed and efficiency.
*Please don't take this as a flame or a troll*
Lisp seems OK for prototyping and implementing higher level
business rules and for general scripting, but it simply
will never be able to compete with languages such as
C and C++ (and to a lesser extent languages such as VB
and Delphi under Windows).
Have you noticed...
You don't see fast numerical libraries written in Lisp.
You don't see scientific libraries written in Lisp.
You don't see commercial games written in Lisp.
You don't see application suites written in Lisp.
In fact, you don't see any mainstream commercial applications
written in Lisp for the the basic reason that any
competitor will simply go out and write their competing
application in C/C++ and make a faster, more responsive
application that makes more efficient use of machine
resources. Why do you think that, despite the massive
amount of hype, no mainstream apps have been written
in Java? Because it is too slow for the real world when
compared to equivalent code written in C or C++.
I would say that C++ has such a bad repution amongst Lisp
programmers because it takes several years to become
a very good and efficient C++ programmer whilst you can
quickly become an efficient Lisp programmer. The massive
number of *bad* C++ programmers certainly doesn't help
its reputation. An experienced C++ programmer can write
truelly elegant, safe, and efficient code that leaves
the equivalent Lisp code in the dust.
Of course, the ease at which you can write good code in
Lisp is a major point in its favour.
But to sum up; we always seem to push hardware to its
limits and because of this languages such as C and C++
will maintain their edge over languages such as Lisp.
I suppose one day we may have computers with more
processing power than we could ever make use of
(e.g. quantum computers) and then it will be commercially
feasible to throw away the low-level languages. But I
imagine by that time Artificial Intelligences will have
done away with programmers alltogether.
OK now... go ahead an rip my argument to shreds :)
Cheers,
- PCM
Shaun Flisakowski
In article <5puscn$e0h$1...@cdn-news.telecom.com.au>,
Satan - The Evil 1 <sa...@vus002.telecom.com.au> wrote:
:After reading the "Lisp in the Real World" thread I have
:the following opinion :) to raise and would be interested
:to hear some other "non-religious" opinions regarading
:Lisp compared to languages such as C/C++ in the area of
:application speed and efficiency.
:Lisp seems OK for prototyping and implementing higher level
:business rules and for general scripting, but it simply
:will never be able to compete with languages such as
:C and C++ (and to a lesser extent languages such as VB
:and Delphi under Windows).
:
:Have you noticed...
: You don't see fast numerical libraries written in Lisp.
: You don't see scientific libraries written in Lisp.
: You don't see commercial games written in Lisp.
: You don't see application suites written in Lisp.
:
:In fact, you don't see any mainstream commercial applications
:written in Lisp for the the basic reason that any
:competitor will simply go out and write their competing
:application in C/C++ and make a faster, more responsive
:application that makes more efficient use of machine
:resources. Why do you think that, despite the massive
:amount of hype, no mainstream apps have been written
:in Java? Because it is too slow for the real world when
:compared to equivalent code written in C or C++.
I think that's more because most programmers don't
_like_ Lisp very much. Notice all the crap being made in/for
VB - and that's _interpreted_, at least Lisp can be compiled.
Look at the popularity of perl - a garbage collected interpreted
language. The upcoming popularity of Java, again garbage collected
and interpreted.
If the programmers wanted to Lisp, and there was a abundance of
Lisp programmers, companies would make programs written in Lisp.
:But to sum up; we always seem to push hardware to its
:limits and because of this languages such as C and C++
:will maintain their edge over languages such as Lisp.
:I suppose one day we may have computers with more
:processing power than we could ever make use of
:(e.g. quantum computers) and then it will be commercially
:feasible to throw away the low-level languages. But I
:imagine by that time Artificial Intelligences will have
:done away with programmers alltogether.
Whoa. I suspect quantum computers will come long before AI
makes any significant headway; unless you mean that the
indeterism in quantum computers might allow something closer
to an actual brain, in which case I dunno.
Again we see the popularity of numerous "unefficient" languages,
Java, Tk/Tcl, and Perl.
:OK now... go ahead an rip my argument to shreds :)
I'm not a regular Lisp programmer, btw; I use mostly C/C++ and Delphi.
Personally, I prefer Scheme to Lisp; it strikes me as a cleaner,
more orthogonal language.
--
Shaun flis...@cs.wisc.edu
http://www.kagi.com/flisakow - Shareware Windows Games, and Unix Freeware.
"In your heart you know its flat."
-Flat Earth Society
Vassil Nikolov
Yet another popular subject...
Satan - The Evil 1 wrote:
> ... text omitted...
>
> I would say that C++ has such a bad repution amongst Lisp
> programmers because it takes several years to become
> a very good and efficient C++ programmer whilst you can
> quickly become an efficient Lisp programmer.
In my opinion, no one can quickly become an efficient Lisp
programmer.
(No one can quickly become an efficient programmer in any
language, for that matter...)
And even if the above were true, I don't think that has any
contribution to the negative attitude towards C++.
I also don't think that an efficient Lisp programmer would
have any problems becoming an efficient C++ programmer
(apart from overcoming their distaste for C++, that is).
> ... text omitted...
My 2 centimes worth, I guess.
--
Vassil Nikolov, visitor at LRI:
Laboratoire de Recherche en Informatique, Universite Paris-Sud
Until 9 July 1997: Vassil....@lri.fr
Normally: vnik...@bgearn.acad.bg
Gareth McCaughan
Someone calling himself "Satan - The Evil 1" (but I beg leave to doubt
whether that's really who it was) wrote:
> Have you noticed...
> You don't see fast numerical libraries written in Lisp.
> You don't see scientific libraries written in Lisp.
> You don't see commercial games written in Lisp.
> You don't see application suites written in Lisp.
>
> In fact, you don't see any mainstream commercial applications
> written in Lisp for the the basic reason that any
> competitor will simply go out and write their competing
> application in C/C++ and make a faster, more responsive
> application that makes more efficient use of machine
> resources.
That might be part of it. I think more relevant facts are:
- There are way, way fewer Lisp programmers than C programmers
around.
- Lisp programmers are usually not very interested in writing
mainstream commercial applications.
- Vendors haven't really targetted their Lisp systems for the
ability to produce mainstream commercial applications.
- The people producing the mainstream commercial applications
have a long history of writing stuff in C. They probably
haven't even considered considering higher-level languages.
It's a cultural thing.
> Why do you think that, despite the massive
> amount of hype, no mainstream apps have been written
> in Java? Because it is too slow for the real world when
> compared to equivalent code written in C or C++.
Actually, there has been at least one mainstream app written in
Java. Unfortunately.
There's no reason why you couldn't make a Java compiler that
produces code at least as good as you get from a C or C++ compiler.
However, for cultural reasons this hasn't been done yet: everyone
is more interested (rightly) in writing Java compilers that target
the JVM, so that the code they produce is portable.
> I would say that C++ has such a bad repution amongst Lisp
> programmers because it takes several years to become
> a very good and efficient C++ programmer whilst you can
> quickly become an efficient Lisp programmer.
I don't agree. It's certainly much faster to become able to write
non-trivial programs in Lisp than to become able to write non-trivaial
programs in C++, because Lisp is a much more elegant language. But
becoming *very good and efficient* in any language takes time, and
Lisp isn't an exception.
> The massive
> number of *bad* C++ programmers certainly doesn't help
> its reputation. An experienced C++ programmer can write
> truelly elegant, safe, and efficient code that leaves
> the equivalent Lisp code in the dust.
If this is true, it's only because of shortcomings in the available
Lisp implementations. In other words, if your argument is valid then
it's not an argument against Lisp but an argument against Allegro
Common Lisp, LispWorks, Macintosh Common Lisp, and all the other
specific compilers out there.
(And I'm not sure it's true at all.)
> But to sum up; we always seem to push hardware to its
> limits and because of this languages such as C and C++
> will maintain their edge over languages such as Lisp.
This might be true if "languages such as Lisp" means "languages
that happen not to have any implementations with properties X,Y,Z".
But I don't think that's really a language issue.
And, of course, even if everything you've said is right, it
doesn't apply to every field of programming. You mentioned
artificial intelligence, for instance. If you're right in predicting
that programmers will be made obsolete by AI, then I bet you the
programs that make them obsolete won't be written in C.
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
gj...@dpmms.cam.ac.uk Cambridge University, England.
Alasdair McIntyre
In article: <5puscn$e0h$1...@cdn-news.telecom.com.au>
>
> After reading the "Lisp in the Real World" thread I have
> the following opinion :) to raise and would be interested
> to hear some other "non-religious" opinions regarading
> Lisp compared to languages such as C/C++ in the area of
> application speed and efficiency.
> Have you noticed...
> You don't see fast numerical libraries written in Lisp.
> You don't see scientific libraries written in Lisp.
> You don't see commercial games written in Lisp.
> You don't see application suites written in Lisp.
I suggest you take a look at the following reference:
R. Bradley Andrews (Brad_A...@rbacomm.com)
"Speeding Game Development and Debugging (Lisp
finds a niche in the game development arena)",
pp.28-31, Object Magazine, May 97,
SIGS Publications (http://www.sigs.com).
Here are some edited quotes which you may find revealing:
"Nichimen Graphics used LISP to devlop their powerful
N-World development environment... Nintendo used N-World
to produce all the characters in their flagship 64-bit
game, "Mario 64" (including Mario himself)."
"...Naughty Dog Software - makers of "Crash Bandicoot,"
the current mascot for the Sony Playstation - have proven
that it [LISP] can [hook together a modern game that gets
played]. Like their previous release, "Way of the Warrior,"
their current bestseller uses LISP code for significant
parts of the game, including character control and AI
functionality."
"Gavin [Naughty Dog co-founder] emphasizes that some ideas
about LISP are outdated... The speed issue is one where
reality is different than the perception. "It is easy to
construct a simple dialect which is just as efficient as
C, but retains the dynamic and consistent qualities that
make LISP a much more effective expression of one's
programming intentions," adds Gavin."
Copyright acknowledged.
Hope you find this informative.
--
alasdair mcintyre - thermoteknix
<initial>"dot"<surname>"at"<company>"dot"com
Pierpaolo Bernardi
: I'm not a regular Lisp programmer, btw; I use mostly C/C++ and Delphi.
: Personally, I prefer Scheme to Lisp; it strikes me as a cleaner,
: more orthogonal language.
Do you mean Scheme is not Lisp? This is weird.
: --
Fred Haineux
sa...@vus002.telecom.com.au (Satan - The Evil 1) wrote:
| After reading the "Lisp in the Real World" thread I have
| the following opinion :) to raise and would be interested
| to hear some other "non-religious" opinions regarading
| Lisp compared to languages such as C/C++ in the area of
| application speed and efficiency.
|
Why not? It *IS* a troll. You can tell it's a troll because anyone with
half-a-brain would have looked in DejaNews and seen that this "brilliant
insight" is posted about once a WEEK, and has been for the last ZILLION
YEARS.
Does this reflect well on C programmers's intelligence or programming
style, if they can't even consider the idea that someone somewhere has
already talked about this topic? No wonder "reusable code" is such a
hot-button!
IF you want real answers to your questions, GET OFF YOUR ASS and go look.
Go ask a Lisp vendor what "real world" apps have been written. For crying
out loud, go read the back scroll of comp.language.lisp
(<http://www.dejanews.com/> found almost 500 articles when I did a simple
query). Don't bother us Lisp weirdos. We're busy hacking dumb things with
lambda calculus.
IF you don't want answers, just go back to your C++ and write some code.
You have my OFFICIAL permission to do so. If you want to feel that C++ is
better, GO RIGHT AHEAD. I don't CARE.
After all, everyone knows that the BEST language in the ENTIRE WORLD is
COBOL, because there's more COBOL code than ALL OTHER LANGUAGES PUT
TOGETHER.
Have a really nice day,
HEINOUS
ps. If application speed is so damn important, explain damn near any
Microsoft product. "Slow, huge programs"? The most popular software in the
world -- and it's written in C.
Martin Rodgers
With a mighty <86g1tox...@g.pet.cam.ac.uk>,
gj...@dpmms.cam.ac.uk uttered these wise words...
> Someone calling himself "Satan - The Evil 1" (but I beg leave to doubt
> whether that's really who it was) wrote:
Well, it's not me. ;-)
> - There are way, way fewer Lisp programmers than C programmers
> around.
This is hard to dispute. I doubt that book publishers are stupid. If
there's money to be made by publishing books that sell, and books
about a particular language do in fact sell, then they'll go for it.
Either there's less interest in Lisp than C/C++, or there's a book
publishing conspiracy.
> - Lisp programmers are usually not very interested in writing
> mainstream commercial applications.
Not too long ago a follow Lisp programmer tried to convince me that
there are more programmers who know Lisp than SQL. His evidence seemed
to be anecdotal, as his sample of programmers only included his
colleagues and the students that he teaches Lisp to. He later argued
that his claim was true of programmers in the city where he lived,
which I couldn't dispute.
Why were we discussing (by email) the relative popularity of SQL vs
Lisp? We began by discussing the use of CL-HTTP as an alternative to
the various - and popular - web server extensions that use database
features. I suggested that most people wanted a familiar query
language.
> - Vendors haven't really targetted their Lisp systems for the
> ability to produce mainstream commercial applications.
Coupling CL-HTTP with a Lisp package would be very tasty. If the Lisp
aspects could be hidden behind a less "Lisp-ish" syntax, not unlike
mu-simp, it might even look "friendly" to non-Lisp people (the kind of
people who're scared off by the simplicity of the Lisp non-syntax).
Some heavy marketing might also help.
> - The people producing the mainstream commercial applications
> have a long history of writing stuff in C. They probably
> haven't even considered considering higher-level languages.
This is why I believe that heavy marketing could help. It might even
be necessary, if we consider the myths about Lisp that need killing
before we can even begin to discuss Lisp with some people.
> It's a cultural thing.
Hmm. Lisp Machines are not what most people want, and yet this seems
to be what many Lisp people are still lusting after. We know how
bloody OS wars can be, but the culture that comes with an OS can also
create friction. Consider the hostility toward command lines, for
example. Any "negative" feature associated with an OS can do this.
Those of us who don't feel such hostility perhaps understand that
feature and appreciate it. Others may understand it and yet still
dislike it. The rest could be baffled and scared of it, because it's
something that they don't understand and it intimidates them.
To remove the hostility, perhaps we first have to create
understanding, then an appreciating. This could be as true for
programmers as it is for non-programmers. Being techie doesn't mean
that a person will understand and appreciate all things technical.
> Actually, there has been at least one mainstream app written in
> Java. Unfortunately.
There are also many that don't get much attention, because they just
quietly work for the people who wrote them and the people they work
for. The same is true for a lot of languages, including Lisp.
> There's no reason why you couldn't make a Java compiler that
> produces code at least as good as you get from a C or C++ compiler.
> However, for cultural reasons this hasn't been done yet: everyone
> is more interested (rightly) in writing Java compilers that target
> the JVM, so that the code they produce is portable.
There are also historical reasons. We should be comparing Java to
languages with an equally short history, or at least with languages at
a point where their history was equally short.
Unfortunately, there are a few people who appear to prefer to ignore a
language's history, and perhaps even distort it. If Java was 20 years
old, perhaps it would be fair to compare it with C. Perhaps if it was
15 years ago, it might be fair to compare it with C++.
There's also the possibility that some people are using Java for
things they might not have considered doing in C++. I know that there
are things I won't hesitate to do in Lisp that I'd never have dreamed
of doing in C or C++. One language opens up my imagination by making
hard things easy, while the other makes simple things hard work.
However, once I've written something in Lisp, and found that it works
and is useful, I can then think about how to write it in C++.
This is not too different from writting a tool in a shell language,
awk, or perl, producing a solution quickly and easily. Later, after
you've used your tool enough to see that it's worth the trouble, you
can re-write it in C++. If you started in C++, you might never start
it, or possibly worse, spend a lot of time on it but never complete
it, making your time and effort a waste.
--
<URL:http://www.wildcard.demon.co.uk/> You can never browse enough
Please note: my email address is gubbish
Will write Lisp code for food
Larry Gordon
During the peak AI years in the 60's special machines were written that
only did lisp (as I'm sure everyone that is reading this obvious troll /
crossposted thread in comp.sys.lisp is aware of).
The fact is that lisp was a language very useful for ai applications
because of it's nature. C++ exists because the UN*X community was
indoctrinated with C in college (because of the computers used in school).
The C language then took on C++ because of widespead support for object
oriented methodologies and a familiar programmer base with 'C' Since C /
C++ are easy to write to hardware in a manner that is familiar and
understandable to both hardware and software engineers, it has become
supported in mainstream computer systems. API's were written into the
operating system (which have been mainly written in C/C++) and the support
for application developers was written in C/C++.
My opinion is that anyone who uses computers to develop
software and wants to have marketable skills needs to
learn the following:
C or C++
familiarity with unix and windowing systems
API libraries (MFC, STL) or that for the operating system you are using
User Interface design fundamentals
Event based programming
Embedded programming fundamentals
Familiarity with threads and multiprocess communication
Debugging
An editor style(brief/EMACS)
Perl or Rexx
Other languages as needed (LISP could be added here in support of a
particular project or as scripting for EMACS)
Object methodologies (OOA/D, Booch or OMT, patterns)
Familiarity with makefile utilities
Familiarity with version control and configuration management
Some type of prototyping package (visual basic/rexx)
Good coding style that is readable and understood by others
Good communication skills and the ability to get along with *ANYONE*
Complete understanding of the problem at hand
Total humility to admit when you do not understand something completely
and are willing to ask questions.
An understanding of full time employment benefits as well as dealing with
contract engineering (you are either a ass kisser, an ass, or a
mercenary...)
The students/young professionals out there wondering what they need to
learn to be marketable need to become good engineers, knowledgable in
tools and technologies, but must first be responsible human beings.
Just my rants.
I welcome any comments,
Larry
-----------------------------------------------------------------------
Laurence A. Gordon
Intelligent Medical Imaging, Inc "No generalization is worth a damn,
4360 Northlake Blvd including this one." -- Will Rogers
Palm Beach Gardens, FL 33410
(561) 627-0344 XT 3201 DISCLAIMER
The opinions of the aforenamed individual
799 Sanctuary Cove Dr. might not be the same as his employer's.
North Palm Beach, FL 33410 If you feel like telling his boss about how
(561) 776-6336 much of an insensitive, obnoxious jerk the
author is, don't bother. He already knows.
-----------------------------------------------------------------------
Tyson Jensen
> Do you mean Scheme is not Lisp? This is weird.
Scheme is a subset of lisp, like C is a subset of C++. There are C
programmers out there who prefer C to C++, citing the simplicity and
standardization present in C. Standards exist in C++, but they aren't
uniformly implemented by compilers such as Microsoft VC++.
--
Tyson Jensen
tje...@mosbych1.com
Dave Hinson
Larry Gordon wrote:
> because of it's nature. C++ exists because the UN*X community was
> indoctrinated with C in college (because of the computers used in school).
Actually I believe the success of C can be most directly attributed to
the successful proliferation of UN*X into mainstream computing,
regardless of what treatment it may or may not have had in schools. If
it were not for UN*X, and the need to port it to platforms other than
DEC PDPs (work initially funded by corporate dollars, not academic
ones), it is very likely there would've never been a K&R effort to begin
with. And since C libraries remain the dominate programming interface
to UN*X system call services, and most kernel source is implemented in
C, it's presence in the marketplace is at least proportional to that of
UN*X. Nowhere else in computing will you find this kind of mutual
symbiotic success between OS and language. Early commercial acceptance
eventually made C "safe" to consider for the desktop, where it
flourished largely because of its low-level expressive power and small
footprint. Plus the fact that it's just a damn good little language.
I would say academia had more of an impact on the successful evolution
of UN*X (e.g. the work with BSD) than the popularity of C as a general
purpose programming language. Of course, granted, the latter did
benefit from the former. And I would agree that C++ had its roots in
academia, although its early explosive popularity growth can only be
attributed to market hysteria... ::shields up::
Where's data modeling?? Schema design, creation and optimization,
access method tuning, relationship integrity methods, etc. College
grad: "Yes sir, I can screw up your company's data in 7 different
languages..."
// David Hinson
// dhi...@rational.com
Pierpaolo Bernardi
Tyson Jensen (tje...@mosbych1.com) wrote:
: > Do you mean Scheme is not Lisp? This is weird.
: Scheme is a subset of lisp, like C is a subset of C++.
This is false.
: There are C programmers out there who prefer C to C++,
Duh. If they are C programmers, this is comprehensible.
Sorry, I don't care about C and C++.
The point is that Scheme _is_ lisp, you are confused about what lisp is.
Scheme is lisp, so is Common Lisp, so is Lisp 1.5, so is T, so is NIL,
so is Maclisp, so is Interlisp, so is Franz Lisp, so is Mulisp, so is
Multilisp, so is Standard Lisp, so is Portable Standard Lisp, so is
Oaklisp, so is elisp, so is xlisp, so is ISO Lisp, so is Eulisp, so is
*lisp, so is 1100 Lisp.
Sorry for the ones that I forgot, hope you got the idea anyway.
: --
: Tyson Jensen
: tje...@mosbych1.com
Jason Trenouth
On 9 Jul 1997 04:58:57 GMT, flis...@fontina.cs.wisc.edu (Shaun Flisakowski)
wrote:
> :Have you noticed...
> : You don't see fast numerical libraries written in Lisp.
> : You don't see scientific libraries written in Lisp.
> : You don't see commercial games written in Lisp.
> : You don't see application suites written in Lisp.
> :
None of the above are true, of course. BTW The third domain is perhaps the
most in fashion of those listed.
__Jason
David Thornley
In article <5q2lv2$u2e$1...@serra.unipi.it>,
Pierpaolo Bernardi <bern...@cli.di.unipi.it> wrote:
>Tyson Jensen (tje...@mosbych1.com) wrote:
>: > Do you mean Scheme is not Lisp? This is weird.
>
>: Scheme is a subset of lisp, like C is a subset of C++.
>
>This is false.
>
implementations. C is not a subset of C++, but the two languages
have a large common subset, much closer to the whole of C than the
whole of C++. There are reasons why it is bad to write soley in
the subset, and you can get a good explanation out of comp.lang.c.
Therefore, Scheme is a subset of Lisp like C is a subset of C++
like fish are a subset of Amazonian life forms - all are false.
Having said that, I'd like to get back to my favorite C/C++/whatever
vs. Lisp rant.
Assume two programmers, both competent, one in C or C++ or something
similar, one in Lisp.
Both write a program to solve a given task. At the end of a certain
time period, they have initial versions. The C version is efficient,
but it doesn't work. The Lisp version works, but is inefficient.
Now, it's obvious to everybody that the program has to work (well,
everybody not involved with Microsoft), but it isn't obvious that
it has to work efficiently. There is a strong temptation to ship the
Lisp version and report to the customers that the C program is coming
along nicely.
Suppose that both programmers continue. Both will end up with a
working, efficient program. The Lisp programmer is likely to finish
sooner, and the Lisp version will be more maintainable (to good
Lisp programmers) than the C version (to good C programmers).
The Lisp version is likely to work better, and will be less susceptible
to certain classes of bugs (like slow memory leaks).
There's also the cultural thing. Most programming books I've seen
make reference to machine efficiency (sometimes mistakenly). There
are exceptions, notably Kernighan and Plauger's (is that correct?)
superb _Elements_of_Programming_Style_. Most Lisp books mention
efficiency only briefly. Until Norvig's excellent book came out,
I didn't have one that helped me write efficient Common Lisp programs.
Another thing that gave rise to the inefficient Lisp myth is that
Lisp runtimes are usually considerably larger than older C
runtimes, and therefore there was a strict limit to how small a
Lisp executable could be, as opposed to a C executable. This is
changing, as the standard applications are getting bigger and the
old, lean, C runtimes are replaced by the more modern and fatter
C++ runtimes, while Lisp runtimes aren't getting much bigger.
>: There are C programmers out there who prefer C to C++,
>
>Duh. If they are C programmers, this is comprehensible.
>
Matter of opinion. The thing to remember about C++ is that you
don't have to use all the features. Operator overloading can get
you into deep weeds if you use it inappropriately, templates can
bloat your executables, RTTI can be used to make some really ugly
programs, and so on. I prefer C++ to C because there are some
things you can do in C++ that you can't do anywhere near as well
in C, and I am old and scarred enough to use the neat powerful stuff
only when appropriate.
>The point is that Scheme _is_ lisp, you are confused about what lisp is.
>
>Scheme is lisp, so is Common Lisp, so is Lisp 1.5, so is T, so is NIL,
>so is Maclisp, so is Interlisp, so is Franz Lisp, so is Mulisp, so is
>Multilisp, so is Standard Lisp, so is Portable Standard Lisp, so is
>Oaklisp, so is elisp, so is xlisp, so is ISO Lisp, so is Eulisp, so is
>*lisp, so is 1100 Lisp.
>Sorry for the ones that I forgot, hope you got the idea anyway.
>
Um, Pearl Lisp, the 8080 and 6800 Lisps in the old Doctor Dobb's
Journals I threw out last year, that CP/M Lisp I used to use and
can't remember the name of any more.... Oh well, I'd rather use
any of them than COBOL or Pascal (there's ones I wouldn't prefer
over C, but that's another story).
David Thornley
Jason Trenouth
Shaun Flisakowski
In article <5q09q4$r44$1...@pania.unipi.it>,
Pierpaolo Bernardi <bern...@cli.di.unipi.it> wrote:
>: I'm not a regular Lisp programmer, btw; I use mostly C/C++ and Delphi.
>
>: Personally, I prefer Scheme to Lisp; it strikes me as a cleaner,
>: more orthogonal language.
>
When I said Lisp, I was referring to common lisp, which I though had
been standardized.
I know that Scheme has been standardized, which seems like rather
unusual for a mere "dialect".
J.D. Jordan
C a subset of C++??? C came first!
Tyson Jensen wrote:
> > Do you mean Scheme is not Lisp? This is weird.
>
Robert Monfera
David Thornley wrote:
[snip]
>
> Another thing that gave rise to the inefficient Lisp myth is that
> Lisp runtimes are usually considerably larger than older C
> runtimes, and therefore there was a strict limit to how small a
> Lisp executable could be, as opposed to a C executable. This is
> changing, as the standard applications are getting bigger and the
> old, lean, C runtimes are replaced by the more modern and fatter
> C++ runtimes, while Lisp runtimes aren't getting much bigger.
I second this. SAP has been the world's most successful standard
application for half a decade, with a footprint of 20GB storage and
192MB - 2GB RAM (it just barely runs with 192MB, average is
256MB-1.5GB).
Even if you can write the same functionality in Lisp with a portion
of this storage footprint, the RAM requirements would not really change.
A few megs of Lisp (running or development) environment is just not
significant at all.
Just my 2 Fille'r.
Robert
Martin Rodgers
With a mighty <5q35sa$s...@spool.cs.wisc.edu>,
flis...@fontina.cs.wisc.edu uttered these wise words...
> When I said Lisp, I was referring to common lisp, which I though had
> been standardized.
Common Lisp and Scheme appear to me to be two dialects of the family
of languages that known as Lisp. Their semantics overlap, but CL
doesn't entirely enclose those of Scheme, nor do Scheme's semantics
entirely enclose those of CL.
The size of the language is a red herring. Think of the semantics as
sets, and then draw a Venn diagram. The sets intersect.
> I know that Scheme has been standardized, which seems like rather
> unusual for a mere "dialect".
Ohh, excellent flamebait. ;) Yep, Fortran is a subset of Basic, C++ is
a subset of Smalltalk, and _everything_ is a subset of Lisp. Hmm.
Well, that last one could be true (in the sense that _anything_ can be
added to Lisp), but you might not get away with it in a newsgroup like
comp.lang.c++. Would _you_ like to try it? Light the blue touch paper
and stand well back...
With Lisp, talking about sets of semantics is probably meaningless,
because we can extend the language in any way we like, so easily. If
you want to be pedantic, and only use the language as defined by the
language spec, then that's different. Does the Scheme spec specify a
standard macro system? Is that even necessary?
Meta-circular evaluators (SICP style) make _anything_ possible. All
you have to do is write your meta-circular evaluator.
Harley Davis
flis...@fontina.cs.wisc.edu (Shaun Flisakowski) writes:
> >: Personally, I prefer Scheme to Lisp; it strikes me as a cleaner,
> >: more orthogonal language.
> >
> >Do you mean Scheme is not Lisp? This is weird.
>
> When I said Lisp, I was referring to common lisp, which I though had
> been standardized.
Common Lisp has been standardized; there is ANSI Common Lisp. There
is also a dialect of Lisp called ISLisp that has been standardized by
ISO. However, "Lisp" is a generic term for a family of languages and
it is unlikely that any standard will ever be called "The Standard
Lisp". This was attempted with ISLisp and voted down; I doubt there
is any standards organization out there which will take up the banner
again.
-- Harley
-------------------------------------------------------------------
Harley Davis net: da...@ilog.com
Ilog, Inc. tel: (415) 944-7130
1901 Landings Dr. fax: (415) 390-0946
Mountain View, CA, 94043 url: http://www.ilog.com/
Harley Davis
ja...@harlequin.co.uk (Jason Trenouth) writes:
That's interesting. Could you give a couple of examples of commercial
games running compiled (or even interpreted) Lisp code. How about an
application suite? Anything mainstream?
Thanks,
Dennis Weldy
Doesnt really matter which came first, with regards to whether something
is a subset. Whether A is a subset of B depends on whether A intersect B =
A. If it does, then A is a subset of B. Doesn't matter whether you had B
first or not :-).
Strictly speaking though, there are enough differences between C and C++ to
make life interesting. :-)
So, realistically, there exists a set S = C intersect C++. S contains the
common language features and syntax. Note that S != C.
Dennis
J.D. Jordan wrote in article <33C4D182...@erols.com>...
>C a subset of C++??? C came first!
>
>Tyson Jensen wrote:
>
>> > Do you mean Scheme is not Lisp? This is weird.
>>
>> Scheme is a subset of lisp, like C is a subset of C++. There are C
>> programmers out there who prefer C to C++, citing the simplicity and
>> standardization present in C. Standards exist in C++, but they aren't
>>
>> uniformly implemented by compilers such as Microsoft VC++.
>>
>> --
>> Tyson Jensen
>> tje...@mosbych1.com
>>
>
>
>
>.
>
Martin Rodgers
With a mighty <33C4D182...@erols.com>,
jord...@erols.com uttered these wise words...
> C a subset of C++??? C came first!
And Scheme existed before Common Lisp. Not that will stop anyone from
calling Scheme a subset of CL. Perhaps it would be better to say that
C++ is a superset of C, and that CL is a larger language than Scheme?
I vaguely remember a language, I think called something like Comal,
that was a superset of Basic. At least, it looked like at the time, as
every Basic available on micros was pathetically small, and most of
them didn't even have WHILE/WEND.
For what it's worth, every Pascal compiler that I've used has been a
superset of ISO Pascal. I've even witnessed a Pascal programmer
refering to as Modular 2 as Pascal. Does that make M-2 a superset of
Pascal, or was he just wrong?
As a he was arguing with some C programmers at the time, perhaps he
was excused. I found it very hard to follow the debate, as neither
side were talking about the same languages. So it could've been
C/C++/K&R vs ISO Pascal/Turbo Pascal/M-2, respectively. No wonder I
was confused!
John Nagle
(Martin Rodgers) writes:
>jord...@erols.com
>> C a subset of C++??? C came first!
>And Scheme existed before Common Lisp. Not that will stop anyone from
>calling Scheme a subset of CL. Perhaps it would be better to say that
>C++ is a superset of C, and that CL is a larger language than Scheme?
No, Scheme came after Common LISP. Scheme was a reaction to Common
LISP by a group of people at MIT who wanted a simple, clean LISP.
Common LISP had too much junk in it at the insistence of the Symbolics
people, who wanted to justify their custom hardware. The original
Scheme paper is a joy to read; in a few tightly-written pages it
defines the whole language.
>For what it's worth, every Pascal compiler that I've used has been a
>superset of ISO Pascal. I've even witnessed a Pascal programmer
>refering to as Modular 2 as Pascal. Does that make M-2 a superset of
>Pascal, or was he just wrong?
Modula 2 is considered to belong to the Pascal/Modula/Ada family
of languages, but it is not a superset of Pascal. It isn't even a
superset of Modula 1. Pascal, Modula 1, and Modula 2 were designed
by Wirth; Modula 3 was designed at DEC, and Ada was designed through
a competition between four proposals.
John Nagle
Martin Rodgers
With a mighty <nagleED...@netcom.com>,
na...@netcom.com uttered these wise words...
> No, Scheme came after Common LISP. Scheme was a reaction to Common
> LISP by a group of people at MIT who wanted a simple, clean LISP.
> Common LISP had too much junk in it at the insistence of the Symbolics
> people, who wanted to justify their custom hardware. The original
> Scheme paper is a joy to read; in a few tightly-written pages it
> defines the whole language.
Hmm. I seem to recall finding references to Scheme: An interpreter for
the extended lambda calculus, Memo 349, MIT AI Laboratory, 1975. Does
Common Lisp predate this memo?
> Modula 2 is considered to belong to the Pascal/Modula/Ada family
> of languages, but it is not a superset of Pascal. It isn't even a
> superset of Modula 1. Pascal, Modula 1, and Modula 2 were designed
> by Wirth; Modula 3 was designed at DEC, and Ada was designed through
> a competition between four proposals.
Exactly. That's why I mentioned it. IMHO a comparison between Scheme
and Common Lisp that declares that one is the subset of the other is
not unlike declaring that Pascal is a subset of Modular 2. I prefer to
say that only that they're different languages, with strong, possibly
supperficial, similarities. I feel that it's more honest to say that
the real relationship between them is a historical one.
I'm happy to leave the exact nature of that relationship to the
historians, language lawyers, and other pedants. ;) I'm a programmer.
If I can use a language to write code that performs tasks useful to
me, then that's good enough for me.
Language wars are for those who either have too much time to spare, or
have too much to gain by spreading hostile memes. If there's an idea
used in some language not currently exploited by the language that I'm
using, there are a number of options. The one that I like best is to
take that idea and add it (perhaps as an option) to my chosen
language. This is how language speciation may occur, but it's not
always necessary to create a new language in order to accomplish this,
esp if your language is flexible enough to extend itself.
This may be why some people claim that Lisp semantics can include the
semantics of any other language. Symbolic expressions may express
anything we wish, making Lisp semantics (or meta semantics?) a
superset of everything else that we can imagine. In order to be of
practical use, we need only implement those semantics. This is true
for all practical languages anyway, hence the superset argument.
So, perhaps there's no point in asking which Lisp dialect is superset
of another? The only real question is how much effort it would take to
add the semantics of one dialect (or language) to another, and what
would be the practical value of doing so? I expect the answer(s) to
vary according to the needs and abilities of each programmer.
Sajid Ahmed the Peaceman
Satan - The Evil 1 wrote:
>
> After reading the "Lisp in the Real World" thread I have
> the following opinion :) to raise and would be interested
> to hear some other "non-religious" opinions regarading
> Lisp compared to languages such as C/C++ in the area of
> application speed and efficiency.
>
> *Please don't take this as a flame or a troll*
>
> business rules and for general scripting, but it simply
> C and C++ (and to a lesser extent languages such as VB
> and Delphi under Windows).
>
> You don't see fast numerical libraries written in Lisp.
> You don't see scientific libraries written in Lisp.
> You don't see commercial games written in Lisp.
> You don't see application suites written in Lisp.
>
> written in Lisp for the the basic reason that any
> competitor will simply go out and write their competing
> application in C/C++ and make a faster, more responsive
> application that makes more efficient use of machine
> amount of hype, no mainstream apps have been written
> in Java? Because it is too slow for the real world when
> compared to equivalent code written in C or C++.
>
> programmers because it takes several years to become
> a very good and efficient C++ programmer whilst you can
> number of *bad* C++ programmers certainly doesn't help
> its reputation. An experienced C++ programmer can write
> truelly elegant, safe, and efficient code that leaves
>
> Of course, the ease at which you can write good code in
> Lisp is a major point in its favour.
>
> limits and because of this languages such as C and C++
> will maintain their edge over languages such as Lisp.
> processing power than we could ever make use of
> (e.g. quantum computers) and then it will be commercially
> feasible to throw away the low-level languages. But I
> imagine by that time Artificial Intelligences will have
> done away with programmers alltogether.
>
>
> - PCM
Lisp is a deception. All lisp compilers and interpreters that
I've seen have been written in C, and run on top of a C program. I've
seen a lot of LISP and PROLOG programmers, especially in the post
graduate
level of computer science, think that lisp functions the same way as
mathematics. They think that a call to a recursive function
instantaneously
returns a result. The fact is, these function is broken down into
machine
level instructions, and is executed the same way as a for next loop.
AI is a bunch of garbage as well. Do you know what the main goal
of AI is? It is to develope a program where a person cannot
distinguish the program from a human being. What does that have to do
with intelligence? It's just an emulator.
The bottom line is, all computer programs, including AI
programs, are just fast pocket calculators.
Peaceman
Martin Rodgers
With a mighty <kig90z9...@jagor.srce.hr>,
hni...@srce.hr uttered these wise words...
> Now, here is a man who has seen a real lot of Lisp compilers. :-)
There are a few _books_ that could refute his belief! A few years ago,
I wrote one myself. Of course, it was very primitive, but it did
compile a small subset of Scheme into C. It didn't take long to write,
either. After all, I wrote it in Scheme...
I sense a round of URLs about to fly, but they could be pre-empted by
a reference to the Lisp FAQ. Do any C++ programmers bother to read it?
I sometimes wonder, esp when someone tries to distort facts that are
available for anyone with Internet access to check for themselves.
There's that nice little "rtfm" ftp site at MIT, where they keep the
FAQs. Anyone who thinks that all Lisp compilers and interpreters are
written in C should take a look. Still, perhaps Sajid Ahmed hasn't
seen many Lisp compilers and interpreters? That might explain a spot
of ignorance. Again, the Lisp FAQ can help fix that.
It certainly beats the old "open mouth and insert foot" strategy that
all anti-Lisp attacks employ. Oops, perhaps I should say qualify that
by adding that this applies to all the attacks that _I've_ seen. There
may be some out there that are better informed. If such things exist,
I've not seen one during the 5 years that I've been reading UseNet.
Not one.
Martin Rodgers
With a mighty <33CA6A...@capital.net>,
peac...@capital.net uttered these wise words...
> The bottom line is, all computer programs, including AI
> programs, are just fast pocket calculators.
Nice troll. Nothing original, alas.
You might like to read the FAQ for comp.lang.lisp, and check every one
of your "claims" against the reality. Section 4 should be esp
illuminating!
<URL:http://www.cs.cmu.edu/afs/cs.cmu.edu/project/ai-
repository/ai/html/faqs/lang/lisp/top.html>
Alternately, try the "rtfm" site at MIT:
<URL:ftp://rtfm.mit.edu/pub/usenet-by-hierarchy/comp/lang/lisp/>
RTFM is rather appropriate, in your case. Read the FAQ and weep.
Then try something rather more constructive, please.
Marco Antoniotti
In article <33CA6A...@capital.net> Sajid Ahmed the Peaceman <peac...@capital.net> writes:
From: Sajid Ahmed the Peaceman <peac...@capital.net>
Newsgroups: comp.lang.lisp,comp.programming,comp.lang.c++
Date: Mon, 14 Jul 1997 14:04:48 -0400
Organization: Logical Net
Reply-To: peac...@capital.net
Lines: 82
References: <5puscn$e0h$1...@cdn-news.telecom.com.au>
NNTP-Posting-Host: dialup098.colnny1.capital.net
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: Mozilla 3.01 (WinNT; I)
Xref: agate comp.lang.lisp:29244 comp.programming:52315 comp.lang.c++:281622
Satan - The Evil 1 wrote:
>
> OK now... go ahead an rip my argument to shreds :)
>
> Cheers,
> - PCM
Lisp is a deception. All lisp compilers and interpreters that
I've seen have been written in C, and run on top of a C program. I've
seen a lot of LISP and PROLOG programmers, especially in the post
graduate
level of computer science, think that lisp functions the same way as
mathematics. They think that a call to a recursive function
instantaneously
returns a result. The fact is, these function is broken down into
machine
level instructions, and is executed the same way as a for next loop.
Coming from a person who might seem to think that binary tree
traversal can be executed in "the same way as a for next loop", I
cannot help to dismiss the whole argument. Why have C (or Pascal or
Algol or Lisp) in the first place? Let's stick to FORTRAN. :)
Cheers
--
Marco Antoniotti
==============================================================================
California Path Program - UC Berkeley
Richmond Field Station
tel. +1 - 510 - 231 9472
Gareth McCaughan
"Sajid Ahmed the Peaceman" trolled:
> Lisp is a deception. All lisp compilers and interpreters that
> I've seen have been written in C, and run on top of a C program.
How sad.
Scheme 48 is written entirely in Scheme. (Its virtual machine
is compiled to C, but that's just for portability; it's *written*
in Scheme.)
CMU Common Lisp is almost entirely written in Lisp. Some bits are
written in C for bootstrapping purposes.
I have a vague feeling someone told me Harlequin's Lisp compiler
is written entirely in Lisp.
> I've
> seen a lot of LISP and PROLOG programmers, especially in the post
> graduate
> level of computer science, think that lisp functions the same way as
> mathematics. They think that a call to a recursive function
> instantaneously
> returns a result. The fact is, these function is broken down into
> machine
> level instructions, and is executed the same way as a for next loop.
Well, knock me down with a feather. Who would have thought it?
You'll be telling me that my hardware doesn't have a single run-emacs
operation next.
If you've seen a lot of postgraduate computer scientists who think
that recursive functions return instantaneously, then the only
conclusion I can draw is that you've been hanging around a university
where either they don't know how to teach computer science or they
get really really weak students. Too bad.
> AI is a bunch of garbage as well. Do you know what the main goal
> of AI is? It is to develope a program where a person cannot
> distinguish the program from a human being. What does that have to do
> with intelligence? It's just an emulator.
Thank you for sharing this profound insight with us. Are you an
emulator or a person, by the way? How are we supposed to tell?
> The bottom line is, all computer programs, including AI
> programs, are just fast pocket calculators.
So much the better for pocket calculators, say I.
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
gj...@dpmms.cam.ac.uk Cambridge University, England.
Hrvoje Niksic
Sajid Ahmed the Peaceman <peac...@capital.net> writes:
> All lisp compilers and interpreters that I've seen have been written
> in C, and run on top of a C program.
Now, here is a man who has seen a real lot of Lisp compilers. :-)
(rest of bait ignored.)
--
Hrvoje Niksic <hni...@srce.hr> | Student at FER Zagreb, Croatia
--------------------------------+--------------------------------
Then... his face does a complete change of expression. It goes from
a "Vengeance is mine" expression, to a "What the fuck" blank look.
Mark Greenaway
Sajid Ahmed the Peaceman <peac...@capital.net> writes:
> Lisp is a deception. All lisp compilers and interpreters that
>I've seen have been written in C, and run on top of a C program. I've
>seen a lot of LISP and PROLOG programmers, especially in the post
>graduate
>level of computer science, think that lisp functions the same way as
>mathematics. They think that a call to a recursive function
>instantaneously
>returns a result. The fact is, these function is broken down into
>machine
>level instructions, and is executed the same way as a for next loop.
<sarcasm>Gosh, who'd have thought it?</sarcasm> Don't be so utterly
stupid! Any decent LISP programmer, in fact any decent programmer, knows
that. Efficiency is part of programming. But it is not the be-all and
end-all. Yes, the lower-level parts of many LISP systems might well be
written in C/Assembly etc.
The real question is: What is the most efficient/elegant/best way to
express a particular program? It might, for some problems, be in C or C++.
For some, it might be LISP or Prolog. If I can write a program which
efficiently does a job in 60 lines of well-documented LISP that would take
300 lines or more of C, and they both run at similiar speeds, it would
seem that LISP is the better choice.
> AI is a bunch of garbage as well. Do you know what the main goal
>of AI is? It is to develope a program where a person cannot
>distinguish the program from a human being. What does that have to do
>with intelligence? It's just an emulator.
Totally untrue. It would appear that you don't understand what you are
talking about.
> The bottom line is, all computer programs, including AI
>programs, are just fast pocket calculators.
This is not accurate either. All digital computers can be said to be
equivalent to a Universal Turing Machine. But not a calculator. A
calculator hasn't got several of the basic properties it needs.
--
Mark
Certified Waifboy And when they come to ethnically cleanse me
Will you speak out? Will you defend me?
http://www.st.nepean.uws.edu.au/~mgreenaw - Ich bin ein Auslander, PWEI
? the platypus {aka David Formosa}
In <33CA6A...@capital.net> Sajid Ahmed the Peaceman <peac...@capital.net> writes:
[...]
> Lisp is a deception. All lisp compilers and interpreters that
>I've seen have been written in C, and run on top of a C program.
Well then you are not looking hard enough. Lisp predates C by meany years.
There are many verents of lisp that are writton in lisp.
In addtion you could say that C is a deception as all C compilers and
interpreters are written in mechean code.
> I've seen a lot of LISP and PROLOG programmers, especially in the post
>graduate level of computer science, think that lisp functions the same way as
>mathematics.
Thats what makes lisp so easy to use.
> They think that a call to a recursive function instantaneously
>returns a result.
No good programer would beleave that.
> The fact is, these function is broken down into machine
>level instructions, and is executed the same way as a for next loop.
You seem to be implieing that ever recusive call gets recompiled. This
is simply not true. In addtion there have been times where the recursive
verson has been faster then the iterave form (I don't know why this is
but time says its so.)
--
Please excuse my spelling as I suffer from agraphia see the url in my header.
Never trust a country with more peaple then sheep. Buy easter bilbies.
Save the ABC Is $0.08 per day too much to pay? ex-net.scum and proud
I'm sorry but I just don't consider 'because its yucky' a convincing argument
Thomas Hallock
> Coming from a person who might seem to think that binary tree
> traversal can be executed in "the same way as a for next loop", I
> cannot help to dismiss the whole argument. Why have C (or Pascal or
> Algol or Lisp) in the first place? Let's stick to FORTRAN. :)
well, correct me if i'm wrong, but i have read in many places that *all
recursive functions can be expressed as iterations* yea, it's hard to
believe, but it's been prooven, but i don't really know how to do such a
work of magic.
note that this is done automatically in some really good compilers!
Marco Antoniotti
Delivery-Date: Tue, 15 Jul 1997 08:21:57 -0700
Date: Tue, 15 Jul 1997 10:23:04 +0000
From: c.ha...@mail.utexas.edu (Thomas Hallock)
Newsgroups: comp.lang.lisp,comp.programming,comp.lang.c++
References: <5puscn$e0h$1...@cdn-news.telecom.com.au> <33CA6A...@capital.net> <scf3eph...@infiniti.PATH.Berkeley.EDU>
Organization: bovine soft.
(A copy of this message has also been posted to the following newsgroups:
comp.lang.lisp, comp.programming,comp.lang.c++)
You are right. I was kinda flame baiting :). You can always express a
recursive function with a loop. However, some functions (e.g. binary
tree traversal) are "inherently" recursive. I.e. to remove the
recursive calls you have to explicitely manage a stack. Old FORTRAN
is a good example of this burden posed on the programmer.
Marco Antoniotti
In article <868938030.121424@cabal> ? the platypus {aka David Formosa} <dfor...@st.nepean.uws.edu.au> writes:
From: ? the platypus {aka David Formosa} <dfor...@st.nepean.uws.edu.au>
Newsgroups: comp.lang.lisp,comp.programming,comp.lang.c++
Date: 15 Jul 1997 03:40:39 GMT
Organization: UWS Nepean - Department of Computing
Path: agate!ihnp4.ucsd.edu!munnari.OZ.AU!metro!metro!ob1.uws.edu.au!news
Lines: 36
In <33CA6A...@capital.net> Sajid Ahmed the Peaceman <peac...@capital.net> writes:
[...]
> Lisp is a deception. All lisp compilers and interpreters that
>I've seen have been written in C, and run on top of a C program.
Well then you are not looking hard enough. Lisp predates C by meany years.
There are many verents of lisp that are writton in lisp.
In addtion you could say that C is a deception as all C compilers and
interpreters are written in mechean code.
You can go even further than that. C compilers are written mostly in
C. However, GNAT (the Ada 95 front end to the gcc backend) is written
partly in Ada 95 and a large portion of the CMU Common Lisp compiler
is written in Common Lisp. This notion of "compiler bootstrapping" is
as old as computer programming itself.
Joe Sysop
On Tue, 15 Jul 1997 10:22:59 +0000, Thomas Hallock <c.ha...@mail.utexas.edu> wrote:
>> Coming from a person who might seem to think that binary tree
>> traversal can be executed in "the same way as a for next loop", I
>> cannot help to dismiss the whole argument. Why have C (or Pascal or
>> Algol or Lisp) in the first place? Let's stick to FORTRAN. :)
>
>well, correct me if i'm wrong, but i have read in many places that *all
>recursive functions can be expressed as iterations* yea, it's hard to
>believe, but it's been prooven, but i don't really know how to do such a
>work of magic.
>note that this is done automatically in some really good compilers!
It is true, and often not that hard. But i don't see why compilers want
to make recursion interative, since that (if the recursion is justified)
means making the code bigger -> bigger/slower executable. Or am i wrong?
/Joe
W. Daniel Axline
Actually, I have been given to understand quite the opposite. Apparently
whenver (during runtime) a function calls itself, it has to make another
complete copy of itself to run. You can see how this would tend to take
up much more in the way of resources than an iterative function.
I'm not sure what the exact effect on speed would be, but I imagine it
would be slower. In my limited experience, iterative algorithms have not
been that much larger than their recursive counterparts, just more
difficult to divine.
W. Daniel Axline
Marco Antoniotti wrote:
>
> Delivery-Date: Tue, 15 Jul 1997 08:21:57 -0700
> Date: Tue, 15 Jul 1997 10:23:04 +0000
> From: c.ha...@mail.utexas.edu (Thomas Hallock)
> Newsgroups: comp.lang.lisp,comp.programming,comp.lang.c++
> References: <5puscn$e0h$1...@cdn-news.telecom.com.au> <33CA6A...@capital.net> <scf3eph...@infiniti.PATH.Berkeley.EDU>
> Organization: bovine soft.
>
> (A copy of this message has also been posted to the following newsgroups:
> comp.lang.lisp, comp.programming,comp.lang.c++)
>
> > traversal can be executed in "the same way as a for next loop", I
> > cannot help to dismiss the whole argument. Why have C (or Pascal or
> > Algol or Lisp) in the first place? Let's stick to FORTRAN. :)
>
> well, correct me if i'm wrong, but i have read in many places that *all
> recursive functions can be expressed as iterations* yea, it's hard to
> believe, but it's been prooven, but i don't really know how to do such a
> work of magic.
> note that this is done automatically in some really good compilers!
>
> recursive function with a loop. However, some functions (e.g. binary
> tree traversal) are "inherently" recursive. I.e. to remove the
> recursive calls you have to explicitely manage a stack. Old FORTRAN
> is a good example of this burden posed on the programmer.
I have written binary tree traversal algorithms which don't use a stack.
I would be interested to know if this were true for some other
algorithms,
however.
Here's an iterative preorder binary tree traversal.
(Preorder means process root, then process the subtrees.)
void BT::Preorder2Screen()
{
BTnode *temp = this->root; //used to find a node with an untraversed
right subtree
BTnode *current = this->root; //start at the root
int i;
while(temp!=NULL) // need to do this for each node
{
cout<<current->key<<" ";
if(current->Lchild)
{
current = current->Lchild;
}
else
{
if(current->Rchild!=NULL)
{
current = current->Rchild;
}
else //go backwards
{
temp = current->parent;
while(((temp->Rchild == NULL)||(temp->Rchild == current))&&
(temp!=NULL)) //shouldn't happen
{
current = temp;
temp = temp->parent;
}
if (temp!=NULL)
current = temp->Rchild;
}
}
}//endwhile
cout<<"\n\n";
}//end Preorder2Screen()
Erik Naggum
* W. Daniel Axline
| Actually, I have been given to understand quite the opposite. Apparently
| whenver (during runtime) a function calls itself, it has to make another
| complete copy of itself to run. You can see how this would tend to take
| up much more in the way of resources than an iterative function. I'm not
| sure what the exact effect on speed would be, but I imagine it would be
| slower. In my limited experience, iterative algorithms have not been that
| much larger than their recursive counterparts, just more difficult to
| divine.
I wonder what you mean by "a complete copy of itself". it appears that you
think a copy of the actual function's _code_ is copied, and this is of
course not true. however, a new stack frame is often created upon a
function call, with space for various registers, local variables, etc, etc.
this does consume resources. languages that are made for or encourage
recursive function calls often offer "tail call merging" to handle the case
where a function returns simply what the function it is about to call would
return. in such a case, the calling function's stack frame is undone
before the call (if necessary), and the called function returns to the
caller's caller, saving both time and memory. (Scheme is "properly tail
recursive" because it requires an implementation to do tail calls as jumps,
not calls. most Common Lisp implementations offer tail call merging.)
I previously made a serious mistake in believing that Lisp compilers were
so much faster than C compilers when the real difference was that the Lisp
compilers did tail call merging and the C compiler did not. on a SPARC,
this translates to a very heavy penalty because of the way register windows
are saved on the stack, so the Lisp compilers won big, disproportionately.
(I haven't been able to compute the actual cost of a call so I could
discount it and get a better comparison. for now, the GNU C compiler makes
recursion extremely costly on the SPARC.)
programmers who write recursive functions learn to use tail recursion soon
after they discover that each function call can take up hundreds of bytes
of memory. e.g., the former of these two functions will use memory (stack
space) proportional to n, while the latter will use constant space if the
compiler merges tail calls.
(defun factorial (n)
(if (plusp n)
(* n (factorial (1- n)))
1))
(defun factorial (n)
(flet ((tail-factorial (n accumulator)
(if (plusp n)
(tail-factorial (1- n) (* n accumulator))
accumulator)))
(tail-factorial n 1)))
let's hope this puts some needless worries about recursion to rest.
#\Erik
--
Microsoft Pencil 4.0 -- the only virtual pencil whose tip breaks.
Michael Schuerig
W. Daniel Axline <wax...@cse.unl.edu> wrote:
> I have written binary tree traversal algorithms which don't use a stack.
> I would be interested to know if this were true for some other
> algorithms,
> however.
> Here's an iterative preorder binary tree traversal.
[snip]
> temp = current->parent;
^ That's the catch.
Effectively you're using a stack. Not the function call stack, but a
stack embedded into your tree. It's fine as long as you need the parent
pointers anyway, but if you only use them for traversal they impose a
possibly significant space overhead and they take time to update.
Michael
--
Michael Schuerig The usual excuse for our most unspeakable
mailto:uzs...@uni-bonn.de public acts is that they are necessary.
http://www.uni-bonn.de/~uzs90z/ -Judith N. Shklar
Bill Wade
Michael Schuerig <uzs...@uni-bonn.de> wrote in article
<1997071614...@rhrz-isdn3-p5.rhrz.uni-bonn.de>...
> W. Daniel Axline <wax...@cse.unl.edu> wrote:
>
> > I have written binary tree traversal algorithms which don't use a
stack.
> > I would be interested to know if this were true for some other
> > algorithms,
There are plenty of recursive functions for which most of us don't use a
stack. Iterative factorial() or fibonicci() are examples.
int fact(unsigned int n)
{
int result = 1;
while(n) result *= n--;
return result;
}
> > however.
> > Here's an iterative preorder binary tree traversal.
> [snip]
> > temp = current->parent;
> ^ That's the catch.
>
> Effectively you're using a stack. Not the function call stack, but a
> stack embedded into your tree. It's fine as long as you need the parent
> pointers anyway, but if you only use them for traversal they impose a
> possibly significant space overhead and they take time to update.
Its possible to do n-ary trees without child or parent pointers (a heap),
but some operations (such as swapping child trees or insertions at arbitray
points) become much more expensive. However depth-first or breadth-first
traversals of a heap are easy to do without recursion.
Its hard to argue that fact() above has significant time or space penalties
compared to a recursive version.
The obvious iterative fib() function requires a linear number of additions
and no stack. The obvious recursive version requires an exponential number
of additions.
Erik Naggum
* Harley Davis
| That's interesting. Could you give a couple of examples of commercial
| games running compiled (or even interpreted) Lisp code. How about an
| application suite? Anything mainstream?
a friend of mine sent me some Lisp code that looked really odd some time
ago, and told me it was from a game called Abuse. I don't know much about
it, but the Lisp code appeared to be definitions of characters and such,
and Lisp is the extension language of this game, running interpreted or
compiled after loading source code. no compile-file exists. he described
Abuse as a "sidescroller" game. I don't know what that is; some sort of
shoot-em-up game. see http://games.3dreview.com/abuse/files/lispedit.txt
or http://games.3dreview.com/abuse/minigames/minigames.html.
the new Nintendo 64-bit games are produced with Common Lisp, but I don't
know how much of Lisp is running in the actual game. Nichimen Graphics and
their N-world is the place to go for Lisp game action. check out
www.franz.com -- they had a lot of pointers there some time ago. (I can't
check right now, 'cuz Netscape expresses their desire to have me to upgrade
to their next version in their own peculiar way.)
Michael Schuerig
W. Daniel Axline <wax...@cse.unl.edu> wrote:
> Actually, I have been given to understand quite the opposite. Apparently
> whenver (during runtime) a function calls itself, it has to make another
> complete copy of itself to run.
You mean a complete copy of the function's *code*? No, definitely not.
Parameters and local variables are allocated on the stack and control
flow continues at the beginning of the function.
If the recursive call is the last one in the function ("tail-recursion")
this can even be done without growing the stack as the new parameters
and variables replace the old ones. You get a function that looks
recursive, but effectively is executed iteratively. Lisp compilers do
this optimization, I'm not sure about others.
Michael
--
Michael Schuerig P'rhaps he's hungry. Six volts make him smile.
mailto:uzs...@uni-bonn.de And twelve volts would probably kill.
http://www.uni-bonn.de/~uzs90z/ -Jethro Tull, "Batteries Not Included"
Marco Antoniotti
In article <01bc91fa$bde89880$2864370a@janeway> "Bill Wade" <bill...@stoner.com> writes:
From: "Bill Wade" <bill...@stoner.com>
Newsgroups: comp.lang.lisp,comp.programming,comp.lang.c++
Date: 16 Jul 1997 15:12:58 GMT
Organization: NeoSoft, Inc.
NNTP-Posting-Host: gateway.stoner.com
X-Newsreader: Microsoft Internet News 4.70.1161
Lines: 44
Xref: agate comp.lang.lisp:29286 comp.programming:52441 comp.lang.c++:282065
Michael Schuerig <uzs...@uni-bonn.de> wrote in article
<1997071614...@rhrz-isdn3-p5.rhrz.uni-bonn.de>...
> W. Daniel Axline <wax...@cse.unl.edu> wrote:
>
> > I have written binary tree traversal algorithms which don't use a
stack.
> > I would be interested to know if this were true for some other
> > algorithms,
There are plenty of recursive functions for which most of us don't use a
stack. Iterative factorial() or fibonicci() are examples.
int fact(unsigned int n)
{
int result = 1;
while(n) result *= n--;
return result;
}
You are not getting it. There are "inherently recursive" function
definitions for which an equivalent iterative algorithm *requires* the
use of a stack. No matter how disguised.
> > however.
> > Here's an iterative preorder binary tree traversal.
> [snip]
> > temp = current->parent;
> ^ That's the catch.
>
> Effectively you're using a stack. Not the function call stack, but a
> stack embedded into your tree. It's fine as long as you need the parent
> pointers anyway, but if you only use them for traversal they impose a
> possibly significant space overhead and they take time to update.
Its possible to do n-ary trees without child or parent pointers (a heap),
but some operations (such as swapping child trees or insertions at arbitray
points) become much more expensive. However depth-first or breadth-first
traversals of a heap are easy to do without recursion.
That, once again is because - I surmise - you are assuming an array
implementation of the heap where you know exactly where "parent" and
"children" are (typically at (i%2), (2*i) and (2*1 + 1) for a node at
'i' in a binary heap). You are always allocating memory in some way
or the other which eventually provides you with an "encoded stack".
You can't do that with purely malloc'ed data structures.
Its hard to argue that fact() above has significant time or space penalties
compared to a recursive version.
The obvious iterative fib() function requires a linear number of additions
and no stack. The obvious recursive version requires an exponential number
of additions.
These are examples of non-inherently recursive functions and do not
change a bit the terms of the debate. If memory does not fail me,
there is even a closed form solution for the Fibonacci numbers that
can - hear hear - be computed in O(1) time.
Again, try to do the binary tree search without extra memory allocated
in the basic data structures.
As you might have noticed. The title of this thread is now totally
bogus :)
Marco Antoniotti
In article <33CC74...@cse.unl.edu> "W. Daniel Axline" <wax...@cse.unl.edu> writes:
From: "W. Daniel Axline" <wax...@cse.unl.edu>
Newsgroups: comp.lang.lisp,comp.programming,comp.lang.c++
Date: Wed, 16 Jul 1997 02:11:31 -0500
Organization: Internet Nebraska
Reply-To: wax...@cse.unl.edu
NNTP-Posting-Host: lin-pm1-022.inetnebr.com
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: Mozilla 3.0Gold (Win95; I)
Xref: agate comp.lang.lisp:29268 comp.programming:52406 comp.lang.c++:281961
Marco Antoniotti wrote:
>
> Delivery-Date: Tue, 15 Jul 1997 08:21:57 -0700
> Date: Tue, 15 Jul 1997 10:23:04 +0000
> From: c.ha...@mail.utexas.edu (Thomas Hallock)
> Newsgroups: comp.lang.lisp,comp.programming,comp.lang.c++
> References: <5puscn$e0h$1...@cdn-news.telecom.com.au> <33CA6A...@capital.net> <scf3eph...@infiniti.PATH.Berkeley.EDU>
> Organization: bovine soft.
>
> (A copy of this message has also been posted to the following newsgroups:
> comp.lang.lisp, comp.programming,comp.lang.c++)
>
> > Coming from a person who might seem to think that binary tree
> > traversal can be executed in "the same way as a for next loop", I
> > cannot help to dismiss the whole argument. Why have C (or Pascal or
> > Algol or Lisp) in the first place? Let's stick to FORTRAN. :)
>
> well, correct me if i'm wrong, but i have read in many places that *all
> recursive functions can be expressed as iterations* yea, it's hard to
> believe, but it's been prooven, but i don't really know how to do such a
> work of magic.
> note that this is done automatically in some really good compilers!
>
> You are right. I was kinda flame baiting :). You can always express a
> recursive function with a loop. However, some functions (e.g. binary
> tree traversal) are "inherently" recursive. I.e. to remove the
> recursive calls you have to explicitely manage a stack. Old FORTRAN
> is a good example of this burden posed on the programmer.
I have written binary tree traversal algorithms which don't use a stack.
I would be interested to know if this were true for some other
algorithms,
however.
Here's an iterative preorder binary tree traversal.
(Preorder means process root, then process the subtrees.)
void BT::Preorder2Screen()
{
BTnode *temp = this->root; //used to find a node with an untraversed
right subtree
BTnode *current = this->root; //start at the root
int i;
while(temp!=NULL) // need to do this for each node
{
cout<<current->key<<" ";
if(current->Lchild)
{
current = current->Lchild;
}
else
{
if(current->Rchild!=NULL)
{
current = current->Rchild;
}
else //go backwards
{
temp = current->parent;
while(((temp->Rchild == NULL)||(temp->Rchild == current))&&
(temp!=NULL)) //shouldn't happen
{
current = temp;
temp = temp->parent;
}
if (temp!=NULL)
current = temp->Rchild;
}
}
}//endwhile
cout<<"\n\n";
}//end Preorder2Screen()
You are embedding a 'parent' field in your tree nodes. This is equivalent
to use up the the memory needed for a call stack or for a node stack.
If you do not need the parent node for other purposes, this is a waste
of memory which makes the C++ program "inefficient" :)
The recursive solution is much more compact and readable.
void
BTNode::Preorder()
{
cout << current->key << ' '; // Write a space character.
if (Rchild != NULL)
Rchild->Preorder();
if (Lchild != NULL)
Lchild->Preorder();
cout << '\n' << endl; // Use 'endl' to flush.
}
//end Preorder2Screen()
Of course, I could have written a standard function taking a BTNode
argument. The code would have been even more compact, but I decided
to stick to your style.
Not bad for a Lisp programmer, isn't it? Or maybe, it is because I am
a Lisp programmer that I see the beauty and the ease in which you
write recursive functions like these :)
BTW. I suggest to look at
http://www.delorie.com/gnu/docs/GNU/standards_toc.html
reading C/C++ code inconsistently formatted is worse than reading lots
of parenthesis.
Mike Rilee
William Clodius wrote:
>
> Joe Sysop wrote:
> ><snip>
> >
> > It is true, and often not that hard. But i don't see why compilers want
> > to make recursion interative, since that (if the recursion is justified)
> \
> > means making the code bigger -> bigger/slower executable. Or am i wrong?
> >
> > /Joe
>
>
> 1. It is not clear to me what you mean by the phrase "if the recursion
> is justified". The typical justification for the use of recursion over
> iteration is that it more clearly represents the programmer's intent for
> the properties of the code. However, clarity of intent need not have a
> direct relationship with efficiency of implementation.
>
> 2. The most commonly quoted examples of replacement of recursion by
> iteration, i.e., tail recursion elimination, do gain in efficiency by
> the replacement, for a reasonably intelligent compiler. The procedure
> call adds overhead and indirection not present in the equivalent
> iterative construct. However it is not clear to me that typical
> compilers can replace more sophisticated useages of recursion with
> comparably efficient iterative implementations.
>
Might one gain some advantage by first implementing some
reasonably complex functionality using a clear, if less
efficient, recursive style? Then, if necessary, one could
implement the same functionality using an iterative style.
This presupposes that it is easier to produce correct recursive
solutions. It can be useful to have two solutions to the
same problem at hand. Even if one is dramatically less
efficient than the other.
I would speculate that choosing to implement a more complex
solution first would run a greater risk of failure and might
be more expensive in the long run. Constructing a prototype
first would allow one to obtain experience solving the
problem (or pieces of it). If the main effort fails then
the prototype would exist as a solution.
--
Mike Rilee NASA/GSFC Mailstop 930.0 Greenbelt, MD 20771
mri...@hannibal.gsfc.nasa.gov Ph. (301)286-4743 Fx. (301)286-1777
--
Composed using Oberon. http://www-cs.inf.ethz.ch/Oberon.html
William Clodius
Joe Sysop wrote:
><snip>
>
> It is true, and often not that hard. But i don't see why compilers want
> to make recursion interative, since that (if the recursion is justified)
\
> means making the code bigger -> bigger/slower executable. Or am i wrong?
>
> /Joe
You are wrong, but it is not clear to me how wrong you are since
1. It is not clear to me what you mean by the phrase "if the recursion
is justified". The typical justification for the use of recursion over
iteration is that it more clearly represents the programmer's intent for
the properties of the code. However, clarity of intent need not have a
direct relationship with efficiency of implementation.
2. The most commonly quoted examples of replacement of recursion by
iteration, i.e., tail recursion elimination, do gain in efficiency by
the replacement, for a reasonably intelligent compiler. The procedure
call adds overhead and indirection not present in the equivalent
iterative construct. However it is not clear to me that typical
compilers can replace more sophisticated useages of recursion with
comparably efficient iterative implementations.
--
William B. Clodius Phone: (505)-665-9370
Los Alamos Nat. Lab., NIS-2 FAX: (505)-667-3815
PO Box 1663, MS-C323 Group office: (505)-667-5776
Los Alamos, NM 87545 Email: wclo...@lanl.gov
Barry Margolin
In article <33CC72...@cse.unl.edu>,
>> It is true, and often not that hard. But i don't see why compilers want
>> to make recursion interative, since that (if the recursion is justified)
>> means making the code bigger -> bigger/slower executable. Or am i wrong?
>
>whenver (during runtime) a function calls itself, it has to make another
>up much more in the way of resources than an iterative function.
Is one of you flame-baiting, or are you both completely clueless?
Neither recursive nor iterative functions are inherently larger than one
another; in general, the amount of code will be very similar. Most of the
work is usually done in the body of the loop or recursive function, not in
the code that determines how to repeat itself, and this should be almost
identical in the two versions.
When a function recurses, it doesn't "make another complete copy of itself
to run." There's just a single copy of a function, but perhaps a new
activation record (AKA stack frame) to hold the context of the recursive
call. And if the function is tail-recursive, and the language
implementation supports tail-call optimization, the recursive call can use
the same activation record. Sometimes the tail-recursive version of a
function is a little less obvious than the recursive version, though.
Here's an example of factorial in iterative, recursive, and tail-recursive
versions:
(defun fact-iter (n)
(do ((result 1 (* result i))
(i n (1- i)))
((< i 2) result)))
(defun fact-recurs (n)
(if (< n 2)
1
(* n (fact-recurs (1- n)))))
(defun fact-tail-recurs (n)
(labels ((recurs (i result)
(if (< i 2)
result
(recurs (1- i) (* result i)))))
(recurs n 1)))
In an implementation that supports tail-recursion optimization, the
iterative and tail-recursive versions should generate almost identical
code. The recursive version, however, will use O(n) stack space for all
the recursive calls; once the recursion bottoms out, the multiplications
will be done as each call returns.
--
Barry Margolin, bar...@bbnplanet.com
BBN Corporation, Cambridge, MA
Support the anti-spam movement; see <http://www.cauce.org/>
Vassili Bykov
Erik Naggum <er...@naggum.no> writes:
> [...good points about tail recursion...]
>
> (defun factorial (n)
> (flet ((tail-factorial (n accumulator)
> (if (plusp n)
> (tail-factorial (1- n) (* n accumulator))
> accumulator)))
> (tail-factorial n 1)))
For perfection, that's LABELS, not FLET.
--Vassili
? the platypus {aka David Formosa}
In <33CC72...@cse.unl.edu> "W. Daniel Axline" <wax...@cse.unl.edu> writes:
[...]
>Actually, I have been given to understand quite the opposite. Apparently
>whenver (during runtime) a function calls itself, it has to make another
>complete copy of itself to run.
This is not true. All has to be done is a new bit of stack has to be
allocated.
[...]
> In my limited experience, iterative algorithms have not
>been that much larger than their recursive counterparts, just more
>difficult to divine.
Ok the extened eucliden algorthum then. I have seen no way to do it
iteraveravly that dosen't involve stacks and a hell of a lot hard to
underatand code.
Gareth McCaughan
David Formosa wrote:
> Ok the extened eucliden algorthum then. I have seen no way to do it
> iteraveravly that dosen't involve stacks and a hell of a lot hard to
> underatand code.
>
> --
> Please excuse my spelling as I suffer from agraphia see the url in my header.
I don't know whether you're a Lisp person or a C++ person (both groups
are in the headers), so I'll do this in pseudocode. It's not the
most efficient code you could write, but it works and it should be
pretty easy to understand.
function euclid(integer x, y) returning integers d,a,b:
// d is the gcd of x,y
// ax+by = d
// for simplicity we assume that x,y are both non-negative,
// and that x>=y.
integer xx=x, px=1, qx=0 // xx=px.x+qx.y always
integer yy=y, py=0, qy=1 // yy=py.x+qy.y always
while yy>0 do
integer q=floor(xx/yy), r=yy-q*xx
// now replace xx,yy with yy,r
(xx,px,qx, yy,py,qy) := (yy,py,qy, r,px-q*py,qx-q*qy)
return d=xx, a=px, b=qx
Not a stack in sight.
Sajid Ahmed the Peaceman
Mark Greenaway wrote:
>
> > Lisp is a deception. All lisp compilers and interpreters that
> >seen a lot of LISP and PROLOG programmers, especially in the post
> >graduate
> >level of computer science, think that lisp functions the same way as
> >instantaneously
> >returns a result. The fact is, these function is broken down into
> >machine
> >level instructions, and is executed the same way as a for next loop.
>
> <sarcasm>Gosh, who'd have thought it?</sarcasm> Don't be so utterly
> stupid!
Calling people names doesn't do anything.
>Any decent LISP programmer, in fact any decent programmer, knows
> that. Efficiency is part of programming. But it is not the be-all and
> end-all. Yes, the lower-level parts of many LISP systems might well be
> written in C/Assembly etc.
>
> The real question is: What is the most efficient/elegant/best way to
> express a particular program? It might, for some problems, be in C or C++.
> For some, it might be LISP or Prolog.
It is true that LISP and Prolog may have some built in functions
that lets the programmer write less code, but as far as speed is
concerned,
Sajid Ahmed the Peaceman
> > in C, and run on top of a C program.
>
>
> (rest of bait ignored.)
>
Your smart to ignore it :)
Sajid Ahmed the Peaceman
Martin Rodgers wrote:
>
> With a mighty <kig90z9...@jagor.srce.hr>,
> hni...@srce.hr uttered these wise words...
>
> > Now, here is a man who has seen a real lot of Lisp compilers. :-)
>
> I wrote one myself. Of course, it was very primitive, but it did
> compile a small subset of Scheme into C. It didn't take long to write,
> either. After all, I wrote it in Scheme...
>
> I sense a round of URLs about to fly, but they could be pre-empted by
> a reference to the Lisp FAQ. Do any C++ programmers bother to read it?
> I sometimes wonder, esp when someone tries to distort facts that are
> available for anyone with Internet access to check for themselves.
>
> There's that nice little "rtfm" ftp site at MIT, where they keep the
> FAQs. Anyone who thinks that all Lisp compilers and interpreters are
> written in C should take a look. Still, perhaps Sajid Ahmed hasn't
> seen many Lisp compilers and interpreters? That might explain a spot
> of ignorance. Again, the Lisp FAQ can help fix that.
>
I took a look at the faq. It's mostly about the syntax of
Lisp code.
Anyway, all lisp programs, as well as the compilers and
interpreters are broken down into assembly level code, which is
iterative. The thing I have a problem with is with people trying
to write programs that are completely recursive, which is what lisp
is about. That is the wrong way to go about it. It's a tremendous
waste.
Peaceman
Marco Antoniotti
In article <33CE58...@capital.net> Sajid Ahmed the Peaceman <peac...@capital.net> writes:
From: Sajid Ahmed the Peaceman <peac...@capital.net>
Newsgroups: comp.lang.lisp,comp.programming,comp.lang.c++
Date: Thu, 17 Jul 1997 13:36:39 -0400
Organization: Logical Net
Reply-To: peac...@capital.net
Lines: 34
NNTP-Posting-Host: dialup077.colnny1.capital.net
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: Mozilla 3.01 (WinNT; I)
Xref: agate comp.lang.lisp:29306 comp.programming:52493 comp.lang.c++:282257
And in one fell swoop, 50 years of programming science and engineering
are thrown out the window (or left for the garbage collectors :) ).
This has nothing to do with Lisp or C/C++ or Assembly language. This
has to do with good programming practices and the experience of the
programmer. Next thing I'll hear from you is how to solve the
general TSP problem in linear time. (Of course, I'd like to hear from
you a definition of "linear time" beforehand).
Emergent Technologies Inc.
Sajid Ahmed the Peaceman wrote in article <33CE59...@capital.net>...
>
> Unfortunately, that is the experience that I've had.
>The postgraduate couses in computer science that I've seen were
>more like math courses than computer courses.
>
Yeah, go figure....
I wonder Y
Sajid Ahmed the Peaceman
> >I've seen have been written in C, and run on top of a C program. I've
> >seen a lot of LISP and PROLOG programmers, especially in the post
> >graduate
> >level of computer science, think that lisp functions the same way as
> >mathematics. They think that a call to a recursive function
> >instantaneously
> >returns a result. The fact is, these function is broken down into
> >machine
> >level instructions, and is executed the same way as a for next loop.
>
> <sarcasm>Gosh, who'd have thought it?</sarcasm> Don't be so utterly
> stupid!
Calling people names doesn't do anything.
>Any decent LISP programmer, in fact any decent programmer, knows
> that. Efficiency is part of programming. But it is not the be-all and
> end-all. Yes, the lower-level parts of many LISP systems might well be
> written in C/Assembly etc.
>
> The real question is: What is the most efficient/elegant/best way to
> express a particular program? It might, for some problems, be in C or C++.
> For some, it might be LISP or Prolog. If I can write a program which
> efficiently does a job in 60 lines of well-documented LISP that would take
> 300 lines or more of C, and they both run at similiar speeds, it would
> seem that LISP is the better choice.
It is true that LISP has some built in functions that allows
a programmer to write less code. As far as speed is concerned, in almost
every situation, the same program written in C would be faster than a
similar program written in Lisp. Why? C is much closer to the machine
level
assembly code that all computers run on. Many C compilers allow inline
assembly
language code within the program.
As far as the size of the program is concerned, most of the time C
programs are smaller? Why? Good Lisp programs only allow recursive code,
without any stop codes, whereas good C programs allow for both recursive
and iterative code.
Have you ever seen a the quicksort algorithm written in Lisp?
Even though it is a recursive function, it still needs well over
100 lines of code. In C it would only be 5 or 6 lines.
Peaceman
William Clodius
Sajid Ahmed the Peaceman wrote:
> <snip>
> Anyway, all lisp programs, as well as the compilers and
> interpreters are broken down into assembly level code, which is
> iterative. The thing I have a problem with is with people trying
> to write programs that are completely recursive, which is what lisp
> is about. That is the wrong way to go about it. It's a tremendous
> waste.
While most assemblers are iterative, I believe I read recently (in the
procedings from the most recent PLDI conference in a paper on developing
code generators for processors from the analysis of C compiler output)
that the assembler for the Tera computer is a dialect of Scheme. This,
of course, need not imply that the Tera assembly code is essentially
recursive, (or that the machine code generated from the assembly need
have a close resemblance to the assembly code), but is interesting none
the less.
Programming language design is about providing a means of expressing an
idea as clearly as possible, (because recursion is often the clearest
way of expressing a concept languages should always include recursion),
implementation is about providing the "best" possible combination of
robustness and efficiency, (if that is best achieved by translating the
recursion into an iterative process then so be it), and programming is
about serving the needs of the user of the code (and, as important one
user of the code is very often its maintainer, that implies that the
code should be written as clearly as possible, with subtle trick (e.g.,
unclear iterative constructs) used rarely and well documented).
Fred Haineux
| Anyway, all lisp programs, as well as the compilers and
| interpreters are broken down into assembly level code, which is
| iterative. The thing I have a problem with is with people trying
| to write programs that are completely recursive, which is what lisp
| is about. That is the wrong way to go about it. It's a tremendous
| waste.
If I write a clever compiler, it can turn recursion into iteration.
Lisp does that, automatically. (see note 1)
If I want to write iteration instead of recursion in Lisp, there are
plenty of ways to do so. I am not at any time required to use recursion.
Here is an example I'm sure you'll understand:
(loop for x from 1 to 10 do (print "I am iterating"))
The Lisp function does not use recursion, but iterates in the exact same
way as this C program:
{for (x=1;x<=10;x++) {printf("I am iterating\n");};}; // (see note 2)
Please also note that in lisp, it's perfectly OK to say:
(defun eat (a b c)
"Combine a b and c into a single number."
(progn ;;;; (see note 3)
(setf x 0)
(setf x (+ a b))
(setf x (* c x))
x))
which is precisely the same as this C program
eat(a,b,c)
{
int x;
x=0;
x=a+b;
x=x*c;
return x;
}
Bottom line: you can do any programming construct you like in Lisp.
fred
(note 1) Recursion has nothing to do with programming languages. You can
write recursive assembly code just as easily as recursive Lisp. You just
push things onto "the stack" and then pop them off when you are finishing
up.
Indeed, every subroutine call, be it written in assembler, FORTRAN, C++,
or Lisp, does exactly this.
However, if you write a lisp function that explicitly uses recursion, the
compiler will be smart enough (in most cases) to compile an equivalent
function that uses iteration instead of recursion.
(note 2) I've put the brackets in here, even though they are unnecessary,
to call attention to the fact that C and Lisp have nearly identical
syntax.
(note 3) Strictly speaking, this particular "(progn" is unnecessary (defun
has one "built in"), but I put it there to make it clear that Lisp has it,
and that it can be used just like any other function call, and that it
works just like you think it should: evaluate each statement in turn, and
return the result of the last one.
Note however, that C does not work precisely this way -- without the
explicit "return" statement, the result of the function is unpredictable,
despite the fact that the compiler will not signal an error!
Henry Baker
In article <33CE62...@capital.net>, peac...@capital.net wrote:
> Have you ever seen a the quicksort algorithm written in Lisp?
> Even though it is a recursive function, it still needs well over
> 100 lines of code. In C it would only be 5 or 6 lines.
;;; Quicksort a lisp list in considerably fewer than 100 lines of code :-)
(defun qs (x l) ; sort the list x onto the list l.
(if (null x) l
(let* ((i (car x)) (restx (cdr x))
(high low (highlow restx i nil nil)))
(qs low (cons i (qs high l))))))
(defun highlow (x i h l) ; select the high and low elts of x onto h and l.
(if (null x) (values h l)
(let* ((firstx (car x)) (restx (cdr x)))
(if (< firstx i) (highlow restx i h (cons firstx l))
(highlow restx i (cons firstx h) l)))))
This is from my paper "A 'Linear Logic' Quicksort' ACM Sigplan Notices
Feb. 1994.
ftp://ftp.netcom.com/pub/hb/hbaker/LQsort.html (also .ps.Z)
Reginald S. Perry
Sajid Ahmed the Peaceman <peac...@capital.net> writes:
> Anyway, all lisp programs, as well as the compilers and
> interpreters are broken down into assembly level code, which is
> iterative. The thing I have a problem with is with people trying
> to write programs that are completely recursive, which is what lisp
> is about. That is the wrong way to go about it. It's a tremendous
> waste.
>
I would advise that you go back to school and retake the assembly
language programming course. When I took my course, using PDP-11
assembly language BTW, I wrote recursive, iterative and self-modifying
code. Thats the beauty and pain of assembly language. You can make it
anything you want it to be. Branches and jumps are not iterative, and
at the assembly language level you can essentially jump wherever you
want and since activation frames are an artifact of the argument
passing convention you impose on the architecture, you can discard
them at this level. This means that all sorts of crazy things are
possible.
Also, in my view Lisp is not just about recursion just like C is not
just about machine level programming. The objective is to find a
medium in which it is straightforward to map abstract concepts into
computational entities. Certain concepts map well in C, some in
assembly language, others in Lisp+CLOS, others in C++,Eiffel, Sather,
Smalltalk, Perl, Tcl, whatever. So first find that medium that allows
you maximum expression, and then after you have the idea on canvas, so
to speak, then you can worry about wether you need to tweak the
medium.
Hopefully, you just program in Visual Basic and not some language where
you could hurt yourself and others, or, God forbid, learn something.
-Reggie
Rainer Joswig
In article <1997071614...@rhrz-isdn3-p5.rhrz.uni-bonn.de>,
uzs...@uni-bonn.de (Michael Schuerig) wrote:
> W. Daniel Axline <wax...@cse.unl.edu> wrote:
>
> > Actually, I have been given to understand quite the opposite. Apparently
> > whenver (during runtime) a function calls itself, it has to make another
> > complete copy of itself to run.
>
> You mean a complete copy of the function's *code*? No, definitely not.
> Parameters and local variables are allocated on the stack and control
> flow continues at the beginning of the function.
>
> If the recursive call is the last one in the function ("tail-recursion")
> this can even be done without growing the stack as the new parameters
> and variables replace the old ones. You get a function that looks
> recursive, but effectively is executed iteratively. Lisp compilers do
> this optimization, I'm not sure about others.
The tail recursive version also doesn't need any function call -
it is just a jump.
For a normal Lisp compiler there won't be much speed difference.
(fac 1000) with bignum arithmetic needs 0.1 seconds on
my Macintosh Powerbook with MCL 4.1 in all three code versions.
The iterative execution. uses less space.
I prefer a system which lets me write most of the time
functional style code (since this is clearer code most of the time)
without much speed penalty. We have that.
Rainer Joswig
In article <33C4D182...@erols.com>, jord...@erols.com wrote:
> C a subset of C++??? C came first!
>
And?
Robert Monfera
Sajid Ahmed the Peaceman wrote:
> Good Lisp programs only allow recursive code,
> without any stop codes, whereas good C programs allow for both recursive
> and iterative code.
How about Backus' FP (Functional Programming) and FFP (Formal FP)
languages? Or APL? They all provide elegant ways to resolve recursion
without the
go-down-the-bit-level-let's-program-the-X-Y-Z-registers-this-is-how-
I've-been-counting-beans-since-kindergarten loops of imperative
languages.
The ideas of FP, FFP and APL can be embedded in Lisp because it IS a
language
that allows abstraction.
As for the speed, my belief is that the more abstract the language is,
the
more optimized the application can be compiled, and it's an area where
Lisp has an
opportunity to go even further. Anyway, it's the Return on Investment
that should
tell you something about the bottom line, and now good people are _far_
more expensive
than good hardware.
C or assembly is still better for high volume, low complexity
programming
(eg. quartz watch, calculator or washing machine logic).
Cheers,
Rob
Gareth McCaughan
"Sajid Ahmed the Peaceman" trolled:
> > Thats what makes lisp so easy to use.
> >
>
> Well, in some circumstances, but if you try to right every program
> using only recursive code, it makes things much much more difficult.
It's just as well Lisp doesn't require you to use "only recursive
code", then.
> > You seem to be implieing that every recursive call gets recompiled.
>
> That is true in some languages, but not true in others.
Name three languages that require all recursive function calls
to cause the function to be recompiled. In fact, name one.
> Every recursive function, whether is LISP, Prolog, C+ , ML, or
> any other language is translated into iterative assembly (machine)
> language
> code.
That's only true if you adopt so broad a definition of "iterative"
as to make your statement meaningless.
Robert Monfera
Sajid Ahmed the Peaceman wrote:
> Every recursive function, whether is LISP, Prolog, C+ , ML, or
> any other language is translated into iterative assembly (machine)
> language
> code.
And?
(You remember Backus' contribution to Fortran? And then inventing FFP as
a corrective step?
If von Neumann had lived longer, he'd have changed the processor history
in a similar way (IMO)).
(Non-Lisp programmers, sorry for the nested parentheses.)
Robert
Barry Margolin
In article <bc-170797...@17.127.18.234>,
Fred Haineux <b...@wetware.com> wrote:
>If I write a clever compiler, it can turn recursion into iteration.
>Lisp does that, automatically. (see note 1)
This is generally only true if the function is tail-recursive. Many
recursive functions are not tail-recursive, and transforming an obviously
recursive function into a tail-recursive one may require somewhat contorted
coding. See my post with the iterative, recursive, and tail-recursive
versions of factorial.
An extremely clever compiler might be able to figure out how to transform a
recursive function into a tail-recursive one, but this requires quite a bit
of flow analysis that's beyond most compiler writers.
Steven Perryman
In article <wken95g...@laura.ilog.com> Harley Davis <da...@laura.ilog.com> writes:
>> > : You don't see commercial games written in Lisp.
>> > : You don't see application suites written in Lisp.
>>
>> None of the above are true, of course. BTW The third domain is perhaps the
>> most in fashion of those listed.
>That's interesting. Could you give a couple of examples of commercial
>games running compiled (or even interpreted) Lisp code. How about an
>application suite? Anything mainstream?
In Object Expert magazine, 2 or 3 issues ago, there was an article on this
topic. A company that writes games were using Lisp (CLOS too ?? ) with
great success. They built a layer on top of Lisp specifically for games-
related needs, and called it GOOL (Games OO Lisp/Layer ?? ) .
I can't remember the name of the game(s) offhand.
Regards,
Steven Perryman
ste...@nortel.co.uk
? the platypus {aka David Formosa}
>David Formosa wrote:
>> Ok the extened eucliden algorthum then. I have seen no way to do it
>> iteraveravly that dosen't involve stacks and a hell of a lot hard to
>> underatand code.
>I don't know whether you're a Lisp person or a C++ person (both groups
>are in the headers), so I'll do this in pseudocode.
The implemention you gave is for the eucliden algorthum. The extened
eucliden algorthum takes 'p' and 'r' and returns q such that
(p * q) mod r == 1
--
Please excuse my spelling as I suffer from agraphia see the url in my header.
William D Clinger
Here is the real answer to the question of whether all recursive
programs can be converted into iterative programs. The question
is a bit subtle, so we need precise definitions.
Definition. A recursive program parameterized by an abstract data
type T consists of a set of first-order recursion equations over T.
Definition. An iterative program over an abstract data type T
consists of a flowchart program over T.
Theorem. Any recursive program parameterized by an abstract data
type T can be translated into an iterative program over the abstract
data type T' consisting of the union of T with auxiliary stacks.
Sketch of proof: Compilers do this. QED
Patterson-Hewitt Theorem. There exists a recursive program
parameterized by an abstract data type T that cannot be
translated into an iterative program over T.
Sketch of proof: Let T have operations
b : T -> boolean
i : T -> T
f : T -> T
g : T -> T
h : T * T -> T
and consider the program F defined by
F (x) = if b (x) then i (x) else h (F (f (x)), F (g (x)))
Suppose there exists an equivalent iterative program over T.
By a construction akin to the pumping lemma for finite state
automata, you can use the Herbrand interpretation of T to
construct two distinct inputs for which the iterative program
computes the same result, at least one of which must be incorrect.
Therefore no such iterative program exists. QED
So the bottom line is that translating recursion into iteration
sometimes requires an auxiliary data structure such as a stack.
Real programming languages provide many choices for this auxiliary
structure. For example, higher order languages allow recursion to
be translated into continuation-passing style (CPS), which is an
iterative form in which first class procedures are used as the
auxiliary data structure.
Will
? the platypus {aka David Formosa}
In <33CE65...@capital.net> Sajid Ahmed the Peaceman <peac...@capital.net> writes:
>? the platypus {aka David Formosa} wrote:
[...]
>> > think that lisp functions the same way as mathematics.
>>
>> Thats what makes lisp so easy to use.
> Well, in some circumstances, but if you try to right every program
>using only recursive code, it makes things much much more difficult.
Did I say anything about using only recursive code? Becuase of lisps
closeness to mathmatics its easy to write mathmatical code. In fact
it is easy to prove lisp is correct.
[...]
>> You seem to be implieing that every recursive call gets recompiled.
> That is true in some languages, but not true in others.
No compler writer worth hir salt would do this.
[...]
> Every recursive function, whether is LISP, Prolog, C+ , ML, or
>any other language is translated into iterative assembly (machine)
>language code.
This is not true, infact it is within the bounds of possablity to directly
write recursive assembly.
Gareth McCaughan
David Formosa wrote:
> The implemention you gave is for the eucliden algorthum. The extened
> eucliden algorthum takes 'p' and 'r' and returns q such that
>
> (p * q) mod r == 1
No, the implementation I gave is for the extended Euclidean algorithm.
Given x,y it returns their gcd d, and integers a,b with ax+by=d. In
particular, if the gcd is 1 then you get ax+by=1, i.e. ax == 1 mod y,
which is exactly what you say above.
If you don't believe me, convert it into your favourite language and
try it.
Marco Antoniotti
In article <JSA.97Ju...@alexandria.organon.com> j...@alexandria.organon.com (Jon S Anthony) writes:
From: j...@alexandria.organon.com (Jon S Anthony)
Newsgroups: comp.lang.lisp,comp.programming,comp.lang.c++
Date: 17 Jul 1997 23:11:36 GMT
Organization: PSINet
Lines: 23
Distribution: world
NNTP-Posting-Host: 38.215.36.2
Xref: agate comp.lang.lisp:29312 comp.programming:52506 comp.lang.c++:282312
In article <scf67uc...@infiniti.PATH.Berkeley.EDU> mar...@infiniti.PATH.Berkeley.EDU (Marco Antoniotti) writes:
> You can go even further than that. C compilers are written mostly in
> C. However, GNAT (the Ada 95 front end to the gcc backend) is written
> partly in Ada 95 and a large portion of the CMU Common Lisp compiler
Actually, the GNAT FE is entirely written in Ada95
> is written in Common Lisp. This notion of "compiler bootstrapping" is
> as old as computer programming itself.
What's more, the GNAT RTL is largely written in Ada95
Well. I am not surprised. I just wasn't up to date.
and from what I
see, most (all?) the CMU CL functions are written in CL (including
EVAL...)
This is true as well. I just did not want to stretch it too
much. (And there are portions of CMUCL written in C - after all it
must run on UN*X platforms).
Cheers
William D Clinger
John Nagle <na...@netcom.com> wrote:
> No, Scheme came after Common LISP. Scheme was a reaction to Common
> LISP by a group of people at MIT who wanted a simple, clean LISP.
This is not true. Scheme was invented in 1975 by Gerry Sussman
and Guy L Steele Jr; see MIT AI Memo 349. Common Lisp did not
begin until after an ARPA "Lisp Community Meeting" in April 1981;
see the article by Steele and Gabriel in the History of Programming
Languages Conference (HOPL-II), SIGPLAN Notices 28(3), March 1993.
The lexical scoping of local variables in Common Lisp came from
Scheme, and Common Lisp had some influence on Scheme's later
evolution (e.g. Scheme's generic arithmetic), but by and large
these two languages evolved separately.
It is true that C is almost a subset of C++, but it is not true
that Scheme is a subset of Common Lisp. There are significant
differences between Scheme and Common Lisp concerning scope rules,
tail recursion, generic arithmetic, data types, exceptions,
continuations, macros, and the Common Lisp Object System.
The relationship between IEEE/ANSI Scheme and ANSI Common Lisp
is more like the relationship between Modula-2 and Ada83 than
the relationship between C and C++.
William D Clinger
Marco Antoniotti
In article <hbaker-1707...@10.0.2.1> hba...@netcom.com (Henry Baker) writes:
From: hba...@netcom.com (Henry Baker)
Newsgroups: comp.lang.lisp,comp.programming,comp.lang.c++
Date: Thu, 17 Jul 1997 22:15:17 GMT
Organization: nil
Content-Type: text/plain; charset=ISO-8859-1
Sender: hba...@netcom21.netcom.com
Content-Transfer-Encoding: 8bit
X-Newsreader: Yet Another NewsWatcher 2.2.0
Mime-Version: 1.0
Lines: 22
Xref: agate comp.lang.lisp:29310 comp.programming:52501 comp.lang.c++:282299
Come on Henry. This is another flame bait in disguise. :) You should
have posted the version with arrays. Otherwise, after the claim that
"Lisp does support only recursion", we'd get also the "Lisp does not
have arrays" crap. :)
Marco Antoniotti
In article <33CE62...@capital.net> Sajid Ahmed the Peaceman <peac...@capital.net> writes:
From: Sajid Ahmed the Peaceman <peac...@capital.net>
Newsgroups: comp.lang.lisp,comp.programming,comp.lang.c++
Date: Thu, 17 Jul 1997 14:22:44 -0400
Organization: Logical Net
Reply-To: peac...@capital.net
Lines: 55
NNTP-Posting-Host: dialup077.colnny1.capital.net
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: Mozilla 3.01 (WinNT; I)
Xref: agate comp.lang.lisp:29313 comp.programming:52509 comp.lang.c++:282315
Mark Greenaway wrote:
>
...
>Any decent LISP programmer, in fact any decent programmer, knows
> that. Efficiency is part of programming. But it is not the be-all and
> end-all. Yes, the lower-level parts of many LISP systems might well be
> written in C/Assembly etc.
>
> The real question is: What is the most efficient/elegant/best way to
> express a particular program? It might, for some problems, be in C or C++.
> For some, it might be LISP or Prolog. If I can write a program which
> efficiently does a job in 60 lines of well-documented LISP that would take
> 300 lines or more of C, and they both run at similiar speeds, it would
> seem that LISP is the better choice.
It is true that LISP has some built in functions that allows
a programmer to write less code. As far as speed is concerned, in almost
every situation, the same program written in C would be faster than a
similar program written in Lisp. Why? C is much closer to the machine
level
assembly code that all computers run on. Many C compilers allow inline
assembly
language code within the program.
How about
(defun i-am-a-very-fast-lisp-function (x y z)
(* i (expt y z)))
or even
(defun i-am-a-very-fast-lisp-function (x y z)
#I(i * y^^z))
followed by a
(declaim (inline i-am-a-very-fast-lisp-function))
What now?
As far as the size of the program is concerned, most of the time C
programs are smaller? Why? Good Lisp programs only allow recursive code,
without any stop codes, whereas good C programs allow for both recursive
and iterative code.
Either you have not read all the posting or you have not seen a Lisp
program or both.
Have you ever seen a the quicksort algorithm written in Lisp?
Even though it is a recursive function, it still needs well over
100 lines of code. In C it would only be 5 or 6 lines.
In Common Lisp it is even shorter!
(defvar my-array (make-array 1000 :element-type 'single-float))
(dotimes (i 1000)
(setf (aref my-array i) (random 1000000.0)))
(sort my-array #'<)
Marco Antoniotti
In article <scfyb76...@infiniti.PATH.Berkeley.EDU> mar...@infiniti.PATH.Berkeley.EDU (Marco Antoniotti) writes:
...
These are examples of non-inherently recursive functions and do not
change a bit the terms of the debate. If memory does not fail me,
there is even a closed form solution for the Fibonacci numbers that
can - hear hear - be computed in O(1) time.
I was just chastised for my big mouth. The closed form contains
exponentials that cannot be computed in constant time.
I guess *I* have to go back to the books.
Henry Baker
In article <5qmqhj$s...@pasilla.bbnplanet.com>, Barry Margolin
<bar...@bbnplanet.com> wrote:
> In article <bc-170797...@17.127.18.234>,
> Fred Haineux <b...@wetware.com> wrote:
> >If I write a clever compiler, it can turn recursion into iteration.
> >Lisp does that, automatically. (see note 1)
>
> This is generally only true if the function is tail-recursive. Many
> recursive functions are not tail-recursive, and transforming an obviously
> recursive function into a tail-recursive one may require somewhat contorted
> coding. See my post with the iterative, recursive, and tail-recursive
> versions of factorial.
EVERY function can be made tail-recursive by means of continuation-passing.
That's what Michael Fischer proved in 1972. (The original 'push'
technology :-)
David Hanley
Sajid Ahmed the Peaceman wrote:
I'm goint to ignore most of what you said, as it is clear you don't
know either lisp or C from your posts. But you raise an interesting
point later...
> [speed stuff snipped]
>
> As far as the size of the program is concerned, most of the
> time C
> programs are smaller? Why? Good Lisp programs only allow recursive
> code,
> without any stop codes, whereas good C programs allow for both
> recursive
> and iterative code.
>
> Have you ever seen a the quicksort algorithm written in Lisp?
> Even though it is a recursive function, it still needs well over
> 100 lines of code. In C it would only be 5 or 6 lines.
I'd very much like to see this C 5 or 6 line quicksort. Can you
post these
sort sources? In ant case, here's a 5 line lisp quicksort I just wrote
( took me ~5 minutes )
(defun part(lst fn) (let ((ls nil)(gs nil)) (dolist (x lst)
(if (funcall fn x) (push x ls) (push x gs)))
(list ls gs)))
(defun qs(lst cmp) (if (< (length lst) 2) lst (let* ((p (first lst))
(pt (part (rest lst) #'(lambda(x)(funcall cmp x p)))))
(nconc (qs (first pt) cmp) (list p) (qs (second pt) cmp)))))
That's quicksort. Not my sort of choice, but it works a-ok.
But I just cooked it up really quickly to show a example. Note the
iteration in
the part(partition) function!
Sajid Ahmed the Peaceman
Gareth McCaughan wrote:
>
> "Sajid Ahmed the Peaceman" trolled:
>
>
> argument.
>
You have my humble apologies.
Sajid Ahmed the Peaceman
Marco Antoniotti wrote:
>
> And in one fell swoop, 50 years of programming science and engineering
> are thrown out the window (or left for the garbage collectors :) ).
>
I feel bad for the people whose careers are based on this stuff.
I once had a professor who went to school with Ted Kazynski (aka the
Unabomber), who supposedly wrote the worlds fastest sorting algorithm.
The only catch was you needed to have more elements than the the total
number of atoms in the universe for it to be faster than any of the
so called slower sorting routines.
Peaceman
Michael Schuerig
Sajid Ahmed the Peaceman <peac...@capital.net> wrote:
> Well, in some circumstances, but if you try to right every program
> using only recursive code, it makes things much much more difficult.
Would you mind to have a look at some actual Lisp code?
Michael
--
Michael Schuerig Opinions are essentially bets on the truth of
mailto:uzs...@uni-bonn.de sentences in a language that you understand.
http://www.uni-bonn.de/~uzs90z/ -Daniel C. Dennett
Horst von Brand
"W. Daniel Axline" <wax...@cse.unl.edu> writes:
[...]
> I have written binary tree traversal algorithms which don't use a stack.
Using a parent pointer is cheating ;-)
--
Dr. Horst H. von Brand mailto:vonb...@inf.utfsm.cl
Departamento de Informatica Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria +56 32 654239
Casilla 110-V, Valparaiso, Chile Fax: +56 32 797513
Sajid Ahmed the Peaceman
Fred Haineux wrote:
>
> | Anyway, all lisp programs, as well as the compilers and
> | interpreters are broken down into assembly level code, which is
> | iterative. The thing I have a problem with is with people trying
> | to write programs that are completely recursive, which is what lisp
> | is about. That is the wrong way to go about it. It's a tremendous
> | waste.
>
> Lisp does that, automatically. (see note 1)
>
All compilers do that.
> If I want to write iteration instead of recursion in Lisp, there are
> plenty of ways to do so. I am not at any time required to use recursion.
...
> Bottom line: you can do any programming construct you like in Lisp.
>
> fred
If that is indeed the case, and considered to be good programming
style in lisp, I'll completely change my outlook on lisp, and accept
it as a decent programming language.
What I've been told when I took a course in Lisp about 5 years
ago, was that you could use iterative code, but it was considered bad
programming style, like using goto statements in other programming
languages.
Peaceman
Barry Margolin
In article <5qng2t$2...@bhars12c.bnr.co.uk>,
Steven Perryman <ste...@bnr.co.uk> wrote:
]In article <wken95g...@laura.ilog.com> Harley Davis <da...@laura.ilog.com> writes:
]>That's interesting. Could you give a couple of examples of commercial
]>games running compiled (or even interpreted) Lisp code. How about an
]>application suite? Anything mainstream?
]
]In Object Expert magazine, 2 or 3 issues ago, there was an article on this
]topic. A company that writes games were using Lisp (CLOS too ?? ) with
]great success. They built a layer on top of Lisp specifically for games-
]related needs, and called it GOOL (Games OO Lisp/Layer ?? ) .
I believe all the old Infocom games were written in ZDL (Zork Definition
Language, I think). I heard that ZDL was derived from MDL, a Lisp dialect
that was in use at MIT in the 70's, and which was used to implement the
original Zork on the PDP-10.
Sajid Ahmed the Peaceman
Henry Baker wrote:
>
> EVERY function can be made tail-recursive by means of continuation-passing.
> That's what Michael Fischer proved in 1972. (The original 'push'
> technology :-)
Good, but could you imagine writing code in lisp using tail
recursion to eveluate a triple integral formula :
x1 y1 z1
/ / /
| | | ex ey ez
| | | C x y z dx dy dz
/ / /
x0 y0 z0
It would be far easier to leave the tail recursion out.
Peaceman
Sajid Ahmed the Peaceman
Gareth McCaughan wrote:
>
> > > You seem to be implieing that every recursive call gets recompiled.
> >
> > That is true in some languages, but not true in others.
>
> to cause the function to be recompiled. In fact, name one.
>
Come to think of it, I can't remember any off hand. I
don't quite remember if Basic did this.
Anyway, I'm sure there are some language designs that don't
use the stack when making calls to functions. They would expand them
inline like a macro definition. When the code would finally be
compiled, there would be recompilations of the function calls.
Peaceman
Sajid Ahmed the Peaceman
>
> In Common Lisp it is even shorter!
>
> (defvar my-array (make-array 1000 :element-type 'single-float))
>
> (dotimes (i 1000)
> (setf (aref my-array i) (random 1000000.0)))
>
> (sort my-array #'<)
>
> Cheers
> --
> Marco Antoniotti
Good, but does it use the quick sort algorithm?
If you want to talk about built in functions, I'd like to
note that the qsort function is included in the standard c
run time libraries.
Cheers.
Peaceman
Sajid Ahmed the Peaceman
Reginald S. Perry wrote:
>
> Sajid Ahmed the Peaceman <peac...@capital.net> writes:
>
> > Anyway, all lisp programs, as well as the compilers and
> > interpreters are broken down into assembly level code, which is
> > iterative. The thing I have a problem with is with people trying
> > to write programs that are completely recursive, which is what lisp
> > is about. That is the wrong way to go about it. It's a tremendous
> > waste.
> >
>
> language programming course. When I took my course, using PDP-11
> assembly language BTW, I wrote recursive, iterative and self-modifying
> code. Thats the beauty and pain of assembly language. You can make it
> anything you want it to be. Branches and jumps are not iterative, and
> at the assembly language level you can essentially jump wherever you
> want and since activation frames are an artifact of the argument
> passing convention you impose on the architecture, you can discard
> them at this level. This means that all sorts of crazy things are
> possible.
>
Branches a jumps are too iterative.
You agree that for next loops are iterative, right?
How about if statements? They both involve branches
and jumps.
> Hopefully, you just program in Visual Basic
Sorry, no VB for me.
Peaceman
Sajid Ahmed the Peaceman
> > Even though it is a recursive function, it still needs well over
> > 100 lines of code. In C it would only be 5 or 6 lines.
>
>
> (defun qs (x l) ; sort the list x onto the list l.
> (if (null x) l
> (let* ((i (car x)) (restx (cdr x))
> (high low (highlow restx i nil nil)))
> (qs low (cons i (qs high l))))))
>
> (defun highlow (x i h l) ; select the high and low elts of x onto h and l.
> (if (null x) (values h l)
> (let* ((firstx (car x)) (restx (cdr x)))
> (if (< firstx i) (highlow restx i h (cons firstx l))
> (highlow restx i (cons firstx h) l)))))
>
> This is from my paper "A 'Linear Logic' Quicksort' ACM Sigplan Notices
> Feb. 1994.
> ftp://ftp.netcom.com/pub/hb/hbaker/LQsort.html (also .ps.Z)
>
> Come on Henry. This is another flame bait in disguise. :) You should
> have posted the version with arrays. Otherwise, after the claim that
> "Lisp does support only recursion", we'd get also the "Lisp does not
> have arrays" crap. :)
>
Looks like he got me hook line and sinker :)
The lisp code you have above is not considered to be good
lisp programming style, (or what was told to me to be good lisp
programming style):
> (let* ((i (car x)) (restx (cdr x))
> (high low (highlow restx i nil nil)))
The i and restx are fine since you can easily substitute the rhs values
wherever they are referenced in the latter part of the function.
However you can't do the same with the high and low vars.
Anyway, I took the time out to make the neccesary changes in your
code to take care of this. It's about 80 lines. I know you guys will
say I'm putting too little in each line, but I don't have access to
G-emacs
( written in Lisp,considered by many as the world's best text editor,
and considered by some as the world's most difficult to use text
editor)
where you can match up the close paranthesis to it's corresponding open
paranthesis. There has to be some kind of alignment for the
parenthesis.
Peaceman
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun high (x i h) ; select the high elts of x onto h.
(if
(null x) h
(if
(< (car x) i)
(high
(cdr x)
i
h
)
(high
(cdr x)
i
(cons
(car x)
h
)
)
)
)
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun low (x i l) ; select the low elts of x onto l.
(if
(null x) l
(if
(< (car x) i)
(low
(cdr x)
i
(cons
(car x)
l
)
)
(low
(cdr x)
i
l
)
)
)
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun qs (x l) ; sort the list x onto the
list l.
(if
(null x) l
(qs
(low
(cdr x)
(car x)
nil
)
(cons
(car x)
(qs
(high
(cdr x)
(car x)
nil
)
l
)
)
)
)
)
Johann Hibschman
In article <33CFF6...@capital.net>,
Sajid Ahmed the Peaceman <peac...@capital.net> wrote:
>
> Good, but could you imagine writing code in lisp using tail
>recursion to eveluate a triple integral formula :
>
> x1 y1 z1
> / / /
> | | | ex ey ez
> | | | C x y z dx dy dz
> / / /
> x0 y0 z0
>
>
>
> It would be far easier to leave the tail recursion out.
Actually, I've been doing some stuff sort of like this in Lisp. First
of all, I feel obligated to say that iteration isn't really considered
to be bad style, which is what I think you were aiming for. for loops
work just as well in Lisp as they do in C. (do constructs, loop
constructs, etc.)
Now on to the cool bit. Imagine you have a function which knows how
to do 1D integrals. There are a zillion out there; call the one
you've got "integrate", so (integrate f x0 x1) does what you want it
to do.
Now, to integrate your 3D function f3(x, y, z), you just have to do:
(integrate
#'(lambda (x)
(integrate
#'(lambda (y)
(integrate
#'(lambda (z) (funcall f3 x y z))
z0 z1))
y0 y1))
x0 x1)
Pretty cool, eh? You don't even have to explicitly write the three
nested for loops. Sure, it's not a very good algorithm for doing 3D
integrals, but it's simple and it works.
Part of the appeal of Lisp is how closures can be used to pull off
trickery like this.
- Johann
--
Johann A. Hibschman | Grad student in Physics, working in Astronomy.
joh...@physics.berkeley.edu | Probing pulsar pair production processes.
William Paul Vrotney
In article <33CFFD...@capital.net> Sajid Ahmed the Peaceman
<peac...@capital.net> writes:
> >
> > (defun qs (x l) ; sort the list x onto the list l.
> > (if (null x) l
> > (let* ((i (car x)) (restx (cdr x))
> > (high low (highlow restx i nil nil)))
> > (qs low (cons i (qs high l))))))
> >
>
> The lisp code you have above is not considered to be good
> lisp programming style, (or what was told to me to be good lisp
> programming style):
>
Don't believe everything you hear. The above style is far preferable to the
garbage you've suggested below. Some poor authors still use your old
fashioned garbage style in their books, especially many C and C++ books.
That doesn't justify it.
> Anyway, I took the time out to make the neccesary changes in your
> code to take care of this. It's about 80 lines. I know you guys will
> say I'm putting too little in each line, but I don't have access to
> G-emacs
Everybody has access to GNU Emacs. Down-load a copy and learn it. If you
learn it, I guarantee it will change your prehistoric thinking. After you
become more hip convert you friends who still think this way.
> ( written in Lisp,considered by many as the world's best text editor,
> and considered by some as the world's most difficult to use text
> editor)
> where you can match up the close paranthesis to it's corresponding open
> paranthesis. There has to be some kind of alignment for the
> parenthesis.
>
Why? I once encounter a large C program that used this style of formatting.
When I printed out a hardcopy to understand it the whole last page was
literally nothing but indented braces! Tell me how this is of any use to
anybody.
> Peaceman
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> (defun qs (x l) ; sort the list x onto the
> list l.
> (if
> (null x) l
> (qs
> (low
> (cdr x)
> (car x)
> nil
> )
> (cons
> (car x)
> (qs
> (high
> (cdr x)
> (car x)
> nil
> )
> l
> )
> )
> )
> )
> )
Tell me how this style of formating is of any use to anyone without a very
long straight-edge? I think that it is old fashioned and for some
programmers just a fetish.
--
William P. Vrotney - vro...@netcom.com
? the platypus {aka David Formosa}
In <33CFFD...@capital.net> Sajid Ahmed the Peaceman <peac...@capital.net> writes:
>Marco Antoniotti wrote:
[...A correctly styled lisp code...]
> The lisp code you have above is not considered to be good
>lisp programming style, (or what was told to me to be good lisp
>programming style):
[...]
> Peaceman
>;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
>(defun high (x i h) ; select the high elts of x onto h.
> (if
> (null x) h
> (if
> (< (car x) i)
> (high
> (cdr x)
> i
> h
> )
[...Rest of the code where each open bracket makes a new line...]
This is realy poorly styled lisp. For one thing a group of close brackets
gose all on one line.
This is lisp code styled as per C. It is inpossable to read or debug.
? the platypus {aka David Formosa}
In <33D000...@capital.net> Sajid Ahmed the Peaceman <peac...@capital.net> writes:
>Gareth McCaughan wrote:
[...]
>> Name three languages that require all recursive function calls
>> to cause the function to be recompiled. In fact, name one.
> Come to think of it, I can't remember any off hand. I
>don't quite remember if Basic did this.
Basic didn't have function calls.
> Anyway, I'm sure there are some language designs that don't
>use the stack when making calls to functions. They would expand them
>inline like a macro definition.
In such a languge it would be inpossable to write recursive code.
I don't beleave that such a languge exists as the size of the
exicutables would be so massive as to be useless.
Henry Baker
> Henry Baker wrote:
> >
> > EVERY function can be made tail-recursive by means of continuation-passing.
> > That's what Michael Fischer proved in 1972. (The original 'push'
> > technology :-)
>
> Good, but could you imagine writing code in lisp using tail
> recursion to eveluate a triple integral formula :
>
> x1 y1 z1
> / / /
> | | | ex ey ez
> | | | C x y z dx dy dz
> / / /
> x0 y0 z0
Yes. You could learn a lot from Sussman & Abelson's book.
You could even learn how to write a program to do those neat ascii
integral formulae in lisp!
Sajid Ahmed the Peaceman
William D Clinger wrote:
>
> Here is the real answer to the question of whether all recursive
> programs can be converted into iterative programs. The question
> is a bit subtle, so we need precise definitions.
>
> Definition. A recursive program parameterized by an abstract data
> type T consists of a set of first-order recursion equations over T.
>
> Definition. An iterative program over an abstract data type T
> consists of a flowchart program over T.
>
> Theorem. Any recursive program parameterized by an abstract data
> type T can be translated into an iterative program over the abstract
> data type T' consisting of the union of T with auxiliary stacks.
>
> Sketch of proof: Compilers do this. QED
>
> Patterson-Hewitt Theorem. There exists a recursive program
> parameterized by an abstract data type T that cannot be
> translated into an iterative program over T.
>
> Sketch of proof: Let T have operations
>
> b : T -> boolean
> i : T -> T
> f : T -> T
> g : T -> T
> h : T * T -> T
>
> and consider the program F defined by
>
> F (x) = if b (x) then i (x) else h (F (f (x)), F (g (x)))
>
> Suppose there exists an equivalent iterative program over T.
> By a construction akin to the pumping lemma for finite state
> automata, you can use the Herbrand interpretation of T to
> construct two distinct inputs for which the iterative program
> computes the same result, at least one of which must be incorrect.
> Therefore no such iterative program exists. QED
>
I don't know what the Herbrand interpretation is,
but I can give you another proof.
Suppose you want to write a function that calculates the
Sine or Cosine of a number. You can write a nonterminating recursive
function for it, which has no iterative counterpart.
The point I'm making here is for functions used on
a computer. They're all translated into iterative assembly
language code.
Peaceman
Sajid Ahmed the Peaceman
> Don't believe everything you hear. The above style is far preferable to the
> garbage you've suggested below. Some poor authors still use your old
> fashioned garbage style in their books, especially many C and C++ books.
> That doesn't justify it.
>
The above style is fine if you don't care about the
readability of your code. You need to put spacing before each line
in a program to keep track of what level your in.
> Everybody has access to GNU Emacs. Down-load a copy and learn it. If you
> learn it, I guarantee it will change your prehistoric thinking. After you
> become more hip convert you friends who still think this way.
>
Believe me, I know how to use it. The IDEs of many compilers
today offer many of Gemacs features.
> Why? I once encounter a large C program that used this style of formatting.
> When I printed out a hardcopy to understand it the whole last page was
> literally nothing but indented braces! Tell me how this is of any use to
> anybody.
>
The spacing of the brackets tells you the end of sublevel,
or how deep you are in the program. By looking at the spacing, you can
go up your code and find the previous line that has the same
amount of spacing. You're then able to easily see the begining
and end of the section.
> Tell me how this style of formating is of any use to anyone without a very
> long straight-edge? I think that it is old fashioned and for some
> programmers just a fetish.
>
Well, some programmers don't care about the readability of
their code. Why not start every line at the very first space?
Peaceman
Igor
--------------087D7F8F6DEB1927E6ECD5F1
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
W. Daniel Axline wrote:
Actually, I have been given to understand quite the opposite.
Apparently
whenver (during runtime) a function calls itself, it has to make
another
complete copy of itself to run.
Function does not make "another complete copy of itself to run."
Function only
allocates local variables on the stack
--------------087D7F8F6DEB1927E6ECD5F1
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<HTML>
W. Daniel Axline wrote:
<OL>Actually, I have been given to understand quite the opposite. Apparently
<BR>whenver (during runtime) a function calls itself, it has to make another
<BR>complete copy of itself to run.
<P> Function does not make "another complete copy of itself to run."
Function only
<BR>allocates local variables on the stack</OL>
</HTML>
--------------087D7F8F6DEB1927E6ECD5F1--
Will Hartung
Sajid Ahmed the Peaceman <peac...@capital.net> writes:
>Gareth McCaughan wrote:
>>
>> Name three languages that require all recursive function calls
>> to cause the function to be recompiled. In fact, name one.
>>
> Come to think of it, I can't remember any off hand. I
>don't quite remember if Basic did this.
> Anyway, I'm sure there are some language designs that don't
>use the stack when making calls to functions. They would expand them
>inline like a macro definition. When the code would finally be
>compiled, there would be recompilations of the function calls.
I once wrote a particularly ugly set of Macros for the PDP-11 that
used a stack for user written routines, but used the registers for
the "primitives". It did, however, save any registeres used by the
primitives on the stack, and restored them later.
Of course, all of these primitives were effectively inlined into the
code. When a programs was compiled, I had about 10% actual code, and
90% saving/restoring registers. Like I said, it was horribly ugly. On
the bright side, though, all of my assembly language projects were
less than 30 "lines" of code.
But even with this horror, recursive functions were only inlined and
expanded once during compile, and then the stack exploded to insane
sizes during the recursion.
It was a great experiment when I wrote it, but quite terrible for
anything practical.
Heck, even calculators don't do what you suggest. Even INTERCAL
doesn't do what you suggest!
--
Will Hartung - Rancho Santa Margarita. It's a dry heat. vfr...@netcom.com
1990 VFR750 - VFR=Very Red "Ho, HaHa, Dodge, Parry, Spin, HA! THRUST!"
1993 Explorer - Cage? Hell, it's a prison. -D. Duck