[stack] Jon Purdy: Why Concatenative Programming Matters

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

William Tanksley, Jr

2012-02-13 17:08:18 UTC

Post by John Nowak
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

John Nowak

2012-02-13 19:05:03 UTC

Post by William Tanksley, Jr
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 UTC

Post by John Nowak
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.

Post by John Nowak
This is very different from concatenative languages where
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.

Post by John Nowak
(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.

Post by John Nowak
- jn

-Wm

John Nowak

2012-02-13 21:23:17 UTC

Post by William Tanksley, Jr
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'.

Post by William Tanksley, Jr
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 UTC

Post by John Nowak
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 UTC

> 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.
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-13 17:27:06 UTC

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.

Post by John Nowak
http://evincarofautumn.blogspot.com/2012/02/why-concatenative-programming-matters.html

eas lab

2012-02-14 05:01:36 UTC

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 UTC

] 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 UTC

Post by eas lab
This commentor appropriately acknowledges the important cognitive-load aspect:-

Indeed.

Post by eas lab
]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.

Post by eas lab
*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.

Post by eas lab
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 UTC

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 UTC

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 UTC

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 UTC

...

*explodes*

William Tanksley, Jr

2012-03-19 17:38:18 UTC

Post by John Nowak
*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 UTC

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.

Post by John Nowak
*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

<*> To visit your group on the web, go to:
http://groups.yahoo.com/group/concatenative/

<*> Your email settings:
Individual Email | Traditional

<*> To change settings online go to:
http://groups.yahoo.com/group/concatenative/join
(Yahoo! ID required)

<*> To change settings via email:
concatenative-***@yahoogroups.com
concatenative-***@yahoogroups.com

<*> To unsubscribe from this group, send an email to:
concatenative-***@yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/

Robbert van Dalen

2012-03-19 19:36:13 UTC

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

it was a dutch/german experience.

Post by Robbert van Dalen
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.

Post by John Nowak
*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 UTC

yes please.

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

Post by John Nowak
*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 UTC

This post might be inappropriate. Click to display it.

Robbert van Dalen

2012-03-20 07:26:08 UTC

Post by William Tanksley, Jr
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/

Post by William Tanksley, Jr
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?

Post by William Tanksley, Jr
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.

-Wm

William Tanksley, Jr

2012-03-20 15:35:36 UTC

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.

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.)

Post by Robbert van Dalen
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.

Post by Robbert van Dalen
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.)

Post by William Tanksley, Jr
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.

Post by Robbert van Dalen
R.

-Wm

Robbert van Dalen

2012-03-22 17:43:37 UTC

Post by William Tanksley, Jr
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?

Post by Robbert van Dalen
i believe the real challenge is to find two combinators that have the most 'impact'.

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.

Post by William Tanksley, Jr
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.

Post by William Tanksley, Jr
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?

Post by William Tanksley, Jr
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

Post by William Tanksley, Jr
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?

Post by William Tanksley, Jr
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).

Post by William Tanksley, Jr
(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 UTC

This post might be inappropriate. Click to display it.

Ruurd

2012-03-24 09:12:16 UTC

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.

Post by William Tanksley, Jr
"0" = [] [q] [k]
and
"1" = k.

William Tanksley, Jr

2012-03-24 20:51:05 UTC

Post by Ruurd
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).

Post by Ruurd
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.

Post by Ruurd
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.

Post by Ruurd
R.

-Wm

Ruurd

2012-03-25 09:59:36 UTC

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.

Post by Ruurd
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 UTC

Post by Ruurd
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).

Post by Ruurd
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.

Post by Ruurd
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.

Post by Ruurd
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.

Post by Ruurd
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.

Post by Ruurd
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.

Post by Ruurd
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.)

Post by Ruurd
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 :-).

Post by Ruurd
R.

-Wm

Robbert van Dalen

2012-03-24 07:11:49 UTC

Post by William Tanksley, Jr
"0" = [] [q] [k]
and
"1" = k.
"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]
[]

Post by William Tanksley, Jr
I can execute
"0011" =
"0" "01" "1" =
"0" drop "1" =
[] [q] [k] drop "1" =
[] [q] "1" =
[] [q] k = q.

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

Post by Robbert van Dalen
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.

Post by Robbert van Dalen
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.

Post by William Tanksley, Jr
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.

William Tanksley, Jr

2012-03-24 16:35:22 UTC

Post by William Tanksley, Jr
"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.)

Post by Robbert van Dalen
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.

Post by Robbert van Dalen
but "0011" isn't q, only after reduction.

See above :-).

Post by Robbert van Dalen
does such flat base mean that you can cut an valid expression anywhere to produce two valid expressions?

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.

Post by Robbert van Dalen
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.

Post by Robbert van Dalen
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.

Post by Robbert van Dalen
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.

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.

Post by Robbert van Dalen
R.

-Wm

Robbert van Dalen

2012-03-24 19:57:16 UTC

Post by Robbert van Dalen
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

Post by William Tanksley, Jr
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.

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

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.

Post by Robbert van Dalen
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.

Post by William Tanksley, Jr
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).

Post by William Tanksley, Jr
-Wm

cheers,

R.

William Tanksley, Jr

2012-03-24 21:14:36 UTC

Post by Robbert van Dalen
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.

Post by Robbert van Dalen
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.

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).