# Jon Purdy: Why Concatenative Programming Matters

## John Nowak — 2012-02-13 13:37:49

    http://evincarofautumn.blogspot.com/2012/02/why-concatenative-programming-matters.html

## William Tanksley, Jr — 2012-02-13 17:08:18

    John Nowak <john@...> wrote:

     > http://evincarofautumn.blogspot.com/2012/02/why-concatenative-programming-matters.html

     Not bad at all.

    We've talked about the wikipedia page... It's an accurate description,

    but doesn't communicate very well. I don't know what else to say.

    -Wm

## eas lab — 2012-02-13 17:27:06

    It's going to take me a few days to work through: -

    /2012/02/why-concatenative-programming-matters.html

    but I'm sending some immediate feedback, because I was grappling with this

    exact issue lately.

    IMO one should state up-front:

      BECAUSE WE WANT MORE RESULTS WITH LESS EFFORT.

    That's what Backus' paper did.

    And then one should backwards-chain eg.

    because 'serial-data-transformation' means that when you do stage N, you.

    don't need to be concerned about earlier stages except N-1.

    Minimal-coupling's value is founded on human psychology: less to remember.

    And [for high level programming] each data-transformer is a stand-alone

    module, whose cost can be amortized over multiple projects.

    When you explain how a TV receiver works, you start from the picture;

    not from the RF-amplifier.

    I particularly appreciate the ascii-diagrams of how the 'impedance

    matching' of the functions works.  Last week I wasted many hours

    researching how monads achieve this, but right now I haven't got a clue.

    Thanks,

    == Chris Glur.

     On 2/13/12, John Nowak <john@...> wrote:

    > http://evincarofautumn.blogspot.com/2012/02/why-concatenative-programming-matters.html

    >

## John Nowak — 2012-02-13 19:05:03

    On 02/13/2012 12:08 PM, William Tanksley, Jr wrote:

      > We've talked about the wikipedia page... It's an accurate

     > description, but doesn't communicate very well. I don't know

     > what else to say.

     Apologies: This email is a bit of a brain dump and ill-proofread.

    I think maybe the most interesting thing about concatenative

    languages isn't stressed enough in the article: Unlike most every

    other type of programming language on the planet, there is no

    syntax for function application. All you get is composition and,

    if higher-order, quotation.

    I think the second most interesting thing is that all functions

    operate on possibly empty sequences containing arbitrary amounts

    of program state. It's this "all the state" element that gives

    concatenative languages their character. For example, Backus's FL

    does not do this; functions that need one number take just that

    number and functions that need two take a pair; never do

    functions take the entire state of a program as they usually do

    in Forth or Factor.

    For example, a tail-recursive 'length' function in a

    concatenative language might be:

       length = [0] dip loop where

         loop = [null?] [drop] [[1 +] dip tail loop] if

       end

    And in FL:

       def length ≡ f ∘ [id, ~0] where {

         def f  ≡ isnull ∘ xs → n; loop ∘ [tl ∘ xs, + ∘ [~1, n]]

         def xs ≡ s1

         def n  ≡ s2

       }

    A quick guide to the FL program:

    - '∘' is composition

    - '~' is constant (i.e. \x y -> x)

    - the square brackets denote "construction"; construction returns

       a function that, when applied to an argument, returns a list of

       length N where N is the number of functions provided by the

       programmer; each element in the result corresponds to one

       function after it was applied to the same input as all other

       functions (e.g. '[f, g]:x  == <f:x, g:x>', where ':' is FL's

       syntax for application and angle brackets denote lists)

    - conditionals are written 'a → b; c', where 'b' and 'c' are the

       functions conditionally applied to the input to get the result

    - 's1' and 's2' select the first and second elements from a list

    - 'tl' is the tail operation

    These two programs are, to me, radically different. The

    concatenative program is decidedly "flat" and feels very

    imperative. The FL program, on the other hand, is "nested" like

    applicative programs usually are and feels, at least to me,

    rather declarative; the fact that you can consider each function

    within the two constructions to be completely independent is

    probably the main reason for this. The independence of functions

    also allows you to write aliases for selectors as I did above. In

    fact, FL offers a form of pattern matching for conveniently

    locally-defining such selector functions via double-square

    brackets:

       def length ≡ f ∘ [id, ~0] where {

         def f ≡〚xs, n〛→

           isnull ∘ xs → n; loop ∘ [tl ∘ xs, + ∘ [~1, n]]

       }

    This is very different from concatenative languages where

    combinators like 'bi@' allow the functions provided to step on

    each other as the second function runs on top of the stack

    returned from the first. This is the reason I gave up on

    concatenative languages; the equational reasoning possible when

    all functions operate on "the stack" just isn't great. I think

    the fact that faking variables in FL is trivial while faking

    variables in something like Factor requires a rather complex

    transformation is evidence of this. I also think the lack of

    useful equational reasoning is why things feel so imperative once

    you get past the pretty examples in the Joy literature. Maybe I

    just need more combinators.

    To be fair, I should point out that having all functions work on

    "the stack" does have its advantages. In particular, higher-order

    programming in FL is pretty gnarly. In fact, doing it requires

    pervasive use of "lifting" which is, essentially, a way of

    modifying functions so that they take an additional argument full

    of all the other stuff you want to use (and hence reminds me a

    bit of stack-based programming). More info here:

       http://theory.stanford.edu/~aiken/publications/trs/FLProject.pdf

    I guess what I'm trying to say is that "every function takes the

    entire program state as input", or at least a good chunk of it

    (as with Joy's 'infra'), is *really important*. While this fact

    is arguably implicit in the definition on Wikipedia, it's not

    spelled out at all. Maybe I can add some insight to it in the

    next few days.

    - jn

## William Tanksley, Jr — 2012-02-13 20:20:57

    John Nowak <john@...> wrote:

     > I think the second most interesting thing is that all functions

    > operate on possibly empty sequences containing arbitrary amounts

    > of program state. It's this "all the state" element that gives

    > concatenative languages their character.

     Indeed. And you're right when you elsewhere say that this gives

    concatenative languages an imperative character.

    You're right that any arbitrary function must be able to access all of

    the state; but it need not be true that any specific function must be

    able to access all the state. Modern concatenative languages use

    typechecking to make sure that no function attempts to consume stack

    state that doesn't match the function's declaration; but other types

    of checking don't have such an obvious typechecking solution. (Were

    you the one who designed a concatenative language with side-effect

    checking?)

    It seems obvious to me that in order to add effect checking, you have

    to formally define the effect. Forth's dictionary could be formally

    defined and checking there from implemented.

    Of course, this is easier to say than to do, and I haven't even said it.

    I also admit that by saying this, I have conceded your point. This has

    the result of making reordering hard.

     > This is very different from concatenative languages where

    > combinators like 'bi@' allow the functions provided to step on

    > each other as the second function runs on top of the stack

    > returned from the first. This is the reason I gave up on

    > concatenative languages; the equational reasoning possible when

    > all functions operate on "the stack" just isn't great. I think

     That specific example need not retain all of its problems, obviously

    -- you can define similar combinators to require the forks to have

    identical static types, and then effectively isolate the forks from

    each other. Factor chooses not to do that, and thereby adds semantics

    which are useful for its purposes.

     > (as with Joy's 'infra'), is *really important*. While this fact

    > is arguably implicit in the definition on Wikipedia, it's not

    > spelled out at all. Maybe I can add some insight to it in the

    > next few days.

     Fair point. We await your input. Fthagn.

     > - jn

     -Wm

## John Nowak — 2012-02-13 21:23:17

    On 02/13/2012 03:20 PM, William Tanksley, Jr wrote:

      > You're right that any arbitrary function must be able to access

     > all of the state; but it need not be true that any specific

     > function must be able to access all the state. Modern

     > concatenative languages use typechecking to make sure that no

     > function attempts to consume stack state that doesn't match the

     > function's declaration;

     This is certainly true; or at least it would be if the languages

    actually excited. With types, something like 'bi' can be

    restricted so that the second function uses no more than one

    element and thus you can consider both functions independently.

    (For the record, I mistakenly referred to 'bi@' in a previous

    email. I meant 'bi'.)

    Even without types, this is possible if you have 'infra' to run a

    function on a stack-on-the-stack and some sort of 'concat'

    operation to join a stack-on-the-stack onto the main stack

    itself. Assuming curly braces denote stacks, we need only the

    following primitives:

       {A} [B] infra   ==  {A B}

        A  {B} concat  ==  A B

       {A}  B  push    ==  {A B}

    This is enough to write a "safe" 'bi':

       bi = [keep] dip [{} swap push] dip infra concat

    With this version of 'bi', you'll get a stack underflow error if

    the second quotation to 'bi' attempts to use more than one

    element. Since we're not using types, you might as well pass an

    argument to some generic version of 'bi' that says how many

    arguments to reserve for the second function; just push that

    many onto the stack before calling 'infra'.

      > Were you the one who designed a concatenative language with

     > side-effect checking?)

     Yes, although it is just a little trick of attaching a variable

    to function types that can either be "effectful" or "not

    effectful". You can infer it via unification. Not much to it.

    It's a bit coarse though because it doesn't offer any form of

    local effects with a pure interface as you can get with the ST

    monad or with linear or uniqueness types (though they could be

    added if you wanted).

    - jn

