what do lispers think of clojure?

36 views
Skip to first unread message

gavino

unread,
Nov 20, 2008, 2:30:29 PM11/20/08
to

Jon Harrop

unread,
Nov 21, 2008, 8:36:05 PM11/21/08
to
gavino wrote:
> http://clojure.org

Clojure is Lisp's best chance of success for people who earn their living. I
thought Rich's presentation was very compelling, making it sound like
Clojure is the pinnacle of dynamic programming languages.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u

Giovanni Gigante

unread,
Nov 22, 2008, 10:16:58 AM11/22/08
to Giovanni Gigante

> Clojure is Lisp's best chance of success for people who earn their living. I
> thought Rich's presentation was very compelling, making it sound like
> Clojure is the pinnacle of dynamic programming languages.


One more specific thing I am curious about: how fast Clojure is?
IMHO one of the wonderful things of Common Lisp is that, while much
higher-level than C, it can provide a comparable execution speed (with
properly optimized code).
I have seen benchmarks saying that clojure is faster than python. But
how does it compare to C (or optimized CL)?

giovanni

Message has been deleted

Mirko

unread,
Nov 24, 2008, 7:50:58 PM11/24/08
to

Yep, his enthusiasm is infecting. I was a bit disappointed with two
aspects:
- no complex number support (because Java lacks it)
- cannot run yet on Android (for reasons way over my head)
(although one should never be disappointed with a remarkable piece of
work that is being given to the community)

Mirko

Jon Harrop

unread,
Nov 24, 2008, 8:57:11 PM11/24/08
to
Mirko wrote:
> On Nov 21, 8:36 pm, Jon Harrop <j...@ffconsultancy.com> wrote:
>> gavino wrote:
>> >http://clojure.org
>>
>> Clojure is Lisp's best chance of success for people who earn their
>> living. I thought Rich's presentation was very compelling, making it
>> sound like Clojure is the pinnacle of dynamic programming languages.
>
> Yep, his enthusiasm is infecting. I was a bit disappointed with two
> aspects:
> - no complex number support (because Java lacks it)

This is just another shortcoming of the JVM. No tail calls is my pet peeve.

> - cannot run yet on Android (for reasons way over my head)
> (although one should never be disappointed with a remarkable piece of
> work that is being given to the community)

Right.

Rock

unread,
Nov 25, 2008, 4:41:32 AM11/25/08
to

Yeah, no complex number support! Very disappointing when I found out.
I even had an exchange with Rich Hickey on the issue. He says he's got
nothing against complex numbers obviously, but he hasn't got the time
to implement them, and for performance reasons it looks like it has to
be done in Java. I wanted to give it a try, but I am definitely no
Java programmer, so I've happily come back to good old Common Lisp.
I'm a mathematician and complex numbers are VERY important, and I
think CL (with few other languages) has got the best support in this
respect.

Mirko

unread,
Nov 25, 2008, 6:48:11 AM11/25/08
to

Um, I it was from that conversation on that I learned about the
aforementioned deficiency.

But in all fairness to Rich, considering the anal (meaning very
detailed, and mathematically correct) implementation of complex
numbers in CL, I am not surprised he punted.

Xah Lee

unread,
Nov 25, 2008, 10:43:54 AM11/25/08
to

Native support of complex numbers in a general purpose language of
today, is absolutely necessary!

Java being a pain in the ass in so many ways, doesn't have complex
numbers as a native datatype.

However, luckily there are few roburst 3rd-party open source java
packages that does it. See:

• Complex Numbers in Java
http://xahlee.org/java-a-day/ex_complex.html

So, if Clojure doesn't want to be another toy, it must support it.

maybe the author doesn't have time, maybe it's complex, maybe it must
be implemented in java for speed or whatnot, but that's not the user's
problem. In short, have it in Clojure out of the box soon, or be
assured Clojure won't have a future. (trust me on this)

See also:

• Proliferation of Computing Languages
http://xahlee.org/UnixResource_dir/writ/new_langs.html

Xah
http://xahlee.org/


Thomas F. Burdick

unread,
Nov 25, 2008, 11:31:58 AM11/25/08
to
On 25 nov, 16:43, Xah Lee <xah...@gmail.com> wrote:

> Native support of complex numbers in a general purpose language of
> today, is absolutely necessary!

How do you figure? It seems more like native support for complex
numbers were more valued 20-30 years ago. The GP languages with such
support date from then ... off the top of my head, I can't think of a
single such language "of today".

Bakul Shah

unread,
Nov 25, 2008, 12:20:40 PM11/25/08
to

C99?

Rock

unread,
Nov 25, 2008, 12:50:02 PM11/25/08
to

Python?

Rock

unread,
Nov 25, 2008, 12:54:01 PM11/25/08
to

And let me add that it's not just a matter of supporting complex
floats. CL and Scheme have always been able to support a full numeric
tower. You've got complex rationals and gaussian integers just as much
as you have complex floats. That is really cool, I believe. I think
it's a big mistake on Clojure's part to underestimate this fact.

Just my 2c.

Rock

Rock

