# News aggregator

### 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> (see the full post for a reddit link)

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

### Anonymous records in Haskell: Nikita Volkov on his solution to the records problem

Haskell on Reddit - Mon, 07/06/2015 - 11:36am
Categories: Incoming News

### 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 build.mk 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

### Dependencies for Cabal Setup.hs files and other goodies

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

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

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
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.

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?")
Categories: Incoming News

### Avoid naming at all costs (X-post /r/clojure)

Haskell on Reddit - Mon, 07/06/2015 - 6:35am
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
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: http://hackage.haskell.org/package/zoom-refs-0.0.0.0 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: http://cr.yp.to/papers.html#salsafamily. 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

### stm onCommit

haskell-cafe - Sun, 07/05/2015 - 9:54pm
I need a onCommit functionality for stm. I know there is the stm-io-hooks [1] package. But it seems so big for such a small thing and then I have to translate everything to their monad. lift lift lift ... So I thought of a little hack to solve the issue and I'm wondering if this is safe to use. My understanding of stm internals is very limited. It's basically just a TChan with IO actions in it and there is another thread waiting to execute anything inserted into it. import Control.Concurrent.STM.TChan onCommitChan :: TChan (IO ()) {-# NOINLINE onCommit #-} onCommitChan = unsafePerformIO \$ do chan <- newTChanIO forkIO \$ forever \$ atomically \$ readTChan chan return chan onCommit :: IO () -> STM () onCommit = writeTChan onCommitChan It would be cool if an onCommit hook could be directly added to the stm package. Silvio [1] https://hackage.haskell.org/package/stm-io-hooks-1.0.1
Categories: Offsite Discussion

### Yesod Web Framework: yesod-table

Planet Haskell - Sun, 07/05/2015 - 6:00pm
Announcing yesod-table

Over the last two years, I've seen the need for safe dynamic table-building in half a dozen yesod projects I've worked on. After several design iterations, the result of this experience is yesod-table, which saw its first stable release last week. This blog post will contain code excerpts, but you can also look at the documentation the full example app on github, which can be compiled and run.

Naive Solution

Before getting into specifics about yesod-table, I want to take a look at the naive table-building strategy and identify the common pitfalls. Let's say that you have a data types Color and Person:

data Color = Red | Green | Blue | Purple deriving (Show) data Person = Person { firstName :: Text , lastName :: Text , age :: Int , favoriteColor :: Color }

We have a list of Person (let's call it people), and we want to show them all in a table. You could write out a hamlet file like this:

<table> <thead> <tr> <th>First Name</th> <th>Last Name</th> <th>Age</th> <tbody> \$forall p <- people <tr> <td>#{firstName p} <td>#{lastName p} <td>#{show (age p)}

And there it is. This is the simplest solution to building a table. In fact, if you've worked on web applications for any length of time, you've probably written code like this before. I've implemented this pattern in PHP+html, in rails+haml, and in yesod+hamlet projects. And every time, it is unsatisfactory.

Problems With Naive Solution

Let's take a look at three reasons why this solution leaves us wanting something more:

• Duplication. After building a few tables this way, you realize that you are copying the HTML elements and the list iteration (\$forall) every time.
• Non-composability. If I want to build a similar table, one that shows the same fields but additionally has a column for favoriteColor, I have to copy the whole thing. I can't glue another piece onto the end.
• Breakable Invariant. If we do decide to add a favoriteColor column, we might try simply adding <td>#{show (favoriteColor p)} to the end. This would cause incorrect behavior at runtime, because we would have forgotten to add <th>Favorite Color to the table header. The problem is that we have an invariant not captured by the type system: thead and the tbody loop must have the same number of <th>/<td> elements, and the order must match.

In particular, the last issue (breakable invariant) has been a source of great pains to me before. On a three-column table, you are less likely to forget the <th> or put it in the wrong place. As the table gets larger though (six or more columns), these mistakes become easier to make, and it's harder to be sure that you did the right thing until you see it at runtime.

Example with yesod-table

So let's take a look at how yesod-table addresses these issues. The module it provides should be imported as follows:

import Yesod.Table (Table) import qualified Yesod.Table as Table

Let's build the same table we saw earlier:

peopleBasicInfoTable :: Table site Person peopleBasicInfoTable = mempty <> Table.text "First Name" firstName <> Table.text "Last Name" lastName <> Table.string "Age" (show . age)

And then we can feed it data and render it with buildBootstrap:

-- Although it's called buildBootstrap, it builds a table just fine -- if you aren't using bootstrap. It just adds bootstrap's table classes. getExamplePeopleR = defaultLayout \$ Table.buildBootstrap peopleTable peopleExplanation of Internals

The key to this approach is looking at a table pattern (called a Table in this library) as a collection of columns, not a collection of rows. From the yesod-table source, we have:

newtype Table site a = Table (Seq (Column site a)) deriving (Monoid) data Column site a = Column { header :: !(WidgetT site IO ()) , cell :: !(a -> WidgetT site IO ()) }

Each column is just the content that will go in the <th> (the value of header) and a function that, given the data for a table row, will produce the content that belongs in the <td>. A table is trivially a collection of columns and gets a Monoid instance from Seq for free (for those unfamiliar, Seq a is like [a] but with different performance characteristics). Consequently, any two Tables that are parameterized over the same types can be concatenated. As a final note of explanation, the Table.text function that we saw above just a helper for building singleton tables. So, the three Tables below are equivalant:

import qualified Data.Sequence as Seq import qualified Data.Text as Text -- These three generate a single-column table that displays the age. reallyEasyToReadTable, easyToReadTable, hardToReadTable :: Table site Person reallyEasyToReadTable = Table.int "Age" age easyToReadTable = Table.text "Age" (Text.pack . show . age) hardToReadTable = Table.Table \$ Seq.singleton \$ Table.Column (toWidget \$ toHtml "Age") (toWidget . toHtml . show . age)

As should be clear, the convenience functions for singleton Tables should always be preferred.

How Is This Better?

Now to address the most important question: Why is this better than what we had earlier? Firstly, consider the issue of the breakable invariant. This is now a non-issue. Imagine that we modified the earlier table to show a person's favorite color as well:

peopleFullInfoTable1 :: Table site Person peopleFullInfoTable1 = mempty <> Table.text "First Name" firstName <> Table.text "Last Name" lastName <> Table.text "Age" (show . age) <> Table.string "Favorite Color" (show . favoriteColor)

The table is correct by construction. You cannot forget the column header because it's part of the Column data type. You're less likely to make this mistake, because now that information is directly beside the content-extracting function, but even if you somehow typed this instead, you would get a compile-time error:

<> Table.string (show . favoriteColor)

Secondly, we can look at duplication. All the table-rendering logic is moved into buildBootstrap (and you can write your own table renderer if that one is not satisfactory). The Table that we are using now has neither the HTML elements nor the list iteration that we dealt with earlier.

Finally, we can look at composability. As an alternative way of adding the column for a person's favorite color, we could write:

peopleFullInfoTable2 :: Table site Person peopleFullInfoTable2 = mempty <> peopleBasicInfoTable <> Table.string "Favorite Color" (show . favoriteColor)

Additionally, if we need to promote this Table to work on something like Entity Person (if it was backed by persistent), we could do this:

-- You need to use ekmett's contravariant package peopleEntityFullInfoTable :: Table site (Entity Person) peopleEntityFullInfoTable = contramap entityVal peopleFullInfoTable2

I won't go into contravariant functors here, but it's a very useful pattern for working with Tables. The astute reader will notice that the monoidal composition pattern shown earlier means that we can only append or prepend columns. We cannot inject them into the middle. I'll give yesod-table a B minus on to composability objective.

Closing Notes and Acknowledgements

One final closing note. You may have noticed that all of the Tables in this post were parameterized over site. This is because they don't depend on a particular foundation type. Usually, the way that this can happen is that you use a route in one of the columns:

-- Assume that our foundation type was named App peopleTableWithLink :: Table App (Entity Person) peopleTableWithLink = mempty <> peopleEntityFullInfoTable <> Table.linked "Profile Page" (const "View") (PersonProfileR . entityKey)

The above example must be parameterized over App (or whatever your foundation type is named), not over site.

This monoidal approach to building tables was inspired by Gabriel Gonzalez's Equational Reasoning at Scale and by the classic diagrams paper. I hope that others find the library useful. I am very open to pull requests and suggestions, so if you have an idea for a convenience function, feel free to open up an issue on the github page.

Categories: Offsite Blogs

### Danny Gratzer: A Basic Tutorial on JonPRL

Planet Haskell - Sun, 07/05/2015 - 6:00pm
Posted on July 6, 2015 Tags: jonprl, types

JonPRL switched to ASCII syntax so I’ve updated this post accordingly

I was just over at OPLSS for the last two weeks. While there I finally met Jon Sterling in person. What was particularly fun is that for that last few months he’s been creating a proof assistant called JonPRL in the spirit of Nuprl. As it turns out, it’s quite a fun project to work on so I’ve implemented a few features in it over the last couple of days and learned more or less how it works.

Since there’s basically no documentation on it besides the readme and of course the compiler so I thought I’d write down some of the stuff I’ve learned. There’s also a completely separate post on the underlying type theory for Nuprl and JonPRL that’s very interesting in its own right but this isn’t it. Hopefully I’ll get around to scribbling something about that because it’s really quite clever.

Here’s the layout of this tutorial

• First we start with a whirlwind tutorial. I’ll introduce the basic syntax and we’ll go through some simple proofs together
• I’ll then dive into some of the rational behind JonPRL’s theory. This should help you understand why some things work how they do
• I’ll show off a few of JonPRL’s more unique features and (hopefully) interest you enough to start fiddling on your own
Getting JonPRL

JonPRL is pretty easy to build and install and having it will make this post more enjoyable. You’ll need smlnj since JonPRL is currently written in SML. This is available in most package managers (including homebrew) otherwise just grab the binary from the website. After this the following commands should get you a working executable

• git clone ssh://git@github.com/jonsterling/jonprl
• cd jonprl
• git submodule init
• git submodule update
• make (This is excitingly fast to run)
• make test (If you’re doubtful)

You should now have an executable called jonprl in the bin folder. There’s no prelude for jonprl so that’s it. You can now just feed it files like any reasonable compiler and watch it spew (currently difficult-to-decipher) output at you.

If you’re interested in actually writing JonPRL code, you should probably install David Christiansen’s Emacs mode. Now that we’re up and running, let’s actually figure out how the language works

The Different Languages in JonPRL

JonPRL is composed of really 3 different sorts of mini-languages

• The term language
• The tactic language
• The language of commands to the proof assistant

In Coq, these roughly correspond to Gallina, Ltac, and Vernacular respectively.

The Term Language

The term language is an untyped language that contains a number of constructs that should be familiar to people who have been exposed to dependent types before. The actual concrete syntax is composed of 3 basic forms:

• We can apply an “operator” (I’ll clarify this in a moment) with op(arg1; arg2; arg3).
• We have variables with x.
• And we have abstraction with x.e. JonPRL has one construct for binding x.e built into its syntax, that things like lam or fun are built off of.

An operator in this context is really anything you can imagine having a node in an AST for a language. So something like lam is an operator, as is if or pair (corresponding to (,) in Haskell). Each operator has a piece of information associated with it, called its arity. This arity tells you how many arguments an operator takes and how many variables x.y.z. ... each is allowed to bind. For example, with lam has an arity is written (1) since it takes 1 argument which binds 1 variable. Application (ap) has the arity (0; 0). It takes 2 arguments neither of which bind a variable.

So as mentioned we have functions and application. This means we could write (lamx.x) y in JonPRL as ap(lam(x.x); y). The type of functions is written with fun. Remember that JonPRL’s language has a notion of dependence so the arity is (0; 1). The construct fun(A; x.B) corresponds to (x : A) → B in Agda or forall (x : A), B in Coq.

We also have dependent sums as well (prods). In Agda you would write (M , N) to introduce a pair and prod A lam x → B to type it. In JonPRL you have pair(M; N) and prod(A; x.B). To inspect a prod we have spread which let’s us eliminate a pair pair. Eg spread(0; 2) and you give it a prod in the first spot and x.y.e in the second. It’ll then replace x with the first component and y with the second. Can you think of how to write fst and snd with this?

There’s sums, so inl(M), inr(N) and +(A; B) corresponds to Left, Right, and Either in Haskell. For case analysis there’s decide which has the arity (0; 1; 1). You should read decide(M; x.N; y.P) as something like

case E of Left x -> L Right y -> R

In addition we have unit and <> (pronounced axe for axiom usually). Neither of these takes any arguments so we write them just as I have above. They correspond to Haskell’s type- and value-level () respectively. Finally there’s void which is sometimes called false or empty in theorem prover land.

You’ll notice that I presented a bunch of types as if they were normal terms in this section. That’s because in this untyped computation system, types are literally just terms. There’s no typing relation to distinguish them yet so they just float around exactly as if they were lam or something! I call them types because I’m thinking of later when we have a typing relation built on top of this system but for now there are really just terms. It was still a little confusing for me to see fun(unit; _.unit) in a language without types, so I wanted to make this explicit.

Now we can introduce some more exotic terms. Later, we’re going to construct some rules around them that are going to make it behave that way we might expect but for now, they are just suggestively named constants.

• U{i}, the ith level universe used to classify all types that can be built using types other than U{i} or higher. It’s closed under terms like fun and it contains all the types of smaller universes
• =(0; 0; 0) this is equality between two terms at a type. It’s a proposition that’s going to precisely mirror what’s going on later in the type theory with the equality judgment
• member(0; 0) this is just like = but internalizes membership in a type into the system. Remember that normally “This has that type” is a judgment but with this term we’re going to have a propositional counterpart to use in theorems.

In particular it’s important to distinguish the difference between ∈ the judgment and member the term. There’s nothing inherent in member above that makes it behave like a typing relation as you might expect. It’s on equal footing with flibbertyjibberty(0; 0; 0).

This term language contains the full untyped lambda calculus so we can write all sorts of fun programs like

lam(f.ap(lam(x.ap(f;(ap(x;x)))); lam(x.ap(f;(ap(x;x)))))

which is just the Y combinator. In particular this means that there’s no reason that every term in this language should normalize to a value. There are plenty of terms in here that diverge and in principle, there’s nothing that rules out them doing even stranger things than that. We really only depend on them being deterministic, that e ⇒ v and e ⇒ v' implies that v = v'.

Tactics

The other big language in JonPRL is the language of tactics. Luckily, this is very familiarly territory if you’re a Coq user. Unluckily, if you’ve never heard of Coq’s tactic mechanism this will seem completely alien. As a quick high level idea for what tactics are:

When we’re proving something in a proof assistant we have to deal with a lot of boring mechanical details. For example, when proving A → B → A I have to describe that I want to introduce the A and the B into my context, then I have to suggest using that A the context as a solution to the goal. Bleh. All of that is pretty obvious so let’s just get the computer to do it! In fact, we can build up a DSL of composable “proof procedures” or /tactics/ to modify a particular goal we’re trying to prove so that we don’t have to think so much about the low level details of the proof being generated. In the end this DSL will generate a proof term (or derivation in JonPRL) and we’ll check that so we never have to trust the actual tactics to be sound.

In Coq this is used to great effect. In particular see Adam Chlipala’s book to see incredibly complex theorems with one-line proofs thanks to tactics.

In JonPRL the tactic system works by modifying a sequent of the form H ⊢ A (a goal). Each time we run a tactic we get back a list of new goals to prove until eventually we get to trivial goals which produce no new subgoals. This means that when trying to prove a theorem in the tactic language we never actually see the resulting evidence generated by our proof. We just see this list of H ⊢ As to prove and we do so with tactics.

The tactic system is quite simple, to start we have a number of basic tactics which are useful no matter what goal you’re attempting to prove

• id a tactic which does nothing
• t1; t2 this runs the t1 tactic and runs t2 on any resulting subgoals
• *{t} this runs t as long as t does something to the goal. If t ever fails for whatever reason it merely stops running, it doesn’t fail itself
• ?{t} tries to run t once. If t fails nothing happens
• !{t} runs t and if t does anything besides complete the proof it fails. This means that !{id} for example will always fail.
• t1 | t2 runs t1 and if it fails it runs t2. Only one of the effects for t1 and t2 will be shown.
• t; [t1, ..., tn] first runs t and then runs tactic ti on subgoal ith subgoal generated by t
• trace "some words" will print some words to standard out. This is useful when trying to figure out why things haven’t gone your way.
• fail is the opposite of id, it just fails. This is actually quite useful for forcing backtracking and one could probably implement a makeshift !{} as t; fail.

It’s helpful to see this as a sort of tree, a tactic takes one goal to a list of a subgoals to prove so we can imagine t as this part of a tree

H | ———–————————— (t) H' H'' H'''

If we have some tactic t2 then t; t2 will run t and then run t2 on H, H', and H''. Instead we could have t; [t1, t2, t3] then we’ll run t and (assuming it succeeds) we’ll run t1 on H', t2 on H'', and t3 on H'''. This is actually how things work under the hood, composable fragments of trees :)

Now those give us a sort of bedrock for building up scripts of tactics. We also have a bunch of tactics that actually let us manipulate things we’re trying to prove. The 4 big ones to be aware of are

• intro
• elim #NUM
• eq-cd
• mem-cd

The basic idea is that intro modifies the A part of the goal. If we’re looking at a function, so something like H ⊢ fun(A; x.B), this will move that A into the context, leaving us with H, x : A ⊢ B.

If you’re familiar with sequent calculus intro runs the appropriate right rule for the goal. If you’re not familiar with sequent calculus intro looks at the outermost operator of the A and runs a rule that applies when that operator is to the right of a the ⊢.

Now one tricky case is what should intro do if you’re looking at a prod? Well now things get a bit dicey. We’d might expect to get two subgoals if we run intro on H ⊢ prod(A; x.B), one which proves H ⊢ A and one which proves H ⊢ B or something, but what about the fact that x.B depends on whatever the underlying realizer (that’s the program extracted from) the proof of H ⊢ A! Further, Nuprl and JonPRL are based around extract-style proof systems. These mean that a goal shouldn’t depend on the particular piece of evidence proving of another goal. So instead we have to tell intro up front what we want the evidence for H ⊢ A to be is so that the H ⊢ B section may use it.

To do this we just give intro an argument. For example say we’re proving that · ⊢ prod(unit; x.unit), we run intro [<>] which gives us two subgoals · ⊢ member(<>; unit) and · ⊢ unit. Here the [] let us denote the realizer we’re passing to intro. In general any term arguments to a tactic will be wrapped in []s. So the first goal says “OK, you said that this was your realizer for unit, but is it actually a realizer for unit?” and the second goal substitutes the given realizer into the second argument of prod, x.unit, and asks us to prove that. Notice how here we have to prove member(<>; unit)? This is where that weird member type comes in handy. It let’s us sort of play type checker and guide JonPRL through the process of type checking. This is actually very crucial since type checking in Nuprl and JonPRL is undecidable.

Now how do we actually go about proving member(<>; unit)? Well here mem-cd has got our back. This tactic transforms member(A; B) into the equivalent form =(A; A; B). In JonPRL and Nuprl, types are given meaning by how we interpret the equality of their members. In other words, if you give me a type you have to say

1. What canonical terms are in that terms
2. What it means for two canonical members to be equal

Long ago, Stuart Allen realized we could combine the two by specifying a partial equivalence relation for a type. In this case rather than having a separate notion of membership we check to see if something is equal to itself under the PER because when it is that PER behaves like a normal equivalence relation! So in JonPRL member is actually just a very thin layer of sugar around = which is really the core defining notion of typehood. To handle = we have eq-cd which does clever things to handle most of the obvious cases of equality.

Finally, we have elim. Just like intro let us simplify things on the right of the ⊢, elim let’s us eliminate something on the left. So we tell elim to “eliminate” the nth item in the context (they’re numbered when JonPRL prints them) with elim #n.

Just like with anything, it’s hard to learn all the tactics without experimenting (though a complete list can be found with jonprl --list-tactics). Let’s go look at the command language so we can actually prove some theorems.

Commands

So in JonPRL there are only 4 commands you can write at the top level

• Operator
• [oper] =def= [term] (A definition)
• Tactic
• Theorem

The first three of these let us customize and extend the basic suite of operators and tactics JonPRL comes with. The last actually lets us state and prove theorems.

The best way to see these things is by example so we’re going to build up a small development in JonPRL. We’re going to show that products are monoid with unit up to some logical equivalence. There are a lot of proofs involved here

1. prod(unit; A) entails A
2. prod(A; unit) entails A
3. A entails prod(unit; A)
4. A entails prod(A; unit)
5. prod(A; prod(B; C)) entails prod(prod(A; B); C)
6. prod(prod(A; B); C) entails prod(A; prod(B; C))

I intend to prove 1, 2, and 5. The remaining proofs are either very similar or fun puzzles to work on. We could also prove that all the appropriate entailments are inverses and then we could say that everything is up to isomorphism.

First we want a new snazzy operator to signify nondependent products since writing prod(A; x.B) is kind of annoying. We do this using operator

Operator prod : (0; 0).

This line declares prod as a new operator which takes two arguments binding zero variables each. Now we really want JonPRL to know that prod is sugar for prod. To do this we use =def= which gives us a way to desugar a new operator into a mess of existing ones.

[prod(A; B)] =def= [prod(A; _.B)].

Now we can change any occurrence of prod(A; B) for prod(A; _.B) as we’d like. Okay, so we want to prove that we have a monoid here. What’s the first step? Let’s verify that unit is a left identity for prod. This entails proving that for all types A, prod(unit; A) ⊃ A and A ⊃ prod(unit; A). Let’s prove these as separate theorems. Translating our first statement into JonPRL we want to prove

fun(U{i}; A. fun(prod(unit; A); _. A))

In Agda notation this would be written

(A : Set) → (_ : prod(unit; A)) → A

Let’s prove our first theorem, we start by writing

Theorem left-id1 : [fun(U{i}; A. fun(prod(unit; A); _. A))] { id }.

This is the basic form of a theorem in JonPRL, a name, a term to prove, and a tactic script. Here we have id as a tactic script, which clearly doesn’t prove our goal. When we run JonPRL on this file (C-c C-l if you’re in Emacs) you get back

[XXX.jonprl:8.3-9.1]: tactic 'COMPLETE' failed with goal: ⊢ funA ∈ U{i}. (prod(unit; A)) => A Remaining subgoals: ⊢ funA ∈ U{i}. (prod(unit; A)) => A

So focus on that Remaining subgoals bit, that’s what we have left to prove, it’s our current goal. Now you may notice that this outputted goal is a lot prettier than our syntax! That’s because currently in JonPRL the input and outputted terms may not match, the latter is subject to pretty printing. In general this is great because you can read your remaining goals, but it does mean copying and pasting is a bother. There’s nothing to the left of that ⊢ yet so let’s run the only applicable tactic we know. Delete that id and replace it with

{ intro }.

The goal now becomes

Remaining subgoals:

1. A : U{i} ⊢ (prod(unit; A)) => A ⊢ U{i} ∈ U{i'}

Two ⊢s means two subgoals now. One looks pretty obvious, U{i'} is just the universe above U{i} (so that’s like Set₁ in Agda) so it should be the case that U{i} ∈ U{i'} by definition! So the next tactic should be something like [???, mem-cd; eq-cd]. Now what should that ??? be? Well we can’t use elim because there’s one thing in the context now (A : U{i}), but it doesn’t help us really. Instead let’s run unfold <prod>. This is a new tactic that’s going to replace that prod with the definition that we wrote earlier.

{ intro; [unfold <prod>, mem-cd; eq-cd] }

Notice here that , behinds less tightly than ; which is useful for saying stuff like this. This gives us

Remaining subgoals: 1. A : U{i} ⊢ (unit × A) => A

We run intro again

{ intro; [unfold <prod>, mem-cd; eq-cd]; intro }

Now we are in a similar position to before with two subgoals.

Remaining subgoals: 1. A : U{i} 2. _ : unit × A ⊢ A 1. A : U{i} ⊢ unit × A ∈ U{i}

The first subgoal is really what we want to be proving so let’s put a pin in that momentarily. Let’s get rid of that second subgoal with a new helpful tactic called auto. It runs eq-cd, mem-cd and intro repeatedly and is built to take care of boring goals just like this!

{ intro; [unfold <prod>, mem-cd; eq-cd]; intro; [id, auto] }

Notice that we used what is a pretty common pattern in JonPRL, to work on one subgoal at a time we use []’s and ids everywhere except where we want to do work, in this case the second subgoal.

Now we have

Remaining subgoals: 1. A : U{i} 2. _ : unit × A ⊢ A

Cool! Having a pair of unit × A really ought to mean that we have an A so we can use elim to get access to it.

{ intro; [unfold <prod>, mem-cd; eq-cd]; intro; [id, auto]; elim #2 }

This gives us

Remaining subgoals: 1. A : U{i} 2. _ : unit × A 3. s : unit 4. t : A ⊢ A

We’ve really got the answer now, #4 is precisely our goal. For this situations there’s assumption which is just a tactic which succeeds if what we’re trying to prove is in our context already. This will complete our proof

Theorem left-id1 : [fun(U{i}; A. fun(prod(unit; A); _. A))] { intro; [unfold <prod>, mem-cd; eq-cd]; intro; [id, auto]; elim #2; assumption }.

Now we know that auto will run all of the tactics on the first line except unfold <prod>, so what we just unfold <prod> first and run auto? It ought to do all the same stuff.. Indeed we can shorten our whole proof to unfold <prod>; auto; elim #2; assumption. With this more heavily automated proof, proving our next theorem follows easily.

Theorem right-id1 : [fun(U{i}; A. fun(prod(A; unit); _. A))] { unfold <prod>; auto; elim #2; assumption }.

Next, we have to prove associativity to complete the development that prod is a monoid. The statement here is a bit more complex.

Theorem assoc : [fun(U{i}; A. fun(U{i}; B. fun(U{i}; C. fun(prod(A; prod(B;C)); _. prod(prod(A;B); C)))))] { id }.

In Agda notation what I’ve written above is

assoc : (A B C : Set) → A × (B × C) → (A × B) × C assoc = ?

Let’s kick things off with unfold <prod>; auto to deal with all the boring stuff we had last time. In fact, since x appears in several nested places we’d have to run unfold quite a few times. Let’s just shorten all of those invocations into *{unfold <prod>}

{ *{unfold <prod>}; auto }

This leaves us with the state

Remaining subgoals:

1. A : U{i} 2. B : U{i} 3. C : U{i} 4. _ : A × B × C ⊢ A 1. A : U{i} 2. B : U{i} 3. C : U{i} 4. _ : A × B × C ⊢ B 1. A : U{i} 2. B : U{i} 3. C : U{i} 4. _ : A × B × C ⊢ C

In each of those goals we need to take apart the 4th hypothesis so let’s do that

{ *{unfold <prod>}; auto; elim #4 }

This leaves us with 3 subgoals still

1. A : U{i} 2. B : U{i} 3. C : U{i} 4. _ : A × B × C 5. s : A 6. t : B × C ⊢ A 1. A : U{i} 2. B : U{i} 3. C : U{i} 4. _ : A × B × C 5. s : A 6. t : B × C ⊢ B 1. A : U{i} 2. B : U{i} 3. C : U{i} 4. _ : A × B × C 5. s : A 6. t : B × C ⊢ C

The first subgoal is pretty easy, assumption should handle that. In the other two we want to eliminate 6 and then we should be able to apply assumption. In order to deal with this we use | to encode that disjunction. In particular we want to run assumption OR elim #6; assumption leaving us with

{ *{unfold <prod>}; auto; elim #4; (assumption | elim #6; assumption) }

This completes the proof!

Theorem assoc : [fun(U{i}; A. fun(U{i}; B. fun(U{i}; C. fun(prod(A; prod(B;C)); _. prod(prod(A;B); C)))))] { *{unfold <prod>}; auto; elim #4; (assumption | elim #6; assumption) }.

As a fun puzzle, what needs to change in this proof to prove we can associate the other way?

What on earth did we just do!?

So we just proved a theorem.. but what really just happened? I mean how did we go from “Here we have an untyped computation system which types just behaving as normal terms” to “Now apply auto and we’re done!”. In this section I’d like to briefly sketch the path from untyped computation to theorems.

The path looks like this

• We start with our untyped language and its notion of computation

We already discussed this in great depth before.

• We define a judgment a = b ∈ A.

This is a judgment, not a term in that language. It exists in whatever metalanguage we’re using. This judgment is defined across 3 terms in our untyped language (I’m only capitalizing A out of convention). This is supposed to represent that a and b are equal elements of type A. This also gives meaning to typehood: something is a type in CTT precisely when we know what the partial equivalence relation defined by - = - ∈ A on canonical values is.

Notice here that I said partial. It isn’t the case that a = b ∈ A presupposes that we know that a : A and b : A because we don’t have a notion of : yet!

In some sense this is where we depart from a type theory like Coq or Agda’s. We have programs already and on top of them we define this 3 part judgment which interacts which computation in a few ways I’m not specifying. In Coq, we would specify one notion of equality, generic over all types, and separately specify a typing relation.

• From here we can define the normal judgments of Martin Lof’s type theory. For example, a : A is a = a ∈ A. We recover the judgment A type with A = A ∈ U (where U here is a universe).

This means that inhabiting a universe A = A ∈ U, isn’t necessarily inductively defined but rather negatively generated. We specify some condition a term must satisfy to occupy a universe.

Hypothetical judgments are introduced in the same way they would be in Martin-Lof’s presentations of type theory. The idea being that H ⊢ J if J is evident under the assumption that each term in H has the appropriate type and furthermore that J is functional (respects equality) with respect to what H contains. This isn’t really a higher order judgment, but it will be defined in terms of a higher order hypothetical judgment in the metatheory.

With this we have something that walks and quacks like normal type theory. Using the normal tools of our metatheory we can formulate proofs of a : A and do normal type theory things. This whole development is building up what is called “Computational Type Theory”. The way this diverges from Martin-Lof’s extensional type theory is subtle but it does directly descend from Martin-Lof’s famous 1979 paper “Constructive Mathematics and Computer Programming” (which you should read. Instead of my blog post).

Now there’s one final layer we have to consider, the PRL bit of JonPRL. We define a new judgment, H ⊢ A [ext a]. This is judgment is cleverly set up so two properties hold

• H ⊢ A [ext a] should entail that H ⊢ a : A or H ⊢ a = a ∈ A
• In H ⊢ A [ext a], a is an output and H and A are inputs. In particular, this implies that in any inference for this judgment, the subgoals may not use a in their H and A.

This means that a is completely determined by H and A which justifies my use of the term output. I mean this in the sense of Twelf and logic programming if that’s a more familiar phrasing. It’s this judgment that we see in JonPRL! Since that a is output we simply hide it, leaving us with H ⊢ A as we saw before. When we prove something with tactics in JonPRL we’re generating a derivation, a tree of inference rules which make H ⊢ A evident for our particular H and A! These rules aren’t really programs though, they don’t correspond one to one with proof terms we may run like they would in Coq. The computational interpretation of our program is bundled up in that a.

To see what I mean here we need a little bit more machinery. Specifically, let’s look at the rules for the equality around the proposition =(a; b; A). Remember that we have a term <> lying around,

a = b ∈ A ———————————————————— <> = <> ∈ =(a; b; A)

So the only member of =(a; b; A) is <> if a = b ∈ A actually holds. First off, notice that <> : A and <> : B doesn’t imply that A = B! In another example, lam(x. x) ∈ fun(A; _.A) for all A! This is a natural consequence of separating our typing judgment from our programming language. Secondly, there’s not really any computation in the e of H ⊢ =(a; b; A) (e). After all, in the end the only thing e could be so that e : =(a; b; A) is <>! However, there is potentially quite a large derivation involved in showing =(a; b; A)! For example, we might have something like this

x : =(A; B; U{i}); y : =(b; a; A) ⊢ =(a; b; B) ———————————————————————————————————————————————— Substitution x : =(A; B; U{i}); y : =(b; a; A) ⊢ =(a; b; A) ———————————————————————————————————————————————— Symmetry x : =(A; B; U{i}); y : =(b; a; A) ⊢ =(b; a; A) ———————————————————————————————————————————————— Assumption

Now we write derivations of this sequent up side down, so the thing we want to show starts on top and we write each rule application and subgoal below it (AI people apparently like this?). Now this was quite a derivation, but if we fill in the missing [ext e] for this derivation from the bottom up we get this

x : =(A; B; U{i}); y : =(b; a; A) ⊢ =(a; b; B) ———————————————————————————————————————————————— Substitution [ext <>] x : =(A; B; U{i}); y : =(b; a; A) ⊢ =(a; b; A) ———————————————————————————————————————————————— Symmetry [ext <>] x : =(A; B; U{i}); y : =(b; a; A) ⊢ =(b; a; A) ———————————————————————————————————————————————— Assumption [ext x]

Notice how at the bottom there was some computational content (That x signifies that we’re accessing a variable in our context) but than we throw it away right on the next line! That’s because we find that no matter what the extract was that let’s us derive =(b; a; A), the only realizer it could possible generate is <>. Remember our conditions, if we can make evident the fact that b = a ∈ A then <> ∈ =(b; a; A). Because we somehow managed to prove that b = a ∈ A holds, we’re entitled to just use <> to realize our proof. This means that despite our somewhat tedious derivation and the bookkeeping that we had to do to generate that program, that program reflects none of it.

This is why type checking in JonPRL is woefully undecidable: in part, the realizers that we want to type check contain none of the helpful hints that proof terms in Coq would. This also means that extraction from JonPRL proofs is built right into the system and we can actually generate cool and useful things! In Nuprl-land, folks at Cornell actually write proofs and use this realizers to run real software. From what Bob Constable said at OPLSS they can actually get these programs to run fast (within 5x of naive C code).

So to recap, in JonPRL we

• See H ⊢ A
• Use tactics to generate a derivation of this judgment
• Once this derivation is generated, we can extract the computational content as a program in our untyped system

In fact, we can see all of this happen if you call JonPRL from the command line or hit C-c C-c in emacs! On our earlier proof we see

Operator prod : (0; 0). ⸤prod(A; B)⸥ ≝ ⸤A × B⸥. Theorem left-id1 : ⸤⊢ funA ∈ U{i}. (prod(unit; A)) => A⸥ { fun-intro(A.fun-intro(_.prod-elim(_; _.t.t); prod⁼(unit⁼; _.hyp⁼(A))); U⁼{i}) } ext { lam_. lam_. spread(_; _.t.t) }. Theorem right-id1 : ⸤⊢ funA ∈ U{i}. (prod(A; unit)) => A⸥ { fun-intro(A.fun-intro(_.prod-elim(_; s._.s); prod⁼(hyp⁼(A); _.unit⁼)); U⁼{i}) } ext { lam_. lam_. spread(_; s._.s) }. Theorem assoc : ⸤⊢ funA ∈ U{i}. funB ∈ U{i}. funC ∈ U{i}. (prod(A; prod(B; C))) => prod(prod(A; B); C)⸥ { fun-intro(A.fun-intro(B.fun-intro(C.fun-intro(_.independent-prod-intro(independent-prod-intro(prod-elim(_; s.t.prod-elim(t; _._.s)); prod-elim(_; _.t.prod-elim(t; s'._.s'))); prod-elim(_; _.t.prod-elim(t; _.t'.t'))); prod⁼(hyp⁼(A); _.prod⁼(hyp⁼(B); _.hyp⁼(C)))); U⁼{i}); U⁼{i}); U⁼{i}) } ext { lam_. lam_. lam_. lam_. ⟨⟨spread(_; s.t.spread(t; _._.s)), spread(_; _.t.spread(t; s'._.s'))⟩, spread(_; _.t.spread(t; _.t'.t'))⟩ }.

Now we can see that those Operator and ≝ bits are really what we typed with =def= and Operator in JonPRL, what’s interesting here are the theorems. There’s two bits, the derivation and the extract or realizer.

{ derivation of the sequent · ⊢ A } ext { the program in the untyped system extracted from our derivation }

We can move that derivation into a different proof assistant and check it. This gives us all the information we need to check that JonPRL’s reasoning and helps us not trust all of JonPRL (I wrote some of it so I’d be a little scared to trust it :). We can also see the computational bit of our proof in the extract. For example, the computation involved in taking A × unit → A is just lam_. lam_. spread(_; s._.s)! This is probably closer to what you’ve seen in Coq or Idris, even though I’d say the derivation is probably more similar in spirit (just ugly and beta normal). That’s because the extract need not have any notion of typing or proof, it’s just the computation needed to produce a witness of the appropriate type. This means for a really tricky proof of equality, your extract might just be <>! Your derivation however will always exactly reflect the complexity of your proof.

Killer features

OK, so I’ve just dumped about 50 years worth of hard research in type theory into your lap which is best left to ruminate for a bit. However, before I finish up this post I wanted to do a little bit of marketing so that you can see why one might be interested in JonPRL (or Nuprl). Since we’ve embraced this idea of programs first and types as PERs, we can define some really strange types completely seamlessly. For example, in JonPRL there’s a type ⋂(A; x.B), it behaves a lot like fun but with one big difference, the definition of - = - ∈ ⋂(A; x.B) looks like this

a : A ⊢ e = e' ∈ [a/x]B ———————————————————————— e = e' ∈ ⋂(A; x.B)

Notice here that e and e' may not use a anywhere in their bodies. That is, they have to be in [a/x]B without knowing anything about a and without even having access to it.

This is a pretty alien concept that turned out to be new in logic as well (it’s called “uniform quantification” I believe). It turns out to be very useful in PRL’s because it lets us declare things in our theorems without having them propogate into our witness. For example, we could have said

Theorem right-id1 : [⋂(U{i}; A. fun(prod(A; unit); _. A))] { unfold <prod>; auto; elim #2; assumption }.

With the observation that our realizer doesn’t need to depend on A at all (remember, no types!). Then the extract of this theorem is

There’s no spurious lam _. ... at the beginning! Even more wackily, we can define subsets of an existing type since realizers need not have unique types

e = e' ∈ A [e/x]P [e'/x]P ———————————————————————————— e = e' ∈ subset(A; x.P)

And in JonPRL we can now say things like “all odd numbers” by just saying subset(nat; n. ap(odd; n)). In intensional type theories, these types are hard to deal with and still the subject of open research. In CTT they just kinda fall out because of how we thought about types in the first place. Quotients are a similarly natural conception (just define a new type with a stricter PER) but JonPRL currently lacks them (though they shouldn’t be hard to add..).

Finally, if you’re looking for one last reason to dig into **PRL, the fact that we’ve defined all our equalities extensionally means that several very useful facts just fall right out of our theory

Theorem fun-ext : [⋂(U{i}; A. ⋂(fun(A; _.U{i}); B. ⋂(fun(A; a.ap(B;a)); f. ⋂(fun(A; a.ap(B;a)); g. ⋂(fun(A; a.=(ap(f; a); ap(g; a); ap(B; a))); _. =(f; g; fun(A; a.ap(B;a))))))))] { auto; ext; ?{elim #5 [a]}; auto }.

This means that two functions are equal in JonPRL if and only if they map equal arguments to equal output. This is quite pleasant for formalizing mathematics for example.

Wrap Up

Whew, we went through a lot! I didn’t intend for this to be a full tour of JonPRL, just a taste of how things sort of hang together and maybe enough to get you looking through the examples. Speaking of which, JonPRL comes with quite a few examples which are going to make a lot more sense now.

Additionally, you may be interested in the documentation in the README which covers most of the primitive operators in JonPRL. As for an exhaustive list of tactics, well….

Hopefully I’ll be writing about JonPRL again soon. Until then, I hope you’ve learned something cool :)

A huge thanks to David Christiansen and Jon Sterling for tons of helpful feedback on this

Categories: Offsite Blogs

### ANN: stack-0.1.2.0

Haskell on Reddit - Sun, 07/05/2015 - 5:31pm

New release of stack, a build tool. (Cross-post from the official mailing list)