Wednesday, April 19, 2006

Interpreter Pattern and Structural Recursion

I have previously discussed the flaws and limitations of the Visitor Pattern; criticised the Singleton Patterm as a global variable in disguise; and dismissed all but one of the rest as kludges to work around the GoF's languages-of-choice. That leaves the Interpreter.

This is a critically important pattern, if you only learn one pattern, make it this one! It is so fundamental to what we do to be different in kind from the other patterns in the book. In fact it is so critical that Gamma et al would probably have been better off ignoring the other patterns and writing their book exclusively on the Interpreter. In a very real sense this is exactly what Daniel Friedman did in "Essentials of Programming Languages" (EoPL).

If nothing else, the fact that you can comfortably write an entire book introducing the basics of the Interpreter Pattern is a good sign we're dealing with a different beast here to the rest of the GoF. Can you imagine writing a 300 page book introducing the basics of the factory-method?

The reason why the interpreter pattern is so important is that it amounts to designing a language, and language is our primary tool as programmers. We solve problems with computers, ultimately we do so with sequences of opcodes passed to the execution unit of our cpus; but the number of concepts we can express in a single sentence in machine code is limited, and the amount of detail we can choose to ignore when it is irrelevant to our solution is minimal. The act of climbing the language stack, (machine code -> symbolic assembly -> macro assembly -> C -> libc -> [java, Scheme, ML, etc]) is an exercise in increasing these two measures. Note I included libc in that list. I did that because language is the core abstraction being invoked in library, module, and macro systems as Kernighan and Pike discuss in "The Practice of Programming".

Now for the bad news. Yes the interpreter pattern is all goodness and light, but the unfortunately the sample implementation provided by GoF is crap. It's crap for exactly the same reason the visitor pattern is an inappropriate approach for parse-tree manipulation. This is a symbolic transformation, and as a problem is decidedly non-object-oriented. I'll go into exactly what an object-oriented problem looks like another time, but suffice to say that there is a good reason why LISP has survived 50 years, and the applicability of functional programming techniques to symbolic programming is a major part of it.

The solution offered in Design Patterns is an excelent piece of OO design. The problem: You have an AST you wish to execute. The solution: encapsulate the knowledge of how each different node-type should be evaluated in an 'evaluate' method on each node-type's associated class. Below is an example calculator implemented in Java using this exact design:

$cat test/*.java

/**
 * test/Add.java
 */
package test;

public class Add implements Expression {
  private Expression lhs;
  private Expression rhs;

  public Add(Expression lhs, Expression rhs) {
    this.lhs = lhs;
    this.rhs = rhs;
  }

  public int calc() {
    return this.lhs.calc() + this.rhs.calc();
  }
}

/**
 * test/Div.java
 */
package test;

public class Div implements Expression {
  private Expression lhs;
  private Expression rhs;

  public Div(Expression lhs, Expression rhs) {
    this.lhs = lhs;
    this.rhs = rhs;
  }

  public int calc() {
    return this.lhs.calc() / this.rhs.calc();
  }
}

/**
 * test/Expression.java
 */
package test;

public interface Expression {
  public int calc();
}

/**
 * test/Main.java
 */
package test;

public class Main {
  public static void main(String[] args) {
    System.out.println(Integer.toString(
        new Mul(
          new Sub(new Num(6), new Num(2)),
          new Add(new Num(2), new Num(3))).calc()));
  }
}

/**
 * test/Mul.java
 */
package test;

public class Mul implements Expression {
  private Expression lhs;
  private Expression rhs;

  public Mul(Expression lhs, Expression rhs) {
    this.lhs = lhs;
    this.rhs = rhs;
  }

  public int calc() {
    return this.lhs.calc() * this.rhs.calc();
  }
}

/**
 * test/Num.java
 */
package test;

public class Num implements Expression {
  private int num;

  public Num(int num) {
    this.num = num;
  }

  public int calc() {
    return this.num;
  }
}

/**
 * test/Sub.java
 */
package test;

public class Sub implements Expression {
  private Expression lhs;
  private Expression rhs;

  public Sub(Expression lhs, Expression rhs) {
    this.lhs = lhs;
    this.rhs = rhs;
  }

  public int calc() {
    return this.lhs.calc() - this.rhs.calc();
  }
}
and indeed this does print '20' as expected.

