Functional - Re: shootout: implementing an interpreter for a simple procedural language Minim

Author

Re: shootout: implementing an interpreter for a simple procedural language Minim

Matthias Blume

2007-07-30, 4:14 am

Raffael Cavallaro
<raffaelcavallaro@pas-d'espam-s'il-vous-plait-mac.com> writes:

> On 2007-07-30 01:29:05 -0400, Matthias Blume <find@my.address.elsewhere> said:
>
>
> But the static type system cannot help you with the fact that in an
> interactive setting you cannot know the nature of the inputs (as
> humans can be so clever),

User input is handled by parsers, not by type systems. Parsers work
the same way in statically and dynamically typed settings. If your
code is prepared for certain inputs, then this can be expressed in
types. A type is just the (static) expression of a program
invariant.

> you cannot fully know the nature of the interactive processing (ditto),

If this were true, you couldn't write any program to deal with
interactive processing. After all, your code (be in statically typed
or dynamically typed) must be prepared to handle all interactions.
Again, static types merely describe (and let a compiler enforce) the
invariants that are inherent to such code.

> You find static typing a support. I find it a hinderance.

How much statically typed code (using a modern type system) have you
written?

> This is a matter of personal taste (and I've said elswhere in this
> thread that the relative popularities of c.l.l. and c.l.f. say
> somthing about where most programmers' tastes in this matter lie).

This is one point we can agree on.

> My main point is not about taste, but about the liklihood that, for
> interactive computing, where the future increasingly lies, the
> research into static typing has been a major research effort in the
> wrong direction.

I understand your point, but I do not agree with it. In fact, I think
that likelihood to be /extremely/ low.

Steve Schafer

2007-07-30, 7:08 pm

On Mon, 30 Jul 2007 19:54:22 +0200, Rainer Joswig <joswig@lisp.de>
wrote:

>If I use a constant integer somewhere and I declare it to be
>a prime, I better want to have it statically checked.

Ah, but now you're asking for the type system to have access to
information that it normally doesn't use; in this case, the integer
value of a text string interpreted by the parser as an integer literal.
There's nothing to prevent a type system from having access to such a
value, but I don't know of any language implementations that expose such
information in a way that a programmer can use.

See my reply to Paul for further elaborations.

Steve Schafer
Fenestra Technologies Corp.
http://www.fenestra.com/

Steve Schafer

2007-07-30, 7:08 pm

On 30 Jul 2007 11:00:00 -0700, Paul Rubin <http://phr.cx@NOSPAM.invalid>
wrote:

> doubleEven :: Even -> Even
> doubleEven x = Even (evenValue x + evenValue x)
>
>then I can write
>
> frob :: Even
> frob = doubleEven 7 -- invalid!!!!

No, you can't write that. You _can_ write this:

frob = doubleEven (Even 7)

And yes, the error won't occur until runtime.

>But unless I'm missing something, this is only a runtime guarantee,
>not a static check.

There are two separate questions that are being discussed here:

1) How do I ensure that a function only receives even numbers as input?

2) How do I do I ensure that the compiler interprets a lexical
representation of a number according to my even/odd criterion?

The first question is answered by the example I gave, and is independent
of whether or not the implementation of evenValue ever raises an error
or not.

The second question is a bit more complicated. In effect, you're asking
for the _parser_ to be able to distinguish between literal strings that
represent even numbers and literal strings that represent odd numbers.
The parser already does this sort of "type narrowing" to some extent:
"4.5" is determined to be of type Fractional, whereas "3" is determined
to be of type Num. There's nothing to prevent a parser from going a step
further and determining that "4" is of type EvenNum, but at the same
time, it's pretty unlikely that you'll find an off-the-shelf compiler
that contains such a parser. (And even more unlikely that you'll find an
off-the-shelf compiler that can distinguish literal strings representing
primes from those representing non-primes!)

There are ways around this, none of them (as far as I know) very pretty.
For example, let's change our definitions for Even:

> data Even = O Even | I Even | Z -- that's an "Oh" not a zero

> evenValue :: Even -> Int
> evenValue (I e) = (evenValue e) + (evenPower e)
> evenValue (O e) = (evenValue e)
> evenValue Z = 0

> evenPower :: Even -> Int
> evenPower (I e) = 2 * (evenPower e)
> evenPower (O e) = 2 * (evenPower e)
> evenPower Z = 2

With this, you can write Even constants using a sort of binary notation:

> I $ O $ O $ Z --> evenValue is 1000b = 8
> I $ O $ I $ O $ I $ Z --> evenValue is 101010b = 42

With this change in definition for Even, it's no longer possible to
express an Even value that isn't even. Of course, it does so at the
expense of a horrendously awful syntax that no one in their right mind
would ever use. But it does work.

Implementing the analogous Prime type is left as an exercise for the
reader....

>There may be a way to do it with GADT's.

I'm a couple of steps below "novice" when it comes to GADT's, but I
don't think so, because this is fundamentally a parser issue rather than
a type system issue. Once the parser has determined that "7" represents
an Int, the game is already lost, because the information that the type
system would need has been discarded.

Steve Schafer
Fenestra Technologies Corp.
http://www.fenestra.com/

Sponsored Links