Here’s the trick that I’ll use – and it’s simple to do.
I’ll define a procedure, which I will call Q,
that will use P’s predictions of halting success
to stir up a terrible logical mess.

Do read the whole thing, as it actually does contain a peer-reviewed proof.

Personally, I find rhyme and meter to be underused tools in the fields of mathematics and computer science. I suspect that most programmers don’t read technical journals at all; making the research more entertaining can only help the field. Then again, I’ve been known to cancel spam in verse, so my opinion may be outside of the mainstream.

So anyway, I’m off to adapt Beowulf into a proof in epic verse of the Taniyama–Shimura conjecture.  I’m still dithering over whether to base my adaptation on Seamus Heaney’s translation, or the original, Old English.

Share This | Email this page to a friend

I’ll be speaking at the CodeRage III virtual conference, on the subject of functional programming in Delphi 2009.  Here’s the (rather bland) abstract:

Delphi 2009 includes several new features well-suited to a functional style of programming.  We’ll explore the use of generics, anonymous methods, and new RTL types while introducing concepts from functional programming.

If you’ve been following my blog over the past few months, you might have a fair idea of what to expect.  As you can tell from the somewhat vague abstract, I’m still rounding out the details of the presentation.  If there’s anything you’d like to see me cover, please make your suggestion in comments.

Share This | Email this page to a friend

This speaks to the importance of abstracting data access.  The nice thing about object relational mapping is that once you’ve read the data, your data are just objects, whether or not they’re POCOs. You can and should emphasize this encapsulation by hiding the reading and writing behind a framework such as the Repository pattern.  It is, IMHO, a mistake to ever call something like Context.SaveChanges inside of a controller.

Share This | Email this page to a friend

It is often the case that we use software tools to transform these conceptual models into executable code of one form or another.  For example, a database management tool may know how to transform an ERD into physical database metadata.  A UML design surface might know how to transform a UML model into compilable code.  Most object-relational mappers designed for non-dynamic languages such as C# and Java seem to work by transforming some kind of schema file, usually XML, into compilable code.  And so on…

Inside the application, at runtime, a similar transformation of models occurs.  Let’s examine the pipeline which results in transforming data in a database into HTML which a user can view:

1. The user invokes an action.  This starts a chain of events ultimately resulting in a call to the database server in the form of an SQL statement.  The database server transforms its will on-disk representation of the data into a result set understandable by the data access components.
2. The object-relational mapping transforms the result set into entity instances — instances of classes in a form useful to implementers of business logic.
3. If the application is using the Repository pattern, these entity instances may be passed directly to the controller.  Or they may be transformed into lightweight data access objects.
4. Whatever their form, the entity instances will be wrapped up into a model containing all of the information required to render a view.
5. The view will transform the entities into a different kind of model: HTML.
6. The browser will transform the HTML into a DOM which can be further manipulated via JavaScript.

A similar series of transformations between model types occurs when we accept user input and store it back in the database.

These series of transformations are not so different from the transformations I mentioned above, like transforming a UML model into executable code.  Indeed, compilation itself is just another kind of model transformation, changing a representation which is (hopefully!) readable by a developer into a representation readable by a machine.  If the transformation is lossless, then it can probably be done in both directions.

So one way to look at an application is as a series of transformations from one model type to another, not only in execution, but also in the manner in which the application itself is built. However, the transformations are performed with wildly different implementations:

• A special-purpose executable (e.g., a compiler) can be used to transform the models. Such executables are typically fairly limited; most compilers support only one language, and do not, for example, transform UML models into code.
•  We can write code in a high-level language to transform the models, often in a way which is dependent on the specific types or properties involved (e.g, A.Foo = b.Foo), or possibly at a more generic level, such as with a common interface.
• We can create informally-specified principles for model transformation, such as "convention over configuration," which are often sufficient to completely specify the transformation without requiring code.
• We can create systems of rules for model transformation. The formal name for such a system of rules is an algebra, not to be confused with the elementary algebra you learned in high school. This is a set of simple rules designed to be composed into more advanced transformations. One such system is relational algebra, which surfaces (in a heavily mutilated form) in SQL databases.

Now, my purpose in this post is not to claim that one of these methods is superior to the others.  "The best tool for the job" still applies.  The idea of model transformation, however, encompasses more parts of a software system than many programmers commonly suppose.  The notion of treating your source code as a model which can be transformed via an algebra into an equivalent, but faster and provably correct, application is not new, but is perhaps surprising to programmers who have not studied functional programming. So the question is not "How do I create an instance of Bar from an instance of Foo?," but "What kind of transformation is this, and how does it fit into the context of the other transformations I’m performing in this application?"

Such a worldview makes technologies like Haskell’s monads and LINQ, designed as generic solutions for the problem of transforming one type of set into another, even more interesting than they already are.

Share This | Email this page to a friend

Most non-trivial applications have many different models, and for good reason.  If the application uses a relational database, it will have a relational model.  A non-trivial web application may use an application server, containing an entity model with an object-relational mapping, perhaps based on a framework like the Entity Framework or NHibernate.  In some designs, these entity types are not exposed from the application server, but rather represented as lightweight data access objects.  These data access objects are made available to clients of the application server, such as a web application.

Inside the web application, it’s possible that the lightweight data access objects will be made available directly to the View, without being wrapped up inside any other type.  But it’s more likely that additional information will need to be passed to the View, requiring the use of an additional model type, which wraps up the information required by a particular View.  Or, a View might require a different representation of the data access objects, such as XML or JSON.

So let’s count the different types of "Models" I’ve listed so far:

1. Relational data model
2. Entity model, perhaps with an object-relational mapping
3. Lightweight data access objects
4. View-specific models

To be clear, I don’t think the existence of multiple types of models is by itself a problem.  But I do think that the overloading of the term create some confusion about how to follow the MVC application design.

When you create a new ASP.NET MVC web application, Visual Studio creates a Solution containing a single project for the web application itself, with a folder called Models.  Many of the demonstrations of ASP.NET MVC projects that I’ve seen drop a LINQ-to-SQL model inside of this folder.  I understand that people like to keep their demonstrations simple, but as a rule I think that any type of object-relational model should be in a separate assembly from the web application, along with any business logic implementation required.  This second assembly becomes the API for your data which the web application will use.  It can be a web service, or an assembly which exposes methods for accessing the data directly, e.g. with the Repository pattern. However, I keep the Models folder in the web application, and use it for "View models," which handle things like pagination, aggregation of multiple instances required by the view, etc.

Maybe MVC should stand for Models View Controller?

In the second part of this series, I will examine additional types of models, and the general problem of transforming one model into another.

Share This | Email this page to a friend

Share This | Email this page to a friend

So I’d like to note another project which uses the same general concept in a very different manner.  OpenCTF is a free framework which generates DUnit test cases by looking for certain "known" errors in arbitrary components.

Delphi’s relatively limited introspection/RTTI features restrict how far you can go with projects like this.  It’s really only possible to automatically test published properties and published methods with known signatures.  Likewise, most of the Delphi-aware automated testing tools require that you change your application to include special testing interfaces in order to get full functionality from the tool. One of the benefits of enhanced RTTI in the future would be more options for automated testing.

Share This | Email this page to a friend

Memoization is a generic solution to the problem of caching function results. The function Memoize accepts a function as an argument and returns a function which does exactly the same thing, except that it caches the results.  Here’s the prototype:

class function Memoize<A, R>(AFunc: TFunc<A, R>): TFunc<A, R>;

So my version of Memoize will accept any function which takes a single argument of any type, and returns a result of any type. Memoize returns a new function with exactly the same signature. I’ve often written systems to cache the results of database queries in my older Delphi code.  Lately, I’ve been using TClientDataSet to do the same thing, but it still results in several lines of code to accomplish what is essentially a single function call.  Memoize allows me to solve this problem one time and use it for as many situations as I can imagine.

Well, almost any function.  Caching is obviously only useful for functions which are referentially transparent, which is another way of saying that their output is completely determined by their input.  You wouldn’t want a cached version of "Now()" or "Create()", for example. Memoization is most useful when a function performs a lengthy calculation, or queries a database or a web service with a lot of latency.  In order to simulate such a function for the purpose of testing my implementation of Memoize, I’ve written the following test function:

class function TestTMemoize.SlowIncrement(ANum: integer): integer;
begin
  Sleep(100); // simulate web service / db access
  Result := ANum + 1;
end;

This is useless, but it allows me to distribute a testable version of the project without having any dependency on any specific database or Web service.  Feel free to substitute a more useful function if you try this yourself. In order to create a memoized version of this function, I just pass it to Memoize, and call the function that is returned instead of the original one:

procedure DoStuff;
var
  MemoizedFunc: TFunc<integer,integer>;
  iResult: integer;
begin
  MemoizedFunc := TMemoize.Memoize<integer,integer>(SlowIncrement);
  iResult := MemoizedFunc(1);
end;

The Memoize function certainly sounds useful, but how could I write such a thing?  Well, I obviously need generics, or my version of Memoize would be limited to functions which only accepted and returned one specific type.  And I need anonymous methods, because that is the only way that I can return new functions at runtime.  Finally, I need some kind of cache to store pairs of arguments and results, so that successive executions with the same argument can find result in the cache.

Let’s examine the last requirement first.  Delphi 2009’s Generics.Collections unit includes a TDictionary<TKey,TValue> type which, at first glance, it appears to do what I need.  Unfortunately, it isn’t lifetime-managed. So I will just subtype Delphi 2009’s TDictionary<TKey,TValue> and implement a new IDictionary<TKey,TValue> interface I will create.

I will explain why it is important to have a lifetime-managed dictionary in order to implement this function at the end of this post. You can easily understand the rest of the post without grasping this detail, if you’re willing to take my word on the fact that I need a lifetime-managed list. For the time being, let’s just continue with the code. Here’s the full source code for Memoize, which is actually very simple:

class function TMemoize.Memoize<A,R>(AFunc: TFunc<A, R>): TFunc<A, R>;
var
  Map: IDictionary<A, R>;
begin
  Map := TManagedDictionary<A, R>.Create;

  Result := function(arg: A): R
  var
    FuncResult: R;
  begin
    if Map.TryGetValue(arg, FuncResult) then begin
      Exit(FuncResult);
    end;
    FuncResult := AFunc(arg);
    Map.Add(arg, FuncResult);
    Exit(FuncResult);
  end;
end;

In Delphi 2009, you can call Exit with an argument in order to return a certain value from a function immediately, as if you had assigned Result and then called Exit without the argument.  Other than that, I don’t think there is too much to explain about the implementation above.

In order to prove that it works, I wrote a unit test.  The unit test shows that the second execution of a Memoized version of a slow function for the same argument (1) returns the same value and (2) is more than two orders of magnitude faster.  One of the reasons I included this unit test was to demonstrate that unit tests can be used to verify performance goals as well as functional specifications.  In order to profile the function, I’ve "borrowed" Barry Kelly’s useful TBenchmarker class. Here’s the test:

procedure TestTMemoize.TestMemoize;
var
  Cold, Warm: Double;
  ColdResult, WarmResult, AnonResult: integer;
  MemoizedSlowInc: TFunc<integer, integer>;
  BenchmarkProc: TProc;
begin
  MemoizedSlowInc := TMemoize.Memoize<integer,integer>(SlowIncrement);
  BenchmarkProc := procedure()
  begin
    AnonResult := MemoizedSlowInc(1);
  end;

  // first execution should be slow
  Cold := TBenchmarker.Benchmark(BenchmarkProc, 1, 0);
  ColdResult := AnonResult;
  // next time for same value should be fast
  Warm := TBenchmarker.Benchmark(BenchmarkProc, 1, 0);
  WarmResult := AnonResult;

  CheckEquals(ColdResult, WarmResult);
  CheckTrue(Warm < (Cold / 100));
end;

You can download the full source code from CodeCentral.

Finally, here’s the full explanation for why I needed to create a lifetime-managed dictionary:

Anonymous methods, in every implementation I’ve ever seen, can "capture" variables in the declaring method.  This means that you can use variables (or method arguments) declared in the method which defines the anonymous method, without passing them as arguments.  But since we are going to return the anonymous function as the result of the defining function, any object referenced in the anonymous function must not be freed by the defining function.  In Delphi 2009, captured variables are captured by reference (this is similar to C#, but different than JavaScript).  Recall that anonymous methods are reference counted.  When an anonymous method captures a variable in the declaring method, it will be freed when there are no more references to the anonymous method, provided that the captured variable is a lifetime-managed type, such as a string, a record, an interface, etc.

Share This | Email this page to a friend

When you run a search query on CDN, you’ll see just below your search results line of text that looks something like this:

Query processed in 375ms (31.25ms server/network, 343.75ms database)

This text describes exactly how long it took to prepare the query, run it, retrieve all information required for display from the database, check the visibility of every result, sort the results according to the user’s preference, and prepare the set of results in the current page for display.

The times I quoted above came from a run of this query, which searches all indexed sites for C++ source code that contains the word "TClientDataSet". The text is slightly inaccurate: although the total processing time was indeed 375ms, there are other valid methods of counting the other times.

The "server/network" time represents the time it took to send the query to Lucene, get the results from the web service, and convert them to classes and records GetPublished can process. Over 95% of that time is used for transferring the results over the network. The rest is taken by the actual search engine on the Lucene server and the result processing code on the server running GetPublished.

Almost everything else GetPublished does with the results involves the database, so we say the rest of the time belongs to "database". However, for large result sets the Lucene engine processing time - and certainly network transfer time - will be longer. GetPublished actually uses that time to execute additional queries, by running the code in multiple threads.

Here’s the actual processing log from GetPublished for the same query:

Search expression started
Getting list of sites to include in the search
Search includes one or more GetPublished sites
Retrieving external sites
Search includes one or more external sites
Building Lucene query
Lucene query: +appid:(gp blogs blogsteamb cc qc) AND (cpp.source:(+TClientDataSet))
Search sites: 1,5,7,9,10,11,12
Search thread starting
Retrieving language ID
Retrieving site names
Retrieving visible version IDs
Retrieving staged visible version IDs
Retrieving welcome content types for welcome page queries
Welcome content filter:  IN (26,314,322)
Query completed in 31.25ms
The web service returned in 31.25ms
The search engine ran the query in 0ms
Total number of results: 59
Sorting results by AppID and version ID
Adding information for live versions in search results
Adding information for staged versions in search results
Removing versions that are not visible to the user
Updated number of items in search results: 59
Sorting results for welcome page processing
Query ran before retrieving live welcome versions - retrieving now
Live welcome versions:
Language ID: 1
Country ID: 239
Removing welcome pages that are not visible to the user
Final number of items in search results: 59
Parsing dates for sorting
Sorting results
Creating result list
Updating site names for visible results
Creating article headers for display and loading additional information
Search expression processing completed in 375ms

As you can see, GetPublished does a lot more than just run the search query. The reason it does so is that it needs to convert the search results - a list of version records - to a list of articles the user can see. Here are some of the things that affect the visibility of articles and versions:

1. Articles can have multiple versions, but only one version per article can be "live" (that is, visible to users).
2. Articles can be mapped to multiple sites, and have different publishing and expiration dates on each site.
3. GetPublished supports "staging sites", that use a different set of versions.
4. Articles are filtered based on the user’s preferred language.
5. Certain articles may only be visible in specific countries or regions.
6. Articles of a special type, known as a "welcome page", are shown on specific site areas instead of in article lists. On such pages, only one "welcome page" can be visible.

The list of results returned by the search web service is trimmed and expanded based on the search criteria, user preferences, and visibility settings:

1. Versions that are not visible to the user are removed from the list.
2. If an article is mapped to multiple sites that are included in the search, additional result records are created for each site.
3. Welcome pages that are mapped to multiple area are stored once per site, but all valid links are stored in the result record to be displayed later.
4. Of multiple welcome pages mapped to a single area, only the one visible by the user is kept.

Many of these checks can run concurrently. For example, if the search engine takes a while to process the query, GetPublished retrieves all visible articles and welcome pages from the database. If the engine returns quickly, GetPublished only checks the database for versions that are included in the search results. Similarly, GetPublished tries to reduce the working result set as much as possible. For example, when sorting by site name, GetPublished has to set the site name of every result before sorting and paging. When sorting by other fields, GetPublished waits until the results are sorted and only sets the site name for results that are going to be displayed.

Share This | Email this page to a friend

class function TStatistics<T>.Average(
  const AData: TEnumerable<T>;
  AAdder: TBinaryOp<T>;
  ADivider: TBinaryOp<T>;
  AExplicitCast: TFunc<integer, T>): T;
var
  Total, Num: T;
begin
  Total := Sum(AData, AAdder, AExplicitCast);
  Num := Count(AData, AAdder, AExplicitCast);
  Result := ADivider(Total, Num);
end;

class function TStatistics<T>.StandardDeviation(
  const AData: TEnumerable<T>;
  ADeviation, AAdder, ADivider:TBinaryOp<T>;
  ARoot, ASquare: TUnaryOp<T>;
  AExplicitCast: TFunc<integer, T>): T;
var
  Avg, Variance: T;
  SquaredDeviations: TEnumerable<T>;
begin
  Avg := Average(AData, AAdder, ADivider, AExplicitCast);
  SquaredDeviations := Map(
    function(AValue: T): T
    begin
      Result := ASquare(ADeviation(AValue, Avg));
    end,
    AData);
  try
    Variance := Average(SquaredDeviations, AAdder, ADivider, AExplicitCast);
    Result := ARoot(Variance);
  finally
    SquaredDeviations.Free;
  end;
end;

You can download the complete project from CodeCentral.

Even having to use functions like "AAdder" in place of the more conventional "+", I think the algorithm is still fairly easy to read here, at least if you understand the standard deviation.  As Raymond points out in comments to the previous post, however, the syntax may not be familiar to see folks who have spent most of their time in older versions of Delphi.

I’m afraid you’re just going to have to get used to it.  Delphi is well behind the pack in getting support for anonymous methods, and in many environments it is difficult to get much done without them.  JavaScript comes to mind; the asynchronous nature of much of what you have to do in JavaScript makes a continuation-passing style quite practical.  Lambda expressions, which are, very roughly, a more concise version of an anonymous function, are required to do any useful work in LINQ.  In languages like Lisp and Haskell, all "lines" of code are (again, very roughly) functions, which are anonymous by default. Few mainstream languages don’t support this, and many environments leverage it heavily. If you don’t understand such syntax well, you will find it hard to work outside of Delphi, like a COBOL programmer who doesn’t understand OO. You aren’t required to like it, but you have to understand it.

Share This | Email this page to a friend

1. GetPublished indexes the content by calling the search web service.
2. GetPublished stores all data in the database.

The problem is that since we’re updating multiple data stores (the Lucene index and GetPublished’s database), we have no way of controlling the entire process as a single transaction. Writing a distributed transaction manager and extending both GetPublished and Lucene to use it wasn’t really an option, but we needed a way to make sure the database and the Lucene index matched.

When faced with complex design decisions, it help to analyze the risks involved. Here’s my initial risk assessment. It estimates the risk of receiving incorrect search results for index-only and database-only failures (if both operations succeed or fail, the database and index match, and we have no problem).

The risks are based on the following assumptions:

1. Only content in the database is "real" - this is what users see.
2. GetPublished rarely modifies existing content - most edits generate new versions.
3. All search results have to be filtered for visibility by GetPublished.

Based on these assumptions, we can determine that there’s generally little risk in index failures. That risk can be further mitigated by retrying to index later. On the other hand, database-only failures are usually a high risk, so we’d better find a way to avoid them. I therefore based the design on the following requirements:

1. If we were unable to commit changes to the database, we must not update the index.
2. If we were unable to update the index, we should retry later.

The first part is easy: all we have to do is make sure all processing is wrapped in a database transaction. Only if the transaction is successfully committed, can we index the content. By only reading committed data and running the indexing code outside the content processing transaction we can make sure we’re only indexing successfully committed data.

The second part is the real problem. Once data is committed, we have to try to index it. But what if we can’t? We can’t keep trying indefinitely - we need to respond to user requests. So, we need to run the indexing request in another thread, one that can keep trying while we return control to the user.

Background threads are a particular problem in web applications. Web applications usually only live for the duration of a single request. The web server software (IIS, in GetPublished’s case) can - and will - terminate the process, including background thread, at any time. Additional complications arise from GetPublished’s distributed architecture and ASP.NET’s application model. GetPublished is designed to run on multiple servers concurrently (web farm). ASP.NET applications run in application pools, which may be recycled (manually by administrators, or automatically by the server or external monitoring tools), terminating all running threads.

GetPublished solves this problem by implementing a system of background jobs. Instead of arbitrary threads, jobs are special classes that can be tracked and monitored by GetPublished. Since the application runs on multiple servers, and can be restarted at any time, jobs are stored in the database. When GetPublished starts, it creates a job monitoring thread, whose job is to periodically check the database and start job threads as necessary:

Requests that require processing that may take longer than a normal web request can use background jobs. Instead of spawning worker threads, requests can create job records in the database. The job monitoring thread will then pick up the request and spawn a worker thread next time it checks the database. GetPublished even lets administrators monitor, stop, and restart running jobs:

Using background jobs, we can now change the article submission process:

The indexing job is created as part of the same transaction that stores the content. This means the job will only run if the data has been successfully committed. The job calls the web service to index the content, and can safely retry the operation if necessary without blocking the user.

So far, we’ve covered indexing. That’s only half the job of a search engine. Next time, I’ll describe the actual search.

Share This | Email this page to a friend

The previous search engine was based on keywords rather the full-text, and had several limitations:

• The keyword parser did not correctly handle Unicode text, particularly east-Asian languages.
• Lack of a full-text index prevented phrase and proximity searches, and did not allow correct scoring of search results.
• The use of multiple databases by CDN applications prevented unified searches across all web sites.
• It was slow.

Obviously, the engine needed to be replaced. We’ve looked at several search engines in the past, but didn’t find one that matched our needs. We started rewriting our parser, but decided to take another look at the latest version of Lucene - and were pleasantly surprised. Lucene seemed more than capable of handling our needs, and since it is open source, we knew we could tweak it if necessary.

The first problem we needed to solve was how to integrate the Lucene index into our applications. CDN applications are written in several languages (Delphi, Java, C#, and PHP), run on multiple platforms (Native Windows, ASP.NET, and Linux), and use several databases (InterBase, Blackfish SQL, Oracle, and Microsoft SQL Server). In addition, most CDN applications run on multiple load-balanced application servers.

One solution would have been to let Lucene access our databases directly. This would have involved setting up special tables that match the index structure, and maintaining application-specific information on the indexing server. For multiple applications and databases, this can become a serious headache. Instead, we wrapped the search engine in a web service. Each application already controls its content, and notifies the search engine of content changes - indexing new content, re-indexing updated content, and removing deleted content:

Next, we had to decide what constitutes a "document" in the index. A document is a single entry, identified by a unique ID, that can be return as a search result. A single document can have multiple fields, but is included no more than once in search results. Each CDN application has a different concept of a document, which may or may not correspond to what users may consider a single piece of content. Here’s what we came up with:

• For blogs, a single blog post is a document.
• For CodeCentral, both a complete submission and a single source code file within a submission are considered documents. They are indexed using different IDs, so we can search for submissions, source code, or both.
• For GetPublished, a single version of an article is considered a document. GetPublished articles can have multiple versions, and GetPublished uses a complex set of rules to determine actual content visibility on its sites. Instead of indexing all possible visibility combinations, we index each version once, and let GetPublished convert search results into a set of articles visible to the user.
• For QualityCentral, a single report is a document.

GetPublished uses DocAdapter to process submitted files and convert them into HTML articles. Among other things, DocAdapter extracts source code snippets from the submitted document and uses YAPP to automatically syntax-highlight them. Since DocAdapter already knew how to extract source code from an article, it was fairly simple to extend the code to return the original snippets to GetPublished, so they could be indexed by Lucene.

Here is what happens when a user submits an article to GetPublished:

Roughly, the steps are:

1. GetPublished checks the submitted files and form fields and generates the necessary data for the article (for example, a unique article ID for a new article).
2. GetPublished then sends the content to DocAdapter for processing.
3. DocAdapter converts the content to HTML, and extracts all code snippets.
4. Each code snippet is stored, then sent to YAPP for syntax highlighting.
5. DocAdapter merges the syntax-highlighted snippets into the final HMTL.
6. DocAdapter returns the merged HTML, all source code snippets, and any additional required information to GetPublished.
7. GetPublished indexes the content by calling the search web service.
8. GetPublished stores all data in the database.

You’ll notice I painted the line from GetPublished to the web service red. This is because there’s a problem here: the process I just describes only works when there’s no error. If either step 7 (indexing) or step 8 (data storage) fails, we’re left with inconsistent data.

One possible solution would be to switch steps 7 and 8. After we store the data (and commit the transaction) successfully, we can safely call the web service, knowing we’re indexing valid content. This still doesn’t solve the problem of index failure: if the web service call then fails, we’re left with new content that’s not indexed.

Another option is to roll back the entire transaction if step 7 fails. This works in case of an indexing error, but doesn’t help us if indexing succeeded but the database commit failed. Once again, the database and index won’t match.

Since we don’t have distributed transactions with the Lucene index, what we need is a way to tie an indexing request to a successful commit, and the ability to ensure the indexing request succeeds - or at least, notify an administrator if there’s a problem.

In my next post, I’ll describe how GetPublished accomplishes this task.

Share This | Email this page to a friend

This post is the fourth in my series on building a statistics library using Delphi 2009’s new generic types.  If you’re new to the series, you might want to start with the first post.  Today I’m going to discuss the second higher-order function that the library uses internally, Map.

Map is a function which takes a list, and a function which operates on individual items in the list, and returns a new list, formed by executing the function against each entry in the original list.  For example, suppose I had this list of integers:

1, 2, 3, 4, 5

Now let’s say that I call Map, passing this list, and the function Inc(). The result would be this list:

2, 3, 4, 5, 6

Don’t confuse Map with functions like jQuery’s each which merely iterate the list and call a passed function without returning a new list.  That’s a different kind of function.

To calculate the standard deviation of a list, I first need to create a list of the squares of the deviations of each entry in the list. Later, I will perform additional calculations to compute the standard deviation, but first I need this list.  Here’s how I do it, using Map:

  SquaredDeviations := Map(function(AValue: T): T
    begin
      Result := ASquare(ADeviation(AValue, Avg));
    end,
    AData);
    // [...]

The anonymous function I pass as an argument to Map computes the deviation of the individual item it is passed, squares it, and returns a value.  This anonymous function is called once for each item in the original list. And here is the implementation of Map itself:

class function TStatistics<T>.Map(
  AFunc: TUnaryOp<T>;
  const AData: TEnumerable<T>): TEnumerable<T>;
var
  Current: T;
  NewList: TList<T>;
begin
  NewList := TList<T>.Create;
  for Current in AData do begin
    NewList.Add(AFunc(Current));
  end;
  Result := NewList;
end;

Note that I have Map returning a new instance.  It is behaving as a constructor of sorts.  Indeed, it might make sense to have a constructor of this style on a list type. You could also write a version of Map which accepted an entity list to use as the result if it makes your lifetime management easier.

Share This | Email this page to a friend

to this:

Code-folding is switched on by default, and there appears to be no way to turn it off permanently.  For those (like me) that never use it, this can be annoying, especially when you click the node to collapse code when you wanted to click elsewhere in the gutter, or you just want to have a few extra pixels of space in your editor.

The hot-key sequence for turning off code-folding is Ctrl-Shift-K-O (KO.. knock-out.. stands to reason) . Unfortunately this doesn’t turn it off permanently as it is not saved between sessions. Fortunately, the setting *is* saved in desktop settings, so if you turn off code-folding and then save the desktop (View|Desktops|Save desktop…) the setting will persist for that desktop. That means you will need to turn it off in each desktop you want it saved to, and save that desktop, too.

Thanks go to Alexander Tereshchenko for the suggestion, which he made in CodeGear’s newsgroups.

Share This | Email this page to a friend

Computing the Average or Standard Deviation of a set of numbers is a fairly trivial task.  For smaller sets, you can do it in your head.  It certainly does not require advanced programming techniques to do in code.  But recall that my purpose in writing this series was to answer commentor Raymond’s request for "something like MapReduce."  So when you read this post and wonder why I’ve chosen such a roundabout method of doing some simple sums, keep this purpose in mind.  The point is to learn about generic list operations, not to learn how to compute an average.  If you need help computing an average, you probably won’t understand the rest of this post.

I chose statistical functions as a sample problem because it is so easy to express a statistical function in terms of operations across lists, and operations across lists are what mapping functions do well.  In this post, I am going to discuss two list operations, Fold and Map, which will be useful in implementing the Average and StandardDeviation functions. Then I’ll go into some detail about what Fold does and how I use it to compute the sum and count of list elements. I’ll discuss Map further in the next post in this series.

Both Fold and Map are "higher order functions," which simply means that they take a function as one of their arguments.  Both Fold and Map transform a list, but they do it in different ways.  Fold applies a function to pairs of entries in a list, carrying an aggregated value as it works, whereas Map generates a new list by applying a function to individual entries in a list, and creating a new list from the results of the function.

In my implementation of the average and standard deviation functions, I will use Fold to calculate the sum and count of entries in a list, and Map to create a new list containing the squared deviations of entries in the original list.

Anyone who has ever balanced a checkbook can intuitively understand what Fold does.  Yet, people often find the function confusing, because of differences in how different versions of the function operate.  So I’m going to examine it in some detail.

Fold is a function which can only be used on ordered lists such as arrays and TList. Note that when I say "ordered" here I don’t mean alphabetical or numeric order, only that each item in the list has a defined position.  In other words, something unlike a (mathematical) set. Fold takes three arguments: The list of values, a function which takes two values as arguments and returns a single value, and an "initial" value.  The Fold traverses the list, performing an operation on each item in the list, and also passing to this operation the result of the previous operation.

Since the fold function internally works on pairs of values, and since it does the same operation on each item in the list, there is also a need for an "initial" value.  Otherwise, we would not have a second argument for the passed function when we evaluated the first (or at last, depending on implementation) entry in the list. This is why I need the "mapping" function I described in my first post in this series.  The function allows me to express an "initial" value in terms of the type used as the type parameter.  However, as I’ve developed this series, I’ve decided to call the function an "explicit cast" instead of a "mapping" function.  Explicit is a Delphi operator which performs exactly the task I’m trying to do.  Using this name is both to avoid confusion with the unrelated Map function I’ll describe later, and for consistency with the notion of passing functions as an alternative to "real" operator constraints.

I will use Fold to calculate the sum of the entries in the list like this:

class function TStatistics<T>.Sum(
  const AData: TEnumerable<T>;
  AAdder: TBinaryOp<T>;
  AExplicitCast: TFunc<integer, T>): T;
var
  Init: T;
begin
  Init := AExplicitCast(0);
  Result := FoldL(AAdder, AData, Init);
end;

FoldL will execute like this: Start with the initial value.  Execute the passed function (in this case, addition), passing the initial value and the first item in the list.  Execute the function again, passing the result of the first execution and the second item in the list.  Execute the function again, passing the results of the second execution and the third item in the list.  Continue in this way until we are out of items.  Since the "initial" value I pass is zero, the result will be the sum of the values in the list.

By modifying the AAdder function slightly, I can calculate a count of the items in the list rather than a sum.  How can I modify a function passed as an argument?  By wrapping it in an anonymous method:

class function TStatistics<T>.Count(
  const AData: TEnumerable<T>;
  AAdder: TBinaryOp<T>;
  AExplicitCast: TFunc<integer, T>): T;
var
  Init: T;
begin
  Init := AExplicitCast(0);
  Result := FoldL(
    function(ALeft, ARight: T): T
    begin
      Result := AAdder(ALeft, AExplicitCast(1));
    end,
    AData,
    Init);
end;

So Count works almost exactly like Sum, except that I alter the passed AAdder function such that it ignores its second argument and always adds 1 to the running total. (Why couldn’t I just use the Count property of the list? TEnumerable<T> doesn’t have one.)

You might have noticed that I called my Fold function FoldL instead of just Fold.  This is because there are two variants of Fold: A left fold and a right fold. Despite the names, both variants process entries in the list in the same order, from start to finish.  The "left" and "right" variants differ in terms of where the "initial" value is used.  If we write down the entries in the list from left to right, the left fold variant positions the initial value on the far left-hand side of the list, and the right fold variant positions the value on the far right-hand side of the list.  In a recursive implementation of fold, the left and right variants also differ in terms of the point at which recursion occurs.  If the compiler does a tail recursion optimization, this results in a substantial performance benefit for the right fold variant.  But in a looping implementation, like the one I’m going to demonstrate, performance should be identical in both variants.

With a commutative function, like addition, the result will also be identical in both variants. So for my Count and Sum functions, I could have used either FoldL or FoldR. With a noncommutative operation such as subtraction, FoldL and FoldR will obviously give different results.  The following diagrams from Wikipedia illustrate the two functions well.

My implementation of FoldL is quite simple.  Note that this is a very limited FoldL; in keeping with my desire to not make this series overly long I’ve restricted this FoldL to only be able to return T. A more general FoldL would allow an arbitrary return type.

class function TStatistics<T>.FoldL(AFunc: TBinaryOp<T>;
  const AData: TEnumerable<T>; const AInit: T): T;
var
  Current, Previous: T;
begin
  Previous := AInit;
  for Current in AData do begin
    Previous := AFunc(Previous, Current);
  end;
  Result := Previous;
end; 

In my next post, I’ll discuss Map.

Share This | Email this page to a friend

So I added a new test project to my project group, and then I added a new test case to the test project.  The test case wizard got confused by the class methods, so I just wrote the tests manually.  They’re quite simple:

uses
  TestFramework, Classes, Unit7, Generics.Collections, SysUtils;

type
  TestTIntStatistics = class(TTestCase)
  published
    procedure TestAverage;
    procedure TestStandardDeviation;
  end;

implementation

procedure TestTIntStatistics.TestAverage;
var
  ReturnValue: Integer;
  AData: TList<integer>;
begin
  AData := TList<integer>.Create;
  try
    AData.Add(2);
    AData.Add(4);
    AData.Add(6);

    ReturnValue := TIntStatistics.Average(AData);

    CheckEquals(4, ReturnValue);
  finally
    AData.Free;
  end;
end;

procedure TestTIntStatistics.TestStandardDeviation;
var
  ReturnValue: Integer;
  AData: TList<integer>;
begin
  AData := TList<integer>.Create;
  try
    AData.Add(2);
    AData.Add(4);
    AData.Add(6);

    ReturnValue := TIntStatistics.StandardDeviation(AData);

    CheckEquals(1, ReturnValue);
  finally
    AData.Free;
  end;
end;

I have just created a small list with values for which it is easy to calculate the average and (integer) standard deviation in my head, and checked that the values returned by my functions correspond to the values I calculated myself. That’s not a rigorous test, but it’s enough to allow me to debug through my code and check for obvious failures.

Of course, I haven’t actually implemented the functions yet, so the tests fail:

With a functioning unit test, however, I can start implementing the library.  In the next post, I’ll start to discuss some of the higher order functions the library will use internally.

Share This | Email this page to a friend

You can do a lot with Delphi 2009’s generic types, but one thing that you can’t do is specify an "operator constraint." This means that I cannot perform operations like +, -, implicit type conversions, etc., on a type passed as a type parameter. In my last post on this subject, I suggested one possible solution, and experimented enough to show that it does work.  But, as I noted in the post, I suspected it might not be the best way. In particular, I didn’t like the fact that my previous approach used virtual methods, and it required creating a new "adder" type for each value type you wanted to use as a type parameter to the generic type.  That’s just too much work.

In the comments to another post on the subject of Delphi 2009 generics, Raymond asked for an implementation of MapReduce.  I thought about how I might demonstrate that in the context of generics, and decided that implementing the higher order functions Fold and Map would be a slightly better demonstration than MapReduce.  But since higher order functions can be a pretty abstract concept, I wanted to show an example of how you might use them, so I will use these functions to build a library that does some simple statistical operations, namely, computing the average and the standard deviation of a list of numbers.

By using generics, I can write the algorithms for average and standard deviation once and reuse them for any type which supports certain primitive operations, like addition and taking the square root.

I’m going to cover a lot of ground in this demo, so I’ll be breaking it down into several posts.  In today’s post, I’m going to examine how data will be supplied to the generic statistical routines.

Most statistical functions take a list of numbers as input and supply one or more numbers as output.  For example, the arithmetic mean, or average, function takes a list of numbers and returns a single number.  A function which returns the mode or modes of a list would take as input a list of numbers and return a different list, which might have one entry, or many.

So right away, I have a problem: I’d like to take a list of numbers as an invalid argument to a function, but I don’t know what type the numbers in the list will be, never mind the type of the list.  Ideally, I would be able to write something like this:

function Average<A, R>(AData: IEnumerable<A>): R;

This declaration should mean that the function Average accepts any list of values of type A which can be enumerated in a for…in loop and returns a value of type R. However, there are a few roadblocks in the Delphi 2009 RTL which make this impossible.

While the Delphi 2009 RTL does define an IEnumerable<T> interface type, neither TList<T> nor its abstract parent type TEnumerable<T> implement this interface.  If a trivial filesystem search can be believed, nothing else does, either. I’ve tried, unsuccessfully, to implement it myself; that’s one of many things that I haven’t figured out how to do in Delphi 2009 yet, and is perhaps the subject for another post.

My wild guess is that the most common type users of my statistics library will want to pass as the argument AData will be TList<A>. So I have to support that.  But I’d like to support other types of lists, as well.  It seems to me that the best I can do today is to specify TEnumerable<T> as the list argument type.  Then, at least, a user of the library can use other subtypes of TEnumerable<T>, such as TStack<T>, TQueue<T>, etc.

So my function declaration now looks like this:

function Average<A, R>(AData: TEnumerable<A>): R;

This, unfortunately, means that the user of the library cannot supply input data in the form of an array, although it’s trivial to write a class which exposes array data in the form of a TEnumerable<T> (using the facade pattern), so this isn’t a huge loss.

In order to make the code I’m going to show simpler, I’ll use the same type argument for the input and output.  In other words, if the function is passed a list of integers, it will return the average as an integer.  If it’s passed a list of doubles, it will return the average as a double.  This is probably not ideal for a general-purpose statistical library, but, for the purposes of this demo, it makes the code quite a bit easier to understand.

That makes the function prototype look like this:

function Average<T>(AData: TEnumerable<T>): T;

However, since I have no way of specifying an "operator constraint" on T, and because specifying an interface constraint on T would prevent using my functions with primitive types, at least in Delphi 2009, and because I suspect that primitive types are the most common use case for a statistical library, I have to tell the function how to perform the mathematical operations it needs to do its work.  In order to compute an average, I need to be able to add two values and divide two values.  For reasons that I’ll cover in a future post, it will also be useful if I can map an integer value into the type of the type argument, so I’m going to require a function for that, as well.

Here’s the final version of the function’s interface:

type
  TBinaryOp<T> = reference to function(ALeft, ARight: T): T

  TStatistics<T> = class
    public
      class function Average(const AData: TEnumerable<T>;
                             AAdder, ADivider: TBinaryOp<T>;
                             AMapper: TFunc<integer, T>): T; overload;

Calling methods with long lists of arguments can be kind of annoying, so I’ve marked a function as overloadable.  This allows me to subtype the class if I want to, implementing the primitive operations, and introducing an overloaded call to Average that passes those implementations, like this:

  TIntStatistics = class(TStatistics<integer>)
  private
    class function Add(ALeft, ARight: integer): integer;
    class function Divide(ALeft, ARight: integer): integer;
    class function Mapper(AValue: integer): integer;
  public
    class function Average(const AData: TEnumerable<integer>): integer; overload;
  end;

That gives me much closer to the "ideal" function prototype I designed above, but requires a new subtype to be implemented.  The nice thing about this current approach is that you can pick whichever solution you like: Implement a subtype if you want a simpler call to Average, or just pass the appropriate functions if you’d like to use a type parameter for which you don’t have a subtype available.

Since I’ve covered quite a bit of material just on the subject of the interface for one function, I’m going to take a break for today.  Stay tuned for part 2!

Share This | Email this page to a friend

unit Unit5;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TAdder<T> = class
  public
    function AddEm(A, B: T): T; virtual; abstract;
  end;

  TIntAdder = class(TAdder<integer>)
  public
    function AddEm(A, B: integer): integer; override;
  end;

  TStringAdder = class(TAdder<string>)
  public
    function AddEm(A, B: string): string; override;
  end;

  TMath<T; A: TAdder<T>, constructor> = class
  public
     function AddTwoDigits(Left, Right: T): T;
  end;

  TForm5 = class(TForm)
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  end;

var
  Form5: TForm5;

implementation

{$R *.dfm}

procedure TForm5.Button1Click(Sender: TObject);
var
  AddInt: TMath<integer, TIntAdder>;
  AddString: TMath<string, TStringAdder>;
begin
  AddInt := TMath<integer, TIntAdder>.Create;
  try
    ShowMessage(IntToStr(AddInt.AddTwoDigits(2, 2)));
  finally
    AddInt.Free;
  end;
  AddString := TMath<string, TStringAdder>.Create;
  try
    ShowMessage(AddString.AddTwoDigits('2', '2'));
  finally
    AddString.Free;
  end;
end;

{ TIntAdder }

function TIntAdder.AddEm(A, B: integer): integer;
begin
  Result := A + B;
end;

{ TStringAdder }

function TStringAdder.AddEm(A, B: string): string;
begin
  Result := IntToStr(StrToInt(A) + StrToInt(B));
end;

{ TMath<T, A> }

function TMath<T, A>.AddTwoDigits(Left, Right: T): T;
var
  Add: A;
begin
  Add := A.Create;
  try
    Result := Add.AddEm(Left, Right);
  finally
    Add.Free;
  end;
end;

end.

Share This | Email this page to a friend

I want to solve problem three of Project Euler. Project Euler is a web site which poses a series of programming problems intended to teach you mathematical concepts.  Here is problem three:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

In order to compute prime factors, it helps to have a method to return a list of primes.  A very simple algorithm to do this is called the Sieve of Eratosthenes. If you don’t already know this algorithm well enough to implement it yourself, then please read the Wikipedia article I just linked before continuing.  The rest of this post will make very little sense unless you understand the Sieve.

I’m going to make a minor change to the algorithm described in the article. In that version, you begin by "writing a list of numbers from 2 to the largest number, say n, you want to test for primality." That won’t work for me, since I don’t know the largest number I need to test for primality.  I could guess, but I might be wrong, and, in any event, it seems inelegant.

So I’m going to take a different approach.  Whenever I have a need for a sequence of something, say, prime numbers, I think of enumerations.  It’s common to see enumerations over a fixed list, like strings in a TStringList, but they work just as well for infinite lists.  So I’m going to write an enumerator which returns prime numbers in ascending order.

The basic outline of the algorithm is this:

1. Start with the lowest prime number.
2. Increment the current prime number.
3. Test it with a function which returns false if any of the previous prime numbers are factors of the number tested, true otherwise.
4. Repeat steps 2 and 3 until a new prime is found.

Obviously, the heart of the algorithm is the function in step 3. To solve this problem without anonymous methods, I would need to maintain a list of the primes returned previously, and test each one in sequence.  That would work fine, but I am going to demonstrate a different approach.

Since I happen to know that 2 is prime, I’m going to start with a function which returns true.  So in step 1 I’ll begin with 1, not a prime number, but the "uninitialized" start of the enumeration.  Note that the value 1 will never be returned by the enumeration. In step 2, I’ll increment it to 2.  In step 3, I’ll test it with my function, which, at this point, returns the constant true.  So far, so good, since 2 is prime.

Now I need to change the function to one which excludes products of 2, the first returned prime.  That way, when we get to 4, it will be rejected by the function. In order to do this, I’m going to dynamically create a new function and substitute it for the original function which always returned true.

OK, enough chat.  Let’s look at some code.  First, here is the interface for the enumerator:

  TPrimeNumberEnumerator = class
  private
    FCurrent: integer;
    FIsPrime: TPredicate<integer>;
    function MakeFilter(CurrentPredicate: TPredicate<integer>; CurrentPrime: integer): TPredicate<integer>;
  public
    constructor Create;
    function GetCurrent: Integer;
    function MoveNext: boolean;
    procedure Reset;
    property Current: integer read GetCurrent;
  end;

The public portion of the interface is just an implementation of the enumerator pattern in Delphi, plus the constructor, which simply calls Reset.  FCurrent will hold the last prime number returned, or 1 if no primes have been returned yet. FIsPrime is a reference to a function which returns false if any of the previously returned returned primes are even factors of the integer argument passed, and true otherwise.  TPredicate<integer> means a function which returns a Boolean with a single, integer argument. GetCurrent just returns FCurrent. First, let’s look at Reset, which gets everything ready.

procedure TPrimeNumberEnumerator.Reset;
begin
  FCurrent := 1;
  FIsPrime := function(AValue: integer): boolean
  begin
    Result := True;
  end;
end;

FCurrent is initialized to the value below the first value returned, as with many enumerator implementations. FIsPrime, at this point, ignores its argument, and simply returns true.  I used an anonymous function here for consistency with the rest of the code, but a non-anonymous function could have been used in this part. Again, since I know that 3 is prime, this trivial function is good enough for this specific case, although we’ll need something better soon!

The heart of the enumerator is in MoveNext and MakeFilter. Here’s MoveNext:

function TPrimeNumberEnumerator.MoveNext: boolean;
begin
  Inc(FCurrent);
  while not FIsPrime(FCurrent) do Inc(FCurrent);
  FIsPrime := MakeFilter(FIsPrime, FCurrent);
  Result := true;
end;

That’s just the algorithm I described above.  Increment FCurrent, then test this value for primality.  Keep incrementing until we find a new prime. Return True, since there’s always another prime.

Importantly, however, when a prime is found I modify the predicate FIsPrime in such a way that it excludes products of this prime.  That’s the Sieve of Eratosthenes. Let’s look at how this is done:

function TPrimeNumberEnumerator.MakeFilter(
  CurrentPredicate: TPredicate<integer>;
  CurrentPrime: integer): TPredicate<integer>;
begin
  Result := function(AValue: integer): boolean
  begin
    Result := CurrentPredicate(AValue) and ((AValue mod CurrentPrime) <> 0);
  end;
end;

MakeFilter takes the function it was passed plus a new prime number and returns a new function, which returns false if the passed function, CurrentPredicate, returns false or the integer argument, AValue, can be evenly divided by the prime number passed to MakeFilter.  The new function returns true, otherwise. Note that the function is "capturing" both the original function, CurrentPredicate, and CurrentPrime, both of which are arguments to MakeFilter, but not to the function returned.

Since I always pass FIsPrime as the CurrentPredicate argument, each time I call MakeFilter I’m enhancing FIsPrime to exclude more non-prime numbers.

In effect, I’m creating a new function which has only one argument, AValue, but incorporates two additional arguments, CurrentPredicate and CurrentPrime.  The difference is that CurrentPredicate and CurrentPrime are captured from the creating method and hence fixed at the time the function is created, whereas AValue will be specified at the time the function is executed.  This is a technique called currying, and it’s quite common in functional programming.  You cannot do currying in the general sense without anonymous methods or lambda expressions.  So this is a new programming technique available in Delphi 2009.

Having done all this, I need to be able to get an instance of my enumerator:

  TPrimes = class
  public
    function GetEnumerator: TPrimeNumberEnumerator;
  end;

And now I can solve the original problem:

procedure TForm4.btnGoClick(Sender: TObject);
var
  Current: integer;
  Primes: TPrimes;
  Composite: Int64;
begin
  Composite := 600851475143;
  lboResults.Items.Clear;
  Primes := TPrimes.Create;
  try
    for Current in Primes do begin
      if Composite mod Current = 0 then begin
        Composite := Composite div Current;
        lboResults.Items.Add(IntToStr(Current));
        if Composite = 1 then break;
      end;
    end;
  finally
    Primes.Free;
  end;
end;

Share This | Email this page to a friend

Share This | Email this page to a friend

Nullable<T>

It’s common to have a reference in code to a value read in from a database.  Of course, most databases allow NULL, whereas many scalar types, like integer, do not. So a programmer can either choose to designate a certain scalar value as a "NULL flag," which can cause problems when that value is actually stored in the database, or to have a separate, Boolean reference indicating whether the other variable should, in fact, be treated as NULL.  Neither solution is great. A better way is to build a single structure which stores both the NULL flag and the scalar value.  This is a more elegant way of storing the value retrieved from the database, but it gets tedious and hard to maintain when you have to create such a structure for many different types.  Using a generic Nullable<T>, however, you can use a single type which can store a reference to any value, whether scalar or not.

Mocks

Generics work really well for mock classes used in unit testing.  Briefly, a mock is an object which appears to be of a certain type, but is, in fact, just an imitation of that type.  You use a mock in a unit test when including the actual object would make the unit test dependent on things which are not practical or advisable to include in a unit test, like a web service.  The mock can pretend to be the web service and return data without actually making an Internet connection.

Mocking is one of those things which is really simple to implement for one specific case, and fairly hard to implement for a general case.  You can fairly easily create a mock for one specific type.  It’s quite a bit harder to create a mocking framework which can imitate any type. But generics help a lot.

In my unit tests for my ASP.NET MVC web applications, I need to mock the HttpContext, since the version included with the .NET framework polls and a whole bunch of stuff related to web applications which I don’t need for the unit test.  So I use the Moq framework and a mocked context which I posted earlier.  In general, to create a mock of a certain type using Moq, you write:

var mockobject = new Mock<TypeToMock>();

After some additional code to specify what values the methods and properties of the "fake" TypeToMock should return, I can then supply the mocked object to some other instance which expects a "real" instance of TypeToMock, and it will be none the wiser:

testInstance.TypeToMockProperty = mockobject.Object;

Now, a full explanation of how to use the Moq framework is outside of the scope of this post; you can read a brief tutorial at the Moq site if you’re interested.  But the important point is that mockobject.Object appears to the outside world to be an instance of TypeToMock, even though it isn’t, and doesn’t carry any of the baggage that the "real" TypeToMock might have.

MVC

Another area where I’ve found generics to be really helpful is when passing a model to a view in an ASP.NET MVC web application.  MVC View pages have a property called ViewData.Model which returns a model instance that was passed by the controller.  By default, this is of type System.Object, which means that you have to cast it to do anything useful with it.  But by using generics, you can get rid of the casts.  Let’s say that the model I want to supply to the view is of type MyModel.  I changed the view declaration from this:

public partial class MyView : ViewPage

…to this:

public partial class MyView : ViewPage<MyModel>

ViewPage<MyModel> is a different type than ViewPage (without the generic type parameter).  MyView is now subclassing a different parent type. In particular, the property ViewData.Model of ViewPage<MyModel> will be of type MyModel instead of type System.Object.  This means that in the code for my View, I can access properties of my model type directly, without any casts, like this:

editLink.HRef = ViewData.Model.EditUrl;

Note that this is not some kind of disguised cast. With a cast, you either sacrifice performance (with a safe/soft cast) or type safety (with an unsafe/hard cast).  With a generic, you don’t make either sacrifice.  Type checking is performed at compile time, just like with a property of a non-generic type.

So When Should I Use Generics?

There are some "code smells" which indicate that you should consider using a generic type.  Whenever you find yourself writing similar code over and over again just to change one or two types (e.g., the type-safe lists that most of us have built in Delphi), or whenever you find yourself casting a reference regularly to the same type, you might want to consider using a generic type instead.

Share This | Email this page to a friend

There is, at the moment, no shipping version of Delphi which includes anonymous methods, so I’m basing my discussion on my experiences using them in other environments.  The final, released version may include a different feature set and what I describe below.

First, let’s answer the obvious question, with the obvious answer: What can I do with an anonymous method which I can’t do without an anonymous method?  Nothing.  In fact, there’s nothing which you can do with Delphi which you cannot do with ASM.  Anonymous methods are a convenience suited to certain styles of programming, like strong, static typing, and object orientation.  They will probably seem useless to people who do not adopt those styles of programming, just as virtual methods will seem useless or dangerous to a non-OO programmer.

I suspect that most "Pascal programmers" view procedures as being a fundamentally different type than other data structures.  In the static typing the world, we typically define the shape of a data structure at compile time, and the contents at runtime.  By contrast, even when passing a procedure as an argument to another procedure, in older versions of Delphi we have had to define both the shape and the contents of the procedure at compile time.  Only the arguments can be set at runtime.

With one exception: Nested procedures.  Let’s talk about that, for a moment.

Nested procedures, scope, and variable capture

Nested procedures are procedures declared inside of another procedure.  This essentially reduces the scope of the nested procedure to being callable within the nesting procedure only: Here is a simple example.

procedure MyClass.Foo;
var
  i: integer;
  procedure Bar;
  begin
    Inc(i);
  end;
begin
  i := 1;
  Bar;
  WriteLn(IntToStr(i));