Python Generators

Background

Back in May, 2013, I posted "Cheap, but not Free, Modular Code has a Price". In that blog article I compared the performance of my solution of Project Euler problem 14 to the performance of Nico Ekkart's solution of that same problem. As I explained in that article last May, Project Euler's guidance on performance is that a solution should be able to complete on a typical PC in less than a minute. My initial solution ran well over a minute and I applied a cache to speed my program up. Once I'd gotten it down below the one minute limit, I had concluded "good enough" and went on to other problems. But Nico honed his solution a little tighter and outperformed my program by a factor of 4.

Looks to me that we had basically the same solution, but his was more of an in-line implementation, while I used a Python generator to produce the sequences of numbers the processing of which is the heart of problem 14. I concluded that the Python structuring facilities like generators do add overhead but I opined that the added clarity of packaging the sequence generation as a "generator" made the overhead worthwhile. Nico's code for his cache was so little code that I didn't really defend my use of a Python "class" for my cache implementation. Some further experiments with the code to determine how much of my extra overhead came from the generator vs. how much came from my cache implementation might be interesting. I've posted the source code and invite you to experiment and share your findings.

But that isn't what I came here to talk about today

This blog post today is aimed at expanding your knowledge of Python Generators and share with you a neat trick that I've recently learned: a generator of dictionaries.

Python Dictionaries

Back in January, 2013, I posted "Dictionary Implementation". In that article I pointed to where the Udacity CS101 MOOC introduces Python dictionaries and pointed to further places to look to learn how Python implements dictionaries, hash tables. If you aren't comfortable with Python's notion of a dictionary, I'll sum it up as an easy to use collection of name-value pairs, much like an array is an easy to use collection of subscript-value pairs.

