开发者

How do functional languages model side-effects?

Sinc开发者_开发技巧e side-effects break referential transparency, don't they go against the point of functional languages?


There are two techniques that are used by purely functional programming languages to model side effects:

1) A world type that represents external state, where each value of that type is guaranteed by the type system to be used only once.

In a language that uses this approach the function print and read might have the types (string, world) -> world and world -> (string, world) respectively.

They might be used like this:

let main w =
  let w1 = print ("What's your name?", w) in
  let (name, w2) = read w1 in
  let w3 = print ("Your name is " ^ name, w2) in
  w3

But not like this:

let main w =
  let w1 = print ("What's your name?", w) in
  let (name, w2) = read w in
  let w3 = print ("Your name is " ^ name, w2) in
  w3

(because w is used twice)

All built-in functions with side-effects would take and return a world value. Since all functions with side-effects are either built-ins or call other functions with side-effects, this means that all functions with side-effects need to take and return a world.

This way it is not possible to call a function with side-effects twice with the same arguments and referential transparency is not violated.

2) An IO monad where all operations with side effects have to be executed inside that monad.

With this approach all operations with side effects would have type io something. For example print would be a function with type string -> io unit and read would have type io string.

The only way to access the value of performing operation would be to use the "monadic bind" operation (called >>= in haskell for example) with the IO operation as one argument and a function describing what to do with the result as the other operand.

The example from above would look like this with monadic IO:

let main =
  (print "What's your name?") >>=
  (lambda () -> read >>=
  (lambda name -> print ("Your name is " ^ name)))


There are several options available to handle I/O in a functional language.

  • Don't be pure. Many functional languages aren't purely functional. It's more that they support functional programming rather than enforcing it. This is by far the most common solution to the problem of I/O in functional programming. (Examples: Lisp, Scheme, Standard ML, Erlang, etc.)
  • Stream transformation. Early Haskell I/O was done this way. Check my link below for details if you want more information. (Hint: you probably don't.)
  • Continuation-passing I/O (the "world-passing" mentioned in other answers). In this one you pass a token of data around with your I/O that acts as the necessary "different value" to keep referential integrity alive. This is used by several ML dialects if memory serves.
  • The "continuation" or "world" thing above can be wrapped in various data types, the most (in)famous being the use of monads in this role in Haskell. Note that this is, notionally, the same thing under the covers, but the tedium of keeping track of "world"/"continuation" state variables is removed.

There's a research dissertation that exhaustively analyses these.

Functional I/O is an ongoing field of research and there are other languages which address this issue in interesting and mind-mangling ways. Hoare logic is put to use in some research languages. Others (like Mercury) use uniqueness typing. Still others (like Clean) use effect systems. Of these I have a very, very limited exposure to Mercury only, so I can't really comment on details. There's a paper that details Clean's I/O system in depth, however, if you're interested in that direction.


To the best of my understanding, if you want to have side effects in a functional language, you have to code them explicitly.


Since side-effects break referential transparency, don't they go against the point of functional languages?

It depends on the functional language:

  • Standard ML allows the liberal use of side-effects like most procedural languages e.g. Fortran, Algol, Pascal, C, etc.

  • Haskell restricts side-effects through the use of abstract data types like IO, ST and STM, which helps to preserve referential transparency.

  • Clean also restricts side-effects, but does this with its extended type system.

  • The functional language Coq uses - Gallina - provides no access to side-effects at all.


How do functional languages model side-effects?

One approach which isn't regularly mentioned relies on pseudo-data: individual single-use abstract values conveyed in an accessible structured value (commonly a tree), with the side effects only occuring when each abstract value is initially used. For more information, see F. Warren Burton's Nondeterminism with Referential Transparency in Functional Programming Language. An working example can also be found in GHC: its Unique name-supply type.

But if the extra parameters needed to make pseudo-data work is just too annoying, it is actually possible to usefully combine I/O and its observable effects with non-strict semantics...if you don't really need referential transparency.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