News aggregator

Keegan McAllister: Turing tarpits in Rust's macro system

Planet Haskell - Fri, 02/20/2015 - 7:55pm
Bitwise Cyclic Tag is an extremely simple automaton slash programming language. BCT uses a program string and a data string, each made of bits. The program string is interpreted as if it were infinite, by looping back around to the first bit.

The program consists of commands executed in order. There is a single one-bit command:

0: Delete the left-most data bit.

and a single two-bit command:

1 x: If the left-most data bit is 1, copy bit x to the right of the data string.

We halt if ever the data string is empty.

Remarkably, this is enough to do universal computation. Implementing it in Rust's macro system gives a proof (probably not the first one) that Rust's macro system is Turing-complete, aside from the recursion limit imposed by the compiler.


#![feature(trace_macros)]

macro_rules! bct {
// cmd 0: d ... => ...
(0, $($ps:tt),* ; $_d:tt)
=> (bct!($($ps),*, 0 ; ));
(0, $($ps:tt),* ; $_d:tt, $($ds:tt),*)
=> (bct!($($ps),*, 0 ; $($ds),*));

// cmd 1p: 1 ... => 1 ... p
(1, $p:tt, $($ps:tt),* ; 1)
=> (bct!($($ps),*, 1, $p ; 1, $p));
(1, $p:tt, $($ps:tt),* ; 1, $($ds:tt),*)
=> (bct!($($ps),*, 1, $p ; 1, $($ds),*, $p));

// cmd 1p: 0 ... => 0 ...
(1, $p:tt, $($ps:tt),* ; $($ds:tt),*)
=> (bct!($($ps),*, 1, $p ; $($ds),*));

// halt on empty data string
( $($ps:tt),* ; )
=> (());
}

fn main() {
trace_macros!(true);
bct!(0, 0, 1, 1, 1 ; 1, 0, 1);
}

This produces the following compiler output:

bct! { 0 , 0 , 1 , 1 , 1 ; 1 , 0 , 1 }
bct! { 0 , 1 , 1 , 1 , 0 ; 0 , 1 }
bct! { 1 , 1 , 1 , 0 , 0 ; 1 }
bct! { 1 , 0 , 0 , 1 , 1 ; 1 , 1 }
bct! { 0 , 1 , 1 , 1 , 0 ; 1 , 1 , 0 }
bct! { 1 , 1 , 1 , 0 , 0 ; 1 , 0 }
bct! { 1 , 0 , 0 , 1 , 1 ; 1 , 0 , 1 }
bct! { 0 , 1 , 1 , 1 , 0 ; 1 , 0 , 1 , 0 }
bct! { 1 , 1 , 1 , 0 , 0 ; 0 , 1 , 0 }
bct! { 1 , 0 , 0 , 1 , 1 ; 0 , 1 , 0 }
bct! { 0 , 1 , 1 , 1 , 0 ; 0 , 1 , 0 }
bct! { 1 , 1 , 1 , 0 , 0 ; 1 , 0 }
bct! { 1 , 0 , 0 , 1 , 1 ; 1 , 0 , 1 }
bct! { 0 , 1 , 1 , 1 , 0 ; 1 , 0 , 1 , 0 }
bct! { 1 , 1 , 1 , 0 , 0 ; 0 , 1 , 0 }
bct! { 1 , 0 , 0 , 1 , 1 ; 0 , 1 , 0 }
bct! { 0 , 1 , 1 , 1 , 0 ; 0 , 1 , 0 }
...
bct.rs:19:13: 19:45 error: recursion limit reached while expanding the macro `bct`
bct.rs:19 => (bct!($($ps),*, 1, $p ; $($ds),*));
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

You can try it online, as well.

Notes about the macro

I would much rather drop the commas and write


// cmd 0: d ... => ...
(0 $($ps:tt)* ; $_d:tt $($ds:tt)*)
=> (bct!($($ps)* 0 ; $($ds)*));

// cmd 1p: 1 ... => 1 ... p
(1 $p:tt $($ps:tt)* ; 1 $($ds:tt)*)
=> (bct!($($ps)* 1 $p ; 1 $($ds)* $p));

