fpLISP: A minimum LISP interpreter for functional programming

This project is aimed to define a minimum specification of LISP interpreter implementations for fun, education or research of functional programming. The following ebook in Japanese is written by referring fpLISP:

『簡易LISP処理系で体験する関数型プログラミング』(Zenn Books)

Current Language Specification

It is mostly a subset of Scheme except built-in and pre-defined function naming convention and lack of global environment. The latter means that just one nested S-expression is supposed to be run. See each language dierctory for reference implementations.

• S-expressions are accepted with parenthesis enclosing, space separating and dot notation for cdr of conscells in quoting lists and displaying values.
• Special forms
  • lambda with lexical scope and Lisp-1. Atom variable is supported to implement variable number of arguments. On the other hand, list variable with dot notation is not accepted.
  • if as conditional operator. The false-clause must be provided.
  • quote
• Built-in functions for list and number processing
  • cons, car, cdr and atom for lists
  • +, -, *, / as quotient and % for numbers
  • lt as < for numbers
  • eq as = for both lists and numbers
• Boolean values
  • t as true
  • nil as false and empty set
• Pre-defined functions for list processing
  • fold similer to Prelude.foldl in Haskell
  • unfold similer to Data.Sequence.unfoldl in Haskell
  • unfold-stream similer to Data.Sequence.unfoldl in Haskell as a stream generator
  • take-stream to get specific number of head elements by unfold-stream

Sample codes

fpLISP has lambda with lexical-scope, no global environment and no loop syntax so fixed-point combinators will be used to recur, except pre-defined functions. The following sample codes are using U combinators. See samples directory for more sample codes, including Ninety-Nine Problems.

• Append two lists

((lambda (f a b) (f (f a nil) b))
 ((lambda (u) (u u))
  (lambda (u)
    (lambda (x y)
      (if (eq x nil) y
          ((u u) (cdr x) (cons (car x) y))))))
 (quote (x y z)) (quote (a b c)))

=> (x y z a b c)

• Generate Fibonacci sequence until 21th

((lambda (fibonacci)
   (fibonacci 21))
 (lambda (n)
   (((lambda (u) (u u))
     (lambda (u)
       (lambda (n a b)
         (if (lt n 0) nil
             (cons a ((u u) (- n 1) b (+ a b)))))))
    n 0 1)))

=> (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946)

• fold example

(fold - 0 (quote (1 2 3 4 5 6 7 8 9)))

=> -45

• unfold example

(unfold (lambda (x) (if (lt x 0) nil (cons (- x 1) x))) 9)

=> (0 1 2 3 4 5 6 7 8 9)

• unfold-stream and take-stream examples

(take-stream (unfold (lambda (x) (cons (- x 1) x)) 9) 10)

=> (0 1 2 3 4 5 6 7 8 9)

(take-stream
 (unfold-stream
  (lambda (x) (cons (car x) (cons (cdr x) (+ (car x) (cdr x)))))
  (cons 0 . 1))
 18)

=> (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597)

License

(C) 2021 TAKIZAWA Yozo

The codes in this repository are licensed under CC0, Creative Commons Zero v1.0 Universal