Anthony C. Hay

29 November 2010

A funny thing happened...



When I got home tonight I had a really nice surprise waiting for me.

Thank you everyone who took time to read the post, and especially those who commented on or linked to it.



UPDATE 4 December 2010

It looks like my 15 minutes of fame - sort of - is drawing to a close now. Here are a few recent graphs in case they are of interest to anyone else.





This one is awesome: if I understand it correctly, three people found my blog by putting "C++" into Google! Bjarne Stroustrup's blog, yes. But mine?! I just tried it but I couldn't see it on the first few pages. They must have been very patient:



Seventeen thousand people stopped by and no one left a rude comment. (I think there's a remote possibility a few people went back to their own communities and left rude comments there.)

Lisp interpreter in 90 lines of C++: I lied right there in the post title: I could be in advertising. I hope people forgive me. It's been a fun new experience for me.

FINAL UPDATE 30 December 2010

It's been a month since the post was published so I thought I'd write a little more about it. To date the post has had 17,423 page views (way more than it deserves); the blog has had 19,382 page views in total. Prior to the post it had just a few hundred page views total.

One more graph



Not only did four people find the blog by Googling for "C++", but three people found it by Googling for "lisp"! Sorry to go on about it but I find it astounding.

I did toy with the idea of developing the code further. I added tail call optimisation as described in Peter Norvig's second article. I also tried to fix the memory leak by replacing the raw pointers with boost::shared_ptr. This reduced the memory leak but didn't eliminate it. I can't work out wether garbage collection is unavoidable or not, but I assume it is. The leak was not eliminated because there were situations where there was a sort of circularity of references. e.g. in (define leak (lambda () (define f (lambda () 0)))) where f is a lambda that references the closure in which f is defined.

In the original article I said the code was inefficient. Having reduced the memory leaks I wanted to give some idea of just how inefficient the code is. I adapted this example of the Sieve of Eratosthenes from rosettacode.org (once again I've shown the code formatted for readability; you have to enter each procedure on one line)



(define iota (lambda (start stop stride)
(if (> start stop)
(list)
(cons start (iota (+ start stride) stop stride)))))

(define strike (lambda (lst start stride)
(if (null? lst)
lst
(if (= (car lst) start)
(strike (cdr lst) (+ start stride) stride)
(if (> (car lst) start)
(strike lst (+ start stride) stride)
(cons (car lst) (strike (cdr lst) start stride)))))))

(define primes (lambda (limit)
(begin
(define stop (/ limit 2))
(define *primes (lambda (lst)
(begin
(define prime (car lst))
(if (> prime stop)
lst
(cons prime (*primes (strike (cdr lst) (* prime prime) prime)))))))
(*primes (iota 2 limit 1)))))

90> (primes 1000)

(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101
103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197
199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311
313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431
433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557
563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661
673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809
811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937
941 947 953 967 971 977 983 991 997)

90>



I didn't bother timing this, but it must have taken about an hour of 100% CPU and peak memory usage of around 50 MB. I must have produced the most inefficient Scheme interpreter ever. (In contrast I found and compiled TinyScheme, which performed this same task in the blink of an eye. Interestingly, TinyScheme is a not-so-tiny 4,500 lines of C.)

Actually, I was hoping to find something "real" I could do with the interpreter, but wasn't able to - probably a lack of imagination on my part.

I enjoyed Steve Yegge's post about computer languages

So if you don't like what I'm saying about about C++, go become an expert at a better language (I recommend Lisp), and then you'll be armed to disagree with me. You won't, though. I'll have tricked you. You won't like C++ anymore, and you might be irked that I tricked you into disliking your ex-favorite language. So maybe you'd better just forget about all this. C++ is great. Really. It's just ducky. Forget what I said about it. It's fine.


I'm pretty sure that the only way I'm going to really learn Scheme is to commit myself to writing a non-trivial application in that language.

It'll be one of my New Year resolutions.



index of blog posts

No comments:

Post a Comment