Given an integer value as a subscript into an array, you can easily ask for the value associated with that subscript. (In Python such an array is called a "list". But if you have a dictionary of name-value pairs, in Python it is easy to ask for the value associated with a name. e.g. What value is associated with "eggplant", where "eggplant" in this example is a possible "name" entry in the dictionary. If this is all still mysterious to you, my suggestion is to dig for more info on the web. Google search is your friend. A Google search for:

python dictionary

turned up more than 5,000,000 web pages today and Google looks to have done a decent job of sorting the most helpful ones to the front of the search results.

Or perhaps you should work your way through Udacity CS101 to learn this concept of dictionaries and more.

Python Generators

But as I already said, the topic of my blog post today is Python Generators. Rather than take the time and trouble to create a fresh new tutorial about Python Generators, I'll pause here to provide a link to an article from April 2013 from Jeff Knupp: "Improve your Python: 'Yield' and Generators Explained". That article resonated with me as written in an easy to understand way. It's about 19 screens long, so it isn't a quick read, but you can get back to Facebook and YouTube later.

Knupp's article should certainly get you to the point of being comfortable with my Project Euler problem 14 generator. My generator is very vanilla, just conjuring up a sequence of numbers. The one tricky aspect is my program often doesn't pursue the sequence to the end, but sometimes decides it needs to see a new sequence. I was a little nervous when I did it that way, but now understand that Python doesn't mind dangling generators like that, and even should know enough to be able to garbage collect their saved state, if memory gets tight and it is clear that there's no way the program could get back into that old sequence. Powerful stuff and a feature unlike anything available available in C, Fortran, Basic or Cobol to name 4 examples of older more traditional programming languages.

But Wait! There's more!

If you've read this far but are yawning, thinking that hardly ever do you, yourself, have occasion to use complex logic to generate a sequence of numbers in the programs that you write, well hang on and see what else generators are good for.

Igor Vasilcovsky recently pointed out to me an interesting tutorial from David Beazley about generators. The meat is the slide deck under the presentation link on that page. Even with 2 slides to a page, that slide set runs to 79 pages so it probably is too much to absorb in one sitting. So try to work through it in several sessions. Here's my summary of the key elements I think you should get from wading through that presentation:

1. A generator can return any kind of Python object. That is, it isn't limited to returning the numbers of a sequence. If you paid close attention to my Pythonic Python from July, 2013, you may remember that one of the points I made there was that Python functions can return large complex objects, not limited to just a number or just a pointer. Better still, Python takes care of the book keeping to automatically garbage collect the returned object if you are no longer using it.

   Beazley has examples with a generator returning strings (lines from log files), and then takes an unexpected turn to have the generator parse the strings into values and stash the values into a dictionary with a name for each value and then return the resulting dictionary as the generator's output. (A dictionary per line of the log file!) My initial reaction to that was to be horrified at the overhead, but if you think about it, looking up a name in a dictionary is quite central to Python's run time modus operandi, so dictionary objects being generated is perhaps more general than generating some more specific Python class object, and looking up values by name is pretty much the same as using a name of a member of a class object to get to a value in the class object. So given that Python is able to get decent performance from run-time interpretive execution, generating dictionaries is a lot more sensible then my initial gut reaction took it to be.

2. A generator is just Python software so it can do anything that any Python software might want to do to provide the next value in the sequence. It can compute the next value using a formula, or it could access a file to learn the next value. It is even able to make use of another generator to get an input sequence that it manipulates and passes along. So generators can be chained together into long pipelines.
3. If your program is basically about iterative processing of a series of stuff, then chaining together pipelines of generators can fundamentally shape a clean structure for your program and with a little practice you'll soon have a collection of useful reusable filters that you can use to construct future programs that you haven't even thought of yet. Share them with your friends. If you own the code, consider making it (and it's documentation) GPL licensed and freely shared on Github or some other such public place.

I'm seeing hints on the Internet that future Python releases will have even more use of generators. e.g. standard approaches built in to the language to process streams of events. e.g. Brett Cannon's 40 minute talk: "Python 3.3: Trust me, it is better than 2.7". He foreshadows a Guido Van Rossum talk about Python 3.4 scheduled for that same conference. If you can find a link to a video of Guido's talk about 3.4 and new roles for generators, please share it in the comments section here.

Linus Torvalds on Teaching Children to Program

Linus Torvalds in this less than 3 minute video clip gives a great answer to a question about teaching children how to write computer code. He specifically mentions the Raspberry Pi as having the attractive property of being cheap enough to throw away. I've said before that if you persuade kids to try a computer programming course, some number of them will hate it, and will vow never to wrestle with computer software again. But there should be some who will decide this is fascinating and will pursue it further, perhaps making a career out of it.

http://www.youtube.com/watch?v=2KfJiWR1FPw

My conclusion is that an introductory programming course should therefore be short. I like Udacity CS101. It is nominally only 8 weeks at 5 hours of class time per week. It is self-paced and not on a fixed schedule. You may want to see my blog post: Is the Udacity CS101 Course Watered Down?

There are many possible ways to introduce computer programming. For example, you could pick a commercially important programming language, e.g. C or Java, and organize a course around learning that language. Or you could create/select a student language just for the students to get started with the concepts (Scratch, Logo, Basic, CUPL, ...) and teach that. I think Udacity CS101 chose wisely in picking a subset of Python. Python is a clean, powerful, multi-paradigm programming language that does see some real use commercially. Udacity CS101 doesn't visit all aspects of the language, but it does teach enough of it to give a good start at understanding the construction of computer programs. I believe it is much easier to get started in Python than in C or Java and that Python can carry you a lot further than Scratch, Basic or CUPL.

Another approach to introducing computer programming is to pick projects that are particularly attractive to students. Robots and computer games are two oft-mentioned examples. The parts and tools needed for a Robot-centered course call for a substantial investment ($10-$25 thousand per team is a working estimate I've seen on the web) and also requires comparatively large secure space to store the project, parts and tools. Real-time software that interacts with sensors and motors strikes me as more advanced material then a short introductory course should aim to cover. Games keep the work in the virtual world, so there's less need for parts and a workshop space, but interactive software with graphics is again, in my opinion, more advanced material that a short introductory course should aim to cover. Fair enough to stir into an introductory course a bit of foreshadowing to hint at how the material the course is covering can be extended to work in games or robots.

But I haven't any real experience teaching computer programming to students. I've been trying to launch such a course at the local community center here in the New Cassel section of North Hempstead, NY for well more than a year now, but it hasn't gotten off the ground yet. A shameless plug for yet another of my blog posts: Marketing the Importance of Programming Education. The comment thread on that article is, in my opinion, particularly worth reading.

A reminder: Blog sites such as this one are intended to be 2-way communication, not just reading material. Whether you are a student, teacher, programmer, experienced or inexperienced, you are invited to post comments about this article down below. Suggestions, counter-examples, criticism, pointers to other sites that said it better, and, of course, praise are all welcomed. Anything but spam.

Bicycles for the mind... A Steve Jobs talk from long ago.

1980

In the Introduction talk to Udacity CS101, Professor Evans mentions Steve Jobs having compared computers to "bicycles for the mind".

I think I've now stumbled across the talk where Jobs more or less said that. Run time for the Jobs talk is about 20 minutes. The bicycle reference is around the 6 minute mark in the Jobs video. Evans attributed the quote to circa 1990, but the talk is said to be from 1980, and given Steve's youthful appearance in the video, I believe the 1980 date.

Speaking of small errors, one of the annoying things in Jobs talk is he speaks of meeting with some 4th and 5th graders, but he then calls them 4-5 year-olds. I think 9-11 year-olds would be a lot closer to correct. 20 kids and 6 Apple computers? What a depressing student/machine ratio that would be these days!

Jobs mentions Visicalc in his talk like that is something that everybody in the audience knows of. But here we are some 30+ years later and I'm no longer sure that you all know what Visicalc was. Happily, Wikipedia remembers. Even if you remember Visicalc, I recommend that you visit the Wikipedia page. It has some wonderful interesting links, including one that lets you download a free copy of Visicalc for your x86 Windows PC. That version was written for DOS 1.0 so it only works within the current directory. DOS 1.0 didn't have directories, just disk drives. Most folks back then didn't have disks with any more capacity than a 5.25" floppy disk. In 1980, that would have maybe been 140KB of storage space.

One other link to particularly take note of is the one that asks "What if Visicalc had been patented?". If you haven't been paying attention to the arguments about software patents and why they are not good for the economy, you really should Google up some background reading for yourself, maybe sit through a Richard Stallman talk or 2 about "intellectual property". Be forewarned that Stallman's talk is a 2 hour talk, so take a bathroom break and get yourself a fresh mug of coffee, tea, or whatever before you fire up the Stallman talk.

If I'm going to mention Steve Jobs and Richard Stallman in the same blog post, it is probably appropriate for me to point also you to this short video where Stallman contrasts his own accomplishments vs. those of Jobs and of Bill Gates.

Time marches on, but progress?

Listening to Jobs 1980 predictions for what the heck we'd do with even more computing power, I can't help but be disappointed with how little real progress we've made on that front. The computing power has, of course, materialized as predicted, and I suppose the graphical user interfaces of Windows, MacOS and web browsers is something of a usability improvement compared to DOS 1.0, but I was sending e-mail and posting netnews items aplenty back in 1980 and it isn't like that process is hugely different today. To keep things in perspective, the Macintosh computer was introduced in 1984. Here's an early 1984 video of Steve Jobs giving a timeline leading up to the Macintosh. It's only about 7 minutes long and includes the famous "1984" teaser ad for the Macintosh; an ad still worth watching, in my opinion. Here's a 10 minute video of Steve Jobs actually introducing and demonstrating the Macintosh.

Still, if you have a problem that you want to solve with a computer, are the barriers to solving your problem significantly lower today or about the same despite the powerful GUI computers that are now available today? If there's an existing product that fits your needs ("there's an app for that"), your path is easy, but if you really need custom software, perhaps a custom database, I expect you still have a rough road ahead. "Cobol is to Visicalc as Y is to Z", but what are Y and Z?

Comparing the Python language to the programming languages of 1980 (C, PL/I, Cobol, Fortran) I guess there's some evidence of our having learned to apply plentiful compute power to making the programming job a little easier, but there's still a steep hill to climb to bring computers to bear on your problem, whatever your problem might be. The Internet, the World Wide Web and search engines seems to be the most evident signs of progress in the computing world since 1980. I do wish the world had more progress to show on reducing the barriers to applying computers to solve problems given the passage of 30+ years since that Jobs talk. Are there specific improvements in the computing world that I'm overlooking here and not giving proper credit to? Should smartphones get mention or are they just scaled down screens with battery powered small computers.

If I was better at HTML, maybe I could rig this article to provide background music as you read the previous paragraph. Or am I being too sentimental about lack of technological progress?

If you are completely unfamiliar with Stallman's contributions to the notions of "free software", you might give a quick read of a past blog post of my own as a way to get started at understanding software licensing and Stallman's GPL in particular: See "Copied Code or Unfortunate Coincidence".

06/11/2014 - Updated: The Steve Jobs talk link went bad! Why didn't anyone tell me with a comment so I'd know? Anyhow, I found a link that works (today).

Learn How to Program Computers!

Say What?

News photo of an experimental self-driving Volvo from Engadget report.

Computer procesors show up almost everywhere these days. Desktops, laptops, cell phones, processors embedded in cars, processors embedded in printers, embedded in cameras, embedded in dish-washers.

One thing that they all have in common is that someone (or some team of folks) had to develop a set of instructions to guide the computer to do whatever it is that it does. Those instructions are called programs, software, and the stuff that goes into a program is called "code", not to be confused with "secret codes", though there is a connection if cryptography is what interests you.

So, no matter what, you are pretty much fated to be a user of computer programs, but with some effort on your part, you can learn to write your own computer programs too. Creating a computer program is called "software development". You can learn to do software development on your own. I'll caution up front that seriously big projects generally are tackled by teams, not individuals working solo. But the longest journey starts with but a single step.

My intent here is to convince you that you should embark on the long journey of learning to program computers, to do software development.

Motive

There are plenty of reasons why you should learn how to program computers. Before you begin on that path, you might want to think about what your motive is. Are you hoping to write your own computer games? Want to understand Cyberwarfare before you are noted as a threat by Skynet? Interested in autonomous robots? Self-driving cars? Want to develop a fancy web site of your own? Thinking it might be a useful skill when seeking a serious job? Want to understand how the NSA accidentally intercepted calls from Washington, DC, when they meant to intercept calls from Egypt?

I can't tell you what motivates you. I will caution that this is no short trip, so you should probably be sure you are well motivated before you dive in.

I'll also mention up front that the early days of getting started with developing your own software can be frustrating. As you master the basics, a self-driving car may seem awfully far away. Part of my hope here is that I can convince you that if you keep your motive in mind, you can work through the steep initial learning curve.

Age restrictions?

In my opinion, there's no upper bound on the age when you can learn to program computers. If you are past retirement age, that might alter your own list of motives for learning, but it is no reason to refuse to give it a try.

Can you be too young to learn to program? Well, programming does generally involve reading and writing, so if you haven't gotten proficient at those skills yet, you may find it hard to get into software development. But then, how is it that you are reading this article? The US apparently has regulations that strongly discourage web sites from registering information for children under age 13, so if you are under age 13, it is important that you discuss your plans with your parent or guardian and have permission from them to get involved in online courses.

Cost?

If you have access to a computer with a good Internet connection, you probably have all that you need to get started. If you don't, then how is it that you are reading this article?

Of course, if you have money to invest in this project of yours, there are things you might want to look into. For instance, books. You can get plenty of materials for free here on the Internet, but sometimes it can be useful to have a paper document that you can bookmark, dog-ear, highlight and annotate. Don't feel you have to invest in books up front, but if you can find a good local book store, you may find that there are useful things to be found by browsing. Your local library may also be useful, though in my experience, the local library tends to be woefully short of current technical books. The good news is that if you can find titles worth looking at, perhaps from web searches of places like amazon.com, then most likely your local library can arrange an inter-library loan so you can examine the book without having to buy it first.

Of course, library books, including books borrowed on inter-library loans, need to be treated politely, not dog-eared, high-lighted and given marginal annotations. And they do have to be returned after a relatively short time. If you find a title that looks really well matched to your needs, that's where you just might blow your allowance on an order from an online book-seller, so you'll have a copy of it for your own. Amazon.com does have provisions for wish lists, sort of like bridal registries, so as you publically grow your list of titles you hunger for, you'll at least make it easy for folks thinking about getting you a birthday present or Christmas present.

Libraries can also be a great place for getting free public access to Internet-connected computers. You might find that there are administrative obstacles to your installing software development tools on the library's PC's, or even filters to protect you from the educational materials. Don't let those barriers stop you. Talk to the librarian to find out who is in charge of those kinds of filters. Most likely, arrangements can be made for good reasons like you have.

Courses?

There are many computer programming courses available on the Internet for free. "Massive Open Online Courses", MOOC's, featuring different programming languages and different levels of material. Some aim to serve particularly younger students. You might look, for example, for courses that introduce the "Scratch" programming language.

I haven't taken a "Scratch" course myself, so I'm not going to single out a specific suggestion here. Just try a simple Google search for:

    scratch programming course

and let us know in a comment which course you picked and why, and how that went for you.

But if you feel you are ready to learn a somewhat more conventional programming language, one that will take you further than I believe Scratch will, my suggestion is CS101 from Udacity.com, where you will learn to program using the Python 2 programming language.

The Python programming language continues to evolve. There are Python 3 versions available today. The world is still catching up to that. You'll be fine starting with Python 2, and learning the differences later on to get over to the newer versions. It is important that you know that there are multiple versions and that when you are shopping for books or tools that you get a version that matches what the course is expecting you to have.

There are other courses available, though I haven't tried the others myself. Certainly there are courses that teach Python specifically for game development. And there are plenty of courses that teach other languages, Java and C, for example. But in my opinion, CS101 from Udacity.com is a good place to start. It is free, self-paced, you work on it on your own schedule. Nominally, it is an 8-week course. It doesn't have pre-requisite other courses. I believe it is an excellent place to get started with MOOC's. There's a final exam at the end and when you pass it, they will e-mail to you a certificate to commemorate your accomplishment. There are reports on the web of real colleges that even give credits if you are a registered student and pass the Udacity.com CS101 course, but being a registered student at a physical college is outside the realm of stuff you can try for no charge.

If nothing else, trying a MOOC to get started will show you if this is a field that holds your interest. I know software development has been a long standing interest of my own, but I also know that some fraction of the students who try it find that they absolutely hate programming. If you find that's the case for you, my advice is that you tough it out to completion of the introductory course and then look for other fields that do hold your interest. It's only a couple of months to work through Udacity CS101, and it isn't anything like a full-time course load while you are working through just the introductory course. Getting the certificate isn't good motive to start the course, but perhaps it is a good motive to stick it out to the end.

Where to find more?

code.org is a web site that advocates that everyone should learn how to code. They offer 3 editions of a promotional video to promote interest in the field. One is a 1-minute teaser. Another is a 5-minute edition featured on their web site's front page. And if you have 10-minutes to spare, there is a full edition available.

There are links on the code.org site to various local places to learn to program. For example, there's a brief plug there for the "Yes We Can Community Center" here in Westbury, NY.

Details of the schedule are not yet nailed down for Fall 2013, but if you are local to here, one way to take on CS101 is to sign up with the Community Center. The Center has the computers and Internet access, and it will have other students so you won't feel too much that you are on-your-own. And, for what it worth, I'll be available to answer questions and help keep you motivated while you are working through the course online.

Not quite free, as there is a membership fee to sign up with the Community Center. But use of the basketball courts, game room and locker room and access to quiet study space for your homework time all come with that membership, so it's probably worth joining if this is your community. (Use of the fitness center is not included in basic membership. Sorry).

The schedule I've proposed is that Monday evenings we'd meet as a class to share discussion of progress and problems. Other school nights I'd be available to answer questions 7-9PM or by appointment.

In any case, you can try udacity.com CS101 on your own before we even get started and then continue at the Community center once we get our act together there. Please, do let them know at the front desk that you're interested in taking CS101 as seating is limited.

Free for Senior Citizens

If you are a resident of North Hempstead and are age 60 or more, you are eligible for free membership in Project Independence and get a free community center membership too when you join Project Independence. Such a deal!

Further reading

Benefits of Teaching Kids To Code That No One Is Talking About - This blog post by an online acquaintance of mine has an example of a Scratch program, and a link to a video of a talk by the creator of Scratch.

Is Udacity CS101 Watered Down - This is a blog post from me in December 2012, describing what you should expect to get out of the online Udacity CS101 course.

Where to Get Python - This is another blog post from me. This one describes how you can install Python on your own PC. Note that back when I wrote that, Udacity was still using Python 2.6, but the course has since updated it's software to Python 2.7. From an end-user point of view that's an almost imperceptible change.

There are numerous Youtube videos available about learning to program games. Here is Episode 1 of a series that is dozens of videos long. Part 1 shows off a couple of games the guy has written in Python and describes what prerequisite knowledge he expects you to have to get started with his tutorials.

This isn't the first time that I've written about plans for CS101 at the Community Center. For more details of my intended format for the weekly meetings, see my blog article: Marketing the Importance of Programming Education

MOOC's: Be careful what you wish for.

There's an old warning that you should be careful what you wish for, because you just might get it. Here's an article from the Slate "web magazine" cautioning that MOOC's are going to doom us all:

http://www.slate.com/articles/technology/future_tense/2013/07/moocs_could_be_disastrous_for_students_and_professors.html

Countering that point of view, the article does manage to provide a link to a TED talk by coursera founder Daphne Koller, speaking at Edinburgh in June 2012:

http://www.ted.com/talks/daphne_koller_what_we_re_learning_from_online_education.html (21 minutes)

Now my own experience is limited. I took Udacity's CS101 course last year. It has no fixed schedule and I worked on the course when time was available and did eventually complete it with 100% on the final exam. I've signed up for another couple of Udacity courses, but haven't managed to get around to finishing either. Home Internet outages and a few weeks hospitalized distracted me from sticking to it. Of course, with no fixed schedule, I can always return to those courses and get down to work on them.

Koller and coursera seem to put much more emphasis on a fixed schedule than does Udacity. For example, I've been taking coursera's Systematic Program Design Course and have to concede that I have not kept up with it's mandatory schedule of weekly homeworks and quizzes. Realistically, I have to concede I'll not be completing that course this summer and will have to try it again the next time it is scheduled. Not a bad course, but it does get tedious in its attention to microscopic details. I also got distracted with learning a new programming language (Racket) along the way. Too bad as the course was to have 2 peer reviewed assignments and they were to be my first experience with peer reviewed work.

I think the gloom and doom suggestions of the Slate article are a bit too Luddite a point-of-view for my taste. I think MOOC's will lead to a lot of change in education courses in the future. The MOOC courses will establish baselines which future improvements will have to beat. Koller emphasizes that the MOOC offerings collect a lot of data which provide the prospect of guiding future improvements. The one thing that I can see screwing up a bright future of continuous course improvement is if copyrights are used to restrict building a better course based on an existing course. U.S. copyright law has seemed to get repeatedly stretched with additional years to make sure Mickey Mouse, et al, never pass into the public domain. I can only hope that the MOOC courses stick to the tradition of Creative Commons licensing so that it is possible to found an improved course on an existing good course.

On a related topic, although Bill Gates is not a person that I often have praise for, in this 10-minute TED talk by Bill, he does a nice job of arguing that teachers need more feedback. A modest bit of technology, such as a video camera on a tripod, can give teachers a basis for self-assessment and the possibility for peer reviews.

http://www.ted.com/talks/bill_gates_teachers_need_real_feedback.html

Recursion

One of the interesting computer science topics that Udacity CS101 introduces is "recursion". Recursion is where you define a function in terms that in some cases require the function to call itself. This is the main topic of Unit 6 of the course. There are important design considerations to be taken into account if you are going to use "recursion" in your implementation of a function.

1. Base case(s) - It is crucial that your function have at least one combination of inputs that do not trigger yet another recursion. This non-recursive case is called the base case of your function. If you don't have at least one base case, then you are fairly certain to have an unending loop that never produces a final result.
2. Progress - It is similarly crucial that your function make progress toward the base case(s) as it recurses. If you have situations where sometimes the function re-invokes itself with the same inputs and state as it had previously, then it may be more subtle, but almost surely you are stuck in an unending loop that never produces a final result.

Not every programming language supports recursion. Cobol and Fortran for example traditionally do not. Some languages (e.g. PL/I) support it, but only if you declare that a specific function may be invoked recursively. ("PROC OPTIONS(RECURSIVE)"). Python supports recursion without any need to declare your intent to use the capability, but Python's support of recursion does not include "tail recursion optimization". Tail recursion optimization is where a language processor recognizes the special case that a procedure is being called recursively, but that when the procedure returns to the point of the call, there's nothing more to do than to return to an earlier call to this procedure. A clever compiler can transform the code for such a program to do a plain loop instead of a recursive call. Alas, in Python, there's much that cannot be known for certain about the code until run time. Guido Von Rossum, the creator of Python and it's "Benevolent Dictator for Life" (BDFL) has blogged about why Python doesn't bother to try harder for this particular case. See: Tail Recursion Elimination.

A key fact to note is that if you've got code with a tail recursion in it, then it is reasonably straight forward for you to restructure that code to explicitly use a loop in place of the recursion. It apparently is in this fact that Guido draws enough comfort to not bother trying to optimize the handling of this kind of code.

Some folks look at the limitation of Python's support of recursion and wrongly conclude that recursion is a feature of the Python programming language that you should avoid. Ned Batchelder did a great job of de-bunking that assertion in his essay: Recursive Dogma.

There are lots of interesting discussions of recursion in the Udacity CS101 forum. Much of the debate is over whether or not recursion is something easy or hard to get your brain wrapped around. Some folks find recursion is an elegant way to express a function while others opine that iteration is a more natural way to conceive of a function's processing. My opinion in this debate is that even if recursion provides a straightforward clean design for a function, do think through how to transform that design into an iteration. Compare the readability, performance and limitations of the 2 alternative designs and pick the alternative that makes the most sense for your needs.

Told You So - MOOC forum participation is important

If you have been a regular reader of this blog and have a long memory, you may recall that back in December of 2012, in my article "Is the Udacity CS101 Course Watered Down?", I strongly emphasized my opinion that a vital part of getting the most out of the course is to participate actively in the forum. As strong as my opinion on this matter was, it was just my opinion. But now I've got data to back me up.

John Duhring has posted to the Google+ STEM Community today a link to an article "Effective Habits of Power Users: A Look At Recent MOOC Research". The article reports on a study of the small percentage of folks who completed the MIT "Circuits and Electronics" course that edX offered as a MOOC in March 2012. About 155,000 folks registered for the online course and only a few more than 7,000 completed the online course and earned a certificate of completion. There was a follow-up study to see what distinguished the folks who made it to the goal line from the rest. The report says the level of participation in the forum is the big differentiator.

Many years ago when I was a college student, I had the pleasure of sharing housing just off-campus with other students taking many of the same courses as I was taking. We had marvelous arguments with each other as to what the professor really was saying in the lectures we'd attended. They were friendly arguments with much hand waving at speeds approaching C to explain space-time dilation and other such hot topics. I'm quite certain that those discussions were an extremely important part of going to a residential college and greatly increased my learning.

I've been watching my wife's kids slow progress as commuter students to a local college and I think part of the problem is that they come home right after class and so don't have any of the discussions that cement into the brain the material of the course lectures. MOOC's bring a similar handicap of splendid isolation of the students from each other, but the forum provides a way for them to virtually get together and have those opinionated arguments with each other through the keyboard (hand-waving is not useful on the forums so some specific verbal skills are called for. At least you are safe from flying meter sticks approaching the speed of light).

So, again, if you take a MOOC, do take the time to participate in the forum associated with the course. Remember what Radio talk-show host Barry Farber used to say at the end of each broadcast: "Keep asking questions!"

A Frequently Asked Question on the Udacity CS101 Forum

On the Udacity CS101 Forum, I've been surprised at the number of questions that were posted for quiz 2-18. For example there's this question: http://forums.udacity.com/questions/100057486/problem-with-is_friend-quiz?page=1&focusedAnswerId=100057509 and several many more that are much like it.

Now part of the confusion, I think is that when Python prints the string value "True" and prints the Boolean value True, there's no visible distinction between the 2 outputs. e.g.:

>>> print "True", True
True True
>>>

But I think it is perhaps worth noting that in the coursera course "Introduction to Systematic Program Design", there is strong emphasis in the course's "How to Design Functions" recipe on starting by writing down the function's "signature", the types of its inputs and of its outputs, which for quiz 2-18 would be:

# String -> Bool

(Mostly irrelevant is the detail that Udacity CS101 is working in Python 2.7 while the coursera course is working in "Dr. Ratchet", another programming language, and one that is new to me).

For as small a quiz as 2-18 is, and as often as similar questions have shown up in the forum, I think it is clear evidence that CS101 needs to add emphasis on function "signatures". It would also make sense to soup up the auto-grader for this problem to give more specific feedback if the function returns string values instead of the desired Boolean values.

For what it is worth, here's my answer to the question I cited in this article's opening paragraph.

I didn't actually run your code, but I see your function returns string values of "True" or "False". Python has special Boolean values of True and False (NB. no quotation marks). They behave in many ways like 1 and 0, but they are easier to read in the source code.

So, my best guess is that the autograder is looking for Boolean True and False, not the strings that you are handing to it. Further reading: Truthiness and Falsiness. By the way, the version of Python that CS101 is using has changed a little since I wrote that blog article last year. Also, be aware that None is another special value in Python.

How does Python identify the type?

In the CS101 forum, a student noticed that types significantly influence the computations in python, but that we generally don't declare types in Python. They wondered how this can be so.

In the speed of the light question,when the prof changed the value of 1 to a float value 1.0,the answer was much more accurate,i want to know , how and why in python unlike other languages,there is no need to define the type?

To see the original discussion thread, see:http://forums.udacity.com/questions/2001224/how-does-python-identify-the-type.

My reply to that question:

In Python, variable names have values and values have types. So if I say x=2, the type of the value of x is int. I can then say x="dog" and now the type of the value of x is string. Python knows the type of a literal in the source from the syntax (e.g. quotes to make something be a string value, or square brackets to make something be a list or curly brackets to make something be a dictionary. Number without a decimal point for an integer. Number with a decimal point for a float. At runtime, all the values of variables in memory have a specific type. Operations on those values therefore have methods that know how to work with those types (or an exception is thrown), and produce results of a specific type.

Python might not know what that type is until runtime, but hopefully the programmer knows what they meant to produce and gets it right. Other languages ("bondage and discipline languages") are much more demanding that all be declared at compile time, but then you might end up with a procedure that you'd like to use on an object in your program, but get snagged that although the object behaves like you need it to, it isn't the exact type that the procedure was coded to expect. Python says "if it walks like a duck and it quacks like a duck, then it's a duck" (Hence, "duck typing"). So if the object provides whatever operations are needed for the procedure, you're good to go.

Broad categories of types include orderable types for which lt and eq (comparison) operations are defined. Another broad category is "iterables". You can easily write a procedure in Python that'll happily operate on any type that meets the requirements of the procedure. e.g. if you can compare objects of the given type and decide how to put them into order (i.e. which is "greater" and which is lesser), then you can probably feed objects of that type to your sort procedure - even types that you created long after you wrote the sort procedure. If you write a procedure that takes an iterable, it can be written to be happy with a list or a file or a generator (a special kind of procedure that returns a value but that you can then resume to get the next value) - and the procedure can be happy as you apply it in amazing new ways.

That's one of the definite sources of the power of Python. This type freedom has its downsides too, such as there being surprisingly little that can be statically verified about a piece of Python code. At "compile time", Python doesn't really know what is going to happen at run time. If I was implementing a nuclear reactor control system, I think I'd feel safer writing it in Ada, not Python. But, most days I definitely am not writing nuclear reactor control software or anything that could seriously kill someone if it has a flaw. That sort of software puts a seriously literal meaning into the phrase "fatal flaw". For a reminder of how fatal a software flaw can be, see: An Investigation of the Therac-25 accidents.

Here's a highly technical talk related to this topic of types which I hardily recommend. Have a pad and pencil handy as you watch it and jot down things he mentions that you don't know about, then Google for more info on those words later. Dynamic Languages Strike Back. After you are more comfortable with those words, you might even want to watch the video again.

Copied code or Unfortunate coincidence?

My blog post today is another reposting of an item I'd originally submitted to the Udacity CS101 forum. This item isn't at all Python-specific. A student there wanted to know how code similarities are handled in the real business world. How to distinguish copied code from an unfortunate coincidence? If you'd like to see the original discussion thread, see: http://forums.udacity.com/questions/100049998/how-do-people-know-when-code-is-a-copy-or-just-an-unfortunate-coincidence?page=1&focusedAnswerId=100053997#100053997

My answer to the question was this:

There is a distinction between copyright and patent. I'm pretty sure that cleanroom techniques can be used to duplicate a piece of copyrighted code without getting into trouble. That is, the people who have seen the original code don't write the copy, but just pass the requirements and specifications through to people who never saw the original code. But if there is a piece of patented code, and you write your own code that inadvertently infringes on the patent, then you've got potential legal woes even though you didn't even know about the patented code. This is why there is such strong opposition to the notion of software patents. For example, see this article in Forbes or this blog from the Electronic Frontier Foundation.

It is also worth noting that not all copyright holders insist that you not copy their code. The GNU GPL license is a form of copyright that declares you are free to copy the code, but, if you do so, you need to make your modified version of the code freely available under a GPL license itself. The GPL is sufficently different from a typical copyright, that the slang term "copyleft" is often used for the GPL. The "contagious" properties of the GPL are fairly terrifying to companies that regard their code as proprietary secrets. If they inadvertently incorporate some GPL'ed code into their package, they might have a court declare that they have to release all that package's source code under GPL terms. The BSD license is different. As I understand it, BSD licensed code is free to copy without imposing restrictions on what you then do with your adaptation of the code. http://www.freebsdnews.net/2008/07/18/bsd-license-vs-gpl-license/

There are many different software licenses. If you have occasion to reuse a piece of code, be sure you know the license terms. Some licenses are incompatible with some other licenses, so it is possible to pick up code with incompatible licenses and produce a program that cannot legally be released. There are companies (e.g. Black Duck Software) in the business of helping folks track down the origins of their code to make sure it is properly licensed.

Robot Wars

Udacity.com CS101 has a unifying theme of building a web crawler and search engine as you learn Python. It's a well chosen project because it introduces HTML, and string processing and then segues into iteration, functions and recursion. As the index grows larger, data structures, hashing and the Python dictionary type are introduced, and improving the quality of search results gets some attention.

This article started out as a discussion thread in the CS101 "forum", but has been substantially re-worked and updated for this blog post. The original thread is here: http://forums.udacity.com/questions/100000043/robot-wars#cs101.

Having learned how to construct a web crawler in this course, I was amused in December to learn there's a company out there intent on protecting the web sites of their customers from being crawled. See: http://www.distil.it/the-dirty-secrets-about-robot-txt/#.ULo0_4c8CSo. A web site may post a robots.txt file on the root of its site to request web crawlers to stay out. But it's a request with no teeth. An ill-mannered or unscrupulous web crawling program might just ignore the robots.txt file and explore pages it was asked not to. The goal of Distil Networks is to block such crawlers. They don't say much about how they'd distinguish the web crawler traffic from real user traffic. Usage patterns, geographic location by IP address, that sort of stuff.

Well, I guess there's risk in publishing anything. IMHO, the web is for sharing information publicly. Hardly the right place to post anything you don't want others to see. The worry seems to be that if the info is too easily copyable by a crawler, that someone will duplicate your site and somehow profit from your work without compensating you.

Seems to me that a crawler that could alert you to duplicates of your page content would be useful. Of course, it would be pretty hard to do as the style wrapped around it could have changed so recognizing "your" content wouldn't necessarily be easy. It's a similar problem to those sites that do plagiarism detection in homework assignments.

Of course, if people are gathering up info from your site and not republishing it, but are finding a way to profit from the knowledge you shared, that seems fair. If they are spamming your customers, then maybe your site needs to keep customer contact info a bit closer to the vest. I believe there was an old business practice of salting confidential lists of customers with fake entries with phone numbers to trap any outsider trying to mine a stolen copy of the list. Similarly, I've heard tell of mapmakers putting some deliberate harmless error in their maps, so a copy could be recognized. Arguably, Google took somewhat that same approach to prove that Microsoft's Bing was copying Google search results. Microsoft, of course, strongly denied the allegation, but the matter did get the attention of even the Comedy Central cable TV network: http://mashable.com/2011/02/04/colbert-bing-google/.

Meanwhile, I think I see coming an escalating battle between sites and crawlers and expect I'll hate repeated interactions like captchas to see if I'm human, or complicated enough javascript tests to see if the query came from a real web browser, but slowing down the time to get to see the web content of interest and just raising the bar on how much like a browser the behavior of a web crawler needs to be.

To be fair, I freely admit that I have not tried the services of distil.it, so I have no real idea of how transparent their protections perhaps are, or any clue as to how easy is it for a sneaky web crawler to work around the restrictions. If you have any actual experience, good or bad, with such protections, please add some comments to this post to get the rest of us up to speed.

Curriculum Design with the End in Mind

As a person who enjoys reading, I'm heartened to see that interesting material about Education isn't limited to video's (e.g. TED talks). I was particularly impressed with this article from Grant Wiggins: "Everything you know about curriculum may be wrong. Really.". Thanks and a tip of the hat to Srdjan Verbić for sharing a link to that article on the Google+ STEM Community.

Wiggins points out that a curriculum is often conceived as an organized ordered progression from basics to advanced knowledge, but points out that to become a great soccer player, you don't plan to sit in long lectures about the rules and strategies of soccer. He asserts, quite convincingly, that the end goal of education today isn't to instill knowledge (heck, you can always Google up more facts on a topic than you're ever going to be able to remember anyhow), but to teach the students how to get things done in a field - to do things.

Once upon a time, it may have been the case that the world was sufficiently static that it might have made sense for a school curriculum to provide you with lectures on the basics, and work up to lectures on advanced topics, but in today's world, everything is changing so rapidly, that mastering the art of sitting through such a sequence of lectures and answering test questions at the end to demonstrate your knowledge of the lecture content is arguably akin to trying to use a classroom as the sole instrument to develop a soccer team.

I think he makes an excellent point. I'd like to believe that the interactivity of MOOC's is a shift toward a "how to get things done" approach vs. classroom lectures. One problem I see though is that if there is no clear progression from basics to advanced knowledge, how do you help a student progress from simple things to complicated things? Software development, for example, is a field where clearly there's a knack to being able to write software, but there is also a lot of background knowledge, (e.g. data structures, fundamental algorithms, development methodologies) that a teacher can't just assume the student will already know or can Google up as they need it. Seems to me that the shift isn't so much away from having to master increasingly complex stuff as it is a shift away from testing the ability to regurgitate explanations and instead to demonstrate application of the increasingly complex stuff. Udacity.com's CS101 final exam, for example, is open-book and you can revise your answers as much as you like, so if it initially doesn't pass one of their test cases, you can fix it. At least on the test I took in Summer, 2012, the problems weren't simply cloned variations of problems we'd done in class. I think that's a Good final exam in a programming course. I believe Prof. Evans and the Udacity staff should be proud of what they put together for that Introduction to Computer Science and Python Programming course.

The Good Eats television show is another example. It is a show that teaches cooking. The bulk of the run time in the show is filled with lectures and demonstrations about cooking, but you are encouraged to try things out yourself. The lectures aren't focused so much on recipes as on explanations as to why the recipe calls for what it calls for. What role does the ingredient or technique play in the recipe. I'm not much of a cook, but I find the show interesting, more so than other cooking shows where an attractive cook just demonstrates preparation of a dish. I'd like to believe that the lessons from Alton Brown on Good Eats have improved my skills in the kitchen. I did apply what he taught to prepare a turkey and the result was good. It helps that the recipes are available on the web, so you don't need to worry about the details as you watch the show.

Not clear how a less project-oriented field, say "History", maps to this "learn to do it" approach to education. Maybe it's just a bad attitude on my part, but it seems to me that History is an example of a subject where indeed the end objective is to be able to sit though long lectures and then be able to regurgitate facts at the end. If the objective is to draw broad lessons from history and write compelling, well-supported essays in support of change, I'm not sure how big a field the study of history would turn out to be.

Particularly, if you are in some other field than me (software engineer), I'd sure like to hear how you think a bias toward "learn to do" vs. "learn the facts" would change your curriculum. Do feel free to add comments to this blog post. Or add a link here to your own blog post if you have something more to say than fits comfortably into the relatively little slots provided for making comments.

Marketing the Importance of Programming Education

At the risk of sounding like Dr. McCoy complaining to Captain Kirk in the original Star-trek TV series, I'm a software engineer, not a marketeer. At my request, the local high school and local BOCES school have announced the availability of a mentored edition of udacity.com's CS101 at the "Yes We Can" Community Center here in the New Cassel section of North Hempstead, NY. My plan is to have weekly meetings of the class at 7PM, Monday, starting March 4, for a Scrum-inspired stand-up meeting where each student will say what they did on the course in the past week, and what they will do this week, and what impediments they see in their way. Other school nights I'll be available 7-9PM to answer questions and the students can put in whatever hours they want to at the community center or if they have the Internet at home, they can work on the course at home. Udacity provides little in the way of a "dashboard" for tracking the progress of the students in a class, so I'm hoping the Scrum-style stand-up meeting will enable me to track progress and figure out who needs extra attention. And, I hope it serves to persuade student's to live up to their announced plans and keep on keeping on. I've prepared a small set of slides to use at the first night's meeting.

But, as of Tuesday this week, the community center tells me no students have enrolled so far. I've nudged my contacts at the high school and BOCES school to see if we can get some students motivated to come check it out. My plan is to show up on Monday evening and bring a book to keep me busy if it turns out I'm there by myself.

Meanwhile, code.org, a non-profit has appeared on the Web to promote the proposition that Every student should have a chance to learn to code. To get people's attention, they've posted to YouTube an "all-star" video in 3 editions. 1 minute, 5 minutes and 10 minutes. What most school's don't teach.

If you've been following my blog here this month, you may have seen the video from Jörn Loviscach, "MOOC's and other faster horses" that I had linked to my recent post "Education and Technology". Loviscach is one of the udacity.com professors. He reported some scary statistics about how the MOOC's typically start out with hundreds of thousands of students, but a huge fraction (90%) typically drop the course. The classroom at the community center only seats about 12 students and even if I had an overwhelming demand for CS101, I don't think we could accomodate more than a Monday team and a Tuesday team. I don't want to get into a situation where we've overcommited the center's PC's so students who show up to work on the course can't get a seat. Bottom line is that unless I can influence that retention rate as part of my local mentoring of the class, I may not live long enough to see anyone actually complete the course. Hence my concern about "retention".

I agree that every student should have a chance to learn to code. Now if I can only manage to recruit and retain some students. I'll blog about how things go. So stay tuned, please. To paraphrase Scotty from Star-Trek, I may think of myself as a software engineer, but I'm a marketeer now. And if you know anyone in North Hempstead, NY, please encourage them to visit the Yes We Can Community Center on Garden Street and sign up for CS101.

Udacity Unit 4 - Index data structure

In Udacity.com CS101, Unit 4, the notion of data structures is expanded beyond simple strings and simple lists. In Lesson 4-7, the web crawler is expanded to be a function:

index=web_crawl(seed)

where index is the data structure that is passed to the web page finder to find pages based on keywords and "seed" is a URL where the web crawler should start its crawl.

One student asked in the forum "What is index to be?". Fair 'nuff question, and they specifically added they didn't want an answer that solved the quiz of unit 4-7, just to understand what is wanted. To see the original forum thread, see: http://forums.udacity.com/questions/2024862/unit-4-7-i-dont-understand-what-index-should-be#cs101

Here's what I replied:

The crawl_web function is supposed to construct the index data structure that your search engine will use to find web pages. Truth is that between 4-7 and the end of the course, there will be evolution of the details of that structure. I suggest you re-watch the earlier lessons in unit-4, especially 4-2.

I'm not sure I understand your notation in this question, but as a broad hint I'll tell you that the whole content of a web page doesn't belong in the index. crawl_web's job is to extract from the web pages the information that you'll need to again find the pages that are relevant to some search word. Think about the index of a book. Say you want to find mentions of eggplant in the book. The book's index is an alphabetized list of important words in the book and for each word gives you a list of page numbers where that word was mentioned. Web pages don't have page numbers, but do have URL's. So what you want from the index data structure is something that your search function can use to tell at a glance what the URL's are for web pages that mention the search term you are looking up. (eggplant, perhaps).

At this point in the course, there are only a small number of data structures to consider. There are strings and lists, and you can compose grander things (lists of strings, lists of lists, ....). You've seen that the content of a web page can be regarded as a big string. With a bunch of effort by your program, you can rummage through that string to find keywords and links (URL's). You don't want to have to go thru all that work each time you just want to look up eggplant, so the idea is to do the work once, and capture a summary in the index data structure of what you saw. Think ahead to looking things up. What kind of index would make that job easiest?

I hope that helps. A marvelous thing about Python is that a function is able to return as its result a large complicated data structure. Other languages would insist that a function can only return simple stuff, such as a number. If you find yourself forced to work in a more old-fashioned programming language some day, you'll have a deeper appreciation of Python's generous approach.

Zero, One, Many Rule of Thumb

In Udacity CS101, Unit 2 introduces functions, parameter passing and return values. Lesson 2-17 has us define a function bigger(a,b) that returns the bigger of the 2 values passed in. As in most of the lessons in the course, they pose a question, have the student work the problem and then explain an answer.

One student noted that her answer was slightly different code than the answer that the instructor gave and asked on the forum if there was any reason one was better than the other. To see the original question and answer thread, see: http://forums.udacity.com/questions/2009058/unit-2-lesson-17-alternative-solution-not-longer#cs101

Now if there's one thing I can't resist, it's expressing opinions on a couple of little scraps of code, and defending my choice. Here's what I said:

I liked his "if a>b: r=a; else: r=b; return r" version better than your "if b>a: a=b; return a" version because even though the procedure doesn't change the passed in value of a, and isn't meant to change a out in the calling procedure, the code as you wrote it can easily be mis-read as doing something to the first parameter. Better to introduce local variable r so there's no need to waste a neuron on wondering if the procedure is changing anything in the caller's variables. Better, in my opinion, to leave the parameters passed in as read-only unless there's real reason to alter them. But my habits were formed working with languages that have different parameter passing rules than Python has. Only clear reason to stick with my habits that I can see is what if you had occasion later to add more code to the procedure and wanted access to the passed in value of a? If the code treated a as "read only", there's no chance of a bad surprise.

I actually preferred the "return a; else return b" version because it dodged the need for a short lived local variable. It's one drawback that I can see is that it isn't so obvious how to extend the code to handle more values such as a, b, c, and d. But at some point you probably should think of having a list of values and not a whole bunch of variable names. I was reading recently that code should be written to handle 0 cases, exactly one case or "many cases". Comparing a & b is one case, comparing a, b, c (and d) is clearly more than one case. Instead of coding for 2 cases and then for 3 cases, look for a way to generalize it to handle the "many" case, such as a loop to pick the biggest element out of a list of arbitrary length. But only do that if you have to handle more than one case. Generalizing the code before there's an actual requirement to do so is likely not time well spent. Zero, one, infinity rule is a decent summary, though where I saw this recently was Tim Ottinger's "Agile in a Flash" blog (Simplify Design with Zero, One, Many Rules). I can still find the article in Google reader, but as for rustling up a URL to it to share here, I'm having no success at that whatsoever. It's like the blog has lost track of that article.

Addendum

Well, better late then never. Google searching again today for that blog article found it. I also stumbled into a Wikipedia article that indicates that design rule predates that blog post by years. Alas, it's one of those "[citation needed]" Wikipedia articles that doesn't back up its information with a reference.

Judging Code Quality

Unit 3 of Udacity.com CS101 introduces functions. One of the more challenging homework problems at the end of that unit was problem 3-8. Given a purported solution to a sudoku puzzle, represented as a list of lists, the assignment is to write a function that determines if the offered solution is valid. The function is to return True if the puzzle solution is valid, and return False otherwise.

One of the students was less than delighted with his solution. His function worked, but he wondered if it was Good Code or Bad Code? Some folks responded that the offered routine was too long, and that made it Bad Code. To see the original question and answer thread, follow this link: http://forums.udacity.com/questions/2024970/is-this-considered-bad-code#cs101

I tried to give a more nuanced answer to the opinion question...

Good code is largely a matter of opinion, which is not to say I don’t have opinions. John’s point about the length of the procedure is a valid point. I’d also argue that clarity could be improved by better choice of variable names, or at least comments explaining what each variable represents.

len(length) set off alarm bells in my head. Looking at the routine, I gather “length” is the list of lists that makes up the sudoku puzzle. Again, a better variable name or a comment would make things easier to read.

In the end, the acid test is “does your program work?”. If I can make it fail with a test case, surely, you’d have to accept that the code has a problem. The ease or difficulty of correcting things is then a valid basis for judging if it’s Good Code or not. That isinstance test to screen out floating point numbers in the data worries me. What does it do if you hand it a different data type, like, say, a complex number? If you eventually arrive at a program that handles every test case I can think of, but the code bristles with odd tests to avoid problem X, Y and Z that we discovered, that still is probably not Good Code.

My version is already posted to the forum with some other sudoku question, so I won’t repost it here. My approach was to generate a list of all the integers that would be valid in a row. (e.g. for a 9x9 puzzle, any valid value should be in the list [1 2 3 4 5 6 7 8 9]. As I matched a value to the list, I’d delete that value from the list so if it came up again in the same row or same column, I’d reject the duplicate as invalid. For each row and each column, I freshly repopulate the list of valid integers.

One aspect of my code that I wasn’t completely happy with was that my code for checking of rows largely duplicated the code for checking columns. “Don’t Repeat Yourself” (DRY) is good guidance for writing Good Code.

One other area where I think my code could use improvement is I had no explicit test to make sure the puzzle data was square (length of each row exactly matching the number of rows). Would be easy to patch that in.

http://www.pearltrees.com/#/N-u=1_391422&N-p=61027473&N-fa=3462050&N-f=1_5113795&N-s=1_5113795 is my collection of links to web pages pertaining to the topic of writing good code. The “Principles of Good Programming” pearl there is probably a good place to start reading.

If the wit and wisdom of the xkcd comic strip appeals to you, you might enjoy: http://xkcd.com/844/. If you’ve read this far and are enjoying my answer, you might try a Google search for:

code smell

to find tons more to read to help you better discern the answer to the code evaluation variant of the question posed to Dorothy soon after she arrived in the land of Oz: “Are you a Good Witch or a Bad Witch?”

And if I still haven’t convinced you that your code could be better: Consider how terse the results from your code are. Suppose your code became widely popular and you get a support call from some distant timezone at an inconvenient hour. The user says “I asked your program if my sudoku puzzle was valid and it said False. What’s wrong?”. Good Code would have precluded the need for that support call, or at least have told the user exactly where to look to find the problem. They might call for support anyway, but such is life.

Want to enrich your book shelf? Well, an Amazon search for books with Brian Kernighan as an author is a good start. The Elements of Programming Style by Kernighan and Plauger and The Practice of Programming by Kernighan and Pike are ones I highly recommend, though neither is specific to Python. Alas, putting the books on your shelf without reading them doesn’t do much good. (Full disclosure: I had the enormous pleasure of working with Kernighan and Pike a while ago). NB. there’s no shame in picking up a used book to save some money. Someone else’s highlighting and marginal notes might even add value.

Best wishes to you on your journey to learning “How to Write Good”. Exposing your code for review by others is generally a Great Idea. Pay attention to the comments and suggestions that come back, even the comments that you don’t like. The comments and suggestions may turn out to be Bad, but do take your time maturely considering the feedback before you arrive at that conclusion.

Addendum

Since posting that answer, I've established a Pearltree about "Code Reviews". I believe code reviews are the best way to check for quality of the code that goes into a project. Sadly, management of developers often is unwilling to invest the resources needed to take the time to review the code their team is grinding out. An article in that Pearltree that I especially enjoyed is this lament over the sorry level of code quality that is so typical in the commercial world.

I confess that, so far as I know, no one else has expressed serious code-review suggestions regarding my sudoku routine. Specifically, nobody ever pointed out that my procedure suffered the same code-smell of being too long for one Python procedure. And, sadly, nobody has explained to me how I can cleanly reuse the same code to check rows and check columns. Transposing the matrix data seems like too much work, so that isn't the solution to my DRY worries. Please share in the "comments" here if you see a way to eliminate the repetition or have other suggestions for improving my version of how to solve this homework problem.

Why don't we use a bucket for every keyword?

As I explained in my first 2013 blog posting, Udacity.com's CS101 course has a project running through it where you learn to program by building a web crawler and a search engine. The web crawler builds a data structure that the search engine then uses to find web pages. The initial implementation does sequential searches to find keyword matches in the data structure. Around unit 5 of the course, the scalability problem of that approach is pointed out, and hash tables are introduced as a more time efficient way to search for keyword matches. Hash tables have N "buckets" and a hash function that assigns any given keyword to a bucket. Sometimes, more than one keyword will hash to the same bucket so the hash table implementation has to know what to do with such collisions.

One student reasoned that if N buckets cuts down the search time to find a keyword match, that it would be even faster to allocate a separate bucket for each keyword. That question appears here: http://forums.udacity.com/questions/2025239/why-dont-we-make-a-new-bucket-for-every-keyword#cs101

So I explained why in my forum response:

Underneath it all, the computer memory is addressed numerically - the first storage location is numbered 0, the next is numbered 1 and so forth. Each storage location in the computer's memory typically can hold one character, so a string is a sequence of storage locations. If you set up a series of entries, each with a fixed length, and want to access the Nth entry, given the starting address of the series in memory, the length of the entry and N, it is a simple matter of arithmetic to compute the address of the Nth entry. But if you want the address of the entry for keyword "Eggplant", how do you map that string to a particular address? A hashtable is one technique. We treat the underlying representation of the letters in the string as numbers and run them through a function that computes a number that falls into a range (the number of buckets). The exact details of the computation can vary from one implementation to another, so long as the same result comes out for the same keyword each time for the same hash table.

Just now, for fun, I wrote a little program to tell me what 'Eggplant' works out to if you look at its underlying bits as a single number. In decimal that works out to: 5,139,324,068,239,476,530. 'Eggplant' isn't even a big word. How many buckets are you prepared to bring to the party? So we need a technique that'll reproducibly map that down to a number in a more convenient range and that's what we call a hash function.

There are other possible approaches than hashtables. b-trees, for instance. But that would take more explaining then I think would fit comfortably in this forum. In the end it all comes down to determining a numeric address that corresponds to the entry you seek.

There are programs that given a fixed list of words will create a "perfect hash function" - one with no collisions for the given words. Not applicable to the web search engine project, because the list of words isn't know-able in advance, but suppose you were writing a program to process Python programs. There is a fixed set of language keywords (if, else, print, def, ...) and an open-ended realm of possibilities for variable names. So a perfect hash to make it easy to look up the keywords might be useful, but the variable names will have to be handled separately.

So there are many ways to organize and store a collection of information. The amount of work to add an entry to the collection, the work to look up an entry and the space to store the collection vary with different techniques. Requirements vary, so good programmers need a large bag to hold all the possibilities they might pull out to apply to whatever problem. There are books where such things can be looked up and library modules often save you from having to reinvent things from scratch. Python embodies a tremendous long history of techniques and makes it look easy. Hurrah for progress and not needing to do pointer arithmetic. Indeed, even lists of variable length strings are pretty amazing when you think about what that involves behind the scenes.

Some day you may learn some less evolved programming languages such as C or assembler language where the underlying hardware is more visible to you. Nice place to visit, but keep your ruby slippers handy to take you back to the ethereal world of Python when you're ready to leave the registers and instruction codes behind. Layers and layers of abstraction, all of it know-able, but if you try to think at the machine code level all the time, you won't be very productive when working on some higher level problem.

The user gave my answer a "thumbs up" vote and "accepted" the answer as resolving his question. Valuable karma points. At least it made me feel I'd helped the guy out.

Approval for CS101 at the Community Center.

As I explained in my late November, 2012, blog posting, I liked Udacity CS101 enough to propose a mentored edition of the course for the new North Hempstead "Yes We Can" community center, here in my neighborhood. The idea is to offer the free CS101 course with the added value that the community center provides the PC's and Internet that folks need for working on the course, and the students get my presence, so they have someone to turn to for help if they get stuck on any points of the course. The challenge for me will be to recruit and retain students. I don't just want to get people to start CS101, I want them to complete the course and earn the certificate that Udacity offers to folks who pass the final exam. I've drafted up a brief course description. Professor Evan's video (linked earlier in this paragraph) may be better marketing than plain old text on paper, but a snazzy video is hard to leave in the hands of a school administrator as a souvenir of a meeting with me.

For more about what I hope people will get out of CS101, see my early December blog posting about CS101. I really hope that the course will influence some kids into taking the prospect of college more seriously, and to maybe even consider a possible major in computer science. Of course, it is easiest to remember your goal is to drain the swamp when you are not waist deep in alligators, and the approval for offering CS101 at the community center only came on 12/21/2012, the day that the schools let out for Christmas vacation. (It was last July that I proposed this program. It just took a while to win consent from Parks and Recreation, the folks who run the center). So, as of this writing, I have not met with the high school administration to discuss how to recruit students for the class and can sit around with high hopes. "Nothing but blue skies...". Even though I know reality is dead ahead and I'm closing in fast.

My plan is to have once/week class meetings of the whole team (Monday evenings). I can slip a little of my own material in to those days. We'll start each of those sessions with a Scrum-inspired stand-up meeting where we'll ask each person to briefly state:

1. Who they are.
2. What did they do last week (lessons, and forum activity).
3. What do they plan to do this week.
4. What obstacles are hindering their progress?

The stand-up meeting is short and we don't try to solve the obstacles during the stand-up meeting, but I hope the meeting will help people connect if someone has a problem and someone else has a solution. If there are consistent problems heard, that'll be my clue to perhaps try to explain something in class. The other "win" from this meeting is it gets people to commit to what they aim to do that week. Scrum-methodology calls for a daily stand-up meeting, but I'm uncertain we could get everyone to show up at the community center every evening. So, I am aiming to do weekly meetings on Mondays.

For the first session, I've prepared a set of slides to give people an overview of what to expect from the course. I'm hoping that first session will get people to commit to sticking with the class for as long as it takes (and as it's nominally an 8 week class, it isn't a particularly long term commitment).

I've given some thought to what we might want to cover in class on other weeks. I hope the CS101 videos convey the technical material well enough on their own, so the sorts of things I'm thinking I might need to add are:

1. Goal setting.
2. Time management.
3. Good work habits. Note taking, minimize distractions. Maintaining a balance between work and play.
4. The value of participating in the forum. Why take the time to help other people out?

Other school nights, I plan to be available in one of the tutoring rooms in the community center from 7PM-9PM. If anyone wants to see me on weekends, they'll have to make an appointment with me. The center is across the street from my home, so it's not going to be a hassle commuting to there.

If you have ideas on ways to improve the wrappings I'm suggesting for Udacity's CS101 course or thoughts on how to recruit students for that course, I'd sure like to hear them. I'm expecting we'll need January to work out a few technical issues (like the community center's overly restrictive firewall) and to get out the word about the class. I hope we'll be able to start the mentored course offering in early February.

The course is free, but membership in the community center is required to use the center's facilities. If you live in North Hempstead, NY, please consider signing up to take CS101 at the Yes We Can Community center on Garden St. in New Cassel.

Dictionary Implementation

In Udacity CS101, the unifying thread of the course is construction of a web crawler and search engine. Without making much of a point of it, the initial implementation involves a simple list and linear search. Then, the scaling problem of that approach is pointed out, and the course explains hash tables as a more time efficient way to store searchable data. After we'd rolled some of our own hash tables, the course goes on to introduce Python's dictionary data type - Hash tables as an inherent part of the language.

One of the students asked in the forum how dictionaries were actually implemented. How does Python know how many buckets to allocate for a dictionary? To see the original question see: http://forums.udacity.com/questions/2015065/dictionary-and-hash-table. I looked into the matter and posted this reply:

There's a book from O'Reilly called "Beautiful Code". Chapter 18 of that book describes the Python dict implementation in detail and the web has positive things to say about that chapter. Alas, the book is not freely available, unless you have access to a good technical library from which you can borrow the book. My local library isn't particularly technical, but they can do interlibrary loans from distant university libraries to get what I need, so long as I'm patient. Ask your librarian for help.

Or, if you are feeling ambitious, take advantage of the fact that Python is open source, so you can look at its innards to your heart's content. Python dictionary implementation (in C). As George Lucas had Obiwan suggest: Use the source, Luke.

The most common Python implementation is Cpython, an interpreter implemented in the C language. But there's a somewhat more experimental implementation called Pypy, an interpreter implemented in Python. I speculated that with a little rummaging around, I ought to be able to find Pypy's implementation of dictionary's, but close as I found was some documentation on Pypy's dictionary optimizations. There are tons of bitbucket.org/pypy pages for Pypy source, but I didn't actually find the Pypy code that you are asking about. Feel free to show me up on locating the routine of interest to you.

Concerns of Real Search Engine Developers

Concerns of Real Search Engine Developers

Udacity updates the course material from time to time. A unifying thread that ran through the course was development of a web search engine. Some while after I'd completed working through unit 6, they added a set of Q&A sessions. Q&A 6-6 is here: http://www.udacity.com/view#Course/cs101/CourseRev/apr2012/Unit/676073/Nugget/674085

Q&A 6-6 is a discussion of the current concerns of real search engine developers.

After viewing that clip, it occurred to me that a major concern of real search engine developers hadn't been included. That led to an exchange of e-mail with the professor, and at his request, I posted that exchange to the CS101 forum.

The original forum thread is here: http://forums.udacity.com/questions/2025563/concerns-of-real-search-engine-developers#cs101

Here is what I posted:

I sent some e-mail recently to Professor Evans:

I just stumbled upon Q&A 6. I guess you guys added it since I'd already completed chapter 6. Q&A 6-6 about what are the challenges for search engines these days could use a little expansion. A major challenge that I don't think you mentioned is how to keep the search engine attractively useful while also figuring out how to make a buck. A recent discussion on facebook started out with a friend mentioning he'd recently purchased some fresh turmeric root and was wondering what to do with it. I suggested he just Google for:

turmeric root recipe

and pick what he wanted from there. I even pointed to a specific page that was early in the search results and looked like a good answer to his question. But the thread degenerated into a lot of gripes about how Google clutters things up with ads, and wishing that someone would do better. Not sure if Facebook will block you from accessing it, but here's the URL for that thread: http://www.facebook.com/barryshein/posts/10151255645449313 That discussion is now up to 54 replies. Clearly a topic about which people have strong opinions. (To be fair, Barry's friends probably are more geek- inclined than a random sample of the population would be. As evidence I offer 2 examples of search terms mentioned in the gripes:

microinverters

double walled heat shrink tubing

).

Prof. Evans graciously replied:

Thanks, Drew. Yes, there is definitely a lot more that goes into this, and a lot of things lead to conflicts between commercial interests and good search results. DuckDuckGo seems to do pretty well on these searches.

Happy to have discussion on this in our forums.

Best,

--- Dave

I'm happy to open the matter up to forum discussion as he suggests. How are the search engines doing, in your opinion, at balancing the interests of providing good search results (to keep us users happy) vs. making a buck to keep the lights on (and the stock-holders happy)?

Addendum

The posting stirred up much less controversy on the forum than I'd expected. Sentiment among the CS101 students who bothered to respond seemed to be that Google was doing a decent job of balancing promotional info and search results, and that DuckDuckGo was a comparatively weaker search engine.