A big thanks to everyone who everyone who sent in space leak specimens. All of the leaks have been inspected and cataloged by our experts, and we are quite pleased to open the doors of the space leak zoo to the public!
There are a few different types of space leak here, but they are quite different and a visitor would do well not to confuse them (the methods for handling them if encountered in the wild vary, and using the wrong technique could exacerbate the situation).
Read more...
Short post, longer ones in progress.
One of the really neat things about the Par monad is how it explicitly reifies laziness, using a little structure called an IVar (also known in the literature as I-structures). An IVar is a little bit like an MVar, except that once you’ve put a value in one, you can never take it out again (and you’re not allowed to put another value in.) In fact, this precisely corresponds to lazy evaluation.
Read more...
I’m currently collecting non-stack-overflow space leaks, in preparation for a future post in the Haskell Heap series. If you have any interesting space leaks, especially if they’re due to laziness, send them my way.
Here’s what I have so far (unverified: some of these may not leak or may be stack overflows. I’ll be curating them soon).
import Control.Concurrent.MVar
-- http://groups.google.com/group/fa.haskell/msg/e6d1d5862ecb319b
main1 = do file <- getContents
putStrLn $ show (length $ lines file) ++ " " ++
show (length $ words file) ++ " " ++
show (length file)
-- http://www.haskell.org/haskellwiki/Memory_leak
main2 = let xs = [1..1000000::Integer]
in print (sum xs * product xs)
-- http://hackage.haskell.org/trac/ghc/ticket/4334
leaky_lines :: String -> [String]
leaky_lines "" = []
leaky_lines s = let (l, s') = break (== '\n') s
in l : case s' of
[] -> []
(_:s'') -> leaky_lines s''
-- http://stackoverflow.com/questions/5552433/how-to-reason-about-space-complexity-in-haskell
data MyTree = MyNode [MyTree] | MyLeaf [Int]
makeTree :: Int -> MyTree
makeTree 0 = MyLeaf [0..99]
makeTree n = MyNode [ makeTree (n - 1)
, makeTree (n - 1) ]
count2 :: MyTree -> MyTree -> Int
count2 r (MyNode xs) = 1 + sum (map (count2 r) xs)
count2 r (MyLeaf xs) = length xs
-- http://stackoverflow.com/questions/2777686/how-do-i-write-a-constant-space-length-function-in-haskell
leaky_length xs = length' xs 0
where length' [] n = n
length' (x:xs) n = length' xs (n + 1)
-- http://stackoverflow.com/questions/3190098/space-leak-in-list-program
leaky_sequence [] = [[]]
leaky_sequence (xs:xss) = [ y:ys | y <- xs, ys <- leaky_sequence xss ]
-- http://hackage.haskell.org/trac/ghc/ticket/917
initlast :: (()->[a]) -> ([a], a)
initlast xs = (init (xs ()), last (xs ()))
main8 = print $ case initlast (\()->[0..1000000000]) of
(init, last) -> (length init, last)
-- http://hackage.haskell.org/trac/ghc/ticket/3944
waitQSem :: MVar (Int,[MVar ()]) -> IO ()
waitQSem sem = do
(avail,blocked) <- takeMVar sem
if avail > 0 then
putMVar sem (avail-1,[])
else do
b <- newEmptyMVar
putMVar sem (0, blocked++[b])
takeMVar b
-- http://hackage.haskell.org/trac/ghc/ticket/2607
data Tree a = Tree a [Tree a] deriving Show
data TreeEvent = Start String
| Stop
| Leaf String
deriving Show
main10 = print . snd . build $ Start "top" : cycle [Leaf "sub"]
type UnconsumedEvent = TreeEvent -- Alias for program documentation
build :: [TreeEvent] -> ([UnconsumedEvent], [Tree String])
build (Start str : es) =
let (es', subnodes) = build es
(spill, siblings) = build es'
in (spill, (Tree str subnodes : siblings))
build (Leaf str : es) =
let (spill, siblings) = build es
in (spill, Tree str [] : siblings)
build (Stop : es) = (es, [])
build [] = ([], [])
Today, we discuss how presents on the Haskell Heap are named, whether by top-level bindings, let-bindings or arguments. We introduce the Expression-Present Equivalent Exchange, which highlights the fact that expressions are also thunks on the Haskell heap. Finally, we explain how this let-bindings inside functions can result in the creation of more presents, as opposed to constant applicative forms (CAFs) which exist on the Haskell Heap from the very beginning of execution.
Read more...
One of the persistent myths about Aristotelean physics—the physics that was proposed by the Ancient Greeks and held up until Newton and Galileo came along—is that Aristotle thought that “heavier objects fall more quickly than light objects”, the canonical example being that of a cannon ball and feather. Although some fraction of contemporary human society may indeed believe this “fact,” Aristotle had a far more subtle and well-thought out view on the matter. If you don’t believe me, an English translation of his original text (Part 8) adequately gives off this impression. Here is a relevant quote (emphasis mine):
Read more...
When we teach beginners about Haskell, one of the things we handwave away is how the IO monad works. Yes, it’s a monad, and yes, it does IO, but it’s not something you can implement in Haskell itself, giving it a somewhat magical quality. In today’s post, I’d like to unravel the mystery of the IO monad by describing how GHC implements the IO monad internally in terms of primitive operations and the real world token. After reading this post, you should be able to understand the resolution of this ticket as well as the Core output of this Hello World! program:
Read more...
It is well known that unsafePerformIO is an evil tool by which impure effects can make their way into otherwise pristine Haskell code. But is the rest of Haskell really that pure? Here are a few questions to ask:
- What is the value of
maxBound :: Int? - What is the value of
\x y -> x / y == (3 / 7 :: Double) with 3 and 7 passed in as arguments? - What is the value of
os :: String from System.Info? - What is the value of
foldr (+) 0 [1..100] :: Int?
The answers to each of these questions are ill-defined—or you might say they’re well defined, but you need a little extra information to figure out what the actual result is.
Read more...
Today, we introduce the Grinch.
A formerly foul and unpleasant character, the Grinch has reformed his ways. He still has a penchant for stealing presents, but these days he does it ethically: he only takes a present if no one cares about it anymore. He is the garbage collector of the Haskell Heap, and he plays a very important role in keeping the Haskell Heap small (and thus our memory usage low)—especially since functional programs generate a lot of garbage. We’re not a particularly eco-friendly bunch.
Read more...
We’ve talked about how we open (evaluate) presents (thunks) in the Haskell Heap: we use IO. But where do all of these presents come from? Today we introduce where all these presents come from, the Ghost-o-matic machine (a function in a Haskell program).
Using a function involves three steps.
We can treat the machine as a black box that takes present labels and pops out presents, but you can imagine the inside as having an unlimited supply of identical ghosts and empty present boxes: when you run the machine, it puts a copy of the ghost in the box.
Read more...
Here is a simple implementation of all of the parts of the Haskell heap we have discussed up until now, ghosts and all.
heap = {} # global
# ---------------------------------------------------------------------#
class Present(object): # Thunk
def __init__(self, ghost):
self.ghost = ghost # Ghost haunting the present
self.opened = False # Evaluated?
self.contents = None
def open(self):
if not self.opened:
# Hey ghost! Give me your present!
self.contents = self.ghost.disturb()
self.opened = True
self.ghost = None
return self.contents
class Ghost(object): # Code and closure
def __init__(self, *args):
self.tags = args # List of names of presents (closure)
def disturb(self):
raise NotImplemented
class Inside(object):
pass
class GiftCard(Inside): # Constructor
def __init__(self, name, *args):
self.name = name # Name of gift card
self.items = args # List of presents on heap you can redeem!
def __str__(self):
return " ".join([self.name] + map(str, self.items))
class Box(Inside): # Boxed, primitive data type
def __init__(self, prim):
self.prim = prim # Like an integer
def __str__(self):
return str(self.prim)
# ---------------------------------------------------------------------#
class IndirectionGhost(Ghost):
def disturb(self):
# Your present is in another castle!
return heap[self.tags[0]].open()
class AddingGhost(Ghost):
def disturb(self):
# Gotta make your gift, be back in a jiffy!
item_1 = heap[self.tags[0]].open()
item_2 = heap[self.tags[1]].open()
result = item_1.prim + item_2.prim
return Box(result)
class UnsafePerformIOGhost(Ghost):
def disturb(self):
print "Fire ze missiles!"
return heap[self.tags[0]].open()
class PSeqGhost(Ghost):
def disturb(self):
heap[self.tags[0]].open() # Result ignored!
return heap[self.tags[1]].open()
class TraceGhost(Ghost):
def disturb(self):
print "Tracing %s" % self.tags[0]
return heap[self.tags[0]].open()
class ExplodingGhost(Ghost):
def disturb(self):
print "Boom!"
raise Exception
# ---------------------------------------------------------------------#
def evaluate(tag):
print "> evaluate %s" % tag
heap[tag].open()
def makeOpenPresent(x):
present = Present(None)
present.opened = True
present.contents = x
return present
# Let's put some presents in the heap (since we can't make presents
# of our own yet.)
heap['bottom'] = Present(ExplodingGhost())
heap['io'] = Present(UnsafePerformIOGhost('just_1'))
heap['just_1'] = makeOpenPresent(GiftCard('Just', 'bottom'))
heap['1'] = makeOpenPresent(Box(1))
heap['2'] = makeOpenPresent(Box(2))
heap['3'] = makeOpenPresent(Box(3))
heap['traced_1']= Present(TraceGhost('1'))
heap['traced_2']= Present(TraceGhost('2'))
heap['traced_x']= Present(TraceGhost('x'))
heap['x'] = Present(AddingGhost('traced_1', '3'))
heap['y'] = Present(PSeqGhost('traced_2', 'x'))
heap['z'] = Present(IndirectionGhost('traced_x'))
print """$ cat src.hs
import Debug.Trace
import System.IO.Unsafe
import Control.Parallel
import Control.Exception
bottom = error "Boom!"
io = unsafePerformIO (putStrLn "Fire ze missiles" >> return (Just 1))
traced_1 = trace "Tracing 1" 1
traced_2 = trace "Tracing 2" 2
traced_x = trace "Tracing x" x
x = traced_1 + 3
y = pseq traced_2 x
z = traced_x
main = do
putStrLn "> evaluate 1"
evaluate 1
putStrLn "> evaluate z"
evaluate z
putStrLn "> evaluate z"
evaluate z
putStrLn "> evaluate y"
evaluate y
putStrLn "> evaluate io"
evaluate io
putStrLn "> evaluate io"
evaluate io
putStrLn "> evaluate bottom"
evaluate bottom
$ runghc src.hs"""
# Evaluating an already opened present doesn't do anything
evaluate('1')
# Evaluating an indirection ghost forces us to evaluate another present
evaluate('z')
# Once a present is opened, it stays opened
evaluate('z')
# Evaluating a pseq ghost may mean extra presents get opened
evaluate('y')
# unsafePerformIO can do anything, but maybe only once..
evaluate('io')
evaluate('io')
# Exploding presents may live in the heap, but they're only dangerous
# if you evaluate them...
evaluate('bottom')
Technical notes. You can already see some resemblance of the ghosts’ Python implementations and the actual Core GHC might spit out. Here’s an sample for pseq:
Read more...