用java写一个lisp 解释器

起初最早听到lisp这个名字是一个偶然的机会,留下了很牛的印象,时间匆匆五年就过去了,前些日子看sicp,里面又再次提到了这个名字,从网上找了几个入门文档学习了一下基础语法,便又继续看起了sicp;从写下第一行(+ 1 2)代码,日子转眼一个月就过去了,不得不说 lisp的前缀表达式的方式还是很不错的,不知怎得慢慢有了写一个lisp 解释器的想法,然后想到了之前王垠似乎写过一篇文章《怎样写一个解释器》 如果你对如何写一个解释器感兴趣可以看下这篇文章,还是有所启发的。

回来了吗?哈哈哈

我们继续旅途,这里选用的lisp方言是Scheme,选用它并无其他,只是因为当初学习的基础语法是它

写一个lisp解释器可以分三步:

1.将lisp表达式的字符串转换成一个树性结构的数组
2.解释这棵树
3.支持变量和方法调用

这里使用的语言是java

构造语法树

首先第一步:如何将lisp表达式的字符串转换成一个树性结构的数组?
我们看一几个lisp表达式 分析一下他的构成

(+ 1 2)
(+ 1 2 (- 3 4))
(+ 1 2 (- 3 4) 5)
(+ 1 2 (- 3 4) 5 (+ 6 7 (+ 8 9)))
(+ 1 2 (- 3 4) (+ 5 6 (+ 7 8)))
(+ 1 2 (- 3 4) (+ 5 6 (+ 7 8)) 9)

可以看到以上表达式里面可以分成两种元素:一个是不可分割的最小元素如 + - 1 2 3 这种 ,还有 (- 3 4)这种复合元素,而复合元素也是由最小的基础元素构成,于是我们得到了第一个规则(复合元素可以被拆分成更小的基础元素和复合元素)。
以(+ 1 2 (- 3 4) 5 (+ 6 7 (+ 8 9)))这个表达式为例,它如果是一棵树长什么样子呢?下面让我们画出它的形态:

我们有了它的样子,但要如何将一个字符串形式的表达式转换成这样一棵树呢? 这是我们接下来要分析的问题
duang duang duang duang...
让我们回到我们的第一个规则 这里还有什么隐藏信息呢?
1.复合元素可拆分
2.基础元素不可拆分
3.复合元素是被“()”包裹的元素
有了这三项我们就可以在进一步的思考了,树树树,树的元素是什么?
1.节点
2.叶子节点
眉目,眉目,有了眉目
节点对应的是复合元素,基础元素对应的是叶子节点,那如何区分复合元素和基础元素呢?
“3.复合元素是被“()”包裹的元素”,是它,是它,就是它。
复合节点里的第一个元素是“(”后的第一个元素,最后一个元素是“)”前的第一个元素,我们又得到了第二个规则;有了上面两个规则我们开始构建我们的第一棵树:
代码:

node

class ExpNode implements Iterable<Object>{

   List<Object> data = new ArrayList<>();
   Node parent;

   public static ExpNode newInstance() {
        return new ExpNode();
   }

    public void add(Object o) {
        if (o instanceof ExpNode) {
            ((ExpNode) o).parent = this;
        }
        super.add(o);
    }

    public Iterator<Object> iterator() {
        return data.iterator();
    }
}

parse

public class Parse {

    public static ExpNode parseTree(String exp) {
        ExpNode root = ExpNode.newInstance();
        buildNode(trimStr(exp), 0, root);
        return (ExpNode) root.iterator().next();
    }

    private static void buildNode(String exp, int level, Cons node) {
        int lIndex = exp.indexOf("(");
        int rIndex = exp.indexOf(")");
        if (rIndex > -1) {
            if (lIndex < rIndex && lIndex > -1) {
                String subExp = exp.substring(lIndex, rIndex + 1);
                if (isBaseLeaf(exp)) {
                    ExpNode a = parseNode(subExp).orElseThrow(RuntimeException::new);
                    node.add(a);
                } else {
                    Optional<ExpNode> nodeOptional = parseNode(subExp);
                    if (nodeOptional.isPresent()) {
                        ExpNode val = nodeOptional.get();
                        node.add(val);
                        node = val;
                    } else {
                        ExpNode objects = ExpNode.newInstance();
                        node.add(objects);
                        node = objects;
                    }
                }
                ++level;
                log.debug("{}{}---{}", createRepeatedStr(level), exp.substring(lIndex), subExp);
                buildNode(exp.substring(lIndex + 1), level, node);
            } else {
                //) b a (+ 8 9) => ) b a ( => b a
                if (lIndex > -1) {
                    String subExp = trimStr(exp.substring(rIndex + 1, lIndex));
                    if (subExp.length() > 0 && !subExp.contains(")")) {
                        String[] values = subExp.split(" ");
                        for (String val : values) {
                            node.parent().add(parseObj(val));
                        }
                    }
                } else {
                    // 所有都是后退
//                    ) b a) => b a) => b a
                    String subExp = exp.substring(rIndex + 1);
                    int r2Index = 1 + subExp.indexOf(")");
                    if (r2Index > 1) {
                        subExp = trimStr(subExp.substring(1, r2Index - 1));
                        if (subExp.length() > 0) {
                            String[] values = subExp.split(" ");
                            for (String val : values) {
                                node.parent().add(parseObj(val));
                            }
                        }
                    }
                }
                --level;
                log.debug("{}{}", createRepeatedStr(level), exp.substring(rIndex));
                buildNode(exp.substring(rIndex + 1), level, node.parent());
            }
        } else {
            log.debug(createRepeatedStr(level));
        }

    }

