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
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.
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
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
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!"
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
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
- def
- cons
- car and cdr
- quote
- if
- lambda
Operator of My Lisp
-
+
,-
,*
,/
,%
-
and
,or
,not
-
==
,!=
,<
,<=
,>
,>=
-
&
,|
,^
,~
Build-in Methods of My Lisp
-
min
andmax
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
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
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
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
Usage
$ git clone git@github.com:vonhyou/lisp-interpreter.git
$ cd ./lisp-interpreter
$ ruby ./prol.rb
"Feature" of Prol
- Basic functions as a minimal lisp
-
No support for
String
- Unable to define local variables
- Comments are not allowed
References
- Yet Another Scheme Tutorial, http://www.shido.info/lisp/idx_scm_e.html
- (How to Write a (Lisp) Interpreter (in Python)), http://norvig.com/lispy.html
Top comments (0)