February 2005 - Haskell

Re: [Haskell] Typing in haskell and mathematics
by Cale Gibbard 01 Feb '05

01 Feb '05

I agree, as an undergraduate student of pure mathematics, I have been finding fairly large parts of the discussion about mathematical notation to be somewhat silly and uninformed. (Really it was more the previous thread, but it seems to have been continued here). One thing to keep in mind about mathematical notation is that it is usually not intended to be read by machines, rather it is a human language, albeit a very precise one. Statements like "a < b < c" are perfectly clear to everyone present, and if anyone has a type error in their head when reading that which they can't get past, they are most likely just being stubborn. Another common thing which is done whenever convenient is to treat Cartesian product as associative, and naturally identify the spaces (A x A) x A and A x (A x A), along with perhaps A^3 which might be functions f: {0,1,2} -> A, or might be treated as one of the preceding. In any given context, it should be easy to determine the author or lecturer's intent as to whether these are distinct or the same. Bookkeeping is left as an exercise to the bored reader or to logicians. (With the recent comment that functional programmers are applied logicians, perhaps it is no surprise that they would be upset with such fuzziness in the language!) The notational confusion between f and f(x) tends not to happen beyond the level of highschool, at least not where I am. The former refers to the function f, and the latter refers to a point in its codomain. In fact, I currently am dealing with the opposite problem in trying to learn differential geometry - people and books using just f to refer to a particular point in the codomain of f. All functions are automatically evaluated at a given point of concern. This seems to be common among physicists for some reason (most likely because they'd like to think of the function as a quantity, and are used to quantities having implicit relationships). Another thing to keep in mind is that mathematics is written in what is usually another human language. If I write a proof in English, I can provide enough context that any natural transformations I implicitly apply to things will be made obvious to the reader. The goal is not usually a machine-checkable proof, rather it's to convey enough information that anyone paying attention could produce one. A professor of mine used the term "rigourisable", halfway joking about the process. Basically, enough logical steps are provided so that the ideas are clear, and everyone is completely convinced that they could fill in the details -- mathematicians are usually pretty good at making sure that the details that they're providing for themselves are consistent. The reasons that such bookkeeping details are not generally provided is that for one, if someone is unable to fill some detail in, they are expected to think about it and then ask a question, and two, providing all of the details only serves to obscure the actual reasoning. Getting caught up in explicitly applying natural transformations that people would apply in their head without much thought anyway is a waste of time and creates a lot of junk to have to sift through to find the key ideas. In any case, it is important to keep the audience in mind while writing anything, including symbols. - Cale p.s. There are other good philosophical reasons not to take everything down to the level of formal logic and set theory all the time, stemming from Goedel's result that a formal system for mathematics cannot be proven consistent within itself. If we ever discover our system is broken it will likely have to be replaced by a similar one which corrects the problem. The fuzziness serves as good protection in the case of such an earthquake. It's easier to map slightly fuzzy notions with a given semantic interpretation onto a new system and find the analogues of theorems that you had before than it is to map direct low-level syntactical statements across and be able to say that they mean anything at all similar. On Mon, 31 Jan 2005 13:59:58 +0100, Benjamin Franksen <benjamin.franksen(a)bessy.de> wrote: > On Monday 31 January 2005 04:24, Jeremy Gibbons wrote: > > Despite being a fan of generic programming, I have my doubts about > > this kind of automatic lifting. It works fine in "ordinary > > mathematics", because there is no fear of confusion - one hardly ever > > deals with functions as entities in their own right. > > May I please beg to differ? When I studied math, things were quite > different, at least. I remember whole branches of mathematics > completely dedicated to dealing with "functions as entities in their > own right". One notable example is Functional Analysis, of which I > happen to know a little. And, as far as I remember, we used notation > which reflected this, i.e. nobody wrote 'f(x)' when actually they meant > just 'f', which is the same as '\x -> f x', which in math is usually > written 'x |-> f(x)'. > > > (Witness "sigma > > sin(x) dx", involving a term sin(x) and a dummy variable x, rather > > than the more logical "sigma sin", involving the function.) > > The notations for 'integral' and 'differential quotient' stem from a > time when dealing with functions as entities in their own right was > indeed not yet a common concept in mathematics, i.e. earlier than 1900. > > BTW, 'sigma sin' is not a function. > > Ben > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell >

5 4

RE: [Haskell] space behaviour of lazy recursive lists
by Simon Marlow 01 Feb '05

01 Feb '05

On 30 January 2005 17:09, Ben Rudiak-Gould wrote: > Axel Jantsch wrote: > > >Consider: > > > >>gibs = 1 : 1 : (zipWith f gibs (tail gibs)) > >> where f x y = min (x + y) 10 > > > >[...] how can I force the garbage collector to reclaim the > >memory of the head of the list after I have processed it, since I > will >never ever reference it again? > > There's no entirely satisfactory way to do this. The language standard > doesn't specify caching behavior, so you have to rely on the way that > actual implementations handle caching. > > I think it's safe in practice to assume that a binding inside a > function won't be cached across call boundaries, even if the value of > the binding doesn't depend on the function argument. I.e. you should > be able to solve your problem with > > makeGibs () = gibs where > gibs = 1 : 1 : (zipWith f gibs (tail gibs)) > f x y = min (x + y) 10 > > In principle a compiler could float the definition of gibs outside the > function makeGibs and cache it across calls, but I don't think any > compiler will actually do this, precisely because it makes this trick > stop working. Actually, GHC can garbage collect top-level definitions, and it also floats things out to the top-level precisely because doing so doesn't affect the space behaviour (any more than floating in general, that is). Unfortunately in this case, laziness is the culprit. Each element of the list is a thunk that refers to the previous two elements of the list, which are thunks that refer to the previous two elements... and so on. So even if you drop the front of the list, each element keeps the whole list alive until it is evaluated. Try this: gibs = 1 : 1 : f gibs (tail gibs) where f (x:xs) (y:ys) = z `seq` z : f xs ys where z = min (x + y) 10 main = print (head (drop 1000000 gibs)) Cheers, Simon

1 0

[HLPP 2005] Call for papers
by Frederic Loulergue 01 Feb '05

01 Feb '05

Third International Workshop on HIGH-LEVEL PARALLEL PROGRAMMING AND APPLICATIONS (HLPP 2005) July 4-5, 2005, Warwick University, Coventry, United Kingdom http://hlpp2005.free.fr AIMS AND SCOPE Parallel and distributed systems are now readily available as their price/performance ratio continues to improve. But parallel and distributed programming is still dominated by low-level techniques such as send/receive message passing. Sequential programming has long benefited from high-level programming techniques and tools that have made today's immense range of software economically viable. Two decades of research into high-level parallel and distributed programming have produced methods and tools that improve the price/performance ratio of parallel software, and broaden the range of target applications. Grid systems offer a tremendous computing power. Nevertheless, this power is far from being effectively exploited. In addition to technical problems related to portability and access, grid computing needs new programming paradigms. Research on high level programming for meta and grid computing is particularly relevant. This workshop follows HLPP 2001 & HLPP 2003, and is aimed at: computer science and scientific computing researchers, practitioners, graduate students; high-performance application developers (e.g. in DBMS, data-mining, parallel model checking, virtual reality) TOPICS We welcome submission of original, unpublished papers in English on topics including (but not limited to) the following aspects of parallel, distributed, meta and grid computing: - high-level algorithmic methods for parallel, communication-efficient and external-memory computation - high-level programming models (BSP, CGM, LogP, MPM, etc.) and tools - performance models and performance evaluation - high level resource-aware approaches - algorithmic skeletons and constructive methods - object, functional, logic, constraint programming - applications using high-level languages and tools - teaching experience with high-level tools and methods Accepted papers should be presented at the workshop and will be published in a special issue of an international journal (provided revisions suggested by the referees are made). IMPORTANT DATES 14 March 2005 Full paper due 2 May 2005 Notification 12 June 2005 Camera-ready paper due 4-5 July 2005 Workshop INVITED SPEAKER Prof. Dr. math. Friedhelm Meyer auf der Heide (Univ. of Paderborn, Germany) PROGRAMME COMMITTEE Rob Bisseling (Univ. of Utrecht, The Netherlands) Murray Cole (Univ. of Edinburgh, UK) Alexandros Gerbessiotis (NJIT, USA) Sergei Gorlatch (Univ. of Muenster, Germany) Gaétan Hains (Univ. of Orléans, France) Zhenjiang Hu (Univ. of Tokyo, Japan) Christoph Kessler (Linköpings Universitet, Sweden) Frédéric Loulergue (Univ. Paris Val de Marne, France) Mauricio Marín (Univ. de Magallanes, Chile) Quentin Miller(Somerville College, Oxford, UK) Andrea Pietracaprina (Univ. of Padova, Italy) Geppino Pucci (Univ. of Padova, Italy) Alexander Tiskin (Univ. of Warwick, UK) CHAIRS AND ORGANIZERS Dr. Alexander TISKIN Department of Computer Science University of Warwick Coventry CV4 7AL UNITED KINGDOM Dr. Frédéric LOULERGUE Laboratory of Algorithms, Complexity and Logic (LACL) University of Paris Val de Marne 61, avenue du Général de Gaulle F-94010 CRÉTEIL - FRANCE PAST HLPP WORKSHOPS HLPP 2003 was held in Paris (June 16-18, 2003). Parallel Processing Letters (Volume 13, issue 3) contains 14 revised papers presented at the workshop. HLPP 2001 was held in Orléans (March 26-27, 2001). Parallel Processing Letters (Volume 11,issue 4) contains 8 revised papers presented at the workshop.

1 0