Simple Lisp interpreter (lisp.rb) and Lisp front-end for Ruby (risp.rb; converting Lisp to Ruby primitives and after that evals it)

lisp.rb

class Lisp

  def ops(s)
    if ([:+, :-, :*, :/, :>, :<, :>=, :<=, :==].include? s)
      return lambda{|a, b| a.send(s, b) }
    end

    case s
      when :first
        return lambda{|x| x[0]}
      when :length 
        return lambda{|x| x.length}
      when :cons 
        return lambda{|x, y| [x]+y}
      when :car 
        return lambda{|x| x[0]}
      when :cdr
        return lambda{|x| x[1..-1]}
      when :append 
        return lambda{|x,y| x+y}
      when :list 
        return lambda{|*xs| xs}
      when :list? 
        return lambda{|x| x.is_a? Array}
      when :null? 
        return lambda{|x| x==nil}
      when :symbol? 
        return lambda{|x| x.is_a? Symbol}
      when :not 
        return lambda{|x| !x}
      when :display 
        return lambda{|x| p x}
      end
  end

  def eval(x ,env)
    return env[x] if env[x] and x.is_a? Symbol
    return ops(x) if ops(x)
    return x if !x.is_a? Array
    case x[0]
      when :define 
        env[x[1]] = eval(x[2], env)
        return env[x[1]]
      when :lambda
        return Proc.new{ |*args| 
          l_env = env.clone
          for i in 0..args.count
            l_env[x[1][i]] = args[i]
          end
          eval(x[2], l_env) }
      when :begin
        return x[1..-1].inject([]) { |agg, y| eval(y, env) }
      when :set! 
        env[x[1]] = eval(x[2], env)
        return env[x[1]]
      when :if
        return (eval(x[1], env)) ? eval(x[2], env) : eval(x[3], env)
    end
    exps = x.map{|exp| eval(exp, env)}
    return exps[0].call(*exps[1..-1]) if exps[0].methods.include? :call
    return exps
  end

  def parse(src)
    tokens = src.gsub('(', ' ( ').gsub(')', ' ) ').split
    Kernel.eval(tokens.map{|s| atom(s)}.join(' ').gsub(' ]',']').gsub(/([^\[]) /,'\1, '))
  end

  def atom(s)
    return "[" if s=='('
    return "]" if s==')'
    return s if s =~ /^-?\d+$/ || s =~ /^-?\d*\.\d+$/
    return s if s[0] == "\""
    ':'+s
  end
end

lisp_spec.rb

require_relative'../lisp.rb'

describe Lisp do
  before(:each) do
    @env = {}
    @lisp = Lisp.new
  end
  
  it "should parse lisp" do
    expect(@lisp.parse("(+ 2 2)")).to eq([:+, 2, 2])
    expect(@lisp.parse("(define x 1)")).to eq([:define, :x, 1])
  end

  def ev(x)
    @lisp.eval(@lisp.parse(x), @env)
  end

  it "should eval num atoms" do
    expect(ev("1")).to eq(1)
  end
  
  it "should eval string atoms" do
    expect(ev('"1"')).to eq("1")
  end
  
  it "should eval empty list" do
    expect(ev("()")).to eq([])
  end

  it "should eval one element list" do
    expect(ev("(1)")).to eq([1])
  end

  it "should eval two elements list" do
    expect(ev("(1 2)")).to eq([1,2])
  end

  it "should eval one element list" do
    expect(ev("(1 (2))")).to eq([1,[2]])
  end

  it "should fetch first from list" do
    expect(ev("(first (1 2))")).to eq(1)
  end

  it "should add" do
    expect(ev("(+ 2 2)")).to eq(4)
  end

  it "should multiply and add" do
    expect(ev("(+ (* 2 100) (* 1 10))")).to eq(210)
  end

  it "should support conditions" do
    expect(ev("(if (> 6 5) (+ 1 1) (+ 2 2))")).to eq(2)
    expect(ev("(if (< 6 5) (+ 1 1) (+ 2 2))")).to eq(4)
  end

  it "should define" do
    expect(ev("(define x 3)")).to eq(3)
    expect(ev("x")).to eq(3)
    expect(ev("(+ x x)")).to eq(6)
  end

  it "should set var" do
    expect(ev("(begin (define x 1) (set! x (+ x 1)) (+ x 1))")).to eq(3)
  end

  it "should calc lambdas" do
    expect(ev("((lambda (x) (+ x x)) 5)")).to eq(10)
  end

  it "should define lambdas" do
    ev("(define twice (lambda (x) (* 2 x)))")
    expect(ev("(twice 5)")).to eq(10)
  end

  it "should define included lambdas" do
    ev("(define twice (lambda (x) (* 2 x)))")
    ev("(define compose (lambda (f g) (lambda (x) (f (g x)))))")
    expect(ev("((compose list twice) 5)")).to eq([10])

    ev("(define repeat (lambda (f) (compose f f)))")
    expect(ev("((repeat twice) 5)")).to eq(20)
    expect(ev("((repeat (repeat twice)) 5)")).to eq(80)
  end

  it "should define factorial" do
    ev("(define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1))))))")
    expect(ev("(fact 3)")).to eq(6)
    expect(ev("(fact 50)")).to eq(30414093201713378043612608166064768844377641568960512000000000000)
  end

  it "should define abs" do
    ev("(define abs (lambda (n) ((if (> n 0) + -) 0 n)))")
    expect(ev("(list (abs -3) (abs 0) (abs 3))")).to eq([3, 0, 3])
  end

  it "should define factorial again" do
    expect(ev("(begin
               (define fact (lambda (n) 
                 (if (<= n 1) 1 (* n (fact (- n 1))))))
                  
                  (define f (lambda (return)
                     (begin
                          (return 2)
                              1)))
                               (display (f (lambda (x) x)))
                                (fact 50)
                                )")).to eq(30414093201713378043612608166064768844377641568960512000000000000)
  end

  it "should define simple recursive lambdas" do
    ev(" (define my_len (lambda (l)
                          (if (null? l) 0 (+ 1 (my_len (cdr l)))))) ")
    expect(ev("(my_len (1 2 3 4 5))")).to eq(5)
  end

  it "should define recursive lambdas" do
    ev("(define combine (lambda (f)
           (lambda (x y)
                 (if (null? x) (quote ())
                           (f (list (car x) (car y))
                                        ((combine f) (cdr x) (cdr y)))))))")
    ev("(define zip (combine cons))")
    expect(ev("(zip (list 1 2 3 4) (list 5 6 7 8))")).to eq([[1, 5], [2, 6], [3, 7], [4, 8]])
  end

  it "should define multiline lambdas in lines" do
    ev("(define riff_shuffle (lambda (deck) (begin
           (define take (lambda (n seq) (if (<= n 0) (quote ()) (cons (car seq) (take (- n 1) (cdr seq))))))
               (define drop (lambda (n seq) (if (<= n 0) seq (drop (- n 1) (cdr seq)))))
                   (define mid (lambda (seq) (/ (length seq) 2)))
                       ((combine append) (take (mid deck) deck) (drop (mid deck) deck)))))")
    expect(ev("(riff_shuffle (list 1 2 3 4 5 6 7 8))")).to eq([1, 5, 2, 6, 3, 7, 4, 8])

    ev("(define repeat (lambda (f) (compose f f)))")
    expect(ev("((repeat riff_shuffle) (list 1 2 3 4 5 6 7 8))")).to eq([1, 3, 5, 7, 2, 4, 6, 8])

    expect(ev("(riff_shuffle (riff_shuffle (riff_shuffle (list 1 2 3 4 5 6 7 8))))")).to eq([1,2,3,4,5,6,7,8])
  end

