Friday, December 19, 2008

The Y-Combinator

I finally found the time to grok the Y-combinator. There are already multiple examples available but I am to thick to get them and, therefore, wanted to derive it myself.

The Y-combinator is a wonderful piece of software that allows you to create self-referential programs without built-in support. That is, it allows me to create anonymous recursive functions. This is best shown by an example.

; The factorial function
(define fact
  (lambda (n)
    (if (< n 2) 1 (* n (fact (- n 1))))))

In the recursive function above the fact refers to itself by name. This relies on the name being available before it is actually defined. To avoid this we can send the function as a parameter to itself. Like so:

; Define a local variable g as the function.
; The function takes a function (itself) as an extra parameter.
; The function is called with itself as a parameter:  (g g 5)).
; This doesn't compile since the function h (that is g) requires 
; an additional parameter.
(let ((g (lambda (h n)
           (if (< n 2) 1 (* n (h  (- n 1)))))))
  (g g 5))

; The working version needs h to also call itself (h h (- n 1)).
(let ((g (lambda (h n)
           (if (< n 2) 1 (* n (h h (- n 1)))))))
  (g g 5))

We can now abstract over the h parameter with a technique reminiscent of currying.

; A new lambda is abstracted over h.
; Note that the function calls to g and h need to change ((g g) 5)) 
; and ((h h) (- n 1)) to ensure that they agree with the definitions.
(let ((g (lambda (h)
           (lambda (n)
             (if (< n 2) 1 (* n ((h h) (- n 1))))))))
  ((g g) 5))

We can now abstract over n and (h h) creating a new lambda with the parameters q and m.

; Function f is declared locally with the parameters q and m 
; and then called directly (f (h h) n).
(let ((g (lambda (h)
           (lambda (n)
             (let ((f (lambda (q m)
                        (if (< m 2) 1 (* m (q (- m 1)))))))               
               (f (h h) n)))))
      ((g g) 5)))

Notice that f is independent of it’s context and can be moved to the top level.

; f moved to the top level.
(let ((f (lambda (q m)
           (if (< m 2) 1 (* m (q (- m 1)))))))
  (let ((g (lambda (h)
             (lambda (n)
               (f (h h) n)))))
    ((g g) 5)))

I can now abstract over q to isolate the definition of fact.

; Notice that the inner function of f is the original fact function.
(let ((f (lambda (q) 
           (lambda (m)
             (if (< m 2) 1 (* m (q (- m 1))))))))
  (let ((g (lambda (h)
             (lambda (n)
               ((f (h h)) n)))))
    ((g g) 5)))


Now I abstract over the local variable f and declare a new variable Y. The call to ((g g) 5) is replaced (g g) and moved to the Y function instead.

; A new variable Y is created for the abstraction over f.
; The function call is moved to the application of Y.
(let ((Y (lambda (f)
           (let ((g (lambda (h)
                      (lambda (n)
                        ((f (h h)) n)))))
             (g g)))))
  ((Y (lambda (q) 
        (lambda (m)
          (if (< m 2) 1 (* m (q (- m 1))))))) 5))

Finally we replace the local variable Y with a the function Y, the Y-combinator.

(define Y
  (lambda (f)
    (let ((g (lambda (h)
               (lambda (n)
                 ((f (h h)) n)))))
      (g g))))

Excellent!

Monday, December 15, 2008

Thoughts on Simplicity

A scientific theory should be as simple as possible, but no simpler. —Albert Einstein

Do the simplest thing that could possibly work. Keep it simple by refactoring. —Kent Beck

If you think something is clever and sophisticated, beware: it is probably self-indulgence. —Donald Norman

Simplicity does not precede complexity, but follows it. —Alan Perlis

To make something generic is to make the simple things complex. —Adam Keys

Simple things should be simple. Complex things should be possible. —Alan Kay

Don’t EVER make the mistake that you can design something better than what you get from ruthless massively parallel trial-and-error with a feedback cycle. That’s giving your intelligence much too much credit. —Linus Torvalds

Consistency is Simplicity: A consistent approach to style and solutions can make code easier to maintain. —Ken Pugh

If you think you’re designing something for idiots, the odds are that you’re not designing something good, even for idiots. —Paul Graham

It is better to be wrong than to be vague. —Fred Brooks

Simplicity is the ultimate sophistication. —Leonardo da Vinci

If you want to make something 10 times cheaper, remove 90 percent of the material—Amy Smith

Wednesday, December 10, 2008

What is "declarative" anyway?

Declarative programming often seems – to me – as the holy grail of programming. But what does it really mean?

According to Dictionary.com

Declarative – serving to declare, make known, or explain: a declarative statement.

or

Declarative – a mood (grammatically unmarked) that represents the act or state as an objective fact [syn: indicative mood]

or

Declarative – making declaration, proclamation, or publication; explanatory; assertive; declaratory.

So, the word means explanatory or stated as facts.

In the context of programming declarative is usually contrasted with imperative and procedural, where imperative programming means programming by changing state and procedural programming means that a detailed algorithm is used.

Wikipedia states

Declarative programming is a programming paradigm that expresses the logic of a computation without describing its control flow.

or

Declarative programming attempts to minimize or eliminate side effects by describing what the program should accomplish, rather than describing how to go about accomplishing it.

So, in this context, declarative means without describing the control flow and without side effects.

Does this mean that I am programming declaratively when I am writing immutable object oriented code (without side effects) with fluent interfaces (explanatory)?

Or does it mean I am programming declaratively when I set up a large table, or even a database, of stated facts that I use to drive my application?

Or, who cares?

Wednesday, November 19, 2008

Report from Öredev day 1

Keynote with Ted Neward

The renaissance in development, according to Neward, is the renaissance of programming languages. The reason the renaissance is here is that the practitioners and the academics are, finally, working towards the same goal. Historically there has been downright hostility between them. This is because the academics and the practitioners are working towards different goals. The academics want to prove a concept while the practitioners wants to get work done. When the practitioners finally get what the academics have done the academics have left the project years ago.

Three forces work together to create the renaissance.

  • Virtualization – virtual machines allow programmers to ignore the low-level details and to focus on the real problem. The same is true for language designers.
  • Tools – IDEs, analyzers, debuggers, profilers, etc. are used by programmers and language designers use parser generators, AST generators, grammar debuggers, etc.
  • Linguistics – Functional languages introduce new ideas, at least to the common programmer. Languages become more diverse to conceptualize different constructs, not everything is an object anymore. We have functions, aspects, meta-object protocols.