unread,
Nov 25, 2008, 4:05:43 PM11/25/08
to
Nice post here on the topic. I feel EXACTLY the same way :)

http://hans.fugal.net/blog/2008/11/17/clojure-dsp-longing

jos...@corporate-world.lisp.de

unread,
Nov 25, 2008, 4:25:24 PM11/25/08
to
On 25 Nov., 22:05, Rock <rocco.ro...@gmail.com> wrote:
> Nice post here on the topic. I feel EXACTLY the same way :)
>
> http://hans.fugal.net/blog/2008/11/17/clojure-dsp-longing

Maybe you like this:

http://xach.livejournal.com/199225.html

David McClain uses Common Lisp for signal processing software.
Recently he wrote about
speed ups in his software after Martin Simmons gave some hints
about how to use the LispWorks foreign function interface...

Jon Harrop

unread,
Nov 25, 2008, 5:43:05 PM11/25/08
to

Today != 1999

Xah Lee

unread,
Nov 25, 2008, 4:54:46 PM11/25/08
to
On Nov 25, 8:31 am, "Thomas F. Burdick" <tburd...@gmail.com> wrote:
> On 25 nov, 16:43, Xah Lee <xah...@gmail.com> wrote:
>
> > Native support of complex numbers in a general purpose language of
> > today, is absolutely necessary!
>
> How do you figure? It seems more like native support for complex
> numbers were more valued 20-30 years ago. The GP languages with such
> support date from then ... off the top of my head, I can't think of a
> single such language "of today".

On Nov 25, 9:54 am, Rock <rocco.ro...@gmail.com> wrote:
> > > C99?
>
> > Python?
>
> And let me add that it's not just a matter of supporting complex
> floats. CL and Scheme have always been able to support a full numeric
> tower. You've got complex rationals and gaussian integers just as much
> as you have complex floats. That is really cool, I believe. I think
> it's a big mistake on Clojure's part to underestimate this fact.

Adding to what has been said in this thread ...

lisp dialects always supported the complex numbers as well as rational
numbers. Clojure being lispy, not supporting these will not please its
main audience.

also, functional langs are in general strong in math and AI fields.
Full support of complex numbers in necessary.

Sure, 3rd party can always write one. To have full complex number
support to the level of industrial use, is not trivial. Even with the
existing 3rd party open source complex number packages for java... it
makes user to wonder to what degree they are robust... this means lots
of time spent to test it out, and there's the arbitrary choice of
syntax made by the 3rd party. Two 3rd party complex number libs will
likely not be compatible, etc.

as mentioned, C99, Python support it natively. In python, as far as
i've seen, it's support is minimal... just allowing to add and
multiply with it, possbly also taking the phase/degree, length, but
not necessarily allowing other functions such as square root or trig
to work with complex numbers. So, here we see that full support is not
trivial. Also, if we implement complex numbers on top of a lang that
doesn't natively support it, then making it work fast for industrial
use such as scientific computing is also not trivial.

Java is rather a low level lang as opposed to scripting lang such as
perl, python, ruby, etc. Also it is a large lang with heavy
architecture that does almost anything, as opposed to C. As such, lack
of native complex number support is problematic.

Sure, most programing tasks don't involve complex numbers. But with
the proliferation of langs, esp in the past 5 years, you have so many
languages coming out, and so many functional languages too even ... as
time matches goes on, lang are just getting higher and higher level,
and that basically means it can do a lot more things out of the box,
lacking complex numbers will mean your lang loses a edge. I doubt any
general purpose lang as heavy weight as java from today on will not
have complex num support.

i don't think we are seeing the end of proliferation. I think there
will be more and more. Even today it's hard to keep track what's
coming into the scene.

These new langs are not just random toys by random student of some
random proof of concept or weird idea. Each is sufficient robust in
some way to be usable in some industry or academia or niche.

Look at this list:

• Proliferation of Computing Languages
http://xahlee.org/UnixResource_dir/writ/new_langs.html

and go read Wikipedia on the rest tens of langs you never heard of
even for us tech geekers who keep our heads in tech and lang news. If
you spend few hours reading, you'll find that how each is rather
extensive ... not something some nobody curios university compiler
student made as is the situation say before 2000.

In anycase, it'd be fruitful if we can have a list of lang today and
whether they support complex numbers. Here i'll start:

Mathematica yes
Common Lisp yes
Scheme Lisps yes

NewLisp ?
Arc yes?
Qi yes?
Scala ?
Dylan ?
Coq ?

Sleep ?
Groovy ?

ObjectiveC ?
C# ?
D ?

Java no
Erlang ?
Haskell ?
Concurrent Clean ?
Mercury ?
Q ?
Qz ?
OCaml ?
Alice ?
F# ?
SmallTalk ?

Scratch ?
ActionScript no?
Processing ?

Python yes
Lua no?
Tcl no?
Ruby ?
Perl6 ?
Javascript no?
AppleScript no?

APL
Forth
Logo
Pascal

Xah
http://xahlee.org/

Rock

unread,
Nov 25, 2008, 6:27:22 PM11/25/08
to

