Virtuous Programmer Adventures of an Autodidact

1Nov/103

Python 1/4: Getting Started

Posted by Frank Berthold

This is the first article in a series, to read the entire series go here.

Why Python is Interesting

Programs must be written for people to read,
and only incidentally for machines to execute.
-Abelson and Sussman

Readable Syntax

When Guido van Rostrum designed Python it's clear that he had this principle, if not this exact quote in mind. The result is a language which often reads like pseudo-code. For example:

  1. def buyFruit(fruit):
  2.   if fruit.color == 'red' and fruit in [Apple, Orange, Tomato]:
  3.     return fruit.price
  4.  

Flexible Semantics

Although Python primarily an object oriented/procedural language, it has functional elements including functions as first class objects, lambda expressions and map/filter/reduce functions. This gives considerable flexibility in how you go about solving problems.

An excellent summary of the design philosophy that guides both Python's code design and the style of Python programs in general see: The Zen of Python

List Comprehension

Python's list comprehension syntax is a compact and clear way to create new lists from existing lists. The syntax itself looks a lot like set comprehension notation as it's used in discrete mathematics. Here are a few examples:

Given the base list of integers:

  1. xs = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

You can create a list of every integer doubled with:

  1. [x * 2 for x in xs]

Or you can create a list of only odd integers with:

  1. [x for x in xs if x % 2 == 1]

Or a combination of both, doubling all of the odd integers from 1 to 10:

  1. [x * 2 for x in xs if x % 2 == 1]

Generators

Generators are a powerful addition to Python's syntax. They permit a form of lazy evaluation where they create values as they are needed rather than all at once. For example, a common way to write a function for a Sieve of Eratosthenes to generate prime numbers is:

  1. def generatePrimes(topValue):
  2.   primes = [2]
  3.   for testValue in range(3, topValue + 1):
  4.     divisors = [prime for prime in primes if testValue % prime == 0]
  5.     if divisors == []:
  6.       primes += [testValue]
  7.   return primes

The above function will, when called, generate all of the prime numbers from 2 up to the value given in the argument. The problem is that it will generate them all immediately, whether you need them or not. This is potentially a serious waste of resources if it comes out that you only needed a handful of them. Python solves this problem by using generators:

  1. def generatePrimes(topValue):
  2.   primes = [2]
  3.   for testValue in range(3, topValue + 1):
  4.     divisors = [prime for prime in primes if testValue % prime == 0]
  5.     if divisors == []:
  6.       primes += [testValue]
  7.       yield testValue

The only difference between our new function and the original is the last line. Note that in the new function there is no return statement, instead there is a 'yield' statement, and it is inside the for loop. The new function returns a generator which can be passed to any function that operates on lists and it will treat it as a linked list. Should the function that uses the generator return before all of the values have been extracted then the remaining values will never be generated. This will allow you to avoid doing work that isn't needed. Even if you find that you need all of those values, rather than having a potentially long wait at the start of the process, the work will be spread throughout the process, allowing for just in time delivery of your data.

Python's Lineage

ABC

Python was originally developed to be a replacement for ABC, and on the surface the resemblance is striking:

ABC:

  1. PUT {} IN telephone
  2. PUT 5551212 IN telephone["Spam Foo"]
  3. PUT 8674309 IN telephone["Eggs Bar"]
  4. FOR name IN keys telephone:
  5.   WRITE "Name:", name, " Phone:", telephone[name] /

Python:

  1. telephone = {}
  2. telephone["Spam Foo"] = 5551212
  3. telephone["Eggs Bar"] = 8674309
  4. for name in telephone.keys():
  5.   print "Name:", name, " Phone:", telephone[name]

Both of the above map telephone numbers to names in an associative array, then print them in the form: Name: Spam Foo Phone: 5551212 Name: Eggs Bar Phone: 8674309

In addition to the similarities in syntax, they both use an interactive environment which allows you to type your code directly into the command line and get a response from the interpreter.

Haskell

From the appearance of the syntax, it's clear that Python acquired its list comprehension functionality from Haskell.

Haskell:

  1. [oddNum * 2 | oddNum <- [1 .. 10], oddNum `mod` 2 == 1]

Python:

  1. [oddNum * 2 for oddNum in range(1, 11) if oddNum % 2 == 1]

