My Minimal Lisp Interpreter
Tags: lisp, ruby, interpreter
Published: 2021-04-19 14:50:21

> Time: 2021-04-03 23:44

> Author: vonhyou

The source code on GitHub: [vonhyou/lisp-interpreter](https://github.com/vonhyou/lisp-interpreter)

My log of implementing a lisp interpreter.



## Try Scheme Lisp

I'll try a famous lisp dialect at first.

### Install `mit-scheme` on macOS

>  MIT/GNU Scheme is an implementation of the Scheme programming language, providing an interpreter, compiler, source-code debugger, integrated Emacs-like editor, and a large runtime library. 

Official website: [www.gnu.org/software/mit-scheme](https://www.gnu.org/software/mit-scheme/)

Install by Homebrew

```bash
$ brew install mit-scheme
```



### Run Interpreter in Terminal

```bash
$ scheme --version
MIT/GNU Scheme 11.2
Copyright (C) 2020 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.

Image saved on Wednesday March 10, 2021 at 2:52:49 PM
  Release 11.2 || SF || LIAR/x86-64

Moriturus te salutat.
```



### Use Scheme Lisp as a Calculator 

```bash
1 ]=> (+ 1 2 3 4 5)

;Value: 15

1 ]=> (/ 12 7)

;Value: 12/7

1 ]=> (* 1 2 3 4)

;Value: 24

1 ]=> (/ (+ 3 2) (* 5 7))

;Value: 1/7

1 ]=> (quotient 7 3)

;Value: 2

1 ]=> (modulo 7 3)

;Value: 1

1 ]=> (sqrt 2)

;Value: 1.4142135623730951

1 ]=> (exact->inexact (/ 7 3))

;Value: 2.3333333333333335

1 ]=> (expt 3 12)

;Value: 531441
```



### Try cons and list

```lisp
1 ]=> (cons 1 2)

;Value: (1 . 2)

1 ]=> (cons 1 (cons 2 3))

;Value: (1 2 . 3)

1 ]=> '(1 2 2 3 4)

;Value: (1 2 2 3 4)

1 ]=> (car (cdr (cdr '(1 2 3 4))))

;Value: 3
```



### Define and Let

```bash
1 ]=> (define var 10)

;Value: var

1 ]=> var

;Value: 10

1 ]=> (define func (lambda () "hello, world!"))

;Value: func

1 ]=> (func)

;Value: "hello, world!"
```



### Condition

```bash
1 ]=> (if #t "true" "false")

;Value: "true"

1 ]=> (define (level grade)
        (cond
        ((> grade 90) 4.0)
        ((> grade 80) 3.5)
        ((> grade 60) 2.0)
        (else 0)))

;Value: level

1 ]=> (level 83)

;Value: 3.5
```





## Implement and Release of My Lisp

Design-> Implement-> Release

### Preparations: Design

I'll take some time to design my minimum Lisp.

#### Keywards of My Lisp

1. def
2. cons
3. car and cdr
4. quote
5. if
6. lambda

#### Operator of My Lisp

1. `+`, `-`, `*`, `/`, `%`
2. `and`, `or`, `not`
3. `==`, `!=`, `<`, `<=`, `>`, `>=`
4. `&`, `|`, `^`, `～`

#### Build-in Methods of My Lisp

1. `min` and `max`
2. `print`

### Parse

```ruby
# in module Prolisp

def self.tokenize(program)
  # Convert scripts to token lists
  program.gsub('(', ' ( ').gsub(')', ' ) ').split
end

def self.make_list(tokens)
  lst = []
  lst << read_tokens(tokens) while tokens[0] != ')'
  tokens.shift
  lst
end

def self.read_tokens(tokens)
  # read expressions from token
  raise SyntaxError, 'Unexpected EOF' if tokens.empty?

  case token = tokens.shift
  when '('
    make_list tokens
  when ')'
    raise SyntaxError, "Unexpected ')'"
  else
    atom token
  end
end

def self.atom(token)
  # Analyse numbers and symbols
  case token
  when /\d/
    (token.to_f % 1).positive? ? token.to_f : token.to_i
  else
    token.to_sym
  end
end
```

### Global env

```ruby
# in module Prolisp
def self.make_global
  @global_env ||= begin
    ops = %i[== != < <= > >= + - * / % & | ^ ～]
    ops.inject({}) do |sp, op|
      sp.merge op => ->(*args) { args.inject(&op) }
    end
  end

  @global_env.merge! quote: ->(*args) { args.to_a }
  @global_env.merge! cons:  ->(*args) { args.to_a }
  @global_env.merge! car:   ->(arr)   { arr[0] }
  @global_env.merge! cdr:   ->(arr)   { arr[1..-1] }
  @global_env.merge! print: ->(arg)   { p arg }
  @global_env.merge! min:   ->(arr)   { arr.min }
  @global_env.merge! max:   ->(arr)   { arr.max }
  @global_env
end
```

### Eval

```ruby
# in module Prolisp
  def self.lisp_eval(elem, env = make_global)
    if elem.instance_of? Symbol
      env[elem]
    elsif elem.instance_of?(Integer) || elem.instance_of?(Float)
      elem
    elsif elem[0] == :def
      _, sym, exp = elem
      env[sym] = lisp_eval(exp, env)
    elsif elem[0] == :if
      _, cod, if_true, if_false = elem
      exp = lisp_eval(cod, env) ? if_true : if_false
      lisp_eval exp, env
    elsif elem[0] == :lambda
      _, params, body = elem
      ->(*args) { lisp_eval body, env.merge(Hash[params.zip(args)]) }
    elsif elem[0] == :and
      lisp_eval(elem[1], env) && lisp_eval(elem[2], env)
    elsif elem[0] == :or
      lisp_eval(elem[1], env) || lisp_eval(elem[2], env)
    elsif elem[0] == :not
      !lisp_eval(elem[1], env)
    else
      func, *args = elem.map { |e| lisp_eval e, env }
      func.call(*args)
    end
  end
```

### REPL

```ruby
# in module Prolisp
  def self.repl(prompt = 'prol ƛ>> ')
    puts $copyleft
    loop do
      print prompt
      val = lisp_eval(parse(gets.chomp))

      print_value val unless val.nil? || val.instance_of?(Proc)
    end
  end

  def self.print_value(value)
    puts ";Value: #{value}"
  end
end
```

### Usage

```bash
$ git clone git@github.com:vonhyou/lisp-interpreter.git
$ cd ./lisp-interpreter
$ ruby ./prol.rb
```

![demo](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pkyxc5xagsdmzrkh8owp.png)

## "Feature" of `Prol`

- Basic functions as a minimal lisp
- **No** support for `String`
- **Unable** to define local variables 
- Comments are **not** allowed
 

## References

1. Yet Another Scheme Tutorial, http://www.shido.info/lisp/idx_scm_e.html
2. (How to Write a (Lisp) Interpreter (in Python)), http://norvig.com/lispy.html