Re: [Haskell] Image manipulation
Jerzy Karczmarczuk: Dan Piponi adds to a short exchange: jerzy.karczmarczuk: [iso-8859-1] Bj�rn Wikstr�m writes: Hi! I have lots and lots of images (jpegs) that I would like to manipulate and shrink (in size). They are around 5 Mb big, so I thought this would be a good Haskell project since it's a lazy evaluating language. ... I must say that I don't see much use of laziness here. Laziness plays a big role in real world image processing. Typically, in applications like Apple's Shake, you build a dataflow representation of the image processing operations you wish to perform, and the final result is computed lazily so as to reduce the amount of computation. For example, if you blur an image, and then zoom in on the top left corner, then only the top left corner will be loaded up from the original image (assuming your image file format supports tiled access). You still work on tiles or scan-lines, rather than individual pixels, so the laziness has a 'coarse' granularity. But I'm not sure if this is what the original poster was talking about. I am neither... Still, Dan, I think that there is quite a difference between incremental processing of signals, and images, etc., and the *lazy evaluation* of them. Of course, a stream is consumed as economically as it can, but not less. If you filter an image (shrinking, so some low-pass MUST be done), a pixel must be loaded with its neighbourhood, which means *some* scan lines. With a JPEG this means that a 8x8 block should be loaded also with its vicinity. But would you suggest that individual pixel processors should be lazy? It would be useless, and probably resulting in some penalties. So, the laziness of Haskell for me here is less than useful. Nw, the lazy *generation* of streams is another story... Generating music (low level, i.e. sound patterns) through lazy algorithms is quite interesting. Wait, Jerzy. Haskell implementations do not have to be lazy as long as they preserve the more abstract semantics. Optimistic evaluation has been considered, for instance by Robert Ennals. My former PhD student Karl-Filip Faxen studied optimizations based on cheap eagerness, simple cases where it is easy to see that it pays off to generate code that is not totally lazy. One case is if we know that a computation always terminates and takes little time, then it can typically pay off to perform that computation optimistically even in cases where a lazy evaluation strategy might have avoided it. For image processing, if we know that individual pixel computations terminate then the compiler is free to carry (a finite number of) them out in any order, even if some of them turn out not to be needed. So tiled computation schemes are certainly possible, even if parts of some tiles fall outside the final image. Another thing is that current Haskell compiler don't work like this. But Haskell itself does not prevent it. A number of years back I worked on something called the data field model, a kind of generalized array construct intended for high-level data parallel programming. We also defined and implemented a dialect of Haskell called Data Field Haskell which extended Haskell with one particular instance of data fields. Data Field Haskell had a function to force the evaluation of all elements in a data field at once. The purpose of this function was exactly to make possible computations like the above, where it pays off to evaluate data fields, or parts of them, in a non-lazy fashion. I am quite confident that it would be easy to express the image processing mentioned above in Data Field Haskell. Alas, we were never able to do anything else than a proof-of-concept implementation. If anyone is interested to see what we did, there was a paper in the Haskell Workshop 2000. Björn Lisper ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] Is Excel a FP language?
I just had a thought... Why doesn't somebody implement a spreadsheet where Haskell is the formula language? 8-) http://sigfpe.blogspot.com/2006/11/from-l-theorem-to-spreadsheet.html may interest. ...ok, and now my head hurts... (Haskell seems to do that lots. I'm not sure why.) Well, check out http://www.mrtc.mdh.se/index.php?choice=projectsid=0041 This might ease the headache a little. It is basically the result of a MSc thesis project that a student did for me a couple of years ago. Björn Lisper PS. Also check out http://www.cs.kent.ac.uk/projects/vital/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Generalizing three programs
Queuing theory is a very large and mature area of research, with many important applications in industry. It is not a coincidence that a certain telephone company named a functional programming language after Erlang, the founder of queuing theory. Erlang actually stands for Ericsson Language. I think the alternative interpretation is intentional, though. Björn Lisper ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is Excel the most used -- and fucntional -- programming lanuage on Earth?
Dan Piponi: On 1/30/07, Lennart Augustsson [EMAIL PROTECTED] wrote: Excel is what I like to call a 0:th order functional language, i.e., you can't even define functions, just values. :) Every cell with an expression in Excel is a function. The problem is that the domains and codomains of these functions don't usually contain functions. Maybe that makes it a first order functional language. Or maybe not. Yes, every cell in isolation contains an expression possibly with free variables, and so can be seen as a function in those variables. But these variables are not unbound since they are defined elsewhere in the spreadsheet. Thus, the sheet is rather a system of equations defining values, not functions. I think 0:th order is a good term :-) But...suppose we had a spreadsheet a little like Haskell where each cell has a static type, and the values can be Haskell functions. What interesting things could we do with it that we couldn't do with Excel? I had a MSc student doing something in this direction some years ago. He made a Haskell interface which was intended to work like a spreadsheet. In this interface, every declaration has a value window (if the entity declared has a showable type) and a declaration window. A designated button triggers a recompilation, and thus also a recalculation of all declared values - this, I think, captures the essence of spreadsheets which is to be able to make changes and quickly see the results. In order to support the kind of array omputations often done in spreadsheets, an extended array module was defined which declares a number of array functions and other conveniences. See http://www.mrtc.mdh.se/index.php?choice=projectsid=0041. Björn Lisper ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Simple matrix
Udo Stenzel: Bjorn Lisper wrote: - your definition of fromInteger will behave strangely with the elementwise extended operations, like (+). 1 + [[1,2],[3,4]] will become [[2,2],[3,5]] rather than [[2,3],[4,5]]. Array languages supporting this kind of overloading invariably have the second form of semantics. Don't call an array a matrix. If is named matrix, it should have matrix multiplication, addition, and they should obey the expected laws. But you still have the problem with the overloading of constants in your proposal. If you write 17 + a, where a is a matrix, what do people in general expect it to be? Björn Lisper ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Simple matrix
I wrote: Here is one way to do it. First, you have to interpret operations on matrices as being elementwise applied. E.g, (*) is interpreted as zipWith (zipWith (*)) rather than matrix multiply, and similar for (+) etc. You then obtain a lazy semantics for the operations, where the extent of the resulting matrix is the intersection of the extents of the argument matrices. Second, you lift constants into infinite matrices containing the constant, that is: fromInteger n = repeat (repeat n). Now your examples will work as intended. Ah, should of course be fromInteger n = repeat (repeat (fromInteger n)). Björn Lisper ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Simple matrix
Udo Stenzel: Bjorn Lisper wrote: Here is one way to do it. First, you have to interpret operations on matrices as being elementwise applied. E.g, (*) is interpreted as zipWith (zipWith (*)) rather than matrix multiply What's this, the principle of greatest surprise at work? Nonono, (*) should be matrix multiplication, fromInteger x should be (x * I) and I should be the identity matrix. Now all we need is an infinitely large I, and that gives: instance Num a = Num [[a]] where (+) = zipWith (zipWith (+)) (-) = zipWith (zipWith (-)) negate = map (map negate) fromInteger x = fix (((x : repeat 0) :) . map (0:)) m * n = [ [ sum $ zipWith (*) v w | w - transpose n ] | v - m ] There are pros and cons, of course. Using (*) for matrix multiply is well-established in linear algebra. But: - it breaks the symmetry. This particular operator is then overloaded in a different way than all the others, and - your definition of fromInteger will behave strangely with the elementwise extended operations, like (+). 1 + [[1,2],[3,4]] will become [[2,2],[3,5]] rather than [[2,3],[4,5]]. Array languages supporting this kind of overloading invariably have the second form of semantics. Björn Lisper ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Simple matrix
Here is one way to do it. First, you have to interpret operations on matrices as being elementwise applied. E.g, (*) is interpreted as zipWith (zipWith (*)) rather than matrix multiply, and similar for (+) etc. You then obtain a lazy semantics for the operations, where the extent of the resulting matrix is the intersection of the extents of the argument matrices. Second, you lift constants into infinite matrices containing the constant, that is: fromInteger n = repeat (repeat n). Now your examples will work as intended. Björn Lisper Atila Romero: Good point. And there is another problem: one could expect 10 * [[1,2],[3,4]] to be equal to [[10,20],[30,40]] and in this case 10 should be equal to [[10,0],[0,10]], instead of [[10,10],[10,10]] or [[10]]. I dont see how to fix this. Could be better to forget about fromInteger... Atila Jared Updike wrote: fromInteger x = [[fromInteger x]] Wouldn't you want the expression [[1,0],[0,2]] + 10 to yield [[11,10],[10,12]] instead of [[11]] ? I guess you would need some complicated machinery so this is one thing you have to ignore to keep your otherwise nifty instance nice and simple. Jared. ___ Novidade no Yahoo! Mail: receba alertas de novas mensagens no seu celular. Registre seu aparelho agora! http://br.mobile.yahoo.com/mailalertas/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The values of infinite lists
Are the values of infinite lists _|_ (bottom)? No. _|_ represents total lack of information about the result, whereas in a lazy language like Haskell an infinite list contains a lot of information: you can observe arbitrary parts of such a list, access them, and compute with them. In section 1.3, the Haskell 98 report said as follows: Errors in Haskell are semantically equivalent to _|_. Technically, they are not distinguishable from nontermination, so the language includes no mechanism for detecting or acting upon errors. The formulation in the Haskell report is sloppy to say the least, and clearly misleading as witnessed by your mail. Nontermination is not the precisely the same as _|_. Only certain kinds of nontermination can be modeled by _|_ in a non-strict language. I think one should consider reformulating the paragraph above in future versions of the Haskell report. Therefore, the value of the following infinity is _|_. Right? data Nat = Zero | Succ Nat infinity = Succ infinity No. Consider the following function: f Zero = 0 f (Succ _) = 17 We then have f infinity = f (Succ infinity) = 17, whereas f _|_ = _|_. Thus, f distinguishes infinity and _|_, so they can not be the same. What about infinite lists? For example, is the value of [1 ..] also _|_? No, see above. Björn Lisper ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The values of infinite lists
Deokhwan Kim: Bjorn Lisper wrote: precisely the same as _|_. Only certain kinds of nontermination can be modeled by _|_ in a non-strict language. What kinds of nontermination are modeled by _|_ in Haskell? Nonterminating computations that never return anything. For instance, inf = inf Björn Lisper ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Compilation of big, computed tables
Chris Kuklewicz: Stefan Karrmann wrote: Dear all, can ghc compile huge tables into efficient code if they are constant at compile time? Two examples may clearify the question: big1 :: UArray Int Char big1 = array (0,1000) $! map (\i - (i,toEnum i)) [0..1000] big2 = sum [0..1]::Int -- == 50005000 == n*(n+1)/2 where n = 1 GHC does not compute such values are compile time because *) The computation may not finish in reasonable time (infinite/not halting) *) The computation may generate a run-time error and crash the compilation (divide by zero, pattern march failure, etc.) *) Haskell is supposed to be lazy, things are computed when needed, not before Does this mean that GHC does not evaluate constant subexpressions at compile-time? Or does it evaluate only some subclass of surely terminating and non-erroneous subexpressions at compile-time? Constant subexpression evaluation is a common compiler optimization technique, so I would be a bit surprised if GHC does not do it. Björn LIsper ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] Numerical methods in Haskell
I finally got some time to answer Simon's posting: Simon P-J: | Between google searching and looking through the activity | report, I take it that no one has really developed serious | libraries for matrix manipulations, diff eqs, etc. | | Are there any practical reasons for this or is it just a | matter of the haskell community being small and there not | being many people interested in something so specialized? The latter I think, but it's just the sort of thing that a functional language should be good at. Two other difficulties (a) It's hard to compete with existing libraries. The obvious thing is not to compete; instead, just call them. But somehow that doesn't seem to be as motivating. Perhaps some bindings exist though? Hard to compete, yes. But on the other hand, the rewards can be high. Numerical library code (especially matrix libraries) tends to be highly optimized for the hardware architecture at hand. As a consequence a small change in, say, the cache architecture, might require a thorough rewrite of the library code to regain high utilisation of the hardware. This is since languages like Fortran and C force you to code so close to the hardware. A high-level language, with good optimizing compilation, would make also library code more portable across hardware architectures. N.b. these optimizations are non-trivial to say the least. (b) A concern about efficiency, because numerical computation is typically an area where people really care about how many instructions you take. It's a legitimate concern, but I don't think that it'll turn out to be justified. With unboxed arrays, and/or calling external libraries for the inner loops -- and the potential for aggressive fusion and/or parallelism, there is plenty of upward potential. I also want to work on nested data parallelism (a la NESL, and NEPAL) which fits right in here. The number of instructions is only one side of the coin. For high-performance computing, memory issues are at least as important: both the amount of memory used (e.g., will the computation fit into memory at all), and how the memory hierarchy is utilized (caches, TLB:s, virtual memory, ...). This is a really sweet spot of functional languages, and laziness adds to it. On the other hand, the increased abstraction of functional languages gives an optimizing compiler larger freedom to reorder computations and choose memory layouts of data structures like matrices. This is potentially very useful, since optimizing for memory hierarchy utilization typically involves both data layout and order of memory accesses. However, to achieve a good result, the compiler must be able to predict a great deal of the computing and the memory usage. For instance, dynamic memory handling of numeric data structures will surely kill any serious attempt to predict the cache behavior. To achieve good optimizing compilation, we need either very good program analyses, or a library of recursion patterns or templates for which the compiler knows how to allocate memory statically and order the computations well, or possibly both. Some encouraging examples: Sven-Bodo Scholz has achieved very good performance for the restricted functional matrix language SAC, using optimizations for cache. My former student Peter Drakenberg invented a restricted functional matrix language, with analyses to infer matrix sizes statically, and sharing analysis, to find opportunities to allocate memory statically and update in-place. He also got some good experimental figures. This leads me to believe that compilers in more general languages could do something similar, by recognizing certain patterns or through advanced program analyses. However, both these languages are strict, and I am not sure at all how to do this in a lazy language. In any case, this is nontrivial compiler work and considerable research efforts would be needed. Unfortunately, I don't see how to fund such research, since the high-performance computing community largely seems to have given up on functional languages since the demise of the data-flow languages. I'd love to see a little community of matrix manipulators spinning up. Yes. There might me a niche for high-level numerical coding, somehwere where MATLAB is today. MATLAB isn't exactly blazingly fast, still very widespread. On the other hand, MATLAB is already in that niche. The question to answer is what advantages a functional language like Haskell could offer in this niche. We need to come up with these answers, and then convince enough people outside our own community. Björn Lisper ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Numerical methods in Haskell
David Roundy: On Mon, Feb 20, 2006 at 11:47:49AM +0100, Bjorn Lisper wrote: (a) It's hard to compete with existing libraries. The obvious thing is not to compete; instead, just call them. But somehow that doesn't seem to be as motivating. Perhaps some bindings exist though? Hard to compete, yes. But on the other hand, the rewards can be high. Numerical library code (especially matrix libraries) tends to be highly optimized for the hardware architecture at hand. As a consequence a small change in, say, the cache architecture, might require a thorough rewrite of the library code to regain high utilisation of the hardware. This is since languages like Fortran and C force you to code so close to the hardware. A high-level language, with good optimizing compilation, would make also library code more portable across hardware architectures. N.b. these optimizations are non-trivial to say the least. The only particularly relevant numerical libraries today (atlas and fftw) already do far better optimization than any compiler is going to acheive, and in the case of fftw can respond to changes in memory configuration at runtime. In both cases they're written in ANSI C (although the C code for fftw is written by an OCaml program... or at least some dialect of ML). In order to take advantage of cache behavior properly, it's necesary to allow adjustments in the actual algorithm used, which isn't something that a clever compiler is likely to accomplish. That's a valid point. You may want to change, e.g., the size of blocks in a block-oriented matrix algorithm to match the cache. This will, in general, require the use of algebraic laws like associativity and commutativity, which are not valid for floating-point arithmetics and thus can change the numerical behaviour, so a compiler shouldn't fiddle around with them unless under strict control of the programmer. Interestingly, the language invented by my aforementioned former PhD student contains a nondeterministic matrix decomposition primitive, which allows the partitioning of a matrix into a fixed number of blocks, but where block sizes can vary. This is exactly to let the programmer give an optimizing compiler this degree of freedom when deemed safe. Alas, he never got around to any serious experiments with this feature. Björn Lisper ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] First steps in Haskell
Simon P-J: Daniel is right, by definition. He is a new user. He had difficulty. That much is incontrovertible. While he may seem unusual, perhaps he is only unusual in that he's told us about his experience rather than trying Perl instead. For which, much thanks, Daniel! Actually, I have sometimes wished that the various interactive Haskell interfaces had the possibility to enter also declarations interactively, as Daniel originally asked for. Lisp interpreters often support this to some extent, so it is not out of line for a newcomer to expect it also for Haskell. I often use hugs as a calculator, and sometimes it would be very convenient to be able to make one or a few short declarations while making some interactive calculations. It can be quite tedious to create and edit a source code file on the side and then load it, when all you want is a short declaration or two. Would it be that complex to have an interactive interface enter a declarations mode when it sees a declaration coming, and then let it create, compile and load a temporary module when the declaration is finished? Björn Lisper ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] First steps in Haskell
Simon: Me: | Actually, I have sometimes wished that the various interactive Haskell | interfaces had the possibility to enter also declarations interactively GHCi does. Ah, I see! Does it open a let-environment with a local definition? ghci let f x = hello ghci f True True Hmm, an interesting semantics for f given the declaration :-) But there's no editor -- it's strictly a one-line definition Which is useful enough in many situations. I'll try it out... Björn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] why don't we have const Ptrs?
Hi, Annotated type systems have been around for some time in static program analysis. I think this is what you want. For instance, you can design such a system to record possible side effects from a function call, as annotations on the type of the function. See the book Principles of Program Analysis, http://www2.imm.dtu.dk/~riis/PPA/ppa.html. Björn Lisper David Roundy: Hello all, I was thinking this morning as I lay on the floor (where I sleep) about static typechecking, and how much more wonderful Haskell is than any other language, when it occurred to me that when working with pointers, Haskell actually has *less* static typechecking than C or C++. It was a very disturbing thought, so much so that I was almost compelled to arise early to place this question before this learned audience. Why is it that in C++ I can write void strcpy(char *dest, const char *src); but in Haskell I must import this function as foreign import ccall unsafe static string.h strcpy strcpy :: Ptr CChar - Ptr CChar - IO () and lose that wonderful information that the function doesn't modify the contents of its second argument? One could pretty easily create a ConstPtr type which one could peek into, but not poke to, but then you'd have to explicitely convert a Ptr into a ConstPtr when passing it as an argument. That feels a bit silly. One could get around this by introducing a class to get around this class ReadablePtr p where peek :: p a - IO a peekOff ... and then make both Ptr and ConstPtr instances of this class, but this still seems like a very hackish solution. Moreover, I'd like to be able to have const objects quite apart from Ptrs, such as a const Handle, which I can read from, but cannot write to, or a const IORef--and we wouldn't want to leave out const ForeignPtrs. Of course, even reading affects a Handle's internal state, so one would need to be explicit about what const indicates. But it seems to me that in the IO world there are a whole slew of things that refer to other things which could all be grouped together. And a const attribute ought to be derived, so that if I create a data type data FooPtr = FooPtr String (Ptr Foo) one should ideally be able to automatically understand that a const FooPtr holds a const (Ptr Foo). One could go further, at least when dealing with Ptrs, and create a way of handling restricted pointers--which we could interpret as a const pointer to an object that cannot be changed by anyone else either. One could safely create restricted pointers with a function of the type mallocRestrictedPtr :: (Ptr a - IO ()) - RestrictedPtr a which would allow one to ensure at the typechecking level that RestrictedPtrs point to memory that cannot be modified. There's still some unstafety involved, in that you could read out of bounds, but you would know that apart from that possibility the contents of a RestrictedPtr truly will never change. So my question is, how would one implement such an annotation extension? I'd like to be able to pass a (Ptr a) as a (Const (Ptr a)) without an explicit typecast, since the Const really isn't changing the type of the pointer, it's just marking it as one that can't be modified. A function that accepts a (Const (Ptr a)) should also accept a (Restricted (Ptr a))--but Restricted pointers are really just pudding, as they only differ from Const pointers in what optimizations are allowed. On the other hand, it's not just compiler optimizations that they would allow, but also user-code optimizations, which could be much more useful. They also have the advantage of making certain unsafe functions safe. The hard part seems to be the lack of a conversion. One could quite easily implement a data Const a = Const a -- this constructor is *not exported* toConst :: x - Const x unsafeAccessConst :: Const x - x peek :: Const (Ptr a) - IO a peekOff ... etc, and everything would work fine, except that you'd always need to explicitely convert from Ptr to Const Ptr. Perhaps one could make Const be a class as well as a data type: class (Const a) x where toConst :: x - Const a instance (Const x) x where toConst = Const instance (Const x) (Const x) where toConst = id and then one could write code like peek :: Const (cp a) = cp a - IO a which would move the typecasting burden out of the calling function and into the function that accepts a const argument. Perhaps this would be sufficient, as many data types have only a limited number of primitive const functions, and all the other const functions wouldn't actually need to call toConst. What this doesn't allow is deriving of constness, so that a Const ForeignPtr would automatically hold a Const Ptr. This whole class+data type scheme seems like it might be useful, but is pretty ugly. Is there a better way this could be done? Might one be able to extend the language so that one could add attribute such as Const to data type without changing the the
Re: [Haskell] getArgs, maxBound, float division: pure functions?
John Meacham:
On Wed, Oct 12, 2005 at 12:05:39AM -0400, David Menendez wrote:
In principle, you could use seperate types to distinguish floats with
different rounding modes, but I imagine this would be difficult or
annoying to implement.
I think it would make more sense to have different operations for each
rounding mode. That matches the reality of the situation more and you
don't want to have to do tons of type conversions when you need to
operate on something with different rounding modes. of course, then you
could declare several 'newtypes' whose default Num instances were of
specific rounding modes too.
A student of mine designed a special-purpose, pure functional language for
block-oriented matrix computations for his PhD. He was very careful to give
the language a good design also regarding floating-point computations. His
design choice, as regards rounding, was to allow the compiler to choose
rounding mode by default (thus allowing more freedom for optimization),
while providing a set of special arithmetic operators, with specified
rounding modes, to use when more explicit control is needed.
He also proposed a special construct letctrl ... in e, where the ... are
a list of directives telling how to interpret and evaluate the expression
e. One possible directive is RoundingMode = ... to set the rounding mode
locally in e. Other directives control, for instance, whether optimizations
like x*0.0 - 0.0 are allowed in e, whether to force strict evaluation of
all subexpressions (so optimizations cannot affect exceptions), to set
allowed miminum accuracy, etc.
The language has exception handling (including a handle construct to catch
exceptions), which also takes care of floating-point exceptions.
If Haskell ever gets redesigned to give better support for numerical
computations, then I think this work is worth a look. Alas, it is not
well-published, but the PhD thesis should be possible to order from the
Dept. of Information Technology and Microelectronics at KTH. I also have a
few copies to give away of someone is interested.
Here's the reference:
@PHDTHESIS{npd-phd,
AUTHOR = {N. Peter Drakenberg},
TITLE = {Computational Structure and Language Design},
SCHOOL = {Dept.\ of Information Technology and Microelectronics, KTH},
ADDRESS = {Stockholm},
YEAR = {2004},
MONTH = sep,
NOTE = {TRITA-IMIT-LECS AVH 04:02}
}
Björn Lisper
___
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] Mixing monadic and non-monadic functions
Ben Rudiak-Gould:
Frederik Eaton wrote:
I want the type system to be able to do automatic lifting of monads,
i.e., since [] is a monad, I should be able to write the following:
[1,2]+[3,4]
and have it interpreted as do {a-[1,2]; b-[3,4]; return (a+b)}.
The main problem is ambiguity: [[1]]++[[2]] could be [[1],[2]] or [[1,2]],
for example. If your proposal resolves this ambiguity in favor of one result
or the other, then I'm opposed to it -- it's far too easy in practice to
write code like this, expecting it to be lifted, and failing to notice that
it also has an interpretation without lifting (or the other way around).
This is the Perl FWIM disease[1] -- not that I dislike Perl, but people are
quite rightly leery about bringing this sort of thing into Haskell.
However, there is a way to resolve the ambiguity that can be claimed to be
the most natural one, and that is to always choose the least possible
lifting. In the example above, this would mean to interpret [[1]]++[[2]]
precisely as [[1]]++[[2]] (lift 0 levels) rather than [[1]++[2]] (lift 1
level). This is akin to choosing the most general type in the pure
Hindley-Milner type system, and it has the advantage that expressions that
are typable in the original type system, without lifting, retain their
semantics in the type system with lifting added.
Lifting (mainly of arithmetic operators) has been around for a long time in
array- and data parallel languages such as Fortran 90 and *lisp. The kind
of ambiguity mentioned here was first observed for nested data-parallel
languages like NESL, which use nested sequences as parallel data structures.
Now, whether to include this kind of lifting in Haskell or not is an
entirely different story. One complication would be to handle possible
clashes between lifting and overloading through the class system. IMHO, I
think it would be interesting to be able to define application-specific
Haskell dialects, which can have this kind of lifting for a restricted set
of types and/or functions, whereas having it as a general feature of the
language would be quite problematic.
Björn Lisper
___
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] some algorithm help with jhc
John Meacham I have started working on jhc more recently and have come across some places where I think my algorithms could be improved but was not sure exactly where to start so thought I would ask the list since perhaps someone here has some insight. After a long time of trying various methods of speeding up the fixpoint iteration of my points-to analysis (the current main bottleneck) I decided to step back and look at the basic problem again. It turns out I can express the problem as one of constraint satisfaction resulting in much smaller code (600 lines vs 2000) and 10fold speedups with my unoptimized first draft solver. It is much faster but still not as fast as I'd like. I don't know a lot about constraint problems, but my intuiton says this particular problem is of a type that should be particularly easy to solve but am uncertain where to start in my searching to find a fast algorithm. My constraints come in two types of rules. Hi, check out the book Principles of Program Analysis by Nielson, Nielson, Hankin (http://www2.imm.dtu.dk/~riis/PPA/ppa.html). It has quite some on constraint solving for program analysis. There are algorithms in that book for set constraint problems that look quite similar to your problem. Björn Lisper ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Python?
Hi all, Finally I found some time to reply to this posting. A couple of years ago we did something called Data Field Haskell, which is Haskell extended with a generalized form of arrays called data fields. Much of the purpose was to investigate convenient and general syntax for array constructions. Data fields are semantically pairs of functions and bounds, where bounds represent sets of indices. Bounds can be pairs of integers representing intervals, but also general finite sets. Certain bounds represent infinite sets, which makes sense in a lazy language. Besides direct notation for creating data fields, Data Field Haskell has a construct forall x - t which defines a data field in a similar way to how lambda-abstraction \x - t defines a function. In addition, the data field defined by a forall-construct has a bound which is derived from the body of the expression. The semantics is derived from the view that data fields (and arrays) are partial functions whose domains do not exceed the index sets defined by their bounds. The forall-construct is intended to provide a simple and powerful syntax for operations on data fields. Let's see below how it matches Jerzy's desired features of an array language: Jerzy: Tim Rowe writes: On 5/11/05, Jerzy Karczmarczuk [EMAIL PROTECTED] wrote: Give me one single language where [3-d arrays are] natural and immediate. I don't know how Matlab does it, but I find the C++ standard library vectorvectorvectorfloat entirely intuitive (apart, perhaps, for the need for those two spaces)! Let's precise what I consider to be important in order to call it natural and immediate. And, in general, useful. 1. The definition of a concrete object, not just its type, but, say, the initialization with constants. Or/and, global initialization with zeros. Since Data Field Haskell is declarative, initialization and definition is the same. Constant data fields are easy to define, viz. forall x - 1, a data field filled with ones forall (i,j) - if i == j then 1 else 0, a unit matrix forall (i,j) - i + j, a Vandermonde matrix All these data fields are infinite, and the first is also dimension-polymorphic (through the usual polymorphism in Haskell). Data Field Haskell has an operator for explicit restriction of data fields, and a data field may also be implicitly restricted from the context where it occurs. 2. Easy synthesis of multi-dim matrices out of planes, of submatrices of lesser dimensions; Not directly expressible, but it is possible to define a binary operator to, say, concatenate a 2-D matrix on some given side of a 3-D matrix. it can be an 'overlay', like, say, making a colour image out of three R/G/B planes, or making a 3D surfaces, or aking tensors through external products. Say, an outer product of two vectors a, b: forall (i,j) - a!i * b!j 3. Easy indexing, and not only A[i][j][k], etc., but slicing, the extraction of sub-dimensional matrices, e.g., one column vector out of a 2D matrix in Matlab: A(3,:). Also, extracting parts (e.g. sub-images). A(3,:) is expressed as forall j - a!(3,j). Or, selecting a plane out of a 3D-matrix: forall (i,j) - a!(i,3,j). Or, selecting the main diagonal of a matrix: forall i - a!(i,i). Extracting parts is done with the explicit restriction operator \: a \ (3,3):(10,20), selecting submatrix of a a \ predicate (\(i,j) - a!(i,j) 0), selecting the subfield of a where it is strictly greater than zero (this is a sparse data field) Also, in mathematical context, intelligent indexing, e.g. treating a matrix as implicitly anti-symmetric. Here the CAS systems as Maple or Mathematica provide the adequate tools. C++ of course doesn't, unless you overload [] yourself. All representation issues are hidden in Data Field Haskell, so there is no direct counterpart. However, it is of course possible to define a data structure of your own and then wrap it up as a data field by providing a bound and a function from indices to values. 4. Readable iterators, perhaps something more compact than insipid do-loops. There are folds for data fields. These can be used for reduction operations over data fields. In a sense, forall-abstraction is also a kind of iterator (although parallel since it does not impose any order of evaluation between the elements of the data field). 5. If those matrices are used as mathematical objects: tensors, etc., I want to have some simple notation for inner multiplications/ contractions, etc. This is not just the syntax problem, but the existence of good libraries as well... You can use folds inside a matrix to, e.g., sum all rows in a matrix. Here is an example of a function that does one iteration in Jacobi's method for iteratively solving the linear equation system ax = b: jacobi_iter a b x = forall i - ((b!i) - dfSum ((forall j - a!(i,j)*(x!j)) \ predicate (\j - j /= i)))/a!(i,i) 6. Reshaping of those arrays. I thought that Matlab
Re: [Haskell] Typing in haskell and mathematics
Jacques Carette: Yes, I am aware that this untypeable in Haskell, because polymorphism is straight-jacketed by structural rules. But in mathematics, it is convenient and extremely common to: 1) look at the type a - b as being a *subtype* of b (though I have never seen it phrased that way in print) 2) to consider every 'natural transformation' available and use it (tuples of functions - obvious function on tuples) Seeing a - b as a subtype of b allows one to take any function f : b - b - c (like + ) and 'lift' it to ff : (a - b) - (a - b) - (a - c) via the obvious definition ff g h = \x - f (g x) (h x) This is done routinely in mathematics. The meaning of the expression (sin + cos) should be immediately obvious. Such 'lifting' is used even in first-year calculus courses, but not in Haskell. I would like to remark that some array languages are doing this kind of overloading (e.g., A + B means elementwise addition of A and B, when A and B are arrays). If arrays are seen as functions from finite index domains, then this is just a special case of your math overloading. Examples of such languages are Fortran 90, HPF, and (the specified, but never implemented) functional language Sisal 2.0. All these languages are first-order, explicitly typed, and provide this overloading only for a predefined set of builtin primitives. However, I think this can be extended to functions in general, in higher-order languages with Hindley-Milner (HM) type inference. I had a PhD student working on this a couple of years ago. Alas, he dropped out before getting his PhD, but we got as far as defining an extended inference system with some nice properties, and I do believe that a reasonable inference algorithm can be found. Rather than using subtyping, this system uses transformational judgements of the form A |- e - e':t, where e':t is inferrable in the original HM type system. Thus, this system resolves the overloading during type inference. For instance, with a proper assumption set A, we would have A |- sin + cos - (\x - sin x + cos x). Now, whether you would want to have this overloading unleashed in a higher order language is another matter. I think it can be useful in some contexts, but probably restricted in some way. Also, in Haskell there would be potential conflicts with the overloading provided by the class system (Num being a prime example). Björn Lisper ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] Implicit parallel functional programming
I'd like to add my two cents worth in this debate... I think the original poster considered the standard multicore processors soon to come, and which can be expected to eventually overtake the processor market. The answer relies a lot on what shape these processors will have: A guess is that the first generation will support a shared memory model much like SMP:s of today (shared main memory with on-chip cache(s), or some other kind of local memory (-ies)). Here, I think implicit parallelism in functional languages can be a win in some situations. This is provided spawning of parallel threads is cheap and local memory can be efficiently utilized (so control of granularity is no problem, and dynamic parallelism is cheap). Cheap threads is likely to be true, efficient use of local memory is a question mark. However, some obstacles: Laziness, if used strictly (sorry) gets in the way for parallelism. Waiting to spawn a parallel thread until we surely know it's result is needed, if it is anyway needed 99% of the time, is not an optimal strategy. I think optimistic evaluation strategies a la Robert Ennals can be helpful here. But designing them to work for new parallel architectures may be non-trivial. I think there can be material for PhD theses here. If the program implements an inherently sequential algorithm then parallelism won't help anyway. The use of lists often leads to sequential algorithms: a prime example is list folds, which all translate the linear spine structure of a list into a sequential dependence graph of the resulting computation. Folds over tree-like structures are better in this regard. The FP community will have a problem with legacy code using inherently sequential computations over lists. There has been quite some research on how to parallellize list computations (skeletons, program transformations using BMF,...). However, they typically rely on knowing the length of the list. In a lazy language it is common that lists are evaluated dynamically, and then it's hard to use these techniques efficiently. Again, speculation may help. In the long run, as hardware dimensions shrink even more and communication becomes relatively even more expensive, it is likely that we will have some kind of on-chip massively parallel, mesh-connected distributed memory machine. This will most likely favor static parallelization techniques, which means only for certain classes of functional programs an automatic approach with implicit parallelism will work well. Björn Lisper ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] Implicit parallel functional programming
Keean Schupke: A guess is that the first generation will support a shared memory model much like SMP:s of today (shared main memory with on-chip cache(s), or some other kind of local memory (-ies)). Here, I think implicit parallelism in functional languages can be a win in some situations. This is provided spawning of parallel threads is cheap and local memory can be efficiently utilized (so control of granularity is no problem, and dynamic parallelism is cheap). Cheap threads is likely to be true, efficient use of local memory is a question mark. You only need one thread per CPU-core, so the spawning threads cost is a red-herring. Just like GHC schedules haskell-threads from a single OS-thread. Then you need some mechanism to assign jobs to threads, which also carries an overhead. How large that overhead is depends to some degree on the architectural characteristics of the machine (some shared workpool is necessary, which means the cost of common memory accesses comes into play). However, some obstacles: Laziness, if used strictly (sorry) gets in the way for parallelism. Waiting to spawn a parallel thread until we surely know it's result is needed, if it is anyway needed 99% of the time, is not an optimal strategy. I think optimistic evaluation strategies a la Robert Ennals can be helpful here. But designing them to work for new parallel architectures may be non-trivial. I think there can be material for PhD theses here. I suggest speculative execution, as used by current CPUs to take advantage of multiple microcode execution units. If the a CPU has spare capacity, functions whose results might be needed are run. As soon as you know a result is not needed the thread can be killed, and the time used for something else. A lot of work has already been done on hardware superscalar-architectures, and a lot of this should be applicable to the software case. Yes, precisely what I refer to above (the work of Robert Ennals). But you need to choose well what to speculate on. This can be nontrivial. If the program implements an inherently sequential algorithm then parallelism won't help anyway. The use of lists often leads to sequential algorithms: a prime example is list folds, which all translate the linear spine structure of a list into a sequential dependence graph of the resulting computation. Folds over tree-like structures are better in this regard. The FP community will have a problem with legacy code using inherently sequential computations over lists. There has been quite some research on how to parallellize list computations (skeletons, program transformations using BMF,...). However, they typically rely on knowing the length of the list. In a lazy language it is common that lists are evaluated dynamically, and then it's hard to use these techniques efficiently. Again, speculation may help. But in the worst case its just a sequential computation, so any gain from parallelism is still a gain... It depends on what you compare with. Multicore CPU:s will probably have cores that are simpler than current processor cores, which means you will want to have some parallelism. Cf. a superscalar processor, which really in a sense is a parallel machine but where you add some complex control hardware to make it emulate a sequential machine. Running a multicore CPU on a single core at a time corresponds to running a superscalar machine where you use none of the superscalarity. Or, running a pipelined CPU (another form of parallelism) without utilizing any of the pipelining. This is not what you want. also the dependant part of a loop is often separate from an independant part... For example consider a list of strings, and taking the length of each string. The next iteration does not have to wait for the length to be computed, it can start the next length computation as soon as the pointer for the next list cell has been dereferenced. Sure you can get some overlap, which can be quite big if the task to perform per list element is big, but a dependence graph with O(n) nodes will still have O(n) depth = at maximum constant speedup. In the long run, as hardware dimensions shrink even more and communication becomes relatively even more expensive, it is likely that we will have some kind of on-chip massively parallel, mesh-connected distributed memory machine. This will most likely favor static parallelization techniques, which means only for certain classes of functional programs an automatic approach with implicit parallelism will work well. The next generation of CPUs seem to be using a shared cache architecture, so overheads are extreemely small... I'm not talking about the next generation but further ahead. Maybe these architectures will have some kind of on-chip shared cache, who knows, but that memory will then still be much more expensive to access than the memory in a local core. So you will want to use the core-local memory all the time, and only communicate between processor cores
Re: [Haskell-cafe] Integrating Haskell into a J2EE environment
I'm surprised that nobody has yet mentioned the ICFP2000 paper Composing Contracts: An Adventure in Financial Engineering by SPJ, Jean-Marc Eber, and Julian Seward. It seems to me that it could provide quite relevant reading. Björn Lisper Paul Hudak: I wouldn't write off Haskell so quickly. All of what Shoeb describes concerning DSL issues might be much more easily solved in Haskell, and will certainly be more flexible than a hard-wired approach. The J2EE interface might be ugly, but if the functionality needed is not too great it might not be too bad. Generally speaking, these kinds of apps -- in this case a DSL for high-level business rules -- sounds like just the sort of thing that Haskell is good for. -Paul Doug Kirk wrote: You're going to spend alot of time marshalling between Java and Haskell values, and you'll either have to do it via JNI or by using pipes [as in System.exec(haskellprogram param param param)], both of which are ugly for a Java app. Have you looked at Jython and JRuby? Jython is an implementation of a Python interpreter in 100% Java, and JRuby implements a Ruby interpreter in 100% Java. Those might get the job done faster than having to delve into the native layer. (Not to mention learning how to use Haskell in order to implement what you want--not a trivial task in itself!) Take care, --doug On Oct 5, 2004, at 4:33 PM, Bhinderwala, Shoeb wrote: Hi All, I am new to Haskell and this mailing list. We have a system that uses a custom high-level language to express high-level business rules. Expressions in the high-level language get compiled to Java bytecode. We express the grammar using BNF notation as required by the javacc parser tool. This is then converted to an AST using jjtree and from there we build the final Java code. Our language could be considered a domain-specific language (DSL) and is used by our business users to express very high-level business logic. The language currently is very limited - we support boolean logic, function invocations and if-then statements. We want to convert it into a more powerful scripting language so that even lower level business logic can be expressed in it. I came across a few papers that talk about writing a DSL with Haskell as the underlying support language. How is this done. Is it possible to create a sort of domain specific business scripting language easily. How does that then compile to Haskell code. And how can the Haskell code be invoked from Java. Essentially, I am thinking if I could use a Haskell like DSL language to express our business rule logic and then be able to integrate into and invoke the logic from a J2EE app server environment. Has anybody done anything like this with Haskell. -- Shoeb ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe This communication is confidential and may be legally privileged. If you are not the intended recipient, (i) please do not read or disclose to others, (ii) please notify the sender by reply mail, and (iii) please delete this communication from your system. Failure to follow this process may be unlawful. Thank you for your cooperation. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe -- Professor Paul Hudak Chair, Dept of Computer Science Office: (203) 432-1235 Yale University FAX:(203) 432-0593 P.O. Box 208285 email: [EMAIL PROTECTED] New Haven, CT 06520-8285 WWW:www.cs.yale.edu/~hudak ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] 2-D Plots, graphical representation of massive data
Jerzy Karczmarczuk: Jacques Carette wrote: John Meacham [EMAIL PROTECTED] wrote: What would be cooler (IMHO) would be brining all of matlabs functionality into haskell via haskell libraries so one may use 'ghci' sort of as one uses matlab, but with the advantages haskell brings. One could create Haskell libraries that are matlab-like, but most of the advantages of haskell (ie stong typing) are not realizable in Haskell. To express even the most basic of matrix datatypes and operations requires dependent types. I did not understand what is not realizable where... I wonder what for do you need those dependent types. Matlab is quite orthodox, its main flexibility comes from the dynamical typing, resolution of the dimensions at the run-time, etc. The Numerical Python gives a good share of Matlab functionalities. Now, overloading arith operations for some bulk data (lists, lists of lists, arrays, etc.) casting them to some matrix general types, should not be impossible without dependent types. Hm. I will not bet my head, but, please, *provide an example* of such situation. I think Jacques possibly means the ability to do static checking of matrix and vector extents, to make sure that you don't try to perform operations like matrix-vector multiply on operands whose extents do not match. If you want to have this ability on your language, then you will have to restrict the way you are allowed to construct array bounds so the equations that arise can be solved. Possibly a dependent type system can be helpful for this. Björn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] Eliminating Array Bound Checking through Non-dependent types
( A really interesting post on static elimination of array bounds checking by Oleg...) Some questions and suggestions: What is the relation to the sized types by Lars Pareto and John Hughes? What is the relation to classical range analyses for (e.g.) array index expressions, which have been known for a long time for imperative languages? A program analysis like range analysis is not exact, of course: it must make safe approximations sometimes and will sometimes say that an array index might be out of bounds when it actually won't. In your framework, this seems to correspond to the fact that you must verify your propositions about index expressions. If the formulae fall into some decidable category, then they can be verified automatically, otherwise an automatic method based on your framework will have to give up sometimes, just like a conventional program analysis. The formulae you give in your example are all Presburger formulae, for which there are decision procedures, and you could use a public domain Presburger solver like the Omega Test by Bill Pugh. Have you though of this possibility? Björn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] insufficiently [EMAIL PROTECTED] -- more counterintuitive stuff
Andrew Bromage: Pattern matching on the LHS of a function definitions looks, for all the world, like a set of rewrite rules. That's because, in some sense, they are. In this definition: f (x:xs) = 1 + f xs f [] = [] Intuitively, the first rule should only fire if the expression being evaluated conforms to the left-hand side. But beware that even though they can be seen as rewrite rules, there is a difference in that a term rewrite system allows all possible orders of applying rewrite rules, whereas Haskell specifies a top-down order in which the rules are tried. This can make a difference if patterns overlap, so several patterns can match a given argument. In the given example the patterns do not overlap though, so this can indeed be seen as a little term rewriting system defining f. Björn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] Programming language shootout (completing the Haskell entry)
From: John Hughes [EMAIL PROTECTED] Actually the cache behaviour of code generated by GHC isn't at all bad. I know because I ran a student project a couple of years ago to implement cache-friendly optimisations. The first thing they did was cache profiling of some benchmarks, and to our surprise we discovered the cache behaviour of lazy code is already pretty good. You get a lot of structure in the evaluation of lazy code -- it just isn't evident in the source code! John, could you describe in some more detail why the code behaved well w.r.t. cache performance? I think this is interesting, and what you say is quite counterintuitive. Björn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] Making a spreadsheet with Haskell
Hi, I would like to know how can I make a spreadsheet using Haskell (something like Excel, a very-reduced version, of course) Do I need any kind of special library? How can I make the interface so the user can introduce data, select data and so on? Thanks for your help. Miren Cob Isasi de Vírgala We did something called Haxcel. It is a spreadsheet-like interface to Haskell, thus making it possible to use Haskell as a formula language. The interface itself is implemented in Java. See http://www.mrtc.mdh.se/projects/getProject.php3?id=0041. Björn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: pet project - 7 Millennium Prize problemss
--- Keith Wansbrough [EMAIL PROTECTED] wrote: Christopher Milton [EMAIL PROTECTED] writes: I think Haskell can be used to solve several, if not all, of the seven problems. Now I have to decide which problem to tackle first. (a joke, I assume...) http://www.claymath.org/Millennium_Prize_Problems/ 1. Birch and Swinnerton-Dyer Conjecture 2. Hodge Conjecture 3. Navier-Stokes Equations 4. P vs NP 5. Poincare Conjecture 6. Riemann Hypothesis 7. Yang-Mills Theory Any ideas how to solve any of these, with Haskell or otherwise? module P where import Complexity_class(np) p = np :-) Björn Lisper ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: palm?
M. Parker: What about a port to Windows CE (i.e., for Pocket PC's). Or even better yet, hugs for Pocket PC! -Matt There is an interesting research question in here: how to design lean implementations of lazy functional languages so they can run on small handheld and embedded systems with restricted resources. In particular the restricted memory available poses an interesting challenge. What I would like to see is an implementation that is designed to be easy to port among different handheld/embedded systems, since there are quite a few of them (in particular there are many embedded processors). Probably a bytecode implementation is good since byte code is compact. Nhc might provide a good starting point since it uses bytecode and was designed to be resource lean in the first place. I think the people at York even did some experiments putting it on some embedded system some years ago. Compilation of standalone programs is also interesting since especially embedded programs often execute in fixed environments. Lots of room for program specialization and subsequent code optimizations here. But I think the programming model also must be developed. One will need to give the programmer more control over resources when necessary. This requires operational semantics with good cost models, notoriously difficult with lazy languages. So one will have to continue the work to integrate eager and stateful execution into the lazy model. Furthermore, the i/o model must be developed to accomodate the event-driven style typical for both embedded and interactive systems. I think the functional reactive stuff from Yale (Fran/FRP) provides a really nice high-level notation but it is hard to make guarantees about limited resource consumption in that model. There are models with resource guarantees (E-FRP) but they seem to limited to be really useful in practice. One would like to cover the spectrum in-between. Now, if one would succeed in doing all this, then there would be support for an embedded software development model where one could first write highly declarative executable specifications, test them for logical bugs, and then sucessively refine the code towards a resource-lean implementation using more and more resource-aware primitives where necessary. I think this would be a really interesting alternative to the current imperative practice (head on with C or assembler) and the object-oriented trend with UML/java/C++. Björn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: palm?
Just a side remark. I wonder whether the byte-code approach is the best possible solution taking into account the overload of the decoder. Why not threaded code? The FORTH (and similar) experience, PostScript implementations, etc. show that this paradigm may be more interesting. Anyway, when you read for the first time the Talmud, ehmmm., I mean the description of the STG machine by Simon PJ and others, you see that some of their ideas are not very far from code threading. The classical FORTH style, with the separation between tha data and return stacks seems quite appropriate for easy implementations of higher-order control structures. If you saw the bells and whistles inside a FORTH processor implemented on 8bit machines, you would agree with me. But I do not exclude the possibility that all this has been already discussed and rejected for some serious reasons... Jerzy Karczmarczuk Good remark, I just didn't think of the threaded approach. There is a reason Forth was popular on early desktop systems. I'd like to hear some arguments regarding the pros and cons of the threaded vs bytecode approaches! Björn ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Arrays vs Lists and Specialization
Matthew Donadio: | Many spectral estimation routines are defined in terms of special | matrices (ie, Toeplitz, etc). Arrays defined recursively by list | comprehensions make it easy to implement algorithms like Levinson-Durbin | recursion, and they look very similar to the mathematical definitions: | | levinson r p = (array (1,p) [ (k, a!(p,k)) | k - [1..p] ], realPart (rho!p)) | where a = array ((1,1),(p,p)) [ ((k,i), ak k i) | k - [1..p], i - [1..k] ] | rho = array (1,p) [ (k, rhok k) | k - [1..p] ] | ak 1 1 = -r!1 / r!0 | ak k i | k==i = -(r!k + sum [ a!(k-1,l) * r!(k-l) | l - [1..(k-1)] ]) / | rho!(k-1) | | otherwise = a!(k-1,i) + a!(k,k) * (conjugate (a!(k-1,k-i))) | rhok 1 = (1 - (abs (a!(1,1)))^2) * r!0 | rhok k = (1 - (abs (a!(k,k)))^2) * rho!(k-1) | | OK, my question then has to do with the efficiency of lists versus | arrays. Do the latest compilers handle handle arrays efficiently, or | are lists really the way to go? If there is a performace difference, is | it generally big enough to warrant rewriting algorithms? Simon: Do not rewrite it! This is a textbook application of Haskell arrays, and they should work beautifully. If not, we should fix it. Using lists will probably be much *less* efficient than arrays. People often use arrays with algorithms derived from imperative programming, which assume update-in-place. They use (\\) for each element, which copies the entire array, and get terrible performance. Haskell arrays are designed to be build en-bloc, as you are doing it. Your programs are lovely, and will not do redundant array copying. It is, however, possible that GHC fails to deforest away all the intermediate lists in the array comprehensions, but I think it does a reasonable job. You can use -ddump-simpl to see. You could check out SAC. SAC is a functional language specialized for arrays, with restrictions in the language to ensure efficient compilation. The SAC compiler can apparently do a very good job on scheduling/memory allocation as to optimize for cache performance: this is an important issue to get performance in array computations that I believe current Haskell implementations do not bother much about. SAC has syntactic forms to define arrays that are somewhat reminiscent of array comprehensions, although they are much more restricted. An interesting route for a *real* array-optimizing Haskell compiler could be to try to find instances of array comprehensions that can be mapped to constructs corresponding to SAC's constructs, and then apply the compilation technology of SAC. An alternative is to make such constructs directly available in Haskell, so the programmer can be explicit whan performance is needed. Homepage http://www.informatik.uni-kiel.de/~sacbase/. Björn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: What does FP do well? (was How to get ...)
Jerzy: Me: ...sometimes the length of a list being returned from a function can be a simple function of the function arguments (or the sizes of the arguments), think of map for instance. In such cases, a static program analysis can sometimes find the length function. If we know thee functions for all list-producing functions in a closed program, then the lists could be represented by arrays rather than linked structures. I know Christoph Herrmann worked on such a program analysis some years ago. Also, I think Manuel Hermenegildo has done this for some logic language. Andrew Appel wrote something about pointer-less lists as well. What bothers me quite strongly is the algorithmic side of operations upon such objects. Typical iterations map- (or zip-) style: do something with the head, pass recursively to the tail, would demand intelligent arrays, with the indexing header detached from the bulk data itself. The consumed part could not be garbage collected. In a lazy language this might possibly produce a considerable amount of rubbish which otherwise would be destroyed quite fast. The concatenation of (parts of) such lists might also have very bad behaviour. Can you calm my anxiety? No, since you're right. For instance, stream-type list computations, where list elements are used and then discarded, will not benefit from this kind of transformation. (They will be better optimized by deforestation.) List-to-array conversion will work best with computations where many different elements are used many times. Björn ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: What does FP do well? (was How to get functional software engineering experience?)
Karl-Filip: But what I really meant is, if I may rephrase it, that imperative programs might often be both faster and harder to write because they embed more information about the abblication domain. That is, if you code in C and want an array, you must specify its size, so you have to think about your program and figure out that you only need 'x' items here, wheras in Haskell you'd use a list and never have to think about what the upper bound on the length of the list is. Yes indeed. But sometimes the length of a list being returned from a function can be a simple function of the function arguments (or the sizes of the arguments), think of map for instance. In such cases, a static program analysis can sometimes find the length function. If we know thee functions for all list-producing functions in a closed program, then the lists could be represented by arrays rather than linked structures. I know Christoph Herrmann worked on such a program analysis some years ago. Also, I think Manuel Hermenegildo has done this for some logic language. Could sized types be used for this purpose? (I must find myself some time to read Lars Pareto's PhD thesis...) Björn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: partial application
Cagdas Ozgenc: That's right. I was thinking of the following syntax. I orginally had the idea for C++, where you can't do partial application at all. f x y z=... f # 3 4 omitting the first parameter, and Array languages with true multidimensional arrays often have a this kind of syntax to extract subarrays, for instance A(*,J) or A(,J) to extract column J from the matrix A. Now, if you think about arrays as partial functions from indices to values, then row J of matrix A is precisely \I - A(I,J). This syntax can be very convenient for array computations. Björn Lisper ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Isn't this tail recursive?
Hal Daume III: Here's the basic idea. Suppose we have the function: sum [] acc = acc sum (x:xs) acc = sum xs (acc+x) This is tail recursive, but not strict in the accumulator argument. ... Just a nitpick here. sum is indeed strict in its second argument (given that (+) is strict in its first argument). That is, sum l _|_ = _|_ for all possible lists l. It is of course possible that the compiler you use does not detect this and generates nonstrict code. But I think a decent strictness analyzer should detect this. Can the problem be that + is overloaded in Haskell, so the compiler cannot assume any semantical properties like strictness for it? Björn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: ideas for compiler project
Simon: Lots of people have observed that Haskell might be a good scripting language for numerical computation. In complicated numerical applications, the program may spend most of its time in (say) matrix multiply, which constitutes a tiny fraction of the code for the application. So write the bulk of the application in Haskell (where the logic is complex but the performance doesn't matter) and then link to a C or Fortran library to do the small part that is really compute intensive. More concretly, suppose you built an FFI interface to BLAS or some readily available numerical library, and then demonstrated the utility of the resulting beast by writing some non-trivial numerical application in it. This is an interesting idea that I think can be made to work to some extent. One issue will be to find the right tradeoff between stateful and purely functional, i.e., allowing nice matrix-algebra based expressions while ensuring that memory can be reused to the extent necessary. If all matrix operations are wrapped up in some state monad, then you lose the nice matrix algebra style. If, on the other hand, you have no way to express updating, then you lose memory reuse (unless you have a *really* smart compiler...). The best tradeoff is probably to mimic a small imperative language with clean, side effect-free matrix operations, where updates are effectuated by explicit matrix assignments. Of course, this is possible only if the BLAS routines are side effect-free themselves our can be wrapped up as such. It is interesting to note that MATLAB started out exactly as a convenient scripting language for a Fortran matrix library. MATLAB is a system for matrix computing that contains nice graphical possibilities and a matrix programming language. It is very popular in engineering, and is widely used for applications like signal processing, automatic control, and PDE solving, in particular in the early prototyping phase. Its popularity does not stem from its speed, since it's quite slow, but rather from: - nice graphics capabilities (plottings, etc) - convenient matrix language (to some extent, I would add), and - above all, lots of toolboxes, i.e., MATLAB software wrapped up for various applications (simulation of control systems/signal processing, etc.) There is a big third-party market for this kind of software. I think MATLAB's matrix language provides about the right level of abstraction for a high-level matrix language. You can for instance write things like Y = inv(A)*B to assign to Y the solution of Ax = B. To some extent this is what you'd like to have, On the other hand, a closer look at the language will reveal that it has many strange and ugly semantical corners, where the imperativeness shines through in nasty ways. This is a hindrance to optimizing compilation, since good optimization of matrix code requires extensive reordering transformations. Also, MATLAB is very ill-suited to expressing block-recursive matrix algorithms, which are becoming increasingly important in numerical computing. And, of course, there is no decent type system, no higher order functions, etc... So, I think it could be interesting to embed a purified version of MATLAB's matrix language in Haskell. This would be interesting as a demonstration of what a good matrix language could look like, but don't expect to be able to sell it to the world since the competitors are far ahead in all other aspects. You'd need to find a real application though. There are plenty. Signal processing, automatic control, PDE solvers,... The classical kernels (matrix multiply, inversion etc) are precisely the things you may not want to do in Haskell. With the current compiler technology for Haskell, one would add. I don't think it would be impossible to compile such Haskell programs into efficient code. Functional languages for matrix/array computing was a quite active research area 10-15 years ago, with efforts like Sisal and Id. These languages were strict and first order, but you can write such programs in Haskell. I think it would be possible to have a Haskell compiler that could manage a subset of Haskell matrix programs quite well. (Christoph Herrmann did some interesting work in this direction: Christoph, you're reading this list aren't you?) Whether it would be worth the (big) effort is another matter. Björn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Compiler error using IO
Zhanyong Wan: Here here. I think that the poor compiler error messages in Haskell are a very major hurdle to learning the language. Adrian Hey: Which compiler are you talking about? Bad error messages are not a valid critisism of the Haskell Language IMHO. But there are language features in Haskell that makes it hard to produce good error messages. Implicit typing, for instance: in an explicitly typed language it is clear where in the code a type error occurs, but with implicit typing there are often many possibilities and it is not always evident where the culprit is. (Haskell compilers seem simply to report the line where the unification fails. Am I right?) Furthermore, semantically distant expressions can be syntactically close in Haskell, so a syntax error actually gives a syntactically correct expression. Often this yields a type error instead, which then may show up as an error message for some totally different part of the code... Higher-orderness increases the risk. An example is inadvertently writing f g y for f (g y) which then is interpreted as (f g) y and will yield incorrect constraints on the types of f, g, and y. Is there any work being done on intelligent error messages for higher-order implicitly typed languages? One could perhaps come up with search strategies that tries to find a minimal number of program transformations (edit distance) that yields a syntactically correct and well-typed program. For instance, in the case of type errors one could try to search for the minimal number of definitions that have to be removed to make the remaining program well-typed, and then report the removed definitions as likely sources of the errors. Has anyone done this? Björn Lisper ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Strange error in show for datatype
Hi again, My question about my student's problem surely stirred an interesting and clarifying discussion. Still, I have a question. Reconsider the example. There's a data type data LispList t = Atom t | LispList [LispList t] | Str [Char] and an instance declaration instance Show t = Show (LispList t) where show (Atom t) = show t show (LispList t) = show t show (Str t) = show t So, hypothetically there could have been an additional, overlapping instance declaration, say instance Show (LispList Int) where show (Atom t) = show t show (LispList t) = show t show (Str t) = Blahonga! Then we cannot know whether show (Str HEJ) should yield HEJ or Blahonga!. However, my student never gave such an overlapping instance, only the first. So far as I can see there should relly be no ambiguity here! I'd really like to know what the cause of the problem is. Björn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Strange error in show for datatype
Hi,
For a change, a teacher asking for help on behalf of a student
I have a student who wants to emulate S-expressions of Lisp in Haskell. He
came up with the following data type:
data LispList t = Atom t | LispList [LispList t] | Str [Char]
This works just fine. He then wanted to make it an instance of Show, in
order to print values of this type:
instance Show t = Show (LispList t) where
show (Atom t) = show t
show (LispList t) = show t
show (Str t) = show t
Now, this compiles and works for some values of the type, but not for all!
Here is what happens in hugs:
hugsprompt (Atom 1) == 1
hugsprompt (LispList [Atom 1, Str HEJ]) == [1,HEJ]
hugsprompt (LispList [Atom 1, LispList [Str HEJ]]) == [1, [HEJ]]
hugsprompt (Str HEJ) == Cannot find show function
hugsprompt (LispList [Str HEJ]) == Cannot find show function
hugsprompt (LispList [Str HEJ,Atom 1]) == Cannot find show function
So there is a problem when the value is of form Str string or where such a
value is first in the list l in a value of the form LispList l. Oddly
enough, such values may appear at other positions without causing any
problems.
I don't think there is a bug in hugs. Similar problems appear if the Show
instance is derived, and ghc will also complain - if the definition
f = show (LispList [Str HEJ])
is compiled, for instance, the compiler will complain about ambiguous
contexts. Ghc will say
Enrico.hs:1: Ambiguous context `{Show taKi}'
`Show taKi' arising from use of `show' at Enrico.hs:17
and hugs
Reading file Enrico.hs:
Type checking
ERROR Enrico.hs (line 17): Unresolved top-level overloading
*** Binding : f
*** Outstanding context : Show b
So I wonder whether the infamous Monomorphism Restriction is lurking
somewhere here? But I cannot see exactly how right now. Does anyone else
have a clue?
Björn
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: A sample revised prelude for numeric classes
Tom Pledger: Brian Boutel writes: : | Having Units as types, with the idea of preventing adding Apples to | Oranges, or Dollars to Roubles, is a venerable idea, but is not in | widespread use in actual programming languages. Why not? There was a pointer to some good papers on this in a previous discussion of units and dimensions: http://www.mail-archive.com/haskell@haskell.org/msg04490.html The main complication is that the type system needs to deal with integer exponents of dimensions, if it's to do the job well. Andrew Kennedy has basically solved this for higher order languages with HM type inference. He made an extension of the ML type system with dimensional analysis a couple of years back. Sorry I don't have the references at hand but he had a paper in ESOP I think. I think the real place for dimension and unit inference is in modelling languages, where you can specify physical systems through differential equations and simulate them numerically. Such languages are being increasingly used in the "real world" now. It would be quite interesting to have a version of Haskell that would allow the specification of differential equations, so one could make use of all the good features of Haskell for this. This would allow the unified specification of systems that consist both of physical and computational components. This niche is now being filled by a mix of special-purpose modeling languages like Modelica and Matlab/Simulink for the physical part, and SDL and UML for control parts. The result is likely to be a mess, in particular when these specifications are to be combined into full system descriptions. Bjrn Lisper ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Revamping the numeric classes
Marcin Kowalczyk: Me: No, the transformation is a single step procedure where a term is transformed into a typeable term (if possible) with a minimal amount of lifting. You don't compose transformations. So functions implicitly lifted can't be used in the same ways as functions originally defined as lifted (namely, they can't be lifted again)... This is bad. Functions themselves are never lifted. They just appear to be lifted when applied to arguments of certain types, and then the function application is always statically resolved into an expression where the function has its original type. Due to the principle of minimal lifting (which implies already well-typed terms should not be transformed) a call to a polymorphic function should not be transformed unless there is a dependence between the type variable(s) of the function and of the argument(s) in the application. Does f x y = (x, x + y) has type Num a = a - a - (a, a) and thus it cannot be used on the type Int - [Int] - (Int, [Int]) even though if its body was inlined into an expression requiring that type, it could (by lifting x+y to map (x+) y)? Your function has its polymorphism constrained to the Num class. So we could allow elemental overloading (on the uncurried form of f) as long as [Int] is not an instance of Num. Yes, if [Int] is made an instance of Num then the meaning of calls to f on lists will change from the elemental meaning to the meaning defined through the instance declarations for [Int]. This can surely be a problem in some cases. But this is not a property of the elemental overloading mechanism per se, but rather that we would have two different overloading mechanisms in the language powerful enough to specify conflicting overloading. BTW, the type signature for your "lifted f" (if it existed) should be (Int,[Int]) - [(Int, Int)]. See second example below. You can't lift arbitrary function of type Int - Int - (Int, Int) into Int - [Int] - (Int, [Int]) without knowing its defintion. Try it with g x y = (y, x). Consider uncurried g: g (x,y) = (y,x) and assume it has an explicit type declaration to (Int,Int) - (Int, Int) (so it's not polymorphic). if x :: Int and l :: [Int], then g (x,l) - zipWith (g.(,)) (repeat x) l :: [(Int,Int)]. The rewrite of the overloaded application is guided only by type information. (Again note only the application of g is rewritten, neither g itself nor its type does change.) Suppose there is a function fancyPrint :: Printable a = [a] - IO () which applies some fancy printing rules to a list of printable values. A programmer knows that this function can be used on lists as well as on single elements, because those elements will be promoted to single-element lists as necessary. So far so good. The rules I have sketched so far only promote a value in connection with elemental overloading. A good example is g (x,l) above. Here, g is elementwise applied to l and in the process x becomes promoted into (repeat x), similar to the original scaling example a*x where a is a scalar and x a matrix. So with these rules alone fancyPrint 17 would not be rewritten into fancyPrint (repeat 17). But the rules can of course be extended to cover this case. Then he applies it to a single String. Guess what? It is not promoted to a single-element list, but each character is printed separately. Oops! Which is the original meaning of fancyPrint applied to a string. Why "oops"? A programmer must be aware of the meaning of function he writes. fancyPrint will always be a function over lists, no matter whether its use is overloaded on arguments of other types or not. It's not enough, because the least lifted type is not the most general answer. Answers for different amounts of liftedness are incompatible with that answer - they are not its instances as in the HM typing. It does not matter that they are not instances. It does. It's not enough to check that there exists a set of places to insert map or zipWith which transforms what is written to what I need. Because there can be a different, incompatible set of places, which is considered "better" by the compiler and my set is not obtainable from what the compiled has done. See the first example above. (I think your example was broken, but in principle you're right.) Of course, the use of the overloading I have described (and any kind of overloading) is justified only if the overloading matches the intuition of the programmer. If it misleads you then it is harmful. Regarding elemental overloading, my experience is that data parallel programmers quickly develop a strong intuition for it. What I have seen through examples is that elemental overloading using the rules I have sketched and the "minimal lifting" principle always seems to produce the intuitively correct meaning, also in a language like Haskell. If the produced result is the "right" one, then the fact that other possible transformations produce terms with incompatible types is
Re: Types from values using existential types?
I recently had an idea to allow one to create types from values. This would have many uses in Haskell; e.g., it would be very nice to have a type of nxn matrices for n that are not necessarily statically determined. (It is easy to create a type of matrices and check that the sizes are compatible at run time; the point is to do more checks at compile time.) Of course, one has to be careful to preserve decidability of type checking. . Are there any pointers to previous work I should look at? If type systems for matrices are of interest for you then I think you should check out Barray Jay's work on the language FiSH. Bjrn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Revamping the numeric classes
I see. So you can transform arbitrary function of type a-b-c to a function of type [a]-b-[c], by applying \f x y - map (\z - f z y) x and similarly a-b-c to a-[b]-[c]. But then there are two ways of transforming a-b-c to [a]-[b]-[[c] There should be no transformation to type [a]-[b]-[[c]] in this case. Wait wait wait. You told that a-b-c is convertible to [a]-b-[c] for *any* a,b,c. Now I have x = [a], y = b, z = [c] and use the transformation x-y-z to x-[y]-[z] and obtain [a]-[b]-[[c]]. Both steps are legal, so their composition must be legal, or I don't like this Haskell-like language anymore. (You never seem to have liked it much ... :-) No, the transformation is a single step procedure where a term is transformed into a typeable term (if possible) with a minimal amount of lifting. You don't compose transformations. Let us write [a]^n for the type of n-deep lists of lists of a. If f :: a - b - c, x :: [a]^m, and y :: [b]^n, then f x y is transformed into a term with type [c]^max(m,n). This is the minimal lifting necessary to obtain the correct elementwise application of f. If m n then promotion will take place on the first argument, if m n on the second, and if m = n then there will be an elementwise application without promotion. Unless you say that a-b-c is convertible to a-[b]-[c] *except* when a is a list. Then it's bad again. There should be no negative conditions in the type system! Moreover, in a polymorphic function you don't know yet if a will be a list or not. Due to the principle of minimal lifting (which implies already well-typed terms should not be transformed) a call to a polymorphic function should not be transformed unless there is a dependence between the type variable(s) of the function and of the argument(s) in the application. Such dependencies could possibly occur in recursive calls in function definitions. Consider, for instance the (somewhat meaningless) definition f x y = head (f [x,x] y) During type inference, f will first be assigned the type a - b - c. In the recursive call, f will be called on arguments with types [a] and b. This causes a lifting to occur, where f is elementwise applied to [x,x] with promotion of y. The transformed definition becomes f x y = head (zipWith f [x,x] (repeat y)) On the other hand, if f somewhere else is applied to some other arguments, with types not containing a, then no transformation of that call will occur. There are no full and partial applications because of currying. It's impossible to say when you should consider a function as a multiparameter function. There are only single-argument functions. So you would have to say that some rule apply only *unless* the result has a function type, which does not work again. Touch! To keep the discussion simple I have kept multiparameter functions curried, but you nailed me. Yes, there will be ambiguities if you allow overloading on other than the first argument in a curried definition (since there really is only one argument). So for a function f :: a - b - c we should only allow elementwise overloadings corresponding to functions of types [a]^n - [b - c]^n. Elementwise overloading on multiparameter functions must appear only on their uncurried forms, so only if f :: (a,b) - c then we can allow transformations of calls corresponding to type signature ([a]^m,[b]^n) - [c]^max(m,n). (This would give problems with elementwise overloading of arithmetic operators in Haskell, since these are curried. But, as I said earlier, I'm not proposing to actually extend Haskell with this overloading, I'm only discussing the concept as such in the Haskell context.) With your rules a programmer writes code which is meant to implicitly convert a value to a single-element list, because something tries to iterate over it like on a list. Unfortunately the element happens to be a string, and he gets iteration over its characters. And if it works the other way, another programmer meant iteration over characters and got iteration over a single string. You can't tell which was meant. I don't think there will be any ambiguities here. The overloading is resolved statically, at compile-time, for each call to the function. Calls to polymorphic functions are not transformed (except for cases like I showed above). Of course the type/term transformation system must have the property that if different transformations can yield the "best" type (wrt liftedness), then the transformed expressions should be semantically equivalent. It's not enough, because the least lifted type is not the most general answer. Answers for different amounts of liftedness are incompatible with that answer - they are not its instances as in the HM typing. It does not matter that they are not instances. Each call is transformed statically, separately. The liftedness ordering is used only to direct the resolution of the overloading, so we pick the minimal lifting (the others are not interesting). The overloaded function
Re: Revamping the numeric classes
Also, what is the inferred type of, for example f x y = x + length y ? It can be Int - [a] - Int [Int] - [a] - [Int] and neither is more general than the other. And this is a simple function. Int - [a] - Int, since this is the type it will get in the original type system. So I can't apply f to lists, but I could if I inline its body. This means that I cannot arbitrarily refactor a piece of code by moving parts of it into separate definitions: subexpressions are given some extra meanings only if they are physically placed in certain contexts. This is bad. This is a misunderstanding. the transformation of f l y , where l :: [Int] for instance, should depend only on the type of f and not its definition. It is the call to f, not f itself, that becomes transformed. No inlining takes place. Ah, so what uses of f are correct depends on its definition, not type! Sorry, this is way to radical. Types exist to formalize possible ways a value can be used. HM allows to determine most general types variables in a let-block (or: of a module) before their uses, so separate compilation is possible. In your system typechecking of a function's definition is done each time it is used! No. See above. Bjrn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Revamping the numeric classes
It is quite similar in spirit to the concept of principal type in Hindley-Milner type systems. An expression can have many types but only one "best" (most general) type in that system. Now, I'm not any kind of expert on this, but isn't the most general HM type one that encompasses the others, and *not* one out of a set of ambigous (and mutually exclusive) types? In a sense. You define a partial order on types by a a' (a more general than a') if there is a substitution s of type variables such that a' = sa. The interesting property of HM type systems is that for each term t and all type judgements t:a that can be derived, there is a type judgement t:a' such that a' a. a' is called the most general type of t. What I suggested was to define a different relation between types, measuring "relative liftedness". We can call it "". Now, if it is the case that for all judgements t - t':a in the type system I sketch, there is a judgement t - t'':a' where a' a, the we can select the transformation to be t - t''. t'' will then have a "most general type" among the possible transformed terms, but wrt rather than . Ambiguity between types depends on the ordering between types that you consider! Bjrn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Revamping the numeric classes
I see. So you can transform arbitrary function of type a-b-c to a function of type [a]-b-[c], by applying \f x y - map (\z - f z y) x and similarly a-b-c to a-[b]-[c]. But then there are two ways of transforming a-b-c to [a]-[b]-[[c]] and the order of applying the former transformations does matter. Worse: a third way is to apply zipWith and then promote the result to a single-element list. Or maybe map the result to a list of single-element lists... There should be no transformation to type [a]-[b]-[[c]] in this case. If f is applied to arguments of type [a] and [b] then this should be interpreted as the elementwise application of f to the two argument lists, and the result type should then be [c]. Note that [a]-[b]-[[c]] is "more lifted" than [a]-[b]-[c]. Elementwise application to one argument should transform to map, of several arguments to zipWith with appropriate arity. It is easier to see how it should work if we skip lists, so we don't have to deal with maps and zipWiths and other list functions. Let us consider elementwise application of f over indexed entitites. For simplicity we consider functions as our indexed entities, but it could as well be arrays. With f as above, then f x y should be transformed to: (1) x :: d - a, y :: b yields \i - f (x i) y (2) x :: a, y :: d - b yields \i - f x (y i) (3) x :: d - a, y :: d - b yields \i - f (x i) (y i) Here (3) is "full" elementwise application, and (1) and (2) are "partial" elementwise applications where the unlifted argument can be seen as promoted. If you have list instead of functions, then the transformation should insert list primitives with the corresponding effect. Sorry, IMHO it's ambiguous as hell except very simple cases. Of course the type/term transformation system must have the property that if different transformations can yield the "best" type (wrt liftedness), then the transformed expressions should be semantically equivalent. I believe a type/term transformation system with this property can be designed, but the details remain to be worked out. Bjrn Lisper (Is this discussion still of interest to the Haskell list members? Or should we take it offline?) ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Revamping the numeric classes
Marcin 'Qrczak' Kowalczyk: Me: I'd like to point out the connection between the use of +, - on vector spaces and * for scaling with features in some data parallel languages. In these languages, writing a + b where a and b are arrays of numerics is interpreted as elementwise addition of a and b. This features generalises to other operations than +, -, other types than numerical ones, and other data structures than arrays. This is what I dislike. It's implicit fmap / zipWith / etc. But it only works as long as there is only one meaningful way to insert these fmaps. When I apply length to a list of lists, is it the length of the whole list or a list of lengths of its elements? So there must be explicit ways of specifying the amount of fmaps, and one cannot assume that they will be always placed automatically. It might be convenient for very specific types computation but is not a working general idea. A natural principle to adopt is that an already typeable expression should not be transformed. This will for instance resolve the ambiguity in the list of list example: if l :: [[a]] then length l is already well-typed and should not be transformed into map length l. Furthermore, some of these languages support "promotion": "lifting" a "scalar"-typed expression, appearing in a context where an array (say) is expected, into an array with suitable dimensions containing copies of the scalar. Again, Haskell does not have subtyping. It is not compatible with type inference - it can only work in poor languages which require an operation to be fully applied where it is used, and either don't have static types or require them to be specified explicitly. I am not so sure about this. Could you exemplify? Note that you can do some of this overloading already within Haskell's class system. For instance, one can make lists of Nums into Nums by declaring instance (Num a) = Num [a] where x + y = zipWith (+) x y x * y = zipWith (*) x y ... fromInteger x = repeat (fromInteger x) ... Now, if x and y are lists of Nums, then 2*x + y becomes zipWith (+) (zipWith (*) (repeat fromInteger 2) x) y In Haskell trying to implement such overloading would be too clumsy and would not work as expected in all cases, so better don't go this way. I should point out that I didn't suggest adding this overloading in Haskell, I was merely pointing out the connection between vector space syntax/scaling and features in data parallel languages. Bjrn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Revamping the numeric classes
Marcin Kowalczyk: Me: A natural principle to adopt is that an already typeable expression should not be transformed. This will for instance resolve the ambiguity in the list of list example: if l :: [[a]] then length l is already well-typed and should not be transformed into map length l. So there are ways to interpret an expression which are not chosen only because some other way is a better match? This is very dangerous in principle. Two interpretations of a code are "correct", but one is "more correct" than the other. It is quite similar in spirit to the concept of principal type in Hindley-Milner type systems. An expression can have many types but only one "best" (most general) type in that system. Also, what is the inferred type of, for example f x y = x + length y ? It can be Int - [a] - Int [Int] - [a] - [Int] and neither is more general than the other. And this is a simple function. Int - [a] - Int, since this is the type it will get in the original type system. The types you mention are incomparable w.r.t. the usual "more general"-ordering on types, but one could consider also other orderings. For the types you give, the second is more "lifted" than the first in that it contains [Int] in places where the first type has Int. One can define a "liftedness" order on types in this vein. (OK, so one would need to go through the formalities and prove that there are "principal types" w.r.t. this relation between types, and that this new principal type concept is not in conflict with the old one. I cannot say for sure that it works.) I should be more specific about what a type system could look like that implements this kind of overloading. It could be a coercive type system, with judgements of the form t - t':a where t, t' are terms, a is a type, and t:a is a correct judgement in the original type system. So the type system not only gives a type but also a transformation that resolves the overloading into a well-typed term. Again, Haskell does not have subtyping. It is not compatible with type inference - it can only work in poor languages which require an operation to be fully applied where it is used, and either don't have static types or require them to be specified explicitly. I am not so sure about this. Could you exemplify? Sorry, I don't have a concrete example in mind. How to infer types when implicit conversions are possible anywhere? The above function f can be applied even to two numbers (because the second would be promoted to a list of length = 1), so what is its inferred most general type? Int - [a] - Int. If f is applied to some arguments with other types for which the overloading is defined, say f l1 l2 where l1 :: [Int] and l2 :: [a], then the term f l1 l2 would be transformed into a well-typed term but the type of f itself would not change. Again, arbitrarily choosing one of the alternatives basing on some set of weighting rules is dangerous, because a programmer might mean the other alternative - there is no simple way to ensure that the compiler interprets it in the same way as I wanted. It's not enough to check that all types match modulo conversions - I must carefully check that no "better" interpretation is possible. I surely agree that this kind of overloading should be used only when it is in accordance with the intuition of the programmer. This could, for instance, imply restrictions to certain types or operators. Bjrn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Specifications of 'any', 'all', 'findIndices'
Koen: The definitions in the Haskell report are a *specification*, not an implementation. It probably depends on the compiler which particular implementation runs faster. Therefore, the Haskell report provides a clear (yes, this is debatable) *possible* implementation, and the compiler writer is free to implement this in whatever way (s)he likes. As long as the implementation has the same functional behavior as the specification in the report. Hear, hear. What I in turn would like to add is that specifications like any p = or . map p are on a higher level of abstraction than definitions like any p [] = False any p (x:xs) = p x || any p xs This makes it easier to find different implementations, which makes it easier to adapt the implementation to fit different architectures. The first specification is, for instance, directly data parallel which facilitates an implementation on a parallel machine or in hardware. Bjrn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Specifications of 'any', 'all', 'findIndices'
Pardon? map is data parallel. foldr not so obviously... Sorry, a slip on my behalf: foldr in general is not data parallel, but if the function being folded with is associative then foldr can be implemented by a parallel (balanced binary-tree) reduction in time O(log n), where n is the length of the list. A compiler needs the information that or is a fold over an associative operation in order to employ such a parallel implementation. Bjrn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Higher-order function application
Tim Sweeney:
Is this "higher order function application" a useful notion, and does any
research exist on the topic?
The answer to the first question is "yes, when it matches the intuition of
the programmer". Your two first examples:
cos+sin-- intent: \x-((cos x)+(sin x))
cos(sin) -- intent: \x-cos(sin(x))
have equivalents in Fortran 90 and HPF, although with arrays rather than
functions. For instance, one can write "A+B" to mean an array with value
A(I)+B(I) for all indices I, and A(B) for the array with elements A(B(I))
(provided B is an integer array whose elements all are valid indices for
A). This feature is widely used in array languages, where it is seen as an
intuitive and convenient notation to express array operations. I definitely
believe it could be useful also for operations over other data structures.
The answer to the second question is "surprisingly little". There is, for
instance, no formal description to be found of the Fortran 90 array
operations and how they type. But it is quite straightforward to define
type systems and type checking algorithms for this, when the language is
explicitly typed. One example is
@InProceedings{Thatte-ScalingA,
author = {Satish Thatte},
title ={Type Inference and Implicit Scaling},
booktitle ={ESOP'90 -- 3rd European Symposium on Programming},
editor = {G. Goos and J. Hartmanis},
number = 432,
series = {Lecture Notes in Computer Science},
year = 1990,
publisher ={Springer-Verlag},
address = {Copenhagen, Denmark},
month =may,
pages ={406--420}
}
where a type system for an APL-inspired overloading in an FP-like language
is described. This approach is based on subtyping.
A student of mine is pursuing another, more direct approach, where a
coercive type system is used to resolve the overloading at compile time
through a combined rewrite and type check. He did this for an explicitly
typed variant of Core ML, and this is reported in his Licentiate thesis
("file://ftp.it.kth.se/Reports/paradis/claest-licthesis.ps.gz"):
@PHDTHESIS{claest-lic,
AUTHOR = {Claes Thornberg},
TITLE = {Towards Polymorphic Type Inference with Elemental Function
Overloading},
SCHOOL = it,
ADDRESS = {Stockholm},
YEAR = {1999},
TYPE = {Licentiate thesis},
MONTH = may,
NOTE = {Research Report } # rep-id # {99:03}
}
@STRING{it = "Dept.\ of Teleinformatics, KTH"}
@STRING{rep-id = "TRITA-IT R "}
When the type system is implicit (inference rather than checking), however,
less is known. You can do some tricks with the Haskell class system (for
instance, defining functions between instances of Num to be instances of
Num themselves, which then lets you overload numerical operations like "+")
but this solution has some restrictions and is also likely to lead to
run-time overheads. We would like to have something better.
Finally, there is an interesting discussion of this overloading business,
for array- and data parallel languages, in
@ARTICLE{Sip-Blel-Coll-Lang,
AUTHOR = {Jay M. Sipelstein and Guy E. Blelloch},
TITLE = {Collection-Oriented Languages},
JOURNAL = {Proc.\ {IEEE}},
YEAR = {1991},
VOLUME = {79},
NUMBER = {4},
PAGES = {504--523},
MONTH = apr
}
For instance, they bring up the possible conflicts which may occur when
trying to resolve this overloading for operations over nested data
structures. (A witness is length l, where l :: [[a]]: should it be just
length l, or resolved into map length l?)
Björn Lisper
Re: What happened to the GRIN project?
1) are anyone pursuing this line of work, and Sadly, Urban left us for industry (Carlstedt Research and Technology), where Thomas Johnsson is also on sabbatical at the moment. So nobody here is pursuing this at the moment. 2) is the software available? Ask Urban: [EMAIL PROTECTED] ought to reach him still. My former student Karl-Filip Faxen did his PhD thesis on very similar compilation methods for lazy languages (Karl-Filip, do you follow the Haskell mailing list?), and he also got impressive speedups for a set of admittedly small benchmarks. His compiler does not implement full Haskell, but there should be no problems in principle to extend it to full Haskell and his compilation techniques are in no way dependent on this restriction. He can be reached at [EMAIL PROTECTED] He is still working on his compiler and he has a paper in the upcoming ICFP conference. I think Karl-Filip's and Urban's methods are very interesting and the way to go for efficient compilation of lazy languages. The key to cope with large programs is probably to have an intelligent strategy for function cloning, which clones functions to increase the potential to optimise by specialisation, but only for calls where there is a potential to gain from this in order to avoid the potential code explosion. Björn Lisper
Re: == and hyperstrictness
Suppose Sven implements his `len' function as above, and furthermore implements a library which depends on this function being hyperstrict. Suppose next that I implement an instance of `==' that returns `True' without evaluating the arguments, and then finally suppose a third programmer called say Joe comes along and uses my type with Sven's library. If it breaks, who is to blame? I think the cleanest solution is to add a method "hseq" to the Eval class, which is similar to seq but evaluates its first argument hyperstrictly before returning its second. Then Sven can write len :: Eq a = [a] - Int len [] = 0 len (x:xs) = x `hseq` (1 + len xs) We did this in "Data Field Haskell" - a dialect of Haskell for collection-oriented programming which we have designed and made a prototype implementation of - where we happened to need this functionality. (Those of you who are interested can have a look at http://www.it.kth.se/labs/paradis/dfh/. I plan to make a "public release" of of the system and announce it here, but there are still some problems with the installation scripts so I have put the release on hold until we have sorted these problems out. For now, download at your own risk :-) Björn Lisper
Re: == and hyperstrictness
Me: I think the cleanest solution is to add a method "hseq" to the Eval class, which is similar to seq but evaluates its first argument hyperstrictly before returning its second. Marcin 'Qrczak' Kowalczyk: You mean "implicit Eval"? Then I would certainly not call this solution "clean". Even the full polymophism of seq is considered controversial, and the Eval class was explicit before. I don't know about full polymorphism (I guess hseq would not work well for function-typed arguments, for instance), but I know there are situations where it can be important from a practical perspective to add varying degrees of strictness explicitly. Then I think the cleanest solution is to have explicit operations which give you this, with a clearly stated semantics, rather than the "x==x" kind of hack. Björn Lisper
Re: definition domain extension proposal
Sergey: To separate a sublanguage of Haskell given by the corresponding compilation key (say, -domExt ) or, maybe, by the compiler pragma. This sublanguage allows the compiler to replace any function f with the function f' being the extension for f. This was discussed on the list a while ago, right? I remember Arvind arguing for this kind of transformation. I also think there is a need for it, or rather for a way to more in general tell the compiler that it is OK to use "almost correct" transformations, which need not be just extending the domain of a function. An example is to let the compiler consider addition of floating-point numbers to be associative (which it really is not, just approximately), which makes it possible to parallelise folds over it. This transformation can be very important in HPC applications, but its application requires the knowledge that the numerics doesn't go wrong. An interesting question is how to specify these kinds of transformations for the compiler in a flexible way. Björn Lisper
Re: fixing typos in Haskell-98
Take and drop
[..]
I can see three alternatives:
(A) Make them defined for any n. If n 0, do something reasonable:
take: give empty list
drop: give whole list
(B) Make them defined for n length xs, but fail for n 0.
(C) Status quo
PROPOSAL: Use alternative (A)
I vote the same. (A) is in accordance with the view of a list xs as a
function from the interval {0,...,length xs - 1} (with [] as a function from
the empty set {}, and {a,...,b} = {} iff a b). Then take n xs selects the
defined elements of xs from {0,...,n - 1} and drop n xs those from
{n,...,length xs - 1}. If some other alternative is chosen then this simple
view breaks down.
Björn Lisper
Re: What is a functional language?
Me: Yes, it makes a lot of sense. The parallel or above is a classical example of a function for which there exists no semantically correct sequential evaluation order of its arguments (i.e., an evaluation order where an argument is evaluated in full before the evaluation of the next argument starts). Therefore, it has usually been discarded as infeasible to implement since the in the worst-case scenario its evaluation may require that you spawn off an exponential number of concurrent threads (imagine a function calling the parallel or recursively on both sides). Adrian Hey: This is the biggest problem I think. Implementation would be very difficult. It requires a compiler smart enough to only start separate threads if it's going to make some difference to the termination properties, and a very efficient implementation capable of supporting an arbitary number of threads. I don't see the potential problem with infinite nos. of threads as a reason not to do this though. Haskell as it stands provides plenty of opportunity to screw up with infinite things :-) This is not to discourage you (I think your idea is quite interesting), but the parallel or actually provided a big headache to early researchers in semantics. It pops up in the standard functional domains used for denotational semantics and its non-sequential nature was seen as kind of unnatural. (For instance, it cannot be encoded in the lambda calculus.) Great efforts were spent do define function domains where non-sequential functions like the parallel or did not exist. I don't think these efforts really ever succeeded. I have always felt that these efforts were somewhat misguided. (Theoreticians out there, please don't kill me!) There is nothing strange with parallel threads, or a function that requires parallel threads for its faithful implementation. But there might be a serious problem with efficiency. There have been attempts in this direction: Early implementations of the language Oz, for instance, used a parallel strategy where a thread was spawned off for each call. I think it was done this way just because it was simple to implement (Oz is concurrent, so they needed to support parallel threads anyway.) In later version of Oz this strategy has been abandonded, though., for efficiency reasons I think. Björn Lisper
Re: What is a functional language?
Adrian Hey [EMAIL PROTECTED]: The issue I'm thinking about is equational reasoning and program transformation. For a lazy (non-strict) language, transformations are constrained so that a function definition which is non-strict in an argument is never transformed into one which is strict in the same argument. (Or so I believe, please correct me if I'm wrong). Well, if you want the transformations to preserve the semantics, yes. (N.b. that a function with a nonstrict argument may be called in an environment where we know something about the argument, for instance, that it is always evaluated, which then makes it correct to replace *that call* to the function with a call to a transformed function with a strict argument.) This seems completely contrary to normal equational reasoning (which is one thing functional languages are supposed to support), where we aren't so constrained. No. Equational reasoning simply means that we use equations which are valid to transform expressions. When used for program transformations, the set of valid equations is determined by the semantics of the language. This set of equations will change depending on whether the language is strict or nonstrict. For instance, a logical or which is strict in both arguments will be commutative and associative, while a nonstrict or with a left-to-right evaluation order of its arguments will be non-commutative but still associative. Nonstrict languages actually have the property that function definitions can be seen as equations. I would say this is what makes the language referentially transparent! This means that a function call can always be symbolically unfolded without altering the semantics. Strict languages do not have this property in general. So in this sense nonstrict languages are more amenable to equational reasoning! Note that if we want the transformations to preserve the semantics of the language w.r.t. termination we will have to deal with bottom in equations also in strict languages, since also strict languages contain certain operations with nonstrict semantics (e.g., conditionals). Of course, we can consider a coarser semantics without the bottom, where we do not distinguish functions w.r.t. termination properties, and then have a different set of equalities: a good example is x - x = 0 which is valid if bottom is discarded but not valid if it is included. (I believe it may be this kind of discrepancy which has lead you to think that nonstrict languages do not permit equational reasoning.) So is it unfair to say that as soon as issues like strict vs. non-strict semantics become an important, the language is no longer purely functional? It is not only unfair, it is wrong. Doesn't having to treat _|_ as a value spoil equational reasoning? No, see above. Björn Lisper
Re: What is a functional language?
On Mon 27 Sep, Bjorn Lisper (i.e., me) wrote: For instance, a logical or which is strict in both arguments will be commutative and associative, while a nonstrict or with a left-to-right evaluation order of its arguments will be non-commutative but still associative. Adrian Hey: But should we let such operational issues muddy the waters? Is a function.. 1- A mapping between input values and output values (which don't include _|_). I imagine this is what mathematicians would call a function. or.. 2- A method of computation. For all its abstraction, as far as Haskell is concerned this has to be the correct way to view a function. This is what makes Haskell a _programming_ language, rather than a tool for reasoning about the properties of functions. In my example, it's both. On one hand, we can give a purely equational specification of the nonstrict or I sketched above (I just give the nonstrict part): true or bot = true false or bot = bot bot or x = bot, for all x On the other hand, it is well known that one particular reduction strategy that implements this semantics faithfully is the classical left-to-right strategy. So, I guess the answer is.. Yes, we do need to let such operational issues muddy the waters. What worries me here is that there might be some unjustifiable assumptions about the nature of the machine which is performing those operations. In particular by talking about things like 'reduction order' and 'order of pattern matching' aren't we assuming a sequential machine. If so, should such considerations be allowed to 'pollute' the semantics of a general purpose high level programming language. We are not assuming a sequential machine. The equational semantics of "or" above does for instance allow that we speculatively fork off a thread evaluating the second argument before we know the value of the first argument, if we just delay the return of the answer until the first argument is fully evaluated. On the other hand, one must keep some operational semantics in mind when specifying a more abstract semantics, so one does not end up with a language which is very expensive or impossible to implement on the machines at hand. Nonstrict languages actually have the property that function definitions can be seen as equations. Almost, but not quite, as Fergus Henderson noted. Well, as Fergus pointed out, syntactic sugar like definitions by patterns may have to be removed first. What started me thinking about this is the 'World as Value' thread on the Clean discussion list, where I tried (unsuccessfully I suspect) to make the case for using a concurrent non-deterministic machine as the basic model for I/O. Then I started thinking about how one would compile function definitions into 'computational actions' on such a machine (a Haskell compiler does this for sequential machines) and realised that this would give that language subtly different semantics wrt the way _|_ was treated. I don't know what the proper name for such semantics is, so I'll call it 'concurrent non-strict' semantics as distinct from 'sequential non-strict' semantics. Do you think about such semantics as the "parallel or", which has its strictness properties defined by: false or bot = bot or false = bot true or bot = bot or true = true ? I think concurrent non-strict semantics restores many (perhaps all?) useful transformations. An obvious example being it restores transformations like.. a b = b a Does this make sense? Yes, it makes a lot of sense. The parallel or above is a classical example of a function for which there exists no semantically correct sequential evaluation order of its arguments (i.e., an evaluation order where an argument is evaluated in full before the evaluation of the next argument starts). Therefore, it has usually been discarded as infeasible to implement since the in the worst-case scenario its evaluation may require that you spawn off an exponential number of concurrent threads (imagine a function calling the parallel or recursively on both sides). Björn Lisper
Re: Non-strictness vs. laziness (was RE: Sisal)
Joe Fasel wrote: Actually, I think we were originally thinking of laziness, rather than nonstrictness, and weren't considering languages like Id as part of our domain, but Arvind and Nikhil (quite correctly) convinced us that the semantic distinction of strictness versus nonstrictness should be our concern, rather than the operational notions of eagerness and laziness. "Frank A. Christoph" [EMAIL PROTECTED]: Please elucidate. Where does this difference become important? What impact did it have on the language? It is definitely important in parallel processing, where you may want to spawn off activities speculatively, to utilize idle processors, and kill off these activities later if it is discovered that their results are not needed. This yields nonstrict behaviour if implemented correctly, but it is not lazy. Björn Lisper
Re: Cryptarithm solver - Haskell vs. C++
"Manuel M. T. Chakravarty" [EMAIL PROTECTED]: * While Sisal is arguably nice than Fortran, it doesn't really provide a new killer feature - rewriting all this Fortran code, just for getting nice programs is maybe not enough of an incentive. As I remember it, a main argument for Sisal was that the freedom of side effects would simplify the automatic parallelisation. So one important percieved incentive was to actually get better performance than from automatically parallelised Fortran. Björn Lisper
Re: more on Rules
The optimization " n+1 n == True " is extremely useful in array subscript analysis, bounds checking etc. and is correct as long as n terminates (is not bottom). The cases where this optimization is used most often, n usually terminates. A more diligent compiler would use the optimization only if it could prove that n does terminate. I will take my chances with a fast but less diligent optimizing compiler which in some diabolical cases produces 3 when it should not have terminated. Both the Id compiler and now the pH compiler follow this philosophy. May be we should let an implementation do whatever it pleases in case of an error. If we regard non-termination as an error then producing a value in case of non-termination may not seem so bizarre. However, there are many cases where I really do want my errors reported. I think such compiler/language decisions should be taken on pragmatic grounds. I think it is important that these "almost always semantics-preserving" optimizations are not carried out silently. If they are, then programmers may start to rely on them and then their programs may break if they are compiled with a compiler that does not perform the optimization. On the other hand it is perfectly true that many useful optimizations have this character. So one would like some kind of user control. I think that sometimes the actual specification one has in mind is not as rigid as the one that actually is implemented by the code. The problem we had here earlier, about reordering reductions where the operations are only "almost AC" (e.g., floating-point arithmetic), is similar. Often one wouldn't care about the numerical variations resulting from different reduction orders, but sometimes they could matter. Bjorn Lisper
Re: non-linear patterns
Term rewriting theory indicates that non-linear patterns should be treated with care. For instance, a term rewriting systems with a non-linear rule will in general not have a normalizing rewrite strategy which is sequential, and nonlinear term rewriting systems are not orthogonal which means they may be nonconfluent. So Haskell's pattern matching is not precisely the same as term rewriting, but anyway. Bjorn Lisper
Re: STL Like Library For Haskell
Me: There is another good reason to have a total order: it makes reduction operations (folds) over the structure well-defined. Kevin Atkinson: But how important is having a fold well defined. For many common numerical operations such as summing a list, taking the product of a list, etc. The order in which the elements get folded does not matter. All that matters is that each element gets represented exactly once. It depends. Sometimes you do fold over binary operations which are associative and commutative, and then the order does not matter of course. But sometimes this is not true - floating-point operations are typically not exactly associative and commutative and then the ordering does matter for the numerical precision. It must then be up to the programmer to use knowledge of the numerical algorithm and indata to decide whether a "loose specification" of fold which does not require a well-defined ordering is OK or not. One can come up with examples where the order of summation makes a big difference in error propagation. Whether pathological or not, the programmer must have control when necessary. Other operations are non-commutative, like function composition. There is an amusing example in Hillis, Steele "Data Parallel Algorithms", CACM vol 29, 1986, where they derive a data parallel algorithm for lexical analysis by expressing this problem as a reduction over composition of transition functions for finite automata. This reduction can be parallelized due to associativity of function composition but the order of the functions being composed cannot be changed. We require that there is a function enumerate :: Bounds a - [a] which provides a total order of the elements Do strings fall within the requirements? Yes (use lexicographic order), but we don't have them for now. Bjorn Lisper
