# Infix syntax

## Slava Pestov — 2004-10-19 05:24:54

    Hi everybody,

    Here is some code for parsing infix expressions like [ 2 * [ 3 + 4 ] ]

    and transforming them into quotations of postfix code. Its not fully

    tested, and it doesn't have any kind of error handling. Extending it to

    support operator precedence is left as an exercise to the reader :-)

    Slava

    ------------>8---------------

    USE: combinators

    USE: lists

    USE: math

    USE: namespaces

    USE: stack

    USE: test

    USE: vectors

    USE: words

    SYMBOL: exprs

    DEFER: infix

    : >e exprs get vector-push ;

    : e> exprs get vector-pop ;

    : e@ exprs get dup vector-empty? [ drop f ] [ vector-peek ] ifte ;

    : e, ( obj -- ) dup cons? [ [ e, ] each ] [ , ] ifte ;

    : end ( -- ) exprs get [ e, ] vector-each ;

    : >postfix ( op -- ) e@ word? [ e> e> -rot 3list ] when >e ;

    : token ( obj -- ) dup cons? [ infix ] when >postfix ;

    : (infix) ( list -- ) [ unswons token (infix) ] when* ;

    : infix ( list -- quot )

         #! Convert an infix expression (passed in as a list) to

         #! postfix.

         [, 10 <vector> exprs set (infix) end ,] ;

    [ [ ] ] [ [ ] infix ] unit-test

    [ [ 1 ] ] [ [ 1 ] infix ] unit-test

    [ [ 2 3 + ] ] [ [ 2 + 3 ] infix ] unit-test

    [ [ 2 3 * 4 + ] ] [ [ 2 * 3 + 4 ] infix ] unit-test

    [ [ 2 3 * 4 + 5 + ] ] [ [ 2 * 3 + 4 + 5 ] infix ] unit-test

    [ [ 2 3 * 4 + ] ] [ [ [ 2 * 3 ] + 4 ] infix ] unit-test

    [ [ 2 3 4 + * ] ] [ [ 2 * [ 3 + 4 ] ] infix ] unit-test

    [ [ 2 3 2 / 4 + * ] ] [ [ 2 * [ [ 3 / 2 ] + 4 ] ] infix ] unit-test

## Daniel Ehrenberg — 2004-10-19 16:37:37

    That's really interesting. It reminds me of something

    I saw in the Joy standard library:

    http://www.latrobe.edu.au/philosophy/phimvt/joy/symlib.joy

    (the corresponding procedure is Inf2Pol) but the

    contrast between the two implementations is

    remarkable. It seems like Joy and Factor, although

    both in the same general paradigm, encourage vastly

    different styles of programming. I find this a little

    unexpected; when I first read about concatenative

    languages I couldn't see at all how they could deviate

    from Joy much, but this is really different.

    Daniel Ehrenberg

     > Hi everybody,

    >

    > Here is some code for parsing infix expressions like

    > [ 2 * [ 3 + 4 ] ]

    > and transforming them into quotations of postfix

    > code. Its not fully

    > tested, and it doesn't have any kind of error

    > handling. Extending it to

    > support operator precedence is left as an exercise

    > to the reader :-)

    >

    > Slava

    >

    > ------------>8---------------

    >

    > USE: combinators

    > USE: lists

    > USE: math

    > USE: namespaces

    > USE: stack

    > USE: test

    > USE: vectors

    > USE: words

    >

    > SYMBOL: exprs

    > DEFER: infix

    > : >e exprs get vector-push ;

    > : e> exprs get vector-pop ;

    > : e@ exprs get dup vector-empty? [ drop f ] [

    > vector-peek ] ifte ;

    > : e, ( obj -- ) dup cons? [ [ e, ] each ] [ , ] ifte

    > ;

    > : end ( -- ) exprs get [ e, ] vector-each ;

    > : >postfix ( op -- ) e@ word? [ e> e> -rot 3list ]

    > when >e ;

    > : token ( obj -- ) dup cons? [ infix ] when >postfix

    > ;

    > : (infix) ( list -- ) [ unswons token (infix) ]

    > when* ;

    >

    > : infix ( list -- quot )

    >      #! Convert an infix expression (passed in as a

    > list) to

    >      #! postfix.

    >      [, 10 <vector> exprs set (infix) end ,] ;

    >

    > [ [ ] ] [ [ ] infix ] unit-test

    > [ [ 1 ] ] [ [ 1 ] infix ] unit-test

    > [ [ 2 3 + ] ] [ [ 2 + 3 ] infix ] unit-test

    > [ [ 2 3 * 4 + ] ] [ [ 2 * 3 + 4 ] infix ] unit-test

    > [ [ 2 3 * 4 + 5 + ] ] [ [ 2 * 3 + 4 + 5 ] infix ]

    > unit-test

    > [ [ 2 3 * 4 + ] ] [ [ [ 2 * 3 ] + 4 ] infix ]

    > unit-test

    > [ [ 2 3 4 + * ] ] [ [ 2 * [ 3 + 4 ] ] infix ]

    > unit-test

    > [ [ 2 3 2 / 4 + * ] ] [ [ 2 * [ [ 3 / 2 ] + 4 ] ]

    > infix ] unit-test

    >

     __________________________________

    Do you Yahoo!?

    Read only the mail you want - Yahoo! Mail SpamGuard.

    http://promotions.yahoo.com/new_mail