## John Nowak — 2012-02-13 21:25:27

    On 02/13/2012 04:23 PM, John Nowak wrote:

     > This is certainly true; or at least it would be if the languages

    > actually excited.

     Existed. Sorry.

    - jn

## William Tanksley, Jr — 2012-02-13 22:05:32

    John Nowak <john@...> wrote:

     > William Tanksley, Jr wrote:

    >  > You're right that any arbitrary function must be able to access

    >  > all of the state; but it need not be true that any specific

    >  > function must be able to access all the state. Modern

    >  > concatenative languages use typechecking to make sure that no

    >  > function attempts to consume stack state that doesn't match the

    >  > function's declaration;

    > This is certainly true; or at least it would be if the languages

    > actually excited.

     Fair point. (I misread this word as "exited", and thought you were

    talking about termination proofs. Yow.)

     > With types, something like 'bi' can be

    > restricted so that the second function uses no more than one

    > element and thus you can consider both functions independently.

    > (For the record, I mistakenly referred to 'bi@' in a previous

    > email. I meant 'bi'.)

     Well, you can also copy the needed elements into place -- type

    checking can handle the rest. That way you can provide every branch

    with the data it needs according to the documented semantics of the

    forking word (whether each branch sees the same stack, or the branches

    see sequential data from the initial stack).

    And you're right that the easy way is to use "infra"... Much less

    infrastructure.

     >  > Were you the one who designed a concatenative language with

    >  > side-effect checking?)

    > Yes, although it is just a little trick of attaching a variable

    > to function types that can either be "effectful" or "not

    > effectful". You can infer it via unification. Not much to it.

    > It's a bit coarse though because it doesn't offer any form of

    > local effects with a pure interface as you can get with the ST

    > monad or with linear or uniqueness types (though they could be

    > added if you wanted).

     Ah, I see. Yes, I was thinking more of defining structures on which

    effects could occur, and checking those effects.

    Forth has a dictionary on which effects can occur, for example.

     > - jn

     -Wm

## eas lab — 2012-02-14 05:01:36

    This commentor appropriately acknowledges the important cognitive-load aspect:-

    ]the code was always *intensely* write-only since you had to have a

    ]mental model of exactly what was on the stack where to even hope to

    ]follow it.

    *nix piping is beautifully simple yet powerfull, since the stack only contains

    "it" [the previous output]. So that at each/every stage, you only need to know

    about your single-supplier.

    ]     2 :: FAA. (A) -> (A, int)

    ]     3 :: FAB. (B) -> (B, int)

    ok

    ]   We match up the types:

    ]

    ]     (A, int) = (B)

    ?! does this mean 'assume they match and see what that implies'?

    -------------

    Apparently, if the output of stageN includes item/s in addition to what

    stageN+1 needs, they can be left on the stack for stageN+2. But he and

    Haskell/monads seems to 'wrap' the extra item/s and pass it on, and

    imply that some automagic relieves you from the mental load of

    remembering what was left on the stack for all possible

    combinations of stages afterN+1 ?

## eas lab — 2012-02-14 06:05:02

    ]   By substituting, we get a new polymorphic type for 3 within the

    ]   expression:

    ? does this mean '3 is polymorphic because it can be written as

    infinitely typed'?

    ? what does "within the expression" mean ?

    ]     3 :: FAC. (C, int) -> (C, int, int)

    => let 3 be a function, which ForAllC, maps (C, int) to (C, int, int)

    ]   This matches the non-polymorphic type:

    ]     3 :: FAA. (A, int) -> (A, int, int) = FAB. B -> (B, int)

    ? is there a bracket missing here ?

    ]   So the final type of the expression becomes:

    ]     2 3 :: FAA. (A) -> (A, int, int)

    ? why/how ? is this formal maths or Haskell-poetry ?

## William Tanksley, Jr — 2012-02-14 06:10:30

    eas lab <lab.eas@...> wrote:

     > This commentor appropriately acknowledges the important cognitive-load aspect:-

     Indeed.

     > ]the code was always *intensely* write-only since you had to have a

    > ]mental model of exactly what was on the stack where to even hope to

    > ]follow it.

     He's talking about HP RPN code -- fairly low-level code. It's not

    entirely fair to attribute cognitive load to stack code when most of

    it is due to bad language design.

     > *nix piping is beautifully simple yet powerfull, since the stack only contains

    > "it" [the previous output]. So that at each/every stage, you only need to know

    > about your single-supplier.

     True for pipes. Not true for programming in general -- you need more

    than one data item per function call.

     > Apparently, if the output of stageN includes item/s in addition to what

    > stageN+1 needs, they can be left on the stack for stageN+2. But he and

    > Haskell/monads seems to 'wrap' the extra item/s and pass it on, and

    > imply that some automagic relieves you from the mental load of

    > remembering what was left on the stack for all possible

    > combinations of stages afterN+1 ?

     Haskell would be a fine language to learn; it gives a large reservoir

    of concepts to discuss language design.

    But no, monads don't relieve your mind; they tend to require a lot of

    careful thought, especially if you start mixing them. They have

    interesting mathematical properties. You can implement a concatenative

    language in Haskell using monads; the stack language is a monoid

    (well, according to von Thun).

    -Wm

## John Nowak — 2012-02-14 21:13:07

    The LtU discussion is now here:

       http://lambda-the-ultimate.org/node/4448

    My post contains some critiques of the original article and a

    translation of concatenative code to Haskell to show there's nothing

    special going on with respect to "row polymorphism"; the Haskell code is

    pretty fun and probably worth a look:

       http://lambda-the-ultimate.org/node/4448#comment-69234

## eas lab — 2012-02-24 18:01:52

    Yes certainly Concatenative Programming Matters, but to convince others

    who have vast experience/INERTIA with old stuff one should do a.

    Hello-world demo before giving the theoretical analysis of cat-style.

    I want to take this real-life problem to illustrate how powerfull

    [i.e. big results from small effort] the concatenative/data-flow programming

    method is; which *nix is using all the time, without even mentioning it.

    My problem is to know what path each of 28 consols, spread over 11 workspaces

    has.  So that when an 'item' arrives I know which of the 28 consols is

    setup to handle the item. If I don't know that consol-11 is already setup to

    handle 'planets', when venus arrives, I'll open a new/redundant and even

    possibly-conflicting 'planets-path'.

    The particular unix syntax, which I too don't know well, is unimportant to the

    principle demonstrated here. The key idea is to see how the data is transformed

    [mostly just filtered] through multiple stages.

     pstree -p | awk '{print $2}'

    which syntax we'll ignore [only the "|" character is important] means

     <give me the table showing the number of each process/consol>

            AND PASS THAT THROUGH THE FILTER WHICH

    cuts off the 1st field of each line ie. give me the 2nd fieldS.

    Fields are separated by space or tab - by default.

    The 2nd field of a  typical line [of the 28] looks like:

    |-xterm(6877)---bash(6879)---mc(6895)---bash(6897)

    .

    We want to know the 'path' corresponding to process: 6897, and the other 27.

    `lsof | wc -l`

    again has the magic syntax, using the "|" <concatenative> symbol, and

    says give me the 'lsof' table

            AND PASS THAT THROUGH THE FILTER WHICH

    counts the number of lines.

    I my case I get 4099, which is not part of the problem, but just gives you

    an idea of the size of the data to be filtered/manipulated.

    The 1 of 4099 lines which contains the path corresponding to the 6897 process

    looks like:-

    bash    6897     root  cwd     DIR    22,17   4096    384273 /mnt/p17/Feb2012

    where the second field: 6897; is the process-number which has the last-field:

     /mnt/p17/Feb2012 as the required path.

    Unfortunately 27 other lines also have 6897 as their 2nd field.

    I believe that 27+1=28 is UNrelated to the 28 consols - just coincidental.

    It seems that the required line [one for each consol] is distinguished by "cwd"

    as the 4th field. The details of the table are irrelevant to the demonstration

    of how 'cat style solves big problems easily'. I just looked at the table for

    a distinguishing field for the required line.

    So the line which CONTAINS the key [for 6897] is got by:

       lsof | grep 6897 | grep cwd

    which means:

     gimme the table of open-files

     but only the lines which contain 6897

     and only those which contain cwd.

    So that's 3 instructions to get the one of 4099 lines.

    and a final ONE instruction say:

     gimme the last field only.

    And here/now :  lsof | grep 6897 | grep cwd | awk '{print $9}'

    gives me:.

       /mnt/p17/Feb2012

    And fluent <one line *nix jockeys> would know how to easily append the path:

     /mnt/p17/Feb2012  to the end of the `pstree-p` generated line, to give:

    |-xterm(6877)---bash(6879)---mc(6895)---bash(6897) = /mnt/p17/Feb2012

      for each of the 28 consols.

    So far the whole experiment has only used *SIX* instructions !! I think.

    And a vocabulary of 4 different instructions:

      pstree, awk, lsof, grep.

    How can you possibly deny that Concatenative Programming Matters,

     when it can do such a BIG job with a vocabulary of 4 instructions?

    ----------------------------

    It seems that each line of the 1st-flow must have the 2nd-flow

     appended/attached to it.

    So the 2nd flow is nested inside the 1st.

    But that takes the problem outside of pure cat-style/piping to another.

    dimension.

    What I'm trying to work out is: how did the unix designers know what

    filters to design, to act as 'primitive' instructions?.

    I.e how to get a optimal set of primitives <which are Turing complete?> ?

    -----

    Re. impedance matching: *nix seems to have solved this, without discussing the

    theoretical background, by having the in/output of 'all' filters being

    <a sequence of text lines>.  This leads me to think that a text editor

    would be a good exercise to test/experiment with cat-style, since the.

    in/out could be fixed N-lines of L-len each?

    == Chris Glur.