    private static Optional<ExpNode> parseNode(String exp) {
        String subExp = "";
        if (isBaseLeaf(exp)) {
            //(xx [xx])
            subExp = exp.substring(1, exp.length() - 1);
        } else {
            // (xx [xx] (xx xx xx)
            // (xx [xx] (
            // ((
            subExp = exp.substring(1);
            subExp = subExp.substring(0, subExp.indexOf("("));
            if (subExp.trim().isEmpty()) {
                return Optional.empty();
            }
        }
        String[] keys = subExp.split(" ");
        ExpNode node = ExpNode.newInstance();
        for (int i = 0; i < keys.length; i++) {
            node.add(parseObj(keys[i]));
        }
        return Optional.of(node);
    }

    private static Object parseObj(String val) {
        try {
            return Integer.valueOf(val);
        } catch (NumberFormatException e) {
            if (val.equals("true") || val.equals("false")) {
                return Boolean.valueOf(val);
            } else if (val.indexOf("'") == 0 && val.lastIndexOf("'") == val.length() - 1) {
                return val.replaceAll("\"", "\"");
            } else {
                return val;
            }
        }
    }

    private static boolean isBaseLeaf(String exp) {
        return count(exp, "\\(") == 1 && count(exp, "\\)") == 1 && exp.matches("^\\(.+?\\)$");
    }

    private static int count(String str, String regx) {
        Matcher matcher = Pattern.compile(regx).matcher(str);
        int i = 0;
        while (matcher.find()) {
            i++;
        }
        return i;
    }

    private static String trimStr(String str) {
        String tempStr = str.replace("  ", " ").trim();
        return tempStr.contains("  ") ? trimStr(tempStr) : tempStr;
    }

    private static String createRepeatedStr(int n) {
        return String.join("", Collections.nCopies(n, "--"));
    }
}

当然还有更简单的方式 哈哈哈,将“(”替换成“[”,将“)”转换成“]”,让后用json 解析器解析即可,哈哈哈哈

解释器

在lisp 中语法构成的是列表+前缀表达式的方式来表达,列表可以对应我们刚才提到的复合元素;关于前缀表达式,这里以我们熟悉的中缀表达式为例:1+2+5 这种,其中的 1,2,5 是运算数,+是运算符,运算符在其运算数中间的方式,前缀表达式则是运算符在其运算数最前面的方式,当然还有后缀表达式。
我们还是以 (+ 1 2 (- 3 4) 5 (+ 6 7 (+ 8 9))) 为例:
我们将其放入进我们的Parse.parseTree()中会得到一个形状是

[
    + 
    1 
    2
    [
        - 
        3
        4
    ]
    5
    [
        +
        6
        7
        [
            +
            8
            9
        ]    
    ]
]

这样的一个嵌套列表,然后我们对其进行解释
结合刚才前缀表达式的构成我们会发现列表中的第一个元素是运算符,后面的可以是运算数或列表,然后我们对ExpNode 部署两个方法: 一个是 car方法 用于获取列表内第一个元素,一个是 cdr方法 用于获取列表内去掉第一个元素的剩余元素:

class ExpNode implements Iterable<Object>{

    List<Object> data = new ArrayList<>();
    ...

    public Object car(){
        return data.get(0);
    }

    public ExpNode cdr(){
         List<Object> subData = getData().subList(1, this.getData().size());
        return ExpNode.one(this, subData.toArray()); 
    }

    private static ExpNode one(ExpNode exp, Object... vs) {
        ExpNode objects = ExpNode.newInstance();
        for (Object o : vs) {
            objects.add(o);
        }
        objects.parent = exp;
        return objects;
    }

    ...
}

开始构造我们第一个解释器:

public class JLispInter {

