# Concatenative Hardware

## Christopher Diggins — 2007-11-02 00:39:43

    So I've been thinking about concatenative hardware lately. Here is a

    single-stack

    machine instruction set:

    0: JZ (val fxn -> ) // jump to fxn if value is below zero

    1: CALL (fxn) // push return address and jump to fxn

    2: LTEQ (val val -> bool) // compare values

    3: AND (val val -> val) // perform bitwise and

    4: XOR (val val -> val) // perform XOR operation

    5: SHL (val val -> val) // shift-left

    6: DUP (a -> a a)  // duplicate top-value

    7: QTE (val -> fxn) // create a thunk

    8: COMP (fxn fxn -> fxn) // compose two functions (append their contents)

    9: POP (a -> ) // pop value from stack

    10: DIP (a fxn -> a) // applies function to below top of stack

    11: SWP (a b -> b a) // swap top two items

    So essentially we can use the data stack also as a return address

    stack. This is a zero operand instruction set, so it is very compact

    and can be implemented efficiently, but it takes a lot of instructions

    to do simple things (e.g. accessing items deep in the stack).

    The "dip" instruction is so important I'm tempted to include variants:

    12: DIP2 : (a b fxn -> a b)

    13: DIP3 : (a b c fxn -> a b c)

    14: DIP4 : (a b c d fxn -> a b c d)

    15: open for suggestions

    Of course "DIP" can be implemented as "SWP QTE COMP CALL", but I'm

    concerned about performance. The "DIP" is one of the most frequent

    instructions in my code.

    Anyway, hopefully this makes sense to my fellow concatenators. I'd

    love to hear thoughts and suggestions. I'm pretty naive when it comes

    to hardware.

    - Christopher

## Daniel Ehrenberg — 2007-11-02 00:46:03

    This is pretty high-level for an instruction set, don't you think?

    Would it be that easy to implement QTE, COMP or DIP? How would

    quotations be represented? This looks like just a small vocabulary for

    a concatenative langauge, or I'm missing something.

    Daniel Ehrenberg

     On 11/1/07, Christopher Diggins <cdiggins@...> wrote:

    >

    > So I've been thinking about concatenative hardware lately. Here is a

    >  single-stack

    >  machine instruction set:

    >

    >  0: JZ (val fxn -> ) // jump to fxn if value is below zero

    >  1: CALL (fxn) // push return address and jump to fxn

    >  2: LTEQ (val val -> bool) // compare values

    >  3: AND (val val -> val) // perform bitwise and

    >  4: XOR (val val -> val) // perform XOR operation

    >  5: SHL (val val -> val) // shift-left

    >  6: DUP (a -> a a)  // duplicate top-value

    >  7: QTE (val -> fxn) // create a thunk

    >  8: COMP (fxn fxn -> fxn) // compose two functions (append their contents)

    >  9: POP (a -> ) // pop value from stack

    >  10: DIP (a fxn -> a) // applies function to below top of stack

    >  11: SWP (a b -> b a) // swap top two items

    >

    >  So essentially we can use the data stack also as a return address

    >  stack. This is a zero operand instruction set, so it is very compact

    >  and can be implemented efficiently, but it takes a lot of instructions

    >  to do simple things (e.g. accessing items deep in the stack).

    >

    >  The "dip" instruction is so important I'm tempted to include variants:

    >

    >  12: DIP2 : (a b fxn -> a b)

    >  13: DIP3 : (a b c fxn -> a b c)

    >  14: DIP4 : (a b c d fxn -> a b c d)

    >  15: open for suggestions

    >

    >  Of course "DIP" can be implemented as "SWP QTE COMP CALL", but I'm

    >  concerned about performance. The "DIP" is one of the most frequent

    >  instructions in my code.

    >

    >  Anyway, hopefully this makes sense to my fellow concatenators. I'd

    >  love to hear thoughts and suggestions. I'm pretty naive when it comes

    >  to hardware.

    >

    >  - Christopher

    >

## Christopher Diggins — 2007-11-02 01:01:56

    On 11/1/07, Daniel Ehrenberg <microdan@...> wrote:

     > This is pretty high-level for an instruction set, don't you think?

     Well part of the fun of designing hardware is you get to do what you want. :-)

    It is very high-level, which is what I want to experiment with.

     > Would it be that easy to implement QTE, COMP or DIP?

     I don't know. A cons cell implementation wouldn't be too bad, but I

    fear the performance might be horrendous.

     > How would

    > quotations be represented?

     This is an open question, I'm fishing for ideas. Some possibilities

    that I am aware of:

    - cons cells

    - linked arrays

    - vlists

     > This looks like just a small vocabulary for

    > a concatenative langauge, or I'm missing something.

     That's one way of looking at it. It is also similar to the language

    minimal instruction set computers (e.g.

    http://www.cs.uiowa.edu/~jones/arch/cisc/), except for higher-order

    instructions.

    It appears that higher-order instructions can allow for significantly

    more compact code than is possible with traditional stack-oriented

    architectures, which is an area of research I am interested in

    pursuing.

    Anyway, I'd like to hear suggestions on how to implement quotations in

    hardware, or ways to improve the effectiveness of the instruction set

    while maintaining higher-order instructions.

    I'm open to the idea of 1 or even 2 operand instruction sets as well.

    Cheers,

    Christopher

## Don Groves — 2007-11-02 02:22:46

    Hi Christopher,

    I like this idea.

    Any thoughts of emulating this set and building Cat on that virtual

    machine (or is that already how Cat is implemented)? It seems to

    me that doing so would yield significant insights into the utility of

    your instruction set.

    --

    Don Groves

     On Nov 1, 2007, at 19:39 , Christopher Diggins wrote:

    > So I've been thinking about concatenative hardware lately. Here is a

    > single-stack

    > machine instruction set:

    >

    > 0: JZ (val fxn -> ) // jump to fxn if value is below zero

    > 1: CALL (fxn) // push return address and jump to fxn

    > 2: LTEQ (val val -> bool) // compare values

    > 3: AND (val val -> val) // perform bitwise and

    > 4: XOR (val val -> val) // perform XOR operation

    > 5: SHL (val val -> val) // shift-left

    > 6: DUP (a -> a a)  // duplicate top-value

    > 7: QTE (val -> fxn) // create a thunk

    > 8: COMP (fxn fxn -> fxn) // compose two functions (append their

    > contents)

    > 9: POP (a -> ) // pop value from stack

    > 10: DIP (a fxn -> a) // applies function to below top of stack

    > 11: SWP (a b -> b a) // swap top two items

    >

    > So essentially we can use the data stack also as a return address

    > stack. This is a zero operand instruction set, so it is very compact

    > and can be implemented efficiently, but it takes a lot of instructions

    > to do simple things (e.g. accessing items deep in the stack).

    >

    > The "dip" instruction is so important I'm tempted to include variants:

    >

    > 12: DIP2 : (a b fxn -> a b)

    > 13: DIP3 : (a b c fxn -> a b c)

    > 14: DIP4 : (a b c d fxn -> a b c d)

    > 15: open for suggestions

    >

    > Of course "DIP" can be implemented as "SWP QTE COMP CALL", but I'm

    > concerned about performance. The "DIP" is one of the most frequent

    > instructions in my code.

    >

    > Anyway, hopefully this makes sense to my fellow concatenators. I'd

    > love to hear thoughts and suggestions. I'm pretty naive when it comes

    > to hardware.

    >

    > - Christopher

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## Christopher Diggins — 2007-11-02 03:22:44

    Hi Don,

    I'm glad you like the idea. The current Cat implementation has over a

    hundred built-in primitives, because I was obsessed with performance in the

    early stages. This is no longer the case, so the design is a bit weird, some

    parts are heavily optimized while others are extremely naive.

    I do plan on writing an VM emulator for the instruction set once I get some

    more feedback. I figure many people might have some insights to share, to

    help reduce the development time. I want to make sure that I am not going

    down a particularly boneheaded path.

    Thanks,

    Christopher

     On 11/1/07, Don Groves <dgroves@...> wrote:

    >

    >   Hi Christopher,

    >

    > I like this idea.

    >

    > Any thoughts of emulating this set and building Cat on that virtual

    > machine (or is that already how Cat is implemented)? It seems to

    > me that doing so would yield significant insights into the utility of

    > your instruction set.

    > --

    > Don Groves

    >

    > On Nov 1, 2007, at 19:39 , Christopher Diggins wrote:

    >

    > > So I've been thinking about concatenative hardware lately. Here is a

    > > single-stack

    > > machine instruction set:

    > >

    > > 0: JZ (val fxn -> ) // jump to fxn if value is below zero

    > > 1: CALL (fxn) // push return address and jump to fxn

    > > 2: LTEQ (val val -> bool) // compare values

    > > 3: AND (val val -> val) // perform bitwise and

    > > 4: XOR (val val -> val) // perform XOR operation

    > > 5: SHL (val val -> val) // shift-left

    > > 6: DUP (a -> a a) // duplicate top-value

    > > 7: QTE (val -> fxn) // create a thunk

    > > 8: COMP (fxn fxn -> fxn) // compose two functions (append their

    > > contents)

    > > 9: POP (a -> ) // pop value from stack

    > > 10: DIP (a fxn -> a) // applies function to below top of stack

    > > 11: SWP (a b -> b a) // swap top two items

    > >

    > > So essentially we can use the data stack also as a return address

    > > stack. This is a zero operand instruction set, so it is very compact

    > > and can be implemented efficiently, but it takes a lot of instructions

    > > to do simple things (e.g. accessing items deep in the stack).

    > >

    > > The "dip" instruction is so important I'm tempted to include variants:

    > >

    > > 12: DIP2 : (a b fxn -> a b)

    > > 13: DIP3 : (a b c fxn -> a b c)

    > > 14: DIP4 : (a b c d fxn -> a b c d)

    > > 15: open for suggestions

    > >

    > > Of course "DIP" can be implemented as "SWP QTE COMP CALL", but I'm

    > > concerned about performance. The "DIP" is one of the most frequent

    > > instructions in my code.

    > >

    > > Anyway, hopefully this makes sense to my fellow concatenators. I'd

    > > love to hear thoughts and suggestions. I'm pretty naive when it comes

    > > to hardware.

    > >

    > > - Christopher

    > >

    > >

    > >

    > > Yahoo! Groups Links

    > >

    > >

    > >

    > >

    >

    >

    >

    [Non-text portions of this message have been removed]

## Don Groves — 2007-11-02 03:48:30

    Not boneheaded at all , imho.  Forth hardware has been around for a

    long time.

    With the ubiquity of Java, I'm expecting to see JVM hardware someday

    also.

    Lately, I've been re-reading the ideas behind Ralph Griswold's Icon

    language.

    Icon has higher level semantics than most programming languages and some

    excellent underlying ideas, such as generators, which implement

    laziness.

    I'm planning on including generators in my experimental concatenative

    language

    as well as other Icon ideas. For example, [1 2 ...] is a lazy list of

    positive integers.

    The ellipsis is a generator which unconses the next integer and

    produces [2 3 ...],

    [3 4 ...], etc.

    Icon can be found at http://www.cs.arizona.edu/icon/ for those

    interested.

    --

    Don

     On Nov 1, 2007, at 19:22 , Christopher Diggins wrote:

    > Hi Don,

    >

    > I'm glad you like the idea. The current Cat implementation has over a

    > hundred built-in primitives, because I was obsessed with

    > performance in the

    > early stages. This is no longer the case, so the design is a bit

    > weird, some

    > parts are heavily optimized while others are extremely naive.

    >

    > I do plan on writing an VM emulator for the instruction set once I

    > get some

    > more feedback. I figure many people might have some insights to

    > share, to

    > help reduce the development time. I want to make sure that I am not

    > going

    > down a particularly boneheaded path.

    >

    > Thanks,

    > Christopher

    >

    > On 11/1/07, Don Groves <dgroves@...> wrote:

    >>

    >>   Hi Christopher,

    >>

    >> I like this idea.

    >>

    >> Any thoughts of emulating this set and building Cat on that virtual

    >> machine (or is that already how Cat is implemented)? It seems to

    >> me that doing so would yield significant insights into the utility of

    >> your instruction set.

    >> --

    >> Don Groves

    >>

    >> On Nov 1, 2007, at 19:39 , Christopher Diggins wrote:

    >>

    >>> So I've been thinking about concatenative hardware lately. Here is a

    >>> single-stack

    >>> machine instruction set:

    >>>

    >>> 0: JZ (val fxn -> ) // jump to fxn if value is below zero

    >>> 1: CALL (fxn) // push return address and jump to fxn

    >>> 2: LTEQ (val val -> bool) // compare values

    >>> 3: AND (val val -> val) // perform bitwise and

    >>> 4: XOR (val val -> val) // perform XOR operation

    >>> 5: SHL (val val -> val) // shift-left

    >>> 6: DUP (a -> a a) // duplicate top-value

    >>> 7: QTE (val -> fxn) // create a thunk

    >>> 8: COMP (fxn fxn -> fxn) // compose two functions (append their

    >>> contents)

    >>> 9: POP (a -> ) // pop value from stack

    >>> 10: DIP (a fxn -> a) // applies function to below top of stack

    >>> 11: SWP (a b -> b a) // swap top two items

    >>>

    >>> So essentially we can use the data stack also as a return address

    >>> stack. This is a zero operand instruction set, so it is very compact

    >>> and can be implemented efficiently, but it takes a lot of

    >>> instructions

    >>> to do simple things (e.g. accessing items deep in the stack).

    >>>

    >>> The "dip" instruction is so important I'm tempted to include

    >>> variants:

    >>>

    >>> 12: DIP2 : (a b fxn -> a b)

    >>> 13: DIP3 : (a b c fxn -> a b c)

    >>> 14: DIP4 : (a b c d fxn -> a b c d)

    >>> 15: open for suggestions

    >>>

    >>> Of course "DIP" can be implemented as "SWP QTE COMP CALL", but I'm

    >>> concerned about performance. The "DIP" is one of the most frequent

    >>> instructions in my code.

    >>>

    >>> Anyway, hopefully this makes sense to my fellow concatenators. I'd

    >>> love to hear thoughts and suggestions. I'm pretty naive when it

    >>> comes

    >>> to hardware.

    >>>

    >>> - Christopher

    >>>

    >>>

    >>>

    >>> Yahoo! Groups Links

    >>>

    >>>

    >>>

    >>>

    >>

    >>

    >>

    >

    >

    > [Non-text portions of this message have been removed]

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## Christopher Diggins — 2007-11-02 04:11:27

    > I'm planning on including generators in my experimental concatenative

    > language > as well as other Icon ideas. For example, [1 2 ...] is a lazy list of

    > positive integers. The ellipsis is a generator which unconses the next integer and

    > produces [2 3 ...], > [3 4 ...], etc.

     Cat has lazy lists too. Cat is sometimes lazy and sometimes eager

    depending on the constructors used. The "unfold" function generates a

    Haskell style lazy list. It takes a successor function and a

    termination predicate (which can be always return true) and a next

    function. In other words the type signature is:

    unfold : ('a ('a -> 'a) ('a -> bool) -> list)

    - Christopher

## Joe Bowbeer — 2007-11-02 04:14:01

    On 11/1/07, Don Groves <dgroves@...> wrote:

     > With the ubiquity of Java, I'm expecting to see JVM hardware someday

    >

     ARM's Jazelle-enabled processors do this in the small

     http://www.arm.com/products/esd/jazelle_home.html

    Azul Compute Appliance does this in the large

     http://www.azulsystems.com/products/compute_appliance.htm

    --Joe

