concatenative

Interpreter for stack based DSL. See details in the rpl-take-home-project1-clj.pdf paper.

Design choices

Decision was made to support continuations to be able to add continue and break even for custom loops (there is an example of a custom each in call-cc tests).

The simplest way to support continuations is to write interpreter in continuation passing style (CPS). Main point here is to support mutual recursion with tail call optimization (trampoline). There is also a performance overhead with CPS.

2 optimizations are used:

• separating analyze and evaluation steps;
• using mutability for environment.

Java interop is implemented like in Clojure:

• (invoke> .method 1) to invoke the method;
• (invoke> ClassConstructor.) to create an instance;

The same with functions parameters and multi-arity.

Lambdas are just quoted forms. Check quotation-test.

Call/cc> is like a quotation with a side effect: continuation is implicitly added in the stack.

Polymorphism

As types are evaluated differently, there is a necessity to dispatch based on them. The first question here is whether it should be an opened or a closed system.

The decision was made to go with an opened one to make it possible to extend the code without modifications. For example, this repository may be used as a library and another app will be able to implement eval for different types.

Next question is what to use — protocols or multimethods.

Protocols are good when we need to dispatch based on types, and performance is 5-100 times better, depending on the actual code, clj- and jvm versions.

Multimethods are good if dispatching on a value or several values/types.

Taking this into account, protocols seem to be good for Interpreter implementation, as types (not values) are evaluated differently.

And methods are good for Clj-kondo hooks, as Clj-kondo works with nodes, but nodes are not exposed (impossible to require them). Instead node's' :tag values could be used to dispatch upon.

Unfortunately, there is a bug: TokenNode returns nil instead of a tag, so the issue was created, and cond was used as a temporary solution.

Error messaging / detection

The most useful thing is to know which particular line (in our case expression) contains a problem. As the code is transformed by macro, jvm exceptions won't do the job.

Two approaches are used to deal with this.

1. Code inspections are smart enough to find typos and errors like division by zero, popping from empty stack, or insufficient arguments count.

TODO:

• support: defn>, each>, times>, java calls, stack manipulation functions;

2. If anything crashes, we have usual jvm exception wrapped into ExceptionInfo with State attached, where we can inspect what step the program stumbled over:

(defstackfn f2 [!a] !a 1 (invoke> / 2) 3 4)
(f2 0)
(ex-data *e) ;; => 
        {:cause {:error-call {:fn /, :args (1 0)}},
         :state {:program ((invoke> / 2) 3 4), :stack [0 1], :env {!a 0}},
         :eval (invoke> / 2)}

This approach is ok while programs are not huge.

Editor integration

Clj-kondo is used to inspect the code.

Warnings from terminal:

clj-kondo --lint src/dumch/concatenative.clj

Should work out of the box if your editor supports LSP or clj-kondo directly:

IntelliJIdea

Put cursor on defstackfn -> right mouse click -> show context action -> resolve ... -> choose defn.

Install Clojure Extras plugin to support clj-kondo inspections.

And turn of preferences -> editor -> inspections -> clojure -> unresolved symbols;

Tests

clj -X:test

License

Copyright © 2022 M1

EPLv1.0 is just the default for projects generated by clj-new: you are not required to open source this project, nor are you required to use EPLv1.0! Feel free to remove or change the LICENSE file and remove or update this section of the README.md file!

Distributed under the Eclipse Public License version 1.0.