Compare this with the ML code below, or the far more complex interpreter on page 74 of EoPL, and the problem is immedately clear. With symbolic transformation we are invariably performing 'structual recursion'. We have a data-structure, that is indeed a structure, defined recursively that is then processed by following the structure of the data, possibly performing an operation at each step. Consequently it is the structure that is important in comprehending the code, and ensuring a perfect match between data-structure and code-structure that is required to get it right. By scattering the code across multiple files, it makes it much more difficult to understand the structure of the code, and impossible to verify that this matches the structure of the data without signifigant effort.

$cat calc.ml

(* Calculator *)

type expression =
  | Num of int
  | Add of expression * expression
  | Sub of expression * expression
  | Mul of expression * expression
  | Div of expression * expression ;;

let rec calc expr =
  match expr with
    | Num n -> n
    | Add (e1, e2) -> calc e1 + calc e2
    | Sub (e1, e2) -> calc e1 - calc e2
    | Mul (e1, e2) -> calc e1 * calc e2
    | Div (e1, e2) -> calc e1 / calc e2

let main () =
  print_int(calc(Mul(Sub(Num 6, Num 2), Add(Num 2, Num 3))));
  print_newline();
  exit 0 ;;
main() ;;
and it is now trivial to inspect the code and the data and verify that the structures are identical. In fact it is so trivial the compiler will warn us of our mistake.
$ diff calc.ml calc-broken.ml 15c15
<     | Mul (e1, e2) -> calc e1 * calc e2
---
> (*    | Mul (e1, e2) -> calc e1 * calc e2 *)
$ ocamlc -o calc-broken calc-broken.ml 
File "calc-broken.ml", line 11, characters 2-199:
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
Mul (_, _)
$ ./calc-broken
Fatal error: exception Match_failure("calc-broken.ml", 11, 2)
Now if you are stuck in an OO-world then the closest you can get to the above is to use either the visitor pattern or dynamic double dispatch. Not as neat, and a scary amount of boilerplate, but it works, and it is definately preferable to the example given in GoF; and when the time comes that you are not compelled to consign yourself to the OOP-only gulag you now know that there is something worth escaping to.

77 comments:

Paula said...

While not addressing every problem, using the new built enumerations in Java can go some way to fixing the Java approach. An example of what I mean is on the description page for the feature. I'm referring here to the example:
public enum Operation {
  PLUS { double eval(double x, double y) { return x + y; } },
  MINUS { double eval(double x, double y) { return x - y; } },
  TIMES { double eval(double x, double y) { return x * y; } },
  DIVIDE { double eval(double x, double y) { return x / y; } };

  abstract double eval(double x, double y);
}

This is still short of what you want, but it has everything in one file, and with a lot less syntactic sugar/salt, making it much clearer.

Incidentally, I note that you have a better approach for AST evaluation. Given the difficulties of implementing some parts of SPARQL in SableCC, would you be inclined to put the theory into practice and write a new compiler compiler for us please? :-)

Unknown said...

I didn't see it then, but it turned out that getting fired from Apple was the best thing that could have ever happened to me. The heaviness of being successful was replaced by the lightness of being a beginner again, less sure about everything. It freed me to enter one of the most creative periods of my life.
Electrician Marbella

Unknown said...

Design is the fundamental soul of a man-made creation that ends up expressing itself in successive outer layers of the product or service. The iMac is not just the color or translucence or the shape of the shell. The essence of the iMac is to be the finest possible consumer computer in which each element plays together.
Electrician Spain

Unknown said...

Who wants a stylus. You have to get em and put em away, and you lose em. Yuck. Nobody wants a stylus.
Tucson Massage Therapy

jhoney said...

Online Pharmacy
There is no question that instantaneous water heaters are good options to trust in terms of their water heating services. However, you need to know that not all kinds of this water heater will work best for you.

jhoney said...

I am really impressed by this excellent stuff on ZBrush which is a digital sculpting and painting program that has revolutionized the industry. I've enjoyed reading the nice post
Cerrajeros en Barcelona

jhoney said...

Xanax Online
You produce a great point in your own final paragraph. We couldn’t agree more together with your points. In today’s modern world, your approach to this issue is lacking in today’s kids. We need to ensure that our kids find out more on this topic so we nev

habshi75 said...

