- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] Program optimisation
by David Roundy 21 Apr '07

21 Apr '07

On Fri, Apr 20, 2007 at 08:33:41PM +0100, Andrew Coppin wrote: > >Indeed, unboxed arrays are much nicer, but the whole Array batch of the > >standard library is pretty useless, in my experience. You can roll your > >own relatively easily using ForeignPtr, similar to Data.ByteString, but > >that's a bit of a pain. > > There is no *way* I'm playing with C. The entire point of Haskell is to > allow mankind to eradicate C forever. :-) ForeignPtr doesn't have anything to do with C, it's just the data structure you need to use if you want to write your own unboxed array. > I was more interested in seeing people's comments about the program > changes. For example, why would an in-place update be slower than lots > of dynamically-allocated lists? That's totally counterintuitive. Also, > is there any way in hell I can make the program stricter without > mutilating the entire thing to use unboxed arrays? I couldn't figure out > a way to do this. (Would be nice if there was a compiler switch to just > turn off all laziness - but as far as I can tell, there isn't.) The in-place update (without boxing) still dynamically allocates thunks, which are similar in cost to cons cells (for some definition of similar). Unboxed arrays are exactly what you want--except that the UArray type is limited, which is why I recommended rolling your own. Hopefully the PArr package will help reduce the pain of using arrays. In any case, in my opinion Haskell desperately needs more strict data types, as strict types can go a long way towards eliminating all sorts of pain. I remember once going through all sorts of pain trying to avoid stack overflows when using Data.Map to compute a histogram, which all would have been avoided if there were a strict version of Data.Map (or even just strict functions on the lazy Data.Map). I don't think eliminating all laziness is a good idea, but (optional) strict datatypes most certainly are, as they can go a very long ways towards eliminating memory leaks. -- David Roundy Department of Physics Oregon State University

3 6

Why Mathematical Soundness Matters.
by Vivian McPhail 20 Apr '07

20 Apr '07

Hi All, This is in regard to previous posts about mathematical preludes. > class Set a > > class (Set s) => SemiGroup s o where > semigroup_op :: o -> (s,s) -> s > -- closure > -- associative > > class (SemiGroup s o) => Monoid s o where > identity :: o -> s > > class (Monoid s o) => Group s o where > inverse :: o -> s -> s > > class Optimisable a where > cost :: Set b => a -> b First, consider a semigroup, which is a set with an associative operation. Into this structure falls Matrices with multiplication. There is scope for optimisation of a series of multiplications. Inductively for each m1 * m2 * m3 compare the cost of m1 * m2 versus m2 * m3 which can be simply obtained from the size of the index of the matrix. Thus expressions like (14,3) x (3,15) x (15,2) can be computed as (14,3) x ((3,15) x (15,2)) and not in a more expensive way. Furthermore, if we tag identities with a phantom type, we can eliminate needless operations like 3 + 0. Not as much optimisation can be achieved with inverses (3 + -3) because it might be just as expensive to calculate that something is an inverse as to do actual calculation. So how can this optimisation be performed? Well this is a question that I put forward to you, Gentle Reader. Static: It seems to me that expressions the types of which are known at compile-time can be optimised by using type-level programming in combination with compiler rewrite rules, e.g. if we have a type class SizeLarger then the expression > semigroup_op (semigroup_op m1 m2) m3 can be rewritten as > semigroup_op m1 (semigroup_op m2 m3) depending upon the SizeLarger types of the various (semigroup_op _ _) function calls. Another method is to manipulate the expressions as ASTs and convert to the concrete using TH. But what about dynamic data? Dynamic: These are terms whose types are not known until run-time (such as would happen when loading an arbitrary matrix from a file). In this case we can't use compiler term-rewriting or TH, but what options are there? Depending upon the speed/complexity of type-checking versus computation would it not be feasible to use run-time type checking (a polymorphic Dynamic type) to achieve this optimisation? Yes there is a lot to said in favour of static type-checking, but there are cases in which it is not feasible, witness type-level bounds checking of run-time loaded matrices of unknown shape. In a program that used run-time typechecking (yes there would be a computational overhead) the dynamic stuff would be isolated from the 'trusted' statically checked program and values could only be injected through trusted entry points (e.g. get4SquareDoubleMatrix :: Dynamic -> IO (Array ((D4 $ Sz),(D4 $ Sz)) Double). In any case, writing 'simple' arithmetic expressions would become more cumbersome because of the overhead of annotating types and possibly moving between ASTs and the concrete. But if we a had collection of mathematically sound classes like SemiGroup, Monoid, Group, Field, etc... then these optimisations could be built into the compiler and we could sugar the programmer-side just as it has been for Monads. In conclusion, I put this forward as a reason for Mathematically Meaningful Numeric Classes and in obiter I am putting forward support for polymorphic Dynamic types (run-time typechecking). Cheers, Vivian

1 0

Re: how would Albus Dumbledore sell Haskell
by Greg Meredith 20 Apr '07

20 Apr '07

