Design Patterns and Functional programming

Hi,
which part of
> > if your language doesn't have a heap, you can just check, when exiting
> > from an activation (e.g., let block or function) looking at the
> > functional values bound to names in the environment (or still being
> > used in a "temporary value" memory area, where you hold the
> > intermediate results of the computation) which one of the retained
> > envs is not needed anymore, and throw away them.
didn't you understand?
maybe I could be clearer..
let's say you store your functional objects (I'm not talking about
object in the oop sense) as (for simplicity) couples of the like
(f,env), and your activation records contain (a pointer to) the non
local env (static chain).
where f is something representing the function and env represents the
enclosed non local environment. given a retained environment e1, you
can throw it away when exiting from an activation when:
1) it doesn't belong to the dynamic chain of environments (it's not
cyrcular, it's just a stack)
2) you can't find references to the e1 env in the functional objects
stored in the temporary value stacks or bound to a name in other
environments which are in the dynamic chain of envs
3) e1 doesn't belong to the static chain of envs of any functional
object stored in the temporary value stacks or bound to a name in the
dynamic chain of envs.

essentially, you can't throw away the thing in this situation:
envstack:
|S|<- top
|R| S indicates "standard envs"
|R| R indicates "retained envs"
....
|S|
because S could use bindings found in the R environments below it, and
in this situation
|R| <- top (let's call this env e1)
....
|S|
if the environments below R (or the temporary values stacks of the |
S| activations) contain functional objects (f,e') where e'=e1 or e'
belongs to the static chains of f (which you can see following the
static chain of the activation record -again, it's a stack, so nothing
cyclic- of the activations having e' as the enclosed env).

maybe I'm wrong, but this seems to me more like a bunch of linear
searches. no cyclic heaps.
On Jul 28, 11:55 am, Jon Harrop <j...@ffconsultancy.com> wrote:
> lay... wrote:
> > On Jul 18, 9:48 am, Jon Harrop <j...@ffconsultancy.com> wrote:
> >> Dmitry A. Kazakov wrote:
> >> > Ada is functional, cool.
>
> >> Ada doesn't support closures. For one thing, closures require a garbage
> >> collector that can handle cyclic heaps.
>
> > This seems incorrect to me. A simple functional language doesn't need
> > a heap (if the language, for example, just handles integer, boolean or
> > functional values, why whould you need that??). Closures are a matter
> > of environments, and when the language is statically scoped, of
> > environment retention.
> > if your language doesn't have a heap, you can just check, when exiting
> > from an activation (e.g., let block or function) looking at the
> > functional values bound to names in the environment (or still being
> > used in a "temporary value" memory area, where you hold the
> > intermediate results of the computation) which one of the retained
> > envs is not needed anymore, and throw away them.
>
> How do you determine which one of the envs is not needed any more?
>
> --
> Dr Jon D Harrop, Flying Frog Consultancy
> OCaml for Scientistshttp://www.ffconsultancy.com/products/ocaml_for_scientists/?usenet

ah, I forgot to say, you mark an env as retained when your expression
returns a functional value and you're going to leave that activation,
as in :
let g f x = f x + x in
g (let a = 5 in (function x -> x + a)) 3


in this case, the environment relative to the "let a = 5 in..." will
be marked as retained, because when you exit the activation, you still
need that environment when evaluating (function x -> x + a).
as for determining when you need an environment when exiting an
activation, you do when the expression corresponding to the activation
(here, the let ... thing) evaluates to a function. so (let a=5 in
(function x -> x)) applies as well, the environment will be retained.

On Jul 28, 2:17 pm, "lay..." <lay...> wrote:
> Hi,
> which part of> > if your language doesn't have a heap, you can just check, when exiting
> > > from an activation (e.g., let block or function) looking at the
> > > functional values bound to names in the environment (or still being
> > > used in a "temporary value" memory area, where you hold the
> > > intermediate results of the computation) which one of the retained
> > > envs is not needed anymore, and throw away them.
>
> didn't you understand?
> maybe I could be clearer..
> let's say you store your functional objects (I'm not talking about
> object in the oop sense) as (for simplicity) couples of the like
> (f,env), and your activation records contain (a pointer to) the non
> local env (static chain).
> where f is something representing the function and env represents the
> enclosed non local environment. given a retained environment e1, you
> can throw it away when exiting from an activation when:
> 1) it doesn't belong to the dynamic chain of environments (it's not
> cyrcular, it's just a stack)
> 2) you can't find references to the e1 env in the functional objects
> stored in the temporary value stacks or bound to a name in other
> environments which are in the dynamic chain of envs
> 3) e1 doesn't belong to the static chain of envs of any functional
> object stored in the temporary value stacks or bound to a name in the
> dynamic chain of envs.
>
> essentially, you can't throw away the thing in this situation:
> envstack:
> |S|<- top
> |R| S indicates "standard envs"
> |R| R indicates "retained envs"
> ...
> |S|
> because S could use bindings found in the R environments below it, and
> in this situation
> |R| <- top (let's call this env e1)
> ...
> |S|
> if the environments below R (or the temporary values stacks of the |
> S| activations) contain functional objects (f,e') where e'=e1 or e'
> belongs to the static chains of f (which you can see following the
> static chain of the activation record -again, it's a stack, so nothing
> cyclic- of the activations having e' as the enclosed env).
>
> maybe I'm wrong, but this seems to me more like a bunch of linear
> searches. no cyclic heaps.
> On Jul 28, 11:55 am, Jon Harrop <j...@ffconsultancy.com> wrote:
>
> > lay... wrote:
> > > On Jul 18, 9:48 am, Jon Harrop <j...@ffconsultancy.com> wrote:
> > >> Dmitry A. Kazakov wrote:
> > >> > Ada is functional, cool.
>
> > >> Ada doesn't support closures. For one thing, closures require a garbage
> > >> collector that can handle cyclic heaps.
>
> > > This seems incorrect to me. A simple functional language doesn't need
> > > a heap (if the language, for example, just handles integer, boolean or
> > > functional values, why whould you need that??). Closures are a matter
> > > of environments, and when the language is statically scoped, of
> > > environment retention.
> > > if your language doesn't have a heap, you can just check, when exiting
> > > from an activation (e.g., let block or function) looking at the
> > > functional values bound to names in the environment (or still being
> > > used in a "temporary value" memory area, where you hold the
> > > intermediate results of the computation) which one of the retained
> > > envs is not needed anymore, and throw away them.
>
> > How do you determine which one of the envs is not needed any more?
>
> > --
> > Dr Jon D Harrop, Flying Frog Consultancy
> > OCaml for Scientistshttp://www.ffconsultancy.com/products/ocaml_for_scientists/?usenet

laynor wrote:
> Hi,
> which part of
>> > if your language doesn't have a heap, you can just check, when exiting
>> > from an activation (e.g., let block or function) looking at the
>> > functional values bound to names in the environment (or still being
>> > used in a "temporary value" memory area, where you hold the
>> > intermediate results of the computation) which one of the retained
>> > envs is not needed anymore, and throw away them.
> didn't you understand?

The problem is this bit that you added the second time:

> 1) it doesn't belong to the dynamic chain of environments (it's not
> cyrcular, it's just a stack)

When you say "its not circular", what you really mean is "we're going to
disallow cyclic dependencies" which is actually a fundamental difference
that undermines the whole concept of a closure to the extent that what you
have left are not closures.

So your idea is perfectly sound, it can and has been implemented. The
resulting kind of closure was known as a "downward closure", referring to
the unidirectional references that result. The problem is that disallowing
mutual recursion between closures because they form cyclic dependencies
greatly undermines the utility of the closures themselves, to the extent
that no modern languages restrict themselves to downward closures.

In practice, cyclic dependencies, graphs and networks are all around us.
Everything from metabolic pathways to the world wide web contain cycles. If
you want to write a program that can handle such data, you must be able to
handle cycles.

If you try to write such programs in a language like Ada, for example, you
end up creating an abstract representation of references (pointers) that
allows cycles. Then you implement algorithms to traverse this abstract heap
and, maybe, remove unused parts. So you've written a garbage collector.

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/product...ntists/?usenet

On Sat, 28 Jul 2007 16:28:37 +0100, Jon Harrop wrote:

> If you try to write such programs in a language like Ada, for example, you
> end up creating an abstract representation of references (pointers) that
> allows cycles.

These cycles could in most cases be broken into chains distinct referential
types. In Ada referential types are true types (it also has inferred
referential types a-la C++, so-called anonymous access types, but that's a
different story). So:

type Ptr_1 is access T;
type Ptr_2 is access T;

Ptr_1 := new T;
Ptr_2 := Ptr_1; -- This is illegal, type error

When the types of references are different, a bad infinite recursion is
effectively broken at the types boundaries. BTW, in a language with GC you
will have to do this as well. This is a fundamental design principle. This
way strong and weak references appear. The advantage of a more structured
approach, as opposed to an all-eating collector, is that in most cases, you
know something about the references and thus can beat any statistical
collection strategy by margin. Note also that since Ada 83 the language
standard had been allowing GC, but did not require a compiler vendor to
provide it. Since then no vendor I know cared to implement GC. No customer
asked for! If a vendor did it, would Ada become a functional language?
Obviously no.

> Then you implement algorithms to traverse this abstract heap
> and, maybe, remove unused parts. So you've written a garbage collector.

Yes, but it is a "customized" collector with a predictable behavior for
which you would be able to say far more in advance than for a predefined
collector. You could be able statically estimate memory footprint, or maybe
the response time. Perhaps you would even be able to certify your program
for hazardous environment...

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

hi again, this is getting interesting :-)
I'm not too practical with the names, as I'm italian.. so could you
make simple code examples of downward and upward closures?
common lisp and ocaml examples are welcome.
On 28 Lug, 17:28, Jon Harrop <j...@ffconsultancy.com> wrote:
> lay... wrote:
> > Hi,
> > which part of
> >> > if your language doesn't have a heap, you can just check, when exiting
> >> > from an activation (e.g., let block or function) looking at the
> >> > functional values bound to names in the environment (or still being
> >> > used in a "temporary value" memory area, where you hold the
> >> > intermediate results of the computation) which one of the retained
> >> > envs is not needed anymore, and throw away them.
> > didn't you understand?
>
> The problem is this bit that you added the second time:
>
> > 1) it doesn't belong to the dynamic chain of environments (it's not
> > cyrcular, it's just a stack)
>
> When you say "its not circular", what you really mean is "we're going to
> disallow cyclic dependencies" which is actually a fundamental difference
> that undermines the whole concept of a closure to the extent that what you
> have left are notclosures.
>
> So your idea is perfectly sound, it can and has been implemented. The
> resulting kind of closure was known as a "downward closure", referring to
> the unidirectional references that result. The problem is that disallowing
> mutual recursion betweenclosuresbecause they form cyclic dependencies
> greatly undermines the utility of theclosuresthemselves, to the extent
> that no modern languages restrict themselves to downwardclosures.
>
> In practice, cyclic dependencies, graphs and networks are all around us.
> Everything from metabolic pathways to the world wide web contain cycles. If
> you want to write a program that can handle such data, you must be able to
> handle cycles.
>
> If you try to write such programs in a language like Ada, for example, you
> end up creating an abstract representation of references (pointers) that
> allows cycles. Then you implement algorithms to traverse this abstract heap
> and, maybe, remove unused parts. So you've written a garbage collector.
>
> --
> Dr Jon D Harrop, Flying Frog Consultancy
> OCaml for Scientistshttp://www.ffconsultancy.com/products/ocaml_for_scientists/?usenet

