Pico Scheme

Pico Scheme

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₀ E*) | (lambda (I*) ∆* E₀) | (lambda I ∆* E₀) | (if E₀ E₁ E₂) | (if E₀ E₁ )

Dec → (define I E₀ )

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)))

External resources

• Pico version of revised⁷ report on the algorithmic language scheme specification releases