Hacker News new | past | comments | ask | show | jobs | submit login
M-Expressions in Haskell (groups.google.com)
143 points by galabad on Mar 30, 2013 | hide | past | web | favorite | 16 comments

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.

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...

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?"

neat code golf reason! :)

btw, I've been to some of the recent LispNYC events, have you been to recent ones?

I live about two hours away, more by public transport, and don't get in to the city much. I'll try to make a meeting in 2013...

Let me advocate something even more interesting.

Take Haskell type, formally find its derivative, notice this new type is useful for traversing the original one and (optionally) explode your head.

(They call it zipper)

I just implemented a tree library using zippers without knowing this. Thanks for pointing this out.... .... .... shutdown initiated.

Zippers are really awesome data structures indeed. More people should use them. (But not for numerical computation)

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.

My RealExpression definition (I also define BoolExpression) is here https://github.com/A1kmm/modml-core/blob/master/ModML/Core/B...

Code to symbolically differentiate a RealExpression is here https://github.com/A1kmm/modml-solver/blob/master/ModML/Solv...

Documented here: Chapters 9 & 10 of https://researchspace.auckland.ac.nz/bitstream/handle/2292/8... [3.3 MB PDF]

"I submitted the post to Hacker news, if we mod it up to at least 20 points it may get on the front page:

https://news.ycombinator.com/newest "

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?

Meh, I'm not surprised. There's too much noise on Hacker News. Just keep your eye on the new submissions to see this.

If they don't, this[1] is the result.

[1] https://news.ycombinator.com/item?id=5449154

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

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact