Skip to content

Latest commit

 

History

History
98 lines (75 loc) · 3.6 KB

README.md

File metadata and controls

98 lines (75 loc) · 3.6 KB
Raw

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

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