Dmitry A. Kazakov wrote:
> When the types of references are different, a bad infinite recursion is
> effectively broken at the types boundaries. BTW, in a language with GC you
> will have to do this as well. This is a fundamental design principle...

That is not true. For example:

http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/product...ntists/?usenet

JXStern wrote:
> On Sun, 15 Jul 2007 23:57:05 +0100, Jon Harrop <jon@ffconsultancy.com>
> wrote:
>>JXStern wrote:
>>> If this is accurate,
>>> http://en.wikipedia.org/wiki/Continuation_passing_style
>>> I fail to see the virtues of CPS.
>>
>>1. Convert stack allocation into heap allocation.
>>
>>2. Defer computations, e.g. to control invert parsers.
>
> Aren't you the same guy who wants compiler warnings?

Yes.

>>3. Compose computations, e.g. to inject abort tests into asynchronous
>>programs.
>>
>>4. Abstract away purity.
>
> Say what?

Pure and impure implementations can provide the same interface if it is
written in continuation passing style.

> This is all a hash of syntax and runtime features and implementation
> details.

This has nothing to do with syntax or runtime features.

>>> You can pass fnargs in C or C++,
>>
>>You must explicitly find and capture all free variables by hand in C/C++.
>>First-class lexical closures are the automation of this. Moreover, this is
>>practically impossible without garbage collection because the captured
>>values result in a cyclic dependency graph.
>
> Gibberish. Lexical closures. All so you can put variables on a heap
> instead of a stack?

