Re: Design Patterns and Functional programming

Dmitry A. Kazakov wrote:
? If side effect is functional, then I don't what to say. At least it
implies that assignment is functional too.

Exactly, yes.

Absolutely. This never had anything to do with a purely functional model.

This raises questions. What is left?

Impure functional programming languages like Mathematica, Lisp, Scheme,
OCaml, Standard ML and Scala.

How much functional is impurely functional?

Depends who you ask. :-)

Why impurity is needed?

Impurity is not required, as purely functional languages do exist, but it
offers a different set of trade-offs that are preferable for certain
classes of user. In particular, impure functional languages are among the
fastest languages in existence whereas purely functional languages tend to
trail with dynamically typed languages as the purity requires laziness
(thunks) and graph traversal for evaluation.

How much of impurity one would require in an average project?

I use impurity quite a bit in OCaml and F#. In F#, it is essential for
interoperability with the rest of .NET, which imposes mutability everywhere
to horrible effect. In OCaml, impurity is simply easier under certain
circumstances.

As Daniel mentioned, anything handling user inputs can be written elegantly
(avoiding a rats nest of dependencies) using event-based programming and
the model-view-controller design pattern. So I use impurity extensively in
GUI code.

Rewriter is defined as a function,

A pattern match.

No, a pattern match gives yes/no

What do you mean by this?

Pattern is a function which takes a chain of letters from some alphabet
and yields true or false. When the result is true, it is said that the
pattern matches the chain.

Ok. In languages like OCaml, patterns can match trees as well as sequences.

Integrating pattern matching into a statically typed language allows
programs to be statically checked more thoroughly and greatly improves
performance by allowing pattern matches to be compiled and optimized
statically.

Why? What is the subject of matching. Some strings (the program
processes), or the program's source code? In either case I see no relation
to static typing. Maybe you mean types matching?

In these languages, sum types (known as "variant" types) are a core part of
the type system and complement product types. A sum type presents
alternatives (like a tagged union in C). For example, a binary tree:

# type t =
| Empty
| Node of t * t;;
type t = Empty | Node of t * t

and values may be constructed of this type:

# Node(Node(Empty, Empty), Empty);;
- : t = Node (Node (Empty, Empty), Empty)

Note that the type of this value was automatically inferred to be the
type "t".

Pattern matching is the only way to deconstruct such data structures in
these languages. For example, a rewriter:

# let rec rewrite rule = function
| Empty as t -> rule t
| Node(l, r) -> rule(Node(rewrite rule l, rewrite rule r));;
val rewrite : (t -> t) -> t -> t = <fun>

Note that the type is automatically inferred to be a higher-order function
handling functions over "t" and a value of type "t". Moreover, the compiler
uses the definition of the type "t" to check that pattern matches over
values of the type "t" are both exhaustive (account for both Empty and Node
in this case) and not redundancy (e.g. do not account for Empty twice).

This is very beneficial in practice as it catches a lot of errors. Moreover,
this form of static checking requires the pattern matcher to be integrated
with the type system.

In the case of OCaml, you can even have the sum type inferred and statically
checked:

# let rec rewrite rule = function
| `E as t -> rule t
| `N(l, r) -> rule(`N(rewrite rule l, rewrite rule r));;
val rewrite :
([> `E | `N of 'a * 'a ] -> 'a) -> ([< `E | `N of 'b * 'b ] as 'b) -> 'a =
<fun>

A stage inside a compiler might alter an abstract syntax tree to remove
certain kinds of node. Using the above approach, the compiler can prove
that the functions that make up this stage remove the constructors and the
inferred sum type of the result will be a new abstract syntax tree that has
fewer kinds of node.

For example, the following function substitutes variables for their values
and, consequently, removes the need for the Var node in the resulting
abstract syntax tree:

# let rec subst vars = function
| `Int _ as e -> e
| `Var v -> List.assoc v vars
| `Add(f, g) -> `Add(subst vars f, subst vars g);;
val subst :
('a * ([> `Add of 'b * 'b | `Int of 'c ] as 'b)) list ->
([< `Add of 'd * 'd | `Int of 'c | `Var of 'a ] as 'd) -> 'b = <fun>

