The post mentions motivation being symbolic differentiation.
Let me instead advocate auto differentiaton. It enables writing mathematical expressions as normal programs, is less error prone for the programmer, is well defined at every valid point in the derivative, and is better at using sharing when computing higher order derivatives. An excellent library for this is, called ad, is available in Haskell.
edit2: I should also add that MOST auto differentiation libraries also have a problem of not being able to distinguish the differential/ epsilon used in two independent derivative calculations, and this can lead to subtle / large numerical errors.
The AD library uses some haskell type system cleverness to prevent users from making that mistake!
Good tip in general. Symbolic differentiation was McCarthy's motivation in 1960. My own motivation was nothing more sophisticated than "I wonder how much Haskell can look like M-expressions, without resorting to Template Haskell?"
The M-Expression in the post is rather limited in what it can do; if anyone is looking for a system for use in practical mathematical modelling, during my PhD research I created a system for expressing ODE / DAE models in Haskell, and a solver which uses symbolic/numeric techniques (including symbolic differentiation) to solve them.
Is this what people really do? The post itself is interesting, but does it really take a mailing list request to get interesting things to show up on the front page?
Some people apparently ask for votes, and some people apparently have voting rings.
On the other hand, during last year y submitted ~20 stories and probably ~4 of them were popular enough to reach the front page. But I never asked people to vote, they get to the front page alone.
Interesting that you can achieve such a close correspondence.
I know Lisp loves lists, but it's a bit strange to insist on them in Haskell when you could have replaced [ and ] with ( and ) and achieved a whole lot of type safety whilst preserving the semantics.
I wasn't insisting on lists, but on square brackets, to match McCarthy's syntax. This golf game has strict rules!
If we drop the brackets we may as well go the whole way and use curried functions, in which case the diff function looks like:
diff y x =
atom y → (eq y x → ONE $ ZERO) $
eq (car y) PLUS →
cons PLUS (maplist (cdr y) (\z -> diff (car z) x)) $
eq (car y) TIMES →
cons PLUS (maplist (cdr y)
(\z -> cons TIMES
(maplist (cdr y)
(\w -> z /= w → car w $
diff (car w) x)))) $
error ("Unexpected term" ++ show y)
What do you mean? Nothing in that post is related to Lisp parenthesis syntax. It is a post about expressing a custom mathematical syntax in valid Haskell.
(Which is obviously a clever game and not a meaningful endorsement of the syntax, since statement syntax is not the point of McCarthy's paper.)
I mean that the Haskell version is not anywhere close to being type safe. If you change almost all of the [] to () you can achieve a great deal of type safety at no extra cost. Having said that, there's still a lot of low-hanging type safety fruit remaining! (I also took the liberty of removing Lambda, which was redundant).
diff (y, x) =
atom (y) → (eq (y, x) → ONE $ ZERO) $
eq (car (y), PLUS) →
cons (PLUS, maplist (cdr (y), \z -> diff (car (z), x))) $
eq (car (y), TIMES) →
cons (PLUS, maplist (cdr (y),
\z ->
cons (TIMES,
maplist (cdr (y),
\w ->
z /= w → car (w) $
diff (car (w), x))))) $
error ("Unexpected term" ++ show y)
mctest1 = diff (List [TIMES, X, List [PLUS, X, A], Y], X)
data SExpr = ZERO | ONE | PLUS | TIMES | X | A | Y
| List [SExpr]
deriving (Eq, Show)
car (List t) = head t
car _ = error "car of non-pair"
cdr (List t) = List (tail t)
cdr _ = error "cdr of non-pair"
cons (h, List t) = List (h : t)
cons _ = error "cons with non-list" -- our lists aren't pairs
atom (List _) = False
atom _ = True
eq (x, y) = x == y
maplist (List x, f) = List (ml x)
where ml [] = []
ml x@(_:t) = f (List x) : ml t
infixl 1 →
(→) :: Bool -> a -> a -> a
(→) True x _ = x
(→) False _ y = y
Let me instead advocate auto differentiaton. It enables writing mathematical expressions as normal programs, is less error prone for the programmer, is well defined at every valid point in the derivative, and is better at using sharing when computing higher order derivatives. An excellent library for this is, called ad, is available in Haskell.
edit: link to package is http://hackage.haskell.org/package/ad/
edit2: I should also add that MOST auto differentiation libraries also have a problem of not being able to distinguish the differential/ epsilon used in two independent derivative calculations, and this can lead to subtle / large numerical errors.
The AD library uses some haskell type system cleverness to prevent users from making that mistake!
a nice exposition of this problem can be found in this excellent blog post http://conway.rutgers.edu/~ccshan/wiki/blog/posts/Differenti...