ABC and The Birth of Python

As I have mentioned in a previous post, I am very interested in the how and why of programming, which includes the history of different languages. One of the posters at PyCon 2012 held in Santa Clara over the past week was about the programming language ABC. There is a Youtube video that is unfortunately edited poorly and has the microphones off during the most important part of the interview here.

Guido van Rossum is often called "The Father of Python" because of his critical involvement in the development of the language. He wanted programming to be more intuitive, easier to learn, written in true English, and available to everyone. However, he did not start Python until ABC lost its funding. He also did not come up with all the basic principles on his own. Although he did work on the ABC project, he was not one of the original creators, nor is he attributed a large portion of the credit. Leo Geurts, Lambert Meertens, and Steven Pemberton are acknowledged as the leads on the ABC Project sponsored by CWI, Netherlands.

Like Python, ABC uses indentions (white space) to organize loops. ABC is also much easier to read than the programming languages of its time, BASIC, Pascal, and AWK. Tuples, lists, and strings were important in ABC, as they now are in Python. Tuples and indentations were actually utilized by SETL before they were used by ABC.

By looking at examples of SETL developed in the late 1960's, then examples of ABC from the 1980's, and finally modern Python, the progression of the structure and readability is apparent. Python is a beautiful language because of its intuitive design.

SICP Square Root Procedure

I haven't progressed much further in SICP. There have been so many interruptions. We traveled to Santa Clara for Pycon, where my husband, sontek, lead a tutorial on gevent, socketio, and realtime web (all things currently above my comprehension). Our son met Steve Holden, the chair of the Python Foundation, and many other developers known in the world of Python. I was hanging out in the lobby of the conference center one day so that I could see some of my husband despite the time involvement of the conference. Oddly enough, my SICP book got just as much attention as having a baby in a stroller and being female. I was more than the elephant in the room. I was a pink elephant wearing roller skates.

Continuing with SICP, I want to discuss the square root procedure example. It is excellent at demonstrating a lot of basic programming principles. Of course, Python has excellent math tools that make defining a procedure for square root unneccesary, but let's just do it for fun. First, we need to understand Newton's Method.

Let's pretend we did not know the square root of 9. We GUESS the answer is 2. But 2 squared is 4. So how do we get closer to the answer? We take the average of our GUESS and X, which is 9, divided by our most recent guess. The average would be 2.75 ( (9/2+2)/2 ). Now 2.75 becomes our new GUESS. We repeat, until guess squared is equal to 9, our x. So what does our code need to do?

make a guess -> square guess to check if good enough -> take the average of guess and x divided by guess if not good enough -> use computed average to improve guess -> square guess to check if good enough -> take the average...
An iterative procedure (repeating) until when?

Some numbers may take a very long time to solve exactly, or the square root may be a decimal with over 10 numbers beyond the decimal, so we also need to allow for some error. When we check if the square of the guess is equal to our x value, we can allow a difference less than .001, between the squared guess and the value of x, ending the iterations. We also need to define what our original guess will be. SICP uses 1.0, so let's try that. In both lisp and python, a number with a decimal allows floating numbers to be computed, while an integer without a decimal does not. Some of our definitions are modular, or reusable, so I'm going to give square, average, and abs their own definitions. I am ignoring the built-in absolute value, just so we can do more coding. I'm calling the absolute value definition abs2. I solve this problem in a different order than SICP, so I'm going to show my logic, in Python.

First, I wrote my code in Vim, so I could fix typos easily and experiment more quickly. In my terminal, I created sqrtsicp.py:

vim sqrtsicp.py

Our modular definitions mentioned previously are easy. Let's get them out of the way.

def square(x):
    return x*x

#naming absolute as abs2 to avoid built-in "abs"
def abs2(x):
    if x<0:
        return -x
   else:
        return x

def average(x,y):
   return (x+y)/2

Now for the hard part. We'll skip the first guess right now. The iterative part involves checking if our guess is good enough, then improving our guess if it is not good enough (good enough is false), only to try to determine if our improved guess is good enough.

def sqrt_iter(guess):
   if good_enough(guess):
       return guess
   else:
       return sqrt_iter(improve(guess))

Next we define how we determine if good_enough is true and how to improve our guess. Both of these need to know the value of x to compute.

def good_enough(guess,x):
   return abs2(square(guess)-x)<.001

def improve(guess,x):
    return average(guess,x/guess)

Now we have two problems. One, the x is being used for good_enough() and improve() without receiving the value of x from sqrt_iter(). Second, we need a starting guess. This is the point where I put good_enough(), improve() and sqrt_iter() all together and give it an initial guess. Our variable x is a constant and can be passed in from the overall procedure sqrt().

def sqrt(x):
    def good_enough(guess):
         return abs2(square(guess)-x)<.001
    def improve(guess):
         return average(guess,x/guess)  
    def sqrt_iter(guess):      
         if good_enough(guess):          
             return guess
         else:
             return sqrt_iter(improve(guess))
     return sqrt_iter(1.0)