## eas lab — 2012-03-19 08:29:00

    I've become increasingly enthusiastic/obsessed about cat-style.

    Clearly there's some ambiguity about 'the definition'.

    I'll give my definition AFTER I've shown WHAT problems it solves.

    Backus correctly stated the problem before he gave his proposed solution.

    That's called goal-directed, and it's the right way, because that's how human.

      minds work. We used to call it top-down-programming.

    Almost all write-ups on 'Concatenative Programming' show a solution looking

    for a problem.  MvThun claimed that joy could help do formal proofs, since

    it allowed algebraic-like manipulation. That would be great; but did anyone

    ever see any such problems solved; eg. proof of an algorithm, via joy?

    The 'hello world' concept is powerfull, because it's a FULL demonstration,

    which can later be successively refined/extended. Cat-style allows this too.

    So the meta-problem is:

     how to minimise the concept-counts that need to be handled simultaneously.

    I.e. reduce the coupling. It's about the human mind, not technology.

    So that eg. you could progress the problem and come back to it next week;

    like evolution works: it doesn't NEED to remember and understand previous

    steps. And this is vital for serial programmERS.

    This little outburst is motivated by another discovery how *nix almost allows

    good cat-style: you can 'concatenate the concepts' but not write them linearly

    from left to right.

    The example problem: I want to reuse a [few-line] script/file, by copying it

    to a new-name and editing it. It's called 'Sa'. But I don't know where it is

    located. But unix helps with:

     whereis Sa  == Sa: /usr/local/sbin/Sa

    But I only want the 2nd 'string/field' so:

     whereis Sa | awk '{print $2}' == /usr/local/sbin/Sa

    [DON'T LOOK AT THE SYNTAX: just see blobs concatenated by "|" ]

    So that's where Sa is located. But I want to DO something with Sa.

    Clearly the evolving structure is:

    [[[noun1 verb1] verb2] verb3]

       where any verb can have modifiers: like 'awk' has "2": for the 2nd string.

    And [[noun1 verb1] verb2] is the noun that verb3 operates on, because

    [noun verb] maps to a noun.

    But we don't want a lispy-bracket-style. So use a forth-style, where for

    readability, we'll put each stage/data-transformation on a new-line:

    Sa whereis |

    2 FieldOnly |     ;; "2" is a modifyer, which joins in the 'data flow'

    dog CopyFileAsName

    What's really annoying me in linux, is that I have to wrap the existing code

    and put <copy it> in FRONT, and then put the copy-destination at the end,

    i.e. split/bracket my existing code, instead of just concatenating to it.

    So:

       cp ` whereis Sa | awk '{print $2}'` dog

    does it...

    The concatenative concepts are all there in *nix, but the syntax should be:

      Sa whereis | 2 Field | dog CopyFileAsName

    So I define cat-style as 'the ability to serially transform data, by applying

    a <verb/operation> to it, without needing to know/remember how the data was

    achieved, by previous stages of transformation'..

    That's the concept, which *nix achieves. It just lacks the good/clean syntax.

    Thanks,

    == Chris Glur. PS. has *nix not got a: <fileName> <printContents>  command?

    I may have asked this before, [I can't get an answer]: How does *nix.

    returning 0 for success and non-zero for different types of function's errors,

    instead of the conventional boolean approach, relate to cat/pipe-lining?

## John Nowak — 2012-03-19 15:52:55

    On 03/19/12 04:29, eas lab wrote:

     > ...

     *explodes*

## William Tanksley, Jr — 2012-03-19 17:38:18

    John Nowak <john@...> wrote:

     > *explodes*

     John, thanks for your comments here and on Lambda the Ultimate. Unless

    everyone's already unsubscribed, we got quite a few new list members

    who are probably wondering what this is all about. The answer: no,

    it's not all about Unix shell syntax for pipes, even though those are

    interesting in their own rights and on their own mailing lists.

    As you saw on the LtU discussion, it's more about the idea of

    languages whose syntactic properties exactly match their semantic

    properties, so that parsing goes away. As Nowak said earlier in this

    thread, that's not a miracle cure-all, but as I also said, it's very

    interesting anyhow.

    The discussion on LtU turned to several interesting points --

    typechecking, Kerby's and my zeroone language, and so on... We should

    start this list moving again. I'm wrapped up in a few things at the

    time, but zeroone's been morphing a little recently, and I'd like to

    talk about it more. Anyone wanna listen?

    -Wm

## Robbert van Dalen — 2012-03-19 19:33:25

    i still remember the days when basicode programs were broadcasted!

    you could actually hear the 0's and 1's.

    Seriously, i do want to hear about your zeroone language!

    what's morphing?

    i'm experimenting with a combination of datalog, the chemical abstract machine and constraint handling rules with postfix syntax.

    nothing concrete yet, but i believe that (syntactic) postfix expressions match (reactive) molecules, whatever that means.

    cheers,

    R.

     On Mar 19, 2012, at 6:38 PM, William Tanksley, Jr wrote:

    > John Nowak <john@...> wrote:

    > > *explodes*

    >

    > John, thanks for your comments here and on Lambda the Ultimate. Unless

    > everyone's already unsubscribed, we got quite a few new list members

    > who are probably wondering what this is all about. The answer: no,

    > it's not all about Unix shell syntax for pipes, even though those are

    > interesting in their own rights and on their own mailing lists.

    >

    > As you saw on the LtU discussion, it's more about the idea of

    > languages whose syntactic properties exactly match their semantic

    > properties, so that parsing goes away. As Nowak said earlier in this

    > thread, that's not a miracle cure-all, but as I also said, it's very

    > interesting anyhow.

    >

    > The discussion on LtU turned to several interesting points --

    > typechecking, Kerby's and my zeroone language, and so on... We should

    > start this list moving again. I'm wrapped up in a few things at the

    > time, but zeroone's been morphing a little recently, and I'd like to

    > talk about it more. Anyone wanna listen?

    >

    > -Wm

    >

## Robbert van Dalen — 2012-03-19 19:36:13

    http://en.wikipedia.org/wiki/BASICODE

    it was a dutch/german experience.

     On Mar 19, 2012, at 8:33 PM, Robbert van Dalen wrote:

    > i still remember the days when basicode programs were broadcasted!

    > you could actually hear the 0's and 1's.

    >

    > Seriously, i do want to hear about your zeroone language!

    > what's morphing?

    >

    > i'm experimenting with a combination of datalog, the chemical abstract machine and constraint handling rules with postfix syntax.

    > nothing concrete yet, but i believe that (syntactic) postfix expressions match (reactive) molecules, whatever that means.

    >

    > cheers,

    > R.

    >

    > On Mar 19, 2012, at 6:38 PM, William Tanksley, Jr wrote:

    >

    >> John Nowak <john@...> wrote:

    >>> *explodes*

    >>

    >> John, thanks for your comments here and on Lambda the Ultimate. Unless

    >> everyone's already unsubscribed, we got quite a few new list members

    >> who are probably wondering what this is all about. The answer: no,

    >> it's not all about Unix shell syntax for pipes, even though those are

    >> interesting in their own rights and on their own mailing lists.

    >>

    >> As you saw on the LtU discussion, it's more about the idea of

    >> languages whose syntactic properties exactly match their semantic

    >> properties, so that parsing goes away. As Nowak said earlier in this

    >> thread, that's not a miracle cure-all, but as I also said, it's very

    >> interesting anyhow.

    >>

    >> The discussion on LtU turned to several interesting points --

    >> typechecking, Kerby's and my zeroone language, and so on... We should

    >> start this list moving again. I'm wrapped up in a few things at the

    >> time, but zeroone's been morphing a little recently, and I'd like to

    >> talk about it more. Anyone wanna listen?

    >>

    >> -Wm

    >>

    >

## stevan apter — 2012-03-19 19:38:05

    yes please.

    more zeroone.  (sounds like a planet in flash gordon's univese, doesn't it?)

     On Mar 19, 2012, at 3:33 PM, Robbert van Dalen wrote:

    > i still remember the days when basicode programs were broadcasted!

    > you could actually hear the 0's and 1's.

    >

    > Seriously, i do want to hear about your zeroone language!

    > what's morphing?

    >

    > i'm experimenting with a combination of datalog, the chemical abstract machine and constraint handling rules with postfix syntax.

    > nothing concrete yet, but i believe that (syntactic) postfix expressions match (reactive) molecules, whatever that means.

    >

    > cheers,

    > R.

    >

    > On Mar 19, 2012, at 6:38 PM, William Tanksley, Jr wrote:

    >

    >> John Nowak <john@...> wrote:

    >>> *explodes*

    >>

    >> John, thanks for your comments here and on Lambda the Ultimate. Unless

    >> everyone's already unsubscribed, we got quite a few new list members

    >> who are probably wondering what this is all about. The answer: no,

    >> it's not all about Unix shell syntax for pipes, even though those are

    >> interesting in their own rights and on their own mailing lists.

    >>

    >> As you saw on the LtU discussion, it's more about the idea of

    >> languages whose syntactic properties exactly match their semantic

    >> properties, so that parsing goes away. As Nowak said earlier in this

    >> thread, that's not a miracle cure-all, but as I also said, it's very

    >> interesting anyhow.

    >>

    >> The discussion on LtU turned to several interesting points --

    >> typechecking, Kerby's and my zeroone language, and so on... We should

    >> start this list moving again. I'm wrapped up in a few things at the

    >> time, but zeroone's been morphing a little recently, and I'd like to

    >> talk about it more. Anyone wanna listen?

    >>

    >> -Wm

    >>

    >

    >

    >

    > ------------------------------------

    >

    > Yahoo! Groups Links

    >

    >

    >

## William Tanksley, Jr — 2012-03-20 02:42:12

    Robbert van Dalen <robbert.van.dalen@...> wrote:

     > i still remember the days when basicode programs were broadcasted!

    > you could actually hear the 0's and 1's.

     Wow, that's something. I remember typing in BASIC programs from

    magazines, but I'd never heard of that.

     > Seriously, i do want to hear about your zeroone language!

    > what's morphing?

     Oh, I'd mentioned that "my zeroone language was morphing" -- I meant

    it's been changing. The internal changes are big enough that my main

    copy doesn't currently work :-), and at the same time I'm playing with

    some theoretical ideas that might possibly make it easier to construct

    new bases for the language. Good thing I'm using version control.

    I've got a few more things to do today, so I can't post much more; but

    anyone who doesn't know what I'm talking about when I say "new bases"

    should start reading http://tunes.org/~iepos/joy.html. What you should

    try to understand is his sentence: "The eight combinators presented

    above are by no means all of the combinators; there are infinitely

    many combinators. However, eventually we'll show that from the above

    combinators, it is possible to construct all other combinators. In

    fact, it will turn out that there is a base consisting of just two

    combinators, from which all other combinators can be constructed."

    Once that sentence makes some sense to you we're ready to go. You

    won't have to understand how to construct combinators; you'll only

    need to understand the basic ideas behind that sentence: combinators,

    a base consisting of a number of combinators, and the concept that

    combinators can be used to construct other combinators.

     > i'm experimenting with a combination of datalog, the chemical abstract machine and constraint handling rules with postfix syntax.

    > nothing concrete yet, but i believe that (syntactic) postfix expressions match (reactive) molecules, whatever that means.

     Wow, that's cool. I've always wanted to experiment with chemical

    abstract machines, but my employer does random testing. Ha hah.

    Seriously, though, I read up on CAMs; sounds right up your alley (from

    your work with the Enchilada language), as it would fit nicely on

    highly parallel machines. I'd like to hear more.

     > R.

     -Wm

## Robbert van Dalen — 2012-03-20 07:26:08

    > I've got a few more things to do today, so I can't post much more; but

    > anyone who doesn't know what I'm talking about when I say "new bases"

    > should start reading http://tunes.org/~iepos/joy.html. What you should

    > try to understand is his sentence: "The eight combinators presented

    > above are by no means all of the combinators; there are infinitely

    > many combinators. However, eventually we'll show that from the above

    > combinators, it is possible to construct all other combinators. In

    > fact, it will turn out that there is a base consisting of just two

    > combinators, from which all other combinators can be constructed."

     Does zeroone have exactly two combinators and are they different from iota or jot?

    http://semarch.linguistics.fas.nyu.edu/barker/Iota/

     > Once that sentence makes some sense to you we're ready to go. You

    > won't have to understand how to construct combinators; you'll only

    > need to understand the basic ideas behind that sentence: combinators,

    > a base consisting of a number of combinators, and the concept that

    > combinators can be used to construct other combinators.

     i believe the real challenge is to find two combinators that have the most 'impact'.

    i.e. their combinations must spawn maximal useful 'functionality'.

    is that what zeroone is about? to find the best two combinators?

     > Wow, that's cool. I've always wanted to experiment with chemical

    > abstract machines, but my employer does random testing. Ha hah.

    > Seriously, though, I read up on CAMs; sounds right up your alley (from

    > your work with the Enchilada language), as it would fit nicely on

    > highly parallel machines. I'd like to hear more.

     the OER language. (http://translate.google.nl/#nl%7Cen%7Coer%0A%0A)

    just a small example of what i'm after.

    consider the following unordered soup (multi-set) of numbers and multiply operators (molecules)

    3,*,2,*,*,4,5

    note that the above has specific (syntactic) order but that's just syntax. comma's separate molecules.

    now every molecule in the soup can (react) with another molecule, by concatenating them together to form a new molecule.

    all this can happen at any time, concurrently.

    molecules themselves also be rewritten concurrently, when they form valid molecules to be reduced to other molecules.

    the rewriting of molecules follow 'standard' concatenative semantics.

    this is a possible sequence of reactions.

    1) 3 *,* 4,5 2,*

    2) 3 * *,5 2 * 4

    3) 3 * * 10 4

    -- it seems where are stuck at 3).

    but OER has a circular 'stack' so we can shift (roll) the expression:

    3 * * 10 4

    to

    4) 10 4 3 * *

    5) 10 12 *

    6) 120

    any order of execution will produce result 6.

    of course, we need to consider confluence when we combine non-associative operators.

    the idea is that OER will always produce all possible results (postfix expressions that can't be rewritten anymore), lazily.

    in that sense, OER is non-deterministic, just like prolog, but i'm not sure if i should pursuit this direction.

    cheers,

    R.

     > > R.

    >

    > -Wm

    >

## William Tanksley, Jr — 2012-03-20 15:35:36

    Robbert van Dalen <robbert.van.dalen@...> wrote:

     >> I've got a few more things to do today, so I can't post much more; but

    >> anyone who doesn't know what I'm talking about when I say "new bases"

    >> should start reading http://tunes.org/~iepos/joy.html. What you should

    >> try to understand is his sentence: "The eight combinators presented

    >> above are by no means all of the combinators; there are infinitely

    >> many combinators. However, eventually we'll show that from the above

    >> combinators, it is possible to construct all other combinators. In

    >> fact, it will turn out that there is a base consisting of just two

    >> combinators, from which all other combinators can be constructed."

    > Does zeroone have exactly two combinators and are they different from iota or jot?

    > http://semarch.linguistics.fas.nyu.edu/barker/Iota/

     Yes, exactly two; and yes, the languages are different. Iota and Jot

    are not concatenative. One simple consequence of this is that in Iota

    or Jot, knowing what a particular sequence of zeros and ones means in

    one part of a program doesn't tell you what that same sequence means

    at a different part of the program. Those two languages have a tree

    sequence, so by copying and pasting a string into a new place you

    produce a string with a different meaning; the one string may actually

    be parsed into two or more strings that get passed to completely

    different combinators.

    iepos proved that although you can produce a parsed combinator

    language with only one complete combinator (in the literature usually

    called X), this is an illusion caused by the availability of arbitrary

    nesting. If you remove parentheses from the language, you need at

    least two combinators. In a completely concatenative combinator

    language, one of the combinators in the base MUST accept no input and

    produce some output, while the other combinator will execute at least

    one of its inputs.

     >> Once that sentence makes some sense to you we're ready to go. You

    >> won't have to understand how to construct combinators; you'll only

    >> need to understand the basic ideas behind that sentence: combinators,

    >> a base consisting of a number of combinators, and the concept that

    >> combinators can be used to construct other combinators.

    > i believe the real challenge is to find two combinators that have the most 'impact'.

     Sure, but what does that *mean*? It's a very tough question and may in

    fact have no answer. I've built most of an evolutionary algorithm to

    test bases against each other to try to find the "best" one. Figuring

    how to measure bestness is TOUGH. I've come up with some measures, but

    none of them are great. (My fitness function builds an array of

    fitness metrics and randomly compares them.)

     > i.e. their combinations must spawn maximal useful 'functionality'.

     Yes, although either a base forms ALL functionality or it isn't

    complete. (Well, iepos does explain some alternate definitions of

    "complete" that have some interesting results.)

    But there might be some other measures of "functionality"; for

    example, would a base be "better" if it provided short bitstrings with

    known meanings (i.e. commonly used combinators)? The base I use now is

    defined so that "drop" is "01". What if "nip" or "swap" could be

    provided as a short bitstring as well, thus allowing selection of a

    single item out of stack junk? And what about quotations -- how hard

    or easy is it to express an enquoted version of "0" and "1", and might

    a language be better if it provided a complete basis, plus a short way

    to express quotations of its constituent combinators, plus concat to

    build arbitrary quotations? The latter language would be easy to build

    a Joylike language on, and the automatically produced zeroone code

    would be decent (unlike a language where the enquoted combinators were

    long and complex).

    That probably made little sense to most people here, but it does

    explain the questions I'm wrestling with.

     > is that what zeroone is about? to find the best two combinators?

     Sort of, yes. Zeroone is just a name for the set of languages.

    "Tworing" is the project's name; it includes a brute force

    superoptimizer, an evolutionary algorithm to find the best two

    combinators, and a language constructor for zeroone(s). (Technically,

    zeroone is more of an abstract machine language than it is a language;

    there's no names or anything like that. Tworing might eventually

    include at least an assembler, already includes a superoptimizer, and

    might include a high level language based on zeroone.)

     >> Seriously, though, I read up on CAMs; sounds right up your alley (from

    >> your work with the Enchilada language), as it would fit nicely on

    >> highly parallel machines. I'd like to hear more.

    > the idea is that OER will always produce all possible results (postfix expressions that can't be rewritten anymore), lazily.

    > in that sense, OER is non-deterministic, just like prolog, but i'm not sure if i should pursuit this direction.

     Sounds like there's a lot of work to be done there. Cool! It also

    reminds me of DNA computing.

     > R.

     -Wm

## Robbert van Dalen — 2012-03-22 17:43:37

    > iepos proved that although you can produce a parsed combinator

    > language with only one complete combinator (in the literature usually

    > called X), this is an illusion caused by the availability of arbitrary

    > nesting.

     can you give an example of a flat - two combinator - base?

    does such flat base mean that you can cut an valid expression anywhere to produce two valid expressions?

     > > i believe the real challenge is to find two combinators that have the most 'impact'.

    >

    > Sure, but what does that *mean*? It's a very tough question and may in

    > fact have no answer. I've built most of an evolutionary algorithm to

    > test bases against each other to try to find the "best" one. Figuring

    > how to measure bestness is TOUGH. I've come up with some measures, but

    > none of them are great. (My fitness function builds an array of

    > fitness metrics and randomly compares them.)

     what's the meaning of life?

    the only we can say for certain, is that we - humans - are more likely to reproduce in 'hostile' environment than any other species.

    for zeroone to survive it must be a meme that easily sticks to a programming brain.

    zeroone certainly sticks as a name :).

    as a concept, zeroone is also interesting.

     > Yes, although either a base forms ALL functionality or it isn't

    > complete. (Well, iepos does explain some alternate definitions of

    > "complete" that have some interesting results.)

     yes, i also only consider complete combinator bases - but that they are also capable in generating short programs for small problems.

    or, even better - short programs for big problems.

     > But there might be some other measures of "functionality"; for

    > example, would a base be "better" if it provided short bitstrings with

    > known meanings (i.e. commonly used combinators)? The base I use now is

    > defined so that "drop" is "01".

     so

    101    and   001

    reduce to empty?

     > What if "nip" or "swap" could be

    > provided as a short bitstring as well, thus allowing selection of a

    > single item out of stack junk?

     can this be done with only 2 combinators?

    can you give an example

     > And what about quotations -- how hard

    > or easy is it to express an enquoted version of "0" and "1", and might

    > a language be better if it provided a complete basis, plus a short way

    > to express quotations of its constituent combinators, plus concat to

    > build arbitrary quotations?

     again, can quotations be encoded with only 2 combinators, without nesting?

     > The latter language would be easy to build

    > a Joylike language on, and the automatically produced zeroone code

    > would be decent (unlike a language where the enquoted combinators were

    > long and complex).

     i think you should stick to flat, otherwise all the nice properties of flatness are lost.

    and then you'll just end up with an alternative Joy (which happens to be encoded in bitstrings).

     > (Technically,

    > zeroone is more of an abstract machine language than it is a language;

    > there's no names or anything like that. Tworing might eventually

    > include at least an assembler, already includes a superoptimizer, and

    > might include a high level language based on zeroone.)

     how does the super optimizer, runtime and other components relate to each other?

    does the super optimizer choose the set of combinators?

    is the high level language independent of the choosen set of combinators?

    when and how do you fix the a sequence of combinators  (like 01 = drop)? is that encoded by the fitness functions.

    etc.

    cheers,

    R.

## William Tanksley, Jr — 2012-03-22 20:27:59

    Robbert van Dalen <robbert.van.dalen@...> wrote:

     >> iepos proved that although you can produce a parsed combinator

    >> language with only one complete combinator (in the literature usually

    >> called X), this is an illusion caused by the availability of arbitrary

    >> nesting.

    > can you give an example of a flat - two combinator - base?

     Yes.

    Given 'q' and 'k', both defined in iepos' webpage, we can define:

    "0" = [] [q] [k]

    and

    "1" = k.

    So, for example, "01" evaluates as follows:

    "01" =

    [] [q] [k] "1" =

    [] [q] [k] k =

    [] k.

    But since 'k' evaluates its topmost argument and drops its next

    argument, the net result is to always drop one argument. (This is the

    base I normally use.)

    Of course, I haven't given you an example that happens to use the

    universal constructor 'q'; this example just dropped it. I can execute

    'q' using the bit sequence "0011":

    "0011" =

    "0" "01" "1" =

    "0" drop "1" =

    [] [q] [k] drop "1" =

    [] [q] "1" =

    [] [q] k = q.

    Notice that I used the previous result that "01" is a drop.

     > does such flat base mean that you can cut an valid expression anywhere to produce two valid expressions?

     Exactly -- at literally any bit boundary. This also means that every

    bitstring is a valid program, which means that the natural numbers are

    valid programs; to enumerate ALL the valid programs I use the natural

    numbers (i.e. positive integers, not zero), converted to bitstrings,

    stripped of their high bit (this easily includes the empty program,

    encoded by "1", and programs with leading zeros).

     >> > i believe the real challenge is to find two combinators that have the most 'impact'.

    >> Sure, but what does that *mean*? It's a very tough question and may in

    >> fact have no answer. I've built most of an evolutionary algorithm to

    >> test bases against each other to try to find the "best" one. Figuring

    >> how to measure bestness is TOUGH. I've come up with some measures, but

    >> none of them are great. (My fitness function builds an array of

    >> fitness metrics and randomly compares them.)

    > what's the meaning of life?

    > the only we can say for certain, is that we - humans - are more likely to reproduce in 'hostile' environment than any other species.

     I feel inadequate -- compared to extremophilic archeobacteria -- for

    having such a difficult time reproducing around hydrothermal vents,

    then. :-)

     > for zeroone to survive it must be a meme that easily sticks to a programming brain.

     Naw. If that's what anyone wants, stay away from zeroone. It's a

    purely computing-theoretic concept.

     > zeroone certainly sticks as a name :).

     Indeed. I really like "tworing".

     > as a concept, zeroone is also interesting.

     That's where it's at.

     >> Yes, although either a base forms ALL functionality or it isn't

    >> complete. (Well, iepos does explain some alternate definitions of

    >> "complete" that have some interesting results.)

    > yes, i also only consider complete combinator bases - but that they are also capable in generating short programs for small problems.

    > or, even better - short programs for big problems.

     Yes, you're right; but it's fairly easy to prove that you can always

    make some programs shorter at the expense of others. It's very

    unlikely that this kind of tradeoff would extend to the macroscopic

    effect of making a complete program shorter. On the other hand, I do

    suspect it could make describing a more useful base (that is, one with

    more than two combinators) easier, and the resulting sublanguage would

    be easier for humans to program in. If the elements of that

    sublanguage were as short as possible, then it's likely that programs

    carefully written using the sublanguage would be candidates for

    maximally short programs, and thus decent estimates for the true

    k-complexity of the programs produced.

     >> But there might be some other measures of "functionality"; for

    >> example, would a base be "better" if it provided short bitstrings with

    >> known meanings (i.e. commonly used combinators)? The base I use now is

    >> defined so that "drop" is "01".

    > so

    > 101    and   001

    > reduce to empty?

     No. First: 1 does not simply return an element. Second: 0 returns 3

    elements, not just 1. The shortest nontrivial no-op is "0010101",

    which runs "0" to place 3 items on the stack, then runs "01" three

    times to pop each of them off.

     >> What if "nip" or "swap" could be

    >> provided as a short bitstring as well, thus allowing selection of a

    >> single item out of stack junk?

    > can this be done with only 2 combinators?

    > can you give an example

     Yes, it can be done -- but the bases I've chosen so far make it very

    hard. No, I can't give a useful example; I don't remember right off

    because there are too many bits.

     >> And what about quotations -- how hard

    >> or easy is it to express an enquoted version of "0" and "1", and might

    >> a language be better if it provided a complete basis, plus a short way

    >> to express quotations of its constituent combinators, plus concat to

    >> build arbitrary quotations?

    > again, can quotations be encoded with only 2 combinators, without nesting?

     Yes. I have constructed this; what you do is use my searcher to find a

    "short" program that has the same stack effect as "[0]", another

    program that has the same effect as "[1]", and a program that performs

    "concat". That proves that I can form all combinators.

     >> The latter language would be easy to build

    >> a Joylike language on, and the automatically produced zeroone code

    >> would be decent (unlike a language where the enquoted combinators were

    >> long and complex).

    > i think you should stick to flat, otherwise all the nice properties of flatness are lost.

    > and then you'll just end up with an alternative Joy (which happens to be encoded in bitstrings).

     Well, building this other language is a secondary goal. I actually am

    more interested in exploring flatness.

     >> (Technically,

    >> zeroone is more of an abstract machine language than it is a language;

    >> there's no names or anything like that. Tworing might eventually

    >> include at least an assembler, already includes a superoptimizer, and

    >> might include a high level language based on zeroone.)

    > how does the super optimizer, runtime and other components relate to each other?

     The superoptimizer uses the runtime to test candidates against the

    combinator goal. Note that the superoptimizer can only test true

    combinators, but within that realm it's quite effective.

     > does the super optimizer choose the set of combinators?

     No; you have to give it to it.

     > is the high level language independent of the choosen set of combinators?

     That's tough to answer; I haven't produced it yet. In theory I suppose

    you could write base-independent code in it, but that's not why I'm

    considering writing it -- it's more intended to help me talk about the

    low-level concepts. I'm also interested in what a high level flat

    language might look like; nobody knows.

    Even more esoteric, though, is the question of what else can happen to

    a flat language. I vaguely suspect that a flat language might be able

    to address control flow. Such a language would not be concatenative in

    the same sense, although it would hold the same aspect in other ways.

    I don't know what it would be.

     > when and how do you fix the a sequence of combinators  (like 01 = drop)? is that encoded by the fitness functions.

     The fitness functions currently test for how good of a base a given

    pair of functions make. As always, the problem is that I don't really

    know what makes a base better; I have some ideas that I've tossed into

    an array, but I don't KNOW.

    To make matters worse, I based this genetic algorithm on my old

    superoptimizer; but the genetic algorithm produces things that aren't

    pure combinators, so the comparison that worked well for the

    superoptimizer is BAD for it. It's obvious to any student of computer

    science that you can't ever hope to compare two functions, but since I

    can already compare combinators correctly, I can make an extension to

    compare some impure combinators in many cases. The evolutionary

    algorithm won't be perfect, but it'll cover a lot more cases than it

    does now, hopefully enough that the fitness landscape will be

    adequate.

     > R.

     -Wm