In Python there's no problem with applying mathematical functions to
complex numbers (sin, atan, sqrt, etc...). Fully supported. Not as
extensively as CL or Scheme of course (no complex rationals for
instance), yet supported to a fair extent.

Rock

Jon Harrop

unread,
Nov 26, 2008, 11:21:27 AM11/26/08
to
Xah Lee wrote:
> In anycase, it'd be fruitful if we can have a list of lang today and
> whether they support complex numbers. Here i'll start:
> ...
> C# ?

No.

> OCaml ?

Yes.

> F# ?

Yes.

Thomas F. Burdick

unread,
Nov 26, 2008, 11:46:37 AM11/26/08
to

Right, this whole thread exposed a blind spot in my reasoning: I was
working under the unstated assumption that *useful* complex numbers
require rationals, which in turn pretty much require bignums to be
useful. Which pretty much leaves ... various Lisps, some Smalltalks,
mathematical languages (which is pushing the "GP" thing a bit),
and ... ?

The blind spot is of course because complex numbers are a useful
addition to rationals. Not having rationals is appalling, but common,
and it seems only older languages care about them.

Scott

unread,
Nov 26, 2008, 12:19:27 PM11/26/08
to
On Nov 26, 9:46 am, "Thomas F. Burdick" <tburd...@gmail.com> wrote:
>
> Right, this whole thread exposed a blind spot in my reasoning: I was
> working under the unstated assumption that *useful* complex numbers
> require rationals, which in turn pretty much require bignums to be
> useful. Which pretty much leaves ... various Lisps, some Smalltalks,
> mathematical languages (which is pushing the "GP" thing a bit),
> and ... ?
>
> Not having rationals is appalling, but common,
> and it seems only older languages care about them.

I agree that any language worth it's salt for scientific purposes
should have complex numbers, but the reason most of us don't care
about rationals is because we have to do things with transcendental
functions... I don't need an array of rational numbers when the first
thing I'm going to do with that array is take an FFT (which multiplies
the elements by sines and cosines...). As such, arbitrary precision
rational numbers are *useless* to me.

jurgen_defurne

unread,
Nov 26, 2008, 12:33:27 PM11/26/08
to

That from the tail calls is one of the things that puzzles me the
most. I mean, the lambda papers date from the mid 70's and a little
bit later, and in them, Steele and Sussman show how languages can be
built, and then about 20 years later, Java is created without
(seemingly) any of the lessons that Steele and Sussman have provided,
despite Steele also working on Java, together with Gabriel (any other
people from the 70's/80's Lisp community?).

jos...@corporate-world.lisp.de

unread,
Nov 26, 2008, 12:54:21 PM11/26/08
to

Steele said in a Fortress presentation that complex numbers are
important. But they should not be part of the core language. The
language should instead be extensible that it is possible to add them
via a library. So in Fortress complex numbers are provided via
library.

David Golden

unread,
Nov 26, 2008, 2:04:19 PM11/26/08
to
jurgen_defurne wrote:


> That from the tail calls is one of the things that puzzles me the
> most. I mean, the lambda papers date from the mid 70's and a little
> bit later, and in them, Steele and Sussman show how languages can be
> built, and then about 20 years later, Java is created without
> (seemingly) any of the lessons that Steele and Sussman have provided,
> despite Steele also working on Java, together with Gabriel (any other
> people from the 70's/80's Lisp community?).


It was a security thing, though things have moved on a bit:

"A Tail Recursive Machine with Stack Inspection", Clements and
Felleisen, 2004
http://www.csc.calpoly.edu/~clements/papers/cf-toplas04.pdf
http://lambda-the-ultimate.org/node/1333

| Security folklore holds that a security mechanism based on stack
| inspection is incompatible with a global tail call optimization
| policy. [...] In this article we prove this widely held belief
| wrong. [...] The Java design team, for example, chose not to
| provice a TCO implementation in part because of the perceived in-
| compatibility between tail call optimizations and stack inspection.
| The .NET effort at Micrsoft provides a runtime system that is
| properly TCO - except in the presence of security primitives, which
| disable it.


Xah Lee

unread,
Nov 26, 2008, 2:57:02 PM11/26/08
to

On Nov 26, 9:54 am, "jos...@corporate-world.lisp.de" <jos...@corporate-

world.lisp.de> wrote:
> Steele said in a Fortress presentation that complex numbers are
> important. But they should not be part of the core language. The
> language should instead be extensible that it is possible to add them
> via a library. So in Fortress complex numbers are provided via
> library.

Interesting.

That remark can be considered the most stupid depending on what the
author means by “part of the language”.

To clarify the issue in this thread, what i personaly mean by “wanting
complex number buildin in the lang”, is in the sense that that a user
of the lang can use complex numbers out of the box. In other words,
it's bundled.

