Theory & Rationale
One of the earliest and most famous efforts to expose people, particularly young children, to programming is LOGO—a programming language and environment created by Seymour Papert. LOGO was designed to be used with a constructionist curriculum. It was designed to allow kids to engage with Big Ideas on their own terms and allow them to have a personal stake in their learning. In 1983, Pea identified a group of language independent "bugs" that novice programmers, regardless of age, often made. Unfortunately, LOGO does not address any of these issues and suffers from same issues as any text-based programming langues.
In 2000, George designed and tested a visualization tool called EROSI that allowed learners to "see" the recursion to help them with comprehension of recursive solutions and problem solving with recursion. The method they used was to create graphical representations of the flow of control passing from one function to the function that it called. It improved students understanding of recursive algorithms and flow-of-control.
Finally, in 2007 Jacob and Horn developed two tangible programming languages, TERN and Quetzal. Both of them used wooden jig-saw puzzle like pieces as the programming primitives. Quetzal was designed to control a robot made of Legos. Tern was designed to control a small robot on wheels. While their goal was educational, to date there have been no studies exploring the learning benefits of a tangible programming language.
The are also a multitude of other resources that I have not yet had the chance to explore: Boxer, Scratch, Squeak, Topobo and Smalltalk.
An existing practice in the current education of programming that is is worth keeping is an emphasis on homework assignments being programming assignments where students apply their knowledge to a problem.