     public static Object inter(ExpNode exp){
        Object car = exp.car();
        ExpNode cdr = exp.cdr();
        if (car instanceof String){
            switch ((String)car){
                case "+":
                    return cdr.data().stream().map(JLispInter::getAtom).mapToInt(o->(Integer)o).sum();
                case "-":
                    return cdr.data().stream().map(JLispInter::getAtom).mapToInt(o->(Integer)o).reduce((x,y)->x-y).orElseThrow(RuntimeException::new);
                case "*":
                    return cdr.data().stream().map(JLispInter::getAtom).mapToInt(o->(Integer)o).reduce((x,y)->x*y).orElseThrow(RuntimeException::new);
                case "/":
                    return cdr.data().stream().map(JLispInter::getAtom).mapToInt(o->(Integer)o).reduce((x,y)->x/y).orElseThrow(RuntimeException::new);
                default:
                    return car;
            }
        }else if (car instanceof ExpNode){
            Object o = inter((ExpNode) car);
            return cdr.isEmpty()?o:inter(cdr);
        }else {
            return cdr.isEmpty()?car:inter(cdr);
        }
    }

    private static Object getAtom(Object o){
        if (o instanceof ExpNode){
            return inter((ExpNode) o);
        }else{
            return o;
        }
    }
}

发现ExpNode还需要部署(data 及 isEmpty) 方法

class ExpNode implements Iterable<Object>{

    List<Object> data = new ArrayList<>();
    ...

    public List<Object> data(){return data};
    public boolean isEmpty(){return data.isEmpty()}
    ...
}

输入

    public static void main(String[] args) {
        System.out.println(inter(Parse.parseTree("(+ 1 2 (- 3 4) 5 (+ 6 7 (+ 8 9)))")));
    }

会得到

37

虽然这个简单解释器只支持四则运算,但它已经具备了解析嵌套列表的能力,为我们后续(如作用域)提供了坚实的基础,后面我们会在这个解释器的基础上增加对 define lambda 关键字的支持,而这些都要依赖两个东西一个是作用域另一个是变量,这两个都是重大的特性,尤其是变量,稍作休息,喝杯水,继续我们的旅途。

支持变量和方法调用

首先让我们在上一个解释器的基础上实现变量的功能,这很简单,关键是把变量和对应的值进行绑定,在java 里面我们可以通过Map来实现它。
定义一个Map我们给他起个名字叫env

Map<String,Object> env = new HashMap<>();

在env 的基础上我们再定义两个方法 分别是定义一个值define(k,v),env(k)

    public static void define(String k, Object v){
        env.put(k,v)
    }

    public static Optional<Object> env(String key){
        return Optional.of(env.get(key));
    }

对 JLispInter 新增一些功能

public class JLispInter {

     public static Object inter(ExpNode exp){
        Object car = exp.car();
        ExpNode cdr = exp.cdr();
        if (car instanceof String){
            switch ((String)car){
                ...
                   case "define":
                    define((String)cdr.car(), inter(cdr.cdr()));
                    return null;
                default:
                   return env((String)car).orElse(car);
            }
        }else if (car instanceof ExpNode){
            Object o = inter((ExpNode) car);
            return cdr.isEmpty()?o:inter(cdr);
        }else {
            return cdr.isEmpty()?car:inter(cdr);
        }
    }

    private static Object getAtom(Object o){
         if (o instanceof ExpNode){
            return inter((ExpNode) o);
        }else if (o instanceof String){
            return env((String)o).orElse(null);
        }else {
            return o;
        }
    }
}

输入

 System.out.println(inter(Parse.parseTree("((define a 5) (+ a 6))")));
 System.out.println(inter("((define a 5) (define b 8) (+ a b))"));

输出

11
13

现在我们已经支持

  • 变量:a
  • 绑定:(define a 5)
  • 四则运算: + - * /

接下来我们再支持 方法 及 调用
方法此处我们选择支持 lambda ,lambda表达式形式如下:
(lambda (x) e)
开始前 我们先对解析器做些改造增加一个符号类型,为了方便后续与String 区分开
Parse

public class Parse {
...
   private static Object parseObj(String val) {
        try {
            return Integer.valueOf(val);
        } catch (NumberFormatException e) {
            if (val.equals("true") || val.equals("false")) {
                return Boolean.valueOf(val);
            } else if (val.indexOf("'") == 0 && val.lastIndexOf("'") == val.length() - 1) {
                return val.replaceAll("\"", "\"");
            } else {
                return Symbols.of(val);
            }
        }
    }
...
}

Symbols

public interface Symbols {
    static Symbols of(String name) {
        return new Symbols.SimpleVar(name);
    }

    String getName();

    @Value
    class SimpleVar implements Symbols {
        String name;

        @Override
        public String toString() {
            return "`" + name;
        }
    }
}

