Tuesday, May 19, 2009

Teaching Functional Programming To Kids

I started teaching some of the basic concepts of functional programming to my 8 year old son yesterday, and wanted to write a little about it. The wonderful thing about it is that kids really are ready to learn the concepts at a very young age. I'm not actually teaching him programming, just concepts, but when the time comes, he'll basically already know how to program.

I have what I think is an absolutely perfect example. It's one that all parents and kids can identify with: The Dr. Seuss Star Belly Sneetch machine.




This is a simple machine that takes in a Sneetch without a star on its belly, and spits out a Sneetch with a star on its belly. I'm just going by memory here to say that I think kids can probably understand this concept at the age of 3. In this post I'm going to use this style to represent machines:

-----------
| |
Sneetch ---> | * | ---> Star Bellied Sneetch
| |
-----------

This is the same as the actual picture above, but works for all cases since I don't have pictures for all the concepts I want to represent.

In the Dr. Seuss book there is also the opposite machine that removes the star from a star bellied Sneetch.

-----------
Star Bellied | |
Sneetch -> | -* | ---> Sneetch
| |
-----------

While that seems really simple, it's all we need to start teaching a wide range of concepts to kids. I started with this one, because of its similarity with the machines above (for all the things below, Jacy and I worked them out on a whiteboard. But, paper is just as good):

-----------
| |
10 ---> | +5 | ---> 15
| |
-----------

Here we have a machine that adds five to whatever you put into it. Very simple, very easy for kids to understand. It helps to run a few more inputs through (0, 10, a billion) just to let them know that the box doesn't just take 10 and give 15, it works with all numbers.

After this one I followed up with another very easy one.

-----------
| |
10 ---> | -5 | ---> 5
| |
-----------

At this point he pointed out, "Well it could be a divided by two machine instead." This was unexpected, and impressive, and at some point I'll talk about it further...but not yet. It was great to feel that he was understanding it though.

Now that he was getting it, it was time to change things up just a little bit. I introduced the plus and minus machines, which take two inputs instead of one.

-----------
7 ---> | |
| + | ---> 19
12 ---> | |
-----------

-----------
12 ---> | |
| - | ---> 5
7 ---> | |
-----------

These presented no challenge whatsoever. In fact (I guess rather surprisingly), nothing I taught him presented any sort of challenge. Next I introduced the biggest and smallest machines (which we programmers call max and min).

-----------
7 ---> | |
| Biggest | ---> 12
12 ---> | |
-----------

-----------
7 ---> | |
| Smallest | ---> 7
12 ---> | |
-----------

-----------
10 ---> | |
| Smallest | ---> 10
10 ---> | |
-----------

I guess he was a bit surprised when I showed him the last one. But, it only took showing him the answer once for him to fully understand.

I then added an equals machine that spits out YES! if the two numbers are equal, and NO! if they aren't (true and false, obviously). This is different because now we were no longer working with numbers as the inputs and outputs.

-----------
7 ---> | |
| = | ---> NO!
12 ---> | |
-----------

-----------
7 ---> | |
| = | ---> YES!
7 ---> | |
-----------

Simple, but effective.

Now, Jacy and I have done considerable work with logic gates, and I wanted to show him how logic gates are really just like machines. I also taught him the word Function at this point, but didn't push it. Kids can relate to machines, not functions.

------------
ON ---> | |
| AND GATE | ---> OFF
OFF ---> | |
------------

------------
ON ---> | |
| OR GATE | ---> ON
OFF ---> | |
------------

------------
ON ---> | |
| AND GATE | ---> ON
ON ---> | |
------------

While the logic gate examples seem simple, it tied two worlds that we've been working on together very nicely.

Fun


My son has a really short attention span, and all the while I'm doing this I have to think of different ways to make it fun. If it's not fun, hes just going to go play video games. Rightfully so, video games are fun. There were a few ideas I tinkered with before settling on the Dr. Seuss machine. One was a monster that stuffs stuff into his mouth and then spits out the answer. I thought that one was kind of neat. The point is, if you plan on teaching your child, think of something fun they can relate to.

Combining Machines



I could sense we needed some more fun at this point, and we'd learned enough basic machines that I thought it would be great to start combining them. After trying this, I recommend starting with all alike boxes. We did something a little more complicated and I ended up going too fast, and fell back on this:

-----------
7 --> | | -------
| + | --> 19 --> | |
12 --> | | | |
----------- | |
| + | --> 39
----------- | |
10 --> | | | |
| + | --> 20 --> | |
10 --> | | -------
-----------

After you get this first larger machine done, its pretty easy to add in more complicated machines. However, it might be good to wait until the next day, as Jacy was definitely getting it, but might have been getting a little fried. Here's an example though:

-----------
7 --> | | -------
| + | --> 19 --> | |
12 --> | | | |
----------- | |
| = | --> NO!
----------- | |
10 --> | | | |
| + | --> 20 --> | |
10 --> | | -------
-----------

And obviously, change the 7 to an 8 and get a YES! Different kinds of boxes doing and spitting out different kinds of things. In essence, this is really all we do as programmers.

Types


Being a lover of static type systems, I also talked to him about types, by saying "kind(s) of things". For example, I asked him, "What kind of thing does this machine take in (or what kind of thing do you put into this machine)?"

-----------
| |
10 ---> | +5 | ---> 15
| |
-----------

Answer: Number. I avoided Integer for now. What kind of thing does it spit out? Answer: Number.

I then showed him this next example, which should arguably have a section of its own:

-----------
| |
D ---> | +5 | ---> I
| |
-----------

This machine looks exactly the same as the machine above, except you put Letters into it, and it spits out letters. We also did months. Both are interesting because they have to loop around. I didn't have to teach him that, he just got it.

Then I introduced a formal notation for types:

-----------
7 ---> | |
| + | ---> 19
12 ---> | |
-----------

(Number,Number) -> Number

And introduced machines that change the type (he had seen it already, but only with YES! and NO! This, I think, is a better example):

-----------
| |
5 ---> | To Letter | ---> E
| |
-----------

Number -> Letter


He understands the notation and can write it if I give him slots to fill in like this:

______ -> ______

or

(______, ______) -> _______


Things I don't know how to teach, Yet


I certainly didn't try to teach him anything about machines that take in machines and spit out machines. Also, some of my boxes were polymorphic, but I don't think I know how to explain that to him.

For now, I think Jacy and I will just do this same stuff for a while, reinforcing it. I'm not sure what the best thing to teach him next is. Some of the stuff here I've skimped on writing up, and we actually spent more time on than it seems.

Anyway, this was all really, really fun, for both of us.

