pattern matching

[Martin R]

Hi there!

I am trying to find out what Pattern and friends do (in the end, I would like to do pattern matching on InputForm).  I found very few examples, one of which is the following.

Does somebody know how to use it?  I tried the following, but I don't understand it.  Isn't Pattern Integer supposed to say that the pattern should only match things of type Integer?

Many thanks,

Martin

(1) -> mR := PATRES(Integer, Complex(Integer))

   (1)  PatternMatchResult(Integer,Complex(Integer))
                                                                   Type: Type
(2) -> pat := convert('x)@Pattern(Integer)

   (2)  x
                                                       Type: Pattern(Integer)
(3) -> patternMatch(3 + 2*%i, 3 + pat, new()$mR)

   (3)  [[key = x, entry = 2 %i]]
                           Type: PatternMatchResult(Integer,Complex(Integer))

[Waldek Hebisch]

On Mon, Mar 23, 2026 at 10:32:56AM -0700, 'Martin R' via FriCAS - computer algebra system wrote:
> Hi there!
>
> I am trying to find out what Pattern and friends do (in the end, I would
> like to do pattern matching on InputForm). I found very few examples, one
> of which is the following.
>
> Does somebody know how to use it? I tried the following, but I don't
> understand it. Isn't Pattern Integer supposed to say that the pattern
> should only match things of type Integer?

No. Pattern is related to Expression and meaning of parameter is
similar: Expression(Integer) means expression where _constants_
are integer. By applying operators to constants you can
produce expressions having non-integer values. Pattern(Integer)
means patterns with constants which are integers, but such patterns
may match expressions having non-integer values. Complex(Integer)
in example below means that you want to match things from
Complex(Integer).

Pattern matching has problem: expressions with equal values
may have different syntactic structure. This problem is
extra prononced in FriCAS: FriCAS Expression is represented in
a form that is frequently different from the form users imagine,
so users tend to use wrong pattern. FriCAS pattern matcher
tries to help there, but for Expression my experience is that
directly using operations on expressions works better.

If you are strictly concerned with InputForm, that is you
consider different InputForm-s as different objects, then
most of problems above are no longer a problem. But AFAICS
currently there is no support form matching InputForm-s.
If you want to see what is currently supported look
for domains of category 'PatternMatchable'. Basically
this is Expression and corresponding base domains (AFAICS
matching for base domains is trivial, it is present only
for technical reasons).

Pattern matching InputForm looks easy, but apparently nobody
wanted it enough to implement. Actually, the main trouble
seem to be that Pattern essentially assumes that it is
dealsing with FriCAS expression, that is assumes operators
and kernels. So pattern matching for InputForm probably
should ignore current pattern matching machinery.

BTW: simple pattern matching is needed for OutputForm, I
created OutputFormTools for this. Similar thing is
available for SExpression. On top of this one could
build much more fancy machinery, but ATM nobody did this.

> Many thanks,
>
> Martin
>
> (1) -> mR := PATRES(Integer, Complex(Integer))
>
> (1) PatternMatchResult(Integer,Complex(Integer))
> Type:
> Type
> (2) -> pat := convert('x)@Pattern(Integer)
>
> (2) x
> Type:
> Pattern(Integer)
> (3) -> patternMatch(3 + 2*%i, 3 + pat, new()$mR)
>
> (3) [[key = x, entry = 2 %i]]
> Type:
> PatternMatchResult(Integer,Complex(Integer))
>

> --
> You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/d866c1cc-3469-4945-b3da-25a708719190n%40googlegroups.com.


--
Waldek Hebisch

[Waldek Hebisch]

On Tue, Mar 24, 2026 at 12:36:56AM +0100, Waldek Hebisch wrote:
> On Mon, Mar 23, 2026 at 10:32:56AM -0700, 'Martin R' via FriCAS - computer algebra system wrote:
> > Hi there!
> >
> > I am trying to find out what Pattern and friends do (in the end, I would
> > like to do pattern matching on InputForm). I found very few examples, one
> > of which is the following.

Maybe I will expand a bit on what I wrote in the previous message.
When one wants to do Rubi-style pattern maching integrator one
of simplest patterns is for product of two linear polynomials:

(a*x + b)*(c*x + d)

Normally FriCAS immediately expands such things, so one really has

a*c*x^2 + b*x + c*x + b*d

Such expanded pattern is unlikely to match expanded user input.
That is, when you look for a product, then expanded expressions
are unlikely to match. However, one can try to factor first.
In other systems naive factoring may work OK. In FriCAS
mere coercion from Factored to orignal domain expands, so it
does not work. If you insist on pattern matching, there is a
workaround, write pattern as

paren(a*x + b)*paren(c*x + d)

You can produce similar thing from FactorList, so matching
should works as in other systems. But once you have
FactorList it is easy to check that factors are linear and
extract coefficients from them. In the process one can
also apply various side conditions, so using pattern gains
only a little (if any).

Given explicit tree form, like InputForm one normally
ignores issues related to expressions. In Boot we have
pattern matching on Lisp lists (which are really rather
general tree forms). One can write:

x is ["where", ["DEF", :.], :.]

to check for specific symbols in given places. One can extract
subtrees using variables in the pattern:

x is [op1, ["DEF", sig, :.], :.]

assigns values to op1 and sig. One can test for presence of
prescribed values contained in variables like:

x is [op1, ["DEF", =sig, :.], :.]

Coding corresponding pattern matcher is easy. Main value is
integration with language syntax. In Spad we have trouble,
namely various candidate syntaxes are already "taken" by
other constructs. In particular 'is' has quite a different
meaning, '==' and '~=' which are next 2 natural choices also
have incompatible meaning. There is another problem, namely
FriCAS objects are typed and both sides of match expression
need to have appriate type. Boot style patterns could work
on SExpression, but building SExpression-s in FriCAS requires
a lot of 'convert'-s, so patterns would look ugly. And
they would not work on tree-like things which are not
SExpression-s. InputForm and OutputForm probably could be
handled by a bunch of trivial coercions (trivial in the
sense that they are implmentd by 'pretend'). But we can
have varied tree-like structures and it would be unnatural
to support only things represented by Lisp lists. Typed
landuages like ML have their form of pattern matching
which can match records and unions and it would be nice
to support something similar. So, it is not so easy to
specify general design for pattern matching. In particular,
it looks that general machinery needs to be part of
the language.

For specific domain like InputForm one can easily implement
special matcher. But then the trouble is that FriCAS
language does not help with syntax and types. Pattern
matching for Expression-s tries to work around the problem
by converting expressions to pattern. For InputForm that
is more trucky: a symbol in InputForm may be just a literal
symbol. But one also needs special things, that is variables
to match subparts (here something like "?(x)" could indicate
that 'x' is a match variable). So there is some work to
design useful notation.

BTW: In some sense patten matching in Boot is trivial. But
it is quite convenient and blends nicely into the language.

--
Waldek Hebisch

[Peter Broadbery]

I guess this is getting off-topic, but I've done a little in aldor regarding pattern matching. It's possible this could fit with fricas too.

Not complete, but a work in progress.

The syntax is 'x case pattern', and 'select x in pattern1 => expr1 ...' Patterns contain wildcards denoted by '?', and match anything.

Other parts of a pattern are partial functions, running in the opposite direction.

Eg. 'cons: % -> Partial(T, %)' and 'nil: % -> Partial ()', and 'aList case cons(?, nil())' matching a list of one element. Silly example, but it maps to more complex ones.

This feels like it works generally, and fits into the compilation pass - one just has to flip the function signature to the dual, and proceed as normal. Code generation then has been be aware that things are backwards.

--
You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/acHc811ZDK9TNN8a%40fricas.org.

[Martin R]

I think I have solved my problem with InputForm - thank you Waldek for your reply, it was indeed helpful!

Best wishes,

Martin

[Waldek Hebisch]

On Tue, Mar 24, 2026 at 08:43:48AM +0000, Peter Broadbery wrote:
> I guess this is getting off-topic, but I've done a little in aldor
> regarding pattern matching. It's possible this could fit with fricas too.
>
> Not complete, but a work in progress.
> The syntax is 'x case pattern', and 'select x in pattern1 => expr1 ...'
> Patterns contain wildcards denoted by '?', and match anything.

I shortly considerd similar possibility, but there seem to be
troubles:
- currently 'case' for Union-s either takes type or a tag. Extending
it to another possibilities gets tricky in the compiler (at least
in Spad compiler, maybe Aldor compiler already has code to handle
it). Somewhat related, such construct may be confusing for users.
- AFAICS 'select' above needs to be reserved word, but that conflicts
with using 'select' as a function name (tens of such uses in current
FriCAS algebra).
- Single '?' as a wildcard has a problem: we may want to extract matches
and that requires identifying them. It would be nice to support
"nonlinear" patterns, that is restrict matches to cases when some
subparts are equal.

> Other parts of a pattern are partial functions, running in the opposite
> direction.
> Eg. 'cons: % -> Partial(T, %)' and 'nil: % -> Partial ()', and 'aList case
> cons(?, nil())' matching a list of one element. Silly example, but it maps
> to more complex ones.
>
> This feels like it works generally, and fits into the compilation pass -
> one just has to flip the function signature to the dual, and proceed as
> normal. Code generation then has been be aware that things are backwards.

AFAICS this requires ability to identify corresponding structure.
For "constuctors" (that is functions that create new things) like 'cons'
that is easy. But say '+' on integers is tricky. I would expect that
"matchable" functions are marked in some special way and provided with
appropriate matcher. That could be similar to relation between 'elt'
and 'setelt!': given 'elt' compiler has no way to create 'setelt!' so
'setelt!' must be provided by the user. But unlike 'elt' which is a
single name constructor functions in principle may have more varied
names.

--
Waldek Hebisch

[Peter Broadbery]

On Wed, 25 Mar 2026 at 13:09, Waldek Hebisch <de...@fricas.org> wrote:
>
> On Tue, Mar 24, 2026 at 08:43:48AM +0000, Peter Broadbery wrote:
> > I guess this is getting off-topic, but I've done a little in aldor
> > regarding pattern matching. It's possible this could fit with fricas too.
> >
> > Not complete, but a work in progress.
> > The syntax is 'x case pattern', and 'select x in pattern1 => expr1 ...'
> > Patterns contain wildcards denoted by '?', and match anything.
>
> I shortly considerd similar possibility, but there seem to be
> troubles:
> - currently 'case' for Union-s either takes type or a tag. Extending
> it to another possibilities gets tricky in the compiler (at least
> in Spad compiler, maybe Aldor compiler already has code to handle
> it). Somewhat related, such construct may be confusing for users.
> - AFAICS 'select' above needs to be reserved word, but that conflicts
> with using 'select' as a function name (tens of such uses in current
> FriCAS algebra).

select is an aldor keyword, I wasn't aware that it was used in fricas.
Not sure what
a good alternative would be. 'match' maybe?

> - Single '?' as a wildcard has a problem: we may want to extract matches
> and that requires identifying them. It would be nice to support
> "nonlinear" patterns, that is restrict matches to cases when some
> subparts are equal.
>
> > Other parts of a pattern are partial functions, running in the opposite
> > direction.
> > Eg. 'cons: % -> Partial(T, %)' and 'nil: % -> Partial ()', and 'aList case
> > cons(?, nil())' matching a list of one element. Silly example, but it maps
> > to more complex ones.
> >
> > This feels like it works generally, and fits into the compilation pass -
> > one just has to flip the function signature to the dual, and proceed as
> > normal. Code generation then has been be aware that things are backwards.
>
> AFAICS this requires ability to identify corresponding structure.
> For "constuctors" (that is functions that create new things) like 'cons'
> that is easy. But say '+' on integers is tricky. I would expect that
> "matchable" functions are marked in some special way and provided with
> appropriate matcher. That could be similar to relation between 'elt'
> and 'setelt!': given 'elt' compiler has no way to create 'setelt!' so
> 'setelt!' must be provided by the user. But unlike 'elt' which is a
> single name constructor functions in principle may have more varied
> names.
>

I would like to find a syntax for associating a constructor with its
corresponding inverse, but not found anything satisfactory. "(matcher
cons)(a: %): (T, %) ==
..." could work, but doesn't feel like a good fit with the existing language.

To help, I've created https://github.com/aldorlang/aldor/issues/175 -
there's this discussion there, plus an implicit call for more ideas;
anything there is editable. I would like aldor to match fricas as far
as possible.

Peter


Peter