10 ms·

Python to Scheme to Assembly (2014)

127 points by sea6ear 12y ago

hawkice 12y ago
If your goal is to reason about correctness, recursion can be a useful tool. Assembly... is not the hammer I'd bust out for that particular reasoning task.
deleted 12y ago
[deleted]
rpedroso 12y ago
This article really got me in the mood to play around with Racket again. Incidentally, I find it hard to square with Guido's belief that recursion isn't the basis of all programming. Sure, Python has some powerful iterators, but my CS professors made it clear that iteration is basically just a special case of recursion. It might very well be the right decision for Python to prefer iteration, but to deny the role of recursion in computer science altogether seems misguided.
- Dewie 12y ago
  > , but my CS professors made it clear that iteration is basically just a special case of recursion. That seems a bit disingenuous, since iteration and general recursion are fundamentally equivalent. So you could say that "recursion is just a special case of iteration". Unless we're talking about specific iterations like iterating over a list, I guess.
  - danking00 12y ago
    I feel that it is a bit disingenuous to claim they are equivalent if the solution to maintaining a call stack is to explicitly maintain a stack structure. Iterating over lists, or integers in a range is pretty straightforward. Iterating over a tree? What does that even mean? I suppose we could take "iterate" to mean a catamorphism. Under that interpretation, structural recursion and "iteration" seem pretty equivalent. Just feels like quite an extension of what "iteration" usually refers to in a language like C.
    - Dewie 12y ago
      > I feel that it is a bit disingenuous to claim they are equivalent if the solution to maintaining a call stack is to explicitly maintain a stack structure. You're funny. Equivalent in a computational sense.
      - danking00 12y ago
        But by that standard ruby is python is C is assembler. Turing-completeness is a not very interesting standard.
    - agumonkey 12y ago
      Good point. I always felt that iteration was 1-dimensional, when recursion is more fractal / N-dimensional. ps: Also, a lot of programming is often conflated into 1-D. sed, grep, awk are mostly init ; iterate{ [PRED] FN }; exit
    - rdc12 12y ago
      But with TCO it is no longer needed to maintain a stack structure, so it would probably be a better stated as a tail-call recursive function is equivalent to iteration (assuming TCO)
