Noulakaz

The blog of Avinash, Christina, Anya and Kyan Meetoo.

Education

Creativity in Programming

By 5 Comments

I’ve just started teaching a new module today to second year Computer Science students. It’s the Programming Languages module where students are supposed to be exposed to alternative paradigms and programming languages.

Today I had a lab session with one of the group of students and, as lecture hasn’t started yet, I asked them to write a number of moderately challenging C++ programs for me to make sure they were competent programmers. Those students studied the imperative portions of C++ during Year I and object-oriented Java during the first semester of Year II so I expect them to be able to complete the lab sheet.

Just for fun, here are the problems I’ve asked them to solve. I’m sure most of you will find them relatively easy but, remember, the point is to make sure everyone starts with (more or less) the same grasp of imperative programming.

Problem 1 – Two kinds of Fibonacci

Write a program in C++ that prompts the user for any non-negative integer n and displays on screen the times required (in seconds) to calculate fib(n) both recursively and iteratively.

(I told the students about the C time() function)

Problem 2 – Generation of numbers

Consider the following algorithm to generate a sequence of numbers. Start with an integer n. If n is even, divide it by 2. If n is odd, multiply it by 3 and add 1. Repeat this process with the new value of n, terminating when n = 1. For example, the following sequence of numbers will be generated for n = 22:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for every integer n. For an input n, the cycle-length of n is the number of numbers generated up to and including the 1. In the example above, the cycle length of 22 is 16.

Write a program in C++ that prompts the user for any positive integer n and displays on screen (i) the sequence of numbers generated for that n and (ii) the cycle length.

(This is a slightly modified version of a real ACM ICPC problem)

Problem 3 – String subsequence

Given two strings a and b, print the longest string x of letters which is a subsequence of both a and b. For example,

  • if a is pretty and b is typing, then x is ty,
  • if a is walking and b is king, then x is king and
  • if a is iris and b is aqua, then x is an empty string.

Write a program in C++ that prompts the user for the two strings a and b and displays on screen the appropriate x.

(I told the students about C++’s extensive string manipulation facilities)

Objective

My first objective is to make sure that students understand than programming can be fun and rewarding as an intellectual (unmarked) activity. My second objective is to make sure that the students are ready to digest whatever I’ve prepared for them as from Friday…

Factor? Scheme? Ruby? I’ll tell you on Friday :-)

The Story of Programming: great idea!

By 6 Comments

I came across a great blog entry “Books that should exist” by Daniel Ehrenberg, a well-known Factor hacker, today where he writes:

I, like many of you reading this blog, have an unhealthy interest in programming languages. Mine may be a little more unhealthy than yours. Whenever I hear the name of a programming language that I don’t know of, I immediately need to read about it, to get some basic knowledge of its history, syntax, semantics and innovations.

Most study of programming languages works by examining the properties of the languages themselves: how functional programming languages are different from imperative object-oriented languages and logic languages and the like. But what about a historical perspective? The history of programming languages is useful for the same reason other kinds of historical inquiry are useful. When we know about the past, we know more about the way things are in the present, and we can better tell what will happen in the future. The history of programming languages could tell us what makes things popular and what makes things ultimately useful.

Unfortunately, not much has been done on this. Knowledge of programming language history is passed on, unsourced, with as much verifiability as folk legend. The ACM has held three conferences called HOPL on this subject over the past 30 years, so all the source material is there. But apart from a book published in 1969, this is all I can find as far as a survey history of programming languages goes.

There is a limit to how much academic research papers can provide. The proceedings of the HOPL conferences aren’t bedtime reading, and they don’t provide much by way of a strong narrative. A new book could present the whole history of programming from the first writings about algorithms to modern scripting languages and functional programming languages so it’s both accessible to non-programmers and interesting to programmers. As far as I know, no one’s really tried. But it would be really fun to try.

I think this is a great idea!

I would love to read such a book. I would even love to contribute to such a book!

Factor, a practical stack language

By 1 Comment

I’ve just discovered Factor, a new programming language. It is a stack-based language like Forth and Postscript. Factor works on many different platforms.

I’m currently looking at it as one of the possible programming languages I’ll cover in my Programming Languages module at the University of Mauritius. Simple stack-based languages are interesting because they are low-level meaning that a student who understands Factor really understands how a computer works. And also the Java virtual machine which is also a stack-based bytecode interpreter.

Some example code

The Factor programming language is simple. For example,

10 20 30 + * .

displays 500. 10 20 and 30 are pushed onto the stack. + consumes the last two elements on that stack (20 and 30) and produces 50 which is pushed on the stack. * consumes the 50 and 10 and 500 is pushed. The . consumes one element of the stack (i.e. 500) and prints it on screen…

This morning, Pascal Grosset and I have been experimenting with different functions in Factor using the Factor workspace which is a great IDE. We have come up with the following:

: square ( x -- y ) dup * ;

This is a function called square that consumes one element of the stack (the x) and produces one element (the y). What it does is easy. dup duplicates the topmost element of the stack. * obviously multiplies the two topmost elements. That’s it.

: cube ( x -- y ) dup dup * * ;

Easy!

: big ( x -- y ) 10 > ;

big looks at the topmost element of the stack and replace it by t(rue) if it is bigger than 10 and (f)alse otherwise. t and f are Boolean values.

: negative ( x -- y ) 0 swap - ;

The swap is used to swap (what else?) the two topmost values on the stack. Notice that 0 is pushed before. And the – only does 0 – the number which was there already i.e. calculates the negative of that number.

: max ( x y -- z ) 2dup < [ swap drop ] [ drop ] if ;

What about this one? It contains a conditional statement (the if) which consumes three elements on the stack: a Boolean and two quotations (which are like Smalltalk and Ruby blocks which are evaluated later if needed). The first quotation [ swap drop ] will be evaluated if the condition is true and the second one [ drop ] otherwise. The 2dup function simply duplicates the two topmost elements on the stack. Get it?

Recursion in Factor

More complex Factor functions allow for recursion:

: fact ( x -- y ) dup 0 = [ drop 1 ] [ dup 1 - fact * ] if ;

Do you recognize our friend factorial? drop simply discards the topmost element of the stack. Notice that fact is called recursively until it hits the boundary case.

And finally,

: fib ( x -- y ) dup 1 <= [ drop 1 ] [ dup 1 - fib swap 2 - fib + ] if ;

This is another friend, the Fibonacci function. Have fun understanding it.

PS: Elie Chaftari says that according to Doug Coleman, one of Factor’s top gurus, you need to learn the following words (aka functions) by heart: dup, keep, 2dup, 2keep, swap, pick, rot, -rot, roll, -roll, 2apply, 2array, first2, nth, set-nth, append. Doug also advises to learn the following words for iterating: each, each-with, map, map-with, 2each, 2map.