# 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

    John Cowan scripsit:

     > Attached is a by-the-book implementation in Scheme of your algorithm.

     Well, no, it isn't.  You can fetch it from

    http://home.ccil.org/~cowan/qlang.ss .

    --

    John Cowan <jcowan@...>     http://www.reutershealth.com

    I amar prestar aen, han mathon ne nen,    http://www.ccil.org/~cowan

    han mathon ne chae, a han noston ne 'wilith.  --Galadriel, _LOTR:FOTR_

## 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