Home » forums » LtU Forum

Looking for list of programming problems to thoroughly test a language

I'm sure some of the other language designers around here have already tackled this problem, but I can't find anything in the archives...

I was wondering if anyone knows of a good list of programming problems that would be good for testing a language. I'm looking to not only test the correctness of my interpreter implementation, but also how usable some of the language's constructs are. The only test/sample programs I can think of off the top of my head would be things that a programming class would assign as homework, such as factorials, sort routines, that sort of thing. But I want to make sure I cover enough bases before I finalize my design.

I was thinking of going through the list of problems on sites such as rosettacode.org, but I'd also like to find problems that target specific paradigms and concepts (at the moment I'm looking at making sure closures are done correctly, in addition to continuations when I get that far). Another idea I had was to go ahead and translate the problems in SICP into my language implementation, seeing as how there's already an SICP translation project out there. Would that pretty much cover all the bases? And possibly add on problems from one of the standard algorithms text books?

Thanks.

By derekp at 2009-05-01 01:53 | LtU Forum | previous forum topic | next forum topic | other blogs | 7736 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Programming Chrestomathy

Programming Chrestomathy [c2] lists a few sites. Rosetta code also provides a list.

Using example problems from books is good, too. SICP is decent, and CTM would also cover a lot of bases.

By dmbarbour at Fri, 2009-05-01 03:04 | login or register to post comments

self-interpreter

Yes it's a bit solipsistic, but trying to write an elegant self-interpreter is one way to find out if your language has any obvious design flaws/omissions.

By Noam at Fri, 2009-05-01 05:02 | login or register to post comments

Project Euler

Noam's suggestion is actually pretty good. You could then run your meta-circular interpreter on many of your other test cases to get double duty out of things, although I doubt this would be as good as twice as many well-chosen test cases.

Project Euler is a thought; though the site tends to be rather geared towards dynamic programming and memoization, combinatorics, and number theory, so the test problems won't be quite as diverse as say, SICP. It's still a good selection of problems though, and a great selection of algorithms.

Also, "pathological" corner cases in your language make good test cases; not only for understanding your language better, but also to make sure you understand the implementation aspects well enough. CALL/CC + LETREC = SET! is a classic example from the Scheme community, although this thankfully no longer applies to R6RS.

By Leon P Smith at Fri, 2009-05-01 05:25 | login or register to post comments

It sounds like you're

It sounds like you're interested in kernel codes. The 'A View From Berkeley' paper outlines 'parallel dwarves' -- types of computations (e.g., dense matrices, FSMs..) common to many applications (and that we want to parallelize).

Examples of programming in the large are important too, if even just one. There was a thread recently where Adam Chlipala asked something similar for web frameworks.

By lmeyerov at Fri, 2009-05-01 06:06 | login or register to post comments

The Salishan problems

The Salishan problems though not exactly what you are looking for are still worth a look.

By Ehud Lamm at Fri, 2009-05-01 07:10 | login or register to post comments

Knight's tour

My standard "first substantive problem" for new programming languages I am interested in is to write code that can find solutions for the knight's tour for M*N sized chess boards. Writing correct-but-infeasible code solving this problem is easy, refactoring the code to get reasonable performance is a sort of stress test for the PL's data structures.

By Charles Stewart at Fri, 2009-05-01 15:57 | login or register to post comments

generic programming

Try to implement a generic graph library and compare your answers to those in
the following paper:

http://ecee.colorado.edu/~siek/pubs/comparing_generic_programming03.pdf

(There's also a more recent journal version with even more languages.)

By Jeremy Siek at Sun, 2009-05-03 02:58 | login or register to post comments

What about the "great

What about the "great language shootout"? The samples are made for micro-benchmarks but it's a small collection that covers a lot of language basics.

By Kay Schluehr at Mon, 2009-05-04 18:46 | login or register to post comments