Thursday, 29 September 2011

Seven in Seven - Prolog is doing my head in.

It's day 2 of the Prolog section and my brain is suffering, I had forgotten how much unlike other languages Prolog is, and we haven't even got to backtracking yet. Things got so bad that I dug out my original copy of Clocksin and Mellish -It is so old the pages have actually yellowed and the reference implementations are for a DEC-10 and PDP-11! It seems to be helping to think of Prolog as a goal-seeking database, i.e. a collection of facts that you can ask questions of, it's quite cute that when you run a program Prolog answers 'yes' or 'no'.

Anyway the exercises, trivially they can be answered thus :

| ?- reverse([12,4,5,7],SL).

SL = [7,5,4,12]

| ?- min_list([12,4,5,7],SL).

SL = 4

| ?- sort([12,4,5,7],SL).  

SL = [4,5,7,12]

(1 ms) yes

But we ought to try a bit harder, so :

revappend([], Ys, Ys).
revappend([X|Xs], Ys, Zs) :- revappend(Xs, [X|Ys], Zs).

rev(Xs,Ys) :- revappend(Xs,[],Ys).

I pinched this in the end, after repeated attempts to use 'is' on something that isn't an arithmetic expression.

smallest(S,[H|T]) :- smallest(Ss,T), H >= Ss, S is Ss.
smallest(S,[H|T]) :- smallest(Ss,T), H < Ss, S is H.
This one is all mine, alas. It's not tail-recursive so it would be inefficient. Here I have added a rule for each case -but it might be possible to use an 'if' statement.

Finally the sort -I can't imagine that this is very efficient either, it works by taking the smallest member off the original list and putting it add the head of a new list, this happens repeatedly (through recursion) until the original list is empty :-

jsort([], Ys, Ys).
jsort(Xs, Ys, Zs) :- min_list(Xs,S), delete(Xs,S,X1s), jsort(X1s, [S|Ys], Zs).

sortj(Xs,Ys) :- jsort(Xs,[],Ys).

Monday, 26 September 2011

Seven in Seven - Prolog Day 1