Let me give some detail. For example, regex. Perl has the regex as
part of the lang. Python has it as a lib. Namely, you have to “import”
it before you can use it. In Java, as far as i know, it's not present.
These 3 models illustrate the issue. With regard to this discussion, i
consider both perl and python having regex “buildin”, while java does
not. (note: java 5 or java 6 might have added regex in the past few
years but i haven't kept up)

Many geekers would go into great length of debate the pros and cons of
perl's part-of-lang regex vs python's regex-as-library. Often terms
like “core”, “primitive”, “native” are also used to debate about
whether some lang has some feature or facility. I think most of these
debates are stupid.

The far more important question is whether certain feature or
facility, is available, “out of the box” with the language. A
language's utility, and popularity, depends on this “out of the box”
nature of feature much more so then some tech geeking concept like
“core”, “native”, “primitive”.

So, i think Java should've had complex numbers out of the box, and
Clojure should have it now. And, if Steele thinks that complex numbers
shouldn't be available out of the box of whatever lang he's designing,
that'd be super stupid.

Xah
http://xahlee.org/

Bruce Stephens

unread,
Nov 26, 2008, 3:09:53 PM11/26/08
to
Xah Lee <xah...@gmail.com> writes:

[...]

> To clarify the issue in this thread, what i personaly mean by “wanting
> complex number buildin in the lang”, is in the sense that that a user
> of the lang can use complex numbers out of the box. In other words,
> it's bundled.

Quite. Whether it fits into an implementation's notion of "language"
or "library" is of no consequence, and might reasonably differ between
implementations.

C++ has complex, and I guess it's usually in a library (or inline in a
header), but it might not be---all the standard says is that if you
have "#include <complex>" then you get to use the std::complex type.

[...]

Tassilo Horn

unread,
Nov 26, 2008, 4:11:54 PM11/26/08
to
Xah Lee <xah...@gmail.com> writes:

Hi,

> Let me give some detail. For example, regex. Perl has the regex as
> part of the lang. Python has it as a lib. Namely, you have to “import”
> it before you can use it. In Java, as far as i know, it's not present.

Java has java.util.regex since 1.4.

Bye,
Tassilo

Tamas K Papp

unread,
Nov 26, 2008, 4:54:51 PM11/26/08
to
On Wed, 26 Nov 2008 08:46:37 -0800, Thomas F. Burdick wrote:

> working under the unstated assumption that *useful* complex numbers
> require rationals, which in turn pretty much require bignums to be

I don't agree. Complex numbers do not have to be rational/exact to be
handy - think about a Schur decomposition for instance.

Best,

Tamas

Jon Harrop

unread,
Nov 26, 2008, 10:01:56 PM11/26/08
to
jurgen_defurne wrote:
> That from the tail calls is one of the things that puzzles me the
> most. I mean, the lambda papers date from the mid 70's and a little
> bit later, and in them, Steele and Sussman show how languages can be
> built, and then about 20 years later, Java is created without
> (seemingly) any of the lessons that Steele and Sussman have provided,
> despite Steele also working on Java, together with Gabriel (any other
> people from the 70's/80's Lisp community?).

Indeed. Microsoft did this 7 years ago. Moreover, they did it deliberately
because they knew languages like F# were on the books.

But the thing that really scares me is that Sun were focussing entirely on
hugely inefficient dynamic languages (Groovy etc.), at least before they
suffered a meltdown and fired thousands of people (again).

Dimiter "malkia" Stanev

unread,
Nov 26, 2008, 9:33:31 PM11/26/08
to
> Indeed. Microsoft did this 7 years ago. Moreover, they did it deliberately
> because they knew languages like F# were on the books.

You say this, as if you were part of that process. Anything to back what
are you saying? Blog quote from one of the creators would be fine...

I always thought .NET simply was made to replace Java more or less, but
I can't say what were the original reasons.

Kenny

unread,
Nov 26, 2008, 10:04:21 PM11/26/08
to
Jon Harrop wrote:
> jurgen_defurne wrote:
>
>>That from the tail calls is one of the things that puzzles me the
>>most. I mean, the lambda papers date from the mid 70's and a little
>>bit later, and in them, Steele and Sussman show how languages can be
>>built, and then about 20 years later, Java is created without
>>(seemingly) any of the lessons that Steele and Sussman have provided,
>>despite Steele also working on Java, together with Gabriel (any other
>>people from the 70's/80's Lisp community?).
>
>
> Indeed. Microsoft did this 7 years ago. Moreover, they did it deliberately
> because they knew languages like F# were on the books.

Thanks for the giggle.

>
> But the thing that really scares me is that Sun were focussing entirely on
> hugely inefficient dynamic languages (Groovy etc.), at least before they
> suffered a meltdown and fired thousands of people (again).
>

Hugely inefficient? What makes you... oh,christ, it's the frog.

kt

Kenny

unread,
Nov 26, 2008, 10:13:27 PM11/26/08
to

World domination? Even more than they already had?

What I heard was that the guy who did NT was a/the main guy behind
Vax/Vms, and I believe it because vax/vms languages could all call each
other with sufficient programmer agonizing over call by reference vs.
call by value vs I forget the other one(s).

So you have some really cool technology but it is proprietary and it
solves the wrong problem: the problem is not how to get a Tower of Babel
of computer languages talking to each other, the problem is people not
all using the same language: Lisp.

