Thursday, May 5, 2016

DDC 0.4.2 -- the "almost useful" release

DDC 0.4.2 was pushed to Hackage a few days ago. Running "cabal update; cabal install ddc-tools" should build it. You'll need a version of the LLVM tools in your path. LLVM 3.4 - 3.8 (the current release) should work.

Code generation and runtime system support for higher order functions is finished. The type checker also now automatically inserts the run and box casts which were mentioned a few posts ago. Release notes are on the github page.

The programs we can compile are starting to look "almost useful". For example, here is some code from the AlmostPrimes example, which I adapted from Rosetta Code:

-- | A stream of k-almost-prime numbers.
kPrimes (k: Nat#): Stream Nat# Nat#
 = sfilter (isKPrime k) (senumFrom 2) 

-- | Check if some number is k-almost-prime.
isKPrime (k n: Nat#): Bool#
 | k == 1       
 = isPrime n

 | otherwise    
 = sany $ smap       (isKPrime (k - 1))
        $ smap       fst
        $ sfilter    (eq 0 ∘ snd)
        $ smap       (divMod n)
        $ stakeWhile (λx: Nat#. x < n)
        $ primes 2

main (_: Unit): S Console Unit
 = do   forS (enumFromTo 1 5)
         (λk: Nat#. 
          do    write $ "k = " % showNat k % ": "
                forS (listOfStream $ stake 10 $ kPrimes k)
                        (λx: Nat#. write $ showNat x % " ")
                write "\n")

The full example code is here

Note that Nat# is the type of a primitive natural number. The # just means "primitive" which is not the same as "unboxed" as per GHC. The hashes will go away once I implement type synonyms and can define a nicer synonym. The example invokes some standard stream combinators, smap, sfilter and so on. The forS function is like mapM, but using the Disciple effect system instead of monads. The type of forS is:
forS : List a -> (a -> S e Unit) -> S e Unit
S e Unit is the type of a suspended computation with effect e which returns a value of type Unit when evaluated. I'm calling this the "almost useful" release because because we still need to finish the garbage collector, as well as desugaring for nested patterns, before I could imagine writing anything substantial in it. Late last year Jacob Stanley was working on the transform to insert GC slot handling into core programs, but the runtime support still needs to be implemented. Current work is to finish support for type synonyms, then I'll do either the GC or nested patterns, depending in which looks like the lowest hanging fruit.