That is not the purpose of lexical closures. Closures encapsulate functions
with their environment, e.g. partially applied arguments.

>>> you can build callbacks in C/C++,
>>
>>You must explicitly encapsulate the function and its environment into a
>>struct or class. Functional languages also automate this.
>
> Could get there without the syntactic tomfoolery.

Automated environment capture is not a syntactic issue.

>>In exactly the same way, very few C and Fortan programs are written in an
>>object-oriented style but this says nothing about the merits of OOP.
>
> Yah, I was a language guy, back when. I know the urge to do something
> more elegant than the next guy, but what wins in the world is simple.
> I mean, tail recursion, I can write a 50,000 line app and do that
> exactly zero times in C. If I wrote it in Scheme or ML, maybe I'd use
> it, I dunno, maybe some, doing map functions of some kind, but then
> anyone doing maintenance on the code three years later, better have
> another fifty IQ points to follow it.

On the other hand, the ML program might be a few orders of magnitude
smaller.

> I see very, very little that has improved since about Algol 60/W,
> except for a little syntactic cuteness you get with objects. The
> dynamic ("weak") typed systems are more fun to hack in and easier to
> extend, but aren't any real quantum leap.
>
> The original topic of design patterns being integrated into language
> features remains vaguely interesting, though the real challenge is
> creating higher level objects and model driven architectures where the
> visible syntax may be even less of an issue.

I think the inference of class hierarchies and the use of pattern matching
are much more interesting.

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/product...ntists/?usenet

H. S. Lahman wrote:
> Responding to Harrop...
>
> > Is there any literature describing how object-oriented design patterns
> > reinvent existing techniques like functional programming?
>
> They don't. Design patterns exist outside both functional and OO
> development. The OO paradigm just makes expressing design patterns
> easier because it already emphasizes problem space abstraction.
>

(Warning: Pandora ahead)

This is bullsh8t. There is no objective proof that OO better fits the
external world. And even if it did, sometimes the external world
sucks. Example: library card catalogues.

OO may fit the way *some* people think about the world, but that is by
definition a subjective claim.

The world world is a bunch of molecues that sometimes clump and
sometimes don't. If that is OOP, then enjoy your 1,000,000,000,000
object model, Mr. Lahman. (Sometimes OO does indeed feel like that.)

[snip]

>
> H. S. Lahman

-T-
oop.ismad.com