6 ms·

> functions are functions in the algebraic sense This is a minor nit, but there are effects in pure Haskell functions, namely partiality and non-termination. (

by cscheid 13y ago

> functions are functions in the algebraic sense This is a minor nit, but there are effects in pure Haskell functions, namely partiality and non-termination. (In other words, the sense in which "functions are functions" is actually a deep question) There's plenty of academic discussions on how to solve this problem. See stuff like this: http://lambda-the-ultimate.org/node/2003 http://lambda-the-ultimate.org/node/2003

stevepike 13y ago
Non-termination makes perfect sense, but would you mind sharing a layman explanation of what you mean by the effects of partiality?
- nandemo 13y ago
  Roughly speaking, partial functions are functions that might crash -- or that might throw exceptions, if you prefer. So even if it always terminates, it might to do so at the cost of not returning a value of the expected type. A bit more precisely, a partial function is a function that is not defined for some values of its domain (its input). A well-known instance is the division operator, which is not defined when the divisor is zero. Other common examples are head and last: -- this promises to receive a list of elements of some type t and return the first element head :: [t] -> t head (first:rest) = first head [] = error "that list has no head, yo!" Where error is analogous to throwing an unchecked Throwable (eg RuntimeException) in Java. One solution is to use a safer version that returns Maybe a instead of a. This is analogous to using checked exceptions. safeHead :: [a] -> Maybe a safeHead (first:rest) = Just first safeHead [] = Nothing The solution above is common and idiomatic. Another option is to accept only arguments of a different list type that's guaranteed to be non-empty.
nandemo 13y ago
Your link is a good example of partiality: > user error: Table './ltu/cache' is marked as crashed and should be repaired query: SELECT data, created, headers FROM cache WHERE cid = 'filter:4:37963a22e3cdd6b501519c657a75ceeb' in /home/vhost/ltu/www/includes/database.mysql.inc on line 66.
efnx 13y ago
I always thought that algebraic functions are not guaranteed to be defined given certain parameters. It's just that perfectly algebraic functions don't throw errors, they silently return +-infinity. Like the asymptotes in `tan x`.
- anon4 13y ago
  To be pedantic, tan doesn't have a value at tau/4 (or pi/2, if you swing that way). Also, algebraic functions don't return, they are - cos(0) is 1, it doesn't return 1, it doesn't compute 1, it is not a kind of computer, nor a kind of program, nor any kind of thing that consumes resources and time and returns a value; it really literally is 1. Algebraic functions are just syntactic notation. You can sit down and convert from one notation to another, like how cos(5) is a number quite close to 0.28366218546322625, and deriving one representation from the other does take resources and time, because it's a physical process performed by a person or computer. But sin, cos, tan, cotan, log and all their friends by themselves don't compute, they are just a different kind of notation for numbers. Which is why I find the desire to make functions in programming like algebraic functions silly - by definition they are two completely different things. One is a specification for a process that produces binary-encoded numbers, the other is a syntactic notation for real numbers.
  - nzp 13y ago
    I upvoted you because I think this is an interesting line of reasoning, but I disagree that it's a very useful one. You seem to be implicitly defining "computation" as that which a physical computer does (machines, biological brains...). Something that literally consumes physical resources. By that logic, a Turing machine is not a computer and lambda calculus is not about computation. As I said, you could spin the semantics that way but is it useful? Does that give us useful insights? Functions are not just syntactic notation. Functions are, by definition, mappings from set A to set B. They don't have anything to do with notation. "cos(x)" is merely a notation, yes, but not of a number but of a function. This is an important distinction. "cos(5)" evaluates to a certain number, yes, but it's not just syntactic sugar for that number. Not to mention that functions don't need to operate on sets of numbers.
pinealservo 13y ago
The Haskell language is described in The Haskell Report via an informal presentation of its denotational semantics. Its types are all "lifted" from Sets to something like Scott Domains to account for partiality and non-termination, which are denoted by the value called "bottom" or _|_. So, they are not strictly functions in the normal set-theoretic sense, but they are (mostly?) mathematically accurate continuous functions between Scott Domains. As the semantics are not formally defined, there is a limit to what you can say about them, but there is an interesting paper entitled "Fast and Loose Reasoning is Morally Correct" that shows that treating Haskell as if it worked in terms of total set-theoretic functions is a reasonable thing to do in some practical circumstances in the use of Haskell. If you want really pure, total set-theoretic functions in a programming language, you will have to go to a total functional language such as Coq or Agda. You lose Turing-completeness when you stick to total functions, though, and most people only type-check their functions rather than actually running them (this is not as crazy as it sounds--these languages are primarily used to help formulate formal proofs, which are finished when they pass the type-checker). In any case, the bit in the blog about FORTRAN and everything conflating procedures and algebraic functions strikes me as nonsense, at least without further explanation to clarify/justify it.

by cscheid 13y ago

stevepike 13y ago

Non-termination makes perfect sense, but would you mind sharing a layman explanation of what you mean by the effects of partiality?

nandemo 13y ago
Roughly speaking, partial functions are functions that might crash -- or that might throw exceptions, if you prefer. So even if it always terminates, it might to do so at the cost of not returning a value of the expected type. A bit more precisely, a partial function is a function that is not defined for some values of its domain (its input). A well-known instance is the division operator, which is not defined when the divisor is zero. Other common examples are head and last: -- this promises to receive a list of elements of some type t and return the first element head :: [t] -> t head (first:rest) = first head [] = error "that list has no head, yo!" Where error is analogous to throwing an unchecked Throwable (eg RuntimeException) in Java. One solution is to use a safer version that returns Maybe a instead of a. This is analogous to using checked exceptions. safeHead :: [a] -> Maybe a safeHead (first:rest) = Just first safeHead [] = Nothing The solution above is common and idiomatic. Another option is to accept only arguments of a different list type that's guaranteed to be non-empty.

nandemo 13y ago

Your link is a good example of partiality: > user error: Table './ltu/cache' is marked as crashed and should be repaired query: SELECT data, created, headers FROM cache WHERE cid = 'filter:4:37963a22e3cdd6b501519c657a75ceeb' in /home/vhost/ltu/www/includes/database.mysql.inc on line 66.

efnx 13y ago

I always thought that algebraic functions are not guaranteed to be defined given certain parameters. It's just that perfectly algebraic functions don't throw errors, they silently return +-infinity. Like the asymptotes in `tan x`.

anon4 13y ago
To be pedantic, tan doesn't have a value at tau/4 (or pi/2, if you swing that way). Also, algebraic functions don't return, they are - cos(0) is 1, it doesn't return 1, it doesn't compute 1, it is not a kind of computer, nor a kind of program, nor any kind of thing that consumes resources and time and returns a value; it really literally is 1. Algebraic functions are just syntactic notation. You can sit down and convert from one notation to another, like how cos(5) is a number quite close to 0.28366218546322625, and deriving one representation from the other does take resources and time, because it's a physical process performed by a person or computer. But sin, cos, tan, cotan, log and all their friends by themselves don't compute, they are just a different kind of notation for numbers. Which is why I find the desire to make functions in programming like algebraic functions silly - by definition they are two completely different things. One is a specification for a process that produces binary-encoded numbers, the other is a syntactic notation for real numbers.
- nzp 13y ago
  I upvoted you because I think this is an interesting line of reasoning, but I disagree that it's a very useful one. You seem to be implicitly defining "computation" as that which a physical computer does (machines, biological brains...). Something that literally consumes physical resources. By that logic, a Turing machine is not a computer and lambda calculus is not about computation. As I said, you could spin the semantics that way but is it useful? Does that give us useful insights? Functions are not just syntactic notation. Functions are, by definition, mappings from set A to set B. They don't have anything to do with notation. "cos(x)" is merely a notation, yes, but not of a number but of a function. This is an important distinction. "cos(5)" evaluates to a certain number, yes, but it's not just syntactic sugar for that number. Not to mention that functions don't need to operate on sets of numbers.

pinealservo 13y ago

The Haskell language is described in The Haskell Report via an informal presentation of its denotational semantics. Its types are all "lifted" from Sets to something like Scott Domains to account for partiality and non-termination, which are denoted by the value called "bottom" or _|_. So, they are not strictly functions in the normal set-theoretic sense, but they are (mostly?) mathematically accurate continuous functions between Scott Domains. As the semantics are not formally defined, there is a limit to what you can say about them, but there is an interesting paper entitled "Fast and Loose Reasoning is Morally Correct" that shows that treating Haskell as if it worked in terms of total set-theoretic functions is a reasonable thing to do in some practical circumstances in the use of Haskell. If you want really pure, total set-theoretic functions in a programming language, you will have to go to a total functional language such as Coq or Agda. You lose Turing-completeness when you stick to total functions, though, and most people only type-check their functions rather than actually running them (this is not as crazy as it sounds--these languages are primarily used to help formulate formal proofs, which are finished when they pass the type-checker). In any case, the bit in the blog about FORTRAN and everything conflating procedures and algebraic functions strikes me as nonsense, at least without further explanation to clarify/justify it.