Ask HN: Convert c to lisp? | Hacker News Reader

Ask HN: Convert c to lisp?

6 pointszackmorris4 comments

Hi I'm trying to find a program or library that can convert an arbitrary procedural program written in c, java, perl or any similar language to a functional language like lisp or haskell.

There are a couple of tools to go the other way or embed lisp in a c program (since you can just "unwind" lisp declarations like a macro):

http://www.interhack.net/projects/lpp/ http://www.youtube.com/watch?v=8TPPW3i4v9A

And I found ECL which lets you call c from lisp and vice versa, but doesn't seem to do any actual conversion of the code or make any guarantees that it's correct or without side effects.

It should be possible to do this, at least for a very simple program that for example only has access to the input and output streams:

http://en.wikipedia.org/wiki/Church-Turing_thesis

Am I just being naive? Is this a nontrivial problem? If so, this seems like it would be an interesting research topic.

I very much need a c to lisp converter so that I can rapidly prototype my functions and results without having to think in a purely functional manner, because it doesn't tend to match the real world and worse, I can't explain my code to other people. I would also like to evolve my code with genetic algorithms and it's much easier to do that with lisp than syntax-heavy languages. If this is a truly intractable problem then I wonder if this has anything to do with the problems facing software engineering today.

Thanks!

The Church-Turing thesis simply tells us that different models of computation are equivalent — and as applied to programming languages, anything that one Turing-equivalent language can compute, another can. But it emphatically does not mean that idiomatic code in one language can be mechanically translated into idiomatic (or even particularly readable) code in another language by a simple process.

If you did have a C-to-Lisp converter, it would almost certainly produce very imperative-style Lisp code that mimics the form of the C input, not nice functional code like you probably want.

If your problem isn't well-suited to a functional approach, why are you using Lisp to solve it?

Anyway, the Church-Turing thesis won't cause you any trouble. C and Lisp are both "Turing-complete" which means that any program you can write in one will be representable in the other. I couldn't find a direct translation, but maybe this Fortran->Lisp converter from 1979 will show you how it's possible? http://www.nhplace.com/kent/Papers/Fortran-to-Lisp.html

Thanks for the link. I try to write most of my code in a functional manner in c, so like, DRY, favoring functions instead of having a variable dependent on another variable, stuff like that. I want to make a tool at some point that takes a block of c code and converts it to lisp so that I can try various transformations and permutations like Mathematica does, or evolve the parse tree with genetic programming:

http://www.geneticprogramming.com/Tutorial/

Then I want to turn the lisp code back into c code and keep it readable. Off the top of my head, I might be able to represent any globals in c as a list and pass that along to the lisp functions, or better yet, ban globals for now. External library calls would probably also be banned, unless they are from a built-in library with no side effects. It's just much easier for me to proofread code than generate it so I'd really like to have a tool like this.

There's a compiler that compiles c/c++ to xml. It's name esacpes me now, but a little bit of google-fu should do,

XML to lisp should be relatively straightforward.

Reply on news.ycombinator.com