hth, kzo

Cor Gest

unread,
Nov 26, 2008, 10:04:05 PM11/26/08
to
Some entity, AKA "Dimiter \"malkia\" Stanev" <mal...@mac.com>,
wrote this mindboggling stuff:
(selectively-snipped-or-not-p)


> I always thought .NET simply was made to replace Java more or less,
> but I can't say what were the original reasons.

Well, the (very very very) simple version of this traumatic event:

SUN-Java could NOT be bought or bribed.
SUN-Java could NOT be perverted with (ms-only)'standards'
SUN-Java could NOT be extented with (ms-only)'innovations'

Hence, MS had to roll it's own .NET & sharpies#.


Cor
--
First directive to dissuade criminal intent: Present a Gun
I may be blonde, but I'm not stupid
Self-defense is a basic human right
God made man, Colt made some equal, Khalashnikov made the poor equal too

gavino

unread,
Nov 27, 2008, 5:17:04 AM11/27/08
to

will java become lisp?

gavino

unread,
Nov 27, 2008, 5:19:10 AM11/27/08
to

I want to learn enough lisp because I know enough linux to procude a
nice website and be like there In YER FACE java! [or insert other
language of management choice here]

Jon Harrop

unread,
Nov 27, 2008, 9:00:35 AM11/27/08
to
Dimiter "malkia" Stanev wrote:
>> Indeed. Microsoft did this 7 years ago. Moreover, they did it
>> deliberately because they knew languages like F# were on the books.
>
> You say this, as if you were part of that process.

This 2001 paper describes tail calls in the CLR and is by the same guy who
did .NET generics (aka parametric polymorphism from ML) and is now doing
F#:

"ILX: Extending the .NET Common IL for Functional Language
Interoperability" -
http://icme2007.org/~dsyme/papers/babel01.pdf

> I always thought .NET simply was made to replace Java more or less, but
> I can't say what were the original reasons.

No, Microsoft had quite a few rocking ideas of their own. Indeed, F# is now
the world's gold standard functional language in terms of usability because
it combines industrial-strength libraries inherited from .NET with a
genuine functional language complete with tail calls.

Without tail calls on the JVM, Scala and Clojure cannot compete. With Sun
going bankrupt, it is unlikely we will ever see tail calls on the JVM.

Xah Lee

unread,
Nov 27, 2008, 9:48:32 AM11/27/08
to
On Nov 27, 6:00 am, Jon Harrop <j...@ffconsultancy.com> wrote:

> Without tail calls on the JVM, Scala and Clojure cannot compete. With Sun
> going bankrupt, it is unlikely we will ever see tail calls on the JVM.

Fuck the lying thru the teeth Sun Microsystems fuck with its lawsuits
and deceptions with Java. Now, time to die!

One thing commercial companies do in the brink of death is to release
their software as Open Source (or $free$) and herald the moral praises
of the stealing youngsters that largely makes up the Open Source
community. The major precursor example is Netscape. Other examples
include: SGI, Be inc, Dylan, Macintosh Common Lisp, ...

See also:

• On Microsoft Hatred
http://xahlee.org/UnixResource_dir/writ/mshatred155.html

• The Microsoft Hatred FAQ
http://xahlee.org/UnixResource_dir/writ/mshatredfaq.html

• The Unix Pestilence
http://xahlee.org/UnixResource_dir/freebooks.html

Also, please avoid the term “tail call” or “tail recursion”. Instead,
when referring to compiler implementation that optimize recursion code
that is a algorithmically flat iteration, use terms like “optimized
linear recursion implementation” or something similar. See:

• The Jargon “Tail Recursion”
http://xahlee.org/UnixResource_dir/writ/tailrecursion.html

Xah
http://xahlee.org/


Tassilo Horn

unread,
Nov 27, 2008, 10:34:50 AM11/27/08
to
Xah Lee <xah...@gmail.com> writes:

Hi,

> Also, please avoid the term “tail call” or “tail recursion”. Instead,


> when referring to compiler implementation that optimize recursion code
> that is a algorithmically flat iteration, use terms like “optimized
> linear recursion implementation” or something similar. See:
>
> • The Jargon “Tail Recursion”
> http://xahlee.org/UnixResource_dir/writ/tailrecursion.html

After reading that text I'd say that you're only half enlightened. Yes,
tail recursion is an implementation detail which enables recursive
functions to be executed in finite space, but in order to do that, the
recursive call must be the last expression. That's what makes the
"tail" in tail recursion.

Bye,
Tassilo
--
"OS's and GUI's come and go, only Emacs has lasting power."
Per Abrahamsen in <rjbsysc...@zuse.dina.kvl.dk>

Xah Lee