- nostrademons 12y ago
  The two of them are exactly the same thing, but in recursion you have an implicit stack that maintains the state of each iteration. In iteration, the stack is either explicit or else condensed down into a few state variables (eg. if you're just keeping a sum, you don't need to store all the intermediate partial sums). Given that Python's philosophy is "explicit is better than implicit", it doesn't surprise me that he prefers iteration to recursion.
  - rpedroso 12y ago
    My issue was more about his opposition to recursion than the preference for iteration. That being said, this is one of the better explanations/arguments for why iterations are more 'Pythonic' that I've heard. Thanks!
    - Veedrac 12y ago
      Guido is not opposed to recursion per-se, just on basing programming around it. As he says, > TRE only addresses recursion that can easily be replaced by a loop and Python already has a very nice tool for that purpose. I have no doubt that he's fine with many other uses of recursion.
    - Veedrac 12y ago
      Guido is not opposed to recursion per-se, just on basing programming around it. As he says, > TRE only addresses recursion that can easily be replaced by a loop and Python already has a very nice tool for that purpose. I have no doubt that he's fine with many other uses of recursion.
    - beagle3 12y ago
      His opposition to recursion is well founded on the "principle of least surprise" that also underlies Python. Consider, e.g. def len1(list, acc=0): if not list: return acc else: return len1(list[1:],acc+1) def len2(list, acc=0): if not list: return acc else: return len2(list[1:],acc+1) + 0 First one is using only tail calls, and with proper TRE will run on any sized list. The second one will blow up the stack, despite being equivalent in almost every sense, especially in those senses (of "ease of proof") touted as the main reason to use tail recursion in the first place. And while this toy examples is easy to reason about, real world examples require more experience to understand - and Python was always intended at non CS people (and is hugely successful in that mission). Personally, I think the whole discussion is misguided. TRE should be explicit, not some kind of implicit optimization - that is, no TRE/TCO unless you explicity use e.g. a "chain" return keyword: def len3(list, acc=0): if not list: return acc else: chain len1(list[1:],acc+1) This way, a compiler could warn you about a syntax error should you rely on TRE and it is impossible or not available; Same thing could (and should) be done in scheme/lisp etc; It's easy to shoot yourself in the foot with macros and tailcalls in scheme. "chain" might not be the right keyword for this, but I haven't found a better one ("tail-return", "return-only", "continue-with" don't seem any better"; maybe reuse "pass"? e.g. "return pass len1(..)" or "pass return len1(...)"
- iamcurious 12y ago
  I have the same thoughts about list comprehension. The first time I read this quote I thought Guido was being ironic: "filter(P, S) is almost always written clearer as [x for x in S if P(x)]"
  - zem 12y ago
    the comprehension version is actually clearer, though. consider: in filter(P, S) 1. which is the predicate and which is the list? 2. is the list filtered in place (destructively) or is a new list emitted? 3. does filter mean "select when P" or "reject when P"? both are valid readings of the english word 'filter', with common non-scitech usage actually leaning more towards 'filter out' the list comprehension has none of those ambiguities.
    - jdpage 12y ago
      The C#/LINQ syntax for this is nice for this reason. It's S.Where(P), which makes it clear that the thing on the left is the thing being filtered, and that it's taking values x where P(x) is true. One could also make the argument that it also suggests that it's a non-destructive operation, but that might just be years of familiarity with SQL semantics talking.
    - actsasbuffoon 12y ago
      To be explicit, they're clearer _in Python_ due to the prevailing style and sensibilities of the community. It's possible to adopt a different set of guidelines that would eliminate the ambiguity. For instance, in Haskell the data you're working with is always the last argument. This stems from the way currying works, which makes life much more pleasant if the predicate comes first. Ruby also makes it clear, as there's special syntax for passing an anonymous function to a function call. For your second point, pure functional languages have complete clarity in this sort of thing. In Haskell it's obvious that you're returning a new list, and you couldn't mutate the original even if you wanted to. Ruby has a convention where ambiguously-mutating function names are suffixed with "!" to indicate that this version mutates. As for your third point, I can see where you're coming from, but filter is a venerable function name. There's a version of filter in most functionally inspired languages (and a version of map, reduce, etc.) and all the ones I've seen only keep elements that match the predicate. I suppose this may be why Ruby calls it "select" instead of "filter". There's also an inverted version called "reject". All of those also have an in-place variant (select!, reject!, map!). My point is that the ambiguity is not unavoidable. These things could easily be made clearer with different conventions/language-support. Other languages do quite well with these tools, so it obviously can be done in a clear way.
- cttet 12y ago
  "iteration is basically just a special case of recursion" for and while loop are just special case of usage of goto, but this does not necessary means that we need to use goto.
- easytiger 12y ago
  > but my CS professors made it clear that iteration is basically just a special case of recursion. More realistically iteration is a practically usable form of recursion to be used in stack based environments. Why do you think you have to optimise recursion into iteration before you can do anything non trivial with it
- nemoniac 12y ago
  Henry G. Baker made the point well, already in 1992. "The appearance of iterators [..] appears to be inversely related to the power of the language's intrinsic control structures." http://home.pipeline.com/~hbaker1/Iterator.html http://home.pipeline.com/~hbaker1/Iterator.html
deleted 12y ago
[deleted]
emmanueloga_ 12y ago
I gather than the author is being hyperbolic in order to emphasize his point ("is easier to reason about correctness with recursion"). But the reason recursion doesn't "suck" in python (an other languages without TCE), even with a small call stack, is that usually it is used to tackle problems with a divide-and-conquer strategy. Even if you are handling a massive amount of items, if your recursive calls splits them to handle in two or more parts until there's no more to handle, then it is very hard to deplete the call stack: log2 1_000_000_000_000_000 => 49.82892142331043 "Recursion and iteration are equally expressive: recursion can be replaced by iteration with an explicit stack, while iteration can be replaced with tail recursion. Which approach is preferable depends on the problem under consideration and the language used." [1] BTW, I sympathize with the author's thesis. I was trying to remember algorithms that are easier to reason about in their iterative form... but I can't remember any. Conversely, compare recursive vs iterative DFS [2]. 1: http://en.wikipedia.org/wiki/Recursion_(computer_science) http://en.wikipedia.org/wiki/Recursion_(computer_science) 2: http://en.wikipedia.org/wiki/Tree_traversal#Depth-first_2 http://en.wikipedia.org/wiki/Tree_traversal#Depth-first_2
- harperlee 12y ago
  But only if you can split parts more or less evenly; in other case, numbers go down quickly...
  - emmanueloga_ 12y ago
    True, in which case you can take some measures to avoid worst case inputs... I'm thinking randomization in quicksort, for instance.
    - harperlee 12y ago
      I always liked a lot that solution ("adding noise"), it seems very elegant.
Veedrac 12y ago
I don't get the argument about why loop invariants are any more complicated than tail calls. The link doesn't seem to clear it up (the same problem would occur with the direct translation to tail recursion).
Cyberis 12y ago
This was a great article. I've spent the last year filling in gaps in my own CS background including CL, Scheme, Racket, CISP, HtDP, etc. This is the first time I've seen good solid reasoning about Scheme using Assembly and it makes things really clear. I wish the author would have taken a little more time reasoning to the correctness of recursion using the y combinator. That's what he ended up with but it would have been helpful to break that down a bit more. Also, he mentioned that his next article in that series would have covered continuations (specifically call-with-current-continuation) and I REALLY would have enjoyed that since I find continuations a little hard to grasp.
- _callcc 12y ago
  I noticed the implicit y combinator as well... here's something I wrote in python some time ago to play with the idea: def tco(fn): """ tco --- Usage: Functions should have the following form: >>> recursive_fn = lambda fn: lambda x: fn(x+1) if x < 1000000 else x or >>> def recursive_fn(fn): ... def recursive_fn_cc(x): ... return fn(x+1) if x < 1000000 else x ... return recursive_fn_cc The notable difference is that called on their own, these functions aren't recursive at all. For example, >>> recursive_fn(lambda x: x)(1) 2 This is easier to see in the anonymous-style definition: >>> lambda fn: lambda x: fn(x+1) if condition(x) else x So we go from >>> def recur(x): ... ( function body modifying x ) ... if not base_case_reached: ... return recur(x) ... else: ... return x to >>> @tco ... def recur(fn): ... def _lambda(x): ... ( function body modifying x ) ... if not base_case_reached: ... return fn(x) ... else: ... return x ... return _lambda Then call as usual like >>> recur(x) Functions need to take this form as it exposes the fixed-point, namely the recursive `fn`. We need a fixed-point for the modified y-combinator. The modified combinator is the same, only where the evaluation step would normally take place, each evaluation is suspended or "thunked" by wrapping in a `lambda`. The thunks are then looped over and called in a while-loop, sidestepping the recursion depth issue. TODO: save the kwargs; eliminate the need to write the functions as continuations (i.e. `recur = lambda fn:lambda x: ...`) by creating new function objects from bytecode, replacing instances of `LOAD_GLOBAL` with `LOAD_DEREF`, may need to build temp function in order to create closure so `fn` can be added in `co_freevars`. See e.g. http://nbviewer.ipython.org/github/bravegnu/python-byte- code/blob/master/Python%20Byte%20Code%20Hacking.ipynb """ # y combinator with evaluation step wrapped in throwaway lambda # which suspends the evaluation step; # important to give `_t_c_o_` or some other highly unlikely keyword # argument so we can signal to the loop when stop evaluating; # want to be able to *return* a function as well, so checking for # '__call__' in directory is not enough. # Could also check that argcount is zero, and no other keywords exist; # if we're really nuts, generate a uuid or timestamp, then assign # it to `_t_c_o_` Y = (lambda f: (lambda x: x(x))( lambda y: f(lambda *args: lambda _t_c_o_=None: y(y)(*args))))(fn) def tco_cc(*args): _fn = Y(*args) while ('__call__' in dir(_fn)) and ('_t_c_o_' in _fn.__code__.co_varnames): _fn = _fn() return _fn return tco_cc
baldfat 12y ago
BASIC --> Assembly --->> Fortran -----> C+- ----> SQL Now I mostly use R and SQL
- sin7 12y ago
  R --> SQL. What's a good complement?
  - cttet 12y ago
    I actually felt that R functions and data structures are more straight forward to use than SQL commands. But sadly the data only exists in memory..
    - baldfat 12y ago
      The memory issue actually isn't "that bad." There are many different solutions and Spark and R are looking like amazing. Here is the announcement link: https://groups.google.com/forum/#!topic/apache-spark-user-mirror/tZs0dHeM6bk https://groups.google.com/forum/#!topic/apache-spark-user-mi...
    - bkeroack 12y ago
      In R you can do anything, including graphics. SQL is just, well, SQL.
tiffanyh 12y ago
This is also one of many reasons why people love Lua. Lua does proper tail recursion automatically. http://www.lua.org/pil/6.3.html http://www.lua.org/pil/6.3.html
peter_l_downs 12y ago
Great article. Fun to read about both Scheme and Assembly at the same time since I'm currently taking class on each (6.004, 6.945 @ MIT). It's great to get theory from both ends of the abstraction spectrum.
golergka 12y ago
> is easier to reason about correctness > my favorite programming language is x64 assembly So, author is _really_ used to reading asm and also smarter than an average developer (and yours truly) or doesn't really care about being able to reason that much. (But let me be clear, I'm not being sarcastic and wouldn't be surprised if he's really 10x genius.)
- andars 12y ago
  Just looked up his bio, and I think thats definitely a safe claim: http://en.m.wikipedia.org/wiki/David_Dalrymple_(computer_scientist) http://en.m.wikipedia.org/wiki/David_Dalrymple_(computer_sci...
