News aggregator

FLTK bindings near completion. Need communityassistance ...

haskell-cafe - Sun, 01/11/2015 - 8:39pm
Hi all, I've been working on bindings [1] to the FLTK GUI toolkit [2] and I've come to the point where it's mostly complete but I could use some help from the community before I put it up on Hackage. My hope is to eventually fill the need in the Haskell ecosystem for a native GUI library that: - runs on all platforms - is easily installable - is small and fast - has a minimum of dependencies. Currently this library uses only base, stm, bytestring and c2hs. - is conservative with extensions. Currently the most recent extension required is GADTs. If any of this sounds good to you, I could use some help with: - testing the build on Linux and OSX. This should be as simple as installing FLTK, cloning the repo [1] and running `cabal build`. Better instructions are in included README. - getting it to build on Windows. I unfortunately don't have access to a Windows machine. - getting it to build on older GHC's. I used 7.8.3 because that is what I have, but it should work back to the first version of GHC that intro
Categories: Offsite Discussion

Show /r/haskell: htoml, a parser for toml files

Haskell on Reddit - Sun, 01/11/2015 - 2:08pm

An update on the TOML file parser (README) that I first posted here ~2 months ago. But first a big thank you for the feedback back then, it was very helpful.

Since then I moved the codebase from Attoparsec to Parsec, as better error messages were more important then speed. I also incorporated BurntSushi's language agnostic toml-tests, as an extra set of (integration) tests on top of my own (unit) tests. I have also uploaded the package on Hackage.

As it is my first public-consumption-lib in Haskell any advice/critique/etc is greatly appreciated. After this round of feedback I want to release a 1.0-stable version.

The meat of the project is in these two files: Types.hs and Parser.hs.

As I also have a criterion benchmark (i really like criterion), I found that the new parsec version is 20% to 400% slower then the old attoparsec version.

submitted by cies010
[link] [3 comments]
Categories: Incoming News

Gabriel Gonzalez: total-1.0.0: Exhaustive pattern matching using traversals, prisms, and lenses

Planet Haskell - Sun, 01/11/2015 - 1:21pm

The lens library provides Prisms, which are a powerful way to decouple a type's interface from its internal representation. For example, consider the Either type from the Haskell Prelude:

data Either a b = Left a | Right b

Instead of exposing the Left and Right constructors, you could instead expose the following two Prisms:

