# Parsing in concatenative languages

## Ehrenberg Daniel — 2005-04-04 22:17:29

    Here's a problem to port to concatenative languages: parsing. I've

    seen many different solutions to this in various applicative

    languages: regular expressions, parser generators and first-class

    parsers with monads, arrows, or some other mechanism that most people

    don't understand. Each one has advantages and disadvantages, and none

    are concatenative (not that they need to be). There's also the

    undesireable path of telling users to write their own parsers, which

    Factor takes for its own parser, but this isn't a very good solution

    for everything; it can make many things unnecessarily complicated.

    What do people here think of this issue?

## Chris Double — 2005-04-04 22:40:46

    On Mon, 4 Apr 2005 18:17:29 -0400, "Ehrenberg Daniel"

    <microdan@...> said:

     >

    > What do people here think of this issue?

     I played with porting a parser combinator library to Factor a while

    back. Here's the documentation which shows example usage:

    http://factor.modalwebserver.co.nz/parser-combinators/parser-combinators.html

    It uses a lazy evaluation library described here:

    http://factor.modalwebserver.co.nz/parser-combinators/lazy.html

    It worked fairly well but the parsing code can be a bit difficult to

    read. Note that the current instance of the library has bugs and won't

    run with the current version of Factor due to bit rot. Fixing it up and

    completing it is my current project.

    Basically a 'parser' is a factor word that accepts an input string and

    returns a lazy list of successes. This lazy list is a list of cons cells

    where the head is the succesfully parsed item and the tail is the

    remaining string to be parsed. A parse can result in multiple

    successfull results so the result is a list of all possibilities. It is

    a lazy list so if you only need the first success the rest aren't

    computed.

    Parsing functions can be composed to build up more specific parsers. The

    composition functions return Factor quotations that when called perform

    the parsing functionality.

    Chris.

    --

    http://radio.weblogs.com/0102385

## William Tanksley, Jr — 2005-04-04 22:57:20

    Ehrenberg Daniel <microdan@...> wrote:

     > Here's a problem to port to concatenative languages: parsing. I've

    > seen many different solutions to this in various applicative

    > languages: regular expressions, parser generators and first-class

    > parsers with monads, arrows, or some other mechanism that most people

    > don't understand. Each one has advantages and disadvantages, and none

    > are concatenative (not that they need to be).

     Nor are they unconcatenative, nor applicative -- they're programs, not

    source code. When you run the program, they take text as input, and

    produce a parse tree (in some format) as an output.

     > There's also the

    > undesireable path of telling users to write their own parsers, which

    > Factor takes for its own parser, but this isn't a very good solution

    > for everything; it can make many things unnecessarily complicated.

     This isn't accurate; Factor uses a distributed parser, which means

    that the user can write his own parsing words that act not on external

    text input, but actually on the source code in the current program

    being compiled. Factor exposes some words that are useful for that

    purpose. Few other languages do that. Factor could no doubt provide

    more; but it already has more than most languages.

    Lisp provides a few _very_ simple parsing words which are used by

    reader macros, but they're so simple people rarely do more than make

    listlike structures with different delimiters. (To Lisp's credit,

    though, this is by design; the simple structure of the language makes

    a lot of other things very easy.)

    Rebol provides a powerful parser than acts like Factor's; in fact,

    I've talked to the author of Rebol, and he learned a lot from Forth

    (although the parser is his own work, much nicer than anything in

    Forth). http://www.rebol.com/docs/core23/rebolcore-15.html

    Several integrated parser generators have been written in Forth; the

    first link in a Google search

    http://www.google.com/search?q=forth+parser+generator turns up

    http://dec.bournemouth.ac.uk/forth/euro/ef99/ertl99.pdf, which

    explores and compares a group of parsers written in different

    languages.

    -Billy

## Ehrenberg Daniel — 2005-04-05 01:30:05

    > Nor are they unconcatenative, nor applicative -- they're programs, not

    > source code. When you run the program, they take text as input, and

    > produce a parse tree (in some format) as an output.

     Regular expressions are not concatenative, and monads and arrows are

    not concatenative, and parser generators are not concatenative.

     >

    > This isn't accurate; Factor uses a distributed parser, which means

    > that the user can write his own parsing words that act not on external

    > text input, but actually on the source code in the current program

    > being compiled. Factor exposes some words that are useful for that

    > purpose. Few other languages do that. Factor could no doubt provide

    > more; but it already has more than most languages.

     What I mean is that Factor doesn't use regexes, monads, or a parser

    generator for parsing; rather it uses its own mechanism to parse *its

    own source code*. For anything that the user wants to parse, like say

    XML, you need a new mechanism, and Factor currently doesn't provide

    anything.

     > Several integrated parser generators have been written in Forth; the

    > first link in a Google search

    > http://www.google.com/search?q=forth+parser+generator turns up

    > http://dec.bournemouth.ac.uk/forth/euro/ef99/ertl99.pdf, which

    > explores and compares a group of parsers written in different

    > languages.

     Thanks, I'll look at those.

    Daniel Ehrenberg

