Functional programming books for practitioners?
Rüdiger Klaehn
I am looking for a good introductory book on functional programming
for practitioners.
I am participating in a software project with a very tight schedule.
There will be many people working on that project, but I am the only
one with a functional programming background.
Under normal circumstances, I would just accept that the whole thing
will have to be object-oriented with lots of mutable state and not
expose the other participants to any functional concepts. But in this
case the resulting application is very performance critical and has to
efficiently use multiple CPU cores.
The other participants are mostly familiar with procedural and object-
oriented programming, and the whole project will be implemented in C#.
The other participants all have a science or engineering background
(the project lead is a math major), so I think there is a good chance
that they will "get" the functional programming style if it is
presented to them in the right way.
Unfortunately, due to the very tight schedule, there will always be
the temptation to just use mutable state even though it is highly
discouraged in the design guidelines. So what I need is a book for OO
programmers that shows how to solve various common problems using
functional programming.
Are there any books that could be useful in this situation?
I bought "functional data structures" from chris okasaki. It is a good
book, but not very helpful in my situation.
The various introductory books on haskell are also not very useful.
thanks in advance,
Rüdiger Klaehn
Joachim Durchholz
Most of that should be adaptable to any OO language with mutable state.
It's certainly what I found out the hard way when programming in Eiffel:
mutable objects tended to break things like proper subtype relationships
and design-by-contract.
It may help if everybody agrees on documenting preconditions and
postconditions. If C# has even modest support for DbC, go for it - even
marginal DbC efforts will immediately make bad programming practices
transparent. (Programmers will begin to feel uneasy about obscure
practices because the preconditions and postconditions will either get
unmanageable, or not capture the full semantics of a routine.)
DbC makes preconditions and postconditions percolate down the subtype
hierarchy. Even if the assertions aren't checked at runtime, they are an
excellent tool to pinpoint where exactly a subclass is not really a
subtype. If (usually non-executable) assertions like "foo is of type
BLAH or a subtype" are accepted as an argument in your group, it's
relatively easy to demonstrate the exact places where overriding a
mutable attribute breaks Liskov substitutability.
Slightly more related to what you want may be using currying. I built a
few helper functions for introducing it in PHP, but I don't think the
techniques used there can be translated to statically-typed language
like C#.
OTOH given that C# 3.0 has acquired some influences from FPLs, it may
well be that currying is supported directly anyway. (Possibly under
another name.)
I'd focus on exploiting the technique if at all possible. Set up
structures that are designed for taking up function references, and fill
them with curried function. This technique allowed me to decouple
aspects that had defied decoupling before, and with very little pain -
even in PHP!
HTH
Regards,
Jo
dbe...@eecs.wsu.edu
Press. I like it!
Also, there is an on-line book for ML by somebody at Carnege-Mellon
University, but the name escapes me just now.
An older book, using Scheme, is the famous MIT volume, "The Design and
Interpretation of Programming Languages." At one time all engineers at
MIT used this a a sophomore year textbook.
There is a book with a title somewhat similar to "OCaml for Scientists
and Engineers".
Rüdiger Klaehn
OK. Thanks for the recommendations. I ordered these books and will see
if they are useful for my colleagues.
They will definitely be interesting for myself.
cheers,
Rüdiger Klaehn
Rüdiger Klaehn
google swallowed it.
On Jun 2, 8:05 pm, Joachim Durchholz <j...@durchholz.org> wrote:
[snip]
>
> It may help if everybody agrees on documenting preconditions and
> postconditions. If C# has even modest support for DbC, go for it - even
> marginal DbC efforts will immediately make bad programming practices
> transparent. (Programmers will begin to feel uneasy about obscure
> practices because the preconditions and postconditions will either get
> unmanageable, or not capture the full semantics of a routine.)
> DbC makes preconditions and postconditions percolate down the subtype
> hierarchy. Even if the assertions aren't checked at runtime, they are an
> excellent tool to pinpoint where exactly a subclass is not really a
> subtype. If (usually non-executable) assertions like "foo is of type
> BLAH or a subtype" are accepted as an argument in your group, it's
> relatively easy to demonstrate the exact places where overriding a
> mutable attribute breaks Liskov substitutability.
>
C# does not support pre- and postconditions. But we are planning to
use debug assertions instead. I am not a big fan of language level
support for pre- and postconditions anyway.
> Slightly more related to what you want may be using currying. I built a
> few helper functions for introducing it in PHP, but I don't think the
> techniques used there can be translated to statically-typed language
> like C#.
> OTOH given that C# 3.0 has acquired some influences from FPLs, it may
> well be that currying is supported directly anyway. (Possibly under
> another name.)
> I'd focus on exploiting the technique if at all possible. Set up
> structures that are designed for taking up function references, and fill
> them with curried function. This technique allowed me to decouple
> aspects that had defied decoupling before, and with very little pain -
> even in PHP!
>
Functional programming in PHP. Never heard of that before. But why
not: functional programming is not bound to a specific language.
Anyway, currying is of course possible in C# since it supports
closures since C# 2.0. In 2.0 it is not as elegant as in haskell, but
it will have to do.
cheers,
Rüdiger
Jon Harrop
> I am looking for a good introductory book on functional programming
> for practitioners.
You may be interested in my book "OCaml for Scientists". Robert Pickering
just published "Foundations of F#", another book about a functional
programming language that is targetted at OO programmers.
You may also be interested in much of the free content on our site:
http://www.ffconsultancy.com/languages/ray_tracer/
http://www.ffconsultancy.com/ocaml/
http://www.ffconsultancy.com/dotnet/fsharp/
as well as the free content from my book (first chapter and code from
chapters on visualization with OpenGL and complete working examples from
scientific computing).
http://www.ffconsultancy.com/products/ocaml_for_scientists/
HTH.
--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?usenet
Rüdiger Klaehn
> Rüdiger Klaehn wrote:
> > I am looking for a good introductory book on functional programming
> > for practitioners.
>
> You may be interested in my book "OCaml for Scientists". Robert Pickering
> just published "Foundations of F#", another book about a functional
> programming language that is targetted at OO programmers.
>
> You may also be interested in much of the free content on our site:
>
> http://www.ffconsultancy.com/languages/ray_tracer/
> http://www.ffconsultancy.com/ocaml/
> http://www.ffconsultancy.com/dotnet/fsharp/
>
> as well as the free content from my book (first chapter and code from
> chapters on visualization with OpenGL and complete working examples from
> scientific computing).
>
> http://www.ffconsultancy.com/products/ocaml_for_scientists/
>
I am not familiar with OCaml. I started getting interested in FP when
I discovered Clean a few years ago. At that time I was very much into
game programming, and I thought that functional programming is only
relevant for academic computer science problems. But the beauty and
performance of clean just blew me away. It was like a relevation.
Unfortunately it is still an niche language even though uniqueness
typing is IMHO much easier to understand for procedural programmers
than monads.
For the time being, I will have to live with C# even though I am
somewhat unhappy with some aspects the language and with the CLR
performance. But maybe I should give OCaml/F# a try.
cheers,
Rüdiger
Joachim Durchholz
> C# does not support pre- and postconditions. But we are planning to
> use debug assertions instead. I am not a big fan of language level
> support for pre- and postconditions anyway.
I can say from personal practice that language-supported preconditions
and postconditions can give invaluable help:
* They help catch errors before they start to propagate. (That's what
assertions do, too.)
* They document your code, in a conciseness that's unattainable
otherwise. (Assertions are worse. Any doctool won't easily know which
assertions are just paranoia and which are documenting a precondition or
postcondition. Could be handled via conventions for the doctool, of
course; I see it rarely done though, for whatever reason.)
* They nudge programmers towards better code: writing sloppy code means
you have to write more preconditions to delinate the boundaries within
which is will work, which in turn means that not only you lose the
advantages of being sloppy (you're forced to write more preconditions),
you also get to see the consequences of your sloppiness. (With
assertions, you'd need a doctool-based culture of documenting your
code's preconditions and postconditions. Usually fails because not
properly supported by the doctool.)
* In an OO context, I found them to be one of the sharpest tools
available to discriminate what exactly breaks a subtyping relationship:
no more handwaving and arguing what "programmers would expect the
subclass here", but simply stating "the subtype does not guarantee
postcondition foo in such-and-those conditions" and everybody can verify
this immediately (saves *hours* of fruitless discussion). (Same as
previous point: few if any projects properly document assumptions on
preconditions.)
The main difference between debug assertions and pre/postcondition
checking is that pre/postconditions can be considered part of a
function's call interface, just as important as parameter and result types.
In fact parameter and result type declarations are just a special case
of pre/postcondition, automatically validated at compile time.
> Functional programming in PHP. Never heard of that before.
Me neither. Actually I built everything myself.
It turned out to be surprisingly simple to implement, less than 20 lines
of code :-)
> But why
> not: functional programming is not bound to a specific language.
Well, it's still a far cry from the Real Thing.
Regards,
Jo
Rüdiger Klaehn
just do not think that it is good language design to have a little
sublanguage just to describe pre- and postconditions.
Given a language with a sufficiently powerful type system, it should
be possible to express pre- and postconditions using the type system.
For a simple example: when a function may not return null, define the
return type in such a way that null is not a valid value. If a
function expects two parameters a and b where a<=b, define a type
OrderedPair or something to express that.
Of course most mainstream languages have relatively primitive type
systems that make it very hard to express pre- and postconditions that
way.
> > Functional programming in PHP. Never heard of that before.
>
> Me neither. Actually I built everything myself.
> It turned out to be surprisingly simple to implement, less than 20 lines
> of code :-)
>
> > But why
>
> > not: functional programming is not bound to a specific language.
>
> Well, it's still a far cry from the Real Thing.
>
C# is quite a bit closer to a functional language than php, but it is
still quite limited. But in the real world, you sometimes have to live
with these inconveniences.
I will have to implement some interesting hacks in C# to make a
functional style possible for the other project participants.
For example, I implemented something like implicit world passing using
a thread-local "world state". That way the other project participants
can use property setters and under the hood it is still fully
functional and thread-safe.
In a way, it is an interesting challenge to work around the
limitations of a language that way.
> Regards,
> Jo
Regards,
Rüdiger
Neelakantan Krishnaswami
Joachim Durchholz <j...@durchholz.org> wrote:
>
> * They document your code, in a conciseness that's unattainable
> otherwise. (Assertions are worse. Any doctool won't easily know
> which assertions are just paranoia and which are documenting a
> precondition or postcondition. Could be handled via conventions for
> the doctool, of course; I see it rarely done though, for whatever
> reason.)
I don't know C# well, but if C# allows you to put annotations on
assertions, then you can perhaps write a small tool to extract them
and put them into your documentation.
--
Neel R. Krishnaswami
ne...@cs.cmu.edu
Joachim Durchholz
> I am not opposed to the concept of pre- and postconditions per se. I
> just do not think that it is good language design to have a little
> sublanguage just to describe pre- and postconditions.
>
> Given a language with a sufficiently powerful type system, it should
> be possible to express pre- and postconditions using the type system.
If the type system is powerful enough, it's just a sublanguage
describing conditions on values. The two concepts converge at some point.
> For a simple example: when a function may not return null, define the
> return type in such a way that null is not a valid value. If a
> function expects two parameters a and b where a<=b, define a type
> OrderedPair or something to express that.
>
> Of course most mainstream languages have relatively primitive type
> systems that make it very hard to express pre- and postconditions that
> way.
Try expressing that kind of stuff even with Haskell's or SML's type system.
It's actually possible, but too complicated to be very useful to the
standard programmer. (Try serving the "this is a square matrix" type to
the average programmer who's supposed to submit data of the right type
to the matrix routine...)
> C# is quite a bit closer to a functional language than php, but it is
> still quite limited.
Not a real surprise, I'd say ;-)
> But in the real world, you sometimes have to live
> with these inconveniences.
That's just reality.
> In a way, it is an interesting challenge to work around the
> limitations of a language that way.
Exactly :-)
Regards,
Jo
Joachim Durchholz
> I don't know C# well, but if C# allows you to put annotations on
> assertions, then you can perhaps write a small tool to extract them
> and put them into your documentation.
Problem is: few people want to write documentation tools if the real
task is something else.
Regards,
Jo
dbe...@eecs.wsu.edu
web. I would be interested in your review, especially of part 3.
Rüdiger Klaehn
> Rüdiger Klaehn schrieb:
[snip]
>
> > For a simple example: when a function may not return null, define the
> > return type in such a way that null is not a valid value. If a
> > function expects two parameters a and b where a<=b, define a type
> > OrderedPair or something to express that.
>
> > Of course most mainstream languages have relatively primitive type
> > systems that make it very hard to express pre- and postconditions that
> > way.
>
> Try expressing that kind of stuff even with Haskell's or SML's type system.
> It's actually possible, but too complicated to be very useful to the
> standard programmer. (Try serving the "this is a square matrix" type to
> the average programmer who's supposed to submit data of the right type
> to the matrix routine...)
>
I do not mean to express the actual conditions using the type system.
I would just use the type system to distinguish between data that
matches a pre/postcondition and data that does not, and to give the
pre/postcondition a name.
In the case of the matrix, I would just define a type SquareMatrix
inheriting from Matrix, and check the square rule in the constructor.
Then I would define an explicit conversion from Matrix to
SquareMatrix. A method that works only on square matrices would take a
SquareMatrix as an argument. Most of the operations on SquareMatrix
would of course again return SquareMatrix objects.
If somebody has a non-square matrix and wants to use it as an argument
for a function that takes a square matrix, he will have to do an
explicit cast. That will immediately notify him of the precondition
and also document the code.
But that requires a language where you can easily create subtypes from
all types including "primitive" types like double etc.
> > C# is quite a bit closer to a functional language than php, but it is
> > still quite limited.
>
> Not a real surprise, I'd say ;-)
>
It is really not that bad. A bit verbose compared to real functional
languages, and the type system is comparatively primitive. But I would
rather work on an interesting problem using a boring language than to
work on a boring problem using an interesting language :-)
cheers,
Rüdiger
Joachim Durchholz
> On Jun 3, 11:46 pm, Joachim Durchholz <j...@durchholz.org> wrote:
>> Rüdiger Klaehn schrieb:
>
> [snip]
>>> For a simple example: when a function may not return null, define the
>>> return type in such a way that null is not a valid value. If a
>>> function expects two parameters a and b where a<=b, define a type
>>> OrderedPair or something to express that.
>>> Of course most mainstream languages have relatively primitive type
>>> systems that make it very hard to express pre- and postconditions that
>>> way.
>> Try expressing that kind of stuff even with Haskell's or SML's type system.
>> It's actually possible, but too complicated to be very useful to the
>> standard programmer. (Try serving the "this is a square matrix" type to
>> the average programmer who's supposed to submit data of the right type
>> to the matrix routine...)
>>
> I do not mean to express the actual conditions using the type system.
> I would just use the type system to distinguish between data that
> matches a pre/postcondition and data that does not, and to give the
> pre/postcondition a name.
If you follow that path to its logical end, you'll get a separate type
for each precondition and postcondition in the system, which is clearly
unmanageable.
So you have to draw the line somewhere - what goes into types, and what
goes into assertions.
And those conditions that don't go into types become assertions.
A more concrete example may be in order.
Let's consider the real numbers.
The the square root function says "no negative numbers" as a
precondition on its parameter.
The logarithm says "no nonpositive numbers".
The gamma function says "no nonpositive integral numbers".
Division says "anything but zero" on its second parameters.
Now - which of these preconditions should be types, which should be
assertions?
Making all of them into types won't work well. Consider
gamma_of_negative x = - gamma x
which would require a new type (all numbers except integral nonnegative
ones) just because you used the gamma function in an unexpected context.
You could, of course, redefine all arithmetic operators for that type -
but what of
gamma (15 - x)
? Potentially a new type for every real number?
It's just as bad for structured data, such as trees and graphs. And I'm
not even mentioning the proliferation of ad-hoc types that inhabit every
application program.
You *do* have to draw the line somewhere. There are lots and lots of
conditions where turning them into types is simply overengineering.
> But that requires a language where you can easily create subtypes from
> all types including "primitive" types like double etc.
If integer ranges are involved, this includes a language where the type
system has the full power of reasoning over integers.
In other words, the type checker would necessarily be undecidable.
That's no different from an assertion checker that's undecidable - the
two concepts unify somewhere on that road anyway.
I think types are just a way of giving a set of preconditions (and
postconditions) a convenient name, and for those cases where such a set
of assertions doesn't warrant a convenient name, writing them down
directly is the way to go.
Well, language design wise. With real-world, existing languages, you
have stick with wherever the language draws the line between types and
assertions.
>>> C# is quite a bit closer to a functional language than php, but it is
>>> still quite limited.
>> Not a real surprise, I'd say ;-)
>>
> It is really not that bad. A bit verbose compared to real functional
> languages, and the type system is comparatively primitive. But I would
> rather work on an interesting problem using a boring language than to
> work on a boring problem using an interesting language :-)
Definitely!
Regards,
Jo
Joshua Dunfield
>If integer ranges are involved, this includes a language where the type
>system has the full power of reasoning over integers.
>In other words, the type checker would necessarily be undecidable.
It might be worth pointing out that it *is* decidable if the integer
expressions are linear, as in Hongwei Xi's DML (which can also
express your `square matrix' invariant, without any obscure phantom
types).
>
>That's no different from an assertion checker that's undecidable - the
>two concepts unify somewhere on that road anyway.
Well, with typechecking, an answer of "it typechecks" means the program
satisfies the specification (subject to the typechecker being correct,
etc.), or rather, the part of the specification expressible in the type
system. With something like ESC, an answer of "no bugs found" means
just that: ESC didn't *find* any violations of the specification
(or that part of it expressible in ESC's assertion language), it doesn't
mean no bugs exist. Just as with runtime assertion checking, if you run
your program on a big test suite and no assertion fails, it doesn't mean
the assertions won't fail on some other input.
Even in Cayenne, where typechecking times out if the dependent
typechecking gets "too hard", *if* it doesn't time out you can take
the answer to the bank, which you can't in something like ESC.
So I think there is a significant difference; I'm not sure the concepts
can be unified.
Just to be clear, I'm not saying that makes typechecking always
superior (tempting as it is, since that's what I work on): you can
get a richer spec language if you "throw off the shackles of soundness"
(I believe that's the phrase used in one of the ESC papers).
Best,
-j.