// cmd 1p: 0 ... => 0 ...
(1 $p:tt $($ps:tt)* ; $($ds:tt)*)
=> (bct!($($ps)* 1 $p ; $($ds)*));

but this runs into the macro future-proofing rules.

If we're required to have commas, then it's at least nice to handle them uniformly, e.g.


// cmd 0: d ... => ...
(0 $(, $ps:tt)* ; $_d:tt $(, $ds:tt)*)
=> (bct!($($ps),*, 0 ; $($ds),*));

// cmd 1p: 1 ... => 1 ... p
(1, $p:tt $(, $ps:tt)* ; $($ds:tt),*)
=> (bct!($($ps),*, 1, $p ; 1 $(, $ds)*, $p));

// cmd 1p: 0 ... => 0 ...
(1, $p:tt $(, $ps:tt)* ; $($ds:tt),*)
=> (bct!($($ps),*, 1, $p ; $($ds),*));

But this too is disallowed. An $x:tt variable cannot be followed by a repetition $(...)*, even though it's (I believe) harmless. There is an open RFC about this issue. For now I have to handle the "one" and "more than one" cases separately, which is annoying.

In general, I don't think macro_rules! is a good language for arbitrary computation. This experiment shows the hassle involved in implementing one of the simplest known "arbitrary computations". Rather, macro_rules! is good at expressing patterns of code reuse that don't require elaborate compile-time processing. It does so in a way that's declarative, hygienic, and high-level.

However, there is a big middle ground of non-elaborate, but non-trivial computations. macro_rules! is hardly ideal for that, but procedural macros have problems of their own. Indeed, the bct! macro is an extreme case of a pattern I've found useful in the real world. The idea is that every recursive invocation of a macro gives you another opportunity to pattern-match the arguments. Some of html5ever's macrosdo this, for example.

Categories: Offsite Blogs

How to best implement Euler's method?

Haskell on Reddit - Fri, 02/20/2015 - 5:08pm

I am using Euler's method to solve the simple ODE for nuclear decay (see this PDF I just found with google if interested in the math). The math is fine, and I've implemented it in Haskell using recursion to the best of my knowledge, but it is slow.

What is the proper way to do something like this in a purely functional manner? I want to use the results from the previous calculations when I generate list, but I don't know how. I am a complete Haskell noob, so please enlighten me on how I can improve this program. Thanks!

module Main where --import Graphics.Gnuplot.Simple dt = 0.01 -- Timestep tau = 0.05 -- Decay constant n0 = 1000 -- Initial number of particles main = do --plotList [] list print list list :: [(Double, Double)] list = [(num t, t) | t <- [0.0, dt..tau*4]] num :: Double -> Double num t | t > 0 = num (t - dt) - dt / tau * num (t - dt) | otherwise = n0 submitted by 0not
[link] [6 comments]
Categories: Incoming News

Robert Harper: Structure and Efficiency of Computer Programs

Planet Haskell - Fri, 02/20/2015 - 4:37pm

For decades my colleague, Guy Blelloch, and I have promoted a grand synthesis of the two “theories” of computer science, combinatorial theory and logical theory.  It is only a small exaggeration to say that these two schools of thought work in isolation.  The combinatorial theorists concern themselves with efficiency, based on hypothetical translations of high-level algorithms to low-level machines, and have no useful theory of composition, the most important tool for developing large software systems.  Logical theorists concern themselves with composition, emphasizing the analysis of the properties of components of systems and how those components are combined; the heart of logic is a theory of composition (entailment).  But relatively scant attention is paid to efficiency, and, to a distressingly large extent, the situation is worsening, and not improving.

