Planet Haskell without Tom Moertel's postsPipes Output
http://pipes.yahoo.com/pipes/pipe.info?_id=Jti_id1G3hGa1KrxdPQQIA
Wed, 30 Jul 2014 19:13:20 +0000http://pipes.yahoo.com/pipes/Transitioning is a mindfuck.
http://winterkoninkje.dreamwidth.org/97220.html
[Content warning: discussion of rape culture and child abuse]
Transitioning is a mindfuck. Doesn't matter how prepared you are, how sure you are, how long and deeply you've thought about gender/sexuality issues. Outside of transitioning1 we have no way of inhabiting more than one position in any given discourse. Sure, we can understand other positions on an intellectual level, we may even sympathize with them, but we cannot empathize with what we have not ourselves experienced, and even having experienced something in the past does not mean we can continue to empathize with it in the present. Julia Serano emphasizes this epistemic limit in her books. And it's no wonder that no matter how prepared you may be, completely uprooting your sense of self and reconfiguring the way the world sees, interprets, and interacts with you is going to fundamentally alter whatever notions you had going into it all.
Since transitioning none of the major details of my identity have changed. I'm still a woman. Still feminine. Still a flaming lesbo. Still kinky, poly, and childfree. Still attracted to the same sorts of people. Still into the same sorts of fashion (though now I can finally act on that). Still interested in all the same topics, authors, and academic pursuits. And yet, despite —or perhaps because of— all this consistency, transitioning is still a mindfuck.
Some thing have changed, in subtle, nuanced, insidious ways. For example, I'm even more attracted to women now than I used to be. (how's that even possible?!) And the tenor of that attraction has changed. I knew I liked girls in a gay way since very early on. I've thought of myself as a lesbian since at least 7th grade (when I learned the word)— without really noticing that calling myself a dyke kinda sorta entails I'm a woman, and well before I understood that feeling like a girl meant I was trans. The funny thing is, in addition to liking girls in a gay way, I also liked them in a straight way. These two forms of attraction feel quite different from one another and, even when both directed at the same target, were easily distinguishable. I use the past tense because since starting HRT my heterosexual attraction to women has decreased over time, zeroing out over the past couple-few months. (Whereas my homosexual attraction to women has increased correspondingly.) This whole experience throws a major wrench into our standard conceptions about "orientation", but that's a topic for another time.
By and large this change hasn't affected who I'm attracted to, except around the periphery. Nevertheless, it has had noticeable effects on my interactions with people. Thanks to the other effects of HRT, the dykes I've always been attracted to have started noticing me. And the increase in my attractions has imbued many of my favorite haunts with a new sexual energy that wasn't there before. It's all very nice, but it takes some getting used to. Suddenly everywhere there's a subtext of queer life I was never privy to, even when living the scene in Portland.
Other things have changed, not so much in myself, but in the ways I am interpreted. In my pre-transition life, I put a lot of myself into raising awareness for the fact that men too are victims of sexual violence, and that men too suffer from depression2. As a survivor of sexual abuse and depression, and as someone who was then-read as being a "man", this raising of awareness was necessary to make a place for myself in the world— especially in feminist and activist circles. Throughout the 1990s and early 2000s as feminist were raising awareness about rape culture, the very same (pseudo)feminists engaged in a discourse of silencing and exclusion against male victims of sexual violence. Opposing this discourse and asserting the right of male survivors to be included in the dialogue surrounding rape culture was a major component of my activism at the time. By disavowing the impact of rape culture and silence culture on men, these pseudofeminists were reinscribing the very culture they sought to raise awareness of. That "feminists" would so blatantly support rape culture is abhorrent. More to the point, this hypocrisy has had very real consequences. Much of the current MRA movement originated from male feminist communities— and many of those male feminist communities were explicitly constructed in order to combat the silencing and marginalization of male survivors by pseudofeminists. The inability of feminists of the 1990s to include men in the discourse on rape culture was foundational to the construction of the MRA movement we must now fight against.
I fought this hypocrisy for years, to the point where I was made a public target in much the same way that TERFs publicly target trans women3. And as pseudofeminists grew ever more entrenched in their erasure of sexual violence against men, I watched as male feminist communities were co-opted and poisoned by the nascent MRA movement. After years of this targeted silencing, I had no choice but to give up on "feminism" entirely, retreating in order to retain and rebuild my sense of self. I alluded to this history earlier, and it took me a decade of isolation before I was willing to engage with feminist communities again. Thankfully much has changed in the meantime, and now "feminist" communities are much more likely to be feminist communities (so far as I've seen). But it's not just the community that has changed. Now when I engage with feminists I am read as being a woman, and my words are received very differently now than before. The lack of alienation is liberating, but at the same time I feel disattached from my history of involvement with feminism. Now, if I argue for the inclusion of men in the discourse on rape culture, I am seen as making this argument from a female positionality; as such, women are far more likely to listen to me, but it feels as though (on this topic in particular) they are less likely to hear what I am saying. As a woman, when I assert that men are often victims of sexual violence and that rape culture has a doubly silencing effect on men since —due to masculine-centrism and homophobia— this violence attacks their gender and sexual identities in addition to the personal, physical, and psychic violation, my words are not received with the same authority as when I uttered those self-same words fifteen years ago. These days it's taken as a position statement, as philosophy, as theory, not as the gritty dirt of reality.
Moreover, these days I do not feel like I can legitimately invoke my personal history in order to receive that authority. The idea of doing so reeks of entitlement and disingenuity. While I do not feel like I would be co-opting the experiences of male survivors, claiming to have any access to male experience now feels deeply inauthentic. All of this despite having experienced the very same things as many men do. My abuser was a woman, and like men who were abused by women, people tried to gaslight me into calling it "getting lucky" instead of calling it rape. Despite having no interest in adopting a male persona, if my history became known it would incur (additional) emasculating, homophobic, and transphobic abuse. The only way to avoid that abuse was to actively position myself as a straight masculine man full of machismo and bravado. Thus, I could either deny myself by masking over my history or I could deny myself by masking over my identity; a devil's choice if ever there was one. Being a queer feminine woman, this devil's choice becomes a twisted form of psychological torture, as the masking identity is the antithesis of who I am, and is moreover an identity I find repugnant; to actively adopt this grotesquery requires I must dehumanize myself, dissociating from everything that gives me nourishment and willfully engaging in degrading acts. While most male survivors of sexual violence are not queer feminine women, those men I have talked to still experienced the devil's choice as psychological torture and for very similar reasons of being forced to actively deny their own identities in order to project an identity they find repulsive. Despite sharing these experiences with cis men and not having had the experiences typical of cis women who've endured sexual violence, I no longer feel like I can authentically access these experiences to speak to the trauma that men endure. At the same time, while it does now feel authentic to frame my history as the sexual abuse of a girl by another girl (for we were both underage), I know that this authenticity does not afford any legitimacy outside of discussing my own experiences. Before, I was silenced by having my experiences excluded from the discourse on rape culture; now, even when listened to, I am silenced by not having a discourse to which my experiences can contribute.
Once again I point out that none of the major details of my identity nor of my history have changed. Who I was at the time of my abuse is no different today than it was a year and a half ago before I transitioned. No new details have come to light. I have not altered my interpretation of that past. In short, nothing has changed. And yet, it seems, everything has changed. As I tweeted yesterday, "even having had clarity for so long, doesn't really seem to help. Clinging to old narratives can become disingenuous." And now I wrestle with that disingenuity, seeking to construct a new narrative to make coherent the detritus of my life. Learning how to position myself as I walk the same paths through the same queer communities I've inhabited all my life. Learning how to vocalize a troubled history I've openly discussed for decades. Learning, somehow, to become the person I have always been, because suddenly nothing has changed.
[1] I do not mean to claim that only transsexuals have the ability to inhabit multiple positions over their lives, rather I mean transitioning in a more general sense. In Self-Made Man Nora Vincent, a cis woman, describes her 18 months posing as a man. This wasn't 18 months of RLE living as a man, but only workaday posing/living as a man. Still, reading her book, it should be clear that this is sufficient to grasp at the immense complexity of how our different positions give rise to very different lived experiences (even if, in the end, Vincent falls back on biological essentialism rather than fully internalizing her experiences). The fact that these 18 months caused her to have a nervous breakdown should be indication enough of how profoundly trans people are affected both by their pre-transition life and by the transition itself. ↩
[2] Throughout the 1990s depression was considered a "woman's disease". As such, many feminist circles at the time were engaged in raising awareness about depression as part of the overarching women's health movement. I don't say much here about my involvement in these groups because, unlike the situation regarding male survivors of sexual violence, feminists raising awareness about depression were welcoming to men and very receptive to male voices and male experiences. ↩
[3] With the important difference that the vast majority of self-proclaimed "feminists" these days are not TERFs, whereas a great many of the self-proclaimed "feminists" in the 1990s were male-exclusionary. Were I to hazard a guess, I'd say that about 20–40% of the online community were actively male-exclusionary, as many as 60–80% of the active community were willing to tolerate or incidentally support their behavior, and less that 5% were willing to actively oppose male-exclusionary behavior. By the late 2000s these proportions had changed significantly since the goals of male-exclusion were, by and large, deemed successful by that point and so were no longer a major point of contention. However, my brief forays into the community at that time indicated that it still wasn't particularly hospitable to girls like me. ↩
Twitter
Facebook
Google+
Tumblr
WordPress
commentstag:dreamwidth.org,2010-05-25:518115:97220Wed, 30 Jul 2014 09:58:23 +0000Suresh Venkatasubramanian criticizes the role of…
http://wadler.blogspot.com/2014/07/suresh-venkatasubramanian-criticizes.html
Suresh Venkatasubramanian criticizes the role of ACM in today's research community, in an open letter to Vint Cerf. He pulls no punches. Many of the same issues arise in discussions in the ACM SIGPLAN Executive Committee. It is too early to go independent, as the Symposium on Computational Geometry has done from ACM and as the Conference on Computational Complexity has done from IEEE, but the idea is on the horizon.How do we satisfy our need to keep informed about results that might influence our work ? We (still) read papers and go to conferences. And how does the ACM help ? Well not very well.Aggregating the deluge of information: anyone will tell you that the amount of research material to track and read has grown exponentially. But we still, to this day, have nothing like PUBMED/MEDLINE as a central clearinghouse for publications in CS-disciplines. The ACM DL is one step towards this, but it's a very poor imitation of what a 21st century repository of information should look like. It's not comprehensive, its bibliographic data is more erroneous than one expects, and the search mechanisms are just plain depressing (it's much easier to use Google).Dealing with the changing nature of peer review and publication: Sadly, ACM, rather than acting like a society with its members' interests at heart, has been acting as a for-profit publisher with a some window dressing to make it look less execrable. Many people have documented this far more effectively than I ever could. Conference services: One of the services a national organization supposedly provides are the conference services that help keep communities running. But what exactly does the ACM do ? It sits back and nitpicks conference budgets, but provides little in the way of real institutional support. There's no infrastructure to help with conference review processes, no support for at-conference-time services like social networking, fostering online discussion and communities, and even modern web support. I only bring this up because all of these services exist, but piecemeal, and outside the ACM umbrella.Underneath all of this is a slow but clear change in the overall CS research experience. The CRA has been doing yeoman service here: taking the temperature of the community every year with the Taulbee surveys, putting out a best practices document for postdocs after extensive community discussion, and even forming action groups to help gain more support for CS research from the government. Does the ACM do any of this ?Philip Wadlertag:blogger.com,1999:blog-9757377.post-1962206980238112073Wed, 30 Jul 2014 09:37:00 +0000Pragmatic Haskell Developer at Anchor Systems (Full-time)
http://functionaljobs.com/jobs/8729-pragmatic-haskell-developer-at-anchor-systems
urn:uuid:ee53c746-4749-559c-8c53-495d43f8cca0Wed, 30 Jul 2014 05:51:33 +0000vectorBuilder: packed-representation yielding for conduit
https://www.fpcomplete.com/blog/2014/07/vectorbuilder-packed-conduit-yielding
This post contains fragments of active Haskell code, best viewed and executed at
https://www.fpcomplete.com/blog/2014/07/vectorbuilder-packed-conduit-yielding
Back in March, I mentioned that we'd be using conduit for high performance analyses. We've been busy working on various aspects of this behind the scenes. This is the first publicly available follow-up since then.One issue with financial analyses is bridging the gap between in-memory representations and streaming data. The former allows for higher performance for many forms of analysis, while the latter allows us to deal with far larger data sets and to generate output more quickly for certain analyses.We'll be using the vector package almost exclusively for efficient in-memory representations in IAP, and conduit for streaming data. The question comes: what happens when we need to transition from one to the other? There are already functions like yieldMany to yield values from a Vector as a Conduit, and conduitVector or sinkVector to consume values from a Conduit into a packed representation.While these solutions are always sufficient, they aren't always optimal. When we're going for high speed analyses, we don't want to waste time boxing unpacked values or allocating extra constructors unnecessarily. This blog post introduces a new tool we're adding to the IAP toolchain (and the conduit toolchain in general): vectorBuilder.The problemOften times when working with Haskell in a high performance context, the overhead introduced by a linked list representation can be too high. Having an extra constructor around each value, a constructor for each cons cell, and the indirection introduced by having to follow pointers, can completely kill performance. The most common examples of this are the high speedup you can often achieve by replacing String with Text (or sometimes ByteString), or by using Vectors- especially unboxed or storable Vectors.conduit has a similar representation of a stream as a list, including the constructor overheads just mentioned. It's not surprising, therefore, that in a situation that a list would be a poor representation, conduits will often suffer similar performance problems. Like lists, some of this overhead is mitigated by shortcut fusion (a.k.a., rewrite rules). But this isn't always the case.conduit-combinators provides a helper function which allows us to take back performance, by working with a packed representation instead of creating a bunch of cons cells. It does this by using the vector package's generic mutable interface under the surface, while at a user-facing level providing a simple yield-like function, avoiding the need to muck around with mutable buffers.This article will cover how to use this function, some implementation details, and comparisons to other approaches.NOTE: At the time of writing, the version of conduit-combinators provided on School of Haskell does not contain the vectorBuilder function, and therefore the active code below will not run.Motivating use caseLet's start with a simple goal: we have chunks of bytes coming in, and we want to (1) duplicate each successive byte so that, e.g. [1, 2, 3] becomes [1, 1, 2, 2, 3, 3] and (2) rechunk the values into vectors of size 512. The original data could be chunked in any way, so we can rely on any specific incoming chunk size (in this case, a known 256 chunk size would be convenient).Likely the easiest approach is to convert our stream of chunked values (e.g., ByteString or Vector Word8) into a stream of elements (e.g., Word8), duplicate the individual values, then chunk those back up. Such a solution would look like:rechunk1 = concatC
=$= concatMapC (\x -> [x, x])
=$= conduitVector 512This uses the concatC combinator to "flatten out" the input stream, concatMapC to duplicate each individual Word8, and then conduitVector to create a stream of 512-sized Vectors. In my simple benchmark, this function took 13.06ms.But as we can probably guess, this falls into the problem zone described in our introduction. So instead of dealing with things on the individual byte level, let's try to use some higher-level functions operating on Vectors of values instead. Our new approach will be to first mapC over the stream and use vector's concatMap to double each value, and then use takeCE and foldC to extract successive chunks of size 4096. In code:rechunk2 =
mapC (concatMap $ replicate 2) =$= loop
where
loop = do
x <- takeCE 512 =$= foldC
unless (null x) $ yield x >> loopIn the same benchmark, this performed at 8.83ms, a 32% speedup. While respectable, we can do better.Buffer copyingOur first approach is optimal in one way: it avoids needless buffer copying. Each Word8 is copied precisely once into an output Vector by conduitVector. Unfortunately, this advantage is killed by the overhead of boxing the Word8s and allocating constructors for conduit. Our second approach avoids the boxing and constructors by always operating on Vectors, but we end up copying buffers multiple times: from the original Vector to the doubled Vector, and then when folding together multiple Vectors into a single Vector of size 512.What we want to do is to be able to yield a Word8 and have it fill up an output buffer, and once that buffer is filled, yield that buffer downstream and start working on a new one. We could do that by directly dealing with mutable Vectors, but that's error-prone and tedious. Instead, let's introduce our new combinator function: vectorBuilder (or its unqualified name, vectorBuilderC).The idea is simple. vectorBuilder will allocate an output buffer for you. It provides you with a special yield-like function that fills up this buffer, and when it's full, yields the entire buffer downstream for you.To use it, we're going to use one other combinator function: mapM_CE, which performs an action for every value in a chunked input stream (in our case, for each Word8 in our input Vector Word8s). Altogether, this looks like:rechunk3 = vectorBuilderC 512 $ \yield' ->
mapM_CE (\x -> yield' x >> yield' x)We call yield' twice to double our bytes. vectorBuilder ensures that each output buffer is of size 512. mapM_CE efficiently traverses the incoming Vectors without creating intermediate data structures.This version benchmarks at 401.12us. This is approximately 95% faster than our previous attempt!Avoiding transformersThere's something tricky about the yield' function above. Notice how it's not being used in the Conduit monad transformer, but is instead living the base monad (e.g., IO). This is not accidental. Not only does this allow us to use existing monadic combinators like mapM_CE, it also allows for far more efficient code. To demonstrate, let's look at two different ways of doing the same thing:bgroup "transformers" $
let src = return () in
[ bench "single" $ nfIO $ do
ref <- newIORef 0
let incr = modifyIORef ref succ
src $$ liftIO (replicateM_ 1000 incr)
, bench "multi" $ nfIO $ do
ref <- newIORef 0
let incr = liftIO $ modifyIORef ref succ
src $$ replicateM_ 1000 incr
]Both of these benchmarks use no conduit features. They both create an IORef, then increment it 1000 times. The difference is that the first calls liftIO once, while the second calls liftIO 1000 times. Let's see the difference in benchmark results:benchmarking transformers/single
mean: 4.292891 us, lb 4.285319 us, ub 4.303626 us, ci 0.950
std dev: 45.83832 ns, lb 35.04324 ns, ub 59.43617 ns, ci 0.950
benchmarking transformers/multi
mean: 93.10228 us, lb 92.95708 us, ub 93.30159 us, ci 0.950
std dev: 869.6636 ns, lb 673.8342 ns, ub 1.090044 us, ci 0.950Avoiding extra liftIO calls has a profound performance impact. The reason for this is somewhat similar to what we've been discussing up until now about extra cons cells. In our case, it's extra PipeM constructors used by conduit's MonadIO instance. I don't want to dwell on those details too much right now, as that's a whole separate topic of analysis, involving looking at GHC core output. But let's take it as a given right now.The question is: how does vectorBuilder allow you to live in the base monad, but still yield values downstream, which requires access to the Conduit transformer? There's a trick here using mutable variables. The implementation essentially works like this:Allocate a new, empty mutable vector.Allocate a mutable variable holding an empty list.Start running the user-supplied Conduit function, providing it with a specialized yield function.The specialized yield function- which lives in the base monad- will write values into the mutable vector. Once that mutable vector is filled, the vector is frozen and added to the end of the mutable variable's list, and a new mutable vector is allocated.The next time the user's function awaits for values from upstream, we jump into action. Since we're already forced to be in the Conduit transformer at that point, this is our chance to yield. We grab all of the frozen vectors from the mutable variable and yield them downstream. Once that's done, we await for new data from upstream, and provide it to the user's function.When the user's function is finished, we freeze the last bit of data from the mutable vector and yield that downstream too.The upsides of this approach are ease-of-use and performance. There is one downside you should be aware of: if you generate a large amount of output without awaiting for more data from upstream, you can begin to accumulate more memory. You can force the collection of frozen Vectors to be flushed using the following helper function:forceFlush :: Monad m => ConduitM i o m ()
forceFlush = await >>= maybe (return ()) leftoverThis simply awaits for a value, allowing vectorBuilder to clear its cache, and then gives the new value back as a leftover.Overall, your goal should be to have a decent trade-off between memory and time efficiency. To demonstrate, try playing around with the functions f1, f2, and f3 in the following code snippet:{-# LANGUAGE NoImplicitPrelude #-}
{-# LANGUAGE FlexibleContexts #-}
import ClassyPrelude.Conduit
forceFlush :: Monad m => ConduitM i o m ()
forceFlush = await >>= maybe (return ()) leftover
-- Memory inefficient, time efficient
f1 :: (Int -> IO ()) -> Sink () IO ()
f1 f = liftIO $ forM_ [1..1000000] f
-- Memory efficient, time inefficient
f2 :: (Int -> Sink () IO ()) -> Sink () IO ()
f2 f = forM_ [1..1000000] $ \i -> do
f i
forceFlush
-- Good trade-off
f3 f = forM_ (chunksOf 10000 [1..1000000]) $ \is -> do
liftIO $ mapM_ f is
forceFlush
where
chunksOf _ [] = []
chunksOf i x =
y : chunksOf i z
where
(y, z) = splitAt i x
main = vectorBuilderC 4096 f3
$$ (sinkNull :: Sink (Vector Int) IO ())ByteString and VectorIt may be surprising to have seen an entire article on packed representations of bytes, and not yet seen ByteString. As a matter of fact, the original use case I started working on this for had nothing to do with the vector package. However, I decided to focus on vector for two reasons:Unlike bytestring, it provides a well developed mutable interface. Not only that, but the mutable interface is optimized for storable, unboxed, and generic vectors, plus existing helper packages like hybrid-vectors. In other words, this is a far more general-purpose solution.It's trivial and highly efficient to convert a ByteString to and from a storable Vector.To demonstrate that second point, let's try to read a file, duplicate all of its bytes as we did above, and write it back to a separate file. We'll use the toByteVector and fromByteVector functions, which I recently added to mono-traversable for just this purpose:{-# LANGUAGE NoImplicitPrelude #-}
import ClassyPrelude.Conduit
import System.IO (IOMode (ReadMode, WriteMode),
withBinaryFile)
double :: (Word8 -> IO ()) -> Sink (SVector Word8) IO ()
double yield' = mapM_CE $ \w ->
yield' w >> yield' w
main :: IO ()
main = withBinaryFile "input.txt" ReadMode $ \inH ->
withBinaryFile "output.txt" WriteMode $ \outH ->
sourceHandle inH
$$ mapC toByteVector
=$ vectorBuilderC 4096 double
=$ mapC fromByteVector
=$ sinkHandle outHComparison with blaze-builderThere's a strong overlap between what vectorBuilder does, and how blaze-builder (and more recently, bytestring's Builder type) are intended to be used. I unfortunately can't give any conclusive comparisons between these two techniques right now. What I can say is that there are cases where using a Builder has proven to be inefficient, and vectorBuilder provides a large performance improvement. I can also say that vectorBuilder addresses many more use cases that Builder. For example, at FP Complete we're planning to use this in financial analyses for creating time series data.On the other hand, blaze-builder and bytestring's Builder have both had far more real-world tuning than vectorBuilder. They also have support for things such as copying existing ByteStrings into the output stream, whereas vectorBuilder always works by copying a single element at a time.So for now, if you have a use case and you're uncertain whether to use vectorBuilder to blaze-builder, I recommend either trying both approaches, or discussing it on one of the Haskell mailing lists to get more feedback.Complete codeThe code for most of the blog post above is below. Sorry that it's a bit messy:{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE NoImplicitPrelude #-}
{-# LANGUAGE NoMonomorphismRestriction #-}
import ClassyPrelude.Conduit
import Control.Monad.Primitive (PrimMonad)
import Control.Monad.ST (runST)
import Criterion.Main (bench, bgroup, defaultMain, nfIO,
whnfIO)
import qualified Data.Vector.Generic as VG
import qualified System.Random.MWC as MWC
import Test.Hspec (hspec, shouldBe)
import Test.Hspec.QuickCheck (prop)
rechunk1 :: ( Monad m
, VG.Vector vector (Element input)
, PrimMonad base
, MonadBase base m
, MonoFoldable input
)
=> Conduit input m (vector (Element input))
rechunk1 = concatC =$= concatMapC (\x -> [x, x]) =$= conduitVector 512
{-# INLINE rechunk1 #-}
rechunk2 :: (Monad m, IsSequence a) => Conduit a m a
rechunk2 =
mapC (concatMap $ replicate 2) =$= loop
where
loop = do
x <- takeCE 512 =$= foldC
unless (null x) $ yield x >> loop
{-# INLINE rechunk2 #-}
rechunk3 :: ( MonadBase base m
, PrimMonad base
, MonoFoldable input
, VG.Vector vector (Element input)
)
=> Conduit input m (vector (Element input))
rechunk3 = vectorBuilderC 512 $ \yield' ->
mapM_CE (\x -> yield' x >> yield' x)
{-# INLINE rechunk3 #-}
main :: IO ()
main = do
hspec $ prop "rechunking" $ \ws -> do
let src = yield (pack ws :: UVector Word8)
doubled = concatMap (\w -> [w, w]) ws
res1 = runST $ src $$ rechunk1 =$ sinkList
res2 = runST $ src $$ rechunk2 =$ sinkList
res3 = runST $ src $$ rechunk3 =$ sinkList
res1 `shouldBe` (res2 :: [UVector Word8])
(res3 :: [UVector Word8]) `shouldBe` (res2 :: [UVector Word8])
(unpack $ (mconcat res2 :: UVector Word8)) `shouldBe` (doubled :: [Word8])
case reverse res1 :: [UVector Word8] of
[] -> return ()
x:xs -> do
(length x <= 512) `shouldBe` True
all ((== 512) . length) xs `shouldBe` True
gen <- MWC.createSystemRandom
bytes <- replicateM 20 $
MWC.uniformR (12, 1024) gen >>= MWC.uniformVector gen
defaultMain
[ bgroup "copy bytes"
[ bench "rechunk1" $ whnfIO
$ yieldMany (bytes :: [UVector Word8])
$$ (rechunk1 :: Conduit (UVector Word8) IO (UVector Word8))
=$ sinkNull
, bench "rechunk2" $ whnfIO
$ yieldMany (bytes :: [UVector Word8])
$$ (rechunk2 :: Conduit (UVector Word8) IO (UVector Word8))
=$ sinkNull
, bench "rechunk3" $ whnfIO
$ yieldMany (bytes :: [UVector Word8])
$$ (rechunk3 :: Conduit (UVector Word8) IO (UVector Word8))
=$ sinkNull
]
, bgroup "transformers" $
let src = return () in
[ bench "single" $ nfIO $ do
ref <- newIORef (0 :: Int)
let incr = modifyIORef ref succ
src $$ liftIO (replicateM_ 1000 incr)
, bench "multi" $ nfIO $ do
ref <- newIORef (0 :: Int)
let incr = liftIO $ modifyIORef ref succ
src $$ replicateM_ 1000 incr
]
]https://www.fpcomplete.com/blog/2014/07/vectorbuilder-packed-conduit-yieldingWed, 30 Jul 2014 04:00:00 +0000A few new papers
http://existentialtype.wordpress.com/2014/07/21/a-few-new-papers/
I’ve just updated my web page with links to some new papers that are now available:
“Homotopical Patch Theory” by Carlo Angiuli, Ed Morehouse, Dan Licata, and Robert Harper. To appear, ICFP, Gothenburg, October 2014. We’re also preparing an expanded version with a new appendix containing material that didn’t make the cut for ICFP. (Why do we still have such rigid space limitations? And why do we have such restricted pre-publication deadlines as we go through the charade of there being a “printing” of the proceedings? One day CS soon will step into its own bright new future.). The point of the paper is to show how to apply basic methods of homotopy theory to various equational theories of patches for various sorts of data. One may see it as an application of functorial semantics in HoTT, in which theories are “implemented” by interpretation into a universe of sets. The patch laws are necessarily respected by any such interpretation, since they are just cells of higher dimension and functors must behave functorially at all dimensions.
“Cache Efficient Functional Algorithms” by Guy E. Blelloch and Robert Harper. To appear, Comm. ACM Research Highlight this fall. Rewritten version of POPL 2013 paper meant for a broad CS audience. Part of a larger effort to promote integration of combinatorial theory with logical and semantic theory, two theory communities that, in the U.S. at least, ignore each other completely. (Well, to be plain about it, it seems to me that the ignoring goes more in one direction than the other.) Cost semantics is one bridge between the two schools of thought, abandoning the age-old “reason about the compiled code” model used in algorithm analysis. Here we show that one can reason about spatial locality at the abstract level, without having to drop-down to low-level of how data structures are represented and allocated in memory.
“Refining Objects (Preliminary Summary)” by Robert Harper and Rowan Davies. To appear, Luca Cardelli 60th Birthday Celebration, Cambridge, October, 2014. A paper I’ve been meaning to write sometime over the last 15 years, and finally saw the right opportunity, with Luca’s symposium coming up and Rowan Davies visiting Carnegie Mellon this past spring. Plus it was a nice project to get me started working again after I was so rudely interrupted this past fall and winter. Provides a different take on typing for dynamic dispatch that avoids the ad hoc methods introduced for oop, and instead deploying standard structural and behavioral typing techniques to do more with less. This paper is a first cut as proof of concept, but it is clear that much more can be said here, all within the framework of standard proof-theoretic and realizability-theoretic interpretations of types. It would help to have read the relevant parts of PFPL, particularly the under-development second edition, which provides the background elided in the paper.
“Correctness of Compiling Polymorphism to Dynamic Typing” by Kuen-Bang Hou (Favonia), Nick Benton, and Robert Harper, draft (summer 2014). Classically polymorphic type assignment starts with untyped -terms and assigns types to them as descriptions of their behavior. Viewed as a compilation strategy for a polymorphic language, type assignment is rather crude in that every expression is compiled in uni-typed form, complete with the overhead of run-time classification and class checking. A more subtle strategy is to maintain as much structural typing as possible, resorting to the use of dynamic typing (recursive types, naturally) only for variable types. The catch is that polymorphic instantiation requires computation to resolve the incompatibility between, say, a bare natural number, which you want to compute with, and its encoding as a value of the one true dynamic type, which you never want but are stuck with in dynamic languages. In this paper we work out an efficient compilation scheme that maximizes statically available information, and makes use of dynamic typing only insofar as the program demands we do so. Of course there are better ways to compile polymorphism, but this style is essentially forced on you by virtual machines such as the JVM, so it is worth studying the correctness properties of the translation, which we do here making use of a combination of structural and behavioral typing.
I hope to comment here more fully on these papers in the near future, but I also have a number of other essays queued up to go out as soon as I can find the time to write them. Meanwhile, other deadlines loom large.
[Update: added fourth item neglected in first draft. Revise formatting. Add links to people. Brief summary of patch theory paper. Minor typographical corrections.]
[Update: the promised expanded version of the forthcoming ICFP paper is now available.]Filed under: Programming, Research Tagged: behavioral typing, cache efficient algorithms, compilation, cost semantics, dynamic dispatch, homotopy type theory, ICFP, polymorphism, structural typing, type refinementsRobert Harperhttp://existentialtype.wordpress.com/?p=558Mon, 21 Jul 2014 17:11:44 +0000"Is it bad to look for signs from the past?"
http://winterkoninkje.dreamwidth.org/96801.html
Someone asked recently whether it's bad to seek "signs" of being trans from the past, and why or why not. This question is one which deserves to be more widely circulated. Within trans circles a fair number of people have an understanding of the situation and it's complexity, but it's something I think non-trans circles should also be aware of— especially given the recent publicity surrounding trans lives.
The problems are twofold:
A lot of people look for signs because they're seeking some sort of validation. The problem here is that you end up misinterpreting and overanalyzing your own life in search of that validation. It's not that the past cannot provide validation for your present, it's just missing the point. What we want (more often than not) is acceptance of who we are now and recognition for our current experience. There's more to current identities, pains, and experiences than the past that gave rise to them, so validation can come from sources other than the past. Moreover, it's all too easy for people to "validate" your past while simultaneously invalidating your present, so validation from the past is not stable. Altogether, none of this is trans-specific: it's a general problem with seeking retrospective validation; and it also applies to people who've suffered abuse, experience mental illness, have changed careers, etc.
The second problem is that, in overanalyzing our pasts in search of validation, we all too often end up reinscribing "standard" trans narratives. If our pasts do not fit the "standard" narrative then we will not find the validation we seek, thus we will call our current understanding even further into question, and this sense of invalidation will only make us feel worse. If our pasts only partially fit the "standard" narrative then, in search of validation, we will highlight those memories and background the others; thus denying ourselves the full actualization of our personal history, and invalidating at least in part who we are. And if our pasts (somehow) completely fit the "standard" narrative then, in holding that history up as "proof" of our legitimacy, we end up marginalizing and invalidating everyone with different narratives. Again, this isn't a trans-specific problem (cf., "standard" narratives of gay lives or depression prior to, say, the 1970s.); though it's especially problematic for trans people because of the dearth of public awareness that our narrative tapestries are as rich and varied as cis narrative tapestries.
There's nothing wrong with seeking support for your current self from your past memories. Doing so is, imo, crucial in coming to understand, respect, and take pride in our selves. The problems of retrospection are all in the mindset with which it is pursued. We shouldn't rely on "born this way" narratives in order to justify the fact that, however we were born, we are here now and in virtue of our presence alone are worthy of respect and validation.
Fwiw, I do very much value my "signs", and often share them as amusing anecdotes— both to foster understanding, and to destabilize people's preconceived notions. But I do not seek validation in these signs; they're just collateral: symptoms of, not support for, who I am.
Twitter
Facebook
Google+
Tumblr
commentstag:dreamwidth.org,2010-05-25:518115:96801Tue, 29 Jul 2014 23:58:11 +0000Many Shades of Halting Oracles
http://jozefg.bitbucket.org/posts/2014-07-30-many-shades-of-halting.html
http://jozefg.bitbucket.org/posts/2014-07-30-many-shades-of-halting.htmlWed, 30 Jul 2014 00:00:00 +0000Beware of bracket
http://feedproxy.google.com/~r/RomanCheplyaka/~3/_0O9V2wAWLQ/2014-07-30-bracket.html
http://ro-che.info//articles/2014-07-30-bracket.htmlTue, 29 Jul 2014 21:00:00 +0000Are you serious? "What degree?"
http://logicaltypes.blogspot.com/2014/07/are-you-serious-what-degree.html
So, serious question.An aside (get used to them, by the way), people are never sure if I'm serious.I'm, like, seriously? C'mon!I am always silly (well, oftentimes silly, compared to my dour workmates), but I am always serious in my silliness.Chesterton said it well: the opposite of funny is not serious: the opposite of funny is not funny.Okay, that aside is done. Now onto the topic at hand.Hands up, those who have ever used your education in your jobs. Hands up, those who needed proof of your degree to prove competency as a prerequisite of employment.(sound of crickets.)Thought so.Actually, more of you might raise your hands to me than to most of my colleagues, because why? Because I have close ties to academe, that's why. So there are more than a few of you who are required to have your Master's degree or, those of you who are post-docs, to have your Ph.D. to get that research position or grant that you're working on.The rest of the world?No.Education, in the real world, is a detriment to doing your job.Across the board.A.Cross.The.Board.Do you know how many Ph.D.s we fire? Do you know how many Ph.D.s and matriculated students we turn away, because of their education and their lack of real-world experience?We did a survey: a sure bell-weather for a prospective employee? The amount of their education: the more they have, the more likely they are to be useless on the job.It's the Ph.D-disease: 'Ph.D: "piled high and deep."' People get ed-ju-ma-kated and then they think because they have a sheepskin or that they have a certain GPA at a certain school and know a certain ... educated way of doing things, that they know how to do this-and-that other thing, totally unrelated on the job."I've studied the Martin-Löf's intuitionistic type theory.""Great, how do you connect to our database.""Uh ....""Next."You'll bridle at this, but you know who agrees most strongly with me?Ph.D.sI went to the ICFP2006 specifically looking to roll dependent types into the programming language I was using, in industry, and I could not get the time of day from a single implementer of the type-theory in Twelf, and you know why?"Why would you be interested in this? This is purely theoretical."Uh, huh. As in "not applicable to industry."I reread the paper again, later: "Dependent types make programs easier to understand and more reliable."And why would I want that in my programs in industry, where it mattered.I spent four years at the United States Coast Guard Academy: 10,000 students apply, only 300 are allowed in, only 150 graduate, each year. It cost, at the time, $250,000 to graduate a student from the Academy, making it the most expensive school in the nation.Thank you, taxpayers, for my education.I graduated with a dual major: mathematics and computer science.How much of my education did I use on the job to save 150 lives from a capsized Arctic research exploration vessel (boy, they surely used their education, didn't they! ... to capsize their ship), act as the translator when we boarded Japanese trawlers, provide civil rights education and mediate EEO complaints and ...None. Zip. Zilch.After my stint, how much of my college education did I use on the job.My job was encoding matrices in FORTRAN. How much FORTRAN did I study in college?Zip. Zilch. Nada.How much of the Advanced Calculus II did I use on the job.People, it was frikken matrix manipulation! Something you can (now) look up on wikipedia and pick up in, oh, two hours if you're really slow.Java. C#. Swift. Visual whatever. Spring. SQL. HBase. Angular. JavaScript.All these things (Python, Ruby on Rails) can be taught in college, but they can be taught in high school, and I learned them in school, did I?No, I did not. I learned them on my own, thank you very much.Design patterns, frameworks, data structures. Do educated people know these things?Some of them do. Most people with a 'computer science' degree DO NOT, people.They do not. They woefully do not, as comp sci teachers lament over and over again, and as I, the hiring manager, scratch my head wondering what, precisely, did these kids learn in school, because, insofar as I see, they did not learn abstraction, polymorphism, typing, or data structures.They learned the if-statement.They learned the if-statement that n-dispatches within a for-loop from 1 to n off an array. That's the data structure they know: the array.Maps? Sets?The array.Polymorphism?We got you covered: the if-statement.Functional decomposition?Well, there's always main(String[] args), with a big-ole if-statement.The word on the street is education is a canard at best and a detriment at most, and at worst, it's a project-sinker.That's a shame, because there are educated people who are productive and smart and effective in their field, and can help.How to Solve It: a Modern Approach claims that one billion dollars is wasted on software because it's written in the absence of very simple techniques, such as linear programming.One.Billion.Dollars.Our authors, Michalewicz and Fogel, are off. Way off. I know. By a factor of at least one-hundred.We wasted a billion dollars on a file-indexing system for the FBI. Oh, it had email, too. Government project. Never used because it was never delivered in a useable state. Do you know how many go through that cycle?I don't. I do know know I've seen project after project just ...God. The waste.And I have friends. And they tell me stories.But, you get MITRE in there, or you get a Ph.D. or two in there, and what happens?They study the issue.They study it for six-plus months, and then they write you a nice little white paper that states the obvious search criteria that you knew from day one, but what do you have to say? Where is your ROC-analyses? So your bayesian system that was cranking out results month after month was killed by the bean-counting pointy-heads and they submit a ... working solution that could go into production? Oh, no. They submit a white paper calling for a research grant to allow for a year of surveying and further study of the issue.God.Then they get fired or they move on to more interesting research areas leaving behind us to clean up the mess and get a working system out the door in some serviceable shape that used zero percent of their research.Zero percent.You see, they modeled the situation, but the model doesn't fit the data, which is raw and dirty, so their solution solved the model, not your problem, not even close.Your degree.How much have you used your degree on your job?If you're a researcher, you probably use quite a bit of what you've studied in your research, and you are contributing more to your field of study.If you're not, then you're told this, day one, on your job: "Friend, put those books away, you're never going to use them again."I mean, seriously: did you really bring your college books to your job thinking you'd use them?NEEEERRRRRRD!This, here, is the real world. The ivory tower is for the academics. In the real world, you roll up your sleeves, get to work, and get some results; because if you don't, the door is right over there.You were expecting to use your degree on your job? This is America, people. We don' need no edjumakashun.Now, if this were Soviet Russia, your degree uses you.-----So, silliness, and serious silliness aside.Seriously.You were expecting to use your degree on your job?English major. This is America, we don't talk English, we talk American, so, that's nice that you have that degree.Mathematics major. This is America, we don't do 'maths,' nor trig, nor geometric algebras, nor category theory, how would you use any of that on your job?I was seriously asked that on my interview for a job overseeing a 1.7 petabyte-sized database.I said: 'uh, map-reduce are straight from category theory.'"Yes, but how do you use that on your job?"We both blinked at each other dumbly.The gulf.You don't go to school to get trained to do a job well, ladies and gentlemen.I mean, too many of you do that, and too many others go do school to party some, to sex some, to blaze some, and then get to work after your folks financed your four-plus year bacchanal.College is not a technical training-institute and has nothing to do with acquiring skills or proficiency on repetitive stress disorder, oh, I meant: 'your job.' Your job, almost without exception, can be just as proficiently performed by nearly anyone they drag off the street and put in your chair for eight hours a day. They sit in your chair for a few days, and everyone else won't even know you're gone.Most jobs.My wife beat the pants off her entire payroll division with an excel spreadsheet because they didn't have simple accounting principles and deductive reasoning. Why? Because they were well-regulated at their jobs, proficient at it, in fact, and their job was to make continuous clerical errors because they had absolutely no rigor. Why would they? They weren't paid for rigor. They were paid for doing their jobs, which was: don't make waves.I regularly go into situations where other software engineers (a misnomer, they are more like computer programmers, not engineers) say such-and-so cannot be done in programming language X.Then, I implement a little bit of category theory, in programming language X, do some simple mappings and natural transformations, and, voilà! those 50,000 lines of code that didn't solve the problem but only made things worse? I replace all that with 500 lines of code that actually delivers the solution.Unit tested: all the edge cases.And meeting their requirements, because I've translated the requirements into a declarative DSL on top of their programming language X.Of course they couldn't solve the insurmountable problem in programming language X, not because they were using programming language X (although it helped with the colossal fail being object-disoriented and improvably/mutatatively impure), but because they couldn't think outside the box that 'you can only do this and that' as a software engineer. They were caught in their own domain and can't even see that they had boxed themselves in.Because they were educated that way. Comp Sci 101: this is how you write a program. This is the 'if'-statement. This is the for-loop. If that doesn't work, add more if-statements wrapped by more for-loops, and this statement is perfectly acceptable:x = x + 1Go to town.That's what their education gave them: they went to school to acquire a trade and a proficiency at the if-statement, and gave up their ability to see and to think.And some, many, academics are the most bigoted, most blundering blinders-on fools out there, because they see it their way, and they see their way as the only way, which requires a six-month research grant and further study after that.With co-authorship on the American Mathematical Society journal article.And the uneducated are the worst, most pigheaded fools out there, so sure that the educated have nothing to offer, that they have no dirt under their perfectly manicured fingernails attached silky smooth hands that have never seen an honest-day's work nor, God forbid! a callous, so what do they know, these blowhards, so the uneducated ignore the advances of research into type-theory, category theory, object theory (polymorphism does help at times), any theory, and just code and code and code until they have something that 'looks good.'How to solve this?Start with you.Not with your education, that is: not with your education that tells you who you are.Start with how you can help, and then help.Project one: I saw how fractal dimensionality would solve a spectrum analysis problem. Did I say the words 'fractal' or 'dimensions'? No. I was working with real-programmers. If I asked if I could try this, do you know what they would say? Pfft. Yeah, right. Get back to work, geophf!But, instead, I implemented the algorithm. I sat with a user who had been working on those signals and knew what he needed, iterated through the result a week.Just a week. While I did my job-job full time. I did the fractal spectrum analysis on my own time.My 'thing' floored the software management team. They had seen straight-line approximations before. They thought I was doing actual signal analysis. I mean: with actual signals.They showed my 'thing' to the prospective customer. And got funded.Another project: data transformation and storage, built a system that encompassed six-hundred data elements using a monadic framework to handle the semideterminism. That was an unsolvable problem in Java. I used Java.Java with my monadic framework, yes, but Java, to solve the problem.Third project: calculating a 'sunset date' over a data vector of dimension five over a time continuum. Hm: continuum.Unsolvable problem. Three teams of software developers tackled it over six months. Nobody could get close to the solution.Continuum.I used a comonadic framework.Took me, along with a tester who was the SME on the problem, and a front-end developer to get the presentation layer just right, about a month, and we solved that baby and put it to bed.Unit tested. All edge cases.Did I tell them I used a comonadic framework?Nah, they tripped over themselves when they saw the word 'tuple.'No joke, my functional programming language friends: they, 'software engineers,' were afraid of the word 'tuple.'So I explained as much as anyone wanted to know when anyone asked. I wrote design documents, showing unit test case results, and they left me alone. They knew I knew what I was doing, and I got them their results. That's what they needed.They didn't need my degree.They didn't need to know I used predicate logic to optimize SQL queries that took four fucking hours to run to a query that took forty-five seconds.They didn't need to know I refactored using type theory, that A + B are disjoint types and A * B are type instances and A ^ B are function applications so I could look at a program, construct a mathematical model of it and get rid of 90% of it because it was all redundantly-duplicated code inside if-clauses, so I simply extracted (2A + 2B ... ad nauseam) to 2(A + B ...) and then used a continuation, for God's sake, with 'in the middle of the procedure' code, or, heaven help me, parameterization over a simple functional decomposition exercise to reduce a nightmare of copy-and-paste to something that had a story to tell that made sense.How do you connect to a database?Do you need a college degree for that?Kids with college degrees don't know the answer to that simple interview question.And they don't know the Spring framework, making 'how to connect to a database' a stupid-superfluous question.They don't know what unit tests give them. They don't know what unit tests don't give them. Because they, college kids and crusty old 'software engineers,' don't write them, so they have no consistency nor security in their code: they can't change anything here because it might break something over there, and they have no unit tests as a safety net to provide that feedback to them, and since they are programming in language X, a nice, strict, object-oriented programming language, they have no programs-as-proofs to know that what they are writing is at all good or right or anything.A college degree gives you not that. A not college degree gives you not that.A college degree is supposed to what, then?It's suppose to open your mind to the possibility of a larger world, and it's supposed to give you the tools to think, and to inquire, so that you can discern."This, not that. That, and then this. This causes that. That is a consequence of this. I choose this for these reasons. These reasons are sound because of these premises. This reason here. Hm. I wonder about that one. It seems unsound. No: unfamiliar. Is it sound or unsound? Let me find out and know why."English. Mathematics. Art. Literature. Music. Philosophy. All of these things are the humanities. The sciences and the above. Law. Physics. All these lead one to the tools of inquiry.In school, you are supposed to have been given tools to reason.Then, you're sent back out into the world.And then you are supposed to reason.And with your reason, you make the world a better place, or a worse place.These things at school, these are the humanities, and they are there to make you human.Not good at your job, not so you can 'use' your degree as a skill at work, but to make you human.And, as human, are you good at your job?Yes.And, as human, do you make your world a place such that others are good and happy at their jobs?Yes.The end of being human is not to be skilled, nor proficient ... 'good' at your job.But it's an accident of it, a happy accident.The 'end' of being human?Well: that's your inquiry.That's what school, that's what everything, is for: for you to answer the unanswered question.Your way.And, if you accept that, and are fully realized as a human being, then your way is the best way in the world, and your way has the ability to change lives. First, your own, then others. Perhaps your coworkers.Perhaps hundreds of others.Perhaps thousands.Perhaps you will change the entire world.But you won't know that until you take that first step of inquiry.Then the next.Then the next.And you look back, and you see how far you've come, and ... wow.Just wow.That's what school is for. Not for your job.For you.geophftag:blogger.com,1999:blog-4650294074444534066.post-5671015007577180231Tue, 29 Jul 2014 03:50:00 +0000Reading files from the proc filesystem
http://www.yesodweb.com/blog/2014/07/reading-files-proc-filesystem
I was stumped by this one myself for a bit today, so I thought writing it up in
a blog post would be a good way to make sure (1) I don't forget this little
fact, and (2) hopefully the next person doesn't need to puzzle over this as
long as I did. Let's say you want to read the contents of a file in the proc
filesystem, such as /proc/uptime. There are many ways to do that in Haskell.
Let's ignore any streaming data framework for the moment, and instead focus on
just the "string-like" types: String and strict/lazy ByteString/Text.
Here's a little program that tries all of them out:import qualified Data.ByteString as S
import qualified Data.ByteString.Lazy as L
import qualified Data.Text.IO as T
import qualified Data.Text.Lazy.IO as TL
test :: Show a => String -> (FilePath -> IO a) -> IO ()
test name reader = do
contents <- reader "/proc/uptime"
putStrLn $ name ++ ": " ++ show contents
main :: IO ()
main = do
test "String " readFile
test "strict ByteString" S.readFile
test "lazy ByteString " L.readFile
test "strict Text " T.readFile
test "lazy Text " TL.readFileGiven that the uptime file is just simple ASCII data, you'd probably assume
(like I did) that all of these will produce the same result. In fact, that's
not the case. On my system, the results are:String : "60740.70 136144.86\n"
strict ByteString: ""
lazy ByteString : "60740.70 136144.86\n"
strict Text : "60740.70 136144.86\n"
lazy Text : "60740.70 136144.86\n"Strict ByteString reading is returning an empty value! Why is this happening?
It's actually quite easy to see once you throw in two new pieces of
information. First, let's look at the implementation of
Data.ByteString.readFile:readFile :: FilePath -> IO ByteString
readFile f = bracket (openBinaryFile f ReadMode) hClose
(\h -> hFileSize h >>= hGet h . fromIntegral)Notice how we allocate a buffer exactly the right size to read in the entire
contents of the file. We don't do this with any of the file reading functions.
For the lazy variants, we don't want to read the entire file into memory at
once. And for strict Text, knowing the size of the file doesn't tell us the
size of the buffer we need to allocate, due to variable length encoding. So
this nifty optimization only applies to strict ByteStrings.Now piece of data number two:$ ls -l /proc/uptime
-r--r--r-- 1 root root 0 Jul 27 13:56 /proc/uptimeHuh, the file is empty! As is well
documented,
virtually every file in the proc filesystem is listed as empty, and the
contents are generated on demand by the kernel.So how do you read the file contents into a strict ByteString? There are actually plenty of approaches that work. In my case, I ended up just writing a helper function using conduit: localReadFile fp =
IO.withBinaryFile fp IO.ReadMode $ \h ->
sourceHandle h $$ foldCBut probably the simplest thing to do is to just convert a lazy ByteString
into a strict ByteString, e.g. fmap L.toStrict . L.readFile.http://www.yesodweb.com/blog/2014/07/reading-files-proc-filesystemSun, 27 Jul 2014 10:50:00 +0000Safety
http://feedproxy.google.com/~r/CartesianClosedComic/~3/bXO55sUNXNE/25
http://ro-che.info/ccc/25Sat, 26 Jul 2014 23:00:00 +0000Converting Make to Shake
http://neilmitchell.blogspot.com/2014/07/converting-make-to-shake.html
Neil Mitchelltag:blogger.com,1999:blog-7094652.post-4114900288419972468Sat, 26 Jul 2014 20:49:00 +0000New theme!
http://feedproxy.google.com/~r/ezyang/~3/2RPJqk-a2Ds/
Hello loyal readers: Inside 206-105 has a new theme! I’m retiring Manifest, which was a pretty nice theme but (1) the text size was too small and (2) I decided I didn’t really like the fonts, I’ve reskinned my blog with a theme based on Brent Jackson’s Ashley, but ported to work on WordPress. I hope you like it, and please report any rendering snafus you might notice on older pages. Thanks!Edward Z. Yanghttp://blog.ezyang.com/?p=9001Sat, 26 Jul 2014 13:58:27 +0000Write web services around databases with 0 boilerplate: announcing servant 0.1
http://alpmestan.com/posts/2014-07-26-announcing-servant.html
http://alpmestan.com/posts/2014-07-26-announcing-servant.htmlSat, 26 Jul 2014 00:00:00 +0000Senior Haskell Developer at Plow Technologies (Full-time)
http://functionaljobs.com/jobs/8726-senior-haskell-developer-at-plow-technologies
urn:uuid:826549a5-c0ee-91f8-da55-d2e7cddddd0eThu, 24 Jul 2014 20:07:52 +0000Applicative vs Monadic build systems
http://neilmitchell.blogspot.com/2014/07/applicative-vs-monadic-build-systems.html
Neil Mitchelltag:blogger.com,1999:blog-7094652.post-1968425869729555507Wed, 23 Jul 2014 19:11:00 +0000When do n and 2n have the same digits?
http://blog.plover.com/math/dd.html
[This article was published last month on the math.stackexchange
blog, which seems to have died young,
despite many earnest-sounding promises beforehand from people who
claimed they would contribute material. I am repatriating it here.]
A recent question on math.stackexchange asks for the smallest positive integer for which the number has the same
decimal digits in some other order.
Math geeks may immediately realize that has this property, because it is the first 6 digits of the decimal expansion of , and the cyclic behavior of the decimal expansion of is well-known. But is this the minimal solution? It is not. Brute-force enumeration of the solutions quickly reveals that there are 12 solutions of 6 digits each, all permutations of , and that larger solutions, such as 1025874 and 1257489 seem to follow a similar pattern. What is happening here?
Stuck in Dallas-Fort Worth airport one weekend, I did some work on the problem, and although I wasn't able to solve it completely, I made significant progress. I found a method that allows one to hand-calculate that there is no solution with fewer than six digits, and to enumerate all the solutions with 6 digits, including the minimal one. I found an explanation for the surprising behavior that solutions tend to be permutations of one another. The short form of the explanation is that there are fairly strict conditions on which sets of digits can appear in a solution of the problem. But once the set of digits is chosen, the conditions on that order of the digits in the solution are fairly lax.
So one typically sees, not only in base 10 but in other bases, that the solutions to this problem fall into a few classes that are all permutations of one another; this is exactly what happens in base 10 where all the 6-digit solutions are permutations of . As the number of digits is allowed to increase, the strict first set of conditions relaxes a little, and other digit groups appear as solutions.
Notation
The property of interest, , is that the numbers and have exactly the same base- digits. We would like to find numbers having property for various , and we are most interested in . Suppose is an -digit numeral having property ; let the (base-) digits of be and similarly the digits of are . The reader is encouraged to keep in mind the simple example of which we will bring up from time to time.
Since the digits of and are the same, in a different order, we may say that for some permutation . In general might have more than one cycle, but we will suppose that is a single cycle. All the following discussion of will apply to the individual cycles of in the case that is a product of two or more cycles. For our example of , we have in cycle notation. We won't need to worry about the details of , except to note that completely exhaust the indices , and that because is an -cycle.
Conditions on the set of digits in a solution
For each we have $$a_{P(i)} = b_{i} \equiv 2a_{i} + c_i\pmod R
$$ where the ‘carry bit’ is either 0 or 1 and depends on whether there was a carry when doubling . (When we are in the rightmost position and there is never a carry, so .) We can then write:
$$\begin{align}
a_{P(P(i))} &= 2a_{P(i)} + c_{P(i)} \\
&= 2(2a_{i} + c_i) + c_{P(i)} &&= 4a_i + 2c_i + c_{P(i)}\\
a_{P(P(P(i)))} &= 2(4a_i + 2c_i + c_{P(P(i)})) + c_{P(i)} &&= 8a_i + 4c_i + 2c_{P(i)} + c_{P(P(i))}\\
&&&\vdots\\
a_{P^n(i)} &&&= 2^na_i + v
\end{align}
$$
all equations taken . But since is an -cycle, , so we have
$$a_i \equiv 2^na_i + v\pmod R$$ or equivalently $$\big(2^n-1\big)a_i + v \equiv 0\pmod
R\tag{$\star$}$$ where depends only on the values of the carry bits —the are precisely the binary digits of .
Specifying a particular value of and that satisfy this equation completely determines all the . For example, is a solution when because , and this solution allows us to compute
$$\def\db#1{\color{darkblue}{#1}}\begin{align}
a_0&&&=2\\
a_{P(0)} &= 2a_0 &+ \db0 &= 4\\
a_{P^2(0)} &= 2a_{P(0)} &+ \db0 &= 0 \\
a_{P^3(0)} &= 2a_{P^2(0)} &+ \db1 &= 1\\ \hline
a_{P^4(0)} &= 2a_{P^3(0)} &+ \db0 &= 2\\
\end{align}$$
where the carry bits are visible in the third column, and all the sums are taken . Note that as promised. This derivation of the entire set of from a single one plus a choice of is crucial, so let's see one more example. Let's consider . Then we want to choose and so that where . One possible solution is . Then we can derive the other as follows:
$$\begin{align}
a_0&&&=5\\
a_{P(0)} &= 2a_0 &+ \db1 &= 1\\
a_{P^2(0)} &= 2a_{P(0)} &+ \db0 &= 2 \\\hline
a_{P^3(0)} &= 2a_{P^2(0)} &+ \db1 &= 5\\
\end{align}$$
And again we have as required.
Since the bits of are used cyclically, not every pair of will yield a different solution. Rotating the bits of and pairing them with different choices of will yield the same cycle of digits starting from a different place. In the first example above, we had . If we were to take (which also solves ) we would get the same cycle of values of the but starting from instead of from , and similarly if we take or . So we can narrow down the solution set of by considering only the so-called bracelets of rather than all possible values. Two values of are considered equivalent as bracelets if one is a rotation of the other. When a set of -values are equivalent as bracelets, we need only consider one of them; the others will give the same cyclic sequence of digits, but starting in a different place. For , for example, the bracelets are and ; the sequences and being equivalent to , and so on.
Example
Let us take , so we want to find 3-digit numerals with property . According to we need where . There are 9 possible values for ; for each one there is at most one possible value of that makes the sum zero:
$$\pi \approx 3 $$
$$\begin{array}{rrr}
a_i & 7a_i & v \\ \hline
0 & 0 & 0 \\
1 & 7 & 2 \\
2 & 14 & 4 \\
3 & 21 & 6 \\
4 & 28 & \\
5 & 35 & 1 \\
6 & 42 & 3 \\
7 & 49 & 5 \\
8 & 56 & 7 \\
\end{array}
$$
(For there is no solution.) We may disregard the non-bracelet values of , as these will give us solutions that are the same as those given by bracelet values of . The bracelets are:
$$\begin{array}{rl} 000 & 0 \\ 001 & 1 \\ 011 & 3 \\ 111 & 7 \end{array}$$
so we may disregard the solutions exacpt when . Calculating the digit sequences from these four values of and the corresponding we find:
$$\begin{array}{ccl}
a_0 & v & \text{digits} \\ \hline
0 & 0 & 000 \\
5 & 1 & 512 \\
6 & 3 & 637 \\
8 & 7 & 888 \
\end{array}
$$
(In the second line, for example, we have , so and .)
Any number of three digits, for which contains exactly the same three digits, in base 9, must therefore consist of exactly the digits or .
A warning
All the foregoing assumes that the permutation is a single cycle. In general, it may not be. Suppose we did an analysis like that above for and found that there was no possible digit set, other than the trivial set 00000, that satisfied the governing equation . This would not completely rule out a base-10 solution with 5 digits, because the analysis only rules out a cyclic set of digits. There could still be a solution where was a product of a and a -cycle, or a product of still smaller cycles.
Something like this occurs, for example, in the case. Solving the governing equation yields only four possible digit cycles, namely , and . But there are several additional solutions: and . These correspond to permutations with more than one cycle. In the case of , for example, exchanges the and the , and leaves the and the fixed.
For this reason we cannot rule out the possibility of an -digit solution without first considering all smaller .
The Large Equals Odd rule
When is even there is a simple condition we can use to rule out certain sets of digits from being single-cycle solutions. Recall that and . Let us agree that a digit is large if and small otherwise. That is, is large if, upon doubling, it causes a carry into the next column to the left.
Since , where the are carry bits, we see that, except for , the digit is odd precisely when there is a carry from the next column to the right, which occurs precisely when is large. Thus the number of odd digits among is equal to the number of large digits among .
This leaves the digits and uncounted. But is never odd, since there is never a carry in the rightmost position, and is always small (since otherwise would have digits, which is not allowed). So the number of large digits in is exactly equal to the number of odd digits in . And since and have exactly the same digits, the number of large digits in is equal to the number of odd digits in . Observe that this is the case for our running example : there is one odd digit and one large digit (the 4).
When is odd the analogous condition is somewhat more complicated, but since the main case of interest is , we have the useful rule that:
For even, the number of odd digits in any solution is equal to the number of large digits in .
Conditions on the order of digits in a solution
We have determined, using the above method, that the digits might form a base-9 numeral with property . Now we would like to arrange them into a base-9 numeral that actually does have that property. Again let us write and , with . Note that if , then (if there was a carry from the next column to the right) or (if there was no carry), but since is impossible, we must have and therefore must be small, since there is no carry into position . But since is also one of , and it cannot also be , it must be . This shows that the 1, unless it appears in the rightmost position, must be to the left of the ; it cannot be to the left of the . Similarly, if then , because is impossible, so the must be to the left of a large digit, which must be the . Similar reasoning produces no constraint on the position of the ; it could be to the left of a small digit (in which case it doubles to ) or a large digit (in which case it doubles to ). We can summarize these findings as follows:
$$\begin{array}{cl}
\text{digit} & \text{to the left of} \\ \hline
1 & 1, 2, \text{end} \\
2 & 5 \\
5 & 1,2,5,\text{end}
\end{array}$$
Here “end” means that the indicated digit could be the rightmost.
Furthermore, the left digit of must be small (or else there would be a carry in the leftmost place and would have 4 digits instead of 3) so it must be either 1 or 2. It is not hard to see from this table that the digits must be in the order or , and indeed, both of those numbers have the required property: , and .
This was a simple example, but in more complicated cases it is helpful to draw the order constraints as a graph. Suppose we draw a graph with one vertex for each digit, and one additional vertex to represent the end of the numeral. The graph has an edge from vertex to whenever can appear to the left of . Then the graph drawn for the table above looks like this:
A 3-digit numeral with property corresponds to a path in this graph that starts at one of the nonzero small digits (marked in blue), ends at the red node marked ‘end’, and visits each node exactly once. Such a path is called hamiltonian. Obviously, self-loops never occur in a hamiltonian path, so we will omit them from future diagrams.
Now we will consider the digit set , again base 9. An analysis similar to the foregoing allows us to construct the following graph:
Here it is immediately clear that the only hamiltonian path is , and indeed, .
In general there might be multiple instances of a digit, and so multiple nodes labeled with that digit. Analysis of the case produces a graph with no legal start nodes and so no solutions, unless leading zeroes are allowed, in which case is a perfectly valid solution. Analysis of the case produces a graph with no path to the end node and so no solutions. These two trivial patterns appear for all and all , and we will ignore them from now on.
Returning to our ongoing example, in base 8, we see that and must double to and , so must be to the left of small digits, but and can double to either or and so could be to the left of anything. Here the constraints are so lax that the graph doesn't help us narrow them down much:
Observing that the only arrow into the 4 is from 0, so that the 4 must follow the 0, and that the entire number must begin with 1 or 2, we can enumerate the solutions:
1042
1204
2041
2104
If leading zeroes are allowed we have also:
0412
0421
All of these are solutions in base 8.
The case of
Now we turn to our main problem, solutions in base 10.
To find all the solutions of length 6 requires an enumeration of smaller solutions, which, if they existed, might be concatenated into a solution of length 6. This is because our analysis of the digit sets that can appear in a solution assumes that the digits are permuted cyclically; that is, the permutations that we considered had only one cycle each.
There are no smaller solutions, but to prove that the length 6 solutions are minimal, we must analyze the cases for smaller and rule them out. We now produce a complete analysis of the base 10 case with and . For there is only the trivial solution of , which we disregard. (The question asked for a positive number anyway.)
For , we want to find solutions of where is a two-bit bracelet number, one of or . Tabulating the values of and that solve this equation we get:
$$\begin{array}{ccc}
v& a_i \\ \hline
0 & 0 \\
1& 3 \\
3& 9 \\
\end{array}$$
We can disregard the and solutions because the former yields the trivial solution and the latter yields the nonsolution . So the only possibility we need to investigate further is , which corresponds to the digit sequence : Doubling gives us and doubling , plus a carry, gives us again.
But when we tabulate of which digits must be left of which informs us that there is no solution with just and , because the graph we get, once self-loops are eliminated, looks like this:
which obviously has no hamiltonian path. Thus there is no solution for .
For we need to solve the equation where is a bracelet number in , specifically one of or . Since and are relatively prime, for each there is a single that solves the equation.
Tabulating the possible values of as before, and this time omitting rows with no solution, we have:
$$\begin{array}{rrl}
v & a_i & \text{digits}\\ \hline
0& 0 & 000\\
1& 7 & 748 \\
3& 1 & 125\\
7&9 & 999\\
\end{array}$$
The digit sequences and yield trivial solutions or nonsolutions as usual, and we will omit them in the future. The other two lines suggest the digit sets and , both of which fails the “odd equals large” rule.
This analysis rules out the possibility of a digit set with , but it does not completely rule out a 3-digit solution, since one could be obtained by concatenating a one-digit and a two-digit solution, or three one-digit solutions. However, we know by now that no one- or two-digit solutions exist. Therefore there are no 3-digit solutions in base 10.
For the governing equation is where is a 4-bit bracelet number, one of . This is a little more complicated because . Tabulating the possible digit sets, we get:
$$\begin{array}{crrl}
a_i & 15a_i& v & \text{digits}\\ \hline
0 & 0 & 0 & 0000\\
1 & 5 & 5 & 1250\\
1 & 5 & 15 & 1375\\
2 & 0 & 0 & 2486\\
3 & 5 & 5 & 3749\\
3 & 5 & 15 & 3751\\
4 & 0 & 0 & 4862\\
5 & 5 & 5 & 5012\\
5 & 5 & 5 & 5137\\
6 & 0 & 0 & 6248\\
7 & 5 & 5 & 7493\\
7 & 5 & 5 & 7513\\
8 & 0 & 0 & 8624 \\
9 & 5 & 5 & 9874\\
9 & 5 & 15 & 9999 \\
\end{array}$$
where the second column has been reduced mod . Note that even restricting to bracelet numbers the table still contains duplicate digit sequences; the 15 entries on the right contain only the six basic sequences , and . Of these, only and obey the odd equals large criterion, and we will disregard and as usual, leaving only . We construct the corresponding graph for this digit set as follows: must double to , not , so must be left of a large number or . Similarly must be left of or . must also double to , so must be left of . Finally, must double to , so must be left of or the end of the numeral. The corresponding graph is:
which evidently has no hamiltonian path: whichever of 3 or 4 we start at, we cannot visit the other without passing through 7, and then we cannot reach the end node without passing through 7 a second time. So there is no solution with and .
We leave this case as an exercise. There are 8 solutions to the governing equation, all of which are ruled out by the odd equals large rule.
For the possible solutions are given by the governing equation where is a 6-bit bracelet number, one of . Tabulating the possible digit sets, we get:
$$\begin{array}{crrl}
v & a_i & \text{digits}\\ \hline
0 & 0 & 000000\\
1 & 3 & 362486 \\
3 & 9 & 986249 \\
5 & 5 & 500012 \\
7 & 1 & 124875 \\
9 & 7 & 748748 \\
11 & 3 & 362501 \\
13 & 9 & 986374 \\
15 & 5 & 500137 \\
21 & 3 & 363636 \\
23 & 9 & 989899 \\
27 & 1 & 125125 \\
31 & 3 & 363751 \\
63 & 9 & 999999 \\
\end{array}$$
After ignoring and as usual, the large equals odd rule allows us to ignore all the other sequences except and . The latter fails for the same reason that did when . But , the lone survivor, gives us a complicated derived graph containing many hamiltonian paths, every one of which is a solution to the problem:
It is not hard to pick out from this graph the minimal solution , for which , and also our old friend for which .
We see here the reason why all the small numbers with property contain the digits . The constraints on which digits can appear in a solution are quite strict, and rule out all other sequences of six digits and all shorter sequences. But once a set of digits passes these stringent conditions, the constraints on it are much looser, because is only required to have the digits of in some order, and there are many possible orders, many of which will satisfy the rather loose conditions involving the distribution of the carry bits. This graph is typical: it has a set of small nodes and a set of large nodes, and each node is connected to either all the small nodes or all the large nodes, so that the graph has many edges, and, as in this case, a largish clique of small nodes and a largish clique of large nodes, and as a result many hamiltonian paths.
Onward
This analysis is tedious but is simple enough to perform by hand in under an hour. As increases further, enumerating the solutions of the governing equation becomes very time-consuming. I wrote a simple computer program to perform the analysis for given and , and to emit the possible digit sets that satisfied the large equals odd criterion. I had wondered if every base-10 solution contained equal numbers of the digits and . This is the case for (where the only admissible digit set is ), for (where the only admissible sets are and ), and for (where the only admissible sets are and ). But when we reach the increasing number of bracelets has loosened up the requirements a little and there are 5 admissible digit sets. I picked two of the promising-seeming ones and quickly found by hand the solutions and , both of which wreck any theory that the digits must all appear the same number of times.
Acknowledgments
Thanks to Karl
Kronenfeld
for corrections and many helpful suggestions.Mark Dominustag:blog.plover.com,2014:/math/ddWed, 23 Jul 2014 13:39:00 +0000EclipseFP 2.6.1 released!
http://jpmoresmau.blogspot.com/2014/07/eclipsefp-261-released.html
I've just released EclipseFP 2.6.1. EclipseFP is a set of Eclipse plugins for Haskell development. This is a bug fixing release, mainly for GHC 7.8 support.Release notes can be found here.As usual, download from http://eclipsefp.sf.net/updates.Happy Haskell Hacking!JP Moresmautag:blogger.com,1999:blog-37404288.post-4138807775029042925Tue, 22 Jul 2014 16:40:00 +0000CTO / Tech Co-Founder at Capital Match (Full-time)
http://functionaljobs.com/jobs/8725-cto-tech-co-founder-at-capital-match
urn:uuid:b5741799-86f1-7f8d-6000-4197338c72adTue, 22 Jul 2014 06:27:49 +0000Summer of Programming Languages
http://existentialtype.wordpress.com/2014/07/06/summer-of-programming-languages/
Having just returned from the annual Oregon Programming Languages Summer School, at which I teach every year, I am once again very impressed with the impressive growth in the technical sophistication of the field and with its ability to attract brilliant young students whose enthusiasm and idealism are inspiring. Eugene was, as ever, an ideal setting for the summer school, providing a gorgeous setting for work and relaxation. I was particularly glad for the numerous chances to talk with students outside of the classroom, usually over beer, and I enjoyed, as usual, the superb cycling conditions in Eugene and the surrounding countryside. Many students commented to me that the atmosphere at the summer school is wonderful, filled with people who are passionate about programming languages research, and suffused with a spirit of cooperation and sharing of ideas.
Started by Zena Ariola a dozen years ago, this year’s instance was organized by Greg Morrisett and Amal Ahmed in consultation with Zena. As usual, the success of the school depended critically on the dedication of Jim Allen, who has been the de facto chief operating officer since it’s inception. Without Jim, OPLSS could not exist. His attention to detail, and his engagement with the students are legendary. Support from the National Science Foundation CISE Division, ACM SIGPLAN, Microsoft Research, Jane Street Capital, and BAE Systems was essential for providing an excellent venue, for supporting a roster of first-rate lecturers, and for supporting the participation of students who might otherwise not have been able to attend. And, of course, an outstanding roster of lecturers donated their time to come to Eugene for a week to share their ideas with the students and their fellow lecturers.
The schedule of lectures is posted on the web site, all of which were taped, and are made available on the web. In addition many speakers provided course notes, software, and other backing materials that are also available online. So even if you were not able to attend, you can still benefit from the summer school, and perhaps feel more motivated to come next summer. Greg and I will be organizing, in consultation with Zena. Applying the principle “don’t fix what isn’t broken”, we do not anticipate major changes, but there is always room for improvement and the need to freshen up the content every year. For me the central idea of the summer school is the applicability of deep theory to everyday practice. Long a dream held by researchers such as me, these connections become more “real” every year as the theoretical abstractions of yesterday become the concrete practices of today. It’s breathtaking to see how far we’ve come from the days when I was a student just beginning to grasp the opportunities afforded by ideas from proof theory, type theory, and category theory (the Holy Trinity) to building beautiful software systems. No longer the abstruse fantasies of mad (computer) scientists, these ideas are the very air we breathe in PL research. Gone are the days of ad hoc language designs done in innocence of the foundations on which they rest. Nowadays serious industrial-strength languages are emerging that are grounded in theory and informed by practice.
Two examples have arisen just this summer, Rust (from Mozila) and Swift (from Apple), that exemplify the trend. Although I have not had time to study them carefully, much less write serious code using them, it is evident from even a brief review of their web sites that these are serious languages that take account of the academic developments of the last couple of decades in formulating new language designs to address new classes of problems that have arisen in programming practice. These languages are type safe, a basic criterion of sensibility, and feature sophisticated type systems that include ideas such as sum types, which have long been missing from commercial languages, or provided only in comically obtuse ways (such as objects). The infamous null pointer mistakes have been eradicated, and the importance of pattern matching (in the sense of the ML family of languages) is finally being appreciated as the cure for Boolean blindness. For once I can look at new industrial languages without an overwhelming sense of disappointment, but instead with optimism and enthusiasm that important ideas are finally, at long last, being recognized and adopted. As has often been observed, it takes 25 years for an academic language idea to make it into industrial practice. With Java it was simply the 1970’s idea of automatic storage management; with languages such as Rust and Swift we are seeing ideas from the 80’s and 90’s make their way into industrial practice. It’s cause for celebration, and encouragement for those entering the field: the right ideas do win out in the end, one just has to have the courage to be irrelevant.
I hope to find the time to comment more meaningfully on the recent developments in practical programming languages, including Rust and Swift, but also languages such as Go and OCaml that are also making inroads into programming practice. (I’ve had quite enough to say about Haskell for the time being, so I’ll give that one a rest, but with a tip of the hat to its enormous popularity and influence, despite my criticisms.) But for now, let me say that the golden age of programming language research is here and now, and promises to continue indefinitely as we develop a grand unified theory of programming and mathematics.Filed under: Programming, Research, Teaching Tagged: OPLSS14, programming languages, Rust, SwiftRobert Harperhttp://existentialtype.wordpress.com/?p=952Sun, 06 Jul 2014 23:09:35 +0000Parallelism and Concurrency, Revisited
http://existentialtype.wordpress.com/2014/04/09/parallelism-and-concurrency-revisited/
To my delight, I still get compliments on and criticisms of my post from three years ago (can it possibly be that long?) on parallelism and concurrency. In that post I offered a “top down” argument to the effect that these are different abstractions with different goals: parallelism is about exploiting computational resources to maximize efficiency, concurrency is about non-deterministic composition of components in a system. Parallelism never introduces bugs (the semantics is identical to the sequential execution), but concurrency could be said to be the mother lode of all bugs (the semantics of a component changes drastically, without careful provision, when composed concurrently with other components). The two concepts just aren’t comparable, yet somehow the confusion between them persists. (Not everyone agrees with me on this distinction, but neither have I seen a rigorous analysis that shows them to be the same concept. Most complaints seem to be about my use of the words “parallelism” and “concurrency” , which is an unavoidable problem, or about my temerity in trying to define two somewhat ill-defined concepts, a criticism that I’ll just have to accept.)
I’ve recently gotten an inkling of why it might be that many people equate the two concepts (or see no point in distinguishing them). This post is an attempt to clear up what I perceive to be a common misunderstanding that seems to explain it. It’s hard for me to say whether it really is all that common of a misunderstanding, but it’s the impression I’ve gotten, so forgive me if I’m over-stressing an obvious point. In any case I’m going to try for a “bottom up” explanation that might make more sense to some people.
The issue is scheduling.
The naive view of parallelism is that it’s just talk for concurrency, because all you do when you’re programming in parallel is fork off some threads, and then do something with their results when they’re done. I’ve previously argued that this is the wrong way to think about parallelism (it’s really about cost), but let’s just let that pass. It’s unarguably true that a parallel computation does consist of a bunch of, well, parallel computations. So, the argument goes, it’s nothing but concurrency. I’ve previously argued that that’s not a good way to think about concurrency either, but we’ll let that pass too. So, the story goes, concurrency and parallelism are synonymous, and bullshitters like me are just trying to confuse people and make trouble.
Being the troublemaker that I am, my response is, predictably, no, just no. Sure, it’s kinda sorta right, as I’ve already acknowledged, but not really, and here’s why: scheduling as you learned about it in OS class (for example) is an altogether different thing than scheduling for parallelism. And this is the heart of the matter, from a “bottom-up” perspective.
There are two aspects of OS-like scheduling that I think are relevant here. First, it is non-deterministic, and second, it is competitive. Non-deterministic, because you have little or no control over what runs when or for how long. A beast like the Linux scheduler is controlled by a zillion “voodoo parameters” (a turn of phrase borrowed from my queueing theory colleague, Mor Harchol-Balter), and who the hell knows what is going to happen to your poor threads once they’re in its clutches. Second, and more importantly, an OS-like scheduler is allocating resources competitively. You’ve got your threads, I’ve got my threads, and we both want ours to get run as soon as possible. We’ll even pay for the privilege (priorities) if necessary. The scheduler, and the queueing theory behind it (he says optimistically) is designed to optimize resource usage on a competitive basis, taking account of quality of service guarantees purchased by the participants. It does not matter whether there is one processor or one thousand processors, the schedule is unpredictable. That’s what makes concurrent programming hard: you have to program against all possible schedules. And that’s why you can’t prove much about the time or space complexity of your program when it’s implemented concurrently.
Parallel scheduling is a whole ‘nother ball of wax. It is (usually, but not necessarily) deterministic, so that you can prove bounds on its efficiency (Brent-type theorems, as I discussed in my previous post and in PFPL). And, more importantly, it is cooperative in the sense that all threads are working together for the same computation towards the same ends. The threads are scheduled so as to get the job (there’s only one) done as quickly and as efficiently as possible. Deterministic schedulers for parallelism are the most common, because they are the easiest to analyze with respect to their time and space bounds. Greedy schedulers, which guarantee to maximize use of available processors, never leaving any idle when there is work to be done, form an important class for which the simple form of Brent’s Theorem is obvious.
Many deterministic greedy scheduling algorithms are known, of which I will mention p-DFS and p-BFS, which do p-at-a-time depth- and breadth-first search of the dependency graph, and various forms of work-stealing schedulers, pioneered by Charles Leiserson at MIT. (Incidentally, if you don’t already know what p-DFS or p-BFS are, I’ll warn you that they are a little trickier than they sound. In particular p-DFS uses a data structure that is sort of like a stack but is not a stack.) These differ significantly in their time bounds (for example, work stealing usually involves expectation over a random variable, whereas the depth- and breadth-first traversals do not), and differ dramatically in their space complexity. For example, p-BFS is absolutely dreadful in its space complexity. For a full discussion of these issues in parallel scheduling, I recommend Dan Spoonhower’s PhD Dissertation. (His semantic profiling diagrams are amazingly beautiful and informative!)
So here’s the thing: when you’re programming in parallel, you don’t just throw some threads at some non-deterministic competitive scheduler. Rather, you generate an implicit dependency graph that a cooperative scheduler uses to maximize efficiency, end-to-end. At the high level you do an asymptotic cost analysis without considering platform parameters such as the number of processors or the nature of the interconnect. At the low level the implementation has to validate that cost analysis by using clever techniques to ensure that, once the platform parameters are known, maximum use is made of the computational resources to get your job done for you as fast as possible. Not only are there no bugs introduced by the mere fact of being scheduled in parallel, but even better, you can prove a theorem that tells you how fast your program is going to run on a real platform. Now how cool is that?
[Update: word-smithing.]Filed under: Programming, Research Tagged: concurrency, parallelismRobert Harperhttp://existentialtype.wordpress.com/?p=906Thu, 10 Apr 2014 03:15:00 +0000Meditations on Using Haskell
http://wadler.blogspot.com/2014/07/meditations-on-using-haskell.html
Bitemyapp - Meditations on Using Haskell explains why and how those in the trenches use Haskell, by quoting from conversations on an IRC channel.ESo when i found haskell i slingshotted off through dependent and substructural types. Assuming that if a little was good a lot was better. Made it half way through TaPL and found pure type systems, coq, etc.I think the power to weight ratio isn’t there. I find that Haskell gives amazingly expressive types that have amazingpower for the amount of code you tie up in them and that are very resistant to refactoring.If i write agda and refactor I scrap and rewrite everything. If i write haskell, and get my tricky logic bits right?I can refactor it, split things up into classes, play all the squishy software engineering games to get a nice API I want. And in the end if it still compiles I can trust I didn’t screw up the refactoring with a very high degree of assurance.CAdmittedly I’m not playing at the level E is, but this was my experience. I can make sweeping changes to my API, get all the bugs caught by the type system, and still have minimal code impact.BThat is what I was getting at with the tweet about not using dynamically typed langs because I need to be able to prototype quickly and get rapid feedback.I think a lot of my friends thought i was just being trollish. Even just being able to see what would have to change if you changed your design slightly and being able to back it out quickly…Philip Wadlertag:blogger.com,1999:blog-9757377.post-8540088540244617222Mon, 21 Jul 2014 09:27:00 +0000That's totes my Bag!
http://logicaltypes.blogspot.com/2014/06/thats-totes-my-bag.html
So, does that mean I like tote-bags?So, today's question on @1HaskellADay was this:write a function countOccurences :: [Stirng] -> Map Char Int(typos faithfully reproduced)such thatlookup 'l' $ countOccurences "Hello" ~> Just 2lookup 'q' $ countOccurences "Hello" ~> NothingOkay, that can be done easily enough, I suppose, by torquing Map into something that it isn't, so one gets wrapped around the axel of creating a mapping from characters to occurrences.But why?First of all, countOccurences maps a String (not a List of Strings) to a Map, and that map is a very specialized kind of map that has existed in the literature for quite a while, and that map is known as the Bag data type, and is also, nowadays, called the MultiSet by people too embarrassed to say the word 'bag' in a sentence, because of their prior drug convictions.("I got two months for selling a dime bag.")So they now twist the word 'Set' (a 'collection of unique objects') to mean something that's not a set at all, the 'Multi'Set, which is a 'collection of unique objects, but you can have multiples of these unique objects, so they're not unique at all, so it isn't a set at all, but we need to say the word 'set' because we can't say the word 'bag' because saying the word 'bag' would make us sound plebeian for some reason.'Yeah, that. 'MultiSet.'What. Ev. Er.But I digress.As always.So I COULD write the countOccurences as a String -> Map Char Int function, but then: why bother? You can either write tons of algorithmic code that obscures the intent or just simply use the appropriate data type.I went for the latter.Now, I wuz gonna do a dependently-typed pair to represent an occurrence...... notice how countOccurences is so badly misspelled, by the way?SOMEbody didn't QA-check their problem for the day today, I'm thinking.... but then I said: 'eh!'I mean: WHY is lookup 'q' $ countOccurences "Hello" ~> Nothing?WHY can't it be that count 'q' for a Bag Char representation of "Hello" be 0? 0 is a valid answer and it keeps everything nice and monoidal without having to lift everything unnecessarily into the monadic domain.So, yeah. Let's do that, instead.So, here we go, and in Idris, because that's how I'm rolling these days. The advantages of dependent types have been enumerated elsewhere, so we'll just go with that they're better as an assumption and move on, using them, instead of extolling them, in this post.Wrong!So, my first attempt at Bag crashed and burned, because I did this:data Bag : (x : Type) -> Type where add : Bag x -> x -> Bag x emptyBag : Bag xand the compiler was fine with that. Hey, I can declare any type I'd like, so long as the types just stay as types, but as soon as I tried to define these things:emptyList : List xemptyList = []emptyBag = Bag emptyListadd (Bag []) x = Bag [(x, 1)]add (Bag ((x, y) :: rest)) x = Bag ((x, y + 1) :: rest)add (Bag ((z, y) :: rest)) x = Bag ((z, y) :: (add rest x))The compiler looked at me and asked: 'geophf, what in tarnation are you-ah tryin' to do?'And about the only intelligent answer I could muster was: 'Ummmm... idk.'I had gotten too clever for myself by half, trying to reshape a data type you learn in Comp.Sci. 101 as a purely functional type.Back to Basics ... (but not BASIC)So, let's just declare Bag to be what it is and KISS: 'keep it simple, stupid!'Yes, let's.data Bag x = Air | Stuffed (x, Nat) (Bag x)Now, I so totally could've gone with the balanced binary-tree representation instead of the simple and standard linked list, but, you know: 'live and learn!'With this declaration the emptyBag becomes so trivial as to be unnecessary, and then add is simplicity, itself, too, but add is, either way, so that's not saying much.add : Eq x => Bag x -> x -> Bag xadd Air x = Stuffed (x, 1) Airadd (Stuffed (z, y) rest) x = case x == z of True => Stuffed (x, y + 1) rest False => Stuffed (z, y) (add rest x)Now, you see me relying on the case-statement, here. Unhappily.I'd like my dependent types to say, 'unify x with x (reflexive) for the isomorphic case, and don't unify x with z for the other case.' But we're not there yet, or my coding isn't on par with being there yet, so I forced total coverage bifurcating the result-set into isomorphic and not with a hard-case statement.Ick. I hate explicit case-statements! Where is really, really, really smart pattern-matching when I need it?But with add, constructing a Bag becomes easy, and then counting elements of that bag is easy, too (again, with another case-statement, sigh!):count : Eq x => x -> Bag x -> Natcount _ Air = 0count x (Stuffed (z, y) rest) = case x == z of True => y False => count x restcountOccurences (with one-too-few 'r's in the function name) becomes easy, given the Bag data type:countOccurences : String -> Bag CharcountOccurences str = co' (unpack str) where co' [] = Air co' (char :: rest) = add (co' rest) charYAWN!But look at this:depth : Bag x -> Natdepth Air = 0depth (Stuffed _ rest) = 1 + depth restsample : ?bagsample = countOccurences "The quick, brown fox jumped over the lazy dog."bag = proof searchWhen we do a depth sample, we get the not-surprising answer of 29 : NatPerhaps this could be made a tad bit more efficient?Just perhaps.Well, then, let's do that!data Bag x = Air | Stuffed (x, Nat) (Bag x) (Bag x)We make Bag balanced, with the add-function, doing the work of (very simply) branching off new nodes:add : Ord x => Bag x -> x -> Bag xadd Air x = Stuffed (x, 1) Air Airadd (Stuffed (z, y) less more) x = case (compare x z) of LT => Stuffed (z, y) (add less x) more GT => Stuffed (z, y) less (add more x) EQ => Stuffed (z, y + 1) less moreThen all the other functions change ('morph') to work with a tree, not a list and work with Ord elements, not with (simply) Eq ones.And so, the redefined depth-function gives a very different result:depth sample ~> 9 : NatNot bad! Not bad! The improved data-structure improves efficiency across the board from O(N) to O(log N).Hm, perhaps I'll have count return a dependently-typed pair, just as the library function filter does on List types, but not tonight.Good night, Moon!geophftag:blogger.com,1999:blog-4650294074444534066.post-8639246761487116204Tue, 03 Jun 2014 03:34:00 +0000BuildWrapper/EclipseFP and GHC 7.8
http://jpmoresmau.blogspot.com/2014/07/buildwrappereclipsefp-and-ghc-78.html
I've been working on some issues related to GHC 7.8 in BuildWrapper and EclipseFP. On the EclipseFP side, mainly the quickfixes are affected, because EclipseFP parses the GHC error messages to offer them, and the quotes characters have changed in the GHC 7.8 messages.On the BuildWrapper side, things are more complex. Adapting to API changes wasn't a big deal, but it seems that GHC bugs involving the GHC API, static linking and other unknowns cause some things to break. The solution I've found was to build BuildWrapper with the -dynamic flag. But I couldn't upload this to hackage because Cabal thinks that -dynamic is a debug flag (it starts with d). I've sent a bug fix to Cabal, so in the next release that'll be fixed. So if you're using GHC 7.8 and BuildWrapper, you may want to rebuild the executable with -dynamic (uncomment the relevant line in the cabal file).Note: BuildWrapper comes with a comprehensive test suite (90 tests covering all aspects). So you can always build the tests and run them to ensure everyting is OK on your system.Happy Haskell Hacking!JP Moresmautag:blogger.com,1999:blog-37404288.post-57664732208534156Sun, 20 Jul 2014 17:24:00 +0000Equational reasoning at scale
http://www.haskellforall.com/2014/07/equational-reasoning-at-scale.html
Haskell programmers care about the correctness of their software and they specify correctness conditions in the form of equations that their code must satisfy. They can then verify the correctness of these equations using equational reasoning to prove that the abstractions they build are sound. To an outsider this might seem like a futile, academic exercise: proving the correctness of small abstractions is difficult, so what hope do we have to prove larger abstractions correct? This post explains how to do precisely that: scale proofs to large and complex abstractions.Purely functional programming uses composition to scale programs, meaning that:We build small components that we can verify correct in isolationWe compose smaller components into larger componentsIf you saw "components" and thought "functions", think again! We can compose things that do not even remotely resemble functions, such as proofs! In fact, Haskell programmers prove large-scale properties exactly the same way we build large-scale programs:We build small proofs that we can verify correct in isolationWe compose smaller proofs into larger proofsThe following sections illustrate in detail how this works in practice, using Monoids as the running example. We will prove the Monoid laws for simple types and work our way up to proving the Monoid laws for much more complex types. Along the way we'll learn how to keep the proof complexity flat as the types grow in size.MonoidsHaskell's Prelude provides the following Monoid type class:class Monoid m where mempty :: m mappend :: m -> m -> m-- An infix operator equivalent to `mappend`(<>) :: Monoid m => m -> m -> mx <> y = mappend x y... and all Monoid instances must obey the following two laws:mempty <> x = x -- Left identityx <> mempty = x -- Right identity(x <> y) <> z = x <> (y <> z) -- AssociativityFor example, Ints form a Monoid:-- See "Appendix A" for some caveatsinstance Monoid Int where mempty = 0 mappend = (+)... and the Monoid laws for Ints are just the laws of addition:0 + x = xx + 0 = x(x + y) + z = x + (y + z)Now we can use (<>) and mempty instead of (+) and 0:>>> 4 <> 26>>> 5 <> mempty <> 510This appears useless at first glance. We already have (+) and 0, so why are we using the Monoid operations?Extending MonoidsWell, what if I want to combine things other than Ints, like pairs of Ints. I want to be able to write code like this:>>> (1, 2) <> (3, 4)(4, 6)Well, that seems mildly interesting. Let's try to define a Monoid instance for pairs of Ints:instance Monoid (Int, Int) where mempty = (0, 0) mappend (x1, y1) (x2, y2) = (x1 + x2, y1 + y2)Now my wish is true and I can "add" binary tuples together using (<>) and mempty:>>> (1, 2) <> (3, 4)(4, 6)>>> (1, 2) <> (3, mempty) <> (mempty, 4)(4, 6)>>> (1, 2) <> mempty <> (3, 4)(4, 6)However, I still haven't proven that this new Monoid instance obeys the Monoid laws. Fortunately, this is a very simple proof.I'll begin with the first Monoid law, which requires that:mempty <> x = xWe will begin from the left-hand side of the equation and try to arrive at the right-hand side by substituting equals-for-equals (a.k.a. "equational reasoning"):-- Left-hand side of the equationmempty <> x-- x <> y = mappend x y= mappend mempty x-- `mempty = (0, 0)`= mappend (0, 0) x-- Define: x = (xL, xR), since `x` is a tuple= mappend (0, 0) (xL, xR)-- mappend (x1, y1) (x2, y2) = (x1 + x2, y1 + y2)= (0 + xL, 0 + xR)-- 0 + x = x= (xL, xR)-- x = (xL, xR)= xThe proof for the second Monoid law is symmetric-- Left-hand side of the equation= x <> mempty-- x <> y = mappend x y= mappend x mempty-- mempty = (0, 0)= mappend x (0, 0)-- Define: x = (xL, xR), since `x` is a tuple= mappend (xL, xR) (0, 0)-- mappend (x1, y1) (x2, y2) = (x1 + x2, y1 + y2)= (xL + 0, xR + 0)-- x + 0 = x= (xL, xR)-- x = (xL, xR)= xThe third Monoid law requires that (<>) is associative:(x <> y) <> z = x <> (y <> z)Again I'll begin from the left side of the equation:-- Left-hand side(x <> y) <> z-- x <> y = mappend x y= mappend (mappend x y) z-- x = (xL, xR)-- y = (yL, yR)-- z = (zL, zR)= mappend (mappend (xL, xR) (yL, yR)) (zL, zR)-- mappend (x1, y1) (x2 , y2) = (x1 + x2, y1 + y2)= mappend (xL + yL, xR + yR) (zL, zR)-- mappend (x1, y1) (x2 , y2) = (x1 + x2, y1 + y2)= mappend ((xL + yL) + zL, (xR + yR) + zR)-- (x + y) + z = x + (y + z)= mappend (xL + (yL + zL), xR + (yR + zR))-- mappend (x1, y1) (x2, y2) = (x1 + x2, y1 + y2)= mappend (xL, xR) (yL + zL, yR + zR)-- mappend (x1, y1) (x2, y2) = (x1 + x2, y1 + y2)= mappend (xL, xR) (mappend (yL, yR) (zL, zR))-- x = (xL, xR)-- y = (yL, yR)-- z = (zL, zR)= mappend x (mappend y z)-- x <> y = mappend x y= x <> (y <> z)That completes the proof of the three Monoid laws, but I'm not satisfied with these proofs.Generalizing proofsI don't like the above proofs because they are disposable, meaning that I cannot reuse them to prove other properties of interest. I'm a programmer, so I loathe busy work and unnecessary repetition, both for code and proofs. I would like to find a way to generalize the above proofs so that I can use them in more places.We improve proof reuse in the same way that we improve code reuse. To see why, consider the following sort function:sort :: [Int] -> [Int]This sort function is disposable because it only works on Ints. For example, I cannot use the above function to sort a list of Doubles.Fortunately, programming languages with generics let us generalize sort by parametrizing sort on the element type of the list:sort :: Ord a => [a] -> [a]That type says that we can call sort on any list of as, so long as the type a implements the Ord type class (a comparison interface). This works because sort doesn't really care whether or not the elements are Ints; sort only cares if they are comparable.Similarly, we can make the proof more "generic". If we inspect the proof closely, we will notice that we don't really care whether or not the tuple contains Ints. The only Int-specific properties we use in our proof are:0 + x = xx + 0 = x(x + y) + z = x + (y + z)However, these properties hold true for all Monoids, not just Ints. Therefore, we can generalize our Monoid instance for tuples by parametrizing it on the type of each field of the tuple:instance (Monoid a, Monoid b) => Monoid (a, b) where mempty = (mempty, mempty) mappend (x1, y1) (x2, y2) = (mappend x1 x2, mappend y1 y2)The above Monoid instance says that we can combine tuples so long as we can combine their individual fields. Our original Monoid instance was just a special case of this instance where both the a and b types are Ints.Note: The mempty and mappend on the left-hand side of each equation are for tuples. The memptys and mappends on the right-hand side of each equation are for the types a and b. Haskell overloads type class methods like mempty and mappend to work on any type that implements the Monoid type class, and the compiler distinguishes them by their inferred types.We can similarly generalize our original proofs, too, by just replacing the Int-specific parts with their more general Monoid counterparts.Here is the generalized proof of the left identity law:-- Left-hand side of the equationmempty <> x-- x <> y = mappend x y= mappend mempty x-- `mempty = (mempty, mempty)`= mappend (mempty, mempty) x-- Define: x = (xL, xR), since `x` is a tuple= mappend (mempty, mempty) (xL, xR)-- mappend (x1, y1) (x2, y2) = (mappend x1 x2, mappend y1 y2)= (mappend mempty xL, mappend mempty xR)-- Monoid law: mappend mempty x = x= (xL, xR)-- x = (xL, xR)= x... the right identity law:-- Left-hand side of the equation= x <> mempty-- x <> y = mappend x y= mappend x mempty-- mempty = (mempty, mempty)= mappend x (mempty, mempty)-- Define: x = (xL, xR), since `x` is a tuple= mappend (xL, xR) (mempty, mempty)-- mappend (x1, y1) (x2, y2) = (mappend x1 x2, mappend y1 y2)= (mappend xL mempty, mappend xR mempty)-- Monoid law: mappend x mempty = x= (xL, xR)-- x = (xL, xR)= x... and the associativity law:-- Left-hand side(x <> y) <> z-- x <> y = mappend x y= mappend (mappend x y) z-- x = (xL, xR)-- y = (yL, yR)-- z = (zL, zR)= mappend (mappend (xL, xR) (yL, yR)) (zL, zR)-- mappend (x1, y1) (x2 , y2) = (mappend x1 x2, mappend y1 y2)= mappend (mappend xL yL, mappend xR yR) (zL, zR)-- mappend (x1, y1) (x2 , y2) = (mappend x1 x2, mappend y1 y2)= (mappend (mappend xL yL) zL, mappend (mappend xR yR) zR)-- Monoid law: mappend (mappend x y) z = mappend x (mappend y z)= (mappend xL (mappend yL zL), mappend xR (mappend yR zR))-- mappend (x1, y1) (x2, y2) = (mappend x1 x2, mappend y1 y2)= mappend (xL, xR) (mappend yL zL, mappend yR zR)-- mappend (x1, y1) (x2, y2) = (mappend x1 x2, mappend y1 y2)= mappend (xL, xR) (mappend (yL, yR) (zL, zR))-- x = (xL, xR)-- y = (yL, yR)-- z = (zL, zR)= mappend x (mappend y z)-- x <> y = mappend x y= x <> (y <> z)This more general Monoid instance lets us stick any Monoids inside the tuple fields and we can still combine the tuples. For example, lists form a Monoid:-- Exercise: Prove the monoid laws for listsinstance Monoid [a] where mempty = [] mappend = (++)... so we can stick lists inside the right field of each tuple and still combine them:>>> (1, [2, 3]) <> (4, [5, 6])(5, [2, 3, 5, 6])>>> (1, [2, 3]) <> (4, mempty) <> (mempty, [5, 6])(5, [2, 3, 5, 6])>>> (1, [2, 3]) <> mempty <> (4, [5, 6])(5, [2, 3, 5, 6])Why, we can even stick yet another tuple inside the right field and still combine them:>>> (1, (2, 3)) <> (4, (5, 6))(5, (7, 9))We can try even more exotic permutations and everything still "just works":>>> ((1,[2, 3]), ([4, 5], 6)) <> ((7, [8, 9]), ([10, 11), 12)((8, [2, 3, 8, 9]), ([4, 5, 10, 11], 18))This is our first example of a "scalable proof". We began from three primitive building blocks:Int is a Monoid[a] is a Monoid(a, b) is a Monoid if a is a Monoid and b is a Monoid... and we connected those three building blocks to assemble a variety of new Monoid instances. No matter how many tuples we nest the result is still a Monoid and obeys the Monoid laws. We don't need to re-prove the Monoid laws every time we assemble a new permutation of these building blocks.However, these building blocks are still pretty limited. What other useful things can we combine to build new Monoids?IOWe're so used to thinking of Monoids as data, so let's define a new Monoid instance for something entirely un-data-like:-- See "Appendix A" for some caveatsinstance Monoid b => Monoid (IO b) where mempty = return mempty mappend io1 io2 = do a1 <- io1 a2 <- io2 return (mappend a1 a2)The above instance says: "If a is a Monoid, then an IO action that returns an a is also a Monoid". Let's test this using the getLine function from the Prelude:-- Read one line of input from stdingetLine :: IO StringString is a Monoid, since a String is just a list of characters, so we should be able to mappend multiple getLine statements together. Let's see what happens:>>> getLine -- Reads one line of inputHello "Hello">>> getLine <> getLineABC DEF "ABCDEF">>> getLine <> getLine <> getLine1 23 456 "123456"Neat! When we combine multiple commands we combine their effects and their results.Of course, we don't have to limit ourselves to reading strings. We can use readLn from the Prelude to read in anything that implements the Read type class:-- Parse a `Read`able value from one line of stdinreadLn :: Read a => IO aAll we have to do is tell the compiler which type a we intend to Read by providing a type signature:>>> readLn :: IO (Int, Int)(1, 2) (1 ,2)>>> readLn <> readLn :: IO (Int, Int)(1,2) (3,4) (4,6)>>> readLn <> readLn <> readLn :: IO (Int, Int)(1,2) (3,4) (5,6) (9,12)This works because:Int is a MonoidTherefore, (Int, Int) is a MonoidTherefore, IO (Int, Int) is a MonoidOr let's flip things around and nest IO actions inside of a tuple:>>> let ios = (getLine, readLn) :: (IO String, IO (Int, Int))>>> let (getLines, readLns) = ios <> ios <> ios>>> getLines1 23 456 123456>>> readLns(1,2) (3,4) (5,6) (9,12)We can very easily reason that the type (IO String, IO (Int, Int)) obeys the Monoid laws because:String is a MonoidIf String is a Monoid then IO String is also a MonoidInt is a MonoidIf Int is a Monoid, then (Int, Int) is also a `MonoidIf (Int, Int) is a Monoid, then IO (Int, Int) is also a MonoidIf IO String is a Monoid and IO (Int, Int) is a Monoid, then (IO String, IO (Int, Int)) is also a MonoidHowever, we don't really have to reason about this at all. The compiler will automatically assemble the correct Monoid instance for us. The only thing we need to verify is that the primitive Monoid instances obey the Monoid laws, and then we can trust that any larger Monoid instance the compiler derives will also obey the Monoid laws.The Unit MonoidHaskell Prelude also provides the putStrLn function, which echoes a String to standard output with a newline:putStrLn :: String -> IO ()Is putStrLn combinable? There's only one way to find out!>>> putStrLn "Hello" <> putStrLn "World"HelloWorldInteresting, but why does that work? Well, let's look at the types of the commands we are combining:putStrLn "Hello" :: IO ()putStrLn "World" :: IO ()Well, we said that IO b is a Monoid if b is a Monoid, and b in this case is () (pronounced "unit"), which you can think of as an "empty tuple". Therefore, () must form a Monoid of some sort, and if we dig into Data.Monoid, we will discover the following Monoid instance:-- Exercise: Prove the monoid laws for `()`instance Monoid () where mempty = () mappend () () = ()This says that empty tuples form a trivial Monoid, since there's only one possible value (ignoring bottom) for an empty tuple: (). Therefore, we can derive that IO () is a Monoid because () is a Monoid.FunctionsAlright, so we can combine putStrLn "Hello" with putStrLn "World", but can we combine naked putStrLn functions?>>> (putStrLn <> putStrLn) "Hello"HelloHelloWoah, how does that work?We never wrote a Monoid instance for the type String -> IO (), yet somehow the compiler magically accepted the above code and produced a sensible result.This works because of the following Monoid instance for functions:instance Monoid b => Monoid (a -> b) where mempty = \_ -> mempty mappend f g = \a -> mappend (f a) (g a)This says: "If b is a Monoid, then any function that returns a b is also a Monoid".The compiler then deduced that:() is a MonoidIf () is a Monoid, then IO () is also a MonoidIf IO () is a Monoid then String -> IO () is also a MonoidThe compiler is a trusted friend, deducing Monoid instances we never knew existed.Monoid pluginsNow we have enough building blocks to assemble a non-trivial example. Let's build a key logger with a Monoid-based plugin system.The central scaffold of our program is a simple main loop that echoes characters from standard input to standard output:main = do hSetEcho stdin False forever $ do c <- getChar putChar cHowever, we would like to intercept key strokes for nefarious purposes, so we will slightly modify this program to install a handler at the beginning of the program that we will invoke on every incoming character:install :: IO (Char -> IO ())install = ???main = do hSetEcho stdin False handleChar <- install forever $ do c <- getChar handleChar c putChar cNotice that the type of install is exactly the correct type to be a Monoid:() is a MonoidTherefore, IO () is also a MonoidTherefore Char -> IO () is also a MonoidTherefore IO (Char -> IO ()) is also a MonoidTherefore, we can combine key logging plugins together using Monoid operations. Here is one such example:type Plugin = IO (Char -> IO ())logTo :: FilePath -> PluginlogTo filePath = do handle <- openFile filePath WriteMode return (hPutChar handle)main = do hSetEcho stdin False handleChar <- logTo "file1.txt" <> logTo "file2.txt" forever $ do c <- getChar handleChar c putChar cNow, every key stroke will be recorded to both file1.txt and file2.txt. Let's confirm that this works as expected:$ ./loggerTest ABC 42 $ cat file1.txtTestABC42$ cat file2.txtTestABC42Try writing your own Plugins and mixing them in with (<>) to see what happens. "Appendix C" contains the complete code for this section so you can experiment with your own Plugins.ApplicativesNotice that I never actually proved the Monoid laws for the following two Monoid instances:instance Monoid b => Monoid (a -> b) where mempty = \_ -> mempty mappend f g = \a -> mappend (f a) (g a)instance Monoid a => Monoid (IO a) where mempty = return mempty mappend io1 io2 = do a1 <- io1 a2 <- io2 return (mappend a1 a2)The reason why is that they are both special cases of a more general pattern. We can detect the pattern if we rewrite both of them to use the pure and liftA2 functions from Control.Applicative:import Control.Applicative (pure, liftA2)instance Monoid b => Monoid (a -> b) where mempty = pure mempty mappend = liftA2 mappendinstance Monoid b => Monoid (IO b) where mempty = pure mempty mappend = liftA2 mappendThis works because both IO and functions implement the following Applicative interface:class Functor f => Applicative f where pure :: a -> f a (<*>) :: f (a -> b) -> f a -> f b-- Lift a binary function over the functor `f`liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f cliftA2 f x y = (pure f <*> x) <*> y... and all Applicative instances must obey several Applicative laws:pure id <*> v = v((pure (.) <*> u) <*> v) <*> w = u <*> (v <*> w)pure f <*> pure x = pure (f x)u <*> pure x = pure (\f -> f y) <*> uThese laws may seem a bit adhoc, but this paper explains that you can reorganize the Applicative class to this equivalent type class:class Functor f => Monoidal f where unit :: f () (#) :: f a -> f b -> f (a, b)Then the corresponding laws become much more symmetric:fmap snd (unit # x) = x -- Left identityfmap fst (x # unit) = x -- Right identityfmap assoc ((x # y) # z) = x # (y # z) -- Associativity where assoc ((a, b), c) = (a, (b, c))fmap (f *** g) (x # y) = fmap f x # fmap g y -- Naturality where (f *** g) (a, b) = (f a, g b)I personally prefer the Monoidal formulation, but you go to war with the army you have, so we will use the Applicative type class for this post.All Applicatives possess a very powerful property: they can all automatically lift Monoid operations using the following instance:instance (Applicative f, Monoid b) => Monoid (f b) where mempty = pure mempty mappend = liftA2 mappendThis says: "If f is an Applicative and b is a Monoid, then f b is also a Monoid." In other words, we can automatically extend any existing Monoid with some new feature f and get back a new Monoid.Note: The above instance is bad Haskell because it overlaps with other type class instances. In practice we have to duplicate the above code once for each Applicative. Also, for some Applicatives we may want a different Monoid instance.We can prove that the above instance obeys the Monoid laws without knowing anything about f and b, other than the fact that f obeys the Applicative laws and b obeys the Applicative laws. These proofs are a little long, so I've included them in Appendix B.Both IO and functions implement the Applicative type class:instance Applicative IO where pure = return iof <*> iox = do f <- iof x <- iox return (f x)instance Applicative ((->) a) where pure x = \_ -> x kf <*> kx = \a -> let f = kf a x = kx a in f xThis means that we can kill two birds with one stone. Every time we prove the Applicative laws for some functor F:instance Applicative F where ...... we automatically prove that the following Monoid instance is correct for free:instance Monoid b => Monoid (F b) where mempty = pure mempty mappend = liftA2 mappendIn the interest of brevity, I will skip the proofs of the Applicative laws, but I may cover them in a subsequent post.The beauty of Applicative Functors is that every new Applicative instance we discover adds a new building block to our Monoid toolbox, and Haskell programmers have already discovered lots of Applicative Functors.Revisiting tuplesOne of the very first Monoid instances we wrote was:instance (Monoid a, Monoid b) => Monoid (a, b) where mempty = (mempty, mempty) mappend (x1, y1) (x2, y2) = (mappend x1 x2, mappend y1 y2)Check this out:instance (Monoid a, Monoid b) => Monoid (a, b) where mempty = pure mempty mappend = liftA2 mappendThis Monoid instance is yet another special case of the Applicative pattern we just covered!This works because of the following Applicative instance in Control.Applicative:instance Monoid a => Applicative ((,) a) where pure b = (mempty, b) (a1, f) <*> (a2, x) = (mappend a1 a2, f x)This instance obeys the Applicative laws (proof omitted), so our Monoid instance for tuples is automatically correct, too.Composing applicativesIn the very first section I wrote:Haskell programmers prove large-scale properties exactly the same way we build large-scale programs:We build small proofs that we can verify correct in isolationWe compose smaller proofs into larger proofsI don't like to use the word compose lightly. In the context of category theory, compose has a very rigorous meaning, indicating composition of morphisms in some category. This final section will show that we can actually compose Monoid proofs in a very rigorous sense of the word.We can define a category of Monoid proofs:Objects are types and their associated Monoid proofsMorphisms are Applicative FunctorsThe identity morphism is the Identity applicativeThe composition operation is composition of Applicative FunctorsThe category laws are isomorphisms instead of equalitiesSo in our Plugin example, we began on the proof that () was a Monoid and then composed three Applicative morphisms to prove that Plugin was a Monoid. I will use the following diagram to illustrate this:+-----------------------+| || Legend: * = Object || || v || | = Morphism || v || |+-----------------------+* `()` is a `Monoid`v| IOv* `IO ()` is a `Monoid`v| ((->) String)v* `String -> IO ()` is a `Monoid`v| IOv* `IO (String -> IO ())` (i.e. `Plugin`) is a `Monoid`Therefore, we were literally composing proofs together.ConclusionYou can equationally reason at scale by decomposing larger proofs into smaller reusable proofs, the same way we decompose programs into smaller and more reusable components. There is no limit to how many proofs you can compose together, and therefore there is no limit to how complex of a program you can tame using equational reasoning.This post only gave one example of composing proofs within Haskell. The more you learn the language, the more examples of composable proofs you will encounter. Another common example is automatically deriving Monad proofs by composing monad transformers.As you learn Haskell, you will discover that the hard part is not proving things. Rather, the challenge is learning how to decompose proofs into smaller proofs and you can cultivate this skill by studying category theory and abstract algebra. These mathematical disciplines teach you how to extract common and reusable proofs and patterns from what appears to be disposable and idiosyncratic code.Appendix A - Missing Monoid instancesThese Monoid instance from this post do not actually appear in the Haskell standard library:instance Monoid b => Monoid (IO b)instance Monoid IntThe first instance was recently proposed here on the Glasgow Haskell Users mailing list. However, in the short term you can work around it by writing your own Monoid instances by hand just by inserting a sufficient number of pures and liftA2s.For example, suppose we wanted to provide a Monoid instance for Plugin. We would just newtype Plugin and write:newtype Plugin = Plugin { install :: IO (String -> IO ()) }instance Monoid Plugin where mempty = Plugin (pure (pure (pure mempty))) mappend (Plugin p1) (Plugin p2) = Plugin (liftA2 (liftA2 (liftA2 mappend)) p1 p2)This is what the compiler would have derived by hand.Alternatively, you could define an orphan Monoid instance for IO, but this is generally frowned upon.There is no default Monoid instance for Int because there are actually two possible instances to choose from:-- Alternative #1instance Monoid Int where mempty = 0 mappend = (+)-- Alternative #2instance Monoid Int where mempty = 1 mappend = (*)So instead, Data.Monoid sidesteps the issue by providing two newtypes to distinguish which instance we prefer:newtype Sum a = Sum { getSum :: a }instance Num a => Monoid (Sum a)newtype Product a = Product { getProduct :: a}instance Num a => Monoid (Product a)An even better solution is to use a semiring, which allows two Monoid instances to coexist for the same type. You can think of Haskell's Num class as an approximation of the semiring class:class Num a where fromInteger :: Integer -> a (+) :: a -> a -> a (*) :: a -> a -> a -- ... and other operations unrelated to semiringsNote that we can also lift the Num class over the Applicative class, exactly the same way we lifted the Monoid class. Here's the code:instance (Applicative f, Num a) => Num (f a) where fromInteger n = pure (fromInteger n) (+) = liftA2 (+) (*) = liftA2 (*) (-) = liftA2 (-) negate = fmap negate abs = fmap abs signum = fmap signumThis lifting guarantees that if a obeys the semiring laws then so will f a. Of course, you will have to specialize the above instance to every concrete Applicative because otherwise you will get overlapping instances.Appendix BThese are the proofs to establish that the following Monoid instance obeys the Monoid laws:instance (Applicative f, Monoid b) => Monoid (f b) where mempty = pure mempty mappend = liftA2 mappend... meaning that if f obeys the Applicative laws and b obeys the Monoid laws, then f b also obeys the Monoid laws.Proof of the left identity law:mempty <> x-- x <> y = mappend x y= mappend mempty x-- mappend = liftA2 mappend= liftA2 mappend mempty x-- mempty = pure mempty= liftA2 mappend (pure mempty) x-- liftA2 f x y = (pure f <*> x) <*> y= (pure mappend <*> pure mempty) <*> x-- Applicative law: pure f <*> pure x = pure (f x)= pure (mappend mempty) <*> x-- Eta conversion= pure (\a -> mappend mempty a) <*> x-- mappend mempty x = x= pure (\a -> a) <*> x-- id = \x -> x= pure id <*> x-- Applicative law: pure id <*> v = v= xProof of the right identity law:x <> mempty = x-- x <> y = mappend x y= mappend x mempty-- mappend = liftA2 mappend= liftA2 mappend x mempty-- mempty = pure mempty= liftA2 mappend x (pure mempty)-- liftA2 f x y = (pure f <*> x) <*> y= (pure mappend <*> x) <*> pure mempty-- Applicative law: u <*> pure y = pure (\f -> f y) <*> u= pure (\f -> f mempty) <*> (pure mappend <*> x)-- Applicative law: ((pure (.) <*> u) <*> v) <*> w = u <*> (v <*> w)= ((pure (.) <*> pure (\f -> f mempty)) <*> pure mappend) <*> x-- Applicative law: pure f <*> pure x = pure (f x)= (pure ((.) (\f -> f mempty)) <*> pure mappend) <*> x-- Applicative law : pure f <*> pure x = pure (f x)= pure ((.) (\f -> f mempty) mappend) <*> x-- `(.) f g` is just prefix notation for `f . g`= pure ((\f -> f mempty) . mappend) <*> x-- f . g = \x -> f (g x)= pure (\x -> (\f -> f mempty) (mappend x)) <*> x-- Apply the lambda= pure (\x -> mappend x mempty) <*> x-- Monoid law: mappend x mempty = x= pure (\x -> x) <*> x-- id = \x -> x= pure id <*> x-- Applicative law: pure id <*> v = v= xProof of the associativity law:(x <> y) <> z-- x <> y = mappend x y= mappend (mappend x y) z-- mappend = liftA2 mappend= liftA2 mappend (liftA2 mappend x y) z-- liftA2 f x y = (pure f <*> x) <*> y= (pure mappend <*> ((pure mappend <*> x) <*> y)) <*> z-- Applicative law: ((pure (.) <*> u) <*> v) <*> w = u <*> (v <*> w)= (((pure (.) <*> pure mappend) <*> (pure mappend <*> x)) <*> y) <*> z-- Applicative law: pure f <*> pure x = pure (f x)= ((pure f <*> (pure mappend <*> x)) <*> y) <*> z where f = (.) mappend-- Applicative law: ((pure (.) <*> u) <*> v) <*> w = u <*> (v <*> w)= ((((pure (.) <*> pure f) <*> pure mappend) <*> x) <*> y) <*> z where f = (.) mappend-- Applicative law: pure f <*> pure x = pure (f x)= (((pure f <*> pure mappend) <*> x) <*> y) <*> z where f = (.) ((.) mappend)-- Applicative law: pure f <*> pure x = pure (f x)= ((pure f <*> x) <*> y) <*> z where f = (.) ((.) mappend) mappend-- (.) f g = f . g= ((pure f <*> x) <*> y) <*> z where f = ((.) mappend) . mappend-- Eta conversion= ((pure f <*> x) <*> y) <*> z where f x = (((.) mappend) . mappend) x-- (f . g) x = f (g x)= ((pure f <*> x) <*> y) <*> z where f x = (.) mappend (mappend x)-- (.) f g = f . g= ((pure f <*> x) <*> y) <*> z where f x = mappend . (mappend x)-- Eta conversion= ((pure f <*> x) <*> y) <*> z where f x y = (mappend . (mappend x)) y-- (f . g) x = f (g x)= ((pure f <*> x) <*> y) <*> z where f x y = mappend (mappend x y)-- Eta conversion= ((pure f <*> x) <*> y) <*> z where f x y z = mappend (mappend x y) z-- Monoid law: mappend (mappend x y) z = mappend x (mappend y z)= ((pure f <*> x) <*> y) <*> z where f x y z = mappend x (mappend y z)-- (f . g) x = f (g x)= ((pure f <*> x) <*> y) <*> z where f x y z = (mappend x . mappend y) z-- Eta conversion= ((pure f <*> x) <*> y) <*> z where f x y = mappend x . mappend y-- (.) f g = f . g= ((pure f <*> x) <*> y) <*> z where f x y = (.) (mappend x) (mappend y)-- (f . g) x = f= ((pure f <*> x) <*> y) <*> z where f x y = (((.) . mappend) x) (mappend y)-- (f . g) x = f (g x)= ((pure f <*> x) <*> y) <*> z where f x y = ((((.) . mappend) x) . mappend) y-- Eta conversion= ((pure f <*> x) <*> y) <*> z where f x = (((.) . mappend) x) . mappend-- (.) f g = f . g= ((pure f <*> x) <*> y) <*> z where f x = (.) (((.) . mappend) x) mappend-- Lambda abstraction= ((pure f <*> x) <*> y) <*> z where f x = (\k -> k mappend) ((.) (((.) . mappend) x))-- (f . g) x = f (g x)= ((pure f <*> x) <*> y) <*> z where f x = (\k -> k mappend) (((.) . ((.) . mappend)) x)-- Eta conversion= ((pure f <*> x) <*> y) <*> z where f = (\k -> k mappend) . ((.) . ((.) . mappend))-- (.) f g = f . g= ((pure f <*> x) <*> y) <*> z where f = (.) (\k -> k mappend) ((.) . ((.) . mappend))-- Applicative law: pure f <*> pure x = pure (f x)= (((pure g <*> pure f) <*> x) <*> y) <*> z where g = (.) (\k -> k mappend) f = (.) . ((.) . mappend)-- Applicative law: pure f <*> pure x = pure (f x)= ((((pure (.) <*> pure (\k -> k mappend)) <*> pure f) <*> x) <*> y) <*> z where f = (.) . ((.) . mappend)-- Applicative law: ((pure (.) <*> u) <*> v) <*> w = u <*> (v <*> w)= ((pure (\k -> k mappend) <*> (pure f <*> x)) <*> y) <*> z where f = (.) . ((.) . mappend)-- u <*> pure y = pure (\k -> k y) <*> u= (((pure f <*> x) <*> pure mappend) <*> y) <*> z where f = (.) . ((.) . mappend)-- (.) f g = f . g= (((pure f <*> x) <*> pure mappend) <*> y) <*> z where f = (.) (.) ((.) . mappend)-- Applicative law: pure f <*> pure x = pure (f x)= ((((pure g <*> pure f) <*> x) <*> pure mappend) <*> y) <*> z where g = (.) (.) f = (.) . mappend-- Applicative law: pure f <*> pure x = pure (f x)= (((((pure (.) <*> pure (.)) <*> pure f) <*> x) <*> pure mappend) <*> y) <*> z where f = (.) . mappend-- Applicative law: ((pure (.) <*> u) <*> v) <*> w = u <*> (v <*> w)= (((pure (.) <*> (pure f <*> x)) <*> pure mappend) <*> y) <*> z where f = (.) . mappend-- Applicative law: ((pure (.) <*> u) <*> v) <*> w = u <*> (v <*> w)= ((pure f <*> x) <*> (pure mappend <*> y)) <*> z where f = (.) . mappend-- (.) f g = f . g= ((pure f <*> x) <*> (pure mappend <*> y)) <*> z where f = (.) (.) mappend-- Applicative law: pure f <*> pure x = pure (f x)= (((pure f <*> pure mappend) <*> x) <*> (pure mappend <*> y)) <*> z where f = (.) (.)-- Applicative law: pure f <*> pure x = pure (f x)= ((((pure (.) <*> pure (.)) <*> pure mappend) <*> x) <*> (pure mappend <*> y)) <*> z-- Applicative law: ((pure (.) <*> u) <*> v) <*> w = u <*> (v <*> w)= ((pure (.) <*> (pure mappend <*> x)) <*> (pure mappend <*> y)) <*> z-- Applicative law: ((pure (.) <*> u) <*> v) <*> w = u <*> (v <*> w)= (pure mappend <*> x) <*> ((pure mappend <*> y) <*> z)-- liftA2 f x y = (pure f <*> x) <*> y= liftA2 mappend x (liftA2 mappend y z)-- mappend = liftA2 mappend= mappend x (mappend y z)-- x <> y = mappend x y= x <> (y <> z)Appendix C: Monoid key loggingHere is the complete program for a key logger with a Monoid-based plugin system:import Control.Applicative (pure, liftA2)import Control.Monad (forever)import Data.Monoidimport System.IOinstance Monoid b => Monoid (IO b) where mempty = pure mempty mappend = liftA2 mappendtype Plugin = IO (Char -> IO ())logTo :: FilePath -> PluginlogTo filePath = do handle <- openFile filePath WriteMode return (hPutChar handle)main = do hSetEcho stdin False handleChar <- logTo "file1.txt" <> logTo "file2.txt" forever $ do c <- getChar handleChar c putChar cGabriel Gonzaleztag:blogger.com,1999:blog-1777990983847811806.post-971828486155429031Sun, 20 Jul 2014 15:27:00 +0000Similarity analysis of quilt blocks
http://blog.plover.com/misc/quilt-analysis.html
As I've discussed elsewhere, I once wrote a program to enumerate all
the possible quilt blocks of a certain type. The quilt blocks in
question are, in quilt jargon, sixteen-patch half-square triangles. A
half-square triangle, also called a “patch”, is two triangles of fabric sewn together, like
this:
Then you sew four of these patches into a four-patch, say like this:
Then to make a sixteen-patch block of the type I was considering, you take four identical four-patch blocks, and sew them together with rotational symmetry, like this:
It turns out that there are exactly 72 different ways to do this.
(Blocks equivalent under a reflection are considered the same, as are
blocks obtained by exchanging the roles of black and white, which are
merely stand-ins for arbitrary colors to be chosen later.) Here is
the complete set of 72:
It's immediately clear that some of these resemble one another,
sometimes so strongly that it can be hard to tell how they differ,
while others are very distinctive and unique-seeming. I wanted to
make the computer classify the blocks on the basis of similarity.
My idea was to try to find a way to get the computer to notice which
blocks have distinctive components of one color. For example, many
blocks have a distinctive diamond shape
in the center.
Some have a pinwheel like this:
which also has the diamond in the middle, while others have a different
kind of pinwheel with no diamond:
I wanted to enumerate such components and ask the computer to list which
blocks contained which shapes; then group them by similarity,
the idea being that that blocks with the same distinctive components are similar.
The program suite uses a compact notation of blocks and of shapes that
makes it easy to figure out which blocks contain which distinctive components.
Since each block is made of four identical four-patches, it's enough
just to examine the four-patches. Each of the half-square triangle
patches can be oriented in two ways:
Here are two of the 12 ways to orient the patches in a four-patch:
Each 16-patch is made of four four-patches, and you must imagine that the
four-patches shown above are in the upper-left position in the
16-patch. Then symmetry of the 16-patch block means that triangles with the
same label are in positions that are symmetric with respect to the
entire block. For example, the two triangles labeled b are on
opposite sides of the block's northwest-southeast diagonal. But there
is no symmetry of the full 16-patch block that carries triangle d to
triangle g, because d is on the edge of the block, while g is in the interior.
Triangles must be colored opposite colors if they are part of the same
patch, but other than that there are no constraints on the coloring.
A block might, of course, have patches in both orientations:
All the blocks with diagonals oriented this way are assigned
descriptors made from the letters bbdefgii.
Once you have chosen one of the 12 ways to orient the diagonals in the
four-patch, you still have to color the patches. A descriptor like
bbeeffii describes the orientation of the diagonal lines in the
squares, but it does not describe the way the four patches are
colored; there are between 4 and 8 ways to color each sort of
four-patch. For example, the bbeeffii four-patch shown earlier can be colored in six different ways:
In each case, all four diagonals run from northwest to southeast.
(All other ways of coloring this four-patch are equivalent to one of these
under one or more of rotation, reflection, and exchange of black and
white.)
We can describe a patch by listing the descriptors of the eight
triangles, grouped by which triangles form connected regions. For
example, the first block above is:
b/bf/ee/fi/i
because there's an isolated white b triangle, then a black parallelogram
made of a b and an f patch, then a white triangle made from the
two white e triangles, then another parallelogram made from the black f
and i, and finally in the middle, the white i. (The two white e
triangles appear to be separated, but when four of these four-patches are
joined into a 16-patch block, the two white e patches will be
adjacent and will form a single large triangle: )
The other five bbeeffii four-patches are, in the same order they are shown above:
b/b/e/e/f/f/i/i
b/b/e/e/fi/fi
b/bfi/ee/f/i
bfi/bfi/e/e
bf/bf/e/e/i/i
All six have bbeeffii, but grouped differently depending on the
colorings. The second one ( b/b/e/e/f/f/i/i) has no regions with
more than one triangle; the fifth (
bfi/bfi/e/e) has two large regions of three triangles each, and two
isolated triangles. In the latter four-patch, the bfi in the
descriptor has three letters because the patch has a corresponding
distinctive component made of three triangles.
I made up a list of the descriptors for all 72 blocks; I think I did
this by hand. (The work directory contains a blocks
file that maps
blocks to their descriptors, but the
Makefile does
not say how to build it, suggesting that it was not automatically
built.) From this list one can automatically
extract a
list of descriptors of interesting
shapes: an
interesting shape is two or more letters that appear together in some
descriptor. (Or it can be the single letter j, which is
exceptional; see below.) For example, bffh represents a distinctive
component. It can only occur in a patch that has a b, two fs, and
an h, like this one:
and it will only be significant if the b, the two fs, and the h are
the same color:
in which case you get this distinctive and interesting-looking hook
component.
There is only one block that includes this distinctive hook component;
it has descriptor b/bffh/ee/j, and looks like this: . But some of the distinctive
components are more common. The ee component represents the large white half-diamonds on the four sides.
A block with "ee" in its descriptor always looks like this:
and the blocks formed from such patches always have a distinctive half-diamond component on
each edge, like this:
(The stippled areas vary from block to block, but the blocks with ee
in their descriptors always have the half-diamonds as shown.)
The blocks listed at http://hop.perl.plover.com/quilt/analysis/images/ee.html
all have the ee component. There are many differences between them, but
they all have the half-diamonds in common.
Other distinctive components have similar short descriptors. The two pinwheels I
mentioned above are
gh and
fi, respectively; if you look at
the list of gh blocks
and
the list of fi blocks
you'll see all the blocks with each kind of pinwheel.
Descriptor j is an exception. It makes an interesting shape all by itself,
because any block whose patches have j in their descriptor will have
a distinctive-looking diamond component in the center. The four-patch looks like
this:
so the full sixteen-patch looks like this:
where the stippled parts can vary. A look at the list of blocks with
component
j will
confirm that they all have this basic similarity.
I had made a list of the descriptors for each of the the 72 blocks, and from this I extracted a list of the descriptors for interesting
component shapes.
Then it was only a matter of finding the component descriptors in the
block descriptors to know which blocks contained which components; if the two blocks share two different distinctive components,
they probably look somewhat similar.
Then I sorted the blocks into groups, where two blocks were in the
same group if they shared two distinctive components. The resulting
grouping
lists, for each block, which other blocks have at least two shapes in
common with it. Such blocks do indeed tend to look quite similar.
This strategy was actually the second thing I tried; the first thing
didn't work out well. (I forget just what it was, but I think it
involved finding polygons in each block that had white inside and
black outside, or vice versa.) I was satisfied enough with this
second attempt that I considered the project a success and stopped
work on it.
The complete final results were:
This tabulation of blocks that are somewhat similar
This tabulation of blocks that are distinctly similar (This is the final product; I consider this a sufficiently definitive listing of “similar blocks”.)
This tabulation of blocks that are extremely similar
And these tabulations of all the blocks with various distinctive components:
bd
bf
bfh
bfi
cd
cdd
cdf
cf
cfi
ee
eg
egh
egi
fgh
fh
fi
gg
ggh
ggi
gh
gi
j
It may also be interesting to browse the work directory.Mark Dominustag:blog.plover.com,2014:/misc/quilt-analysisSun, 20 Jul 2014 00:00:00 +0000Fun with (Kalman) Filters Part I
http://idontgetoutmuch.wordpress.com/2014/07/19/fun-with-kalman-filters-part-i/
Suppose we wish to estimate the mean of a sample drawn from a normal distribution. In the Bayesian approach, we know the prior distribution for the mean (it could be a non-informative prior) and then we update this with our observations to create the posterior, the latter giving us improved information about the distribution of the mean. In symbols
Typically, the samples are chosen to be independent, and all of the data is used to perform the update but, given independence, there is no particular reason to do that, updates can performed one at a time and the result is the same; nor is the order of update important. Being a bit imprecise, we have
The standard notation in Bayesian statistics is to denote the parameters of interest as and the observations as . For reasons that will become apparent in later blog posts, let us change notation and label the parameters as and the observations as .
Let us take a very simple example of a prior where is known and then sample from a normal distribution with mean and variance for the -th sample where is known (normally we would not know the variance but adding this generality would only clutter the exposition unnecessarily).
The likelihood is then
As we have already noted, instead of using this with the prior to calculate the posterior, we can update the prior with each observation separately. Suppose that we have obtained the posterior given samples (we do not know this is normally distributed yet but we soon will):
Then we have
Writing
and then completing the square we also obtain
More Formally
Now let’s be a bit more formal about conditional probability and use the notation of -algebras to define and where , is as before and . We have previously calculated that and that and the tower law for conditional probabilities then allows us to conclude . By Jensen’s inequality, we have
Hence is bounded in and therefore converges in and almost surely to . The noteworthy point is that if if and only if converges to 0. Explicitly we have
which explains why we took the observations to have varying and known variances. You can read more in Williams’ book (Williams 1991).
A Quick Check
We have reformulated our estimation problem as a very simple version of the celebrated Kalman filter. Of course, there are much more interesting applications of this but for now let us try “tracking” the sample from the random variable.
> {-# OPTIONS_GHC -Wall #-}
> {-# OPTIONS_GHC -fno-warn-name-shadowing #-}
> {-# OPTIONS_GHC -fno-warn-type-defaults #-}
> {-# OPTIONS_GHC -fno-warn-unused-do-bind #-}
> {-# OPTIONS_GHC -fno-warn-missing-methods #-}
> {-# OPTIONS_GHC -fno-warn-orphans #-}
> module FunWithKalmanPart1 (
> obs
> , nObs
> , estimates
> , uppers
> , lowers
> ) where
>
> import Data.Random.Source.PureMT
> import Data.Random
> import Control.Monad.State
> var, cSquared :: Double
> var = 1.0
> cSquared = 1.0
>
> nObs :: Int
> nObs = 100
> createObs :: RVar (Double, [Double])
> createObs = do
> x <- rvar (Normal 0.0 var)
> ys <- replicateM nObs $ rvar (Normal x cSquared)
> return (x, ys)
>
> obs :: (Double, [Double])
> obs = evalState (sample createObs) (pureMT 2)
>
> updateEstimate :: (Double, Double) -> (Double, Double) -> (Double, Double)
> updateEstimate (xHatPrev, varPrev) (y, cSquared) = (xHatNew, varNew)
> where
> varNew = recip (recip varPrev + recip cSquared)
> xHatNew = varNew * (y / cSquared + xHatPrev / varPrev)
>
> estimates :: [(Double, Double)]
> estimates = scanl updateEstimate (y, cSquared) (zip ys (repeat cSquared))
> where
> y = head $ snd obs
> ys = tail $ snd obs
>
> uppers :: [Double]
> uppers = map (\(x, y) -> x + 3 * (sqrt y)) estimates
>
> lowers :: [Double]
> lowers = map (\(x, y) -> x - 3 * (sqrt y)) estimates
Bibliography
Williams, David. 1991. Probability with Martingales. Cambridge University Press.Dominic Steinitzhttp://idontgetoutmuch.wordpress.com/?p=713Sat, 19 Jul 2014 16:37:07 +0000A Tutorial on Church Representations
http://jozefg.bitbucket.org/posts/2014-07-19-church-tutorial.html
http://jozefg.bitbucket.org/posts/2014-07-19-church-tutorial.htmlSat, 19 Jul 2014 00:00:00 +0000[gggpgqye] Narrow type signatures which can be widened
http://kenta.blogspot.com/2014/07/gggpgqye-find-narrow-type-signatures.html
Create a tool to find type signatures that are less polymorphic than would be inferred by type inference.This is a solution in search of a problem.Kentag:blogger.com,1999:blog-6757805.post-4194554597026468212Fri, 18 Jul 2014 16:55:00 +0000On uninhabited types and inconsistent logics
http://blog.plover.com/CS/a-to-b.html
Earlier this week I gave a talk about the Curry-Howard
isomorphism. Talks never go quite
the way you expect. The biggest sticking point was my assertion that
there is no function with the type a → b. I mentioned this as a
throwaway remark on slide 7, assuming that everyone would agree
instantly, and then we got totally hung up on it for about twenty
minutes.
Part of this was my surprise at discovering that most of the audience
(members of the Philly Lambda functional programming group) was not
familiar with the Haskell type system. I had assumed that most of the
members of a functional programming interest group would be familiar
with one of Haskell, ML, or Scala, all of which have the same basic
type system. But this was not the case. (Many people are primarily
interested in Scheme, for example.)
I think the main problem was that I did not make clear to the audience
what Haskell means when it says that a function has type a → b. At the
talk, and then later on
Reddit
people asked
what about a function that takes an integer and returns a string:
doesn't it have type a → b?
If you know one of the HM languages, you know that of course it
doesn't; it has type Int → String, which is not the same at all. But I
wasn't prepared for this confusion and it took me a while to formulate
the answer. I think I underestimated the degree to which I have
internalized the behavior of Hindley-Milner type systems after twenty
years. Next time, I will be better prepared, and will say something
like the following:
A function which takes an integer and returns a string does not have
the type a → b; it has the type Int → String. You must pass it an
integer, and you may only use its return value in a place that makes
sense for a string. If f has this type, then 3 +
f 4 is a compile-time type error because Haskell knows that f
returns a string, and strings do not work with +.
But if f had
the type a → b, then 3 + f 4 would be legal, because context requires that
f return a number, and the type a → b says that it can return a
number, because a number is an instance of the completely general type
b. The type a → b, in contrast to Int → String, means that b
and a are completely unconstrained.
Say function f had type a → b. Then you would be able to use the
expression f x in any context that was expecting any sort of return
value; you could write any or all of:
3 + f x
head(f x)
"foo" ++ f x
True && f x
and they would all type check correctly, regardless of the type of
x. In the first line, f x would return a number; in the second
line f would return a list; in the third line it would return a
string, and in the fourth line it would return a boolean. And in each
case f could be able to do what was required regardless of the type
of x, so without even looking at x. But how could you possibly
write such a function f? You can't; it's impossible.
Contrast this with the identity function id, which has type a → a. This says that id always returns a value whose type is the same as
that if its argument. So you can write
3 + id x
as long as x has the right type for +, and you can write
head(id x)
as long as x has the
right type for head, and so on. But for f to have the type a → b, all those
would have to work regardless of the type of the argument to f. And
there is no way to write such an f.
Actually I wonder now if part of the problem is that we like to write
a → b when what we really mean is the type ∀a.∀b.a → b. Perhaps making
the quantifiers explicit would clear things up? I suppose it probably
wouldn't have, at least in this case.
The issue is a bit complicated by the fact that the function
loop :: a -> b
loop x = loop x
does have the type a → b, and, in a language with exceptions, throw
has that type also; or consider Haskell
foo :: a -> b
foo x = undefined
Unfortunately, just as I thought I was getting across the explanation
of why there can be no function with type a → b, someone brought up
exceptions and I had to mutter and look at my shoes. (You can also take
the view that these functions have type a → ⊥, but the logical
principle ⊥ → b is unexceptionable.)
In fact, experienced practitioners will realize, the instant the type
a → b appears, that they have written a function that never returns.
Such an example was directly responsible for my own initial interest
in functional programming and type systems; I read a 1992 paper (“An
anecdote about ML type
inference”)
by Andrew R. Koenig in which he described writing a merge sort
function, whose type was reported (by the SML type inferencer) as [a]
-> [b], and the reason was that it had a bug that would cause it to
loop forever on any nonempty list. I came back from that conference
convinced that I must learn ML, and Higher-Order Perl was a direct
(although distant) outcome of that conviction.
Any discussion of the Curry-Howard isomorphism, using Haskell as an
example, is somewhat fraught with trouble, because Haskell's type
logic is utterly inconsistent. In addition to the examples above, in
Haskell one can write
fix :: (a -> a) -> a
fix f = let x = fix f
in f x
and as a statement of logic, is patently false.
This might be an argument in favor of the Total Functional
Programming
suggested by D.A. Turner and others.Mark Dominustag:blog.plover.com,2014:/CS/a-to-bFri, 18 Jul 2014 16:01:00 +0000Toward a Projectivistic Theory of Gender, Identity, and Social Categorization
http://winterkoninkje.dreamwidth.org/94494.html
As discussed last time there's a deep-seated problem with performativity as a theory of social categorization. Specifically, it puts the focus on the wrong thing. That our actions are performative in nature gives us important insight into the role agency plays both in forming our own identities and in defending those identities against silencing, marginalization, oppression, and colonialism. But, by centering discussions of identity on our own personal agency we miss out on other important facets of the issue. When we say that someone belongs to a category, we do so because we've decided they belong to the category, or because we think they belong to the category. The statement that they belong to the category is not merely true (or false), we are projecting it to be true (or false). That is, we do not passively observe people's gender, race, class, etc; instead we actively project our own notions of gender, race, class, etc upon them. This projecting of beliefs onto others is called projectivism[1].
Interestingly, by localizing "truth" as the beliefs we hold to be true[2], the projective act is itself performative: by projecting something to be true, one comes to believe that it is true. And yet there is no reason to suppose these beliefs are correct (local truths need not be global truths), nor that they will agree with others' beliefs (local truths need not be true in other locales). Crucially, in the case of categorizing or identifying ourselves, we have access to our own personal thoughts, feelings, memories, subconscious inclinations, etc. Whereas, when others are categorizing us, they do not; they can only observe our bodies, our actions, and the results of our actions. Thus arises the discrepancy in cases like transgenderism. When self-identifying, we may well prize our internal observations over our externally observable state. Nevertheless, others will continue to project their categorizations upon us, regardless of our self-identification.
Not only do people project categories onto others, we do it compulsively. Our persistent and ubiquitous gendering of others is an especially powerful example, but it is in no way unique. Projecting race is another example. And in professional cultures where there are sharply contested borders between "tribes" (e.g., academia and hacker culture), projecting these "tribes" is yet another. This compulsive projectivism —or, more particularly, our unconsciousness of it— is where issues arise.
When we are not typically confronted with evidence that our projections are mistaken, our projectivism becomes almost unconscious. Once there, we fail to notice the fact that we are actively projecting and we come to believe we're passively observing truths about the world. So when our projections turn out to be mistaken, we get a feeling of betrayal, we feel like the person whose identity we were mistaken about was "lying" to us. This subsequent projection that they were "lying" stems from the fact that we mistook our earlier projections for mere observations. Thus, because of an original error on our part, we end up imputing that others are being dishonest or deceptive.
When the identity one desires to be seen as (which may differ from the identity they claim for themselves) is often or easily at odds with the identities projected upon them, they understandably become concerned about trying to avoid these projections of "lying". If one can successfully avoid projections of "lying" they are said to "pass", terminology which turns around and suggests that they were in fact lying the whole time and only managed not to get caught. This terminology is, of course, deeply problematic.
Simply acknowledging compulsive projectivism is not enough. To undo the damage caused by misgendering, racial profiling, stereotyping, and other misprojections, we must lift this knowledge up and remain consciously aware that the beliefs we project onto others are not an observation of their identities. We must denaturalize the projectivist assumption that our beliefs are others' truths, by discontinuing the use words like "passing" which rely on that assumption. And when we feel betrayed we must locate that feeling within ourselves and stop projecting it in bad faith. The performative theory highlights the positive role of agency in our lives, but agency alone is not enough. The projectivistic theory extends this to highlight the negative role of agency when used to deny or overwhelm the agency of others.
[1] I do not mean this terminology to be the same as Hume's notion of projectivism, though of course both terms have the same etymology. Hume's projectivism is popular in the ethics literature, with which I am largely unfamiliar; thus, my use of the term here is not meant to entail whatever baggage it may have accrued in that literature.
[2] While it is not usually presented as such, Austin's original definition of performative speech acts should also only hold up to localized truth. In the classical example "I now pronounce you married", by saying the words one does the deed of pronouncing the couple to be married. However, the pronouncement of marriage does not cause the couple to be married in a universal sense; it only causes them to be married in the current jurisdiction, and a different jurisdiction may or may not recognize that marriage as valid. Because the marriage must be localized, therefore the pronouncement of marriage must be localized: one can't pronounce a couple to be married (everywhere), they can only pronounce them to be married (here, or there, or wherever). Thus, the deed performed by the utterance of the words is a localized deed: the pronouncement of a localized wedding.
Twitter
Facebook
Google+
Tumblr
commentstag:dreamwidth.org,2010-05-25:518115:94494Sat, 28 Jun 2014 03:27:10 +0000I've forgotten how to write
http://winterkoninkje.dreamwidth.org/95307.html
I've forgotten how to write. Somewhere along the way I've forgotten how to say, what I mean. Little sticks and thistles, they burrow under your skin like dry wind and the leaves you brush from your faces. And you find yourself there, looking over, looking out, and turn to tell another how you came to this place, this pretty place, and all you find are tangled weeds and hills and where was the path where you left that friend you thought had come with you
I have half a dozen half written posts, if half written means written and my mind keeps telling me to edit to edit to go over once more, unable to let go, unable to let slip a word lest it falls all out and i somehow say what i somehow mean and someone takes offense. Offence. That word of our times, that police baton with which we beat the helpless, refuse to listen to the stories, those stories once heard we proclaim have "set us free" but we leave the authors beaten, unwilling to look at their lives lest we feel too closely the grip of that truncheon in our fist.
Half a dozen half written posts, weeks of thoughts writ out, on programs and mathematics and words and history. Thoughts I cannot set free. They haunt me, they call me beckoning to spill once again that mental blood to pore and pore over them and wring them dry of every drip of humanity so I can hang out the scraps and let others see how terribly clever i am. I never wanted to be clever, never wanted to be seen like that. I only wanted, once, to be free. From the heartache of a harrowing life, from the illusions and false idols, from my own ignorance. And now these thoughts tie me up in clever little knots, and have me writing bad poetry
Twitter
Facebook
Google+
Tumblr
commentstag:dreamwidth.org,2010-05-25:518115:95307Thu, 10 Jul 2014 01:47:14 +0000A Word on Words
http://winterkoninkje.dreamwidth.org/95904.html
I'd like to take this moment to point out that all forms of binarism are bad. (Including the binarist notion that all things are either "good" or "bad".) I feel like this has to be pointed out because we, every one of us, has a nasty habit: in our overzealousness to tear down one binary, we do so by reinforcing other binaries. So let me say again. All forms of binarism are bad.
It's well-known that I've had a long, fraught history with certain "feminist" communities, due to which I have heretofore disavowed that label. Because of these persistent conflicts, around ten years ago I retreated from feminist circles and communities. However, over the past year I have rejoined a number of feminist circles— or rather, I have joined womanist, black feminist, transfeminist, and queer feminist circles. And thanks to this reinvolvement with feminist activism I have come, once again, to feel a certain attachment to that word: "feminist". The attachment feels strange to me now, having disavowed it for so long in favor of "womanism", "black feminism", "transfeminism", and "queer feminism". But because of this attachment I feel, once more, the need to reclaim feminism away from those "feminist" communities whose philosophy and political methods I continue to disavow.
So, to piss everyone off once more: ( a manifesto. )
Edit 2014.07.13: Added footnotes [2] and [3].
Twitter
Facebook
Google+
Tumblr
commentstag:dreamwidth.org,2010-05-25:518115:95904Sun, 13 Jul 2014 04:23:00 +0000Information content and allele frequency difference
http://blog.malde.org/posts/esi-vs-freq.html
http://blog.malde.org/posts/esi-vs-freq.htmlThu, 17 Jul 2014 12:00:00 +0000Guess what this does (solution)
http://blog.plover.com/prog/perl/barewords.html
A few weeks ago I asked people to
predict,
without trying it first, what this would print:
perl -le 'print(two + two == five ? "true" : "false")'
(If you haven't seen this yet, I recommend that you guess, and then
test your guess, before reading the rest of this article.)
People familiar with Perl guess that it will print true; that is
what I guessed. The reasoning is as follows: Perl is willing to treat
the unquoted strings two and five as strings, as if they had been
quoted, and is also happy to use the + and == operators on them,
converting the strings to numbers in its usual way. If the strings
had looked like "2" and "5" Perl would have treated them as 2 and
5, but as they don't look like decimal numerals, Perl interprets them
as zeroes. (Perl wants to issue a warning about this, but the warning is not enabled by default.
Since the two and five are treated as
zeroes, the result of the == comparison are true, and the string
"true" should be selected and printed.
So far this is a little bit odd, but not excessively odd; it's the
sort of thing you expect from programming languages, all of which more
or less suck. For example, Python's behavior, although different, is
about equally peculiar. Although Python does require that the strings
two and five be quoted, it is happy to do its own peculiar thing
with "two" + "two" == "five", which happens to be false: in Python
the + operator is overloaded and has completely different behaviors
on strings and numbers, so that while in Perl "2" + "2" is the
number 4, in Python is it is the string 22, and "two" + "two"
yields the string "twotwo". Had the program above actually printed
true, as I expected it would, or even false, I would not have
found it remarkable.
However, this is not what the program does do. The explanation of two
paragraphs earlier is totally wrong. Instead, the program prints
nothing, and the reason is incredibly convoluted and bizarre.
First, you must know that print has an optional first argument. (I
have plans for an article about how optional first argmuents are almost
always a bad move, but contrary to my usual practice I will not insert
it here.) In Perl, the print function can be invoked in two ways:
print HANDLE $a, $b, $c, …;
print $a, $b, $c, …;
The former prints out the list $a, $b, $c, … to the filehandle
HANDLE; the latter uses the default handle, which typically points
at the terminal. How does Perl decide which of these forms is being
used? Specifically, in the second form, how does it know that $a is
one of the items to be printed, rather than a variable containing the filehandle
to print to?
The answer to this question is further complicated by the fact that
the HANDLE in the first form could be either an unquoted string,
which is the name of the handle to print to, or it could be a variable
containing a filehandle value. Both of these prints should do the
same thing:
my $handle = \*STDERR;
print STDERR $a, $b, $c;
print $handle $a, $b, $c;
Perl's method to decide whether a particular print uses an explicit
or the default handle is a somewhat complicated heuristic. The basic
rule is that the filehandle, if present, can be distinguished because
its trailing comma is omitted. But if the filehandle were allowed to
be the result of an arbitrary expression, it might be difficult for
the parser to decide where there was a a comma; consider the
hypothetical expression:
print $a += EXPRESSION, $b $c, $d, $e;
Here the intention is that the $a += EXPRESSION, $b expression
calculates the filehandle value (which is actually retrieved from $b, the
$a += … part being executed only for its side effect) and the
remaining $c, $d, $e are the values to be printed. To allow this
sort of thing would be way too confusing to both Perl and to the
programmer. So there is the further rule that the filehandle
expression, if present, must be short, either a simple scalar
variable such as $fh, or a bare unqoted string that is in the right
format for a filehandle name, such as `HANDLE``. Then the parser need
only peek ahead a token or two to see if there is an upcoming comma.
So for example, in
print STDERR $a, $b, $c;
the print is immediately followed by STDERR, which could be a
filehandle name, and STDERR is not followed by a comma, so STDERR
is taken to be the name of the output handle. And in
print $x, $a, $b, $c;
the print is immediately followed by the simple scalar value $x,
but this $x is followed by a comma, so is considered one of the
things to be printed, and the target of the print is the default
output handle.
In
print STDERR, $a, $b, $c;
Perl has a puzzle: STDERR looks like a filehandle, but it is
followed by a comma. This is a compile-time error; Perl complains “No
comma allowed after filehandle” and aborts. If you want to print the
literal string STDERR, you must quote it, and if you want to print A, B,
and C to the standard error handle, you must omit the first comma.
Now we return the the original example.
perl -le 'print(two + two == five ? "true" : "false")'
Here Perl sees the unquoted string two which could be a filehandle
name, and which is not followed by a comma. So it takes the first
two to be the output handle name. Then it evaluates the expression
+ two == five ? "true" : "false"
and obtains the value true. (The leading + is a unary plus
operator, which is a no-op. The bare two and five are taken to be
string constants, which, compared with the numeric == operator, are
considered to be numerically zero, eliciting the same warning that I
mentioned earlier that I had not enabled. Thus the comparison Perl
actually does is is 0 == 0, which is true, and the resulting string is
true.)
This value, the string true, is then printed to the filehandle named
two. Had we previously opened such a filehandle, say with
open two, ">", "output-file";
then the output would have been sent to the filehandle as usual.
Printing to a non-open filehandle elicits an optional warning from
Perl, but as I mentioned, I have not enabled warnings, so the print
silently fails, yielding a false value.
Had I enabled those optional warnings, we would have seen a plethora
of them:
Unquoted string "two" may clash with future reserved word at -e line 1.
Unquoted string "two" may clash with future reserved word at -e line 1.
Unquoted string "five" may clash with future reserved word at -e line 1.
Name "main::two" used only once: possible typo at -e line 1.
Argument "five" isn't numeric in numeric eq (==) at -e line 1.
Argument "two" isn't numeric in numeric eq (==) at -e line 1.
print() on unopened filehandle two at -e line 1.
(The first four are compile-time warnings; the last three are issued
at execution time.) The crucial warning is the one at the end,
advising us that the output of print was directed to the filehandle
two which was never opened for output.
[ Addendum 20140718: I keep thinking of the following remark of Edsger W. Dijkstra:
[This phenomenon] takes one of two different forms: one programmer
places a one-line program on the desk of another and … says, "Guess
what it does!" From this observation we must conclude that this
language as a tool is an open invitation for clever tricks; and
while exactly this may be the explanation for some of its appeal,
viz., to those who like to show how clever they are, I am sorry, but
I must regard this as one of the most damning things that can be
said about a programming language.
But my intent is different than what Dijkstra describes. His
programmer is proud, but I am discgusted. Incidentally, I believe
that Dijkstra was discussing APL here. ]Mark Dominustag:blog.plover.com,2014:/prog/perl/barewordsThu, 17 Jul 2014 00:00:00 +0000Haskell data analysis: Reading NetCDF files
http://www.skybluetrades.net/blog/posts/2014/07/16/data-analysis-ao1-1.html
http://www.skybluetrades.net/blog/posts/2014/07/16/data-analysis-ao1-1.htmlWed, 16 Jul 2014 21:09:57 +0000Guess what this does
http://blog.plover.com/prog/perl/barewords-setup.html
Here's a Perl quiz that I confidently predict nobody will get right.
Without trying it first, what does the following program print?
perl -le 'print(two + two == five ? "true" : "false")'
(I will discuss the surprising answer tomorrow.)Mark Dominustag:blog.plover.com,2014:/prog/perl/barewords-setupWed, 16 Jul 2014 14:37:00 +0000Notes on the Advanced Akka course
http://alessandrovermeulen.me/2014/07/15/notes-on-the-advanced-akka-course/
The Advanced Akka course is provided by Typesafe and is aimed at teaching advanced usages of Akka. The course covers the basics of Akka, Remoting, Clustering, Routers, CRDTs, Cluster Sharding and Akka Persistance. The following post starts with a general introduction to Akka and presents the takeaways from the course as we experienced them.
A general overview of Akka
The reader which is already familiar with Akka can skip this section.
According to the Akka site this is Akka:
Akka is a toolkit and runtime for building highly
concurrent, distributed, and fault tolerant event-driven
applications on the JVM.
Akka achieves this by using Actors.
Actors are very lightweight concurrent entities.
Each Actor has a corresponding mailbox stored separately from the Actor. The Actors together with their mailboxes reside in an ActorSystem. Additionally, the ActorSystem contains the Dispatcher which executes the handling of a message by an actor. Each Actor only handles a single message at a time.
In Akka everything is remote by design and philosophy. In practice this means that each Actor is identified by its ActorRef. This is a reference to the actor which provides Location Transparency.
Actors communicate with each other by sending messages to an another Actor through an ActorRef. This sending of the message takes virtually no time.
In addition to ActorRef there exists also an ActorSelection which contains a path to one or more actors. Upon each sending of the message the path is traversed until the actor is found or when not. No message is send back when the actor is not found however.
States: Started - Stopped - Terminated
If an actor enters the Stopped state it first stops its child actors before entering the Terminated state.
Best-practices
Import the context.dispatcher instead of the global Scala ExecutionContext. It is the ExecutionContext managed by Akka. Using the global context causes the Actors to be run in the global Thread pool.
You should not use PoisonPill as it will be removed from future versions of Akka since it is not specific enough. Roll your own message to make sure the appropriate actions for graceful shutdown are done. Use context.stop to stop your actor.
Place your business logic in a separate trait and mix it in to the actor. This increases testability as you can easily unit test the trait containing the business logic. Also, you should put the creation of any child actors inside a separate method so the creation can be overridden from tests.
Remoting
With the Remoting extension it is possible to communicate with other Actor Systems. This communication is often done through ActorSelections instead of ActorRef.
Remoting uses Java serialisation by default which is slow and fragile in light of changing definitions. It is possible and recommended to use another mechanism such as Google Protobuf.
Clustering
Akka has a simple perspective on cluster management with regards to split-brain scenarios. Nodes become dead when they are observed as dead and they cannot resurrect. The only way a node can come up again is if it registers itself again.
When a net split happens the other nodes are marked as unreachable. When using a Singleton, this means that only the nodes that can reach the singleton will access it. The others will not decide on a new Singleton in order to prevent a split-brain scenario.
Another measure against split-brain is contacting the seed nodes in order. The first seed node is required to be up.
The seed nodes are tried in order.
FSM
There is an library for writing finite state machines called FSM. For larger actors it can be useful to use the FSM. Otherwise stick to pure become and unbecome.
FSM also has an interval timer for scheduling messages. However, the use of stay() resets the interval timer therefore you could have issues with never executing what is at the end of the timer.
Routers
There are two different kinds of routers: Pools and Groups. Pools are in charge of their own children and they are created and killed by the pool. Groups are configured with an ActorSelection that defines the actors to which the group should sent its messages. There are several implementations: Consistent Hash, Random, Round Robin, BroadCast, Scatter - Gather First, and Smallest Mailbox. The names are self-explanatory.
Synchronisation of data with CRDTs
Synchronising data between multiple nodes can be done by choosing your datatype so that If the timestamps and events are generated in one place no duplicate entries occur. Therefore merging a map from a different node in your map is easily done by copying entries you don’t already have to your own data.
This can be implemented by letting each member node broadcast which data-points they have. Each node can then detect which information is lacking and request the specific data from the node that claimed to have the data. At some future point in time all nodes will be in sync. This is called eventual consistency.
Singleton
If you have a singleton cluster manager proxy it only starts when the cluster is formed. A cluster is formed if a member connects. The proxy will then pass on the buffered messages.
Cluster Sharding
Sharding is a way to split up a group of actors in a cluster. This can be useful if the group is too large to fit in the memory of a single machine. The Cluster Sharding feature takes care of the partitioning of the actors using a hash you have to define with a function shardResolver. The sharded actors can be messaged with an unique identifier using ClusterSharding(system).shardRegion("Counter") which proxies the message to the correct actor.
ClusterSharding.start is what the Manager is to Singletons.
It is recommended to put the sharding functions into a singleton object for easy re-use of your shards, containing the functions to start the sharding extension and proxy to the shard etc. It is also convenient to adds tell and initialise helper functions to respectively send a message and initialise the actor by its unique id.
Akka Persistence
Akka persistence uses a Journal to store which messages were processed. One of the supported storage mechanisms is Cassandra. It is also possible to use a file-based journal which, of course, is not recommended.
In the current version of Akka there are two approaches to persistence: command sourcing and event sourcing. Simply but, in command storing each message is first persisted and then offered to the actor to do as it pleases whereas in event sourcing only the results of actions are persisted. The latter is preferred and will be the only remaining method in following versions.
Both methods support storing a snapshot of the current state and recovering from it.
Command Sourcing
The main problem with command sourcing lies in that all messages are replayed. This includes requests for information from dead actors which wastes resources for nothing. Moreover, in case of errors, the last message that killed the actor is also replayed and probably killing the actor again in the proces.
Event Sourcing
With event sourcing one only stores state changing events. Events are received by the receiveRecover method. External side-effects should be performed in the receive method. The code for the internal side-effect of the event should be the same in both the receive and receiveRecover methods. The actor or trait for this will be named PersistentActor.
Actor offloading
One can use Akka Persistence to “pause” long living actors, e.g. actors that have seen no activity lately. This frees up memory. When the actor is needed again it can be safely restored from the persistence layer.
Tidbits
Akka 3 is to be released “not super soon”. It will contain typed actors. The consequence of this is that the sender field will be removed from the actor. Therefore, for request-response, the ActorRef should be added to the request itself.
Concluding
The Advanced Akka course gives a lot of insights and concrete examples of how to use the advanced Akka features of clustering, sharding and persisting data across multiple nodes in order to create a system that really is highly available, resilient and scalable. It also touches on the bleeding edge functionalities, the ideas and concepts around it and what to expect next in this growing ecosystem.http://alessandrovermeulen.me/2014/07/15/notes-on-the-advanced-akka-courseTue, 15 Jul 2014 10:00:00 +0000Examining Hackage: extensible-effects
http://jozefg.bitbucket.org/posts/2014-07-15-reading-extensible-effects.html
http://jozefg.bitbucket.org/posts/2014-07-15-reading-extensible-effects.htmlTue, 15 Jul 2014 00:00:00 +0000Type-based lift
http://feedproxy.google.com/~r/RomanCheplyaka/~3/_i99PeIadAU/2014-07-15-type-based-lift.html
http://ro-che.info//articles/2014-07-15-type-based-lift.htmlMon, 14 Jul 2014 21:00:00 +0000Haskell Best Practices for Avoiding "Cabal Hell"
http://feedproxy.google.com/~r/SoftwareSimply/~3/95XwEEh-oPk/haskell-best-practices-for-avoiding.html
I posted this as a reddit comment and it was really well received, so I thought I'd post it here so it would be more linkable. A lot of people complain about "cabal hell" and ask what they can do to solve it. There are definitely things about the cabal/hackage ecosystem that can be improved, but on the whole it serves me quite well. I think a significant amount of the difficulty is a result of how fast things move in the Haskell community and how much more reusable Haskell is than other languages.
With that preface, here are my best practices that seem to make Cabal work pretty well for me in my development.
1. I make sure that I have no more than the absolute minimum number of packages installed as --global. This means that I don't use the Haskell Platform or any OS haskell packages. I install GHC directly. Some might think this casts too much of a negative light on the Haskell Platform. But everyone will agree that having multiple versions of a package installed at the same time is a significant cause of build problems. And that is exactly what the Haskell Platform does for you--it installs specific versions of packages. If you use Haskell heavily enough, you will invariably encounter a situation where you want to use a different version of a package than the one the Haskell Platform gives you.
2. Make sure ~/.cabal/bin is at the front of your path. Hopefully you already knew this, but I see this problem a lot, so it's worth mentioning for completeness.
3. Install happy and alex manually. These two packages generate binary executables that you need to have in ~/.cabal/bin. They don't get picked up automatically because they are executables and not package dependencies.
4. Make sure you have the most recent version of cabal-install. There is a lot of work going on to improve these tools. The latest version is significantly better than it used to be, so you should definitely be using it.
5. Become friends with "rm -fr ~/.ghc". This command cleans out your --user repository, which is where you should install packages if you're not using a sandbox. It sounds bad, but right now this is simply a fact of life. The Haskell ecosystem is moving so fast that packages you install today will be out of date in a few months if not weeks or days. We don't have purely functional nix-style package management yet, so removing the old ones is the pragmatic approach. Note that sandboxes accomplish effectively the same thing for you. Creating a new sandbox is the same as "rm -fr ~/.ghc" and then installing to --user, but has the benefit of not deleting everything else you had in --user.
6. If you're not working on a single project with one harmonious dependency tree, then use sandboxes for separate projects or one-off package compiles.
7. Learn to use --allow-newer. Again, things move fast in Haskell land. If a package gives you dependency errors, then try --allow-newer and see if the package will just work with newer versions of dependencies.
8. Don't be afraid to dive into other people's packages. "cabal unpack" makes it trivial to download the code for any package. From there it's often trivial to make manual changes to version bounds or even small code changes. If you make local changes to a package, then you can either install it to --user so other packages use it, or you can do "cabal sandbox add-source /path/to/project" to ensure that your other projects use the locally modified version. If you've made code changes, then help out the community by sending a pull request to the package maintainer. Edit: bergmark mentions that unpack is now "cabal get" and "cabal get -s" lets you clone the project's source repository.
9. If you can't make any progress from the build messages cabal gives you, then try building with -v3. I have encountered situations where cabal's normal dependency errors are not helpful. Using -v3 usually gives me a much better picture of what's going on and I can usually figure out the root of the problem pretty quickly.mightybytetag:blogger.com,1999:blog-8768401356830813531.post-2432647583227639482Sun, 13 Jul 2014 23:45:00 +0000Announcing engine-io and socket-io for Haskell
http://ocharles.org.uk/blog/posts/2014-07-13-announcing-socket-io-for-haskell.html
http://ocharles.org.uk/blog/posts/2014-07-13-announcing-socket-io-for-haskell.htmlSun, 13 Jul 2014 00:00:00 +0000Rearranging equations using a zipper
http://dorchard.wordpress.com/2014/07/10/rebalancing-equations-using-a-zipper/
Whilst experimenting with some ideas for a project, I realised I needed a quick piece of code to rearrange equations (defined in terms of +, *, -, and /) in AST form, e.g., given an AST for the equation x = y + 3, rearrange to get y = x - 3.
I realised that equations can be formulated as zippers over an AST, where operations for navigating the zipper essentially rearrange the equation. I thought this was quite neat, so I thought I would show the technique here. The code is in simple Haskell.
I’ll show the construction for a simple arithmetic calculus with the following AST data type of terms:
data Term = Add Term Term
| Mul Term Term
| Div Term Term
| Sub Term Term
| Neg Term
| Var String
| Const Integer
with some standard pretty printing code:
instance Show Term where
show (Add t1 t2) = (show' t1) ++ " + " ++ (show' t2)
show (Mul t1 t2) = (show' t1) ++ " * " ++ (show' t2)
show (Sub t1 t2) = (show' t1) ++ " - " ++ (show' t2)
show (Div t1 t2) = (show' t1) ++ " / " ++ (show' t2)
show (Neg t) = "-" ++ (show' t)
show (Var v) = v
show (Const n) = show n
where show' is a helper to minimise brackets e.g. pretty printing “-(v)” as “-v”.
show' :: Term -> String
show' (Var v) = v
show' (Const n) = show n
show' t@(Neg (Var v)) = show t
show' t@(Neg (Const n)) = show t
show' t = "(" ++ show t ++ ")"
Equations can be defined as pairs of terms, i.e., ‘T1 = T2′ where T1 and T2 are both represented by values of Term. However, instead, I’m going to represent equations via a zipper.
Zippers (described beautifully in the paper by Huet) represent values that have some subvalue “in focus”. The position of the focus can then be shifted through the value, refocussing on different parts. This is encoded by pairing a focal subvalue with a path to this focus, which records the rest of the value that is not in focus. For equations, the zipper type pairs a focus Term (which we’ll think of as the left-hand side of the equation) with a path (which we’ll think of as the right-hand side of the equation).
data Equation = Eq Term Path
Paths give a sequence of direction markers, essentially providing an address to the term in focus, starting from the root, where each marker is accompanied with the label of the parent node and the subtree of the branch not taken, i.e., a path going left is paired with the right subtree (which is not on the path to the focus).
data Path = Top (Either Integer String) -- At top: constant or variable
| Bin Op -- OR in a binary operation Op,
Dir -- in either left (L) or right (R) branch
Term -- with the untaken branch
Path -- and the rest of the equation
| N Path -- OR in the unary negation operation
data Dir = L | R
data Op = A | M | D | S | So | Do
The Op type gives tags for every operation, as well as additional tags So and Do which represent sub and divide but with arguments flipped. This is used to get an isomorphism between the operations that zip “up” and “down” the equation zipper, refocussing on subterms.
A useful helper maps tags to their operations:
opToTerm :: Op -> (Term -> Term -> Term)
opToTerm A = Add
opToTerm M = Mul
opToTerm D = Div
opToTerm S = Sub
opToTerm So = (\x -> \y -> Sub y x)
opToTerm Do = (\x -> \y -> Div y x)
Equations are pretty printed as follows:
instance Show Path where
show p = show . pathToTerm $ p
instance Show Equation where
show (Eq t p) = (show t) ++ " = " ++ (show p)
where pathToTerm converts paths to terms:
pathToTerm :: Path -> Term
pathToTerm (Top (Left c)) = Const c
pathToTerm (Top (Right v))= Var v
pathToTerm (Bin op L t p) = (opToTerm op) (pathToTerm p) t
pathToTerm (Bin op R t p) = (opToTerm op) t (pathToTerm p)
pathToTerm (N p) = Neg (pathToTerm p)
Now onto the zipper operations which providing rebalancing of the equation. Equations are zipped-down by left and right, which for a binary operation focus on either the left or right argument respectively, for unary negation focus on the single argument, and for constants or variables does nothing. When going left or right, the equations are rebalanced with their inverse arithmetic operations (show in the comments here):
left (Eq (Var s) p) = Eq (Var s) p
left (Eq (Const n) p) = Eq (Const n) p
left (Eq (Add t1 t2) p) = Eq t1 (Bin S L t2 p) -- t1 + t2 = p -> t1 = p - t2
left (Eq (Mul t1 t2) p) = Eq t1 (Bin D L t2 p) -- t1 * t2 = p -> t1 = p / t2
left (Eq (Div t1 t2) p) = Eq t1 (Bin M L t2 p) -- t1 / t2 = p -> t1 = p * t2
left (Eq (Sub t1 t2) p) = Eq t1 (Bin A L t2 p) -- t1 - t2 = p -> t1 = p + t2
left (Eq (Neg t) p) = Eq t (N p) -- -t = p -> t = -p
right (Eq (Var s) p) = Eq (Var s) p
right (Eq (Const n) p) = Eq (Const n) p
right (Eq (Add t1 t2) p) = Eq t2 (Bin So R t1 p) -- t1 + t2 = p -> t2 = p - t1
right (Eq (Mul t1 t2) p) = Eq t2 (Bin Do R t1 p) -- t1 * t2 = p -> t2 = p / t1
right (Eq (Div t1 t2) p) = Eq t2 (Bin D R t1 p) -- t1 / t2 = p -> t2 = t1 / p
right (Eq (Sub t1 t2) p) = Eq t2 (Bin S R t1 p) -- t1 - t2 = p -> t2 = t1 - p
right (Eq (Neg t) p) = Eq t (N p)
In both left and right, Add and Mul become subtraction and dividing, but in right in order for the the zipping-up operation to be the inverse, subtraction and division are represented using the flipped So and Do markers.
Equations are zipped-up by up, which unrolls one step of the path and reforms the term on the left-hand side from that on the right. This is the inverse of left and right:
up (Eq t1 (Top a)) = Eq t1 (Top a)
up (Eq t1 (Bin A L t2 p)) = Eq (Sub t1 t2) p -- t1 = t2 + p -> t1 - t2 = p
up (Eq t1 (Bin M L t2 p)) = Eq (Div t1 t2) p -- t1 = t2 * p -> t1 / t2 = p
up (Eq t1 (Bin D L t2 p)) = Eq (Mul t1 t2) p -- t1 = p / t2 -> t1 * t2 = p
up (Eq t1 (Bin S L t2 p)) = Eq (Add t1 t2) p -- t1 = p - t2 -> t1 + t2 = p
up (Eq t1 (Bin So R t2 p)) = Eq (Add t2 t1) p -- t1 = p - t2 -> t2 + t1 = p
up (Eq t1 (Bin Do R t2 p)) = Eq (Mul t2 t1) p -- t1 = p / t2 -> t2 * t1 = p
up (Eq t1 (Bin D R t2 p)) = Eq (Div t2 t1) p -- t1 = t2 / p -> t2 / t1 = p
up (Eq t1 (Bin S R t2 p)) = Eq (Sub t2 t1) p -- t1 = t2 - p -> t2 - t1 = p
up (Eq t1 (N p)) = Eq (Neg t1) p -- t1 = -p -> -t1 = p
And that’s it! Here is an example of its use from GHCi.
foo = Eq (Sub (Mul (Add (Var "x") (Var "y")) (Add (Var "x")
(Const 1))) (Const 1)) (Top (Left 0))
*Main> foo
((x + y) * (x + 1)) - 1 = 0
*Main> left $ foo
(x + y) * (x + 1) = 0 + 1
*Main> right . left $ foo
x + 1 = (0 + 1) / (x + y)
*Main> left . right . left $ foo
x = ((0 + 1) / (x + y)) - 1
*Main> up . left . right . left $ foo
x + 1 = (0 + 1) / (x + y)
*Main> up . up . left . right . left $ foo
(x + y) * (x + 1) = 0 + 1
*Main> up . up . up . left . right . left $ foo
((x + y) * (x + 1)) - 1 = 0
It is straightforward to prove that: up . left $ x = x (when left x is not equal to x) and up . right $ x = x(when right x is not equal to x).
Note, I am simply rebalancing the syntax of equations: this technique does not help if you have multiple uses of a variable and you want to solve the question for a particular variable, e.g. y = x + 1/(3x), or quadratics.
Here’s a concluding thought. The navigation operations left, right, and up essentially apply the inverse of the operation in focus to each side of the equation. We could therefore reformulate the navigation operations in terms of any group: given a term L ⊕ R under focus where ⊕ is the binary operation of a group with inverse operation -1, then navigating left applies ⊕ R-1 to both sides and navigating right applies ⊕ L-1. However, in this blog post there is a slight difference: navigating applies the inverse to both sides and then reduces the term of the left-hand side using the group axioms X ⊕ X-1 = I (where I is the identity element of the group) and X ⊕ I = X such that the term does not grow larger and larger with inverses.
I wonder if there are other applications, which have a group structure (or number of interacting groups), for which the above zipper approach would be useful?dorchardhttp://dorchard.wordpress.com/?p=295Thu, 10 Jul 2014 16:20:34 +00001HaskellADay: Up, up, and away!
http://logicaltypes.blogspot.com/2014/07/1haskelladay-up-up-and-away.html
I've taken it upon myself to submit problems, then show the solutions, for @1HaskellADay. I started this work on July 1st, 2014. So the next set of entries serve to collect what I've done, both problems and solutions, and, if a particular day posed a particularly interesting problem, that I solved, or, that I didn't solve, I'll capture that here, too.geophftag:blogger.com,1999:blog-4650294074444534066.post-2969917412601225441Sat, 12 Jul 2014 14:06:00 +0000The Four Rs of Programming Language Design (revisited)
http://dorchard.wordpress.com/2012/02/29/the-four-rs-of-programming-language-design-revisited/
Following my blog post last year about the “four Rs of programming language design” I wrote a short essay expanding upon the idea which has now been included in the online post-proceedings of the ACM Onward ’11 essay track (part of the SPLASH conference).
The essay was a lot of fun to write (I somehow end up referencing books from the 19th century, a sci-fi novel, 1984, and The Matrix!) and is a kind of mission statement (at least for myself) for language design; it is available on my research page here. I hope that it provides some food-for-thought for others interested in, or working in, language design.dorchardhttp://dorchard.wordpress.com/?p=147Wed, 29 Feb 2012 10:05:35 +0000Arrow's place in the Applicative/Monad hierarchy
http://gergo.erdi.hu/blog/2014-07-12-arrow's_place_in_the_applicative_monad_hierarchy
http://gergo.erdi.hu/blog/2014-07-12-arrow's_place_in_the_applicative_monad_hierarchySat, 12 Jul 2014 09:30:00 +0000Arrow's place in the Applicative/Monad hierarchy
http://gergo.erdi.hu/blog/2014-07-12-arrow's_place_in_the_applicative/monad_hierarchy
http://gergo.erdi.hu/blog/2014-07-12-arrow's_place_in_the_applicative/monad_hierarchySat, 12 Jul 2014 09:30:00 +0000Type classes: confluence, coherence and global uniqueness
http://feedproxy.google.com/~r/ezyang/~3/gIt01Sq_uGw/
Today, I'd like to talk about some of the core design principles behind type classes, a wildly successful feature in Haskell. The discussion here is closely motivated by the work we are doing at MSRC to support type classes in Backpack. While I was doing background reading, I was flummoxed to discover widespread misuse of the terms "confluence" and "coherence" with respect to type classes. So in this blog post, I want to settle the distinction, and propose a new term, "global uniqueness of instances" for the property which people have been colloquially referred to as confluence and coherence.
Let's start with the definitions of the two terms. Confluence is a property that comes from term-rewriting: a set of instances is confluent if, no matter what order
constraint solving is performed, GHC will terminate with a canonical set
of constraints that must be satisfied for any given use of a type class.
In other words, confluence says that we won't conclude that a program
doesn't type check just because we swapped in a different constraint
solving algorithm.
Confluence's closely related twin is coherence (defined in the paper "Type
classes: exploring the design space"). This property states that
every different valid typing derivation of a program leads to a
resulting program that has the same dynamic semantics. Why could
differing typing derivations result in different dynamic semantics? The
answer is that context reduction, which picks out type class instances,
elaborates into concrete choices of dictionaries in the generated code.
Confluence is a prerequisite for coherence, since one
can hardly talk about the dynamic semantics of a program that doesn't
type check.
So, what is it that people often refer to when they compare Scala type classes to Haskell type classes? I am going to refer to this as global uniqueness of instances, defining to say: in a fully compiled program, for any type, there is at most one
instance resolution for a given type class. Languages with local type
class instances such as Scala generally do not have this property, and
this assumption is a very convenient one when building abstractions like sets.
So, what properties does GHC enforce, in practice?
In the absence of any type system extensions, GHC's employs a set of
rules to ensure that type
class resolution is confluent and coherent. Intuitively, it achieves
this by having a very simple constraint solving algorithm (generate
wanted constraints and solve wanted constraints) and then requiring the
set of instances to be nonoverlapping, ensuring there is only
ever one way to solve a wanted constraint. Overlap is a
more stringent restriction than either confluence or coherence, and
via the OverlappingInstances and IncoherentInstances, GHC
allows a user to relax this restriction "if they know what they're doing."
Surprisingly, however, GHC does not enforce global uniqueness of
instances. Imported instances are not checked for overlap until we
attempt to use them for instance resolution. Consider the following program:
-- T.hs
data T = T
-- A.hs
import T
instance Eq T where
-- B.hs
import T
instance Eq T where
-- C.hs
import A
import B
When compiled with one-shot compilation, C will not report
overlapping instances unless we actually attempt to use the Eq
instance in C. This is by
design:
ensuring that there are no overlapping instances eagerly requires
eagerly reading all the interface files a module may depend on.
We might summarize these three properties in the following manner.
Culturally, the Haskell community expects global uniqueness of instances
to hold: the implicit global database of instances should be
confluent and coherent. GHC, however, does not enforce uniqueness of
instances: instead, it merely guarantees that the subset of the
instance database it uses when it compiles any given module is confluent and coherent. GHC does do some
tests when an instance is declared to see if it would result in overlap
with visible instances, but the check is by no means
perfect;
truly, type-class constraint resolution has the final word. One
mitigating factor is that in the absence of orphan instances, GHC is
guaranteed to eagerly notice when the instance database has overlap (assuming that the instance declaration checks actually worked...)
Clearly, the fact that GHC's lazy behavior is surprising to most
Haskellers means that the lazy check is mostly good enough: a user
is likely to discover overlapping instances one way or another.
However, it is relatively simple to construct example programs which
violate global uniqueness of instances in an observable way:
-- A.hs
module A where
data U = X | Y deriving (Eq, Show)
-- B.hs
module B where
import Data.Set
import A
instance Ord U where
compare X X = EQ
compare X Y = LT
compare Y X = GT
compare Y Y = EQ
ins :: U -> Set U -> Set U
ins = insert
-- C.hs
module C where
import Data.Set
import A
instance Ord U where
compare X X = EQ
compare X Y = GT
compare Y X = LT
compare Y Y = EQ
ins' :: U -> Set U -> Set U
ins' = insert
-- D.hs
module Main where
import Data.Set
import A
import B
import C
test :: Set U
test = ins' X $ ins X $ ins Y $ empty
main :: IO ()
main = print test
-- OUTPUT
$ ghc -Wall -XSafe -fforce-recomp --make D.hs
[1 of 4] Compiling A ( A.hs, A.o )
[2 of 4] Compiling B ( B.hs, B.o )
B.hs:5:10: Warning: Orphan instance: instance [safe] Ord U
[3 of 4] Compiling C ( C.hs, C.o )
C.hs:5:10: Warning: Orphan instance: instance [safe] Ord U
[4 of 4] Compiling Main ( D.hs, D.o )
Linking D ...
$ ./D
fromList [X,Y,X]
Locally, all type class resolution was coherent: in the subset of
instances each module had visible, type class resolution could be done
unambiguously. Furthermore, the types of ins and ins'
discharge type class resolution, so that in D when the database
is now overlapping, no resolution occurs, so the error is never found.
It is easy to dismiss this example as an implementation wart in GHC, and
continue pretending that global uniqueness of instances holds. However,
the problem with global uniqueness of instances is that they are
inherently nonmodular: you might find yourself unable to compose two
components because they accidentally defined the same type class
instance, even though these instances are plumbed deep in the
implementation details of the components. This is a big problem for Backpack, or really any module system, whose mantra of separate modular development seeks to guarantee that linking will succeed if the library writer and the application writer develop to a common signature.Edward Z. Yanghttp://blog.ezyang.com/?p=8987Fri, 11 Jul 2014 16:07:53 +0000Automatic SIMD Vectorization for Haskell and ICFP 2013
http://dorchard.wordpress.com/2013/10/14/automatic-simd-vectorization-for-haskell-and-icfp-2013/
I had a great time at ICFP 2013 this year where I presented my paper “Automatic SIMD Vectorization for Haskell”, which was joint work with Leaf Petersen and Neal Glew of Intel Labs. The full paper and slides are available online. Our paper details the vectorization process in the Intel Labs Haskell Research Compiler (HRC) which gets decent speedups on numerical code (between 2-7x on 256-bit vector registers). It was nice to be able to talk about HRC and share the results. Paul (Hai) Liu also gave a talk at the Haskell Symposium which has more details about HRC than the vectorization paper (see the paper here with Neal Glew, Leaf Petersen, and Todd Anderson). Hopefully there will be a public release of HRC in future.
Still more to do
It’s been exciting to see the performance gains in compiled functional code over the last few years, and its encouraging to see that there is still much more we can do and explore. HRC outperforms GHC on roughly 50% of the benchmarks, showing some interesting trade-offs going on in the two compilers. HRC is particularly good at compiling high-throughput numerical code, thanks to various strictness/unboxing optimisations (and the vectorizer), but there is still more to be done.
Don’t throw away information about your programs
One thing I emphasized in my talk was the importance of keeping, not throwing away, the information encoded in our programs as we progress through the compiler stack. In the HRC vectorizer project, Haskell’s Data.Vector library was modified to distinguish between mutable array operations and “initializing writes”, a property which then gets encoded directly in HRC’s intermediate representation. This makes vectorization discovery much easier. We aim to preserve as much effect information around as possible in the IR from the original Haskell source.
This connected nicely with something Ben Lippmeier emphasised in his Haskell Symposium paper this year (“Data Flow Fusion with Series Expressions in Haskell“, joint with Manuel Chakravarty, Gabriele Keller and Amos Robinson). They provide a combinator library for first-order non-recursive dataflow computations which is guaranteed to be optimised using flow fusion (outperforming current stream fusion techniques). The important point Ben made is that, if your program fits the pattern, this optimisation is guaranteed. As well as being good for the compiler, this provides an obvious cost model for the user (no more games trying to coax the compiler into optimising in a particular way).
This is something that I have explored in the Ypnos array language, where the syntax is restricted to give (fairly strong) language invariants that guarantee parallelism and various optimisations, without undecidable analyses. The idea is to make static as much effect and coeffect (context dependence) information as possible. In Ypnos, this was so successful that I was able to encode the Ypnos’ language invariant of no out-of-bounds array access directly in Haskell’s type system (shown in the DSL’11 paper; this concept was also discussed briefly in my short language design essay).
This is a big selling point for DSLs in general: restrict a language such that various program properties are statically decidable, facilitating verification and optimisation.
Ypnos has actually had some more development in the past year, so if things progress further, there may be some new results to report on. I hope to be posting again soon about more research, including the ongoing work with Tomas Petricek on coeffect systems, and various other things I have been playing with. – Ddorchardhttp://dorchard.wordpress.com/?p=228Mon, 14 Oct 2013 16:02:28 +0000Resource-dependent Algebraic Effects
http://edwinb.wordpress.com/2014/07/10/resource-dependent-algebraic-effects/
A new draft paper, Resource-dependent Algebraic Effects, is available. Abstract:
There has been significant interest in recent months in finding new ways to implement composable and modular effectful programs using handlers of algebraic effects. In my own previous work, I have shown how an algebraic effect system (called “effects“) can be embedded directly in a dependently typed host language. Using dependent types ought to allow precise reasoning about programs; however, the reasoning capabilities of effects have been limited to simple state transitions which are known at compile-time. In this paper, I show how effects can be extended to support reasoning in the presence of run-time state transitions, where the result may depend on run-time information about resource usage (e.g. whether opening a file succeeded). I show how this can be used to build expressive APIs, and to specify and verify the behaviour of interactive, stateful programs. I illustrate the technique using a file handling API, and an interactive game.
I’ve just submitted this, although constructive comments and suggestions are still of course very welcome!edwinbhttp://edwinb.wordpress.com/?p=288Thu, 10 Jul 2014 17:21:03 +0000RFC: New Data.Conduit.Process
http://www.yesodweb.com/blog/2014/07/rfc-new-data-conduit-process
I've been working on a new iteration of the Data.Conduit.Process API over the
past few days. The current API (provided by the process-conduit package), has
some
issues.
So I'm starting over with a new API, and will be including this in
conduit-extra's next release.Before releasing, I'd like to get some feedback on the new API. I've put
together a School of Haskell
tutorial,
which will ultimately become the real documentation for this module. It
describes usage of the library, as well as why the library looks the way it
does. You can view the
source
on the process branch of conduit.In case anyone's wondering, the "well known bug" in waitForProcess may
actually not be very well known yet. There's a race condition documented in
the source code, but it's not nearly as narrow a window as implied there. For
example, the following code will reliably throw an exception:import System.Process
import Control.Concurrent.Async
main :: IO ()
main = do
(_, _, _, ph) <- createProcess $ shell "sleep 1"
let helper i = do
ec <- waitForProcess ph
print (i :: Int, ec)
((), ()) <- concurrently (helper 1) (helper 2)
return ()Thus the motivation for fixing the problem in Data.Conduit.Process. Thanks go
to Michael Sloan for discovering the severity of this race condition. In fact,
the bug he ran into, combined with a separate process-conduit bug I ran up
against, were the impetus for me getting this library written now.For the lazy, here's a copy of the content from School of Haskell:NOTE: This tutorial documents a not-yet-released version of conduit-extra's Data.Conduit.Process module. Currently, that module name is provided by process-conduit, which provides a completely different API. This tutorial is present now for early feedback. If you'd like to experiment, this code is available on the process branch of the conduit repo.IntroductionWhenever you run an external process, there are four ways to interact with it post-creation:Write to its standard inputRead from its standard outputRead from its standard errorCheck its exit codeThe standard System.Process module provides means for all of these interactions. However, there are some downsides with using them:Many of the function in System.Process rely on lazy I/O.There is a subtle race condition when checking for exit codes.Dealing with Handles directly is relatively low-level.Data.Conduit.Process provides a higher-level interface for these four interactions, based on conduit. It additionally leverages type classes to provide more static type safety than dealing directly with System.Process, as will be described below. The library is also designed to work with the wonderful async library, providing for easy, high-quality concurrency.Note that providing general parameters for creating a process, such as its working directory or modified environment variables, are not addressed by this module; you should instead use the standard facilities from System.Process.Synopsis{-# LANGUAGE OverloadedStrings #-}
import Control.Applicative ((*>))
import Control.Concurrent.Async (Concurrently (..))
import Control.Concurrent.Async (Concurrently (..))
import Data.Conduit (await, yield, ($$), (=$))
import qualified Data.Conduit.Binary as CB
import qualified Data.Conduit.List as CL
import Data.Conduit.Process (ClosedStream (..), conduitProcess,
proc, waitForConduitProcess)
import System.IO (stdin)
main :: IO ()
main = do
putStrLn "Enter lines of data. I'll base64-encode it."
putStrLn "Enter \"quit\" to exit."
((toProcess, close), fromProcess, ClosedStream, cph) <-
conduitProcess (proc "base64" [])
let input = CB.sourceHandle stdin
$$ CB.lines
=$ inputLoop
=$ toProcess
inputLoop = do
mbs <- await
case mbs of
Nothing -> close
Just "quit" -> close
Just bs -> do
yield bs
inputLoop
output = fromProcess $$ CL.mapM_
(\bs -> putStrLn $ "from process: " ++ show bs)
ec <- runConcurrently $
Concurrently input *>
Concurrently output *>
Concurrently (waitForConduitProcess cph)
putStrLn $ "Process exit code: " ++ show ecExit codesThere's a well documented corner case in waitForProcess whereby multiple calls can end up in a race condition, and therefore a deadlock. Data.Conduit.Process works around this issue by not providing direct access to a ProcessHandle. Instead, it wraps this with a ConduitProcessHandle, which uses an STM TMVar under the surface. This allows you to either poll to check if a process has exited, or block and wait for the process to exit. As a minimal example (ignore the streaming bits for now, they'll be explained shortly).import Data.Conduit.Process
main :: IO ()
main = do
(Inherited, Inherited, Inherited, cph) <-
conduitProcess (shell "sleep 2")
-- non-blocking
getConduitProcessExitCode cph >>= print
-- blocking
waitForConduitProcess cph >>= printIf you need direct access to the ProcessHandle (e.g., to terminate a process), you can use conduitProcessHandleRaw.StreamingNow to the main event: streaming data. There are multiple ways you can interact with streams with an external process:Let the child process inherit the stream from the parent processProvide a pre-existing Handle.Create a new Handle to allow more control of the interaction.One downside of the System.Process API is that there is no static type safety to ensure that the std_out parameter in fact matches up with the value produced by createProcess for the standard output handle. To overcome this, Data.Conduit.Process makes use of type classes to represent the different ways to create a stream. This isn't entirely intuitive from the Haddocks, but once you see the concept used, it's easy to use yourself.Inherited and ClosedStreamLet's start with an example of using the simplest instances of our typeclasses. Inherited says to inherit the Handle from the parent process, while ClosedStream says to close the stream to the child process. For example, the next snippet will inherit stdin and stdout from the parent process and close standard error.import Data.Conduit.Process
main :: IO ()
main = do
putStrLn "Just wrapping cat. Use Ctrl-D to exit."
(Inherited, Inherited, ClosedStream, cph) <-
conduitProcess (shell "cat")
waitForConduitProcess cph >>= printNote that there's no way to send an EOF in School of Haskell, so the above active code will never terminate.ConduitIt would be pretty strange to have a library in conduit-extra that didn't provide some conduit capabilities. You can additionally get a Sink to be used to feed data into the process via standard input, and Sources for consuming standard output and error.This next example reads standard input from the console, process standard output with a conduit, and closes standard error.import Data.Conduit (($$))
import qualified Data.Conduit.List as CL
import Data.Conduit.Process
main :: IO ()
main = do
putStrLn "Just wrapping cat. Use Ctrl-D to exit."
(Inherited, src, ClosedStream, cph) <-
conduitProcess (shell "cat")
src $$ CL.mapM_ print
waitForConduitProcess cph >>= printNote that these Sources and Sinks will never close their Handles. This is done on purpose, to allow them to be used multiple times without accidentally closing their streams. In many cases, you'll need to close the streams manually, which brings us to our next section.Conduit + closeLet's say we'd like to close our input stream whenever the user types in "quit". To do that, we need to get an action to close the standard input Handle. This is simple: instead of just returning a Source or Sink, we ask for a tuple of a Source/Sink together with an IO () action to close the handle.{-# LANGUAGE OverloadedStrings #-}
import Data.ByteString (ByteString)
import Data.Conduit (Source, await, yield, ($$), ($=))
import qualified Data.Conduit.Binary as CB
import Data.Conduit.Process
import System.IO (stdin)
userInput :: Source IO ByteString
userInput =
CB.sourceHandle stdin
$= CB.lines
$= loop
where
loop = do
mbs <- await
case mbs of
Nothing -> return ()
Just "quit" -> return ()
Just bs -> do
yield bs
yield "\n"
loop
main :: IO ()
main = do
putStrLn "Just wrapping cat. Type \"quit\" to exit."
((sink, close), Inherited, ClosedStream, cph) <-
conduitProcess (shell "cat")
userInput $$ sink
close
waitForConduitProcess cph >>= printUseProvidedHandleLet's take a quick detour from our running example to talk about the last special type: UseProvidedHandle. This says to conduitProcess: use the example value of UseHandle provided in std_in/std_out/std_err. We can use this to redirect output directly to a file:import Data.Conduit.Process
import System.IO (withFile, IOMode (..))
main :: IO ()
main = do
let fp = "date.txt"
withFile fp WriteMode $ \h -> do
(ClosedStream, UseProvidedHandle, ClosedStream, cph) <-
conduitProcess (shell "date")
{ std_out = UseHandle h
}
waitForConduitProcess cph >>= print
readFile fp >>= printUse with asyncIn our examples above, we only ever used a single Source or Sink at a time. There's a good reason for this: we can easily run into deadlocks if we don't properly handle concurrency. There are multiple ways to do this, but I'm going to strongly recommend using the async package, which handles many corner cases automatically. In particular, the Concurrently data type and its Applicative instance make it easy and safe to handle multiple streams at once.Instead of duplicating it here, I'll ask the reader to please refer back to the synopsis example, which ties this all together with two threads for handling streams, and another thread which blocks waiting for the process to exit. That style of concurrency is very idiomatic usage of this library.http://www.yesodweb.com/blog/2014/07/rfc-new-data-conduit-processThu, 10 Jul 2014 07:15:00 +0000Examining Hackage: logict
http://jozefg.bitbucket.org/posts/2014-07-10-reading-logict.html
http://jozefg.bitbucket.org/posts/2014-07-10-reading-logict.htmlThu, 10 Jul 2014 00:00:00 +0000Dissecting crush
http://jozefg.bitbucket.org/posts/2014-07-09-dissecting-crush.html
http://jozefg.bitbucket.org/posts/2014-07-09-dissecting-crush.htmlWed, 09 Jul 2014 00:00:00 +0000Markup Plugin for RapidWeaver 5
http://algorithm.com.au/blog/files/rapidweaver-5-markup.html#unique-entry-id-618
For the RapidWeaver users out there, I’ve updated my antique Markup plugin to work with RapidWeaver 5 (slow clap). It also now lives on GitHub, like all the other cool open-source projects published after about 1970. (BitBucket is so 1969.)
As an aside, ohmigosh, there still isn’t anything out there that’s as good as RapidWeaver for building websites. I wanted to redo my site, and looked into a bunch of RapidWeaver alternatives, especially Web apps. Tumblr, Wordpress, Blogger and all that are great for just blogs, but useless for building anything more than a blog. Online site-builders like Squarespace, Weebly, and Virb are either way too dumbed down, too complex, have the most boring themes, or more likely, are all of the above. Despite RapidWeaver still being compiled for ppc and i386 only (it’s not a 64-bit app yet), and using the Objective-C 1.0 runtime (my Markup plugin uses +[NSObject poseAsClass:]!), it is still the best thing going for building sites. Amazing.
Anyway, Markup plugin, go get it.André Pang (ozone)http://algorithm.com.au/blog/files/rapidweaver-5-markup.html#unique-entry-id-618Mon, 07 Jul 2014 18:26:15 +0000How to run SQL actions in persistent
http://feedproxy.google.com/~r/RomanCheplyaka/~3/Hc2kxBOaDq0/2014-07-07-persistent.html
http://ro-che.info//articles/2014-07-07-persistent.htmlSun, 06 Jul 2014 21:00:00 +0000[mvoghuaz] One-dimensional puzzle generator
http://kenta.blogspot.com/2014/07/mvoghuaz-one-dimensional-puzzle.html
Here is a one-dimensional jigsaw puzzle generator implemented in Haskell, creating one-dimensional instances of the exact cover problem.For generation purposes, the one-dimensional field is divided into n blocks each of size b. Each of the n pieces is roughly centered on a unique block and spans at most p blocks. The arguments to the program are b p n.Each generated piece is specified by a list of coordinates offset from its leftmost coordinate. Each individual piece is typically not contiguous; that would make the puzzle trivial to solve. Solve the puzzle by finding the offset of each piece in the field so that the field is exactly covered by all the pieces.There is a "edge effect" flaw such that pieces near the edge tend to span less than p blocks.Example run with parameters 10 5 10:
Pieces are:
(0,[0,5,12,15,19,29])
(1,[0,1,5,6,7,12,16,17,22,23,25,27,29,30,31,32])
(2,[0,1,6,7,8,11,22,32,38,40,44,45])
(3,[0,4,5,21,23,24,26,33,37])
(4,[0,5,14,16,30,35,38,39])
(5,[0,12,25,28,30,32])
(6,[0,1,7,10,12,21,23,25,27,30,31,34,37,42,43,44,45])
(7,[0,5,8,18,27,29,33,34,35])
(8,[0,10,13,17,28,29,30,35,36])
(9,[0,2,12,20,24,25,26,27])
Solution is the concatenation of:
[0,1,1,2,2,0,1,1,1,2]
[2,2,0,1,2,0,3,1,1,0]
[3,3,4,1,1,2,1,4,1,0]
[1,1,1,1,5,2,4,3,4,3]
[3,2,3,2,6,6,5,2,2,3]
[7,6,4,3,6,7,6,4,7,5]
[4,4,5,8,5,6,5,6,7,6]
[9,6,9,8,6,6,8,7,6,7]
[8,6,9,7,7,7,6,6,6,6]
[9,8,8,8,9,9,9,9,8,8]
Motivation is to generate random inputs to Knuth's Dancing Links DLX algorithm. What puzzle parameters generate difficult puzzles?Kentag:blogger.com,1999:blog-6757805.post-3257740703849282061Fri, 04 Jul 2014 23:12:00 +0000HsQML 0.2.0.2 released
http://blog.gekkou.co.uk/2014/01/hsqml-0202-released.html
I've been meaning start blogging again for ages, and this seemed to be as good a time as any. I've just released HsQML 0.2.0.2 and uploaded it to Hackage. This minor point release fixes two issues:Firstly, API changes in Cabal 1.18 broke HsQML's rather involved Setup.hs. I didn't want mandate that users have the latest Cabal library, so I investigated a couple of different options for supporting both the old and new. There are no really pretty solutions here and I ended up using Template Haskell to select between two different sets of utility functions.Secondly, the text package has recently gone through two major version changes under the PVP. I've widened the Cabal version constraint to permit both text-1.0 and text-1.1.Hope you enjoy!release-0.2.0.2 - 2014.01.18 * Added support for Cabal 1.18 API. * Relaxed Cabal dependency constraint on 'text'.Robin KAYtag:blogger.com,1999:blog-4001434382262009587.post-5547750687044867289Sat, 18 Jan 2014 23:00:00 +0000HsQML 0.2.0.3 released
http://blog.gekkou.co.uk/2014/02/hsqml-0203-released.html
Yesterday, I made new a minor release of HsQML in order to address two issues with using it interactively via GHCi. As usual, it's available for download from Hackage. One little mistake did slip in however, in that I forget to change the darcs repository listed in the package cabal file to the Qt 4 branch. The main trunk is now being used for porting to Qt 5.An explanation of the GHCi problems follows:GHCi has traditionally had a number of limitations owing to the built-in linker it uses to load static object files dynamically. The linker is capable enough to load the output of GHC and any simple FFI C code that might be included in a library, but it can't cope with some of the relocations emitted by a C++ compiler. Originally, it wasn't even capable of reading the same archive libraries used by the GHC compiler for linking, and required that Cabal produce special compounded object files for it to use.The C++ limitation was an issue for HsQML because Qt is a C++ library and hence HsQML needs to include some C++ code as part of its binding layer. I made use of the fact that GHCi depended on special object files in order to incorporate a workaround especially for GHCi. HsQML's build script modifies the build process by removing the objects containing C++ code from being compounded into the special object file, and places them into a separate shared library which is then referenced by the package's extra-ghci-libraries field. GHCi will hence load the shared library and the compiled C++ code within using the system linker, thereby avoiding the problems with its own.However, it came to my attention recently* than this strategy had run into trouble as GHCi can now load regular archive libraries directly, supplanting the need for special object files. I discovered that the Fedora Linux had modified their distribution of GHC to disable generating the GHCi objects by default. Furthermore, that this behaviour would become the new standard default with Cabal 1.18. This broke HsQML with GHCi because because the aforementioned workaround didn't apply to the regular archive libraries and so GHCi's linker couldn't handle the C++ object files contained within.I didn't want to simply apply the same workaround to the archive libraries as to the GHCi ones because that would introduce dealing with an additional magic shared library to users who simply wanted to compile their applications. The modification I've applied for this release was therefore to add code to Setup.hs to force (re-)enable generating the special GHCi object files under certain circumstances.The impact of this issue is likely to decrease over time as GHC now also supports producing shared libraries from Haskell code in addition to static ones. This means that, going forward, the entirety of HsQML can be built as a shared library and GHCi can load it using the system linked without difficulty. My understanding is that this behaviour will become the default with GHC 7.8 for platforms other than Windows.Hence, the rule is that generating GHCi object files is only force enabled if shared libraries are not enabled. The forcing behaviour can be disabled by passing -f-ForceGHCiLib to cabal-install.The other issue I found that's fixed with this release is that GHCi had problems finding the workaround shared library on Windows. Unlike other platforms, the extra-ghci-libraries field needed to include the "lib" prefix to the referenced library name in order for Windows GHCi to find it without the library being on the PATH. With that fixed, HsQML should now work with GHCi out of the box on all platforms.Now, back to working on the Qt 5 port!release-0.2.0.3 - 2014.02.01 * Added mechanism to force enable GHCi workaround library. * Fixed reference name of extra GHCi library on Windows.* Thanks to rnons.Robin KAYtag:blogger.com,1999:blog-4001434382262009587.post-6670810057395306718Sun, 02 Feb 2014 18:00:00 +0000Using the Connections element with HsQML
http://blog.gekkou.co.uk/2014/02/using-connections-element-with-hsqml.html
I was asked recently if the Connections element could be used to declaratively connect QML actions to signals defined in Haskell code. I wasn't completely sure if it would work off-hand so I wrote the following example program with HsQML 0.2.x to find out (Hint: the answer is yes).To begin with, we need a Haskell program which will load a QML document and fire off some signals. The following program forks off a thread which blocks for the user to enter a new line in the terminal window and fires a signal every time they do. The context object has two members, the signal we're experimenting with and a property called 'self' whose function will become apparent shortly.{-# LANGUAGE DeriveDataTypeable, TypeFamilies #-}import Graphics.QMLimport Data.Typeableimport Data.Taggedimport Control.Concurrentimport Control.Monadmain :: IO ()main = do ctx <- newObject MainObject tid <- forkIO $ forever $ do putStrLn "Press ENTER to run animation" void $ getLine fireSignal (Tagged ctx :: Tagged TheSignal (ObjRef MainObject)) runEngineLoop defaultEngineConfig { contextObject = Just $ anyObjRef ctx} killThread tiddata TheSignal deriving Typeableinstance SignalKey TheSignal where type SignalParams TheSignal = IO ()data MainObject = MainObject deriving Typeableinstance Object MainObject where classDef = defClass [ defPropertyRO "self" ((\x -> return x) :: ObjRef MainObject -> IO (ObjRef MainObject)), defSignal (Tagged "theSignal" :: Tagged TheSignal String)]The QML document to accompany the above program follows below. It should be placed in a file called 'main.qml' in order to be loaded by the defaultEngineConfig. You could set the initialURL field to something else if you wanted, but I'm trying to keep the code short.import Qt 4.7Rectangle { id: root width: 500; height: 500 color: "red" Rectangle { id: square x: 150; y: 150; width: 200; height: 200 color: "yellow" Rectangle { width: 50; height: 50; color: "black" } transform: Rotation { id: rotateSquare origin.x: 100; origin.y: 100; angle: 0 } NumberAnimation { id: rotateAnim target: rotateSquare; property: "angle" from: 0; to: 360; duration: 1500 } Connections { target: self onTheSignal: rotateAnim.start() } }}The code for the Connections element is highlighted in bold. Of its two attributes, the first, called 'target', specifies the object with signals that we want to bind handlers to. In this example the signal is a member of the global object and this complicates matters because it's not straightforward to write an expression which yields the global object. Hence, I placed the 'self' property on the global object to provide a convenient way of the getting a reference to it.There are ways to get the global object, but they're not particularly pretty and I don't fully trust that kind of thing inside Qt's script environment anyway.The second attribute specifies the signal binding. Specifically, the attribute name identifies the signal and is derived by pre-pending the string 'on' to the actual signal name. Hence, in this case, binding to 'theSignal' is specified using the attribute 'onTheSignal'. The value of the attribute is the JavaScript code to be executed when the signal fires. In our example it causes a simple little animation to occur.Up to now, the only example I provided of using signals was the hsqml-morris demo application. It's not a great example of idiomatic QML because it uses a big chunk of JavaScript to work around some of the present limitations of HsQML's marshalling facilities (e.g. no lists/arrays). It makes no great attempt to be a "pure" QML application, so it just calls the signal's connect() method to attach it via JavaScript.You could use the same approach with this test program by replacing the Connections element with the following code snippet: Component.onCompleted: { self.theSignal.connect(rotateAnim.start); }The 'self' property is superfluous here because we can access the signal member on the global object directly. However, it's a slightly unfair comparison because the JavaScript code only covers connecting to the signal, whereas the Connections element also handles disconnections. When you're dynamically creating and destroying Components using things like the Repeater element, this is important to prevent overloading your signals with handlers that are never cleaned up.The Connections element also allows the target attribute to be specified with a property or dynamic expression. If the value of the target expression changes at runtime then all the signal handlers will be disconnected and reconnected to the new object.Addendum: Writing this example has made me think that HsQML relies too heavily on top-level data and instance declarations. I'd like to rectify that in the future by making QML classes first-class values on the Haskell side.Robin KAYtag:blogger.com,1999:blog-4001434382262009587.post-7947344411393398911Tue, 04 Feb 2014 22:00:00 +0000HsQML 0.3.0.0 released: Now with Qt 5
http://blog.gekkou.co.uk/2014/05/hsqml-0300-released-now-with-qt-5.html
I've just made a new major release of HsQML, my Haskell binding for the Qt Quick GUI framework. You can download it from Hackage in the usual manner.This is a particularly exciting release because it's the first to have been ported over to use Qt 5. Previously, HsQML was developed against an older version of the Qt Quick technology which shipped as part of Qt 4.7 and 4.8. Support for Qt 5 has been a constant theme in the e-mails I get concerning HsQML for some time and so I'm pleased to finally deliver on that point.There are also number of other improvements to the library which should allow more idiomatic QML code and hence reduce the need for helper JavaScript. Properties now support an associated notify signal which allows QML to automatically update in response to property changes rather than needing manual signal handlers. Also, lists and Maybe values can be marshalled between Haskell and QML natively, again reducing friction between the two environments.The API has been redesigned slightly so that object classes and signal keys can be defined directly inside Haskell functions in addition to the older type-class based method. It's unclear yet if this style is wholly superior but, for smaller programs at least, it permits greater clarity and much less verbosity.Finally, although still far from comprehensive, I've spent some time trying to improve the documentation on my web-site. It now provides some more substantial examples and goes into greater depth. The complete buildable source code for these examples is contained in the hsqml-demo-samples package. Also, the original Nine Men's Morris demo application is still available, but the package has been renamed to hsqml-demo-morris.release-0.3.0.0 - 2014.05.04 * Ported to Qt 5 and Qt Quick 2 * Added type-free mechanism for defining classes. * Added type-free mechanism for defining signal keys. * Added property signals. * Added marshallers for Bool, Maybe, and lists. * Added less polymorphic aliases for def functions. * Replaced Tagged with Proxy in public API. * Removed marshallers for URI and String. * New design for marshalling type-classes (again). * Generalised facility for user-defined Marshal instances. * Relaxed Cabal dependency constraint on 'QuickCheck'. * Fixed GHCi on Windows with pre-7.8 GHC.Robin KAYtag:blogger.com,1999:blog-4001434382262009587.post-8744890983667599714Mon, 05 May 2014 09:11:00 +0000