It's good structuring to have all your definitions before your actions. The final line is the return function that causes the dominos to fall. sqrt_iter() calls itself on the new guess if our latest guess was not good enough. "Calling itself" is known as recursion. Now just make it a program. Within my file, I define the main procedure (not sure of the programmers vernacular)where my program is going to ask what to take the square root of. I want the input to be any positive number, including decimals. I want to use exception handling to ask for a floating number if the user inputs a string. I'm also going to define the decimal places for the output of the square root procedure to 3 digits past the decimal. If a negative number is entered, I ask for a positive number and attempt the program again. If a string is entered, I say "Oops, that's not a number" before calling the program again.

def main():
    try:
        x=float(raw_input("What number do you want to find the square root of? "))
        answer = sqrt(x)
        print("The answer is \n%.3f") %answer
    except:
        print("Oops, that is not a number")
        main()

if __name__=="__main__":
    main()

Those three pieces combined are a completed program. In my terminal, I can run it by typing:
python sqrtsicp.py

Playing with it, I attempt to find the square root of -9, 874, .04, and L. All my results are what I expect. This may be a good candidate for selenium testing or a unit test in more complicated programs. For another example of exception handling, view my Caesar's Shift. For more information of float from wikipedia, read this article. You can also refresh your math tools knowledge, including absolute value here.

Applicative Order Versus Normal Order Interpreter

How would you solve for c in the following problem? Ignore computer programming languages for just a minute.

b=(a+2)*(a+1) c=a*b a=3

Choice 1:

c=(3)*(3+2)*(3+1)
c=3*5*4
c=60

Choice 2:

c= (3)*((3+2)*(3+1))
c=(3)*(5*4)
c=(3)*(20)
c=60

They look very similar and yield the same result, however they act differently. In choice 1, the numbers are substituted and evaluated at the end. In Choice 2, the intermediate step (solving for b) is completed before evaluating for c. Choice 2 is applicative order, or strict evaluation. Choice 1 is normal order, also known as lazy evaluation because it only calls what is needed. The Lisp interpreter acts like Choice 2.

Knowing that lisp is applicative-order, we can now theorize the results of the somewhat famous Ben Bitdiddle Test, exercise 1.5 in SICP.I attempted to predict the outcome yesterday when I did not have access to my computer. I'm still bitter about it. First is the example written in lisp. Second is the test translated into Python. Do you think lisp and python act the same? What will they do when tested?

(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))

(test 0 (p))

Or in Python

def p():
return p()

def test(x, y):
return 0 if x==0 else y

test(0, p())

I spent about 45 minutes irritated, thinking there was no way lisp would return either 0 or y, because the p would be looping forever, I was able to get on a computer. I WAS RIGHT! Applicative order interpreters cannot evaluate the test, because they are too concerned with the definition of p. "Lazy" or normal order interpreters only apply the needed information, so they are able to return 0. According to this test, Python is also a strict interpreter, using applicative order like lisp. I expect the differences between normal order and applicative order will be relevant again in further reading of SICP.

Getting Back Into It

It has been awhile since I have posted anything for two reasons. First, I got stuck. Python came easy for me, but programming requires much more than knowing one language. For that reason, I have decided to resume my learning with more elementary programming concepts. Some people learn by doing, but I learn by dissecting. I need to know how and why things work the way they do. Which programming languages came first? How does a program evaluate a complex math problem with variables? What are the strengths and weaknesses of each of the languages? What are interpreters and how do they work? How does code become a website? My second reason for my absence is that I had a baby. Now 8 months old, he is a little less demanding of my attention and energy than he was before he was capable of sitting up on his own.

I am currently reading Structure and Interpretation of Computer Programs. SICP and Little Schemer are used to teach generalized computer programming principles, utilizing the languages of LISP and Scheme for examples. Both books were created at MIT for computer programmers. Lisp is the second oldest programming language still in use. Reddit.com was written in Lisp before it was converted to Python. Unlike how Python is organized by white space, Lisp uses parenthesis. A ridiculous amount of parenthesis. I have not yet attempted to write code in Lisp, but I am anticipating customizing a VIM configuration for using only with Lisp will be beneficial. I am enjoying the conciseness and organization of Lisp, compared to Python. Below is an example of the same mathematical expression in the two languages.

Python

3 * a + 7 + b

Lisp

(+ (* 3 a) 7 b)

I'll be discussing any "Eureka" revelations here on the blog, though it may take me a couple weeks to get through SICP.

Now on Github

HousewifeHacker is now on Github. To avoid further formatting problems with pasting my code on the blog, I will be using github to embed my code. For those who are unfamiliar with Github, the site allows programmers to follow open source contributions from different authors and contribute to full projects (Repositories) or small code snippets (Gists) by creating your own code or making changes to other user's work (forking). Users can determine whether their repositories and gists are public or private. The objective of Github is to serve as a social coding resource as well as a revision control. Because I want to be able to contribute to open source projects as I become more knowledgeable of Python, Github will become an increasingly valuable resource.

maketrans Python and Improved Caesar's Shift

Maketrans is used to translate strings, character for character. The characters can be symbols, letters, or numbers. The following short example is a Caesar's Shift moving backwards by two letters.

