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
> 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
On Nov 21, 8:36 pm, Jon Harrop <····@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.
>
> --
> Dr Jon D Harrop, Flying Frog Consultancy Ltd.http://www.ffconsultancy.com/?u
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
On Nov 25, 1:50 am, Mirko <·············@gmail.com> wrote:
> On Nov 21, 8:36 pm, Jon Harrop <····@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.
>
> > --
> > Dr Jon D Harrop, Flying Frog Consultancy Ltd.http://www.ffconsultancy.com/?u
>
> 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
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.
On Nov 25, 4:41 am, Rock <···········@gmail.com> wrote:
> On Nov 25, 1:50 am, Mirko <·············@gmail.com> wrote:
>
>
>
> > On Nov 21, 8:36 pm, Jon Harrop <····@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.
>
> > > --
> > > Dr Jon D Harrop, Flying Frog Consultancy Ltd.http://www.ffconsultancy.com/?u
>
> > 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
>
> 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.
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.
On Nov 25, 1:41 am, Rock <···········@gmail.com> wrote:
> On Nov 25, 1:50 am, Mirko <·············@gmail.com> wrote:
>
>
>
> > On Nov 21, 8:36 pm, Jon Harrop <····@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.
>
> > > --
> > > Dr Jon D Harrop, Flying Frog Consultancy Ltd.http://www.ffconsultancy.com/?u
>
> > 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
>
> 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!
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/
☄
On 25 nov, 16:43, Xah Lee <······@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 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
Xah Lee <······@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
Bakul Shah wrote:
> Thomas F. Burdick wrote:
>> On 25 nov, 16:43, Xah Lee <······@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
Jon Harrop wrote:
> Bakul Shah wrote:
>> Thomas F. Burdick wrote:
>>> On 25 nov, 16:43, Xah Lee <······@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
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. :-)
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
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
Xah Lee wrote:
> On Nov 25, 1:41 am, Rock <···········@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
From: Lew
Subject: Re: what do lispers think of clojure?
Date:
Message-ID: <ggng3e$gpv$2@aioe.org>
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
Mirko wrote:
> On Nov 21, 8:36 pm, Jon Harrop <····@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.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
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).
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
> 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.
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. 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.
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
Some entity, AKA "Dimiter \"malkia\" Stanev" <······@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
On Nov 26, 7:04 pm, Cor Gest <····@clsnet.nl> wrote:
> Some entity, AKA "Dimiter \"malkia\" Stanev" <······@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
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]
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.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
On Nov 27, 6:00 am, Jon Harrop <····@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/
☄
Xah Lee <······@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 <··············@zuse.dina.kvl.dk>
On Nov 27, 7:34 am, Tassilo Horn <·······@member.fsf.org> wrote:
> Xah Lee <······@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/
☄
From: Don Geddis
Subject: Re: what do lispers think of clojure?
Date:
Message-ID: <87fxlcsxxw.fsf@geddis.org>
Xah Lee <······@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/ ···@geddis.org
Sometimes I think I'd be better off dead. No, wait. Not me, you.
-- Deep Thoughts, by Jack Handey [1999]
Xah Lee <······@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
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/
☄
On Nov 27, 12:19 pm, Tassilo Horn <·······@member.fsf.org> wrote:
> Xah Lee <······@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 <······@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
> On Nov 27, 12:19 pm, Tassilo Horn <·······@member.fsf.org> wrote:
>> Xah Lee <······@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
>
>
--
sudo = stallman user designation option
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.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
On Nov 27, 5:59 pm, Jon Harrop <····@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/
☄
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/
Jon Harrop wrote:
> 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.
>
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
On Nov 26, 7:01 pm, Jon Harrop <····@ffconsultancy.com> 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.
>
> 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).
>
> --
> Dr Jon D Harrop, Flying Frog Consultancy Ltd.http://www.ffconsultancy.com/?u
will java become lisp?