Simon, Regarding Justin Bailey's idea of a calculator -- here's a twist. There is some sample Haskell code of Conway's account of numbers as games floating around the internet (http://www.dcs.ed.ac.uk/home/pgh/conway.html, http://www.dcs.ed.ac.uk/home/pgh/Conway.lhs) i can't vouch for the code as i have not read it in anger. However, i've always thought it would be fun to do the standard calculator example, but with Conway games on the back end for doing the arithemetic. Some of the attractions: - you could have another set of buttons for displaying the games respresentation of the numbers - you could really emphasize the polymorphism of the basic operations - you could emphasize the use of laziness for calculations involving infinitary entities - you could explain Conway games (which are an intellectual treat for those who never seen them and just get better and better the more you return to them) Best wishes, --greg -- L.G. Meredith Managing Partner Biosimilarity LLC 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 http://biosimilarity.blogspot.com

1 0

fftw bindings
by Fawzi Mohamed 20 Apr '07

20 Apr '07

Hi everybody, I was wondering if someone had fftw bindings for haskell, or if I should roll my own. I did a small search but found nothing. Fawzi

8 11

Writing guards shorthand
by Joel Reymont 20 Apr '07

20 Apr '07

Support I want to infer the type given an Op that looks like this (incomplete): data Op = Minus | Plus | Mul | LT | GT Is there a shorthand way of bunching Minus, Plus and Mul in a function guard since they all result in TyNum whereas the rest in TyBool? I really don't want several function clauses and neither do I want separate guards for every constructor. Thanks, Joel -- http://wagerlabs.com/

7 11

Vacancy for a PhD student
by Johan Jeuring 20 Apr '07

20 Apr '07

(Knowledge of Haskell is a big plus; implementation of most of the tools will be done in Haskell.) Vacancy: PhD student in the Strategy Feedback project 1+3 years, Open University the Netherlands, location: Heerlen (preference). The project: In many subjects students have to acquire procedural skills. Problems in mathematics are often solved using a standard procedure, such as for example solving a system of linear equations by subtracting equations from top to bottom, and then substituting variables from bottom to top. Problems in computer science, physics, chemistry, electrotechnics, and other subjects, often require procedural skills as well. Furthermore, procedural skills appear at any educational level. E-learning systems offer excellent possibilities for practicing procedural skills. The first explanations and motivation for a procedure that solves a particular kind of problems are probably best taught in a class room, or studied in a book, but the subsequent practice can often be done behind a computer. There exist many e-learning systems or intelligent tutoring systems that support practicing procedural skills. The tools vary widely in breadth, depth, user-interface, etc, but, unfortunately, almost all of them lack sophisticated techniques for providing immediate feedback. If feedback mechanisms are present, they are hard coded in the tools, often even with the exercises. This situation hampers the usage of e-learning systems for practicing procedural skills. This project aims to investigate techniques for providing flexible and immediate feedback in tools that support practicing procedural skills. We want to use advanced techniques from computer science, taken from fields such as term rewriting, strategies, error-correcting parsers, and generic programming to provide feedback at each intermediate step from the start towards the solution of an exercise. We want to further develop some of these techniques, and apply and experiment with them in the domain of e-learning systems. Our goal is to obtain e-learning systems that give immediate and useful feedback. We will cooperate on this project with the Software Technology group from Utrecht University. Requirements: University degree in Computer Science. Good knowledge of functional programming, and several advanced computer science techniques. Knowledge of parsing, rewriting, strategies, generic programming, etc. will be useful. More information about the project can be found on http://ideas.cs.uu.nl/wiki/index.php/IDEAS:StrategicFeedback or contact Johan Jeuring (johanj(a)cs.uu.nl, +31 6 40010053). To apply: send a letter and your curriculum vitae before May 5, 2007 to: Open Universiteit Nederland, afdeling Personele ondersteuning, Postbus 2960, 6401 DL Heerlen. U kunt ook or an e-mail to: martin.vanloo(a)ou.nl Mention vacancynr FAC/INF/07024 In both cases, please cc Johan Jeuring (johanj(a)cs.uu.nl)

1 0

Morphing ASTs and scrapping boilerplate code
by Joel Reymont 19 Apr '07

19 Apr '07

Folks, I'm transforming ASTs as part of my compiler from one language into another. The source AST is a list of statements whereas the target AST is a "class definition". type Object a = State Obj a data Obj = Object { objSym :: Integer -- starting # for gensym , objVars :: M.Map String VarDecl , objProps :: M.Map String PropDecl , objMeths :: M.Map String MethodDecl } deriving (Show, Eq) I'm using a state monad and the transformations are supposed to update the state (object) as needed to add variables, methods, etc. class Morpher a b | a -> b where morph :: a -> Object b I have a lot of boilerplate code like this and wonder how I can scrape it. instance Morpher Type C.Type where morph TyInt = return C.TyInt morph TyFloat = return C.TyFloat morph TyStr = return C.TyStr morph TyBool = return C.TyBool morph TyColor = return C.TyColor morph TyStyle = return C.TyStyle morph (TyList ty) = liftM C.TyList (morph ty) morph (TyArray ty) = liftM C.TyArray (morph ty) morph (TySeries ty) = liftM C.TySeries (morph ty) morph (TyInput ty) = liftM C.TyProp (morph ty) morph (TyRef ty) = liftM C.TyRef (morph ty) morph TyUnit = return C.TyUnit morph TyPrintDest = return C.TyPrintDest Notice that I'm calling a constructor of the same name in a different module ... unless it's an exception. instance Morpher BackRef C.Expr where morph Now = C.Int 0 morph (BarsBack e) = morph e instance Morpher DataRef C.Expr where morph (DS x) = C.Int x How can I reduce the boilerplate here? Thanks, Joel -- http://wagerlabs.com/

