Slashdot Mirror
Interviews With The Creators of Vyper and Stackless
Frank writes: "What most programmers probably think of when they talk about 'Python' is the specific implementation sometimes called 'CPython' (because it is implemented in C). However, Python as a language specification has been implemented several times in parallel with the evolution of Guido van Rossum's reference implementation. This article consists of annotated interviews with the creators of two of the non-standard Pythons -- Stackless and Vyper." A pair of interviews to make your head spin with talk of Literate Programming and the odd but neat concept of "continuations."
I feel pretty much the same way. Ruby seems to be a step forward compared to Python in some respects, and a step backward in others. Overall it's a wash, and since Python already works very well for me I don't think I'd gain much by learning Ruby. That doesn't mean, though, that I would discourage anyone who doesn't already have a scripting language under their belt from choosing Ruby over Python. From what I can tell, they would learn better habits from Ruby than from Perl or Tcl.
Slashdot - News for Herds. Stuff that Splatters.
---- Opps... COMPLETE COMMENT BELOW
When you have programmed using a functional language (Scheme for me) and used this way
of working it takes a bit to get back to Java/C!
The basic idea for those of you who are confused is to use recursion and get away with not using the stack for the calls. How you might ask... well first of all its easy when you are using a language like Scheme/Lisp which treats functions as first class data members! There is no difference b/w (well almost none) b/w data types and functions, each can be passed into a function and returned!
SO Normally when you make a recursive call you are just pushing down your current data into the stack and when you reach the base case you go back up the stack!
In case of Continuation Passing Style the idea is really very very neat! You basically make a recursive call and pass a function to that will be able to compute the answer with the data it needs! There is no stack. For example (Factorial of course)
(define fac
(lambda (n)
(if (<= n 0) 1
(* n (fac (- n 1)))))
Note you had to keep the info of where you were so you can recurse back doing the multiplications!
This data went into the stack!!! Now if you want to do this without stacks you can use a method that you build each time you go through the loop and so you build the answer on your way!!!
(define fact-cps
(lambda (n fun)
(if (\>= n 1)
(fun 1)
(fact-cps
(+ n -1)
(lambda(z)(fun (* n z))))))
This way of course you just build a formulae that will give you the answer! No stack.
There is a formal algo that you can take any recursive funtion and make it into CPS which is pretty cool till your professor thinks that a scheme interpreter in written in scheme should use CPS!! BUT i digress!! So you can seee that this is really a very powerful idea! It introduces a lot of neat tricks you can do! One of which is hte Y-Combinator... but taht I cant talk about cause i sit in amazement for sometime when i see it:)
Hmmm these are things i think you should sometime learn if you are in the computer world cause most of the time we stick with the real programming issues and dont see some of the cooler things! So this wont make you much money but you will see how sexy some of these ideas really are!! SCHEME RULZ!
Non-Deterministic Finite Automata
I am the author of the interviews in question here. As pointed to in the first interview, I also did interviews about J(P)ython and Python for .NET developers. Those have not made it to IBM developerWorks yet (they are a bit slow with publication schedules), but it all can be found at my own website already. (As well, certain manglings by IBM editors are not present in my home versions [says the spoiled artist :-)])
Take a look at:
http://gnosis.cx/publish/tech_index.html
Buy Text Processing in Python
A Python compiler written in Python? It could use a GCC backend to compile C code emitted by the Python compiler.
The stage 1 compiler would be a simple distribution of Python source files, and it would be run with the regular CPython installation. That would be used to compile itself into a binary Python compiler.
Why not? Develop Python programs with CPython. When you're done, compile it for speed.
If tits were wings it'd be flying around.
But, since nobody uses Perl, due to its atrocious language design, this doesn't matter. :-)
Seriously, Perl the language has grown a lot since it was first released, and you can find yourself tripping (quite literally) over its roots. But an interesting part of Perl's design is that it's author, Larry Wall, has an academic background in Linguistics rather than CS, and had a pressing need to get something like perl working rather than a prime requirement that everything be perfect at the start.
But today's perl has lexical scoping and closures and many of the nice things people wish other scripting languages had (or had had sooner). Now that Perl6 is really going to happen (since Damian Conway is motivated to get all his language features implemented before the magic spell wears off :-)), I wouldn't be surprised to see a lot of the dubious stuff finally go away.
And there will be much rejoicing. But the claim that Perl's non-CS roots have somehow doomed it to obscurity or uselessness really seems quite far-fetched.
Babar
what exactly does the author of vyper mean when he says that python doesn't support lexical scoping properly? I've done a bit of work with python and always assumed that the scope of variables and classes was the same as for C or C++. Is he saying that variables don't pass out of scope at the end of a block? Or that it has dynamic scoping and that variables pass into scope depending on how the function was called? I guess I haven't delved deeply enough into python to be able to see what he's talking about.
In Soviet Russia, hot grits put YOU down THEIR pants.
And I suppose this is in contrast to the Perl weenies who come into Python articles to bash Python, based on their many many hours spent studying the pros and cons of each? Yeah right. Most Perl folks spend about three minutes looking at Python, notice maybe one thing about the language itself - usually the indentation thing - but mostly just notice that it doesn't look like Perl, and then spend the rest of their lives making the illogical claim that Perl must be better because more people use it.
Python has its weaknesses, which I have gone out of my way to describe in my last post on the subject (a copy of which pretty easy for any non-moron to find on my website), but overall it's a fine language. As with Ruby, and Pike, and several other languages, on technical merit it deserves at least equal consideration to Perl.
Slashdot - News for Herds. Stuff that Splatters.
IIRC, Guy Steele (one of the designers of the Java spec) wrote his thesis on converting Scheme code into continuation-passing style, then compiling that. This gives you tail-recursion (briefly, writing code in a recursive style, but making it behave iteratively) for free!
Continuations are really nice for *formally* defining how languages should behave under forking (with data dependencies among threads), and other wacky control features that may or may not be useful. I've only seen this stuff done rigorously for Lisp-like languages, in the lambda calculus. I doubt it's used at all for imperative languages.
Might the main CPython branch adopt these innovations? Vyper's scoping and functional features, and Stackless' continuations? The article says that Stackless isn't a huge fork--could it get brought back into the trunk?
Just something to ponder.
---
Zardoz has spoken!
Oper on the Nightstar
uhm.... Someone please explain this one to me.
Any sufficiently advanced civilization is indistinguishable from Gods.
aslo available in PDF format
Ruby really is a great language, and I suspect that by time Perl6 is done, it will resemble Ruby in many ways.
Moving to Ruby now will probably give you everything Perl6 is promising, without the three year wait.
I'll believe it when I see it. There are alot of system specifics that would need to be taken into account; for example, I might have a file-descriptior stored in a variable. That file descriptor is not going to survive a move to another machine.
Likewise, any C-land objects that are pointed to by the state are going to be hard to move. It seems to be the sort of thing you really want to implement at the VM level using Distributed Shared Memory, not at the language level.
But, I expect that anyone smart enough to implement stackless wouldn't go around saying these sorts of things if he didn't know something I obviously don't.
One way to understand continuations is to look at how it's implemented. Check out the source code to one implementation of scheme, SCM. In effect it doesn't interpret continuations in scheme but implements continuations in C and then implements the scheme continuations using the C ones. The actual code works by deviously using setjmp, longjmp and messing with the stack but it's not that hard to understand (although it's a bit messy on architectures that have a non-contiguous stack). The last time I looked at this code was about 5 years ago so apologies if it's been reimplemented differently since then. Many years ago I used a similar implementation of continuations in C myself in order to implement a version of the very complex recursive pattern matching that Mathematica supports - in effect by using coroutines to generate streams of possible matches. At the time most people thought this was a gross solution to the problem but now I see that continuations are considered to be respectable I shall have to start using the method again.
--
-- SIGFPE
<SCRIPT> .html and load in your browser.
s ion.html
;)
// See explanation at end.
// This code works and will run in a web browser -
// just save as
// Will work in Mozilla or IE.
// sample calls
printFacVal( "fact", 12, fact(12) );
printFacVal( "factail", 12, factail(12, 1) );
printFacVal( "factfn", 12, factfn(12, function (x) { return x; } ) );
// write the function name, value of n and result to the browser window
function printFacVal( fname, n, x )
{
document.write( fname + "(" + n + ") = " + x + "<P>" );
}
// Plain ol' recursive implementation of factorial
function fact( n )
{
if ( n == 0 )
return 1;
else
return n * fact( n - 1 );
}
// Version which supports tail recursion: final value is
// known when recurse bottom is reached, so stack can be
// optimized away in a language which supports this.
// See http://www.cs.utexas.edu/users/novak/cs30770.html -
// or for fun, http://info.astrian.net/jargon/terms/t/tail_recur
function factail( n, total )
{
if ( n == 0 )
return total;
else
return factail( n - 1, n * total );
}
/*
factfn()
Version which builds a function to calculate factorial(n)
This only really makes sense in a functional language.
Although syntactically it can be mapped directly onto its
functional language equivalent, and although it does
actually work in Javascript, CS students around the
country are recoiling in amazement tinged with horror
as they read this.
*/
function factfn( n, fn )
{
if ( n == 0 )
return fn( 1 );
else
return factfn( n - 1, function ( p ) { return fn( n * p ) } );
}
/*
factfn() would be rather hard to implement in a language like Pascal or C,
except if you were using one of those languages to build a functional language
(in which case, that would be easy!
As factfn() descends through its recursive calls, the anonymous function which
is passed as the second parameter becomes a function built specifically to
calculate the factorial of the specified n, i.e. the final value of fn(1)
equals the factorial of n.
However, since current implementations of Javascript don't support tail
recursion, factfn() relies on a stack to achieve its recursion, and is
thus bounded by stack size in what it can compute (actually, in this case,
the factorial calculation is limited numerically: factorial(170) or so
will overflow a typical Javascript implementation, long before the stack
fills up.) A tail-recursion implementation doesn't need a stack to recurse,
thus is not limited by stack depth.
Another difference between this and a tail-recursive implementation is that
when fn(1) is finally evaluated, in the Javascript implementation, it will
call itself recursively, again using the stack. At each level, the value
of n is taken from the function's context at the appropriate level (which
may be implemented on the stack).
A fully tail-recursive cps implementation would do all this without the
need for a stack. The final evaluation of fn(1) would simply evaluate the
final result of n * (n-1) * (n-2)... and get the right answer.
*/
</SCRIPT>
A lot of continuation-based research was done in the Standard ML project at AT&T and Princeton in the late 80's/early 90's. Andrew Appel (who wrote the native-code generator for this particular SML compiler) has a book, Compiling with Continuations, which goes into this stuff. Continuation-passing is odd at first but pretty easy to code up in a functional language.
And people claim Perl is hard to read!
:-)
Exactly the same methods that work for human languages, human biology and capitalism. A central plan works well when you've got a closed, well-defined problem to solve: "reimplement UNIX" or "make a fast C compiler". The trouble with planned solutions to open-ended problems is that sooner or later, the planner will miss a trick which Monte Carlo methods would have hit on, which is why evolution wins in the long run.
perl -e 'fork||print for split//,"hahahaha"'
The last expression in my third function, factfn():
The explanation h ere is more explicit, IMO:
The example on that page is the canonical example of factorial in cps style in Lisp-like languages:
(define fact-k
(lambda (n k)
(if (zero? n) (k 1)
(fact-k (1- n) (lambda (v) (k (* n v)))))))
This program maps syntactically to my Javascript example, exactly: their n is my n, their k is my fn, and their v is my p.
To further demonstrate the apparent "continuation-ness" of the Javascript implementation, if you change the line in factfn() which reads "return fn(1)" to simply "return fn", factfn() will now return an unevaluated function to its caller. That function encapsulates the factorial of the value of n specified by the caller. You can then evaluate it, after the factfn() function has returned. The calling code would then look like this:
aFacFn = factfn( 5, function (x) { return x; } );
document.write( aFacFn( 1 ) );
When aFacFn(1) executes, it returns 120. It happens to arrive at this result by recursion. Nevertheless, the values of n which it uses internally come from function contexts (what that Python page is referring to as "frames") which are not (or no longer) on the traditional call stack. Since functions are first-class objects in Javascript, it pretty much has to support the concept of a frame detached from the call stack, and it does.
Having defended my position, I will say that no-one should seriously try to learn about these things using Javascript, or Python for that matter. When learning, it's much easier to work with these concepts in the context in which they're most effective, i.e. a true functional language. I picked Javascript for these examples because of its 1st-class function support and the fact that just about anyone reading this can run the code in their browser.
In my other response to you, I forgot to mention that there's a potentially important difference between tail recursion and iteration: ideally, tail recursion actually simply allows optimal use of the stack, and doesn't necessarily involve recursion (or iteration) at all. It's just that the context in which it's most discussed is that of recursion & iteration. However, the tail call at the end of a function does not need to recursively call the current function: it could call something else, and the result would simply be that the stack depth is not increased and when the called function returns, it returns directly to the original caller rather than popping through a stack of intermediate calls. Think of it like a GOTO written in a function calling style with parameters.
And how, exactly, would you make it easier? In particular, how would you make it easier without sacrificing the full power and flexibility of extensions?
I think the real problem is with terminology. It's not a matter of "inner loops" vs. "outer loops". It's about performance-critical parts vs. non-performance-critical parts. For most scripts and tools and anything else short of full-blown industrial strength applications, coding any part of your Python application as an extension module is just stupid. In those cases where it might make sense, it's really not that hard to apply standard software-engineering approaches to the design of one or more extension modules which neatly encapsulate the performance-critical parts of your app behind a fairly simple interface. I've done it several times, and been quite satisfied with the results...and it's not because I'm particularly easy to satisfy. ;-)
That's a pretty tall order. C/C++ interfaces aren't exactly self-describing, even as far as number of arguments in many cases, let alone type and meaning etc. There's actually a Python extension module - forgot the name - that lets you do pretty much the sort of direct invocation you're talking about, putting all of the burden on the programmer to make sure they're passing the right number of arguments etc. It turns out not to be all that useful, though, because it really only provides part of a real extension interface - the "interpreter calls X" part. A full extension interface also allows X to call the interpreter, or X to interpret or manipulate or even create complex structures - objects, lists, dictionaries, aggregates of same - comprehensible to the interpreted code, and so on. Without all of that, which is not available in the model you propose, what you have is a crippled extension interface lacking many benefits inherent in the real thing.
This sounds pretty much like what "freeze" does, or perhaps a minimally-enhanced version of it. Could you explain what exactly you want that goes beyond that?
BTW, keep in mind that creation of a single monolithic executable is not always the goal. Many ways of doing what you describe would preclude component models or interactive use. It's just one more example of how Python represents a certain set of tradeoffs. It's not perfect for every usage, but the omission of certain features you might want might well be a conscious decision based on the fact that their inclusion might have precluded some other feature that is more generally useful.
Slashdot - News for Herds. Stuff that Splatters.
As for improving module building and other things, I hope to make significant steps in that area for 2.1.
The online docs are also good.
In short, I think I agree with another poster's comment that instead of waiting for Perl6, you should look at Ruby instead. Not as pleasant to read Ruby code as Python code, though, and its syntax isn't as clean, so it won't be replacing Python for me just yet.
Ok, that's distributed processing.
However, the implementor in the articl discusses "pickling" program state, which allows it to be stored to disk, for example. This implies that it is not using a secondary server to manage state, but somehow hoping to store all of it. My comment was basically that this seemed impossible, because some state is stored in kernel space and only accessed by a handle.
But I can see how my comment about DSM was misleading. Sorry about that.
Both Vyper and Stackless Python offer some extremely cool features that I would definitely like to see in CPython.
Python 2.0 saw the introduction of assignment-operators ( +=, -=, *=, etc.), and list comprehensions (a quick steal from Haskell). Both of these are cool, but there are still nagging usability problems:
The fact that lambdas are fundamentally broken because you cannot do anything really powerful with them. Adding lexical scoping to python would alleviate this problem, and let me do nifty 'map' and 'filter' stuff in python a LOT easier.
And continuations are damned powerful. Right now you can hack up a semblance of continuations using the fact that you can divorce instance-methods from their instances, and use them as normal methods, which means methods can have a static state, and use a 'if/elif/else' statement block to choose a continuation.. but hat is a horrible hack.
Python is an excellent language, but the cool thing about it is that there are so many obvious things that need to be fixed, it can only get better
-Laxitive
Wrong. John Ousterhout, creator of Tcl, is a CS professor. Guido van Rossum, creator of Python, is well versed in language design. You may not like their decisions - I personally detest Tcl - but I would bet either of them is about 10x more qualified to design a language than anyone here.
Larry Wall, on the other hand, has no discernible background or ability in language design, and it shows in Perl.
Slashdot - News for Herds. Stuff that Splatters.
Stackless Python is supposed to let you wrap up the program and its state, and send it to a friend who can continue where you left of. Sounds alot like process migration in a system like MOSIX, to me. Could Stackless Python be set up as a daemon and auto-migrate based on load?
-_Quinn
Reality Maintenance Group, Silver City Construction Co., Ltd.
When you have programmed using a functional language (Scheme for me) and used this way
of working it takes a bit to get back to Java/C!
The basic idea for those of you who are confused is to use recursion and get away with not using the stack for the calls. How you might ask... well first of all its easy when you are using a language like Scheme/Lisp which treats functions as first class data members! There is no difference b/w (well almost none) b/w data types and functions, each can be passed into a function and returned!
SO Normally when you make a recursive call you are just pushing down your current data into the stack and when you reach the base case you go back up the stack!
In case of Continuation Passing Style the idea is really very very neat! You basically make a recursive call and pass a function to that will be able to compute the answer with the data it needs! There is no stack. For example (Factorial of course)
(define fac
(lambda (n)
(if (
Note you had to keep the info of where you were so you can recurse back doing the multiplications!
This data went into the stack!!! Now if you want to do this without stacks you can use a method that you build each time you go through the loop and so you build the answer on your way!!!
Non-Deterministic Finite Automata