Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #46900 > unrolled thread

"pattern matching as inverting functions" for "languages without named parameters"

Back to article view | Back to comp.lang.forth

Contents

  "pattern matching as inverting functions" for "languages without named parameters" Andreas Wagner <andreas.wagner@lowfatcomputing.org> - 2016-05-03 11:24 -0700
    Re: "pattern matching as inverting functions" for "languages without named parameters" Andreas Wagner <andreas.wagner@lowfatcomputing.org> - 2016-05-03 11:42 -0700
    Re: "pattern matching as inverting functions" for "languages without named parameters" anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-05-06 14:56 +0000
      Re: "pattern matching as inverting functions" for "languages without named parameters" anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-05-06 16:35 +0000
        Re: "pattern matching as inverting functions" for "languages without named parameters" Paul Rubin <no.email@nospam.invalid> - 2016-05-06 09:43 -0700
          Re: "pattern matching as inverting functions" for "languages without named parameters" anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-05-07 13:57 +0000
            Re: "pattern matching as inverting functions" for "languages without named parameters" Paul Rubin <no.email@nospam.invalid> - 2016-05-07 17:51 -0700
              Re: "pattern matching as inverting functions" for "languages without named parameters" anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-05-08 14:02 +0000
      Re: "pattern matching as inverting functions" for "languages without named parameters" "WJ" <w_a_x_man@yahoo.com> - 2016-05-07 14:51 +0000

#46900 — "pattern matching as inverting functions" for "languages without named parameters"

Prompted by Brad Nelson's talk "Ruminations on Text Processing" and the ensuing discussion ( https://youtu.be/_AXPVwpshUU?t=1h45m12s ), I Googled some thoughts and stumbled upon this paper:

http://micsymposium.org/mics_2009_proceedings/mics2009_submission_72.pdf

Rather than viewing pattern matching as some separate library to be implemented over strings, pattern matching is thought of as the inverse of functions ( or rather of words).

The composition ( or rather juxtaposition) of an inverse with an inverse is an inverse. I would think one would only need to manually implement the inverses of words in the nucleus wordset of a Forth interpreter.

The paper does not attempt conditionals or recursion.