Both of the above produce a list of integers, [2, 6, 10, 14, 18] which are the odd numbers from 1 to 10, doubled.

Python Installation

Complications to Look Out For

Currently there are two active branches in Python, 2.7 and 3.1. Python 3.1 has a number of improvements to the language which make the syntax regular and prevent some difficult to track bugs that are a serious issue in 2.7. Unfortunately it is not backwards compatible. I'll be using 2.7 for this article because it continues to have the most libraries available for it.

If you're interested in the changes made in Python 3.1, you can find them at What's New In Python 3.0.

Downloading And installing Python 2.7

You can find the latest release of Python 2.7 from Python download. From that point installation is easy, run the installer and accept the default values. The full install will take 52MB of space on your drive.

First Program

For a first program, we'll get started with "Hello World". In Python this one is so trivial that it takes more effort to run it than to write it. Copy and paste the code below into your preferred text editor and save it as 'helloworld.py':

helloworld.py:

  1. print "Hello World"

Executing the Program

The primary purpose of the hello world program is to create a simple program that demonstrates how to compile/execute a program in the given language.

To execute this one type "c:\python27\python helloworld.py" at the command line.

There is no direct use of a 'main' function in Python. Code execution starts at the beginning of the file and progresses through the end.

There are a number of ways to impose more structure on a Python program, but the purpose of this first project is to make sure our systems are configured correctly. I'll get to the more interesting stuff in next week's post.

Trivia

Python was named for the British comedy group Monty Python. Python's creator creator, Guido van Rostrum has the final say on all of Python's design decisions and is called the Benevolent Dictator for Life.

Resources

Python Wikipedia Article

Python.org

Python Download

The Zen of Python

What's New In Python 3.0

Python Cheat Sheet

Filed under: python, hello world 3 Comments
6Dec/100

Scala 1/4: Getting Started

Posted by Frank Berthold

This is the first article in a series, to read the whole series go here.

Scala

"The work on Scala stems from a research effort to develop better language support for component software." -Scala Overview

Scala is:

  • Object Oriented
  • Functional
  • Strongly Typed
  • A Research Language
  • JVM Based

Why Scala is Interesting

The overall theme of Scala seems to be the same as the theme with any building toy: make it possible to create interesting things from relatively simple things. While studying it I've been repeatedly surprised by finding language constructs that are not from the core language, but can be created from it. For example, Erlang is well known for its actor model for concurrency. With Scala it's possible to create such a system in libraries.

Purely Object Oriented... and Functional?

Scala is both object oriented and functional. My first reaction was that this is a contradiction in terms. The minimum requirement for a language to be functional is that all functions are first class objects. While there are a lot of ideas attached to object oriented languages, at the core an object oriented language has two basic attributes:

  1. Every element in the language is an object.
  2. Every action is performed by a method call from one of those objects.

Scala resolves this apparent contradiction by making functions objects in the object oriented sense. Each function is a singleton object with the single method apply which is executed when the function is called.

Powerful Pattern Matching

Most programming languages have some variant on:

(pseudo code)
switch val:
  "first" -> res1
  "second" -> res2

Which is syntactic sugar for:

(pseudo code)
if val == "first":
  res1
elif val == "second":
  res2

Scala's match functionality is a generalization of this pattern that applies to classes as well as values, for example if you first create a couple of case classes:

  1. case class Node(left: Tree, right: Tree) extends Tree
  2. case class Leaf(num: Int) extends Tree
  3.  

You can then create a function that will sum the tree:

  1. def sumTree(tree: Tree): Int = tree match {
  2.   case Node(l, r) => sumTree(l) + sumTree(r)
  3.   case Leaf(n)    => n
  4. }
  5.  

This will look familiar to those who've coded in languages with Algebraic Type systems like Haskell. This is a case of Scala taking two relatively common elements, classes and switch statements, and combining them into something that is more powerful.

Access to Java's Libraries

One of the major problems with any programming language is having sufficient libraries to be useful for real tasks. For a language to have these on its own it must either have a large community to produce the libraries over time or an exceptionally dedicated small community. Scala solves this problem by having transparent access to Java's libraries, and thus the work of Java's very large community. Any Java library can be imported into a Scala program as though it were one of Scala's native libraries. Strictly speaking since Scala compiles to Java bytecode, it is.

