Mathematical Search and Regular Expressions

[David Breecker]

Melodyhound should delight the mathematicians among you, especially its use
of the "Parsons Code," or "melodic contour," which is able to identify
melodies quite accurately just by knowing the sequence of rising or falling
pitches:  http://www.melodyhound.com/melodic_contour.0.html

You can also enter notes from a piano keyboard, sing, whistle, or tap a
rhythm on your computer keyboard.  It will try to find a match, with
surprisingly good results.  My intuition says there's some information
theory at work here...
db

----- Original Message -----
From: "Rob Howard" <[hidden email]>
To: "'The Friday Morning Applied Complexity Coffee Group'"
<friam at redfish.com>
Sent: Tuesday, December 26, 2006 10:38 PM
Subject: Re: [FRIAM] Mathematical Search and Regular Expressions

> Math ability and music ability are related. Similar to Owen's question, I
> would love to know how to search for a song on the internet given that I
> only know how to hum a few bars.
>
> -----Original Message-----
> From: friam-bounces at redfish.com [mailto:friam-bounces at redfish.com] On
> Behalf
> Of Martin C. Martin
> Sent: Tuesday, December 26, 2006 4:14 PM
> To: The Friday Morning Applied Complexity Coffee Group
> Subject: Re: [FRIAM] Mathematical Search and Regular Expressions
>
> I think Barbie summed it up best: "Math is hard."
>
> Even most people who are good with computers find math hard.  There are
> many programmers who have trouble thinking in recursive/dynamic
> programming terms, or who have trouble with the sort of simple 3D vector
> math found in games.  As such, searching for exponentials, or putting
> them on the web, just doesn't come up that often.  If it did, it would
> be a bigger part of HTML/wiki/whatever.
>
> At least, that's how it looks to me.
>
> Best,
> Martin
>
> Owen Densmore wrote:
>> Some of us have been discussing the relationship between mathematics
>> and computation.  One particular element of this is how math is a
>> second class citizen within the web and computing world.
>>
>> Its tough for me to send you an equation, for example, one with a
>> standard representation and easily input into your particular math
>> software (MatLab, Maple, Mathematica).  The specialization of math
>> software bears this out .. all the packages are quite expensive and
>> not particularly interoperable.  MathML has not matured and is not
>> yet ubiquitous, nor can it be used as input to these math packages.
>> TeX can typeset math, but has no semantics tied to it.
>>
>> One particular example came to me yesterday while thinking about
>> searching for certain kinds of exponentials: How would I search for
>> an equation on the web, and how could I "grep" through a set of
>> papers using a regular expression containing mathematics?
>>
>> The semantics of mathematical notation has to be considered in regex
>> as well: a*b is the same as b*a, and the regex engine would have to
>> know that.
>>
>> I'm wondering if this is just that math has not yet had its day in
>> the web sunlight, or it is deeper .. a fundamental problem.
>>
>>      -- Owen
>>
>> Owen Densmore   http://backspaces.net
>>
>>
>>
>> ============================================================
>> FRIAM Applied Complexity Group listserv
>> Meets Fridays 9a-11:30 at cafe at St. John's College
>> lectures, archives, unsubscribe, maps at http://www.friam.org
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9a-11:30 at cafe at St. John's College
> lectures, archives, unsubscribe, maps at http://www.friam.org
>
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9a-11:30 at cafe at St. John's College
> lectures, archives, unsubscribe, maps at http://www.friam.org
>
>

[David Eric Smith]

Hi Friam,

Returning from music to the question of searching for mathematical
expressions.  This may be foolish, but what about using a functional
programming language, such as Haskell, as a "standard format" for
searchable math expressions?  It reads enough like math that it
wouldn't be very difficult to learn, and the context of an executable
code ensures a form of validity testing by the person initiating the
query (make sure it evaluates correctly on your own machine, then
submit the code as a search string).  It wouldn't be necessary that a
search engine support all forms of representation initially; it would
be enough to support one form in a useful way.

I want to imagine, though this is not well thought out, that one wants
a definitional language rather than an assignment language, even if
evaluating the expression on some standard set of inputs would be one
criterion for assigning it a mathematical "identity".  Even better, of
course, would be to have criteria for a "normal form" of some kind, so
that among the possible changes of variable in a single equation,
automatic conversions could select a particular one as the search
standard.  This would be along the lines of using a symbolic package
as an engine to try to relate different representations of equivalent
expressions.  

Does this add anything to what can be done now?

Eric

[Marcus G. Daniels-3]

Eric Smith wrote:
> Returning from music to the question of searching for mathematical
> expressions.  This may be foolish, but what about using a functional
> programming language, such as Haskell, as a "standard format" for
> searchable math expressions?  
Some of the popular functional programming languages like ML (or OCaml)
take the perspective that programmers may find it easier to think in
terms of loops and side effects than recursion and monads, but even if
that is true, programmers are not the concern.   Mathematica is also one
of these languages that can be used in a functional way but also provide
imperative programming features.   It might be tempting just to use
Mathematica, but of course it's a proprietary thing, which might not be
ideal for some environments or audiences.  In contrast, Haskell is
purely functional and a new set of conventions built on it would limit
the risk that junk (that was hard to search or grok) could sneak in and
complicate things..

[Owen Densmore]

First of all, a big THANKS for all the interesting ideas.  I've been  
trying to get my brain around all this for quite some time.  And I  
think its time I sit down and start writing on the divide between  
Math and Computing.

One of the more interesting discussions on this topic comes from the  
APL/Ken Iverson world.  APL (A Programming Language) used a concise  
mathematical notation for its syntax.  It was quite a hit at Xerox in  
the early to mid '70s and indeed was considered a great rapid  
prototyping language.

One of Iverson's ideas was that mathematical notation was flawed and  
could easily be fixed by focusing on making it more parseable and  
less ambiguous.  His 1979 Turing Award lecture was a wonderful  
summary of these ideas:
   Notation as a Tool of Thought (1979 Turing Award Lecture)
   by Kenneth E. Iverson, Communications of the ACM,
   Volume 23, Number 8, August 1980.
     http://elliscave.com/APL_J/tool.pdf

In a sense, Ken was the one of the pioneers poking at the topic we're  
discussing.  I suspect Turing, Von Neuman, and others were there too.

Ken's APL work has been carried on by Ken's son Eric and Roger Hui,  
both of whom worked closely with Ken.  APL has been morphed into the  
J Programming Language:
   http://en.wikipedia.org/wiki/J_programming_language

I've taken a run at J with some success.  Its reasonably cross  
platform.  But boy, the learning curve is steep!  The power of J,  
however, is considerable.  If any FRIAMers start in on J, let me  
know.  These sites are representative of the leaders of the J community:
   http://olegykj.sourceforge.net/
   .. and all the External links at the end of the Wikipedia article.

     -- Owen

Owen Densmore   http://backspaces.net

[Owen Densmore]

Here's a more recent Ken Iverson discussion on Computers and  
Mathematical Notation:
   http://tinyurl.com/ym8r64
or
   http://www.cacs.louisiana.edu/~mgr/404/burks/language/apl/camnweb/ 
camn.htm

This is J based, rather than APL.

     -- Owen

Owen Densmore   http://backspaces.net


On Dec 28, 2006, at 12:00 PM, Owen Densmore wrote:

> First of all, a big THANKS for all the interesting ideas.  I've been
> trying to get my brain around all this for quite some time.  And I
> think its time I sit down and start writing on the divide between
> Math and Computing.
>
> One of the more interesting discussions on this topic comes from the
> APL/Ken Iverson world.  APL (A Programming Language) used a concise
> mathematical notation for its syntax.  It was quite a hit at Xerox in
> the early to mid '70s and indeed was considered a great rapid
> prototyping language.
>
> One of Iverson's ideas was that mathematical notation was flawed and
> could easily be fixed by focusing on making it more parseable and
> less ambiguous.  His 1979 Turing Award lecture was a wonderful
> summary of these ideas:
>    Notation as a Tool of Thought (1979 Turing Award Lecture)
>    by Kenneth E. Iverson, Communications of the ACM,
>    Volume 23, Number 8, August 1980.
>      http://elliscave.com/APL_J/tool.pdf
>
> In a sense, Ken was the one of the pioneers poking at the topic we're
> discussing.  I suspect Turing, Von Neuman, and others were there too.
>
> Ken's APL work has been carried on by Ken's son Eric and Roger Hui,
> both of whom worked closely with Ken.  APL has been morphed into the
> J Programming Language:
>    http://en.wikipedia.org/wiki/J_programming_language
>
> I've taken a run at J with some success.  Its reasonably cross
> platform.  But boy, the learning curve is steep!  The power of J,
> however, is considerable.  If any FRIAMers start in on J, let me
> know.  These sites are representative of the leaders of the J  
> community:
>    http://olegykj.sourceforge.net/
>    .. and all the External links at the end of the Wikipedia article.
>
>      -- Owen
>
> Owen Densmore   http://backspaces.net
>
>
>
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9a-11:30 at cafe at St. John's College
> lectures, archives, unsubscribe, maps at http://www.friam.org

[Owen Densmore]

OK, just one more addition to the J theme.  Sorry to be noisy!

I wrote to the J forum two years ago on the topic:
   http://www.jsoftware.com/pipermail/general/2004-July/017809.html
Some of the responses were quite interesting.  For example, J has a  
"Tacit" mode which lets you prove equivalence of certain operations  
like commutativity of addition.  I.e. J allows "meta operations" on  
algorithms.

Just click on the "next message" link in the above to follow the  
conversation.  Note that Ken himself, along with Roger Hui jumped  
into the fray!

I *gotta* write all this up!

     -- Owen

Owen Densmore   http://backspaces.net


On Dec 28, 2006, at 12:15 PM, Owen Densmore wrote:

> Here's a more recent Ken Iverson discussion on Computers and
> Mathematical Notation:
>    http://tinyurl.com/ym8r64
> or
>    http://www.cacs.louisiana.edu/~mgr/404/burks/language/apl/camnweb/
> camn.htm
>
> This is J based, rather than APL.
>
>      -- Owen
>
> Owen Densmore   http://backspaces.net
>
>
> On Dec 28, 2006, at 12:00 PM, Owen Densmore wrote:
>
>> First of all, a big THANKS for all the interesting ideas.  I've been
>> trying to get my brain around all this for quite some time.  And I
>> think its time I sit down and start writing on the divide between
>> Math and Computing.
>>
>> One of the more interesting discussions on this topic comes from the
>> APL/Ken Iverson world.  APL (A Programming Language) used a concise
>> mathematical notation for its syntax.  It was quite a hit at Xerox in
>> the early to mid '70s and indeed was considered a great rapid
>> prototyping language.
>>
>> One of Iverson's ideas was that mathematical notation was flawed and
>> could easily be fixed by focusing on making it more parseable and
>> less ambiguous.  His 1979 Turing Award lecture was a wonderful
>> summary of these ideas:
>>    Notation as a Tool of Thought (1979 Turing Award Lecture)
>>    by Kenneth E. Iverson, Communications of the ACM,
>>    Volume 23, Number 8, August 1980.
>>      http://elliscave.com/APL_J/tool.pdf
>>
>> In a sense, Ken was the one of the pioneers poking at the topic we're
>> discussing.  I suspect Turing, Von Neuman, and others were there too.
>>
>> Ken's APL work has been carried on by Ken's son Eric and Roger Hui,
>> both of whom worked closely with Ken.  APL has been morphed into the
>> J Programming Language:
>>    http://en.wikipedia.org/wiki/J_programming_language
>>
>> I've taken a run at J with some success.  Its reasonably cross
>> platform.  But boy, the learning curve is steep!  The power of J,
>> however, is considerable.  If any FRIAMers start in on J, let me
>> know.  These sites are representative of the leaders of the J
>> community:
>>    http://olegykj.sourceforge.net/
>>    .. and all the External links at the end of the Wikipedia article.
>>
>>      -- Owen
>>
>> Owen Densmore   http://backspaces.net
>>
>>
>>
>>
>> ============================================================
>> FRIAM Applied Complexity Group listserv
>> Meets Fridays 9a-11:30 at cafe at St. John's College
>> lectures, archives, unsubscribe, maps at http://www.friam.org
>
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9a-11:30 at cafe at St. John's College
> lectures, archives, unsubscribe, maps at http://www.friam.org

[Marcus G. Daniels-3]

If you like a function-level programming the language Joy offers a pure
approach:

http://www.latrobe.edu.au/philosophy/phimvt/joy/j08cnt.html

[Owen Densmore]

I happened across this book while searching on the math/computer divide.
   Discrete Mathematics Using a Computer
   http://www.dcs.gla.ac.uk/~jtod/discrete-mathematics/
Here's the manual for the software tools (Haskell) used:
   http://www.dcs.gla.ac.uk/~jtod/discrete-mathematics/StdmMan.pdf

A few of us have mentioned Haskell, a few attached, which the book  
uses.  Could any FRIAMers familiar with Haskell elaborate a bit more?

     -- Owen

Owen Densmore   http://backspaces.net

Begin forwarded message:

> From: "Eric Smith" <desmith at santafe.edu>
> Date: December 28, 2006 7:50:44 AM MST
> To: The Friday Morning Applied Complexity Coffee Group  
> <friam at redfish.com>
> Subject: Re: [FRIAM] Mathematical Search and Regular Expressions
>
> Hi Friam,
>
> Returning from music to the question of searching for mathematical
> expressions.  This may be foolish, but what about using a functional
> programming language, such as Haskell, as a "standard format" for
> searchable math expressions?  It reads enough like math that it
> wouldn't be very difficult to learn, and the context of an executable
> code ensures a form of validity testing by the person initiating the
> query (make sure it evaluates correctly on your own machine, then
> submit the code as a search string).  It wouldn't be necessary that a
> search engine support all forms of representation initially; it would
> be enough to support one form in a useful way.
>
> I want to imagine, though this is not well thought out, that one wants
> a definitional language rather than an assignment language, even if
> evaluating the expression on some standard set of inputs would be one
> criterion for assigning it a mathematical "identity".  Even better, of
> course, would be to have criteria for a "normal form" of some kind, so
> that among the possible changes of variable in a single equation,
> automatic conversions could select a particular one as the search
> standard.  This would be along the lines of using a symbolic package
> as an engine to try to relate different representations of equivalent
> expressions.
>
> Does this add anything to what can be done now?
>
> Eric

Begin forwarded message:

> From: "Marcus G. Daniels" <mgd at santafe.edu>
> Date: December 28, 2006 10:06:51 AM MST
> To: The Friday Morning Applied Complexity Coffee Group  
> <friam at redfish.com>
> Subject: Re: [FRIAM] Mathematical Search and Regular Expressions
>
> Eric Smith wrote:
>> Returning from music to the question of searching for mathematical
>> expressions.  This may be foolish, but what about using a functional
>> programming language, such as Haskell, as a "standard format" for
>> searchable math expressions?
> Some of the popular functional programming languages like ML (or  
> OCaml)
> take the perspective that programmers may find it easier to think in
> terms of loops and side effects than recursion and monads, but even if
> that is true, programmers are not the concern.   Mathematica is  
> also one
> of these languages that can be used in a functional way but also  
> provide
> imperative programming features.   It might be tempting just to use
> Mathematica, but of course it's a proprietary thing, which might  
> not be
> ideal for some environments or audiences.  In contrast, Haskell is
> purely functional and a new set of conventions built on it would limit
> the risk that junk (that was hard to search or grok) could sneak in  
> and
> complicate things..

Begin forwarded message:

> From: Carl Tollander <carl at plektyx.com>
> Date: April 20, 2005 10:22:44 AM MDT
> To: Wedtech at redfish.com
> Subject: [WedTech] more non-remunerative fun
> Reply-To: carl at plektyx.com, Wedtech at redfish.com
>
> Just when I thought it was safe to start coding....
> http://lambda-the-ultimate.org
> http://etymon.blogspot.com/
> http://www.kimbly.com/blog/cat_languages.html
> These are language design blogs.  Beware.
>
> Has anybody in the group played with the Haskell language?*
> *http://www.haskell.org*
> *There appears to be a lot of activity for future languages in
> the functional programming space.  Haskell could clearly
> compete in terms of conciseness (concision?)  with some of the  
> scripting
> languages we've been considering.
>
> I came to the above links roundabout looking for prior work
> connecting RDF with Category Theory.  Along the way,
> http://www.kowari.org/  ( a metadata storage facility ) might be  
> worth checking out for
> its Jena hooks.  One of the Kowari head programmers is
> doing a PhD thesis on Complexity (that's SFI-style definition) in
> emergent software metrics.
>
> carl

[Marcus G. Daniels-3]

I'd say there are several dimensions to consider..

1) Assignments or not:  Are there side effects to operators?  Is it
possible to directly store to memory locations or bind values to variables?

2) Combinators or not:  Does application of a function involve named
parameters, or are values curried into combinations of functions?

3) A presence of a typing system.  To what extent can compiler can
deduce correct usage of an object from context (without a lot of fuss
declaring things)

Lisp variants are mostly functional, with dialects like DSSSL Scheme
being purely functional and dialects like R and Common Lisp generally
facilitating it but not insisting on it.   I mention Lisp because one of
the first and most famous symbolic math packages, Macsyma is written in
Lisp, as are simpler systems like JACAL.

http://en.wikipedia.org/wiki/Macsyma
http://maxima.sourceforge.net  (Open source fork -- incidentally it can
export TeX)
http://www-swiss.ai.mit.edu/~jaffer/JACAL.html

As I understand it, J has #1 and #2, but not much of #3.   Haskell has
all three.   I think it safe to say that Haskell gets the most attention
from academic researchers, but there are perhaps other functional
languages that get broader or more intensive use in practice, e.g. ML,
OCaml, Erlang.

In most languages it is possible to implement function curries (#2) and
make programs easier to follow or even faster (e.g. when iterating over
set of things only passing the parameters that per the iteration and not
all of the values they need to calculate each value).  In GNU C, for
example, there are nested functions, and packages like
http://www.haible.de/bruno/documentation/ffcall/trampoline/trampoline.html 
will do the job.  Here's an example of how it can be done in Scheme:  
http://www.engr.uconn.edu/~jeffm/Papers/curry.html

However, for the purposes of expressing equations/calculations in a
clear way, and making it easy to reason about those forms (either for a
computer/compiler or a human), it's useful to pull them all together in
a unified language as Haskell does (as do others like Mercury).    And
from a purely practical point of view, no more nasty stuff like memory
alias identification as is needed in C, etc.