## Robbert van Dalen — 2012-03-24 07:11:49

    > Given 'q' and 'k', both defined in iepos' webpage, we can define:

    >

    > "0" = [] [q] [k]

    > and

    > "1" = k.

    >

    > So, for example, "01" evaluates as follows:

    >

    > "01" =

    > [] [q] [k] "1" =

    > [] [q] [k] k =

    > [] k.

    >

     but the result

    [] k

    cannot be expressed with the defined combinators 0 and 1, except implicitly with "01"

    isn't that a problem?

    aren't there actually five combinators?

    q

    k

    [q]

    [k]

    []

     > I can execute

    > 'q' using the bit sequence "0011":

    >

    > "0011" =

    > "0" "01" "1" =

    > "0" drop "1" =

    > [] [q] [k] drop "1" =

    > [] [q] "1" =

    > [] [q] k = q.

    >

     but "0011" isn't q, only after reduction.

     >> does such flat base mean that you can cut an valid expression anywhere to produce two valid expressions?

     what about these - more strong - requirements?:

    1) you can cut any flat expression anywhere - into two valid flat (sub)expressions.

    2) each flat (sub)expression can be reduced one step (or many steps, to reach fixpoint).

    3) any flat (reduced) expressions can be concatenated into a new flat expression.

    4) this new flat expression can be further reduced (until fixpoint).

    5) the reduction order of flat expressions doesn't matter - any reduction order will always yield the same (fixpoint) expression (confluence)

    note: reduction = execution,

    i prefer to discuss concatenative programming languages in terms of abstract (expression) rewriting.

     >

    >> is the high level language independent of the choosen set of combinators?

    >>

    > That's tough to answer; I haven't produced it yet. In theory I suppose

    > you could write base-independent code in it, but that's not why I'm

    > considering writing it -- it's more intended to help me talk about the

    > low-level concepts. I'm also interested in what a high level flat

    > language might look like; nobody knows.

     a high-level flat language would probably have more than two combinators.

     > Even more esoteric, though, is the question of what else can happen to

    > a flat language. I vaguely suspect that a flat language might be able

    > to address control flow. Such a language would not be concatenative in

    > the same sense, although it would hold the same aspect in other ways.

    > I don't know what it would be.

     may be flatness can be preserved if there can't be a construct such as *if-then-else*

    may be a flat language should reduce postfix expressions (containing a choice), to both choices.

    cheers,

    R.