Note that the resulting tree has the inferred type "[> `Add of 'b * 'b |
`Int of 'c ] as 'b" without Var.

These are implemented as "active patterns"
in F# and are very useful under certain circumstances. For example, you
can write active patterns that deconstruct XML documents directly from
the .NET representation. Then you can use pattern matching to manipulate
XML documents quickly and easily from F# code.

Looks like fighting some architectural problems to me...

I don't really see a better way around this. The conventional OO approach
used by the XML libraries of Java and .NET is certainly horrendous in
comparison.

I'm assuming there are design patterns representing special cases of
pattern matching, just as there are design patterns representing special
cases of first-class functions.

It is a too wide stretch, and I think it is wrong. The whole idea of
pattern matching is to ignore the semantics of the thing being analysed.
In some cases it gives you an advantage of doing the job quickly without
much clutter. When we talk about design patterns, the idea is quite
opposite. Design patterns heavily rely on the semantics while trying to
ignore any syntactical differences.

Well, there are certainly problems if you overuse pattern matching.
Particularly in languages that don't support views (as F# does).

I wrote a GUI editor for some technical presentation software and my
extensive use of pattern matching in its core ties it to the data structure
(lots of lists). If we want to handle a more asymptotically efficient data
structure then I would need to rewrite it.

How a user of the class could design a program in terms of these
properties?

Apply the appropriate arguments.

That's too late. The whole idea is to know properties in advance during
design.

Both of these are addressed by parameterizing via a functor (a
higher-order module) rather than a higher-order function. A monadic style
is another alternative.

I.e. by screwing the paradigm.

Functors are a core component of the ML family of languages. I wouldn't say
that using them is "screwing the paradigm" in any way. Indeed, they are
just a static version of a higher-order function.

Hmm, I bet some OO design patterns correspond to functors. An ordinary
module is probably a Singleton pattern. So a functor might be an Abstract
Factory for making Singletons.

2. How would you extend / modify a rewriter?

Using a continuation.

That is same as composition. BTW, this is a great problem of many OO
languages too. They also use extension = composition with some epilogue
and prologues, or overriding. That is too limiting in many cases. A
typical example is dispatching constructors / destructors.

I don't really understand this. Can you give an example?

The problem is, to dispatch to some virtual method from the constructor.
In terms of functional decomposition you need to inject some code into the
body of another function, here a constructor. The problem is that at this
point the object is still under construction, so you cannot pass to object
to the target. It can only be solved by proper typing.

I see. Yes. I've certainly hit that problem a few times with OO. I think
higher-order objects are the solution: you just pass an object to the
constructor of another object. Of course, this leads you straight into
object-hell, where you start creating objects for everything unnecessary,
as Java and .NET do for any non-trivial sets of parameters.

I think the only way we can justify a conclusion is by looking at some
real examples. Can you think of any equivalent compilers written in both
functional and OO styles? Prolog implementations, maybe.

You need somebody to pay for such study. A typical software maintenance
period is 20+ years. Then you will know the answer, which probably nobody
will hear anyway.

Yes.

Actually it is much simpler. Ask you senator to pass a law making
no-warranty licenses illegal. You will be amazed how quickly the number of
languages will reduce.

:-)

If you give something away from FP and
OO-preachers do the same, then you will probably meet somewhere at the
optimum. Stateless design is a great advantage *when* appropriate.

I'm not advocating statelessness though, only first-class functions.

Oh, that is OK. Surely subroutines have to be ADTs. Why do you think that
this would be anti-OO?

I would call it an excellent complement to OO rather than anti-OO. Languages
like OCaml and F# demonstrate that these methods can usefully coexist. I'm
still trying to pin down the applications for which I would choose OO and
those for which I would choose a functional style though...

Well, an immutable value cannot have state. Mutable values do, of course.

No, there is no such thing as a mutable value. Mutable can be a variable,
parameter, object. They are functions mapping execution states onto
values. Switching states just selects another value without changing them.

This is just nomenclature. In OCaml, a mutable reference is a type of value:

# let a = ref 4;;
val a : int ref = {contents = 4}

--
Dr Jon D Harrop, Flying Frog Consultancy
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?usenet
.

Relevant Pages

  • Universal Translators - undoing babel
    ... the hologram to encode it as a specific image. ... The interference pattern diffracts beams of light creating ... sound waves can be interfered and diffracted as well. ... sounded natural continuous and in each of our respective languages. ...
    (rec.arts.startrek.tech)
  • Re: Design Patterns and Functional programming
    ... OCaml, Standard ML and Scala. ... Impurity is not required, as purely functional languages do exist, but it ... this form of static checking requires the pattern matcher to be ... compiler use to parse literals of the type t, that is up to the compiler. ...
    (comp.object)
  • Re: Scheme closures
    ... It's these latter considerations that really limit syntax-rules. ... were writing the macro in a good way. ... > who uses argument pattern matching, ... I like the sort of pattern-matching used in functional languages ...
    (comp.lang.lisp)
  • Re: ML-style pattern matching in C-like languages
    ... > for introducing some form of ML-style pattern matching ... > in C-like languages? ... pattern-action, the match primitive selects a pattern ... The main difference is that the discrimination ...
    (comp.compilers)
  • Re: Design Patterns and Functional programming
    ... Impure functional programming languages like Mathematica, Lisp, Scheme, ... a pattern match gives yes/no ... What is the subject of matching. ... body of another function, here a constructor. ...
    (comp.object)
Quantcast