# Pico Scheme

Jump to navigation
Jump to search

Paradigm(s) | functional |
---|---|

Designed by | Joshua Cogliati |

Appeared in | 2021 |

Computational class | Turing complete |

Reference implementation | rust pr7rs |

Influenced by | Scheme |

File extension(s) | `.scm` |

**Pico Scheme** is a minimalist purely functional version of Scheme, with all non-functional features removed. The syntax and semantics are defined both informally and in formal extended BNF and denotational semantics.

## Abstract Syntax

- K ∈ Con: constants, including quotations
- I ∈ Ide: identifiers (variables)
- E ∈ Exp: expressions
- ∆ ∈ Dec: declarations

Exp → K | I | (E_{0} E*)
| (lambda (I*) ∆* E_{0})
| (lambda I ∆* E_{0})
| (if E_{0} E_{1} E_{2}) | (if E_{0} E_{1} )

Dec → (define I E_{0} )

## Examples

### Hello, World!

(display '(Hello World!)) (newline)

Output:

(Hello World!)

### Y combinator and Factorial

(let ((Y (lambda (phi) ((lambda (f) (f f)) (lambda (f) (phi (lambda x (apply (f f) x)))))))) (let ((fact (Y (lambda (fact) (lambda (n) (if (< n 2) 1 (* n (fact (- n 1))))))))) (fact 5)))