## Eizneckam — 2004-10-19 21:33:39

    On Tue, 19 Oct 2004 01:24:54 -0400, Slava Pestov <slava@...> wrote:

     >  Hi everybody,

    >

    >  Here is some code for parsing infix expressions like [ 2 * [ 3 + 4 ] ]

    >  and transforming them into quotations of postfix code. Its not fully

    >  tested, and it doesn't have any kind of error handling. Extending it to

    >  support operator precedence is left as an exercise to the reader :-)

    >

    >  Slava

     Here's some equivalent code in Exuberance (0.3), also untested and

    without precedence:

    "util.ex" include

    "unit-test.ex" include

    `term [dup typeof {"list": (infix) | $_ : unit }];

    `token [dup typeof {

          "symbol": [unswons term swapd swoncat] dip swons swap

        | $_      : swapd term swoncat swap

    }];

    `(infix) [[] swap [null] [pop] [unswons token] tailrec];

    `infix [(infix) reverse];

    [

      ["infix-1" [[] infix] [[]]]

      ["infix-2" [[1] infix] [[1]]]

      ["infix-3" [[2 + 3] infix] [[2 3 +]]]

      ["infix-4" [[2 * 3 + 4] infix] [[2 3 * 4 +]]]

      ["infix-5" [[2 * 3 + 4 + 5] infix] [[2 3 * 4 + 5 +]]]

      ["infix-6" [[[2 * 3] + 4] infix] [[2 3 * 4 +]]]

      ["infix-7" [[2 * [3 + 4]] infix] [[2 3 4 + *]]]

      ["infix-8" [[ 2 * [[3 / 2] + 4]] infix] [[2 3 2 / 4 + *]]]

    ] unit-test

    --eiz

## Slava Pestov — 2004-10-20 00:16:18

    Hi,

    It is more of a difference in programmer's style than language style.

    The Joy code could be ported to Factor with little effort.

    I wrote my infix parser in an imperitive fashion; it relies on an

    expression stack that is mutated with the words >e/e>. If I wrote it in

    a functional manner, it would probably look a lot more like the Joy code.

    Daniel Ehrenberg wrote:

     > That's really interesting. It reminds me of something

    > I saw in the Joy standard library:

    > http://www.latrobe.edu.au/philosophy/phimvt/joy/symlib.joy

    > (the corresponding procedure is Inf2Pol) but the

    > contrast between the two implementations is

    > remarkable. It seems like Joy and Factor, although

    > both in the same general paradigm, encourage vastly

    > different styles of programming. I find this a little

    > unexpected; when I first read about concatenative

    > languages I couldn't see at all how they could deviate

    > from Joy much, but this is really different.

