map fusion
John Nowak — 2008-08-01 08:52:43
In a functional language, the following optimization is valid
(assuming F and G are pure functions that terminate):
map G (map F xs) -> map (G . F) xs
This is not only an optimization: It is a law that can be used for
understanding and proving program properties.
For a concatenative language, we might assume the following rule
(using Joy's syntax):
[F] map [G] map -> [F G] map
Unfortunately, this is not valid because 'F' and 'G' can access more
than one value on the stack. Here is a counterexample to the above rule:
9 [1 2 3] [drop dup] map [[1 -] dip] map -- yields 6 [9 9 9]
9 [1 2 3] [drop dup [1 -] dip] map -- yields 6 [9 8 7]
This seems to be yet another argument against n-ary combinators where
the quotation is not called a fixed number of times. (Combinators that
call their quotation a fixed number of times like 'dip', 'twice', or
'@bi' are fine.) The fact that 'map' in a concatenative language is
still "purely functional" doesn't change the fact that the
unrestricted stack access complicates things the same way mutable
local variables do.
It seems the solution is to offer two versions of certain combinators.
The restricted versions ('map, 'each', etc) will be easier to reason
about and optimize, while the unrestricted versions ('map*', 'each*',
etc) will remain useful in a way only possible in stack-based
languages. I think this would be worthwhile to adopt in both typed and
untyped languages.
- John
William Tanksley, Jr — 2008-08-01 14:01:46
John Nowak <
john@...> wrote:
> Unfortunately, this is not valid because 'F' and 'G' can access more
> than one value on the stack. Here is a counterexample to the above rule:
Okay, I think I get this. (I certainly agree.)
> This seems to be yet another argument against n-ary combinators where
> the quotation is not called a fixed number of times.
_This_ I don't understand. What does that mean?
I would have said "this is an argument against combinators which
repeatedly call function inputs that do not have a statically known
stack effect." Am I being too restrictive? Are you being too
restrictive?
> It seems the solution is to offer two versions of certain combinators.
> The restricted versions ('map, 'each', etc) will be easier to reason
> about and optimize, while the unrestricted versions ('map*', 'each*',
> etc) will remain useful in a way only possible in stack-based
> languages. I think this would be worthwhile to adopt in both typed and
> untyped languages.
I definitely like this; although of course in Factor the asterisk
prefix is already taken.
> - John
-Wm
Christopher Diggins — 2008-08-01 16:29:00
On Fri, Aug 1, 2008 at 4:52 AM, John Nowak <
john@...> wrote:
> In a functional language, the following optimization is valid
> (assuming F and G are pure functions that terminate):
>
> map G (map F xs) -> map (G . F) xs
>
> This is not only an optimization: It is a law that can be used for
> understanding and proving program properties.
>
> For a concatenative language, we might assume the following rule
> (using Joy's syntax):
>
> [F] map [G] map -> [F G] map
>
> Unfortunately, this is not valid because 'F' and 'G' can access more
> than one value on the stack. Here is a counterexample to the above rule:
>
> 9 [1 2 3] [drop dup] map [[1 -] dip] map -- yields 6 [9 9 9]
> 9 [1 2 3] [drop dup [1 -] dip] map -- yields 6 [9 8 7]
>
> This seems to be yet another argument against n-ary combinators where
> the quotation is not called a fixed number of times. (Combinators that
> call their quotation a fixed number of times like 'dip', 'twice', or
> '@bi' are fine.) The fact that 'map' in a concatenative language is
> still "purely functional" doesn't change the fact that the
> unrestricted stack access complicates things the same way mutable
> local variables do.
>
> It seems the solution is to offer two versions of certain combinators.
> The restricted versions ('map, 'each', etc) will be easier to reason
> about and optimize, while the unrestricted versions ('map*', 'each*',
> etc) will remain useful in a way only possible in stack-based
> languages. I think this would be worthwhile to adopt in both typed and
> untyped languages.
I think I understand. To summarize with Cat type notation:
map : (list ('a -> 'a) -> list)
map* : (list ('A 'b -> 'A 'b) -> list)
In other words, "map" accepts only 1->1 functions, while map* accepts
n->n functions where n >= 1.
FWIW I think this is a very good idea, and I like the notation.
In Cat I simply disallowed "map" and similar combinators from
modifying the stack. It made type analysis easier, it preserved the
fusion properties, and it didn't really cause any huge loss of
expressiveness AFAICT. However: there was definitely some scenarios,
where Joy would be more succinct.
- Christopher
- Christopher
Daniel Ehrenberg — 2008-08-01 16:33:35
On Fri, Aug 1, 2008 at 7:01 AM, William Tanksley, Jr
<
wtanksleyjr@...> wrote:
>> This seems to be yet another argument against n-ary combinators where
>> the quotation is not called a fixed number of times.
>
> _This_ I don't understand. What does that mean?
>
> I would have said "this is an argument against combinators which
> repeatedly call function inputs that do not have a statically known
> stack effect." Am I being too restrictive? Are you being too
> restrictive?
I agree with William. In a high level language, it'd generally be
better if the compiler can figure out its optimizations itself without
needing changes in the language design. Here, it should be easy to
check whether the quotation given affects values lower down on the
stack. In its fusion optimization, the compiler can just use this
information, rather than change the kind of program that the user
writes.
(Maybe map* would be good for documentation purposes or something, but
this is not a good justification for it.)
Dan
Christopher Diggins — 2008-08-01 16:44:08
On Fri, Aug 1, 2008 at 12:33 PM, Daniel Ehrenberg <
microdan@...> wrote:
> On Fri, Aug 1, 2008 at 7:01 AM, William Tanksley, Jr
> <wtanksleyjr@...> wrote:
>>> This seems to be yet another argument against n-ary combinators where
>>> the quotation is not called a fixed number of times.
>>
>> _This_ I don't understand. What does that mean?
>>
>> I would have said "this is an argument against combinators which
>> repeatedly call function inputs that do not have a statically known
>> stack effect."
However, they *do* have a statically known stack effect.
> Am I being too restrictive? Are you being too
>> restrictive?
>
> I agree with William. In a high level language, it'd generally be
> better if the compiler can figure out its optimizations itself without
> needing changes in the language design.
> Here, it should be easy to
> check whether the quotation given affects values lower down on the
> stack.
Yes it is (in most scenarios).
> In its fusion optimization, the compiler can just use this
> information, rather than change the kind of program that the user
> writes.
That is a valid point. However, one of the benefits of being able to
manipulate the concatenative program syntactically while preserving
meaning is now lost.
> (Maybe map* would be good for documentation purposes or something, but
> this is not a good justification for it.)
There is a precedence for such a naming system in Scheme. Effectively
"map*" is a version with side-effects. We could perhaps call it
"map!". For Cat which was intended for use as an intermediate language
at least, the goal of being able to apply simply term rewriting to the
syntax of a program (e.g. identify "[f] map [g] map" and rewrite it
without analysis) was really quite appealing.
- Christopher
John Nowak — 2008-08-01 21:06:17
On Aug 1, 2008, at 10:01 AM, William Tanksley, Jr wrote:
>> This seems to be yet another argument against n-ary combinators where
>> the quotation is not called a fixed number of times.
>
> _This_ I don't understand. What does that mean?
I mean that in languages like Factor, allowing the quotation given to
'map' to use any amount of the stack can make things difficult -- even
if that quotation is appropriately balanced (e.g. 2 -> 2, 3 -> 3,
etc). Ideally, it would be nice to have '[F] map [G] map -> [F G] map'
be applicable in the general case, but it isn't unless you restrict
'F' and 'G' to only using one element. Of course, given that Factor
allows unrestricted side effects, there are other issues to deal with
anyway.
At least from an optimization standpoint, this is not an issue in a
language like 5th because "quotations" are supplied directly, stack
effects are always statically determinable, and side effects are
tracked on the type level. Still, it may be useful to offer both 'map'
and 'map*' so that certain optimizations (like map fusion) can be
guaranteed to the programmer more simply.
- John
John Nowak — 2008-08-01 21:21:31
On Aug 1, 2008, at 12:29 PM, Christopher Diggins wrote:
> I think I understand. To summarize with Cat type notation:
>
> map : (list ('a -> 'a) -> list)
> map* : (list ('A 'b -> 'A 'b) -> list)
I don't understand when you're allowed to omit row variables in Cat's
notation. I also think you mean "'a -> 'b" rather than "'a -> 'a".
In any case, here are the (simplified) type signatures as they'd
appear in 5th:
map[a -> b] : R (a) -> R (b).
map*[R a -> R b] : R (a) -> R (b).
> In other words, "map" accepts only 1->1 functions, while map*
> accepts n->n functions where n >= 1.
Correct.
> In Cat I simply disallowed "map" and similar combinators from
> modifying the stack. It made type analysis easier,
Why would it make type analysis easier?
> it preserved the fusion properties, and it didn't really cause any
> huge loss of
> expressiveness AFAICT.
This is arguably a reasonable solution in Cat because you have
'papply' (aka 'curry' in Factor). In 5th however, you don't, so you'd
have to use variables to write things like 'map-with':
x map-with[F] -> map[x F].
The only way to write 'map-with' without variables is to use a version
of 'map' that can call a function that uses more than one element:
map-with[F] -> map*[over dip[swap F]] nip.
Of the two, I prefer the first version for (obvious) reasons, so
perhaps this is a bad example.
Still, there are cases where 'map*', 'each*', etc, are quite handy,
even in a language like Cat. Slava has given me a few examples of
where they're used in Factor (although obviously not with those names).
- John
John Nowak — 2008-08-01 21:37:10
On Aug 1, 2008, at 12:44 PM, Christopher Diggins wrote:
> On Fri, Aug 1, 2008 at 12:33 PM, Daniel Ehrenberg
> <microdan@...> wrote:
>
>> In its fusion optimization, the compiler can just use this
>> information, rather than change the kind of program that the user
>> writes.
>
> That is a valid point. However, one of the benefits of being able to
> manipulate the concatenative program syntactically while preserving
> meaning is now lost.
This is essentially the point I was trying to make. How strong of a
point it is I am not sure.
> There is a precedence for such a naming system in Scheme. Effectively
> "map*" is a version with side-effects. We could perhaps call it
> "map!".
I think you need to be careful here. 'map*' acts strangely because it
is really some sort of map/fold combination. (I've not checked my
dictionary to figure out exactly what sort of morphism it is.)
I had a related discussion with Slava last night where he took issue
with the characterization of 'map*' as having side effects. Instead,
he preferred to talk more meaningfully about the additional stack
elements as loop-carried dependencies. You can find the discussion
here (luckily, it began right around midnight):
http://bespin.org/~nef/logs/concatenative/08.08.01
How come you never make it onto IRC chris? You're leaving me all alone
in my type system and rewriting interests...
> For Cat which was intended for use as an intermediate language
> at least, the goal of being able to apply simply term rewriting to the
> syntax of a program (e.g. identify "[f] map [g] map" and rewrite it
> without analysis) was really quite appealing.
How far along have you gotten on this? At least in my opinion, it is
an open question as to if function-level rewrite rules are a
worthwhile addition to other means of optimization. Their biggest
appeal to me isn't in their power (which likely isn't that great
compared to more advanced methods), but rather in their simplicity
which enables guarantees of optimization to be simply conveyed to
users of a language. Of course, such rules are useful for other things
like as proving program equality.
- John
Chris Cogan — 2008-11-10 01:59:51
It's been a long time since I've participated in this forum, but it hasn't
been because of loss of interest. Mostly, I've been preoccupied with other
things. I'm very glad to see that this forum is still active.
I thought I'd report on an evolutionary programming project using Joy as the
language of the evolved programs. Several months ago, I started this project
but only worked on it for an hour or two, and then set it aside until the
day before yesterday.
General Description
The idea is to write a program that writes Joy programs, tests them for
fitness against samples of the task data, where the task is do something
like handwriting recognition. Those that produce the most nearly correct
results are saved and used as parents for the next generation, which will
consist mostly of variations on each of the parent programs. Because each
one will be tested in isolation against the same test data, there will be no
direct competition for resources (as there would be in Tom Ray's Tierra).
1. A program generator takes as input an existing program and returns a
small modification of it, such as adding, deleting, or replacing a single
atom or item in a list, etc. (I'll talk in Joy terms, since I'm not
sufficiently knowledgeable about any of the other languages discussed in
this forum.) Use this generator to generate a slew of offspring from each of
the programs, if any, that made it through fitness testing for the previous
generation.
3. Execute each generated program on the test data and measure fitness based
on the results. Save the programs with the highest fitness rating and
discard all the rest.
4. When completely successful code is produced, stop.
5. Otherwise go back to step, using the most successful programs so far as
parents of the next generation.
Why Use Joy?
I considered using Prolog (before I ever heard of Joy) for this kind of
thing, because prolog programs can effectively modify themselves in useful
ways (by adding and deleting rules, mainly), and because it has an automatic
solution-tree search as the core of the way Prolog programs work.
However, a modified Joy is a lot easier to work with because Joy has no
syntax to speak of (although Prolog's syntax is simple compared to that of,
say, C++), except at the lowest level (lists must have a bracket at each
end, numbers can't have two decimal points, etc.). This makes generation and
modification trivial, because the code doing either doesn't have to worry
about complex control constructs, and it doesn't have to worry about it in
making modifications. Once you have code for properly recognizing aggregate
data types (lists, strings, etc.), your work is largely done.
There is a problem, but it is relatively minor: Exceptions, such as dividing
by zero. Normally, these can crash a program, and code generated
unintelligently can easily lead to such errors.
The solution is a modified Joy that basically handles all errors by ignoring
them. In Visual Basic, this can be done with a "Try" block, which can be
used to cause execution to resume after the block if an error occurs in it.
It can also be done with two versions of an "On Error" statement: "On Error
Resume Next" and "On Error Goto <label>" (where <label> is a label at a
location in the code where you want execution to resume if an error occurs).
Once one has a version of Joy that won't crash on errors (simply by
modifying a bunch of the primitives), one can then generate truly arbitrary
string of code, as long as it is syntactically correct, and they will
"execute" (perhaps doing nothing much at all, but still terminating without
error (infinite loops are still possible in combinators that repeat chunks
of code, but even this can be counteracted by putting a fixed limit of, say,
one million, on the number of iterations).
Sticking closely to the evolutionary paradigm can mean that one must start
with truly simple versions of the task, such as distinguishing between two
values of a variable. If we start with samples of the full task, such as
recognizing full documents of text correctly, we won't be able to provide
any fitness tests that are both meaningful and useful, and it could be
billions of years before anything works. Narrowing the task down to
something completely simple allows for some fitness to be discovered early
on (then we increase the difficulty of the task a little).
So, I'm planning to start my own evolver on a single Boolean variable. When
the evolver finally produces one that can handle this task reliably, I can
switch to having it try to make code that correctly reports the values of
two Booleans. At some point, I should be able to add code for creating
simple images in memory, and start over with one-pixel images, and only one
distinction (white vs. non-white, perhaps).
Eventually, I should be able to use images with enough pixels to represent
symbols such as plus-signs and minus-signs. From there, I should be able to
start using actual image files, which will require scanning samples of my
handwritten material (over two hundred pounds of the stuff, written over the
past twenty-odd years) and cutting it into small, one-character image files.
This will also require that I provide the correct text for each sample. At
first, I will probably just include the text in the names of the files (and
make sure that the generated code has no access to this information, to
avoid evolving code that only reports text from the file names!).
For now, I'll be happy just to get my evolver working well enough to evolve
code to make some simple distinction reliably, even if I have to hand-tweak
mutation-rates and types of mutations allowed. I'm using what will be my
third implementation of Joy (more of a mini-Joy, in this case). (I've got
one implementation in Visual Basic (Visual Studio) and another in Visual
Basic for Applications (the macro language for the Microsoft Office programs
-- Microsoft Word in this case).
My Visual Studio version of Joy "compiles" to lists of what I call "code
objects," and this makes for a very generalized implementation and allows
for easy de-compilation, etc., but it's also slow, so my new version will
not use "objects," and this will eliminate at least one level of
indirection, in that it will use "delegates" (which are basically pointers
to functions, but with type-checking for parameters and return types). It
will also not "compile" code but will only process code into arrays of
strings (even lists with many elements will each just be a single string
until it is "executed" (pushed onto the stack), at which point it will be
made into an array of strings (one string for each element).
This version of Joy will also be the least faithful to Manfred's version.
I'm more interested, this time, in making a language that simply has a
suitable set of primitives for my evolutionary programming purposes. One
difference will be that executing code can define new functions (and
re-define them, thus making them into variables). This violates Joy's
variable-free nature, especially if I allow non-local variables (but I
haven't decided on this yet).
It's interesting that Joy code is more like the genetic code of DNA than
ordinary programming languages are, in that DNA doesn't have much in the way
of syntax, and it doesn't have any explicit looping or other typical control
constructs. DNA is constructed in a concatenative way, as long chains,
without loops or other interconnections. Of course, this parallelism is very
limited, but it suggests why I think Joy is a good programming language for
evolutionary programming: The only structuring is done by defining functions
and making chunks of code into lists. Both of these are forms of
modularization (and defining functions is basically just naming a list
(quoted program) so it can be used by reference rather than being included
bodily (which also requires an extra step to execute its contents as code).
I had hoped to have some evolving going on by now (Sunday evening), but I
took time out to write this post so I may not get to actual evolution for a
day or so, depending on available time. But, I'm close.
I'm working on the Joy source code preprocessor now. Since I've done it
twice before and since I'm using a simplified version of Joy, this shouldn't
take long.
I'll report on results, soon, I hope.
Chris Cogan
chris glur — 2008-11-15 07:32:10
> The idea is to write a program that writes Joy programs,
> tests them for fitness against samples of the task data,
> where the task is do something like handwriting recognition.
--snip--
>3. Execute each generated program on the test data and measure
>fitness based on the results. Save the programs with the highest
>fitness rating and discard all the rest.
Having just read 75% of 'The collapse of chaos' by Cohen &
Ian Stew[au]rt I'm less believing than when I read of some
claimed successes in this scheme previously.
I see now that my previous extention of neural-nets
concepts, where the state space searched is continuous
and 'hill climbing' is aimed at; is completely misplaced.
The author starts by looking at Mandelbrot fractals ..etc.
where even with infinitesimal errors the output is still
unpredictable. Ie. effectively discontinuity.
>Sticking closely to the evolutionary paradigm can mean that
>one must start with truly simple versions of the task, such
>as distinguishing between two values of a variable. If we
>start with samples of the full task, such as recognizing full
>documents of text correctly, we won't be able to provide any
>fitness tests that are both meaningful and useful, and it could
>be billions of years before anything works. Narrowing the task
>down to something completely simple allows for some fitness to
>be discovered early on (then we increase the difficulty of the
>task a little).
OK, this sound plausible.
But then only the micro-modules evolve, and the intelligent
human uses them to build the complete algorithm.
Or you can automate the combinations of the modules, but
the human has designed the initial intelligent module
partitioning first.
>It's interesting that Joy code is more like the genetic code
>of DNA than ordinary programming languages are, in that DNA
>doesn't have much in the way of syntax, and it doesn't have
>any explicit looping or other typical control constructs.
I suspect these claims are mostly intuitive ?
IMO 'looping' can only apply in a digital computer.
Whereas DNA is digital, I think the functions which it
'controls' are analog-like. Ie. "DO x UNTIL enough".
So you could say 'the molecules of water evaporated
until the cup was dry", but it that really 'looping'.
I suspect that the 'divide by zero' is only one of [possibly
infinite] many discontinuities in the scheme, as I understand
your description of it.
You can simulate an analog-system in your output, but
your input is discontinuous/chaotic ?
OTOH you could simulate all the analog-processes, with
your digital computer ?
Can you give any mathematical insight into why:
run M*N should be closer to a goal than run N ?
It seems like one of these schemes which sound
plausible on a first superficial consideration, but
fails on deeper analysis.
An fascinating can-O-worms ?
It would be nice to be able to consult biologist-Cohen
& mathematician-Stewart on this ?
== Chris Glur.
janvanlent — 2008-11-16 19:06:15
Stevan Apter — 2008-11-16 19:25:06
or search back in the concatenative archives and read billy
tanksley's remarks about his languages 01 and 10 and their
suitability for darwinian evolutionary experiments.
i did an implementation in k (www.nsl.com/k/10.k) and stopped
at the point where i needed to adapt dennis shasha's tree-
distance algorithm. it still seems to me that 10 is a perfect
candidate for this kind of work.
----- Original Message -----
From: "janvanlent" <jan.vanlent+concatenative@...>
To: <concatenative@yahoogroups.com>
Sent: Sunday, November 16, 2008 2:06 PM
Subject: [stack] Re: Evolutionary Programming
> --- In concatenative@yahoogroups.com, "Chris Cogan" <ccogan@...> wrote:
>> I thought I'd report on an evolutionary programming project using
> Joy as the
>> language of the evolved programs.
>
> You might be interested in the work by Lee Spector on the Push, PushGP
> and Pushpop systems [1].
>
> jan
>
> [1] http://hampshire.edu/lspector/push.html
>
>
>
William Tanksley, Jr — 2008-11-16 20:46:14
Stevan Apter <
sa@...> wrote:
> or search back in the concatenative archives and read billy
> tanksley's remarks about his languages 01 and 10 and their
> suitability for darwinian evolutionary experiments.
The nice thing about 01 (or 10, it's just a logical NOT away) is that
you can cut and splice anything anywhere and it's still a valid
program. The bad thing is that I still haven't decided how to express
input/output... It's merely a matter of convention, but it's a pretty
important convention.
I've not touched "tworing", my 10 lab program, in a while; one of its
unit tests fail, and I'm not sure why. I want to use it to design a
more effective base ... I've got some theories about what might make a
base better than another one, I just need to do some testing.
BTW, while you're thinking about evolutionary algorithms, check this
page out:
http://williamtozier.com/slurry/2008/04/02/search-algorithms.
-Wm
Stevan Apter — 2008-11-16 22:00:35
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
>
> I've not touched "tworing", my 10 lab program, in a while; one of its
> unit tests fail, and I'm not sure why.
perhaps you can post your 10 unit tests. i'd like to try running them in
my implementation.
John Meacham — 2008-11-17 04:21:34
Hi, you would probably be really interested in the work of Jurgen
Schmidhuber, in particular the 'OOPS' optimal ordered problem solver[1].
It is an algorithm to optimally find the solution to any problem, via
a brute force search of the program space. Now, it has been known for a
while that there exists a simple provably optimal solution to all
definable problems (see LSEARCH and HSEARCH), however, it was of purely
theoretical interest since the constant factor was on the order of
2^500.
OOPS has actually made this sort of algorithm practical via the clever
use of.. a concatinative language, in particular a varient of forth. (it
is described in the paper). The novel use of forth in OOPS was taking
advantage of the fact that a program that solves a subset of a certain
problem is more likely to be of use to a program that solves the general
problem, and that the concatination of valid forth programs is a valid
program. In particular, it attempts to solve problems in order from
smallest to larger, incrementally expanding the forth programs biased
towards using succesful runs of smaller functions.
As to a couple other points mentioned, when it comes to exceptions, you
actually, perhaps counterintuitivly, want to abort programs that come
across an exception rather than trying to handle it. in fact, you should
be ultra paranoid. You want to weed out the bad programs as soon as
possible so they don't take up time when you could be testing other
candidates, in particular, you want the most 'dense' encoding possible,
in that you don't want to spend time testing algorithms that have
already been tested, by ignoring exceptions, you have increased your
search space with a lot of 'duplicate' entries. a program that has an
ignored exception and one that never attempted the invalid op in the
first place behave identically, and you will end up running both to
completion needlessly. Of course, there is no way to remove all
redundancy, but you certainly can make it less likely by allowing
exceptions to kill your program.
Also, when it comes to automatcally generating joy programs, you can
avoid having to deal with the bit of syntax joy has by using the floy[2]
variant of joy. floy is joy where are quotations are restricted to a
single symbol. it turns out to be just as expressive as joy, but you
don't need to worry about matching quotations, your primitive 'base
pairs' are simple the joy primitives and the quoted versions of each
and nothing else.
When it comes to recursion, no need to fear, you actually can express
arbitrary recursion without bindings by use of a y combinator[3], which
is easy enough to provide as a primitive in joy, if you include it as a
choice in your genetic code, you are not limited by your lack of
definitions in any way.
I think the following works... but someone check my work.
fix == dup [fix] dip i;
John
[1]
http://www.idsia.ch/~juergen/oops.html
[2]
http://www.latrobe.edu.au/philosophy/phimvt/joy/jp-flatjoy.html
[3]
http://en.wikipedia.org/wiki/Fixed_point_combinator
--
John Meacham - ⑆repetae.net⑆john⑈
chris glur — 2008-11-18 16:37:11
If it's to run as an auto-evolving machine, then decoding,
analysing & reverse-engineering the results is not realistic.
And not a goal.
What is the advantage of having a less syntaxy-language?
Well what does syntax mean ?
In this context it's a human aid to grouping and classifying.
Ie. imposing order. Which is exactly what you DON'T want.
You want the finest possible granularity.
At the same time you want to use the cost effectivness and
speed of a PC.
In fact why bother with joy ?
Just go as close as managable [without crashes] to the
native instruction set of the machine/PC.
For those who know PCs down to the register level,
"divide by zero" is a completely artifical human concept.
In fact "divide" is not know at the register level.
[ It might be interesting to 'evolve' a divide machine
instruction sequence, from the basic add, subtr shifts and
various logical-operations and test/branch instructions ?!]
Similarly the concept of "loop" is just a human construct,
invented for manageability purposes.
When the stone fell from PizaTower it didn't think in
terms of a loop: REPEAT decr(1 mm.) UNTIL (crash).
-------------
So yes, joy is much more appropriate than most
other "languages", but a more general purpose,
finely granulated instruction set, as close as possible
to the hardware's instruction set is best.
Of course the finer the granualarity the closer to a
continuous/analog-computer and the less 'problems'
with chaotic discontinuity.
Alternatively use standard languages to simulate a
continuous analog machine, which would be orders of
magnitude slower, and impose a whole extra layer of
complexity in between.
IMO the divide-by-zero crash is merely one example
of a more general problem. The 'problem' is stability:
a monotomical increase - towards infinity.
Similarly I guess, any infinite-loop [by definition a
stability] is a failure in the-game-of-life algorithm.
So how does natural evolution handle this ?
1. a random mutation breaks the stability;
2. the species goes off towards infinity before a mutation
'turns it', and a failed evolutionary branch results.
== Chris Glur.
On 11/17/08, John Meacham <john@...> wrote:
> Hi, you would probably be really interested in the work of Jurgen
> Schmidhuber, in particular the 'OOPS' optimal ordered problem solver[1].
>
> It is an algorithm to optimally find the solution to any problem, via
> a brute force search of the program space. Now, it has been known for a
> while that there exists a simple provably optimal solution to all
> definable problems (see LSEARCH and HSEARCH), however, it was of purely
> theoretical interest since the constant factor was on the order of
> 2^500.
>
> OOPS has actually made this sort of algorithm practical via the clever
> use of.. a concatinative language, in particular a varient of forth. (it
> is described in the paper). The novel use of forth in OOPS was taking
> advantage of the fact that a program that solves a subset of a certain
> problem is more likely to be of use to a program that solves the general
> problem, and that the concatination of valid forth programs is a valid
> program. In particular, it attempts to solve problems in order from
> smallest to larger, incrementally expanding the forth programs biased
> towards using succesful runs of smaller functions.
>
> As to a couple other points mentioned, when it comes to exceptions, you
> actually, perhaps counterintuitivly, want to abort programs that come
> across an exception rather than trying to handle it. in fact, you should
> be ultra paranoid. You want to weed out the bad programs as soon as
> possible so they don't take up time when you could be testing other
> candidates, in particular, you want the most 'dense' encoding possible,
> in that you don't want to spend time testing algorithms that have
> already been tested, by ignoring exceptions, you have increased your
> search space with a lot of 'duplicate' entries. a program that has an
> ignored exception and one that never attempted the invalid op in the
> first place behave identically, and you will end up running both to
> completion needlessly. Of course, there is no way to remove all
> redundancy, but you certainly can make it less likely by allowing
> exceptions to kill your program.
>
> Also, when it comes to automatcally generating joy programs, you can
> avoid having to deal with the bit of syntax joy has by using the floy[2]
> variant of joy. floy is joy where are quotations are restricted to a
> single symbol. it turns out to be just as expressive as joy, but you
> don't need to worry about matching quotations, your primitive 'base
> pairs' are simple the joy primitives and the quoted versions of each
> and nothing else.
>
> When it comes to recursion, no need to fear, you actually can express
> arbitrary recursion without bindings by use of a y combinator[3], which
> is easy enough to provide as a primitive in joy, if you include it as a
> choice in your genetic code, you are not limited by your lack of
> definitions in any way.
>
> I think the following works... but someone check my work.
>
> fix == dup [fix] dip i;
>
>
> John
>
>
>
> [1] http://www.idsia.ch/~juergen/oops.html
> [2] http://www.latrobe.edu.au/philosophy/phimvt/joy/jp-flatjoy.html
> [3] http://en.wikipedia.org/wiki/Fixed_point_combinator
>
> --
> John Meacham - ⑆repetae.net⑆john⑈
>
Chris Glur —
Did anybody else follow up on the good links which
John Meacham gave ?
Jürgen Schmidhuber starts laying out the algorithms in:
http://www.idsia.ch/~juergen/mljssalevin/node5.html
His drastic claims seem plausible.
So far I haven't seen what language/s he proposes.
== Chris Glur
ET.Do CatGmailSET
Chris Glur —
Did anybody else follow up on the good links which
ementation 2 gave ?
> Jürgen Schmidhuber starts laying out the algorithms in:
> http://www.idsia.ch/~juergen/mljssalevin/node5.html
>
> His drastic claims seem plausible.
>
> So far I haven't seen what language/s he proposes.
== Chris Glur
PS. I'm testing the hack: post via gmail without bogging
down in web-click-mechanism.
My 'proper' mailing-list gives auto-confirms, but perhaps
this one is moderated ?
--------
In:
http://www.idsia.ch/~juergen/mljssalevin/node9.html
he tells: ---------
Implementation 2: Incremental Self-Improvement (IS)
..snip...
= Overview. We will use a simple, assembler-like programming language
which allows for writing many kinds of (learning) algorithms.
-------- and in node10.html he tells:-------
$b_0$ :
Add( $w_1,w_2,w_3$ ) : $c_{w_3}\leftarrow c_{w_1} + c_{w_2}$
(add the contents of work cell $w_1$ and work cell $w_2$ ,
write the result into work cell $w_3$ ).
$b_1$ :
Sub( $w_1,w_2,w_3$ ) : $c_{w_3}\leftarrow c_{w_1} - c_{w_2}$ .
$b_2$ :
Mul( $w_1,w_2,w_3$ ) : $c_{w_3}\leftarrow c_{w_1} * c_{w_2}$ .
$b_3$ :
Mov( $w_1, w_2$ ) : $c_{w_2}\leftarrow c_{w_1}$ .
$b_4$ :
JumpHome: IP $\leftarrow 0$ (jump back to 1st program cell).
Instruction probabilities / Current policy. For each program cell $i$
there is a variable probability distribution $P_i$ on $I$ .
----
That's apparently Latex format, where $b_1$ looks like
"b <subscript 1>". But you get the flavour ?
IMO this all looks promising.
BTW I think: c1 + c2 -> c3 is a better syntax.
Pop-11 uses it and I just can't see why "c3 <- c1 + c2", has
prevailed.
== Chris Glur.
ET.Do CatGmailSET
William Tanksley, Jr — 2008-11-22 22:35:05
chris glur <
crglur@...> wrote:
> If it's to run as an auto-evolving machine, then decoding,
> analysing & reverse-engineering the results is not realistic.
> And not a goal.
You do have to decide the relative fitness of the results, so some
amount of decoding results is needed.
> At the same time you want to use the cost effectivness and
> speed of a PC.
> In fact why bother with joy ?
> Just go as close as managable [without crashes] to the
> native instruction set of the machine/PC.
There's a reason why this hasn't been done -- CPU instructions sets
and architectures aren't amenable to mathematical modeling.
> For those who know PCs down to the register level,
> "divide by zero" is a completely artifical human concept.
> In fact "divide" is not know at the register level.
> [ It might be interesting to 'evolve' a divide machine
> instruction sequence, from the basic add, subtr shifts and
> various logical-operations and test/branch instructions ?!]
Are you thinking of some specific chip? All PCs have a division
instruction in their CPU, and ways to handle division by zero. Intel
and PowerPC both. Some embedded processors don't (I like the SeaForth
S40C18, for obvious reasons to people in this newsgroup), but those
aren't PCs.
> Similarly the concept of "loop" is just a human construct,
> invented for manageability purposes.
No, it's a machine concept.
> Of course the finer the granualarity the closer to a
> continuous/analog-computer and the less 'problems'
> with chaotic discontinuity.
Now I do like the idea of an analog computer; but "fine granularity"
won't give you that. Technically, proteins/DNA are analog, but they
have ENORMOUS chaotic discontinuity. In fact, I suspect you MUST have
chaotic discontinuity in order to make effective computations;
otherwise you have to expend a lot of energy in order to get results.
> == Chris Glur.
-Wm
John Meacham — 2008-11-23 01:02:44
On Sat, Nov 22, 2008 at 03:59:07PM +0000, Chris Glur wrote:
> Did anybody else follow up on the good links which
> John Meacham gave ?
>
> Jürgen Schmidhuber starts laying out the algorithms in:
> http://www.idsia.ch/~juergen/mljssalevin/node5.html
>
> His drastic claims seem plausible.
>
> So far I haven't seen what language/s he proposes.
There are a wide variety of languages that would be suitable for the
techniques he describes, Appendix A of this paper gives the
specification for the specific forth-derived one used for his
implementation of the OOPS (optimal ordered problem solver), which
should also be usable for the adaptive levin search referenced in your
link above.
ftp://ftp.idsia.ch/pub/juergen/oopsmlj.pdf
John
--
John Meacham - ⑆repetae.net⑆john⑈
John Meacham — 2008-11-24 22:44:36
On Sat, Nov 22, 2008 at 02:35:05PM -0800, William Tanksley, Jr wrote:
> chris glur <crglur@...> wrote:
> > If it's to run as an auto-evolving machine, then decoding,
> > analysing & reverse-engineering the results is not realistic.
> > And not a goal.
>
> You do have to decide the relative fitness of the results, so some
> amount of decoding results is needed.
I should say, the main reason I recommended 'floy' instead of joy was
not for easy interpretation of the results, but rather to have a more
convinient base to use as a genetic code. Imagine your language has 16
basic primitives, when using floy, you need only consider those 16
primitives and the quoted versions of each. You have a straight up
linear language of 32 primitives you can cut-up and paste all you want
and still have a valid program. you can consider a length n program as a
base 32 number of length n if that suits you. If you allowed arbitrary
quoting, then you have to make sure quotes are balanced, you no longer
have a linear reppresentation of the language, but a tree-like one,
where each node is a primitive or a quote of an arbitrary list of
primitives or quotes themselves. Not that this is fatal, but it might
make things less convinient depending on how your algorithm works. for
instance, OOPS likes to extend its programs a single instruction at a
time, which is easier for the linear style.
Note that when talking about 'linear genetic programming' many will
assume you mean a first order imperative language, but a higher order
concatenative language like the floy variant of joy is just as linear.
but when communicating with others it is good to keep in mind. perhaps a
better term is in order 'concatenative linear genetic programming'
'functional linear genetic programing' maybe?
> > Similarly the concept of "loop" is just a human construct,
> > invented for manageability purposes.
>
> No, it's a machine concept.
I would go a bit further and say it is a fundamental mathematical
concept if we are talking about what computational "power" loops give
you over not having them. by loops I am including equivalent
(computationally) constructions such as recursion or fixed point
combinators.
http://en.wikipedia.org/wiki/Recursion_theory is the study of this.
John
--
John Meacham - ⑆repetae.net⑆john⑈
chris glur — 2008-11-29 17:53:58
I know little of joy and none of floy.
> OOPS likes to extend its programs a single >instruction at a time, which is easier for the >linear style.
Please define 'linear style'.
From your description, machine-code is linear,
because all 'constructs' are acheived by goto/s.
I suspected the 'extend by 1 instr scheme', but
couldn't find concrete reference -- yet.
Re. OOPS' probability-matrix: does each instruction
aquire a probability ?
And does it's initial probability also change/evolve?
== Chris Glur.