For a personal learning and fun project, I build an abstract virtual machine based on a stack. The instructions are simple and act on the top of the stack only. There are also stack operators such as SWAP, DUP or ROT. I have no way to manage memory, pointers, or variables (it's all on the stack after all). Typically, here is a very simple example:

    DUP           -- duplicate the top of the stack
    MUL           -- consumes the first two values at the top of the stack and pushes the product
    RET           -- come back after the last call of `square`.

    PUSH 6        -- pushes `6` on the stack
    CALL square   -- call the label `square`

Such a VM and IR can be related to a concatenative language, which offers the interesting feature of quotations; so this program "becomes" the following:

square == dup mul
main   == 6 square

My question is to what extent this type of VM (and therefore more broadly simple concatenative languages) is limited (or not). Without any use of FFI, I wonder if impure languages can be fully compiled into it, and if so, how?

For example, with a naive and trivial compilation, is the following C-like program compilable in a pure concatenative approach?

void assign_and_double(int *dest_ptr, int src)
    *dest_ptr = src * 2;

I had imagined a somewhat ridiculous approach that would simulate pointers with quotations: the quotation would represent the address, and the data would be in the quotation, for the example given just above, one could imagine this:

assign_and_double(&num, 4)  ==  4 [num] assign_and_double

But my hunch stopped there...

Thank you if you know how to enlighten me about this!


I'm editing my question to give an update on Turing-complete languages.

I suspect my little language to be Turing-complete because it meets the criteria for.

In compilation classes, we are taught how to compile from high level to low level (and/or from "pure to impure"), and in fact my question had more of a "practical" side because I would like to do the opposite. Beyond the fact that it is theoretically possible to compile a complete Turing-complete language to another, I wonder how this could be done. The particular example of pointers (C-like) interested me here (I "target" not to be too broad).

Indeed, I would like to be able to generalize a rough and trivial compilation from a very simple program written in C using pointers to my abstract machine (which may be similar to a concatenative language like Joy (as it is the implementation that inspired me, although Forth is also a close candidate)).

So the question is how to do this, or to make it less vague: what are the tracks to explore?

  • $\begingroup$ Can you clarify exactly what you are asking? Are you asking if it is Turing-complete? Forth is Turing-complete, and I suspect your language is too, but we don't have a specification of which instructions it has so it's hard to be sure. If it's Turing complete, any other Turing-complete language can be compiled into it. See also cs.stackexchange.com/q/991/755. $\endgroup$ – D.W. Apr 16 '20 at 17:29
  • $\begingroup$ @D.W. I edited my question in the hope that it would be more specific. I hope that's clearer? $\endgroup$ – Foxy Apr 16 '20 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.