## Ruurd — 2012-03-24 09:12:16

    Hi,

    I can't find q on iepos' webpage, but I do find cake.

    Is q the same as cake ?

    Can zeroone be used to write a brainfuck interpreter in 112 bytes

    or less ? That would be interesting.

    R.

     --- In concatenative@yahoogroups.com, "William Tanksley, Jr" <wtanksleyjr@...> wrote:

    > Given 'q' and 'k', both defined in iepos' webpage, we can define:

    >

    > "0" = [] [q] [k]

    > and

    > "1" = k.

## William Tanksley, Jr — 2012-03-24 16:35:22

    Robbert van Dalen <robbert.van.dalen@...> wrote:

     >> So, for example, "01" evaluates as follows:

    >> "01" =

    >> [] [q] [k] "1" =

    >> [] [q] [k] k =

    >> [] k.

    > but the result

    > [] k

    > cannot be expressed with the defined combinators 0 and 1, except implicitly with "01"

    > isn't that a problem?

     Looking elsewhere in your email, I see the problem. This is a good

    time to ask that implied question: "is there any difference between

    []k and drop, or between 0011 and q"?

    No, it's not a problem, and there's no detectable difference. "01"

    performs the action "drop" requires. There are other ways to implement

    "drop" as well, all of them taking more bits, more time, and more

    stack space. They're perfectly valid implementations of drop, but this

    is the one I told you about. (There are good complexity theory reasons

    to prefer "01" to any of the others.)

     > aren't there actually five combinators?

    > q

    > k

    > [q]

    > [k]

    > []

     There are a countably infinite number of combinators, and zeroone can

    express all of them. I'm not showing you [q] and [k] because they're

    fairly ugly. [], on the other hand, is quick to produce from memory.

    [] = "00101".

    One effective way to prove that a base is complete is to use it to

    produce all of the combinators in a known complete set. I'll do

    that... But not now.

     > but "0011" isn't q, only after reduction.

     See above :-).

     >>> does such flat base mean that you can cut an valid expression anywhere to produce two valid expressions?

    > what about these - more strong - requirements?:

    > 2) each flat (sub)expression can be reduced one step (or many steps, to reach fixpoint).

     You later define "reduce" as "execute". I have to point out that some

    expressions in any Turing-complete language never reach a fixed point

    by execution.

    Furthermore, you later assume that the reduced expression is itself

    flat; that's not correct in my notation. It's actually possible to

    build a formal logic where that does hold, but such a logic will be

    both VERY complex and either incomplete or possible to express

    contradictions in (per Godel). Using zeroone formally requires

    understanding how zeroone works internally first, which is what we're

    doing now. It's possible to perform all program transformations by

    replacing substrings with different strings (that's called "formal

    logic"), but before we can talk about how that works we have to

    understand how to discover the meaning of a substring so that we can

    prove that the two substrings have the same meaning.

    I consider flat formal logic a "later" step, not for now. For now, we

    use the semantics of the language to assist in proofs, rather than

    doing things formally. Although we ARE using formal logic on the

    semantics, it isn't a flat formal logic.

     > 5) the reduction order of flat expressions doesn't matter - any reduction order will always yield the same (fixpoint) expression (confluence)

     Whatever "reduce" means, it doesn't mean this. Sorry, but this would

    imply that any two expressions of the same function will always reduce

    to the same fixed form, thus allowing you to test in a finite amount

    of time whether two functions are equivalent. That's impossible.

     > note: reduction = execution,

    > i prefer to discuss concatenative programming languages in terms of abstract (expression) rewriting.

     That's the only way I've really worked it out at this point, so I agree.

     > a high-level flat language would probably have more than two combinators.

     More importantly, it'll have syntax to allow user-defined names -- so

    you can define any combinator you want using zeroone, and from then on

    refer to it by name.

     >> Even more esoteric, though, is the question of what else can happen to

    >> a flat language. I vaguely suspect that a flat language might be able

    >> to address control flow. Such a language would not be concatenative in

    >> the same sense, although it would hold the same aspect in other ways.

    >> I don't know what it would be.

    > may be flatness can be preserved if there can't be a construct such as *if-then-else*

    > may be a flat language should reduce postfix expressions (containing a choice), to both choices.

     Implementing true/false/if/else actually isn't hard; it usually starts

    by defining "false" as "drop", and "true" as "execute". The function (

    func flag ) "if" would then simply be "execute" -- that is, it

    executes the true/false flag, and if that's a 'true' it executes the

    function; if it's a 'false' it drops the function.

     > R.

     -Wm

