Church Encoding Parser

Introduction

This repository contains a simple parser for church encoding, implemented in the parser.rkt file.

The goal is to code an executor capable of outputting the results of statements written in church encoding.

Reference: Church Encoding - Wikipedia

Usage

To use, you can follow the example provided in the testNum.rkt:

#lang racket
(require "./parser.rkt")

(println "---- number enum ----")
(showNum zero)
(showNum one)

(println "---- you can write like this ----")
(showNum (λ (f) (λ (x) x)))
(showNum (λ (f) (λ (x) (f x))))

Executing the test units will yield the following:

smallyu@smallyus-Air church-encoding-parser % racket testNum.rkt 
"---- number ----"
0
1
"---- you can write like this ----"
0
1

TODO List

• Church numerals

  • numerals
  • plus
  • succ
  • mult
  • exp
  • pred
  • minus

• Church Booleans

  • true
  • false
  • and
  • or
  • not1
  • not2
  • xor
  • if

• Predicates

  • IsZero
  • LEQ
  • EQ

• Church pairs

  • pair
  • first
  • second

• List encodings

  • nil
  • isnil
  • cons
  • head
  • tail

• Y Combinator