## Don Groves — 2007-11-02 05:57:13

    Thanks, Joe, both look interesting. I sure wish the ARM processor family

    had been available before I retired from embedded systems programming!

    --

    Don

     On Nov 1, 2007, at 19:14 , Joe Bowbeer wrote:

    > On 11/1/07, Don Groves <dgroves@...> wrote:

    >> With the ubiquity of Java, I'm expecting to see JVM hardware someday

    >>

    >

    > ARM's Jazelle-enabled processors do this in the small

    >

    >  http://www.arm.com/products/esd/jazelle_home.html

    >

    > Azul Compute Appliance does this in the large

    >

    >  http://www.azulsystems.com/products/compute_appliance.htm

    >

    > --Joe

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## Don Groves — 2007-11-02 06:00:16

    Most interesting. Haskell is another language I know a bit about

    and need to learn much more. So little time, so many languages ;-)

    --

    Don

     On Nov 1, 2007, at 19:11 , Christopher Diggins wrote:

    >> I'm planning on including generators in my experimental concatenative

    >> language > as well as other Icon ideas. For example, [1 2 ...] is

    >> a lazy list of

    >> positive integers. The ellipsis is a generator which unconses the

    >> next integer and

    >> produces [2 3 ...], > [3 4 ...], etc.

    >

    > Cat has lazy lists too. Cat is sometimes lazy and sometimes eager

    > depending on the constructors used. The "unfold" function generates a

    > Haskell style lazy list. It takes a successor function and a

    > termination predicate (which can be always return true) and a next

    > function. In other words the type signature is:

    >

    > unfold : ('a ('a -> 'a) ('a -> bool) -> list)

    >

    > - Christopher

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## Don Groves — 2007-11-02 07:38:25

    Hi,  All --

    Since I've mentioned generators and my lazy list example, I may as well

    present the entire design for discussion. Also, I've decided on a name

    change. Instead of Catenate, I've decided on ACL. ACL could stand for

    A Concatenative Language, or Another Concatenative Language, or

    Anterior Cruciate Ligament, but it doesn't have to. It will be

    referred to

    simply as ACL.

    A generator is a persistent function. When activated, it pushes a

    copy of

    itself on the stack. The copy performs the generative function and

    remains

    on the stack until specifically dropped. Each time it comes to the

    top of

    the stack it generates a value according to its definition.

    Example: [1 2 ...] defgen Z+

    Z+ is now a generator a copy of which will generate positive integers as

    long as it remains active (until dropped from the stack).

    stack:

    => Z+

    yields -

    stack:[2 3 ...] 1

    =>

    The next time it comes to the top of the stack, it will generate a 2,

    thusly -

    stack:[3 4 ...] 2

    =>

    This behaviour continues until the user/program decides to stop it.

    Thus,

    the ellipsis generator, ..., can mimic an infinite list. Z+ is

    included in the

    ACL standard library.

    This form of generator may also be finite: [1 3 ... 99] defgen odd<100

    behaves like this -

    stack:

    => odd<100

    stack:[3 5 ... 99] 1

    =>

    ... and so on until 99 is produced, at which point the generator copy

    self-destructs.

    ACL will have other generator forms, such as the Fibonacci sequence.

    Comments, suggestions, etc., are solicited and greatly appreciated,

    Don Groves

    "Computers are like Old Testament gods; lots of rules and no mercy."

      -- Joseph Campbell

## pml060912 — 2007-11-02 09:25:15

    --- In concatenative@yahoogroups.com, "Christopher Diggins"

    <cdiggins@...> wrote:

     >

    > So I've been thinking about concatenative hardware lately. Here is a

    > single-stack

    > machine instruction set:

    >

    > 0: JZ (val fxn -> ) // jump to fxn if value is below zero

    > 1: CALL (fxn) // push return address and jump to fxn

    > 2: LTEQ (val val -> bool) // compare values

    > 3: AND (val val -> val) // perform bitwise and

    > 4: XOR (val val -> val) // perform XOR operation

    > 5: SHL (val val -> val) // shift-left

    > 6: DUP (a -> a a)  // duplicate top-value

    > 7: QTE (val -> fxn) // create a thunk

    > 8: COMP (fxn fxn -> fxn) // compose two functions (append their

     contents)

     > 9: POP (a -> ) // pop value from stack

    > 10: DIP (a fxn -> a) // applies function to below top of stack

    > 11: SWP (a b -> b a) // swap top two items

    >

    > So essentially we can use the data stack also as a return address

    > stack.

     Maybe I'm missing a layer of sophistication hidden within the

    capabilities of one of these instructions (COMP, maybe?), but doesn't

    that restrict the virtual machine to the capabilities of a pure single

    stack machine? As I mentioned the other day, those aren't Turing

    equivalent - I had a quick look at the wikipedia entry on stack

    machines to confirm it - although you get that with two stack machines

    and machines with more generalised instructions like PICK or ROLL or

    data structuring/accessing instructions (ignoring finite physical

    restrictions for the moment).

     This is a zero operand instruction set, so it is very compact

     > and can be implemented efficiently, but it takes a lot of instructions

    > to do simple things (e.g. accessing items deep in the stack).

     For what it's worth, I contributed the original versions of the high

    level PICK and ROLL used in Ting's Eforth. They work using recursion

    and the return stack for temporary storage. That approach doesn't use

    many instructions in the code or many different opcodes, but it does

    use a lot of cycles to get very deep.

     >

    > The "dip" instruction is so important I'm tempted to include variants:

    >

    > 12: DIP2 : (a b fxn -> a b)

    > 13: DIP3 : (a b c fxn -> a b c)

    > 14: DIP4 : (a b c d fxn -> a b c d)

    > 15: open for suggestions

    >

    > Of course "DIP" can be implemented as "SWP QTE COMP CALL", but I'm

    > concerned about performance. The "DIP" is one of the most frequent

    > instructions in my code.

    >

    > Anyway, hopefully this makes sense to my fellow concatenators. I'd

    > love to hear thoughts and suggestions. I'm pretty naive when it comes

    > to hardware.

    >

    > - Christopher

    >

## Christopher Diggins — 2007-11-02 12:02:12

    On 11/2/07, pml060912 <pml540114@...> wrote:

     > --- In concatenative@yahoogroups.com, "Christopher Diggins"

    > <cdiggins@...> wrote:

    > >

    > > So I've been thinking about concatenative hardware lately. Here is a

    > > single-stack

    > > machine instruction set:

    > >

    > > 0: JZ (val fxn -> ) // jump to fxn if value is below zero

    > > 1: CALL (fxn) // push return address and jump to fxn

    > > 2: LTEQ (val val -> bool) // compare values

    > > 3: AND (val val -> val) // perform bitwise and

    > > 4: XOR (val val -> val) // perform XOR operation

    > > 5: SHL (val val -> val) // shift-left

    > > 6: DUP (a -> a a) // duplicate top-value

    > > 7: QTE (val -> fxn) // create a thunk

    > > 8: COMP (fxn fxn -> fxn) // compose two functions (append their

    > contents)

    > > 9: POP (a -> ) // pop value from stack

    > > 10: DIP (a fxn -> a) // applies function to below top of stack

    > > 11: SWP (a b -> b a) // swap top two items

    > >

    > > So essentially we can use the data stack also as a return address

    > > stack.

    >

    > Maybe I'm missing a layer of sophistication hidden within the

    > capabilities of one of these instructions (COMP, maybe?), but doesn't

    > that restrict the virtual machine to the capabilities of a pure single

    > stack machine?

     QTE and COMP allows you to treat function like stacks, by adding data

    to them, which you can accesss later by calling CALL. So

    computationally it is a multi-stack machine.

     > As I mentioned the other day, those aren't Turing

    > equivalent - I had a quick look at the wikipedia entry on stack

    > machines to confirm it - although you get that with two stack machines

    > and machines with more generalised instructions like PICK or ROLL or

    > data structuring/accessing instructions (ignoring finite physical

    > restrictions for the moment).

    >

    > This is a zero operand instruction set, so it is very compact

    > > and can be implemented efficiently, but it takes a lot of instructions

    > > to do simple things (e.g. accessing items deep in the stack).

    >

    > For what it's worth, I contributed the original versions of the high

    > level PICK and ROLL used in Ting's Eforth. They work using recursion

    > and the return stack for temporary storage. That approach doesn't use

    > many instructions in the code or many different opcodes, but it does

    > use a lot of cycles to get very deep.

     What are the stack effects of PICK and ROLL? (I don't really know

    FORTH that well).

    I wonder if PICK and ROLL would be a better choice than DIP, QTE, COMP, etc.

    - Christopher