unread,
Nov 27, 2008, 1:31:28 PM11/27/08
to
On Nov 27, 7:34 am, Tassilo Horn <tass...@member.fsf.org> wrote:
> Xah Lee <xah...@gmail.com> writes:
>
> Hi,
>
> > Also, please avoid the term “tail call” or “tail recursion”. Instead,
> > when referring to compiler implementation that optimize recursion code
> > that is a algorithmically flat iteration, use terms like “optimized
> > linear recursion implementation” or something similar. See:
>
> > • The Jargon “Tail Recursion”
> > http://xahlee.org/UnixResource_dir/writ/tailrecursion.html
>
> After reading that text I'd say that you're only half enlightened. Yes,
> tail recursion is an implementation detail which enables recursive
> functions to be executed in finite space, but in order to do that, the
> recursive call must be the last expression. That's what makes the
> "tail" in tail recursion.

Huh?

Let's make sure we are on the same page.

recursion can be that the algorithm is recursive or the source code is
recursive.

Here's 3 aspects of recursion in our context:

• the source code is recursive. Meaning, it calls itself.
• the algorithm is recursive. Meaning, the algorithm repeats (its
steps) itself.
• the compiler produced code is recursive. (i don't know compilers,
but the basic idea is that it will consume resources proportional to
number of recursion steps.)

The essential idea in SICP book about “tail recursion”, is that when a
source code is recursive, its algorithm expressed is not necessarily
so, and in fact can be linear (in other words, recursive source code
may just express a iteration algorithm). Such source code, we could
call it “linear recursion”. The concept of the compiler recognizing
linear recursion and produce compiled code that behaves as a
iteration, can be called “linear recursion recognition”.

You seem to suggest that linear recursion in source code has one
defining characteristics, namely, that the self call occures at the
end of the function definition. (and it is implied, because of this,
therefore it “tail recursion” is a very good term for linear
recursion) Is that what you are saying?

What you are saying seems to be obviously wrong... Here's a pseudo
lisp code to demo:

(set x 1)

(defun f ()
(set x (+ x 1))
(f)
(message "hi mom")
)

Xah
http://xahlee.org/


Don Geddis

unread,
Nov 27, 2008, 3:42:19 PM11/27/08
to
Xah Lee <xah...@gmail.com> wrote on Thu, 27 Nov 2008:
> The essential idea in SICP book about "tail recursion", is that when a
> source code is recursive, its algorithm expressed is not necessarily so,
> and in fact can be linear (in other words, recursive source code may just
> express a iteration algorithm).
[...]

> What you are saying seems to be obviously wrong... Here's a pseudo
> lisp code to demo:
> (set x 1)
> (defun f ()
> (set x (+ x 1))
> (f)
> (message "hi mom")
> )

Is this example meant to show linear recursion?

What result do you expect from the algorithm, by calling the function (f)?

What is the equivalent iterative way of expressing this same algorithm?

-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ d...@geddis.org
Sometimes I think I'd be better off dead. No, wait. Not me, you.
-- Deep Thoughts, by Jack Handey [1999]

Tassilo Horn

unread,
Nov 27, 2008, 3:19:45 PM11/27/08
to
Xah Lee <xah...@gmail.com> writes:

Hi Xah,

>> After reading that text I'd say that you're only half enlightened.
>> Yes, tail recursion is an implementation detail which enables
>> recursive functions to be executed in finite space, but in order to
>> do that, the recursive call must be the last expression. That's what
>> makes the "tail" in tail recursion.

[...]

> You seem to suggest that linear recursion in source code has one
> defining characteristics, namely, that the self call occures at the
> end of the function definition. (and it is implied, because of this,
> therefore it “tail recursion” is a very good term for linear
> recursion) Is that what you are saying?

Yes, quite so. When a function is called, the caller's address (and
other state information, like local variables of the caller) is pushed
on a stack. When the function call returns, control is passed back to
the caller by popping the stack and looking at the return address. If
the call hierarchy is deep, the stack grows and grows.

But if the compiler is aware of tail recursion and the last thing a
function does (control flow wise) is a recursive call, then it's not
necessary to save the caller's state informations in a stack, because
they won't be used anymore (hey, it's the last thing in the function),
and so this tail call optimization can be performed.

If the recursive call is somewhere in the middle of a function, then it
cannot be done, because then the caller's state is still needed after
the call.

Got it?

> What you are saying seems to be obviously wrong... Here's a pseudo
> lisp code to demo:
>
> (set x 1)
>
> (defun f ()
> (set x (+ x 1))
> (f)
> (message "hi mom")
> )

What should that demo? That can neither be optimized nor will it
terminate.

Look at that example.

Here's a definition that cannot be optimized. If I execute it with (sum
9999999999999999999999999999999999999) it'll abort, cause the stack gets
too big.

--8<---------------cut here---------------start------------->8---
CL-USER> (defun sum (n)
(if (= n 0)
0
(+ (sum (- n 1)) 1)))
SUM
CL-USER> (sum 17)
17
CL-USER> (disassemble #'sum)

Disassembly of function SUM
(CONST 0) = 0
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
10 byte-code instructions:
0 L0
0 (LOAD&PUSH 1)
1 (CALLS2&JMPIF 172 L12) ; ZEROP
4 (LOAD&DEC&PUSH 1)
6 (JSR&PUSH L0)
8 (CALLS2 177) ; 1+
10 (SKIP&RET 2)
12 L12
12 (CONST 0) ; 0
13 (SKIP&RET 2)
NIL
--8<---------------cut here---------------end--------------->8---

And here's the same transformed to being tail recursive. (sum
9999999999999999999999999999999999999) yields its result in a fraction
of a second.