No one wants to die. Even people who want to go to heaven don't want to die to get there. And yet death is the destination we all share. No one has ever escaped it. And that is as it should be, because Death is very likely the single best invention of Life. It is Life's change agent. It clears out the old to make way for the new.
Accident Lawyer Calgary

jhoney said...

Hi, just wanted to say I attended this conference last year, and found it by far the best of about 8 conferences that I attended in the field. Full of professional insight based on testing by experts that knew what they were talking about. I would certain

jhoney said...

Valium
Hi, just wanted to say I attended this conference last year, and found it by far the best of about 8 conferences that I attended in the field. Full of professional insight based on testing by experts that knew what they were talking about. I would certain

jhoney said...

When everything else physical and mental seems to diminish, the appreciation of beauty is on the increase.
Pool Surrounds Spain

jhoney said...

wow, awesome post, I was wondering if there is a way to enlarge my penis quickly. and found your site by google, learned a lot, now i’m a bit clear. bookmarked and also signed up your rss. keep us updated.
Pool Surrounds Costa del Sol

mical3211 said...

A lot of people in our industry haven't had very diverse experiences. So they don't have enough dots to connect, and they end up with very linear solutions without a broad perspective on the problem. The broader one's understanding of the human experience, the better design we will have.
Buy Sleeping Tablets Online

mical3211 said...

Flaming enthusiasm, backed up by horse sense and persistence, is the quality that most frequently makes for success.
Buy Sleeping Tablets

mical3211 said...

Remembering that you are going to die is the best way I know to avoid the trap of thinking you have something to lose. You are already naked. There is no reason not to follow your heart.
Lunesta Online

jhoney said...

Diazepam Online
Though beauty gives you a weird sense of entitlement, it's rather frightening and threatening to have others ascribe such importance to something you know you're just renting for a while.

habshi75 said...

Your work is going to fill a large part of your life, and the only way to be truly satisfied is to do what you believe is great work. And the only way to do great work is to love what you do. If you haven't found it yet, keep looking. Don't settle. As with all matters of the heart, you'll know when you find it.​location appartement toscane

jhoney said...

This is a nice post in an interesting line of content.Thanks for sharing this article, great way of bring this topic to discussion.
Lorazepam Online

habshi75 said...

Always bear in mind that your own resolution to succeed is more important than any other.
online veiling

mical3211 said...

Everyone here has the sense that right now is one of those moments when we are influencing the future.
Personal injury lawyers Cambridge

jhoney said...

Car Accident Lawyer Barrie
Hi, just wanted to say I attended this conference last year, and found it by far the best of about 8 conferences that I attended in the field. Full of professional insight based on testing by experts that knew what they were talking about. I would certain

mical3211 said...

Sometimes when you innovate, you make mistakes. It is best to admit them quickly, and get on with improving your other innovations.
Personal injury lawyers Scarborough

jhoney said...

When everything else physical and mental seems to diminish, the appreciation of beauty is on the increase.
Accident Lawyers Barrie

jhoney said...

When virtue and modesty enlighten her charms, the lustre of a beautiful woman is brighter than the stars of heaven, and the influence of her power it is in vain to resist.
Accident Lawyers Barrie

mical3211 said...

I have a great respect for incremental improvement, and I've done that sort of thing in my life, but I've always been attracted to the more revolutionary changes. I don't know why. Because they're harder. They're much more stressful emotionally. And you usually go through a period where everybody tells you that you've completely failed.
Injury Lawyer Brampton

mical3211 said...

A lot of companies have chosen to downsize, and maybe that was the right thing for them. We chose a different path. Our belief was that if we kept putting great products in front of customers, they would continue to open their wallets.
Car Accident Lawyers Woodbridge

jhoney said...

We live in a wonderful world that is full of beauty, charm and adventure. There is no end to the adventures that we can have if only we seek them with our eyes open.
Injury Lawyer Bolton

jhoney said...

Though beauty gives you a weird sense of entitlement, it's rather frightening and threatening to have others ascribe such importance to something you know you're just renting for a while.
Accident Lawyers Keswick

jhoney said...

Car Accident Lawyers Niagara Falls
We want to reinvent the phone. What's the killer app? The killer app is making calls! It's amazing how hard it is to make calls on most phones. We want to let you use contacts like never before - sync your iPhone with your PC or mac.

Unknown said...

The BIN number is the first 6 digits on a credit card, and is used to identify a few things. It tells the checker where the card was issued and by what bank.

prevent online fraud