- gwu78 12y ago
  Are you associating x64 assembly with "smart" or "10x genius"? How do you make this connection? Do you think that Python is more complex than assembly or vice versa? Are you suggesting that being able to program a computer using a subset of a relatively small, simple language requires more "smart" or "10x genius" than programming a computer using larger, more complex language? Please note I am not singling you out, nor am I criticizing your comment nor your opinion. I have seen a similar view of assembly expressed many, many times on this website and I truly am curious how the thought process behind it works.
  - golergka 12y ago
    In my experience, assembly is hard to read and reason about. Harder than C, much harder than python. It doesn't operate in terms in abstractions I, as a developer, am used to; it doesn't have easy syntax that correlates to logic flow (blocks and event statements). May be if I spent significant time with asm, I'll change my mind. Also, thanks for the disclaimer, although I don't mind if you criticise my opinion and/or comment. Even if you say that I'm just "too stupid for assembly", I wouldn't really mind.
sriku 12y ago
It would've been nice if mathematical induction were indicated as the foundation of recursion. You're not assuming "it does the right thing" and then proving "it does the right thing". What you're doing is that you're proving that "it does the right thing" by showing that "it does the right thing for N" if "it does the right thing for N-1", and your terminal condition is something like "it does the right thing for 0". Thus mathematical induction takes care of both correctness and termination.

