trees in practice
stevan apter — 2003-06-02 13:02:10
>
> My question is about all the other trees, which contain non-homogeneous
> lists, ones containing as members both other lists and leaves.
> Do you have any examples of those arising in practise?
> The only ones that I would come across are the formulas or expressions
> that arise from various notations e.g. [+ 2 [* 3 4]] for Lisp.
> But these are not the sort of things one would want to (tree)map.
>
you put your finger on it - structured data, but not necessarily
confined to syntax trees. for example, in our app, the definition
of a simulation will contain timeseries with various scalar
parameters, e.g.
[offset<=somedate offset>somedate [... timeseries ...]]
i think you can see similar configurations wherever there is a
GUI (e.g. a search-in-files popup contains a list of files,
a search-for-string, a checkbox to search within directories,
&c.) (in fact, directory structures themselves are trees more
often than not: a directory containing files + directories)
the 'iterate' combinator in ck will take a list with an
initial element and then some further lists:
[10 [1 2 3][4 5 6]] [+*] iterate
3150
in fact, trees are so common that i just don't think of them
as separate from the general case of lists of lists of ...
John Cowan — 2003-06-02 13:04:07
stevan apter scripsit:
> > Do you have any examples of those arising in practise?
> > The only ones that I would come across are the formulas or expressions
> > that arise from various notations e.g. [+ 2 [* 3 4]] for Lisp.
> > But these are not the sort of things one would want to (tree)map.
> >
>
> you put your finger on it - structured data, but not necessarily
> confined to syntax trees.
Another excellent example is HTML, which can be readily understood as
a non-homogeneous tree:
[[p "This is a simple text."] [p "This is an " [em "important"] " text."]]
Joy lists, Lisp s-expressions, and SGML/HTML/XML are all instances of
the same data structure.
--
Is a chair finely made tragic or comic? Is the John Cowan
portrait of Mona Lisa good if I desire to see
jcowan@...
it? Is the bust of Sir Philip Crampton lyrical, www.ccil.org/~cowan
epical or dramatic? If a man hacking in fury www.reutershealth.com
at a block of wood make there an image of a cow,
is that image a work of art? If not, why not? --Stephen Dedalus
stevan apter — 2003-06-02 13:32:06
but i guess the point of manfred's question is, where do you encounter
trees which you would want to process with the tree combinators? that
would seem to narrow the hunt for examples to ones which satisfy two
constraints: (i) the structure of the data is not known, and (ii)
there is an operation you want to apply to the leaves. i think your
html example might qualify (if strings are leaves, as they are in
joy).
----- Original Message -----
From: "John Cowan" <cowan@...>
To: <concatenative@yahoogroups.com>
Sent: Monday, June 02, 2003 9:04 AM
Subject: Re: [stack] trees in practice
> stevan apter scripsit:
>
> > > Do you have any examples of those arising in practise?
> > > The only ones that I would come across are the formulas or expressions
> > > that arise from various notations e.g. [+ 2 [* 3 4]] for Lisp.
> > > But these are not the sort of things one would want to (tree)map.
> > >
> >
> > you put your finger on it - structured data, but not necessarily
> > confined to syntax trees.
>
> Another excellent example is HTML, which can be readily understood as
> a non-homogeneous tree:
>
> [[p "This is a simple text."] [p "This is an " [em "important"] " text."]]
>
> Joy lists, Lisp s-expressions, and SGML/HTML/XML are all instances of
> the same data structure.
>
> --
> Is a chair finely made tragic or comic? Is the John Cowan
> portrait of Mona Lisa good if I desire to see jcowan@...
> it? Is the bust of Sir Philip Crampton lyrical, www.ccil.org/~cowan
> epical or dramatic? If a man hacking in fury www.reutershealth.com
> at a block of wood make there an image of a cow,
> is that image a work of art? If not, why not? --Stephen Dedalus
>
>
> To unsubscribe from this group, send an email to:
> concatenative-unsubscribe@egroups.com
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
John Cowan — 2003-06-02 14:47:17
stevan apter scripsit:
> but i guess the point of manfred's question is, where do you encounter
> trees which you would want to process with the tree combinators? that
> would seem to narrow the hunt for examples to ones which satisfy two
> constraints: (i) the structure of the data is not known, and (ii)
> there is an operation you want to apply to the leaves. i think your
> html example might qualify (if strings are leaves, as they are in
> joy).
Just so. Thus a good use of treemap would be to extract a list of strings
(easily transformed to a single string) from an HTML text.
--
John Cowan
jcowan@... www.reutershealth.com www.ccil.org/~cowan
Assent may be registered by a signature, a handshake, or a click of a computer
mouse transmitted across the invisible ether of the Internet. Formality
is not a requisite; any sign, symbol or action, or even willful inaction,
as long as it is unequivocally referable to the promise, may create a contract.
--_Specht v. Netscape_
stevan apter — 2003-06-02 23:13:19
i suppose my answer at this point has to be: why draw the distinction
in the first place (between trees and other non-tree lists of .. lists)?
there are atoms and there are lists built inductively from atoms.
there are operations you want to apply to atoms (e.g. +) and there are
operations you want to apply to lists (e.g. size). sometimes you want
to recurse to the atoms and apply an operation, sometimes you want to
recurse to lists of depth i and apply an operation (e.g. reverse
strings in a list, transpose matrices in a list, &c.), and sometimes you
want to recurse until some condition is met and then apply an operation
(e.g. when you have a list of symbol value pairs, append some further
symbol value pair).
btw, i persist in using "recurse" as a verb, although i think "recur"
is probably the correct term. you seem to have the pulse of the
language john - what say you?
----- Original Message -----
From: "John Cowan" <cowan@...>
To: <concatenative@yahoogroups.com>
Sent: Monday, June 02, 2003 10:47 AM
Subject: Re: [stack] trees in practice
> stevan apter scripsit:
>
> > but i guess the point of manfred's question is, where do you encounter
> > trees which you would want to process with the tree combinators? that
> > would seem to narrow the hunt for examples to ones which satisfy two
> > constraints: (i) the structure of the data is not known, and (ii)
> > there is an operation you want to apply to the leaves. i think your
> > html example might qualify (if strings are leaves, as they are in
> > joy).
>
> Just so. Thus a good use of treemap would be to extract a list of strings
> (easily transformed to a single string) from an HTML text.
>
> --
> John Cowan jcowan@... www.reutershealth.com www.ccil.org/~cowan
> Assent may be registered by a signature, a handshake, or a click of a computer
> mouse transmitted across the invisible ether of the Internet. Formality
> is not a requisite; any sign, symbol or action, or even willful inaction,
> as long as it is unequivocally referable to the promise, may create a contract.
> --_Specht v. Netscape_
>
>
> To unsubscribe from this group, send an email to:
> concatenative-unsubscribe@egroups.com
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
Samuel Falvo — 2003-06-03 00:06:44
> btw, i persist in using "recurse" as a verb, although i think "recur"
> is probably the correct term. you seem to have the pulse of the
> language john - what say you?
I know you asked John, but here's my take on it. To recur is to do again;
however, to recurse is to step into a nested structure FIRST, then repeat.
Hence, I also tend to use the phrase "to recurse" instead of "to recur."
--
Samuel A. Falvo II
__________________________________
Do you Yahoo!?
Yahoo! Calendar - Free online calendar with sync to Outlook(TM).
http://calendar.yahoo.com
John Cowan — 2003-06-03 01:35:25
stevan apter scripsit:
> btw, i persist in using "recurse" as a verb, although i think "recur"
> is probably the correct term. you seem to have the pulse of the
> language john - what say you?
I do the same.
--
If you understand, John Cowan
things are just as they are;
http://www.ccil.org/~cowan
if you do not understand,
http://www.reutershealth.com
things are just as they are.
jcowan@...
phimvt@lurac.latrobe.edu.au — 2003-06-06 06:36:02
> > My question is about all the other trees, which contain non-homogeneous
> > lists, ones containing as members both other lists and leaves.
> > Do you have any examples of those arising in practise?
> > The only ones that I would come across are the formulas or expressions
> > that arise from various notations e.g. [+ 2 [* 3 4]] for Lisp.
> > But these are not the sort of things one would want to (tree)map.
From the reponses to my question I gather that I must reformulate it.
Of course Joy has trees as a data structure because lists are allowed
to contain lists. And such trees can serve for lots of things
such as expressions (including formulas) in all sorts of languages.
But in all the cases of processing these things the '+' and '*'
would want to be processed differently from the '2', '3' and '4'.
I cannot imagine any use of treemap here. So, to reformulate:
Are there (in the "real" world, outside academia) any cases where
1) the structure of the trees (variable number of trees in lists,
maximum depth occurring) is not known in advance, and 2) all
leaves are to be treated "in the same way" (I know that is vague -
we can argue about wording. Note that a tree remains a tree if
some of its sublists [..] are replaced by their unitlist [[..]].
For some processing this should make a difference, for example
for treemap and treefilter, where the sublists of the result
will differ similarly. For other processing this should make no
difference, for example for treeflatten and treefold (and hence
for treesum).
> you put your finger on it - structured data, but not necessarily
> confined to syntax trees. for example, in our app, the definition
> of a simulation will contain timeseries with various scalar
> parameters, e.g.
>
> [offset<=somedate offset>somedate [... timeseries ...]]
But does your program have to work also for the case where
some of the sublists are replaced by their unit lists?
Where the result may or may not have to differ if the
replacement is done?
> i think you can see similar configurations wherever there is a
> GUI (e.g. a search-in-files popup contains a list of files,
> a search-for-string, a checkbox to search within directories,
> &c.) (in fact, directory structures themselves are trees more
> often than not: a directory containing files + directories)
>
> the 'iterate' combinator in ck will take a list with an
> initial element and then some further lists:
^^^^^^^
but not a list instead ?
^^^^^
Can these be lists of lists?
> [10 [1 2 3][4 5 6]] [+*] iterate
> 3150
unitlist test ...?
> in fact, trees are so common that i just don't think of them
> as separate from the general case of lists of lists of ...
But one has to. Consider a list of lists of lists of integers.
If I want the sum of all the numbers in this tree, and also
sums of all sorts of trees I would write a little 'treesum'.
If I want the list of lists of sums of the bottom lists I would
have to use a different program. If I want the list of
sums of ths lists of lists, different again. So, my question
again: will I evere really need treesum, and not the other
far more specific ones?
- Manfred
phimvt@lurac.latrobe.edu.au — 2003-06-06 06:51:44
On Mon, 2 Jun 2003, John Cowan wrote:
> stevan apter scripsit:
>
> > > Do you have any examples of those arising in practise?
> > > The only ones that I would come across are the formulas or expressions
> > > that arise from various notations e.g. [+ 2 [* 3 4]] for Lisp.
> > > But these are not the sort of things one would want to (tree)map.
> >
> > you put your finger on it - structured data, but not necessarily
> > confined to syntax trees.
>
> Another excellent example is HTML, which can be readily understood as
> a non-homogeneous tree:
I see. Yes, the word "homogeneous" was missing from my question.
I had it in mind. In your example below most processing would
be required to treat the 'p' and the 'em' differently from the
strings.
> [[p "This is a simple text."] [p "This is an " [em "important"] " text."]]
>
> Joy lists, Lisp s-expressions, and SGML/HTML/XML are all instances of
> the same data structure.
In many examples the Lisp convention is used, operators as first
elements of lists, to be treated differently from other elements.
There are even cases where even this does not work:
[ John admires [the-inventor-of the-steam-engine] ]
where 'admires' is a predicate, here written infix, where Lisp
would have made it the first element of the list.
But I can't think of any use of treemap or any of the
other (actual and possible) homogenous tree combinators.
(Well, maybe translate word by word into French, but I
won't make a fool of myself producing the translation.)
- Manfred
phimvt@lurac.latrobe.edu.au — 2003-06-06 06:59:56
On Mon, 2 Jun 2003, stevan apter wrote:
> but i guess the point of manfred's question is, where do you encounter
> trees which you would want to process with the tree combinators? that
> would seem to narrow the hunt for examples to ones which satisfy two
> constraints: (i) the structure of the data is not known, and (ii)
> there is an operation you want to apply to the leaves. i think your
> html example might qualify (if strings are leaves, as they are in
> joy).
I can see that my definition of 'leaf' should really include
symbols. So the HTML example is a case of non-homogeneous trees.
Otherwise, if 'leaf' specifically excludes symbols, then that
example was not a tree.
- Manfred
phimvt@lurac.latrobe.edu.au — 2003-06-06 07:08:58
On Mon, 2 Jun 2003, stevan apter wrote:
> i suppose my answer at this point has to be: why draw the distinction
> in the first place (between trees and other non-tree lists of .. lists)?
As I had it in mind, homogenous lists of homogeneous lists ... are indeed
trees, but some trees are inhomogeneous at arbitrary levels.
> there are atoms and there are lists built inductively from atoms.
> there are operations you want to apply to atoms (e.g. +) and there are
> operations you want to apply to lists (e.g. size). sometimes you want
> to recurse to the atoms and apply an operation, sometimes you want to
> recurse to lists of depth i and apply an operation (e.g. reverse
> strings in a list, transpose matrices in a list, &c.), and sometimes you
> want to recurse until some condition is met and then apply an operation
> (e.g. when you have a list of symbol value pairs, append some further
> symbol value pair).
Exactly my point. And you would want to program for your needs.
But: does it occur much in practice that one wants to treat all
the leaves in arbitary non-homogeneous trees the same way ?
- Manfred
phimvt@lurac.latrobe.edu.au — 2003-06-06 07:31:58
No, don't worry. I haven't abandoned the Joy of the stack.
But for years I have had a simple idea about using a queue
for evaluating expressions. I never wrote it up because
I did not want to get side-tracked. But recently the group
has become interested in "Array languages", and this queue
machine might even be useful for that. Keep in mind that I
wrote it in a hurry - it is woefully sketchy.
http://www.latrobe.edu.au/philosophy/phimvt/misc/queue.html
Stevan: I hope to get more time to look more at you long paper.
Nick: It seems to me that your fix will do it. But wait till
I manage to refresh some suppressed 7 year old memories.
(Suppressed because it did not work.)
- Manfred
Samuel Falvo — 2003-06-06 15:35:47
> http://www.latrobe.edu.au/philosophy/phimvt/misc/queue.html
This is very fascinating. Billy and I have considered queue-based languages in
the past, but have never gotten to the point of being able to define how it
works. It seems to mandate that both data AND operators be enqueued; this
requires a "tagged" implementation: that is, some means of distinguishing
between data and an executable operation.
I wonder how it would be able to handle subroutines (or words, or functions, or
whatever you choose to call them). My idea is that encountering a subroutine
causes the contents of the subroutine to be enqueued, like this:
(assume : CtoF 100 / 180 * 32 + ; )
50 CtoF
CtoF 50
50 100 / 180 * 32 + (contents of CtoF placed on queue)
180 * 32 + 0.5
* 32 + 0.5 180
32 + 0.5 180 *
+ 0.5 180 * 32
0.5 180 * 32 +
32 + 90
+ 90 32
90 32 +
122 <--
Another issue is how the queue is initially populated, and what triggers the
actual evaluation of the queue. If it is aggressively evaluated, then the only
real difference I see from a stack is that it doesn't perform an in-place
rewrite.
--
Samuel A. Falvo II
__________________________________
Do you Yahoo!?
Yahoo! Calendar - Free online calendar with sync to Outlook(TM).
http://calendar.yahoo.com
John Cowan — 2003-06-06 19:41:08
phimvt@... scripsit:
> But for years I have had a simple idea about using a queue
> for evaluating expressions. I never wrote it up because
> I did not want to get side-tracked. But recently the group
> has become interested in "Array languages", and this queue
> machine might even be useful for that. Keep in mind that I
> wrote it in a hurry - it is woefully sketchy.
Attached is a by-the-book implementation in Scheme of your algorithm.
To try it out, make sure getprop, putprop, and error are implemented
in your favorite Scheme (they are in Chez) and type
(q-exec '(+ * 2 3 * 4 5))
You can add new operators like this: (q-prim '- - 2) meaning that
"-" is an operator defined by Scheme's - procedure and with arity 2.
You can use a lambda definition as the second argument.
Bugs: The interpreter will hang if passed a list containing all operands
(anything not defined by q-prim is an operand), as they will be shuffled
to the end of the queue forever. A list consisting solely of a zero-arity
operator will return the operator itself without invoking it.
--
John Cowan
jcowan@... www.ccil.org/~cowan www.reutershealth.com
"If he has seen farther than others,
it is because he is standing on a stack of dwarves."
--Mike Champion, describing Tim Berners-Lee (adapted)
John Cowan — 2003-06-06 19:57:04
phimvt@lurac.latrobe.edu.au — 2003-06-17 07:59:44
On Fri, 6 Jun 2003, Samuel Falvo wrote:
> > http://www.latrobe.edu.au/philosophy/phimvt/misc/queue.html
> I wonder how it would be able to handle subroutines (or words, or functions, or
> whatever you choose to call them). My idea is that encountering a subroutine
> causes the contents of the subroutine to be enqueued, like this:
>
> (assume : CtoF 100 / 180 * 32 + ; )
>
> 50 CtoF
> CtoF 50
> 50 100 / 180 * 32 + (contents of CtoF placed on queue)
For the queue evaluation algorithm to work left to right,
CtoF would have to be written in prefix notation. If postfix
notation is used, the queue would have to work right to left.
[..]
> If it is aggressively evaluated, then the only
^^^^ could you explain, please ?
> real difference I see from a stack is that it doesn't perform an in-place
> rewrite.
That is one difference. The other is that the stack algorithm does not
destroy the original expression.
I'll use this opportunity to mention two other things:
1. The queue is not a suitable data structure as a runtime
book-keeping repository of parameters, local variables and return
addresses. That is best done by a stack.
2. The queue is suitable for time-sharing evaluation. Consider
two jobs:
job1: + 1 * 2 - 3 4
job2: * 5 + 6 / 7 8
Enqueue both:
job1 job2
+ 1 * 2 - 3 4 * 5 + 6 / 7 8
and watch the sparks fly. There is no interference !
- Manfred
Samuel Falvo — 2003-06-17 22:23:46
> > 50 CtoF
> > CtoF 50
> > 50 100 / 180 * 32 + (contents of CtoF placed on queue)
>
> For the queue evaluation algorithm to work left to right,
> CtoF would have to be written in prefix notation. If postfix
> notation is used, the queue would have to work right to left.
But then it ceases to be a queue. Consider:
50 CtoF
50 100 / 180 * 32 +
Assume right to left evaluation. Note that the top element is popped off and
replaced with CtoF's equivalent definition. The 50 stays where it's at. In
other words, it follows a LIFO behavior, not a FIFO. This is why I performed
the substitution left-to-right, with the queue circulating a bit. That
maintained proper FIFO behavior.
--
Samuel A. Falvo II
__________________________________
Do you Yahoo!?
SBC Yahoo! DSL - Now only $29.95 per month!
http://sbc.yahoo.com
stevan apter — 2003-06-19 00:18:26
i've placed a simple k implementation of manfred's prefix
queue algorithm on my site: www.nsl.com/k/q.k
----- Original Message -----
From: "Samuel Falvo" <falvosa@...>
To: <concatenative@yahoogroups.com>
Sent: Tuesday, June 17, 2003 6:23 PM
Subject: Re: [stack] The stack is dead. Long live the queue.
> > > 50 CtoF
> > > CtoF 50
> > > 50 100 / 180 * 32 + (contents of CtoF placed on queue)
> >
> > For the queue evaluation algorithm to work left to right,
> > CtoF would have to be written in prefix notation. If postfix
> > notation is used, the queue would have to work right to left.
>
> But then it ceases to be a queue. Consider:
>
> 50 CtoF
> 50 100 / 180 * 32 +
>
> Assume right to left evaluation. Note that the top element is popped off and
> replaced with CtoF's equivalent definition. The 50 stays where it's at. In
> other words, it follows a LIFO behavior, not a FIFO. This is why I performed
> the substitution left-to-right, with the queue circulating a bit. That
> maintained proper FIFO behavior.
>
> --
> Samuel A. Falvo II
>
>
> __________________________________
> Do you Yahoo!?
> SBC Yahoo! DSL - Now only $29.95 per month!
> http://sbc.yahoo.com
>
>
> To unsubscribe from this group, send an email to:
> concatenative-unsubscribe@egroups.com
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
stevan apter — 2003-06-19 00:33:37
>
> 2. The queue is suitable for time-sharing evaluation. Consider
> two jobs:
> job1: + 1 * 2 - 3 4
> job2: * 5 + 6 / 7 8
> Enqueue both:
> job1 job2
> + 1 * 2 - 3 4 * 5 + 6 / 7 8
> and watch the sparks fly. There is no interference !
>
indeed.
here's a simple k implementation of your queue algorithm. one
modification which was required for time-sharing evaluation:
"while the queue contains more than one element .." -> "while
the queue contains operators .."
job1:(+;1;*;2;-;3;4)
job2:(*;5;+;6;%;7;8)
the evaluator is 'e':
e job1,job2
(-1;34.375)
to trace evaluation, use 'f':
f job1,job2
((+;1;*;2;-;3;4;*;5;+;6;%;7;8)
(1;*;2;-;3;4;*;5;+;6;%;7;8;+)
(*;2;-;3;4;*;5;+;6;%;7;8;+;1)
(2;-;3;4;*;5;+;6;%;7;8;+;1;*)
(-;3;4;*;5;+;6;%;7;8;+;1;*;2)
(*;5;+;6;%;7;8;+;1;*;2;-1)
(5;+;6;%;7;8;+;1;*;2;-1;*)
(+;6;%;7;8;+;1;*;2;-1;*;5)
(6;%;7;8;+;1;*;2;-1;*;5;+)
(%;7;8;+;1;*;2;-1;*;5;+;6)
(+;1;*;2;-1;*;5;+;6;0.875)
(1;*;2;-1;*;5;+;6;0.875;+)
(*;2;-1;*;5;+;6;0.875;+;1)
(*;5;+;6;0.875;+;1;-2)
(5;+;6;0.875;+;1;-2;*)
(+;6;0.875;+;1;-2;*;5)
(+;1;-2;*;5;6.875)
(*;5;6.875;-1)
(-1;34.375))
the code:
O:(-:;+;-;*;%)
V:1 2 2 2 2
o:7=4::
v:V O?
a:{:[~o h:*x;1!x;(+/&\~o'1_ x)<n:v h;1!x;((n+1)_ x),,h . n#1_ x]}
e:(|/o')a/
f:(|/o')a\
Samuel Falvo — 2003-06-19 06:05:55
> i've placed a simple k implementation of manfred's prefix
> queue algorithm on my site: www.nsl.com/k/q.k
Now, if only I knew K . . . :)
--
Samuel A. Falvo II
__________________________________
Do you Yahoo!?
SBC Yahoo! DSL - Now only $29.95 per month!
http://sbc.yahoo.com
stevan apter — 2003-06-19 13:36:02
a slight modification to the algorithm:
if the queue starts with n operands, rotate *all* of them to the rear
else if the queue starts with an operator, and continues with too few
operands, rotate the operator *and* the operands to the rear
else append the value to the result of dropping the operator and its
operands.
f job1,job2
((+;1;*;2;-;3;4;*;5;+;6;%;7;8)
(*;2;-;3;4;*;5;+;6;%;7;8;+;1) <- e.g. (+;1) rotated
(-;3;4;*;5;+;6;%;7;8;+;1;*;2)
(*;5;+;6;%;7;8;+;1;*;2;-1)
(+;6;%;7;8;+;1;*;2;-1;*;5)
(%;7;8;+;1;*;2;-1;*;5;+;6)
(+;1;*;2;-1;*;5;+;6;0.875)
(*;2;-1;*;5;+;6;0.875;+;1)
(*;5;+;6;0.875;+;1;-2)
(+;6;0.875;+;1;-2;*;5)
(+;1;-2;*;5;6.875)
(*;5;6.875;-1)
(-1;34.375))
there's also a slick way to reduce the queue in parallel.
again, you want to process the queue until there are no operators
left.
there are two k ideas we will use.
first, the idea of partitioning a list at indices. e.g.
v:"abcadaefg"
v="a" / mark the a's
1 0 0 1 0 1 0 0 0
&v="a" / where are they?
0 3 5
(&v="a")_ v / partition v at those points
("abc"
"ad"
"aefg")
second, the idea of projection as partial application ("currying"):
+[2;3] / apply + to 2 and 3
5
+[2][3] / project + on 2, then apply it to 3
5
given a function x and a list of arguments y = ..z.., the following
function repeatedly projects. if there are too few arguments in y,
the projected function is returned, else the value:
{x[y]}/
e.g.
{x[y]}/[+;,1]
+[1]
{x[y]}/[+;1 2]
3
f:{x[y]}/[+;,1]
{x[y]}/[f;,2]
3
so, given a queue, repeatedly partition the queue on its operators
and apply projection/evaluation to each partition.
A:{{{x[y]}/[*x;1_ x]}'(&o'x)_ x}
E:(|/o')A/ / evaluate
F:(|/o')A\ / trace
F job1,job2
((+;1;*;2;-;3;4;*;5;+;6;%;7;8)
(+[1];*[2];-1;*[5];+[6];0.875)
(+[1];-2;*[5];6.875)
(-1;34.375))
in particular, you don't have to know how many arguments each operator
takes. when there aren't enough, it just projects.
----- Original Message -----
From: "Samuel Falvo" <falvosa@...>
To: <concatenative@yahoogroups.com>
Sent: Thursday, June 19, 2003 2:05 AM
Subject: Re: [stack] The stack is dead. Long live the queue.
> > i've placed a simple k implementation of manfred's prefix
> > queue algorithm on my site: www.nsl.com/k/q.k
>
> Now, if only I knew K . . . :)
>
> --
> Samuel A. Falvo II
>
>
> __________________________________
> Do you Yahoo!?
> SBC Yahoo! DSL - Now only $29.95 per month!
> http://sbc.yahoo.com
>
>
> To unsubscribe from this group, send an email to:
> concatenative-unsubscribe@egroups.com
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
stevan apter — 2003-06-20 12:18:47
>
> A:{{{x[y]}/[*x;1_ x]}'(&o'x)_ x}
> E:(|/o')A/ / evaluate
> F:(|/o')A\ / trace
>
here's an implementation in cK:
[[|: *: type] map 7 =] `q.o def;
[dup q.o &: _. [q.r] map] `q.q def;
[dup 1 _. swap *: infra i] `q.r def;
[[q.q] Converge] `queue def;
www.nsl.com/k/ck/q.ck
and here's what i say about it in www.nsl.com/papers/ck.htm:
The analogue of a projection in cK is a list of size <= n whose
last element is an operator of valence n. For example, the following
are "projections" of a function f of valence 3:
[1 f]
[1 2 f]
Since cK treats a short stack as an opportunity to project, the
'infra' combinator can be used as an analogue of the K behavior
described above:
10 20 30 unit [+] infra i
10 20 [30 +]
Examples:
[+ 1 * 2 - 3 4] queue
[+ 1 * 2 - 3 4] [[1 +] [2 *] -1] [[1 +] -2] [-1] []
[* 5 + 6 % 7 8] queue
[* 5 + 6 % 7 8] [[5 *] [6 +] 0.875] [[5 *] 6.875] [34.375] []
--
louis:
a while ago, you wrote about your work on a lazily evaluating joy.
have you continued along this path, and if so, do you have anything
new to report?
stevan apter — 2003-06-22 12:58:21
>
> 2. The queue is suitable for time-sharing evaluation. Consider
> two jobs:
> job1: + 1 * 2 - 3 4
> job2: * 5 + 6 / 7 8
> Enqueue both:
> job1 job2
> + 1 * 2 - 3 4 * 5 + 6 / 7 8
> and watch the sparks fly. There is no interference !
>
the problem is that the cycling algorithm doesn't preserve order:
j1:(+;1;*;2;-;3;4)
j2:(%;5;6)
f j1,j2
((+;1;*;2;-;3;4;%;5;6)
(*;2;-;3;4;%;5;6;+;1)
(-;3;4;%;5;6;+;1;*;2)
(%;5;6;+;1;*;2;-1)
(+;1;*;2;-1;0.8333333)
(*;2;-1;0.8333333;+;1)
(0.8333333;+;1;-2)
(+;1;-2;0.8333333)
(0.8333333;-1)) <- (value of j2;value of j1)
my projection-based algorithm failed on this example for a different
reason - fixed on nsl.com (also the ck implementation).
a different question.
how often do you find patterns like these?
f [g] c f
f [g] c inverse-of-f
where c is a combinator? for example,
reverse [p] map reverse
unit [p] map i
phimvt@lurac.latrobe.edu.au — 2003-06-23 07:29:18
For some years I have had thoughts about using bit manipulation
of computer words as a fast implementation of truth tree tests.
I never got around it during my Pascal years, and my C years
have been dominated by Joy. But of course Joy has sets as one of
its datatypes - a somewhat neglected datatype. I have written
up these thoughts in a note:
http://www.latrobe.edu.au/philosophy/phimvt/joy/jp-trutab.html
Don't expect too much: it only works for up to 5 propositions
- but the method is faster than any other theorem prover.
Also, don't look for the new library for sets, setlib.joy,
because I have not tested some other parts.
- Manfred
Martin Young — 2003-06-23 20:58:41
A semi-serious adjunct to the discussion of what data structures might
be used to represent a program and data...
I first came across the language "orthogonal" when it first appeared
around '94 and have had the odd idea that it might be interesting ever
since. The program is a two dimensional array with a stack for data.
Program control runs in any direction in the grid.
The archive can be fetched from here
http://www.catb.org/retro/orthogonal.shar.gz
Apologies to those who've seen it before.
--
Martin Young, at home.
wtanksleyjr@cox.net — 2003-06-23 22:12:45
From: Martin Young <
martin@...>
>A semi-serious adjunct [snip]
>I first came across the language "orthogonal" when it
>first appeared around '94 and have had the odd idea
>that it might be interesting ever since. The program
>is a two dimensional array with a stack for data.
> Program control runs in any direction in the grid.
I hadn't seen it before -- but I'm immediately reminded of
Funge, an N-dimensional equivalent to Befunge, a more
"modern" mockery of all that is holy and right.
I'm very afraid that Befunge might classify as a
concatenative language, and thus be on-topic on this list.
:-)
http://cgibin.erols.com/ziring/cgi-bin/cep/cep.pl?_key=Befunge
http://dmoz.org/Computers/Programming/Languages/Befunge/
> Martin Young, at home.
-Billy
Brent Kerby — 2003-06-24 00:49:55
> I'm immediately reminded of
> Funge, an N-dimensional equivalent to Befunge, a more
> "modern" mockery of all that is holy and right.
>
> I'm very afraid that Befunge might classify as a
> concatenative language, and thus be on-topic on this list.
Hi Billy, and folks. I'm so glad you brought Befunge up! :-)
A few months ago, a friend and I created a new programming language along
the lines of Befunge. The special thing here is that this language, Befreak,
as we call it, is reversible (i.e., every operation is invertible), which
has some interesting implications on control flow.
Take a look:
http://www.tunes.org/~iepos/befreak.html
The system still has a few bugs, but it's quite fun to play with, as there's
an interactive interpreter, where you can see the stack, instruction
pointer, etc., and you step or adjust the speed of execution, and also run
backwards if you like ...
The interpreter needs documentation ... Use CTRL-L to load from a file,
CTRL-W to write, CTRL-R to rename... see the source for the rest :-)
Enjoy...
- Brent Kerby
stevan apter — 2003-06-24 12:34:11
what a fiendishly twisted creation - i love it.
i'm glad to see that the link to the interpreter is
(temporarily?) broken - i have work to do today.
----- Original Message -----
From: "Brent Kerby" <iepos@...>
To: <concatenative@yahoogroups.com>
Sent: Monday, June 23, 2003 8:49 PM
Subject: Re: Re: [stack] The stack is dead. Long live the queue.
> > I'm immediately reminded of
> > Funge, an N-dimensional equivalent to Befunge, a more
> > "modern" mockery of all that is holy and right.
> >
> > I'm very afraid that Befunge might classify as a
> > concatenative language, and thus be on-topic on this list.
>
> Hi Billy, and folks. I'm so glad you brought Befunge up! :-)
>
> A few months ago, a friend and I created a new programming language along
> the lines of Befunge. The special thing here is that this language, Befreak,
> as we call it, is reversible (i.e., every operation is invertible), which
> has some interesting implications on control flow.
>
> Take a look: http://www.tunes.org/~iepos/befreak.html
>
> The system still has a few bugs, but it's quite fun to play with, as there's
> an interactive interpreter, where you can see the stack, instruction
> pointer, etc., and you step or adjust the speed of execution, and also run
> backwards if you like ...
>
> The interpreter needs documentation ... Use CTRL-L to load from a file,
> CTRL-W to write, CTRL-R to rename... see the source for the rest :-)
>
> Enjoy...
>
> - Brent Kerby
>
>
>
> To unsubscribe from this group, send an email to:
> concatenative-unsubscribe@egroups.com
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
Brent Kerby — 2003-06-24 16:37:57
> i'm glad to see that the link to the interpreter is
> (temporarily?) broken - i have work to do today.
Oops. Thanks. Fixed now.
Unfortunately my friend, the author of BFC, the Befreak-to-C compiler, is
not around here anymore and I don't have the sources; I'll try to contact
him and get them. I do still have the DOS executable on my hard drive; I
suppose I should put that up at least.
- Brent
phimvt@lurac.latrobe.edu.au — 2003-06-25 05:49:40
On Mon, 23 Jun 2003, Brent Kerby wrote:
> > I'm immediately reminded of
> > Funge, an N-dimensional equivalent to Befunge, a more
> > "modern" mockery of all that is holy and right.
> >
> > I'm very afraid that Befunge might classify as a
> > concatenative language, and thus be on-topic on this list.
Oh dear, yes. But anyone proposing a Bejoy shall be expelled
from the concatenative group ...
> Hi Billy, and folks. I'm so glad you brought Befunge up! :-)
>
> A few months ago, a friend and I created a new programming language along
> the lines of Befunge. The special thing here is that this language, Befreak,
> as we call it, is reversible (i.e., every operation is invertible), which
> has some interesting implications on control flow.
I am impressed by what you called the prime number program, even if I
don't quite know what it does - keeps on printing primes? And of course
I don't understand how it works, but never mind.
[..]
> http://www.tunes.org/~iepos/befreak.html
Incidentally, two of its links are bad:
Cat's Eye - currently being re-organised
Ping Pong - Error: Unable to determine IP address...
Is the two-dimensionality crucial for the reversibility,
or would it be possible to achieve the same with just
two (longer) rows rather than many (shorter) rows ?
- Manfred
Brent Kerby — 2003-06-25 16:33:47
> Oh dear, yes. But anyone proposing a Bejoy shall be expelled
> from the concatenative group ...
:-)
> > http://www.tunes.org/~iepos/befreak.html
>
> Incidentally, two of its links are bad:
> Cat's Eye - currently being re-organised
> Ping Pong - Error: Unable to determine IP address...
Whoops ... fixed. Thanks.
> Is the two-dimensionality crucial for the reversibility,
> or would it be possible to achieve the same with just
> two (longer) rows rather than many (shorter) rows ?
Hmm, I think the two-dimensionality is necessary. Because control only flows
from instructions to adjacent instructions, it seems that we'd need
arbitrarily many rows in order to achieve arbitrary depths of nested loops,
conditionals, etc. This is an interesting question, though: given a
particular program, what is the minimum number of rows it can be squashed
down to?
If the system had an instruction that allowed (conditional) jumping to an
arbitrary place in the program (I think Funge 98 had such a thing), then we
could probably just squash everything down to one row. But that's pretty
ugly, of course.
However, it is feasible even under the constraints of reversibility.
Clearly, having just an instruction that simply pops that coordinates off
the stack and jumps to it would be irreversible. However, we could have an
instruction that modifies the IP delta (i.e., direction the instruction
pointer is moving/flying, as in Funge 98), via addition (or XOR, perhaps);
then the instruction that receives the jump would be expected to restore the
delta to a normal value (so the IP doesn't fly off to never-never-land).
This is also similar to how branches work in the Pendelum processor, I
believe.
> - Manfred
- Brent