Technical challenges of the next generation are for example

  • Concurrency
  • Security
  • Distribution and services
  • User interface expression

There are more languages than ever and it is easier than ever to create your own language.

5(2) aspects you’ve never heard about by Alef Arendsen

Started with a quick introduction to AOP for logging. AOP is about the three Ws: Where?, When?, and What?.

Before, a business service, log a message.

  • A pointcut is an expression for finding a number of joinpoints.
  • A joinpoint is a place where you can inject an aspect.
  • An advice is the code that is injected in the joinpoint.
  • An aspect is the combination of a pointcut and an advice.
  • Pointcuts should always be singular.

Aspect 1: Mixing Hibernate and JDBC usage

Hibernate uses transactional write-behind which will put the database and the cache out of sync. If I try to access the code via JDBC it will not get the correct data.

This can be solved with an aspect that flushes the cache to the database before a JDBC call is performed.

Before any JDBC operations flush the Hibernate session.

Aspect 2: Specific criteria should be applied based on orthogonal data.

I only want to get data from a specific location when performing a query.

Before a top level business service propagate location and after a top level business service delete location.

The advantage of this approach is again that it applies to both the Hibernate code and the JDBC code. It requires adding views to the database, but that would probably be a good idea anyway.

Dynamic Languages on .Net with J. Hartley

In five years we will look at compilation as the weakest form of unit testing.

Jim started out by saying that Ruby is not just simpler, but better :) Generics in C# is nice but it comes at a tremendous cost of obscuring the actual code.

IronPython supports Decorators to allow adding functionality through attributes. It will be supported in Visual Studio in 2009. An IronPython ScriptingEngine can be embedded into an application with a just a few lines of code.

What makes a programming language productive by Walter Bright

The D language is created by a diverse community of experts. It is a multi-paradigm language that supports c-style, OO, scripting, template metaprogramming, assembler, and functional programming. It is meant to replace C++.

The right way is the easy way. Work harder to do it the wrong way.

D supports simple template syntax. Header files are optional, type inference, foreach loops, reducing the source code with 30 percent compared to C++.

Diversity Challenges in Agile Teams by Aslam Khan

Writing software is cerebral but EQ overrides all IQ.

Leadership is taught to all, but followship is never taught.

Tuesday, November 18, 2008

Time for Smalltalk

Öredev is coming up and I’ll be giving a talk called Time for Smalltalk. The title of the talk is supposed to imply that the time for Smalltalk is finally here. I claim this since the publicity of dynamic languages like Ruby and Python has paved the way for Smalltalk. Only a few hardcore developers are still resisting the power of modern IDEs, so the barrier of Smalltalk adaption is considerably lower than it was a in the beginning of the eighties when Smalltalk first arrived.

The reason developers in dynamic languages should switch to Smalltalk is that the Smalltalk environment is alive. You are working inside a running system and instead of constantly trying to create new worlds, the Smalltalk way is to modify the world to fit your needs. This metaphor fits a lot better with the way good systems are usually developed. Start small and let the system grow incrementally.

The liveness property of Smalltalk also gives you the ability to refactor the code in a safe way. At runtime I can just ask the system in what classes a certain method is implemented and then I can let the system rename it as I wish.

Three of my new colleagues from factor10 Jimmy Nilsson, Aslam Khan and Lennart Ohlsson will also be speaking at the conference.

Saturday, November 08, 2008

What should be in an application 2008?

Listed here are features that I want in any application. The features are separate from the domain specific service that the application is designed to provide.

Search

The feature that I want more than anything is search. Everything should be indexed: menus, toolbars, dialogs, windows, selection boxes, shortcuts, help files, configuration files, application components, objects, scripts, the works! It should be possible to make generic full-text searches for anything matching my criteria, but it should also be possible to make specific searches by category or tag. It should also be possible to save the searches for later.

Search should also be available in all places possible. It does not have to be a search field, it can be a selection box or a textfield. It should preferably be integrated into the components to help me out whenever it is possible.

External tools should also be able to search. Tools like Google Desktop and Spotlight, and Launchers like Quicksilver and Launchy must be kept in mind when designing for search.

Tags

Anything searchable should also be taggable. It is possible that my terminology is different from the one that the application developers have. I may also want to group things together that does not appear related to anyone else. It should of course be possible to assign multiple tags to the same thing.

Scripting

Everything should be scriptable. Whatever is possible to do in the GUI should be possible to script. This lets me create my own automated tasks that I can re-use later or share with other users. It should be possible to run and create the scripts both inside and outside the application. The scripts should not be limited to use application functionality, they should be allowed to call operating system commands or other applications. The scripts will thus also serve as plugins for the application.

As with search it is important to have external tools like Quicksilver and Launchy in mind, but when it comes to scripting the scope is wider and you need to think about command line interfaces and other external applications too. Provide many entries to your application.

Shortcuts

It should be possible to assign shortcuts to any action available in the system. This includes saved searches, tags and scripts. Shortcuts should allow Emacs-style multi-key-shortcuts, such as Ctrl-C, Esc-V, M.

Persistence

It should be possible to save the state of the application at any time!. It does not matter to me that a form or that whatever I’m doing is an invalid state. Perhaps I like invalid.

It should be possible to save it anyway. It should also be possible to take snapshots at any time and to reset the application to a previous snapshot at any time. Preferably it should also be possible to compare different snapshots with each other in a useful way.

All in all I want persistence to work like a versioning system giving me the possibility to move through history at my leisure.

Export – Import

Exporting is just a different flavor of persistence. It should be possible to export (persist) the application data into some format that is useful to another similar application. This format should naturally also be importable.

Since exporting is just a flavor of persistence I naturally want versioning of my exports to. Perhaps it’s a good idea to just use git as a persistence engine?

Validation

I mentioned validation above on persistence. Validation is a valuable tool in an application but more often than not it gets in the way. The validation should not force me to enter data in a specified order unless it is absolutely necessary. It is good and even helpful to provide hints and markers along the way. But let me work the way I want to work and stay out of my way.

The important thing with validation is that it should indicate an error as soon as it appears but it should not force me to do anything about it until whenever I try to do something fatal such as, to quote Simon Peyton Jones, launch missiles.

Wiki

I find it really helpful to be able to link things together in Wiki style. The need for this is very dependent on the type of application but I find it very useful to be able to relate one item to another when I commonly need them together.

