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."
---- 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
aslo available in PDF format
But since the Stackless stuff brings real performance improvements, microthreads, and nifty new libraries, it is likely to go into the main trunk at maybe 2.1 or probably 2.2.
I believe posters are recognized by their sig. So I made one.
<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>
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.
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.