Sign in to follow this  
cypherx

Implementing recursion optimization?

Recommended Posts

cypherx    204
Hi, I'm writing a lisp/scheme derived scripting engine. I'd like to implement "tail-call optimization"...but I'm not sure how to identify when a function call is a tail call. Any ideas? Also, the design of my evaluator seems to me very inefficient...the core are the mutually recursive functions evaluate(expression) and apply (function, arguments). The mutual recursion is slow and quickly eats up my stack. Is there a better (iterative) way to evaluate expressions? Thanks, Alex

Share this post


Link to post
Share on other sites
SiCrane    11839
If you look at the Scheme R5RS standard you'll find that there's a detailed description as to what is a tail call. If you find the long single document version of the standard just search for the term "tail expression" and you should end up in the middle of the discussion.

Share this post


Link to post
Share on other sites
cypherx    204
Wow, thanks for pointing me to the standard. It helped me iron out a lot of fuzzy areas in my design.

I have a few questions, though, that maybe someone can help me out with...

Do I lose performance by implementing my own call stack vs. using the C call stack. I'm guessing C function calls are highly optimized...does this matter?

What about "stackless" languages (like stackless python)? How are these implemented? Is there a performance benefit?

Also, I want to use my language for genetic programming (mutating populations of functions) and simulation scripting. What would be a good standard library for these purposes?

I'm thinking:
-threads
-gui (hooks into wxwidgets?)
-math (matrix, vector, random num generators)

Any others?

Thanks,
-Alex

Share this post


Link to post
Share on other sites
Extrarius    1412
Using the native stack (the same one any decent C compiler generates code to use, but it is not "the C stack") is better because processors are heavily optimized with the assumption that you'll use whatever they give you. Using a custom stack allows more flexability, and in this case the flexability comes with the cost that the stack won't be able to take advantage of certain hardware optimizations. If you're using a custom dynamic language, though, you shouldn't really care about the difference. If you want extreme performance in a dnymic language, you need something developed over a long period of time by experienced professionals.

As far as what libraries tht would be helpful, I don't really see the need for any of the things you listed. Personally, if I were going to be working with genetic programming, I think the most useful library would be something to do the graph analysis, manipulation, translation, and execution. A random number generator would probably be good too.

As far as threading and a gui library, they seem somewhat exclusive - if you need threads, you probably want them because you have multiple processors (or cores or hyperthreading or something like that) and want to take full advantage of them because the program will take a long time to execute. If you have a GUI, that implies that you're going to have some kind of graphical realtime feedback which doesn't seem likely with such a long running time. I think a simple command line interface would do fine.

As far as things like matrix support, vectors, etc, those would only really be helpful if you want to generate functions using them. Otherwise, I don't see how they apply to genetic programming.

Share this post


Link to post
Share on other sites
flangazor    516
Readscheme has some excellent papers. Of interest will be the one, "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO".

If you have an FFI into a language using .o files (e.g. C, Fortran, C++, etc) then I would definitely look into learning Fortran95 and using that for the matrix and vector operations. They are built into good F95 compilers so you get the vectorization for free.

I would ignore threading and go with processes and IPC.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this