7
$\begingroup$

John Tromp defines a version of the lambda calculus that is encoded in binary: https://tromp.github.io/cl/cl.html

a) Does there exist a concatenative version of this language (or its combinatory equivalent)?

b) Does there exist a concatenative version restricted to the primitive recursive functions (e.g. as per Combinators for the Primitive Recursive Functions)?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ I'm not sure what you mean by concatenative. Do you mean something like here: en.wikipedia.org/wiki/Concatenative_programming_language or a language in which the concatenation of any two programs is a valid program? $\endgroup$ – cody Aug 18 '15 at 14:32
  • $\begingroup$ @cody - Actually, it looks like just the condition that the concatenation of any two programs is a valid program suffices. If anyone can say what languages with this weaker condition are called, I'll edit the question/title accordingly. $\endgroup$ – NietzscheanAI Aug 18 '15 at 14:37
  • 1
    $\begingroup$ With this weaker condition, I believe that Iota, Jot and Zot are examples of a): semarch.linguistics.fas.nyu.edu/barker/Iota/zot.html $\endgroup$ – NietzscheanAI Aug 18 '15 at 14:38
  • $\begingroup$ You should turn your comment into an answer. $\endgroup$ – cody Aug 18 '15 at 14:40
  • 1
    $\begingroup$ This is a related post. cstheory.stackexchange.com/questions/31883/… $\endgroup$ – Joshua Herman Aug 19 '15 at 0:11
0
$\begingroup$

As per @cody's comment above, if we require only that "the concatenation of any two programs is a valid program" then I believe that Iota, Jot and Zot (semarch.linguistics.fas.nyu.edu/barker/Iota/zot.html) are examples of a).

However, IMO the more interesting question part of the question is b)...

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.