## Robbert van Dalen — 2012-03-24 19:57:16

    On Mar 24, 2012, at 5:35 PM, William Tanksley, Jr wrote:

     > > 2) each flat (sub)expression can be reduced one step (or many steps, to reach fixpoint).

    >

    > You later define "reduce" as "execute". I have to point out that some

    > expressions in any Turing-complete language never reach a fixed point

    > by execution.

     of course, never to reach fixed point is an 'infinite loop'.

    to reach fixed point is called the normal form of an expression.

    see: http://en.wikipedia.org/wiki/Term_rewriting_system

     > Furthermore, you later assume that the reduced expression is itself

    > flat; that's not correct in my notation. It's actually possible to

    > build a formal logic where that does hold, but such a logic will be

    > both VERY complex and either incomplete or possible to express

    > contradictions in (per Godel).

     i always understood that a flat language must have this property:

    that *any* expression (albeit reduced) must be flat.

     > > 5) the reduction order of flat expressions doesn't matter - any reduction order will always yield the same (fixpoint) expression (confluence)

    >

    > Whatever "reduce" means, it doesn't mean this. Sorry, but this would

    > imply that any two expressions of the same function will always reduce

    > to the same fixed form, thus allowing you to test in a finite amount

    > of time whether two functions are equivalent. That's impossible.

    >

     the chosen reduction order (or strategy) doesn't imply at all that you can test two different expressions for equivalence.

    confluence means that you always end up with the same normal form, irrespective of reduction order.

    (when there are multiple ways rewrite an expression).

    confluence is a very nice property to have for a chosen reduction strategy.

    consider for example the difference between lazy evaluation and eager evaluation.

    with lazy evaluation, taking the first element of an (lazy) infinite list will yield a value.

    not so with eager evaluation.

     > > a high-level flat language would probably have more than two combinators.

    >

    > More importantly, it'll have syntax to allow user-defined names -- so

    > you can define any combinator you want using zeroone, and from then on

    > refer to it by name.

     sure, names are good.

     > Implementing true/false/if/else actually isn't hard; it usually starts

    > by defining "false" as "drop", and "true" as "execute". The function (

    > func flag ) "if" would then simply be "execute" -- that is, it

    > executes the true/false flag, and if that's a 'true' it executes the

    > function; if it's a 'false' it drops the function.

     actually, what you describe is very much the 'enchilada' way of doing conditionals.

    for example, the following expression:

    10 ? [is_ten] * .

    tests for 10 and reduces to is_ten if so

    10 10 ? [is_ten] * .

    1 [ten] * .

    [ten] .

    ten

    5 10 ? [is_ten] * .

    0 [ten] * .

    0 .

    (empty).

     > -Wm

     cheers,

    R.

