Debugging closures is too hard now

so we can map them, for example

We tried this before and decided against it because an inexplicable performance hit, but we should reconsider. This has the potential to significantly clean up the instruction generation code and should (theoretically) perform as well as the reverse execution order.

Fully processed expression that is ready to be compiled. Should have no variable references any more. Tail/ self calls should be resolved. Each macro should have its own type.

We need this because we're doing the same checks multiple times when processing expressions.

cons and car now take off the last element of lists instead of the last. This is very unorthodox in lisps. We should fix this.

Writing a parser from scratch has been fun, but using a parser combinator or parser generator may be more maintainable. Try nom or lalrpop.

(((lambda (n f x) (f (n f x))) (lambda (f x) x)) add1 0) results in a NonFunctionApplication error when it should return 1.

It tries to apply a false to some value, which is probably an indication that we've messed up the move analysis.

Should be a bit faster than peeking at the stack of stack pointers every time.

Very minor optimization. Should save us one check.

So we can have things like (x y a) always represent function application.

This should reduce the current excessive cloning and hence improve performance

Swap a dummy value onto the return stack and swap it. Only do this when the argument is used no more than once in a function!

We're spending a lot of time getting and cloning functions - there's no need for that when we're straight up recursing.

Micro optimization? Do this last!

parser, evaluation etc

Only allow it at top level.

Walking backwards is a remnant from our instruction stack days. Walking forward may perform better.

since we run out of stack space pretty quickly. we'll have to emulate our own stack on the heap and run evaluation in a loop? not sure of the implementation details yet. we should probably have state execute evaluations instead of regular functions? not sure if that would prevent stackgrowth..

Expressions that both car and cdr the same list are common. This split can be done more efficiently without cloning that it is currently done (using at least one clone).

It's got the latest goodies.

This is a big one.

Als je nu een variable uit de state uit wil lezen, dan moet dat via iets als (car (list var)), want var wordt niet geparst.

The current approach works OK, but it has drawbacks.

Firstly, the instruction stack grows very large for deeply recursive calls. This is because we now push the instructions for both branches of a condition.

Further, we clone a vector onto the instruction stack for each function call. Since instructions are not Copy, this is pretty expensive.

It's not immediately clear what the ideal solution here is. We cannot precompile the bytecode for all functions and add them to a large vector since new functions can (only!) be made during runtime. Just pushing to a big vector whenever a function is created at runtime may work, but this may overflow when many one-shot functions are created, for example in (map (lambda (x) (lambda (y) (list x y))) (range 1 10000)).

Ideally, we don't ever clone instructions and yet throw away that which we know won't run any more. One way we may do this is by introducing (another!) stack with an Rc<Vec<Instr>> and usize, where the usize points to current instruction in the instruction vector. Instead of creating two more vectors, these values should probably be combined with the value stack pointer stack into one vector of structs, containing instruction pointer, value pointer and current instruction vector.

Instruction vectors are now Rc<RefCell<Vec<Instr>>>, which is inefficient since it may be as many as three indirections to get a vector and some runtime checking (because of the RefCell). We should probably introduce a new type which combines the properties of Rc, RefCell and Vec. It should be possible to have only a single level of indirection and no runtime checks other than the bounds check.

cons, null?, cdr and car are essential.

Could we write a lisp that has no integers, but only lists? Where we would internally represent ints as ordinals maybe?

We would have to do the recursion in the heap instead of the stack though, because it will probably overflow very quickly.

Useful? Maybe?

Interesting? Definitely!

So that it's not as painful to read results.

Some tests and a benchmark would be useful!

Should make things a bit faster.

Basically this would be a version of bytecode that can have references to variables and arguments, which can be substituted to create closures.

Test case:

(define popn (lambda (l n) (cond (zero? n) l (popn (cdr l) (sub1 n)))))
(popn (list 1 2 3) 2)

returns an ArgumentTypeMismatch error.

This happens because we do partial copy elision from the back instead of the front and that won't work (I think).

(cond #f 0 (add 1)) evaluates to 0. How weird is that? This expression compiles to

Return,
PushValue(Integer(0)),
EvalFunction(1, Some(0)),
PushValue(Function(Custom(CustomFunc(InnerCustomFunc { arg_count: 2, body: Cond((FunctionCall(Value(Function(BuiltIn(CheckZero))), [Argument(StackOffset(1), Scope(0), NeedFull)], false, false), Argument(StackOffset(0), Scope(0), Unconstrained), FunctionCall(Variable(InternedString(3)), [FunctionCall(Value(Function(BuiltIn(AddOne))), [Argument(StackOffset(0), Scope(0), Unconstrained)], false, false), FunctionCall(Value(Function(BuiltIn(SubOne))), [Argument(StackOffset(1), Scope(0), Unconstrained)], false, false)], true, true)), false, true, CanTailCall), returns: false, byte_code: UnsafeCell })))),
PushValue(Integer(1)),
CondJump(3),
PushValue(Boolean(false))]

The EvalFunction is probably not treated as a tail-call during execution. Or it should be followed by a Return instruction.

We need #t and #f for the cond function to work.

Update build instructions, point to online repl

So we have pretty efficient argument copy elision for tail calls and recursive calls, but nothing yet for non-tail calls. We could analyse per end-point of a function whether or not all arguments have been moved. If this is the case, we could replace the regular way of moving arguments (swapping them with a false) by simply copying the bytes to the top of the stack. When the function returns, we would then splice the functions arguments from the value stack without dropping them. Profiling has shown that a lot of time is spent dropping items from the value stack, even though they have usually been replaced and therefore no cleanup is required. We could gain a lot of time here.

This would entail introducing a Return instruction, which encapsulates whether or not the arguments need dropping. We would no longer need to check the instruction pointer on every loop, which would also be a performance win.

Downsides are mostly implementation costs: this will almost certainly entail some unsafe code. Worse, the current infrastructure cannot really additional late stage analysis. To make this feasible, we should probably introduce another intermediate expression type, between the FinalizedExpr and Vec<Instr>. It will be a lot of work.

Shouldn't be too difficult now that we have a stack machine.

vscode stuff, flamegraph, perf data

and add them to .gitignore

Running (add) will produce a panic.

We now state what is wrong, but not the scope or place.

(lambda (x) (lambda (x) x)) should return the identity function regardless of input variable.
Test case:

(define f (lambda (x) (lambda (x) x)))
(list ((f #t) 3) ((f (list)) #f))
(3 #f)

That'd be sooo dope.

Maybe it should be

struct CustomFunc(Rc<RefCell<InnerCustomFunc>>);

where

enum InnerCustomFunc {
    Body(LispExpr),
    Finalized {
        body: FinalizedExpr,
        instr: Rc<Vec<Instr>>,
        specializations: HashMap<SmallVec<ArgType>, Rc<Vec<Instr>>>,
    }
}

?

Would that let us add new specializations when multiple copies of the function are in expressions somewhere and possibly has instructions on the stack? I believe so.

Do note that getting/ setting specializations is pretty expensive in this setup. It may be necessary to get the flexibility we need though.

bool?, int?, func? and list?

I feel like this should work, but it doesn't :-(

(define range (lambda (start end) (cond (> end start) (cons end (range start (sub1 end))) (list start))))