接着我们再对环境进行改造让其可以将 lambda 中的变量与 define 中定义的变量区分开来,并支持当前作用域不存在的变量向上查找,都没有找到报异常。
Env

    public static class Env{

        private  final Map<String,Object> env = new HashMap<>();
        private Env parent;

        public static Env newInstance(Env parent){
            Env env1 = new Env();
            env1.parent = parent;
            return env1;
        }
        
        public  void define(String key,Object val){
            env.put(key,val);
        }

        public  Optional<Object> env(Symbols symbols){
            String symbolsName = symbols.getName();
            return Optional.ofNullable(env.containsKey(symbolsName)?env.get(symbolsName):(parent!=null?parent.env(symbols).orElse(null):null));
        }
    }

JLispInter

public class JLispInter {
   public static Object inter(String exp){
      return inter(Parse.parseTree(exp),Env.newInstance(null));
    }

    // 1
    public static Object inter(ExpNode exp,Env env){
        Object car = exp.car();
        ExpNode cdr = exp.cdr();
        if (car instanceof Symbols){
            switch (((Symbols) car).getName()){
                case "+":
                    //2
                    return cdr.data().stream().map(o->getAtom(o,env)).mapToInt(o->(Integer)o).sum();
                case "-":
                    return cdr.data().stream().map(o->getAtom(o,env)).mapToInt(o->(Integer)o).reduce((x,y)->x-y).orElseThrow(RuntimeException::new);
                case "*":
                    return cdr.data().stream().map(o->getAtom(o,env)).mapToInt(o->(Integer)o).reduce((x,y)->x*y).orElseThrow(RuntimeException::new);
                case "/":
                    return cdr.data().stream().map(o->getAtom(o,env)).mapToInt(o->(Integer)o).reduce((x,y)->x/y).orElseThrow(RuntimeException::new);
                case "define":
                    env.define(cdr.carSymbols().getName(), inter(cdr.cdr(),env));
                    return null;
                case "lambda":
                    return (Function<Object[],Object>) (x)->{
                        ExpNode args = (ExpNode)cdr.car();
                        ExpNode body = cdr.cdr();
                        validateTrue(args.data().size()==x.length,"参数不一致");
                        //3
                        Env env0 = Env.newInstance(env);
                        int i = 0;
                        for (Object argName : args) {
                            env0.define(((Symbols)argName).getName(), x[i]);
                            i++;
                        }
                        return inter(body,env0);
                    };
                default:
                    Optional<Object> env1 = env.env((Symbols)car);
                    // 4
                    boolean isApply = env1.isPresent()&&env1.get() instanceof Function&&exp.isExp();
                    if(isApply){
                        Object v = env1.get();
                        Function<Object[],Object> f = (Function<Object[], Object>) v;
                       return f.apply(cdr.data().stream().map(o -> getAtom(o, env)).toArray());
                    }
                    return env1.orElse(car);
            }
        }else if (car instanceof ExpNode){
            Object o = inter((ExpNode) car,env);
            return cdr.isEmpty()?o:inter(cdr,env);
        }else {
            return cdr.isEmpty()?car:inter(cdr,env);
        }
    }

    private static Object getAtom(Object o,Env env){
        if (o instanceof Cons){
            return inter((Cons) o,env);
        }else if (o instanceof Symbols){
            //5
            return env.env((Symbols) o).orElseThrow(()->new IllegalArgumentException(o+"不存在"));
        }else {
            return o;
        }
    }

    private static void validateTrue(boolean flag, String err){
        if (!flag){
            throw new IllegalArgumentException(err);
        }
    }
}

当我们输入

 System.out.println(inter("((define f (lambda (x y) (+ x y))) (f 9 8))"));
System.out.println(inter("((define add (lambda (x y) (+ x y)))(define f (lambda (o x y) (o x y))) (f add 9 8))"));

会输出

17
17

标记1处我们增加了env 环境变量的入参,使一开始与全局环境绑定 exp 可以与不同的环境进行绑定,从而与全局环境解耦,为后续作用域提供支持。
标记2处将获取数据的从全局变量环境改为具体的上下文变量环境
标记3处每个lambda表达式有自己的变量环境,并且拥有外部的变量环境引用,方便后面可以支持变量向外部变量环境查找
标记4处增加了判断当前表达式第一个元素是否是变量并且绑定的值是否是函数,是的话再(通过isExp)判断是否是表达式(完整表达式,想反的是通过 exp.cdr 截取出来的 表达式片段),然后进行调用 (apply)
标记5处未绑定值的变量抛出异常

总结

此时我们写的JLispInter已经支持了

  • 变量:a
  • 绑定:(define a 5)
  • 四则运算: + - * /
  • 函数 (lambda (x) (exp))
  • 调用 (g exp)

当然还有许多不完善的地方,如解析器还不支持字符串,高阶函数中四则运算 define 等还不能作为入参,不支持匿名函数 ,分支判断 等,这些后面如果有时间的话会写一篇新的文章, 剧透一下支持这些功能的解析器在去年年底就写出来了,如果只是贴代码的话,我想这篇文章会很快。

评论

暂无评论