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] 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] 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 b
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] 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
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
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] 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: 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: 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: 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: 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: 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: Revamping the numeric classes
Marcin 'Qrczak' Kowalczyk: >Me: >> 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. >This does not solve the problems. Instead of composed liftings I will >split the code into separate bindings. Suppose I write: >let >g x y = x + y >f x y = g x y >in f [1, 2] [10, 20] :: [[Int]] >What does it mean? I could mean this: >let >g :: Int -> Int >g x y = x + y >f :: Int -> [Int] -> [Int] >f x y = g x y >in f [1, 2] [10, 20] :: [[Int]] >which results in [[11, 21], [12, 22]], or this: >let >g :: Int -> Int >g x y = x + y >f :: [Int] -> Int -> [Int] >f x y = g x y >in f [1, 2] [10, 20] :: [[Int]] >which results in [[11, 12], [21, 22]]. Anyway, somebody loses (one >who thought that his version would be chosen by the compiler). Actually, both will lose :-). If we change f to uncurried form f(x,y) = g x y then we will have f :: (Int,Int) -> Int, and f [1, 2] [10, 20] -> zipWith f.(,) [1, 2] [10, 20] :: [Int] which evaluates to [11,22]. If you mean that f [1, 2] [10, 20] is explicitly typed to [[Int]], then I'd say a type error is the correct result. I think explicit typing should only affect the HM typing of the transformed expression by possibly giving it a less general type, it should not coerce the elemental overloading into a more lifted result than necessary. >If you think that the fact that bodies of let-bound variables are >typechecked prior to their usage help, let's transform let to lambdas >(it's not used polymorphically so it's possible): >(\g -> (\f -> f [1, 2] [10, 20] :: [[Int]]) (\x y -> g x y)) >(\x y -> x + y) >Now it is not clear in what order this should be typechecked, and >different orders give different results. Unlike algorithm W, a type inference algorithm that resolves elemental overloading as part of the type inference must (I believe) maintain a set of different possible assumptions about the type variables, and in the end make a choice guided by the "minimal lifting" principle. In your example (with uncurried f) there will be an assumption f::(Int,Int)->a stemming from (\f -> ...)(\x y -> g x y) and an assumption f::([Int],[Int])->b from f [1, 2] [10, 20]. These types cannot be unified, but can be made related wrt the "liftedness" order if b=[a]. Minimal lifting now dictates that (Int,Int)->a is chosen, and f [1, 2] [10, 20] is subsequently transformed as above into an expression of type [Int]. A type error follows since [Int] is not a substitution instance of [[Int]]. I should say I don't have the details of an inference algorithm sorted out, but I think something along the lines above should work. >It can be beta/eta-reduced to >[1, 2] + [10, 20] :: [[Int]] >and I really don't know what meaning would you give to it. If + has uncurried type then [1, 2] + [10, 20] -> zipWith (+).(,) [1, 2] [10, 20] :: [Int], but in general one should not expect that unresolved overloaded expressions have the subject reduction property. (For instance, the example above breaks if + has curried type Int -> Int -> Int.) >Anyway, examples are pointless. Functional programming, as opposed to >imperative programming, leads to more common use of lists and functions >as values (instead of repeated stateful calls you return all elements >in a list to process them later), also Maybes, tuples etc. Function >explicitly take as arguments things they depend on, explicitly return >things they modify, functions are curried, there are combinators like >(.) or curry which manipulate functions without applying them... >All this means that there are many more places when somebody can >make a type error by mismatching levels of lifting functions or >lifting repetition. Probably true. What I have tried to argue is merely that elemental overloading probably can be done in a consistent way even in language like Haskell that has an advanced type system. I don't deny that there can be problems if it behaves in ways unexpected to the programmer. >When I am making a type error, the last thing I want from a compiler >is to guess what I could mean and silently compile incorrect code >basing on this assumption. I could have done the error in a different >place! Well, "silent": as for any kind of syntactical convenience, the use of elemental overloading would require the possibility to obtain good diagnostics and information about the resulting typings and transformed expressions. >> 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 stro
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 o
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. Björn 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
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. Björn 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
>> 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! Björn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
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. Björn 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. Björn Lisper ___ 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. Björn Lisper ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Revamping the numeric classes
Dylan Thurston: >Andreas Gruenbacher: >> It may be the case that using (*) for scaling too is a generally bad >> idea... >It may not be type sound to have the same operation, but there should >be some standard operation for scaling. (Probably you need >multi-parameter type classes for this.) 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. 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. Scaling can be seen as a special case of promotion, if "*" is interpreted elementwise: for instance, 17*a where a is an array is then seen as an array with elements 17 elementwise multiplied with a. Thus, using "*" both for scaling and elementwise multiplication can be made to work, and it is compatible with the data parallel generalizations of scaling and use of +, - on vector spaces. But using "*" for inner product is not compatible with these generalizations. Preference is probably dependent on background (mathematician or data parallel programmer...). Björn 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. Björn 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. Björn 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
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: == 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: 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?
>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: 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: 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: Cryptarithm solver - Haskell vs. C++
"D. Tweed" <[EMAIL PROTECTED]>: >I'm quite open to arguments that maybe you can't >make a functional language that's as nice as Haskell (features like lazy >evaluation, nice type classes, etc) that's also able to `really hammer >until it's totally flat' functional code that implements heavily numerical >algorithms. However I'd argue that this is still an area where a >functional language which was standard, widely used and compilable into >very very efficient code would be of great benefit to many people who work >on simulation, image processing problems, control systems, etc. (So I'm >happy for the Haskell people to say `We can't make >computation intensive programming better because it'd screw up stuff we do >well now' but not that `development time shrinkage compensates for >run-time growth'.) Sisal was an attempt to define precisely such a functional language. Of course, it is not nearly as "nice" as Haskell as regards features: restricted type system, call by value (except a particular nonstrict data type for streams), no higher order functions, no recursive array comprehensions, etc. These limitations were deliberate design decisions made to make the compilation to efficient code simpler. Sisal also has a rich set of array primitives and a loop-like notation which is syntactic sugar for tail-recursion (the latter making it possible to write surprisingly Fortran-like code in Sisal...). On a standard set of benchmarks, a couple of years back, Sisal obtained performance on par with the state-of-the-art parallelising/vectorising Fortran compilers of that time. There's a C.ACM paper on this, from -93 I think. Yet, Sisal never took off. As far as I know there is neither any development of the language nor on compilers now. 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
Re: STL Like Library For Haskell
Hans Aberg: >The total order is needed in order to make the balanced trees used for the >sets/maps. So what I have in my mind is that somehow Haskell produces a >default total order on elements. This could be the declaration order or an >alphabetical order, or whatever (and it is nice to humans that the elements >always come out in a specific, known order). For elements that have a >natural order, one can use that of course. And as an option, one can think >of that it can be overridden. There is another good reason to have a total order: it makes reduction operations (folds) over the structure well-defined. >The main point though is that the total order exists, and is a sorting >order separate from the Ord derivation. >Then Haskell uses this to implement sets and maps by using C++ STL style >balanced trees. As Haskell already has generic variables, just as in the >case of lists, it needs only be implemented once. We have been working for a while on a related topic: support for generic and convenient collection-oriented programming over indexed structures. In order to achieve this, we have designed something called "data fields" which can be seen as arrays generalized to more arbitrary index sets than the "rectangular" ones given by array bounds. So we have a data type "Bounds a" which provide representations of sets of elements of type a, and some abstract set operations. Bounds be either "dense" (array-like bounds), "sparse" (general finite sets), or cartesian products. Data fields are created from bounds in Bounds a and functions a -> b. We require that there is a function enumerate :: Bounds a -> [a] which provides a total order of the elements in any bound defining a finite set. This is exactly to make operations like folds well-defined for any finite data field regardless of the "shape" of its bound. We assume a predefined total order on elements of non-product data types (we require that these belong to the class Ix), and if a is a product data type then we use the lexicographical ordering on tuples. We use balanced trees to represent "sparse" bounds. So in some sense we seem to be quite close to what you ask for. Our implementation is a somewhat rehacked version of nhc from Gothenburg/York. It has been "almost finished" for a while now (some minor things to polish) and we will make it available on the net as soon as this is done. Just a final comment on total orders on sets: this makes sense, as regards operations where the order is important for the semantics, only if the elements of the set are drawn from an enumerable set. It would not be very sensible to, for instance, try to impose a total order on a set of functions. A total order of the objects representing the functions would of course be possible and could be used to have the balanced trees, but it would not be possible to, say, have a well-defined fold over that kind of set (or any indexed structure using this set as index set). Bjorn Lisper