## William Tanksley, Jr — 2005-04-05 03:47:04

    Ehrenberg Daniel <microdan@...> wrote:

     > > Nor are they unconcatenative, nor applicative -- they're programs, not

    > > source code. When you run the program, they take text as input, and

    > > produce a parse tree (in some format) as an output.

    > Regular expressions are not concatenative,

     I didn't know until now, but I've actually been waiting 7 years (since

    my fundamentals of computation class) for someone to say that. :-)

    Regular expressions are concatenative in the sense that the language

    recognised by the concatenation of a pair of rexexps is the

    concatenanation of the languages recognised by the regexps. I don't

    know what you meant by saying that, but I can't think of a way in

    which regexps are not concatenative.

    Not that it matters -- a regexp parser in most languages takes input

    that's strictly distinct from the source code of the program. So the

    concatenativity of the implementation language is entirely irrelevant

    to the concatenativity of the parsed language.

     > and monads and arrows are

    > not concatenative,

     Funny. Read the paper on the arithmetic foundations of Joy -- every

    monad is concatenative by definition. I don't know too much about

    "arrows", though -- I left the TUNES group while they were still

    discussing it.

     > and parser generators are not concatenative.

     Gray is a parser generator written in a concatenative language. Is it

    concatenative?

     > > This isn't accurate; Factor uses a distributed parser, which means

    > > that the user can write his own parsing words that act not on external

    > > text input, but actually on the source code in the current program

    > > being compiled. Factor exposes some words that are useful for that

    > > purpose. Few other languages do that. Factor could no doubt provide

    > > more; but it already has more than most languages.

    > What I mean is that Factor doesn't use regexes, monads,

     It doesn't need them.

     > or a parser generator for parsing;

     It actually IS its own parser generator.

     > rather it uses its own mechanism to parse *its

    > own source code*. For anything that the user wants to parse, like say

    > XML, you need a new mechanism, and Factor currently doesn't provide

    > anything.

     Factor no doubt would benefit from more contributions, but such

    contributions would fit onto Factor's nicely defined framework, which

    is quite adequate for the work you're requesting. More than adequate.

    I forget -- does Factor have continuations? If so, it has more power

    than any out of the box parser generator you'll see.

     > Daniel Ehrenberg

     -Billy

