News aggregator

Problems with type families

haskell-cafe - Mon, 07/06/2015 - 6:20pm
Hi All! Consider the following definitions: type family TFunIn t e type family TFunOut t e data IdT data ComposeT t1 t2
Categories: Offsite Discussion

New Functional Programming Job Opportunities

haskell-cafe - Mon, 07/06/2015 - 5:00pm
Here are some functional programming job opportunities that were posted recently: Senior Developer at Elsen, Inc. Cheers, Sean Murphy
Categories: Offsite Discussion

I'd appreciate help figuring out how to use polymorphism in a simple case

Haskell on Reddit - Mon, 07/06/2015 - 3:31pm

I think I know why this code is failing (I'm guessing because the typechecker sees that t can be an Int or a String and thinks I've made a mistake). What I'd like to know is how I can get something like this working. I think the code explains my basic case pretty well, so I'll let it do the work:

data TestMode = A | B data Test = Test { a :: String, b :: Int, mode :: TestMode } getProperty :: Show t => Test -> t getProperty test = case mode test of A -> a test B -> b test main = do let t = Test { a = "yes!", b = 5, mode = A } print $ getProperty t

I leave the error in the comments to make this a bit shorter to read. My goal is to not do a lot of duplicate code. The following script works, but if I have to do a lot of print operations like this it gets unwieldy:

data TestMode = A | B data Test = Test { a :: String, b :: Int, mode :: TestMode } main = do let t = Test { a = "yes!", b = 5, mode = A } case mode t of A -> print $ a t B -> print $ b t submitted by benekastah
[link] [17 comments]
Categories: Incoming News

Roman Cheplyaka: How Haskell handles signals

Planet Haskell - Mon, 07/06/2015 - 2:00pm

How is it possible to write signal handlers in GHC Haskell? After all, the set of system calls allowed inside signal handlers is rather limited. In particular, it is very hard to do memory allocation safely inside a signal handler; one would have to modify global data (and thus not be reentrant), call one of the banned syscalls (brk, sbrk, or mmap), or both.

On the other hand, we know that almost any Haskell code requires memory allocation. So what’s the trick?

The trick is that a Haskell handler is not installed as a true signal handler. Instead, a signal is handled by a carefully crafted RTS function generic_handler (rts/posix/Signals.c). All that function does (assuming the threaded RTS) is write the signal number and the siginfo_t structure describing the signal to a special pipe (called the control pipe, see GHC.Event.Control).

The other end of this pipe is being watched by the timer manager thread (GHC.Event.TimerManager). When awaken by a signal message from the control pipe, it looks up the handler corresponding to the signal number and, in case it’s an action, runs it in a new Haskell thread.

The signal handlers are stored in a global array, signal_handlers (GHC.Conc.Signal). When you install a signal action in Haskell, you put a stable pointer to the action’s code into the array cell corresponding to the signal number, so that the timer thread could look it up later when an actual signal is delivered.

See also

Categories: Offsite Blogs

Daniel Mlot (duplode): Applicative Archery

Planet Haskell - Mon, 07/06/2015 - 2:00pm

It is widely agreed that the laws of the Applicative class are not pretty to look at.

pure id <*> v = v -- identity pure f <*> pure x = pure (f x) -- homomorphism u <*> pure y = pure ($ y) <*> u -- interchange pure (.) <*> u <*> v <*> w = u <*> (v <*> w) -- composition

Monad laws, in comparison, not only look less odd to begin with but can also be stated in a much more elegant way in terms of Kleisli composition (<=<). Shouldn’t there be an analogous nice presentation for Applicative as well? That became a static question in my mind while I was studying applicative functors many moons ago. After finding surprisingly little commentary on this issue, I decided to try figuring it out by myself. 1

Let’s cast our eye over Applicative:

class Functor t => Applicative t where pure :: a -> t a (<*>) :: t (a -> b) -> t a -> t b

If our inspiration for reformulating Applicative is Kleisli composition, the only sensible plan is to look for a category in which the t (a -> b) functions-in-a-context from the type of (<*>) are the arrows, just like a -> t b functions are arrows in a Kleisli category. Here is one way to state that plan in Haskell terms:

> class Applicative t => Starry t where > idA :: t (a -> a) > (.*) :: t (b -> c) -> t (a -> b) -> t (a -> c) > > infixl 4 .* > -- The Applicative constraint is wishful thinking: > -- When you wish upon a star...