Conclusion

This list is by no means meant to cover everything, but I think it is a good starting point for anyone who want to make a useful application that can evolve with time.

Friday, November 07, 2008

How (not) to buy books

If you, like I, read a lot of books from different areas you probably buy a lot of books that are of questionable quality. I used to do this too. Now, I use libraries instead. Some of the advice here will be specific to Sweden, since this is where I get my books, but you can probably find similar places where you live.

  • Find the book you want. If it is an English book Amazon is the place to go. If it is Swedish use Bokus or AdLibris. The value of these websites is that they provide a lot of information about the book, such as summaries, reviews and references to other related books. The related books are interesting since they provide you with options based on what others bought, the author and other people’s recommendations. All to help you find the best book for your topic.
  • Use the ISBN, title, author, etc and search in your local on-line library catalog. In my case it is the library in Staffanstorp. If you find it all is well, just reserve it and pick it up the next day.
  • If you don’t find it in your local library goto your country’s common library catalog. In my case it is called bibliotek.se. If you don’t find it here you will have to buy it, but I have found more than 90 percent of my books here lately.
  • If you find the book, go back to your local library catalog and make an Inter library loan (fjärrlån in Swedish). Make sure you say that you found the book in the common catalog and that you want it delivered to your local library unit. The book is usually delivered in about a week at the cost of 5 SEK.
  • If you like the book and think you will read it again, buy it. If you don’t, just return it and feel content with that along with saving a small tree, you didn’t encourage a crappy author to write another book :)

Monday, November 03, 2008

Notes on The Long Tale

The Long Tail by Chris Anderson is a book about what happens in a market where the cost of production and distribution becomes negligible. The long tail refers to a statistical distribution where the distribution curve never drops to zero.

Short-Tailed Markets

In a market where the costs of inventory are high, such as in a standard book store, the store can only hold a limited amount of products in stock. The store will naturally want to keep the best selling books in stock to maximize their profit. This is often referred to as the 80/20 rule. 80 percent of the sales come from 20 percent of the products.

The 80/20 rule and the inventory limitations changes the buying patterns of the customers since they will buy what is available instead of going to great lengths to get something that is hard to get or even completely unknown to them, thus re-enforcing the rule.

Long-Tailed Markets

The reduced costs of product inventory and distribution due to the Internet and Just-In-Time techniques is changing the rules. Amazon is reporting that sales from books that would not normally be kept in stock in a normal book store provides one third of the total market share. And the share is growing rapidly.

There are three things that enable the long-tailed markets: production tools that enable cheaper small scale production, cheap and simple distribution tools, and a new connection between producers and consumers.

Production

Cheap, simple production tools, such as Garage Band, iMovie, blogging tools, etc. enable enthusiasts to create acceptable music, movies, podcasts, articles, etc. at virtually no cost. And they do. The production in the tail is not driven by money. In the tail the drive comes from the need to express oneself and to have fun. People who do things for themselves instead of for money often produce better products.

Distribution

The digital media can be distributed via any of thousands of channels, YouTube, Vimeo, iTunes Store, Pirate Bay and DC++. Music and video are easily downloaded to iPods and other portable players. Books are available as audio books or available as PDFs to read on-screen or to print at home. Bloggers are writing millions of articles everyday, available to anyone, for free!

The Connection between Producers and Consumers

Google is The Start Page for the Internet and it enables the connection between producers and consumers. It also enables the consumer-to-consumer connection. The trust in advertising is steadily decreasing while the trust in individuals continue to rise. Google enables me to find like-minded people that are happy to give recommendations to anyone who is interested in what they do or are interested in. We are the critics in the Internet age.

There is so much information available that the need to filter is higher than ever. Google provides this filter with the assistance of numerous blogs and other social tools. The filter has moved from pre-production to post-production making it possible for us to choose what fits our needs instead of the needs of publishers that are ultimately driven by money and professional critics with different taste than ours.

But, the professional critics have not disappeared, they have just become less important. And in the abundance of information that the Internet provides it can still be a good choice to rely on external agents instead of trying to make all the choices ourselves (see The Paradox of Choice).

Saturday, October 25, 2008

TDD and LINQ to SQL

Microsoft has made the unfortunate mistake of not making System.Data.Linq.Table<T> implement an interface. If they had only done this it would have been easy to mock out the Persistence Layer when using LINQ to SQL.

Since it is a class and a sealed one at that, this is not an available path for TDD. What to do? If we can’t implement it we can adapt it. What is required for this to work is two interfaces: IUnitOfWork and ITable<T>, two classes LinqToSqlUnitOfWork and LinqToSqTable<T> and for testing purposes two additional classes InMemoryUnitOfWork and InMemoryTable<T>.

ITable<T> looks like this. I usually only include the methods that I need and add more by need.


   public interface ITable<T> : IQueryable<T> where T : class
    {
        void Attach(object entity);
        IQueryable<TElement> CreateQuery<TElement>(Expression expression);
        IQueryable CreateQuery(Expression expression);
        void DeleteAllOnSubmit(IEnumerable entities);
        void DeleteOnSubmit(T entity);
        object Execute(Expression expression);
        TResult Execute<TResult>(Expression expression);
        void InsertAllOnSubmit(IEnumerable entities);
        void InsertOnSubmit(T entity);
    }

IUnitOfWork looks like this with one accessor method for every aggregate in my domain model. I have only included SubmitChanges in the interface but it is entirely possible to include all the methods of DataContext here if you have the need for it.


   public interface IUnitOfWork
   {
       ITable<Player> Players { get; }
       ITable<Round> Rounds { get; }
       void SubmitChanges();
   }

LinqToSqlUnitOfWork looks like this. Every method wraps the sealed Table<T> in a LinqToSqlTable<T>.


public class LinqToSqlUnitOfWork : IUnitOfWork
{
     private readonly LinqToSqlDataContext dataContext;

     public LinqToSqlUnitOfWork(LinqToSqlDataContext dataContext)
     {
         this.dataContext = dataContext;
     }

     public ITable<Player> Players
     {
         get { return new LinqToSqlTable<Player>(dataContext.GetTable<Player>()); }
     }

     public ITable<Round> Rounds
     {
         get { return new LinqToSqlTable<Round>(dataContext.GetTable<Round>()); }
     }

     public void SubmitChanges()
     {
         dataContext.SubmitChanges();
     }

 }

The next class need is LinqToSqlTable<T>. As shown above the constructor takes a Table<T> as a parameter. All actual work is delegated to the Table<T>.


public class LinqToSqlTable<T> : ITable<T> where T : class
{
    private readonly Table<T> table;

    public LinqToSqlTable(Table<T> table)
    {
        this.table = table;
    }


    public void Attach(T entity)
    {
        table.Attach(entity);
    }

    public IQueryable<TElement> CreateQuery<TElement>(Expression expression)
    {
        return ((IQueryProvider) table).CreateQuery<TElement>(expression);
    }

    public IQueryable CreateQuery(Expression expression)
    {
        return ((IQueryProvider) table).CreateQuery(expression);
    }

    public void DeleteOnSubmit(T entity)
    {
        table.DeleteOnSubmit(entity);
    }
    ...

Finally we have the InMemory classes. InMemoryUnitOfWork works similarly to SqlToLinqUnitOfWork creating InMemoryTables that implement the ITable<T> Interface. The SubmitChanges method is left as an interesting exercise for the reader :)


public class InMemoryUnitOfWork : IUnitOfWork
{
    private readonly ITable<Player> players;
    private readonly ITable<Round> rounds;

    public InMemoryUnitOfWork()
    {
        players = new InMemoryTable<Player>();
        rounds = new InMemoryTable<Round>();
    }

    public ITable<Player> Players
    {
        get { return players; }
    }

    public ITable<Round> Rounds
    {
        get { return rounds; }
    }

    public void SubmitChanges()
    {
        //TODO
    }
}

In its simplest form the InMemoryTable<T> just uses a List<T> as storage, delegating all possible functionality to the list. A lot of methods are left out for brevity.


    public class InMemoryTable<T> : ITable<T> where T : class 
    {
        private readonly IList<T> list;
 
        public InMemoryTable() : this(new List<T>())
        {
        }

        public InMemoryTable(IList<T> aList)
        {
            list = aList;
        }

        public IEnumerator<T> GetEnumerator()
        {
            return list.GetEnumerator();
        }

        public Expression Expression
        {
            get { return list.AsQueryable().Expression; }
        }
   ...


This simple wrapper gives me the ability to create repositories for my classes that work for both LingToSql and with in memory collections. Here is an example:


public class RoundRepository
 {
     private readonly IUnitOfWork unitOfWork;

     public RoundRepository(IUnitOfWork unitOfWork)
     {
         this.unitOfWork = unitOfWork;
     }

     public IQueryable<Round> Rounds
     {
         get { return unitOfWork.Rounds; }
     }

     public void AddRound(Round round)
     {
         unitOfWork.Rounds.InsertOnSubmit(round);
     }

     public void ClearRounds()
     {
         unitOfWork.Rounds.DeleteAllOnSubmit(unitOfWork.Rounds);
     }

     public IEnumerable<Round> ByYear(int year)
     {
         var rounds = from round in Rounds
                      where round.PlayDate.Year == year
                      select round;
         return rounds;
     }
 }


This gives me the ability to test my domain classes at the relatively small cost of six new classes and interfaces. It also allows me to use the same test code for both unit testing and integration testing. Not bad for a days work :)

Thursday, October 23, 2008

Code Comments

I am a firm believer of Programming by Intent and TDD as a means to communicate effectively with my fellow programmers (current and future). I find that sometimes this is not enough and I have therefore started using the following code comments to improve the communication.

TODO: why, why not

The TODO signals that here is incomplete functionality here. The comment should be followed by a reason why this should be done and why it isn't.

WTF: who doesn't get it, what

A WTF signals that there is something I don't understand. It is a signal to whomever wrote the code to clarify its intent by refactoring or with a BECAUSE comment. Hopefully this code is written by someone else. :) The WTF should be followed by my signature and what I don't get.

BECAUSE: who, why

A BECAUSE signals that I am unable to express my intent in code and that I need help clarifying it. The comment contains my signature and what I am trying to express. Hopefully I or someone else will be able to clarify my intent later.

REF: link

A REF signals that this code is described elsewhere. The code may be an algorithm that is described somewhere on the web or in a book. The ref is followed by a URL or some other pointer that allows whomever is interested to find the information easily. I usually add the comment patterns as to-do regexps in my editor making it easy to navigate to them. I also let the continuous integration server parse for them to give me a list of things that needs attention.

The comments also provide the additional value of showing the quality of the code.

Wednesday, October 01, 2008

Notes on 'Secrets of Successful Speakers'

Notes on Secrets of Successful Speakers
by Lilly Walters.

Effective Communication

To be able to communicate effectively with your audience you need to have a clear message.
People will typically forget 90% of what you have said after one week. What are those 10%?

Decide what the purpose of your speach is. Write it down in one sentence. It should be:

  • Precise
  • Measurable
  • Reasonable
  • Relevant to your audience
  • Obtainable within your time limit

Don’t talk about something you are not passionate about.

Know and care about your audience:

  • Are they positive or negative?
  • What do they want?
  • Are they analytical, relational, dominating, expressive?

Developing the Presentation

  • Pick a simple easily remembered theme; one central idea.
  • Only use three to four main points. Every point should be relveant, independent and advantageous.
  • Create your own material.
  • Find a suitable structure: Story, Problem-Solution, Analogy, Acronyms.
  • What, Where, When, How, Why and Who?
  • Edit without mercy. No one ever complains that a speach is too short.
  • Give it a good title.

The Presentation

  • Attention: Be silent, look at the audience, joke, surprise.
  • Convince: Ethos, make them like you. Pathos, make them laugh or cry. Logos, substantiate your position.
  • Remember: Repeat
  • Practice

Wednesday, September 24, 2008

Notes on 'How to Solve It'

A quick overview of George Pólyas How to Solve It. Problem solving can be divided into four separate steps: Understand the problem. Make a plan. Carry out the plan. Reflect on the solution.

Understand the problem

What is the unknown? What are the data? What is the condition? Do you understand the problem? Restate it in your own words. Can the condition be satisfied given the data? Introduce suitable notation. Draw a figure. Write it down.

Make a plan

Have you seen it before? Have you seen a related problem? Find a problem with a similar unknown. Divide the problem into simpler problems. Look at a more specialized problem or a more general.

Carry out the plan

As you carry out the plan: check each step! Can you see that it is correct? Can you prove that it is correct?

Reflect on the solution