## pml060912 — 2007-11-02 13:15:37

    --- In concatenative@yahoogroups.com, "Christopher Diggins"

    <cdiggins@...> wrote:

     >

    > On 11/2/07, pml060912 <pml540114@...> wrote:

     .

    .

    .

     > > Maybe I'm missing a layer of sophistication hidden within the

    > > capabilities of one of these instructions (COMP, maybe?), but doesn't

    > > that restrict the virtual machine to the capabilities of a pure single

    > > stack machine?

    >

    > QTE and COMP allows you to treat function like stacks, by adding data

    > to them, which you can accesss later by calling CALL. So

    > computationally it is a multi-stack machine.

     Could you describe their behaviour a bit more?

    .

    .

    .

     > > > to do simple things (e.g. accessing items deep in the stack).

    > >

    > > For what it's worth, I contributed the original versions of the high

    > > level PICK and ROLL used in Ting's Eforth. They work using recursion

    > > and the return stack for temporary storage. That approach doesn't use

    > > many instructions in the code or many different opcodes, but it does

    > > use a lot of cycles to get very deep.

    >

    > What are the stack effects of PICK and ROLL? (I don't really know

    > FORTH that well).

    >

    > I wonder if PICK and ROLL would be a better choice than DIP, QTE,

     COMP, etc.

    They provide means of accessing items arbitrarily deep in the stack,

    e.g. 7 PICK puts a copy of the 7th item on top and 7 ROLL moves the

    7th item to the top withe higher ones each moving down one, a

    generalised DUP and a generalised SWAP. But they don't do the other stuff.

    However, my personal taste would be to separate the different kinds of

    functionality during the research phase anyway, at least until I found

    the combinations that seemed to come up the way you found with the DIP

    generalisations. That would mean, say, using PICK and I rather than a

    generalised DIP.