_Left :: Prism (Either a b) (Either a' b ) a a'

_Right :: Prism (Either a b) (Either a b') b b'

Everything you can do with a constructor, you can do with the equivalent Prism. For example, if you want to build a value using a Prism, you use review:

review _Left :: a -> Either a b
review _Right :: b -> Either a b

You can also kind-of pattern match on the Prism using preview, returning a Just if the match succeeds or Nothing if the match fails:

preview _Left :: Either a b -> Maybe a
preview _Right :: Either a b -> Maybe b

However, preview is not quite as good as real honest-to-god pattern matching, because if you wish to handle every branch you can't prove in the types that your pattern match was exhaustive:

nonTypeSafe :: Either Char Int -> String
nonTypeSafe e =
case preview _Left e of
Just c -> replicate 3 c
Nothing -> case preview _Right e of
Just n -> replicate n '!'
Nothing -> error "Impossible!" -- Unsatisfying

However, this isn't a flaw with Prisms, but rather a limitation of preview. Prisms actually preserve enough information in the types to support exhaustive pattern matching! The trick for this was described a year ago by Tom Ellis, so I decided to finally implement his idea as the total library.

Example

Here's an example of a total pattern matching using the total library:

import Lens.Family.Total
import Lens.Family.Stock

total :: Either Char Int -> String -- Same as:
total = _case -- total = \case
& on _Left (\c -> replicate 3 c ) -- Left c -> replicate 3 c
& on _Right (\n -> replicate n '!') -- Right n -> replicate n '!'

The style resembles LambdaCase. If you want to actually supply a value in the same expression, you can also write:

e & (_case
& on _Left ...
& on _Right ... )

There's nothing unsafe going on under the hood. on is just 3 lines of code:

on p f g x = case p Left x of
Left l -> f l
Right r -> g r

(&) is just an operator for post-fix function application:

x & f = f x

... and _case is just a synonym for a type class method that checks if a type is uninhabited.

class Empty a where
impossible :: a -> x

_case = impossible

The rest of the library is just code to auto-derive Empty instances using Haskell generics. The entire library is about 40 lines of code.

Generics

Here's an example of exhaustive pattern matching on a user-defined data type:

{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE TemplateHaskell #-}

import Control.Lens.TH (makePrisms)
import GHC.Generics (Generic)
import Lens.Family.Total

data Example a b c = C1 a | C2 b | C3 c deriving (Generic)

makePrisms ''Example

instance (Empty a, Empty b, Empty c) => Empty (Example a b c)

example :: Example String Char Int -> String -- Same as:
example = _case -- example = \case
& on _C1 (\s -> s ) -- C1 s -> s
& on _C2 (\c -> replicate 3 c ) -- C2 c -> replicate 3 c
& on _C3 (\n -> replicate n '!') -- C3 n -> replicate n '!'

This uses two features to remove most of the boiler-plate:

  • deriving (Generic) auto-generates the code for the Empty instance
  • makePrisms uses Template Haskell to auto-generate Prisms for our type.

For those who prefer the lens-family-* suite of libraries over lens, I opened up an issue against lens-family-th so that Lens.Family.TH.makeTraversals can be used in place of makePrisms for exhaustive pattern matching.

When we write this instance in our original code:

instance (Empty a, Empty b, Empty c) => Empty (Example a b c)

... that uses Haskell generics to auto-generate the implementation of the impossible function:

instance (Empty a, Empty b, Empty c) => Empty (Example a b c)
impossible (C1 a) = impossible a
impossible (C2 b) = impossible b
impossible (C3 c) = impossible c

That says that the type Example a b c is uninhabited if and only if the types a, b, and c are themselves uninhabited.

When you write makePrisms ''Example, that creates the following three prisms:

_C1 :: Prism (Example a b c) (Example a' b c ) a a'
_C2 :: Prism (Example a b c) (Example a b' c ) b b'
_C3 :: Prism (Example a b c) (Example a b c') c c'

These Prisms are useful in their own right. You can export them in lieu of your real constructors and they are more powerful in several respects.

Backwards compatibility

There is one important benefit to exporting Prisms and hiding constructors: if you export Prisms you can change your data type's internal representation without changing your API.

For example, let's say that I change my mind and implement Example as two nested Eithers:

type Example a b c = Either a (Either b c)

Had I exposed my constructors, this would be a breaking change for my users. However, if I expose Prisms, then I can preserve the old API by just changing the Prism definition. Instead of auto-generating them using Template Haskell, I can just write:

import Lens.Family.Stock (_Left, _Right)

_C1 = _Left
_C2 = _Right . _Left
_C3 = _Right . _Right

Done! That was easy and the user of my Prisms are completely unaffected by the changes to the internals.

Under the hood

The trick that makes total work is that every branch of the pattern match subtly alters the type. The value that you match on starts out as:

Example String Char Int

... and every time you pattern match against a branch, the on function Voids one of the type parameters. The pattern matching flows from bottom to top:

example = _case
& on _C1 (\s -> s ) -- Step 3: Example Void Void Void
& on _C2 (\c -> replicate 3 c ) -- Step 2: Example String Void Void
& on _C3 (\n -> replicate n '!') -- Step 1: Example String Char Void
-- Step 0: Example String Char Int

Finally, _case just checks that the final type (Example Void Void Void in this case) is uninhabited. All it does is check if the given type is an instance of the Empty type class, which only provides instances for uninhabited types. In this case Example Void Void Void is definitely uninhabited because Void (from Data.Void) is itself uninhabited:

instance Empty Void where
impossible = absurdLenses

What's neat is that this solution works not only for Prisms and Traversals, but for Lenses, too! Check this out:

example :: (Int, Char) -> String -- Same as:
example = _case -- example = \case
& on _1 (\n -> replicate n '1') -- (n, _) -> replicate n '1'

... and the identity lens works (which is just id) works exactly the way you'd expect:

example :: (Int, Char) -> String -- Same as:
example = _case -- example = \case
& on id (\(n, c) -> replicate n c) -- (n, c) -> replicate n c

I didn't intend that when I wrote the library: it just fell naturally out of the types.

Conclusion

The total library now allows library authors to hide their constructors and export a backwards compatible Prism API all while still preserving exhaustive pattern matching.

Note that I do not recommend switching to a lens-only API for all libraries indiscriminately. Use your judgement when deciding whether perfect backwards compatibility is worth the overhead of a lens-only API, both for the library maintainers and your users.

I put the code under the Lens.Family.Total module, not necessarily because I prefer the Lens.Family.* hierarchy, but rather because I would like to see Edward Kmett add these utilities to lens, leaving my library primarily for users of the complementary lens-family-* ecosystem.

You can find the total library on Hackage or on GitHub.

Categories: Offsite Blogs

Cabal: Specify multiple package databases in config file

libraries list - Sun, 01/11/2015 - 2:36am
Hi All, Is it possible to specify multiple package databases in Cabal's config file? Currently, I have two installed package databases. One is the system readonly package database, and the other is the system writable package database. This structure is due to how packaging works on Haiku, so can't be changed. A similar structure would also exist for user package databases. My Cabal config file currently looks like: package-db: /packages/ghc/.self/lib/package.conf.d I need this to be something like: package-db: /packages/ghc/.self/lib/package.conf.d; /system/non-packaged/lib/ghc/package.conf.d Is this possible with the Cabal config file? If so, what is the correct syntax to use? Many Thanks, Jessica
Categories: Offsite Discussion

System.Posix.IO.ByteString

libraries list - Sun, 01/11/2015 - 2:15am
Hi All, I'm playing around with some low level IO and found the following function: System.Posix.IO.fdRead :: Fd -> ByteCount -> IO (String, ByteCount) Ok, close, but what if I need a ByteString instead. I then found this: System.Posix.IO.ByteString.fdRead :: Fd -> ByteCount -> IO (String, ByteCount) which is identical to the one above. The ByteString in the module name suggests it would be using ByteString instead of String? Can anyone explain this for me? Cheers, Erik
Categories: Offsite Discussion

Russell O'Connor: Secure diffie-hellman-group-exchange-sha256

Planet Haskell - Sat, 01/10/2015 - 10:05pm

Recently I have been working on purging DSA from my computer systems. The problem with DSA and ECDSA is that they fail catastrophically with when nonces are accidentally reused, or if the randomly generated nonces are biased. At about the same time, I was pleased to discover an article on securing SSH. It gives further advice in setting up SSH and I have proceeded to apply most of the recommendation listed there.

For key exchange algorithms, the article suggests using curve25519-sha256 and falling back to diffie-hellman-group-exchange-sha256 for compatibility purposed if you must. The diffie-hellman-group-exchange-sha256 protocol allows the client and server to negotiate a prime field to perform the key exchange in. In order to avoid using the smaller prime fields, the article suggests deleting prime numbers less than 2000 bits in size from /etc/ssh/moduli. The problem with this advice is that only the SSH server reads /etc/ssh/moduli; touching this file does nothing to secure your SSH client from using small prime fields during key negotiation. Securing the client is the important use case for diffie-hellman-group-exchange-sha256, because if you can control the server, then it means you will probably use curve25519-sha256 instead.

However, the protocol for diffie-hellman-group-exchange-sha256 does allow the client to negotiate the field side. The problem is that this ability is not exposed for configuration in SSH. To address this, I created a patch for OpenSSH that raises the minimum field size allowed for the diffie-hellman-group-exchange-sha256 key exchange for both the client and server. This means you do not need to edit the /etc/ssh/moduli file to increase the minimum field size for the server, but it will not hurt to do so either.

If you are running NixOS you can download the patch and add it to your /etc/nixos/configuration.nix file with the following attribute.

nixpkgs.config.packageOverrides = oldpkgs: { openssh = pkgs.lib.overrideDerivation oldpkgs.openssh (oldAttrs: { patches = oldAttrs.patches ++ [ ./openssh-dh-grp-min.patch ]; }); };

As an aside, I noticed that this key exchange protocol has a design flaw in it. The hash signed by the server is the hash of V_C || V_S || I_C || I_S || K_S || min || n || max || p || g || e || f || K. The details of what those variables stand for is not important. What is important is that there is a older format of the protocol that is supported for backwards compatibility where the hash signed by the server is the hash of V_C || V_S || I_C || I_S || K_S || n || p || g || e || f || K. In this older protocol, the client only requests a field size without specifying the minimum and maximum allowed bounds. This is why the variables min and max are do not appear in the hash of the older protocol. A short header is sent by the client to determine which of these two versions of this protocol it is using.

The problem is that this header is not part of the hashed data. This little crack has potential to be an exploit. A MITM attacker could replace the header the client sends with the old protocol header, and then try to manipulate the remaining communication between the client and server so that both the client and server hash the same serialized byte string allowing the server to appear to be authenticated to the client, but where the client and server are interpreting that serialized byte string in two different ways. In particular the MITM wants the client to not be doing computation modulo some safe prime, but instead do modular arithmetic over a different ring entirely.

Fortunately this particular little crack does not appear to be wide enough to exploit. The incidental properties of the serialization format do not allow a successful manipulation, at least not in practical SSH configurations.

When one is signing a serialized blob of data, it is important that the data can be unambiguously parsed using only the contents of that data. This principle is violated here because one cannot decide if one will parse min and max without knowing the header, which is not part of the serialized blob of data. The reason this failure can so easily creep into the protocol is that neither the client nor the server actually have to parse that blob of data. They both serialize the data and then create or verify the signature, but parsing is never done. Therefore, parsing is never implemented. Since parsing is not implemented, it is easy to miss that the data serialization format is ambigous.

Categories: Offsite Blogs

Keegan McAllister: 151-byte static Linux binary in Rust

Planet Haskell - Sat, 01/10/2015 - 8:03pm

Part of the sales pitch for Rust is that it's "as bare metal as C".1 Rust can do anything C can do, run anywhere C can run,2 with code that's just as efficient, and at least as safe (but usually much safer).

I'd say this claim is about 95% true, which is pretty good by the standards of marketing claims. A while back I decided to put it to the test, by making the smallest, most self-contained Rust program possible. After resolving a fewissues along the way, I ended up with a 151-byte, statically linked executable for AMD64 Linux. With the release of Rust 1.0-alpha, it's time to show this off.

Here's the Rust code:


#![crate_type="rlib"]
#![allow(unstable)]

#[macro_use] extern crate syscall;

use std::intrinsics;

fn exit(n: usize) -> ! {
unsafe {
syscall!(EXIT, n);
intrinsics::unreachable()
}
}

fn write(fd: usize, buf: &[u8]) {
unsafe {
syscall!(WRITE, fd, buf.as_ptr(), buf.len());
}
}

#[no_mangle]
pub fn main() {
write(1, "Hello!\n".as_bytes());
exit(0);
}

This uses my syscall library, which provides the syscall! macro. We wrap the underlying system calls with Rust functions, each exposing a safe interface to the unsafe syscall! macro. The main function uses these two safe functions and doesn't need its own unsafeannotation. Even in such a small program, Rust allows us to isolate memory unsafety to a subset of the code.

Because of crate_type="rlib", rustc will build this as a static library, from which we extract a single object file tinyrust.o:

$ rustc tinyrust.rs \
-O -C no-stack-check -C relocation-model=static \
-L syscall.rs/target
$ ar x libtinyrust.rlib tinyrust.o
$ objdump -dr tinyrust.o
0000000000000000 <main>:
0: b8 01 00 00 00 mov $0x1,%eax
5: bf 01 00 00 00 mov $0x1,%edi
a: be 00 00 00 00 mov $0x0,%esi
b: R_X86_64_32 .rodata.str1625
f: ba 07 00 00 00 mov $0x7,%edx
14: 0f 05 syscall
16: b8 3c 00 00 00 mov $0x3c,%eax
1b: 31 ff xor %edi,%edi
1d: 0f 05 syscall

We disable stack exhaustion checking, as well as position-independent code, in order to slim down the output. After optimization, the only instructions that survive come from inline assembly blocks in the syscall library.

Note that main doesn't end in a ret instruction. The exit function (which gets inlined) is marked with a "return type" of !, meaning "doesn't return". We make good on this by invoking the unreachableintrinsic after syscall!. LLVM will optimize under the assumption that we can never reach this point, making no guarantees about the program behavior if it is reached. This represents the fact that the kernel is actually going to kill the process before syscall!(EXIT, n) can return.

Because we use inline assembly and intrinsics, this code is not going to work on a stable-channel build of Rust 1.0. It will require an alpha or nightly build until such time as inline assembly and intrinsics::unreachable are added to the stable language of Rust 1.x.

Note that I didn't even use #![no_std]! This program is so tiny that everything it pulls from libstd is a type definition, macro, or fully inlined function. As a result there's nothing of libstd left in the compiler output. In a larger program you may need #![no_std], although its role is greatly reduced following the removal of Rust's runtime.

Linking

This is where things get weird.

Whether we compile from C or Rust,3 the standard linker toolchain is going to include a bunch of junk we don't need. So I cooked up my own linker script:

SECTIONS {
. = 0x400078;

combined . : AT(0x400078) ALIGN(1) SUBALIGN(1) {
*(.text*)
*(.data*)
*(.rodata*)
*(.bss*)
}
}

We smash all the sections together, with no alignment padding, then extract that section as a headerless binary blob:

$ ld --gc-sections -e main -T script.ld -o payload tinyrust.o
$ objcopy -j combined -O binary payload payload.bin

Finally we stick this on the end of a custom ELF header. The header is written in NASM syntax but contains no instructions, only data fields. The base address 0x400078 seen above is the end of this header, when the whole file is loaded at 0x400000. There's no guarantee that ld will put main at the beginning of the file, so we need to separately determine the address of main and fill that in as the e_entry field in the ELF file header.

$ ENTRY=$(nm -f posix payload | grep '^main ' | awk '{print $3}')
$ nasm -f bin -o tinyrust -D entry=0x$ENTRY elf.s
$ chmod +x ./tinyrust
$ ./tinyrust
Hello!

It works! And the size:

$ wc -c < tinyrust
158

Seven bytes too big!

The final trick

To get down to 151 bytes, I took inspiration from this classic article, which observes that padding fields in the ELF header can be used to store other data. Like, say, a string constant. The Rust code changes to access this constant:


use std::{mem, raw};

#[no_mangle]
pub fn main() {
let message: &'static [u8] = unsafe {
mem::transmute(raw::Slice {
data: 0x00400008 as *const u8,
len: 7,
})
};

write(1, message);
exit(0);
}

A Rust slicelike &[u8] consists of a pointer to some memory, and a length indicating the number of elements that may be found there. The module std::raw exposes this as an ordinary struct that we build, then transmute to the actual slice type. The transmute function generates no code; it just tells the type checker to treat our raw::Slice<u8> as if it were a &[u8]. We return this value out of the unsafe block, taking advantage of the "everything is an expression" syntax, and then print the message as before.

Trying out the new version:

$ rustc tinyrust.rs \
-O -C no-stack-check -C relocation-model=static \
-L syscall.rs/target
$ ar x libtinyrust.rlib tinyrust.o
$ objdump -dr tinyrust.o
0000000000000000 <main>:
0: b8 01 00 00 00 mov $0x1,%eax
5: bf 01 00 00 00 mov $0x1,%edi
a: be 08 00 40 00 mov $0x400008,%esi
f: ba 07 00 00 00 mov $0x7,%edx
14: 0f 05 syscall
16: b8 3c 00 00 00 mov $0x3c,%eax
1b: 31 ff xor %edi,%edi
1d: 0f 05 syscall

...
$ wc -c < tinyrust
151
$ ./tinyrust
Hello!

The object code is the same as before, except that the relocation for the string constant has become an absolute address. The binary is smaller by 7 bytes (the size of "Hello!\n") and it still works!

You can find the full code on GitHub. The code in this article works on rustc 1.0.0-dev (44a287e6e 2015-01-08). If I update the code on GitHub, I will also update the version number printed by the included build script.

I'd be curious to hear if anyone can make my program smaller!

  1. C is not really "bare metal", but that's another story

  2. From a pure language perspective. If you want to talk about availability of compilers and libraries, then Rust still has a bit of a disadvantage ;) 

  3. In fact, this code grew out of an earlier experiment with really small binaries in C. 

Categories: Offsite Blogs

Fix (Compose IO f) -> IO (Fix (Compose Identity f))

Haskell on Reddit - Sat, 01/10/2015 - 3:13pm

Suppose I am playing a game where I can move left or right some number of times before dying:

data GameF a b = LeftF a b | RightF a b | DeadF a newtype GameT f a = Game { getGameT :: Fix (Compose f (GameF a)) } type Game a = GameT Identity a type GameIO a = GameT IO a

I can build this structure up taking user input at each level with some function

play :: IO (GameIO a)

And then I have a function like

evaluate :: GameIO a -> IO (Game a)

But is there a general pattern/name for this? Or for types like the following?

Fix (Compose IO f) -> IO (Fix (Compose Identity f)) Fix (Compose IO f) -> IO (Fix f) submitted by markandrus
[link] [8 comments]
Categories: Incoming News

Getting it Done with Haskell.pdf

del.icio.us/haskell - Sat, 01/10/2015 - 12:43pm
Categories: Offsite Blogs

Getting it Done with Haskell.pdf

del.icio.us/haskell - Sat, 01/10/2015 - 12:43pm
Categories: Offsite Blogs

PFQ 4.0 is out!

Haskell on Reddit - Sat, 01/10/2015 - 10:08am

Linux Networking Framework PFQ 4.0 is out! This major release includes HugePages, line-speed capture/transmission with vanilla drivers, a revamped PFQ/lang eDSL, accelerated pcap library and LTS 1.0 Haskell compliancy. http://www.pfq.io

submitted by awgn
[link] [8 comments]
Categories: Incoming News

Philip Wadler: Are the Greens or UKIP a major party? Have your say.

Planet Haskell - Sat, 01/10/2015 - 9:33am
Ofcom has issued a draft ruling that the Greens are not a 'major party' but that UKIP is. Hard to justify, one might think, given that Carolyn Lucas has been a sitting MP since September 2008, while UKIP did not acquire its first MP until a by-election in October 2014. One consequence of Ofcom's decision is that the Greens may be shut out of any televised national election debates, while Farage is given a seat.

It's a draft ruling, and there is still time to have your say.
My own response to Ofcom is below.

Question 1: Please provide your views on:a) the evidence of current support laid out in Annex 2, andb) whether there is any other relevant evidence which you consider Ofcom should take intoaccount for the purposes of the 2015 review of the list of major parties:
The Green Party has had a sitting MP since September 2008, while UKIP has only had a sitting MP since October 2014. This relevant point appears nowhere in the annex.
Question 2: Do you agree with our assessment in relation to each of:a) The existing major parties,b) Traditional Unionist Voice in Northern Ireland,c) The Green Party (including the Scottish Green Party), andd) UKIP?Please provide reasons for your views:
It is a scandal to include UKIP as a major party while excluding the Greens. Either both should be included, or both excluded. I would prefer to see both included.
While UKIP enjoys stronger support than the Greens in current opinion polls, this is a shortlived phenomenon in part driven by the increased coverage recently given to UKIP by news media. Ofcom's role should be to dampen the effect of media focus on the current bandwagon, not to amplify it.
Ofcom should ensure that all serious contenders have an opportunity to make their views heard. The cutoff for being a 'serious contender' should sit at support from around 5% of the electorate.
Question 3: Do you agree with the proposed amendment to Rule 9 of the PPRB Rules Procedures outlined in paragraph 3.7 above? Please provide reasons for your views:
I do not agree with the proposed amendment. It is stated the parties 'might'' raise unsustainable complaints, but no evidence is provided that this is a serious problem. It is more democratic to leave the decision to the Election Commission than to give Ofcom the ability to refuse complaints without any right of appeal.
[I note also that the reference on the web form to 'paragraph 3.7 above' is confusing. Not only does the relevant paragraph not appear on the web page with the question, the web page does not even contain a link to the document containing the paragraph.] 
Categories: Offsite Blogs

Option Monads in Rust

del.icio.us/haskell - Sat, 01/10/2015 - 8:57am
Categories: Offsite Blogs