> Nevertheless, I get a little thrill out of having made something that allows me to type (define cube (lambda (n) (* n n n))) and then (cube 3). It's like magic.
This is great, and it's really true. I've just finished the Metacircular chapter of SICP and felt the same way after reading their code and doing some of the exercises. I think "90 lines of C++" is kind of a silly goal (just because LOC is silly) but it's still a great learning experience. I'd love to try a non-metacircular evaluator after I've read more SICP.
I have to say I'm a huge fan of these "X in 100 lines of C++" adventures. They're a great starting point for people like me wanting to learn about a subject in a programmatic way.
Here's one of the most interesting "X in Y lines of Z" programs I've seen, a prototype interpreter for the basics of an APL-like language in one page of (rather funky, Arthur Whitney-style) C: http://nsl.com/papers/origins.htm
It segfaults due to nonportable assumptions about pointer sizes in the allocator, and is far from complete as APLs go, but I spent a couple hours picking it apart and came away quite impressed.
There's a similar raytracer (http://nsl.com/k/ray/rayq.k) in 17 lines of Q, but I haven't figured that one out yet.
. . . or MiniLight: http://www.hxa.name/minilight/ is an alternative: it is larger -- averaging 650 lines -- but it is available in 9 different languages -- and is a more complete renderer that you can put your own scenes into.
(I am working on the Scheme translation at the moment)
It's based on Peter Norvig's article of a similar name. I think that the '90 lines' was a reference to that former article rather than a literal description of this one.
- Use the STL algorithms more. There are way too many "for" loops in this code which are trivial std::accumulate or std::transform calls.
Pre-C++0x, that's not a clear tradeoff. Since pre-C++0x does not have lambdas, you would have to write one-off functions or function objects. In this case, I think that would increase the number of lines of code.
I do a lot of work in C++, and I prefer using the STL algorithms to explicit for loops. But I have often written code that uses the STL algorithms, then reverted it back to a for loop because I had to introduce more code at another level of scope for a marginal gain in clarity - a voice in the back of my head tells me I'm being too cute. Now that C++0x has lambdas, this should cease to become an issue as I can assume compilers support them.
I played with boost::lambda, and I found the resulting code less clear than a simple for loop. I also had difficulty gaining an intuition for what I could and could not do with it. Rather than constantly asking myself "Can I use boost::lambda here...? Will it look better or worse than the alternative?" I just decided to never use it.
While I prefer a functional style of coding, I recognized that it was silly to adhere to it if doing so made my code worse - C++'s support for what I wanted to do just wasn't there. If what I wanted to accomplish was several lines of code, I wrote a separate function or function object. If it was brief and I could not express it with combinations of existing functions, then I just wrote a for loop.
I didn't play with boost::proto, so I can't comment on that. But! C++ has real lambdas now. So, problem solved. (Once the compilers catch up.)
Like the other post said, I really wanted boost::lambda to work. However, I found that anything more complicated than "_1 * 2.0" became write-only code, so in practice it was useless.
I find that to be very interesting. I spent far too many years working with C++, trying to master all of its nooks and crannies. It was my frustration with the limits of the language that drove me to finally learn Lisp. The fact that for loops always ended up appearing clearer than using STL was extremely frustrating. I'm not 100% sure that the introduction of lambdas in the newer versions of the C++ standard will not fix the problem (or at least help some), but I sincerely doubt that they will be enough. I truly wanted to use STL and the the standard containers, but it always ended up feeling like I was working extra hard to try and "get it right". In the end it was faster just to grumble, write another for loop with an explicit iterator, and move on.
And yes, I'm aware of Boost and the like. I have all the template metaprogramming books you are likely to name. It all still feels terribly unnatural and forced compared to, say, composing a chain of function calls against a list of data in Lisp or Scheme.
I really like playing with Racket. It's very powerful and simple. Mathematical. I concede that. But it's not "natural". I can guarantee you that Lisp showed to a novice isn't "natural".
C++ is different. It's not unnatural. There's no "natural" programming language.
C++ is explicit. You need to manage your memory. You need to tell how the return value will be handled. You need to work with the compiler, the linker.
You have more control. More power. It gets in the way for some tasks, but it is mandatory for others.
I find the lack of STL to be frustrating, because I'm used to it. To me it feels "natural".
There's no problem with not being proficient with C++ or the STL. It's just not your thing!
Just to be clear, I didn't describe Lisp as "natural", I described using the STL (meaning, particularly, heavy use of STL algorithms, function objects, etc) as feeling terribly unnatural and forced. Judging by the reaction here, "unnatural" was perhaps not the best choice of words. What I meant was this: when trying to use the STL to get stuff done, I felt like I was always jumping through hoops to do things "the STL way", with the end result being more complicated and less clear than just doing it in a "C++ without the STL" way.
> I can guarantee you that Lisp showed to a novice isn't "natural".
Again, I never argued that Lisp was "natural". And secondly, if you are dealing with a true novice (as in, someone who has never programmed in any programming language), both C++ and Lisp are going to look decidedly "unnatural" to them. But I don't want to beat the natural/unnatural language dead horse any longer, since that was not what I was discussing. However, I will concede that Lisp looks decidedly foreign to people who have programmed before in languages with an Algol-like syntax (C, C++, Java, Javascript, Perl, etc).
And, for the record, I am very proficient in C++ (many years of work experience), and I understand how the STL works very well (I invested a lot of time in learning the STL). I invested that time because I wanted to make C++ do more than it had done for me in the past, and the STL seemed like the way to do that. However, in the end I decided that there really was no good way to make C++ do what I wanted, and the real answer was to go with something that was far better at handling higher level constructs. After trying out Lisp (and Scheme) for I while I realized that the primary things I was trying to do with the STL were no-brainers in Lisp. And with a decent FFI I can still use C or C++ when I need to do things at a lower level. I still use C++ libraries when it makes sense to do so, but I would not now start a new project with C++ as the primary language if given the choice to use something else (unless, of course, the only choices were something even worse than C++ :-D ).
I actually enjoy programming with C++ and Qt containers.
Both STL and Boost seem like pathologically complex ways to do something that's already hard. Consider; in a situation where you're doomed to sometimes use a for-loop, where for-loops are pretty much the underlying semantics, using some proportion of higher level methods like filter when they don't shorten your code, turns these construction into obfuscating, leaky abstractions.
But perhaps you have to actually be a C++ fan to use STL and Boost. I only view C++ as the least-bad-for-my-purpose language.
I threatened to do this in an introductory undergrad systems programming course I had to take to satisfy a degree requirement in spite of it being way below my level of proficiency. Fortunately for my grade and the grader's sanity, I chose not to do it.
Graders at the University of Michigan are willfully unaware of it because we want students to have some coding style. You'd be surprised how many have to be repeatedly slapped around until they get a real programmer's editor instead of trying to use gedit without configuring it.
I looked at the Norvig lis.py code and took the time to understand every line. It's a clever program and taught me a few new Python tricks. The main reason he can get it down to so few lines of code is that he leans back on the capabilities of Python. E.g. garbage collection, arbitrary objects stored in hierarchical lists, lambdas, use of dictionaries for the environment/symbol table. If you try the same thing with a language like C you either need library support or more lines of original code.
Sorry I know this is rude, but I'm tired of seeing so many posts about lisp interpreters in high level languages, the vast majority of which don't mention macros -- the only plausible reason that such an interpreter would really be useful (mine does support macros :)).
I know this is a curmudgeonly thing to say, but I'm happy to see one of these "implementing Lisp" articles where someone started with a lower-level language than Lisp. It just seems like you miss out on a lot of interesting learning if you start with something like Ruby or Python that is so close to Lisp already.
For example, implementing lambda with a Python lambda...really? You are missing a giant a-ha moment there, as you can see from this article.
Note: implementing a metacircular interpreter for Lisp in Lisp is a beautiful special case exception to my curmudgeonliness.
Tried to compile this using Borland's C++ 5.5 (free). The only function not supported was 'isdigit()'. Wrote a simple version just for fun and it compiled.
I was able to run the first example completely.
Not bad for an out-of-date but free compiler with a 1993,2000 copyright.
38 comments
[ 3.3 ms ] story [ 87.9 ms ] threadThis is great, and it's really true. I've just finished the Metacircular chapter of SICP and felt the same way after reading their code and doing some of the exercises. I think "90 lines of C++" is kind of a silly goal (just because LOC is silly) but it's still a great learning experience. I'd love to try a non-metacircular evaluator after I've read more SICP.
The author might be interested in http://michaux.ca/articles/scheme-from-scratch-introduction
I think I found that on HN somewhere, it's been in my TOREAD for a while.
This global illumination ray-tracer was posted a while back: http://kevinbeason.com/smallpt/
It segfaults due to nonportable assumptions about pointer sizes in the allocator, and is far from complete as APLs go, but I spent a couple hours picking it apart and came away quite impressed.
There's a similar raytracer (http://nsl.com/k/ray/rayq.k) in 17 lines of Q, but I haven't figured that one out yet.
(I am working on the Scheme translation at the moment)
It's actually 333 lines.
- Use the STL algorithms more. There are way too many "for" loops in this code which are trivial std::accumulate or std::transform calls.
- When I see the eval and tokenize functions I ask myself, why not use Boost.Spirit.Qi?
- I'm not sure working on a list of strings is efficient, why not work on a list of pairs of pointers instead?
- Use smart pointers to avoid leaks.
Just a small contribution, I really like the idea.
You mean to use Qi's eval? I don't know Qi, so I don't understand what that would entail.
When I see the eval and tokenize functions I ask myself, why not use Qi?
Pull down your eye-brows folks, he means boost::spirit::qi, not http://en.wikipedia.org/wiki/Qi_(programming_language)
I had a whole minute of flabbergasted awe, then decided to double check with the Google :-)
Pre-C++0x, that's not a clear tradeoff. Since pre-C++0x does not have lambdas, you would have to write one-off functions or function objects. In this case, I think that would increase the number of lines of code.
I do a lot of work in C++, and I prefer using the STL algorithms to explicit for loops. But I have often written code that uses the STL algorithms, then reverted it back to a for loop because I had to introduce more code at another level of scope for a marginal gain in clarity - a voice in the back of my head tells me I'm being too cute. Now that C++0x has lambdas, this should cease to become an issue as I can assume compilers support them.
While I prefer a functional style of coding, I recognized that it was silly to adhere to it if doing so made my code worse - C++'s support for what I wanted to do just wasn't there. If what I wanted to accomplish was several lines of code, I wrote a separate function or function object. If it was brief and I could not express it with combinations of existing functions, then I just wrote a for loop.
I didn't play with boost::proto, so I can't comment on that. But! C++ has real lambdas now. So, problem solved. (Once the compilers catch up.)
I find that to be very interesting. I spent far too many years working with C++, trying to master all of its nooks and crannies. It was my frustration with the limits of the language that drove me to finally learn Lisp. The fact that for loops always ended up appearing clearer than using STL was extremely frustrating. I'm not 100% sure that the introduction of lambdas in the newer versions of the C++ standard will not fix the problem (or at least help some), but I sincerely doubt that they will be enough. I truly wanted to use STL and the the standard containers, but it always ended up feeling like I was working extra hard to try and "get it right". In the end it was faster just to grumble, write another for loop with an explicit iterator, and move on.
And yes, I'm aware of Boost and the like. I have all the template metaprogramming books you are likely to name. It all still feels terribly unnatural and forced compared to, say, composing a chain of function calls against a list of data in Lisp or Scheme.
C++ is different. It's not unnatural. There's no "natural" programming language.
C++ is explicit. You need to manage your memory. You need to tell how the return value will be handled. You need to work with the compiler, the linker.
You have more control. More power. It gets in the way for some tasks, but it is mandatory for others.
I find the lack of STL to be frustrating, because I'm used to it. To me it feels "natural".
There's no problem with not being proficient with C++ or the STL. It's just not your thing!
How do you define a language as "natural"?
I can't say I find any language to be 'natural', there are just some that I know the rules to more implicitly than others.
(Including natural languages like English or Spanish).
> I can guarantee you that Lisp showed to a novice isn't "natural".
Again, I never argued that Lisp was "natural". And secondly, if you are dealing with a true novice (as in, someone who has never programmed in any programming language), both C++ and Lisp are going to look decidedly "unnatural" to them. But I don't want to beat the natural/unnatural language dead horse any longer, since that was not what I was discussing. However, I will concede that Lisp looks decidedly foreign to people who have programmed before in languages with an Algol-like syntax (C, C++, Java, Javascript, Perl, etc).
And, for the record, I am very proficient in C++ (many years of work experience), and I understand how the STL works very well (I invested a lot of time in learning the STL). I invested that time because I wanted to make C++ do more than it had done for me in the past, and the STL seemed like the way to do that. However, in the end I decided that there really was no good way to make C++ do what I wanted, and the real answer was to go with something that was far better at handling higher level constructs. After trying out Lisp (and Scheme) for I while I realized that the primary things I was trying to do with the STL were no-brainers in Lisp. And with a decent FFI I can still use C or C++ when I need to do things at a lower level. I still use C++ libraries when it makes sense to do so, but I would not now start a new project with C++ as the primary language if given the choice to use something else (unless, of course, the only choices were something even worse than C++ :-D ).
Both STL and Boost seem like pathologically complex ways to do something that's already hard. Consider; in a situation where you're doomed to sometimes use a for-loop, where for-loops are pretty much the underlying semantics, using some proportion of higher level methods like filter when they don't shorten your code, turns these construction into obfuscating, leaky abstractions.
But perhaps you have to actually be a C++ fan to use STL and Boost. I only view C++ as the least-bad-for-my-purpose language.
https://github.com/rongarret/Ciel
Note: not quite ready for prime time. Just a proof of concept for now.
Sorry I know this is rude, but I'm tired of seeing so many posts about lisp interpreters in high level languages, the vast majority of which don't mention macros -- the only plausible reason that such an interpreter would really be useful (mine does support macros :)).
For example, implementing lambda with a Python lambda...really? You are missing a giant a-ha moment there, as you can see from this article.
Note: implementing a metacircular interpreter for Lisp in Lisp is a beautiful special case exception to my curmudgeonliness.
I was able to run the first example completely.
Not bad for an out-of-date but free compiler with a 1993,2000 copyright.