end

risp.rb

class Risp
  def parse(src)
    tokens = src.gsub('(', ' ( ').gsub(')', ' ) ').split
    Kernel.eval(tokens.map{|s| atom(s)}.join(' ').gsub(' ]',']').gsub(/([^\[]) /,'\1, '))
  end

  def atom(s)
    return "[" if s=='('
    return "]" if s==')'
    return s if s =~ /^-?\d+$/ || s =~ /^-?\d*\.\d+$/
    return s if s[0] == "\""
    ':'+s
  end

  def to_ruby(s)
    return to_ruby(s[0]) if (s.is_a? Array) && (s.count == 1) && (s[0].is_a? Array)
    if !s.is_a? Array
      return s.to_s if !s.is_a? String
      return "\"" + s + "\""
    end
    case s[0]
      when :set!
        return  "#{to_ruby(s[1])}=#{to_ruby(s[2])}"
      when :begin
        return to_ruby(s[1..-1]) + ".last"
      when :>, :<
        return to_ruby(s[1]) + s[0][0] + to_ruby(s[2])
      when :*, :+, :/, :-
        return to_ruby(s[1..-1]) + ".reduce(:#{s[0]})"
      when :if
        return "if " + to_ruby(s[1]) + "; " + to_ruby(s[2]) + " else " + to_ruby(s[3]) + " end"
      when :define
        return "#{to_ruby(s[1])}=#{to_ruby(s[2])}"
      when :lambda
        return "lambda { #{to_ruby(s[1])}".gsub("[","|").gsub("]","|") +  " #{to_ruby(s[2])} }"
      when :first
        return to_ruby(s[1..-1]) + ".first"
    end

    arr = s.map { |x| to_ruby(x) }
    return arr[0] + ".(" + arr[1..-1].join(", ") + ")" if (arr[0].is_a? String) && (arr[0].start_with? "lambda")
    return "[" + arr.join(", ") + "]"
  end

  def initialize
    @b = binding
  end

  def risp_reduce(arr)
    return arr if (!arr.is_a? Array) || arr.count == 0
    return arr[0][*arr[1..-1]] if (arr.is_a? Array) && (arr[0].is_a? Proc)

    arr.map { |x| risp_reduce(x) }
  end

  def eval(s, e)
    r = to_ruby(s)
    @b.eval("risp_reduce(" + r + ")")
  end
end

if (ARGV[0] == "r")
  risp = Risp.new
  while true
    print "risp> "
    line = $stdin.readline()
    r = risp.parse(line)
    puts risp.eval(r, {})
  end
end

run.rb

require "./lisp.rb"

env = {}
while true
  print "> "
  line = $stdin.readline()
  lisp = Lisp.new
  p lisp.eval(lisp.parse(line),env)
end