News aggregator

goldfirere/units · GitHub

del.icio.us/haskell - Mon, 01/12/2015 - 3:08pm
Categories: Offsite Blogs

JP Moresmau: EclipseFP 2.6.3 released

Planet Haskell - Mon, 01/12/2015 - 1:44pm
A new version of EclipseFP, the Eclipse plugins for Haskell development, has been released. The release notes can be found here.

As usual install or update from Eclipse by using the update site http://eclipsefp.sf.net/updates.

Happy Haskell Hacking!
Categories: Offsite Blogs

Trying to compile a Haskell program statically, but ghc can't find ffi

Haskell on Reddit - Mon, 01/12/2015 - 11:39am

I'm running Fedora 20 trying to statically compile a very minimal Haskell program (I want to make an executable suitable for cgi-bin). The command I'm using is

ghc -O2 --make -static -optc-static -optl-static Test.hs

It exits with this error however:

Linking Test ... /usr/bin/ld: cannot find -lffi /usr/lib64/ghc-7.6.3/libHSrts.a(Linker.o): In function `addDLL': (.text+0x1a19): warning: Using 'dlopen' in statically linked applications requires at runtime the shared libraries from the glibc version used for linking collect2: error: ld returned exit status 1

/usr/bin/ld: cannot find -lffi seems to me to be the failure inducing error (the other message is a warning). So I think I need the to install the static version of the foreign function interface library, but I can't find it in the Fedora repo.

Has anybody else had this kind of problem before or know what is going on?

submitted by dissonantloos
[link] [5 comments]
Categories: Incoming News

why can it never go smoothly,language-c-0.4.7 edition

haskell-cafe - Mon, 01/12/2015 - 8:00am
Hi, setup-Simple-Cabal-1.22.0.0-x86_64-linux-ghc-7.8.4: The program 'happy' is required but it could not be found. so i installed happy. then it wanted alex. which i was also able to install. and then language-c-0.4.7 successfully installed. I have seen this sort of thing many times across all sorts of different packages. So my question is : are these dependency bugs that should be reported to the package maintainer ? or is that certain packages can't be built as a dependency target for some reason ? Thanks, Brian
Categories: Offsite Discussion

Asking for feedback on a small library - Constructing Transformer stacks and Interfaces at compile time

Haskell on Reddit - Mon, 01/12/2015 - 7:09am

Hi,

in my quest on making programs extensible, but also hide implementation details between plug-ins or components I wrote a small library which uses Template Haskell to construct a Transformer stack at compile time. Transformers can be user defined newtypes which hide the underlying Reader, State or whatever implementation. For those newtyped Transformers, interface function can be defined. Using those functions, classes can be automatically generated, so that lifting is not necessary anymore.

The library can be found here. If the description above sounds too strange, please take a look at the example.

Ninja edit: Didn't submit to Hackage yet, because I wanted to hear first if people find it worthy. Thanks!

submitted by jrk-
[link] [3 comments]
Categories: Incoming News

Antti-Juhani Kaijanaho (ibid): Planet Haskell email is broken (UPDATE: fixed)

Planet Haskell - Mon, 01/12/2015 - 5:54am

I became aware about a week ago that Planet Haskell’s email address had not received any traffic for a while. It turns out the community.haskell.org email servers are misconfigured. The issue remains unfixed as of this writing. Update: this issue has been fixed.

Please direct your Planet Haskell related mail directly to me (antti-juhani@kaijanaho.fi) for the duration of the problem.

Categories: Offsite Blogs

Data.ByteString.Unsafe.unsafeWipe

libraries list - Mon, 01/12/2015 - 5:42am
Discussion period: one month When handling sensitive information (like a user's password) it is desirable to only keep the data around for as short a time as possible. Specifically, relying on the garbage collector to clean it up is simply not good enough. I therefore propose that the following function to be added to the Data.ByteString.Unsafe module: -- | Overwrites the contents of a ByteString with \0 bytes. unsafeWipe :: ByteString -> IO () unsafeWipe bs = BS.unsafeUseAsCStringLen bs $ \(ptr, len) -> let go i | i < 0 = return () | otherwise = pokeElemOff ptr i 0 >> go (i - 1) in go (len - 1) It is added to the Unsafe module because it break referential transparency but since ByteStrings are always kept in pinned memory, it should not otherwise be considered unsafe. It could be used as follows: main = do passwd <- getPassword doSomethingWith passwd unsafeWipe passwd restOfProgram
Categories: Offsite Discussion

Equality Constraints (a ~ b)

glasgow-user - Mon, 01/12/2015 - 1:04am
Hi, I am trying to find more background on these. They don’t exist in the Haskell 2010 Language Report, they didn’t exist in ghc 6.8.2 but make an appearance in 7.0.1. The documentation in the manual is rather sparse and doesn’t contain a reference: https://downloads.haskell.org/~ghc/latest/docs/users_guide.pdf section 7.11. Folk on #ghc referred me to http://research.microsoft.com/en-us/um/people/simonpj/papers/ext-f/. I can find papers that refer to ~ in F_C (aka FC?) but as far as I can tell not in the Haskell language itself. Many thanks Dominic Steinitz dominic< at >steinitz.org http://idontgetoutmuch.wordpress.com
Categories: Offsite Discussion

Keegan McAllister: Continuations in C++ with fork

Planet Haskell - Mon, 01/12/2015 - 12:18am

[Update, Jan 2015: I've translated this code into Rust.]

While reading "Continuations in C" I came across an intriguing idea:

It is possible to simulate call/cc, or something like it, on Unix systems with system calls like fork() that literally duplicate the running process.

The author sets this idea aside, and instead discusses some code that uses setjmp/longjmp and stack copying. And there are several other continuation-like constructs available for C, such as POSIX getcontext. But the idea of implementing call/cc with fork stuck with me, if only for its amusement value. I'd seen fork used for computing with probability distributions, but I couldn't find an implementation of call/cc itself. So I decided to give it a shot, using my favorite esolang, C++.

Continuations are a famously mind-bending idea, and this article doesn't totally explain what they are or what they're good for. If you aren't familiar with continuations, you might catch on from the examples, or you might want to consult another source first (1, 2, 3, 4, 5, 6).

Small examples

I'll get to the implementation later, but right now let's see what these fork-based continuations can do. The interface looks like this.

template <typename T>
class cont {
public:
void operator()(const T &x);
};

template <typename T>
T call_cc( std::function< T (cont<T>) > f );

std::function is a wrapper that can hold function-like values, such as function objects or C-style function pointers. So call_cc<T> will accept any function-like value that takes an argument of type cont<T> and returns a value of type T. This wrapper is the first of several C++11 features we'll use.

call_cc stands for "call with current continuation", and that's exactly what it does. call_cc(f) will call f, and return whatever f returns. The interesting part is that it passes to f an instance of our cont class, which represents all the stuff that's going to happen in the program after f returns. That cont object overloads operator() and so can be called like a function. If it's called with some argument x, the program behaves as though f had returned x.

The types reflect this usage. The type parameter T in cont<T> is the return type of the function passed to call_cc. It's also the type of values accepted by cont<T>::operator().

Here's a small example.

int f(cont<int> k) {
std::cout << "f called" << std::endl;
k(1);
std::cout << "k returns" << std::endl;
return 0;
}

int main() {
std::cout << "f returns " << call_cc<int>(f) << std::endl;
}

When we run this code we get:

f called
f returns 1

We don't see the "k returns" message. Instead, calling k(1) bails out of f early, and forces it to return 1. This would happen even if we passed k to some deeply nested function call, and invoked it there.

This nonlocal return is kind of like throwing an exception, and is not that surprising. More exciting things happen if a continuation outlives the function call it came from.

boost::optional< cont<int> > global_k;

int g(cont<int> k) {
std::cout << "g called" << std::endl;
global_k = k;
return 0;
}

int main() {
std::cout << "g returns " << call_cc<int>(g) << std::endl;

if (global_k)
(*global_k)(1);
}

When we run this, we get:

g called
g returns 0
g returns 1

g is called once, and returns twice! When called, g saves the current continuation in a global variable. After g returns, main calls that continuation, and g returns again with a different value.

What value should global_k have before g is called? There's no such thing as a "default" or "uninitialized" cont<T>. We solve this problem by wrapping it with boost::optional. We use the resulting object much like a pointer, checking for "null" and then dereferencing. The difference is that boost::optional manages storage for the underlying value, if any.

Why isn't this code an infinite loop? Because invoking a cont<T> also resets global state to the values it had when the continuation was captured. The second time g returns, global_k has been reset to the "null" optional value. This is unlike Scheme's call/cc and most other continuation systems. It turns out to be a serious limitation, though it's sometimes convenient. The reason for this behavior is that invoking a continuation is implemented as a transfer of control to another process. More on that later.

Backtracking

We can use continuations to implement backtracking, as found in logic programming languages. Here is a suitable interface.

bool guess();
void fail();

We will use guess as though it has a magical ability to predict the future. We assume it will only return true if doing so results in a program that never calls fail. Here is the implementation.

boost::optional< cont<bool> > checkpoint;

bool guess() {
return call_cc<bool>( [](cont<bool> k) {
checkpoint = k;
return true;
} );
}

void fail() {
if (checkpoint) {
(*checkpoint)(false);
} else {
std::cerr << "Nothing to be done." << std::endl;
exit(1);
}
}

guess invokes call_cc on a lambda expression, which saves the current continuation and returns true. A subsequent call to fail will invoke this continuation, retrying execution in a world where guess had returned false instead. In Scheme et al, we would store a whole stack of continuations. But invoking our cont<bool> resets global state, including the checkpoint variable itself, so we only need to explicitly track the most recent continuation.

Now we can implement the integer factoring example from "Continuations in C".

int integer(int m, int n) {
for (int i=m; i<=n; i++) {
if (guess())
return i;
}
fail();
}

void factor(int n) {
const int i = integer(2, 100);
const int j = integer(2, 100);

if (i*j != n)
fail();

std::cout << i << " * " << j << " = " << n << std::endl;
}

factor(n) will guess two integers, and fail if their product is not n. Calling factor(391) will produce the output

17 * 23 = 391

after a moment's delay. In fact, you might see this after your shell prompt has returned, because the output is produced by a thousand-generation descendant of the process your shell created.

Solving a maze

For a more substantial use of backtracking, let's solve a maze.

const int maze_size = 15;
char maze[] =
"X-------------+\n"
" | |\n"
"|--+ | | | |\n"
"| | | | --+ |\n"
"| | | |\n"
"|-+---+--+- | |\n"
"| | | |\n"
"| | | ---+-+- |\n"
"| | | |\n"
"| +-+-+--| |\n"
"| | | |--- |\n"
"| | |\n"
"|--- -+-------|\n"
"| \n"
"+------------- \n";

void solve_maze() {
int x=0, y=0;

while ((x != maze_size-1)
|| (y != maze_size-1)) {

if (guess()) x++;
else if (guess()) x--;
else if (guess()) y++;
else y--;

if ( (x < 0) || (x >= maze_size) ||
(y < 0) || (y >= maze_size) )
fail();

const int i = y*(maze_size+1) + x;
if (maze[i] != ' ')
fail();
maze[i] = 'X';
}

for (char c : maze) {
if (c == 'X')
std::cout << "\e[1;32mX\e[0m";
else
std::cout << c;
}
}

Whether code or prose, the algorithm is pretty simple. Start at the upper-left corner. As long as we haven't reached the lower-right corner, guess a direction to move. Fail if we go off the edge, run into a wall, or find ourselves on a square we already visited.

Once we've reached the goal, we iterate over the char array and print it out with some rad ANSI color codes.

Once again, we're making good use of the fact that our continuations reset global state. That's why we see 'X' marks not on the failed detours, but only on a successful path through the maze. Here's what it looks like.


X-------------+
XXXXXXXX| |
|--+ |X| | |
| | |X| --+ |
| |XXXXX| |
|-+---+--+-X| |
| |XXX | XXX|
| |X|X---+-+-X|
|XXX|XXXXXX|XX|
|X+-+-+--|XXX |
|X| | |--- |
|XXXX | |
|---X-+-------|
| XXXXXXXXXXX
+-------------X

Excess backtracking

We can run both examples in a single program.

int main() {
factor(391);
solve_maze();
}

If we change the maze to be unsolvable, we'll get:

17 * 23 = 391
23 * 17 = 391
Nothing to be done.

Factoring 391 a different way won't change the maze layout, but the program doesn't know that. We can add a cut primitive to eliminate unwanted backtracking.

void cut() {
checkpoint = boost::none;
}

int main() {
factor(391);
cut();
solve_maze();
}

The implementation

For such a crazy idea, the code to implement call_cc with fork is actually pretty reasonable. Here's the core of it.

template <typename T>
// static
T cont<T>::call_cc(call_cc_arg f) {
int fd[2];
pipe(fd);
int read_fd = fd[0];
int write_fd = fd[1];

if (fork()) {
// parent
close(read_fd);
return f( cont<T>(write_fd) );
} else {
// child
close(write_fd);
char buf[sizeof(T)];
if (read(read_fd, buf, sizeof(T)) < ssize_t(sizeof(T)))
exit(0);
close(read_fd);
return *reinterpret_cast<T*>(buf);
}
}

template <typename T>
void cont<T>::impl::invoke(const T &x) {
write(m_pipe, &x, sizeof(T));
exit(0);
}

To capture a continuation, we fork the process. The resulting processes share a pipe which was created before the fork. The parent process will call f immediately, passing a cont<T> object that holds onto the write end of this pipe. If that continuation is invoked with some argument x, the parent process will send x down the pipe and then exit. The child process wakes up from its read call, and returns x from call_cc.

There are a few more implementation details.

  • If the parent process exits, it will close the write end of the pipe, and the child's read will return 0, i.e. end-of-file. This prevents a buildup of unused continuation processes. But what if the parent deletes the last copy of some cont<T>, yet keeps running? We'd like to kill the corresponding child process immediately.

    This sounds like a use for a reference-counted smart pointer, but we want to hide this detail from the user. So we split off a private implementation class, cont<T>::impl, with a destructor that calls close. The user-facing class cont<T> holds a std::shared_ptr to a cont<T>::impl. And cont<T>::operator() simply calls cont<T>::impl::invoke through this pointer.

  • It would be nice to tell the compiler that cont<T>::operator() won't return, to avoid warnings like "control reaches end of non-void function". GCC provides the noreturn attribute for this purpose.

  • We want the cont<T> constructor to be private, so we had to make call_cc a static member function of that class. But the examples above use a free function call_cc<T>. It's easiest to implement the latter as a 1-line function that calls the former. The alternative is to make it a friend function of cont<T>, which requires some forward declarations and other noise.

There are a number of limitations too.

  • As noted, the forked child process doesn't see changes to the parent's global state. This precludes some interesting uses of continuations, like implementing coroutines. In fact, I had trouble coming up with any application other than backtracking. You could work around this limitation with shared memory, but it seemed like too much hassle.

  • Each captured continuation can only be invoked once. This is easiest to observe if the code using continuations also invokes fork directly. It could possibly be fixed with additional forking inside call_cc.

  • Calling a continuation sends the argument through a pipe using a naive byte-for-byte copy. So the argument needs to be Plain Old Data, and had better not contain pointers to anything not shared by the two processes. This means we can't send continuations through other continuations, sad to say.

  • I left out the error handling you would expect in serious code, because this is anything but.

  • Likewise, I'm assuming that a single write and read will suffice to send the value. Robust code will need to loop until completion, handle EINTR, etc. Or use some higher-level IPC mechanism.

  • At some size, stack-allocating the receive buffer will become a problem.

  • It's slow. Well, actually, I'm impressed with the speed of fork on Linux. My machine solves both backtracking problems in about a second, forking about 2000 processes along the way. You can speed it up more with static linking. But it's still far more overhead than the alternatives.

As usual, you can get the code from GitHub.

Categories: Offsite Blogs

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