Posts Tagged ‘software’

A very nice way to write applications

June 21, 2015

Recently I have been reading about the UNIX philosophy for writing programs and applications. [1]

Their approach is to create small, simple programs (exe files) that can be flexibly composed using a scripting language. Here’s an example: ls is a program that lists the content of your current folder, sort is a program that sorts its input. Most scripting languages have a pipe ( | ) operator. We can use pipe to send the output of the ls program into the sort program:

ls | sort

That results in outputting the content of your current folder, in sorted order.

The UNIX people have been following this kind of assemble-from-small-programs approach for decades and it has been phenomenally successful. Many of their programs were written in C. But today a lot of their programs are written in Python [2]. A really awesome thing is that C programs and Python programs can be mixed-and-matched. I wanted to see how this works so I wrote a simple Python program, mesg.py, which outputs a message (Hello, World) and a simple C program, id.c, which reads input and outputs it. The two programs are completely independent (two exe files). Then I used a scripting language to compose the two programs:

mesg | id

That results in outputting the message.

In general, with this approach we can compose any number of programs:

A | B | C | …

Each program can be written in Python or C (increasingly programs are written in the Go programming language).

Interested in learning more about how I implemented my mesg-id application? See here [3].

[1] These are fantastic books: (1) The UNIX Philosophy by Mike Gancarz, and (2) The Art of UNIX Programming by Eric S. Raymond.

[2] See this Stack Overflow question: Modern-day Unix tools are written in what programming language? (http://stackoverflow.com/questions/30830759/modern-day-unix-tools-are-written-in-what-programming-language)

[3] I initially implemented both the mesg program and the id program in Python. I’m a Python newbie so I asked a question about this on Stack Overflow: How to compose Python exe programs using pipes? (stackoverflow.com/questions/30956979/how-to-compose-python-exe-programs-using-pipes) Later I implemented the id program in C and then used a scripting language to compose the Python mesg program to the C id program. This is a very nice way to write applications!

There is less than a 1% chance that your program is correct … program contains 500 components and each component has a 99% chance of being correct

September 28, 2013

As we build ever larger and more powerful systems it becomes ever more important that those systems, and the components of which they are made, should be transparently simple and self-evidently correct. As Professor Dijkstra points out (Structured Programming, Academic Press 1972):

                If the chance of correctness of an individual
                component equals p, the chance of correctness
                of a whole program, composed of N such
                components, is something like

                                P = pN

                As N will be very large, p should be very, very
                close to 1 if we desire P to differ significantly
                from zero!

The purpose of this book is to present a coherent method and procedure for designing systems, programs and components which are transparently simple and self-evidently correct.

                Principles of Program Design
                by M.A. Jackson

Example: Suppose the chance of correctness of an individual component is 99% (p=0.99) and the program is composed of 500 such components (N=500). The chance of correctness of the program is

                                P=(0.99)500
                                               
P = 0.007

There is less than a 1% chance that the program is correct!

My New Mantra: Modularity is the Key to Successful Programming

March 8, 2013

Modularity is the key to successful programming. [John Hughes]

Lazy evaluation is perhaps the most powerful tool for modularization in the functional programmer’s repertoire. Consider …

Most functional programming languages have a function called “repeat” which generates an infinite list; its argument is used as the value of the list. For example, this generates an infinite list of 3:

        repeat 3        returns [3, 3, 3, …]

Also provided by most functional programming languages is a function called “take” which has two arguments, an integer N and a list. The function “take” returns the first N values of the list.

“take” can be composed with “repeat” to obtain a pruned list of values. The following returns the first 5 values of an infinite list:

        take 5 . repeat

Function composition is denoted by the dot ( . )

Applying that composed function to 3 results in a list of five 3’s:

        (take 5 . repeat) 3        returns [3, 3, 3, 3, 3]

It is lazy evaluation that allows us to modularize the pruning problem in this way. The “repeat” function is evaluated lazily – only as many values as requested are generated. So lazy evaluation is very efficient. Without lazy evaluation we would have to fold these two functions together into one function which only constructs the first five values.

Here’s another example. We can define the set of even numbers by enumerating all positive numbers [1..] and multiplying each by 2:

        evens = [x * 2 | x <- [1..]]

That is, of course, an infinite list. However, lazy evaluation will compute only as many as needed. Let’s take the first 5 evens:

        take 5 evens        returns [2, 4, 6, 8, 10]

One more example. The example comes from the field of Artificial Intelligence. A decision tree is generated. It could be a decision tree for medical diagnosis or a decision tree for chess moves or a decision tree for something else. The decision tree is potentially infinite. Without lazy evaluation, processing may never terminate. Rather than exploring a potentially infinite space we prune the tree to a depth of, say, 5 levels:

        prune 5 . decisiontree

decisiontree is a function that generates the tree. prune 5 chops off any levels of the tree beyond 5 levels deep. We can make improvements by tinkering with each part. Without lazy evaluation we would have to fold these two functions into one function which only constructed the first five levels of the tree. That is a significant reduction in modularity.

Lesson Learned: Want to have successful software? Then you need to learn how to take advantage of the enhanced modularity that lazy evaluation provides. And, of course, you need to use a programming language that supports lazy evaluation.