The laws of Starry are the category laws for the t (a -> b) arrows:

idA .* v = v -- left identity u .* idA = u -- right identity u .* v .* w = u .* (v .* w) -- associativity

The question, then, is whether it is possible to reconstruct Applicative and its laws from Starry. The answer is a resounding yes! The proof is in this manuscript, which I have not transcribed here as it is a little too long for a leisurely post like this one 2. The argument is set in motion by establishing that pure is an arrow mapping of a functor from Hask to a Starry category, and that both (<*>) and (.*) are arrow mappings of functors in the opposite direction. That leads to several naturality properties of those functors, from which the Applicative laws can be obtained. Along the way, we also get definitions for the Starry methods in terms of the Applicative ones…

> idA = pure id > u .* v = fmap (.) u <*> v

… and vice-versa:

pure x = fmap (const x) idA u <*> v = fmap ($ ()) (u .* fmap const v)

Also interesting is how the property relating fmap and (<*>)…

fmap f u = pure f <*> u

… now tells us that a Functor results from composing the pure functor with the (<*>) functor. That becomes more transparent if we write it point-free:

fmap = (<*>) . pure

In order to ensure Starry is equivalent to Applicative we still need to prove the converse, that is, obtain the Starry laws from the Applicative laws plus the definitions of idA and (.*) just above. That is not difficult; all it takes is substituting the definitions in the Starry laws and:

  • For left identity, noticing that (id .) = id.

  • For right identity, applying the interchange law and noticing that ($ id) . (.) is id in a better disguise.

  • For associativity, using the laws to move all (.) to the left of the (<*>) and then verifying that the resulting messes of dots in both sides are equivalent.

As a tiny example, here is the Starry instance of Maybe…

instance Starry Maybe where idA = Just id Just g .* Just f = Just (g . f) _ .* _ = Nothing

… and the verification of the laws for it:

-- Left identity: idA .* u = u Just id .* u = u -- u = Nothing Just id .* Nothing = Nothing Nothing = Nothing -- u = Just f Just id .* Just f = Just f Just (id . f) = Just f Just f = Just f -- Right identity: u .* idA = u u .* Just id = u -- u = Nothing Nothing .* Just id = Nothing Nothing = Nothing -- u = Just g Just g .* Just id = Just g Just (g .* id) = Just g Just g = Just g -- Associativity: u .* v .* w = u .* (v .* w) -- If any of u, v and w are Nothing, both sides will be Nothing. Just h .* Just g .* Just f = Just h .* (Just g .* Just f) Just (h . g) .* Just f = Just h .* (Just (g . f)) Just (h . g . f) = Just (h . (g . f)) Just (h . g . f) = Just (h . g . f)

It works just as intended:

GHCi> Just (2*) .* Just (subtract 3) .* Just (*4) <*> Just 5 Just 34 GHCi> Just (2*) .* Nothing .* Just (*4) <*> Just 5 Nothing

I do not think there will be many opportunities to use the Starry methods in practice. We are comfortable enough with applicative style, through which we see most t (a -> b) arrows as intermediates generated on demand, rather than truly meaningful values. Furthermore, the Starry laws are not really easier to prove (though they are certainly easier to remember!). Still, it was an interesting exercise to do, and it eases my mind to know that there is a neat presentation of the Applicative laws that I can relate to.

This post is Literate Haskell, in case you wish to play with Starry in GHCi (here is the raw .lhs file ).

> instance Starry Maybe where > instance Starry [] where > instance Starry ((->) a) where > instance Starry IO where

As for proper implementations in libraries, the closest I found was Data.Semigroupoid.Static, which lives in Edward Kmett’s semigroupoids package. “Static arrows” is the actual technical term for the t (a -> b) arrows. The module provides…

newtype Static f a b = Static { runStatic :: f (a -> b) }

… which uses the definitions shown here for idA and (.*) as id and (.) of its Category instance.

<section class="footnotes">
  1. There is a reasonably well-known alternative formulation of Applicative: the Monoidal class as featured in this post by Edward Z. Yang. While the laws in this formulation are much easier to grasp, Monoidal feels a little alien from the perspective of a Haskeller, as it shifts the focus from function shuffling to tuple shuffling.

  2. Please excuse some oddities in the manuscript, such as off-kilter terminology and weird conventions (e.g. consistently naming arguments in applicative style as w <*> v <*> u rather than u <*> v <*> w in applicative style). The most baffling choice was using id rather than () as the throwaway argument to const. I guess I did that because ($ ()) looks bad in handwriting.