#first we need to import maketrans
>>> from string import maketrans
#now define the translation
#parameters are strings, not lists
#first parameter defines what will be found in the string
#second parameter defines what each will be changed to
>>> trans = maketrans('cdefg','abcde')
#define our string and translate
>>> s = 'deg'
>>> s.translate(trans)
'bce'

Now using maketrans and a few other suggestions from the comments, I have written a newly improved Caesar's Shift. Encode and decode use the same code, because a shift of 4 in one direction of a 26 character alphabet is equivalent to a shift of 22 in the other direction. I also used ascii_letters to shift my translation, which is 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'. The letter w may be encoded to be a A by a shift of 4, but the decoding will return the lowercase w. There was an error in my exception handling, which is now corrected.

Caesar Cipher in Python Using ASCII

ASCII is how American computers store numbers, letters, certain commands, and symbols as numbers. A binary byte is eight digits long, consisting of only 1 and 0. When ASCII was developed, there were 2^8, or 256 possible characters for 8-bit (1 byte) personal computers. Unicode is used more commonly and extensively, but ASCII is sufficient or this exercise. Consult an ASCII Table or play with python's default functions to determine the encoding of a character such as 'a', 'A' or '&'.

In python, we can find the ascii value using ord of a string

>>> ord('a')
97
>>> ord('A')
65
>>> ord('b')
98
>>> ord('1')
49
>>> ord('2')
50
>>> 3-0
3
>>> ord('3')-ord('0')
3

Notice how the lower case and upper case are unique. Also, the ASCII numeric value and the character increase by the same amount. The same trend is true for the continuation of the alphabet, if lower case or upper case characteristic is preserved. The string length must be 1 when using ord, because each index has its own ASCII value.For a multiple digit number or a word, you can use a for loop to go through the string.

The reverse of ord is chr, for character.

>>> chr(97)
'a'
>>> i=97
>>> while i<104:
...   print chr(i)
...   i+=1
... 
a
b
c
d
e
f
g
>>> alpha=[]
>>> i=97
>>> while i<104:
...   alpha.append(chr(i))
...   i+=1
... 
>>> print alpha
['a', 'b', 'c', 'd', 'e', 'f', 'g']

Caesar's shift was how Caesar communicated with his generals, in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, if an 'a' is encoded by a 'c' with a shift of 2, then a 'b' would be encoded by a 'd.' Reversely, an 'a' in the encoded text would be a 'y' in the plaintext. The following program was inspired by thepythonchallenge.com. My husband and I had a lot of fun testing and debugging by sending each other messages over email. The code only changes letters so that spaces, smilies, brackets, and other punctuations and characters will be preserved. string.maketrans would be very useful and less code for a one time application, but the following code is highly reusable.

#string will later allow us to test for ascii letters
import string

def encode(input,shift):
  #create an empty string
  foo = ''
  #a for loop to shift the letters by the shift input 
  for x in input:
    #changes only ascii letters
    if x in string.ascii_letters:
      #upper case end of alphabet, to loop back to A
      if ord(x) > ord("Z") - shift and ord(x) <= ord("Z"):
        new_ord = ord(x) + shift - 26
      #lower case end of alphabet
      elif ord(x) > ord("z") - shift and ord(x) <= ord("z"):
        new_ord = ord(x) + shift - 26
      else:
        new_ord = ord(x) + shift
    #other characters will remain unchanged
    else:
      new_ord = ord(x)

    new_chr = chr(new_ord)
    foo += new_chr

  print "Your encoded message is ", foo

def decode(input,shift):
  #create an empty string
  foo = ''
  #a for loop to shift the leters by the shift input 
  for x in input:
    #changes only ascii letters
    if x in string.ascii_letters:
      #upper case start of alphabet, to loop back to Z
      if ord(x) - shift < ord("A")  and ord(x) >= ord("A"):
        new_ord = ord(x) - shift + 26
      #lower case end of alphabet
      elif ord(x) - shift < ord("a") and ord(x) >= ord("a"):
        new_ord = ord(x) - shift + 26
      else:
        new_ord = ord(x) - shift
    #other characters will remain unchanged
    else:
      new_ord = ord(x)
    new_chr = chr(new_ord)
    foo += new_chr
  print "Your decoded message is ", foo


def get_shift():
  try:
    shift = int(raw_input("How many characters do you want to\
 shift?\n"))
  except:
    print 'Shift must be a number'
    shift = get_shift()
  if not (shift > 0 and shift <= 25):
    print 'Shift must be between 1 and 25'
    shift = get_shift()
  return shift

def main():
  try:
    action=raw_input("Welcome to Caeser's Shifter! Would you \
like to encode or decode a message today?\n")
  except:
    print 'Please type encode or decode'
    main()
  shift = get_shift()

  print "Ok, let's %s your message with a shift of %d." % (action, shift)
  input=raw_input("What would you like to be translated?\n")

  if action=='encode':
    encode(input,shift)
  elif action=='decode':
    decode(input,shift)

if __name__ == "__main__":
  main()

There are probably a few areas where redundancy can be reduced, but I am still learning as a developer. This was my first time trying exception handling, which I learned from my husband.