Guy and I have argued, through our separate and joint work, for the applicability of PL ideas to algorithms design, leading. for example, to the concept of adaptive programming that Umut Acar has pursued aggressively over the last dozen years.  And we have argued for the importance of cost analysis, for various measures of cost, at the level of the code that one actually writes, and not how it is compiled.  Last spring, prompted by discussions with Anindya Banerjee at NSF in the winter of 2014, I decided to write a position paper on the topic, outlining the scientific opportunities and challenges that would arise in an attempt to unify the two, disparate theories of computing.  I circulated the first draft privately in May, and revised it in July to prepare for a conference call among algorithms and PL researchers (sponsored by NSF) to find common ground and isolate key technical challenges to achieving its goals.

There are serious obstacles to be overcome if a grand synthesis of the “two theories” is to be achieved.  The first step is to get the right people together to discuss the issues and to formulate a unified vision of what are the core problems, and what are promising directions for short- and long-term research.  The position paper is not a proposal for funding, but is rather a proposal for a meeting designed to bring together two largely (but not entirely) disparate communities.  In summer of 2014 NSF hosted a three-hour long conference call among a number of researchers in both areas with a view towards hosting a workshop proposal in the near future.  Please keep an eye out for future developments.

I am grateful to Anindya Banerjee at NSF for initiating the discussion last winter that led to the paper and discussion, and I am grateful to Swarat Chaudhuri for his helpful comments on the proposal.

[Update: word smithing, corrections, updating, removed discussion of cost models for fuller treatment later, fixed incoherence after revision.]


Filed under: Research Tagged: algorithms, programming languages, research
Categories: Offsite Blogs

Austin Seipp: The New Haskell Homepage

Planet Haskell - Fri, 02/20/2015 - 2:55pm

Roughly 3/4 of a year after Chris Done first proposed his redesign, we finally went live with the new https://haskell.org homepage.

Much of the intermediate time was spent on cleanup of the introductory text, as well as adding features and tweaking designs. There was also a very length process of setting everything up to ensure that the "try it" feature could be deployed and well supported. Finally, we had to do all the work to ensure that both the wiki remained hosted well somewhere else with proper rewrite rules, and also that the non-wiki content hosted under haskell.org (things like /ghc, /platform, /hoogle, etc) continued to work. Some of the more publicly visible elements of this are the move of mailinglist hosting to http://mail.haskell.org and of the wiki content to http://wiki.haskell.org.

When we did finally go live, we got great feedback on reddit and made #1 on hacker news.

There were also a lot of things we missed, and which those threads pointed out -- in particular we didn't pay enough attention to the content of various pages. The "documentation" and "community" section needed lots of cleanup and expansion. Furthermore, the "downloads" page didn't point to the platform. Whoops! (It is to be noted that recommendation of the platform or not is an issue of some discussion now, for example on this active reddit thread. )

We think that we have fixed most of the issues raised. But there are still issues! The code sample for primes doesn't work in the repl. We have an active github ticket discussing the best way to fix this -- either change the sample, change the repl, or both. This is one of a number of issues under discussion on the github tracker.

We still want feedback, we still want patches, and there's still plenty to be made more awesome. For example: should we have some sort of integrated search? How? Where? The github infrastructure makes taking patches and tracking these issues easy. The repo now has 27 contributors, and we're look forward to more.

One balance that has been tricky to strike has been in making the site maximally useful for new users just looking to learn and explore Haskell, while also providing access to the wide range of resources and entry points that the old wiki did. One advantage that we have now is that the wiki is still around, and is still great. Freed from needing to also serve as a default haskell landing page, the wiki can hopefully grow to be an even better resource. It needs volunteers to chip in and curate the content. And ideally it needs a new front page that highlights the things that you _won't_ find on the main homepage, instead of the things you now can. One place we could use more help is in wiki admins, if anyone wants to volunteer. We need people to curate the news and events sections, to fight spam, to manage plugins and investigate adding new features, to update and clean up the stylesheets, and to manage new user accounts. If you're interested, please get in touch at admin@h.o.

All the resources we have today are the result of our open-source culture, that believes in equal parts in education, innovation, and sharing. They stem from people who enjoy Haskell wanting to contribute back to others -- wanting to make more accessible the knowledge and tools they've struggled to master, and wanting to help us make even better and more powerful tools.

