共计 11743 个字符，预计需要花费 30 分钟才能阅读完成。
Symbols
public interface Symbols {static Symbols of(String name) {return new SimpleSymbols(name);
}
String getName();
@Value
class SimpleSymbols implements Symbols {
String name;
@Override
public String toString() {return "`" + name;}
}
}Strings
public interface Strings {static Strings of(String str) {return new SimpleStr(str);
}
String getString();
@Value
class SimpleStr implements Strings {
String string;
@Override
public String toString() {return "'"+ string+"'";}
}
}Cons
@RequiredArgsConstructor(staticName = "of")
public class Cons implements Iterable<Object> {
private final List<Object> data;
private final Cons parent;
private final boolean exp;
public static Cons newInstance(Cons parent) {return Cons.of(new ArrayList<>(), parent, true);
}
public void add(Object obj) {data.add(obj);
}
public Object car() {return iterator().next();}
public Cons carCons() {return (Cons) car();}
public Symbols carSymbols() {return (Symbols) car();}
public Cons cdr() {return Cons.of(data.subList(1, data.size() ), this,false);
}
public Collection<Object> data() {return Collections.unmodifiableList(data);
}
public Cons parent() {return parent;}
public boolean isExp() {return exp;}
public boolean isEmpty(){return data.isEmpty();
}
@Override
public Iterator<Object> iterator() {return data.iterator();
}
@Override
public String toString() {Optional<String> reduce = data.stream().map(Object::toString).reduce((x, y) -> x + "" + y).map(o ->"("+ o +")");
return reduce.orElse("()");
}
}Parse
@Slf4j
public class Parse {
private static final String PREFIX = "(";
private static final String SUFFIX = ")";
public static Cons parse(String expStr) {return parse(format(replaceSpace(expStr)), Cons.newInstance(null));
}
private static Cons parse(String expStr, Cons r) {String tempExpStr = expStr.trim();
boolean isPush = tempExpStr.indexOf(PREFIX) == 0;
String nextStr = tempExpStr.substring(1);
int prefixIndex2 = nextStr.indexOf(PREFIX);
int suffixIndex2 = nextStr.indexOf(SUFFIX);
int nextFixIndex = (prefixIndex2==-1||suffixIndex2==-1? Math.max(prefixIndex2,suffixIndex2):Math.min(prefixIndex2, suffixIndex2) );
if(nextFixIndex>-1){if (isPush) {Cons astList = Cons.newInstance(r);
String subExpStr = nextStr.substring(0, nextFixIndex);
exp2List(subExpStr).forEach(astList::add);
r.add(astList);
return parse(tempExpStr.substring(nextFixIndex+1), astList);
} else {String subExpStr = nextStr.substring(0, nextFixIndex);
exp2List(subExpStr).forEach(r.parent()::add);
return parse(tempExpStr.substring(nextFixIndex+1), r.parent());
}
}else{return r;}
}
private static List<Object> exp2List(String exp){return exp.trim().length()==0? Collections.emptyList(): Arrays.stream(exp.trim().split(" ")).map(Parse::parseObj).collect(Collectors.toList());
}
private static String format(String str) {return str.contains("") ? format(str.replaceAll(" "," ")) : str;
}
private static String replaceSpace(String str){if(str.contains("'")){int first = str.indexOf("'");
int last = str.substring(first+1).indexOf("'")+first+1;
String substring = str.substring(first, last + 1);
substring = substring.replaceAll("","\\\\\\O");
return str.substring(0, first) + substring + replaceSpace(str.substring(last + 1));
}
return str;
}
private static Object parseObj(String atom){
try {return Integer.valueOf(atom);
} catch (NumberFormatException e) {if (atom.equals("true") || atom.equals("false")) {return Boolean.valueOf(atom);
} else if (atom.indexOf("'") == 0 && atom.lastIndexOf("'") == atom.length() - 1) {return Strings.of(atom.replaceAll("'","").replaceAll("\\\\O", " "));
} else {return Symbols.of(atom);
}
}
}
public static void main(String[] args) {log.debug("{}", (parse("(1 2 3 4 5 6 7 (8 9 10) 11 12 (13 (14 15)) 16 true's 5 8''456' a b c (7 8 9))")));
log.debug("{}", parse("(let ((cons (lambda (x y) (lambda (g) (g x y (lambda (a) (set! x a)) (lambda (a) (set! y a)))))) (car (lambda (f) (f (lambda (x y sx sy) (x))))) (cdr (lambda (f) (f (lambda (x y sx sy) (y))))) (set-car! (lambda (f a) (f (lambda (x y sx sy) ((sx a) f))))) (set-cdr! (lambda (f a) (f (lambda (x y sx sy) ((sy a) f)))))) (cdr (set-cdr! (cons 1 2) 3)))"));
}
}Env
public 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 setEnv(Symbols symbols, Object val) {setEnv(symbols.getName(),val);
}
public void setEnv(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));
}
public boolean contains(Symbols symbols){return env.containsKey(symbols.getName());
}
public Env parent(){return parent;}
}JLispInterpreter3
@Slf4j
public class JLispInterpreter3 {
private static final Predicate<Object> IS_EXP = o -> o instanceof Cons;
private static final Predicate<Object> IS_SYMBOLS = o -> o instanceof Symbols;
private static final Predicate<Object> IS_FUN = o -> o instanceof Function;
private static final Predicate<Object> IS_ATOM = o -> o instanceof Number || o instanceof String || o instanceof Boolean;
private static final BiPredicate<Cons, Object> CAN_APPLY = (exp, v) -> IS_FUN.test(v) && exp.isExp();
public static Object eval(String exp) {Env root = Env.newInstance(null);
FunManager.FUNCTIONAL.forEach(root::setEnv);
return eval(Parse.parse(exp), Env.newInstance(root));
}
private static Object eval(Cons exp, Env env) {Object car = exp.car();
Cons cdr = exp.cdr();
if (IS_EXP.test(car)) {Object v = eval(exp.carCons(), env);
if (CAN_APPLY.test(exp, v)) {return apply(v, cdr, env);
}
return cdr.isEmpty() ? v : eval(cdr, env);
} else if (IS_SYMBOLS.test(car)) {Object v = env.env(exp.carSymbols()).orElseThrow(() -> new IllegalArgumentException(exp.parent() + ":" + exp.carSymbols() + "not define"));
if (CAN_APPLY.test(exp, v)) {return apply(v, cdr, env);
}
return cdr.isEmpty() ? v : eval(cdr, env);
} else if (IS_ATOM.test(car)) {return cdr.isEmpty() ? car : eval(cdr, env);
} else {return cdr.isEmpty() ? car : eval(cdr, env);
}
}
private static Object apply(Object v, Cons cdr, Env env) {return ((Function<ApplyArgs, Object>) v).apply(ApplyArgs.of(cdr, env, () -> cdr.data().stream().map(o -> getAtom(o, cdr, env)).toArray(), JLispInterpreter3::eval));
}
private static Object getAtom(Object o, Cons exp, Env env) {if (IS_EXP.test(o)) {return eval((Cons) o, env);
} else if (IS_SYMBOLS.test(o)) {return eval(toSubCons(o, exp), env);
} else {return o;}
}
private static Cons toSubCons(Object obj, Cons parent) {return Cons.of(Collections.singletonList(obj),parent, false);
}
@Value(staticConstructor = "of")
public static class ApplyArgs {
Cons exp;
Env env;
Supplier<Object[]> lazyArgs;
BiFunction<Cons, Env, Object> eval;
}
}FunManager
class FunManager{private static final Map<String, Function<ApplyArgs, Object>> FUNCTIONAL = new ConcurrentHashMap<>();
static {reg("+", applyArgs -> toIntStream(applyArgs.getLazyArgs()).reduce(Integer::sum).orElse(null));
reg("-", applyArgs -> toIntStream(applyArgs.getLazyArgs()).reduce((a, b) -> a - b).orElse(null));
reg("*", applyArgs -> toIntStream(applyArgs.getLazyArgs()).reduce((a, b) -> a * b).orElse(null));
reg("/", applyArgs -> toIntStream(applyArgs.getLazyArgs()).reduce((a, b) -> a / b).orElse(null));
reg("lambda", applyArgs -> lambda(applyArgs.getExp(), applyArgs.getEnv()));
reg("define", FunManager::define);
reg("let", applyArgs -> let(applyArgs.getExp(), applyArgs.getEnv(), applyArgs.getEval()));
reg("set!", applyArgs -> set(applyArgs.getExp(), applyArgs.getEnv(), applyArgs.getEval()));
reg("apply", applyArgs -> apply0(applyArgs.getExp(), applyArgs.getEnv()));
regBooleanFun();
reg("if", applyArgs -> if0(applyArgs.getExp(), applyArgs.getEnv(), applyArgs.getEval()));
reg("cond", applyArgs -> cond(applyArgs.getExp(), applyArgs.getEnv(), applyArgs.getEval()));
}
private static void reg(String optKey, Function<ApplyArgs, Object> opt) {FUNCTIONAL.put(optKey, opt);
}
private static Function<ApplyArgs, Object> lambda(Cons cdr, Env env) {return (applyArgs) -> {Object[] x = applyArgs.getLazyArgs().get();
Cons args = cdr.carCons();
Cons body = cdr.cdr();
validateTrue(args.data().size() == x.length, "参数不统一");
Env env0 = Env.newInstance(env);
int i = 0;
for (Object argName : args) {env0.setEnv(((Symbols) argName), x[i]);
i++;
}
return applyArgs.getEval().apply(body, env0);
};
}
private static Object if0(Cons cdr, Env env, BiFunction<Cons, Env, Object> eval) {Cons car = cdr.carCons();
if (isaBoolean(eval.apply(car, env))) {Object then = cdr.cdr().car();
return getAtom(then, cdr.cdr(), env);
} else {if (cdr.cdr().cdr().data().size() > 0) {return eval.apply(cdr.cdr().cdr(), env);
}
return null;
}
}
private static Object cond(Cons cdr, Env env, BiFunction<Cons, Env, Object> eval){Cons car = cdr.carCons();
Cons predicateExp = car.carCons();
Cons body = car.cdr();
if(isaBoolean(eval.apply(predicateExp, env))){return eval.apply(body, env);
}else{Cons elseCdr = cdr.cdr();
if(elseCdr.data().size()==1){
// 去掉括號
while (IS_EXP.test(elseCdr.car())&&elseCdr.data().size()==1){elseCdr = elseCdr.carCons();
}
validateTrue(IS_SYMBOLS.test(elseCdr.car())&&elseCdr.carSymbols().getName().equals("else"),"cond last item not else key");
return eval.apply(elseCdr.cdr(), env);
}
return cond(elseCdr, env, eval);
}
}
private static Object define(ApplyArgs applyArgs) {Cons cdr = applyArgs.getExp();
Object val = applyArgs.eval.apply(cdr.cdr(), applyArgs.getEnv());
validateTrue(!applyArgs.getEnv().contains(cdr.carSymbols()), "Do not repeat the definition" + cdr.carSymbols());
applyArgs.getEnv().setEnv(cdr.carSymbols(), val);
return null;
}
private static Object let(Cons cdr, Env env, BiFunction<Cons, Env, Object> eval) {Object car0 = cdr.car();
validateTrue(car0 instanceof Cons && cdr.data().size() == 2, "please check" + car0);
Env env0 = Env.newInstance(env);
Cons car = cdr.carCons();
Cons body = cdr.cdr().carCons();
for (Object con : car) {validateTrue(IS_EXP.test(con), "please check" + con);
Cons item = (Cons) con;
Symbols var = item.carSymbols();
validateTrue(!env0.contains(var), "Do not repeat the let" + var);
env0.setEnv(var, eval.apply(item.cdr(), env));
}
return eval.apply(body, env0);
}
private static Object set(Cons cdr,Env env, BiFunction<Cons, Env, Object> eval) {Symbols var = cdr.carSymbols();
Object val = eval.apply(cdr.cdr(),env);
validateTrue(env.env(var).isPresent(), "not definition set! error" + var);
Env envParent = env;
while (!envParent.contains(var)) {envParent = envParent.parent();
}
envParent.setEnv(var, val);
return null;
}
private static Object apply0(Cons cdr, Env env) {Object f = cdr.car();
f = getAtom(f, cdr, env);
if (IS_FUN.test(f)) {return apply(f, cdr.cdr(), env);
} else {throw new IllegalArgumentException("apply" + cdr);
}
}
private static void validateTrue(boolean flag, String err) {if (!flag) {throw new IllegalArgumentException(err);
}
}
private static void regBooleanFun() {
reg("and", applyArgs -> {Object[] ts = applyArgs.getLazyArgs().get();
return Stream.of(ts).allMatch(FunManager::isaBoolean) ? ts[ts.length - 1] : false;
});
reg("or", applyArgs -> Stream.of(applyArgs.getLazyArgs().get()).filter(FunManager::isaBoolean).findFirst().orElse(false));
reg("not", applyArgs -> {Object[] ts = applyArgs.getLazyArgs().get();
validateTrue(ts.length == 1, applyArgs.getExp() + "not args only one");
return !isaBoolean(ts[0]);
});
reg("<", applyArgs -> predicate(applyArgs.getExp(), applyArgs.getLazyArgs(), (x, y) -> (x instanceof Integer && y instanceof Integer) ? (Integer) x < (Integer) y : x.toString().length() < y.toString().length()));
reg("<=", applyArgs -> predicate(applyArgs.getExp(), applyArgs.getLazyArgs(), (x, y) -> (x instanceof Integer && y instanceof Integer) ? (Integer) x <= (Integer) y : x.toString().length() <= y.toString().length()));
reg("=", applyArgs -> predicate(applyArgs.getExp(), applyArgs.getLazyArgs(), Object::equals));
reg("!=", applyArgs -> predicate(applyArgs.getExp(), applyArgs.getLazyArgs(), (x, y) -> !x.equals(y)));
reg(">", applyArgs -> predicate(applyArgs.getExp(), applyArgs.getLazyArgs(), (x, y) -> (x instanceof Integer && y instanceof Integer) ? (Integer) x > (Integer) y : x.toString().length() > y.toString().length()));
reg(">=", applyArgs -> predicate(applyArgs.getExp(), applyArgs.getLazyArgs(), (x, y) -> (x instanceof Integer && y instanceof Integer) ? (Integer) x >= (Integer) y : x.toString().length() >= y.toString().length()));
}
private static Object predicate(Cons exp, Supplier<Object[]> lazyArgs, BiPredicate<Object, Object> predicates) {Object[] objs = lazyArgs.get();
validateTrue(objs.length > 1, exp + "args qty > 1");
Object o = objs[0];
for (int i = 1; i < objs.length; i++) {Object o1 = objs[i];
boolean b = predicates.test(o, o1);
if (!b) {return b;}
o = o1;
}
return true;
}
private static boolean isaBoolean(Object o) {if (o instanceof Boolean) {return (Boolean) o;
} else {return !o.equals(0);
}
}
private static Stream<Integer> toIntStream(Supplier<Object[]> supplierObjs) {return Stream.of(supplierObjs.get()).map(Object::toString).map(Integer::valueOf).collect(Collectors.toList()).stream();}
}
正文完