Scala Installation

Before you install Scala, you'll most likely want to make sure you have Java's JDK installed. You can pick it up here.

Scala doesn't have a true installer, so you have to do a bit of manual work to get started:

  1. Download the zip file from Scala Downloads.
  2. Unzip the file into your C:\ directory.
  3. Renaming the resulting directory to something like "scala" may make your life easier if you have to upgrade later.
  4. Add "C:\scala\bin" to your path in environment variables.
  5. If you have Java installed and you want to be able to run Scala programs using Java, add "C:\scala\lib*" to your CLASSPATH environment variable.

Hello World

Scala as Script Interpreter

Scala has a double life, it's both a compiler for Java bytecode and a scripting language. When it's acting as a scripting language the rules are a little more flexible. Compiled, Scala's syntax requires that everything be contained in an object or class. When run through its interpreter you can just have sequences of commands. For example:

HelloWorld1.scala:

  1. println("Hello World!")
  2.  

You can run this program from the command line with: scala HelloWorld1.scala

Scala as Compiler

HelloWorld2.scala:

  1. object HelloWorld {
  2.   def main(args: Array[String]) {
  3.     println("Hello World!")
  4.   }
  5. }
  6.  

This version of hello world can be run by first compiling it with scalac HelloWorld2.scala then running it in Java's VM with java HelloWorld or in Scala with scala HelloWorld. As with Java, by default the name of the produced class comes from the main class, or here singleton object.

Scala's Interactive Shell

Interactive shell has to be one of my favorite language feature and Scala's is rather nice. To start it up type scala at your command line. From there, you can get hello world by typing println("Hello World").

A Couple of Nice Features

When you type something into Scala's interactive shell you'll notice that the interaction looks something like this:

scala> 3 + 4
res0: Int = 7

You can then use res0 as a variable. Additionally if you type :power you'll get access to several nice exploratory features of the language, for example, type in 7. then tab to get all the methods that apply to an integer.

Trivia

  • Scala stands for "scalable language".
  • Scala was originally designed to be interoperable with both Java and .Net.
  • The leader of the Scala team, Martin Odersky, also helped develop Java Generics.

References:

Filed under: hello world, scala No Comments
3Jan/110

Prolog 1/4: Getting Started

Posted by Frank Berthold

Getting Started with Prolog

The Plan

Prolog is rather unusual when compared to other programming languages. Rather than describing a sequence of steps as in a procedural language, it's a declarative language that uses formal logic as its primary metaphor. Prolog is used predominantly in academic settings for language research and artificial intelligence. That being said it is a general purpose programming language and used in commercial settings where the system must be able to reason about complex data like logistics, language processing and data mining. Some examples can be found at SICStus's Website.

Although it's a general purpose programming language, generally other languages are used to do GUI and interface coding. There are GUI packages available though, so I'll give one of them a try in Week 4. With a little luck we'll see Prolog's strength in Weeks 2 and 3.

What to Expect

When this article is complete:

  • You will have:
    • An installation of SWI-Prolog
    • A program that'll say "Hello World"
  • You will know:
    • How to compile a program in SWI-Prolog.
    • How to use the interactive interpreter to make logical queries from a logic base.
    • That Socrates is mortal.

Files Used in this Project

SWI-Prolog

There are a large variety of implementations of Prolog. From these I chose SWI-Prolog because:

  • It works on Windows. (All projects on this blog do)
  • It has a GUI toolkit. (necessary for week 4)
  • It's free, under the LGPL. (Please remember to include a link to SWI's page if you use it for your applications)
  • It has an interactive interpreter. (I like interactive interpreters)

Installation

  1. Download the latest version of SWI-Prolog from their download page.
  2. Run the installer accepting all the defaults.
  3. Add "C:\Program Files\pl\bin" to your PATH in environment variables. How to change your path.

The Code

helloworld.txt (Rename to helloworld.pl):

  1. % Say Hello Prolog
  2. main :-
  3.   write('Hello World!'), nl,
  4.   halt.
  5.  

Comments

In Prolog comments are preceded by a %.

Clause Structure

