Anders Persson (Ericsson, Chalmers)
Guest lecture in Introduction to Functional Programming, 2013
17 years at Ericsson
7 years ASIC development
10 years embedded software
Industrial Ph.D student at Chalmers
Embedded systems need fast programs
Fast programs means highly optimized
Optimization means target specific
Target specific means non-portable
Non-portable means increased maintenence
Increased maintenence means less time to optimize programs
High performance, easily maintained code that runs on many platforms
Write programs that write programs, instead of writing programs
Developed in collaboration between
Chalmers
Ericsson
Open source
http://hackage.haskell.org/package/feldspar-language
http://hackage.haskell.org/package/feldspar-compiler
https://github.com/Feldspar
Installation:
cabal install feldspar-language
cabal install feldspar-compiler
A functional language embedded in Haskell
Reuse syntax
Reuse type checker
A Feldspar program is a Haskell program written using Feldspar libraries
Generates code that can run on the target architecture
Feldspar Architecture
type Point = (Data Float, Data Float)
dist :: Point -> Point -> Data Float
dist (x1,y1) (x2,y2) = sqrt (square (x1-x2) + square (y1-y2))
where
square x = x*x
Data
gives the same definition in ordinary HaskellInteractive evaluation:
*Main> eval dist (5,10) (8,6)
5.0
Typical DSP operations
Exercise: Express as Haskell functions
elemMult :: [Float] -> [Float] -> [Float]
movingAvg :: [Float] -> [Float]
sProd :: [Float] -> [Float] -> Float
Haskell:
elemMult :: [Float] -> [Float] -> [Float]
movingAvg :: [Float] -> [Float]
sProd :: [Float] -> [Float] -> Float
elemMult as bs =
movingAvg as =
sProd as bs =
Haskell:
elemMult :: [Float] -> [Float] -> [Float]
movingAvg :: [Float] -> [Float]
sProd :: [Float] -> [Float] -> Float
elemMult as bs = zipWith (*) as bs
movingAvg as =
sProd as bs =
Haskell:
elemMult :: [Float] -> [Float] -> [Float]
movingAvg :: [Float] -> [Float]
sProd :: [Float] -> [Float] -> Float
elemMult as bs = zipWith (*) as bs
movingAvg as = zipWith (\a a' -> (a+a')/2) (tail as) as
sProd as bs =
Haskell:
elemMult :: [Float] -> [Float] -> [Float]
movingAvg :: [Float] -> [Float]
sProd :: [Float] -> [Float] -> Float
elemMult as bs = zipWith (*) as bs
movingAvg as = zipWith (\a a' -> (a+a')/2) (tail as) as
sProd as bs = sum $ zipWith (*) as bs
Feldspar:
elemMult :: Vector1 Float -> Vector1 Float -> Vector1 Float
movingAvg :: Vector1 Float -> Vector1 Float
sProd :: Vector1 Float -> Vector1 Float -> Data Float
elemMult as bs = zipWith (*) as bs
movingAvg as = zipWith (\a a' -> (a+a')/2) (tail as) as
sProd as bs = sum $ zipWith (*) as bs
Haskell code not suitable for running directly in a base station
But Feldspar produces efficient C code:
*Main> icompile elemMult
...
void test(struct array * v0, struct array * v1, struct array * out)
{
uint32_t len0;
len0 = min(getLength(v0), getLength(v1));
initArray(out, sizeof(float), len0);
for(uint32_t v2 = 0; v2 < len0; v2 += 1)
{
at(float,out,v2) = (at(float,v0,v2) * at(float,v1,v2));
}
}
Which one is most readable?
movingAvg :: Vector1 Float -> Vector1 Float
movingAvg as = zipWith (\a a' -> (a+a')/2) (tail as) as
movingAvg2 :: Vector1 Float -> Vector1 Float
movingAvg2 as = map (/2) $ zipWith (+) (tail as) as
movingAvg
is perhaps closer to the specification:
movingAvg2
is more modular!
Which one is most efficient?
movingAvg :: Vector1 Float -> Vector1 Float
movingAvg as = zipWith (\a a' -> (a+a')/2) (tail as) as
movingAvg2 :: Vector1 Float -> Vector1 Float
movingAvg2 as = map (/2) $ zipWith (+) (tail as) as
*Main> icompile movingAvg
...
void test(struct array * v0, struct array * out)
{
uint32_t v2;
uint32_t len0;
v2 = getLength(v0);
len0 = min((v2 - min(v2, 1)), v2);
initArray(out, sizeof(float), len0);
for(uint32_t v1 = 0; v1 < len0; v1 += 1)
{
at(float,out,v1) = ((at(float,v0,(v1 + 1))
+ at(float,v0,v1)) / 2.0f);
}
}
*Main> icompile movingAvg2
...
void test(struct array * v0, struct array * out)
{
uint32_t v2;
uint32_t len0;
v2 = getLength(v0);
len0 = min((v2 - min(v2, 1)), v2);
initArray(out, sizeof(float), len0);
for(uint32_t v1 = 0; v1 < len0; v1 += 1)
{
at(float,out,v1) = ((at(float,v0,(v1 + 1))
+ at(float,v0,v1)) / 2.0f);
}
}
Feldspar’s vector library guarantees fusion!
Haskell makes it very convenient to represent expressions as recursive data types. For example:
-- Arithmetic expressions
data Expr = Num Int
| Add Expr Expr
| Mul Expr Expr
-- Evaluation
eval :: Expr -> Int
eval (Num n) = n
eval (Add e1 e2) = eval e1 + eval e2
eval (Mul e1 e2) = eval e1 * eval e2
num :: Int -> Expr
num = Num
(<+>) :: Expr -> Expr -> Expr
(<+>) = Add
(<*>) :: Expr -> Expr -> Expr
(<*>) = Mul
Example:
prog = (num 10 <*> num 4) <+> (num 34 <+> num 6)
*Main> eval prog
80
instance Num Expr
where
fromInteger = Num . fromInteger
(+) = (<+>)
(*) = (<*>)
prog2 :: Expr
prog2 = 10*4 + 34 + 6
Convert an expression to a sequence of variable assignments:
*Main> compile (10*4 + 34 + 6)
v0 = 10
v1 = 4
v2 = v0*v1
v3 = 34
v4 = v2+v3
v5 = 6
v6 = v4+v5
var v = "v" ++ show v
assign v expr = var v ++ " = " ++ expr ++ "\n"
matchOp (Add e1 e2) = ("+",e1,e2)
matchOp (Mul e1 e2) = ("*",e1,e2)
compile' :: Int -> Expr -> (String,Int)
compile' v (Num n) = (assign v (show n), v)
compile' v0 e = (code1 ++ code2 ++ code3, v3)
where
(op,e1,e2) = matchOp e
(code1,v1) = compile' v0 e1
(code2,v2) = compile' (v1+1) e2
v3 = v2+1
code3 = assign v3 (var v1 ++ op ++ var v2)
compile :: Expr -> IO ()
compile = putStrLn . fst . compile' 0
prog2 :: Expr
prog2 = 10*4 + 34 + 6
*Main> compile prog2
v0 = 10
v1 = 4
v2 = v0*v1
v3 = 34
v4 = v2+v3
v5 = 6
v6 = v4+v5
The language API can be extended without changing the Expr
type
Simple example, loop construct:
loop :: Int -> (Expr -> Expr) -> (Expr -> Expr)
loop 0 f = id
loop n f = f . loop (n-1) f
loop
) to the user, while keeping the expressions simple*Main> compile (loop 5 (*2) 30)
v0 = 30
v1 = 2
v2 = v0*v1
v3 = 2
v4 = v2*v3
v5 = 2
v6 = v4*v5
v7 = 2
v8 = v6*v7
v9 = 2
v10 = v8*v9
Expr
languageVector
type only exists as sugarFunctional programming suitable for numeric processing and DSP
Embedding is a powerful implementation technique
Feldspar allows you to use high-level functional programming for performance-critical software
Some work remains
Space, Right Arrow or swipe left to move to next slide, click help below for more details