Inspirations & experiments, mainly about denotative/functional programming in Haskell
I’ve heard from a few people that my blog’s RSS feeds were broken. I just upgraded my blog to WordPress 2.9.1, which appears to have fixed the problem with RSS generation.
If you notice any problems with RSS or anything else, please let me know.
There is a lot of confusion about the meaning of “functional” and “declarative” as descriptions of programming languages and paradigms. For instance, Haskell is sometimes advertised as a “purely functional programming language” and other times as “the world’s finest imperative programming language”. I added some playful confusion (and clarity, I hope) with my post The C language is purely functional.
I still regularly hear people ask and disagree about whether Haskell’s monadic I/O is “functional”. I would say yes in one (technical) sense of “functional”. But not the same sense in which we say “functional programming has simple, precise semantics” or “functional programming has good compositional properties” or “functional programming is good for reasoning about”. Monadic I/O is a clever trick for encapsulating sequential, imperative computation, so that it can “do no evil” to the part that really does have precise semantics and good compositional properties.
It’s because of this confusion that I’ve started using the more specific term “denotational programming” in my blog subtitle and elsewhere, as an alternative to what I used to call “functional programming”. While there are other notions of “functional”, applicable even to monadic IO, I think “denotational” captures the fundamental and far-reaching benefits that we called “good for reasoning about” and “powerfully compositional”.
When I bash monadic I/O, my real complaint isn’t with the technical invention–which I like. Rather, I’m cranky about confusion and misleading communication, and about distraction from what we originally meant by “functional programming”–from what I call “denotational programming”.
I don’t mind that we haven’t yet been liberated from the von Neumann model. As long as remember we haven’t.
As long as we keep on searching.
This post describes an idea I’ve had in mind for years and have chatted about with friends but haven’t written down before.
Functional programmers used to worry about how to solve “the I/O problem”. Functional programming (FP) eschews any notion of side-effect or order of execution, and instead has an order-independent notion of evaluation. In contrast, input & output (I/O) seems to be an inherently effectful, ordered notion.
For a long time, I’ve been dissatisfied with the current Haskell solution to “the I/O problem”. Of course it’s very clever and effective. With “monadic IO” we can program both functionally and imperatively, and the imperative semantics doesn’t compromise the functional semantics.
I look at monadic IO not as any solution to functional I/O, but rather as a (clever) way not to bring I/O into the functional world. There’s a ton of confusion buzzing around monadic IO, so let me try to restate more carefully: “monadic IO” is a way to generate imperative computations (not just I/O) without having to say anything at all about the semantic content of those computations. Rather than retooling our mental habits completely away from the imperative model of computation, monadic IO is a way to hang onto these old mental habits, and use them in a hybrid functional/imperative programming style, in which the imperative doesn’t contaminate the functional, semantically.
John Backus offered us a gift and a blessing in his 1977 Turing Award lecture, Can Programming Be Liberated from the von Neumann Style? A functional style and its algebra of programs. He told us how the sequential/imperative model enslaves us in weak thoughts, inhibiting manageable scaling (sections 1 through 5.1). In the abstract, Backus says
Conventional programming languages are growing ever more enormous, but not stronger. Inherent defects at the most basic level cause them to be both fat and weak: their primitive word-at-a-time style of programming inherited from their common ancestor–the von Neumann computer, their close coupling of semantics to state transitions, their division of programming into a world of expressions and a world of statements, their inability to effectively use powerful combining forms for building new programs from existing ones, and their lack of useful mathematical properties for reasoning about programs.
As well, Backus showed one way to throw off the shackles of this mental and expressive slavery — how to liberate our notions of programming by leaving the von Newmann mental model behind.
Haskell is often described as a “purely functional programming language”, and in a technical sense it is. (In good company, too; see The C language is purely functional.) However, as commonly practiced, imperative computation still plays a significant role in most Haskell programs. Although monadic IO is wily enough to keep a good chunk of purity in our model, Haskell programmers still use the imperative model as well and therefore have to cope with the same fundamental difficulties that Backus told us about. In a sense, we’re essentially still programming in Fortran, with its mixture of statements and expressions (or, semantically, of commands and values). Don’t get me wrong; Haskell is a much better Fortran than the original. (If you have an urge to inform me how monadic IO works, re-read what I’m really saying. Honestly, I know.)
(Sadly, the very definition of “program” in Haskell requires that there be a main of type IO ()!
Haskell programs thus cannot be purely functional (except technically), and so cannot be composed except very weakly, as Backus describes.
For an alternative model, see
Tangible Functional Programming: a modern marriage of usability and composability.)
In a sense, I see us as in a worse position than before. Since the adoption of monadic IO, it’s been less immediately apparent that we’re still enslaved, so there’s been much less activity in searching for the promised land that the prophet JB foretold. Our current home is not painful enough to goad us onward, as were continuation-based I/O and stream-based I/O. (See A History of Haskell, section 7.1.) Nor does it fully liberate us.
Since I/O is an intrisically sequential, effectful notion, and we need some way of doing input & output, perhaps the best we can do is what we’ve done with monadic I/O: support both imperative and functional programming and proctect the functional from the imperative.
Or can we do better?
Continue reading ‘Can functional programming be liberated from the von Neumann paradigm?’ »
Ever since ActiveVRML, the model we’ve been using in functional reactive programming (FRP) for interactive behaviors is (T->a) -> (T->b), for dynamic (time-varying) input of type a and dynamic output of type b (where T is time).
In “Classic FRP” formulations (including ActiveVRML, Fran & Reactive), there is a “behavior” abstraction whose denotation is a function of time.
Interactive behaviors are then modeled as host language (e.g., Haskell) functions between behaviors.
Problems with this formulation are described in Why classic FRP does not fit interactive behavior.
These same problems motivated “Arrowized FRP”.
In Arrowized FRP, behaviors (renamed “signals”) are purely conceptual.
They are part of the semantic model but do not have any realization in the programming interface.
Instead, the abstraction is a signal transformer, SF a b, whose semantics is (T->a) -> (T->b).
See Genuinely Functional User Interfaces and Functional Reactive Programming, Continued.
Whether in its classic or arrowized embodiment, I’ve been growing uncomfortable with this semantic model of functions between time functions. A few weeks ago, I realized that one source of discomfort is that this model is mostly junk.
This post contains some partially formed thoughts about how to eliminate the junk (“garbage collect the semantics”), and what might remain.
Continue reading ‘Garbage collecting the semantics of FRP’ »
When people talk, especially via the Internet, I expect misunderstandings, since human language is so fraught with ambiguity. And though I work very hard at clarity, I know my skill is limited and I sometimes fail.
So I see communication as an iterative process: I say something that you don’t quite get, and you say “Huh?” about the what or why or how of some particular part, and I refine my message. Likewise, I listen to you, and check out the places were I’m puzzled.
I’m very sensitive where I think I’m seeing criticisms/dismissals without inquiry/curiosity, and hence some peevishness in some remarks (now edited) in my previous post, Why program with continuous time?. See Fostering creativity by relinquishing the obvious for related remarks.
In some venues, like reddit, aggressive non-inquiry can become the dominant mode of discussion. Because I prefer high-quality, open-minded inquiry, I mostly choose moderated blogging instead. If I don’t pass a comment through, I’ll usually offer the writer some suggestions, perhaps suggesting a possible misreading of whatever was being responded to, and invite re-submission. If I’m particularly annoyed with the writer, I’ll usually take time to get over my annoyance before responding, so there can be a delay.
In this way, I try to keep a high signal-to-noise ratio, where noise includes assumptions, reactions to misreadings, and often compounded public attempts by people to get each other to listen more carefully.
I’m starting to discover that people I don’t get along with sometimes have a very different style from mine. I like to invite many possibilities into a space and explore them. My mother shared with me a quote from Henry Nelson Wieman, which she now uses as her email signature:
To get the viewpoint of the other person appreciatively and profoundly and reconcile it with his own so far as possible is the supreme achievement of man and his highest vocation.
While I’m agnostic about the “supreme/highest” part (and open to it), I very much like Wieman’s description of individual and collective learning as progressing most powerfully by integrating different viewpoints, as founded on working to understanding each other “appreciatively and profoundly”.
I’m learning that some other folks have an oppositional style of learning and discovering.
When Thomas (Bob) Davie and I worked together in Antwerp, he told me that his style is to fiercely resist (battle) any new idea proposed to him. Whatever breaks through his defenses is worth his learning. I was flabbergasted at the distance between his style and mine. And greatly relieved also, because I had to work with him, and I had previously interpreted his behavior as non-curious and even anti-creative. Although I wasn’t willing to collaborate in the battle mode at the time, fortunately he was willing to try shifting his style. And the recognition of our differing style toward similar ends helped greatly in relieving the building tension between us. Now I enjoy him very much.
Since this surprising discovery, I’ve wondered how often friction I have with other people coincides with this particular difference in personal styles and whether there are additional style that I hadn’t been aware of. So when friction arises, I now try to find out, via a private chat or email.
Edits:
Is program proving a viable and useful endeavor? Does it create more problems than it solves?
Today I participated in a reddit discussion thread. The discussion brought up some issues I care about, and I think others will care also.
Although I’m quoting from another person whose viewpoint may contrast with mine, I mean no insult or disrespect to him. I think his views are fairly common, and I appreciate his putting them into writing and stimulating me to put some of mine into writing as well.
[…] you could specify the behavior it should have precisely. However in this case (and in most practical cases that aren’t tricky algorithms actually) the mathematical spec is not much shorter than the implementation. So meeting the spec does not help, the spec is just as likely to be wrong/incomplete as the implementation. With wrong/incomplete I mean that even if you meet the spec you don’t attain your goal.
I like the observation that precise specifications can be as complex and difficult to get correct as precise programs.
And indeed specification complexity is problematic.
Rather than give up on precision, my own interest is in finding simpler and clearer ways to think about things so that specifications can be quite simple.
Thus my focus on simple and precise semantic models.
One example is as given in Push-pull functional reactive programming.
I’m proud of the simplicity of this specification and of how clearly it shows what parts of the model could use improving.
(The Event type doesn’t follow the type class morphism principle, and indeed has difficulty in practice.)
And since such semantics-based software design methods are still in their infancy, I agree that it’s usually more practical to abandon preciseness in software development.
For more examples of formally simple specifications, see the papers Denotational design with type class morphisms and Beautiful differentiation.
I suspect the crux of the issue here is that combining precision and simplicity is very difficult — whether for specifications or programs (or for many other other human endeavors).
Any intelligent fool can make things bigger and more complex … it takes a touch of genius — and a lot of courage — to move in the opposite direction. – Albert Einstein
We had been writing informal/imprecise “programs” for a long time before computers were invented, as various kinds of instructions/recipies. With mechanization of program handling in the 1940s came the requirement of precision. Since simple precision is difficult (according to my hypothesis), and precision is required, simplicity usually loses out. So our history of executably-precise programs is populated mostly by complexity.
I conclude that there are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is make it so complicated that there are no obvious deficiencies. The first method is far more difficult. – C.A.R. Hoare, The Emperor’s Old Clothes, Turing Award lecture, 1980
As much as one assumes that the future is bound to perpetuate the past, one might believe that we will never escape complexity. In my own creative process, I like to distinguish between the notion of necessarily true and merely historically true. I understand progress itself to be about this distinction — the overturning of the historically true that turns out (often surprisingly) not to be necessarily true.
What about specification? Are precise specifications necessarily complex, or merely historically complex? (I.e., must we sit by while the future repeats the complexity of the past?) This question I see as even more unexplored than the same question for programs, because we have not been required to work with formal specifications nearly as much as with formal programs. Even so, some people have chosen to work on precise specification and so some progress has been made in improving their simplicity, and I’m optimistic about the future. Optimistic enough to devote some of my life energy to the search.
Simplicity is the most difficult thing to secure in this world; it is the last limit of experience and the last effort of genius. – George Sand
Everything is vague to a degree you do not realize till you have tried to make it precise. – Bertrand Russell
I expect that future software developers will look back on our era as barbaric, the way we look at some of the medical practices of the past. Of course, we’re doing the best we know how, just as past medical practitioners were.
I know people are apt to hear criticism/insult whether present or not, and I hope that these words of mine are not heard as such. I appreciate both the current practitioners, doing their best with tools at hand, and the pioneer, groping toward the methods of the future. Personally, I play both roles, and I’m guessing you do as well, perhaps differing only in balance. I urge us all to appreciate and respect each other more as we muddle on.
For me functional reactive programming (FRP) has been mainly about two principles.
One is denotational design (i.e., based on simple, precise denotational semantics), which has been integral to FRP since the first incarnation as ActiveVRML. I’ve written several things recently about denotational design.
My second core principle is continuous time, which has been present since Fran & ActiveVRML’s predecessor TBAG.
Today I read a confusion that I’ve heard many times before about continuous time, which I’d like to bring up, in part because I love continuous time, and in part because there’s a much broader underlying principle of software design.
[…] I don’t see why the lack of continuous streams leaves a “gap”. In the end all streams are discrete.
“In the end”, yes. Just as in the end, numbers are displayed as ascii numerals. However, programming is more about the middle than the end, i.e., more about composition than about output. For that reason, we don’t generally use strings in place of numbers. If we did, composition operations (arithmetic) would be very awkward. Similarly, continuity in space and in time is better for composition/modularity, leaving discreteness to the output step.
Another name for “continuous” is “resolution-independent”, and thus able to be transformed in time and space with ease and without propagating and amplifying sampling artifacts.
As another example, consider the data types in a 3D graphics API. In the end, all graphics is pixels, isn’t it? So what gap is left in a pixel-oriented API that doesn’t address higher-level continuous notions like triangles or curved surfaces? (Hint: it’s not just speed.)
One could go further than strings and pixels, and say that “in the end” my data types will end up as phosphors or electrical impulses, so programming at those levels is perfectly adequate. Again, composability would suffer.
Another example is functional vs imperative programming. It’s all side-effects in the end. Functional programming excels in composability, as explained and illustrated by John Hughes in Why Functional Programming Matters. And I’m not just talking about pure functional programming, but the availability of compound expressions, as introduced in Fortran (controversially), despite that machines just execute sequences of atomic, side-effecting statements in the end.
Another example, and really the heart of John’s paper, is finite vs infinite data structures. We only access a finite amount of data in the end. However, allowing infinite data structures in the middle makes for a much more composable programming style.
Some unsolicited advice to us all: Next time you see someone doing something and you don’t understand their underlying motivation, ask them. Many issues are not immediately obvious, so don’t be shy! Reading papers can help as well.
For more on continuous time:
Edits:
This post describes a simple way to integrate a function over an interval and get an exact answer. The question came out of another one, which is how to optimally render a continuous-space image onto a discrete array of pixels.
For anti-aliasing, I’ll make two simplying assumptions (to be revisited):
The average of a function over a region (here a continuous image over a 2D interval) is equal to the integral of the function across the region divided by the size (area for 2D) of the region. Since our regions are simple squares, the average and the integral can each be defined easily in terms of the other (dividing or multiplying by the size).
To simplify the problem further, I’ll consider one-dimensional integration, i.e., integrating a function of R over a 1D interval.
My solution below involves the least upper bound operator I’ve written about (and its specialization unamb).
The central question for me in designing software is always
What does it mean?
With functional programming, this question is especially crisp. For each data type I define, I want to have a precise and simple mathematical model. (For instance, my model for behavior is function-of-time, and my model of images is function-of-2D-space.) Every operation on the type is also given a meaning in terms of that semantic model.
This specification process, which is denotational semantics applied to data types, provides a basis for
For an example (2D images), some motivation of this process, and discussion, see Luke Palmer’s post Semantic Design. See also my posts on the idea and use of type class morphisms, which provide additional structure to denotational design.
In spring of 2008, I started working on a functional 3D library, FieldTrip. I’ve designed functional 3D libraries before as part of TBAG, ActiveVRML, and Fran. This time I wanted a semantics-based design, for all of the reasons given above. As always, I want a model that is
For 3D, I also want the model to be GPU-friendly, i.e., to execute well on (modern) GPUs and to give access to their abilities.
I hadn’t thought of or heard a model that I was happy with, and so I didn’t have the sort of firm ground I like to stand on in working on FieldTrip. Last February, such a model occurred to me. I’ve had this blog post mostly written since then. Recently, I’ve been focused on functional 3D again for GPU-based rendering, and then Sean McDirmid posed a similar question, which got me thinking again.
Part one of this series introduced the problem of memoizing functions involving polymorphic recursion. The caching data structures used in memoization typically handle only one type of argument at a time. For instance, one can have finite maps of differing types, but each concrete finite map holds just one type of key and one type of value.
I extended memoization to handle polymorphic recursion by using an existential type together with a reified type of types. This extension works (afaik), but it is restricted to a particular form for the type of the polymorphic function being memoized, namely
-- Polymorphic function
type k :--> v = forall a. HasType a => k a -> v a
My motivating example is a GADT-based representation of typed lambda calculus, and some of the functions I want to memoize do not fit the pattern. After writing part one, I fooled around and found that I could transform these awkwardly typed polymorphic functions into isomorphic form that does indeed fit the restricted pattern of polymorphic types I can handle.
Continue reading ‘Memoizing polymorphic functions – part two’ »