Passion * Technology * Ruthless Competence

Wednesday, July 30, 2008

Monadic Philosophy Part 2 - The LINQ Monad

If you don't come from a math or philosophy background (and I don't) "monad" sounds like a made-up word. Of course, understanding OO's use of terms like "class" and "object" can be hard to grok at first too. But at least those terms have some grounding in real-world concepts that non-math geeks come across. Because I couldn't draw an analogy of monads to anything at first, it made grasping the concept of monads very hard for me.

It's such a unfamiliar word that the F# team doesn't like it either:

"[W]hen the designers of F# talked with the designers of Haskell about this, they agreed that the word monad is a bit obscure and sounds a little daunting and that using other names might be wise."
[F# Workflows and Haskell Monads, Expert F#, p232]

The F# team thought about calling them workflows, but settled on computation expression. Frankly, I don't like these names much better. Workflow is too easily confused with WF and if the term computation expression is way to generic. Isn't everything in programming a computation expression? I think I'll just stick with monad.

Of course, if there was a short, pithy way of describing a monad, I'm sure that's what we'd call them. It's a kinda complicated idea, so there's no simple two or three word phrase that accurately describes it. "Sequential computation with context flow" is the best I could come up with. It's a crappy description, but here's an elegant example that most .NET programmers are probably already familiar with.

var Orders = new List<Order>()

//code to populate orders omitted
var q = Orders 
    .Where(x => x.OrderDate < DateTime.Now) 
    .OrderBy(x => x.OrderDate) 
    .Select(x => new {ID = x.OrderID, Date = x.OrderDate})

Yes it's true: LINQ is a monad. The two basic concepts about a monad from my description above is that it's a) a sequence of operations and b) there's a context that flows from operation to operation. We see both here in this simple LINQ query. I realize I'm using what looks like a LINQ to SQL query here, but for the sake of argument let's assume that this is all happening in memory.

The query is a sequence of three operations: Where, OrderBy and Select. LINQ has a set of standard query operators that you can mix and match in whatever order you need to. Part of the monad's job is to enforce the sequence of actions. For C#, that's not really a big deal, since it has explicit sequencing already. However, other languages like Haskell use lazy evaluation, meaning there is no explicit order of execution. Many lazy evaluation languages use monads in areas, such as I/O, where order of execution matters.

While C# doesn't need any help to enforce execution order, monads are very useful in the way they flow context between the operations. In the case of LINQ, all the standard query operators take an IEnumerable<T> as their first parameter and return an IEnumerable<T>. Since they have the same inputs and outputs, they can be plugged together in whatever order is required. Yet, you don't see any reference to GetEnumerator or the enumerator objects they return in the LINQ code above. All that code is hidden inside the LINQ query operators so the LINQ developer doesn't have to look at it.

If you squint hard enough, IEnumerable kinda looks like a functional construct. It exposes a single method (GetEnumerator) and can be passed around much the same way functional languages like F# pass around first-order functions. Furthermore, the result of calling GetEnumerator is an IEnumerator object that likewise exposes one main function (MoveNext). In other words, you can think of IEnumerable sort of like a function that returns a function that you call to iterate the collection.

So to sum up, a monad is a sequence of operations in a specific order that automatically flows context from one operation to the next. In the LINQ example, C# has built-in constructs - IEnumerable<T>, foreach and yield return - that makes the monad seem less foreign (which is why I used it as my first example!) However, as we'll see, the concepts of sequence and context flow in a monad still hold even if we're not using built in features of C# to implement them.

Posted By Harry Pierson at 9:53 AM Pacific Daylight Time

Tuesday, July 29, 2008

Monadic Philosophy

(Since I accidentally published part one of this series a few minutes ago, I figured I might as well start publishing the series.)

If you start learning functional programming, eventually you'll come across the idea of a monad. Coming from the object/imperative world of languages like C#, I've had a hard time wrapping my head around this concept. There's no shortage of monad tutorials out there, but most use Haskell's IO as the prototypical example of a monad. Given that I don't know Haskell very well, I found it hard to separate the Haskell stuff from monad stuff. So I set monads on the back burner and decided not to worry about them.

However, all that changed when Stephan Tolksdorf alerted me to his very cool monadic parser combinator library FParsec. I found the FParsec parsers much easier to read my F# parser efforts, so I became very interested in monadic parser combinators. As you might guess, a "monadic parser combinator library" makes heavy use of monads. Time to switch burners.

The problem with learning monads with FParsec is that it's really designed for production use. I needed to break monads down to first principles, so I rolled my own monadic parser library. Make no mistake, if I were looking to build a production parser in F# right now, I'd use with FParsec. My monadic parser library might "get there" eventually, but right now it's a toy.

Over a series of posts, I'm going to describe what I know about monads. I didn't set out to write a tutorial on monads - as I said, there are plenty of them out there. However, I found most of the the many monad tutorials I read lacking because the did a good job explaining the "how", but not such a good job on the "why". Coming from an imperative world, I wanted to understand the philosophy better. That being said, there's a lot of tutorial in and around the philosophy. Hopefully, you'll find both useful.

Posted By Harry Pierson at 5:10 PM Pacific Daylight Time

Pushed the Wrong Button

I'm working on a new series of posts on parser monads, but I accidentally pushed out part thre (I hit "Publish" instead of "New" in WL Writer). I can't stop you from reading it, as it's already in Google and FeedBurner's cache. However, if you want any context at all, do yourself a favor and wait until I publish parts one and two first!

Posted By Harry Pierson at 5:06 PM Pacific Daylight Time

Monday, July 28, 2008

Some Powershell Scripts

By popular demand, I uploaded a bunch of my scripts to my SkyDrive. Included are:

  • Set Powershell Home - this is actually a zip file that contains the profile redirect script. Unzip this in your Documents folder and change the path in Microsoft.PowerShell_profile to where ever you want your profile and home directories to live.
  • _profile - my "real" profile script. Note, the su function requires the Script Elevation PowerToys in order to work. Also, all the various aliases are hard coded to their location on my machine. You'll probably want to change them.
  • prompt - my prompt script
  • prepend-path - a script to add a directory to start of my path
  • append-path - like above, but adds the directory to the end of the path
  • append-path-perm - like append-path, but permanently updates the path in the registry

Enjoy.

Posted By Harry Pierson at 4:26 PM Pacific Daylight Time

DevHawk's Slightly Useful Powershell Configuration

Since folks were interested in my favorite tools, I thought I'd blog how I have PowerShell configured. I'm not an ultra-power user, but I hold my own and hopefully you can use some of this configuration for yourself. Please tell me you're not still using CMD.

First, I use a trick I picked up from Tomas Restrepo to change your home directory and profile script. Here's my Microsoft.PowerShell_profile.ps1 file (in the WindowsPowerShell subdirectory of My Documents)

# reset $HOME and $PROFILE variables
set-variable -name HOME -value "D:\HPierson.Files" -force 
(get-psprovider FileSystem).Home = $HOME 
set-variable -name Profile -Value "$Home\Scripts\_profile.ps1"

# Run the $PROFILE script
. $profile

By default, PS uses the user's personal directory (c:\users\hpierson in my case) as the home directory and the aforementioned filename for the profile script. Personally, I like to keep all "real" data off my boot partition so that I don't have to back it all up when I repave. So my "real" home location is d:\HPierson.Files. The above script sets both the $HOME variable and file system home property to this directory. It also resets the $PROFILE variable to a script in my $home\Scripts folder and runs it.

My $PROFILE script does several things of note:

  • It adds the aforementioned $home\Scripts folder to the path. My utilities folder is a permanent part of the path, put I only add the scripts folder when I'm actually running PS.
  • If I'm running as administrator, I set the background color of the console window to red. I think I picked up this script from Brad Wilson at some point.
  • Set location to home, otherwise when I start PS as admin, it starts in c:\win\sys32.
  • I have a simple prompt script file that displays current folder, the current command number and a list of yellow plus signs indicating how deep I am in the directory stack. To get it to work, I have to remove the standard prompt function, which I do in $PROFILE.
  • I can't ever remember the space between "cd" and "..", so I wrote a simple function called "cd.." that executes "cd ..".
  • I have a su function that leverages the Script Elevation PowerToys. If you pass in a command, it executes it with elevated credentials. If you just execute su, it runs an elevated PowerShell.
  • I use 7-zip for my compression needs, including the 7za command line app. However, PS has issues w/ executing an exe that starts with a number. So I aliased 7za as "zip". UPDATE: Tomas points out that you can prepend an ampersand to force execution, so I could have typed "&7za". I forgot that when I created the alias and am now used to using zip, so I'm not going to change it. But I thought you should know.
  • I have an ever-changing set of aliases, depending on my needs. Currently, I alias "ipy", "cpy", "fsi", "fsc", "devenv" and "chiron" to their fully path-qualified equivalents, so I can run them from anywhere without having to add their respective folders to the path.