There's always more infrastructure work to be done, and there are always more ways to get involved. In a forthcoming blog, I'll write further about some of the other pressing issues we hope to tackle, and where interested parties can chip in.

Categories: Offsite Blogs

A public thank-you for the `lucid` package!

Haskell on Reddit - Fri, 02/20/2015 - 11:40am

I just made a 42 slide html presentation about lambda calculus, with interactive parts, without writing anything else than pure Haskell. Before lucid, this would have been just painful, but now, it was easier to it do this way than by using latex+beamer or even pandoc.

Well Done Chris.

submitted by aleator
[link] [18 comments]
Categories: Incoming News

type checker plugin success depends on whether an expression is manually inlined

glasgow-user - Fri, 02/20/2015 - 4:48am
Hello list, The following file compiles with my plugin. It makes a data family HList have role representational in a way that I believe is safe: https://github.com/aavogt/HListPlugin/blob/master/ex/Coerce.hs#L19 I expect the highlighted line to be acceptable. However, it seems that the plugin never sees anything from line 19, when I uncomment it. Is there something I can do to make that L19 work? Is this a known or intentional limitation of type checker plugins? Thanks, Adam
Categories: Offsite Discussion

Generating modules with data

Haskell on Reddit - Fri, 02/20/2015 - 4:38am
Categories: Incoming News

Beam: an type-safe RDBMS interface that doesn't use Template Haskell

Haskell on Reddit - Fri, 02/20/2015 - 12:14am

In my spare time, I've been working on a type-safe RDBMS (named Beam) that doesn't rely on Template Haskell. I think there are a number of problems with TH, but both persistent and HaskellDB seem to rely on it. I wanted to experiment and see what I could come up with.

Beam uses plain Haskell data types plus some advanced type system extensions like DeriveGeneric, DeriveDataTypeable, and TypeFamilies, and aims to be fairly complete in its mapping from Haskell to SQL. It currently supports where clauses, sub-selects, joins (inner, outer, left, and right), grouping, projection, and aggregates. It's missing support for HAVING clauses and a lot of SQL arithmetic operators (although these are straight-forward to add). Projections work fine as long as you're only projecting full tables, but projecting expressions or fields has some issues that I'll resolve soon. It also needs a lot more documentation (I'm working on it!).

Basically, it's a work in progress (there will be bugs), but I think it's at a good enough place to start soliciting comments and feedback.

I've written up a small tutorial on my website, and here's a link to the github.

So what do you think /r/haskell?

submitted by tathougies
[link] [25 comments]
Categories: Incoming News

Haskell Google Summer of Code Proposal Brainstorming

Haskell on Reddit - Thu, 02/19/2015 - 10:17pm

Haskell.org has applied to be a mentoring organization to the Google Summer of Code. We've been a participating mentoring organization in the Summer of Code since 2006. While we won't know for a couple of weeks if Google has accepted us into the program, it is probably a good idea for us to get our house in order.

We have a Trac full of suggested Google Summer of Code proposals both current and from years past, but it could use a whole lot of eyeballs and an infusion of fresh ideas:

https://ghc.haskell.org/trac/summer-of-code/report/1

If you have a proposal that you think a student could make a good dent in over the course of a summer, especially one with broad impact on the community, please feel free to submit it to the Trac, or just discuss it here.

If you are a potential student, please feel free to skim the proposals for ideas, or put forth ones of your own.

If you are a potential mentor, please feel free to comment on proposals that interest you, put forth ideas looking for students and express your interest, to help us pair up potential students with potential mentors.

Ultimately, the project proposals that are submitted to Google for the summer of code get written by students, but if we can give a good sense of direction for what the community wants out of the summer, we can improve the quality of proposals, and we can recruit good mentors to work with good students on good projects.

