Lojic Technologies

Archive for August 2009

Daniel Weinreb re: Lisp use at ITA

with one comment

Some random notes:

  • 650 KLOC plus 150 KLOC of open source code
  • 100 people on the team, 70 programmers
  • SBCL for the QPX product
  • Clozure CL for the reservations product
  • Availability requirement: four 9’s => less than 53 minutes downtime per year
  • Latency agreement

    • 90% of requests w/in 300 ms
    • 5% of requests w/in 600 ms
    • 5% of requests w/in 1,200 ms
  • Java presentation layer, Common Lisp stateless business layer, Oracle data layer
  • Daniel is very positive about Clojure
  • Some links from the talk:

Written by Brian Adkins

August 29, 2009 at 1:31 pm

Posted in business, programming, technology, video

Tagged with

Haskell In The Finals

with 3 comments

As I explain in 2009 Programming Language Plan, I’ve been in the process of evaluating programming languages to determine their suitability for use in my work. I’ve been proceeding on two fronts – statically typed functional programming languages and the venerated Lisp family.

Haskell The Hope Of The Statically Typed Family

After many hours of research and a brief dive into Standard ML, I’ve selected Haskell as the best candidate for me to evaluate statically typed functional programming languages. At this point, I’m subjectively biased against statically typed functional programming languages because of the enjoyment and productivity I’ve found in Ruby & Lisp, but my only experience with statically typed languages (C, C++, Java) has not been representative of good statically typed languages, so I’m reluctant to form a strong opinion of static typing before I’ve become proficient in a good statically typed language.

There are, of course, a number of respected statically typed functional programming languages, but I think Haskell provides me with the best opportunity to make a personal assessment regarding the benefits of static typing for my particular situation, and I think someone would be hard pressed to convince me that it’s a poor choice objectively.

There Can Be Only One

After working halfway through Programming in Standard ML by Robert Harper, I realized that I enjoy the language and it seems simpler & cleaner than Haskell, but I also realized that I only have time to become truly proficient in one statically typed functional programming language in the near future. I feel that a reasonable level of proficiency is required to evaluate a language well. I have seen many examples of someone, with only a little knowledge of a programming language, making an unfounded criticism of a programming language, or a particular feature, only to be corrected with an accurate, elegant and convincing counter argument by someone who is experienced with the language.

A quick survey of a language won’t be enough for me to make a decision on some key points such as static vs. dynamic, nonstrict vs. strict, pure vs. impure, etc. as well as important peripheral issues such as existing libraries, tools, etc. – it’s going to require understanding some of the subtleties of the language and writing enough code to get a feel for the language, so I felt I needed to limit my choice to one statically typed FPL.

Static vs. Dynamic

Clearly both static and dynamic typing work well for large numbers of people. One of my goals is simply to answer the static vs. dynamic question for myself given my preferences and the type of software I want to develop. I’d previously decided to learn both Standard ML and Haskell, so my reasons below for choosing Haskell are primarily with respect to comparing the two languages:

Haskell Is Pure And Lazy

I’m already familiar with impure, or multi-paradigm, programming languages that offer some functional features but allow imperative programming, so being forced to program in a purely functional manner and abandon my comfort zone of imperative patterns is an advantage for me. I have no experience with lazy languages, so Haskell offers an opportunity to gain more experience with laziness :).

In some respects, Haskell is more different than Lisp compared to other statically typed functional programming languages, so it’s a good point of comparison. It may end up being the ultimate death match 🙂

  • Static vs. Dynamic
  • Nonstrict vs. Strict
  • Rich/Complex Syntax vs. Simpler Syntax
  • Pure vs. Impure/Multi-paradigm

Active Community

Haskell has a very active community. Although I’m skeptical about whether a statically typed functional programming language will be suitable for the type of work I want to do with it, it makes sense to choose one that has a reasonable shot, and I don’t personally feel that Standard ML does – it was mainly to be an introduction to functional programming and a stepping stone to another FPL.

Part of the reason I don’t feel that Standard ML has a reasonable shot is that it feels dated and somewhat abandoned. Functional programming languages are niche languages to begin with, but it seems that Haskell and OCaml both have fairly strong communities.

Cool Features

Although I think Haskell’s custom of continuing to add cutting edge research features into the language may have some disadvantages if not done well, i.e. making the language messier and complicated, for my primary purpose of evaluating the benefits of statically typed languages, I think having more advanced features is an advantage over Standard ML. If a language with such an active research community as Haskell fails to convince me of the benefits of static typing, then it may just not be for me.

Monads and type classes seem interesting, and Haskell provides an opportunity to learn them. Monads seem useful outside of Haskell, so the time spent learning about them can be leveraged. I already like list comprehensions, so it’s nice to have them available again.

Learning some of the advanced features of Haskell will be beneficial to me regardless of whether I continue programming in Haskell or decide to go with the Lisp family.

Textual Resources

Standard ML actually has a surprising number of good texts available, so I don’t think Haskell offers a big advantage here, but in my particular case, I already own two Haskell texts – Programming in Haskell by Graham Hutton and The Craft of Functional Programming by Simon Thompson. Also, Chris Okasaki’s Purely Functional Data Structures provides Haskell examples as does Richard Bird’s Introduction to Functional Programming using Haskell (2nd ed.). Lastly, I think Real World Haskell may be very helpful.

Haskell Crash Course

My goal now on the statically typed front is to become as proficient in Haskell as I can in a very short period of time. There seem to be plenty of resources available, but if you’re aware of any particularly helpful resources or tips, feel free to add a comment.

Written by Brian Adkins

August 18, 2009 at 11:36 am

Posted in programming

Tagged with

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 , ,