BASIC as a Haskell DSL (2009) | Hacker News Reader

BASIC as a Haskell DSL (2009)

augustss.blogspot.com

58 pointstel12 comments

Open articleView on HN

Source code and docs:

http://hackage.haskell.org/package/BASIC-0.1.5.0

Scala BASIC DSL: http://www.scala-lang.org/old/node/1403

Some more background to this:

http://blog.fogus.me/2009/03/26/baysick-a-scala-dsl-implemen...

I wonder what domain would BASIC be specific with? :)

The domain of beginner's all-purpose symbolic instruction code.

Obvious use of mutable arrays? And making "spaghetti code."

Very funny. But there are actually quite a few very nice versions of basic that you could write enormous programs with reasonable structure in, and a number of those appeared very long ago (For instance, GFA basic on the Atari ST and BBC Basic for the BBC Micro).

Not that that is in any way relevant to the version of BASIC on display here, but there was no reason to implement a crappy basic, they could have done it with a decent version as well. (but that would have been a lot more work).

I know that the Goto isn't necessary but I believe that the implementor demonstrated Gotos exactly to prove that even that can be done in Haskell. The "decent" constructs were probably easier to implement in Haskell.

I'm personally honestly totally impressed with what the author did because I've learned a lot, not actually using Haskell myself. It's a good demonstration of what is possible, especially when the generated code is shown. I'm one of those that only care for performance, and according to one comment the generated code seem to be even better than the one produced by idiomatic Haskell:

"Don Stewart said...

And the assembly we get from GHC with just the obvious recursive implementation in Haskell,

    go:
     comisd .LC0(%rip), %xmm5
     jb .L4
     movapd %xmm6, %xmm5
     jmp *(%rbp)
    .L4:
     movsd .LC1(%rip), %xmm0
     movapd %xmm0, %xmm7
     divsd %xmm5, %xmm7
     addsd %xmm0, %xmm5
     addsd %xmm7, %xmm6
     jmp go

The one made from the Basic source by Haskell as cited by the article author is obviously better:

    LBB1_1: ## _L4
        movsd   LCPI1_0, %xmm2
        movapd  %xmm1, %xmm3
        addsd   %xmm2, %xmm3
        ucomisd LCPI1_1, %xmm3
        divsd   %xmm1, %xmm2
        addsd   %xmm2, %xmm0
        movapd  %xmm3, %xmm1
        jne     LBB1_1  ## _L4

So it seems using Basic idioms in Haskell is still a bit more effective than using the Haskell idioms in Haskell. Or more poignantly "the spaghetti code in Haskell is faster than the idiomatic Haskell." That was the starting point of my former comment.

I'd still welcome the comments from the language implementors.

That was the case in 2009. GHC 7.8.3 is doing better now for regular Haskell code in the loop.

    main :: IO ()
    main = do
      let go :: Double -> Double -> Double
          go !i !s
            | i < 100000000 = go (i+1) (s + 1/i)
            | otherwise = s
      printf "Almost infinity is %g\n" (go 1 0)

Inner loop assembly:

    LBB0_4:                                 ## %c3Sk
      movaps	%xmm3, %xmm0
      divsd	%xmm1, %xmm0
      addsd	%xmm3, %xmm1
      ucomisd	%xmm1, %xmm4
      addsd	%xmm2, %xmm0
      movaps	%xmm0, %xmm2
      ja	LBB0_4
      jmp	LBB0_2

I think thats the best of both worlds. You can write really nice and clean code (the default) while still having the ability to "get ugly" (for performance reasons) if you really need to.

Then it seems confirmed that something like Basic in Haskell is actually useful. Imagine, once when everybody learns Haskell as the first language, "advanced" books will teach people BASIC. In Haskell. Or maybe the compiler will get even better.

Still, the educational value of the Basic in Haskell is huge for me. I thank Augustsson.

There is a wide gulf between beautiful Haskell and Basic-in-Haskell. There ate more direct techniques to optimize recursive logic, including (as another commenter notes) waiting a few years for someone to improve the compiler itself.

Reply on news.ycombinator.com