Talking to computers, revisited

Back to our old friend Fibonacci, poised precariously between human conversation and computer programming. The more I think about the Fibonacci sequence as a way in to the question of a lingua franca for introducing people to ideas about how to program, the more intriguing it gets.

In this post I’m going to write things mathematically, foregoing the wordy english versions, since I think we’re all agreed that the concepts are what ultimately matter here, not the syntax. Once we’ve worked out the best conceptual approaches, then we can go back and make things more “natural-language friendly”.

One question that comes up is how soon you should introduce variables. When you say:

    F(n)   ←   if   n ≤ 1   then   n   else   F(n-1)+F(n-2)

you are assuming your student is ready to understand and use variables like “n”.

In contrast, here is a description of the Fibonacci sequence without variables, stated as two “production rules”:
    F   ←   [ 0 , 1 ]

    F   ←   F   append   Flast + Flast-1

This doesn’t just return a number – it builds the whole sequence. Is this approach conceptually clearer and more intuitive? Is it closer to the way people already think?

6 Responses to “Talking to computers, revisited”

  1. Doug says:

    Maybe the most natural way is programming by example? After all, when you explained the Fibonacci sequence to us, you gave the example of the first few steps before you gave the algorithm.
    I’m not sure how you could compose them to form more complex programs, but I think it might be the right direction.
    I’ve tried to teach my son (who is 6) variables and fractions. He is simply not able to hold the idea of a variable in his head yet. I think it is too abstract. But I can teach him fractions by giving him lots of examples.
    He made up and wrote down his own rules for Monopoly today.

  2. Dean says:

    It might be closer to the way some people think, but your first post might be closer to the way others think, what is the ratio, I don’t know.

    It is suggested the way most people learn additional (spoken) languages is through memorization, repetition and correction by fluent speakers. One can learn the grammar (conjugation, etc), but it doesn’t stick until practice and correction by other fluent speakers. Most beginners speak the second language words using their native language grammar and phrasing; it takes time to learn to think and then speak in the second language. I once spent a year learning Russian in college, but after a summer in the CCCP, I came back a significantly better speaker, for a variety of reasons; through hearing (examples), speaking (repetition) and being corrected (memorization).

    I see the same thing in my Computer Science students : They first learn by doing lot’s of little programs (repetition and memorization), then after some time, they learn to “think” in the language. Then, when they go from, say C++ to C#, they program C++ using the C# syntax, it takes some time to learn to think in C# and use it appropriately. You must be familiar with the phrase, “He can program FORTRAN in any language”, seems applicable. I understand you aren’t talking specifically about learning computer languages, I’m trying to use a specific example as an analogy, if that is possible.

    Whenever I’m introducing Recursion using the Fibonacci sequence, some student will mention, “you know, you can use a recurrence relation to solve it directly.” The student sees that I’m trying to solve the Fibonacci sequence because they first learned recurrence relations, it hinders them from seeing that I’m actually teaching Recursion, not the Fibonacci sequence; I have to stop and remind them Recursion is the topic, not Fibonacci. This brings up the issue of how knowledge of one language/subject hinders learning in another.

    We have this ongoing discussion in our dept, much like others, about how to do a better job of introducing programming concepts to students, not only in our program, but also to elementary, middle and high-school students. Lot’s of ideas come and go, but I always fall back to the above, memorization, practice and correction by fluent speakers. In your previous post you mentioned the concept of Computational Thinking, that appears to be the new hot kid on the block, I’ve been hearing it bandied about more and more recently.

    Well, I could go on, have already wandered around too much as it is, I do find your discussion an interesting one, have been mindful of it for many years, have no universal solution, only opinions :)

  3. andras says:

    I wish there were ways to practice programming without programming. For instance Is there a Lewis Carroll story that tells the tale of =, == and === in a way that makes the concepts seem perfectly natural and intuitive?

    Also, I wish that there was a way to practice programming that didn’t require syntactical precision. I want to practice the concepts and enjoy the magic of coding the way a baby gets to crawl and babble while learning how to walk and talk (I’m told I was a prodigy at babble 😉

    Maybe programming can only be learned as precisely stated mathematical language. But how to bring that precision in line with the analogies and metaphors of the math of daily life? I just took a class at UCLA that required me to study some basic coding. As I tried to make the magic work it was as if it was just beyond the tip of my tongue.

    I wish you luck in finding better ways to bridge the gap between the way people and computers think. If anyone can do it it’s you.

  4. Ashley says:

    Sadly, I think that “objects” with state that mutates as the result of operations actually is close to the way people think about the world. But, humans have a difficult time keeping track of the state in a complicated process in this case; the main reason programmers need debuggers. I think the way you represent it above as a recursive definition that can be understood inductively without “walking” through the process is absolutely the best way to program! How to reconcile the two world views? Very hard problem indeed!

    As for getting rid of variables, I think that concatenative languages are very cool, or a so called “point free” (some would say “pointless” :-) style in other languages is very interesting. It’s then easy to talk about the “process” directly rather than walking the “flow of variable names”. It can lead to very succinct definitions. For example, in Haskell “scanl” already defines the general process of applying a function while walking a list and threading an accumulator through, producing a list of all the intermediate results. We can then say that the Fibonacci sequence is really 1 followed by applying addition (+) and threading through the total sum (starting with 0) as we go. No mention of any variable names, “fibs = scanl (+) 0 (1:fibs)”

  5. Marc says:

    I think the second one is more intuitive, potentially because I can imagine preforming the algorithm in real life, since it is constructive. What’s a simple way to describe a variable? Maybe a bag that can contain a certain number of oranges? Start with two bags, one with 0 oranges and the other with 1 orange. Count how many oranges you have in both bags, then make a new bag with that many oranges. Then discard the oldest bag. Keep going…

  6. Johannes says:

    @andras: I agree that having to worry about syntax is annoying and difficult for beginners. Good IDE’s really make a difference, but I think there’s still a lot of room for improvement, mainly when it comes to visualization.

    I think Mark is on the right track…

    In Eclipse, you instantly see if there’s something wrong with your code, errors in your code are instantly highlighted on the screen. This way you can react to those “events” that take into account the semantics of your code. Another really great feature that some editors ( e.g. Notepad++) have is that if you select a word ( e.g. “myVariableName”) all the other instances of that word light up. This way you get an instant visual feedback on where that variable is used. But that’s just the beginning.

    I think that in the future we will see more and more of these improvements. I already got used to the two mentioned above. Another visualization I’d love to see is some kind of marking of types … E.g all strings would be orange, all integers would be green,
    that code blocks would be in a shape reflecting their purpose. This way a program would become something colorful and cool that is fun to build, like a house of legos or something like that. When I think of a program, I think more of a machine of thoughts than a sequence of words. If the environment in which we create software would reflect that, more people would like to play with it. Why is Flash so successful? Because it’s very easy to build visual things. Yeah you could do it as a JavaApplet but no one did. I’m not a big fan of visual programming, because so far it just doesn’t work very well. I do think that visualizations that happen while you’re typing code are extremely powerful… I imagine something like this: A split screen , on the left side you type the code. On the right side, as soon as some part of the code makes sense you see a possibly animated visualization of what the code does.. Maybe bags and oranges?

    Another thought:
    I just realized that when I’m coding, I use google as a translator between a English problem description and a bit of code. This works really well for most common problems. Sure, there are some manual steps involved … But essentially you ask “how can I calculate the fibonacci series in java” and you get back the code. Except for a little copy and pasting and adjusting, you have the solution thanks to the collectively shared knowledge. As long as the smart guys keep coming up with algorithms and publish them online, everyone will be able to make software, simply by uttering the problem into a search box and assembling those modules..

Leave a Reply