## William Tanksley, Jr — 2007-11-02 17:57:06

    Christopher Diggins <cdiggins@...> wrote:

     > So I've been thinking about concatenative hardware lately. Here is a

    > single-stack machine instruction set:

     Interesting. I've played a lot with stack hardware (designed a

    complete processor for a HW class), so your twist on the subject is

    very thought-provoking.

     > 0: JZ (val fxn -> ) // jump to fxn if value is below zero

    > 1: CALL (fxn) // push return address and jump to fxn

    > 2: LTEQ (val val -> bool) // compare values

    > 3: AND (val val -> val) // perform bitwise and

    > 4: XOR (val val -> val) // perform XOR operation

    > 5: SHL (val val -> val) // shift-left

    > 6: DUP (a -> a a)  // duplicate top-value

    > 7: QTE (val -> fxn) // create a thunk

    > 8: COMP (fxn fxn -> fxn) // compose two functions (append their contents)

    > 9: POP (a -> ) // pop value from stack

    > 10: DIP (a fxn -> a) // applies function to below top of stack

    > 11: SWP (a b -> b a) // swap top two items

     Very high-level... You'll need more detailed semantics for that to

    work at all (memory management will be a BEAR for you). Of course,

    you're entirely missing ADD and such. Oh, and I see you've got a

    comparison instruction, but no conditional call or branch. I assume

    you intended to imply those, of course.

    You might want to look at Henry Baker's papers on a similar topic.

    Check out his paper on O(1) instructions which could implement a VERY

    flexible VM that doesn't require GC;

    http://home.pipeline.com/~hbaker1/LinearLisp.html. "Hash cons"ing is

    very important, and might even fit into hardware.

    Once you get memory management a bit more simple, you need to

    determine the implications of your instruction encoding. You don't

    explain your encoding, which leads me to suspect that each instruction

    is encoded as a byte. Needless to say, bit packing is a LOT nicer,

    even when you're doing a VM.

    The worst implication of your instruction encoding -- and this isn't

    something you've made explicit -- is that your instructions _appear_

    to be stored in CONS cells. This implies that there's one per cell.

    That's MAJORLY inefficient in every way, needless to say. It's obvious

    that one optimization would be to pack multiple instructions into a

    single CONS cell, but that could well give you worse problems, as then

    you have to decide how to handle CALLs. Perhaps the answer should be

    that a CALL is always the CDR of a CONS pair...

     > So essentially we can use the data stack also as a return address

    > stack. This is a zero operand instruction set, so it is very compact

    > and can be implemented efficiently, but it takes a lot of instructions

    > to do simple things (e.g. accessing items deep in the stack).

     "Doctor, it hurts when I do this." ;-)

    It's possible that you shouldn't consider "accessing items deep in the

    stack" to be a "simple thing".

     > The "dip" instruction is so important I'm tempted to include variants:

    > 12: DIP2 : (a b fxn -> a b)

    > 13: DIP3 : (a b c fxn -> a b c)

    > 14: DIP4 : (a b c d fxn -> a b c d)

     The DIP instruction is so complex, high-overhead, and dependent on

    precise details of user needs that I'm tempted to not include it.

     > 15: open for suggestions

     YES! 4 bits! (Assuming you don't want math or conditionals...)

     > Of course "DIP" can be implemented as "SWP QTE COMP CALL", but I'm

    > concerned about performance. The "DIP" is one of the most frequent

    > instructions in my code.

     It seems to me that DIP is inherently complex -- you don't want to

    stretch your clock cycle to accommodate a single instruction. Much

    better to let users implement DIP the way they need it.

    Although I just noticed you use CONCAT instead of CONS. Hmm. That's

    another inherently complex instruction (it takes linear time).

     > Anyway, hopefully this makes sense to my fellow concatenators. I'd

    > love to hear thoughts and suggestions. I'm pretty naive when it comes

    > to hardware.

     Think about this carefully... Generally speaking, the minimal

    requirement for hardware is that all instructions should be O(1). I've

    seen that requirement skipped... Chuck Moore's processors use cycle

    times so fast that there's isn't time for the carry flag to propagate

    on addition, so when you do addition you have to allow the stack to

    settle in the ALU before you read the result of the addition (it's

    simpler in practice than it sounds). Most CISCs have varying

    instruction times. But in general it makes things messy.

    Whatever you do, you do NOT want any single instruction to NOT take

    constant time.

     > - Christopher

     -Billy

## William Tanksley, Jr — 2007-11-02 18:26:56

    Don Groves <dgroves@...> wrote:

     > A generator is a persistent function. When activated, it pushes a

    > copy of

    > itself on the stack. The copy performs the generative function and

    > remains

    > on the stack until specifically dropped. Each time it comes to the

    > top of the stack it generates a value according to its definition.

     "Comes to the top of the stack" is unclear. It would make more sense

    to say that every time GENERATE is called on it, it produces the next

    value. (You could also overload UNCONS to work that way... but that

    seems dangerous.)

     > Example: [1 2 ...] defgen Z+

    > Z+ is now a generator a copy of which will generate positive integers as

    > long as it remains active (until dropped from the stack).

     As long as you're defining new syntax, why not have "[x ...]" be

    defined in the language as a "generator quotation", so you don't need

    'defgen'? Just use 'const' or whatever.

     > stack:

    > => Z+

    > yields -

    > stack:[2 3 ...] 1

    > =>

    > The next time it comes to the top of the stack, it will generate a 2,

    > thusly -

    > stack:[3 4 ...] 2

    > =>

     Specifically, does this mean that:

    => Z+ SWAP SWAP

    yields -

    stack:1 2 [4 5 ...] 3

    ?

    If so, is there any way to drop a generator from the stack?

     > This behaviour continues until the user/program decides to stop it.

     How?

     > Thus,

    > the ellipsis generator, ..., can mimic an infinite list. Z+ is

    > included in the

    > ACL standard library.

     Obviously the ellipsis generator is either very clever with lots of

    special cases, or it can only handle additive sequences.

     > ... and so on until 99 is produced, at which point the generator copy

    > self-destructs.

     Without being dropped? How will client code know that their stack's

    been changed?

     > Don Groves

     -Billy

## Christopher Diggins — 2007-11-02 18:32:58

    On 11/2/07, William Tanksley, Jr <wtanksleyjr@...> wrote:

     > Christopher Diggins <cdiggins@...> wrote:

    >  > So I've been thinking about concatenative hardware lately. Here is a

    >  > single-stack machine instruction set:

    >

    >  Interesting. I've played a lot with stack hardware (designed a

    >  complete processor for a HW class), so your twist on the subject is

    >  very thought-provoking.

    >

    >  > 0: JZ (val fxn -> ) // jump to fxn if value is below zero

    >  > 1: CALL (fxn) // push return address and jump to fxn

    >  > 2: LTEQ (val val -> bool) // compare values

    >  > 3: AND (val val -> val) // perform bitwise and

    >  > 4: XOR (val val -> val) // perform XOR operation

    >  > 5: SHL (val val -> val) // shift-left

    >  > 6: DUP (a -> a a)  // duplicate top-value

    >  > 7: QTE (val -> fxn) // create a thunk

    >  > 8: COMP (fxn fxn -> fxn) // compose two functions (append their contents)

    >  > 9: POP (a -> ) // pop value from stack

    >  > 10: DIP (a fxn -> a) // applies function to below top of stack

    >  > 11: SWP (a b -> b a) // swap top two items

    >

    >  Very high-level... You'll need more detailed semantics for that to

    >  work at all (memory management will be a BEAR for you).

     Yes, this is where I am stuck.

     > Of course,

    >  you're entirely missing ADD and such. Oh, and I see you've got a

    >  comparison instruction, but no conditional call or branch. I assume

    >  you intended to imply those, of course.

     Whoops some mistakes. Especially the missing ADD.

     >  You might want to look at Henry Baker's papers on a similar topic.

    >  Check out his paper on O(1) instructions which could implement a VERY

    >  flexible VM that doesn't require GC;

    >  http://home.pipeline.com/~hbaker1/LinearLisp.html. "Hash cons"ing is

    >  very important, and might even fit into hardware.

     Great, I'll look into it.

     >  Once you get memory management a bit more simple, you need to

    >  determine the implications of your instruction encoding. You don't

    >  explain your encoding, which leads me to suspect that each instruction

    >  is encoded as a byte.

     4 bits is my goal.

     > Needless to say, bit packing is a LOT nicer,

    >  even when you're doing a VM.

    >

    >  The worst implication of your instruction encoding -- and this isn't

    >  something you've made explicit -- is that your instructions _appear_

    >  to be stored in CONS cells.

     I'm looking for alternatives, I don't like the idea of CONS cells. I'm

    thinking of a linked list of mini-stacks, but this is just a vague

    notion at this point.

     > This implies that there's one per cell.

    >  That's MAJORLY inefficient in every way, needless to say.

     Yep.

     > It's obvious

    >  that one optimization would be to pack multiple instructions into a

    >  single CONS cell,

     I'm thinking of 32 bit stack, which can contain 8 4 bit instructions.

     > but that could well give you worse problems, as then

    >  you have to decide how to handle CALLs. Perhaps the answer should be

    >  that a CALL is always the CDR of a CONS pair...

     Interesting idea.

     >  > So essentially we can use the data stack also as a return address

    >  > stack. This is a zero operand instruction set, so it is very compact

    >  > and can be implemented efficiently, but it takes a lot of instructions

    >  > to do simple things (e.g. accessing items deep in the stack).

    >

    >  "Doctor, it hurts when I do this." ;-)

    >

    >  It's possible that you shouldn't consider "accessing items deep in the

    >  stack" to be a "simple thing".

    >

    >  > The "dip" instruction is so important I'm tempted to include variants:

    >  > 12: DIP2 : (a b fxn -> a b)

    >  > 13: DIP3 : (a b c fxn -> a b c)

    >  > 14: DIP4 : (a b c d fxn -> a b c d)

    >

    >  The DIP instruction is so complex, high-overhead, and dependent on

    >  precise details of user needs that I'm tempted to not include it.

     Good point. Besides I need those slots for ADD, a PUSH, and possibly a NOOP.

     >  > 15: open for suggestions

    >

    >  YES! 4 bits! (Assuming you don't want math or conditionals...)

     JZ was the conditional (which I am thinking of combining with LTEQ, to

    make JLE (Jump if less than or equal)  when do we use LTEQ outside of

    a branch anyway, if we need a true LTEQ we can say: JLE

     >  > Of course "DIP" can be implemented as "SWP QTE COMP CALL", but I'm

    >  > concerned about performance. The "DIP" is one of the most frequent

    >  > instructions in my code.

    >

    >  It seems to me that DIP is inherently complex -- you don't want to

    >  stretch your clock cycle to accommodate a single instruction.

     That is a good point.

     > Much

    >  better to let users implement DIP the way they need it.

     Its just that when I generate Cat from C code algorithmically it

    generates a ton of DIPs.

     >  Although I just noticed you use CONCAT instead of CONS. Hmm. That's

    >  another inherently complex instruction (it takes linear time).

     Not neccessarily, if we use lists with tail pointers. However, that is ugly.

     >  > Anyway, hopefully this makes sense to my fellow concatenators. I'd

    >  > love to hear thoughts and suggestions. I'm pretty naive when it comes

    >  > to hardware.

    >

    >  Think about this carefully... Generally speaking, the minimal

    >  requirement for hardware is that all instructions should be O(1).

     Good idea.

     > I've

    >  seen that requirement skipped... Chuck Moore's processors use cycle

    >  times so fast that there's isn't time for the carry flag to propagate

    >  on addition, so when you do addition you have to allow the stack to

    >  settle in the ALU before you read the result of the addition (it's

    >  simpler in practice than it sounds). Most CISCs have varying

    >  instruction times. But in general it makes things messy.

    >

    >  Whatever you do, you do NOT want any single instruction to NOT take

    >  constant time.

     Great point. Thank you for mentioning it.

    Thanks a lot for sharing your ideas!

    - Christopher

## Rodney D Price — 2007-11-02 20:11:58

    Chris,

    This suggestion may be somewhat orthogonal to your memory management

    issue (or not), but it's something I've been interested in

    for some time:  Could you build a machine with capability-based

    addressing?  That is, instead of building an MMU (not that you said

    you were going to) could you protect a process' memory from other

    processes with capabilities?

    In this context, a "capability" is like a conventional pointer into

    memory, but it also includes other information, such as the size of

    the memory area it points to, some permission bits (read/write/

    execute user code/execute system code), and an extra bit to indicate

    that this is a capability.

    See Levy, "Capability-based Computing Systems" for a somewhat dated

    review, at http://www.cs.washington.edu/homes/levy/capabook/

    So why do I suggest this for your Cat machine?  Cat has a real static

    type system (not just "types").  There's a very interesting

    interaction between capabilities and type systems:  if your machine

    had capabilities, the Cat type system might be able to handle memory

    management for you.  The suggestion below for LinearLisp is somewhat

    in this vein, but doesn't go as far as some current research in

    handling the problem.  For a start, have a look at Greg Morrisett,

    "Linear regions are all you need", and "Monadic regions", both

    available at his web page, http://www.eecs.harvard.edu/~greg/papers/

    index.html.  Another site of interest is the Typed Assembly Language

    site at http://www.cs.cornell.edu/talc/

    This way, you "pay" for memory management, and you get MMU-like

    process separation for free.  Or vice versa.

    -Rod

     On Nov 2, 2007, at 12:32 PM, Christopher Diggins wrote:

    > On 11/2/07, William Tanksley, Jr <wtanksleyjr@...> wrote:

    > > Christopher Diggins <cdiggins@...> wrote:

    > > > So I've been thinking about concatenative hardware lately. Here

    > is a

    > > > single-stack machine instruction set:

    > >

    > > Interesting. I've played a lot with stack hardware (designed a

    > > complete processor for a HW class), so your twist on the subject is

    > > very thought-provoking.

    > >

    > > > 0: JZ (val fxn -> ) // jump to fxn if value is below zero

    > > > 1: CALL (fxn) // push return address and jump to fxn

    > > > 2: LTEQ (val val -> bool) // compare values

    > > > 3: AND (val val -> val) // perform bitwise and

    > > > 4: XOR (val val -> val) // perform XOR operation

    > > > 5: SHL (val val -> val) // shift-left

    > > > 6: DUP (a -> a a) // duplicate top-value

    > > > 7: QTE (val -> fxn) // create a thunk

    > > > 8: COMP (fxn fxn -> fxn) // compose two functions (append their

    > contents)

    > > > 9: POP (a -> ) // pop value from stack

    > > > 10: DIP (a fxn -> a) // applies function to below top of stack

    > > > 11: SWP (a b -> b a) // swap top two items

    > >

    > > Very high-level... You'll need more detailed semantics for that to

    > > work at all (memory management will be a BEAR for you).

    >

    > Yes, this is where I am stuck.

    >

    > > Of course,

    > > you're entirely missing ADD and such. Oh, and I see you've got a

    > > comparison instruction, but no conditional call or branch. I assume

    > > you intended to imply those, of course.

    >

    > Whoops some mistakes. Especially the missing ADD.

    >

    > > You might want to look at Henry Baker's papers on a similar topic.

    > > Check out his paper on O(1) instructions which could implement a

    > VERY

    > > flexible VM that doesn't require GC;

    > > http://home.pipeline.com/~hbaker1/LinearLisp.html. "Hash cons"ing is

    > > very important, and might even fit into hardware.

    >

    > Great, I'll look into it.

    >

    > > Once you get memory management a bit more simple, you need to

    > > determine the implications of your instruction encoding. You don't

    > > explain your encoding, which leads me to suspect that each

    > instruction

    > > is encoded as a byte.

    >

    > 4 bits is my goal.

    >

    > > Needless to say, bit packing is a LOT nicer,

    > > even when you're doing a VM.

    > >

    > > The worst implication of your instruction encoding -- and this isn't

    > > something you've made explicit -- is that your instructions _appear_

    > > to be stored in CONS cells.

    >

    > I'm looking for alternatives, I don't like the idea of CONS cells. I'm

    > thinking of a linked list of mini-stacks, but this is just a vague

    > notion at this point.

    >

    > > This implies that there's one per cell.

    > > That's MAJORLY inefficient in every way, needless to say.

    >

    > Yep.

    >

    > > It's obvious

    > > that one optimization would be to pack multiple instructions into a

    > > single CONS cell,

    >

    > I'm thinking of 32 bit stack, which can contain 8 4 bit instructions.

    >

    > > but that could well give you worse problems, as then

    > > you have to decide how to handle CALLs. Perhaps the answer should be

    > > that a CALL is always the CDR of a CONS pair...

    >

    > Interesting idea.

    >

    > > > So essentially we can use the data stack also as a return address

    > > > stack. This is a zero operand instruction set, so it is very

    > compact

    > > > and can be implemented efficiently, but it takes a lot of

    > instructions

    > > > to do simple things (e.g. accessing items deep in the stack).

    > >

    > > "Doctor, it hurts when I do this." ;-)

    > >

    > > It's possible that you shouldn't consider "accessing items deep

    > in the

    > > stack" to be a "simple thing".

    > >

    > > > The "dip" instruction is so important I'm tempted to include

    > variants:

    > > > 12: DIP2 : (a b fxn -> a b)

    > > > 13: DIP3 : (a b c fxn -> a b c)

    > > > 14: DIP4 : (a b c d fxn -> a b c d)

    > >

    > > The DIP instruction is so complex, high-overhead, and dependent on

    > > precise details of user needs that I'm tempted to not include it.

    >

    > Good point. Besides I need those slots for ADD, a PUSH, and

    > possibly a NOOP.

    >

    > > > 15: open for suggestions

    > >

    > > YES! 4 bits! (Assuming you don't want math or conditionals...)

    >

    > JZ was the conditional (which I am thinking of combining with LTEQ, to

    > make JLE (Jump if less than or equal) when do we use LTEQ outside of

    > a branch anyway, if we need a true LTEQ we can say: JLE

    >

    > > > Of course "DIP" can be implemented as "SWP QTE COMP CALL", but I'm

    > > > concerned about performance. The "DIP" is one of the most frequent

    > > > instructions in my code.

    > >

    > > It seems to me that DIP is inherently complex -- you don't want to

    > > stretch your clock cycle to accommodate a single instruction.

    >

    > That is a good point.

    >

    > > Much

    > > better to let users implement DIP the way they need it.

    >

    > Its just that when I generate Cat from C code algorithmically it

    > generates a ton of DIPs.

    >

    > > Although I just noticed you use CONCAT instead of CONS. Hmm. That's

    > > another inherently complex instruction (it takes linear time).

    >

    > Not neccessarily, if we use lists with tail pointers. However, that

    > is ugly.

    >

    > > > Anyway, hopefully this makes sense to my fellow concatenators. I'd

    > > > love to hear thoughts and suggestions. I'm pretty naive when it

    > comes

    > > > to hardware.

    > >

    > > Think about this carefully... Generally speaking, the minimal

    > > requirement for hardware is that all instructions should be O(1).

    >

    > Good idea.

    >

    > > I've

    > > seen that requirement skipped... Chuck Moore's processors use cycle

    > > times so fast that there's isn't time for the carry flag to

    > propagate

    > > on addition, so when you do addition you have to allow the stack to

    > > settle in the ALU before you read the result of the addition (it's

    > > simpler in practice than it sounds). Most CISCs have varying

    > > instruction times. But in general it makes things messy.

    > >

    > > Whatever you do, you do NOT want any single instruction to NOT take

    > > constant time.

    >

    > Great point. Thank you for mentioning it.

    >

    > Thanks a lot for sharing your ideas!

    >

    > - Christopher

    >

    >

    [Non-text portions of this message have been removed]

## William Tanksley, Jr — 2007-11-02 20:31:22

    William Tanksley, Jr <wtanksleyjr@...> wrote:

     > You might want to look at Henry Baker's papers on a similar topic.

    > Check out his paper on O(1) instructions which could implement a VERY

    > flexible VM that doesn't require GC;

    > http://home.pipeline.com/~hbaker1/LinearLisp.html. "Hash cons"ing is

    > very important, and might even fit into hardware.

     While re-reading this, I was thinking how this might not only fit into

    hardware, it might even allow multiple parallel processors on the same

    chip talking to external memory. Whoops, looks like Baker beat me to

    it! See his section titled "Implications for Real Multiprocessors".

    If you also want to handle arrays in such an architecture, you might

    have to explore his suggestion in

    http://home.pipeline.com/~hbaker1/ShallowArrays.html. That might have

    the nice side effect of giving you machine-addressable code (the most

    common architecture right now).

    This looks like a really interesting processor arch.

    -Billy

## William Tanksley, Jr — 2007-11-02 20:51:57

    William Tanksley, Jr <wtanksleyjr@...> wrote:

     > If you also want to handle arrays in such an architecture, you might

    > have to explore his suggestion in

    > http://home.pipeline.com/~hbaker1/ShallowArrays.html. That might have

    > the nice side effect of giving you machine-addressable code (the most

    > common architecture right now).

     Ugh. I read that, and have NO idea what he's trying to say. If anyone

    else does, please speak up...

    -Billy

## Stevan Apter — 2007-11-02 22:16:39

    who IS henry baker anyway?

    [Non-text portions of this message have been removed]

## John Cowan — 2007-11-02 21:38:42

    William Tanksley, Jr scripsit:

     > Ugh. I read that, and have NO idea what he's trying to say. If anyone

    > else does, please speak up...

     I understand it, but it wasn't easy....

    Basically the idea is that you represent each state of an array by a

    linked list holding the history of changes made to that state.

    There can be several different lines of change which may share

    things; if I give you an array with 5 changes, you can add 3 more

    without interfering with the changes I make.

    The algorithm is a clever way to implement this without giving up

    the idea of a having a linear array.  The underlying linear array

    is used as a cache for one particular state: when we want to work

    with a different state, we permute the data structure so that the

    new state is now what appears in the cache.

    --

    Mark Twain on Cecil Rhodes:                    John Cowan

    I admire him, I freely admit it,               http://www.ccil.org/~cowan

    and when his time comes I shall                cowan@...

    buy a piece of the rope for a keepsake.

## John Cowan — 2007-11-02 21:43:29

    Stevan Apter scripsit:

     > who IS henry baker anyway?

     He's probably best known for the Baker garbage collector, which divides

    the available space into Tospace and Fromspace.  Each gc run lazily

    copies some non-garbage from Fromspace to Tospace until nothing is left

    in Fromspace: then the two semi-spaces swap identities.  It was the

    first stop and copy (as opposed to mark and sweep or mark-sweep-compact)

    garbage collector.

    One of his papers also inspired Chicken Scheme.

    --

    John Cowan    cowan@...    http://ccil.org/~cowan

    Half the lies they tell about me are true.

            -- Tallulah Bankhead, American actress

## Don Groves — 2007-11-02 21:53:18

    Sorry for not changing the subject line earlier...

     On Nov 2, 2007, at 19:26 , William Tanksley, Jr wrote:

    > Don Groves <dgroves@...> wrote:

    >> A generator is a persistent function. When activated, it pushes a

    >> copy of

    >> itself on the stack. The copy performs the generative function and

    >> remains

    >> on the stack until specifically dropped. Each time it comes to the

    >> top of the stack it generates a value according to its definition.

    >

    > "Comes to the top of the stack" is unclear. It would make more sense

    > to say that every time GENERATE is called on it, it produces the next

    > value. (You could also overload UNCONS to work that way... but that

    > seems dangerous.)

    Good point! I could just use the I or DIP combinator to execute a

    generator.

    This would make it more generally useful.

    >> Example: [1 2 ...] defgen Z+

    >> Z+ is now a generator a copy of which will generate positive

    >> integers as

    >> long as it remains active (until dropped from the stack).

    >

    > As long as you're defining new syntax, why not have "[x ...]" be

    > defined in the language as a "generator quotation", so you don't need

    > 'defgen'? Just use 'const' or whatever.

    That was my original design and I'll return to that, thanks!

    >> stack:

    >> => Z+

    >> yields -

    >> stack:[2 3 ...] 1

    >> =>

    >

    >> The next time it comes to the top of the stack, it will generate a 2,

    >> thusly -

    >> stack:[3 4 ...] 2

    >> =>

    >

    > Specifically, does this mean that:

    >

    > => Z+ SWAP SWAP

    > yields -

    > stack:1 2 [4 5 ...] 3

    >

    > ?

    >

    > If so, is there any way to drop a generator from the stack?

    I was thinking of having a dropY instruction, but then that couldn't be

    defined as swap drop could it?  This problem is also solved by using

    a combinator to execute a generator.

    >> This behaviour continues until the user/program decides to stop it.

    >

    > How?

    >

    >> Thus,

    >> the ellipsis generator, ..., can mimic an infinite list. Z+ is

    >> included in the

    >> ACL standard library.

    >

    > Obviously the ellipsis generator is either very clever with lots of

    > special cases, or it can only handle additive sequences.

    That depends on the definition. [0 -1 ...] would generate negative

    sequences, for example. I could also include an operator in the

    definition

    and make it more group-like. Nothing in ACL is cast in concrete yet

    which

    is one reason I appreciate your (and other's) comments and suggestions

    so much!

    >> ... and so on until 99 is produced, at which point the generator copy

    >> self-destructs.

    >

    > Without being dropped? How will client code know that their stack's

    > been changed?

    One thing I forgot to mention is that a finite generator acts like an

    empty

    list after generating its last value so a null value will be

    generated when

    the client code asks for the next value. I suppose I could require

    the client

    code to drop the generator at that point...

    --

    Don

    >

    >> Don Groves

    >

    > -Billy

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## William Tanksley, Jr — 2007-11-02 21:59:32

    Stevan Apter <sa@...> wrote:

     > who IS henry baker anyway?

     He should be especially notable to THIS group for having written "The

    Forth Shall Be First", a paper exploring how Forth (ahem, a

    concatenative language) implemented a cutting-edge theoretical concept

    long before that concept became known.

    An interesting read, and applicable to almost all concatenative

    languages (more so to the functional ones).

    His home page is here: http://home.pipeline.com/~hbaker1/

    The "Forth Shall Be First" paper is here:

    http://home.pipeline.com/~hbaker1/ForthStack.html

    -Billy

## William Tanksley, Jr — 2007-11-03 00:05:44

    Christopher Diggins <cdiggins@...> wrote:

     > William Tanksley, Jr <wtanksleyjr@...> wrote:

    > >  Very high-level... You'll need more detailed semantics for that to

    > >  work at all (memory management will be a BEAR for you).

    > Yes, this is where I am stuck.

     I'm picturing a multiprocessor model based on Baker's model, with one

    dedicated memory processor (hooks up to external memory) and a bunch

    of general purpose processors, each with a decent amount (TBD) of

    internal memory.

    The memory processor will handle synchronizing all the internal

    memories with the external shared memory, and will also continuously

    compact external memory.

    (Of course, this can also be done in software as a VM, in which case

    the "memory processor" will simply be a compactor task.)

     > > Of course,

    > >  you're entirely missing ADD and such. Oh, and I see you've got a

    > >  comparison instruction, but no conditional call or branch. I assume

    > >  you intended to imply those, of course.

    > Whoops some mistakes. Especially the missing ADD.

     The "missing comparison" claim was my mistake -- I didn't notice JZ. My bad.

     > >  Once you get memory management a bit more simple, you need to

    > >  determine the implications of your instruction encoding. You don't

    > >  explain your encoding, which leads me to suspect that each instruction

    > >  is encoded as a byte.

    > 4 bits is my goal.

     Whoops, I did see that later; should have corrected my

    misapprehension. 4 bits is great.

    Another thing to consider is that control flow instructions are

    special and rarely used; if you're packing multiple instructions in a

    single memory word, it makes sense to define those instructions as

    valid only at the last instruction in the word, which leaves those

    opcodes open for other uses in the other instruction slots. If you do

    this, you can has room for all the arithmetical opcodes.

     > >  The worst implication of your instruction encoding -- and this isn't

    > >  something you've made explicit -- is that your instructions _appear_

    > >  to be stored in CONS cells.

    > I'm looking for alternatives, I don't like the idea of CONS cells. I'm

    > thinking of a linked list of mini-stacks, but this is just a vague

    > notion at this point.

     That's equivalent to what I was thinking of as a linked list of

    arrays, so we're on the same page.

     > > It's obvious

    > >  that one optimization would be to pack multiple instructions into a

    > >  single CONS cell,

    > I'm thinking of 32 bit stack, which can contain 8 4 bit instructions.

     Ah, I see. Yes, that's just fine.

     > > but that could well give you worse problems, as then

    > >  you have to decide how to handle CALLs. Perhaps the answer should be

    > >  that a CALL is always the CDR of a CONS pair...

    > Interesting idea.

     It would be like the RPC-4000

    (http://catb.org/jargon/html/story-of-mel.html, highly recommended

    programming literature) -- every instruction word would include its

    own implicit GOTO.

    I guess you'd bitpack a bit more and use the last instruction slot to

    choose between JUMP, BRANCH, and CALL behavior (so only 2 bits; I

    guess we'd invent a CALLBRANCH instruction to use all the bits, and

    we'd encode a few extra instructions in the 2 remaining bits, so every

    32-bit word would have 3 full instructions, 1 short instruction, and 1

    call instruction).

    Now, because the instruction stream isn't on the stack, it might be

    possible to load it from a linked list in shared memory (canonical

    form) into a array form in-processor, thus making it much more

    compact. I have no idea what would work better. (There will not be any

    issues with cache locality, so it may be better to simply store the

    on-chip form as a linked list -- in fact the first software model

    should do that.)

     > Good point. Besides I need those slots for ADD, a PUSH, and

    > possibly a NOOP.

     NOOP is very handy when dealing with slotted instructions... Sometimes

    you just don't have 4 instructions to fill a word with.

     > > Much

    > >  better to let users implement DIP the way they need it.

    > Its just that when I generate Cat from C code algorithmically it

    > generates a ton of DIPs.

     Sure, but this processor isn't Cat; a decent generator for it will

    generate different code than a decent one would for Cat.

    To be fair, if we can do DIP in vaguely similar time to the other

    instructions I've got no beef with it.

     > >  Although I just noticed you use CONCAT instead of CONS. Hmm. That's

    > >  another inherently complex instruction (it takes linear time).

    > Not neccessarily, if we use lists with tail pointers. However, that

    > is ugly.

     Oh, yes, you could tail-CONS the dipped value on, if that's what you

    meant. But tail pointers would be really, really nasty... I'm pretty

    sure they wouldn't work in general (EVERY node of a list would have to

    maintain a tail pointer, right?).

    There's got to be a cleaner solution...

    I definitely would prefer using CONS as the machine primitive; CONCAT

    is (as I mentioned) linear time, and that's just not good in hardware.

     > Thanks a lot for sharing your ideas!

     Hard to stop me, isn't it. ;-)

     > - Christopher

     -Billy

## Christopher Diggins — 2007-11-03 01:51:29

    On 11/2/07, Rodney D Price <rodprice@...> wrote:

     > Chris,

    >

    > This suggestion may be somewhat orthogonal to your memory management

    > issue (or not), but it's something I've been interested in

    > for some time: Could you build a machine with capability-based

    > addressing? That is, instead of building an MMU (not that you said

    > you were going to) could you protect a process' memory from other

    > processes with capabilities?

     Yes I could do that, but I am currently strudying minimalist system

    architectures.

     > So why do I suggest this for your Cat machine? Cat has a real static

    > type system (not just "types"). There's a very interesting

    > interaction between capabilities and type systems: if your machine

    > had capabilities, the Cat type system might be able to handle memory

    > management for you.

     So the gain be would be increased safety, correct? Capabilities as I

    understand them are essentially dynamically managed permissions. I

    haven't yet been swooned by capabilities, but perhaps I just need to

    do more reading on them.

    Would there be commercial interest in this line of exploration? Right

    about now some kind of financial sponsorship would be very motivating.

    ;-)

    - Christopher