</section> Comment on GitHub (see the full post for a reddit link)

Post licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Categories: Offsite Blogs

Announcing yesod-table

Haskell on Reddit - Mon, 07/06/2015 - 1:33pm
Categories: Incoming News

SPJ's Venn diagram on type-correctness

haskell-cafe - Mon, 07/06/2015 - 12:12pm
Hi all, Sometime in the past, I came across a presentation from SPJ in which he showed a Venn diagram showing "programs that compile" and "programs that are correct". Unfortunately, I cannot remember the exact wording and I'm unable to find the slides/talk on google/youtube. Does anyone remember the exact details of the diagram? Or the title of the talk? Is there still a link to it? Thanks, Mathijs
Categories: Offsite Discussion

The GHC Team: GHC Weekly News - 2015/07/06

Planet Haskell - Mon, 07/06/2015 - 10:25am

Hi *,

Welcome for the latest entry in the GHC Weekly News. The past week, GHC HQ met up to discuss the status of the approaching 7.10.2 release.

7.10.2 status

After quite some delay due to a number of tricky regressions in 7.10.1, 7.10.2 is nearing the finish line. Austin cut release candidate 2 on Friday and so far the only reports of trouble appear to be some validation issues, most of which have already been fixed thanks to Richard Eisenberg.

7.10.2 will include a number of significant bug-fixes. These include,

  • #10521, where overlap of floating point STG registers weren't properly accounted for, resulting in incorrect results in some floating point computations. This was fixed by the amazing Reid Barton.
  • #10534, a type-safety hole enabling a user to write unsafeCoerce with data families and coerce. Fix due to the remarkable Richard Eisenberg.
  • #10538, where some programs would cause the simplifier to emit an empty case, resulting in runtime crashes. Fix due to the industrious Simon Peyton Jones.
  • #10527, where the simplifier would expend a great deal of effort simplifying arguments which were never demanded by the callee.
  • #10414, where a subtle point of the runtime system's black-holing mechanism resulting in hangs on a carefully constructed testcase.
  • #10236, where incorrect DWARF annotations would be generated, resulting in incorrect backtraces. Fixed by Peter Wortmann
  • #7450, where cached free variable information was being unnecessarily dropped by the specialiser, resulting in non-linear compile times for some programs.

See the ​status page for a complete listing of issues fixed in this release.

In the coming days we will being working with FP Complete to test the pre-release against Stackage. While Hackage tends to be too large to build in bulk, the selection of packages represented in Stackage is feasible to build and is likely to catch potential regressions. Hopefully this sort of large-scale validation will become common-place for future releases.

If all goes well, 7.10.2 will mark the end of the 7.10 series. However, there is always the small possibility that a major regression will be found. In this case we will cut a 7.10.3 release which will include a few ​patches which didn't make it into 7.10.2.

Other matters

It has been suggested in #10601 that GHC builds should ship with DWARF symbols for the base libraries and runtime system. While we all want to see this new capability in users' hands, 7.10.2 will, like 7.10.1, not be shipping with debug symbols. GHC HQ will be discussing the feasibility of including debug symbols with 7.12 in the future. In the meantime, we will be adding options to to make it easier for users to build their own compilers with debug-enabled libraries.

In this week's GHC meeting the effort to port GHC's build system to the Shake? build system briefly came up. Despite the volume of updates on the ​Wiki Simon reports that the project is still moving along. The current state of the Shake-based build system can be found on ​Github.

While debugging #7540 it became clear that there may be trouble lurking in the profiler. Namely when profiling GHC itself lintAnnots is showing up strongly where it logically should not. This was previously addressed in #10007, which was closed after a patch by Simon Marlow was merged. As it appears that this did not fully resolve the issue I'll be looking further into this.

~ Ben

Categories: Offsite Blogs

Radix sort(s)

Haskell on Reddit - Mon, 07/06/2015 - 9:29am
Categories: Incoming News

Well-Typed.Com: Dependencies for Cabal Setup.hs files and other goodies

Planet Haskell - Mon, 07/06/2015 - 9:10am
No untracked dependencies!

Years ago, back when Isaac Potoczny-Jones and others were defining the Cabal specification, the big idea was to make Haskell software portable to different environments. One of the mantras was “no untracked dependencies!”.

The problem at the time was that Haskell code had all kinds of implicit dependencies which meant that while it worked for you, it wouldn’t build for me. For example, I might not have some other module that it needed, or the right version of the module.

So of course that’s what the build-depends in .cabal files is all about, requiring that the author of the code declare just what the code requires of its environment. The other important part is that the build system only lets your code see the dependencies you’ve declared, so that you don’t accidentally end up with these untracked dependencies.

This mantra of no untracked dependencies is still sound. If we look at a system like nix, part of what enables it to work so well is that it is absolutely fanatical about having no untracked dependencies.

Untracked dependencies?!

One weakness in the original Cabal specification is with Setup.hs scripts. These scripts are defined in the spec to be the entry point for the system. According to the Cabal spec, to build a package you’re required to compile the Setup.hs script and then use its command line interface to get things done. Because in the original spec the Setup.hs is the first entry point, it’s vital that it be possible to compile Setup.hs without any extra fuss (the runhaskell tool was invented just to make this possible, and to make it portable across compilers).

But by having the Setup.hs as the primary entry point, it meant that it’s impossible to reliably use external code in a Setup.hs script, because you cannot guarantee that that code is pre-installed. Going back to the “no untracked dependencies” mantra, we can see of course that all dependencies of Setup.hs scripts are in fact untracked!

This isn’t just a theoretical problem. Haskell users that do have complex Setup.hs scripts often run into versioning problems, or need external tools to help them get the pre-requisite packages installed. Or as another example: Michael Snoyman noted earlier this year in a diagnosis of an annoying packaging bug that:

As an aside, this points to another problematic aspect of our toolchain: there is no way to specify constraints on dependencies used in custom Setup.hs files. That’s actually caused more difficulty than it may sound like, but I’ll skip diving into it for now.

The solution: track dependencies!

As I said, the mantra of no untracked dependencies is still sound, we just need to apply it more widely.

These days the Setup.hs is effectively no longer a human interface, it is now a machine interface used by other tools like cabal or by distro’s install scripts. So we no longer have to worry so much about Setup.hs scripts always compiling out of the box. It would be acceptable now to say that the first entry point for a tool interacting with a package is the .cabal file, which might list the dependencies of the Setup.hs. The tool would then have to ensure that those dependencies are available when compiling the Setup.hs.

So this is exactly what we have now done. Members of the Industrial Haskell Group have funded us to fix this long standing problem and we have recently merged the solution into the development version of Cabal and cabal-install.

From a package author’s point of view, the solution looks like this: in your .cabal file you can now say:

build-type: Custom custom-setup setup-depends: base >= 4.6, directory >= 1.0, Cabal >= 1.18 && < 1.22, acme-setup-tools == 0.2.*

So it’s a new stanza, like libraries or executables, and like these you can specify the library dependencies of the Setup.hs script.

Now tools like cabal will compile the Setup.hs script with these and only these dependencies, just like it does normally for executables. So no more untracked dependencies in Setup.hs scripts. Newer cabal versions will warn about not using this new section. Older cabal versions will ignore the new section (albeit with a warning). So over time we hope to encourage all packages with custom setup scripts to switch over to this.

In addition, the Setup.hs script gets built with CPP version macros (MIN_VERSION_{pkgname}) available so that the code can be made to work with a wider range of versions of its dependencies.

In the solver…

So on the surface this is all very simple and straightforward, a rather minor feature even. In fact it’s been remarkably hard to implement fully for reasons I’ll explain, but the good news is that it works and the hard work has also gotten us solutions to a couple other irksome problems.

Firstly, why isn’t it trivial? It’s inevitable that sooner or later you will find that your application depends on one package that has setup deps like Cabal == 1.18.* and another with setup deps like Cabal == 1.20.*. At that point we have a problem. Classically we aim to produce a build plan that uses at most one version of each package. We do that because otherwise there’s a danger of type errors from using multiple versions of the same package. Here with setup dependencies there is no such danger: it’s perfectly possible for me to build one setup script with one version of the Cabal library and another script with a different Cabal version. Because these are executables and not libraries, the use of these dependencies does not “leak”, and so we would be safe to use different versions in different places.

So we have extended the cabal solver to allow for limited controlled use of multiple versions of the same package. The constraint is that all the “normal” libraries and exes all use the same single version, just as before, but setup scripts are allowed to introduce their own little world where independent choices about package versions are allowed. To keep things sane, the solver tries as far as possible not to use multiple versions unless it really has to.

If you’re interested in the details in the solver, see Edsko’s recent blog post.

Extra goodies

This work in the solver has some extra benefits.

Improve Cabal lib API without breaking everything

In places the Cabal library is a little crufty, and the API it exposes was never really designed as an API. It has been very hard to fix this because changes in the Cabal library interface break Setup.hs scripts, and there was no way for packages to insulate themselves from this.

So now that we can have packages have proper dependencies for their custom Setup.hs, the flip side is that we have an opportunity to make breaking changes to the Cabal library API. We have an opportunity to throw out the accumulated cruft, clean up the code base and make a library API that’s not so painful to use in Setup.hs scripts.

Shim (or compat) packages for base

Another benefit is that the new solver is finally able to cope with having “base shim” packages, as we used in the base 3.x to 4.x transition. For two GHC releases, GHC came with both base-3.x and base-4.x. The base-4 was the “true” base, while the base-3 was a thin wrapper that re-exported most of base-4 (and syb), but with some changes to implement the old base-3 API. At the time we adapted cabal to cope with this situation of having two versions of a package in a single solution.

When the new solver was implemented however support for this situation was not added (and the old solver implementation was retained to work with GHC 6.12 and older).

This work for setup deps has made it relatively straightforward to add support for these base shims. So next time GHC needs to make a major bump to the version of base then we can use the same trick of using a shim package. Indeed this might also be a good solution in other cases, perhaps cleaner than all these *-compat packages we’ve been accumulating.

It has also finally allowed us to retire the old solver implementation.

Package cycles involving test suites and benchmarks

Another feature that is now easy to implement (though not actually implemented yet) is dealing with the dependency cycles in packages’ test suites and benchmarks.

Think of a core package like bytestring, or even less core like Johan’s cassava csv library. These packages have benchmarks that use the excellent criterion library. But of course criterion is a complex beast and itself depends on bytestring, cassava and a couple dozen other packages.

This introduces an apparent cycle and cabal will fail to find an install plan. I say apparent cycle because there isn’t really a cycle: it’s only the benchmark component that uses criterion, and nothing really depends on that.

Here’s another observation: when benchmarking a new bytestring or cassava, it does not matter one bit that criterion might be built against an older stable version of bytestring or cassava. Indeed it’s probably sensible that we use a stable version. It certainly involves less rebuilding: I don’t really want to rebuild criterion against each minor change in bytestring while I’m doing optimisation work.

So here’s the trick: we break the cycle by building criterion (or say QuickCheck or tasty) against another version of bytestring, typically some existing pre-installed one. So again this means that our install plan has two versions of bytestring in it: the one we mean to build, and the one we use as a dependency for criterion. And again this is ok, just as with setup dependencies, because dependencies of test suites and benchmarks do not “leak out” and cause diamond dependency style type errors.

One technical restriction is that the test suite or benchmark must not depend on the library within the same package, but must instead use the source files directly. Otherwise there would genuinely be a cycle.

Now in general when we have multiple components in a .cabal file we want them to all use the same versions of their dependencies. It would be deeply confusing if a library and an executable within the same package ended up using different versions of some dependency that might have different behaviour. Cabal has always enforced this, and we’re not relaxing it now. The rule is that if there are dependencies of a test suite or benchmark that are not shared with the library or executable components in the package, then we are free to pick different versions for those than we might pick elsewhere within the same solution.

As another example – that’s nothing to do with cycles – we might pick different versions of QuickCheck for different test suites in different packages (though only where necessary). This helps with the problem that one old package might require QuickCheck == 2.5.* while another requires QuickCheck == 2.8.*. But it’d also be a boon if we ever went through another major QC-2 vs QC-3 style of transition. We would be able to have both QC-2 and QC-3 installed and build each package’s test suite against the version it requires, rather than freaking out that they’re not the same version.

Private dependencies in general

Technically, this work opens the door to allowing private dependencies more generally. We’re not pursuing that at this stage, in part because it is not clear that it’s actually a good idea in general.

