Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Lisp in Huskell
Search
αλεx π
December 20, 2013
1
110
Lisp in Huskell
αλεx π
December 20, 2013
Tweet
Share
More Decks by αλεx π
See All by αλεx π
Scalable Time Series With Cassandra
ifesdjeen
1
350
Bayesian Inference is known to make machines biased
ifesdjeen
2
350
Cassandra for Data Analytics Backends
ifesdjeen
7
410
Stream Processing and Functional Programming
ifesdjeen
1
720
PolyConf 2015 - Rocking the Time Series boat with C, Haskell and ClojureScript
ifesdjeen
0
440
Clojure - A Sweetspot for Analytics
ifesdjeen
8
2k
Going Off Heap
ifesdjeen
3
1.9k
Always be learning
ifesdjeen
1
140
Learn Yourself Emacs For Great Good workshop slides
ifesdjeen
3
320
Featured
See All Featured
For a Future-Friendly Web
brad_frost
175
9.4k
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
7
150
Imperfection Machines: The Place of Print at Facebook
scottboms
264
13k
Building a Scalable Design System with Sketch
lauravandoore
459
33k
Why Our Code Smells
bkeepers
PRO
334
57k
It's Worth the Effort
3n
183
27k
Rebuilding a faster, lazier Slack
samanthasiow
79
8.6k
Teambox: Starting and Learning
jrom
132
8.7k
Build your cross-platform service in a week with App Engine
jlugia
229
18k
How to Think Like a Performance Engineer
csswizardry
19
1.1k
Designing for Performance
lara
604
68k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
664
120k
Transcript
Lisp in Huskell
Huskelldoge
By an 100% Haskell dummy
What is Lisp, really?
(def b 100) ;; defining vars! (def a (fn [c]
(+ b c))) ;; defining functions! (a 5 7) ;; executing functions
Easy!
How do we express it?
data LispExpression = LispSymbol String |! ReservedKeyword ReservedKeyword |! LispList
[LispExpression] |! LispVector [LispExpression] |! LispNumber Integer |! --LispNumber LispNum |! LispString String |! LispBool Bool |! LispFunction LispFunk |! -- LispFunction [LispExpression] LispExpression |! LispNil! deriving (Generic)
Parsing
Come on bro, really?
Reserved keywords (if, def, fn) parseReserved :: Parser LispExpression! parseReserved
= do! res <- try (string "def") <|>! try (string "if") <|>! try (string "fn")! return $ toSexp res
Numbers parseNumber :: Parser LispExpression! parseNumber = do! _ <-
try (many (string "#d"))! sign <- many (oneOf "-")! num <- many1 (digit)! if (length sign) > 1! then pzero! else return $ (LispNumber . read) $ sign ++ num
Booleans parseTrue :: Parser LispExpression! parseTrue = do! res <-
try (string "true")! return $ LispBool True! ! parseFalse :: Parser LispExpression! parseFalse = do! res <- try (string "false")! return $ LispBool False
Booleans parseReserved :: Parser LispExpression! parseReserved = do! res <-
try (string "def") <|>! try (string "if") <|>! try (string "fn")! return $ toSexp res! ! parseTrue :: Parser LispExpression! parseTrue = do! res <- try (string "true")! return $ LispBool True
Symbols parseSymbol :: Parser LispExpression! parseSymbol = do! first <-
letter <|> symbols! rest <- many (letter <|> digit <|> symbols)! let symbol = first:rest! return $ LispSymbol symbol
Lists parens parseList <|>! ! ! ! parseList :: Parser
LispExpression! parseList = liftM LispList $ sepBy parseLispExpression whiteSpace
Lists parseString :: Parser LispExpression! parseString = do _ <-
char '"'! x <- many (noneOf "\"")! _ <- char '"'! return $ LispString x
So, let’s see how it werkz
(+ 1 1) LispList [LispSymbol "plus", ! LispNumber 1, !
LispNumber 1]
Evaluation process
Easy-peasy
Literals evaluate to their values
Numbers - to numbers
Strings - to strings
Lists - recursively evaluate their values left to right
Symbols - to…
(def a 1)! (def b 2)! (+ a b)
(def a 1)! (def b 2)! (+ a b) What
is `a`?
Let’s check the Environment
Ah ok, a is 1
(def a 1)! (def b 2)! (+ a b) What
is `b`?
Ah ok, b is 1
Substitution β-reduction
None
(+ a b)! ! ! ! ! ! (+ 1
1) Becomes
(def a 1)! (def b 2)! (def c 3)! (def
d 4)! ! (+ a b (* c d))
(def a 1)! (def b 2)! (def c 3)! (def
d 4)! ! (+ a b (* 4 3))
(def a 1)! (def b 2)! (def c 3)! (def
d 4)! ! (+ a b 12)
(def a 1)! (def b 2)! (def c 3)! (def
d 4)! ! (+ 1 2 12)
When you see the symbol, look for it in Environment
Environment
Monad is just a box, right?
type Environment k v = H.BasicHashTable k v! type LispEnvironment
= (Environment LispExpression LispExpression)!
findVar :: LispEnvironment -> LispExpression -> ! ! ! !
! ! IO (Maybe LispExpression)! ! findVar env symbol = H.lookup env symbol!
Closures and polluting Environment
I’m not polluting, I just don’t need it anymore
(def sum ! (fn [a b] ! (fn [c] (+
c a b))))! ! (+ a b) ;; Shouldn't work Creates Closure
Closure is a temporary Environment
Passed only to recursive calls
(def sum ! (fn [a b] ! (fn [c] (+
c a b))))! ! (+ a b) ;; Shouldn't work Limited Visibility
That leads us to two-step lookup (shines in Haskell)
Look up var value in Closure
If there’s no Closure, look up Environment
If there’s Closure, look up in Closure first (shadowing)
If all fails, error
None
lookup_ <- (liftM2 mplus) ! (findVarMaybe closure func_) ! (findVar
envRef func_)
(def sum ! (fn [a b] ! (fn [c] (+
c a b))))! ! (+ a b) ;; Shouldn't work Limited Visibility
That makes me dance!
None
Built-in Functions
Problem: `+` symbol is a “native” function
None
2 function types
data LispFunk = UserFunction [LispExpression] LispExpression |! LibraryFunction String ([LispExpression]
-> LispExpression)! deriving (Generic)
“User” - is just a lisp expression (list)
“Library” - is a Haskell (“native”) function
numericOp :: (Integer -> Integer -> Integer) -> ! [LispExpression]
-> LispExpression! ! numericOp op args = LispNumber $ foldl1 op $ ! ! ! ! ! ! ! ! ! map unpackNum args! ! builtInOp :: String -> [LispExpression] -> ! LispExpression! builtInOp "+" args = numericOp (+) args
If statement
Consists of 3 blocks: Test expression Truthy expression Faulty expression
Test Expression: True is True (optimisation) Nil is False False
is False Anything else is True
eval env closure (LispList[(ReservedKeyword IfKeyword), ! ! ! ! !
! ! ! ! testExpression,! truthyExpression, falsyExpression]) = do! test <- (eval env closure testExpression)! res <- if (isTrue test)! then (eval env closure truthyExpression)! else (eval env closure falsyExpression)! return res
Map/reduce
Primitives
(def empty?! (fn [a] (= a (quote ()))))
None
(def map! (fn [f coll]! (if (empty? coll)! (quote ())!
(cons (f (first coll))! (map f (next coll)))))) Recur here
(def reduce! (fn [f coll acc]! (if (empty? coll)! acc!
(reduce f (next coll) (f acc (first coll)))))) Recur here
Bottomline
Definition is adding an evaluated expression to hash map
Function (fn) captures an enclosed environment and evaluates to internal
function primitive
If Evaluates only test expression and one of given blocks,
skipping the other one
Recursion Is given basically for free, since it’s just a
var lookup and a function call
Evaluation Evaluate left from right, recursively
Closures Capture the current environment, dismiss when reaching end of
lexical scope
Thanks everyone!
None
@ifesdjeen