127 points by sea6ear 12y ago

If your goal is to reason about correctness, recursion can be a useful tool. Assembly... is not the hammer I'd bust out for that particular reasoning task.

deleted 12y ago

[deleted]

rpedroso 12y ago

This article really got me in the mood to play around with Racket again. Incidentally, I find it hard to square with Guido's belief that recursion isn't the basis of all programming. Sure, Python has some powerful iterators, but my CS professors made it clear that iteration is basically just a special case of recursion. It might very well be the right decision for Python to prefer iteration, but to deny the role of recursion in computer science altogether seems misguided.

Dewie 12y ago
> , but my CS professors made it clear that iteration is basically just a special case of recursion. That seems a bit disingenuous, since iteration and general recursion are fundamentally equivalent. So you could say that "recursion is just a special case of iteration". Unless we're talking about specific iterations like iterating over a list, I guess.
- danking00 12y ago
  I feel that it is a bit disingenuous to claim they are equivalent if the solution to maintaining a call stack is to explicitly maintain a stack structure. Iterating over lists, or integers in a range is pretty straightforward. Iterating over a tree? What does that even mean? I suppose we could take "iterate" to mean a catamorphism. Under that interpretation, structural recursion and "iteration" seem pretty equivalent. Just feels like quite an extension of what "iteration" usually refers to in a language like C.
  - Dewie 12y ago
    > I feel that it is a bit disingenuous to claim they are equivalent if the solution to maintaining a call stack is to explicitly maintain a stack structure. You're funny. Equivalent in a computational sense.
    - danking00 12y ago
      But by that standard ruby is python is C is assembler. Turing-completeness is a not very interesting standard.
  - agumonkey 12y ago
    Good point. I always felt that iteration was 1-dimensional, when recursion is more fractal / N-dimensional. ps: Also, a lot of programming is often conflated into 1-D. sed, grep, awk are mostly init ; iterate{ [PRED] FN }; exit
  - rdc12 12y ago
    But with TCO it is no longer needed to maintain a stack structure, so it would probably be a better stated as a tail-call recursive function is equivalent to iteration (assuming TCO)
