Lojic Technologies

Posts Tagged ‘programming

Programming in Standard ML – Part 3

leave a comment »

Table of Contents

Chapter 6 – Case Analysis

Tuple types are homogeneous e.g. all values of type int*real are pairs containing an int and a real. Match failures occur at compile time. Types that have more than one form, such as int, are heterogeneous. Pattern matches fail at run time as a bind failure.

ML defines functions over heterogeneous types using clausal function expressions. For example:

fn pat1 => exp1
 | pat2 => exp2
 | ...
 | patn => expn

Each component pat => exp is called a clause, or a rule. The entire assembly of rules is a called a match. For example:

val recip : int -> int =
    fn 0 => 0 | n:int => 1 div n

The fun notation is generalized so we can be more concise:

fun recip 0 = 0
  | recip (n:int) = 1 div n

Case analysis on the values of a heterogeneous type is performed by application of a clausally-defined function. The notation:

case exp
  of pat1 => exp1
   | ...
   | patn => expn

is short for the application:

(fn pat1 => exp1
  | ...
  | patn => expn)
exp

Matches are subject to two forms of “sanity check” – exhaustiveness checking and redundancy checking.

Chapter 7 – Recursive Functions

For a function to be able to call itself, it needs a name. For example:

val rec factorial : int->int =
    fn 0 => 1 | n:int => n * factorial (n-1)

or using fun notation:

fun factorial 0 = 1
  | factorial (n:int) = n * factorial (n-1)

Iteration

If we define a helper function that accepts an accumulator we can reduce the storage needed:

fun helper (0,r:int) = r
  | helper (n:int,r:int) = helper (n-1,n*r)
fun factorial (n:int) = helper (n,1)

It’s better programming style to hide the helper function w/in a local declaration:

local
    fun helper (0,r:int) = r
      | helper (n:int,r:int) = helper (n-1,n*r)
in
    fun factorial (n:int) = helper (n,1)
end

Tail recursive functions are analogous to loops in imperative languages – they iterate the computation w/o needing auxiliary storage.

Mutual Recursion

Definitions which are mutually recursive can be joined together with the and keyword to indicate they are defined simultaneously by mutual recursion:

fun even 0 = true
  | even n = odd (n-1)
and odd 0 = false
  | odd n = even (n-1)

Chapter 8 – Type Inference and Polymorphism

Standard ML allows you to omit type information whenever it can be determined from context. Consider the following:

fn s:string => s ^ "n"

There is no need to declare the type of s since it can be inferred from the context, so we may write:

fn s => s ^ "n"

A type scheme is a type expression involving one or more type variables standing for an unknown, but arbitrary type expression. Type variables are written ‘a (pronounced alpha), ‘b (pronounced beta), etc. For example, the type scheme ‘a->’a has instances int->int, string->string, (int*int)->(int*int), and (‘b->’b)->(‘b->’b), etc. It does not have the type int->string.

We may bind an identity function to the variable I as follows:

val I : 'a->'a = fn x=>x

We may also write:

fun I(x:'a) : 'a = x

Standard ML eliminates the need to ascribe a type scheme to the variable:

val I = fn x=>x

or

fun I(x) = x

Chapter 9 – Programming with Lists

The values of type type list are the finite lists of values of type type:

1. nil is a value of type typ list.
2. if h is a value of type typ, and t is a value of type typ list,
   then h::t is a value of type typ list.
3. Nothing else is a value of type typ list.

The type expression typ list is a postfix notation for the application of the type constructor list to the type typ.

A value val of type typ list has the form:
val1 :: (val2 :: (… :: (valn :: nil) … ))

The :: operator is right-associative, so we may omit parentheses:
val1 :: val2 :: … :: valn :: nil

Or, we may use list notation:
[ val1, val2, …, valn ]

Computing With Lists

Some examples:

fun length nil = 0
  | length (_::t) = 1 + length t

Note we do not give a name to the head of the list, instead we use a wildcard _

fun append (nil, l) = l
  | append (h::t, l) = h :: append (t, l)

The latter is built into Standard ML and is written using infix as: exp1 @ exp2

fun rev nil = nil
  | rev (h::t) = rev t @ [h]

The running time of the latter is O(n2). The following definition makes use of an accumulator and has a running time of O(n):

local
    fun helper (nil, a) = a
      | helper (h::t, a) = helper (t, h::a)
in
    fun rev' l = helper (l, nil)
end

Chapter 10 – Concrete Data Types

Non-Recursive Datatypes

Example of nullary i.e. zero argument, constructors:

datatype suit = Spades | Hearts | Diamonds | Clubs

It is conventional to capitalize the names of value constructors, but this is not required by the language.

Datatypes may be parameterized by a type:

datatype 'a option = NONE | SOME of 'a

The values are NONE or Some val, where val is a value of type typ. The option type constructor is pre-defined in Standard ML.

Option types can also be used in aggregate data structures:

type entry = { name:string, spouse string option }

An entry for an unmarried person would have a spouse field with a value of NONE.

Recursive Datatypes

datatype 'a tree =
  Empty |
  Node of 'a tree * 'a * 'a tree

1. The empty tree Empty is a binary tree.
2. If tree_1 and tree_2 are binary trees, and val is a value of type type, then Node (tree_1, val, tree_2) is a binary tree.
3. Nothing else is a binary tree.
A function to compute the height of a binary tree, and one to compute the number of nodes:

fun height Empty = 0
  | height (Node (lft, _, rht)) = 1 + max (height lft, height rht)

fun size Empty = 0
  | size (Node (lft, _, rht)) = 1 + size lft + size rht

Heterogeneous Data Structures

The tree data type above requires that the type of the data items at the nodes must be the same for every node of the tree. To represent a heterogeneous tree, the data item must be labelled with enough info to determine the type at run-time.

datatype int_or_string =
  Int of int |
  String of string

type int_or_string =
  int_or_string tree

Datatype declarations and pattern matching can be useful for manipulating the abstract syntax of a language. Consider an example representing arithmetic expressions:

datatype expr =
  Numeral of int |
  Plus of expr * expr |
  Times of expr * expr

fun eval (Numeral n) = Numeral n
  | eval (Plus (e1, e2)) =
    let
        val Numeral n1 = eval e1
        val Numeral n2 = eval e2
    in
        Numeral (n1+n2)
    end
  | eval (Times (e1, e2)) =
    let
        val Numeral n1 = eval e1
        val Numeral n2 = eval e2
    in
        Numeral (n1*n2)
    end

If we extend the expr datatype as follows:

datatype expr =
  Numeral of int |
  Plus of expr * expr |
  Times of expr * expr
  Recip of expr

The compiler will complain about eval being incompatible with the new version of expr. Recompiling eval will produce an inexhaustive match warning since eval lacks a case for Recip. This is one of the benefits of static typing provided in Standard ML.

Written by Brian Adkins

August 15, 2009 at 2:43 pm

Posted in programming

Tagged with ,

Send Growl Notifications From Carbon Emacs On OSX

leave a comment »

I found a handy article for sending growl notifications from Emacs and made some modifications for my particular setup.

Step One: Register Emacs with Growl
We need to register Carbon Emacs with Growl. This is a one time setup task. The following AppleScript script can be run in Script Editor.

tell application "GrowlHelperApp"
	-- Declare a list of notification types
	set the allNotificationsList to {"Emacs Notification"}

	-- Declare list of active notifications.  If some of them
	-- isn't activated, user can do this later via preferences
	set the enabledNotificationsList to {"Emacs Notification"}

	-- Register our application in Growl.
	register as application "Emacs.app" all notifications allNotificationsList default notifications enabledNotificationsList icon of application "Emacs.app"
end tell

Step Two: Create Growl Notification Script
This is a template of the AppleScript that will be used in the Emacs Lisp function. It can be tested by executing it in the Script Editor.

tell application "GrowlHelperApp"
	notify with name "Emacs Notification" title "Emacs alert" description "Message!!!" application name "Emacs.app"
end tell

Step Three: Emacs Lisp Function
Create an Emacs Lisp function that can be invoked with a title and message.

(defun bja-growl-notification (title message &optional sticky)
  "Send a Growl notification"
  (do-applescript
   (format "tell application "GrowlHelperApp"
              notify with name "Emacs Notification" title "%s" description "%s" application name "Emacs.app" sticky %s
           end tell"
           title
           (replace-regexp-in-string """ "''" message)
           (if sticky "yes" "no"))))

This can be tested with the following function which sends two growl notifications. The “sticky” one requires an explicit dismissal.

(defun bja-growl-test ()
  (interactive)
  (bja-growl-notification "Emacs Notification" "This is my message")
  (bja-growl-notification "Emacs Notification" "This is my sticky message" t))

UPDATE: I noticed bja-growl-notification was failing if the message had embedded double quotes, so I added a call to replace-regexp-in-string to replace them with two apostrophes.

UPDATE 2: My main motivation for setting this up was to be able to generate growl notifications from ERC (Emacs IRC client). However, I quickly realized that having a generic reminder that I can easily fire up from within Emacs is very handy. Here’s the code:

(defun bja-growl-timer (minutes message)
  "Issue a Growl notification after specified minutes"
  (interactive (list (read-from-minibuffer "Minutes: " "10")
                     (read-from-minibuffer "Message: " "Reminder") ))
  (run-at-time (* (string-to-number minutes) 60)
               nil
               (lambda (minutes, message)
                 (bja-growl-notification "Emacs Reminder" message t))
               minutes
               message))

Written by Brian Adkins

August 6, 2009 at 6:42 am

Posted in programming

Tagged with , ,

Use Ruby to parse NMEA sentences from your GPS

with 2 comments

I recently obtained a mobile broadband device that has a built in GPS receiver and can emit NMEA sentences. My old Garmin portable GPS can emit NMEA also, but it’s a pain to hookup to the laptop. Combining a GPS unit in a mobile broadband device is a great idea.

Update: it appears that the accuracy radius of the wireless card is quite a bit larger than my old Garmin unit. The Garmin is usually between 15 and 30 feet, but the Sierra Wireless 598U ranges from 100 to 1,000 feet or more.

After installing the ruby-serialport gem, I was able to write a simple Ruby program to read GPS information from the device and update a remote file on my web server to allow real time location tracking.

Add a simple server side script to read the file and update an iframed Google Map and you’re all set.

The code is also in the Ruby section of my sample code repository on Github.

sudo gem install ruby-serialport
#!/usr/local/bin/ruby
# Author: Brian Adkins
# Date:   2009/04/08
# Copyright 2009 Brian Adkins - All Rights Reserved
#
# Ruby program to retrieve and parse GPS information (via NMEA sentences)
# from a Sprint Sierra Wireless 598U device.
#
# ruby gps-nmea.rb                # prints latititude/longitude info
# ruby gps-nmea.rb update-remote  # scp a file of location info to a remote server
#
# This program depends on the ruby-serialport gem:
# sudo gem install ruby-serialport
#
# From: http://www.gpsinformation.org/dale/nmea.htm#GGA
#  $GPGGA,123519,4807.038,N,01131.000,E,1,08,0.9,545.4,M,46.9,M,,*47
# Where:
#      GGA          Global Positioning System Fix Data
#      123519       Fix taken at 12:35:19 UTC
#      4807.038,N   Latitude 48 deg 07.038' N
#      01131.000,E  Longitude 11 deg 31.000' E
#      1            Fix quality: 0 = invalid
#                                1 = GPS fix (SPS)
#                                2 = DGPS fix
#                                3 = PPS fix
#              4 = Real Time Kinematic
#              5 = Float RTK
#                                6 = estimated (dead reckoning) (2.3 feature)
#              7 = Manual input mode
#              8 = Simulation mode
#      08           Number of satellites being tracked
#      0.9          Horizontal dilution of position
#      545.4,M      Altitude, Meters, above mean sea level
#      46.9,M       Height of geoid (mean sea level) above WGS84
#                       ellipsoid
#      (empty field) time in seconds since last DGPS update
#      (empty field) DGPS station ID number
#      *47          the checksum data, always begins with *

require 'rubygems'
require 'serialport'

# Emacs macro to reset user modified values (highlight, then: M-x eval-region )
# ((lambda (&optional arg) "Keyboard macro." (interactive "p") (kmacro-exec-ring-item (quote ("USERNAME
"
372"HOSTNAME
"
372"REMOTE_DIR
"
372"" 0 "%d")) arg)))

# --- MODIFY THESE -- #
USERNAME   = ""  # Username for remote host
HOSTNAME   = ""  # Remote host name e.g. foo.com
REMOTE_DIR = ""  # Remote directory e.g. /var/www/bar
# --- MODIFY THESE -- #

port_str  = '/dev/cu.sierra05'
baud_rate = 9600
data_bits = 8
stop_bits = 1
parity    = SerialPort::NONE

sp = SerialPort.new(port_str, baud_rate, data_bits, stop_bits, parity)

# lat is of the form 4807.038 where the first 2 digits are degrees and
#   the remainder is minutes.
# dir is either 'N' or 'S'
def convert_lat lat, dir
  degrees = lat[0,2].to_f + (lat[2,lat.length-2].to_f / 60.0)
  dir == 'N' ? degrees : -degrees
end

# lon is of the form 01131.000 where the first 3 digits are degrees and
#   the remainder is minutes.
# dir is either 'E', or 'W'
def convert_lon lon, dir
  degrees = lon[0,3].to_f + (lon[3,lon.length-2].to_f / 60.0)
  dir == 'E' ? degrees : -degrees
end

TEMP_PATH = '/tmp'
TEMP_FILE = 'location.txt'

def update_remote_info lat, lon
  File.open("#{TEMP_PATH}/#{TEMP_FILE}", 'w') do |tf|
    tf.puts Time.now.to_s
    tf.puts "#{lat},#{lon}"
  end
  puts 'Updating remote location info'
  `scp #{TEMP_PATH}/#{TEMP_FILE} #{USERNAME}@#{HOSTNAME}:#{REMOTE_DIR}/#{TEMP_FILE}`
  File.delete("#{TEMP_PATH}/#{TEMP_FILE}")
end

# 99 requests should be sufficient to find a $GPGGA sentence
99.times do
  if (str = sp.gets) =~ /^$GPGGA/
    fix = str.split(',')
    if fix[6] == '1'
      lat = convert_lat(fix[2], fix[3])
      lon = convert_lon(fix[4], fix[5])
      if ARGV[0] == 'update-remote'
        update_remote_info(lat,lon)
      elsif
        puts "#{lat}, #{lon}"
      end
      exit 0
    end
  end
end

puts "Invalid data - GPS coordinates not found"

Written by Brian Adkins

April 8, 2009 at 11:07 am

Posted in programming, technology

Tagged with , , ,

Retrieve Sunrise, Sunset & Twilight Info in Ruby

with 5 comments

Sunrise, Sunset & Twilight

TwilightI was curious about the exact time of sunrise & sunset at my location, so I found this US Naval Observatory site. In the process, I learned a more precise definition of twilight. I wanted to be able to automate the process of retrieving the information, so my first attempt was to simply put the query parameters used in the form in the URL as an HTTP GET request, but the server wouldn’t accept that, so I needed to issue an HTTP POST request.

Ruby Code

Ruby is a great language for this sort of task, so I put together the following simple program:

require 'net/http'

YOUR_ID    = ''    # A unique ID per comment above
YOUR_CITY  = ''    # The name of your city
YOUR_STATE = ''    # Two letter state abbreviation

now   = Time.now
month = now.month
day   = now.day + 1 # Tomorrow
year  = now.year

Net::HTTP.start('aa.usno.navy.mil') do |query|
  response = query.post('/cgi-bin/aa_pap.pl',
    "FFX=1&ID=#{YOUR_ID}&xxy=#{year}&xxm=#{month}&xxd=#{day}&st=#{YOUR_STATE}&place=#{YOUR_CITY}&ZZZ=END")
  if response.body =~ /Begin civil twilight[^0-9]*(d+:d{2} [ap].m.).*Sunrise[^0-9]*(d+:d{2} [ap].m.).*Sunset[^0-9]*(d+:d{2} [ap].m.).*End civil twilight[^0-9]*(d+:d{2} [ap].m.)/m
    puts "#{month}/#{day}/#{year}"
    puts "Begin Twilight: #{$1}"
    puts "Sunrise       : #{$2}"
    puts "Sunset        : #{$3}"
    puts "End Twilight  : #{$4}"
  end
end

You just need to edit the three constants that begin with YOUR_. The id used on the Navy web form is ‘AA’, but they have a comment in the HTML that requests you use a unique id of your own up to 8 characters to help them with tracking. You can find a more complete version of the code in my github profile.

Emacs Goodness

After writing the above Ruby script, I made it executable, ‘chmod +x sunrise.rb’, and placed it in my path so I could write a simple Emacs function to invoke it.

(defun bja-sunrise ()
  "Display sunrise, sunset & twilight information."
  (interactive)
  (shell-command "sunrise.rb"))

Imagine my surprise when I invoked the Emacs apropos help ‘C-h a’ to see my newly defined function and discovered that Emacs, naturally, already has several commands to display sunrise/sunset information!

calendar-mouse-sunrise/sunset
Show sunrise/sunset times for mouse-selected date.
calendar-sunrise-sunset
Local time of sunrise and sunset for date under cursor.
sunrise-sunset
Local time of sunrise and sunset for today. Accurate to a few seconds.

It doesn’t, however, display twilight information, so my simple function still has a purpose in life. Emacs is awesome 🙂

Written by Brian Adkins

March 11, 2009 at 12:41 am

Digest Tag Population in Ruby

with 6 comments

I saw a post on comp.lang.lisp demonstrating the suitability of Common Lisp for functional programming. The poster asked to see versions in other languages including Ruby, so I thought I’d whip something up. Here’s the original post with description of the problem:

This one was too much fun for words in re how cool it is programming
with Lisp. I would like to see this in Ruby, Clojure, Qi, and
Scheme. The precise fun part tho is typing it all in in the final form
versus dividing the thing up into steps to get intermediate results,
ie, a test of one's mastery of one's language. Non-functional
languages I guess have no choice but to stop and assign temporaries.

Given:

(defparameter *pets*
  '((dog ((blab 12)(glab 17)(cbret 82)(dober 42)(gshep 25)))
    (cat ((pers 22)(siam 7)(tibet 52)(russ 92)(meow 35)))
    (snake ((garter 10)(cobra 37)(python 77)(adder 24)(rattle 40)))
    (cow ((jersey 200)(heiffer 300)(moo 400)))))

Write:

(defun digest-tag-population (tag-population pick-tags count)...)

Such that:

(digest-tag-population *pets* '(dog cat snake) 5)

=> ((DOG CBRET 82) (DOG DOBER 42) (CAT RUSS 92) (CAT TIBET 52) (SNAKE
PYTHON 77))

...the rules being:

- consider only the populations of tags (the first symbol in each
sublist) found in the parameter pick-tags, a list

- take only the  most populous of the union of the populations

- return (tag name population) of the most populous in this order:

    firstly, by position of the tag in pick-tags
    second, ie within a tag, in descending order of population

(defun subseq-ex (st e s)
  (subseq s st (min e (length s))))

(defun digest-tag-population (tag-population pick-tags count)
  (flet ((tagpos (tag) (position tag pick-tags)))
    (stable-sort (subseq-ex 0 count
                   (sort (loop for (tag population) in tag-population
                             when (tagpos tag)
                             append (loop for pop in population
                                        collecting (list* tag pop)))
                     '> :key (lambda (x)
                               (caddr x))))
      '< :key (lambda (x) (tagpos (car x))))))

(defparameter *pets*
  '((dog ((blab 12)(glab 17)(cbret 82)(dober 42)(gshep 25)))
    (cat ((pers 22)(siam 7)(tibet 52)(russ 92)(meow 35)))
    (snake ((garter 10)(cobra 37)(python 77)(adder 24)(rattle 40)))
    (cow ((jersey 200)(heiffer 300)(moo 400)))))

#+test
(digest-tag-population *pets* '(dog cat snake) 5)

And here is my Ruby version:

PETS = [
  [:dog, [[:blab, 12], [:glab, 17], [:cbret, 82], [:dober, 42], [:gshep, 25]]],
  [:cat, [[:pers, 22], [:siam, 7], [:tibet, 52], [:russ, 92], [:meow, 35]]],
  [:snake, [[:garter, 10], [:cobra, 37], [:python, 77], [:adder, 24], [:rattle, 40]]],
  [:cow, [[:jersey, 200], [:heiffer, 300], [:moo, 400]]]
]

def digest_tag_population tag_population, pick_tags, count
  tag_population.select {|e| pick_tags.include?(e[0]) }.
    inject([]) {|memo,obj| obj[1].each {|e| memo << [obj[0], e[0], e[1]] }; memo }.
    sort {|a,b| b[2] <=> a[2] }[0,count].
    sort_by {|e| [ tag_population.map{|p| p[0]}.rindex(e[0]), e[2] * -1] }
end

digest_tag_population(PETS, [:dog, :cat, :snake], 5)

Within the function:
Line 1: select elements that match the pick tags
Line 2: map to a list of tuples of the form [:dog, :blab, 12]
Line 3: sort the list of tuples by population and select the first count of them
Line 4: sort by tag position, population

Output:

[[:dog, :cbret, 82],
[:dog, :dober, 42],
[:cat, :russ, 92],
[:cat, :tibet, 52],
[:snake, :python, 77]]

I think Ruby compares very favorably. What do you think? Feel free to submit a version in another language.

Written by Brian Adkins

March 1, 2009 at 12:47 am

Posted in programming

Tagged with , , , ,

jQuery in Action

with one comment

jQuery in Action cover image I just finished “jQuery in Action” by Bear Bibeault and Yehuda Katz. It’s an excellent book on the jQuery JavaScript library. The book comes with a number of example labs to try out various jQuery/JavaScript techniques w/o having to write a lot of code.

There’s plenty of jQuery information online, but “jQuery in Action” easily paid for itself in saved time in getting me up to speed quickly. It’s nicely organized, well written and the editing/quality control seems to be higher than many tech books (although that bar isn’t very high!). It also has a brief, 20 page, tutorial on JavaScript that you may find helpful.

jQuery may not satisfy the zealots on comp.lang.javascript, but I’ve found it to be an excellent JavaScript library thus far, and I think this book was the fastest way to becoming proficient.

Written by Brian Adkins

January 20, 2009 at 4:49 pm

Posted in books, programming

Tagged with , ,

Ruby Dynamic Method Invocation Performance

leave a comment »

Ruby is a very flexible and expressive language. A recent question posted by a Ruby newbie got me looking through my IRC logs for a discussion about the performance of various dynamic method invocation approaches, so I thought I’d share some performance results.

Ruby is currently my primary programming language, and I like it a lot; however, the conciseness (except for blocks) and performance of its higher order function capabilities could be improved. Scheme and Haskell beat it in this regard.

Consider three versions of a higher order function, caller, and associated ways of providing information to it to allow invoking a method dynamically given a pre-existing object and argument:

# 1. lambda
def caller fn
  fn.call(obj, arg)
end

caller(lambda {|obj,arg| obj.meth(arg) })

# 2. send
def caller sym
  obj.send(sym, arg)
end

caller(:meth)

# 3. bind/call
def caller meth
  meth.bind(obj).call(arg)
end

caller(MyClass.instance_method(:meth))

A simple benchmark of the three approaches with results follows. The benchmark uses an elide(n) method that has been added to String:

lam = lambda {|s,n| s.elide(n) }
sen = :elide
met = String.instance_method(:elide)

bm(5) do |x|
  x.report('lambda') { 100_000.times { lam.call('abcdef',4) } }
  x.report('send') { 100_000.times { 'abcdef'.send(sen,4) } }
  x.report('meth') { 100_000.times { met.bind('abc').call(4) } }
end

           user     system      total        real
lambda 1.460000   0.510000   1.970000 (  1.982085)
send   0.810000   0.260000   1.070000 (  1.075201)
meth   0.660000   0.250000   0.910000 (  0.913455)

# results with the 3 preparation lines w/in their respective loops

           user     system      total        real
lambda 1.900000   0.590000   2.490000 (  2.498358)
send   0.800000   0.250000   1.050000 (  1.068035)
meth   0.760000   0.260000   1.020000 (  1.021275)

I personally like the lambda approach, but Ruby does impose a penalty for using it.

Written by Brian Adkins

December 22, 2008 at 4:23 pm

Posted in programming

Tagged with , ,

How to Write a Spelling Corrector in Ruby

with 16 comments

Update 10/16/2015: Please see the Racket Version also.

Peter Norvig wrote a simple spelling corrector in 20 lines of Python 2.5,
so I thought I’d see what it looks like in Ruby. Here are some areas I’m not pleased with:

  1. List comprehensions in Python made the edits1 function more elegant IMO.
  2. The boolean expression in the correct function evaluates empty sets/arrays as false in Python but not in Ruby, so I had to add the “result.empty? ? nil : result” expression to several functions. I expect there’s a better way to handle this also.

Otherwise, the translation was pretty straightforward.

Here’s a link to Norvig’s page:
http://www.norvig.com/spell-correct.html

That page includes a link to a text file that I saved locally as
holmes.txt: http://www.norvig.com/holmes.txt

def words text
  text.downcase.scan(/[a-z]+/)
end

def train features
  model = Hash.new(1)
  features.each {|f| model[f] += 1 }
  return model
end

NWORDS = train(words(File.new('holmes.txt').read))
LETTERS = ("a".."z").to_a.join

def edits1 word
  n = word.length
  deletion = (0...n).collect {|i| word[0...i]+word[i+1..-1] }
  transposition = (0...n-1).collect {|i| word[0...i]+word[i+1,1]+word[i,1]+word[i+2..-1] }
  alteration = []
  n.times {|i| LETTERS.each_byte {|l| alteration << word[0...i]+l.chr+word[i+1..-1] } }
  insertion = []
  (n+1).times {|i| LETTERS.each_byte {|l| insertion << word[0...i]+l.chr+word[i..-1] } }
  result = deletion + transposition + alteration + insertion
  result.empty? ? nil : result
end

def known_edits2 word
  result = []
  edits1(word).each {|e1| edits1(e1).each {|e2| result << e2 if NWORDS.has_key?(e2) }}
  result.empty? ? nil : result
end

def known words
  result = words.find_all {|w| NWORDS.has_key?(w) }
  result.empty? ? nil : result
end

def correct word
  (known([word]) or known(edits1(word)) or known_edits2(word) or
    [word]).max {|a,b| NWORDS[a] <=> NWORDS[b] }
end

After you’ve saved the holmes.txt file, load the code into irb and call the correct function with a string as follows:

badkins:~/sync/code/ruby$ irb
irb(main):001:0> require 'spelling_corrector.rb'
=> true
irb(main):002:0> correct "whree"
=> "where"

Written by Brian Adkins

September 4, 2008 at 3:58 pm

Posted in people, programming

Tagged with ,

Ubuntu Linux 8.04 – Wake on LAN

with 3 comments

Now that I’ve switched to a Macbook Pro with OSX Leopard as my primary desktop, I’ve located my Ubuntu machine in another part of the house to be accessible to my children. Not wanting to walk to the room where it’s located just to flip the power switch, I researched how to get “wake on LAN” working, so I could power it up remotely.

1. Enable the appropriate setting in your BIOS. Mine had something to do with wake on PCI device.

2. Install ethtool if you don’t already have it.

sudo apt-get install ethtool
cd /etc/init.d
sudo vim wakeonlanconfig

Add the following lines to that file:

#!/bin/bash
ethtool -s eth0 wol g

Install the script:

sudo update-rc.d -f wakeonlanconfig defaults

Run the script:

sudo /etc/init.d/wakeonlanconfig

3. Keep the network interface alive after shut down.

sudo vim /etc/init.d/halt

Change the following line:

halt -d -f -i $poweroff $hddown

to the following line (i.e. remove the -i)

halt -d -f $poweroff $hddown

4. Get the MAC address

ifconfig | grep HW

5. Send the magic packet via the following Ruby program:

require 'socket'
mac_addr = "x21x53x39xB3x90x42"
s = UDPSocket.new
s.setsockopt(Socket::SOL_SOCKET, Socket::SO_BROADCAST, 1)
s.send("xff"*6 + mac_addr*16, Socket::SO_BROADCAST, '10.0.0.255', 7)

Written by Brian Adkins

September 3, 2008 at 12:23 am