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

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