# Standards

Blogged by Ujihisa. Standard methods of programming and thoughts including Clojure, Vim, LLVM, Haskell, Ruby and Mathematics written by a Japanese programmer. github/ujihisa

## Tuesday, December 20, 2011

Unlambda is a minimal, "nearly pure"[1] functional programming language invented by David Madore. It is based on combinatory logic, a version of the lambda calculus that omits the lambda operator. It relies mainly on two built-in functions (s and k) and an "apply" operator (written `, the backquote character). These alone make it Turing-complete, but there are also some I/O functions to make it possible to interact with the user, some shortcut functions and a function for lazy evaluation. There are no variables in the language.

`http://en.wikipedia.org/wiki/Unlambda`

``````import qualified Text.Parsec as P
import Control.Applicative ((*>), (<\$>), (<*>))

data AST = Apply AST AST | Val Value
instance Show AST where
show (Apply a b) = "(" ++ show a ++ " " ++ show b ++ ")"
show (Val (Dot c)) = "put-" ++ [c]
show (Val (Builtin c)) = [c]

data Value = Dot Char
| Builtin Char
| PendingK Value
| PendingS1 Value
| PendingS2 Value Value
deriving Show

main = do
let helloworld = "`r```````````.H.e.l.l.o. .w.o.r.l.di"
let fibonacci = "```s``s``sii`ki`k.*``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`kr``s`k`sikk`k``s`ksk"
print \$ desugar \$ parse helloworld
eval \$ desugar \$ parse helloworld
--eval \$ desugar \$ parse fibonacci

parse :: String -> AST
parse = either (error . show) id . P.parse parse' "unlambda"

parse' = P.try (P.char '`' *> (Apply <\$> parse' <*> parse'))
P.<|>
P.try (P.char '.' *> (Val . Dot <\$> P.anyChar))
P.<|>
P.try (Val . Builtin <\$> P.anyChar)

desugar :: AST -> AST
desugar (Apply a b) = Apply (desugar a) (desugar b)
desugar (Val (Builtin 'r')) = Val (Dot '\n')
desugar (Val (Builtin 'i')) = Apply (Apply (Val (Builtin 's')) (Val (Builtin 'k'))) (Val (Builtin 'k')) -- i = ``skk
desugar x = x

eval :: AST -> IO (Value)
eval (Apply a b) = do
a' <- eval a
b' <- eval b
apply a' b'
eval (Val x) = return x

apply :: Value -> Value -> IO Value
apply (Dot c) x = putChar c >> return x
apply (Builtin 'k') x = return \$ PendingK x
apply (Builtin 's') x = return \$ PendingS1 x
apply (PendingK x) y = return \$ x
apply (PendingS1 x) y = return \$ PendingS2 x y
apply (PendingS2 x y) z = do
a <- apply x z
b <- apply y z
apply a b
``````
1. parse the given string to abstract syntax tree
2. desugar the ast; expanding macros like r or i.
3. interpreter evaluates all nodes!

AST

``````(put-\n (((((((((((put-H put-e) put-l) put-l) put-o) put- ) put-w) put-o) put-r) put-l) put-d) ((s k) k)))
``````

Result of `helloworld`

``````Hello world
``````

Result of `fibonacci`

``````*
*
**
***
*****
********
*************
*********************
**********************************
*******************************************************
*****************************************************************************************
``````

## (added at Tue Dec 20 23:57:12 PST 2011)

I also made a stackmachine-based virtual machine and a compiler for it.

`https://gist.github.com/1505131`

This was actually much simpler/easier than I thought. There's a difference between pure interpreter and this virtualmachine, but it's not very big.

For example very short program "hi" that shows "hi" is "``.h.ii" in unlambda. First this parser converts the text to AST.

``````((put-h put-i) ((s k) k))
``````

Then the compiler converts the tree to sequence of instructions.

``````IPush (Dot 'h')
IPush (Dot 'i')
IApply
IPush (Builtin 's')
IPush (Builtin 'k')
IApply
IPush (Builtin 'k')
IApply
IApply
``````

Then the virtualmachine runtime will run it.

``````hi
``````