denkspuren

The kernel of a concatenative programming language can be easily implemented using a rewriting system. As a proof-of-concept the presented implementation fully relies on Scheme's rewriting system at macro expand time! All one needs is define-syntax and -- in order to provide access to Scheme's built-in procedures -- a single defmacro. (Apologies, if the formatting makes the code below hard to read. If you like to get the Scheme code, just drop me an email.) Rewriting rules concerning the data stack (ds) are written as follows: (rule swap : (@d ... snd fst) ==> (@d ... fst snd)) ^^^^ ^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^ word datastack before datastack after Note that the topmost element of the data stack is the rightmost element in the notation above. Rewriting rules concerning the data _and_ the program stack (ps) are written as (rule call : (@d ... (@q ...)) (@p ...) ==> (@d ...) (@q ... @p ...)) ^^^^ ^^^^^^^^^^^^^^^^^ ^^^^^^^^ ...

I think I solved the problem of type inference for "call" in concatenative languages. In a private mail, Slava Pestov (the creator of Factor ) challenged me with the problem of inferring types for the bi and bi@ combinator. In essence, the problem boils down to "call". The solution, Christopher Diggins proposes in his papers on Cat is not without complications. First let me introduce a notation for describing the effect of a word via substitutions. I use pattern matching. $X matches a single word, #X matches a single word _or_ quotation, and @X matches any number of words/quotations. To refer to a quotation, I use squared brackets. For example, "[ $X ]" matches a quotation with a single word inside like "[ 7 ]". Furthermore, I explicitly distinguish the data stack and the program stack and separate them with a bar "|". Here are some example substitutions: @D #X | dup @P ==> @D #X #X | @P @D #X #Y | swap @P ==> @D #Y #X | @P @D $X...