## William Tanksley, Jr — 2012-03-24 20:51:05

    Ruurd <r.wiersma26@...> wrote:

     > Hi,

    > I can't find q on iepos' webpage, but I do find cake.

    > Is q the same as cake ?

     I'm sorry -- I didn't realize that. Using the same notation as iepos' page:

    [B] [A] q == [[B]] [A B]

    So, q serves three purposes: it makes A and B into siblings in a list;

    it swaps the order of A and B; and it adds a layer of quotation to B.

    You noticed cake; it turns out that cake can serve in place of q,

    since it does all of the above things (although in a more complex

    way).

     > Can zeroone be used to write a brainfuck interpreter in 112 bytes

    > or less ? That would be interesting.

     No, because zeroone's underlying machine has no i/o capability of any

    kind. The obvious question pops to mind: is it possible to make a

    zeroone with i/o? It's taken me a while, but I finally realized what I

    needed -- the ability to pack an arbitrary number of primitives into

    the "zero" pseudocombinator.

    The zero combinator I used before was zero == [] [q] [k]. All three

    components are important -- the empty list gives us a starting point

    for building lists at runtime, the 'k' combinator allows us to take

    lists apart, and 'q' is the universal constructor. The combinators can

    be replaced by others that do similar jobs, though. I mentioned that

    "q" can be replaced by the "cake" combinator you found, and indeed

    anything that can do the same basic tasks that 'q' does can fill its

    place.

    So what I'm going to do is pack all those extra combinators into a

    binary tree in place of the [q] combinator, and make it quick and easy

    to climb that tree by making both 'k' and its stack-flipped version,

    'z', easily available. Remember, the entire tree can be placed on the

    stack by itself with the code "0011" (which doesn't actually depend on

    what is inside the middle element of the 'zero' combinator);

    therefore, I'll simply use the name "tree" for that.

    So; let's make a tree that contains z, input, output, and q: [

    [[input] [q]], [[output] [z]] ].

    So to construct 'z' here, we write "tree 11"; read this as "get the

    tree, execute the right branch, then the right branch again." (I

    assume none of the spaces matter.) You'll recall that 'k' is simply

    "1", so we now have both 'k' and 'z'; and for our special purposes

    here, I'll use "left" and "right" as a synonym for "z" and "k",

    respectively.

    From this, we get q == "tree left right"; input == "tree left left",

    and "output" == "tree right left".

    Obviously, at this point we've proven that we can access anything in

    ANY binary tree; we can use any number of primitives we want. (I know,

    I haven't explained what "input" and "output" do. They do whatever we

    want them to do, and now we can define and provide primitives that

    manipulate what they produce.)

    Another thing I haven't done is to figure out how to get a shorter

    expression for "z". Right now it's much bigger than "k", and strong

    asymmetry is usually a hint of non-optimality.

     > R.

     -Wm

