Mini-Lisp Interpreter

Mini-LISP is the subset of LISP. You can find the grammar rules in the README.md file. This is the final project of Compiler in NCU, Taiwan.

Overview

LISP is an ancient programming language based on S-expressions and lambda calculus. All operations in Mini-LISP are written in parenthesized prefix notation. For example, a simple mathematical formula (1 + 2) * 3 written in Mini-LISP is:

(* (+ 1 2) 3)

As a simplified language, Mini-LISP has only three types (Boolean, number and function) and a few operations.

Features

Basic Features

• Syntax Validation
• Print
• Numerical Operations
• Logical Operations
• if Expression
• Variable Definition
• Function
• Named Function

Bonus Features

• Recursion
• Type Checking
• Nested Function
• First-class Function

Usage

Clone the project.

git clone https://github.com/seanwu1105/mini-lisp-interpreter

Change directory to project folder.

cd mini-lisp-interpreter/

Install the dependencies with Poetry.

poetry install --no-root

Feed the Mini-LISP source codes into the interpreter as standard input file.

python main.py < filename.lsp

Or import the Interpreter class in mini_lisp_interpreter folder and call the Interpreter().interpret(your_mini_lisp_code).

For example:

mini_lisp_interpreter.Interpreter().interpret(r'(print-num (mod 10 4))')

Type Definition

• Boolean: Boolean type includes two values, #t for true and #f for false.
• Number: Signed integer from -(231) to 231 - 1, behavior out of this range is not defined.
• Function: See Function.

Casting: Not allowed, but type checking is a bonus feature.

Operation Overview

Numerical Operators

Logical Operators

Other Operators

• define
• fun
• if

All operators are reserved words, you cannot use any of these words as ID.

Lexical Details

Preliminary Definitions

separator ::= ‘\t’ | ‘\n’ | ‘\r’ | ‘ ’
letter ::= [a-z]
digit ::= [0-9]

Token Definitions

number ::= 0 | [1-9]digit* | -[1-9]digit*

Examples: 0, 1, -23, 123456

ID ::= letter (letter | digit | ‘-’)*

Examples: x, y, john, cat-food

bool-val ::= #t | #f

Grammar Overview

PROGRAM ::= STMT+
STMT ::= EXP | DEF-STMT | PRINT-STMT
PRINT-STMT ::= (print-num EXP) | (print-bool EXP)
EXP ::= bool-val | number | VARIABLE | NUM-OP | LOGICAL-OP
| FUN-EXP | FUN-CALL | IF-EXP
NUM-OP ::= PLUS | MINUS | MULTIPLY | DIVIDE | MODULUS | GREATER
| SMALLER | EQUAL
PLUS ::= (+ EXP EXP+)
MINUS ::= (- EXP EXP)
MULTIPLY ::= (* EXP EXP+)
DIVIDE ::= (/ EXP EXP)
MODULUS ::= (mod EXP EXP)
GREATER ::= (> EXP EXP)
SMALLER ::= (< EXP EXP)
EQUAL ::= (= EXP EXP+)
LOGICAL-OP ::= AND-OP | OR-OP | NOT-OP
AND-OP ::= (and EXP EXP+)
OR-OP ::= (or EXP EXP+)
NOT-OP ::= (not EXP)
DEF-STMT ::= (define VARIABLE EXP)
VARIABLE ::= id
FUN-EXP ::= (fun FUN_IDs FUN-BODY)
FUN-IDs ::= (id*)
FUN-BODY ::= EXP
FUN-CALL ::= (FUN-EXP PARAM*) | (FUN-NAME PARAM*)
PARAM ::= EXP
FUN-NAME ::= id
IF-EXP ::= (if TEST-EXP THAN-EXP ELSE-EXP)
TEST-EXP ::= EXP
THEN-EXP ::= EXP
ELSE-EXP ::= EXP

Grammar and Behavior Definition

Program

PROGRAM :: = STMT+
STMT ::= EXP | DEF-STMT | PRINT-STMT

Print

PRINT-STMT ::= (print-num EXP)

Behavior: Print exp in decimal.

    | (print-bool EXP)

Behavior: Print #t if EXP is true. Print #f, otherwise.

Expression (EXP)

EXP ::= bool-val | number | VARIABLE
    | NUM-OP | LOGICAL-OP | FUN-EXP | FUN-CALL | IF-EXP

Numerical Operations (NUM-OP)

NUM-OP ::= PLUS | MINUS | MULTIPLY | DIVIDE | MODULUS |
    | GREATER | SMALLER | EQUAL

PLUS ::= (+ EXP EXP+)

Behavior: return sum of all EXP inside.

Example:

(+ 1 2 3 4)   ; → 10

MINUS ::= (- EXP EXP)

Behavior: return the result that the 1st EXP minus the 2nd EXP.

Example:

(- 2 1)   ; → 1

MULTIPLY ::= (* EXP EXP+)

Behavior: return the product of all EXP inside.

Example:

(* 1 2 3 4)   ; → 24

DIVIDE ::= (/ EXP EXP)

Behavior: return the result that 1st EXP divided by 2nd EXP.

Example:

(/ 10 5)  ; → 2
(/ 3 2)   ; → 1 (just like C++)

MODULUS ::= (mod EXP EXP)

Behavior: return the modulus that 1st EXP divided by 2nd EXP.

Example:

(mod 8 5) ; → 3

GREATER ::= (> EXP EXP)

Behavior: return #t if 1st EXP greater than 2nd EXP. #f otherwise.

Example:

(> 1 2)   ; → #f

SMALLER ::= (< EXP EXP)

Behavior: return #t if 1st EXP smaller than 2nd EXP. #f otherwise.

Example:

(< 1 2)   ; → #t

EQUAL ::= (= EXP EXP+)

Behavior: return #t if all EXPs are equal. #f otherwise.

Example:

(= (+ 1 1) 2 (/6 3))  ; → #t

Logical Operations (LOGICAL-OP)

LOGICAL-OP ::= AND-OP | OR-OP | NOT-OP

AND-OP ::= (and EXP EXP+)

Behavior: return #t if all EXPs are true. #f otherwise.

Example:

(and #t (> 2 1))  ; → #t

OR-OP ::= (or EXP EXP+)

Behavior: return #t if at least one EXP is true. #f otherwise.

Example:

(or (> 1 2) #f)   ; → #f

NOT-OP ::= (not EXP)

Behavior: return #t if EXP is false. #f otherwise.

Example:

(not (> 1 2)) ; → #t

define Statement (DEF-STMT)

DEF-STMT ::= (define id EXP)

VARIABLE ::= id

Behavior: Define a variable named id whose value is EXP.

Example:

(define x 5)
(+ x 1)  ; → 6

Note: Redefining is not allowed.

Function

FUN-EXP ::= (fun FUN-IDs FUN-BODY)
FUN-IDs ::= (id*)
FUN-BODY ::= EXP
FUN-CALL ::= (FUN-EXP PARAM*)
    | (FUN-NAME PARAM*)
PARAM ::= EXP
FUN-NAME ::= id

Behavior:

FUN-EXP defines a function. When a function is called, bind FUN-IDs to PARAMs, just like the define statement. If an id has been defined outside this function, prefer the definition inside the FUN-EXP. The variable definitions inside a function should not affect the outer scope. A FUN-CALL returns the evaluated result of FUN-BODY. Note that variables used in FUN-BODY should be bound to
PARAMs.

Examples:

((fun (x) (+ x 1)) 2) ; → 3
(define foo (fun () 0))
(foo) ; → 0
(define x 1)
(define bar (fun (x y) (+ x y)))
(bar 2 3) ; → 5
x ; → 1

if Expression

IF-EXP ::= (if TEST-EXP THEN-EXP ELSE-EXP)
TEST-EXP ::= EXP
THEN-EXP ::= EXP
ELSE-EXP ::= EXP

Behavior: When TEST-EXP is true, returns THEN-EXP. Otherwise, returns ELSE-EXP.

Example:

(if (= 1 0) 1 2)  ; → 2
(if #t 1 2)   ; → 1

Bonus Features Details

Recursion

The interpreter is able to handle recursive function call.

(define f
    (fun (x) (if (= x 1)
                1
                (* x (f (- x 1))))))
(f 4)   ; → 24

Type Checking

For type specifications of operations, please check out the table below:

(> 1 #t)    ; Type Error: Expect 'number' but got 'boolean'.

Nested Function

There could be a function inside another function. The inner one is able to access the local variables of the outer function.

The syntax rule of fun-body should be redefined to

fun-body ::= def-stmt* exp

(define dist-square
    (fun (x y)
        (define square
            (fun (x) (* x x)))
        (+ (square x) (square y))))

First-Class Function

Functions can be passed like other variables. Furthermore, it can keep its environment.

(define chose
    (fun (chose-fun x y)
        (if (chose-fun x y) x y)))
(chose (fun (x y) (> x y)) 2 1) ; → 2
(define add-x
    (fun (x)
        (fun (y) (+ x y))))
(define f (add-x 5))
(f 3)   ; → 8

References

• Ruslan’s Blog - Let’s Build A Simple Interpreter
• Peter@Norvig.com - lispy