--8<---------------cut here---------------start------------->8---
CL-USER> (defun sum (n)
(summer n 0))
SUM
CL-USER> (defun summer (i j)
(if (= 0 j)
i
(summer (+ i 1) (- j 1))))
SUMMER
CL-USER> (sum 17)
17
CL-USER> (disassemble #'sum)

Disassembly of function SUM
(CONST 0) = 0
(CONST 1) = SUMMER
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
4 byte-code instructions:
0 (LOAD&PUSH 1)
1 (CONST&PUSH 0) ; 0
2 (CALL2 1) ; SUMMER
4 (SKIP&RET 2)
NIL
CL-USER> (disassemble #'summer)

Disassembly of function SUMMER
2 required arguments
0 optional arguments
No rest parameter
No keyword parameters
9 byte-code instructions:
0 L0
0 (LOAD&PUSH 1)
1 (CALLS2&JMPIF 172 L12) ; ZEROP
4 (LOAD&INC&PUSH 2)
6 (LOAD&DEC&PUSH 2)
8 (JMPTAIL 2 5 L0)
12 L12
12 (LOAD 2)
13 (SKIP&RET 3)
NIL
--8<---------------cut here---------------end--------------->8---

As you can see in summer's disassembly, a tail call elimination was
done (the recursive call is replaced with a jump operation).

Bye,
Tassilo

Xah Lee

unread,
Nov 27, 2008, 5:14:34 PM11/27/08
to
2008-11-27

> If the recursive call is somewhere in the middle of a function, then it
> cannot be done, because then the caller's state is still needed after
> the call.

here's a actual elisp code to demonstrate a recursive code that
expresses linear algorithm but the self-reference does not happen at
the end (aka “tail”) the the source code.

(setq x 1)

(defun f ()
(when (< x 10)
(message "%d" x)
(setq x (1+ x))
(funcall 'f)
)
(+ 1 1)
)

(f)

(for those who don't know elisp: Paste the above into a empty file in
emacs. Select them all, then type Alt+x eval-region.)

Now, in the above, you see that the call to f itself happens in the
middle of the program, not at the end. However, the algorithm
expressed by this recursive source code is still linear.

Therefore, it contradict your claim that the self-call must be at the
end for recursive code to express iteration.

> Got it?

if you try not to begin to be a moron, i foresee we could have
fruitful conversation, where i teach you computer science and
mathematical thinking, while you might teach me something about
compiler.

To reduce back n forth posts, let me just say here first that you need
to pay attention to distinguish the source code, the algorithm, and
the algorithm produced by the compiler code. With clear awareness of
these distinctions, then we can have better communication.

Xah
http://xahlee.org/

Arne Vajhøj

unread,
Nov 27, 2008, 6:37:23 PM11/27/08
to
Xah Lee wrote:
> On Nov 25, 1:41 am, Rock <rocco.ro...@gmail.com> wrote:
>> Yeah, no complex number support! Very disappointing when I found out.
>> I even had an exchange with Rich Hickey on the issue. He says he's got
>> nothing against complex numbers obviously, but he hasn't got the time
>> to implement them, and for performance reasons it looks like it has to
>> be done in Java. I wanted to give it a try, but I am definitely no
>> Java programmer, so I've happily come back to good old Common Lisp.
>> I'm a mathematician and complex numbers are VERY important, and I
>> think CL (with few other languages) has got the best support in this
>> respect.

>
> Native support of complex numbers in a general purpose language of
> today, is absolutely necessary!

Complex numbers are very useful in scientific computing
but not in business computing.

> Java being a pain in the ass in so many ways, doesn't have complex
> numbers as a native datatype.

Scientific computing has never been a high priority for Java.

Arne

Arne Vajhøj

unread,
Nov 27, 2008, 6:40:50 PM11/27/08
to
Bakul Shah wrote:
> Thomas F. Burdick wrote:
>> On 25 nov, 16:43, Xah Lee <xah...@gmail.com> wrote:
>>
>>> Native support of complex numbers in a general purpose language of
>>> today, is absolutely necessary!
>>
>> How do you figure? It seems more like native support for complex
>> numbers were more valued 20-30 years ago. The GP languages with such
>> support date from then ... off the top of my head, I can't think of a
>> single such language "of today".
>
> C99?

The complex support in C99 is not that good.

Even Fortran is better.

Arne

Arne Vajhøj

unread,
Nov 27, 2008, 6:42:58 PM11/27/08
to
Jon Harrop wrote:
> Bakul Shah wrote:
>> Thomas F. Burdick wrote:
>>> On 25 nov, 16:43, Xah Lee <xah...@gmail.com> wrote:
>>>
>>>> Native support of complex numbers in a general purpose language of
>>>> today, is absolutely necessary!
>>> How do you figure? It seems more like native support for complex
>>> numbers were more valued 20-30 years ago. The GP languages with such
>>> support date from then ... off the top of my head, I can't think of a
>>> single such language "of today".
>> C99?
>
> Today != 1999

Today is very close to 99 when we talk about the C standard.

Lot of compiler have not even implemented all of C99.

Other priorities.

Arne

Lew

unread,
Nov 27, 2008, 8:04:46 PM11/27/08
to
Xah Lee wrote:
>> Java being a pain in the ass in so many ways, doesn't have complex
>> numbers as a native datatype.

Arne Vajhøj wrote:
> Scientific computing has never been a high priority for Java.

Besides, even if we grant "Java being a pain in the ass in so many ways",
unsubstantiated as that toss-off is, it remains to establish that Java is any
more a "pain in the ass" than any other computer language, or in any way not
inherent to computer languages generally

--
Lew

Jon Harrop

unread,
Nov 27, 2008, 8:56:23 PM11/27/08
to
Arne Vajhøj wrote:

> Jon Harrop wrote:
>> Today != 1999
>
> Today is very close to 99 when we talk about the C standard.
>
> Lot of compiler have not even implemented all of C99.
>
> Other priorities.

Other languages more like. :-)

Jon Harrop

unread,
Nov 27, 2008, 8:59:55 PM11/27/08
to
Xah Lee wrote:
> Also, please avoid the term “tail call” or “tail recursion”. Instead,
> when referring to compiler implementation that optimize recursion code
> that is a algorithmically flat iteration, use terms like “optimized
> linear recursion implementation” or something similar.

Tail recursion is only one special case of tail calls. I was deliberately
referring to all tail calls.

Arne Vajhøj

unread,
Nov 27, 2008, 9:00:00 PM11/27/08
to
Jon Harrop wrote:
> Arne Vajhøj wrote:
>> Jon Harrop wrote:
>>> Today != 1999
>> Today is very close to 99 when we talk about the C standard.
>>
>> Lot of compiler have not even implemented all of C99.
>>
>> Other priorities.
>
> Other languages more like. :-)

Yes.

Arne

Tassilo Horn

unread,
Nov 28, 2008, 2:38:38 AM11/28/08
to
Xah Lee <xah...@gmail.com> writes:

Hi,

>> If the recursive call is somewhere in the middle of a function, then


>> it cannot be done, because then the caller's state is still needed
>> after the call.

The "it" in the above sentence is not the recursive call itself, but the
tail call optimization cannot be done.

> here's a actual elisp code to demonstrate a recursive code that
> expresses linear algorithm but the self-reference does not happen at
> the end (aka “tail”) the the source code.

Yes, recursion works no matter where the recursive call is in the
function. But the call stack grows at least linear then, and if it gets
too deep, it'll abort.

If the last expression in the control flow graph of a function is a
recursive call, then the stacking isn't needed and a jump operation can
be used instead. So the space complexity shrinks from O(n) where n is
the recursion depth to O(x) for some constant x.

So if it didn't get clear with my last posting: Sure, recursion always
works, but without tail call optimization you need to use a call stack
which grows linear to the depth of the function calls. With tail call
optimization, which requires that the recursive call is the last thing
in a function's control flow, then you can shrink the needed space for
the calculation to a constant value.

> Therefore, it contradict your claim that the self-call must be at the
> end for recursive code to express iteration.

I didn't claim that! I claim that it must be at the end of control flow
to enable the compiler to do tail call optimization and reduce the space
complexity from linear to constant.

> if you try not to begin to be a moron, i foresee we could have
> fruitful conversation, where i teach you computer science and
> mathematical thinking,

Thanks, I already have a diploma in computer science. ;-)