When the solution is found: check the result! Check the solution. Can you derive the result differently? Can you use the result for another problem?

Saturday, August 16, 2008

Notes On Design

A summary of The Non-Designers Design Book by Robin Williams. The four basic principles of design are: Proximity, Alignment, Repetition and Contrast – PARC.


Proximity

The purpose of proximity is to organize. Elements that are intellectually connected should be visually connected. Unrelated elements should not be in close proximity. The closeness or lack of closeness indicates the relationship. Equal amounts of whitespace between elements indicate that they are part of a subset.

Alignment

The purpose of alignment is to unify and organize. Every element on a page should have visual alignment with another item on the page. Nothing should be placed on the page arbitrarily. Find a strong line, such as a graphic, and use it.

Repetition

The purpose of repetition is to unify and to add visual interest. Repetition is being consistent. Examples are headlines, list items, page numbering, etc. Repetition can be accomplished with a mere suggestion of a repeated element. It is not necessary to use the whole thing.

Contrast

The purpose of contrast is to create interest. If two items are not exactly the same then make them very different. Contrasted elements can often be used with repetition in the page.

Using Color

Get to know the color wheel. Good color combinations are:

  • Complementary colors – two color on opposite sides of the color wheel.
  • Triads – three colors equidistant from each other.
  • Split complement triads – two colors on each side of the complement instead of the complement.
  • Analogous colors – three colors next to each other on the wheel.

Use shades (black added) and tints (white added) to vary the combinations above. Be aware that cool colors recede into the background and warm colors come to the front.

Using Fonts

Fonts can be categorized into roughly six categories:

  • Oldstyle with slated serifs.
  • Modern with horizontal serifs.
  • Slab Serif with fat horizontal serifs.
  • Sans Serif without serifs.
  • Script looks like handwriting.
  • Decorative are crazy fonts like Zapf Dingbats

Never use two different fonts from the same category on the same page.

Tuesday, July 29, 2008

Notes on Clay Shirkys 'Here Comes Everybody!'

Groups It has never been as easy to form groups as it is now with the availability of social tools. Journalism What is a journalist? It used to be defined by where you work but now it's not so clear. What will happen to the journalistic privileges when everyone is a journalist? Interaction Even though mass interaction is made possible by new tools. The time it takes to communicate sets an upper limit on how much interaction is possible. People who receive a ot of comments on their blogs are unable to answer all of them thus inhibiting interaction. The Tragedy of the Commons In a community where everyone is expected to do things for the common good of everyone. It is better for the individual not to pull his share and instead invest the time for his own good. Rules are needed to make sure everyone behaves.

Friday, May 16, 2008

Patterns of Software

Patterns of Software (PDF) is an essay collection written by Dick Gabriel. The collection is, like software patterns, based on the work of Christopher Alexander. It is more a thoughtful analysis of Alexanders work, with comments related to software, than a practical implementation of his ideas as in the GoF-book. Please note that this is not my analysis of Alexander, whom I haven't read yet, but simply notes of Gabriels analysis of Alexander. Gabriel identifies three important concepts in software systems:

Compression - the ability to describe something succinctly by using the surrounding context. Examples are subclassing and closures. The benefit of compression is the elegance of avoiding unnecessary words that distract from the main issue. The downside is that the reader must know the surrounding context.

Habitability - the characteristic of source code that enables programmers to understand and change the it comfortably and confidently. It is related to Alexanders organic order which is defined as... "the kind of order that is achieved when there is a perfect balance between the needs of the whole and the need of the parts". If the programmers lose the sense of responsibility for the environment they live in hoe can they feel any sense of purpose there. Habitability enables piecemeal growth, small incremental modifications, a reality in software. An interesting and controversial idea on habitability is: "Habitability is not clarity. The danger of clarity is it's uncompromised beauty; it's really tough to improve uncompromised beauty. Clarity is dangerous."

Abstraction - is the thought process wherein ideas are distanced from objects. In programming the implementor of an abstraction can ignore the exact uses and the user of the abstraction can forget the details of the abstraction. Abstraction especially when it is take too far may limit the habitability of the software. It is important to keep the abstractions clear and intuitive. Abstracting is difficult and should be handled with care. Abstractions are part of the context that makes compression possible but at the cost of knowing the abstractions. Sometimes, when no good abstraction can be found, it is better to just write the common code.

Patterns

Qwan- At the heart of Alexanders pattern language was his quest for the Quality without a name, Qwan. It is interesting to note that this central idea is not mentioned at all in the GoF-book. It is as if they found it to vague to be of any interest.

Gabriel does not claim to know what qwan is but mentions things about software that possesses it. Here are a few:

  • Its abstractions and modules are not too big. They make sense for themselves; they are whole.
  • If I look at any small part I can see what is going on, I don't need to look at other parts to understand it.
  • Everything about it seems familiar.
  • I can image changing it without fear of breaking it.
  • It is like a fractal in which every level of detail is locally coherent.
Patterns and Carpets - Alexander patterns contains people and their activities, this is because the buildings are meant to be lived in. This is also true for software; it is meant to be maintained. Another aspect of Alexander patterns was that their geometrical nature was fundamental.

Alexander also studied Turkish carpets since he found a beauty in them that he could not explain. He even published a book about them. In it he says:

  • The beauty of a structure comes from the fine detail at an almost microscopic level.
  • The beauty of the color of the carpet was due to the fact that the master dyer served a 15-year apprenticeship after which he was required to produce a color no one had seen before.
  • Fanatical precision is not required. It is only important to know what is important and what is not and to pay attention to what is important.
  • To get wholeness, you must leave things that don't matter rough and unimportant and give things that really matter deep attention.
  • Every successful center is made of a center surrounded by a boundary which is itself made by centers.
The solution to a large problem is a nested set of patterns.

Failure - Another interesting thing not mentioned in the software pattern literature is the fact that Alexander failed (his own words) when he tried to implement his ideas. The building that were built did not have the quality that he had expected.

Friday, April 25, 2008

Annoying Mail Signatures

I’m fed up with annoying mail signatures. Here is my interpretation of a particularly annoying one.

This email (including any attachment) is confidential and may contain privileged information. If you are not the intended recipient or receive it in error,

I’m an idiot who occasionally sends confidential mail to the wrong person!

You may not use, distribute, disclose or copy any of the information contained within it and it may be unlawful to do so. If you are not the intended recipient please notify us immediately by returning this e-mail to us and destroy all copies.

Besides being an idiot I also like to tell you what you can and cannot do and I’m not above lying to bully you into correcting my mistakes!

Any views expressed by individuals within this e-mail do not necessarily reflect the views of X or any of its subsidiaries’ or affiliates’.

My company does not trust me.

This email does not constitute a binding offer, acceptance, amendment, waiver or other agreement, unless such intention is clearly stated in the body of the email.

What I say is not trustworthy!

Whilst we have taken reasonable steps to ensure that this e-mail and attachments are free from viruses, recipients are advised to subject this mail to their own virus checking, in keeping with good computing practice.

I have no clue if this email contains viruses or not!

Please, do not include anything apart from contact information in your signature, the exception is a short quote to enlighten my day :)

Wednesday, April 23, 2008

The Paradox of Choice

The Paradox of Choice is a Google tech talk by Barry Schwartz. He is also the author of the book with the same name (which I haven’t read).

The paradox in the title is that: the more choices we have the worse we feel even though many options gives us the opportunity to make a better choice.

We do better but feel worse!

With more choices we have higher expectations and become more frustrated and less happy when we choose. The frustration and unhappiness continues after the choice is made since we are not sure we made the best choice.

The unhappiness comes from self-blame. If we have no options it is the worlds fault, but if we have many it is our fault since we have to be idiots not to make a good choice with 200 options.

Sometimes we even create the frustrating options ourselves. An example is:

  • A todo list with things we have to.
  • A like-todo list with things we would like to do.

The like-todo-list produces more frustration than the todo-list.

Too many options may also paralyze us into not doing anything! Even though making no choice is obviously the worst decision we can make.

Solutions

A solution in life is to become a satisficers instead of a maximizers. To make a good choices instead of best choices. It can also be wise to rely on agents to make the choices for us since they are not personally involved.

Solutions for software developers trying to make less frustrating software are:

  • Create smart defaults so that even if the user does not make a choice it is a good one.
  • Create hierarchical options, limiting the number of choices available at a given time. It is important to make smart hierarchies so that the user don’t have to move back up the hierarchy.

Saturday, March 29, 2008

Concepts, Techniques and Models of Computer Programming

In the book Concepts, Techniques and Models of Computer Programming (CTM), Peter van Roy and Seif Haridi build a programming language based on a very small kernel language. The kernel language is extended as the models needs become more complex but it remains simple and understandable. The language used in the book is called Oz and it is implemented by the Mozart Programming System.

The models are described by three different views:
  • The computation model; the language and how sentences of the language are executed by the abstract machine.
  • The programming model; the techniques and design principles used to write programs.
  • Reasoning techniques; techniques for reasoning about the program to increase confidence that they work as expected.

The Kernel Language

The full kernel language, supporting the models is shown below.

<Statement> ::=

% Statements needed in declarative model
    <Statement1> <Statement2>           % Statement sequence
    | X = <number>|<atom>|<boolean>     % Variable and value

    | X = f(I1:Y1 ... In:Yn)|           % Record and tuple
    | X = Y                             % Variable variable binding
    | local X1 ... Xn in S1 end         % Variable declaration

    | proc {X Y1 ... Yn} S1 end         % Procedure declaration
    | {X Y1 ... Yn}                     % Procedure application (call)
    | if B then S1 else S2 end          % Conditional

    | case X of pat then S1 else S2 end % Pattern matching
    | {NewName X}                       % Creates a new locally unique name


% Statements needed in declarative model with exceptions
    | try S1 catch X then S2 end        % Try a statement and catch the possible exception
    | raise X end                       % Raise an exception


% Statements needed in concurrent declarative model
    | thread S1 end                     % Run statement in new thread.

% Statements needed in stateful model
    | {NewCell I C}                     % Creates a cell C with content I
    | {Exchange C Old New}              % Replaces the value of C with New; Old is returned




The Practical Language

Apart from extending the kernel language, the practical language of Oz is also extended by adding linguistic abstractions and syntactic sugar.

A linguistic abstraction is a new linguistic construct such as a function fun instead of a proc. This construct is both an abstraction and an addition to the language.

fun {Max X Y}
    if X>=Y then X else Y end

end

% Translates into:
proc {Max X Y ?R}
    R = if X>=Y then X else Y end

end

Syntactic sugar on the other hand does not involve a new abstraction. It simply allows us to write the same statements in a more convenient and readable way An example is:

if N==1 then [1]
else
    local L in

    ...
    end
end

% Translates into:
if N==1 then [1]
else L in

    ...
end

Both are added by means of transformations into the kernel language. While building the language all the transformations are shown in detail making it very clear what is going on.

The Declarative Model

The basic model of CTM is called the declarative model. Van Roy and Haridi defines a declarative model as evaluating functions over partial data structures. It covers both functional programming as in Scheme without state and logic programming as in Prolog without search.

The Abstract Machine

The abstract machine of the declarative model consists of: A single-assignment store, a value-store extended with single-assignment or dataflow variables. An environment, a mapping from variable identifiers to entities in the store. A semantic stack, containing pairs of statements in execution and the associated environment.

When a program is executing different values are added to the stack, the store and the environment according to the specified semantics of the statement. A thorough walk-through is done in the book.

Dataflow Variables

The single-assignment store may contain variables that are unbound, dataflow variables. This means that they can be used as out-parameters from procedures and partial values in records. It is also possible to bind two variables to each other. When one becomes bound then all variables see that binding.

When an unbound variable is accessed before it is bound execution waits until the variable is bound and then continues. This will enable both concurrent declarative programming and relational programming later in the book.

Practical Language

To make the language practical several syntactic conveniences are added to the kernel language:
  • Nested partial values: person(name:"George" age:25) instead of local A B in A="George" B=25 X=person(name:A age:B) end
  • expr1 andthen expr2 translates into if expr1 then expr2 else false end
  • expr1 orelse expr2 translates into if expr1 then true else expr2 end
  • if and case statements can be nested concisely.
  • Statements can be turned into expressions using a nesting marker $: proc {name} skip end translates into name = proc {$} skip end
  • Records are written animal(name:”Tapir” age:77)
  • Tuples are records with integer values animal(1:”Tapir” 2:77) may be written as animal(“Tapir” 77)
    • Anonymous tuples are commonly written with infix notation with # as the separator
    • ’#’ (“Tapir” 77) equals “Tapir”#77
  • Lists are either the atom nil or a tuple ’|’ (H T).
    • In infix that is H|T.
    • 1 | 2 | 3 | nil may be abbreviated [1 2 3]