jhoney said...

The pursuit of truth and beauty is a sphere of activity in which we are permitted to remain children all our lives.
valium 10mg

jhoney said...

Sometimes when you innovate, you make mistakes. It is best to admit them quickly, and get on with improving your other innovations.
http://www.costapharmacy.com/valium.htm

jhoney said...

We live in a wonderful world that is full of beauty, charm and adventure. There is no end to the adventures that we can have if only we seek them with our eyes open.
insurance management

mical3211 said...

You can't just ask customers what they want and then try to give that to them. By the time you get it built, they'll want something new.
agyevents

jhoney said...

The real sin against life is to abuse and destroy beauty, even one's own even more, one's own, for that has been put in our care and we are responsible for its well-being.
Mail Order & Internet Online Pharmacy

jhoney said...

I gathered useful information on this point as I am working on a business project. Thank you posting relative information and its now becoming easier to complete this assignment

jhoney said...

I gathered useful information on this point as I am working on a business project. Thank you posting relative information and its now becoming easier to complete this assignment
Ambien Online

jhoney said...

There is no question that instantaneous water heaters are good options to trust in terms of their water heating services. However, you need to know that not all kinds of this water heater will work best for you.
zolpidem online

jhoney said...

This is a nice post in an interesting line of content.Thanks for sharing this article, great way of bring this tbuy facebook likes
opic to discussion.

eramejaz said...

To succeed in life, you need two things: ignorance and confidence.
fax broadcasting

jhoney said...

The real sin against life is to abuse and destroy beauty, even one's own even more, one's own, for that has been put in our care and we are responsible for its well-being.
buy facebook fans

mical3211 said...

You have a real ability for writing unique content. I like how you think and the way you represent your views in this article. I agree with your way of thinking.
buy facebook status likes

Unknown said...

placing the buns backtalk on the entrance cavity further blowing atmosphere straight private the tool though playing dissimilar memorandums by boot besides uncovering the hollows onward the carcass of the channel.
detox nj

hhaniya said...

Great info! I recently came across your blog and have been reading along. I thought I would leave my first comment. I don’t know what to say except that I have.
maison toscane

Unknown said...

Hey! I simply wish to give a huge thumbs up for the good info you will have here on this post. I shall be coming back to your blog for more soon.
Wisconsin

jhoney said...

The problem with beauty is that it's like being born rich and getting poorer.
valium online without prescription

Unknown said...

Replacement cartridge for the Salmson NSB 04-15, Wilo Z 15 A and Salmson SB 04 -15 hot water circulating pumps are exactly the same. The model number and external look of the pump will differ depending on its age and where the model of pump you have has originated from.

Salmson NSB 04-15 Replacement Impeller Cartridge

Unknown said...

Se você estiver olhando para enviar convites para gostar de uma página, procure Facebook Convide a página. Esse é o nosso outro aplicativo que funciona para páginas do Facebook desde a mudança de interface.

Convide Todos Seus Amigos do Facebook

hhaniya said...

Ryan Shed Plans: Ryan Henderson Reveals His Staggering Collection Of More Than 12,000 DIY Shed Plans And Woodworking Projects You Can Accomplish Quickly And Easily Right From Home...
Peter J. Burns III

Unknown said...

There is no question that instantaneous water heaters are good options to trust in terms of theitamaris
r water heating services. However, you need to know that not all kinds of this water heater will work best for you.

Unknown said...

Amazing Las Vegas Escorts will blow you away. Use this Las Vegas escorts directory to find and hire the ideal nude adult entertainer for your private party.

las vegas escorts

mical3211 said...

Remembering that I'll be dead soon is the most important tool I've ever encountered to help me make the big choices in life. Because almost everything - all external expectations, all pride, all fear of embarrassment or failure - these things just fall away in the face of death, leaving only what is truly important.
diazepam online

jhoney said...

The real sin against life is to abuse and destroy beauty, even one's own even more, one's own, for that has been put in our care and we are responsible for its well-beibuy real diazepam
ng.

Unknown said...

At Ideal Homes Portugal we specialise in assisting people like you in purchasing property overseas, and have over ten years experience of doing so.

houses in portugal

mical3211 said...

For the past 33 years, I have looked in the mirror every morning and asked myself: 'If today were the last day of my life, would I want to do what I am about to do today?' And whenever the answer has been 'No' for too many days in a row, I know I need to change something.
xanax online