nostrademons 12y ago
The two of them are exactly the same thing, but in recursion you have an implicit stack that maintains the state of each iteration. In iteration, the stack is either explicit or else condensed down into a few state variables (eg. if you're just keeping a sum, you don't need to store all the intermediate partial sums). Given that Python's philosophy is "explicit is better than implicit", it doesn't surprise me that he prefers iteration to recursion.
- rpedroso 12y ago
  My issue was more about his opposition to recursion than the preference for iteration. That being said, this is one of the better explanations/arguments for why iterations are more 'Pythonic' that I've heard. Thanks!
  - Veedrac 12y ago
    Guido is not opposed to recursion per-se, just on basing programming around it. As he says, > TRE only addresses recursion that can easily be replaced by a loop and Python already has a very nice tool for that purpose. I have no doubt that he's fine with many other uses of recursion.
  - Veedrac 12y ago
    Guido is not opposed to recursion per-se, just on basing programming around it. As he says, > TRE only addresses recursion that can easily be replaced by a loop and Python already has a very nice tool for that purpose. I have no doubt that he's fine with many other uses of recursion.
  - beagle3 12y ago
    His opposition to recursion is well founded on the "principle of least surprise" that also underlies Python. Consider, e.g. def len1(list, acc=0): if not list: return acc else: return len1(list[1:],acc+1) def len2(list, acc=0): if not list: return acc else: return len2(list[1:],acc+1) + 0 First one is using only tail calls, and with proper TRE will run on any sized list. The second one will blow up the stack, despite being equivalent in almost every sense, especially in those senses (of "ease of proof") touted as the main reason to use tail recursion in the first place. And while this toy examples is easy to reason about, real world examples require more experience to understand - and Python was always intended at non CS people (and is hugely successful in that mission). Personally, I think the whole discussion is misguided. TRE should be explicit, not some kind of implicit optimization - that is, no TRE/TCO unless you explicity use e.g. a "chain" return keyword: def len3(list, acc=0): if not list: return acc else: chain len1(list[1:],acc+1) This way, a compiler could warn you about a syntax error should you rely on TRE and it is impossible or not available; Same thing could (and should) be done in scheme/lisp etc; It's easy to shoot yourself in the foot with macros and tailcalls in scheme. "chain" might not be the right keyword for this, but I haven't found a better one ("tail-return", "return-only", "continue-with" don't seem any better"; maybe reuse "pass"? e.g. "return pass len1(..)" or "pass return len1(...)"
iamcurious 12y ago
I have the same thoughts about list comprehension. The first time I read this quote I thought Guido was being ironic: "filter(P, S) is almost always written clearer as [x for x in S if P(x)]"
- zem 12y ago
  the comprehension version is actually clearer, though. consider: in filter(P, S) 1. which is the predicate and which is the list? 2. is the list filtered in place (destructively) or is a new list emitted? 3. does filter mean "select when P" or "reject when P"? both are valid readings of the english word 'filter', with common non-scitech usage actually leaning more towards 'filter out' the list comprehension has none of those ambiguities.
  - jdpage 12y ago
    The C#/LINQ syntax for this is nice for this reason. It's S.Where(P), which makes it clear that the thing on the left is the thing being filtered, and that it's taking values x where P(x) is true. One could also make the argument that it also suggests that it's a non-destructive operation, but that might just be years of familiarity with SQL semantics talking.
  - actsasbuffoon 12y ago
    To be explicit, they're clearer _in Python_ due to the prevailing style and sensibilities of the community. It's possible to adopt a different set of guidelines that would eliminate the ambiguity. For instance, in Haskell the data you're working with is always the last argument. This stems from the way currying works, which makes life much more pleasant if the predicate comes first. Ruby also makes it clear, as there's special syntax for passing an anonymous function to a function call. For your second point, pure functional languages have complete clarity in this sort of thing. In Haskell it's obvious that you're returning a new list, and you couldn't mutate the original even if you wanted to. Ruby has a convention where ambiguously-mutating function names are suffixed with "!" to indicate that this version mutates. As for your third point, I can see where you're coming from, but filter is a venerable function name. There's a version of filter in most functionally inspired languages (and a version of map, reduce, etc.) and all the ones I've seen only keep elements that match the predicate. I suppose this may be why Ruby calls it "select" instead of "filter". There's also an inverted version called "reject". All of those also have an in-place variant (select!, reject!, map!). My point is that the ambiguity is not unavoidable. These things could easily be made clearer with different conventions/language-support. Other languages do quite well with these tools, so it obviously can be done in a clear way.
cttet 12y ago
"iteration is basically just a special case of recursion" for and while loop are just special case of usage of goto, but this does not necessary means that we need to use goto.
easytiger 12y ago
> but my CS professors made it clear that iteration is basically just a special case of recursion. More realistically iteration is a practically usable form of recursion to be used in stack based environments. Why do you think you have to optimise recursion into iteration before you can do anything non trivial with it
nemoniac 12y ago
Henry G. Baker made the point well, already in 1992. "The appearance of iterators [..] appears to be inversely related to the power of the language's intrinsic control structures." http://home.pipeline.com/~hbaker1/Iterator.html http://home.pipeline.com/~hbaker1/Iterator.html

deleted 12y ago

[deleted]

emmanueloga_ 12y ago

I gather than the author is being hyperbolic in order to emphasize his point ("is easier to reason about correctness with recursion"). But the reason recursion doesn't "suck" in python (an other languages without TCE), even with a small call stack, is that usually it is used to tackle problems with a divide-and-conquer strategy. Even if you are handling a massive amount of items, if your recursive calls splits them to handle in two or more parts until there's no more to handle, then it is very hard to deplete the call stack: log2 1_000_000_000_000_000 => 49.82892142331043 "Recursion and iteration are equally expressive: recursion can be replaced by iteration with an explicit stack, while iteration can be replaced with tail recursion. Which approach is preferable depends on the problem under consideration and the language used." [1] BTW, I sympathize with the author's thesis. I was trying to remember algorithms that are easier to reason about in their iterative form... but I can't remember any. Conversely, compare recursive vs iterative DFS [2]. 1: http://en.wikipedia.org/wiki/Recursion_(computer_science) http://en.wikipedia.org/wiki/Recursion_(computer_science) 2: http://en.wikipedia.org/wiki/Tree_traversal#Depth-first_2 http://en.wikipedia.org/wiki/Tree_traversal#Depth-first_2

harperlee 12y ago
But only if you can split parts more or less evenly; in other case, numbers go down quickly...
- emmanueloga_ 12y ago
  True, in which case you can take some measures to avoid worst case inputs... I'm thinking randomization in quicksort, for instance.
  - harperlee 12y ago
    I always liked a lot that solution ("adding noise"), it seems very elegant.

Veedrac 12y ago

I don't get the argument about why loop invariants are any more complicated than tail calls. The link doesn't seem to clear it up (the same problem would occur with the direct translation to tail recursion).

Cyberis 12y ago

This was a great article. I've spent the last year filling in gaps in my own CS background including CL, Scheme, Racket, CISP, HtDP, etc. This is the first time I've seen good solid reasoning about Scheme using Assembly and it makes things really clear. I wish the author would have taken a little more time reasoning to the correctness of recursion using the y combinator. That's what he ended up with but it would have been helpful to break that down a bit more. Also, he mentioned that his next article in that series would have covered continuations (specifically call-with-current-continuation) and I REALLY would have enjoyed that since I find continuations a little hard to grasp.

_callcc 12y ago
I noticed the implicit y combinator as well... here's something I wrote in python some time ago to play with the idea: def tco(fn): """ tco --- Usage: Functions should have the following form: >>> recursive_fn = lambda fn: lambda x: fn(x+1) if x < 1000000 else x or >>> def recursive_fn(fn): ... def recursive_fn_cc(x): ... return fn(x+1) if x < 1000000 else x ... return recursive_fn_cc The notable difference is that called on their own, these functions aren't recursive at all. For example, >>> recursive_fn(lambda x: x)(1) 2 This is easier to see in the anonymous-style definition: >>> lambda fn: lambda x: fn(x+1) if condition(x) else x So we go from >>> def recur(x): ... ( function body modifying x ) ... if not base_case_reached: ... return recur(x) ... else: ... return x to >>> @tco ... def recur(fn): ... def _lambda(x): ... ( function body modifying x ) ... if not base_case_reached: ... return fn(x) ... else: ... return x ... return _lambda Then call as usual like >>> recur(x) Functions need to take this form as it exposes the fixed-point, namely the recursive `fn`. We need a fixed-point for the modified y-combinator. The modified combinator is the same, only where the evaluation step would normally take place, each evaluation is suspended or "thunked" by wrapping in a `lambda`. The thunks are then looped over and called in a while-loop, sidestepping the recursion depth issue. TODO: save the kwargs; eliminate the need to write the functions as continuations (i.e. `recur = lambda fn:lambda x: ...`) by creating new function objects from bytecode, replacing instances of `LOAD_GLOBAL` with `LOAD_DEREF`, may need to build temp function in order to create closure so `fn` can be added in `co_freevars`. See e.g. http://nbviewer.ipython.org/github/bravegnu/python-byte- code/blob/master/Python%20Byte%20Code%20Hacking.ipynb """ # y combinator with evaluation step wrapped in throwaway lambda # which suspends the evaluation step; # important to give `_t_c_o_` or some other highly unlikely keyword # argument so we can signal to the loop when stop evaluating; # want to be able to *return* a function as well, so checking for # '__call__' in directory is not enough. # Could also check that argcount is zero, and no other keywords exist; # if we're really nuts, generate a uuid or timestamp, then assign # it to `_t_c_o_` Y = (lambda f: (lambda x: x(x))( lambda y: f(lambda *args: lambda _t_c_o_=None: y(y)(*args))))(fn) def tco_cc(*args): _fn = Y(*args) while ('__call__' in dir(_fn)) and ('_t_c_o_' in _fn.__code__.co_varnames): _fn = _fn() return _fn return tco_cc

baldfat 12y ago

BASIC --> Assembly --->> Fortran -----> C+- ----> SQL Now I mostly use R and SQL

sin7 12y ago
R --> SQL. What's a good complement?
- cttet 12y ago
  I actually felt that R functions and data structures are more straight forward to use than SQL commands. But sadly the data only exists in memory..
  - baldfat 12y ago
    The memory issue actually isn't "that bad." There are many different solutions and Spark and R are looking like amazing. Here is the announcement link: https://groups.google.com/forum/#!topic/apache-spark-user-mirror/tZs0dHeM6bk https://groups.google.com/forum/#!topic/apache-spark-user-mi...
  - bkeroack 12y ago
    In R you can do anything, including graphics. SQL is just, well, SQL.

tiffanyh 12y ago

This is also one of many reasons why people love Lua. Lua does proper tail recursion automatically. http://www.lua.org/pil/6.3.html http://www.lua.org/pil/6.3.html

peter_l_downs 12y ago

Great article. Fun to read about both Scheme and Assembly at the same time since I'm currently taking class on each (6.004, 6.945 @ MIT). It's great to get theory from both ends of the abstraction spectrum.

golergka 12y ago

> is easier to reason about correctness > my favorite programming language is x64 assembly So, author is _really_ used to reading asm and also smarter than an average developer (and yours truly) or doesn't really care about being able to reason that much. (But let me be clear, I'm not being sarcastic and wouldn't be surprised if he's really 10x genius.)