## William Tanksley, Jr — 2007-11-03 03:45:06

    Christopher Diggins <cdiggins@...> wrote:

     >>for some time: Could you build a machine with

    >>capability-based addressing? That is, instead

    >>of building an MMU (not that you said you were

    >>going to) could you protect a process' memory

    >>from other processes with capabilities?

    >Yes I could do that, but I am currently studying

    >minimalist system architectures.

     Then you'll certainly want to study Capability based security. A

    capability is a pointer without which it is impossible to access a

    given object.

    Very powerful, very simple. Shapiro (KeyKOS, EROS, Coyotos) has

    written a lot about it online. The paper

    http://citeseer.ist.psu.edu/689826.html was useful to me.

    The Baker model I pointed to would make Capabilities very simple to

    build; it would be entirely impossible (not merely improbable) to

    access a data structure which isn't linked to from something already

    given to you.

     > Would there be commercial interest in this line

    > of exploration? Right

    > about now some kind of financial sponsorship

    > would be very motivating. ;-)

     Grin.

    I don't know, but I doubt it.

    Unless maybe you can convince Chuck Moore that your work would go

    perfectly on his SeaForth24 chip. He's got plenty of money now that

    Intel and AMD are paying him royalties on his patents.

     > - Christopher

     -Billy

## Daniel Ehrenberg — 2007-11-03 04:39:12

    On 11/2/07, Stevan Apter <sa@...> wrote:

     >

    > who IS henry baker anyway?

    >

     Kind of funny you asked. I've heard his name referenced so many times,

    but never really understood who he is, except some kind of programming

    demigod who you can cite as a source of absolute truth. Wikipedia

    (http://en.wikipedia.org/wiki/Henry_Baker_(computer_scientist)) says

    "a computer scientist who has made contributions in garbage

    collection, functional programming languages, and linear logic. He was

    also one of the founders of Symbolics." but not much else. His website

    (http://home.pipeline.com/~hbaker1/), in dire need of a CSS file,

    shows that he invented a whole bunch of stuff. I guess he's most

    notable for Cheney on the MTA (a model for a CPS translation of Lisp

    to C, the inspiration for Chicken) and his Linear Lisp, a lisp which

    compiles to a forth and needs no garbage collection, just a whole

    bunch of copying. He also opposed relational databases, and came up

    with a whole bunch of algorithms.

    But really, to me, he's somewhat of a mystery, still. Where did he

    come from? What was his job?

    Daniel Ehrenberg

## Christopher Diggins — 2007-11-04 18:23:51

    On 11/2/07, William Tanksley, Jr <wtanksleyjr@...> wrote:

     > Christopher Diggins <cdiggins@...> wrote:

    > >>for some time: Could you build a machine with

    > >>capability-based addressing? That is, instead

    > >>of building an MMU (not that you said you were

    > >>going to) could you protect a process' memory

    > >>from other processes with capabilities?

    >

    > >Yes I could do that, but I am currently studying

    > >minimalist system architectures.

    >

    > Then you'll certainly want to study Capability based security. A

    > capability is a pointer without which it is impossible to access a

    > given object.

     For non-mission critical embedded systems, is this really a huge gain?

    I can imagine though it being useful for embedded devices on cars and

    rockets, and other such things.

    How should an architecture react in the case of catastrophe (i.e.

    capability violation)? Some kind of interrupt mechanism I imagine?

     > Very powerful, very simple. Shapiro (KeyKOS, EROS, Coyotos) has

    > written a lot about it online. The paper

    > http://citeseer.ist.psu.edu/689826.html was useful to me.

     I'll look at it soon.

     > The Baker model I pointed to would make Capabilities very simple to

    > build; it would be entirely impossible (not merely improbable) to

    > access a data structure which isn't linked to from something already

    > given to you.

     The kind of architecture I am considering at this time is so tiny that

    the overheard of capability pointers would be too big. However, as

    soon as I move into larger architectures I can see advantages.

     > > Would there be commercial interest in this line

    > > of exploration? Right

    > > about now some kind of financial sponsorship

    > > would be very motivating. ;-)

    >

    > Grin.

    >

    > I don't know, but I doubt it.

    >

    > Unless maybe you can convince Chuck Moore that your work would go

    > perfectly on his SeaForth24 chip. He's got plenty of money now that

    > Intel and AMD are paying him royalties on his patents.

     You know, that isn't a half-bad idea!

    It would be interesting to implement a Cat machine using one of those

    SeaForth 24 chips.

    - Christopher

## Christopher Diggins — 2007-11-04 18:25:53

    > > QTE and COMP allows you to treat function like stacks, by adding data

    > > to them, which you can accesss later by calling CALL. So

    > > computationally it is a multi-stack machine.

    >

    > Could you describe their behaviour a bit more?

     I'll be providing some C code shortly, but here is the brief description.

    QTE creates a thunk (a nullary function) from a value. The value is

    popped from the stack and replaced with a function that always returns

    the value.

    COMP composes two function pointers to create a new function that

    executes the first function then the second function.

    - Christopher

## Don Groves — 2007-11-04 21:30:32

    On Nov 4, 2007, at 19:25 , Christopher Diggins wrote:

     >>> QTE and COMP allows you to treat function like stacks, by adding

    >>> data

    >>> to them, which you can accesss later by calling CALL. So

    >>> computationally it is a multi-stack machine.

    >>

    >> Could you describe their behaviour a bit more?

    >

    > I'll be providing some C code shortly, but here is the brief

    > description.

    >

    > QTE creates a thunk (a nullary function) from a value. The value is

    > popped from the stack and replaced with a function that always returns

    > the value.

     Enlightenment time...

    I understand the form of this construct but not its essential nature.

    How does it differ from, and in what way is it more useful than, a

    constant?

    -- Don

     > COMP composes two function pointers to create a new function that

    > executes the first function then the second function.

    >

    > - Christopher

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## Christopher Diggins — 2007-11-04 23:13:15

    > > QTE creates a thunk (a nullary function) from a value. The value is

    > > popped from the stack and replaced with a function that always returns

    > > the value.

    >

    > Enlightenment time...

    >

    > I understand the form of this construct but not its essential nature.

    > How does it differ from, and in what way is it more useful than, a

    > constant?

     It allows you to create functions dynamically out of thin air. This is

    useful when performing computations with higher-order functions.

    - Christopher

## Don Groves — 2007-11-05 00:17:22

    On Nov 4, 2007, at 19:13 , Christopher Diggins wrote:

     >>> QTE creates a thunk (a nullary function) from a value. The value is

    >>> popped from the stack and replaced with a function that always

    >>> returns

    >>> the value.

    >>

    >> Enlightenment time...

    >>

    >> I understand the form of this construct but not its essential nature.

    >> How does it differ from, and in what way is it more useful than, a

    >> constant?

    >

    > It allows you to create functions dynamically out of thin air. This is

    > useful when performing computations with higher-order functions.

     Ah, since higher-order functions only operate on functions... Thanks!

    --

    Don

     >

    > - Christopher

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## William Tanksley, Jr — 2007-11-05 17:22:16

    Christopher Diggins <cdiggins@...> wrote:

     > William Tanksley, Jr <wtanksleyjr@...> wrote:

    > > Then you'll certainly want to study Capability

    > > based security.

    > For non-mission critical embedded systems, is

    > this really a huge gain?

     Sorry, I had a different understanding of 'minimalist' than you do.

    Yes, there's no need to implement capabilities when you don't need any

    process security at all.

     > How should an architecture react in the case of catastrophe (i.e.

    > capability violation)? Some kind of interrupt mechanism I imagine?

     The Baker system can't express a capability violation (it's simply not

    possible). For most other systems, a capability violation is the same

    as accessing a page of memory that doesn't exist -- page fault. It

    doesn't mean somebody's being bad; it simply means someone tried to

    access memory using something that isn't a pointer.

     > It would be interesting to implement a Cat machine using one of those

    > SeaForth 24 chips.

     I agree.

     > - Christopher

     -Billy