Abstracts.2019.Optimizing

On the impact of semantics in functional optimizing compilers

by Riccardo Zanetti

Abstract

The talk investigates some of the connections between functional languages design, semantics and the optimization techniques that can consequently be performed.

During the past 30 years Haskell showed us non-strict functional languages can also be fast, sometimes as fast as imperative counterparts. We are going to have a deeper look into what a strict/non-strict functional language is and how this trait intimately relates to the optimization techniques that can be performed, as well as some tricks used in GHC in order to overcome the downsides.

Notes

Making

intersperse :: a -> [a] -> [a]
intersperse _   []     = []
intersperse _   [x]    = [x]
intersperse sep (x:xs) = x:sep:intersperse sep xs
-- > concat $ intersperse ", " $ map show [1..4]
-- "1, 2, 3, 4"

less strict

intersperse' :: a -> [a] -> [a]
intersperse' _   []     = []
intersperse' sep (x:xs) =
  x:case xs of                    -- yield `x` immediately
    [] -> []
    _  -> sep:intersperse' sep xs -- shortcoming: matching on `xs` again in the recursive call

in the sense that

intersperse' sep (x:_|_) = x:_|_

as opposed to

intersperse sep (x:_|_) = _|_

solves a space leak (using more space than one would expect) with GHC.

References

1. Olaf Chitil. Promoting Non-Strict Programming. 2006. University of Kent publication.
2. Daniel Fischer. Unnecessarily Strict Implementations. 2010. Haskell-Cafe post.
3. Jan Christiansen. Investigating Minimally Strict Functions in Functional Programming. 2011. University of Kiel thesis.