I know it's out of sequence, but Io isn't making on the work Mac (it's fine on Fedora) so I'll jump ahead to Prolog for now. Prolog, it's nearly 30 years since I last had a play with Prolog and I eventually developed a soft spot for it -let's see if I still feel this way nowadays, or whether the soft spot is the bottom of the compost heap.

From memory Prolog stands for 'Programming with Logic' and it was popular with the Japanese AI community back in the 1980s, when they were taking over the world.  It is based around 'first order predicate calculus', and if I had my notes I'd tell you what it meant.  One of the main things to take from it though, is that Prolog is a formal language based on mathematics, and thus (in some sense) provable. Another formal language, that you may have heard of? SQL is based on set theory and in an ideal world is provable -E & OE, YMMV, not all implementations are equal, shares may go down as well as up!

First black mark, likes(X, Y) isn't the same as likes (X, Y) -the first is correct- in GNU Prolog.

Exercise : Create a knowledge base representing musicians and instruments. Also represent musicians and their genre of music.

I did this using tuples :
musician('Richard Thompson','Guitar','Folk') .
musician('Kathryn Tickell','Uillean Pipes','Folk') .
musician('John Lee Hooker','Guitar','Blues') .
 Which allows me to write queries like :

| ?- musician(Who,'Guitar',Genre).

Genre = 'Folk'
Who = 'Richard Thompson' ? a

Genre = 'Blues'
Who = 'John Lee Hooker'


Very pretty, but at the end of the day it's just a database query.

Friday, 23 September 2011

Seven in Seven - Ruby Day 3

This is the day hat the light is supposed to dawn -unfortunately I was in the pub last night and it feels like midnight in Svalbard on December the 21st. I think I'm also somewhat underwhelmed because Ruby is familiar territory, I did a little bit a few years ago and I've just carried out a project in Python so I'm just left thinking 'and...'

Exercise -extend the RubyCsv class to iterate and return CsvRow objects which you can index via 'method missing'

Again I'm not going  to post the complete code, aside from anything else there's a notice at the top saying that it can't be used in articles. For the iteration I mixed in Enumerable, changed @cvs_contents to an attr_reader and defined the 'each' method :

def each
  @csv_contents.each { |i| yield i }

@cvs_contents isn ow an array of CsvRow objects :

class CsvRow
        attr_accessor :contents, :index

        def initialize idx,row
                @contents = []
                @index = idx
                @contents = row.split(', ')

        def method_missing name, *args
created thus :

I don't really like having the header with each object, and their might be a way around this by creating the class on the fly, populating a class variable with the header list, but see the first paragraph.

What have I learned
Mixin is a powerful concept -but not unique to Ruby. method_missing is a powerful idea -and bloody dangerous. I have achieved the same thing in PHP by overriding __call() and I think that was safer.

Ruby syntax is nice, at least you don't have to scatter ':'s everywhere as you do in Python, it's more consistent than PHP and prettier than Perl5 which  generally looks as though a demented spider has been dancing on your keyboard.

Thursday, 22 September 2011

Seven in Seven, Ruby Day 2

Here we're starting to get a little deeper into Ruby, coming across a few nice features, such as code blocks (closures) and mixins. Still not really sure what the fuss is about though.

What did I learn?

Ruby is starting to look quite like python. Duck typing can catch you out : a regex pattern looks like a sting, quacks like a string, but doesn't waddle like a string. Ruby has nicked some of Perls' pattern-matching syntax, which is a good thing as it's great for rule-based input processing.

Exercise : Can we translate a hash to an array, and can we iterate over a hash?

Well, yes we can :


numbers = {1=>'one', 2=> 'two', 3=>'three', 4 => 'four'}
num_array = []

numbers.each do |num, str|
p 'My class is ' + num_array.class.to_s
p 'Element class is ' + num_array[0].class.to_s
puts num_array

 Of course we could have just used numbers.flatten()

This exercise is to print the numbers 1 to 16 in groups of 4

#Old school
i = 0
ary = []
(1..16).each do |num|
        if i % 4 ==  0
                if i > 0
                        p ary
                ary = []
        i = i + 1
p ary

# One liner -using a code block
(1..16).each_slice(4) {|ary| p ary}

Exercise 3 : Populate the Tree class from a hash.

 I'm not going to put all the code up for this, and I struggled a bit to get it going. The solution that I settled on was to have two classes,  a Tree class that took the hash argument which extended a Node class that was the basic structure.

The Node initializer looks like this :
def initialize(name, node = {})
    @children = []
    @node_name = name
    node.each { |key,child| @children.push(,child)) }

So it just build the tree recursively.

Exercise 4 implement grep

Grep implementation, matches a string against lines from a file,
outputs the line number and contents of the matched line

usage : rb_grep pattern file

i = 1[1],"r") do |f|
        pattern =[0])
        while line =  f.gets 
                line =~ pattern and printf("%d : %s", i,line)
                i = i + 1

Tuesday, 20 September 2011

Seven in Seven : Ruby Day 1.

Here we go, day 1, Bonus challenge -guess a number.


guess = 1

while guess > 0
        num = rand(10)
        guess = gets.to_i
        if guess > num
                puts "Too high was : " + num.to_s
        elsif guess < num
                puts "Too Low was : " + num.to_s
                puts 'Just Right'

Bonus tip, the ruby interpreter is called irb, and doesn't necessarily come with the ruby package.

Monday, 19 September 2011

The Road to Oxiana

by Robert Byron

Byron  was a pre WWII travel writer, indeed he died when his ship was torpedoed in 1941. The Road to Oxiana is the diary of a trip he made to Afghanistan in 1933-4, it can be read on many levels, from 'travelogue of an upper-class brit abroad' to the 'wanderings of an archaeological aesthete'.

One of the main joys of the book is that Byron is always well-written and forthright, for instance on the Venice Lido from the first paragraph :-
 The bathing, on a calm day, must be the worst in Europe: water like hot saliva, cigar-ends floating into one's mouth and shoals of jellyfish.

Lifar came to dinner. Bertie mentioned that all whales have syphilis.
The journey is travelling in the old style, things happen when they will, cars break, rivers flood roads, visas are granted and denied on a whim -his whole trip seems to run several months over its allotted time, and in the end he never does see the Oxus.

Byron's true passion if for architecture -I advise you to cultivate a knowledge of the squinch, it'll be useful for scrabble if nothing else- again the best I can do is to quote, this is about the Friday Mosque in Isfahan :