I don't set vsvars in the $profile script, but I do have a copy of the one Chris Tavares wrote in my scripts folder, so I can set up a VS environment in a moments' notice.

Also, I put PowerShell on the Vista quick launch bar, so I can bring it up by typing Win-2.

Posted By Harry Pierson at 9:52 AM Pacific Daylight Time
TechEd New Zealand
TechEd Australia

PDC08

patterns & practices
Summit 2008

Change Congress
Recent Bookmarks
Tags .NET Framework (2) ADO.NET (5) Agile (7) AJAX (3) Architecture (284) Guidance (6) Interop (2) Modelling (61) Patterns (7) Process (4) SOA (93) Web Services (5) ASP.NET (22) Battlestar Galactica (3) BI (2) BizTalk (4) Blogging (115) dasBlog (11) Podcasting (4) BPM (1) C# (10) C++ (4) Capitals (5) CardSpace (3) CLR (2) College Football (10) Comedy Central (1) Community (81) Concurrency (6) Consumer Electronics (1) Database (13) Dependency Injection (2) Development (116) C Plus Plus (1) Embedded (5) Lanugages (37) Media (2) P2P (11) Rotor (1) SharePoint (6) SOP (3) DIY (1) DLR (12) Domain Specific Languages (13) Durable Messaging (5) Dynamic Languages (9) Dynamic Silverlight (1) Education (3) Enterprise 2.0 (1) Entertainment (14) ETech (15) F# (50) Functional Programming (17) Game Development (2) Guidance Automation (3) Hardware (8) HawkEye (3) Hockey (29) Home Electronics (1) Home Network (5) Humor (5) IASA (1) Idempotence (3) infrastructure (5) Instrumentation (4) Integration (2) IronPython (24) IronRuby (10) Java (2) Job (3) LINQ (19) Live Mesh (1) Lost (1) Master Data Management (1) Media 2.0 (6) Microsoft (29) MIX06 (2) Mobile Phone (1) Monads (5) Morning Coffee (171) Object Oriented (4) Office (5) Open Source (5) Open Space (2) Operations (3) Other (135) Art (1) Books (1) Family (31) Games (18) General Geekery (26) Home Theater (1) Movies (23) Music (20) Politics (3) Society (1) Sports (37) Working at MSFT (15) Parsing Expression Grammar (16) patterns & practices (2) PDC08 (2) Politics (42) PowerPoint (2) PowerShell (32) Presentation (5) Projects (1) HawkWiki (1) Python (4) Quote of the Day (4) Refactoring (1) Research (2) REST (18) Reuse (5) Robotics (2) Rome (5) Ruby (23) Ruby on Rails (1) Sci-Fi (2) Scripting (4) Security (3) Service Broker (14) SharePoint (2) Silverlight (17) Social Software (1) Software + Services (2) Software Factories (11) Software Industry (1) Spark (1) SQL Server (2) Stephen Colbert (1) TechEd (7) TechEd06 (1) TechRec League (1) Television (6) Travel (6) Unified Client (1) Unit Testing (4) UX (1) Virtual PC (2) Visual Basic (1) Visual Studio (20) Volta (2) Washington Capitals (34) WCF (31) Web 2.0 (65) Web Services (5) WF (21) Windows Live (23) Xbox (1) Xbox 360 (53) XML (7) XNA (14)
Disclaimer: The information in this weblog is provided "AS IS" with no warranties, and confers no rights. This weblog does not represent the thoughts, intentions, plans or strategies of my employer. It is solely my opinion. Inappropriate comments will be deleted at the authors discretion.