Unknown said...

I enjoyed this post very much, such a out standing post. Marketing is a complex thing and there is no proper formula but constant engagement and efforts are the key of succes.
Amir Parekh

Unknown said...

ildcare is very expensive!In today's economy, everyone is trying to save a buck wherever they can. And work-at-home moms are no exception. From stay-at-home moms who want to bring in extra cash to
buy online casino

jhoney said...

Being the richest man in the cemetery doesn't matter to me. Going to bed at night saying we've done something wonderful, that's what matters to me.
diazepam buy online

Unknown said...

There are a plenty of online sites for the fund transfer and exchange of currency. These sites ensure the delivery of payments from different websites and direct it to the customer accounts on these online websites or in local bank accounts.

Virtual World Services GmbH

jhoney said...

I like your all activities because children who participating in these activities will surely learn the necessary thing which helps to live healthy.
diazepam without a prescription

Unknown said...

Der er ingen måde du kan forhindre folk i at få drukket sig fulde og rode lidt rundt til din fest. Men det du kan forhindre dem i, er at smadre glas kopper og komme til skade, ved at vælge red cups.

RED Cups

mical3211 said...

Try not to become a man of success, but rather try to become a man of value.
online casino malta

jhoney said...

You must know by now, your article goes to the nitty-gritty of the subject. Your clarity leaves me wanting to know more. Just so you know, i will immediately grab your feed to keep up to date with your online blog. Sounding Out thanks is simply my little
Regalos Originales

jhoney said...

Thank you for this post. Thats all I are able to say. You most absolutely have built this blog website into something speciel. You clearly know what you are working on, youve insured so many corners.thanks
HayCompras

Unknown said...

La seule application qui a survécu à 19+ mois de mises à jour de Facebook et toujours aussi fort !!! Accepter aucune copie, le soutien est disponible via notre site.

Tout Sélectionner pour Évènements Facebook

Unknown said...

LAVORO DA CASA -Scopri come lavorare da casa e guadagnare soldi in pochi minuti grazie a questa semplice guida gratuita adatta anche per i pricipianti.

LAVORO DA CASA

Unknown said...

Peter J. Burns III is a very successful and hardworking businessman. Everyone knows that punctuality and honesty is the key to success. Peter J. Burns III is the person who fully satisfies this quality.

Peter J. Burns III

Unknown said...

Menopausal females face an increased risk regarding heart conditions. This will be blamed on the fall inside estrogen levels that assist in:
Buy Sleeping Tablets Online

Unknown said...

Amir Parekh says, that being the manager of the organization, you need to appreciate the right person, at the right time. This increases the confidence of your employee and the employee become more dedicated for the work.

Amir Parekh

mical3211 said...

My favorite online money maker by far has been email marketing. I like it because it allows me to have a captive audience that I can connect with and market to at will.
Buy Facebook Likes

Unknown said...

I motivi per cui potresti volerti rivolgere a una delle Palestre Monza possono essere i più vari. Si parte dal desiderio di migliorare il tuo aspetto fisico.

palestre monza

Unknown said...

Solar Hot Water Parts has the largest range of replacement spare parts, catering for all makes and models of solar hot water systems on the market. Where a product has become obsolete, we have researched and sourced alternatives, making the repair and maintenance of your hot water system simple and easy.

circulating pump

kiranjee17 said...

I motivi per cui potresti volerti rivolgere a una delle Palestre Monza possono essere i più vari. Si parte dal desiderio di migliorare il tuo aspetto fisico.
where to buy stilnox

mical3211 said...

In order to succeed you must fail, so that you know what not to do the next time.
stilnox purchase

Unknown said...

A magnetic starter is a full voltage starter designed to give thermal overload as well as under voltage security for collector cage motor and might be remotely operated automatically or through push button post if you are far from the motor.
salt lake city climbing

Unknown said...

Violini elettrici di ispirazione etnica ad amplificazione elettrica e meccanica. Strumenti multimediali a spettro continuo.Le competenze per sviluppare gli strumenti sono infinite, chiunque abbia passione per la musica può metter del suo nel creare nuove sonorità basate sulla vibrazione del legno e filtraggio elettronico.

violini elettrici

Unknown said...

Animals and Pets Marketplace - Sell and Buy Pets and Animals directly form buyer or seller in your country, region or city for FREE.

Sell My Pet