10

I came across the following post on the boost mailing lists (emphasis mine):

hello all,

does anybody know of an existing spirit/lisp implimentation, and is there any interest in developing such a project in open source?

None yet, AFAIK.

I'll be writing an example for Spirit2 to complement the tiny-C virtual machine in there. What's equally interesting though is that scheme (or at least a subset of it) can be implemented in pure c++. No parsing, just pure DSEL in C++. Now, imagine a parser that targets this DSEL (through C++) -- a source to source translator. Essentially, your scheme code will be compiled into highly efficient C++.

Has anyone actually done this? I would be very interested in such a DSEL.

HighCommander4
  • 50,428
  • 24
  • 122
  • 194
  • 2
    Though I have no interest in scheme, I'd really like to see such a thing :) – Matthieu M. Feb 24 '11 at 08:15
  • This probably works for a small subset of Scheme's functionality. I can't imagine this working for, say, Scheme macros or continuations. ;-) – C. K. Young Feb 24 '11 at 08:17
  • @Chris: continuations, probably not. But macros... C++ might just surprise us. – HighCommander4 Feb 24 '11 at 08:19
  • @Matthieu, me too. I'd esp. like to see how the implementer is going to handle garbage collection in "pure C++"... – Fred Foo Feb 24 '11 at 08:58
  • @HighCommander4, unfortunately, there is no way to translate scheme hygienic macros into C++ templates. It is a fundamental limitation. – SK-logic Feb 24 '11 at 11:08
  • @SK-logic: This article suggests otherwise: http://cplusplus-soup.com/2010/07/23/lisp-macro-capability-in-c/ (Then again, the author doesn't actually present code to back up his claim.) But why do you say this is a "fundamental limitation"? – HighCommander4 Feb 25 '11 at 09:21
  • @HighCommander4, this article is about a completely different thing. The problem is that you can't implement a compile-time Lisp `(defmacro ...)` on top of a C++ template eDSL. And the rest of Lisp is not interesting at all without this fundamental feature. – SK-logic Feb 25 '11 at 09:25
  • 2
    This one doesn't based on boost, but anyway - http://www.intelib.org/ – hoha Mar 07 '11 at 13:04

3 Answers3

6

I wrote a Lisp-like language called Funky using Spirit in C++. An Open Source version is available at http://funky.vlinder.ca. It wouldn't take too much to turn that into a Lisp-like to C++ translator.

Actually, what it would take is a run-time support library to provide generic closure times and somesuch: if you want to turn the Lisp code into efficient C++, you will basically need C++ classes (functors, etc.) to do the heavy lifting once you get to run-time, so your Lisp-to-C++ translator would need to:

  1. parse the Lisp
  2. create an AST from the Lisp
  3. transform the AST to optimize it, if possible (optimizations in Lisp are different from optimizations in C++, so if you want rally fast C++, you have to optimize the Lisp and let your C++ compiler optimize the generated C++)
  4. generate the C++, for which you'd rely on your run-time support library for things like built-in functions, functor types, etc.

If you were to start from Funky, you'd already have the parse and the AST (though Funky doesn't optimize the AST), so you could go from there an create the run-time and generate the C++...

It wouldn't be overly complicated to write one from scratch either: Lisp grammar isn't that difficult, so most of the work would go into the AST and the run-time support.

If I weren't writing an object-oriented DSL right now, I might try my hand at this.

rlc
  • 2,808
  • 18
  • 23
  • Interesting... Do you think this translation can be done at compile time, i.e. using metaprogramming? – HighCommander4 Mar 17 '11 at 06:12
  • @HighCommander4 You can already do a lot of functional programming when meta-programming: meta-functions can "return" meta-functions, loops are implemented as recursive "calls" to meta-functions, etc. The thing is that that doesn't look (or feel) like Lisp and getting the C++ meta-programming syntax to look like Lisp (even if you turn '(' into '<' and ')' into '>') ... I guess it's feasible, but I'd be surprised if it's really useful... – rlc Mar 17 '11 at 13:30
1

scheme to (readable) c++ http://www.suri.cs.okayama-u.ac.jp/servlets/APPLICATION.rkt

How about this

Hirotaka Niitsuma
  • 11
  • 1
  • That's quite interesting (is the source code for it available?). However, it's not what I was looking for. I was looking for a C++ library (most probably implemented using template metaprogramming and/or preprocessor metaprogramming) that allows you to write code in C++ that looks like (infix, S-expressions) and acts like (macros, pattern matching) Scheme. – HighCommander4 Oct 26 '11 at 18:13
  • In fact quite interesting. I would love to see the code. The thing is that there are VERY FEW (if any) translators that actually generate .h and .cpp to be included as if they were written in C++. – Diego Sevilla Apr 17 '12 at 17:52
0

Not sure if this is what you want, but:

http://howtowriteaprogram.blogspot.com/2010/11/lisp-interpreter-in-90-lines-of-c.html

It looks like a start, at least.

Albert Perrien
  • 1,153
  • 12
  • 27