## Ivan Tomac — 2005-04-05 13:05:35

    --- In concatenative@yahoogroups.com, Ehrenberg Daniel <microdan@g...> wrote:

     > Here's a problem to port to concatenative languages: parsing. I've

    > seen many different solutions to this in various applicative

    > languages: regular expressions, parser generators and first-class

    > parsers with monads, arrows, or some other mechanism that most people

    > don't understand. Each one has advantages and disadvantages, and none

    > are concatenative (not that they need to be). There's also the

    > undesireable path of telling users to write their own parsers, which

    > Factor takes for its own parser, but this isn't a very good solution

    > for everything; it can make many things unnecessarily complicated.

    > What do people here think of this issue?

     Don't know if you've already seen this but you should check out Haskell's parser

    combinator library, Parsec: http://www.cs.uu.nl/~daan/download/parsec/parsec.html

    In combination with point-free style of programming (Haskell term for programming

    without variables - not always possible in Haskell though) it often feels almost like

    programming in a concatenative language (of course it all depends on which subset of

    Parsec you end up using - for example whether you decide to use the choice combinator

    or whether you prefer using the infix function <|>).

    It is the most elegant parser generator I've seen so far and it's pretty easy to use (provided

    you know some Haskell - I actually found it extremely useful for learning Haskell).

    Here's a grammer for a simple concatenative language written using Parsec:

    module Test where

    import Control.Monad

    import Data.Char

    import Data.Either

    import Data.Maybe

    import Text.ParserCombinators.Parsec

    data Expr = List [Expr] | Strn String | Symb String | Comment String deriving Show

    parseExpr :: String -> Maybe [Expr]

    parseExpr s = either (const Nothing) Just (parse expr "" s)

    expr :: Parser [Expr]

    expr = subexpr >>= \l -> eof >> return l

    subexpr :: Parser [Expr]

    subexpr = whiteSpace >> many literal

    literal :: Parser Expr

    literal = choice [strnLit,comment,symbLit,listLit] >>= \x -> whiteSpace >> return x

    strnLit :: Parser Expr

    strnLit = liftM Strn $ between (char '"') (char '"') (many $ satisfy (/= '"'))

    symbLit :: Parser Expr

    symbLit = liftM Symb $ many1 (noneOf " \n\t[]")

    listLit :: Parser Expr

    listLit = liftM List $ between (char '[') (char ']') subexpr

    comment :: Parser Expr

    comment = try (string "--") >> liftM Comment (many $ satisfy (/= '\n'))

    whiteSpace :: Parser ()

    whiteSpace = skipMany (satisfy isSpace)

    *** eof ***

    You can test it by running 'ghci Test.hs' (Glasgow Haskell interpreter - note that Parsec

    comes packaged with GHC so you don't need to download it separatley):

    *Test> parseExpr "1 [2 swap \"test\" put -- comment\n] i"

    Loading package parsec-1.0 ... linking ... done.

    Just [Symb "1",List [Symb "2",Symb "swap",Strn "test",Symb "put",Comment "

    comment"],Symb "i"]

    I don't think it would be too hard to implement a library of parser combinators for a

    concatenative language (even a pure one like Joy) - in fact I think it would be about as easy

    as implementing one in Haskell.

    Ivan

## Ivan Tomac — 2005-04-05 13:17:04

    Here's the updated code that gets rid of all the variables :)

    Maybe it is possible to rewrite every Haskell expression to not use variables afterall?

    --------------------

    module Test where

    import Control.Monad

    import Data.Char

    import Data.Either

    import Data.Maybe

    import Text.ParserCombinators.Parsec

    data Expr = List [Expr] | Strn String | Symb String | Comment String deriving Show

    parseExpr :: String -> Maybe [Expr]

    parseExpr = either (const Nothing) Just . parse expr ""

    expr :: Parser [Expr]

    expr = subexpr >>= flip liftM eof . const

    subexpr :: Parser [Expr]

    subexpr = whiteSpace >> many literal

    literal :: Parser Expr

    literal = choice [strnLit,comment,symbLit,listLit] >>= flip liftM whiteSpace . const

    strnLit :: Parser Expr

    strnLit = liftM Strn $ between (char '"') (char '"') (many $ satisfy (/= '"'))

    symbLit :: Parser Expr

    symbLit = liftM Symb $ many1 (noneOf " \n\t[]")

    listLit :: Parser Expr

    listLit = liftM List $ between (char '[') (char ']') subexpr

    comment :: Parser Expr

    comment = try (string "--") >> liftM Comment (many $ satisfy (/= '\n'))

    whiteSpace :: Parser ()

    whiteSpace = skipMany (satisfy isSpace)

## William Tanksley, Jr — 2005-04-05 15:21:09

    Ivan Tomac <e1_t@...> wrote:

     > Maybe it is possible to rewrite every Haskell expression to not use variables afterall?

     It is -- I don't know whether you can do that without using monads,

    but you can do it with them. (Hint: a stack will work, in which case

    Haskell will become concatenative, although with an explicit

    concatenation operator.)

    -Billy

## sonof — 2005-04-05 20:00:16

    This is called point-free style. It should be possible to convert any pure

    function into point-free style, I think.

    http://lambda-the-ultimate.org/classic/message7365.html

    http://haskell.org/hawiki/PointFreeStyle

    -sonof

    --- Ivan Tomac <e1_t@...> wrote:

     >

    >

    > Here's the updated code that gets rid of all the variables :)

    > Maybe it is possible to rewrite every Haskell expression to not use variables

    > afterall?

    >

    > --------------------

    >

    > module Test where

    >

    > import Control.Monad

    > import Data.Char

    > import Data.Either

    > import Data.Maybe

    > import Text.ParserCombinators.Parsec

    >

    > data Expr = List [Expr] | Strn String | Symb String | Comment String deriving

    > Show

    >

    > parseExpr :: String -> Maybe [Expr]

    > parseExpr = either (const Nothing) Just . parse expr ""

    >

    > expr :: Parser [Expr]

    > expr = subexpr >>= flip liftM eof . const

    >

    > subexpr :: Parser [Expr]

    > subexpr = whiteSpace >> many literal

    >

    > literal :: Parser Expr

    > literal = choice [strnLit,comment,symbLit,listLit] >>= flip liftM whiteSpace

    > . const

    >

    > strnLit :: Parser Expr

    > strnLit = liftM Strn $ between (char '"') (char '"') (many $ satisfy (/=

    > '"'))

    >

    > symbLit :: Parser Expr

    > symbLit = liftM Symb $ many1 (noneOf " \n\t[]")

    >

    > listLit :: Parser Expr

    > listLit = liftM List $ between (char '[') (char ']') subexpr

    >

    > comment :: Parser Expr

    > comment = try (string "--") >> liftM Comment (many $ satisfy (/= '\n'))

    >

    > whiteSpace :: Parser ()

    > whiteSpace = skipMany (satisfy isSpace)

    >

    >

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

    >

    >

     __________________________________

    Yahoo! Messenger

    Show us what our next emoticon should look like. Join the fun.

    http://www.advision.webevents.yahoo.com/emoticontest

## Ehrenberg Daniel — 2005-04-06 00:17:55

    Before reading this, keep in mind I don't know what the hell I'm talking about.

     > > Regular expressions are not concatenative,

    >

    > I didn't know until now, but I've actually been waiting 7 years (since

    > my fundamentals of computation class) for someone to say that. :-)

    > Regular expressions are concatenative in the sense that the language

    > recognised by the concatenation of a pair of rexexps is the

    > concatenanation of the languages recognised by the regexps. I don't

    > know what you meant by saying that, but I can't think of a way in

    > which regexps are not concatenative.

    >

    > Not that it matters -- a regexp parser in most languages takes input

    > that's strictly distinct from the source code of the program. So the

    > concatenativity of the implementation language is entirely irrelevant

    > to the concatenativity of the parsed language.

     What I meant wasn't that regular expressions (as any rational person

    would define them) in the computer science world aren't concatenative;

    they can be concatenated and still get a reasonable meaning. But when

    you start writing regexes for irregular grammars as regular

    expressions exist in Perl, like /.*$1/, it doesn't work to take pieces

    of it out of context. But I'm not completely sure how useful irregular

    grammars are, as I don't have much experience in this field.

     >

    > > and monads and arrows are

    > > not concatenative,

    >

    > Funny. Read the paper on the arithmetic foundations of Joy -- every

    > monad is concatenative by definition. I don't know too much about

    > "arrows", though -- I left the TUNES group while they were still

    > discussing it.

     I don't fully understand arrows either, and in their most basic form,

    arrows and monads could be used in a variable-free setting, but it's

    usually very awkward and unlike how they're normally used.

     >

    > > and parser generators are not concatenative.

    >

    > Gray is a parser generator written in a concatenative language. Is it

    > concatenative?

    >

     I'm not sure, but it doesn't really matter. It looked like it used

    infix operators, but nevermind my comments about what is and isn't

    concatenative.

     > It actually IS its own parser generator.

    >

     Haha, I guess it is.

     > Factor no doubt would benefit from more contributions, but such

    > contributions would fit onto Factor's nicely defined framework, which

    > is quite adequate for the work you're requesting. More than adequate.

    >

    > I forget -- does Factor have continuations? If so, it has more power

    > than any out of the box parser generator you'll see.

     Yes, Factor does have continuations, but as I saw from Chris Double's

    parser combinator library, you don't need call/cc for backtracking,

    you just need lazylists.

    Daniel Ehrenberg

## William Tanksley, Jr — 2005-04-06 00:20:17

    sonof <unlin_e@...> wrote:

     > This is called point-free style. It should be possible to convert any pure

    > function into point-free style, I think.

    > http://lambda-the-ultimate.org/classic/message7365.html

    > http://haskell.org/hawiki/PointFreeStyle

     Thank you for the links -- very informative.

    It's not clear whether it's always possible to express code point-free

    in K and J, according to the discussion on the mailing lists while I

    was a member. J people often try and often succeed, but I'm not aware

    of anyone trying to prove whether or not it's generally possible.

    I'm glad to hear that it is always possible for pure functions in Haskell.

     > -sonof

     -Billy

## William Tanksley, Jr — 2005-04-06 00:27:38

    Ehrenberg Daniel <microdan@...> wrote:

     > Before reading this, keep in mind I don't know what the hell I'm talking about.

     An impressive list of credentials indeed -- worth at least as much as

    my computing theory class 7 years ago :-).

     > > > Regular expressions are not concatenative,

    > > a regexp parser in most languages takes input

    > > that's strictly distinct from the source code of the program. So the

    > > concatenativity of the implementation language is entirely irrelevant

    > > to the concatenativity of the parsed language.

    > But when

    > you start writing regexes for irregular grammars as regular

    > expressions exist in Perl, like /.*$1/, it doesn't work to take pieces

    > of it out of context. But I'm not completely sure how useful irregular

    > grammars are, as I don't have much experience in this field.

     Irregular grammars are extremely useful, but they're not regular

    expressions. That's why they're called "irregular". :-) An an

    irregular grammar may or may not itself be concatenative; presumably,

    however, if you wrote a parser in a concatenative language you're

    probably trying to parse a _different_ language than the original one,

    which means that it might not be concatenative even if the original

    language was. If you just wanted to parse the original language, you

    wouldn't have written a parser (you'd just use the original parser).

    But again, none of this matters. The parser can be fully concatenative

    while parsing something that's not.

     > > > and parser generators are not concatenative.

    > > Gray is a parser generator written in a concatenative language. Is it

    > > concatenative?

    > I'm not sure, but it doesn't really matter. It looked like it used

    > infix operators, but nevermind my comments about what is and isn't

    > concatenative.

     It allows you to parse infix operators; it itself is concatenative.

     > Daniel Ehrenberg

     -Billy

