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
Yes, Perl is an extremely popular language. This is because it solves a problem for a lot of people. You can have all of this dispite the fact that its design leaves something to be desired.
Perl is not the end of language evolution and certainly Larry Wall has never claimed that it was. You really shouldn't have that much difficulty accepting this.
Thanks
Bruce
Bruce Perens.
sorry, write-only languages aren't where it's at. grow up, logo boy.
Go Kathryn Thurber!
Try browsing the new book from Addison Wesley, it is much better than the translated docs.
Don't let the perl-like variables fool you, they are merely a convenience. If you wish, you can do things such as get a regular expression object and access its features instead of doing things the perl way. In fact the perl way is simply accessing features of the current object...
Come on folks, I know there's an anti-Java contingent out there but when you discuss non-C implementations of Python you really shouldn't omit JPython.
Some key differences between JPython and CPython:
Syntax
- JPython has a different interpretation of floating point
literals. CPython doesn't allow 001.1 CPython should be
fixed.
- JPython supports continue in a try clause. CPython
should be fixed - but don't hold your breath.
Standard types, functions and behaviorLa via sola al paradiso incommincia nel inferno
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.
We all love GvR, but with that same reasoning, the language would not have threads. I'm actually hoping the digital creation's guys ruffle his feathers a bit and get him more proactive in removing some of the barriers to making python a better software engineering tool. sure it is a great glue, but this language has the capability to morph into much more.
jim
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
Stackless Python is not about distributed processing at all.
Stackless Python only means that the state info for the current thread of execution is not saved on the C stack as you go along, but maintained elsewhere. The best selling point (to us here at CCP at least) is the microthread support this allows, rather than create an operating system thread (and a seperate C stack) for every seperate task, we just allocate tiny Python microthreads, with little or no overhead.
i'm not so sure you are using continuations in your example.
e r.htm
from what i understand, a continuation is a semantic element that allows you to save a place in the future execution of a block of code. the continuation can then be called (with local vars as parameters) at a later point in time.
http://www.tismer.com/research/stackless/spcpap
jim
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.
Well, I'd say that ML is mostly a functional language. You can write code in an imperative style using references, but it gets painful really quickly. In the end it's easier to write functional code, and let ML do all the work of turning it into something imperative, what with it's tail-recursion elimination, automatic replacement of code that has repeated identical recursive calls (eg. to compute the nth fibonacci number, f(n) -> if n
-- "This is the Space Age, and we are Here To Go" - W.S.Burroughs
Oh, arse. Yeah, I know, I should have used the preview button...
Anyway, as I was saying, to compute the nth fibonacci number,
f(n) -> if n <= 2 then n else f(n-1) + f(n-2)
ML will replace this with either a memoisation technique, or some dynamic programming technique.
-- "This is the Space Age, and we are Here To Go" - W.S.Burroughs
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.
It seems to be a pretty nice language. Nobody here seems to have heard of it. Why? I think it needs a bigger community outside of Japan.
Thanks
Bruce
Bruce Perens.
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
Does anyone have an example in something like X86 assember, Pascal, Delphi or even C?
--Mike--
I prefer it this way:
(define fact
(letrec
((facto
(lambda (n t)
(if (< n 2)
t
(facto (- n 1) (* n t))))))
(lambda (n) (facto n 1))))
Note that by coding in this manner, one is coding tail-recursively--Nothing has to be saved on the stack from one recursive call to the next (in Scheme functions evaluate their arguments before applying the operator so (- n 1) and (* n t) are evaluated before recursion).
I've tried this in Python and got interesting results: A nontail recursive factorial will stack overflow. A tail-recursive implementation still overflows, but after more calls.
Most coders couldn't care less, but then most coders prefer an iterative approach to a recursive one. Which is a bleeding shame, because often recursion is so much cleaner. You can always make it iterative later.
A lot of people who grew up with imperative languages like C, seem to bear a lot of malice towards more functional languages like Python (it's almost first order and pretty functional) or Scheme. I don't really see why. The common whine is that it's the difference between theory and practice. But hey, this is computer science: Theory is practice.
--
Lagos
As for complexity; as long as it's not required where's the harm? Advanced perl melts my brain (around halfway through the camel book) but the advanced features aren't necessarily required to make functional perl code. I'm beginning to get the idea of continuations and am probably going to look at applying the stackless patches to my own customized python tomorrow just to play with it. If I can do it and not break anything, even should I decide not to use new capabilites I won't go to the effort of reverting back to stock unless there's a functionality based reason.
It's only write-only if you're too stupid to understand Scheme.
Stating on Slashdot that I like cheese since 1997.
Heh, and someone got modded up for posting Scheme code. I think someone has it out for you, Bruce. I shudder to think what would happen if RMS were to happen along with some elisp examples.
Stating on Slashdot that I like cheese since 1997.
Python is quite an ok language, even though I understand that quite a lot of developers are less than fond of the concept of "significant whitespace".
.py, .pyc, .pyd, dot anything files, and as a bonus, you will probably be forced to pollute the \system32 folder extensively with global dll-hell-raising dependencies. A python deployment is the definition itself of "system pollution". The McMillan installer is a conceptual heavyweight, gathering complex dependency trees; and watch it go wrong regardless: not really your mother's deployment tool.
.pyd, .py, .pyc, .dll files! Just one .exe!
If you start off with the idea that one "significant" tab is equivalent to 4 "significant" spaces, things can turn out differently than you may have thought when the emacs setting of the day happens to be: 1 tab is traded for 5 significant spaces.
The real issues to me, however, are:
(1) Oosterhout says that the inner loops are to be coded in C, while the outer, administrative loops can be done in -Script-. I could have agreed with this idea, as it sounds good, if it were not that integrating C and -Script- becomes a project in itself. I dare you to figure out tools like SWIG, or even to use the python.h files manually. You're in there for some major undertaking. God save the queen!
(2) Now that you're finished SWIGging and re-SWIGging, compiling, re-compiling your libs, scripts, glue code, you can create your deployment package: an atrocious bunch of dlls,
(3) Python depends on a virtual machine, say the pyxxyy.dll, which shares the problems of all shared objects. While Guido was going from v1.52 to v1.6b to v1.6 to v2.0b to v2.0, which is fine, because that improves the system, it had one major drawback: continuous redeployment of almost identical but slightly different virtual machines. You will find that your virtual machine gets updated more rapidly than the applications that depend on it. What's more, virtual machines create a horrendous need for backward compatibility of the APIs, with its trail of deprecated classes, methods, and entire packages. All the cruft will remain there forever, and you will be deploying an everincreasing pile of mostly unneeded dog shit to your users. In my opinion, *virtual machining* is bound to end in tears.
I'm looking for a high-level language, regardless of its syntax that:
(1) understands seemlessly C/C++ header files and the APIs that it exposes. No SWIGgin! (But also, no IDL or stuff like that, just direct invocation!)
(2) grabs its language run-time (virtual machine) (whichever version that you indicate), native methods (.obj files), and your application, uncrufts it (removes every class or method not used) and nicely links it into one, single clean executable (optionally compressed with, for example, UPX).
No shared objects, no \system32 pollution, no dlls, no folders full of
Correct me if I'm wrong, but isn't there simply a syntactic difference, then, between a tail-recursive function and an iterative function, provided that tail-recursion is implemented by the compiler/interpreter in the optimized way you mention?
I know you were joking, but I want my Karma, so I'm going to reiterate your post in a serious tone.
aslo available in PDF format
Just look at this picture. Is that the face of a man with a dick?
Stop asking: My Karma is nowhere near -100 and will never get there with a default score of -1. I lost.
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.
And, nice as Python is, there is some room for improvement in its role as a scripting and VHLL for UNIX. Module configuration even in 2.0 is somewhat messy (configure, compile, edit Setup, compile some more). There is still nothing quite like CPAN and the CPAN shell module for Perl. Documentation is still more difficult to get to than "perldoc". Despite distutils, Python extensions still sometimes don't "just" install. And building C extensions could also be greatly simplified with a bit more support from the Python installation. Just about the only language enhancement I would like to see for now is lexical closures, not because I think its functionality is desparately needed, but because it would simplify scoping rules if done right.
I think Python is at risk of going down the same path as other dynamic languages before it. Adding a lot of new features (continuations, type declarations, list comprehensions, etc.) complicates the language to the point where people may not feel comfortable just picking the language up anymore. And the effort that goes into those fun features is effort that doesn't go into making the language even easier to install and interface with.
Well Condor does (and has been doing for quite a while) exactly this with C. Assuming you follow the link, now you can believe it. Basically you link with condor's library and it intercepts i/o calls and sends them back to a central controller. Keep in mind this is distributed processing not distributed i/o.
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
JPython was in fact mentioned as another implementation. But this particular article was about Vyper & Stackless.
<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.
I'm a bit up in the air myself, and will eagerly pursue any other replies... in the meantime, maybe take a look at Coroutines in C. It's by PuTTY's author, and there's an example of such coding in it's SSH code apparantly.
Doing this in easy-to-read Python is why the IBM interview is sooooo significant. I really want to use the lazy functional language Haskell for everything (I'm a power freak). I wouldn't mind using Scheme but I'm having enough trouble talking my boss into letting me use Python. Extended functional language and/or ('C') stackless capabilities in Python is just what I want so I can have even more fun programming.
Perl, C, FORTRAN, Pascal and AWK are a purely procedural (not even OO) languages. Functional languages are to large reflecting telescopes what these languages are to binoculars and it does boil down to vision preceded by imagination.
Nice.
People tend to dislike and resent what they don't understand.
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.
Smalltalk uses too much memory. And loading the (huge) image at startup just sucks.
Ruby, on the other hand, has good characteristics of Smalltalk, like pure oo, is faster, the syntax is sweet, you load the modules as you need them, etc. . I suggest everyone to at least take a look at it. It's syntax is very easy (much easier than Python, IMHO), and once you get the grasp, you start to just do right guesses of how to do things.
"Video bona proboque; deteriora sequor." -- Ovid
I understand he didn't want to rewrite the core, and was working off an existing codebase, but if one were to start from scratch, it seems like that might be the simplest way to do this.
---
Moderators: I've got tons of accounts, do your worst.
The online docs are also good.
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
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