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