Teaching & Learning

Scratch: Programming for All

Mitchel Resnick, John Maloney, Andrés Monroy Hernández, Natalie Rusk, Evelyn Eastmond, Karen Brennan, Amon Millner, Eric Rosenbaum, Jay Silver, Brian Silverman, Yasmin Kafai, Scratch: Programming for All, Communications of the ACM, vol. 52, no. 11, November 2009.

When Moshe Vardi, Editor-in-Chief of CACM, invited us to submit an article about
Scratch, he shared the story of how he learned about Scratch:

A couple of days ago, a colleague of mine (CS faculty) told me how she tried to
get her 10-year-old daughter interested in programming, and the only thing that
appealed to her daughter (hugely) was Scratch.

That’s what we were hoping for when we set out to develop Scratch six years ago. We
wanted to develop an approach to programming that would appeal to people who hadn’t
previously imagined themselves as programmers. We wanted to make it easy for
everyone, of all ages, backgrounds, and interests, to program their own interactive stories,
games, animations, and simulations – and to share their creations with one another.

Scratch is the cover story of the November 2009 issue of CACM. The goal of Scratch is to get kids programming so that they become more fluent in information technology, and develop "computational thinking" skills. Scratch is a graphical language based on a collection of “programming blocks” that children snap together like Lego blocks to create programs. The programs themselves appear to be imperative in nature (at least based on the samples in the CACM article). Programs can be made concurrent by creating multiple stacks of blocks, and the authors claim that their goal is to make concurrent execution as intuitive as parallel execution.

Scratch was previously mentioned on LtU here.

State of the art C compiler optimization tricks

A survey about state of the art C compiler optimization tricks, Felix von Leitner, Linux Kongress 2009.

The introduction and the conclusion is quite well put:

  • Optimizing == important.
  • But often: Readable code == more important
  • Learn what your compiler does

    Then let the compiler do it.

  • If you do an optimization, test it on real world data.
  • If it’s not drastically faster but makes the code less readable: undo it.

That's certainly something that I agree with 110%. And really, that's why a good compilers course is so important, even if the vast majority of students never write a compiler outside of class.

Safe Garbage Collection = Regions + Intensional Type Analysis

Safe Garbage Collection = Regions + Intensional Type Analysis, by Daniel C. Wang and Andrew W. Appel:

We present a technique to implement type-safe garbage collectors by combining existing type systems used for compiling type-safe languages. We adapt the type systems used in region inference [16] and intensional type analysis [8] to construct a safe stop-and-copy garbage collector for higher-order polymorphic languages. Rather than using region inference as the primary method of storage management, we show how it can be used to implement a garbage collector which is provably safe. We also introduce a new region calculus with non-nested object lifetimes which is significantly simpler than previous calculi. Our approach also formalizes more of the interface between garbage collectors and code generators. The efficiency of our safe collectors are algorithmically competitive with unsafe collectors.

I'm surprised this region calculus hasn't received more attention or follow-up discussion in subsequent papers. It seems eminently practical, as it replaces the more complicated alias analyses required in other region calculi, with garbage collection of region handles; seems like a huge improvement over general GC, assuming region inference is sufficiently precise.

Verified Programming in Guru

Verified Programming in Guru is a tutorial introduction to Guru:

GURU is a pure functional programming language, which is similar in some ways to Caml and Haskell. But GURU also contains a language for writing formal proofs demonstrating the properties of programs. So there are really two languages: the language of programs, and the language of proofs.

In comparison to Coq:

GURU is inspired largely by the COQ theorem prover, used for formalized mathematics and theoretical computer science, as well as program verification. Like COQ, GURU has syntax for both proofs and programs, and supports dependent types. GURU does not have as complex forms of polymorphism and dependent types as COQ does. But GURU supports some features that are difficult or impossible for COQ to support, which are useful for practical program verification. In COQ, the compiler must be able to confirm that all programs are uniformly terminating: they must terminate on all possible inputs. We know from basic recursion theory or theoretical computer science that this means there are some programs which really do terminate on all inputs that the compiler will not be able to confirm do so. Furthermore, some programs, like web servers or operating systems, are not intended to terminate. So that is a significant limitation. Other features GURU has that COQ lacks include support for functional modeling of non-functional constructs like destructive updates of data structures and arrays; and better support for proving properties of dependently typed functions.

The tutorial is worth a read to anybody new to this style of programming as it is one of the most gentle introductions to dependent types and automated program verification that I've seen.

A Functional I/O System (or Fun for Freshman Kids)


A Functional I/O System (or Fun for Freshman Kids)
, by Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, and Shriram Krishnamurthi. ICFP 2009.

Functional programming languages ought to play a central role in mathematics education for middle schools (age range: 10­-14). After all, functional programming is a form of algebra and programming is a creative activity about problem solving. Introducing it into mathematics courses would make pre-algebra course come alive. If input and output were invisible, students could implement fun simulations, animations, and even interactive and distributed games all while using nothing more than plain mathematics.

We have implemented this vision with a simple framework for purely functional I/O. Using this framework, students design, implement, and test plain mathematical functions over numbers, booleans, string, and images. Then the framework wires them up to devices and performs all the translation from external information to internal data (and vice versa) -- just like every other operating system. Once middle school students are hooked on this form of programming, our curriculum provides a smooth path for them from pre-algebra to freshman courses in college on object-oriented design and theorem proving.

This is a paper explaining some of the technical underpinnings of the How to Design Worlds curriculum that the PLT group has worked on.

I was tempted to categorize this as "functional", but decided against it. One of the really nice features of this curriculum is actually its applicability to imperative programming. Here, students are taught to think of interactive programs as functions written in world-passing style, and to specify programs in terms of the invariants that the function maintains on the world data.

That is: students are taught about loop invariants, without ever having to write an explicit loop. In my experience, loop invariants are the most difficult part of explaining Hoare logic (and hence of explaining imperative programming), because they require imagining a dynamic picture of what the static source code will eventually do. This style of teaching helps to manage that difficulty by making the dynamic state into visible animations.

Programming Made "Simple"

The Simple programming language is a BASIC dialect for the Android platform highly influenced by Microsofts's pre-dot-NET Visual Basic.

In the 90s, a big company from up north was extremely successful with a dialect of the programming language BASIC (acronym for Beginner's All-purpose Symbolic Instruction Code). One of the reasons it was so successful was that the language was easy to learn and use.

Bringing an easy to learn and use language to the mobile world and the Android platform is the goal of the Simple project. Simple is a BASIC dialect for developing Android applications. It is particularly well suited for non-professional programmers (but not limited to). Simple allows programmers to quickly write Android applications by using the components supplied by its runtime system.

Similar to its 90s relative, Simple programs are form definitions (which contain components) and code (which contains the program logic). The interaction between the components and the program logic happens through events triggered by the components. The program logic consists of event handlers which contain code reacting to the events.

Oh no! Animated Alligators!

Lambda calculus as animated alligators and eggs. Virtually guaranteed to turn any 4 year old into a PLT geek.

The non-animated game was mentioned previously on LTU here.

MitchFest 2009: Symposium in Honor of Mitchell Wand

I'm pleased to announce that we are planning a celebration for Mitch Wand's 60th birthday!

From the MitchFest home page:

Northeastern University is hosting a special Symposium in celebration of Dr. Mitchell Wand's 60th birthday and honoring his pioneering work in the field of programming languages. For over 30 years Mitch has made important contributions to many areas of programming languages, including semantics, continuations, type theory, hygienic macros, compiler correctness, static analysis and formal verification.

After receiving his PhD from MIT in 1973, Mitch taught at Indiana University where he and colleague Daniel P. Friedman wrote the first edition of their seminal text, Essentials of Programming Languages. Described by a reviewer as "so influential that the initials EOPL are a widely understood shorthand," the text is now in its third edition from MIT Press. Mitch joined the faculty of Northeastern University in 1985 and has been a leader in the College of Computer and Information Science. In 2007, Mitch was inducted as a Fellow of the Association for Computing Machinery.

Please join us at Northeastern on August 23rd and 24th as we celebrate this personal milestone and pay tribute to a great computer scientist, researcher, teacher and colleague, Dr. Mitchell (Mitch) Wand.

LtU regulars will recall that we've discussed DanFest 2004 here before, as well as the talk videos.

MitchFest is open to the public and coordinated with Scheme Workshop 2009, which will be at MIT on August 22nd (the same weekend). More event information, including registration, is available on the MitchFest home page. Following the Symposium, we will be publishing a special edition of HOSC as a Festschrift in honor of Mitch.

We will post a schedule on the web site soon, but for now you can view the preliminary list of papers in the Call for Participation.

Update: added link to HOSC.

Why Did M.I.T. Switch from Scheme to Python?

Daniel Weinreb has a short investigative piece about why MIT's well-known 6.001 course based around SICP and Scheme has been replaced with Python:

I’ve been seeing mail and blog postings, particularly from people in the Lisp community, why MIT has switched from using Scheme to Python in the freshman core curriculum for the department of Electrical Engineering and Computer Science.

At the International Lisp Conference, Prof. Gerry Sussman gave a short impromptu talk explaining the new freshman curriculum. Just to get a second opinion, I later called Prof. Jacob White, one of the designers of the curriculum and lecturers for the core courses. He confirmed Gerry’s description.

Asking why they changed languages is, in some sense, the wrong question.

Also discussed previously on LtU here.

Project Euler

Ran across a short weblog entry on Leonhard Euler, the father of functions and initiator of much in the way of number theory. The mention of Project Euler caught my eye, as I rather like projects that involve multiple PLs attacking the same sets of problems.

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems. The motivation for starting Project Euler, and its continuation, is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.
Project Euler has been around for almost as long as LtU but this is the first I'd heard of it. I find the questions and the competitive gaming aspect to be interesting, though I have a long way to go (level 2 out 5). Not sure there is a direct tie into PLs, but since I'm using it to learn more math and investigate the breaking points and elegance of PLs... and anything involving multiple PLs in competition and mathematics can't be too far removed... and since I haven't posted a story to LtU in a while and this happens to be my current interest... well, that will have to suffice. I'll have to admit though that many of the solutions I looked at are either too rushed (brute force), too cumbersome (indexes flying everywhere) or too terse. But that's true of most code that I run across (including my own). Still hoping for a PL that has that just right aspect - though I'm leaning to Oz these days.

(For those of us that are looking for walk-through/cheat guides, the Haskell wiki has the code to the first 200 problems, and I've put my Oz code for the first 50 up on the CTM wiki).

XML feed