Mark Lentczner has pointed out the not-unreasonable fear that once you allow multiple versions of packages within the same solution it will in practice become impossible to re-establish the situation where there is just one version of each package, which is what distros want and what most people want in production systems.

So that’s something we should consider carefully as a community before opening those flood gates.

Categories: Offsite Blogs

How Scalable is Haskell?

Haskell on Reddit - Mon, 07/06/2015 - 8:26am

The thing I hear talked about most with node and go is their ability to handle thousands of concurrent connections at once.

On the other side of the coin are the people who say that while node and go are useful languages, other languages like C#, Scala, and Haskell are more powerful in the long run.

However, I don't ever hear much in relation to Haskell and Web Dev, and moreover I have no idea how scalable it is in that regard.

submitted by Agent_HK-47
[link] [21 comments]
Categories: Incoming News

Is stack a "package manager"

Haskell on Reddit - Mon, 07/06/2015 - 7:33am

In the olden days, it was par for the course to answer queries about haskell package management with "cabal is not a package manager".

With stack putting practicality first, I wonder if it is reasonable to expect "package management" features to be added to it at some point of time?

To be more specific, I'm thinking of being able to uninstall or upgrade packages. And perhaps even fixing versioning / dependency issues with a bit of hand holding.

submitted by haskman
[link] [32 comments]
Categories: Incoming News

What am I getting myself into trying to write a REST API with a haskell framework? (I don't know haskell, but am very interested)

Haskell on Reddit - Mon, 07/06/2015 - 7:31am

I need to write some APIs for work.

I am very interested in learning haskell, and these projects seem like a great chance to learn.

But am I shooting myself in the foot here? How does building an API with a haskell framework compare to ruby/rails, js/node?

Like I said, I don't mind if it costs me extra time since I'm learning, but what are we talking here?

More specifically:

  • Abstracting database CRUD activities (almost trivial in rails/node since there are existing libraries that do 99% of the heavy lifting)
  • Quickly making "routes"
  • Parsing headers / token authentication stuff (again really I'm asking is "are there good libraries for this, or do I need to DIY?")
submitted by rorriMnmaD
[link] [22 comments]
Categories: Incoming News

Question: Finding the source of incomplete record construction

Haskell on Reddit - Mon, 07/06/2015 - 12:26am

Disclaimer: crossposted on StackOverflow

I'm trying to debug a large, complicated program in Haskell, which I didn't entirely write myself.

I'm trying to print my data structures to diagnose a bug, but when I do so, I get the following error: error: Prelude.undefined. As you can see, this error is extremely non-informative.

I'm reasonably sure that this is coming from a record that I've "partially" initialized, where I'm trying to access a field whose value has not been set.

The program (a compiler) is spread over two cabal projects, a library, and an executable which uses that library. This makes debugging using GHCI/cabal-repl hard: I can't run use GHCi on the executable, because it's not the source of the error, but recreating the input the executable gives to the library is too complicated to do by hand.

I'm wondering: what can I do to get more information about where the incorrect record is being created, what field is the source of the error, etc. Is there an RTS option or something I can use to give more information for error output?

submitted by jmite
[link] [20 comments]
Categories: Incoming News

ANN: zoom-refs - zoom and pairing for mutablereferences

haskell-cafe - Sun, 07/05/2015 - 10:49pm
Hello, I've just uploaded my package zoom-refs: It's a "port" of State monad zoom (from lens) to mutable references: zoomTVar :: Lens' a b -> TVar a -> TVar b These TVars aren't actually the raw TVars from STM, but wrappers that provide the same functionality. Similar functions are provided for STRefs and IORefs. Additionally, TVars and STRefs can be paired to create composite references: pairTVars :: TVar a -> TVar b -> TVar (a,b) No such functionality is provided for IORefs, as there would be no way to guarantee atomicity of operations on the underlying references. Together. mutable references can be used sort of like Functors and Applicatives, though one needs to use lenses rather than plain functons to map them. Finally, there are multiple references that use traversals instead of lenses to zoom: readMultiTVar :: Monoid a -> MultiTVar a -> STM a readMultiTVarList :: MultiTVar a -> STM [a] readMultiTVarHead :: MultiTVar a
Categories: Offsite Discussion

Ken T Takusagawa: [dcqhszdf] ChaCha cipher example

Planet Haskell - Sun, 07/05/2015 - 10:15pm

The ChaCha cipher seems not to get as much love as Salsa20. Here is a step-by-step example of the ChaCha round function operating on a matrix. The format of the example is loosely based on the analogous example in section 4.1 of this Salsa20 paper: D. J. Bernstein. The Salsa20 family of stream ciphers. Document ID: 31364286077dcdff8e4509f9ff3139ad. URL: Date: 2007.12.25.

original column [a;b;c;d] 61707865 04030201 14131211 00000007 after first line of round function 65737a66 04030201 14131211 7a616573 after second line of round function 65737a66 775858a7 8e747784 7a616573 after third line of round function dccbd30d 775858a7 8e747784 aab67ea6 after all 4 lines of round function, i.e., quarter round dccbd30d 395746a7 392af62a aab67ea6 original matrix, with the same original column above 61707865 3320646e 79622d32 6b206574 04030201 08070605 0c0b0a09 100f0e0d 14131211 18171615 1c1b1a19 201f1e1d 00000007 00000000 01040103 06020905 one round (4 quarter rounds on columns) dccbd30d 109b031b 0eb5ed20 4483ec2b 395746a7 d88a8f5f 7a292fab b06c9135 392af62a 6ac28db6 dfbce7ba a234a188 aab67ea6 e8383c7a 8d694938 0791063e after shift rows dccbd30d 109b031b 0eb5ed20 4483ec2b d88a8f5f 7a292fab b06c9135 395746a7 dfbce7ba a234a188 392af62a 6ac28db6 0791063e aab67ea6 e8383c7a 8d694938 after another 4 quarter rounds on columns 06b44c34 69a94c11 2ce99b08 216830d1 29b215bd 721e2a33 f0a18097 708e1ee5 2b0e8de3 b801251f 42265fb2 696de1c2 e6fef362 c96c6325 c6cc126e 82c0635a unshifting rows (concludes 1 double round) 06b44c34 69a94c11 2ce99b08 216830d1 708e1ee5 29b215bd 721e2a33 f0a18097 42265fb2 696de1c2 2b0e8de3 b801251f c96c6325 c6cc126e 82c0635a e6fef362 after 8 rounds (4 double rounds) f6093fbb efaf11c6 8bd2c9a4 bf1ff3da bf543ce8 c46c6b5e c717fe59 863195b1 2775d1a0 babe2495 1b5c653e df7dc23c 5f3e08d7 041df75f f6e58623 abc0ab7e Adding the original input to the output of 8 rounds 5779b820 22cf7634 0534f6d6 2a40594e c3573ee9 cc737163 d3230862 9640a3be 3b88e3b1 d2d53aaa 37777f57 ff9ce059 5f3e08de 041df75f f7e98726 b1c2b483 reading the above as bytes, little endian 20 b8 79 57 34 76 cf 22 d6 f6 34 05 4e 59 40 2a e9 3e 57 c3 63 71 73 cc 62 08 23 d3 be a3 40 96 b1 e3 88 3b aa 3a d5 d2 57 7f 77 37 59 e0 9c ff de 08 3e 5f 5f f7 1d 04 26 87 e9 f7 83 b4 c2 b1 same as above but with 20000 rounds (10000 double rounds) 11 a3 0a d7 30 d2 a3 dc d8 ad c8 d4 b6 e6 63 32 72 c0 44 51 e2 4c ed 68 9d 8d ff 27 99 93 70 d4 30 2e 83 09 d8 41 70 49 2c 32 fd d9 38 cc c9 ae 27 97 53 88 ec 09 65 e4 88 ff 66 7e be 7e 5d 65

The example was calculated using an implementation of ChaCha in Haskell, whose end results agree with Bernstein's C reference implementation. The Haskell implementation is polymorphic, allowing as matrix elements any data type (of any word width) implementing Bits, and parametrizable to matrices of any size 4xN. (Security is probably bad for N not equal to 4. For word width different from 32, you probably want different rotation amounts.) The flexibility comes at a cost: the implemention is 3000 times slower than Bernstein's reference C implementation (which is in turn is slower than SIMD optimized assembly-language implementations).

Also included in the same project is a similar Haskell implementation of Salsa20, parametrized to matrices of any size MxN because of the more regular structure of the Salsa20 quarter round function compared to ChaCha. We demonstrate taking advantage of polymorphism to use the same code both to evaluate Salsa20 on Word32 and to generate C code for the round function.

Categories: Offsite Blogs