4 ms·
Python does not do tail recursion, though! def f(n): if n <= 0: return n return f(n-1) f(1000) will blow out your stack. Meanwhile
by vitus 6y ago
Python does not do tail recursion, though!
def f(n):
if n <= 0:
return n
return f(n-1)
f(1000)
will blow out your stack. Meanwhile,
scheme@(guile-user)> (define (f n) (if (<= n 0) n (f (- n 1))))
scheme@(guile-user)> (f 1000000)
$1 = 0
Also bear in mind that this was lesson 1 of an intro programming course that culminates in writing a Scheme interpreter in Scheme. There's something to be said about the simplicity / consistency of a language's syntax such that a first-year undergrad can implement it.
- taeric 6y agoThe truly mind blowing one, to me, is it is one of the first handful of lessons that they go over symbolic derivatives.
- spekcular 6y agoBut this is not symbolic differentiation, it's numerical differentiation. A true symbolic integrator would not give 48.00120000993502 when asked for the value of 3x^2 at 4. This kind of approximation exercise is given to calculus students all the time ("Use the definition of derivative to approximate the derivative of f(x) at 3 by taking dx=.001," etc.). edit: I misread! See reply below.
- taeric 6y agoRight, I was referencing later lessons. Section 2.3 of the book. Surprisingly early. Granted Knuth's work also did symbolic rather early. A bit harder to work with in his. Edit: To be fair, I could have worded that first post more clearly! :D
- etaioinshrdlu 6y agoIt seems like a lot of Lisps don't do tail call optimization either though, such as Emacs lisp, common lisp, and Clojure.
- taeric 6y agoThat was the point of the lecture talking about how their system /could/ do this. I get the impression that scheme was one of the first languages that mandated that, though I suspect someone with a better view of history can correct that. For common lisp, I thought it was just not required, but that it was common to do so?
- fishmaster 6y agoNot true, SBCL definitely has TCO.
- mrtranscendence 6y agoClojure is so close. I never understood why it went for a special form rather than proper TCO.
- pimeys 6y agoIf I remember correctly it is a restriction of JVM. That's why Scala also needs a special annotation for TCO.
- patrickthebold 6y agoThat's not quite right. In Scala, the annotation is there so you get a complier error if it does not do the optimization. It doesn't affect when the compiler actually does the annotation. As you can imagine, there are cases where the developer is counting on the optimization but the code isn't such that it can be made.
- waynesonfire 6y agoYour post got me curious and I did some googling. I think this explains it, https://softwareengineering.stackexchange.com/questions/157684/what-limitations-does-the-jvm-impose-on-tail-call-optimization https://softwareengineering.stackexchange.com/questions/1576... Looks like it's a scalac optimization that doesn't always work hence the need for the annotation to give the developer feedback. There is also a link to a Closure discussion board exploring why Clojure doesn't have the annotation, by design. I didn't read it as I'm not that interested.
- zitterbewegung 6y agoYann LeCun created a lisp called Lush which allowed for the intermixing of C code with lisp and also allowed for interaction with Python. Eventually he would later make Torch which used Lua which was inspired by Scheme. Then Tensorflow and Pytorch basically are the two large players in deep learning. Now Google has JAX which allows for symbolic differentiation of Python code.
- madhadron 6y agoOh, I forgot that Lush was LeCun's work. It was such an odd beast...
- gumby 6y ago> Also bear in mind that this was lesson 1 of an intro programming course Back in '83 when the author took 6.001 only a minority of students had previously used a computer (note that Hal is quoted as having said, “If you already know how to program..." (emphasis mine). For the majority of students back then this wasn't just "introduction to programming" but "introduction to computers". Lots of non-EECS students took the class.