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
360
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
Large-scale JavaScript Application Architecture
addyosmani
510
110k
Build your cross-platform service in a week with App Engine
jlugia
229
18k
Bootstrapping a Software Product
garrettdimon
PRO
305
110k
YesSQL, Process and Tooling at Scale
rocio
169
14k
The Cult of Friendly URLs
andyhume
78
6k
The Web Performance Landscape in 2024 [PerfNow 2024]
tammyeverts
0
110
A Modern Web Designer's Workflow
chriscoyier
693
190k
The Invisible Side of Design
smashingmag
298
50k
Happy Clients
brianwarren
98
6.7k
Scaling GitHub
holman
458
140k
Navigating Team Friction
lara
183
14k
Building a Scalable Design System with Sketch
lauravandoore
459
33k
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