Is there any way to make this Haskell program faster?

Question

Mind the following Haskell program:

-- Lambda Calculus ADT
data Term = Fun (Term -> Term) | Num !Double
instance Show Term where
    show (Num x) = "(Num "++(if fromIntegral (floor x) == x then show (floor x) else show x)++")"
    show (Fun _) = "(<function>)"

-- Lambda Calculus term application
(#) :: Term -> Term -> Term
(Fun f) # x = f x
infixl 0 # 

-- We have floats as primitives for performance
float_toChurch :: Term
float_toChurch = Fun (\ (Num n) -> Fun (\f -> Fun (\x -> 
    if n <= 0 
        then x 
        else (f # (float_toChurch # (Num (n - 1)) # f # x)))))

float_add :: Term
float_add = Fun (\ (Num x) -> Fun (\ (Num y) -> Num (x + y)))

-- Function compiled from the Lambda Calculus.
-- It sums all nats from 0 til a number.
sum_til :: Term
sum_til = (Fun(\v0->((((((float_toChurch # v0) # (Fun(\v1->(Fun(\v2->(Fun(\v3->(Fun(\v4->((v3 # v2) # (((v1 # ((float_add # v2) # (Num 1))) # v3) # v4))))))))))) # (Fun(\v1->(Fun(\v2->(Fun(\v3->v3))))))) # (Num 0)) # (Fun(\v1->(Fun(\v2->((float_add # v2) # v1)))))) # (Num 0))))

-- Testing it
main = do
    let n = 512*512*8
    print $ (sum_til # (Num n))

Since there is no fast lambda calculator around, I'm using the strategy above to compile terms of the Untyped Lambda Calculus to Haskell in order to evaluate them fast. I'm impressed with the performance: that program creates a list of numbers from 0 to 2097152 and sums them all in less than a second on my computer. That is much faster than I expected - only 4 times slower than a Haskell direct equivalent - and sufficient to be useful for my goals. Yet, notice that I had to wrap functions and terms under the Fun/Num constructors in order to satisfy the type system. That boxing is probably not ideal. So, my question is: is it possible to run the same Lambda Calculus program and get the same result even faster? I.e., any way to remove the boxing? (Also, it doesn't need to use Haskell.)

Uh nothing, guess I added it by mistake. `Num !Double` is important, though - basically doubles the performance. — MaiaVictor, Apr 29 '15 at 13:10

score 4 · Accepted Answer · answered Apr 29 '15 at 13:22

4

I don't think you can keep Double and avoid wrapping. I think the closest you can get would be just

newtype Term = Term (Term -> Term)

But that's going to make arithmetic massively slower, I would imagine.

The only other thing I can think of is maybe trying to cache previous results to avoid recomputing them (but that could easily be slower, not faster).

I am curious to know what on Earth you've actually "using" this for though. ;-)

answered Apr 29 '15 at 13:22

MathematicalOrchid

61,854
19
123
220

tl;dr I'm just programming on the LC because I'm more productive on it than in Haskell. I dealt with untyped languages all my life and never had a problem, so that's how I'm used to do it, I guess. I love the idea of FP and see how the type system is useful for some, but day by day I've been [struggling against it](http://stackoverflow.com/questions/29879944/why-haskell-doesnt-accept-my-combinatoric-zip-definition), so I gave up. (And please don't mention Scheme.) – MaiaVictor Apr 29 '15 at 13:37
Anyway, are you sure about that? I heard well placed "unsafeCoerce"s could solve it. – MaiaVictor Apr 29 '15 at 13:38
2

Using `unsafeCoerce` will definitely make your program *compile*. The problem is that it is impossible, at run-time, to figure out what's a `Double` and what's a function. To know that, you have to — you know — store that information. – MathematicalOrchid Apr 29 '15 at 14:30
It isn't like (say) JavaScript where everything gets auto-converted. If you use `unsafeCoerce` to make your code compile, then your program will almost certainly segfault as soon as you run it. – MathematicalOrchid Apr 29 '15 at 14:31
1

Side note: I have the opposite problem to you. Whenever I use untyped languages, it always goes horribly wrong. ;-) – MathematicalOrchid Apr 29 '15 at 15:33
Right? I still don't understand what is wrong with me but I gave like an year of chance and it just doesn't work. I once remade the engine of a big Nintendo game in 5 days on JavaScript, yet I couldn't create a pong in a week in Haskell. And that's not about FP - I reinvented a huge part of Prelude in less than a week on LC. The types hate me, man. Go figure. – MaiaVictor Apr 29 '15 at 15:46
The thing I hate the most is when I get stuck for hours trying to decipher a type error and in the end the code was fine - I just needed to do some type-level hackery for it to work. That zip function I just posted on my last question is an example, and trust me, that happens **a lot**. I like to program things more generically than Haskell can handle trivially, and I'm not smart enough to explain it to the type system. – MaiaVictor Apr 29 '15 at 15:50

Is there any way to make this Haskell program faster?

1 Answers1