48 comments:

  1. You have the beginnings of an outstanding book here on how to teach logic and programming concepts to kids. I would love to see you develop it further and publish it.

    ReplyDelete
  2. Excellent stuff. As I was reading about the boxes, I was thinking that you could use ? marks in either outputs or inputs to perhaps teach forward-chaining and backward-chaining rules, i.e. deduction and induction. Might even be able to slip Sherlock Holmes into the mix.

    Functions == machines == rules.

    ReplyDelete
  3. @tupshin Thanks! I'm glad you liked it. I'm sure I'll be doing a lot more of this work as Jacy continues to grow up. I'm not sure if it would be publishable as I only have one kid to base my data on. Also, I need to learn more about functional programming first! However, I'd certainly be willing to collaborate with anyone on pushing this further.

    ReplyDelete
  4. @moon Thanks too! Maybe you could draw up an example of the question marks/chaining? Also, unfortunately for me, I never read any Sherlock Holmes. Maybe you can enlighten me.

    ReplyDelete
  5. Excellent! I think I would next go to composability: define a machine by chaining machines. Chaining is possible when one machine has the same kind and number of outputs as the next one has inputs. Then it's easy to tell what inputs and outputs the new machine has, based on the first and last sub-machines.
    "Smallest+5" = "Smallest" ~ "+5"
    Something like that!

    ReplyDelete
  6. I'd go with a high order functions (machines?) next. I can't format this here. I'll use this representation:

    7, 12 -> [+] -> 19

    That's the first two inputs example, ok? So, I suggest this:

    7 -> [Even] -> false
    7 -> [Odd] - true
    12 -> [Even] -> true
    12 -> [Odd] -> true

    [Even], 7, 12 -> [filter] -> 12
    [Odd], 7, 12 -> [filter] -> 7

    [+5], 7, 12 -> [map] -> 12,17
    [-5], 7 12 -> [map] -> 2, 7

    [Biggest], 2, 7, 12 -> [reduce] -> 12
    [Smallest], 2, 7, 12 -> [reduce] -> 2

    I'd place the machine input coming from above or below, to distinguish it from the other inputs.

    ReplyDelete
  7. This is really really well done. Now I just need a child to teach this to ;)


    Btw: Your comment system does not work on an Android Phone...the Drop Down list is empty.

    ReplyDelete
  8. This looks a lot like math homework my 7 year old is already doing. Just sayin'

    ReplyDelete
  9. My kid would hit your kid with an axe in the face!

    ReplyDelete
  10. Nice post, Jack.

    I teach functional programming to slightly older kids (a small liberal arts college), but I have taught computing concepts to younger ones, including my own, on a less formal basis.

    I had a paper called "Tips for Teaching Types and Functions" in last year's (2008) FDPE workshop which gives some ideas that Jacy might appreciate soon: one is a way of printing and manipulating finite functions concretely in Haskell (including higher-order ones); another is a graphical/pictorial way of representing function types. (The last involves Curry-Howard stuff and is probably a little too advanced.)

    Anyway, if you're interested, let me know in the comments and I can try to get a copy to you.

    Oh, as an aside, I definitely approve of the use of Dr. Seuss in explaining FP concepts: do a google search on seuss & monad to see my own take on this. :)

    ReplyDelete
  11. Your diagrams really remind me of LabVIEW. Maybe you could teach him how to write simple programs with it.

    ReplyDelete
  12. robotics is far easier way of teaching kids computer science without them knowing it. Take a look at scribbler bit made specifically for kids. It also has a visual programming language.

    ReplyDelete
  13. I don't know if you're familiar with Scratch, but its a great way to get kids familiar with general programming concepts like loops and logic statements in which you develop a program to animate various characters. Its a free downloadable program developed by MIT. (scratch.mit.edu) Though its a little complicated to get the hang of at first, if you play around with it a little first you should be able to help your son figure it out!

    ReplyDelete
  14. @fritz - thanks. im definitely interested. :)

    as far as dr seuss goes, some people on reddit are mad that the machine modifies the input. i tend to think that they are missing the point - captivation of the childs mind.

    ReplyDelete
  15. @ankur: do you have a link? i'd appreciate it. i found this: http://www.parallax.com/tabid/455/Default.aspx, but i want to make sure.

    ReplyDelete
  16. @justin - thanks. i'll take a look at labVIEW. though it looks like its not free, and possibly complicated. i only looked for a second.

    ReplyDelete
  17. @michele - scratch looks awesome! thanks.

    ReplyDelete
  18. I have done something similar here:

    http://geocities.com/dcblaha/timezero/TimeZero.htm

    ReplyDelete
  19. Hmm... I hope you're aware that you're also giving your son the beginnings of a strong mathematical foundation! Be careful, you never know what he might accomplish with something like that. Good for you. I wish my parents had done something like that with me; for me it was just workbooks on arithmetic I had to work from before I went out and played...

    ReplyDelete
  20. Wonderful post. Your approach immediately made me think of the first chapters of "Common Lisp: a Gentle Introduction to Symbolic Computation". If you haven't checked it out, it's freely available on the web and might provide inspiration.

    ReplyDelete
  21. Your post got me thinking about how one could write an app to create/connect machines and inputs in JavaScript (because kids like video games more than paper - just the world we live in I suppose).

    Looks like something already exists...
    http://www.lilyapp.org/about/

    ReplyDelete
  22. Nice so far, but it seems you are just introducing combinatorial elements and not sequential ones (EE student here so forgive me if my terminology is different). So I thought up an way to introduce memory elements - the simplest possible one is a machine that would store the input, then give the last input as an output when you input something else into it.


    So, suppose the machine starts out holding a zero. You input a 5, and get a zero. Then you input a 6, and you get a 5.

    For a finite state machine you use three machines - a state register, a next state decoder, and an output decoder. The next state decoder takes any inputs and the current state and uses them to figure out what the next state should be, the state register just holds what the current state is until the state needs to be updated, and the output decoder decides what gets output based on the current state and (optionally) the inputs.

    ReplyDelete
  23. @ Jack: as usual with these bloggy things, I can't find your contact info (I guess that's intentional).

    Anyway, my email is (for better or worse) easily found by googling my name: send me a note and I'll get you a copy of the paper.

    ReplyDelete
  24. Have you seen Microsoft's Small Basic?

    It's designed for people learning to program including kids and adults.

    Just Google:
    Microsoft Small Basic

    ReplyDelete
  25. Be careful, you might end up teaching kids ascii art instead.

    ReplyDelete
  26. I think you could bridge to machines that create machines by first teaching variables using the (?) symbol with sets of machines. Kids know (?) represents an unknown, but can be confused if letters are introduced poorly; school will do that badly soon enough. Then you have:

    (?) := +

    5 --> [?] --> 8 --> [=] 13
    becomes

    (?) := { +, -, * }

    8 --> [?] --> 5 --> [=] { 13, 3, 40 }
    then

    (?) := ^2 +

    4 --> [?] --> 5 --> [=] 21

    ...err, my example is a little messy, but I think variables will get you where you want to go. Also, it looks like you have great intuition on this so you can clean it up if you like the direction.

    Great Job :)

    ReplyDelete
  27. Actually I kinda screwed up my examples, but the ideas there...

    ReplyDelete
  28. When you get to monads let me know. I figure that maybe an explanation that works for an eight year old can help me.

    Or maybe I'm having so much trouble because I'm NOT an eight year old.

    ReplyDelete
  29. There is a way to teach programming in high schools that is similar to how you have been doing it, though with fewer number-based exercises and more image composition exercises. You want to look at DrScheme and the book How to Design Worlds.

    ReplyDelete
  30. Jack,

    The reddit folks should not get so mad about the Dr. Seuss example. You aren't creating a machine which is modifying its input. No, you are creating a machine which returns a Sneetch in the Star Bellied monad!

    ReplyDelete
  31. Iteration! Recursion! These are things your budding programmer should learn, and are the basis of most programs. Recursion is obviously a difficult concept to understand, but with the right metaphor, you should be fine!

    ReplyDelete
  32. Dood, great post. You really have something here... the basis for a kids book or a cool iphone app, maybe? Stick with this.

    ReplyDelete
  33. seems no one has mentioned Alice yet so check this out: http://www.alice.org and there's a 12 minute walkthrough on the same site here (see 2nd video): http://tinyurl.com/3a9ru2. good stuff.

    if we're talking teaching "programming" then wouldn't examples exploring data, decisions and loops cover it pretty well at this level instead of arithmetic? your boxes, the Dr. Seuss reference, etc. all work for those 3 topics: say data are the sneetches, boolean is hasStar? and loops is lotsa sneetches gettin' stamped. could be introduced gradually, ie. not in one sentence like i did here.

    ReplyDelete
  34. just another thought ...

    and if we're talking teaching "how to think like a programmer, engineer, scientist, etc" then is it helpful to get so specific, or does it give too much weight to the abstract when, in the end, all we really want is control over our environment?

    natural curiosity and experimental method go hand in hand when you're around kids. i'd challenge us as adults to do something kids think is freaky neat then trick them into learning something while we have their attention. say robotics, as Ankur suggests above, or, along the same lines, instructables.com, makezine.com, etc.

    there's some ridiculous stuff you can do for under $0.50 like LED Throwies http://tinyurl.com/28u44v

    ReplyDelete
  35. Great idea!
    This kept my 5-year-old occupied for 2 hours tonight.

    Some observations:
    The sneetch star-on and star-off machines were a great introduction.

    We also tried a mama-making machine:
    Gracie -> [Mama] -> Mama
    Daddy -> [Mama] - Nana
    etc

    It is fun to run in circles yelling "Type mismatch! Type mismatch!" when you try to put a number into a sneetch star-off machine.

    Apparently, a 5yo has a concept of type coercion, because (according to her):
    2 -> [Mama] -> 3

    Some novel functions she came up with:
    Dirty Dishes -> [DishWasher] -> Clean Dishes
    Food -> [Dog] -> Poop

    Dual inputs can be done with colors:
    Blue ->
    Yellow -> [Mixer] -> Green

    Rhymes are fun, but have amgiguous outputs. We argued about which is correct:
    Grace -> [Rhyme] -> Face
    Grace -> [Rhyme] -> Chase
    etc.

    This ambiguity can be resolved by introducing state (ack!) into the machine (a machine that remembers). For example, re-use the first letter of the last transformation:
    Bat -> [Rhyme] -> Cat
    Tall -> [Rhyme] -> Ball (re-use the B from Bat)
    Hop -> [Rhyme] -> Top
    etc.

    Projection is not allowed:
    "What happens if we put one machine into the slot of another machine?"
    "That's silly, Daddy!"

    All in all, lots of fun.

    ReplyDelete
  36. The great thing about teaching kids this sort of thing is they don't ask you why they're learning it. They can just have fun with it. I am in college and I see that while students may eventually get interested in their classes in programming, they seem afraid to have fun while they are supposed to be learning. I guess it is the idea that school should be a "job" or serious and stern and not about enjoying the process of learning.

    I wish we had this available in schools.

    Thanks for the article!

    ReplyDelete
  37. Reading through all of these comments, I noted the one that the Reddit dudes are complaining about about the Sneetches being stateful. One is tempted to dismiss them as pedantic twits, but for two things,

    1) Eventually in the Dr. Seuss story we have a race condition the situation breaks down, not only because the Sneetches run out of money, but also because they can no longer remember who was who.

    2) We see a comment like @Thrustvectoring who wants to introduce stateful memory as a machine, which is a FUNDAMENTALLY different thing, and breaks down the whole metaphor of a machine as a function.

    ReplyDelete
  38. One thing I thought about reading this. For trying to teach about 'machines that create machines from other machines', you can start with the idea of a machine that takes in e.g. a number and creates a machine out of it. e.g. a machine, that given a number, returns a machine that adds that number to any input. This seems like an easily understandable stepping stone, and could also introduces the concept of closures.

    You could then bring in the concept of a machine that 'composes' two other machines together, creating a machine that 'contains' both machines wired together somehow, as the next step.... and you'd probably have to discuss polymorphism at this point too....

    ReplyDelete
  39. Excellent post. Really good stuff there.

    If you want to learn a little more about functional programming, I'd highly recommend How To Design Programs: An Introduction to Programming and Computing.

    It's a book targeted towards an introductory audience (not quite kids, but designed for high school computer science students). Great book, though, and available online for free. It makes use of the Scheme programming langauge, and concentrates on functional programming.

    I wouldn't give it to a child on their own, unless they were truly a genius at programming, but I think you could work through a lot of it with a child and get a lot out of it.

    ReplyDelete
  40. Great stuff! You've inspired me to get around to uploading Squarrows, which is a set of similar materials, although coming from a different perspective, that I used successfully with a group of 9- and 10-year-olds a year ago.

    ReplyDelete
  41. @cjh who said "...you are creating a machine which returns a Sneetch in the Star Bellied monad!"
    Oh, no! Another one of those darn monad tutorials. I guess not really... just a Star Bellied monad unit. return :)

    ReplyDelete
  42. Wow. So many nice comments, its really hard to keep up!

    And, so many software suggestions...phew. I will take the time to get to them.

    I also found this to be very nice: http://joshblog.net/projects/logic-gate-simulator/Logicly.html

    ReplyDelete
  43. @Askatasuna you're right! i looked at that book and it is almost exactly the same. thanks! it gives me a lot of material to teach him.

    ReplyDelete
  44. @Mitch Blevins - the type mismatch thing is great. :) we had some fun with that today. since we were dealing with machines, it was easy to pretend the machine had an alarm. the alarm goes off on a type mismatch.

    ReplyDelete
  45. Good stuff. I tried teaching my daughter w/ Logo, but it went nowhere. You were wise to start without the computer, which in my experience got in the way of the actual lesson.

    ReplyDelete
  46. Have you tried a machine that takes a number and outputs another machine (just simple currying), and after that a machine that takes a number and another machine that takes two numbers, outputting a specialized machine that takes one number?

    It seems to me like using this approach higher order functions are simple concepts, the distinction between function application and the function as a value is very clear with a physical metaphor.

    ReplyDelete
  47. For metafunctions, don't use machines that take numbers as inputs! Talk about something more concrete. like:

    motorcicle -> BigFactoryMachine -> MotorcicleReparingMachine

    plane -> BigFactoryMachine -> PlaneReparingMachine


    then you can use the created machine:

    brokenMotorcicle -> MotorcicleReparingMachine -> FixedMotorcicle

    ReplyDelete
  48. Blogs are so informative where we get lots of information on any topic. Nice job keep it up!!
    _____________________________

    Politics Dissertation

    ReplyDelete