Is it possible in Lisp to implement call-by-pattern,
as in the functional language Hope?
In call-by-pattern you do pattern matching on the arguments of a
function, to decide what to do with them.
Moth-eaten factorial example: (Hope code follows)
! myfact is a function that takes a number to a number.
dec myfact : num -> num;
! if the arg to myfact is a number, return n * myfact of n-1.
--- myfact (n) <= n * myfact(n-1);
! if the arg to myfact is 0, return a 1.
--- myfact (0) <= 1;
! example of a call to myfact().
myfact(4);
>> 24 : num
The neat thing in Hope is that you can write the constraints
(or definitions) in any order; the most specific pattern will
be selected for a given call. So the function myfact() defined
above will in fact terminate (for small positive integer values
of n -- Hope generally uses fixnums), even tho' the definition
is "backward."
So I'm wondering if something like this could be done in Lisp...
(I'm just doodling here...
(defun fact #p( 0 )
1)
(defun fact #p( n )
(* n (fact (- n 1))))
where #p(...) is my home-made syntax for a "pattern",
and these separate "definitions" operationally
coalesce into roughly what you think they should:
(defun fact (n)
(cond ((eql n 0)
1)
(t
(* n (fact (- n 1))))))
The syntax I've introduced above --- #p(...) for patterns ---
is nothing I'm wed to. It's just the first thing that popped
into my mind, thinking of #c(..) for complex values. So if you
have a more Lisp-like and/or cleaner alternative, feel free
to improve on my first effort.
One might wonder -- why would anyone want to do this? Is there
any advantage to call-by-pattern over the usual parameter-association
mechanism we use in Lisp?
I don't have a solid answer to that, beyond --- call-by-pattern
seems to give us function definitions that are simpler
to read, for some cases. Conventionally, we gobble up an argument
list, examine the args, possible pre-digest them somewhat, then
branch into various alternatives to really make progress towards
the answer we want. In call-by-pattern, some (or maybe all) of
the "deciding" happens up-front, right when you specify the argument-list
to the function. It's a declarative approach to problem-solving,
and while I'm not convinced that this is The One True Way we
should solve everything, it seems to me it has its uses...
So I'm curious -- do you think something like this could be
implemented in Lisp? (By "Lisp", I mean "Common Lisp").
Thanks in advance-
-Lou
In article <············@netra.msu.montana.edu> , Louis Glassy
<······@acheta.nervana.montana.edu> wrote:
>
>Is it possible in Lisp to implement call-by-pattern,
>as in the functional language Hope?
>
>In call-by-pattern you do pattern matching on the arguments of a
>function, to decide what to do with them.
>
>Moth-eaten factorial example: (Hope code follows)
>
>! myfact is a function that takes a number to a number.
>dec myfact : num -> num;
>
>! if the arg to myfact is a number, return n * myfact of n-1.
>--- myfact (n) <= n * myfact(n-1);
>
>! if the arg to myfact is 0, return a 1.
>--- myfact (0) <= 1;
>
>! example of a call to myfact().
>myfact(4);
>>> 24 : num
>
>The neat thing in Hope is that you can write the constraints
>(or definitions) in any order; the most specific pattern will
>be selected for a given call. So the function myfact() defined
>above will in fact terminate (for small positive integer values
>of n -- Hope generally uses fixnums), even tho' the definition
>is "backward."
>
>So I'm wondering if something like this could be done in Lisp...
>
>(I'm just doodling here...
>
>(defun fact #p( 0 )
> 1)
>
>(defun fact #p( n )
> (* n (fact (- n 1))))
>
>where #p(...) is my home-made syntax for a "pattern",
>and these separate "definitions" operationally
>coalesce into roughly what you think they should:
>
>(defun fact (n)
> (cond ((eql n 0)
> 1)
> (t
> (* n (fact (- n 1))))))
>
>The syntax I've introduced above --- #p(...) for patterns ---
>is nothing I'm wed to. It's just the first thing that popped
>into my mind, thinking of #c(..) for complex values. So if you
>have a more Lisp-like and/or cleaner alternative, feel free
>to improve on my first effort.
>
>One might wonder -- why would anyone want to do this? Is there
>any advantage to call-by-pattern over the usual parameter-association
>mechanism we use in Lisp?
>
>I don't have a solid answer to that, beyond --- call-by-pattern
>seems to give us function definitions that are simpler
>to read, for some cases. Conventionally, we gobble up an argument
>list, examine the args, possible pre-digest them somewhat, then
>branch into various alternatives to really make progress towards
>the answer we want. In call-by-pattern, some (or maybe all) of
>the "deciding" happens up-front, right when you specify the argument-list
>to the function. It's a declarative approach to problem-solving,
>and while I'm not convinced that this is The One True Way we
>should solve everything, it seems to me it has its uses...
>
>So I'm curious -- do you think something like this could be
>implemented in Lisp? (By "Lisp", I mean "Common Lisp").
>
>Thanks in advance-
>
>-Lou
>
Heh, heh. <g> A new way to write factorial in Lisp:
? (defgeneric factorial (n))
#<STANDARD-GENERIC-FUNCTION FACTORIAL #x4EE4446>
? (defmethod factorial ((n (eql 0))) 1)
#<STANDARD-METHOD FACTORIAL ((EQL 0))>
? (defmethod factorial ((n integer)) (* n (factorial (1- n))))
#<STANDARD-METHOD FACTORIAL (INTEGER)>
? (factorial 6)
720
?
Seriously, though, you probably want something more general than what your
example suggests. CLOS methods can specialize on EQL objects (same object
or number). To do _pattern_ matching, you'll have to do some work. There
are some examples of unification pattern matchers in the Lisp literature;
see "Paradigms of Artificial Intelligence Programming: Case Studies in
Common Lisp", Norvig, 1992, Morgan Kaufmann, ISBN 1-55860-191-0 for one
example.
I don't know your point of reference (Hope), so I don't know how general
you'd like your matcher to be. There's a spectrum ranging from simple
identity (the CLOS example) to full unification.
As far as your #p(...) goes, that's an unfortunate choice, since Common Lisp
reserves #p as a reader macro for pathnames, as in #p"/foo/bar/baz.lisp".
But, again, you _can_ introduce new syntax using reader macros. Take a look
at chapter 23 of the Common Lisp Hyperspec at
<http://www.harlequin.com/books/HyperSpec/>.
---
David B. Lamkins <http://www.teleport.com/~dlamkins/>
In article <············@netra.msu.montana.edu>, Louis Glassy
<······@acheta.nervana.montana.edu> wrote:
> Is it possible in Lisp to implement call-by-pattern,
> as in the functional language Hope?
Sure. He is an example for something mirnada-like.
(defmacro miranda (function-name (arg) &body forms)
`(defun ,function-name (,arg)
(select-match ,arg . ,forms)))
(miranda perms (x)
() => '(())
(_ . _) => [(cons a p)
(a <- x)
(p <- (perms (remove a x :count 1)))])
> I don't have a solid answer to that, beyond --- call-by-pattern
> seems to give us function definitions that are simpler
> to read, for some cases.
Lisp already has detected that structures/classes sometimes are more
useful. Using lists as the one universal data structure is old style,
especially when your data structures are getting complex.
Using positional list patterns and writing a lot
of functions with them easily creates a maintenance
nightmare (you sure would need tools to help you update the patterns, etc).
--
http://www.lavielle.com/~joswig
In article <·······················@194.163.195.67>, ······@lavielle.com
(Rainer Joswig) wrote:
>Sure. He is an example for something mirnada-like.
Damn. And I wrote http://www.westfalen.de/hugo/lisp/defmatch.lsp ;-)
(ok, it was more training in macros, so it was worth the effort even if it
wasn't that usefull)
bye, Georg
--
http://www.westfalen.de/hugo/