Programming is one of the most difficult branches of applied mathematics; the poorer mathematicians had better remain pure mathematicians.
It was Edsger W. Dijkstra, the famous computer scientist, who wrote these words in his note named “How do we tell truths that might hurt?“. I am sure that many people didn’t like to read them, and didn’t understand what he meant.
Although it is not my intention to discuss his words, I want to present a simple example that demonstrates how mathematics can be used to program better and to make you more confident about your own programs.
This post includes a fair amount of mathematical definitions and concepts, but they should not be difficult to understand. After the mathematical discussion, I present an example using the Perl programming language (it also applies to languages like C or Java).
The Problem
The problem I am going to deal with, involves the ceiling and floor functions. If you don’t remember, the floor of a real number 
is (usually) written as 
and it is defined as the greatest integer that is at most . Similarly, the ceiling of a real number is written as 
and it is defined as the smallest integer that is at least .
The goal is to implement the ceiling function supposing that our programming language only provides the floor function to round numbers. Formally, given a real , we want to calculate an expression 
such that:
(Continued)
Related Articles:
In my previous post I have promised that I would put here some of my technical notes (JFFs). Today I am posting JFF1, which presents a very well-known problem in a non-traditional way. The problem is how to swap the values of two variables without using another temporary one.
I start by presenting the properties involved in the traditional solution and then I generalize it for arbitrary operators. I finish the note with a simple refinement. If you have any nice example instantiation for the last set of assumptions, I would be glad to know it. Other than that, comments or corrections are more than welcome!
The note is available in PDF. Click the following link to get it:
JFF1 - Swapping the value of two variables
Related Articles:
That’s true: the last post was exactly 5 months ago, but I’m still alive! A lot of new stuff happened during these 5 months. Two days after writing the last post, I went with my group (Foundations of Programming) to a very nice hotel in Ruddington, where, during two days, each member had to present something about his/her work. I’ve talked about a result I’ve derived related with distributivity through the Greatest Common Divisor. My slides are available at the event’s webpage and I will put online a note with all the details.
A few days later Alexandra got ill with some strange pain in the abdominal area. The following weeks were really hard, since she had to go to the hospital emergency services. So that you have an idea of how strange the whole thing was, the doctors still don’t know what the problem is! Now, she has occasional pain, but it seems to be much more controlled.
Anyway, more or less at the same time I started to read a very nice article (a Functional Pearl) written by Jeremy Gibbons, Richard Bird and David Lester named “Enumerating the Rationals“. The paper presents some algorithms encoded in Haskell to enumerate the positive rational numbers. In particular, it presents algorithms to construct the famous Stern-Brocot and Calkin-Wilf trees. It also presents a very efficient algorithm to enumerate the rationals in Calkin-Wilf order just by using as current state the previous rational (i.e., two integer numbers). However, the authors claim that “it is not at all obvious” how to create a similar efficient algorithm for enumerating the rationals in Stern-Brocot order. Well, after reading it, Roland (my supervisor) and me found a way of doing it. The key idea is that rational numbers are pairs of coprime numbers (numbers which greatest common divisor is 1) and thus, we can use Euclid’s algorithm as a basis for enumerating these pairs. By using the Extended Euclid’s algorithm written using matrix multiplication, we were able to derive both Calkin-Wilf and Stern-Brocot enumerations from the same algorithm. We wrote a paper named “Recounting the Rationals: Twice!” that was submitted to the journal American Mathematical Monthly.
(Continued)
In the last post I have presented some historical context about programming and mathematical methodology. If you read it, then you should have an idea when and why programmers started to investigate on mathematical methodology. However, I haven’t mentioned any aspects of mathematical methodology that can help us to improve our programming or mathematical skills.
In this post, I’ll talk about mathematical proofs. And what’s the relevance of this topic to programmers? Well, computer programs are mathematical formulae, with a precise formal meaning and embodying constructive theorems about the systems they implement (as well-written in “Mathematics and Programming - A Revolution in the Art of Effective Reasoning“, by Roland Backhouse). The difference between theorems embodied by computer programs and the ones usually studied in mathematics is that they are applied by an unforgiving machine, with the effect that the smallest error can cause a huge damage. This means that computer programmers must create trustworth designs, i.e., the constructive theorems embodied by their programs must be programmed correctly.
Mathematical Proofs
Mathematicians job is to do mathematics, i.e., to design and present theorems, arguments, algorithms and in some cases whole theories. However, the traditional mathematical curriculum is more concerned with teaching mathematical facts — existing theories and concepts — than with the doing of mathematics. And even when design and presentation get some attention, they are treated separately: design of solutions is viewed as a psychological issue, while presentation is viewed as a matter of personal style (words from this Dijkstra’s note on Mathematical Methodology).
(Continued)
Related Articles:
Thursday, December 28, 2006
First of all, welcome to my new blog. Being this my first post, I will present myself, give you some background on what I am doing and explain what are my intentions about this blog. My name is João Fernando Ferreira and I am a research student at the Foundations of Programming research group at the University of Nottingham (visit the About page to find out more).
My research is on algorithmic problem solving and its main goal is to develop calculational problem-solving techniques resulting in educational material supporting the use of a calculational approach to algorithmic problem solving. The focus of the project will be on the dynamics of problem solving - the processes of mathematical modelling and effective calculation in the formulation of concise and precise algorithmic methods.
As any other researcher, I spend most of my time reading and writing. That is one of the reasons I have created this blog: to organise my written notes. Using a blog system brings me some advantages like:
- I can tag my notes and use the system search capabilities to find them;
- I can access and change them from any place in the world, as long as I have Internet access;
- I can add new content from any place in the world, as well;
- I can share my notes and get feedback from my colleagues, supervisors, friends or anyone who is just interested in the same topics.
Other important reason to share my notes and thoughts is that I think they may be of interest for programmers. Since this is my first post, and (probably) most of you don’t really understand what I am doing, I will start by presenting some historical facts (mixed with personal opinions) and motivations. It is my hope that these facts will help you understand the relation and importance of mathematical methodology to programming. Please note that to read the entire post, you may need to click the “Read more” link.
Historical context
In the 1960s, programmers started recognising that there were serious problems in the programming field and that it was necessary to prove the correctness of programs. At the time, software engineering was facing a software crisis and programming was not very well understood. Many software projects ran over budget and schedule and some of them even caused property damage and loss of life (see the RISKS-FORUM Digest for some examples).
To solve these problems, computer scientists focused on programming methodology and on ways to build programs in a systematic way. A common consensus was that programs should be proved correct, and in the late 1960s, some important articles had an important impact on the field. In 1968, Edsger W. Dijkstra published an article on the harmfulness of the Go To statement, where he claims that its use makes it impossible to determine the progress of a program. Also, one year later, Tony Hoare published a seminal article where he introduces the Hoare triples and an axiomatic approach to language definition.
(Continued)
Related Articles:
