Python to Scheme to Assembly (2014)

https://davidad.github.io/blog/2014/02/28/python-to-scheme-to-assembly-1/

by sea6ear • 11 years ago

127 60 11 years ago

davidad.github.io

rpedroso2• 11 years 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.

iamcurious• 11 years 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• 11 years 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.

adregan• 11 years ago

Python 3 really pushes you towards list comprehensions as you have to wrap your filter in a list(). I ended up just going with the flow. However, nesting list comprehensions can get me into a place where I forget what it is I'm doing.

nonissue• 11 years ago

The latter example certainly is clearer.

Dewie2• 11 years 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.

danking002• 11 years 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.

nostrademons3• 11 years 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.

rpedroso2• 11 years 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!

easytiger• 11 years 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

cttet2• 11 years 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.

nemoniac• 11 years 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

hawkice• 11 years 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.

Cyberis• 11 years 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.

_callcc4• 11 years 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

_callcc4• 11 years ago

...re-reading this I realize the comments are a bit of a mess... basically, it's a decorator that uses the y-combinator to get around the recursion depth problem by "suspending" the evaluation at each step (I'm sure there's some technical term for this... thunking?), then later performing each evaluation inside a while loop. I tested it a bunch and it seemed to work on anything.

I recall being convinced keyword arguments could be made to work, and also that some byte code hacking would get around the "non-user friendly" bit where recursive functions need to be written as "functionals" in order to expose the recursive function itself as a fixed point.

baldfat2• 11 years ago

BASIC --> Assembly --->> Fortran -----> C+- ----> SQL

Now I mostly use R and SQL

sin7• 11 years ago

R --> SQL.

What's a good complement?

cttet2• 11 years 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..

tiffanyh• 11 years 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

emmanueloga_2• 11 years 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)

2: http://en.wikipedia.org/wiki/Tree_traversal#Depth-first_2

harperlee2• 11 years ago

But only if you can split parts more or less evenly; in other case, numbers go down quickly...

emmanueloga_2• 11 years ago

True, in which case you can take some measures to avoid worst case inputs... I'm thinking randomization in quicksort, for instance.

Veedrac2• 11 years 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).

peter_l_downs• 11 years 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.

golergka2• 11 years 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• 11 years ago

Just looked up his bio, and I think thats definitely a safe claim: http://en.m.wikipedia.org/wiki/David_Dalrymple_(computer_sci...

gwu78• 11 years 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.

golergka2• 11 years 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• 11 years 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.

Python to Scheme to Assembly (2014)

Related Stories