Prolog programs are composed of clauses separated by periods. A clause is divided into the head and the body with the format <head> :- <body> or just <head>. When just the head is given it's treated like <head> :- true. The body of a clause is a statement composed of either a term, or sequence of terms composed by operators and ending in a period.

In Prolog a , is equivalent to boolean and. In the above, should any of the statements return false, then the others will not be executed. Each of the terms: * write('Hello World!'): Writes "Hello World!" to the screen. * nl: Writes a new line to the screen. * halt: Causes Prolog to shutdown.

Running/Compiling Your Code

SWI-Prolog has an interactive interpreter, an interpreter and a compiler.

The Interactive Interpreter

A session with the interactive interpreter looks like:

  1. C:\>swipl
  2. Welcome to SWI-Prolog (Multi-threaded, 32 bits, Version 5.10.2)
  3. Copyright (c) 1990-2010 University of Amsterdam, VU Amsterdam
  4. SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
  5. and you are welcome to redistribute it under certain conditions.
  6. Please visit http://www.swi-prolog.org for details.
  7.  
  8. For help, use ?- help(Topic). or ?- apropos(Word).
  9.  
  10. 1 ?- write('Hello World!'), nl.
  11. Hello World!
  12. true.
  13.  
  14. 2 ?- halt.
  15.  
  16. C:\Documents and Settings\fberthold\My Documents\My Dropbox\VirtuousProgrammer\Prolog\1 - Getting Started>
  17.  

You can also interact with the interpreter through SWI-Prolog's IDE. I'm a command line junky so haven't played with it too much yet, but you can find it in the Start menu.

The Interpreter

To run your programmer through the interpreter type:

  1. swipl -g main helloworld.pl
  2.  

Where "helloworld.pl" is your Prolog program, commonly called a logicbase. "main" is what you've declared to be the main clause in your program.

The Compiler

You can compile it with:

  1. swipl -g main -o helloworld.exe -c helloworld.pl
  2.  

This will generate a windows executable "helloworld.exe" by compiling "helloworld.pl".

Prolog's Hello World

It's a little hard to do Prolog justice from this first example, because the primary function of Prolog is to describe and evaluate relationships, which don't come up in 'hello world'. To give a little more flavor of what Prolog does, here's a simple relationship:

socrates.txt (Rename to socrates.pl):

  1. % All men are mortal, Socrates is a man.
  2. mortal(X) :- man(X).
  3. man(socrates).
  4.  

Here we have two assertions. That men are mortal and that Socrates is a man. We can how use Prolog to draw a couple of conclusions. The first step is to load "socrates.pl" into the interactive interpreter with:

  1. swipl socrates.pl
  2.  

Here's a sample session in which we can find that Socrates is mortal and that if you are mortal, you are Socrates (Add more facts to the logicbase if you want more mortals):

  1. 1 ?- mortal(socrates).
  2.  
  3. 2 ?- mortal(X).
  4. X = socrates.
  5.  

Prolog's single data type is a term. Prolog terms can be(with examples from the above code):

  • atoms: socrates
  • numbers: no example in the above code
  • variables: X
  • compound terms: man(socrates)
    • where man is called a functor

Summary

Prolog is unlike any programming language I've worked with to date. Not only is it's model entirely different, but it's syntax was designed before it was obvious Algol style syntax was going to predominate, so it's syntax is more influenced by it's logical roots than what is currently considered normal looking syntax.

Coming Up

Next week I'll be putting Prolog through it's paces. The fizzbuzz problem should be interesting to solve. It feels like it should naturally be able to deal with conditional statements, but it doesn't have any direct looping facilities other than recursion. Unit tests on the other hand also feel like a natural fit.

Resources

Trivia

  • Despite being based on an entirely different semantic set than other programming languages, Prolog is Turing complete.
  • Prolog was created at the University of Aix-Marseille by Alain Colmerauer and Phillipe Roussel, collaborating with Robert Kowalski of the University of Edinburgh in 1972.
  • If you enter X. at the interactive interpreter, SWI-Prolog gives Douglas Adams fans the answer.
7Feb/110

Smalltalk 1/4: Getting Started

Posted by Frank Berthold

This is the first article in a series, to read the whole series go here.

The Plan