Resources:

  • We have a wiki on https://ghc.haskell.org/trac/summer-of-code/ It is, of course, a Wiki, so if you see something out of order, take a whack at fixing it.

  • We have an active #haskell-gsoc channel on irc.freenode.net that we run throughout the summer. Potential mentors and students alike are welcome.

  • We're also adding a haskell-gsoc mailing list this year. I've created a mailing list through Google Groups: https://groups.google.com/forum/#!forum/haskell-gsoc and we've forwarded gsoc@haskell.org there. We'll continue to post general announcements on the progress of the summer of code to the main Haskell mailing list as usual, but this gives us a shared forum for students and mentors alike to talk and may serve as a better venue for longer term conversations than the #haskell-gsoc channel.

  • Many of our best proposals in years have come from lists of project suggestions that others have blogged about. Many of our best students decided to join the summer of code based on these posts. The Trac isn't the only source of information on interesting projects, and I'd encourage folks to continue posting their ideas.

  • The Google Summer of Code website itself is at https://www.google-melange.com/gsoc/homepage/google/gsoc2015 and has the schedule for the year, etc. You can register on the site today, but you can't yet join the organization as a mentor or apply as a student.

  • And of course, by all means feel free to use this space to help connect projects with mentors and students.

Thank you,

-Edward Kmett

submitted by edwardkmett
[link] [112 comments]
Categories: Incoming News

What are the best real world applications developed with Haskell?

Haskell on Reddit - Thu, 02/19/2015 - 9:30pm

Hi,

I am trying to convince my friend to start developing a toy project on Haskell. This project will need some GUI development, Networking, and AI.

He wants to do the project on Java. His points are: - Haskell will be too slow. - We will never find enough help and libraries for Haskell.

I would like to show him some real life applications written in Haskell. But after few searches on Google, I could not find anything that is usefull.

Could you please give me few real world applications that are developed by using Haskell??

Thanks.

Edit: Fyi, I found following: https://wiki.haskell.org/Haskell_in_industry Almost none of them are related to GUI and I can not download and show them to my friend.

submitted by ThatDrunkGuyInBar
[link] [30 comments]
Categories: Incoming News

build troubles with ghc binary

haskell-cafe - Thu, 02/19/2015 - 9:29pm
(i hope this is not a repost - sent it to haskell-cafe-bounces the first time) new thread because i have the details i should have provided in the first place. development system is centos 6.6 but i suspect something's broken because... i built and installed gmp-4.3.2 only to find that it's being build as a 32-bit library and will only build as 32-bits. which is really weird, because 64-bit system: 2.6.32-504.3.3.el6.x86_64 #1 SMP Wed Dec 17 01:55:02 UTC 2014 x86_64 x86_64 x86_64 GNU/Linux however- no problem- i'll simply download the 32-bit version of the ghc binary, which was built on centos no less, and install that instead of the 64-bit version. so i do that, point configure at my gmp thusly ./configure --prefix=/home/denheyer/local --with-gmp-includes=/home/denheyer/local/include --with-gmp-libraries=/home/denheyer/local/lib and get this checking for path to top of build tree... utils/ghc-pwd/dist-install/build/tmp/ghc-pwd: error while loading shared libraries: libgmp.so.3: cannot op
Categories: Offsite Discussion

Pattern match checking for GADTs

haskell-cafe - Thu, 02/19/2015 - 7:37pm
Friends George Karachalas, Tom Schrijvers, Dimitrios Vytiniotis, and I are working on finally cracking the problem of accurately reporting pattern-match overlap and redundancy warnings, in the presence of GADTs. You know the problem; consider vzip :: Vect n a -> Vect n b -> Vect n (a,b) vzip VN VN = VN vzip (VC x xs) (VC y ys) = VC (x,y) (vzip xs ys) data Vect :: Nat -> * -> * where VN :: Vect Zero a VC :: a -> Vect n a -> Vect (Succ n) a Are there any missing equations in vzip? No! But GHC complains anyway. We have lots of Trac tickets about this; e.g. https://ghc.haskell.org/trac/ghc/ticket/3927. We now have a draft paper (wait a week) and a prototype implementation, that fixes the problem. But we need your help. We'd like to try our prototype on real code, not just toy examples. So, could you send George a pointer to any packages you have, or know of, that * use GADTS (or other fancy type features) and * would benefit from accurate pattern-match overlap/re
Categories: Offsite Discussion