Perhaps for conditionals, what we really want is the converse ( http://www.mathwords.com/c/converse.htm ) not the inverse ( http://www.mathwords.com/i/inverse_conditional.htm )?

I haven't yet thought about inverting/matching recursive words.

[toc] | [next] | [standalone]

#46902

In a similar vein there's some work done by various people on "[software] reversible Forth,"

http://strangepaths.com/reversible-computation/2008/01/20/en/

"A Reversible Computing Approach to Forth Floating Point." https://www.complang.tuwien.ac.at/anton/euroforth2007/papers/stoddart.pdf

"Implementing Sets for Reversible Computation" http://www.complang.tuwien.ac.at/anton/euroforth/ef02/stoddart02b.pdf

"Using reversible computing to achieve fail-safety" http://www.adelard.com/papers/i97_revh.pdf

"Wrongforth - A reversible Forth" http://www.complang.tuwien.ac.at/anton/euroforth/ef09/papers/wodni/wrongforth.pdf

By the way, simply writing reversible software on a conventional computer will not solve heat dissipation and current consumption, even for the bijective Boolean NOT function. You would need reversible hardware like the Pendulum architectures: http://dspace.mit.edu/handle/1721.1/36039

[toc] | [prev] | [next] | [standalone]

#46936

Andreas Wagner <andreas.wagner@lowfatcomputing.org> writes:
>Prompted by Brad Nelson's talk "Ruminations on Text Processing" and the ensuing discussion ( https://youtu.be/_AXPVwpshUU?t=1h45m12s ), I Googled some thoughts and stumbled upon this paper:
>
>http://micsymposium.org/mics_2009_proceedings/mics2009_submission_72.pdf
>
>Rather than viewing pattern matching as some separate library to be implemented over strings, pattern matching is thought of as the inverse of functions ( or rather of words).

This is not about string pattern matching, but, in the first part,
about constructor pattern matching (e.g., different constructors for
Cons nodes and Nil nodes, and pattern matching of these node types) as
used in functional programming.  The paper then discusses various
forms of inverted-function construction, but then does not get back to
the original example of implementing the sum (of list elements) with
pattern matching, but instead goes into an example of using the
feature for unit conversion, which is cute, but makes me wonder about
the general appeal.

However, I think that his idea is that the inverse of the constructor

<cons> ( car cdr -- list )

has the stack effect ( list -- car cdr ), and gives an exception if
"list" is not a cons cell.  And he uses the syntax 

: sum ( list -- n )
       {
              { [ <nil> ] [ 0 ] }
              { [ <cons> ] [ sum + ] }
       } case ;

for pattern matching.  The [ <nil> ] and [ <cons> ] parts are inverted
with undo; if the inverted functions match (do not give an exception),
the next quotation is performed, otherwise the next pattern is tried.
The ( car cdr ) coming out of the inverted <cons> is passed to [ sum + ].

Has a certain cuteness factor, although in this case one would
probably rather use a list-reducing combinator rather than direct
pattern matching.  But I guess that this kind of pattern matching
could be useful in cases where you deal with lots of differnt node
types in only a few places, such as in compilers.

>The paper does not attempt conditionals or recursion.
>
>Perhaps for conditionals, what we really want is the converse ( http://www.mathwords.com/c/converse.htm ) not the inverse ( http://www.mathwords.com/i/inverse_conditional.htm )?
>
>I haven't yet thought about inverting/matching recursive words.

His method for constructing the inverse requires total inlining of
everything, so recursive words are out of scope for his method.
Concerning conditionals, they might be needed to be treated similar to
map (see "Pop inverses in Section 3.2).

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2016: http://www.euroforth.org/ef16/

[toc] | [prev] | [next] | [standalone]

#46941

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>But I guess that this kind of pattern matching
>could be useful in cases where you deal with lots of differnt node
>types in only a few places, such as in compilers.

However, I guess that object-oriented dispatch fulfills this role
nicely already in Factor, so the structure pattern-matching looks like
a solution looking for a problem.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2016: http://www.euroforth.org/ef16/

[toc] | [prev] | [next] | [standalone]

#46942

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> However, I guess that object-oriented dispatch fulfills this role
> nicely already in Factor, so the structure pattern-matching looks like
> a solution looking for a problem.

Lisp and Python have features like that, and they are very useful, even
though Python doesn't have conses (it has vector-like lists and tuples).

[toc] | [prev] | [next] | [standalone]

#46976

Paul Rubin <no.email@nospam.invalid> writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> However, I guess that object-oriented dispatch fulfills this role
>> nicely already in Factor, so the structure pattern-matching looks like
>> a solution looking for a problem.
>
>Lisp and Python have features like that, and they are very useful, even
>though Python doesn't have conses (it has vector-like lists and tuples).

Can you present an example use that cannot be solved with same-length
or shorter programs with OOP or higher-order words?

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2016: http://www.euroforth.org/ef16/

[toc] | [prev] | [next] | [standalone]

#46984

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>Lisp and Python have features like that
> Can you present an example use that cannot be solved with same-length
> or shorter programs with OOP or higher-order words?

It's used all the time, e.g. the Python equivalent of the Forth word
/MOD is the divmod function:

   quotient, remainder = divmod(num, divisor)

divmod returns a pair, and in that example I bound the two elements
of the pair into 'quotient' and 'remainder' through destructuring
(that's the Lisp term, I don't remember if there's a Python term).

[toc] | [prev] | [next] | [standalone]

#46986

Paul Rubin <no.email@nospam.invalid> writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>>Lisp and Python have features like that
>> Can you present an example use that cannot be solved with same-length
>> or shorter programs with OOP or higher-order words?
>
>It's used all the time, e.g. the Python equivalent of the Forth word
>/MOD is the divmod function:
>
>   quotient, remainder = divmod(num, divisor)
>
>divmod returns a pair, and in that example I bound the two elements
>of the pair into 'quotient' and 'remainder' through destructuring
>(that's the Lisp term, I don't remember if there's a Python term).

Ok, that's a solution to a problem that Factor probably does not have
(Forth certainly does not have it).  That still leaves the question
open for what Factor would need ML-style pattern matching.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2016: http://www.euroforth.org/ef16/

[toc] | [prev] | [next] | [standalone]

#46977

Anton Ertl wrote:

> : sum ( list -- n )
>        {
>               { [ <nil> ] [ 0 ] }
>               { [ <cons> ] [ sum + ] }
>        } case ;

OCaml:

Not tail-recursive (can blow the stack):

let rec sum = function
    []      -> 0
  | a::more -> a + sum more ;;


Tail-recursive:

let sum list =
  let rec loop result = function
      []      -> result
    | a::more -> loop (result + a) more
  in loop 0 list ;;


Testing the tail-recursive version:


sum (Array.to_list (Array.init 20_000 abs)) ;;
 ===>
199990000

-- 
If confirmed, Garland would be the fourth Jewish justice on the nation's
highest court, which is comprised entirely of Jews and Catholics. The three
current Jewish members of the Supreme Court are Ruth Bader Ginsburg, Elana
Kagan, and Stephen Breyer.
www.jta.org/2016/03/16/news-opinion/united-states/obama-to-name-jewish-federal-judge-to-supreme-court

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web