tag:blogger.com,1999:blog-154463792024-03-13T06:06:54.084-04:00Meta-Metalet meta x = meta (meta x)Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.comBlogger40125tag:blogger.com,1999:blog-15446379.post-31232076960792578162014-08-17T13:00:00.001-04:002014-08-17T13:00:11.606-04:00Covariant return types in C# and how to not to carefully change a libraryC# doesn't allow covariant return types in interface method implementations. Briefly<br />
<br />
class A { }<br />
class B : A { }<br />
<br />
interface I <br />
{<br />
A M();<br />
}<br />
<br />
class C : I<br />
{<br /> B M() { ... }<br />}<br />
<br />
will not compile. class C's implementation of M must return A. In Java and C++ (with the appropriate syntactic changes) the original code will have worked as written. <br />
<br />
I'm not going to argue strongly one way or the other for the feature of covariant return types in C#, but it's absence illuminated a corner of the pitfalls of evolving a library that don't think I would have noticed otherwise.<br />
<br />
To set the stage I will go through the abstract evolution of a library and a client.<br />
<br />
First the library (or framework really) appeared:<br />
<br />
interface I { ... }<br />
abstract class Base {<br />
I GetI() { ... }<br />
...<br />
}<br />
<br />
Base has various methods intended to be overridden by clients, and its all documented as you would expect.<br />
<br />
Then a client appears<br />
<br />
class Client : Base {<br />
...<br />
}<br />
<br />
The client code works happily. The library evolves some, specificly, GetI changes to return a richer object. In the library:<br />
<br />
interface I2 : I {<br />
...<br />
}<br />
<br />
abstract class Base {<br />
I2 GetI() { ... }<br />}<br />
<br />
The client code continues to work happily, the values returned from GetI still do all the I things they did before, they just happen to do more. After some time the client changes again:<br />
<br />
interface IBase {<br />
I2 GetI();<br />
...<br />
}<br />
<br />
class Client : Base, IBase {<br />
...<br />
}<br />
<br />
Some important things to note. IBase is defined in the _client_ it does not exist in the library, it was not introduced by the library, the client code just extracted it out of some of the methods on Base. This is fine, client code is allowed to create interfaces after all. The other important thing to do note is that the client does implement IBase in the body of the Client class. Rather it simply lets the implementation of Base.GetI serve as the implementation of IBase.GetI. The client has other classes that do not inherit from Base and implement IBase, i.o.w. this was not done just to have some extra code lying around. The client is "borrowing" some of the abstractions of the framework. This was down to allow reuse of the client code in contexts where the framework of the library was not being used. I mention these reasons not to have a debate about the design of the client but merely to emphasize that their was a real reason for this.<br />
<br />
The library now changes again, once again adding more functionality to the object returned from GetI().<br />
<br />
interface I3 : I2 {<br /> ...<br />
}<br />
<br />
class Base {<br />
I3 GetI() { .... }<br />
...<br />}<br />
<br />
This time however, this change actually breaks the compilation of the client. Because the Client class is no longer implementing IBase. IBase was created in the client, the class Client was created in the client, but the client code effectively imposed a responsibility on the library code of implementing IBase, which it no longer does.<br />
<br />
I find this to be fascinating situation. Each individual change on the part of the library was done in a way that was mindful of not breaking consumers. Likewise it is hard to say the client code did anything wrong. Is this a flaw in the language? If so is the flaw simply not supporting covariant return types? Or is it that base classes are allowed to implicitly interfaces? Or is it that the library is actually wrong, that changing the return type of a public method, even if it's a subtype of the previous version of the method? I'm not sure what the correct answer is, but I don't think the answer is as simple as "C# should support covariant return types", because it seems to me this fixes this problem by accident. As far as I can tell the writer of IBase wasn't thinking "C# has covariant return types so library can still evolve GetI and likewise the writer of Base was not thinking "someone may write an interface and use us to implement it by simply inheriting, but that's ok because C# has covariant return types." The writer of Base was certainly thinking in terms of the LSP when they changed the return type of GetI, granted. <br />
<br />
At the end of the day this was fixed by the client simply explicitly implementing IBase.GetI, something like:<br />
<br />
class Client : Base, IBase {<br />
I2 Ibase.GetI() { return GetI(); }<br />
}<br />
<br />
This is unsatisfying for the obvious reasons of the library went out of its way to ensure clients wouldn't have to change, and they ended up having to anyway.<br />
<br />
It is clear that "obey LSP" is not a sufficient principle for determining how to perform backwards compatible library changes. So here are some guidelines about what can and cannot be done in a backwards compatible manner.<br />
<br />
First, there is a minimum of one convention that can't be checked by the compiler unfortunately. That is, the library's namespace is the library's namespace. Many of the suggestions I am going to make rely on that. Fortunately this should not be too onerous on client code, and this is generally accepted as an unwritten rule anyway. I am making it explicit here because the entire impetus for this a seemingly backwards compatible change that actually relied on some fairly intricate unwritten rules.<br />
<br />
I will use the term "member" below to refer to both methods and variables.<br />
<br />
1) Prefer sealed classes. A sealed class can't be inherited from, so you may add new members to it with impunity.<br />
2) In all classes never remove public members. This I hope is obvious.<br />
3) In non-sealed classes never remove protected members. A protected member is effectively public to any sub class.<br />
4) Never change the signature of a public method, even if the changes would satisfy LSP. The preceding explains why sufficiently I hope.<br />
5) The addition of new members in a non-sealed class must be accompanied by the addition of a new type in the library's namespace, to scope them properly. This is because names from the base class are visible in sub classes, and sub classes may have already used those names. Since the names of the members themselves can't be scoped to the namespace, we take advantage of a type. This can be done in two ways:<br />
<br />
Introduce a new subclass:<br />
<br />
class Base { ... }<br />class BaseWithX : Base { MemberType newMember; ... }<br />
<br />
Existing client subclasses will only subclass existing subclasses of Base, and so can continue to use their own newMember if they happen to have a member named that. If they want to take advantage of newMember they have to actively change their code, inheriting from BaseWithX, at which point they will be forced to deal with the ambiguity. If they don't touch their code, this change can't impact them.<br />
<br />
Introduce a new type (probably an enum) that serves purely to separate client overloads from library overloads<br />
<br />
enum GetI3E { Value };<br />
<br />
class Base<br />
{<br />
I2 GetI() { ... }<br />
I3 GetI(GetI3E e) { ... }<br />}<br />
While clients may use a name you want to use for a method in a future release, they can't use a type that's in your library's namespace that doesn't exist yet. This allows the overloading mechanism to avoid you stepping on each other's toes. Note that you cannot reuse these types for different releases, once the client has access to the type they can use it in their own overloads, so new members in new releases must come with their new types. <br />
<br />
If these guidelines are followed it is pretty difficult to break a client inadvertently, and with the exception of (1) it should be possible to follow them for C++ as well (or with an additional written rule that classes with no virtual methods shall not be inherited from). Next time though, GetI is just going to return a sealed class instead of an interface.<br />
<br />
<br />
<br />
<br />
<br />
Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com0tag:blogger.com,1999:blog-15446379.post-53863895868512763622012-12-30T18:19:00.001-05:002012-12-30T18:19:55.001-05:00C++11 (sort of kind of) has path dependent types (ish)Scala has a neat feature called "Path Dependent Types". It's a form of dependent typing that sort of piggy backs on the idea of Java's inner classes. A nice brief little overview is here on Stackoverflow:<br /><br />
<a href="http://stackoverflow.com/questions/2693067/what-is-meant-by-scalas-path-dependent-types">http://stackoverflow.com/questions/2693067/what-is-meant-by-scalas-path-dependent-types</a><br />
<br />
If you're too lazy to read that (which would be disappointing, it's pretty brief), the general idea is that given:<br />
<br />
class A {<br />
class B {<br />
...<br />
}<br />
...<br />
}<br />
<br />
var a1 = new A;<br />
var a2 = new A;<br />
var b1 = a1.new B;<br />
var b2 = a2.new B;<br />
<br />
b1 and b2 actually have different types. This is actually something that would be super useful in C++. Consider perhaps:<br /><br />vector<int> a, b;</int><br />
std::sort(a.begin(), b.end());<br />
<br />
Would it not be nice if that didn't compile? With path dependent types you could make it so!<br />
<br />
I think this feature is, the bee's knees, largely because I once ran into a problem that this functionality would have thwarted (granted there are many other ways of thwarting my particular problem, but PDTs would have given a result closest in spirit and runtime overhead (read: none), to the original interface).<br />
<br />
C++11 gives us many interesting features, none of which are path dependent types. However, some of them in conjunction get us pretty close. One is auto, which works like "var" in my Java pseudocode above (or like val in the Stackoverflow example, which you should really read if you haven't yet), The other is the lambda. Now, I'm not going to be using a lambda as well a lambda. Instead I'm going to be using lambda expressions as a sort of compile-time unutterable type factory. Lambda expressions have the fascinating property that even syntactically identical lambda expressions don't have the same type. This ties into the fact that they cannot appear in an unevaluated expression like decltype or sizeof. What they've done in effect, is snuck a tiny little dependently typed value (in a very loose sense) into the language. We're going to take advantage of this feature (compile time type factory) and leverage lambdas to populate a sort of phantom type variable to mimic path dependent types. It'll probably be easier if I just show you:<br />
<br />
<br />
<script src="https://gist.github.com/4415772.js">This is an embedded gist which won't show up in RSS or with noscript. Look at it <a href="https://gist.github.com/4415772">here</a>.</script>
<p>You see the board class is templated on a template parameter that never appears again, this is our so called phantom type. The "make_board" macro uses a lambda expression to whip up a new lambda expression (and consequently a new type) every time we happen to need one, thus each new board, much like each new lambda expression has a unique type. Likewise, each nested Coordinate type is consequently different, and line 52 of our snippet, were it to be uncommented, would not compile.
<p>I think this is sort of a neat trick. It has various problems when compared to the "real" thing, but given the presence of features like decltype is perhaps less painful that might initially be imagined. I suspect there are probably a whole world of meta-programming and type-system hacks that can be created by taking advantage of the ability of lambda expressions in conjunction with template argument deduction / auto to create new unutterable types.
Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com2tag:blogger.com,1999:blog-15446379.post-28753166606884147242012-03-18T12:47:00.003-04:002012-03-18T12:47:47.343-04:00Conditional Critical Regions: State sidebarI'm going to try and explain this better and justify it in my next post, but here is the State Monad (ala Haskell) in C++11. I have to say, without C++11 this would be even more painful than it already is.<div>
<br /></div>
<div>
<script src="https://gist.github.com/2065956.js?file=gistfile1.cpp">
</script><br /><div>
<br /></div>
</div>Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com0tag:blogger.com,1999:blog-15446379.post-61037801458695129322012-03-08T19:50:00.000-05:002012-03-08T19:50:03.299-05:00Conditional Critical Regions: Implementing (or not) in C++<i>Two notes. First I'm using embedded gists for the code examples. This may not work in RSS. Secondly, I thought this would be two parts but it's getting long so it's going to be three.</i><br />
<br />
First let's set the stage. This code is written with C++11 in mind, I assume lambda support. I also assume C++11 type mutex/condition_variable support, but since I didn't actually have that I wrote my own, so in this code their not explicitly in the std namespace. You should be able to to use std ones or boost ones or what have you by dropping in the appropriate using declarations. I also whipped up a simple scope guard doodad.
<script src="https://gist.github.com/1992638.js?file=gistfile1.cpp">
</script>
<br />
<br />
Before I forget, you probably should have read the <a href="http://meta-meta.blogspot.com/2012/02/conditional-critical-regions.html">last</a> post. So let's start with the simple versions of these, the <span style="font-family: 'Courier New', Courier, monospace;">with </span><span style="font-family: inherit;"><i>r</i></span><span style="font-family: 'Courier New', Courier, monospace;"> do </span><span style="font-family: inherit;">and the </span><span style="font-family: 'Courier New', Courier, monospace;">with </span><span style="font-family: inherit;"><i>r</i></span><span style="font-family: 'Courier New', Courier, monospace;"> when </span><i style="font-family: inherit;">Condition </i><span style="font-family: 'Courier New', Courier, monospace;">do.</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span>
<script src="https://gist.github.com/1992678.js?file=gistfile1.cpp">
</script>
<br />
<span style="font-family: inherit;">That's actually not bad at all, no? Lambdas and std::function make this all a bit smoother than the C++ of yore would have. Ok, let's talk about problems. What happens when we nest? Actually, not at all what I expected! This blog post might turn out to be about compiler bugs.</span><br />
<br />
<script src="https://gist.github.com/1992759.js?file=gistfile1.cpp">
</script>So what happens when we compile this? We get a compiler error (I'm using VS2010): <span style="font-family: 'Courier New', Courier, monospace;">error C2872: ' ?? A0xc6bc40fc' : ambiguous symbol</span><span style="font-family: inherit;">. Oops. Your C++ is showing. Intellisense has a better message, telling me that it's an "Invalid reference to a outer-scope local variable in a lambda body". My first instinct was to believe the compiler error and try and disambiguate it:</span><br />
<span style="font-family: inherit;"><br /></span>
<script src="https://gist.github.com/1992779.js?file=gistfile1.cpp">
</script>
I should have listened to Intellisense.<br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="font-family: 'Courier New', Courier, monospace;">fatal error C1001: An internal error has occurred in the compiler.</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">1> (compiler file 'msc1.cpp', line 1420)</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">1> To work around this problem, try simplifying or changing the program near the locations listed above.</span><br />
<span style="font-family: 'Courier New', Courier, monospace;">1> Please choose the Technical Support command on the Visual C++ </span><br />
<span style="font-family: 'Courier New', Courier, monospace;">1> Help menu, or open the Technical Support help file for more information</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><br /></span><br />
<span style="font-family: inherit;">I broke my compiler :(. Anyway, I suppose this is what happens when we try to point out a specific problem with a small example, we find new, different problems. We can solve this problem, and demonstrate what I really wanted to.</span>
<script src="https://gist.github.com/1992801.js?file=gistfile1.cpp">
</script>
Take that, lambda nesting! So what is the problem, I was trying to demonstrate? Well it's not necessarily safe for a <span style="font-family: 'Courier New', Courier, monospace;">mutex</span> to be locked multiple times on the same thread, so if we want to support nesting of with blocks on the same resource we'd better make sure that's a <span style="font-family: 'Courier New', Courier, monospace;">recursive_mutex</span>. Simple enough. Now, let's get to the real meat of the matter, the <span style="font-family: 'Courier New', Courier, monospace;">await </span><span style="font-family: inherit;">statement.</span>
<script src="https://gist.github.com/1993005.js?file=gistfile1.txt">
</script>
So above is the naive implementation of await. So what's wrong with it?
<script src="https://gist.github.com/2000726.js?file=gistfile1.cpp">
</script>
Oops. It's not legal to wait if we don't have the lock. Well, that's fine, we're using a recursive_mutex now, we can fix this.
<script src="https://gist.github.com/2000734.js?file=gistfile1.cpp">
</script>
Warning: notation abuse. There's still a problem here. It's unsatisfying from a correctness standpoint in at least two scenarios. Before your bug would do something weird, not it has a defined semantic, but it probably wasn't what you wanted. And now you can write this:
<script src="https://gist.github.com/2004350.js?file=gistfile1.cpp">
</script>
The limitations of nesting lambdas is really making this uglier than I intended. What do we want? We want a version of await that we can only call in the right circumstances. We can of course check these things at runtime, and throw exceptions, but I'd much rather await not even mention the resource, in other words be impossible to be incorrect. Of course if we make await a free function we can do that, but then we're back to runtime detection in the case when we're not inside a block at all. This is the real problem I want to solve, and we'll look at some approaches next time.<br />
<br />Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com0tag:blogger.com,1999:blog-15446379.post-50043769239576026262012-02-25T15:18:00.000-05:002012-02-25T15:18:12.441-05:00Conditional Critical RegionsHoare, in "Towards a Theory of Parallel Programming" describes something called a "conditional critical region", this is an expansion of an idea of Dijkstra's, called critical regions.<div>
<br /></div>
<div>
Briefly then, a critical region is a syntactic construct that looks something like:</div>
<div>
<br /></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">with</span> <i>r</i> <span style="font-family: 'Courier New', Courier, monospace;">do</span> <i>C</i></div>
<div>
<i><br /></i></div>
<div>
where <i>r </i>is the name of the critical region or resource, and <i>C </i>is the statement to be executed without interference from any other such statements also executed under the auspices of with <i>r. </i>This is pretty much exactly the sort of thing we have in C# and Java with the lock and synchronized statements, respectively.</div>
<div>
<br /></div>
<div>
Stop me if I am going too fast. So what is a conditional critical region then? It, as Hoare described it originally adds a Boolean condition to which the critical region will not be entered until such time as the condition is or becomes true. It looks like</div>
<div>
<br /></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">with</span> <i>r</i> <span style="font-family: 'Courier New', Courier, monospace;">when</span> <i>B</i> <span style="font-family: 'Courier New', Courier, monospace;">do</span> <i>C</i></div>
<div>
<i><br /></i></div>
<div>
So if <i>B </i>is false, we block until it becomes true through the intervention of some other thread of execution. Java and C# do not have this construct. Instead they have a lower level mechanism, <span style="font-family: 'Courier New', Courier, monospace;">await</span> and <span style="font-family: 'Courier New', Courier, monospace;">Monitor.Wait</span> respectively. These are a little bit similar to an extension to condtional critical regions, the await statement.</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">with</span> <i>r</i> <span style="font-family: 'Courier New', Courier, monospace;">do</span> </div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">begin</span></div>
<div>
<i>C1</i></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">await</span> <i>B</i></div>
<div>
<i>C2</i></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">end</span></div>
<div>
<br /></div>
<div>
After <i>C1, </i>if <i>B </i>is false, control of the region will be relinquished until <i>B</i> becomes true. Then <i>C2</i> will be executed again with the resource held. The difference between this, and Java's await is that await in Java releases the critical region unconditionally, you have to check <i>B</i> yourself. Consequently, the correct way to write this in Java (or C#) looks like</div>
<div>
<br /></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">synchronized</span>( r ) {</div>
<div>
<i>C1</i></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace;">while</span>( ! <i>B</i> ) {</div>
<div>
<i>r</i>.<span style="font-family: 'Courier New', Courier, monospace;">await</span>();</div>
<div>
}</div>
<div>
<i>C2</i></div>
<div>
}</div>
<div>
<br /></div>
<div>
This is, as you can imagine a source of errors, commonly using if instead of while to test <i>B. </i></div>
<div>
<i><br /></i></div>
<div>
So that is what conditional critical regions are. I think that when and await are probably the appropriate level of abstraction and utility when compared to something like pthread-style condition variables or Java/C# monitors. So I would like to implement them in C++. When I started doing that I found myself facing a problem, which is actually going to be the focus of my next post (and will have nothing to do with concurrency at all really).</div>
<div>
<br /></div>Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com0tag:blogger.com,1999:blog-15446379.post-24786880109317448322011-11-13T18:02:00.001-05:002011-11-13T18:24:17.118-05:00I did Two Shoes Weekend II: The Shoesening<p><a href="http://ckolderup.tumblr.com/post/11569684987/two-shoes-weekend-2-the-shoesening">Two Shoes Weekend</a> is an event put on by my friend Casey. The basic idea is that you do two projects (two shoes if you will) over a weekend. It is inspired by Shoes, which is a _why the Lucky Stiff thing, but you don't have to use Shoes. This is the second run of two shoes weekend. Last time I almost did something, but I got distracted. At the time, I was using Vista (mock my operating system all you want, it's not germane to story time), and the Windows version of shoes had some issues there. Specifically, the background of the window was an inky black darkness, impervious to light. You could "fix" this problem by lying to Shoes, and saying you were XP. Unfortunately, this triggered the Vista bug that the code that created the inky blackness was designed to avoid, an abominable amount of flickering that would give you a headache. Part of my day job involves wrangling GDI and windows so I started to take a look at the code. I didn't really accomplish anything by doing this, and the weekend largely ended with me having little to nothing to show for it.</p>
<p>
This year, I decided to avoid that whole class of problem by making one of my shoes shoes itself. More specifically, I took one part IronRuby, and one part WPF and whipped up a reasonable facisimle of Shoes. It has the "advantage" of being pure ruby since the <a href="http://ironruby.net/">IronRuby</a> guys did all the work of binding ruby to the CLR for me, and the WPF guys did all the hard work of implementing the moral equivalent of "slots" for me. I took a rather haphazard approach though, basically implementing the bits that were needed for some initial sample projects. It wasn't until relatively late in the weekend that I actually started going through the manual and adding the features in the right way. It will probably never replace real Shoes for Shoes use case, for one thing you have to install IronRuby to run it, but it is sort of interesting for slapping a GUI on to some existing .NET functionality perhaps. Shoes seems remarkably well-suited for being implemented in WPF, stack might as well be a StackPanel, and flow might as well be a WrapPanel, and that's what I did really. WPF's pervasive tendency to use URIs might things like <tt>image "http://thing.png"</tt> worked with almost no effort on my part.</p>
<p>My second shoe was pretty boring, but I felt compelled to do two. I made a "lonely blog", aka a diary. It displays a stream of text and images that it saves/loads from a local file on your computer. It looks like this:
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-f_OAxnuUnVM/TsBQxLWD2BI/AAAAAAAAAC0/bIj7BYRLsss/s1600/lonelyblog.png" imageanchor="1" style="clear:left; float:left;margin-right:1em; margin-bottom:1em"><img border="0" height="190" width="320" src="http://2.bp.blogspot.com/-f_OAxnuUnVM/TsBQxLWD2BI/AAAAAAAAAC0/bIj7BYRLsss/s320/lonelyblog.png" /></a></div>
<p>You enter either image urls or commentary and click the appropriate button. The save button saves the blog, and the entries will appear the next time you load it.</p>
<p>All in all, a fun time. I haven't done anything in Ruby in a while so that was fun. The code for the WPF/IronRuby shoes work-a-like is <a href="https://github.com/lcapaldo/steeltoedboots">here</a>, and the lonelyblog shoes app is <a href="https://gist.github.com/1362872">here</a>.Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com1tag:blogger.com,1999:blog-15446379.post-33016614944825960882011-06-26T21:59:00.010-04:002011-06-27T10:46:02.996-04:00Lambda didn't (or won't) kill the expression template starNow that C++0x is on it's way, and many compilers already implement lambdas, it may be thought that the venerable "functor" is on it's way out. Well aside from the obvious reasons of supporting legacy code, that's simply not true. operator() is here to stay, and I will tell you why.<br /><br />Lambdas, though convenient, are opaque. You can't peek inside of a lambda or peel back it's inner workings, and the vast majority of the time, that's fine, you don't need to. The same is true for normal named functions and member functions. On occasion however, a slightly more transparent tool can be useful, and operator() can help you build such translucent functions.<br /><br />Let me try to justify this with an example. LLVM is a library for building compiler backends. It is written in C++, and it happens to have a <a href="http://llvm.org/docs/CodingStandards.html">coding standards document</a>. One of the style points is <a href="http://llvm.org/docs/CodingStandards.html#hl_predicateloops">"Turn Predicate Loops into Predicate Functions"</a>.<br /><br />Basically, instead of code like<br /><br /><pre>bool pred = false;<br />for(unsigned i = 0; i < list.size(); ++i)<br />{<br /> if( list[i].satisfies() )<br /> {<br /> pred = true;<br /> break;<br /> }<br />}<br /><br />if( pred )<br />{<br /> ...<br />}<br /></pre><br /><br />You should have code like<br /><br /><pre>if( TestPred(list) )<br />{<br /> ...<br />}<br /></pre><br /><br />They have their justifications, which you can read if you're interested. This really isn't about whether this is a good idea or not, but rather how to write TestPred. There is an obvious approach:<br /><pre>bool TestPred(const std::vector<Something>& list)<br />{<br /> for(unsigned i = 0; i < list.size(); ++i)<br /> {<br /> if( list[i].satisfies() ) return true;<br /> }<br /> return false;<br />}<br /></pre><br /><br />The problem with this, is that you can't reuse the predicate. Or rather, that you can, but only in a very specific way. If you need to test a std::list of Something instead you need to either copy the list or duplicate the code. Worse, if you don't know what the code is, you don't even have duplication as an option.<br /><br />A brief aside, yes a solution to this mess would be to just use std::find_if in the first place. This is just however the motivating example that came to mind when I happened to be reading the LLVM coding guidelines, so bear with me.<br /><br />So we can change TestPred to operate on iterators. Now we can use it with list, vector, etc.<br /><pre><br />template <typename FwdIter><br />bool TestPred(FwdIter begin, FwdIter end)<br />{<br /> for(FwdIter i = begin; i != end; ++i)<br /> {<br /> if( i->satisfies() ) return true;<br /> }<br /> return false;<br /> // or return find_if(begin, end, [](const Something& s) { return s.satisfies(); }) != end<br />}<br /></pre><br /><br />But before we had the nice feature of being able to call this on a std::vector directly. We could add overloads for that, but that gets tedious especially since we're writing one of these functions every time we have a new predicate we need to loop over. We can use templates to let us get that std::vector overload back (and more, std::list for example, and your plain old array) by writing the code for iteration once and plugging in the varying <tt>i->satisfies</tt> part.<br /><br /><pre><br />template<typename F><br />struct RangedAnyPredicate<br />{<br /> typedef F Tester;<br /> template<typename FwdIter><br /> bool operator()(FwdIter begin, FwdIter end) const<br /> {<br /> for(FwdIter i = begin; i != end; ++i)<br /> {<br /> if(F::test(*i))<br /> {<br /> return true;<br /> }<br /> }<br /> return false;<br /> }<br />};<br /><br />struct satisfier<br />{<br /> typedef const Something& testee_type;<br /> static bool test(const Something& s)<br /> {<br /> return s.satifies();<br /> }<br />};<br /><br />static RangedAnyPredicate<satisfier> TestPred;<br /></typename></pre><br /><br />Here we've extracted out just the looping over part. TestPred will behave almost identically to our templated on a pair of iterators version of the function (exceptions being things like, we can't pass this TestPred around as a function pointer). This is more typing that previous version of course, even with multiple predicates the overhead of a struct for each one is high. Where it starts to pay dividends is when provide more overloads for free. We're going to need some traits to do that, and again while this is a bunch of code up front, some of these traits are independently useful and already exist.<br /><br />We want to be able to call this on two iterators, on a container with begin and end methods, and on a standard array. We can distinguish between the two argument and single argument forms easily with the normal overloading mechanism. For distinguishing between containers with begin and end and standard arrays we'll assume anything not an array should have a begin and an end.<br /><br />So to detect arrays will use an is_array trait:<br /><pre>template<typename T><br />struct is_array<br />{ enum {val = false}; };<br /><br />template<typename T, long N><br />struct is_array<T [N]><br />{ enum {val = true}; };<br /></pre><br /><br />We can then use this information to decide to either call TestPred(arg.begin(), arg.end()) or TestPred(arg, arg + N).<br /><br /><pre><br /> template<bool C><br /> struct do_test;<br /><br /> template<><br /> struct do_test<true><br /> {<br /> template <typename Self, typename T, int N><br /> static bool go(const Self& self, T (&a)[N])<br /> {<br /> return self(a, a + N);<br /> }<br /> };<br /><br /> template<><br /> struct do_test<false><br /> {<br /> template<typename Self, typename C><br /> static bool go(const Self& self, const C& c)<br /> {<br /> return self(c.begin(), c.end());<br /> }<br /> };<br /><br /> ...<br /> // back inside RangedAnyPredicate<br /> template<typename Container><br /> bool operator()(const Container& c) const<br /> {<br /> return do_test<is_array<Container>::val>::go(*this, c);<br /> }<br /> ...<br /></pre><br /><br />Now we've got overloads for vector, list, and any other container that might come along and behave like a standard sequence, as well as old fashioned arrays. <br /><br />But there's more. You may have noticed we included a Tester typedef in RangedAnyPredicate. This is where the ability to make a functor less opaque than a regular function or a lambda starts to be useful. Let's say we have two predicates, PredA and PredB. And furthermore the coding guidelines were followed and we have TestPredA and TestPredB functions to work with. If we want to find out if a list has an eliminate that satisfies PredA or PredB we can do the obvious:<br /><pre><br />if( TestPredA(list) || TestPredB(list) )<br />{<br /> ...<br />}<br /></pre><br /><br />But this is C++! The code above has the potential to needlessly traverse the list twice. We've got to be able to do something about that, right? Well not if TestPredA and TestPredB are regular functions. We can write a third function that does the or-ing, but it can't peek inside the functions. If however, we use RangedAnyPredicate to define TestPredA and TestPredB we can extend them as needed. First will need a predicate to represent the or-ing of the internal predicates of A and B:<br /><br /><pre><br />template<typename Lhs, typename Rhs><br />struct OrCombiner<br />{<br /> typedef typename Lhs::testee_type testee_type;<br /> static bool test(testee_type testee)<br /> {<br /> return Lhs::test(testee) || Rhs::test(testee);<br /> }<br />};<br /></pre><br /><br />Next we use a little operator-overloading-fu in RangedAnyPredicate to make this easy to use:<br /><pre><br />// Back in RangedAnyPredicate<br />template<typename TestF><br /> RangedAnyPredicate< OrCombiner<F, TestF> > operator|(RangedAnyPredicate<TestF> )<br /> {<br /> return RangedAnyPredicate< OrCombiner<F, TestF> >();<br /> }<br /></pre><br /><br />Now our code becomes<br /><pre><br /><br />if( (TestPredA | TestPredB)(list) )<br />{<br /> ...<br />}<br /><br /></pre><br />and only one pass is made over the list. If you want different semantics, of course you can just simply use the prior code. The same can be done for logical and as well of course.<br /><br />This was of course a contrived example, but I hope of demonstrated how the functor still has its place, even in a world of lambdas.Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com0tag:blogger.com,1999:blog-15446379.post-89922319610730431322011-06-02T18:52:00.008-04:002011-06-02T20:13:54.684-04:00Taking Herb Sutter out of Context (or type system assisted type safety)I was watching <a href="http://channel9.msdn.com/Shows/Going+Deep/Conversation-with-Herb-Sutter-Perspectives-on-Modern-C0x11">this interview</a> with Herb Sutter and an off-hand comment was made about how you need GC (or automatic memory management) for "type safety". What is "type safety"? I'm going to use a very informal definition, that is, we say a program is "type safe" if a value of T* is not null it is correct to interpret the memory it refers to as a T. This is pretty hand-wavy, but good enough for this exercise.<br /><br />Now you might say "Well duh, malloc returns void*", but let's instead imagine a C++ variant with no reinterpret_cast (or C casts) no void *, no malloc and no placement or global operator new. <br /><br />Is this a "type safe" language? Or does it need GC to take it all the way?<br /><br />Consider the following program, X and Y are classes unrelated by inheritance:<br /><br /><pre><br />X* x = new X;<br />x->something();<br />delete x;<br />Y* y = new Y;<br />X x2;<br />*x = x2;<br /></pre><br /><br />I just called X::operator= on a Y with no casts. I was able to do this because this hypothetical implementation happens to be super aggressive with regards to using recently freed memory. Now, this is undefined behavior in C++ and would presumably be so in our hypothetical "type safe(er)" subset.<br /><br />But is that useful? If you're the kind of person who fervently believes in nasal demon style consequences for undefined behavior and that it is foolish to ask for more you can skip to the end, because any undefined behavior in the program can scramble it, you don't need to rely on "aggressive" heap managers and plausible explanations.<br /><br />So then what we need to do is either a) define this behavior, or b) disallow it or c) refine"undefined behavior" to allow for nasal demons et. al. but not for breaking the type safety of our programs.<br /><br />Option C is easily said, and since a language spec. is just things you say, might even be easily done (although saying it specifically and clearly would probably be difficult in practice). <br /><br />We could try to define this behavior. What if delete also set the pointer to null (and we made dereferencing null defined behavior, it calls std::terminate let's say)? This obviously won't be sufficient:<br /><pre><br />X* a = new X ;<br />X* b = a;<br />delete a;<br /></pre><br /><br />A delete like this could also only ever operate on lvalues.<br /><br /><pre><br />delete i_only_love_for_your_sideeffects();<br /></pre><br /><br />would become illegal.<br /><br />The <tt>b = a</tt> program snippet is also a counter example to a delete that takes its argument out of scope. <br /><br />Maybe we can fix this by messing with our "aggressive" allocator. We could specify that once an X, always an X (if not necessarily the same X). That is to say our allocator would be specified as reserving blocks of memory for specific types, once reserved a block could not be reused for allocations of different types.<br /><br />This places some constraints on our allocator implementation, and is somewhat dissatisfying. But it does satisfy our hand-wavy definition of type-safety. Part of the problem is that our definition of type-safety doesn't seem to let us write safer programs. A pointer that unpredictably becomes an alias to another object without any assignment will probably result in a buggy program, even if we can confidently state the type it aliases.<br /><br />Except this allocator doesn't even give us that. Remember we're talking about C++ (or a C++ variant anyway) here. Have you ever called a virtual method from a constructor? What about a pure virtual method? What about from a destructor? By the time delete is done our T might not be a T anymore. Assuming a less aggressive allocator (or the program just never news another T) we're left with a type-unsafe program again.<br /><br />delete seems to be a serious problem. The way garbage collection handles it is, they don't let you delete anything. Can we do the same? We could just remove delete from the language. Then we're fine as long as we have infinite memory. As a practical matter though, we need some way to reclaim the unused memory, since we don't have infinite memory. Oops garbage collection again.<br /><br />So getting rid of delete is tantamount to GC. Can we keep it somehow? Earlier we discussed the idea of having delete null out its argument. That didn't work because of aliasing. Sounds like we need to get rid of aliasing.<br /><br />To simplify eliminating aliasing we're going to remove some features from the language. Don't worry: later we'll try and put them back.<br /><br />We're going to get rid of the address of operator and references (basically any use of the ampersand that doesn't involve Boolean logic). By removing references we just throw away a whole slew of opportunities for aliasing. Ditching the address of operator means the only way of manufacturing a new pointer value is with, well, new. We'll allow aliasing NULL (or we can treat it as syntax if you like).<br /><br />Ok first we'll do the obvious way of disallowing aliasing: no copy constructor or assignment operator for pointer types. This is clearly useless as you can't even pass pointers to functions then. <br /><br />Let's get a little more complicated then: when a pointer typed variable appears on the right hand side of an assignment or as a parameter to a function, that variable is no longer considered to be in scope.<br /><br />It's as though<br /><pre><br />A * x = new A;<br />A * y = x;<br /></pre><br />were transformed to<br /><pre><br />A * y = NULL;<br />{<br /> A * x = new A;<br /> y = x;<br />}<br /></pre><br /><br />As you can see, this is a purely mechanical transform, and can be enforced at compile-time. Except for one little wrinkle: global pointers. So ban 'em, we don't need them. Or we can be a little nicer and just ban assigning from them, but that has its own wrinkle. Note that this restriction is infectious, no global structs with pointer members or members with pointer members.<br /><br />As a convenience we can allow assigning to an assigned from pointer variable and treating it as though we've introduced a new variable with same type and name. This allows code like:<br /><pre><br />x = munge(x);<br /></pre><br /><br />We have to be careful with conditionals: a simple rule is to require that the same variables are assigned-from in all branches of the conditional, and this can be checked at compile-time. This is some more pain for our programmers but such is life.<br /><br />We're now type-safe but still manually managing memory. Once you say<br /><pre><br />delete x;<br /></pre><br /><br />x goes out of scope, so we can't use the value x referred to after it's been deleted, and we know there are no aliases to it.<br /><br /><pre><br />T* sneaky(T* x)<br />{<br />delete x;<br />return x; // compiler error here<br />}<br /><br />T * x = ...;<br />T * y = x;<br />delete x; // compiler error here<br />y->stuff();<br /></pre><br /><br />As you may have realized by now I didn't invent this idea, it's called linear types and there's been a fair amount of research into it which you can look up with your favorite search engine. In this case we've made all pointers linear types, in languages that support this for "real" they'll typically have non-linear versions of the types as well.<br /><br />The usual example actually isn't memory (because GC makes using linear types for this redundant) but rather file handles. A linear file handle let's you make sure you've got an open handle before you try to read or write to it, and insures you don't close a handle twice, etc. I think you can imagine how that would work by this point.Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com0tag:blogger.com,1999:blog-15446379.post-29316184589405827322011-05-22T19:28:00.004-04:002011-05-22T20:00:38.475-04:00Management (or the art of delegation)Microsoft's .NET has a method called <a href="http://msdn.microsoft.com/en-us/library/system.runtime.interopservices.marshal.getfunctionpointerfordelegate.aspx">GetFunctionPointerForDelegate</a>. It allows you to turn a managed delegate into a function pointer that can be passed around to native code. A delegate is usually a method bound to a particular instance of a class. <br /><br />This sort of thing can be useful outside of the managed world as well. Many APIs that take callbacks allow you to pass in some additional user-specified data, usually as a void* or similar. However, some times they don't provide this capability. There are a few ways around this involving some variety of globals or thread-local storage, but this becomes awkward if we need to use more than one instance of this callback at a time.<br /><br /><a href="http://code.google.com/p/asmjit/">AsmJit</a> is a cute little C++ library for doing runtime code-gen for x86 and x64. In the following example I'm going to use it to let me use a member function as a callback. This code is for x86 using the cdecl calling convention, on linux.<br /><br /><pre><br />#include "AsmJit.h"<br />#include <iostream><br /><br />typedef void (*callback)(int);<br /><br />struct A<br />{<br /> int m_accum;<br /> void doIt(int x)<br /> {<br /> m_accum += x;<br /> std::cout << "A: " << x << " " << m_accum << std::endl;<br /> }<br />};<br /><br />void A_trampoline(A* a, int x)<br />{<br /> a->doIt(x);<br />}<br /><br />void takes_callback(callback cb)<br />{<br /> cb(1);<br /> cb(2);<br /> cb(3);<br />}<br /><br />int main()<br />{<br /> using namespace AsmJit;<br /> A a = A();<br /><br /> Assembler assemblr;<br /><br /><br /> assemblr.push(dword_ptr(esp, 4)); // push the original int arg<br /> assemblr.push(imm(reinterpret_cast<intptr_t>(&a))); // push a<br /> assemblr.call(imm(reinterpret_cast<intptr_t>(&A_trampoline))); // call A_trampoline(&a, [esp + 4])<br /> assemblr.add(esp, 8); // clean up the stack, cdecl is caller cleans up<br /> assemblr.ret(); // return<br /><br /> callback cb = function_cast<callback>(assemblr.make());<br /> takes_callback(cb);<br /><br />}<br /></pre><br /><br />Here takes_callback is one of those lame callback taking apis that don't let you pass around any user-speicified info. Using a little bit of x86 assembly we create a thunk, that adds an additional argument (the instance of A) and forwards it to A's doIt method.<br /><br />If we run this we get as ouptut:<br /><pre><br />A: 1 1<br />A: 2 3<br />A: 3 6<br /></pre><br /><br />Now an interesting thing to consider is, what would this code look like with different calling conventions? In particular, Microsoft's __thiscall is interesting. __thiscall is like Microsoft's __stdcall, except for the quirk that the this pointer is passed in the ecx register. __stdcall is like cdecl, except the callee is responsible for cleaning up the stack. Knowing this, and assuming our callback function was expected to be __stdcall our thunk code could look like (pseudo code)<br /><pre><br />mov ecx, &a<br />jmp A::doIt<br /></pre><br /><br />Only two instructions! Furthermore this template of two instructions works regardless of the arity of the member function we're forwarding to, and we don't have to copy any stack arguments or shuffle it around like we needed to for cdecl. Given the thunk uses a jmp, rather than a call, the thunk itself doesn't appear on the call stack during a stack trace, but it looks rather as though the member function had directly been called. This is arguably a nice feature from a debugging standpoint (is this a dynamically generated function on the stack, or did we go off into the woods?). It almost looks like __thiscall was at least partially designed with this use case in mind.Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com0tag:blogger.com,1999:blog-15446379.post-19401965561120740352011-03-13T17:50:00.003-04:002011-03-13T18:16:05.847-04:00Memory leaks and other bugsIt was pointed out to me that my last post had a bug (one that I wasn't aware of). Specifically, <tt>pure_modify</tt> leaks the old value. It is a simple fix:<br /><br /><pre><br /><br />template<typename F><br /> T pure_modify(F f)<br /> {<br /> std::auto_ptr<T> mem;<br /> T* old_val; // not an auto_ptr becase if we throw we have not taken ownership<br /> // We either threw from user code, or from new. And throwing user<br /> // user code would be wrong anyway (impure)<br /> AdapterF<F,T> adapter;<br /> adapter.f = f;<br /> adapter.mem = &mem;<br /> adapter.old_val = &old_val;<br /> m_impl.pure_modify(adapter);<br /> delete old_val;<br /> return *mem.release();<br /> }<br /></pre><br /><br />We'll also need to adjust <tt>AdapterF</tt> for this<br /><pre><br />template<typename F, typename V><br /> struct AdapterF<br /> {<br /> F f;<br /> std::auto_ptr<V>* mem;<br /> V** old_val;<br /> void* operator()(void *in)<br /> {<br /> V r = f(*(*old_val = static_cast<V*>(in)));<br /> mem->reset(new V(r));<br /> return static_cast<void*>(mem->get());<br /> }<br /> };<br /><br /></pre><br /><br />Once pure_modify returns, we know that the last pointer value in old_val belongs to us, because we've successfully replaced it with something else, and it becomes our responsibility to clean it up.<br /><br />So then, what was the other bug I alluded to last time? That was the so-called "ABA" problem. Basically, with this code I treat pointers as being unique identities for the life of the process. However, all heap implementations reuse memory (that's sort of the point, if you didn't reuse it you wouldn't need free) so two different objects can have the same address at different points during the lifetime of the program. <br /><br />Two threads walk into an MVar. They both read the value and begin their operation. Thread A's operation is particular CPU intensive. Thread B is done lickity split and puts a new value in. Meanwhile Thread C comes along, and his operation is also fast. Thread B returned the old block of memory to the heap manger, so when Thread C finishes, it happens to grab that very same block for its result and puts it back into the MVar. Thread A finally finishes up, sees the pointer value is the same as last time, and happily shoves his modification in as the new value, completely unaware he had just wiped out the effects of two prior modifications.<br /><br />And these sorts of things are the reasons why I'm probably not going to go off and implement this kind of abstraction at my day job. That and <tt>pure_modify</tt>'s constraints aren't all that C++-friendly and it's hard to imagine good use cases. Some kind of atomic bignum library maybe?Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com0tag:blogger.com,1999:blog-15446379.post-2607007611673378602011-02-02T21:27:00.002-05:002011-02-02T21:31:14.665-05:00Purity, laziness, and stupid compiler tricks<p>So now we have a pointer sized (on x86-32 Linux anyway), type-safe concurrenc ry primitive in our MVar<T>. I'm going to add an additional operation, and we're going to talk about the ramifications.<br /><br /><p>First, we need to add it to ptrmvar32:<br /><br /><pre><br /><br /> template<typename F><br /> void* pure_modify(F f)<br /> {<br /> uintptr_t curr;<br /> while(1) {<br /> curr = m_val;<br /> if( curr == 0 )<br /> {<br /> if( __sync_bool_compare_and_swap(&m_val, 0, 1) )<br /> futex_wait(&m_val, 1);<br /> } else if( curr == 1 ) {<br /> futex_wait(&m_val, 1);<br /> } else {<br /> void *new_val = f(reinterpret_cast<void*>(curr & ~1));<br /> if( __sync_bool_compare_and_swap(&m_val, curr, new_val) )<br /> break;<br /> }<br /> }<br /> }<br /></pre><br /><br /><p> We're going to add this to the type-safe version as well before we get into it, so don't worry if this looks confusing.<br /><br /><pre><br />private:<br /> template<typename F, typename V><br /> struct AdapterF<br /> {<br /> F f;<br /> std::auto_ptr<V>* mem;<br /> void* operator()(void *in)<br /> {<br /> V r = f(*static_cast<V*>(in));<br /> mem->reset(new V(r));<br /> return static_cast<void*>(mem->get());<br /> }<br /> };<br /><br />public:<br /> template<typename F><br /> T pure_modify(F f)<br /> {<br /> std::auto_ptr<T> mem;<br /> AdapterF<F,T> adapter;<br /> adapter.f = f;<br /> adapter.mem = &mem;<br /> m_impl.pure_modify(adapter);<br /> return *mem.release();<br /> }<br /></pre><br /><br /><p> Because this is C++, there is some noise with regards to memory management, but it should be pretty clear what this new operation does. It takes the current value of the MVar, applies a function to the value, and returns a new value tha t is put into the MVar. Now, the analogous operation for Haskell is modifyMVar/m odifyMVar_. Interestingly the type of the function that the Haskell modifyMVar t akes is<br /><pre><br /> a -> IO a<br /></pre><br /><br /><p> This is because Haskell's modifyMVar has semantics more like the following:<br /><pre><br /> template<typename F><br /> T haskell_modify(F f)<br /> {<br /> T val = take();<br /> struct ValRestorer {<br /> T val;<br /> bool restore;<br /> MVar<T> *self;<br /> ~ValRestorer() { if(restore) self->put(val); }<br /> ValRestorer(T val_, MVar<T> *self_) : val(val_), self(self_),<br /> restore(true) {}<br /><br /> void Dismiss() { restore = false; }<br /> } restorer(val, this);<br /> T new_val = f(val);<br /> put(new_val);<br /> restorer.Dismiss();<br /> }<br /></pre><br /><p> In other words, Haskell's modify is to make the update transactional in the face of exceptions in the modifying code. To properly use modify, you have to ma ke sure all the threads take from the mvar before they put to it.<br /><p>I called attention to the type of modifyMVar earlier, and also by naming my m ethod pure_modify. As should be obvious from the code, the user supplied functio n may be called many times (although we hope it isn't in the common case). In Ha skell, the user supplied function would have to have the type<br /><pre><br />a -> a<br /></pre><br /><br /><p>This is wonderful! Wonderful because we can actually express it. Among other things, we know the user supplied function won't take any other locks for instan ce, so modification is deadlock free. The other great thing, is that we can feel comfortable calling it as many times as we need, because beign a pure function the observable effect is that it atomically modified the value in the MVar.<br /><br /><p>Often when we think about purity and how it enables laziness (or is it the ot her way around?), we think in terms of functions being called less often (someti mes we even think laziness implies automatic memoization, this is not the case, and if you think about the memory usage you'll quickly realize why). But here, w e can leverage the same properties of pure code to spend less time blocked or wa iting, and hopefully, in the common case waste less CPU time.<br /><br /><p>Finally, see if you can see what classic "lock-free programming" bug I've int roduced into this code (or bugs? There's at least one) by adding this pure_modif y operation.Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com0tag:blogger.com,1999:blog-15446379.post-34057773492569562432011-01-16T17:13:00.004-05:002011-01-16T17:20:46.579-05:00Implementing Haskell-style MVars in C++ using futexes<p>Last time we talked about what Linux futexes were. Now, I want to use them to implement a concept from Haskell called an MVar. An MVar can be thought of as concurrent queue with a size of 1, that is it is a box which you can put things in, and take things out safely from multiple threads. The basic operations are two:<br /><ul><li>put(T value)</li><br /><li>T take()</li></ul><br /><br /><p>When the MVar is empty, take'ing blocks, when it is full, put'ing blocks. Real Haskell MVars have guarantees with regards to fairness, we're not going to address those here. In fact, we're going to do a "cute" implementation, and it has several flaws. First, it's only going to work on x86-32, this will not be a portable implemnetation. But this lets us be "cute", our MVar is going to be only the size of an int. Below is `ptrmvar32`, it is a 32bit void* MVar implementation that we we'll use to build our MVar<T>. NULL will represent empty, and we'll use the LSB to note whether we need to wake anyone up (using only one bit for this is one of the flaws).<br /><pre><br />#ifndef PTRMVAR32_H<br />#define PTRMVAR32_H<br />#include <stdint.h><br />#include <assert.h><br />class ptrmvar32<br />{<br /> uintptr_t m_val;<br /> static char s_pointers_are_32_bits[sizeof(void*) == 4 ? 1 : -1];<br /> static void futex_wait(void *, uintptr_t);<br /> static void futex_wake(void *);<br /> public:<br /> ptrmvar32(void *initial_value) : m_val(reinterpret_cast<uintptr_t>(initial_value))<br /> {<br /> assert(m_val);<br /> }<br /><br /> ptrmvar32() : m_val(0)<br /> {}<br /><br /> void* take()<br /> {<br /> uintptr_t curr;<br /> while(1) {<br /> curr = m_val;<br /> if( curr == 0 )<br /> {<br /> if( __sync_bool_compare_and_swap(&m_val, 0, 1) )<br /> futex_wait(&m_val, 1);<br /> } else if( curr == 1 ) {<br /> futex_wait(&m_val, 1);<br /> } else {<br /> if( __sync_bool_compare_and_swap(&m_val, curr, 0) )<br /> {<br /> if( curr & 1 )<br /> {<br /> futex_wake(&m_val);<br /> }<br /> curr &= ~1;<br /> return reinterpret_cast<void*>(curr);<br /> }<br /> }<br /> }<br /> }<br /><br /> void put(void *val)<br /> {<br /> const uintptr_t new_val = reinterpret_cast<uintptr_t>(val);<br /> uintptr_t curr;<br /> while(1) {<br /> curr = m_val;<br /> if( curr == 0 )<br /> {<br /> if( __sync_bool_compare_and_swap(&m_val, 0, new_val) )<br /> return;<br /> } else if( curr == 1 ) {<br /> if( __sync_bool_compare_and_swap(&m_val, 1, new_val) ) {<br /> futex_wake(&m_val);<br /> return;<br /> }<br /> } else {<br /> if( __sync_bool_compare_and_swap(&m_val, curr, curr | 1) ) {<br /> futex_wait(&m_val, curr | 1);<br /> }<br /> }<br /> }<br /> }<br /><br /> void* unsafe_value()<br /> {<br /> return reinterpret_cast<void*>( m_val & ~1);<br /> }<br />};<br />#endif<br /></pre><br /><p>ptrmvar32.cpp contains the implementation of futex_wake and futex_wait which are wrappers around the futex syscall<br /><br /><pre><br />#include "ptrmvar32.h"<br />#include &t;linux/futex.h><br />#include <sys/syscall.h><br />#include <unistd.h><br />#include <limits><br /><br />void ptrmvar32::futex_wait(void *on, uintptr_t when)<br />{<br /> syscall(__NR_futex, on, FUTEX_WAIT, when, NULL, 0, 0);<br />}<br /><br />void ptrmvar32::futex_wake(void *on)<br />{<br /> syscall(__NR_futex, on, FUTEX_WAKE, std::numeric_limits<int32_t>::max(), NULL, 0, 0);<br />}<br /><br /></pre><br /><br /><p>As you can see futex_wake wakes up everyone, not just one waiter. This is because someone could be waiting to take and someone could be waiting to put and if we wake the wrong one of the two we'll never wake up. If this situation does actually occur we end up in thudering herd territory.<br /><br /><p>Next we build our typesafe, templated version on top of this:<br /><pre><br />#include "ptrmvar32.h"<br /><br />template<typename T><br />class MVar<br />{<br /> ptrmvar32 m_impl;<br /><br /> public:<br /> MVar() : m_impl()<br /> {}<br /><br /> MVar(const T& val) : m_impl(static_cast<void*>(new T(val)))<br /> {}<br /><br /> void put(const T& val)<br /> {<br /> T* p = new T(val);<br /> m_impl.put(static_cast<void*>(p));<br /> }<br /><br /> T take()<br /> {<br /> T *p = static_cast<T*>(m_impl.take());<br /> T r(*p);<br /> delete p;<br /> return r;<br /> }<br /><br /> ~MVar()<br /> {<br /> delete static_cast<T*>(m_impl.unsafe_value());<br /> }<br />};<br /></pre><br /><br /><p>Now put and take use new and delete, really we should be using a thread local allocator here, but I got too lazy to implement that part. Maybe next time. Ignoring that, you can see that this is a very light weight primitive, only taking 4 bytes. The pthread based implementation would take at least a mutex and condition variable, probably two condition variables to avoid the problem of waking up the wrong threads that this implementation is suspectible to. However, this is implemented the way it is to set up for next time, where we are going to talk about the implications of laziness and purity, and the operation that Haskell doesn't provide but could.<br /><br /><p>Here's a sample program making use of the MVars:<br /><pre><br />#include "mvar_template.h"<br />#include <string><br />#include <iostream><br />#include <pthread.h><br /><br />using namespace std;<br /><br />namespace<br />{<br /> MVar<string> in;<br /> MVar<string> out;<br /><br /> void *worker(void *)<br /> {<br /> cout << "waiting for value" << endl;<br /> string v = in.take();<br /> cout << "got value: " << v << endl;<br /> v += " gotten";<br /> out.put(v);<br /> return NULL;<br /> }<br /><br />}<br /><br />int main()<br />{<br /> cout << sizeof(in) << endl;<br /> string s = "in";<br /> pthread_t t;<br /> pthread_create(&t, NULL, &worker, NULL);<br /> pthread_detach(t);<br /> in.put(s);<br /> string r = out.take();<br /> cout << "got " << r << endl;<br />}<br /></pre>Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com0tag:blogger.com,1999:blog-15446379.post-7172257991604634112010-11-21T17:04:00.005-05:002010-11-21T18:21:36.958-05:00Linux threading primitives: the futex<div>Linux and glibc support POSIX threads. Unsurprisingly, POSIX concepts like mutexs, condition variables, etc. are not baked into the kernel. How then does glibc's implementation of pthreads for Linux work? Well, for mutual exclusion and signaling (that is mutexes, condition variables, semphores, etc.) pthreads on Linux generally uses the "futex", which is an abbreviation for "fast user-space mutex". This is a somewhat deceptive name. The actual futex system call's capabilities bring more to mind a "fast user-space semaphore" but I guess "fuphore" isn't quite as catchy. We'll assume the name is descriptive of usage rather than the mechanism.</div><div><br /></div><div>The futex syscall itself has 6 parameters. </div><div><br /></div><div><code> </code></div><div><code>int futex(int *uaddr, int op, int val, const struct timespec *timeout,</code></div><div><code> int *uaddr2, int val3);</code></div><div></div><div><br /></div><div>The first is always the address of the futex. A futex is just an <tt>int</tt> (this brings to mind, at least to me, NT's keyed events), generally representing the count of the semaphore. The identity of that int (that is to say, not the _value_ of its address, because that can vary across processes) is how the kernel distinguishes futexes. This is a neat trick, avoiding the requirement of a global namespace (such as with named events, mutexes etc. in Windows), while allowing for it by leveraging existing mechanisms (mmap, SysV shared memory, etc.). Of course, by typing this to the virtual address space of the process, this can't serve as cluster wide mechanism (mmaping a file shared over NFS is not going to be sufficient for example). </div><div><br /></div><div>The fourth parameter to the call is an optional timeout, which applies when using some operations. The third, fifth and sixth parameters meaning vary based on the operation.</div><div><br /></div><div>The operation is of course the second parameter. I'm only going to talk about two of the most basic operations, <tt>FUTEX_WAIT</tt> and <tt>FUTEX_WAKE</tt>.</div><div><br /></div><div>For <tt>FUTEX_WAIT</tt>, the val parameter is the current value of *uaddr. When you call futex with the wait operation, it checks atomically that *uaddr == val. If not, you return from futex right away. Otherwise, you FUTEX_WAIT until someone FUTEX_WAKEs you up.</div><div><br /></div><div><tt>FUTEX_WAKE</tt> wakes val processes (for the purposes of this discussion thread and process are synonymous) waiting on the futex uaddr.</div><div><br /></div><div>These two operations, in conjunction with atomic operations on int values give us everything we need to implement a semaphore. We can then use that semaphore to implement various other synchronization primitives (a mutex can be modelled as a binary semaphore for example).</div><div><br /></div><div><div>The "fast" and the "user-space" parts both refer to the idea that you don't actually call the system call save in the case of contention. Rather you platform specific code to increment and decrement *uaddr. If there is no contention, we need never go to the kernel to arbitrate.</div></div><div><br /></div><div>To demonstrate this, I'm going to show a small library for working with futexes. Note that I'm not using them entirely correctly, which you will discover if you check out the "further reading" section.</div><div><br /></div><div>First, we'll create an API for dealing with semaphores implemented with futexes. it is written in C, and I have named the header simple_futex.h</div><div><code><br /><div>#ifdef __cplusplus</div><div>extern "C" {</div><div>#endif</div><div>struct simplefu_semaphore {</div><div> int avail;</div><div> int waiters;</div><div>};</div><div><br /></div><div>typedef struct simplefu_semaphore *simplefu;</div><div><br /></div><div>void simplefu_down(simplefu who);</div><div>void simplefu_up(simplefu who);</div><div><br /></div><div><br /></div><div>#ifdef __cplusplus</div><div>}</div><div>#endif</div><div><br /></div><div><br /></div></code></div><div>Our sempahore consists of two operations, simplefu_down and simplefu_up, which perform as one expects a semaphore to. The avail member of the struct represents the count of the semaphore, the waiters member is used for tracking if we need to issue a wake operation.</div><div><br /></div><div>Here, in simple_futex.c is the implementation:</div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><div><br /><pre><br />#include "simple_futex.h"<br />#include <linux/futex.h><br />#include <sys/syscall.h><br /><br />void simplefu_down(simplefu who)<br />{<br />int val;<br />do {<br />val = who->avail;<br />if( val > 0 && __sync_bool_compare_and_swap(&who->avail, val, val - 1) )<br />return;<br />__sync_fetch_and_add(&who->waiters, 1);<br />syscall(__NR_futex, &who->avail, FUTEX_WAIT, val, NULL, 0, 0);<br />__sync_fetch_and_sub(&who->waiters, 1);<br />} while(1);<br />}<br /><br />void simplefu_up(simplefu who)<br />{<br />int nval = __sync_add_and_fetch(&who->avail, 1);<br />if( who->waiters > 0 )<br />{<br />syscall(__NR_futex, &who->avail, FUTEX_WAKE, nval, NULL, 0, 0);<br />}<br />}<br /></pre>A few things. This code is gcc specific, I'm using its atomic built-ins. I am using an atomic compare and swap to decrement the count only if doing so would not reduce the count to below zero. I am using an additional count to track if the semaphore ahs been contended. The futex documentation says you should use atomic increments/decrements and treat -1 as being contended. Since this was for my own edification I decided to use a mechanism that I felt was more clear. I would not attempt to use this semaphore in the real world.</div><div><br /></div><div>The basics of the down operation are "Try to atomically decrement the avail member, if that is not possible, note that we are going to wait by incrementing waiters and then wait on the futex. Then decrement waiters and try again." The basics of the up operation are "increment the available count. Additionally if there are waiters, wake as many of them that could proceed given the current count.".</div><div><br /></div><div>Now that we have a semaphore implementation we can endeavorer to come up with a use for it.</div><div><br /></div><div>In this program, we start a child process and wait for it to perform some initialization before using it further. In this example, the initialization is represented by a sleep. main.c:</div><div><span class="Apple-style-span" style="font-family: monospace; font-size: 13px; white-space: pre; "><br /></span></div><div><span class="Apple-style-span" style="font-family: monospace; font-size: 13px; white-space: pre; ">#include <stdio.h></span></div><div><span class="Apple-style-span" style="font-family: monospace; font-size: 13px; white-space: pre; "></span><pre><br />#include <sys/types.h><br />#include <sys/stat.h><br />#include <fcntl.h><br />#include <sys/mman.h><br />#include <stdlib.h><br />#include <assert.h><br /><br />#include "simple_futex.h"<br /><br />int main()<br />{<br />int lockfile = open("ipc_lock", O_RDWR);<br />assert(lockfile != -1);<br />simplefu sema = mmap(NULL, sizeof(*sema), PROT_READ|PROT_WRITE,<br />MAP_SHARED, lockfile, 0);<br />assert(sema != MAP_FAILED);<br /><br />int pid = fork();<br />assert(pid != -1);<br />if( pid == 0 ) { // child<br />printf("Initializing...\n");<br />sleep(10);<br />printf("Done initializing\n");<br />simplefu_up(sema);<br />exit(0);<br />}<br />printf("Waiting for child...\n");<br />simplefu_down(sema);<br />printf("Child done initializing\n");<br /><br />return 0;<br />}<br /><br /></pre>ipc_lock is simply an 8 byte file (the platform specific size of *sema), filled with zeros. You can make your own with <tt>dd if=/dev/zero of=ipc_lock bs=8 count=1</tt>.</div><div><br /></div><div>If we run this guy we get:</div><div><code></code></div><div><div><code>% ./a.out</code></div><div><code>Waiting for child...</code></div><div><code>Initializing...</code></div><div><code>Done initializing</code></div><div><code>Child done initializing</code></div></div><div></div><div><br /></div><div>Now, coming back to the "fast" and "user-space" part of this, if there's no contention, there's no need to make a syscall. We can demonstrate this by using a slightly different program, main2.c The only difference between main2.c and min.c is as follows:</div><div><br /></div><div><br /></div><div><br /></div><div><br /></div><br /><pre><br /><br />% diff -du main.c main2.c<br />--- main.c 2010-11-21 16:57:50.000000000 +0000<br />+++ main2.c 2010-11-21 20:12:24.000000000 +0000<br />@@ -25,6 +25,7 @@<br /> simplefu_up(sema);<br /> exit(0);<br />}<br />+ sleep(15);<br />printf("Waiting for child...\n");<br />simplefu_down(sema);<br />printf("Child done initializing\n");<br /></pre><br /><div>That is, the additional of a sleep(15) call before we start waiting for the child. This represents some other, real work that the other process may be doing at this time instead of waiting for its child to be ready. First, let's confirm that futex is called in the first program:</div><div><br /></div><div><br /></div><br /><pre><br /><br />% strace -o traces ./a.out && grep futex traces<br />Initializing...<br />Waiting for child...<br />Done initializing<br />Child done initializing<br />futex(0xb7861000, FUTEX_WAIT, 0, NULL) = 0<br /></pre>Now, let's compare to the second program, where we're off busy doing something instead of immediately waiting for the child:<div><br /></div><div><br /></div><br /><pre><br /><br />% strace -o traces ./a.out && grep futex traces<br />Initializing...<br />Done initializing<br />Waiting for child...<br />Child done initializing<br /></pre>As you can see, we did not have occasion to actually go to kernel land for this version.<div><br /></div><div>If you are interested in futexes you find out more in the man pages, <a href="http://www.kernel.org/doc/man-pages/online/pages/man2/futex.2.html">http://www.kernel.org/doc/man-pages/online/pages/man2/futex.2.html</a> and <a href="http://www.kernel.org/doc/man-pages/online/pages/man7/futex.7.html">http://www.kernel.org/doc/man-pages/online/pages/man7/futex.7.html</a> as well as the original paper http://www.kernel.org/doc/ols/2002/ols2002-pages-479-495.pdf</div><div><br /></div>Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com2tag:blogger.com,1999:blog-15446379.post-71671484585657396762010-07-20T20:26:00.002-04:002010-07-20T20:29:07.180-04:00Last Call - Tim PowersThis is a book about poker with Tarot cards. If you've ever read a Stephen King book and enjoyed it, especially Dark Tower before it got all meta-fictiony on us, you'll probably like this. Towards the end it does get a little too "and this is how this actually works" which I did not appreciate, but over all a good one.Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com0tag:blogger.com,1999:blog-15446379.post-58378508089241855602008-04-09T18:59:00.002-04:002008-04-09T19:11:43.576-04:00Stupid C++ tricksEver wanted to downcast something, but not too far down? Me either really, but just in case I came up with this:<br /><pre><br />template<typename Target, typename Excluding, typename Source><br />struct exclusive_cast {<br />static Target* cast(Source *s) {<br /> if( ! dynamic_cast<Excluding *>(s) ) {<br /> return dynamic_cast<Target *>(s);<br /> }<br /> return NULL;<br />}<br />};<br /><br />template<typename Ex1, typename Ex2><br />struct ExcludingBoth {};<br /><br />template<typename Target, typename Ex1, typename Ex2, typename Source><br />struct exclusive_cast<Target, ExcludingBoth<Ex1, Ex2>, Source> {<br />static Target* cast(Source *s) {<br /> if( ! dynamic_cast<Ex1 *>( s ) ) {<br /> return exclusive_cast<Target, Ex2, Source>::cast(s);<br /> }<br /> return NULL;<br />}<br />};<br /></pre><br />That was the header, exclusive_cast.hpp. Now here's a little test program that makes sure it does what I think it does:<br /><pre><br />#include <iostream><br />#include "exclusive_cast.hpp"<br /><br />class A {<br /> virtual void rtti_rules() {}<br />};<br />class B : public A {};<br />class C : public B {};<br />class D : public B {};<br />class E : public B {};<br />int main() {<br /> B b;<br /> C c;<br /> D d;<br /> E e;<br /> A *ab = &b;<br /> A *ac = &c;<br /> A *ad = &d;<br /> A *ae = &e;<br /><br /> if( exclusive_cast<B, C, A>::cast(ab) ) {<br /> std::cout << "correct" << std::endl;<br /> } else {<br /> std::cout << "incorrect" << std::endl;<br /> }<br /><br /> if( exclusive_cast<B, C, A>::cast(ac) ) {<br /> std::cout << "incorrect" << std::endl;<br /> } else {<br /> std::cout << "correct" << std::endl;<br /> }<br /><br /> if( exclusive_cast<B, ExcludingBoth<C, D>, A>::cast(ad) ) {<br /> std::cout << "incorrect" << std::endl;<br /> } else {<br /> std::cout << "correct" << std::endl;<br /> }<br /> typedef exclusive_cast<B, ExcludingBoth<C, ExcludingBoth<D, E> >, A> complicated;<br /><br /> if( complicated::cast(ae) ) {<br /> std::cout << "incorrect" << std::endl;<br /> } else {<br /> std::cout << "correct" << std::endl;<br /> }<br /> if( complicated::cast(ad) ) {<br /> std::cout << "incorrect" << std::endl;<br /> } else {<br /> std::cout << "correct" << std::endl;<br /> }<br /> if( complicated::cast(ac) ) {<br /> std::cout << "incorrect" << std::endl;<br /> } else {<br /> std::cout << "correct" << std::endl;<br /> }<br /> if( complicated::cast(ab) ) {<br /> std::cout << "correct" << std::endl;<br /> } else {<br /> std::cout << "incorrect" << std::endl;<br /> }<br /> return 0;<br />}<br /></pre><br /><br />A possible improvement might be to nest the template parameter Source inside the struct for the cast function so wouldn't need to name Source necessarily.Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com0tag:blogger.com,1999:blog-15446379.post-60624760666272511842008-04-04T21:52:00.004-04:002008-04-04T21:56:50.033-04:00Something I wish terminated but doesn'tSure,<br /><code> data Weekday = Sun | Mon | Tue | Wed | Thu | Fri | Sat deriving Enum</code> is fine.<br /><br />But wouldn't it be fun if this actually worked?<br /><code>let as@[sun, mon, tue, wed, thur, fri, sat] = [1..length as]</code>, unfortunately attempt to evaluate mon for instance, and it doesn't terminate (at least as far as I know, I didn't wait for all eternity for it to finish). Needs -XDWIM I suppose.Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com0tag:blogger.com,1999:blog-15446379.post-50387948425118986132007-10-13T16:26:00.000-04:002007-10-13T16:34:47.766-04:00A simple infix calculator in Haskell<p>I saw <a href="http://jcreigh.blogspot.com/2006/11/simple-rpn-calculator-in-haskell.html">this</a> on reddit and knew that my infix calculator was hanging around, so I decided to post it for some contrast. <br /><p>There are a few problems, mainly that I had this desire to "not cheat" when I wrote it so I didn't use nearly as many Parsec functions as I could have. Also it's not very user-friendly, the only way to quit is Ctrl-C or EOF and EOF causes an error to be displayed. That said, here it is in all it's "glory". Compile with ghc --make Main.hs (or whatever you named the file, if you bothered).<br /><pre><br />module Main where<br />import Text.ParserCombinators.Parsec<br />import Control.Monad<br />import Control.Monad.Error<br />import System.IO<br /><br />data Expr a = Number a<br /> | Add (Expr a) (Expr a)<br /> | Mul (Expr a) (Expr a)<br /> | Sub (Expr a) (Expr a)<br /> | Div (Expr a) (Expr a)<br /> | Negate (Expr a)<br /> deriving (Show, Eq)<br /><br />data AddOp = Plus | Minus<br />data MulOp = Times | Over<br /><br />evaluate :: (Fractional a, Monad m) => Expr a -> m a<br />evaluate (Negate x) = liftM negate (evaluate x)<br />evaluate (Div x y) = do x' <- (evaluate x)<br /> y' <- (evaluate y)<br /> if y' == 0 then fail "Division by zero"<br /> else return $ x' / y'<br />evaluate (Sub x y) = liftM2 (-) (evaluate x) (evaluate y)<br />evaluate (Mul x y) = liftM2 (*) (evaluate x) (evaluate y)<br />evaluate (Add x y) = liftM2 (+) (evaluate x) (evaluate y)<br />evaluate (Number x) = return x<br /><br /><br /><br />pDigit = oneOf ['0'..'9']<br />pSign = option '+' $ oneOf "-+"<br />pDigits = many1 pDigit<br />pDecimalPoint = char '.'<br />pFracPart = option "0" (pDecimalPoint >> pDigits)<br /><br />number = do sign <- pSign<br /> integerPart <- pDigits<br /> fracPart <- pFracPart<br /> expPart <- pExp<br /> let i = read integerPart<br /> let f = read fracPart<br /> let e = expPart<br /> let value = (i + (f / 10^(length fracPart))) * 10 ^^ e<br /> return $ Number $ case sign of<br /> '+' -> value<br /> '-' -> negate value<br /> where pExp = option 0 $ do<br /> oneOf "eE"<br /> sign <- pSign<br /> num <- pDigits<br /> let n = read num<br /> return $ if sign == '-' then negate n else n<br /><br />whitespace = many $ oneOf "\n\t\r\v "<br /><br />term = do t <- term'<br /> whitespace<br /> return t<br /> where term' = (try number) <|> negTerm <|> parenExpr<br /><br />negTerm = do<br /> char '-'<br /> whitespace<br /> e <- term<br /> return $ Negate e<br /><br />expr = do<br /> first <- mulTerm<br /> ops <- addOps<br /> return $ foldl buildExpr first ops<br /> where buildExpr acc (Plus, x) = Add acc x<br /> buildExpr acc (Minus, x) = Sub acc x<br /><br />addOp = do operator <- oneOf "+-"<br /> whitespace<br /> t <- mulTerm<br /> return $ case operator of<br /> '-' -> (Minus, t)<br /> '+' -> (Plus, t)<br /><br />addOps = many addOp<br /><br /><br />parenExpr = do char '('<br /> e <- expr<br /> char ')'<br /> return e<br /><br />mulTerm = do first <- term<br /> ops <- mulOps<br /> return $ foldl buildExpr first ops<br /> where buildExpr acc (Times, x) = Mul acc x<br /> buildExpr acc (Over, x) = Div acc x<br /><br />mulOp = do operator <- oneOf "*/"<br /> whitespace<br /> t <- term<br /> return $ case operator of<br /> '*' -> (Times, t)<br /> '/' -> (Over, t)<br /><br />mulOps = many mulOp<br />calculation = do whitespace<br /> e <- expr<br /> eof<br /> return e<br /><br />evalPrint s = case (parse calculation "" s) of<br /> Right x -> case evaluate x of<br /> Right v -> print v<br /> Left err -> putStrLn $ "Error: " ++ err<br /> Left err -> putStr "parse error at " >> print err<br /><br />main = getLine >>= evalPrint >> main<br /></pre>Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com0tag:blogger.com,1999:blog-15446379.post-68749644534886015902007-06-09T09:08:00.000-04:002007-06-13T10:39:03.951-04:00The Church Code<p>You may have heard of the lambda calculus, in which everything is a function. And you may have asked yourself, as I have, ok that's great, but I how do I do anything with just functions? How do I create all those datastructures I've become acustommed to? Do I need to build the datastructures I've become accustomed to? If so, how do I do it?<br /><p>One answer to this question, is the Church encoding, named after Alonzo Church who first came up with the idea. So how do you use Church encoding?<br /><p>Well, before I get into that I'm going to describe the environment I'm going to use. I'm going to use the ruby programming language, because it's familar to me, and Haskell's type system makes it difficult to use Church encoding. Secondly I'm gonna define a convience method in ruby called curry:<br /><pre><br />def curry(&l)<br /> lambda { |a| lambda { |b| l[a,b] } }<br />end<br /></pre><br /><br /><p><tt>curry</tt> takes a block of two arguments and transforms it into a Proc w/ a single argument that returns another Proc of a single argument. This is just to save me typing later. <br /><p>Now that that's out of the way we can start talking about how to turn our functions into values. Consider one of the simplest values in most programming languages, true and false. <br /><pre><br /># we are going to use the names ctrue and cfalse because<br /># ruby takes exception to our using true and false<br /># as variables<br />ctrue = curry { |a,b| a }<br />cfalse = curry { |a,b| b }<br /></pre><br /><p>Now if you didn't stop reading a while ago because you already know all about this stuff, you may be wondering, how are those functions true and false? Actually, let's just make sure that curry method makes sense first.<br /><pre><br />curry { |a,b| a } --><br />lambda { |a| lambda { |b| a } }<br /># So to call ctrue we'd do the following:<br />ctrue[1][0] #=> 1<br /></pre><br />The reason for currying all these functions should become clear fairly soon. Now that that's out of the way, how does this give us true and false? Well, think about an if statement. Now imagine if was defined as a function, like the following:<br /><pre><br />cif = lambda { |condition| curry { |true_branch, false_branch|<br /> condition[true_branch][false_branch] } }<br /></pre><br /><br />Now we can for instance write not:<br /><pre><br />cnot = lambda { |cond| cif[cond][cfalse][ctrue] }<br /></pre><br /><br />Now if you've picked up on what's going on with cif you've realized that it's not really necessary. <tt>ctrue</tt> and <tt>cfalse</tt> are true and false, and they are also if.<br /><br />So we can write <tt>cnot</tt> as <br /><pre><br />cnot = lambda { |cond| cond[cfalse][ctrue] }<br /></pre><br />And if we cheat for a moment, we can discover which value a given church encoded boolean is by using the following function<br /><pre><br />cbool_to_rbool = lambda { |cond| cond[true][false] }<br /></pre><br /><br />Now we can make sure our <tt>cnot</tt> method works<br /><pre><br />>> cbool_to_rbool[ctrue]<br />=> true<br />>> not_ctrue = cnot[ctrue]<br />=> #<Proc:0x02b9876c@(irb):1><br />>> cbool_to_rbool[not_ctrue]<br />=> false<br /></pre><br /><p>So now what? We've managed to come up with bools out of functions. Doesn't seem very useful yet, although maybe kind of entertaining.<br /><br /><p> Well we can now also define and and or. A and B is true if A is true and B is true. Put another way, A and B is true if neither A nor B are false.<br /><pre><br />cand = curry { |a,b| a[b][a] }<br /></pre><br />So let's walk through this function<br />if a is true, it will take a the left value and give us b. If b is true, we have true and true -> true, which is what we wanted. if b is false, we have true and false -> false which is again, what we wanted. If a is false, we get a so we had false and <i>anything</i> -> false, which is what we want as well.<br /><p>Next we can define or.<br /><pre><br />cor = curry { |a,b| a[a][b] }<br /></pre><br /><p>If is a true, we get a, if a is false we get b. Therefore we will only get a false result if both a and b are false. Now that we have and, or and not, we can build boolean operation (xor, etc.), and we've done it using only functions. No datastructures in sight.<br /><p>The next thing we are going to try, is to create some datastructures out of pure functions. The first thing we will create is a pair, that is a list of two values.<br /><pre><br />cpair = curry { |a,b| lambda { |f| f[a][b] } }<br />cfst = lambda { |apair| apair[ctrue] }<br />csnd = lambda { |apair| apair[cfalse] }<br /></pre><br /><p><tt>cpair</tt> is a 3 argument function, it takes the first value for the pair, the second value for the pair, and a function that takes two arguments to use the pair.<tt>cfst</tt> will let us extract the first value from a pair, and <tt>csnd</tt> will allow us to extract the second value from a pair. Let's try it out:<br /><pre><br />>> pair_of_values = cpair["Ok"][5]<br />=> #<Proc:0x02b7ec40@(irb):12><br />>> csnd[pair_of_values]<br />=> 5<br />>> cfst[pair_of_values]<br />=> "Ok"<br /></pre><br /><p>Now you can see the purpose of using curried functions. It makes it easier for us to partially apply our functions so we can perform multiple operations with an argument of true, selecting the first value. You can also see that we can if we want create tuples of any arity. Since we already have true and false, one way to encode numbers could be to have an N-tuple of bits (true and false) and define the arithmetic operators in terms of logical operations on bits, like the way the ALU of a processor works. An interesting idea, but this is not how Church actually defined numbers with functions.<br /><p>Instead, he represented natural numbers as the nth composition of a function with itself:<br /><pre><br />zero = curry { |f, x| x }<br />one = curry { |f,x| f[x] }<br />two = curry { |f,x| f[f[x]] }<br /></pre><br />Writing this definitions can be a bit tedius, so we can define a successor function:<br /><pre><br />succ = lambda { |n| curry { |f,x| f[n[f][x]] } }<br />three = succ[two]<br />four = succ[three]<br />.<br />.<br />.<br /></pre><br />We also define a function to convert our church numerals to ruby integers so we can see what's going on:<br /><pre><br />cnum_to_rnum = lambda { |n| n[lambda { |x| x + 1 }][0] }<br /><br />>> cnum_to_rnum[two]<br />=> 2<br /></pre><br />What's happening is that n is composing the function lambda { |x| x + 1 } n times, so in the case of two, it is twice. We then feed it an initial value of zero, so 0 + 1 + 1 = 2.<br /><p>We can also add our church numerals<br /><pre><br />plus = curry { |m,n| curry { |f,x| m[f][n[f][x]] } }<br /><br />>> cnum_to_rnum[plus[two][four]]<br />=> 6<br /></pre><br /><p>We can also define multiplication, a predecessor function etc. But I'm getting bored of church numerals so lets move on into how you create algebraic data types. This is going to allow us to create linked lists, trees, pretty much any data structure you can have in a pure functional language.<br /><p>In Haskell, there is a type Maybe a, (ML has the same type, only they spell it 'a option). The definition in Haskell looks like:<br /><pre><br />data Maybe a = Just a | Nothing<br /></pre><br />That is, any value of Maybe Int for instance will either be <tt>Nothing</tt> or <tt>Just <i>some integer value</i></tt>.<br /><p>We can define this same data structure using just functions. Each constructor, <tt>Just</tt> and <tt>Nothing</tt> will be a function. Each value of Maybe a will be a function that takes a function (a -> b) and a value ( b ).<br /><pre><br />just = lambda { |value| curry { |f,x| f[value] } }<br />nothing = curry { |f,x| x } # if you recall this is also the definition of cfalse<br /></pre><br /><p>Haskell also has a type Either a b whose definition looks like:<br /><pre><br />data Either a b = Left a | Right b<br /></pre><br /><p>You may have noticed that Maybe a is just a special case of Either a b where we don't care about the second value. Again, we can define this type using only functions. We will have two functions left and right. Both will take a value, and return a function that takes two arguments, two functions, one from a to c and the other from b to c.<br /><pre><br />left = lambda { |value| curry { |f,g| f[value] } }<br />right = lambda { |value| curry { |f,g| g[value] } }<br /></pre><br /><p>Given that an N-tuple can be represented in pairs, and that nested Eithers give us all the sum-types we need we can represent almost any datatype you can define in Haskell (barring things like strictness annotations, FFI, etc.) using pure functions.<br /><p>For instance, we can define a linked list. In Haskell the definition might look like:<br /><pre><br />data List a = Cons a (List a) | Empty<br /></pre><br />Like maybe or either we will have two constructor functions cons, and empty<br />cons will take two inputs, a head and a tail and return a function taking two functions. The first one will take as parameters the head and the tail, the second will be a value to use if the list is empty. Empty will simple be a function that takes two functions, with the same parameters as the function returned by cons.<br /><pre><br />cons = curry { |h,t| curry { |cf, ev| cf[h][t] } }<br />empty = curry { |cf, ev| ev }<br /></pre><br /><p>Now we can write <tt>first</tt> and <tt>rest</tt> to get the first item of the list<br />and the rest of the list:<br /><pre><br />first = lambda { |alist| alist[ctrue][nil] }<br />rest = lambda { |alist| alist[cfalse][nil] }<br /><br />>> list = cons[1][cons[2][empty]]<br />=> #<Proc:0x00002b4d4a52aa18@(irb):1><br />>> h = first[list]<br />=> 1<br />>> t = rest[list]<br />=> #<Proc:0x00002b4d4a52aa18@(irb):1><br />>> first[t]<br />=> 2<br /></pre><br /><p>We can also write the function <tt>map</tt> for instance:<br /><pre><br />map = curry { |f,l| l[curry { |h,t| cons[f[h]][map[f][t]] }][empty] }<br /><br />>> l2 = cons[1][cons[2][cons[3][empty]]]<br />=> #<Proc:0x00002b1909def588@(irb):10><br />>> l3 = map[lambda { |x| x.to_s }][l2]<br />=> #<Proc:0x00002b1909def588@(irb):10><br />>> first[l3]<br />=> "1"<br />>> first[rest[l3]]<br />=> "2"<br />>> first[rest[rest[l3]]]<br />=> "3"<br /></pre><br /><p>Given that we've defined church numerals earlier we can of course use them instead of<br />ruby numbers. Strings can be represented as lists of characters, and characters as integers, which again can be represented using church numerals. Basically, all you need are functions. I hope you've learned something, or were at least mildly entertained.Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com6tag:blogger.com,1999:blog-15446379.post-6004133781210537672007-06-02T03:53:00.000-04:002007-06-02T04:04:04.422-04:00Let's eval some stringsList comprehensions are neat, but ruby doesn't have em. That's ok, we've got string eval!<br /><br /><pre><br />module Enumerable<br /> def concat_map(&f)<br /> inject([]) { |a, b| a.concat(f.call(b)) }<br /> end<br />end<br /><br /><br />def guard( b )<br /> if b<br /> [nil]<br /> else<br /> []<br /> end<br />end<br /><br />def r( v )<br /> [v]<br />end<br /><br />def comp( s, b = binding )<br /> before_bar, after_bar = s.split("|")<br /> before_bar.gsub!(/\A\s*\[/, '')<br /> after_bar.gsub!(/\]\s*\z/, '')<br /> components = after_bar.split(/;/)<br /> gen_exprs, guard_exprs = components.partition { |e| e =~ /<-/ }<br /> final = "r(#{before_bar})"<br /> final = guard_exprs.reverse.inject(final) { |s, e| "guard(#{e}).concat_map { #{s} }" }<br /> final = gen_exprs.reverse.inject(final) { |s, e|<br /> var, expr = e.split("<-").map { |c| c.strip }<br /> "(#{expr}).concat_map { |#{var}| #{s} }"<br /> }<br /> eval(final,b)<br /> #final<br />end<br /></pre><br /><br />See, easy?<br /><br />Now we can do things like:<br /><pre><br />def factors( n )<br /> comp "[ [x,y] | x <- (1..n) ; y <- (1..n) ; x * y == n ]", binding<br />end<br /></pre><br /><br />If we do <tt>factors 25</tt> we get <tt>[[1, 25], [5, 5], [25, 1]]</tt>.<br /><br />We can also write "quicksort" (being that not so great list comprehension quicksort that I'm sure you've seen before:"<br /><pre><br />def qsort( a )<br /> if a.length < 2<br /> a<br /> else<br /> pivot = a.first<br /> tail = a[1..-1]<br /> b = binding<br /> qsort(comp("[ x | x <- tail ; x < pivot ]", b)) + [pivot] + qsort(comp("[ y | y <- tail ; y >= pivot ]", b))<br /> end<br />end<br /></pre><br /><br />And of course we write a cartesian product function:<br /><br /><pre><br />def cart_prod(a, b)<br /> comp "[ [x,y] | x <- a ; y <- b ]", binding<br />end<br /></pre><br /><br />By the way the code that this expands to is:<br /><pre><br />(a).concat_map { |x| (b).concat_map { |y| r( [x,y] ) } }<br /></pre><br /><br />Of course we could've written all these functions before, w/o list comprehensions but this was more fun.Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com0tag:blogger.com,1999:blog-15446379.post-35265234544554562092007-05-04T23:00:00.000-04:002007-05-04T23:03:52.726-04:00Abuse: Is it ruby? Is it Haskell? It's both!<pre><br />=begin<br /><br />> puts = return ()<br />> main = do let (.) = flip ($)<br /><br />=end<br />eval <<HERE.gsub(/^>/, '')<br /><br />> print([1,2,3].length)<br />> puts<br /><br />HERE<br /></pre><br /><br />Save to somefile.lhs<br /><br />Run with ruby something.lhs<br />runhaskell something.lhsLogan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com0tag:blogger.com,1999:blog-15446379.post-1165726790683698012006-12-09T23:58:00.000-05:002006-12-09T23:59:50.693-05:00How Arrays Work In RubyWKC CCC <wai-kee.chung@uk.bnpparibas.com> wrote:<br /><br />> unknown wrote:<br />> > WKC CCC <wai-kee.chung@uk.bnpparibas.com> wrote:<br />> > <br />> >> <br />> >> count = count + 1<br />> >> end<br />> >> <br />> >> puts one.inspect<br />> > <br />> > Array.new(array) copies the *array* but it does not copy its *elements*.<br />> > So tempArr[0] is another name for the very same object as one[0], and so<br />> > forth. m.<br />> <br />> If they are referring to the same object, why is it when<br />> <br />> tempArr = Array.new(one)<br />> one.clear<br />> <br />> results in tempArr still having the values originally assigned to array<br />> one?<br /><br />Reread what I said. I didn't say that tempArr and one refer to the same<br />object; I said that tempArr[0] and one[0] (and so on) refer to the same<br />object.<br /><br />Think of it this way. Items in an array are dogs. Arrays are people<br />holding leashes. Anyone can attach a leash to a dog. So I (tempArr) can<br />have a leash on Fido, and so can you (one). If you let go of your leash<br />(one.clear), Fido is still Fido; you just don't have a leash on him. But<br />if you cut off one Fido's legs (modify one[0]), that leg on my Fido<br />(tempArr[0]) is also cut off, because they are the same Fido.<br /><br />m. <br /><br />-- <br />matt neuburg, phd = matt@tidbits.com, http://www.tidbits.com/matt/<br />Tiger - http://www.takecontrolbooks.com/tiger-customizing.html<br />AppleScript - http://www.amazon.com/gp/product/0596102119<br />Read TidBITS! It's free and smart. http://www.tidbits.comLogan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com0tag:blogger.com,1999:blog-15446379.post-1165329209772471022006-12-05T08:41:00.000-05:002006-12-05T09:34:14.850-05:00Monads in Ruby Part 2: Maybe (then again Maybe not)So here's when things start to get interesting. Today I'm going to discuss the maybe monad. In Haskell, the maybe type is used for computations that might fail. An example of this in ruby would be the #index method on arrays. In ruby index returns either the index of the passed in item in the array, or nil if the item is not in the array. Haskell is statically typed so variables can only hold one type of data. This means we can't return a 3 or a nil. Instead we have the maybe type which looks like <tt> data Maybe a = Just a | Nothing </tt>. So index would return a Maybe Integer. e.g:<br /><pre><br />index "hello" ["world", "planet", "hello", "hi"] --> Just 2<br />index 25 [3,4,5] --> Nothing<br /></pre><br /><br />What does this have to do with monads you may be wondering? Well, just like identity, the maybe type is a monad. In fact maybe is a monad with some extra features, an instance of MonadPlus. We'll come back to that. But first a detour in ruby land. You may have seen something like this:<br /><pre><br />class NilClass<br /> def method_missing(*args, &block)<br /> nil<br /> end<br />end<br /></pre><br />This is sometimes called the null pattern, and it makes Ruby's nil act like Objective-C's. That is, nil will just swallow messages it doesn't understand. The general opinion among the ruby community is that this is a Bad Idea (tm). I would tend to agree with that idea. It's also not as useful as it might initially appear, consider 1 + nil. <br /><br />This pattern however is superficially similar to how Maybe works in Haskell as a monad. I mentioned earlier that maybe was an instance of MonadPlus. This means it supports two additional operations, mzero and mplus. mzero, acts as you might guess from it's name as a zero. mzero mplus anything will always be the anything. Likewise if you think of the bind operation (discussed last time) as a sort of multiplication, mzero bind f will always be mzero. For the maybe monad, Nothing is mzero.<br /><br />So if I define<br /><pre><br />class Array<br /> def maybe_index( obj )<br /> i = index( obj )<br /> if i<br /> Maybe.Just( i )<br /> else<br /> Maybe.Nothing<br /> end<br /> end<br />end<br /></pre><br /><br />I can now change the first 3 in an array for instance into a 4, with no need for error checking:<br /><pre><br />a = [1,3,5]<br />b = Maybe.m_bind( a.maybe_index( 3 ) ) { |i| a1 = a.dup; a1[ i ] += 1; Maybe.m_return( a1 ) }<br /></pre><br /><br />So b will either be Just [1,4,5] or Nothing. Either way, we had no opportunity to index an array by nil, and no need to litter our code with if statements. (What we did litter our code with was quite a bit more verbose, but you win some you lose some.)<br /><br />Now, you must be wondering, what about this mplus business? Well let's same you need to address someone. If you know their nickname, you'd like to use that, if you don't know their nickname, you'd like to use their first name, and if you don't know their first name, you'd like to use their last name (which you know you'll always have). So how do we do this? We get all three and mplus the results together:<br /><pre><br />class Hash<br /> def maybe_fetch( key )<br /> if has_key? key<br /> Maybe.Just(self[key])<br /> else<br /> Maybe.Nothing<br /> end<br /> end<br />end<br /><br />person1 = { :nick => 'Big Joe', :first => 'Joseph', :last => 'Smith' }<br />person2 = { :last => 'Baggins' }<br /><br />greeting1 = Maybe.mplus( Maybe.m_bind( person1.maybe_fetch( :nick ) ) { |nick| Maybe.m_return("Hey, #{nick}") },<br /> Maybe.mplus( Maybe.m_bind( person1.maybe_fetch( :first ) ) { |first| Maybe.m_return("Hi, #{first}") },<br /> Maybe.m_bind( person1.maybe_fetch( :last ) ) { |last| Maybe.m_return("Hello, Mr. #{last}") }))<br /><br />puts greeting1.from_just<br /><br />greeting2 = Maybe.mplus( Maybe.m_bind( person2.maybe_fetch( :nick ) ) { |nick| Maybe.m_return("Hey, #{nick}") },<br /> Maybe.mplus( Maybe.m_bind( person2.maybe_fetch( :first ) ) { |first| Maybe.m_return("Hi, #{first}") },<br /> Maybe.m_bind( person2.maybe_fetch( :last ) ) { |last| Maybe.m_return("Hello, Mr. #{last}") }))<br /><br />puts greeting2.from_just<br /><br /></pre><br /><br />This is similar to something like<tt>p1[:nick] || p1[:first] || p1[:last]</tt> in your standard ruby idiom, but note how I also transformed each value differently. And this code won't misevaluate due to things like nil being false or "" being true. The effect is localized entirely to the semantics you give it. This also means that you won't easily run into the major problem of the null pattern in that it runs away with you. It's very easy to contain this to a small section of code.<br /><br />Before I post the code, I'm going to make one small note. I've decided not to bother with writing "type-safe" versions of this monads anymore. a) They aren't really type-safe anyway and b) classes aren't types, especially not in Ruby. It's a losing battle, so I think that to use monads in ruby you'll unfortunately have to rely more on self-discipline and less on type-checking.<br /><br /><pre><br />class Maybe<br /> def initialize(*args)<br /> if args.length > 1<br /> raise ArgumentError, "Expected 0 or 1 arguments, got #{args.length}"<br /> end<br /><br /> @nothing = args.empty?<br /> @val = args.first<br /> end<br /><br /> def nothing?<br /> @nothing<br /> end<br /><br /> def from_just<br /> raise "Maybe pattern match failure" if nothing?<br /> @val<br /> end<br /><br /> def self.Just( v )<br /> new(v)<br /> end<br /><br /> def self.Nothing<br /> new<br /> end<br />end<br /><br /># Monad stuff<br />class Maybe<br /> def self.m_bind(maybe_a)<br /> if maybe_a.nothing?<br /> Maybe.Nothing<br /> else<br /> yield(maybe_a.from_just)<br /> end<br /> end<br /><br /> def self.m_return(v)<br /> Maybe.Just v<br /> end<br /><br /> def self.mplus(a, b)<br /> if a.nothing?<br /> b<br /> else<br /> a<br /> end<br /> end<br />end<br /></pre>Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com2tag:blogger.com,1999:blog-15446379.post-1165199072940613072006-12-03T21:21:00.000-05:002006-12-03T21:24:46.503-05:00Monads In Ruby Part 1.5: IdentitySo after chatting in #haskell on freenode it became apparent that my Identity monad was kind of a cheat. It wasn't a function from types to types. So I present here for comment, a modified version, that pretends that ruby has parametric types:<br /><pre><br />% cat identity.rb<br />$implementation_detail = {}<br />def Identity(klass)<br /> $implementation_detail[klass] ||= Class.new do<br /> define_method :initialize do |obj|<br /> @obj = obj<br /> end<br /><br /> define_method :m_bind do |f|<br /> r = f.call( @obj )<br /> raise TypeError, "Bind did not type check" unless r.kind_of? Identity(klass)<br /> r<br /> end<br /><br /> (class << self; self; end).class_eval {<br /> define_method :m_return do |obj|<br /> raise TypeError, "#{obj} not instance of #{klass}" unless obj.kind_of? klass<br /> self.new( obj ) <br /> end<br /><br /> define_method :name do<br /> "Identity(#{klass})"<br /> end<br /><br /> alias_method( :to_s, :name )<br /> alias_method( :inspect, :name )<br /> }<br /> end<br />end<br /><br />p Identity(Array).m_return( [1, 2, 3] ).m_bind( lambda do |a|<br /> Identity(Array).m_return( [3] + a[1..-1] )<br />end)<br /><br /><br /><br /><br />% ruby identity.rb<br />#<#<Class:0x1eb3b0>:0x1eaff0 @obj=[3, 2, 3]><br /><br /></pre>Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com0tag:blogger.com,1999:blog-15446379.post-1165194848221103292006-12-03T19:47:00.000-05:002006-12-03T20:14:08.290-05:00Monads in Ruby Part 1: IdentityJust to get this out of the way, yes it's been done before: http://moonbase.rydia.net/mental/writings/programming/monads-in-ruby/00introduction.html<br /><br />In order to better understand the various monads available in Haskell, I've been re-implementing them in Ruby. Thus far I've done Identity, List (well Array), Maybe and State. Today I'm going to show you the Identity monad. A monad is a framework of sorts for applying rules to a series of computations. A monad has at least two operations, bind and return. return takes a non monadic value and converts it to a monadic one, it has type:<br /><tt> (Monad m) => a -> m a </tt><br />(I'm using Haskell type notation here because ruby doesn't have type notation ;) )<br /><br />Bind takes a monadic value and de-monadifies it to feed it into a function that returns a monadic value. It has the type:<br /><tt> (Monad m) => m a -> (a -> m b) -> m b </tt><br /><br />Bind is where the magic happens. Haskell uses it's type system to ensure that every sequence of computations in a given monad goes through bind. Bind therefore lets the writer of the monad decide the rules for the little monadic world within a given program. (This is how Haskell deals with side-effects (IO) ).<br /><br />So now without further ado, I present the Identity monad:<br /><pre><br />class Identity<br /> def initialize( val )<br /> @val = val<br /> end<br /><br /> def self.m_return( a )<br /> Identity.new( a )<br /> end<br /><br /> def self.m_bind(id_a, &f)<br /> f.call( id_a.val )<br /> end<br /><br /> def val<br /> @val<br /> end<br />end<br /></pre><br /><br />Short and sweet. All you can really do with an Identity monad is force evaluation order. Ruby is imperative so that doesn't really matter.<br /><br />Here's some code using Identity:<br /><pre><br />Identity.m_bind( Identity.m_return( 1 ) ) do |x| # x is 1, we've sucked it out of the Monad.<br /> Identity.m_return( x + 1 )<br />end<br /></pre><br /><br />This is quite verbose. In Haskell it would be <tt>return 1 >>= (\x -> return x + 1)</tt>, where <tt>>>=</tt> is bind and <tt>(\x -> ... )</tt> is analogous to <tt>lambda { |x| ... }</tt>. Haskell also has some syntactic sugar for monadic expressions like this. Using the the syntactic sugar it would look like:<br /><br /><pre><br />let i = return 1 in<br /> do x <- i<br /> return x + 1<br /><br /></pre><br /><br />The real difference of course is the type checking. If I wrote <tt>return 1 >>= (\x -> x + 1)</tt> in Haskell it would not compile where ruby cares not a whit if we want to escape our monads. That combined with the fact that unlike Haskell we have no syntactic sugar for monads means it's going to be difficult to debug our ruby implementations. Hopefully I've whet your appetite, next time we'll tackle the Maybe monad, that allows us to handle computations that might fail.Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com3tag:blogger.com,1999:blog-15446379.post-1164922168666754532006-11-30T16:26:00.000-05:002006-11-30T16:29:28.680-05:00Seen in #ruby-lang[4:21pm] <tpope> blink, less +F<br />[4:21pm] <teferi> tpope: I just SUGGESTED that<br />[4:21pm] <blink> technomancy: ssh+screen+tail, and doing an escape to copy mode everytime i want tos croll back is a hassle.<br />[4:21pm] bingeldac joined the chat room.<br />[4:21pm] <tpope> well good for you<br />[4:22pm] <blink> teferi: oh, i thought you were referring to tail -F<br />[4:22pm] <technomancy> if you say so<br />[4:22pm] langenberg_ left the chat room. (Connection timed out)<br />[4:23pm] <LoganCapaldo> he<br />[4:23pm] <LoganCapaldo> it's funny how you can man less and search for tail and get relevant info<br />[4:23pm] <blink> teferi: heeeeee, it works in conjuction with the F command within less. thank you.<br />[4:23pm] <blink> LoganCapaldo: i didn't se anything, so i decided to ask some geeks :P<br />[4:24pm] <simplicoder> a manless search for tail?<br />[4:24pm] <blink> simplicoder: i do that all the time.Logan Capaldohttp://www.blogger.com/profile/08200960657931329509noreply@blogger.com0