[Zero]

Hi,

I'm wondering whether or not this instruction set is Turing complete. It's meant to be used in a stack-oriented engine.

Code

Available instructions:
  * cons
  * head
  * tail
  * bind

CONS
  a b cons
  => (a b)

HEAD
  (a b c) head
  => a

TAIL
  (a b c) tail
  => (b c)

BIND
  (a) b bind b
  => a


Example
=======

Program:
    (tail head) second-element bind
    (a b c d) second-element

Expected:
    b

I intuitively believe that it's Turing complete. What do you think?

The idea beyond this step would be to build an ontology of this mechanism, or to build an "understanding" of it. Then, given a goal, being able to automatically construct a program that fulfils the goal. In this very language of course (in another lang / from the outside, it wouldn't be funny).

Ed: No, there's something wrong. It lacks depth. There should be substitution somewhere.

[ivan.moony]

A programming language is said to be Turing complete if we can program fully functional Turing machine in it. Another way is to program lambda calculus in it, as it is proven that lambda calculus is Turing complete.

Interesting choice of operators. Look what I managed to do with a similar set of operators (link), but what I lack is simplicity. It's still a bit of awkward, but I'm working on it.

[ranch vermin]

Youll have to explain it a bit more if im going to understand this,  what is cons.  bind is assign?  heads and tails is 1 and 0?

[Zero]

Youll have to explain it a bit more if im going to understand this,  what is cons.  bind is assign?  heads and tails is 1 and 0?

Ok, I'll do my best.
The "cons",  "head" and "tail" come from the Lisp world. Except in Lisp, "head" and "tail" are rather named "car" and "cdr" (for some obscure/irrelevant historical reason). Say you have a list of elements a b c and d. Lists are written between parentheses : (a b c d). The "head" of the list is a, and the "tail" of the list is the list (b c d). The "cons" builds a pair. In Lisp, lists are single-linked list at low-level, where "car" always point to a value, and "cdr" points on the next pair, or on "nil" to indicate the end of the list. I think the wikipedia article explains it quite well. Interesting stuff.

A programming language is said to be Turing complete if we can program fully functional Turing machine in it. Another way is to program lambda calculus in it, as it is proven that lambda calculus is Turing complete.

Interesting choice of operators. Look what I managed to do with a similar set of operators (link), but what I lack is simplicity. It's still a bit of awkward, but I'm working on it.

I like it, even though I'm not sure I get it all. I'm ok with ?, but what does ! mean?


I realize that I really lack conditional here, because I don't see how I would implement branching with only this instruction set. I found a nice thread on SO about minimal Lisp primitives.

A very very minimal lisp could be a beautiful thing.

[ivan.moony]

I'm ok with ?, but what does ! mean?

It's a complement. For expression `"x"."abc"`, `x.!` stands for everything but `abc`.

[Zero]

got it

[ranch vermin]

means invert.    I didnt understand btw...  still...

[Zero]

Maybe the answer I'm looking for is rather a subset of an existing language, like Js for instance.