The importance and relevance of FP
Jacques Lemire
be the kiss of death for FP in the large -- OO just seems 90 degrees out of
phase with FP.
Craig Dickson
> On the contrary, languages like C++ (and Java) and
> C# are full of concepts and ideas coming from FP
> languages. For example, the catch/try/throw construct
> is coming directly from Common Lisp (Lisp is a
> (although impure) FP language).
This is, needless to say, something of a matter of opinion and historical
interpretation. I wouldn't call LISP an FP language, though it is surely
ancestral to many FP languages, and many FP concepts have their basis in
LISP features.
FP has had some influence on non-FP languages, surely, but usually the
effect of this influence has been not to add core FP capabilities or allow
FP thinking, but instead to add some isolated feature that is more or less
orthogonal to FP, even if it originated in an FP language. Exceptions are a
good example of this; they really have nothing to do with FP as such (in the
sense of "FP is sugared lambda calculus"). How many non-FP languages have
real higher-order functions? Certainly not C++, despite the STL's "function
objects".
> I would not be a bit suprise to see tuples, lists and
> cons(es) introduce in the next generation of languages.
Which "next generation"? If you mean the descendants of C++ and Java, I
would be quite surprised to see LISP-style lists built into them.
> If you what to see the limitations of OO and C++, take
> a look at the MFC, MFC architects had to introduce macros.
Well, I'm not sure that's a fair target. I don't think anyone knowledgeable
about OO would consider MFC (or C++ itself) a very good example of it.
Craig
Friedrich Dominicus
> This is, needless to say, something of a matter of opinion and historical
> interpretation. I wouldn't call LISP an FP language, though it is surely
> ancestral to many FP languages, and many FP concepts have their basis in
> LISP features.
Could you explain why Lisp isn't a FP language? I think among others
it is one. And the combination of features makes Lisp IMHO outstanding
even nowadays.
Regards
Friedrich
--
for e-mail reply remove all after .com
Ketil Malde
> Could you explain why Lisp isn't a FP language?
Well, the obvious arguments would be that
: functions, while pretty first class objects, reside in their own
namespace, and need special operators.
: iteration and side effects are not particularly discouraged, and is
probably as common as recursion and purity in actual code.
-kzm
--
If I haven't seen further, it is by standing in the footprints of giants
Ketil Malde
<87r97p6...@q-software-solutions.com>
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
From: Ketil Malde <ke...@ii.uib.no>
In-Reply-To: Friedrich Dominicus's message of "16 Aug 2000 08:09:54 +0200"
Date: 16 Aug 2000 11:17:25 +0200
Message-ID: <KETIL-vk1v...@eris.bgo.nera.no>
Lines: 14
User-Agent: Gnus/5.0803 (Gnus v5.8.3) XEmacs/20.4 (Emerald)
Sender: k...@eris.bgo.nera.no
Original-Sender: Ketil Malde <k...@networks.nera.no>
MIME-Version: 1.0
Julz
>
> Well, the obvious arguments would be that
>
> : functions, while pretty first class objects, reside in their own
> namespace, and need special operators.
> : iteration and side effects are not particularly discouraged, and is
> probably as common as recursion and purity in actual code.
Does that then not just make it a functional language that can be (and has
been) 'abused'?
People do tend to be lazy (as in water) and take the easiest path.
Not necessarily the 'right' one.
If something is used for a purpose that it was not originally intended
for, does that change _what_ it is?
I ask the question, If Lisp is not a 'functional language', then what is
it?
Best Regards,
Julz.
--
Student, University of Otago, New Zealand.
Friedrich Dominicus
> > > Could you explain why Lisp isn't a FP language?
> >
> > Well, the obvious arguments would be that
> >
> > : functions, while pretty first class objects, reside in their own
> > namespace, and need special operators.
>
> > : iteration and side effects are not particularly discouraged, and is
> > probably as common as recursion and purity in actual code.
>
> Does that then not just make it a functional language that can be (and has
> been) 'abused'?
Why abused? Why should the "pure" functional way the best for
programming? Couldn't it be that a language which supports other
features besides functionl elements.
> People do tend to be lazy (as in water) and take the easiest path.
> Not necessarily the 'right' one.
What's the "right" way. I hardly believe something simular will exist.
> I ask the question, If Lisp is not a 'functional language', then what is
> it?
I would think Lisp among other things is a functional language.
Manuel M. T. Chakravarty
> Friedrich Dominicus <fr...@q-software-solutions.com> writes:
>
> > Could you explain why Lisp isn't a FP language?
>
> Well, the obvious arguments would be that
>
> : functions, while pretty first class objects, reside in their own
> namespace, and need special operators.
> : iteration and side effects are not particularly discouraged, and is
> probably as common as recursion and purity in actual code.
May I politely refer to the FP FAQ:
http://www.cs.nott.ac.uk/~gmh/faq.html#functional-languages
I guess that there are heaps of people on this list who have
heard this type of discussion already a million times and
are a bit wary of it.
Thank you,
Manuel
Ketil Malde
>>>> Could you explain why Lisp isn't a FP language?
>>> functions (...) reside in their own namespace
>>> iteration and side effects are not particularly discouraged
>>> (...and commonly used)
>> Does that then not just make it a functional language that can be (and has
>> been) 'abused'?
Which in a nutshell exemplifies why we have these debates. Let's
realize that whether a programming language is functional or not, is a
question of semantics, and a question of degree.
Haskell is clearly more functional than Lisp, which is more functional
than C++. On the other hand, there's no good way to agree on where
exactly to draw the line, so some people (in particular coming from
the imperative camp?) think Lisp is functional, and therefore
incomprehensible and useless, and others (coming from the functional
camp, entrenched somewhere in academia) think Lisp is imperative, and
unworthy of attention. *shrug*
> Why abused? Why should the "pure" functional way the best for
> programming? Couldn't it be that a language which supports other
> features besides functionl elements.
Indeed. Could it be that Lisp supports, yea, even encourages,
non-functional programming? Why, then, is it important to you that
it is considered a functional programming language?
> I would think Lisp among other things is a functional language.
Functional features like higher order functions are commonly used, so
Lisp is certainly not as defunctional as e.g. Pascal. Would you
consider Python a functional language?
Finally, it isn't obvious that more "functionality" in languages is
necessarily good, and I think Lisp illustrates that. I think if I had
to use one language for everything, CL would definitely be a
candidate. Of course, Haskell is so much prettier.
Friedrich Dominicus
> > programming? Couldn't it be that a language which supports other
> > features besides functionl elements.
>
> Indeed. Could it be that Lisp supports, yea, even encourages,
> non-functional programming? Why, then, is it important to you that
> it is considered a functional programming language?
It isn't so important to me. But saying Lisp isn't functional (to some
extend) is simply not true. Personally I think a nice combination of
different "paradigms" in a programming language might give a better
language. I do think that functional programming provided clear
advantags (what am I doing? this is a Haskell mailing list;-), but
it's not the end of all language development.
I am a used Eiffel programmer but I do feel that Eiffel could gain
very much from functional extensions. In fact I'm sure that a langauge
combining FP and OOP (with imperative roots) is even better than e.g
Haskell of Eiffel alone.
>
> > I would think Lisp among other things is a functional language.
>
> Functional features like higher order functions are commonly used, so
> Lisp is certainly not as defunctional as e.g. Pascal. Would you
> consider Python a functional language?
I have programmed a bit Python, but other Lisp Hackers have pointed
out that Python can be considered a FP language. But IMHO Lisp is much
more "functional" if I which than Python. But besided it's Object
System is one of the most amazing things I fouind. Lisp stands IMHO
for a degree of flexibility which is is unbeaten by any other
language.
>
> Finally, it isn't obvious that more "functionality" in languages is
> necessarily good, and I think Lisp illustrates that.
I see, that we agree to soem extend, just IMHO every language gains
from functional extensions. As I would think that Haskell could gain
much by OO-extensions (which is a bit more on-topic than Lisp here, I
guess)
>I think if I had
> to use one language for everything, CL would definitely be a
> candidate. Of course, Haskell is so much prettier.
I'm on my way learning both languages. IMO Lisp a more programmer
friendly language. I guess both are simular difficult (or easy it's a
matter of taste) to lean. And both have their special merits. But at
the moment I think Lisp is much prettier than Haskell.
Craig Dickson
California) night, so I'll just make a couple of comments...
Ketil Z. Malde wrote:
> : functions, while pretty first class objects, reside in
> their own namespace, and need special operators.
> : iteration and side effects are not particularly discouraged,
> and is probably as common as recursion and purity in actual
> code.
I agree, and would add (if I'm recalling correctly) that LISP lacks lexical
scoping, which may not be an absolute requirement for functional programming
but certainly enhances it, and is a common feature of functional languages.
Friedrich Dominicus wrote:
> But saying Lisp isn't functional (to some extend) is
> simply not true.
Well, it's that "to some exten[t]" that is the crux here, I think. If you
are going to say that LISP "is" or "is not" a functional language (an overly
simplistic, binary distinction), then you have to decide where to draw the
line between "functional languages" and other languages that may, to some
degree, include support for functional programming. LISP has much more
support for FP than C++ or Perl, but not as much as Scheme, which in turn is
less "pure" than Haskell or Erlang. So whether you want to say that it "is"
functional or not is just a matter of where you draw the line. Scheme, which
is undeniably more "functional" than LISP, is about the least purely
functional language I would call "functional". So that's where I draw the
line. Your mileage may vary.
Craig
Rainer Joswig
<c...@inversenet.com> wrote:
> I agree, and would add (if I'm recalling correctly) that LISP lacks lexical
> scoping, which may not be an absolute requirement for functional programming
> but certainly enhances it, and is a common feature of functional languages.
Common Lisp, EuLisp, Scheme, ISLisp, Dylan (and most other modern
Lisp dialects) - all these have lexical scoping. Common Lisp
also has dynamic scoping.
> Well, it's that "to some exten[t]" that is the crux here, I think. If you
> are going to say that LISP "is" or "is not" a functional language (an overly
> simplistic, binary distinction), then you have to decide where to draw the
> line between "functional languages" and other languages that may, to some
> degree, include support for functional programming. LISP has much more
> support for FP than C++ or Perl, but not as much as Scheme,
This is a common misconception.
Scheme has only one FP-related facility more compared to Common Lisp:
upward *and* downward continuations.
All other FP features from Scheme are directly available
in Common Lisp.
> which in turn is
> less "pure" than Haskell or Erlang. So whether you want to say that it "is"
> functional or not is just a matter of where you draw the line. Scheme, which
> is undeniably more "functional" than LISP,
It is not. See above.
Common Lisp does directly support three programming paradigms:
imperative, functional, object-oriented. It even encourages
the use of all these three, because a large built-in library provides
a lot of functionality in all these three paradigms. Still
FP provides largely the core ideas (functions as first class objects,
lexical scoping, closures, higher-order functions, functions
as basic building blocks, generic functions as the building blocks
for CLOS, etc.).
Haskell differs from here by:
- lazy evaluation
- different syntax with more syntactic sugar
- type system with type-inference and compile-time
type-checking
- mostly a single-paradigm language
--
Rainer Joswig, Hamburg, Germany
Email: mailto:jos...@corporate-world.lisp.de
Ralf Muschall
> I agree, and would add (if I'm recalling correctly) that LISP lacks lexical
> scoping, which may not be an absolute requirement for functional programming
Some old dead lisps might lack lexical scoping, at least CL has it
since a long time. The only places I know about where old lisps still
live are Reduce and Autocad (is this still dynamical?).
> simplistic, binary distinction), then you have to decide where to draw the
> line between "functional languages" and other languages that may, to some
I think it became impossible to draw that line since the inventors
and maintainers of dysfunctional langauges learned that FP is cool
and added closures etc. (Perl has them since 5.001m, Javascript
since 1.2, just to mention a few).
> degree, include support for functional programming. LISP has much more
> support for FP than C++ or Perl, but not as much as Scheme, which in turn is
This again is a matter of taste -- Lisp has series, which is hard to
do in scheme (the problem is not the formal behavior (this is IIRC in
SICP), but the optimizing macroexpansion (series redefines defun
etc. into codewalkers)).
Ralf
Richard
>Some old dead lisps might lack lexical scoping, at least CL has it
>since a long time. The only places I know about where old lisps still
>live are Reduce and Autocad (is this still dynamical?).
They still live in Emacs. (Emacs Lisp's variables are dynamically scoped.)
Benjamin Leon Russell
Friedrich Dominicus <fr...@q-software-solutions.com> wrote:
>
> <stuff deleted></stuff deleted>
>
> >I think if I had
> > to use one language for everything, CL would definitely
> be a
> > candidate. Of course, Haskell is so much prettier.
> I'm on my way learning both languages. IMO Lisp a more
> programmer
> friendly language. I guess both are simular difficult (or
> easy it's a
> matter of taste) to lean. And both have their special
> merits. But at
> the moment I think Lisp is much prettier than Haskell.
Well, just for the record, I've programmed in both Common LISP and Scheme, and am currently learning Haskell, but I found Scheme to be a much cleaner language than CL (so much so, in fact, that Scheme was my favorite in college, and CL was my least favorite).
Scheme is a compact language (when I studied it, it had only about 50 built-in functions); CL is a huge language (it had about 500 built-in functions). Besides, some of the semantics (closure properties, in particular) are different (sorry, but I don't have my copy of _Structure and Interpretation of Computer Programs,_ by Abelson, Sussman, & Sussman, with me right now :-) ).
The emphases placed in the courses using them were different, too: in CL, side-effects were used often; in Scheme, strict functional programming was stressed, and side-effects were rarely, if ever, used.
It just seemed that Scheme went much closer in the style of functional programming than CL--one CL course even had an optional book on object-oriented extensions to CL!
I'm not necessarily saying that this is either good or bad, but that, at least in the way it was taught, Scheme seemed more closer to the functional style of programming than CL did.
Of course, Haskell was much more functional than Scheme. The issue seemed largely a question of degree.
--Ben
--
Benjamin L. Russell
rus...@brainlink.com
benjamin.ru...@aya.yale.edu
"Furuike ya! Kawazu tobikomu mizu no oto." --Matsuo Basho
Lars Henrik Mathiesen
> Date: 16 Aug 2000 21:46:44 +0200
> "Craig Dickson" <c...@inversenet.com> writes:
> > simplistic, binary distinction), then you have to decide where to
> > draw the line between "functional languages" and other languages
> > that may, to some
>
> I think it became impossible to draw that line since the inventors
> and maintainers of dysfunctional langauges learned that FP is cool
> and added closures etc. (Perl has them since 5.001m, Javascript
> since 1.2, just to mention a few).
Yes, but in Perl at least you have to call a closure, or any function
passed as a parameter, with a different syntax than a function defined
at top level. To my taste, that's an important difference from 'real'
functional languages. (Emacs Lisp wouldn't be a functional language
either by this criterion).
Lars Mathiesen (U of Copenhagen CS Dep) <tho...@diku.dk> (Humour NOT marked)
Frank Atanassow
> > simplistic, binary distinction), then you have to decide where to draw the
> > line between "functional languages" and other languages that may, to some
>
> I think it became impossible to draw that line since the inventors
> and maintainers of dysfunctional langauges learned that FP is cool
> and added closures etc. (Perl has them since 5.001m, Javascript
> since 1.2, just to mention a few).
First, you might well include first-order (algebraic) languages in your
definition of "functional".
Second, if your language has a semantics, it is not very hard to draw a
distinction: you just have to show an appropriate embedding of
lambda-calculus.
If your language has no semantics, then you are in for a world of trouble
anyway, and the question of whether your language is (higher-order) functional
will be the least of your worries.
--
Frank Atanassow, Dept. of Computer Science, Utrecht University
Padualaan 14, PO Box 80.089, 3508 TB Utrecht, Netherlands
Tel +31 (030) 253-1012, Fax +31 (030) 251-3791
Doug Ransom
> If C# again makes it easy to write unsafe code, then in order
> to avoid the learning curve, many current C/C++ programmers
> are likely to continue programming in The Old Way. The trick
> lies in the learning curve.
>
I think you are mistakening ignorance for stupidity. It is true that C/C++
programmers like to write OO and few have any idea about functional
programming,
but very few will miss the ability to constantly shoot themselves in the
foot with uninitalized random pointers, weird memory access errors, and none
will miss spending a couple of weeks at the end of the development cycle
trying to find a memory leak.
Doug Ransom
Craig Dickson
> I think you are mistakening ignorance for stupidity. It
> is true that C/C++ programmers like to write OO and few
> have any idea about functional programming, but very few
> will miss the ability to constantly shoot themselves in
> the foot with uninitalized random pointers, weird memory
> access errors, and none will miss spending a couple of
> weeks at the end of the development cycle trying to find
> a memory leak.
With such optimism about programmers, I'm astounded that you're writing from
a .com rather than a .edu address. :-) My experience in industry has led me
to quite different conclusions. Many C/C++ programmers seem not to recognize
pointer issues as a problem, or at least, one with a viable solution; when
offered languages with built-in GC, they say things like, "I like doing my
own memory management; it gives me more control and makes it clearer what's
really going on in the program." As I pointed out in a previous message,
most of these people can't really handle the power that this "more control"
gives them, but they have a blind spot that prevents them from recognizing
that this is a problem.
Craig
Ralf Muschall
> They still live in Emacs. (Emacs Lisp's variables are dynamically scoped.)
OK. I tend to forget about this one, since I'm using it every day
(and use the macro "lexical-let" unless I am sure that no evil things
will happen).
Ralf
Andrei Errapart
[]
> With such optimism about programmers, I'm astounded that you're writing from
> a .com rather than a .edu address. :-) My experience in industry has led me
> to quite different conclusions. Many C/C++ programmers seem not to recognize
> pointer issues as a problem, or at least, one with a viable solution;
> when offered languages with built-in GC, they say things like, "I like doing my
> own memory management; it gives me more control and makes it clearer what's
> really going on in the program." As I pointed out in a previous message,
> most of these people can't really handle the power that this "more control"
> gives them, but they have a blind spot that prevents them from recognizing
> that this is a problem.
I believe that stagnacy is more widespread than creativity and logical
thinking, too :(
That said, you don't have to use pointers in C++ that much. Legacy code
can be a problem, though. Besides, I think the management should be blamed
for that, too. They should listen to programmers and pay attention to
_recurrent_ problems.
Anyway, that my-language-is-better-than-yours war is ridiculous. But it
certainly pointed out one fact: a FPL isn't the first programming language
for most FP people!
Andrei
Having worked for poor management, they no longer value their jobs.
---
Geoffrey James, "Tao of Programming".
Florian Hars
> none will miss spending a couple of weeks at the end of the
> development cycle trying to find a memory leak.
Apart from the fact that they are called space leaks, a lazy
functional language will not help them with this problem. It may
rather aggravate it by hiding the leaks in very wierd places. Show me
any working programmer who reads the "Improving laziness"-part in the
Hutton/Meijer paper on monadic parser combinators and says "Oh! What
an elegant language! And these nifty efficiency improving no-ops like
(fst (head x), snd (head x)): tail x !" (By the way, can anyone
explain this section to me?)
To cite the comments of Olof Torgersson on Haskell
(www.cs.chalmers.se/pub/users/oloft/Papers/wm96/wm96.html):
As a consequence the programmer loses control of what is really
going on and may need special tools like heap-profilers to find out
why a program consumes memory in an unexpected way. To fix the
behavior of programs the programmer may be forced to rewrite the
declarative description of the problem in some way better suited to
the particular underlying implementation. Thus, an important
feature of declarative programming may be lost -- the programmer
does not only have to be concerned with how a program is executed
but has to understand a model that is difficult to understand and
very different from the intuitive understanding of the program.
As another example, compare the propaganda version of quicksort in
Haskell with a more realistic tail recursive one.
If you want to increase the popularity of functional languages, remove
the possibility of unintended space leaks and the necessity to
make algorithms tail recursive manually (or solve the traveling
saleperson problem in O(n)). Then you will only have to overcome the
problem that most people are already hard pressed to understand
functions as mappings from real numbers to real numbers, let alone as
mappings from one function space to another.
Yours, Florian.
Reuben Thomas
> Haskell with a more realistic tail recursive one.
I remember thinking "wow!" when I first saw the Gentle Introduction
version of quicksort, then "hang on...that's not quicksort!". Whatever
happened to in-place update (one of the points of it, I thought), and can
I really be sure this will have the time behaviour I expect?
> Then you will only have to overcome the problem that most people are
> already hard pressed to understand functions as mappings from real
> numbers to real numbers, let alone as mappings from one function space
> to another.
This is a false problem, or rather, it's a question of presentation.
Most Haskell programmers know little category theory, but are quite happy
with monads. I find all sorts of problems that neophyte friends of mine
have (e.g. scientists who have to script a little for data collection and
analysis) that are down to arbitrary and stupid features of conventional
languages (C-like, BASIC-like) that would go away in a nice language (such
as Lua or Haskell; I'm not being FP-partisan here).
Personally, I find the source code for GHC much easier to read for being
written in Haskell, though of the three virtues I'm about to list, only
one is essentially FP: structurally based (pattern matching),
referentially transparent, syntactically clean. It bears a striking
resemblance to Martin Richards's BCPL compiler, written in BCPL (but my
initial reaction to the latter was "ugh, how verbose", because it's not a
style that BCPL supports elegantly; it's much better in MCPL).
--
http://sc3d.org/rrt/ | maxim, n. wisdom for fools
Doug Ransom
-----Original Message-----
From: Jacques Lemire [mailto:jacl...@sympatico.ca]
Sent: Tuesday, August 15, 2000 2:24 PM
To: haskell
Subject: The importance and relevance of FPMr Rawson wrote:=========================
However, almost no one is even thinking about FP. I think NGWS will
be the kiss of death for FP in the large -- OO just seems 90 degrees out of
phase with FP.
=========================
On the contrary, languages like C++ (and Java) and C# are full of concepts and ideas coming from FP languages.For example, the catch/try/throw construct is coming directly from Common Lisp (Lisp is a (although impure) FP language).
I would n ot be a bit suprise to see tuples, lists and cons(es) introduce in the next generation of languages.
FP languages are to VB or C++ what F1 cars are to a Chevrolet or Diesel trucks. You don't get a liter of milk with a F1 car!Moreover, OO is only one way of doing things: it is amazing the numbers of projects (and working) that are *not* programmed
with C++. If you what to see the limitations of OO and C++, take a look at the MFC, MFC architects had to introduce macros.Jacques Lemire
Manuel M. T. Chakravarty
> To cite the comments of Olof Torgersson on Haskell
> (www.cs.chalmers.se/pub/users/oloft/Papers/wm96/wm96.html):
>
> As a consequence the programmer loses control of what is really
> going on and may need special tools like heap-profilers to find out
> why a program consumes memory in an unexpected way. To fix the
> behavior of programs the programmer may be forced to rewrite the
> declarative description of the problem in some way better suited to
> the particular underlying implementation. Thus, an important
> feature of declarative programming may be lost -- the programmer
> does not only have to be concerned with how a program is executed
> but has to understand a model that is difficult to understand and
> very different from the intuitive understanding of the program.
What's the problem with using a heap profiler? Sure, heap
usage can get out of hand when writing a straight forward
maximally declarative (whatever that means) version of a
program. Is this a problem? No.
The trick about a language like Haskell is that you get to a
working prototype of your program extremely quickly. Then,
you can improve performance and, eg, use a heap profiler to
find the weak spots and rewrite them. And yes, then, I
usually lose the pure high-level view of my program in
theses places in the code.
This is still a *lot* better then not having the high-level
view at all and taking much longer to get the first working
version of my program (even if it is already more efficient
at that point). I don't know about you, but I rather have
90% of my program in a nice declarative style and rewrite
10% later to make it efficient, then having a mess
throughout 100% of the program.
Cheers,
Manuel
Tom Pledger
> [...] Show me any working programmer who reads the "Improving
> laziness"-part in the Hutton/Meijer paper on monadic parser
> combinators and says "Oh! What an elegant language! And these nifty
> efficiency improving no-ops like (fst (head x), snd (head x)): tail
> x !" (By the way, can anyone explain this section to me?)
Rather than a no-op, I prefer to think of it as a chiropractor: it
fixes up the spine.
In general, a parser may fail, which Hutton and Meijer represent by an
empty list of possible parses. However, a parser which recognises
zero or more `a's - with the help of some other parser which
recognises exactly one `a' - is infallible. It can always return
[([], s)] where s is the entire input string it was given, meaning "I
successfully found zero `a's."
The overly strict parse of zero or more `a's has this structure:
do { x <- p;
xs <- (
do { x <- p;
xs <- (
--etc.
);
return (x:xs) } +++ return []
);
return (x:xs) } +++ return []
where p is a parser which recognises exactly one `a', and p1 +++ p2
means "return the first possible parse from p1 if p1 succeeds,
otherwise the first possible parse from p2." In this case, the x <- p
part may fail (because there isn't an `a' next in the input) but the
return [] part always succeeds.
This is overly strict because the spine of the expression, which
contains all the (+++) nodes, must be evaluated before the run time
system can (reasonably be expected to) determine the outermost
data constructor in the resulting list of possible parses.
The (fst (head x), snd (head x)) : tail x construction assures the run
time system that a parser for zero or more `a's is infallible. It
works because the outermost (+++) is now of the form
Foo (_:_) +++ Foo []
instead of
Foo _ +++ Foo []
where Foo stands for some additional structure which doesn't affect
the strictness issue, and _ stands for an expression node which is not
necessarily a data constructor.
To express the same hint even more niftily, we'd need to be able to
express laws like "for all p, p +++ return [] is infallible."
Terminology: Someone more confident with the terms WHNF, closure,
suspension and thunk, could probably have used them in an explanation,
where I've resorted to waffling. If I've used terms like spine
inappropriately, will someone please say so (and explain)?
Regards,
a working Informix-4GL programmer :-)
D. Tweed
> I do believe FP is current 90 degrees out of phase with OO. I think the
> isue with tuples, lists, conses, etc. it the big problem. I currently see
> no way for someone to write a clever matrix library in Haskell and have it
> seamlessly integrate into the NGWS framework (the new object type and
> runtime system from MS likely here to stay for a long long time) and C#, VB,
> etc. The impedance mismatch is just too high.
I can't quite see why you say (at least twice) `is 90 degrees out of phase
with OO' rather than `90 degrees out of phase with lots of assumptions &
attitudes prevailing in mainstream (imperative) programming', and surely
that's the big problem? I'm just pointing this out because I do believe
that (de-hyped) OO is a useful & productive way of programming some kinds
of thing, and that both type classes and the object oriented haskell
extensions (nb: only read the reports, not actually progammed with
these firsthand) are useful for solving problems using Haskell.
However, the issue that lots of the simple & productive ideas
from FP are culturally alien & even suspect to programmers in other
languages is very true. I write lots of stuff in C++ and the fact that I
have functions returning two results return a pair<T,U> rather than either
a specially created class or a copy-into-reference-parameter, or that I
use STL vectors/lists rather than writing inplace code using
arrays/pointers elicits cries of `Yuck' & `Too weird'. And I agree that
this is a real phenomenon/problem which may well lead to Haskell remaining
a language that's scorned (in both senses) and runtime systems which make
it difficult to do simple Haskell things.
But unless I'm missing something, this has nothing in particular to do
with OO. (I may well be: I know nothing of NGWS)
___cheers,_dave________________________________________________________
www.cs.bris.ac.uk/~tweed/pi.htm|tweed's law: however many computers
email: tw...@cs.bris.ac.uk | you have, half your time is spent
work tel: (0117) 954-5250 | waiting for compilations to finish.
Claus Reinke
> Florian Hars writes:
> > efficiency improving no-ops like (fst (head x), snd (head x)): tail
> > x !" (By the way, can anyone explain this section to me?)
> The (fst (head x), snd (head x)) : tail x construction assures the run
> time system that a parser for zero or more `a's is infallible
And this extra assurance tells us that we are not exactly talking about
no-ops. Let me simplify the example a bit:
f :: (a,b) -> c
f x = .. x ..
g :: (a,b) -> (a,b)
g x = (fst x, snd x)
Both f and f.g operate on pairs - this seems to be guaranteed by the
type system. But Haskell's type system only makes a slightly weaker
guarantee for f, also referred to as partial correctness: if f's parameter
is ever successfully computed, it will be a pair. In practice, the
evaluation of f's parameter might fail to terminate, or terminate
exceptionally (outside the expected type, by throwing an exception).
In these conditions, g is not quite a no-op: it takes a parameter that
will not normally be anything other than a pair and returns a result
that will (almost) definitely be a pair (almost, because the construction
of the result could still run out of resources). This still doesn't safeguard
against resource problems or other exceptional conditions, but it does
safeguard against non-termination: if g's parameter fails to evaluate
successfully (is equivalent to bottom), then the components of g's
result will not become available, but g's result will still be a pair.
This, in turn, can have an effect on the body of f: if some computation
in f's body (that is needed for the result) depends only on the structure
of its parameter x, then the evaluation of (f x) will depend on the
evaluation of x, at least far enough to reveal the structure of x.
In contrast, the evaluation of (f (g x)), under the same dependencies,
will not require the evaluation of x, because g guarantees the structure
of x to be that of a pair. This helps to decouple the evaluation of f from
that of its parameter, without otherwise changing the dataflow. Taking
a more concrete example:
x :: (a,b) -- not quite a pair, but not anything else, either ;-)
x = x
f :: (a,b) -> IO ()
f x = case x of { (_,_) -> print "hooray!" }
i :: (a,b) -> (a,b)
i x = x
g :: (a,b) -> (a,b)
g x = (fst x, snd x)
mainA = f (i x)
mainB = f (g x)
This should demonstrate the difference between no-ops and the
kind of constructions used for program optimizations. Both i and g
are identities, as far as their types can tell us, but they differ for
things at the borderline between promised structure and computed
structure, if that makes any sense.
Statically, the type (a,b) promises a pair without any guarantee that
a pair will be computed. Operationally, (g x) promises a pair before
checking whether x actually evaluates to a pair. If it does, g is just
an identity, but if it doesn't, g delivers more information than it gets.
This is the source of the decoupling effect.
If we change f slightly,
f' :: (Show a,Show b) => (a,b) -> IO ()
f' x = case x of { (a,b) -> do {print "hooray!";print a;print b} }
(and restrict x's type, to (Bool,Bool) say,) we get an example of
how this decoupling of f' and x, via g, can influence resource usage.
In (f' x), nothing can be done in the body of f' before x evaluates to
a pair, so everything in f' has to be put on hold until the evaluation of
x starts to deliver. In (f' (g x)), on the other hand, parts of the body
can be executed, and their resources reclaimed, before the rest of
the body demands the evaluation of x.
Others have mentioned that old equation: algorithm = logic + control.
One could say that non-no-ops, such as g above, allow us to add
control information without changing a working logic.
My personal opinion in that matter is that FPLs enable us to focus
on the logic aspect, but that we have neglected to provide good
support for the other aspect of working programs. Working
heap-profilers and work on operational semantics that permit the
prediction of resource usage are good signs, showing that some
researchers are working on this second aspect.
What I'm not so sure about is how to make use of these results.
Rewriting programs to modify their control aspects mixes control
and logic aspects again. As Manuel said, that is better not having
the choice at all. But I would prefer if I could specify both aspects
separately and then specify how they are to be combined into a
working program.
> Regards,
> a working Informix-4GL programmer :-)
Ha! Living proof that there is hope for real-world programmers :-)
In rephrasing your answer, I didn't quite use all the technical terms
you expected, so perhaps there's hope for us academics as well?-)
I don't want to get into the propagandistic aspects of this thread,
but earlier instances of this discussion (yes, there have been a few)
left one important message behind:
* stop discussing why FP isn't used by others for all their projects,
* start using it yourself for the kind of projects for which it is useful
* (by now, this includes quite a large set, and it is still growing).
I did not learn Perl, for instance, because others were discussing
its qualities, but because I had some problems for which it seemed
suited. And I continued using it not because I thought it was an
elegant language, but because it was suited for those problems
and kept developing to keep up with programmer's practical needs.
I only use it for some kinds of problems, and it is certainly not the
only language I use. So why should I expect others to use FPLs
for everything, or to drop all other languages they find useful?
In this sense,
Claus
-- we could also adopt that old advertizing wisdom:
If you like what you can do with FPLs, tell your friends.
If you have any complaints about FPLs, tell their implementers.
John Hörnkvist
> On Fri, 18 Aug 2000, Doug Ransom wrote:
>
> > I do believe FP is current 90 degrees out of phase with OO. I
think the
> > isue with tuples, lists, conses, etc. it the big problem. I
currently see
> > no way for someone to write a clever matrix library in Haskell
and have it
and
> > runtime system from MS likely here to stay for a long long time)
and C#, VB,
> > etc. The impedance mismatch is just too high.
>
> I can't quite see why you say (at least twice) `is 90 degrees out
of phase
> with OO' rather than `90 degrees out of phase with lots of
assumptions &
I think there are two interpretations on what makes up an object
oriented system; the interpretation founded in Simula, and the
interpretation founded in Smalltalk. IIRC, the term object
orientation was coined by Alan Kay, in reference to Smalltalk.
The great difference between object oriented languages with static
method dispatch, like C++, and Java to some extent, and languages
with dynamic method dispatch, such as Smalltalk, Objective-C and TOM, =
is vast --- but you have to be experienced in designing for such
languages to notice the difference.
As far as I can see, using a state monad makes it possible to create
a static object oriented language within Haskell. Haskell++ is an
example of this.
However, the gap between Haskell and dynamic object oriented
languages is much greater. The existence of a universal object type
(id or Any) is central to the design paradigm of such languages ---
collections of anonymous objects would be impossible without them.
Another issue is composition, an example of which is delegation:
- (void) forwardInvocation:(NSInvocation*) invocation
{
if ([delegate respondsToSelector:[invocation selector]])
{
[invocation invokeWithTarget:delegate];
}
else
[super forwardInvocation:invocation];
}
forwardInvocation is the method which gets called when an object
gets send a message for a method that it doesn't implement. Here we
can do error handling, in this case we check if our delegate
implements the method, and in that case, we let the delegate handle
the method.
A delegate is normally typed as
id delegate;
which means that it can be an instance of any class, or
id<MyDelegateProtocol> delegate;
which means that it can be any object responding to the methods in
MyDelegateProtocol.
An example of objects using a delegate is a user interface window;
it lets the delegate get final say on actions such as closing,
resizing and so forth.
Another design pattern which becomes difficult without dynamic
dispatch and object references is notification:
[[NSNotificationCenter defaultCenter] addObserver:self
selector:@selector(handleWindowClosed:)
name:NSWindowDidCloseNotification
object:nil];
This pattern lets an object observe, and react to, the actions of
other objects without having to be directly aware of these objects.
Another example is action/target based user interface modelling:
[button setTarget:anObject action:@selector(buttonPressed:)];
Now, when pressed, the button object will invoke the buttonPressed:
method of the object referred to by anObject. Since the action/target =
information part of the state of the object, rather than part of the
program, we can trivially load user interfaces from at run time.
Dynamic dispatch also allows us to extend and amend objects without
subclassing, we can just replace one method implementation with
another at run time, as well as add methods to objects. TOM even
allows adding instance variables at run time. Of course these
abilities create new ways to wreck havoc, but it does not really
matter once you have an imperative system.
Features such as these greatly simplify the design of flexible,
loosely coupled and easily maintained systems.
Much as I like Haskell --- I write a lot of Haskell code and am very
pleased with it, for a certain set of problems --- I'd think twice
about writing a word processor in it --- although I'd consider
writing the glyph layout algorithm in it.
Haskell could conceivably replace C++ and similar languages --- it
probably comes down to improving compilers, creating a wealth of
reusable libraries, and providing cook-book solutions.
However, getting Haskell to a point where it can compete with the
ease of design of dynamic object oriented languages is another
matter. O'Haskell's reactive object's get you part of the way, but
nowhere near far enough.
Regards,
John Hörnkvist
--
ToastedMarshmallow, the perfect Cocoa companion
http://www.toastedmarshmallow.com
Frank Atanassow
> Florian Hars <flo...@hars.de> wrote,
>
> > To cite the comments of Olof Torgersson on Haskell
> > (www.cs.chalmers.se/pub/users/oloft/Papers/wm96/wm96.html):
> >
> > As a consequence the programmer loses control of what is really
> > going on and may need special tools like heap-profilers to find out
> > why a program consumes memory in an unexpected way. To fix the
> > behavior of programs the programmer may be forced to rewrite the
> > declarative description of the problem in some way better suited to
> > the particular underlying implementation. Thus, an important
> > feature of declarative programming may be lost -- the programmer
> > does not only have to be concerned with how a program is executed
> > but has to understand a model that is difficult to understand and
> > very different from the intuitive understanding of the program.
>
> What's the problem with using a heap profiler? Sure, heap
> usage can get out of hand when writing a straight forward
> maximally declarative (whatever that means) version of a
> program. Is this a problem? No.
One might argue analagously that C/C++ programmers ought to use tools like
proof assistants and model checkers to help reason about the correctness of
their programs. The fact is that, when we talk about the operational behavior
or denotational semantics of a program, any reasoning "tool" which is _in_ the
language is preferable to a tool which is _outside_ the language.
Thus, when correctness is the more important, it is better to use Haskell, the
language constructs of which encourage (partial) correctness, than it is to
use a C + a verifier; and when efficiency is more important, it is better to
use C, the language constructs of which encourage efficiency, rather than
Haskell + profiling tools.
For me, correctness is almost always paramount, but clearly some people feel
differently, or we would not be so ubiquitously plagued with buggy free and
commercial software, hardly any of which is written in declarative languages.
> The trick about a language like Haskell is that you get to a
> working prototype of your program extremely quickly. Then,
> you can improve performance and, eg, use a heap profiler to
> find the weak spots and rewrite them. And yes, then, I
> usually lose the pure high-level view of my program in
> theses places in the code.
I would rather not lose it at all, by expressing the operational behavior
which I demand in a declarative fashion. This is, IMO, part of the reason why
notions such as monads (and linearity) are valuable: they give you some
measure of control over operational details without sacrificing the "pure
high-level view".
Of course, some fiddling is always needed...
> This is still a *lot* better then not having the high-level
> view at all and taking much longer to get the first working
> version of my program (even if it is already more efficient
> at that point). I don't know about you, but I rather have
> 90% of my program in a nice declarative style and rewrite
> 10% later to make it efficient, then having a mess
> throughout 100% of the program.
A problem, as I see it, is that, although compilers like GHC do an admirable
job of optimizing away the overhead of laziness, etc. in many circumstances,
you can't be sure. You can use profiling tools and such after writing
my code, but sometimes the changes that need to be made can be far-reaching,
and you'll wish you had short-circuited this cycle in the first place.
A lot of people who program extensively in Haskell have a good
understanding of the underlying abstract machine, and can anticipate the
changes that need to be made, or at least ensure that they are
localized. For example, they know "tricks" like ways to increase laziness;
when I see messages like Florian's, I am reminded that such tricks can be
relatively obscure.
In short, the problem is that in a language such as Haskell without a
high-level abstract operational semantics, you don't see all the benefits of a
declarative style, since, as far as efficiency goes, we have only replaced the
conventional programmer's mental model of a traditional machine architecture,
with a more esoteric model which is some fuzzy idea of a lazy abstract
machine. The abstract machine may be simpler, but you still can't reason about
it in a formal way if it's not a part of the standard. The best you can do is
go off and read some papers, written by researchers for researchers, which
describe a lazy machine, and take a guess that your particular implementation
uses much the same thing. And hardly anyone will bother to go that far.
Frank Atanassow
> However, the issue that lots of the simple & productive ideas
> from FP are culturally alien & even suspect to programmers in other
> languages is very true. I write lots of stuff in C++ and the fact that I
> have functions returning two results return a pair<T,U> rather than either
> a specially created class or a copy-into-reference-parameter, or that I
> use STL vectors/lists rather than writing inplace code using
> arrays/pointers elicits cries of `Yuck' & `Too weird'. And I agree that
> this is a real phenomenon/problem which may well lead to Haskell remaining
> a language that's scorned (in both senses) and runtime systems which make
> it difficult to do simple Haskell things.
[Written with tongue only halfway in cheek.]
I disagree. "They just don't get it" doesn't cut it anymore.
Proposition
Hackers can like FP.
We give two proofs. First, a lemma.
Lemma
Hackers like weird, obscure, esoteric, complicated stuff.
Proof:
We exhibit a witness.
Consider *NIX. Now there is a big sprawling mess of complicated
interdependent gobbledygook if ever I saw one. And yet it attracts those
critters like honey.
Back to our proposition.
Proof 1:
By contradiction.
Nothing could be more obscure or esoteric to a hacker than FP. (They even
seem to admit it themselves.)
Therefore, by the lemma, hackers can potentially like FP. QED.
Proof 2:
Compared to *NIX, Haskell is cake. A simple functional language can
be axiomatized in a few lines. There are concrete rules for reasoning about
it. There are tangible implementations. That's more than enough.
Therefore, hackers can like FP. QED.
Of course, many hacker sapiens are something less than open-minded. You only
need to look at /. to convince yourself of that. But their weakness is their
fawning admiration of hacker superioris, i.e., gurus and other gung-ho
gift-giving go-getters.
Now, a guru may not know much about adjunctions or omega-CPOs, but gurus are
typically rather open-minded (cause or effect?)---if it gets results, they'll
use it. So, to convert a guru, you need to show them some concrete results. So
write some useful applications, write them fast, write them well, show them to
a guru, and show the guru how to do it too. Then you'll convert the gurus;
convert gurus, and you'll convert their flock. Convert the flock and you're
halfway home. (Just look at the recent announcements about the GNOME
Foundation.)
[Musical interlude:
You can't change the world
But you can change the facts
And when you change the facts
You change points of view
If you change points of view
You may change a vote
And when change a vote
You may change the world.
-- Depeche Mode ("New Dress")
]
And if you _can't_ convince a guru and write better programs faster, then
maybe FP isn't so good after all... unless you plan on writing all the world's
programs yourself.
Unfortunately, I don't see many FP programs that are better or faster than
conventional ones. Those that are are incestuous: things like compilers and
program analyzers for FP languages. Hackers don't need those yet. They need
things like Manuel's Gtk interface, or Daan's DB interface. Then they need to
see them in action, outperforming existing applications in some way.
Of course, IANAH (I Am Not A Hacker) so you may take my hypocritical remarks
with a grain of salt or three.
Manuel M. T. Chakravarty
I don't completely agree, because I think the situation is
not as symmetric as you pciture it. Of course, all
languages have their strengths and I personally have not the
slightest problem coding in C when I think C is more
appropriate for the job than Haskell.
However, I would claim that in your average program, rapid
prototyping and correctness first are winning over
efficiency first. I think that this position is backed by
current software engineering principles.
> > The trick about a language like Haskell is that you get to a
> > working prototype of your program extremely quickly. Then,
> > you can improve performance and, eg, use a heap profiler to
> > find the weak spots and rewrite them. And yes, then, I
> > usually lose the pure high-level view of my program in
> > theses places in the code.
>
> I would rather not lose it at all, by expressing the operational behavior
> which I demand in a declarative fashion. This is, IMO, part of the reason why
> notions such as monads (and linearity) are valuable: they give you some
> measure of control over operational details without sacrificing the "pure
> high-level view".
Nevertheless, optimising a program usually means imposing
more and more control taking into account operational
aspects of the program. I am all for expressing this
additional control as nicely as possible, but ultimately it
means breaking abstraction levels.
> > This is still a *lot* better then not having the high-level
> > view at all and taking much longer to get the first working
> > version of my program (even if it is already more efficient
> > at that point). I don't know about you, but I rather have
> > 90% of my program in a nice declarative style and rewrite
> > 10% later to make it efficient, then having a mess
> > throughout 100% of the program.
>
> A problem, as I see it, is that, although compilers like GHC do an admirable
> job of optimizing away the overhead of laziness, etc. in many circumstances,
> you can't be sure. You can use profiling tools and such after writing
> my code, but sometimes the changes that need to be made can be far-reaching,
> and you'll wish you had short-circuited this cycle in the first place.
I agree. At some point a developer with a good intuition of
where the hot spots of the program will probably be and a
forward thinking design will always win. But, I think, this
is true for every language.
> A lot of people who program extensively in Haskell have a good
> understanding of the underlying abstract machine, and can anticipate the
> changes that need to be made, or at least ensure that they are
> localized. For example, they know "tricks" like ways to increase laziness;
> when I see messages like Florian's, I am reminded that such tricks can be
> relatively obscure.
>
> In short, the problem is that in a language such as Haskell without a
> high-level abstract operational semantics, you don't see
> all the benefits of a declarative style, since, as far as
> efficiency goes, we have only replaced the conventional
> programmer's mental model of a traditional machine
> architecture, with a more esoteric model which is some
> fuzzy idea of a lazy abstract machine. The abstract
> machine may be simpler, but you still can't reason about
> it in a formal way if it's not a part of the standard. The
> best you can do is go off and read some papers, written by
> researchers for researchers, which describe a lazy
> machine, and take a guess that your particular
> implementation uses much the same thing. And hardly anyone
> will bother to go that far.
It is definitely true that this is a neglected area and that
on a much more basic level not much effort has been spent on
producing documentation that makes it easy for a casual
Haskell programmer to gain an intuition of the various
methods for improving efficiency.
Cheers,
Manuel
Tim Sweeney
to indicate isomorphism, we have (roughly):
sum of numbers ~= disjoint union of types
product numbers ~= cartesian product of types
exponentiation ~= function spaces
"sigma" summations ~= dependent products
"pi" products ~= dependent functions
successor function ~= "maybe" monad
In mathematics, there is a progression between the operators of addition,
multiplication, exponentiation, etc., known as the Ackermann hierarchy.
The next operation in the sequence is often called "tetration" and refers to
iterated exponentiation. Let us write a^b for "a raised to the power of b",
and then a-->b for b raised to its own power a times, i.e.:
1-->b = b
2-->b = b^b
3-->b = (b^b)^b
...
Now I am trying to understand the type-theory analogy to tetration. Given
"unit" as the one-valued type, "bool" as the two-valued type, "three" as the
three-valued type (isomorphic to "maybe bool"), etc., clearly:
unit-->t ~= t
bool-->t ~= t->t
three-->t ~= (t->t)->t
four-->t ~= ((t->t)->t)->t
So, what is going on here? "bool->t" is the type of identity functions on
t; "three-->t" is especially interesting because it is the type of fixpoint
operator from t->t to t.
This hints that there may be some computational utility here. Is there a
useful type-theory interpretation of tetration?
And is there a useful interpretation of tetration on infinitary types, like
lists, i.e. list(nat)-->nat? In particular, I am interested in defining the
corresponding value-level operation whose type corresponds to a tetrant. In
other words, pardoning the pecular notation, fill in the blank:
* An injection inl(123) or inr("a") is of sum type nat+string.
* A pair (123,"a") is of product type nat*string.
* A lambda \t->t+123 is of function type nat->nat.
* A ______ is of tetrant type t-->u.
-Tim
Manuel M. T. Chakravarty
> D. Tweed writes:
> > However, the issue that lots of the simple & productive ideas
> > from FP are culturally alien & even suspect to programmers in other
> > languages is very true. I write lots of stuff in C++ and the fact that I
> > have functions returning two results return a pair<T,U> rather than either
> > a specially created class or a copy-into-reference-parameter, or that I
> > use STL vectors/lists rather than writing inplace code using
> > arrays/pointers elicits cries of `Yuck' & `Too weird'. And I agree that
> > this is a real phenomenon/problem which may well lead to Haskell remaining
> > a language that's scorned (in both senses) and runtime systems which make
> > it difficult to do simple Haskell things.
>
> [Written with tongue only halfway in cheek.]
>
> I disagree. "They just don't get it" doesn't cut it anymore.
>
> Proposition
> Hackers can like FP.
[..]
> Proof 1:
> By contradiction.
>
> Nothing could be more obscure or esoteric to a hacker than FP. (They even
> seem to admit it themselves.)
I don't see the validity of this point. Especially, given
that much of todays hackerdom originated in the Lisp
communities. For example, when I talked with ESR about
programming languages, he said that one of the things he
misses in Python is fully-fledged lambda abstractions.
> Of course, many hacker sapiens are something less than open-minded. You only
> need to look at /. to convince yourself of that.
Never confuse wannabees
<http://www.tuxedo.org/~esr/jargon/html/entry/wannabee.html>
with the real thing.
> And if you _can't_ convince a guru and write better programs faster, then
> maybe FP isn't so good after all... unless you plan on writing all the world's
> programs yourself.
>
> Unfortunately, I don't see many FP programs that are better or faster than
> conventional ones. Those that are are incestuous: things like compilers and
> program analyzers for FP languages. Hackers don't need those yet. They need
> things like Manuel's Gtk interface, or Daan's DB interface. Then they need to
> see them in action, outperforming existing applications in some way.
I think, the critical thing here is not outperforming
existing applications, but saving time developing new
applications. If there is one thing a hacker hates, then it
is wasting time on doing a job that could be done more
efficiently[1] or repeatedly doing a job that could be
automated.
Manuel
[1] The exception is of course where doing the job is the
end, not a means.
Frank Atanassow
Manuel M. T. Chakravarty writes:
> Frank Atanassow <fra...@cs.uu.nl> wrote, > Proposition > Hackers can like
> FP. [..] > Proof 1: > By contradiction.
> >
> > Nothing could be more obscure or esoteric to a hacker than FP. (They
> > even seem to admit it themselves.)
>
> I don't see the validity of this point. Especially, given that much of
> todays hackerdom originated in the Lisp communities. For example, when I
> talked with ESR about programming languages, he said that one of the things
> he misses in Python is fully-fledged lambda abstractions.
I was going to mention Stallman and Emacs; but by my definition Stallman was a
guru, not a hacker...
ESR and RMS may like LISP, but clearly they aren't "converts" in the same
sense as most of the list members here; Emacs and Guile aside, most of the
code they produce seems to be in conventional languages.
I should admit that I am not one of those people who feel we should be so
gung-ho about using different languages for different purposes, i.e., it may
be impractical to do otherwise now, but it's not a state of affairs we should
be perpetuating. The differences between languages within each paradigm
(imperative, FP, LP) are not very significant. Constructing a reasonably
"universal" language in each class is not that far outside our reach. And the
distinctions between each class are starting to break down too (witness
imperative monads). Even for very domain-specific languages, there are
substantial benefits to treating them in an internal fashion, and it's
becoming increasingly practical to do so (witness combinator-style libraries).
> > Of course, many hacker sapiens are something less than open-minded. You
> > only need to look at /. to convince yourself of that.
>
> Never confuse wannabees
> <http://www.tuxedo.org/~esr/jargon/html/entry/wannabee.html> with the real
> thing.
OK, different names, same denotation. My "guru" is your "hacker"; my "hacker"
is your "wannabee". Your hackers are still in the minority, and the
proposition is that something needs to be done about convincing the masses. I
was suggesting that if you hook the gurus, then the rest will follow.
> > And if you _can't_ convince a guru and write better programs faster, then
> > maybe FP isn't so good after all... unless you plan on writing all the
> > world's programs yourself.
> [..]
> I think, the critical thing here is not outperforming existing
> applications, but saving time developing new applications. If there is one
> thing a hacker hates, then it is wasting time on doing a job that could be
> done more efficiently[1] or repeatedly doing a job that could be automated.
> [..]
> [1] The exception is of course where doing the job is the
> end, not a means.
Not if the cost in efficiency is too high. The situation isn't that black and
white. I really do believe that the imperative camp's valuation of the
correctness vs. efficiency tradeoff is different.
<rant>
Also, I've observed many FP/LP people argue that slow or memory-hungry
applications aren't such a big deal because "in 5 years, Moore's law will make
them efficient." The problem with this argument is that consumers and
programmers don't reason this way. They don't say to themselves, "Now I have a
shiny new computer, three times faster and with twice the memory of my old
one. NOW I can run functional programs!" :) They say, "Now I have a shiny new
computer, three times faster and with twice the memory of my old one. NOW I
can run twice as many applications three times as fast!" As machines get
better, program functionality also increases. "Perceived performance" seems to
remain fairly constant, if you see what I mean.
</rant>
Rapid application development is not enough. There are imperative languages
for that already: Python, Perl, Tcl... They fit into the imperative mold, and
they seem to give imperative programmers the things they want. Probably Haskell
can provide equal benefits, but to convince people to change paradigms,
you need to provide quite substantial advantages _beyond_ that.
"Extraordinary claims require extraordinary evidence."
OK, enough ranting. All this is pretty incidental to Haskell, so, for the
benefit of others who have already been put off by the recent excess of
off-topic posts, I'll reply to any replies in e-mail, and you are all free to
sling mud at me, since I probably deserve it anyway...
Ketil Malde
> Also, I've observed many FP/LP people argue that slow or memory-hungry
> applications aren't such a big deal because "in 5 years, Moore's law will make
> them efficient."
No FP people would admit to producing slow and memory-hungry
applications! :-)
YMMV, but the only functional program that I find slow enough to be
bothersome, is GHC, and it is rather complex, and anyway uses GCC (or
so I gather). Of course, I don't use that many. I do use a lot of
applications written in C++ or similar languages, though.
> They say, "Now I have a shiny new computer, three times faster and
> with twice the memory of my old one. NOW I can run twice as many
> applications three times as fast!"
No, they say "NOW I might get Word to act fast enough to be as useful
as a typewriter once was". (And then their IT guy upgrades Word.) I
bet we lose more cycles due to unintelligent software, than we do to
garbage-collectors and laziness.
And there's plenty of software just aching to be written with a FPL.
Why not start making software *smart*? Where's a grammar analyzer
that actually works? For that matter, where's a program that
understands language semantics?
Or just a mail server witout buffer overruns would be great. *Sigh*
-kzm
--
If I haven't seen further, it is by standing in the footprints of giants
Manuel M. T. Chakravarty
> Sorry, I got carried away with my silly "hacker" post.
>
> Manuel M. T. Chakravarty writes:
> > Frank Atanassow <fra...@cs.uu.nl> wrote, > Proposition > Hackers can like
> > FP. [..] > Proof 1: > By contradiction.
> > >
> > > Nothing could be more obscure or esoteric to a hacker than FP. (They
> > > even seem to admit it themselves.)
> >
> > I don't see the validity of this point. Especially, given that much of
> > todays hackerdom originated in the Lisp communities. For example, when I
> > talked with ESR about programming languages, he said that one of the things
> > he misses in Python is fully-fledged lambda abstractions.
>
> I was going to mention Stallman and Emacs; but by my
> definition Stallman was a guru, not a hacker...
I guess, the problem here is that by a hacker's definition
of a hacker, what you call a guru is a hacker - and many of
those that you call hackers are wannabees :-)
> ESR and RMS may like LISP, but clearly they aren't "converts" in the same
> sense as most of the list members here; Emacs and Guile aside, most of the
> code they produce seems to be in conventional languages.
I don't really agree with that. RMS advocates C a lot for
systems projects, but that's largely because of the
portability issues and frankly, a language like Haskell in
its current form is about as unportable as it gets (ok, VB
is worse, but that's about it).
OSS programs often use Lisp-based extension languages:
Emacs, GIMP, Gnome has Guile support, the window manager
sawfish (formerly know as sawmill), and others. Python also
gets more and more popular and it includes FP concepts. In
fact, AFIK RMS advocates writing core programs in C and
adding a Lisp-based extension language to program the rest
(like with Emacs).
> > > Of course, many hacker sapiens are something less than open-minded. You
> > > only need to look at /. to convince yourself of that.
> >
> > Never confuse wannabees
> > <http://www.tuxedo.org/~esr/jargon/html/entry/wannabee.html> with the real
> > thing.
>
> OK, different names, same denotation. My "guru" is your "hacker"; my "hacker"
> is your "wannabee". Your hackers are still in the minority, and the
> proposition is that something needs to be done about convincing the masses. I
> was suggesting that if you hook the gurus, then the rest will follow.
Ok :-)
> > > And if you _can't_ convince a guru and write better programs faster, then
> > > maybe FP isn't so good after all... unless you plan on writing all the
> > > world's programs yourself.
> > [..]
> > I think, the critical thing here is not outperforming existing
> > applications, but saving time developing new applications. If there is one
> > thing a hacker hates, then it is wasting time on doing a job that could be
> > done more efficiently[1] or repeatedly doing a job that could be automated.
> > [..]
> > [1] The exception is of course where doing the job is the
> > end, not a means.
>
> Not if the cost in efficiency is too high. The situation isn't that black and
> white. I really do believe that the imperative camp's valuation of the
> correctness vs. efficiency tradeoff is different.
>
> <rant>
> Also, I've observed many FP/LP people argue that slow or memory-hungry
> applications aren't such a big deal because "in 5 years, Moore's law will make
> them efficient." The problem with this argument is that consumers and
> programmers don't reason this way. They don't say to themselves, "Now I have a
> shiny new computer, three times faster and with twice the memory of my old
> one. NOW I can run functional programs!" :) They say, "Now I have a shiny new
> computer, three times faster and with twice the memory of my old one. NOW I
> can run twice as many applications three times as fast!" As machines get
> better, program functionality also increases. "Perceived performance" seems to
> remain fairly constant, if you see what I mean.
> </rant>
In the days of Java and Word, I think, the claim that users
expect fast programs doesn't cut it anymore. They have long
ago given up.
Nevertheless - if I understand you correctly - I agree with
the core of your statement anyway: It is time to make
Haskell a practically useful language, rather than just a
beautiful language. AFAIK now there is a substantial number
of people on this list who are working towards this goal.
Cheers,
Manuel
Jeffrey Straszhiem
> Or just a mail server witout buffer overruns would be great. *Sigh*
Just this sort of thing is so often sugested as a proving ground for
all sorts of "fringe" languages. I know it is frequently suggested on
both the Eiffel and Ada lists. Yet it never seems to get done.
I think Haskell would be perfect for this task. Perhaps for the beta
level project just focus on SMTP and local mail delivery, and not on
all the strange mail systems that sendmail endevors to cover.
Let's hear some thoughts on this.
--
-- Jeffrey Straszheim | A sufficiently advanced
-- Systems Engineer, Programmer | regular expression is
-- http://www.shadow.net/~stimuli | indistinguishable from
-- stimuli AT shadow DOT net | magic
Christian Sievers
> In mathematics, there is a progression between the operators of addition,
> multiplication, exponentiation, etc., known as the Ackermann hierarchy.
>
> The next operation in the sequence is often called "tetration" and refers to
> iterated exponentiation. Let us write a^b for "a raised to the power of b",
> and then a-->b for b raised to its own power a times, i.e.:
>
> 1-->b = b
> 2-->b = b^b
> 3-->b = (b^b)^b
> ...
This looks strange, as (b^b)^b = b^(b^2), or generally
n-->b = b^(b^(n-1)). A quick web search showed me tetration as
b ^^ 1 = b
b ^^ (n+1) = b ^ (b ^^ n)
so b^^3 = b^(b^b); clearly a more interesting (and faster growing) definition.
> Now I am trying to understand the type-theory analogy to tetration. Given
> "unit" as the one-valued type, "bool" as the two-valued type, "three" as the
> three-valued type (isomorphic to "maybe bool"), etc., clearly:
>
> unit-->t ~= t
> bool-->t ~= t->t
> three-->t ~= (t->t)->t
> four-->t ~= ((t->t)->t)->t
As b^a ~= a->b, this is still correct.
> So, what is going on here? "bool->t" is the type of identity functions on
> t; "three-->t" is especially interesting because it is the type of fixpoint
> operator from t->t to t.
>
> This hints that there may be some computational utility here. Is there a
> useful type-theory interpretation of tetration?
>
> And is there a useful interpretation of tetration on infinitary types, like
> lists, i.e. list(nat)-->nat? In particular, I am interested in defining the
Hmm. Taking nat as fixpoint of maybe, we might reason
t^^nat = t^^(fixp maybe) = t^^(1+fixp maybe) = t ^ t^^(fixp maybe) =
t ^ (t^^nat) = (t^^nat) -> t,
which reminds me vaguely to domains of untyped lambda calculus.
HTH,
Christian Sievers
Peter Douglass
> This looks strange, as (b^b)^b = b^(b^2), or generally
> n-->b = b^(b^(n-1)). A quick web search showed me tetration as
>
> b ^^ 1 = b
> b ^^ (n+1) = b ^ (b ^^ n)
>
> so b^^3 = b^(b^b); clearly a more interesting (and faster
> growing) definition.
Faster growing if and only if b > e ^ (1/e). For example if b = sqrt(2),
b^^n < 2 for all finite n>0.
--PeterD
Tim Sweeney
function f::t->u is passed a parameter of type t, returning a result of type
u. Example function calls are:
1+2
sin 3.14
map sin [1:2:3]
However, a higher-order notion of function application seems sensible in
many cases. For example, consider the following expressions, which Haskell
rejects, despite an "obvious" programmer intent:
cos+sin -- intent: \x->((cos x)+(sin x))
cos(sin) -- intent: \x->cos(sin(x))
(cos,sin)(1,2) -- intent: cos(1),sin(2)
(+)(1,2) -- intent: (+)(1)(2)
cos [1:2:3] -- intent: map cos [1:2:3]
From this intuition, let's postulate that it's possible for a compiler to
automatically accept such expressions by translating them to the more
verbose "intent" listed above, using rules such as:
1. Operator calls like (+) over functions translate to lambda abstractions
as in the "cos+sin" example.
2. A pair of functions f::t->u, g::v->w acts as a single function from pairs
to pairs, (f,g)::(t,u)->(v,w).
3. Translating function calling into function composition, like "cos(sin)".
4. Automatic currying when a pair is passed to a curried function.
5. Automatic uncurrying when a function expecting a parameter of type (t,u)
is passed a single value of type t.
6. Applying a function f:t->u to a list x::[t] translates to "map f x".
I wonder, are these rules self-consistent? Are they unambiguous in all
cases? Are there other rules we can safely add?
It also seems that every statement above is simply a new axiom at the type
checker's disposal. For example, to describe the general notion of
"cos+sin" meaning "\x->(cos(x)+sin(x))", we say:
for all types t,u,v,
for all functions f,g :: t->u,
for all functions h ::u->u->v,
h (f,g) = \x->h(f(x),g(x)).
Is this "higher order function application" a useful notion, and does any
research exist on the topic?
-Tim
Ch. A. Herrmann
Tim> 6. Applying a function f:t->u to a list x::[t] translates to
Tim> "map f x".
the problem is that we loose much of the strength the Haskell type
system provides and a lot of programming errors will remain
undetected.
What you can do is write a preprocessor that provides a
nicer syntax for you.
Cheers
--
Christoph Herrmann
E-mail: herr...@fmi.uni-passau.de
WWW: http://brahms.fmi.uni-passau.de/cl/staff/herrmann.html
Adrian Hey
On Wed 23 Aug, Tim Sweeney wrote:
> Is this "higher order function application" a useful notion,
Eeek!, no IMHO
> and does any research exist on the topic?
I suspect not, though I must admit I'm no expert on what's being researched
in the world.
What scares me about this is that even if it were possible to produce
a compiler which disambiguated such expressions using complex rules, that's
not enough. You (we) as a programmer also need to understand those rules
and apply them to make sure the program you get is what you intended.
I think its much better to stick with the philosopy of writing down exactly
what you mean. Unless your proposal enables functions to be defined which
are currently undefinable in Haskell, I'd say forget it. Sorry :-(
P.S. This is also why I'm not entirely happy with using the type system
to resolve ambiguities caused by overloading. It makes programs harder
to understand IMHO. But people who think this way seem to be in a
minority, so maybe your proposal will get the approval of somebody other
than me :-)
Regards
--
Adrian Hey
Andreas Rossberg
>
> the problem is that we loose much of the strength the Haskell type
> system provides and a lot of programming errors will remain
> undetected.
Moreover, it is completely incompatible with polymorphic typing and type
inference, because you overload notation. Consider for example a
definition like
f x y = x y
How do you want to type this if actually application syntax can mean
many different things? Using your rules, f could be typed
f :: (a -> b) -> a -> b
f :: (a -> b) -> (c -> a) -> (c -> b)
f :: (a -> b, c -> d) -> (a,c) -> (b,d)
f :: (a -> b -> c) -> (a,b) -> c
f :: (a -> b) -> [a] -> [b]
...
all of which are incompatible. Also note that operators like (+) usually
have no special status in functional languages, they are ordinary
functions. So giving them special typing rules is a bad idea. Similarly,
types like [] should have no special meaning besides being predefined.
It's better to say what you mean, overloading is your enemy! (Well, not
counting Haskell style "overloading" through type classes, which I
wouldn't call overloading in the first place.) BTW, this sort of
notational overloading used in maths has always been a good source of
confusion for students, IMHO.
All the best,
- Andreas
--
Andreas Rossberg, ross...@ps.uni-sb.de
:: be declarative. be functional. just be. ::
D. Tweed
> Tim> "map f x".
This can be done in mathematica via function attribute (Listable if my
memory is correct). IIRC It's defined by default only for functions that
only make sense on pure numbers/symbols (eg Sin) and it's very convenient
when working interactively on expressions a few levels deep. It's also one
of the things that makes building bigger programs in Mathematica a very
error prone business. I agree with the others who've said it's probably
not appropriate or implementable for a compiled, typed language like
Haskell.
Andrew Kennedy
"implicit scaling". See
S. Thatte. A type system for implicit scaling. Science of computer
programming, 17:217--245, 1991.
S. Thatte. Type inference and implicit scaling. In European Symposium on
Programming. Springer Verlag LNCS 432, 1990.
Unfortunately neither appear to be available online.
- Andrew.
> 6. Applying a function f:t->u to a list x::[t] translates to
> "map f x".
>
> I wonder, are these rules self-consistent? Are they
> unambiguous in all
> cases? Are there other rules we can safely add?
>
> It also seems that every statement above is simply a new
> axiom at the type
> checker's disposal. For example, to describe the general notion of
> "cos+sin" meaning "\x->(cos(x)+sin(x))", we say:
>
> for all types t,u,v,
> for all functions f,g :: t->u,
> for all functions h ::u->u->v,
> h (f,g) = \x->h(f(x),g(x)).
>
> Is this "higher order function application" a useful notion,
> and does any
> research exist on the topic?
>
> -Tim
>
>
Bjorn Lisper
>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
George Russell
> However, a higher-order notion of function application seems sensible in
> many cases. For example, consider the following expressions, which Haskell
> rejects, despite an "obvious" programmer intent:
A classic example: in the assignment
x := y + 2
suppose that the values x and y are declared to be references to integer. 2 is of course
an integer. Then y is implicitly dereferenced to get a pure integer. Dereferencing
can occur any number of times. Compare this with ML (using refs) or Haskell (using IORefs)
where you'd have to put a dereference to y in explicitly.
Other coercions were: you could use a value as if it were an array containing
that value; you could use a function of type (Haskell notation)
() -> A as if it were a value of type A (the function would implicitly be called)
and so on.
The rules for exactly what coercions can and can't be used exactly where in
Algol68 are extremely complicated. (There are different contexts in which
different casts are permitted.) However I used Algol68 to write quite a bit
of code about 10 years ago and I usually found that it worked as I intuitively
expected, even though I didn't understand the rules.
However in my own opinion I think that Haskell's type system and error messages
are already complicated enough; indeed probably too complicated. I would not
favour extending Haskell to allow such friendly coercions.
Christian Sievers
First of all, I was releaved to see that the definition can be
extended to
b ^^ 0 = 1
(a functional programmer's favourite number must be zero!),
or for types
void --> t ~= unit
> Now I am trying to understand the type-theory analogy to tetration. Given
> "unit" as the one-valued type, "bool" as the two-valued type, "three" as the
> three-valued type (isomorphic to "maybe bool"), etc., clearly:
I find it hard to believe that the size of a flat domain can make such
a difference. I find (), Maybe (), Maybe (Maybe ()), ..., which are
not flat, more promising candidates. (Or Void, Maybe Void, ....)
Still I doubt there can be a type constructor Tetra with
Tetra () t ~= t and
Tetra (Maybe n) t ~= (Tetra n t) -> t,
although I couldn't disprove it.
It should reflect arithmetic laws of tetration, which for example
relate (b ^^ (a1*a2)) with b^^a1 and b^^a2 or so, but are there any?
So how should (a,b)-->t be defined?
Nevertheless we can nearly do it in Haskell, it's not legal, but the
intended meaning should be clear ;-)
First of all, we use church numerals at the type constructor level -
not my idea, must have seen it in some paper:
Z :: (* -> *) -> * -> *
type Z f x = x
S :: ((* -> *) -> * -> *) -> (* -> *) -> * -> *
type S n f x = f (n f x)
Now we can define Tetra as
type Tetra t n = n (->t) ()
just as we could define (^^) as
b ^^ n = foldnat (b^) 1 n
only that the fold is already built into the numerals.
Tetra hasn't kind * -> * -> *, but has * -> ((* -> *) -> * -> *) -> *.
Now we'd have Tetra t Z = (), Tetra t (S Z) = () -> t ~= t,
Tetra t (S (S Z)) = (() -> t) -> t ~= t -> t and so on.
The problems with this are: Haskell has no kind signatures, so Z gets
kind * -> * -> *, you can't write (->t), and you can't use a type
synonym without giving all its arguments.
Still it could be instructive to ask yourself what other constructors
of kind (*->*)->*->* you might use, and what you'd get. Most
interessting should be Infinity:
type Inf f x = f (Inf f x)
(where we use x to get the correct kind) - this recursive type synonym
is even more forbidden!
> unit-->t ~= t
> bool-->t ~= t->t
> three-->t ~= (t->t)->t
> four-->t ~= ((t->t)->t)->t
>
> So, what is going on here? "bool->t" is the type of identity functions on
> t; "three-->t" is especially interesting because it is the type of fixpoint
> operator from t->t to t.
It's interesting (for those to which this wasn't obvious) to see that
there exists a recursion- und bottom-free term (this is what type
theory usually is about) of type n-->t (where n is a number) iff
n is even:
For n=2 there is id::t->t (or const id :: (() -> t) -> t, if you use
this) - or if you take my advice and start with zero, there is ()::().
Now if you have f::n-->t, then ($f) has type (n-->t)->t'->t', which is
even more general than (n+2)-->t.
We know there is no term of type t = 1-->t.
[For the following argument I first wanted to use the
Curry-Howard-Isomorphism, but then I realized I could show it
direct. Do I need it if I wanted to rigourously prove there is no term
of type t?]
Consider there were a term f of type n-->t = ((n-1)-->t) -> t with odd n>=3.
We already know there is a term h of type (n-1)-->t,
so the application f h would have type t, which is impossible.
Of course it is different if you take a fixed non-void type for t.
For example, ($0) has type (more general than) 3-->Int.
Bye,
Christian
Ralf Muschall
> > 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
But I'd look at this differently: Essentially it means to have
a typeclass Addable which is a superclass of Num and making vectors
instances of Addable. (If Fortran9x also allows multiplication,
we need no Addable and use Num directly.)
OTOH, something like this is used in Xlisp-stat, and I hate it :-)
(it does make programming harder, since I always have to think (or
even worse, to experiment) whether some function will map itself over
lists or not. (Xlisp-stat is even harder, since it uses lists as well
as vectors. As a result of this "niceness", I have to write all my
functions which might be passed as arguments to HOFs with a typecheck
in order to find out whether the system's functions (like minimizers
etc.) called them with a vector, a list, or a number).
If one really needs to add functions argumentwise in a programm, one
should IMHO use something like
data (Num b) => NumFunction a b = NumFunction (a->b)
instance (Num b) => Eq (NumFunction a b)
where
(NumFunction f) == (NumFunction g) = error "cannot eq funcs"
instance (Num b) => Show (NumFunction a b)
where
show (NumFunction f) = error "cannot show funcs"
-- one should use something smarter here
instance (Num b) => Num (NumFunction a b)
where
(NumFunction f)+(NumFunction g) = NumFunction (\x->(f x)+(g x))
(NumFunction f)*(NumFunction g) = NumFunction (\x->(f x)*(g x))
(NumFunction f)-(NumFunction g) = NumFunction (\x->(f x)-(g x))
negate (NumFunction f) = NumFunction (negate . f)
abs (NumFunction f) = NumFunction (abs . f)
signum (NumFunction f) = NumFunction (signum . f)
fromInteger x = NumFunction (\_ -> fromInteger x)
fromInt x = NumFunction (\_ -> fromInt x)
useFunc :: (Num b) => (NumFunction a b) -> a -> b
useFunc (NumFunction f) = f
-- example
h::NumFunction Double Double
h = (NumFunction cos) + (NumFunction sin)
-- useFunc h 0.7 gives 1.40905987
-- usefunc 3 4 gives 3
-- useFunc (1+h*3) 0.01 gives 4.0298495
Ralf
William Lee Irwin III
}}> 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
This is achievable in Haskell as well.
See http://holomorphy.com/~wli/scripts/FunctionAlgebra.hs
On Thu, Aug 24, 2000 at 04:04:45AM +0200, Ralf Muschall wrote:
} But I'd look at this differently: Essentially it means to have
} a typeclass Addable which is a superclass of Num and making vectors
} instances of Addable. (If Fortran9x also allows multiplication,
} we need no Addable and use Num directly.)
Well, the separation of the various operations and perhaps
making things more mathematically sensible was part of the basic algebra
proposal. The mailing list archives should give you an idea of what
issues were involved with this.
On Thu, Aug 24, 2000 at 04:04:45AM +0200, Ralf Muschall wrote:
} OTOH, something like this is used in Xlisp-stat, and I hate it :-)
} (it does make programming harder, since I always have to think (or
} even worse, to experiment) whether some function will map itself over
} lists or not. (Xlisp-stat is even harder, since it uses lists as well
} as vectors. As a result of this "niceness", I have to write all my
} functions which might be passed as arguments to HOFs with a typecheck
} in order to find out whether the system's functions (like minimizers
} etc.) called them with a vector, a list, or a number).
The system of type classes can also yield something that is also
perhaps a little confusing, and without the recourse of reflection and
dynamic whatever wizardry. See the below.
On Thu, Aug 24, 2000 at 04:04:45AM +0200, Ralf Muschall wrote:
} If one really needs to add functions argumentwise in a programm, one
} should IMHO use something like
}
}> data (Num b) => NumFunction a b = NumFunction (a->b)
[snip]
I believe I had something on the order of this in my (by now older) post
on "Function Algebra". My formulation has the advantage that a number of
other things may be done more directly. For instance:
FunctionAlgebra> (+1) + (*2) $ 3.0
10.0
FunctionAlgebra> sin + cos $ 1.0
1.38177
FunctionAlgebra> ((+) + (*) $ 1) 2
5
FunctionAlgebra> cos sin
<<function>>
FunctionAlgebra> cos sin $ 2.0
0.6143
And a disadvantage:
FunctionAlgebra> 1 2
1
FunctionAlgebra> ((+) + (*) $ 1) 2 $ 3
5
Another thing is that the transformer (a->) of kind (*->*) is irrelevant.
The only thing that matters is enough "algebraic" character getting
inherited by the result type. Witness the following:
> instance Num a => Num [a] where
> f + g = zipWith (+) f g
> f * g = zipWith (*) f g
> f - g = zipWith (-) f g
> negate f = map negate f
> abs f = map abs f
> signum f = map signum f
> fromInt i = [i]
> fromInteger n = [n]
with silly examples like
ListNumbers> [1..3] + [5..8]
[6,8,10]
ListNumbers> [2..5] * [9..12]
[18,30,44,60]
ListNumbers> -[1..10]
[-1,-2,-3,-4,-5,-6,-7,-8,-9,-10]
ListNumbers> (map (\n -> reverse [n..n^2]) [2..6]) - (map (\n -> [n..n^2]) [1..5])
[[3],[7,5,3],[13,11,9,7,5,3,1],[21,19,17,15,13,11,9,7,5,3,1,-1,-3],[31,29,27,25,23,21,19,17,15,13,11,9,7,5,3,1,-1,-3,-5,-7,-9]]
ListNumbers> reverse 2
[2]
I think we can all see where this is going.
It's generalizable to all constructors of class Functor and that are
zippable and have a unary constructor. Unfortunately, the existing
class structure makes this phenomenally difficult to do without nasties
like overlapping instances. In hugs, minus some setup code, this yields
instance (Eq (f a), Show (f a), Num a, Functor f, Zippable f, HasUnaryCon f) => Num (f a) where
f + g = fmap (uncurry (+)) $ fzip f g
f * g = fmap (uncurry (*)) $ fzip f g
f - g = fmap (uncurry (-)) $ fzip f g
negate f = fmap negate f
abs f = fmap abs f
signum f = fmap signum f
fromInteger i = unaryCon . fromInteger $ i
The nasty language feature (overlapping instances) would not be
required given some slight modifications to the Prelude, but thus far
hugs can handle this.
See http://holomorphy.com/~wli/scripts/FunctorAlgebra.hs
Cheers,
Bill
Tim Sweeney
>relate (b ^^ (a1*a2)) with b^^a1 and b^^a2 or so, but are there any?
>So how should (a,b)-->t be defined?
I couldn't find any papers on this topic, so I'm trying to work out the laws
now. The interesting ones are (a*b)^^c and (a^b)^^n. They don't seem to be
as "obvious" as the rules for exponents and products, though.
There is also a notion of "dependent tetration" which is even more
mysterious. Just as Sigma(a:t).b corresponds to "dependent sum" (with types
or numbers) and Pi(a:t).b corresponds to "dependent product", there is a
Tetra(a:t).b corresponding to "dependent tetration".
This operation is mysterious because exponentiation, the operator upon which
tetration is defined, is the first operator in the Ackermann hierarchy which
is not symmetric. So we can't just carelessly say that Tetra(a:t).f(a) =
((...->f(e2))->f(e2) where e1,e2,... are the elements of type t. The result
of Tetra(a:t).f(a) depends on the order in which we choose the elements of
t. Which begs the question: *which* order is appropriate?
Perhaps our notion of dependent products and dependent functions is
currently oversimplified, since we are neglecting this hidden "ordering"
which is implicitly involved, but can neatly be hidden because sums and
products are symmetric, up to isomorphism, i.e. a+b~=b+a and a*b~=b*a. I
wonder, are there useful types (in a type theory) for which sum and product
are not so neatly symmetric? One such construction is to apply the rules of
simple matrix algebra, but put types inside the matrices rather than
numbers. The resulting types commute: (a*b)*c~=a*(b*c) but we don't have
a*b~=b*a, since the "shape" of the resulting matrix depends on the ordered
dimensions of the inputs.
-Tim