## William Tanksley, Jr — 2012-03-24 21:14:36

    Robbert van Dalen <robbert.van.dalen@...> wrote:

     > William Tanksley, Jr wrote:

    >> > 2) each flat (sub)expression can be reduced one step (or many steps, to reach fixpoint).

    >> You later define "reduce" as "execute". I have to point out that some

    >> expressions in any Turing-complete language never reach a fixed point

    >> by execution.

    > of course, never to reach fixed point is an 'infinite loop'.

     Informally, yes. Formally, nontermination. There are many ways of

    doing that which aren't as simple to discover as infinite loops.

     > to reach fixed point is called the normal form of an expression.

    > see: http://en.wikipedia.org/wiki/Term_rewriting_system

     Okay, that's fine, then. I thought you were saying that every

    expression has a normal form, and every expression will reduce to its

    normal form no matter what path you take. The latter is definitely not

    true.

     >> Furthermore, you later assume that the reduced expression is itself

    >> flat; that's not correct in my notation. It's actually possible to

    >> build a formal logic where that does hold, but such a logic will be

    >> both VERY complex and either incomplete or possible to express

    >> contradictions in (per Godel).

    > i always understood that a flat language must have this property:

    > that *any* expression (albeit reduced) must be flat.

     That depends on what you mean by "reduce". As long as you stick to

    term rewriting, it's true. But I don't have a term rewriting system

    yet for zeroone; my past attempts indicated that such a system would

    be very complex, and would depend very much on the specific base I

    chose (and I still haven't picked out a single base).

     >> > 5) the reduction order of flat expressions doesn't matter - any reduction order will always yield the same (fixpoint) expression (confluence)

    >> Whatever "reduce" means, it doesn't mean this. Sorry, but this would

    >> imply that any two expressions of the same function will always reduce

    >> to the same fixed form, thus allowing you to test in a finite amount

    >> of time whether two functions are equivalent. That's impossible.

    > the chosen reduction order (or strategy) doesn't imply at all that you can test two different expressions for equivalence.

    > confluence means that you always end up with the same normal form, irrespective of reduction order.

    > (when there are multiple ways rewrite an expression).

     Unless I'm badly wrong, it should mean that you'll always end that way

    *in theory*. In practice, the average solvable problem is much harder.

     > actually, what you describe is very much the 'enchilada' way of doing conditionals.

    > for example, the following expression:

     You're right! I should have remembered that.

     > R.

     -Wm

## Ruurd — 2012-03-25 09:59:36

    Hi,

    You don't have to add i/o primitives to your language. All computers

    are permutations of a Turing machine and a Turing machine does not

    have i/o.

    First you put the brainfuck interpreter on tape, followed by the

    brainfuck program, followed by the input that the brainfuck program

    takes, if any.

    You feed this tape to the program that interpretes the zeroone universal evaluator and after executing, whatever is left on the tape

    is the output.

    The interpreter can read the tape and output what is there.

    You can find the competitor here: http://homepages.cwi.nl/~tromp/cl/cl.html

    The commandline to produce 'Hello, world!' is either:

    cat bf.Blc hw.bf | ./blc m8 uni8.lam

    or:

    cat bf.Blc hw.bf | perl blc.pl -8

    That last one is very slow and is less beautifull, because it has

    the interpreter encoded in perl instead of in the lambda calculus.

    The author switched from combinatory calculus to the lamda calculus,

    because the last one is more descriptive. The comparison was made,

    based on the size of the self-interpreter. I think that a comparison

    based on a brainfuck interpreter is more realistic. Also, the

    combinatory calculus was restricted to just S and K and I wonder

    what difference it will make if more combinators are added.

    Also, I wonder if the comparison is still in favor of the lambda

    calculus when concatenative combinators are used instead.

    It is not my personal quest to find an answer, that's why I am

    asking.

    R.

    <wtanksleyjr@...> wrote:

     >

    > Ruurd <r.wiersma26@...> wrote:

    > > Can zeroone be used to write a brainfuck interpreter in 112 bytes

    > > or less ? That would be interesting.

    >

    > No, because zeroone's underlying machine has no i/o capability of any

    > kind. The obvious question pops to mind: is it possible to make a

    > zeroone with i/o?

## William Tanksley, Jr — 2012-03-25 17:03:10

    Ruurd <r.wiersma26@...> wrote:

     > Hi,

    > You don't have to add i/o primitives to your language. All computers

    > are permutations of a Turing machine and a Turing machine does not

    > have i/o.

     Computers with i/o are categorically different from ones without it,

    capable of computing tasks in completely different time orders. Turing

    machines help to define the Chomsky hierarchy (they're at the top),

    but there are many types of Turing machines, not all of which are

    equivalent (and i/o is the big difference).

     > You feed this tape to the program that interpretes the zeroone universal evaluator and after executing, whatever is left on the tape

    > is the output.

     Most significantly, zeroone, unlike a Turing machine, has no access to

    its own code. This means that there is NO tape, no data left on the

    tape, no writing to the tape. There is a stack, but the stack isn't a

    simple list of symbols; rather, it's a stack of functions, and by

    definition there's no way to interpret a function consistently. So

    adding i/o is a major upgrade.

     > You can find the competitor here: http://homepages.cwi.nl/~tromp/cl/cl.html

     I'd clean forgotten that... Excellent, more citation materiel. Yes,

    his goal is similar to mine.

     > The author switched from combinatory calculus to the lambda calculus,

    > because the last one is more descriptive. The comparison was made,

    > based on the size of the self-interpreter.

     I recall that, yes.

     > I think that a comparison

    > based on a brainfuck interpreter is more realistic.

     If by that you mean that comparing the size of the *same* program is

    more useful than comparing the size of different programs -- I agree.

    But I wouldn't expect the results to change -- although that's just my

    gut feeling. The reason I expect that is that although a lambda

    combinator requires more program-bits to express, it's always the

    exact combinator that's needed, never an approximation that needs to

    be corrected.

    Meanwhile, a zeroone program carries no information in the arrangement

    of program-bits that isn't already encoded in the interpreter.

    Practically, this means that zeroone programs will always (well,

    normally) be bigger than the same program written in either other

    language.

     > Also, the

    > combinatory calculus was restricted to just S and K and I wonder

    > what difference it will make if more combinators are added.

     More combinators certainly means the program will be shorter; the

    worry is that one can define a combinator which makes the program VERY

    short. I'm reminded of a UCSD processor design task where one of the

    final goals was to run a median computation; I built a stack processor

    and included hardware to implement a "perfect bitonic shuffle" on the

    stack, which I'd made deep enough to handle all of the data on which

    the median was being computed. Since the assignment was graded on how

    many cycles our processor required to perform the tasks, my team broke

    the grade curve. That was fun. Especially since the TA didn't believe

    it would work at all.

    But adding more combinators has long been a goal of mine. Particularly

    because handling i/o will allow me to make a sensible comparison along

    the same line as the above, but also because it seems perfectly

    obvious that granting access to a neater selection of combinators

    would allow for shorter, clearer programs. Interestingly, adding more

    combinators should also force the interpreter's source code to be

    larger, especially if it's expressed in a different language.

    For this reason, I'd want to compare sizes of the language's

    interpreter written in a standard language (compared to the other

    interpreters written in the same standard language), then the sizes of

    a standard program (your suggestion of a brainfuck interpreter is

    perfectly valid) written in the language itself.

    Sadly, adding more combinators has revealed some kind of bug in the

    most important of my "tworing" utilities -- so I've got some work to

    do.

     > Also, I wonder if the comparison is still in favor of the lambda

    > calculus when concatenative combinators are used instead.

     Since zeroone not only loses the ability to define its own

    combinators, but also loses the ability to have the beginning of the

    program define the parse environment in which the latter part is read

    -- I expect short to medium length programs to be MUCH longer in

    zeroone. (Once the program size gets large, the data structures on the

    stack should begin to help, and the sizes should come out roughly

    similar.)

     > It is not my personal quest to find an answer, that's why I am

    > asking.

     I assume you meant "now" rather than "not". My personal most annoying typo :-).

     > R.

     -Wm