You've heard about it, every child will have a portable computer, small enough to carry in her bookbag. Its software will be an open environment that they can change and program themselves. I'm talking, of course, about the Dynabook, from Alan Kay's proposal in 1972. The programming language that was to be the center of the Dynabook and its environment was Smalltalk, one of the first object oriented programming languages. Smalltalk was intended to be easy for children to learn, to that end has a simple and highly regular syntax and a deeply interactive environment.

Dynabook was an idea before its time. It lives on in spirit in the OLPC project, which also contains Smalltalk, or an application of it in the form of Squeak's EToys.

Modernly Smalltalk has a number of implementations. One of the best known is Squeak which Alan Kay continues to be involved with. Squeak is an wonderful programmer's playground where Kay and his team have tried out a multitude of ideas, still with the goal of creating an environment that children may learn in. Unfortunately for the working programmer the playground has become rather cluttered with toys, so the Pharo team has made a stripped down version for a much leaner programming environment.

As I alluded to above, Smalltalk isn't just a programming language, it's an environment in its own right. When you open up the Pharo image you have an entire integrated development system, including the System Browser where you do most of your coding, the debugger and the unit test system. And all of which is written in Smalltalk and can be modified inside the system in real time.

What to Expect

When this article is complete:

  • You will have:
    • An installation of Pharo
    • An object that says Hello
  • You will know:
    • Basic elements of the Pharo/Smalltalk environment including:
      • The Workspace
      • The Transcript
      • The Class Browser
    • How to create new classes in the Pharo environment

What You'll Need

To install Pharo, start by downloading the zip of latest version from Pharo Downloads. You'll have the choice between the Cog and Standard VM. Cog is newer and faster, which won't matter much for our purposes, but why not get the fancier toy when you can?

Unzip "Pharo.app" to the location you want to keep it, "Program Files" will do the job. Once you've unzipped it, navigate into the Pharo.app directory and double click the "Pharo" link and your new Pharo system will open.

A Brief Tour of the Environment

Smalltalk was designed to be an entire environment, separate from whatever system that it's running on. The advantage is it gives you a completely portable programming environment that you can move to any machine that has a Smalltalk VM and it will work the same way on each of them. A disadvantage is that there's a lot to get used to in it. For the next couple of weeks, 90% of the work is going to be in the System Browser with side trips in a few of the other tools. The major components of it are:

Smalltalk Environment

  • System Browser: This is where you'll do your actual coding.
    • Packages: Packages are similar to modules, but they only have formal existance when you're importing them in the system. Once they're part of your Smalltalk image, their purpose is purely organizational.
    • Classes: Once you've selected a package, the classes are the primary element in the system.
    • Protocols: Protocols, like packages, are a way to organize the methods in a class.
    • Methods: Methods are what the classes do.
    • Edit Pane: The Edit Pane is where you'll do most of your coding including specifying classes and adding methods.
  • Workspace: You can view the Workspace as a scratch pad, you'll use it when you're trying to figure something out in the small, or when you've completed a piece of work and are doing a bit of ad hoc testing.
  • Transcript: The transcript is where you'll print logs and quick bits of system interaction. You can think of it as a combination of stderr and stdout in a more conventional system.

Files Used in this Project

  • Virtuous-Demo.st: Contains all of the sample code developed during this project.

To import "Virtuous-Demo.st" into your Smalltalk image:

  1. Open Pharo
  2. Click on the background to open the World menu.
  3. In the World menu select Tools > File Browser
  4. In the File Browser dialog, navigate to the folder that contains "Virtuous-Demo.st"
  5. Select "Virtuous-Demo.st"
  6. Click the "install" button at the top of the File Browser dialog.
  7. Close the File Browser.

You can verify that the package has been correctly installed by doing the following:

  1. In the World menu select System Browser
  2. In the Package pane, scroll to the bottom where you should see a package called "Virtuous-Demo" which contains the class "Greeter".

To keep it as part of the image (along with any other changes) click "Save" in the World menu or to exit click "Save and quit".

Executing Code

To execute code in Pharo:

  1. In the World menu, select Workspace, this is where you'll enter the code to execute.
  2. In the World menu, select "Tools" > "Transcript", this is where results will be displayed.

In the Workspace window enter the following code:

  1. Transcript show: 'Hello World'; cr.
  2.  

There are two ways to run the code. You can either right-click on the same line as the code and select "do it" or fellow keyboard addicts can type Alt-d while the cursor is on the same line as the code. In either case the words "Hello World" will then appear in the Transcript followed by a new-line. You might also see some paired numbers that come up during the process, this is a side effect of the Transcript being where logging data for the system in general is sent.

Understanding the code you just Executed

One element at a time:

  • Transcript is the object of interest, generally objects will start with a lowercase letter, but this is a special case
  • show: is a method (message) that is called (sent) to the Transcript object. This says that whatever object it is given should be written to the Transcript window, the : indicates that it takes an argument which is...
  • 'Hello World' is a string, note that Smalltalk strings are surrounded by single, not double quotes.
  • ; indicates the end of one method, but that the following method is also getting sent to the same object.
  • cr another method that is sent to Transcript and writes a new line to the Transcript window.
  • . indicates the end of a statement.

The Code

Coding in Smalltalk

The first step you'll take in your Smalltalk project is to add it to the Packages pane of the System Browser window. To do this:

  1. Make sure that the Packages pane is selected, left-clicking it will do the trick.
  2. Right-click in the Packages pane and select "add category..."
  3. Enter a name that works for you and click OK. (Mine was "Virtuous-Demo", remember, this is just to keep your code organized)

Now that you've added your category, select it from the Packages pane, notice that in the Edit Pane there's a template for creating a class:

  1. Object subclass: #NameOfSubclass
  2.   instanceVariableNames: ''
  3.   classVariableNames: ''
  4.   poolDictionaries: ''
  5.   category: 'Virtuous-Demo'
  6.  

You'll want to add a new class:

  1. Change '#NameOfSubclass' to '#Greeter'
  2. Right click in the Edit pane and select "accept" (or type alt-s) to write your class to the system.

Now you can see the new class in the Classes pane. In the Protocols pane click "as yet unclassified", this is a generic bucket for any methods you write without sorting them. Now you can see a template for a method in the Edit pane:

  1. messageSelectorAndArgumentNames
  2.   "comment stating purpose of message"
  3.  
  4.   | temporary variable names |
  5.   statements
  6.  

Start writing your method, since there's going to be no need to track temporary data within an object I made this a "class" rather than "instance" method, so click the "class" button underneath the class pane. Now change the Edit pane like so:

  1. sayHello
  2.   "Greet the User"
  3.  
  4.   Transcript show: 'Hello World'; cr.
  5.  

The first line is the method name, followed by a comment. I removed the | temporary variable names| because there was no need for them, and put the actual action of the method in the last line.

When you've finished entering the method "accept" it the same way you did with the class. When you "accept" a new method for the first time, it will ask you to enter your full name. Smalltalk automatically tracks all changes to the system and it will uses each individual's name to track who has made the changes.

To try your new method out, type Greeter sayHello. into the Workspace and then execute it.

Arguments in Methods

To get an idea of how arguments, I wrote a version of sayHello that knows who it's talking to. To add another method click "as yet unclassified" in the Protocols pane again and the Edit pane will be populated with the template again, add the method sayHello: as below:

  1. sayHello: toWho
  2.   "Greet the User"
  3.  
  4.   Transcript show: ('Hello ', toWho); cr.
  5.  

Inside the method declaration is the argument list. To indicate that a method has an argument append a : to it and follow it with the argument name. In the body of the method there's one more bit of Smalltalk syntax the , operator concatenates two strings. Strictly speaking it's not Smalltalk syntax, but just an operator attached to the String class. I'll get into the details of operator declaration in a later article.

Try this method by typing Greeter sayHello: 'Professor'.

Final Summary

Nice things about Smalltalk so far:

  • Very simple syntax
  • Very clear code

Difficult things about Smalltalk:

  • Learning the environment
  • Resisting the urge to spend hours just playing with the system instead of working

Coming Up

Next week I'll be putting together a class for calculating the "FizzBuzz" problem and unit test it using Pharo's integrated unit test system.

Resources

  • Squeak: Squeak Smalltalk is the basis of many of the modern free Smalltalk implementations
  • Pharo: Pharo is a professional design system based on Squeak
  • Smalltalk Zen: Dimitri Zagidulin's informative page about web development in Pharo/Squeak
  • Smalltalk Language Notes: A nice reference for a lot of basic Smalltalk programming