## Ivan Tomac — 2005-04-06 02:03:22

    --- In concatenative@yahoogroups.com, "William Tanksley, Jr"

    <wtanksleyjr@g...> wrote:

     > sonof <unlin_e@y...> wrote:

    > > This is called point-free style. It should be possible to convert

     any pure

    I already mentioned it was called point-free style in Haskell.

     > > function into point-free style, I think.

    > > http://lambda-the-ultimate.org/classic/message7365.html

    > > http://haskell.org/hawiki/PointFreeStyle

    >

    > Thank you for the links -- very informative.

    >

    > It's not clear whether it's always possible to express code

     point-free

     > in K and J, according to the discussion on the mailing lists while I

    > was a member. J people often try and often succeed, but I'm not

     aware

     > of anyone trying to prove whether or not it's generally possible.

    >

    > I'm glad to hear that it is always possible for pure functions in

     Haskell.

     >

     Actually I would think Haskell has the same problem that J has. It

    often seems like it's always possible but then you run into an

    expression that can't be written in point-free style unless you write

    a bunch of parameter-permutation functions (Haskell already has some

    such as flip which acts similar to swap in Joy and Forth except rather

    then swaping 2 values on the stack, it swaps the 2 inputs to some

    function).

    The problem is that even if you add more of such permutation functions

    to the core, you're always going to need more of those glue functions

    for different kinds of expressions.

    Realistically though some of those expressions would be very unlikely

    to happen in real world (like a function that takes 20 parameters) but

    theoretically you wouldn't be able to reorder those 20 parameters

    without a set of 20-parameter permutation functions. And some (in fact

    most I would think) of those permutation functions cannot be written

    in point-free style.

    Even a simple 2-parameter permutation function like flip is impossible

    to write in point-free style.

    The only solution would be like you already mentioned, to use some

    sort of a stack and pass all parameters on that stack.

     > > -sonof

    >

    > -Billy

     Ivan