2 2

First order Haskell without Data
by Neil Mitchell 19 Apr '07

19 Apr '07

Hi, I've been wondering what is essential to Haskell and what isn't. Not from a point of view of what could be removed from the language, but what could be removed from a Core language. Given the features of higher-order, laziness and data types: Laziness can be converted to higher-order functions Data types can be converted to higher-order functions Higher-order functions can be converted to Data So as far as I can see it we have left: {data-types only} {higher-order functions only} But we don't have laziness only, so my question is if it is possible to represent all of Haskell in a first-order language without data types, but with laziness. If its possible to do so in a strict first-order language without data types, then I'd also be interested. Are any of these known results? Thanks Neil References: * data types -> higher order is in "Efficient Interpretation by Transforming Data Types and Patterns to Functions" http://www.cs.nott.ac.uk/~nhn/TFP2006/Papers/03-JansenKoopmanPlasmeijer-Eff… * laziness -> functions, functions -> data is in "Definitional Interpreters for Higher-Order Programming Languages" http://www.brics.dk/~hosc/local/HOSC-11-4-pp363-397.pdf

4 4

Parallel executing of actions
by Mitar 19 Apr '07

19 Apr '07

Hi! Is there a parallel version of mapM_? Like it is for map (parMap)? I would like to execute actions in parallel as the computation of necessary data for actions is quite computational heavy. But it does not matter in which order those actions are executed. (I am rendering pixels with OpenGL and it does not matter in which order I draw them, but it matters that for one pixel it takes some time to calculate its color.) The example would be: main :: IO () main = do -- the order of printed characters is not important -- instead of putStrLn there will be a computationally big function -- so it would be great if those computations would be done in parallel -- and results printed out as they come mapM_ rwhnf (putStrLn) ["a","b","c","d"] Is this possible? Without unsafe functions? And without changing the semantics of the program. Mitar

9 13

RE: [Haskell] haskell question
by Simon Peyton-Jones 19 Apr '07

19 Apr '07

[Redirecting to Haskell Cafe] Hi Greg I think it's very likely that you *can* do what you want. I have not taken long enough to understand just what you are trying to do, but I do know why your program is failing, and I think you'll agree it *should* fail. Look at these lines (slightly simplified) class CoreAgentSyntax x where offer :: (CoreProcessSyntax p) => [n] -> (p a x) -> x data MinimalAgentSyntax nn pp = Concretion [nn] pp instance CoreAgentSyntax (MinimalAgentSyntax nn pp) where offer = Concretion The class decl says that every instance of 'offer' must have type forall p, forall n, forall a. (CoreProcessSyntax p) => [n] -> p a x -> x where x is the instance type. Not the "forall n"! Even once x is fixed, we must have a function that is polymorphic in n,p,a But in your instance declaration, offer = Concretion has the type [nn] -> pp -> MinimalAgentSyntax nn pp No for-alls, because the whole instance decl binds the 'nn'. Hence it's just not polymorphic enough. I'm not sure how to fix your problem. Perhaps you need another argument for CoreAgentSyntax? class CoreAgentSyntax n x where offer :: (CoreProcessSyntax p) => [n] -> (p a x) -> x instance CoreAgentSyntax nn (MinimalAgentSyntax nn pp) where offer = Concretion now you are in better shape. There's another problem because you use 'p' with kind * in some places and (*->*->*) in others, but thats a separate issue. Oleg is good at this kind of stuff. Simon From: haskell-bounces(a)haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Greg Meredith Sent: 18 April 2007 14:53 To: haskell(a)haskell.org Subject: [Haskell] haskell question Haskellians, In the attached file i have implemented the bare bones core of the syntax -- pre structural equivalence -- of Milner's presentation of \pi via abstractions and concretions. (There's a minor twist in that the notion of location affords more structure than in Milner's original presentation which i have added to support an ultimate probabilistic interpretation.) The file compiles with ghc as is. If you uncomment the last section, however, you see that to close the loop on the constraints for the agent syntax we hit a typing error. i think this is a hard constraint in Haskell that prevents this level of generality in the specification, but maybe you can see a way around it. i'm certainly no Haskell expert. Best wishes, --greg P.S. The reason for this level of generality is that with it you can close the loop and form a mutual recursion between the types for the syntax of processes and the type of names -- without having that choice predesigned into the structure of processes (or names). i can do this trick in OCaml with recursive modules, but it's definitely not pretty. i was hoping Haskell could make it pretty. -- L.G. Meredith Managing Partner Biosimilarity LLC 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 http://biosimilarity.blogspot.com

1 0