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, 2015 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, 2015 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, 2015 at 14:38
  • $\begingroup$ You should turn your comment into an answer. $\endgroup$
    – cody
    Aug 18, 2015 at 14:40
  • 1
    $\begingroup$ This is a related post. cstheory.stackexchange.com/questions/31883/… $\endgroup$
    – Joshua Herman
    Aug 19, 2015 at 0:11

1 Answer 1

Reset to default
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.