Thursday, 6 August 2015

Returning from a function

I remember the first time I saw someone violate the return conventions in a function.

This was in submission to Personal Computer World magazine.  They used to run a column where people could write in with their own utility routines.

Someone submitted a routine that returned the current contents of the program counter - that is to say where in the code you are currently executing.

The routine looked like this:

; v.1
          PUSH HL

Perfectly simple; you pop the return address into the HL pair then push it back on the stack and then return as normal.  You might use it like this:

76CC      ; on return, HL contains 76CC

The author submitted comprehensive documentation about the routine, aiming at some arcane humour in setting a new record for comment-to-code line count ratio.

However the record was promptly snatched away by the editor of the column, who pointed out that the routine can be rewritten thus:

; v.2
          JP   (HL)

You can hear the original author saying damn.  Or can you?  There is more than just a simple optimisation that separates v.2 from v.1 - in fact a different way of thinking is at work.  I would have written v.1.  I know about the JP (HL) instruction but until I saw this I would never have thought of v.2.

I pondered for a long time before I was convinced that v.2 would really work.  It looks like one of those dodgy bodges that looks good but falls over when you apply it to the real world.  Surely what happens when the routine that calls WHEREAMI returns to whereever it came from?  No that would work.

It's just so... disturbing... to see someone ending a function with a jump rather than a return, much as it would be to see someone leave a meeting by leaping out of the window rather than walking through the door.

In v.1 we temporarily allow ourselves to peek at the stack, and make a strict point of putting it all back where it was before we proceed.  It is not our business to mess with the stack.  It is not our business to tell the processor where to go next.  That is all taken care of automatically by CALL and RET and we do poke around there unless we want to lose a finger in the machinery.

In v.2 the attitute is different.  We take responsibility for the flow of control, we grab the return address and use it ourselves - this is a significantly different way to think about code.

Tuesday, 4 August 2015

A Quick Visit to the Database

To tie together these threads let's actually issue that query to the database from Haskell...

Link to the modules for database access via ODBC (one I prepared earlier):

> :m +Database.HDBC
> :m +Database.HDBC.ODBC

Create a connection using the credentials set up in the ODBC settings:

> conn <- connectODBC "DSN=Lethbridge;UID=POLLY;PWD=S0wn4kb8J6f"

Get a record set back by sending the query via the connection:

> records <- quickQuery conn "select dept, sum(salary) from employees group by dept;" []

And what do we get back?

> records
[[SqlByteString "Ed",SqlInt32 175],[SqlByteString "MS",SqlInt32 320],[SqlByteString "Yale",SqlInt32 160]]

Close the session...

> commit conn
> disconnect conn

Monday, 3 August 2015

A Random Thought

I recently listened to the podcast on Artificial Intelligence from the Programming Throwdown boys and I was struck by the thought that the phrase "No fruit flies like a banana" exactly fits the opening theme of Brahms' Second Piano Concerto.

List Comprehensions And Beyond

From Simon Peyton-Jones web site I find a link to a paper discussing extensions to list comprehensions to make them more like SQL select statements.

To make use of these we need to do two things: firstly warn the GHCi that I will be using the language extensions:

:set -XTransformListComp

And then import some extra functionality it will need:

:module +GHC.Exts

As an example we have a table of people with the Name (String), Dept (String) and Salary (Int).
To see the contents of this table on the database we issue a basic SQL select command:


And the results are

Name Dept Salary
Simon MS 80
Erik  MS 100
Phil Ed 40
Gordon Ed 45
Paul Yale 60
Polly MS 45
Sue Ed 90
Jill Yale 100
Jackie MS 95

And how we would replicate this in Haskell code?

Start by setting out a couple of type synonyms to make the database fields clearer:

type Name = String
type Dept = String
type Salary = Int

And here is our database table as a Haskell list of tuples:

