DEV Community

loading...
Cover image for My Minimal Lisp Interpreter

My Minimal Lisp Interpreter

Your 🍟 Classmate
Former OIer
・Updated on ・3 min read

Time: 2021-04-03 23:44

Author: vonhyou

The source code on GitHub: 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

Install by Homebrew

$ brew install mit-scheme
Enter fullscreen mode Exit fullscreen mode

Run Interpreter in Terminal

$ 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.
Enter fullscreen mode Exit fullscreen mode

Use Scheme Lisp as a Calculator

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
Enter fullscreen mode Exit fullscreen mode

Try cons and list

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
Enter fullscreen mode Exit fullscreen mode

Define and Let

1 ]=> (define var 10)

;Value: var

1 ]=> var

;Value: 10

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

;Value: func

1 ]=> (func)

;Value: "hello, world!"
Enter fullscreen mode Exit fullscreen mode

Condition

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
Enter fullscreen mode Exit fullscreen mode

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

# 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
Enter fullscreen mode Exit fullscreen mode

Global env

# 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
Enter fullscreen mode Exit fullscreen mode

Eval

# 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
Enter fullscreen mode Exit fullscreen mode

REPL

# 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
Enter fullscreen mode Exit fullscreen mode

Usage

$ git clone git@github.com:vonhyou/lisp-interpreter.git
$ cd ./lisp-interpreter
$ ruby ./prol.rb
Enter fullscreen mode Exit fullscreen mode

demo

"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

Discussion (0)