andars 12y ago
Just looked up his bio, and I think thats definitely a safe claim: http://en.m.wikipedia.org/wiki/David_Dalrymple_(computer_scientist) http://en.m.wikipedia.org/wiki/David_Dalrymple_(computer_sci...
gwu78 12y ago
Are you associating x64 assembly with "smart" or "10x genius"? How do you make this connection? Do you think that Python is more complex than assembly or vice versa? Are you suggesting that being able to program a computer using a subset of a relatively small, simple language requires more "smart" or "10x genius" than programming a computer using larger, more complex language? Please note I am not singling you out, nor am I criticizing your comment nor your opinion. I have seen a similar view of assembly expressed many, many times on this website and I truly am curious how the thought process behind it works.
- golergka 12y ago
  In my experience, assembly is hard to read and reason about. Harder than C, much harder than python. It doesn't operate in terms in abstractions I, as a developer, am used to; it doesn't have easy syntax that correlates to logic flow (blocks and event statements). May be if I spent significant time with asm, I'll change my mind. Also, thanks for the disclaimer, although I don't mind if you criticise my opinion and/or comment. Even if you say that I'm just "too stupid for assembly", I wouldn't really mind.

sriku 12y ago

It would've been nice if mathematical induction were indicated as the foundation of recursion. You're not assuming "it does the right thing" and then proving "it does the right thing". What you're doing is that you're proving that "it does the right thing" by showing that "it does the right thing for N" if "it does the right thing for N-1", and your terminal condition is something like "it does the right thing for 0". Thus mathematical induction takes care of both correctness and termination.