employees :: [(Name, Dept, Salary)]
employees = [("Simon", "MS", 80)
            ,("Erik", "MS", 100)
            ,("Phil", "Ed", 40)
            ,("Gordon", "Ed", 45)
            ,("Paul", "Yale", 60)
            ,("Polly", "MS", 45)
            ,("Sue", "Ed", 90)
            ,("Jill", "Yale", 100)
            ,("Jackie", "MS", 95)]

In Haskell the query to select all the records comes out as a simple list comprehension:

selectAll = [ (name, dept, salary) |
              (name, dept, salary) <- employees ]

The result is so:

*Main> selectAll

So far so normal.  For our first enhancement we want to be able to specify an order for the output records.  For example let us see the records in order of increasing salary.  This is simple enough with an "order by" clause in SQL:

name, salary
order by salary

name salary
Phil 40
Gordon 45
Polly 45
Paul 60
Simon       80
Sue 90
Jackie 95
Jill 100
Erik 100

To do the same in a list comprehension we add an extra use for the keyword then, which
here lets us introduce the function sortWith into the expression:

selectWithOrder = [ (name, salary) |
                    (name, dept, salary) <- employees,
                    then sortWith by salary ]

The sortWith function sorts a list of elements using the user supplied function to project something out of each element

*Main> :t sortWith
sortWith :: Ord b => (a -> b) -> [a] -> [a]

So here we are sorting by the salary field of the record:

*Main> selectWithOrder

But nobody wants to see who is getting the lowest salary.  In SQL we add the keyword desc to see the results sorted into descending order:

name, salary
order by salary desc

name  salary
Erik 100
Jill 100
Jackie 95
Sue 90
Simon 80
Paul 60
Polly 45
Gordon 45
Phil 40

To do the same in our list comprehension we use the newtype Down like this:

selectWithReverseOrder = 
    [ (name, salary) |
      (name, dept, salary) <- employees,
      then sortWith by Down salary ]

Down has the ingenious function of inverting the sort order:

newtype Down a = Down a deriving (Eq, Show, Read)

instance Ord a => Ord (Down a) where
    compare (Down x) (Down y) = y `compare` x

So if you compare Down x with Down y you get the reverse of what you'd get if you compare x with y.  So our comprehension now comes up with the top salary first:

*Main> selectWithReverseOrder

We can also create selections with group functions such as sum: for example we need to list the departments and their total salary spends. In SQL we group by a field and apply functions such as sum():

dept, sum(salary) as [total salary]
group by

Which looks like this:

dept total salary
Ed 175
MS 320
Yale 160

The corresponding list comprehension is this:

selectByGroup = [ (the dept, sum salary) |
                  (name, dept, salary) <- employees,
                  then group by dept using groupWith ]

*Main> selectByGroup

There are several new things happening here.

Here we have a group by clause added to the list comprehension.  This does something dodgy to the fields: what we are returning is not individual dept and salary fields but lists of fields, so we add the the function and the sum function to reduce these back to a single record.

The function the is a new one: it checks first that all the elements of the list are identical and then returns just that duplicated element.  (It bears no resemblance to the Common Lisp operator of the same name, I checked)

*Main> :t the
the :: Eq a => [a] -> a

The function groupWith uses the function that you supply, with type (a -> b), to projects out an element (the one of type b) from each list element in your list - - it uses the b-type item to sort the input list and then to form groups by equality on these projected elements.

*Main> :t groupWith
groupWith :: Ord b => (a -> b) -> [a] -> [[a]]

But I just want to see the top one... the department with the largest spend...

In SQL I can opt to see the top so many of the results, like this:

select top 1
dept, sum(salary) as [total salary]
group by
order by sum(salary) desc

Which comes out as:

dept total salary
MS 320

In our newly empowered list comprehensions we can use the then keyword this time to bring in the standard function take, to take just the first record from the result set:

selectMaxGroup = [ (the dept, sum salary) |
                   (name, dept, salary) <- employees,
                   then group by dept using groupWith,
                   then sortWith by Down salary,
                   then take 1 ]

*Main> selectMaxGroup