## William Tanksley, Jr — 2005-04-06 14:18:42

    Ivan Tomac <e1_t@...> wrote:

     > Even a simple 2-parameter permutation function like flip is impossible

    > to write in point-free style.

     Facinating. Thanks for the voice of experience.

     > The only solution would be like you already mentioned, to use some

    > sort of a stack and pass all parameters on that stack.

     Even if you do that, you're still stuck with a point-based style; see

    also my ab--baab shuffle notation (which is emphaticly NOT

    point-free). The quickest way out of it is to provide an additional

    stack. In Forth, the return stack serves for this; and in Joy, the dip

    combinator creates a LIFO data structure (in other words, a stack)

    that's automatically managed and only accessible to dip.

    Is there some other way to be truly point-free (or pointless, as some

    have called it)? Was Forth actually the first point-free by design

    language? If so, this is astounding, considering how untainted Forth

    is by theoretical purity.

     > Ivan

     -Billy

## Ehrenberg Daniel — 2005-04-06 20:28:28

    > Is there some other way to be truly point-free (or pointless, as some

    > have called it)? Was Forth actually the first point-free by design

    > language? If so, this is astounding, considering how untainted Forth

    > is by theoretical purity.

     I think the language FP is completely, 100% point free without using a

    stack, but I'm not sure.

## Ehrenberg Daniel — 2005-04-06 20:38:57

    > Even a simple 2-parameter permutation function like flip is impossible

    > to write in point-free style.

     Of course it's impossible; in order to be able to write in a

    point-free style, you need some primitives. Haskell only provides the

    very pointed functional builtins of lambda calculus, as far as things

    relevant to this discussion. But it's possible to do anything you want

    and you don't need points. All you need is S and K. Is this practical?

    No. Is it possible to make this practical? There's a package called

    Pointless Haskell that tries to accomplish this, but I think the name

    says it all. In any case, even some programs in concatenative

    languages aren't point-free; most written in Factor and Forth are not,

    and it's easy to write a program in Joy using recursion, which is not

    point-free.

    Daniel Ehrenberg

## Ehrenberg Daniel — 2005-04-06 20:41:27

    > Irregular grammars are extremely useful, but they're not regular

    > expressions. That's why they're called "irregular". :-)

     Yeah, but most regular expression engines support irregular grammar,

    even if it's completely contradictory to the name. Because of their

    usefulness, I don't think it would be that bad to include them in a

    potential regex engine for Factor

    But anyway, I think Chris Double is going to make a BNF parser

    generator from his parser library, though I'm not sure.

    Daniel Ehrenberg

## Greg Buchholz — 2005-04-06 21:20:35

    --- In concatenative@yahoogroups.com, "Ivan Tomac" <e1_t@y...> wrote:

     > Actually I would think Haskell has the same problem that J has. It

    > often seems like it's always possible but then you run into an

    > expression that can't be written in point-free style unless you write

    > a bunch of parameter-permutation functions

         FWIW, a similar thread popped up on the haskell-cafe mailing list

    recently.  The following message seemed on topic...

    http://www.haskell.org//pipermail/haskell-cafe/2005-February/009112.html

     > Realistically though some of those expressions would be very unlikely

    > to happen in real world (like a function that takes 20 parameters)

     but

     > theoretically you wouldn't be able to reorder those 20 parameters

    > without a set of 20-parameter permutation functions.

         And for the really hard-core out there (those with 20 parameter

    functions), you might like the automatic point-free translation

    program in...

    http://www.haskell.org//pipermail/haskell-cafe/2005-February/009124.html

    Greg Buchholz

