Functional Programming Winter Meeting
25th - 26th March, 2013
The meeting takes place at VANN, in Brastad, Sweden (see map here). As part of the event, we have access to the swimming pool facilities and common areas in the Spa (6 swimming pools with different water temperatures, 3 type of saunas, and gym).
There will be a bus taking participants to VANN and back to Chalmers. More specifically,
- 25th March 7:00: The bus is leaving from the Chalmers copper building (Kopparbunkern). Note that the bus is leaving at 7:00 sharp! It is early. However, there will be coffee and something small to eat waiting for us when the bus arrive. For those travelling by car, you can get coffee from 8:15.
- 26th March 14:00: The bus is leaving from the front door at VANN back to Chalmers.
Due to the meeting takes place near the ICFP deadline, the program contains less scientific talks than usual. Additionally, the meeting contemplates short talks and discussion about VR-proposals. You can take the opportunity to get feedback about your ICFP/VR submissions before the deadlines as well as have the chance to work during the meeting.
25th March - Morning Session (Chair Emil Axelsson)
- 9:40 - 10:15, Michał
Splittable PRNG using crypto hashing
We present a high-quality splittable PRNG for Haskell based on a cryptographic hashing construction. The proposed PRNG gives concrete randomness guarantees, according to cryptographic notion of randomness. Our implementation has performance comparable to StdGen and can serve to replace it.
Push arrays are from Mars, Pull arrays are from Venus
25th March - Morning Session II (Chair Mary Sheeran)
- 11:00 - 11:15, Josef VR-Proposal
- 11:15 - 11:30, Meng VR-Proposal 2
- 11:30 - 11:45, Patrik VR-Proposal 3
Algebra of Parallel Programming? Core Agda? Something else?
- 11:45 - 12:00, Setting up feedback groups for VR-proposals 1 to 4
During these minutes, people will be organized into groups that will provide feedback to the applicant(s) of the VR-proposals after lunch. We are very flexible regarding who would like to be in which group.
- 12:00 - Lunch (No drinks included).
- Breaded Haddock with Danish remoulade (Panerad kolja med dansk remoulad)
- Chicken with roasted paprika créme (Kyckling med rostad paprikacremé)
25th March - Afternoon Session
- 13:00 - 17:00, Working session.
You should take the opportunity to get feedback from your colleagues for the VR-application (recommendable 30-40 minutes per feedback group) and then you have time to work on your ICFP submission.
25th March - Evening Session (Chair Alejandro Russo)
This session mainly has the goal to summarize the constructive feedback received for the different VR-proposals.
- 17:00 - 17:10, Josef VR-Proposal
- 17:10 - 17:20, Meng VR-Proposal 2
- 17:20 - 17:30, Patrik VR-Proposal 3
- 20:00 - Dinner (No drinks included)
- Scallops with couliflower, parseley créme and hazelnuts (Sotad pilgrimsmussla med mjukbakad blomkål, persiljecremé och hasselnöt)
- Sirloin (or Roast beef) with union and potato créme, artichoke and caprice (Kalvrostlock med brynt lök och potatiscremé, kronärtskocka, rädisa och kapris)
- Creme Brulee with gooseberry sorbet and juniper berry crumbs (Cremé Brulé med krusbärsorbet och enbärssmulor)
26th March - Morning Session (Chair John Hughes)
- 9:45 - 10:15, Coffee break
- 10:15 - 10:30, Björn: ICFP 2014
ICFP 2014 Preparations
- 10:30 - 11:00, Pablo
Instruction-based scheduling via a library
Information-flow control (IFC) allows untrusted code to manipulate sensitive data while preserving confidentility. Although promising, this technology suffers from the presence of covert channels. It has been recently demonstrated that LIO, a concurrent IFC system, is vulnerable to cache-based attacks affecting the timing behavior of threads which is then observable within the system. To avoid such leaks, instruction-based scheduling, where schedulers assign instruction-budgets to threads rather than time slots, prove to be robusts against these attacks. Rather than modifying the runtime system, this work shows how to provide instruction-based scheduling via a library. To achieve that, we leverage the notion of resumptions as a model of interleaved computations. We extend the notion of resumptions to deal with local state and exceptions, both features present in LIO. To amend for performance degradation, our library supplies primitives to securely control de granularity of atomic actions. The library suffers from leaks due to the non-termination of programs. Nevertheless, this channel can only be exploited by brute-force attacks as it occurs in most of the state-of-the-art IFC tools.
- 11:00 - 11:30, Jonas Duregård
A Monad for Shrinking Test Cases & Generic Shrinking to Patterns
I discuss ongoing work on a simple but elegant solution for defining shrinking functions on randomly generated test data. I also present a really cool application of the shrinking monad: a datatype generic shrinking function that produces Haskell patterns as counter examples instead of just values.
- 11:30 - 12:00, Nikita Frolov
Partial Scheduling of Recursive Programs
The phase ordering problem concerns loop transformations too. One of common solutions for this problem is to merge conflicting transformations into a single phase. The polyhedral model allows for composition of loop nest transformations by representing them as affine transformations of convex integer sets. While the polyhedral model allows for separation of data dependencies and computation order, it does not provide a way to separate computation order and architectural constraints. We show how the latter can be accomplished if the notions of locality are encoded with combinators that compose recursive combinators instead of transformations of nested loops. The locality combinators impose a partial schedule on data structure traversals and serve as annotations for region allocators.
- Jean-Philippe Bernardy (kindly gave the talk while waiting for the bus)
Efficient Parallel and Incremental Parsing of Practical Context-Free Languages
Valiant (74) has reduced the problem of parsing to that of doing matrix multiplications, yielding subcubic complexity for the context-free recognition problem. We show that, under conditions which widely occur in practice, the multiplications performed by the algorithm involve an overwhelming majority of empty matrices. This means that, under the above assumptions, and using a sparse matrix representation, the complexity of parsing using Valiant’s algorithm is O(n log3 n). Furthermore, because the algorithm is an instance of the divide and conquer skeleton, we obtain a polylogarithmic complexity for the problem of parallel and incremental parsing of practical context-free languages.
- 12:00 - Lunch (No drinks included)
- Steamed cod with eggsause (Ångad rimmad torsk med äggsås)
- Loin with glazed brusselsprouts (Helstekt kotlettrad med glaserad brysselkål)