## stevan apter — 2004-10-20 11:18:30

    some not-quite-equivalent code to convert k infix to postfix.

    in k infix, all symbols are ambivalent:  '+' denotes addition

    in the context x+y, but transposition in the context +x.  so

    x++y means "x plus the flip of y".  in general, k expressions

    are read left-to-right:

        2 + - 3 * 4 % % 12

    reads

        2 plus the negate of 3 times 4 divided by the reciprocal of 12

    i.e.

        2 + (- (3 * ( 4 % (% 12))))

    there is no precedence among operators.

    in XY, monads like reciprocal and negate are denoted by suffixing

    ':' to the function-symbol:

        2 - 3

        3 -:

    // infix k -> postfix

    ; infix         {{ [x] [x] [infix.] infra }} ;

    ; infix.        {{ [x] x #: 2 < x [x terms] if }} ;

    ; terms         {{ [x] x monad? [x monad] [x dyad] if }} ;

    ; monad?        {{ [[a A]] \a 4:: 4 = }} ;

    ; dyad          {{ [[x f Y]] x infix. Y infix. \f }} ;

    ; monad         {{ [[f X]] X infix. \f $: ': , .g }} ;

    notice how the templates in the last three patterns busts up the

    expression into the right parts.  for example, 'dyad', called on

        2 + 3 * 4

    will map 2 to x, + to f, and [3 * 4] to Y (the terminal capital

    indicating the rest of the list.)

      [2 + - 3 * 4 % % 12] infix

    [2 3 4 12 %: % * -: +]

      i

    -142.0

      :k

      2 + - 3 * 4 % % 12

    -142.0

     ----- Original Message -----

    From: "Eizneckam" <eizneckam@...>

    To: <concatenative@yahoogroups.com>

    Sent: Tuesday, October 19, 2004 5:33 PM

    Subject: Re: [stack] Infix syntax

    >

    > On Tue, 19 Oct 2004 01:24:54 -0400, Slava Pestov <slava@...> wrote:

    > >  Hi everybody,

    > >

    > >  Here is some code for parsing infix expressions like [ 2 * [ 3 + 4 ] ]

    > >  and transforming them into quotations of postfix code. Its not fully

    > >  tested, and it doesn't have any kind of error handling. Extending it to

    > >  support operator precedence is left as an exercise to the reader :-)

    > >

    > >  Slava

    > Here's some equivalent code in Exuberance (0.3), also untested and

    > without precedence:

    >

    > "util.ex" include

    > "unit-test.ex" include

    >

    > `term [dup typeof {"list": (infix) | $_ : unit }];

    > `token [dup typeof {

    >       "symbol": [unswons term swapd swoncat] dip swons swap

    >     | $_      : swapd term swoncat swap

    > }];

    > `(infix) [[] swap [null] [pop] [unswons token] tailrec];

    > `infix [(infix) reverse];

    >

    > [

    >   ["infix-1" [[] infix] [[]]]

    >   ["infix-2" [[1] infix] [[1]]]

    >   ["infix-3" [[2 + 3] infix] [[2 3 +]]]

    >   ["infix-4" [[2 * 3 + 4] infix] [[2 3 * 4 +]]]

    >   ["infix-5" [[2 * 3 + 4 + 5] infix] [[2 3 * 4 + 5 +]]]

    >   ["infix-6" [[[2 * 3] + 4] infix] [[2 3 * 4 +]]]

    >   ["infix-7" [[2 * [3 + 4]] infix] [[2 3 4 + *]]]

    >   ["infix-8" [[ 2 * [[3 / 2] + 4]] infix] [[2 3 2 / 4 + *]]]

    > ] unit-test

    >

    > --eiz

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

    >

## sa@dfa.com — 2004-10-20 15:21:49

    a more conventional implementation:

    ; infix         enlist [infix.] infra ;

    ; infix.        [count 2 <] [first] [terms] ifte ;

    ; terms         [monad?] [monad] [dyad] ifte ;

    ; monad?        first sym? ;

    ; dyad          {{ [[x f Y]] x infix. Y infix. \f }} ;

    ; monad         {{ [[f X]] X infix. \f string ': , .g }} ;

    'enlist' turns anything x into [x]

    'count' gives the length of a list (or 1 for an atom)

    'first' gives the first element of a list (identity for atoms)

    'sym?' gives 1 for a symbol, 0 otherwise

    'string' turns anything into a string

    ',' is concat (e.g. "abc" ': , -> "abc:"

    \x puts x on the stack (e.g. \+ puts + on the stack)

    btw, the fact that XY has access to the queue as well as the

    stack means that we can wrap 'infix' in a little interpreter:

    grab the queue, parse it, replace the queue with the result,

    let XY evaluate the new queue:

    ; Infix         {{ [] _y infix -> }} ;

      Infix 2 + - 3 * 4 % % 12

    -142.0

    eiz:  could you talk a bit about your implementation of pattern-

    matching in exuberance

    "stevan apter" <sa@...> wrote on 10/20/2004 07:18:30 AM:

     >

    > some not-quite-equivalent code to convert k infix to postfix.

    >

    > in k infix, all symbols are ambivalent:  '+' denotes addition

    > in the context x+y, but transposition in the context +x.  so

    > x++y means "x plus the flip of y".  in general, k expressions

    > are read left-to-right:

    >

    >     2 + - 3 * 4 % % 12

    >

    > reads

    >

    >     2 plus the negate of 3 times 4 divided by the reciprocal of 12

    >

    > i.e.

    >

    >     2 + (- (3 * ( 4 % (% 12))))

    >

    > there is no precedence among operators.

    >

    > in XY, monads like reciprocal and negate are denoted by suffixing

    > ':' to the function-symbol:

    >

    >     2 - 3

     oops - that should be:

          2 3 -

     >     3 -:

    >

    > // infix k -> postfix

    >

    > ; infix         {{ [x] [x] [infix.] infra }} ;

    > ; infix.        {{ [x] x #: 2 < x [x terms] if }} ;

    > ; terms         {{ [x] x monad? [x monad] [x dyad] if }} ;

    > ; monad?        {{ [[a A]] \a 4:: 4 = }} ;

    > ; dyad          {{ [[x f Y]] x infix. Y infix. \f }} ;

    > ; monad         {{ [[f X]] X infix. \f $: ': , .g }} ;

    >

    > notice how the templates in the last three patterns busts up the

    > expression into the right parts.  for example, 'dyad', called on

    >

    >     2 + 3 * 4

    >

    > will map 2 to x, + to f, and [3 * 4] to Y (the terminal capital

    > indicating the rest of the list.)

    >

    >   [2 + - 3 * 4 % % 12] infix

    > [2 3 4 12 %: % * -: +]

    >   i

    > -142.0

    >

    >   :k

    >   2 + - 3 * 4 % % 12

    > -142.0

    >

    > ----- Original Message -----

    > From: "Eizneckam" <eizneckam@...>

    > To: <concatenative@yahoogroups.com>

    > Sent: Tuesday, October 19, 2004 5:33 PM

    > Subject: Re: [stack] Infix syntax

    >

    >

    > >

    > > On Tue, 19 Oct 2004 01:24:54 -0400, Slava Pestov <slava@...>

     wrote:

     > > >  Hi everybody,

    > > >

    > > >  Here is some code for parsing infix expressions like [ 2 * [ 3 + 4 ]

     ]

     > > >  and transforming them into quotations of postfix code. Its not fully

    > > >  tested, and it doesn't have any kind of error handling. Extending it

     to

     > > >  support operator precedence is left as an exercise to the reader :-)

    > > >

    > > >  Slava

    > > Here's some equivalent code in Exuberance (0.3), also untested and

    > > without precedence:

    > >

    > > "util.ex" include

    > > "unit-test.ex" include

    > >

    > > `term [dup typeof {"list": (infix) | $_ : unit }];

    > > `token [dup typeof {

    > >       "symbol": [unswons term swapd swoncat] dip swons swap

    > >     | $_      : swapd term swoncat swap

    > > }];

    > > `(infix) [[] swap [null] [pop] [unswons token] tailrec];

    > > `infix [(infix) reverse];

    > >

    > > [

    > >   ["infix-1" [[] infix] [[]]]

    > >   ["infix-2" [[1] infix] [[1]]]

    > >   ["infix-3" [[2 + 3] infix] [[2 3 +]]]

    > >   ["infix-4" [[2 * 3 + 4] infix] [[2 3 * 4 +]]]

    > >   ["infix-5" [[2 * 3 + 4 + 5] infix] [[2 3 * 4 + 5 +]]]

    > >   ["infix-6" [[[2 * 3] + 4] infix] [[2 3 * 4 +]]]

    > >   ["infix-7" [[2 * [3 + 4]] infix] [[2 3 4 + *]]]

    > >   ["infix-8" [[ 2 * [[3 / 2] + 4]] infix] [[2 3 2 / 4 + *]]]

    > > ] unit-test

    > >

    > > --eiz

    > >

    > >

    > >

    > >

    > > Yahoo! Groups Links

    > >

    > >

    > >

    > >

    > >

    > >

    > >

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

    >