Procedures are selected over functions since they are more flexible. They allow multiple outputs or none. In combination with the strong support for records, procedures will later enable modules and object oriented programming through simple transformations.

When adding functions as linguistic abstractions, notice how the dataflow variable R is unbound until inside the procedure. This is impossible if using a normal value store where the variables are bound at definition time.

% Functions as linguistic abstractions
fun {Max X Y}
    if X>=Y then X else Y end

end

% Translates into:
proc {Max X Y ?R}
    R = if X>=Y then X else Y end

end

Loops as linguistic abstractions (definitions of the procedures inf Programming Techniques below):

% The integer loops
for I in A..B do statements end

% and
for I in A..B;S do statements end

% translates into (with S=1 in the first case)
{For A B S proc {$ I} statements end}



% The list loop
for X in L do statements end

% translates into
{ForAll L proc {$ X} statements end}


Programming Techniques

Since the declarative model is similar to the functional (stateless) model, standard functional programming techniques such as higher order functions and recursion is used.

Iteration

Iteration is done with recursion:

% Standard iteration
fun {Iterate S IsDone Transform}
    if {IsDone S} then S
    else S1 in

        S1={Transform S}
        {Iterate S1 IsDone Transform}
    end
end

% A list loop
proc {ForAll L P}
    case L
    of nil then skip
    [] X|L2 then

        {P X}
        {ForAll L2 P}
    end
end

% An integer loop
proc {For A B S P}
    proc {LoopUp C}
            if C=<B then {P C} {LoopUp C+S} end

        end
    proc {LoopDown C}
        if C>=B then {P C} {LoopDown C+S} end
    end

in
    if S>0 then {LoopUp A} end
    if S<0 then {LoopDown A} end

end

Difference Lists

Another technique that is enabled by choosing single-assignment variables is programming with difference lists. A difference list is a 2-tuple where the first element is a list and the second element is a tail of the first list.

  • nil#nil % Represents the empty list
  • [a]#[a] % so does this
  • X#X % and this
  • (a|b|c|X)#X % Represents [a b c]
  • (a|b|c|d|X)#(d|X) % so does this
  • [a b c d]#[d] % and this

Notice how unbound variables can be placed at the end of the lists. This enables some very cool features. To append (a|b|c|X)#X and (d|e|f|Y)#Y, just bind X to (d|e|f|Y). This creates the difference list (a|b|c|d|e|f|Y)#Y. We have just appended the lists [a b c] and [d e f] with a single binding. Here is a function that appends any two difference lists:

% Function to append to difference lists
fun {AppendD D1 D2}
    S1#E1=D1
    S2#E2=D2
in
    E1=S2
    S1#E2
end

