/birdForest

An implementation of the bird forest

Primary LanguageHaskellGNU General Public License v3.0GPL-3.0

Bird Forest

An implementation of bird forest inspired from To mock a mocking bird.

A lambda calculus and combinatory logic interpreter.

As for now, you can call out the following birds

  • I : Idiot
  • S : Starling
  • K : Kestrel
  • B : Bluebird
  • C : Cardinal

Most of the birds could be found in the forest, although they are unnamed. Some birds might not terminate, for example, the Y-combinator bird (S(CB(SII))(CB(SII))).

The REPL can parse mentioned birds and lambda expression using the de bruijn index notation.

Examples

  • SKK will be parsed as (SK)K and return I
  • λ[0] means λx.x
  • λλλ[0][1] means λxyz.zy

Using

  1. download haskell and cabal
  2. cabal run birdForest to open a repl

Test

  • run cabal test to run the test

Implementation Detail

All library files are in /src/, tests are in /test/ and repl is in /app/

Parsing

  • Implemented parsing certain birds listed above
  • Parsing detail specified in Expr.hs
  • Parsing algorithm in Parser.hs

Evaluation

  • splited into intepret, (re)sugar
  • intepretation break down each bird into the equivalent lambda expression with de bruijn index
  • interpretation takes care of reductions and result in a non-reducible lambda expression
  • encyclopedia map back the expression to its name
    • ie. map λx.x or λ0 to I
    • ie. map λxy.x or λλ1 to K
  • prettify by changing de bruijn index notation into named lambda

Library Specification

Expr is a type that represent the syntax of the language.

Result is a type of Either String Expr where the string is the error message

Parser

  1. parseExpr :: String -> Result
    • parse string into a Result

Evaluation

  1. interp :: Expr -> Result
    • makes reduction of any Expression containing S and K
  2. evaluate :: String -> Result
    • parse the string, and do interp.

Output

  1. encyclopedia :: Expr -> String
    • yields the prettiest response with bird name and named lambda expression
  2. prettify :: Expr -> String
    • returns the corresponding named lambda expression
  3. show :: Expr -> String
    • returns the lambda expression in de bruijn index style

Reference

birds list