...But while the larger lacked the experience necessary to its scale the smaller embodies that precious moment between too little and too much,when the elements of construction have been refined of superfluous bulk, yet still withstand the allurements of superfluous grace; so that each element, like the muscles of a trained athlete, performs its function with winged precision, not concealing its effort as over refinement will do, but adjusting it to the highest degree on intellectual meaning.
 All in all it's worth taking the journey with Byron and listening to his story telling on the way. You wouldn't want to be on the sharp end of his tongue though -even if he does dish it out fairly impartially.

Wednesday, 7 September 2011

Haskell - 7 languages in 7 weeks, Day 2

Haskell Day 2 Exercises

Write a Haskell function to convert a string to a number. The string should be in the form of $2,345,678.99 and can possibly have leading zeros.

As I mentioned in the last post, there was a better way to solve this than tail recursion.

strToNum :: String -> Float
strToNum(str) = let num = [x|x <- str,  (x >= '0' && x <= '9') || x == '.']
       in read num :: Float

This function uses list comprehension to filter the string for valid characters and the uses read to convert the filtered string into a floating point number. As you can see it's very concise, and when you are used to the form very readable. This says num is all the valid (0-9 and .) characters from the string str. 

Write a function that takes an argument x and returns a lazy sequence that has every third number, starting with x. Then, write a function that includes every fifth number, beginning with y. Combine these functions through composition to return every eighth number, beginning with x + y.

stepList x n = take 5 [x,x+n..]

threeList x = stepList x 3
fiveList x = stepList x 5

eightList x y = zipWith (+) (threeList x) (fiveList y)

So, the lazy sequence is [x,x+n..] to stop things running off into infinity I've used take to perform the lazy eveluation. Again, Haskell can be very concise -look at zipWith in eightList.

Use a partially applied function to define a function that will return half of a number and another that will append \n to the end of any string.

half = (*) 0.5

This is quite cunning (of Haskell). Inside Hskell all functions are, I believe, curried -that is they take only one argument. As a bit of syntactic sugar Haskell support infix operators, but you can force them to their curried form but surrounding the operator in brackets.  Since the functions are curried they are quite happy to have a dangling second argument, in fact we have here a function that is 'multiply by 0.5'.

backAppend x y = y ++ x
append = backAppend "\n"

The same applies to the append function here, only we have had to define backAppend to get the arguments the way round we want.

I'm going to leave the second set for now, and maybe come back to them at the end.

Tuesday, 6 September 2011

Haskell, where vs let in guards

I'm making a stab at learning Haskell, a functional programming language, and as part of it I'm going through the section in Seven Languages in Seven Weeks, one of the exercises is to convert a string representation of a number to a real (floating point) number, so " $2,345,678.99" to  2345678.99.
Here's my first stab :

import Char

strToNum :: String -> Float

sToN :: (Float, Int, String) -> Float
sToN (acc, dec_place, []) = acc
sToN (acc, dec_place, xs)
        | head xs == '$' = sToN (acc, dec_place, tail xs)
        | head xs == ',' = sToN (acc, dec_place, tail xs)
        | head xs == '.' = sToN (acc, 1, tail xs)
        | dec_place > 0 =
                let  newacc = acc + (fromIntegral (digitToInt (head xs)) )  / (10.0  ^ dec_place)
                in sToN (newacc, dec_place + 1, tail xs)
        | otherwise =
                let newacc = acc * 10.0 + (fromIntegral (digitToInt (head xs)) )
                in sToN (newacc, dec_place, tail xs)

strToNum "" = 0.0
strToNum(xs) = sToN (0.0, 0, xs)

It's a bit brute force and ignorance, but it works. Just thought of a more elegant solution though. The point of this post is the use of 'let' rather than 'where' in the guard expression. The guards (| expressions) handle the various characters and states of the string, and in the two that alter the accumulator define the new value via a 'let'. Initially I tried using a 'where' for this, but it seems that you can only have one per pattern sequence, it would seem that this is because 'let' is a proper expression whilst 'where' is not.

BTW I also tried this with lambdas, but fell foul of the type system.

I quite like this pattern matching approach in general, and have used it in Perl a lot, as it is quite easy to see each 'case' and the logic that goes with it.