## phimvt@lurac.latrobe.edu.au — 2005-04-07 06:18:41

    On Mon, 4 Apr 2005, William Tanksley, Jr wrote:

     >

    > Ehrenberg Daniel <microdan@...> wrote:

     [..]

     > > Regular expressions are not concatenative,

    >

    > I didn't know until now, but I've actually been waiting 7 years (since

    > my fundamentals of computation class) for someone to say that. :-)

    > Regular expressions are concatenative in the sense that the language

    > recognised by the concatenation of a pair of rexexps is the

    > concatenanation of the languages recognised by the regexps. I don't

    > know what you meant by saying that, but I can't think of a way in

    > which regexps are not concatenative.

     You said it well: recognition maps concatenation of regular expressions

    onto concatenation of languages. I say it without "recognition" but

    with "denoting" instead:

    There seem to be several senses of concatenativity around:

    1. A language L is concatenative iff

         for programs P and Q in L,

             the program-concatenation P Q denotes the composition

             of the functions denoted by P and Q.

    2. But regular expressions (RE's) do not denote functions, they denote

       sets of strings (SS's). For example, the RE (a | b) denotes the SS

       {"a" "b"}. RE's can be concatenated, for example (a | b)(c | d).

       is the RE-concatenation of (a | b) with (c | d). SS's can also be

       concatenated, for example {"ac" "ad" "bc" "bd"} is the SS-concatenation

       of {"a" "b"} with {"c" "d"}. So SS-concatenation concatenates each

       string in the one set with each string in the other set. If the

       two sets have m and n members, then their SS-concatenation has

       up to m*n members (in the above example, exactly m*n members).

       So we can say this:

          for RE's P and Q,

              the RE-concatenation P Q denotes the SS-concatenation

              of the SS's denoted by P and Q.

       Or, since a SS is also called a language,

              the RE-concatenation of P and Q denotes the language-

              concatenation of what they denote.

      - Manfred

## sa@dfa.com — 2005-04-07 21:22:52

    a friend who had been doing some reading on combinatory logic asked

    me whether i knew how to write the Y-combinator in k.  i didn't, but

    a little reading turned up a clever method for deriving it from any

    recursive function.  my analysis is here:

          http://www.nsl.com/k/y.k

    it turns out that there's a much simpler applicative-order self-

    reference combinator -- U -- which bears a striking resemblance to

    manfred's joy quine [[dup cons] dup cons].  for example, in XY,

          ; fact [1 =] [1 *] [dup 1 - fact *] ifte ;

          5 fact

        120

    now define U:

          ; U dup cons i ;

    and ufact:

          ; ufact [swap 1 =] [pop 1 *] [[dup 1 -] dip U *] ifte ;

    then

          5 [ufact] U

        120

    ufact expects

          .. n [ufact]

    on the stack.

    in pattern-notation, the relation between fact and ufact is more

    apparent:

          ; fact  { [x]   x 0 = 1 [x 1 - fact x *] if } ;

          ; ufact { [x y] x 0 = 1 [x 1 - y U x *]  if } ;

    this is all collected here:

          http://www.nsl.com/k/xy/eg/u.xy

## Ivan Tomac — 2005-04-08 03:16:08

    --- In concatenative@yahoogroups.com, Ehrenberg Daniel <microdan@g...>

    wrote:

     > > Even a simple 2-parameter permutation function like flip is

     impossible

     > > to write in point-free style.

    >

    > Of course it's impossible; in order to be able to write in a

    > point-free style, you need some primitives. Haskell only provides

     the

    The problem with point-free style in Haskell is not that you need

    primitives, it's that even if you have a set of primitives like

    Haskell does right now you can never have enough of them - you can't

    create all of the new ones using the existing ones in point-free

    style.

    I used flip as an example - it's impossible to write it in point-free

    style, however it's provided in Haskell already so there is no need to

    write it. But what if swapping 2 parameters isn't enough and you need

    to reorder 3 parameters? Then you have to write your own functions to

    do that and you can't do it point-free. Now you could include those

    into the core again and solve that problem but then what about 4

    parameter functions?

    Like Billy said this could be solved with a stack (and of course a dip

    combinator) but that would be more like writing a domain specific

    language to solve the problem - same goes for the SK combinators.

     > very pointed functional builtins of lambda calculus, as far as

     things

     > relevant to this discussion. But it's possible to do anything you

     want

     > and you don't need points. All you need is S and K. Is this

     practical?

     > No. Is it possible to make this practical? There's a package called

    > Pointless Haskell that tries to accomplish this, but I think the

     name

     > says it all. In any case, even some programs in concatenative

    > languages aren't point-free; most written in Factor and Forth are

     not,

     > and it's easy to write a program in Joy using recursion, which is

     not

     > point-free.

     How so? No Joy program has any variables. And same is true for a pure

    but still quite usable subset of Factor and Forth. They are completely

    point-free as every expression can trivially be written without using

    variables.

     > Daniel Ehrenberg

     Ivan

## William Tanksley, Jr — 2005-04-08 16:32:22

    Ehrenberg Daniel <microdan@...> wrote:

     > > Even a simple 2-parameter permutation function like flip is impossible

    > > to write in point-free style.

    > and you don't need points. All you need is S and K. Is this practical?

     It sounds correct to me that S and K are complete, which means that

    using them you can construct all of the possible parameter reorderings

    you could ever need in order to operate in a completely point-free

    style.

    So, therefore, it sounds incorrect to me to claim that "flip is

    impossible to write in point-free style". Is that correct?

     > says it all. In any case, even some programs in concatenative

    > languages aren't point-free; most written in Factor and Forth are not,

    > and it's easy to write a program in Joy using recursion, which is not

    > point-free.

     Isn't implicit recursion -- which is one of Joy's strengths -- point-free?

    I would expect most programs written in Forth to be point-free, except

    for the occasional (heavily discouraged) use of global variables.

     > Daniel Ehrenberg

     -Billy

## sa@dfa.com — 2005-04-08 18:12:57

    "Ivan Tomac" <e1_t@...> wrote on 04/07/2005 11:16:08 PM:

     >

    >

    > --- In concatenative@yahoogroups.com, Ehrenberg Daniel <microdan@g...>

    > wrote:

    > > > Even a simple 2-parameter permutation function like flip is

    > impossible

    > > > to write in point-free style.

    > >

    > > Of course it's impossible; in order to be able to write in a

    > > point-free style, you need some primitives. Haskell only provides

    > the

    >

    > The problem with point-free style in Haskell is not that you need

    > primitives, it's that even if you have a set of primitives like

    > Haskell does right now you can never have enough of them - you can't

    > create all of the new ones using the existing ones in point-free

    > style.

     a k function is either a primitive (of one or two arguments),

    or a lambda, which has an argument list and a body, e.g.:

          {[a;b;c]a+b-c}

    the function f below takes a function and returns a pair

          (arglist;body)

    and the function g below takes such a pair and returns a

    function.

    so for any function h

          h = g f h

    (technically:  h ~ g . f h)

    to achieve any permutation of arguments, the following set of

    three functions will serve:

          X h         / swap last two arguments of h

          L h         / shift argument list left

          R h         / shift argument list right

    X, L, and R each use f to split the input function into arglist

    and body, modify the arglist, then use g to make a new function.

    e.g.,

          L L X L L X L L X L{[a;b;c;d;e;f]a+b+c+d+e+f}

        {[c;b;e;d;a;f]a+b+c+d+e+f}

    the code is in:

          http://www.nsl.com/k/f.k

    can this be done in haskell?

     >

    > I used flip as an example - it's impossible to write it in point-free

    > style, however it's provided in Haskell already so there is no need to

    > write it. But what if swapping 2 parameters isn't enough and you need

    > to reorder 3 parameters? Then you have to write your own functions to

    > do that and you can't do it point-free. Now you could include those

    > into the core again and solve that problem but then what about 4

    > parameter functions?

    >

    > Like Billy said this could be solved with a stack (and of course a dip

    > combinator) but that would be more like writing a domain specific

    > language to solve the problem - same goes for the SK combinators.

    >

    > > very pointed functional builtins of lambda calculus, as far as

    > things

    > > relevant to this discussion. But it's possible to do anything you

    > want

    > > and you don't need points. All you need is S and K. Is this

    > practical?

    > > No. Is it possible to make this practical? There's a package called

    > > Pointless Haskell that tries to accomplish this, but I think the

    > name

    > > says it all. In any case, even some programs in concatenative

    > > languages aren't point-free; most written in Factor and Forth are

    > not,

    > > and it's easy to write a program in Joy using recursion, which is

    > not

    > > point-free.

    >

    > How so? No Joy program has any variables. And same is true for a pure

    > but still quite usable subset of Factor and Forth. They are completely

    > point-free as every expression can trivially be written without using

    > variables.

    >

    > > Daniel Ehrenberg

    >

    > Ivan

    >

    >

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

    >

## Ehrenberg Daniel — 2005-04-08 18:44:51

    > How so? No Joy program has any variables. And same is true for a pure

    > but still quite usable subset of Factor and Forth. They are completely

    > point-free as every expression can trivially be written without using

    > variables.

    >

    > Ivan

     I thought names of functions/words were "points", so any program using

    manual recursion without a combinator is not completely point-free.

    Joy usually tries to encourage point-freeness, though, through the use

    of its combinators.

    Daniel Ehrenberg

## Ivan Tomac — 2005-04-09 02:00:22

    --- In concatenative@yahoogroups.com, "William Tanksley, Jr"

    <wtanksleyjr@g...> wrote:

     > It sounds correct to me that S and K are complete, which means that

    > using them you can construct all of the possible parameter reorderings

    > you could ever need in order to operate in a completely point-free

    > style.

    >

    > So, therefore, it sounds incorrect to me to claim that "flip is

    > impossible to write in point-free style". Is that correct?

    >

     Yes, I was wrong there. My initial thought was that to solve the

    problem you'd have to write a domain specific language on top of

    Haskell (like the stack+dip idea or what Stevan suggested with the

    arguments being passed in a list and then having a set of shifting and

    swapping combinators to reorder the arguments) and I thought it would

    be the same with the S K combinators but after looking at the S K

    combinators again it seems it's possible with just plain Haskell

    functions and no other abstractions.

     > -Billy

     Ivan

## Ivan Tomac — 2005-04-09 02:19:09

    --- In concatenative@yahoogroups.com, Ehrenberg Daniel <microdan@g...>

    wrote:

     > I thought names of functions/words were "points", so any program using

    > manual recursion without a combinator is not completely point-free.

    > Joy usually tries to encourage point-freeness, though, through the use

    > of its combinators.

     I'm not sure I understand the part about functions being points.

    Point-free style of programing simply involves using function

    composition and combinators to do the argument shuffling without

    explicitly naming any arguments.

     > Daniel Ehrenberg

     Ivan

## William Tanksley, Jr — 2005-04-09 15:42:47

    Ivan Tomac <e1_t@...> wrote:

     > Yes, I was wrong there. My initial thought was that to solve the

    > problem you'd have to write a domain specific language on top of

    > Haskell (like the stack+dip idea or what Stevan suggested with the

    > arguments being passed in a list and then having a set of shifting and

    > swapping combinators to reorder the arguments)

     Why would you identify either of these as being a domain-specific

    language? They seem like they'd fit into any language. In Haskell I'm

    sure the stack pair would be a monad; the S and K thing would seem to

    require a lazy stack language.

     > Ivan

     -Billy

## William Tanksley, Jr — 2005-04-09 15:55:39

    Ehrenberg Daniel <microdan@...> wrote:

     > I thought names of functions/words were "points", so any program using

    > manual recursion without a combinator is not completely point-free.

    > Joy usually tries to encourage point-freeness, though, through the use

    > of its combinators.

     I'm hunting for a definition of point-free to help me here; the best I

    can find is that the word originated in topology, where it describes a

    branch of topology that studies collections of points called

    "lattices" without having to identify any of the points explicitly.

    From this definition, it seems to me that applying names to data would

    violate the premise, but naming functions wouldn't matter.

    I wasn't able to find any real definitions for the computer science

    term online -- the ones I found weren't really definitions, but rather

    sets of examples. One of them claimed that a point-free style tries to

    "minimise" the use of lambda... The same one said the recursion would

    be forbidden, but again I think that's because the author couldn't

    think of a way to recurse without naming the function.

     > Daniel Ehrenberg

     -Billy

## phimvt@lurac.latrobe.edu.au — 2005-04-11 02:24:24

    On Thu, 7 Apr 2005 sa@... wrote:

    [..]

    > it turns out that there's a much simpler applicative-order self-

    > reference combinator -- U -- which bears a striking resemblance to

    > manfred's joy quine [[dup cons] dup cons].  for example, in XY,

    >

    >       ; fact [1 =] [1 *] [dup 1 - fact *] ifte ;

    >       5 fact

    >     120

    >

    > now define U:

    >

    >       ; U dup cons i ;

    >

    > and ufact:

    >

    >       ; ufact [swap 1 =] [pop 1 *] [[dup 1 -] dip U *] ifte ;

    I was a bit surpised by         ^^^   multiplication by 1,

    but I suppose this works.

    For comparison, and using details just like yours,

    here is factorial using y:

          yfact == [swap 1 =] [pop 1 *] [[dup 1 -] dip i *] ifte] y

    The only difference is that yours uses U where the other uses i.

    As far as execution is concerned, both will do pretty much the

    same steps. To be exact, if your U is inlined, they will do

    exactly the same steps. I am glad to see that XY can handle this.

    [..]

    I am currently working on a survey of replicating programs in Joy.

    From the simplest self-replicating via all sorts of things (including

    lazy lists) to the U and y-combinator, to a form of recursion

    combinator with internal state which can be modified during

    execution. But it is taking longer than I had expected.

      - Manfred

## phimvt@lurac.latrobe.edu.au — 2005-04-11 02:53:44

    On Thu, 7 Apr 2005 phimvt@... wrote:

    Sorry to be replying to myself. But it may be useful:

    [..]

    > There seem to be several senses of concatenativity around:

    >

    > 1. A language L is concatenative iff

    >      for programs P and Q in L,

    >          the program-concatenation P Q denotes the composition

    >          of the functions denoted by P and Q.

    >

    > 2. But regular expressions (RE's) do not denote functions, they denote

    >    sets of strings (SS's). For example, the RE (a | b) denotes the SS

    >    {"a" "b"}. RE's can be concatenated, for example (a | b)(c | d).

    >    is the RE-concatenation of (a | b) with (c | d). SS's can also be

    >    concatenated, for example {"ac" "ad" "bc" "bd"} is the SS-concatenation

    >    of {"a" "b"} with {"c" "d"}. So SS-concatenation concatenates each

    >    string in the one set with each string in the other set. If the

    >    two sets have m and n members, then their SS-concatenation has

    >    up to m*n members (in the above example, exactly m*n members).

    >    So we can say this:

    >       for RE's P and Q,

    >           the RE-concatenation P Q denotes the SS-concatenation

    >           of the SS's denoted by P and Q.

    >    Or, since a SS is also called a language,

    >           the RE-concatenation of P and Q denotes the language-

    >           concatenation of what they denote.

    Concatenation and the null-string form a monoid, hence there are

    homomorphisms from that monoid to any other monoid. We have seen

    two examples already: 1: The monoid of function composition and the

    identity function, and 2: The monoid of language (set of strings

    composition and as identity element the one element language

    whose only element is the null-string). Another example is 3:the

    commonly used notation in algebra where xy means the product of

    x and y. Here the homomorphism maps concatenation onto multipli-

    cation and the null-string onto the number 1. Pretty much the

    same in 4: matrix algebra, where concatenation means matrix

    multiplication and where the identity element(s ?) are appropriate

    matrices such that multiplication by them does nothing. The nature

    of the elements in the matrix can be (and fruitfully should be)

    left completely open. I don't know of any other examples in actual

    use, but any other monoid is a candidate for being the target

    of a homomorphism.

      - Manfred

## Ivan Tomac — 2005-05-08 09:03:15

    --- In concatenative@yahoogroups.com, "William Tanksley, Jr"

    <wtanksleyjr@g...> wrote:

     > Ivan Tomac <e1_t@y...> wrote:

    > > Yes, I was wrong there. My initial thought was that to solve the

    > > problem you'd have to write a domain specific language on top of

    > > Haskell (like the stack+dip idea or what Stevan suggested with the

    > > arguments being passed in a list and then having a set of shifting and

    > > swapping combinators to reorder the arguments)

    >

    > Why would you identify either of these as being a domain-specific

    > language? They seem like they'd fit into any language. In Haskell I'm

    > sure the stack pair would be a monad; the S and K thing would seem to

    > require a lazy stack language.

    >

     My apologies for the late reply - I've been a bit preoccupied lately.

    What I meant is that it might be possible to construct functions that

    can reorder the arguments to another function using just S and K

    combinators (when I have some free time I might look into that) - in

    other words normal Haskell functions without any other abstractions.

    The other approaches that use a stack or a list or some other data

    structure essentially implement a sub-language on top of Haskell to

    deal with the problem. You are restricted to using functions that

    operate on those data structures.

     > -Billy

     Ivan