% It can be used like this (Browse means evaluate in Oz)
local X Y in {Browse {AppendD (1|2|3|X)#X (4|5|Y)#Y}} end

Constant time append versus linear time of the first list with a value store. Nice!

Abstract Data Types

Simple implementations of ADT leak implementation details to the user. This makes it possible to preform unsafe operations.

% Simple implementation of a stack.
fun {NewStack} nil end
fun {Push S E} E|S end
fun {Pop S E} case S of X|S1 then E=X S1 end end

fun {IsEmpty S} S==nil end

One way to avoid this is by using keys for accessing the ADT. Oz introduces the concept of names, created with {NewName}, to create tokens that are unique within the system. {NewName} is not declarative, since it returns a new value every time it is called, but programs using it may still behave declaratively.

% A procedure for creating a wrap/unwrap pair, for protecting values.
proc {NewWrapper ?Wrap ?Unwrap}
    Key={NewName}
in
    fun {Wrap X}
        fun {$ K} if K==Key then X end end

    end
    fun {Unwrap W} {W Key} end
end

% Protect the value
ProtectedValue={Wrap Value}

% Retrieve the value
Value={Unwrap ProtectedValue}


% A secure version of the stack

local Wrap Unwrap in
    {NewWrapper Wrap Unwrap}
    fun {NewStack} {Wrap nil} end
    fun {Push S E} {Wrap E|{Unwrap S}} end

    fun {Pop S E}
        case {Unwrap S} of X|S1 then E=X {Wrap S1} end
    end
    fun {IsEmpty S} {Unwrap S}==nil end

end

Programming in the large

Oz supports structuring programs by modules and functors. A module is implemented as a record with procedures. Only the interface is put into the export record.

declare MyList in
local
    proc {Append ... } ... end
    proc {MergeSort ...} ... end

    proc {Sort ... } ... {MergeSort ...} ... end
    proc {Member ...} ... end
in
    MyList=´export´(append:Append sort:Sort member:Member)

end

Using procedural abstraction this module can be turned into a software component or functor.

fun {MyListFunctor}
    proc {Append ... } ... end

    proc {MergeSort ...} ... end
    proc {Sort ... } ... {MergeSort ...} ... end
    proc {Member ...} ... end

in
    ´export´(append:Append sort:Sort member:Member)
end

Every time MyListFunctor is called it creates and returns a new MyList module.
  • A functor definition can be evaluated at runtime, giving a functor.
  • A functor can have external references to other entities through closures.
  • A functor can have arguments, which are the other modules needed.
  • A functor is lightweight; it can be used to encapsulate a single entity.

A linguistic abstraction is added to the practical language.


functor
export
    append:Append
    sort:Sort
    member:Member
define
    proc {Append ... } ... end
    proc {MergeSort ...} ... end

    proc {Sort ... } ... {MergeSort ...} ... end
    proc {Member ...} ... end
end

Apart from {NewName}, everything up to now has been declarative, that is without side-effects. To enable programming with functors we need to be able to load functors from multiple files. To do this we need IO.

Values in Oz can be stored and loaded with the Pickle module. Note that loading takes a URL and hence can be loaded over the network.

{Pickle.save X FN} % Save X in file FN
{Pickle.load FNURL ?X} % Load X from file (or URL) FNURL


And since procedures are values and functors procedures, they to can be saved and loaded. Since modules are so common additional functions exists in the Module module.

% Loads the MyList module into the variable MyListModule
MyListModule = Module.link [´MyList.ozf´]}

% System modules are loaded from a known path while others may be loaded explicitly.
functor
import
    Browser
    FO at ´file:///home/mydir/FileOps.ozf´
define

    {Browser.browse {FO.countLines ´/etc/passwd´}}
end

The Pickle module is also used when implementing distributed computing in a very elegant way in the chapter about distribution.

The Other Models

Van Roy and Haridi investigates many models apart from the declarative model: The concurrent declarative model, the concurrent message-passing model, the stateful model, the object-oriented model, the stateful concurrent model, the relational model, the distributed model and the constraint programming model. Here is quick overview of some of the other models:

The Concurrent Declarative Model

The abstract machine of the declarative model is extended to include multiple semantic stacks instead of just one. Nothing else is changed. The kernel language is extended with the statement: thread S1 end.

thread
    proc {Count N} if N>0 then {Count N-1} end end

in
    {Count 1000000}
end

Streams are also implemented in the concurrent declarative model with the use of flow variables.

fun {Generate N Limit}
    if N<Limit then

        N|{Generate N+1 Limit}
    else nil end
end
fun {Sum Xs A}
    case Xs
    of X|Xr then {Sum Xr A+X}
        [] nil then A
    end

    end
local Xs S in
    thread Xs={Generate 0 150000} end % Producer thread
    thread S={Sum Xs 0} end % Consumer thread

    {Browse S}
end

Laziness cab be added to the model by one more instruction, ByNeed, to the kernel language. The execution state is extended with a by-need trigger, a pair trig(x, y) consisting of a dataflow variable y and a one-argument procedure x. Next to the single-assignment store, a new store called the trigger store is added to the abstract machine. The trigger store contains all the by-need triggers and is initially empty.

lazy is a linguistic abstraction that is defined in terms of ByNeed.

fun lazy {Generate N} N|{Generate N+1} end

% Is transformed into
fun {Generate N}
    {ByNeed fun {$} N|{Generate N+1} end}

end

The Stateful Model

Explicit state is added as one new basic type to the computation model. We call the type a cell. A cell is a pair of a constant, which is a name value, and a reference into the single-assignment store. The set of all cells lives in the mutable store, which is added to the abstract machine.

Compared to the declarative model, it adds just two new statements, the cell operations NewCell and Exchange. Syntactic sugar is added with: X=@C, bind X to the content of cell C and C:=X: set x to be the content of cell C.

The Object Oriented Model

Object oriented programming is supported by adding linguistic abstractions for class, attr and meth.

% A class
class Counter
    attr val
    meth init(Value)
        val:=Value
    end

    meth browse
        {Browse @val}
    end
    meth inc(Value)
        val:=@val+Value
    end
end

% A class without semantic support
local

    proc {Init M S}
        init(Value)=M in (S.val):=Value
    end
    proc {Browse2 M S}
        {Browse @(S.val)}
    end
    proc {Inc M S}
        inc(Value)=M in (S.val):=@(S.val)+Value
    end

in
    Counter=c(attrs:[val]
    methods:m(init:Init browse:Browse2 inc:Inc))
end

The methods of Oz supports variable length argument lists, optional arguments and an otherwise method that will be called if no other method is appropriate. This gives strong support for delegation and meta-programming.

As can be seen above, classes are implemented as a set of methods and a set of attributes.

An object can be implemented like this:

fun {New WClass InitialMethod}
    State Obj Class={Unwrap WClass}
in
    State = {MakeRecord s Class.attrs}
    {Record.forAll State proc {$ A} {NewCell _ A} end}
    proc {Obj M}
        {Class.methods.{Label M} M State Obj}
    end

    {Obj InitialMethod}
    Obj
end

Inheritance is implemented by calculating a new class record starting from existing class records. They are combined according to the preferred inheritance rules.

Summary

Van Roy and Haridi has produced an impressive book in the spirit of the Structure and Interpretation of Computer Programs. The book is notably free from critique of other languages. The authors let their impressive work speak for itself.

This short walk-through of the book, with most of the models and details left out, cannot do justice to this incredible work. A must read for anyone interested in programming language design.

Five out of five!

Friday, March 07, 2008

Summary of "Tog on Maximizing Human Performance"

Summary of Tog on Maximizing Human Performance with additional conclusions.

Prefer the human model to the machine model:

  • Eliminate as much as possible through calculations or guesses.
  • Prefer the human model to the machine model, compare two faucets, a good one lets the user control flow with one control and temperature with another.

Decrease Data Entry

  • Limit decision making.
    • Limit required information.
  • Provide the user with the needed information.
    • Pop up help information.
    • Find the information automatically if possible.
  • Communicate high probability answers.
    • Present choices so the odds become clear.
  • Hide obscure information under an advanced tab.

Limit percieved wait

  • Do calculations in the background.
    • Get the needed information first.
    • Start the background task while the user enters other information.
  • Pop up something relevant for the user to read if the wait is inevitable.
  • Mark lengthy operations early in the design process.

Thursday, March 06, 2008

How to Handle Project Managers

There is only one thing you need to do to keep a project manager happy: Tell them how long it takes!

If you think you will be done in three hours, tell them! If you think you will be done in three days, tell them! If you don’t know if it will take between three and five days, tell them! If your original estimate does not hold, tell them! If the task is to large or fuzzy to estimate, tell them! If you don’t have a clue, get one or get yourself another job! If they think your estimates are to large, tell them to do it themselves, then, get yourself another job!

The main thing to be aware about with project managers is: They don’t produce anything of value! No matter how much they belive that their status reports and powerpoint slides are progress, they aren’t, they show progress. This is why they are happy when they know how long you will take to complete a task; it makes them believe that they are in control.

Does this mean that project managers are useless? Not at all! An invalueble project manager can make the difference between a failing project and a successful one. So, what separates a invalueble project manager from a useless one?

  • An invalueble PM asks you when you will be done; a useless one tells you when you have to be done.
  • An invalueble PM asks you what he can do to help; a useless one why you are not done.
  • An invalueble PM shares everything; a useless one shares as little as possible.
  • An invalueble PM takes responsibility for a failing project; a useless one blames the team.
  • An invalueble PM gives the team credit for success; a useless one takes credit himself.
  • An invalueble PM cares about the team and the project; a useless one about himself.
  • An invalueble PM inspires the team; a useless one makes the team indifferent.
  • An invalueble PM has a happy team; a useless one a miserable team.
  • An invalueble PM knows that he is not invalueble; a useless one thinks he is.

No matter what kind of PM you have. Tell them how long it takes! works.