Re: dynamic vs. static: the age-old debate

Curtis W wrote:
Other than that, it does everything yours does

Yours doesn't statically check to the same degree
How can you be sure of this? What is your definition of "statically
check"?

Good point. My statement was meaningless. Allow me to rephrase: I believe my
program will be checked more thoroughly by OCaml's static type system.

and will be many times slower.

And many times more extensible.

We'll see. ;-)

and has the same length.

Yours is 18 LOC and incomplete, my OCaml is 14 LOC and my Mathematica is
11 LOC and also incomplete.

No, that was the more readable version.

True. I think I factored out the "apply" function last time, which makes the
OCaml a little more readable.

The compacted version would be
exactly the same length with the 3 lines added. If my language had let
rec support built in, then it would have exactly the same functionality
in your version, although I fail to see the need for such a construct
when generators are available.

I don't mind how LETREC is implemented, as long as it is.

Because it is known to be incomplete and is written in a language that
doesn't exist.

How is it possible to write something in a language that does not
exist? Doesn't the presence of such a program prove that said language
does, indeed exist?

I think a high-level programming language requires a formal specification or
implementation for it to exist.

A compiler or interpreter might not be available,
but it's perfectly possible to "run" it by hand. After all, your brain
is turing complete.

My brain is finite. At least, that's what my wife tells me.

It's clear enough to be verifiable by hand,

Except for the non-trivial bit that is missing, yes.

Which is only made trivial in your version because it happens to be
built in to the language.

True. I can't see how to implement this in Mathematica. SML was ok though,
and that doesn't support recursive values.

In fact, the only reason it's needed at all
is because you're practically rewriting the host language in itself--if
you were to write a python interpreter, for example, there would be
several non-trivial bits that you'd have to write from scratch.

No, this LETREC construct is applicable to any target language with
closures. That includes Python AFAIK.

The hard parts of writing an ML interpreter are the static type checker and
the pattern matcher.

Generators are a concept from python, not OO. They're basically
functions which stream data back instead of returning it all at once,
e.g.:

def get_nums():
while True:
num = int(raw_input())
yield num

This basically returns an iterator which lets you iterate over the
users input in a lazy manner.

Ok. OCaml has a nice syntax for lazy lists BTW: [< 'h; t >]

Can you challenge me with some way that you want to extend the
functionality of this program that you believe will be easier to add
using OOP? Then we can both have a go and compare the results
objectively.

Of course. Let's say I want to add a 'print' function and a new type of
expression. (it doesn't matter what kind--take your pick :)

Ok. Let's go with Marcin's proposal for a "<" operator. I'll get coding on
the OCaml...

The first one is still
rather inflexible in that you have to update all function definitions
every time you add a function,

Not if you use a functor, for example.

Perhaps, but you still have to pass them around at the callsite, don't
you?

No, you pass a module implementing those functions (e.g. "print") to a
functor that implements functions over that function (e.g. eval) which
results in a new module.

For example, OCaml's sets are implemented using a functor. You pass a module
defining the element type and a comparison function over elements to the
Set functor and it gives you a module implementing sets of that type of
element.

This is academic anyway, I can see no reason to "pass around all
functions..." unless I want a higher-order function.

Or if you want to leave the door open to extension later on without
having to rewrite a large portion of code.

We'll see...

The following Mathematica code implements polynomial integration using
only Mathematica's pattern matcher and the FreeQ[e, f] function (which
checks that the pattern "f" does not match any subexpression of "e"):

integrate[y_ + z_, x_] := integrate[y, x] + integrate[z, x]
integrate[c_ y_, x_] := c integrate[y, x] /; FreeQ[c, x]
integrate[c_, x_] := c x /; FreeQ[c, x]
integrate[x_^n_., x_] := x^(n + 1)/(n + 1) /; FreeQ[n, x] && n != -1

For example:

integrate[3 a x^2 + 2 b x + c, x]
=> c x + b x^2 + a x^3

Just doing that exploits tremendous sophistication in the pattern
matcher, far beyond the capability of OOP.

I have no idea what that does. Could you possibly describe the
algorithm in a bit more detail?

Sure. The core of the integrator consists of four "rules". A rule consists
of a pattern on the left and a substitution on the right. Mathematica tries
to apply every rule to every subexpression repeatedly, until the result
stops changing (fixed point is reached).

The first rule:

integrate[y_ + z_, x_] := integrate[y, x] + integrate[z, x]

matches the integration of the sum of any two subexpressions y and z with
respect to x and replaces that expression with the sum of the integrals of
y and z.

For example:

integrate[a + b + c, x]
= integrate[a, x] + integrate[b + c, x]
= integrate[a, x] + integrate[b, x] + integrate[c, x]

Note that Mathematica's pattern matcher automatically tried all permutations
and combinations of the subexpressions of commutative operators like "+".

The second rule hoists constant factors:

integrate[c_ y_, x_] := c integrate[y, x] /; FreeQ[c, x]

This matches the product of two expressions c and y only when FreeQ[c, x]
evaluated to true. The FreeQ function tests an expression c to see if all
subexpressions fail to match the given pattern x. In this case, the rule is
only applied if c does not contain x, i.e. it is a constant with respect to
the integrating variable.

The third rule integrates constants:

integrate[c_, x_] := c x /; FreeQ[c, x]

The fourth rule integrates powers of x:

integrate[x_^n_., x_] := x^(n + 1)/(n + 1) /; FreeQ[n, x] && n != -1

Firstly, Mathematica's pattern matcher checks that repeated pattern
variables (x is used twice in this case) are semantically equivalent
(accounting for commutativity). Secondly, the pattern x_^n_. matches both x
raised to a power n and also x alone. In the latter case, n is taken to be
1 automatically.

Combined, these four rules allow any polynomial to be integrated.

Given that this is more complicated and more error prone than the
previous example, it is essential that the translation can be executed.

I'll put up a python version once I figure out what it does, which
should be useful to show that the version in my language is correct. I
doubt I'll have to use any facilities not present in python, so mine
should be almost identical except less verbose.

I am prepared to be amazed.

--
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists
.

Relevant Pages

  • Re: Does ANSI Common Lisp have pattern matching?
    ... I end up writing a pattern matcher. ... None are as common as any of the other FPLs with pattern matching built in. ... he thinks about what should be in lisp, a language that he doesn't ...
    (comp.lang.lisp)
  • Re: A request for information please.
    ... Could language explain our intelligence? ... with instincts! ... not possible without possessing consciousness or a mind. ... But Pi is not considered random even though it has no pattern because ...
    (comp.ai.philosophy)
  • Re: Need advices regarding signature tunning...
    ... More advanced pattern matching engines will allow you to set simple state variables based on patterns and to use those state variables as conditions in later patters. ... Just like vulnerable clients and servers write their protocol parsers in full featured, turing-complete, languages this approach uses some programming language to implement bits of code that handle specific sets of traffic. ...
    (Focus-IDS)
  • Re: Unlearning Pattern Matching
    ... It's almost hard to believe a language can be ... This ML-style pattern matcher ... takes just a few hours to write, even less for a real Lisp guru. ... Obviously you haven't read Dijkstra's PATTERN MATCHING considered ...
    (comp.lang.lisp)
  • Re: Raise of hands (virtually): How many here use AOP?
    ... I kind of understand what you are meaning (talking about pattern ... specific language overloading or not though, ... such a label to AOP including pattern matching features. ... simple language that lets the programmer attach code to class, method, ...
    (comp.lang.java.programmer)