> To reduce back n forth posts, let me just say here first that you need
> to pay attention to distinguish the source code, the algorithm, and
> the algorithm produced by the compiler code. With clear awareness of
> these distinctions, then we can have better communication.

Yes. So what I say is that making a clever source code version of some
iterative algorithm where the recursive call is the last thing in a
function, can enable the compiler to make machine code that has constant
space requirements.

Bye,
Tassilo

--
sudo = stallman user designation option

Xah Lee

unread,
Nov 29, 2008, 1:39:48 PM11/29/08
to
On Nov 27, 5:59 pm, Jon Harrop <j...@ffconsultancy.com> wrote:
> XahLee wrote:
> > Also, please avoid the term “tailcall” or “tailrecursion”. Instead,

> > when referring to compiler implementation that optimize recursion code
> > that is a algorithmically flat iteration, use terms like “optimized
> > linear recursion implementation” or something similar.
>
> Tailrecursion is only one special case oftailcalls. I was deliberately

> referring to all tail calls.

Good point.

Xah
http://xahlee.org/


Dimiter "malkia" Stanev

unread,
Dec 1, 2008, 4:35:55 PM12/1/08
to
Thank you!

It looks like there are still some cool stuff coming from there!

(Hugues Hoppe is my favourite MS research scientist btw):
http://research.microsoft.com/~hoppe/

Reply all
Reply to author
Forward
0 new messages