Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > What is Expressiveness in a Computer Language

Reply
Thread Tools

What is Expressiveness in a Computer Language

 
 
Joachim Durchholz
Guest
Posts: n/a
 
      07-12-2006
Darren New schrieb:
> There are also problems with the complexity of things. Imagine a
> chess-playing game trying to describe the "generate moves" routine.
> Precondition: An input board with a valid configuration of chess pieces.
> Postcondition: An array of boards with possible next moves for the
> selected team. Heck, if you could write those as assertions, you
> wouldn't need the code.


Actually, in a functional programming language (FPL), you write just the
postconditions and let the compiler generate the code for you.

At least that's what happens for those FPL functions that you write down
without much thinking. You can still tweak the function to make it more
efficient. Or you can define an interface using preconditions and
postconditions, and write a function that fulfills these assertions
(i.e. requires no more preconditions than the interface specifies, and
fulfills at least the postcondition that the interface specifies); here
we'd have a postcondition that's separate from the code, too.
I.e. in such cases, the postconditions separate the accidental and
essential properties of a function, so they still have a role to play.

Regards,
Jo
 
Reply With Quote
 
 
 
 
David Hopwood
Guest
Posts: n/a
 
      07-12-2006
Marshall wrote:
> Joachim Durchholz wrote:

[...]
>>Preconditions/postconditions can express anything you want, and they are
>>an absolutely natural extensions of what's commonly called a type
>>(actually the more powerful type systems have quite a broad overlap with
>>assertions).
>>I'd essentially want to have an assertion language, with primitives for
>>type expressions.

>
> Now, I'm not fully up to speed on DBC. The contract specifications,
> these are specified statically, but checked dynamically, is that
> right? In other words, we can consider contracts in light of
> inheritance, but the actual verification and checking happens
> at runtime, yes?


For DBC as implemented in Eiffel, yes.

> Wouldn't it be possible to do them at compile time? (Although
> this raises decidability issues.)


It is certainly possible to prove statically that some assertions cannot fail.

The ESC/Java 2 (http://secure.ucd.ie/products/openso...ava2/docs.html)
tool for JML (http://www.cs.iastate.edu/~leavens/JML/) is one system that does
this -- although some limitations and usability problems are described in
<http://secure.ucd.ie/products/opensource/ESCJava2/ESCTools/papers/CASSIS2004.pdf>.

> Mightn't it also be possible to
> leave it up to the programmer whether a given contract
> was compile-time or runtime?


That would be possible, but IMHO a better option would be for an IDE to give
an indication (by highlighting, for example), which contracts are dynamically
checked and which are static.

This property is, after all, not something that the program should depend on.
It is determined by how good the static checker currently is, and we want to be
able to improve checkers (and perhaps even allow them to regress slightly in
order to simplify them) without changing programs.

--
David Hopwood <(E-Mail Removed)>
 
Reply With Quote
 
 
 
 
Marshall
Guest
Posts: n/a
 
      07-13-2006
Joachim Durchholz wrote:
> Marshall schrieb:
> > Joachim Durchholz wrote:
> >> Marshall schrieb:
> >>> I can see the lack of a formal model being an issue, but is the
> >>> imperative bit really all that much of an obstacle? How hard
> >>> is it really to deal with assignment? Or does the issue have
> >>> more to do with pointers, aliasing, etc.?
> >> Actually aliasing is *the* hard issue.

> >
> > Okay, sure. Nice explanation.
> >
> > But one minor point: you describe this as an issue with "imperative"
> > languages. But aliasing is a problem associated with pointers,
> > not with assignment.

>
> Aliasing is not a problem if the aliased data is immutable.


Okay, sure. But for the problem you describe, both imperativeness
and the presence of pointers is each necessary but not sufficient;
it is the two together that causes the problem. So it strikes
me (again, a very minor point) as inaccurate to describe this as
a problem with imperative languages per se.


> > One can have assignment, or other forms
> > of destructive update, without pointers; they are not part of the
> > definition of "imperative."

>
> Sure.
> You can have either of destructive updates and pointers without
> incurring aliasing problems. As soon as they are combined, there's trouble.


Right. To me the response to this clear: give up pointers. Imperative
operations are too useful to give up; indeed they are a requirement
for certain problems. Pointers on the other hand add nothing except
efficiency and a lot of confusion. They should be considered an
implementation technique only, hidden behind some pointerless
computational model.

I recognize that this is likely to be a controversial opinion.



> Functional programming languages often drop assignment entirely. (This
> is less inefficient than one would think. If everything is immutable,
> you can freely share data structures and avoid some copying, and you can
> share across abstraction barriers. In programs with mutable values,
> programmers are forced to choose the lesser evil of either copying
> entire data structures or doing a cross-abstraction analysis of who
> updates what elements of what data structure. A concrete example: the
> first thing that Windows does when accepting userland data structures
> is... to copy them; this were unnecessary if the structures were immutable.)


I heartily support immutability as the default, for these and other
reasons.


> Some functional languages restrict assignment so that there can exist at
> most a single reference to any mutable data structure. That way, there's
> still no aliasing problems, but you can still update in place where it's
> really, really necessary.


Are we speaking of uniqueness types now? I haven't read much about
them, but it certainly seems like an intriguing concept.


> I know of no professional language that doesn't have references of some
> kind.


Ah, well. I suppose I could mention prolog or mercury, but then
you used that troublesome word "professional." So I will instead
mention a language which, if one goes by number of search results
on hotjobs.com for "xxx progammer" for different value of xxx, is
more popular than Java and twice as popular as C++. It lacks
pointers (although I understand they are beginning to creep in
in the latest version of the standard.) It also posesses a quite
sophisticated set of facilities for declarative integrity constraints.
Yet for some reason it is typically ignored by language designers.

http://hotjobs.yahoo.com/jobseeker/j...sql+programmer


Marshall

 
Reply With Quote
 
Marshall
Guest
Posts: n/a
 
      07-13-2006
David Hopwood wrote:
> Marshall wrote:
>
> > Wouldn't it be possible to do them at compile time? (Although
> > this raises decidability issues.)

>
> It is certainly possible to prove statically that some assertions cannot fail.
>
> The ESC/Java 2 (http://secure.ucd.ie/products/openso...ava2/docs.html)
> tool for JML (http://www.cs.iastate.edu/~leavens/JML/) is one system that does
> this -- although some limitations and usability problems are described in
> <http://secure.ucd.ie/products/opensource/ESCJava2/ESCTools/papers/CASSIS2004.pdf>.


I look forward to reading this. I read a paper on JML a while ago and
found it quite interesting.


> > Mightn't it also be possible to
> > leave it up to the programmer whether a given contract
> > was compile-time or runtime?

>
> That would be possible, but IMHO a better option would be for an IDE to give
> an indication (by highlighting, for example), which contracts are dynamically
> checked and which are static.
>
> This property is, after all, not something that the program should depend on.
> It is determined by how good the static checker currently is, and we want to be
> able to improve checkers (and perhaps even allow them to regress slightly in
> order to simplify them) without changing programs.


Hmmm. I have heard that argument before and I'm conflicted.

I can think of more reasons than just runtime safety for which I'd
want proofs. Termination for example, in highly critical code;
not something for which a runtime check will suffice. On the
other hand the points you raise are good ones, and affect
the usability of the language.


Marshall

 
Reply With Quote
 
Andreas Rossberg
Guest
Posts: n/a
 
      07-13-2006
Marshall wrote:
>
> Okay, sure. But for the problem you describe, both imperativeness
> and the presence of pointers is each necessary but not sufficient;
> it is the two together that causes the problem. So it strikes
> me (again, a very minor point) as inaccurate to describe this as
> a problem with imperative languages per se.
>
> [...]
>
> Right. To me the response to this clear: give up pointers. Imperative
> operations are too useful to give up; indeed they are a requirement
> for certain problems. Pointers on the other hand add nothing except
> efficiency and a lot of confusion. They should be considered an
> implementation technique only, hidden behind some pointerless
> computational model.


Don't get yourself distracted by the low-level notion of "pointer". The
problem *really* is mutability and the associated notion of identity,
which explicit pointers just exhibit on a very low level.

When you have a language with mutable types (e.g. mutable arrays) then
objects of these types have identity, which is observable through
assignment. This is regardless of whether identity is an explicit
concept (like it becomes with pointers and comparison of pointer values,
i.e. addresses).

Consequently, you cannot possibly get rid of aliasing issues without
getting rid of (unrestricted) mutability. Mutability implies object
identity implies aliasing problems.

On the other hand, pointers are totally a futile concept without
mutability: if everything is immutable, it is useless to distinguish
between an object and a pointer to it.

In other words, pointers are essentially just an *aspect* of mutability
in lower-level languages. On a sufficiently high level of abstraction,
it does not make much sense to differentiate between both concepts -
pointers are just mutable objects holding other mutable objects
(immutable pointer types exist, but are only interesting if you also
have pointer arithmetics - which, however, is largely equivalent to
arrays, i.e. not particularly relevant either).

- Andreas
 
Reply With Quote
 
Joachim Durchholz
Guest
Posts: n/a
 
      07-13-2006
Marshall schrieb:
> Joachim Durchholz wrote:
>> Marshall schrieb:
>>> Joachim Durchholz wrote:
>>>> Marshall schrieb:
>>>>> I can see the lack of a formal model being an issue, but is the
>>>>> imperative bit really all that much of an obstacle? How hard
>>>>> is it really to deal with assignment? Or does the issue have
>>>>> more to do with pointers, aliasing, etc.?
>>>> Actually aliasing is *the* hard issue.
>>> Okay, sure. Nice explanation.
>>>
>>> But one minor point: you describe this as an issue with "imperative"
>>> languages. But aliasing is a problem associated with pointers,
>>> not with assignment.

>> Aliasing is not a problem if the aliased data is immutable.

>
> Okay, sure. But for the problem you describe, both imperativeness
> and the presence of pointers is each necessary but not sufficient;
> it is the two together that causes the problem. So it strikes
> me (again, a very minor point) as inaccurate to describe this as
> a problem with imperative languages per se.


Sure.
It's just that I know that it's viable to give up destructive updates.
Giving up pointers is a far more massive restriction.

> Right. To me the response to this clear: give up pointers. Imperative
> operations are too useful to give up; indeed they are a requirement
> for certain problems.


I don't know any.
In some cases, you need an additional level of conceptual indirection -
instead of *doing* the updates, you write a function that *describes* them.

> Pointers on the other hand add nothing except
> efficiency and a lot of confusion. They should be considered an
> implementation technique only, hidden behind some pointerless
> computational model.
>
> I recognize that this is likely to be a controversial opinion.


Indeed.

In fact "modes" are a way to restrict pointer aliasing.

> I heartily support immutability as the default, for these and other
> reasons.


OK, then we're in agreement here.

>> Some functional languages restrict assignment so that there can exist at
>> most a single reference to any mutable data structure. That way, there's
>> still no aliasing problems, but you can still update in place where it's
>> really, really necessary.

>
> Are we speaking of uniqueness types now? I haven't read much about
> them, but it certainly seems like an intriguing concept.


Yup.
It's called "modes" in some other languages (Mercury or Clean IIRC).

>> I know of no professional language that doesn't have references of some
>> kind.

>
> Ah, well. I suppose I could mention prolog or mercury, but then
> you used that troublesome word "professional." So I will instead
> mention a language which, if one goes by number of search results
> on hotjobs.com for "xxx progammer" for different value of xxx, is
> more popular than Java and twice as popular as C++. It lacks
> pointers (although I understand they are beginning to creep in
> in the latest version of the standard.) It also posesses a quite
> sophisticated set of facilities for declarative integrity constraints.
> Yet for some reason it is typically ignored by language designers.
>
> http://hotjobs.yahoo.com/jobseeker/j...sql+programmer


Oh, right. SQL is an interesting case of getting all the problems of
pointers without having them

Actually SQL has references - they are called "primary keys", but they
are references nevertheless. (Some SQL dialects also offer synthetic
"ID" fields that are guaranteed to remain stable over the lifetime of a
record. Seems like SQL is imperative enough that programmers want this,
else the SQL vendors wouldn't have added the feature...)
SQL also has updates.
The result: updates with undefined semantics. E.g. if you have a numeric
key field, UPDATE commands that increment the key by 1 will fail or work
depending on the (unspecified) order in which UPDATE touches the
records. You can have even more fun with updatable views.
With a "repeatable read" isolation level, you actually return to a
declarative view of the database: whatever you do with it, you won't see
it until you commit the transaction. (As soon as you commit, the
declarative peace is over and you better watch out that your data
doesn't become inconsistent due to aliasing.)


Aliasing isn't really related to specific programming practices. If two
accountants chat, and one talks about the hot blonde secretaire and the
other about his adorable wife, you can imagine the awkwardness that
ensues as soon as they find out they're talking about the same person!
The only thing that can really be done about it is not adding it
artificially into a program. In those cases where aliasing is part of
the modelled domain, you really have to carefully inspect all
interactions and never, never, never dream about abstracting it away.


Regards,
Jo
 
Reply With Quote
 
Joachim Durchholz
Guest
Posts: n/a
 
      07-13-2006
Darren New schrieb:
> Joachim Durchholz wrote:
>> Actually, in a functional programming language (FPL), you write just
>> the postconditions and let the compiler generate the code for you.

>
> Certainly. And my point is that the postcondition describing "all valid
> chess boards reachable from this one" is pretty much going to be as big
> as an implementation for generating it, yes?


Yes. It's a classical case where the postcondition and the code that
fulfils it are essentially the same.

> The postcondition will
> still have to contain all the rules of chess in it, for example. At best
> you've replaced loops with some sort of universal quanitifier with a
> "such that" phrase.


Correct.

OTOH, isn't that the grail that many people have been searching for:
programming by simply declaring the results that they want to see?

> Anyway, I expect you could prove you can't do this in the general case.
> Otherwise, you could just write a postcondition that asserts the output
> of your function is machine code that when run generates the same
> outputs as the input string would. I.e., you'd have a compiler that can
> write other compilers, generated automatically from a description of the
> semantics of the input stream and the semantics of the machine the code
> is to run on. I'm pretty sure we're not there yet, and I'm pretty sure
> you start running into the limits of computability if you do that.


No, FPLs are actually just that: compilable postconditions.
Computability issues aren't more or less a factor than with other kinds
of compilers: they do limit what you can do, but these limits are loose
enough that you can do really useful stuff within them (in particular,
express all algorithms).

Regards,
Jo
 
Reply With Quote
 
Joachim Durchholz
Guest
Posts: n/a
 
      07-13-2006
Marshall schrieb:
> David Hopwood wrote:
>> This property is, after all, not something that the program should depend on.
>> It is determined by how good the static checker currently is, and we want to be
>> able to improve checkers (and perhaps even allow them to regress slightly in
>> order to simplify them) without changing programs.

>
> Hmmm. I have heard that argument before and I'm conflicted.


I'd want several things.

A way for me to indicate what assertions must be proven statically.
Highlighting (be it compiler messages or flashing colors in an IDE) that
marks assertions that *will* break.
And highlighting for assertions that *may* break.
In the language, a (possibly) simplicistic inference engine definition
that gives me minimum guarantees about the things that it will be able
to prove; if something is out of the reach of the engine, a
straightforward way to add intermediate assertions until the inference
succeeds.

(Plus diagnostics that tell me where the actual error may be, whether
it's a bug in the code or an omission in the assertions. That's probably
the hardest part of it all.)

Regards,
Jo
 
Reply With Quote
 
Marshall
Guest
Posts: n/a
 
      07-13-2006
Andreas Rossberg wrote:
> Marshall wrote:
> >
> > Okay, sure. But for the problem you describe, both imperativeness
> > and the presence of pointers is each necessary but not sufficient;
> > it is the two together that causes the problem. So it strikes
> > me (again, a very minor point) as inaccurate to describe this as
> > a problem with imperative languages per se.
> >
> > [...]
> >
> > Right. To me the response to this clear: give up pointers. Imperative
> > operations are too useful to give up; indeed they are a requirement
> > for certain problems. Pointers on the other hand add nothing except
> > efficiency and a lot of confusion. They should be considered an
> > implementation technique only, hidden behind some pointerless
> > computational model.

>
> Don't get yourself distracted by the low-level notion of "pointer". The
> problem *really* is mutability and the associated notion of identity,
> which explicit pointers just exhibit on a very low level.
>
> When you have a language with mutable types (e.g. mutable arrays) then
> objects of these types have identity, which is observable through
> assignment. This is regardless of whether identity is an explicit
> concept (like it becomes with pointers and comparison of pointer values,
> i.e. addresses).


Hmmm, well, I cannot agree. You've defined away the pointers
but then slipped them back in again by assumption ("objects
of these types have identity".)

First let me say that the terminology is somewhat problematic.
For the specific issue being discussed here, pointers, identity,
and objects are all the same concept. (I agree that "pointer"
connotes a low-level construct, however.) Sometimes I think
of this issue as being one with first class variables. An object
with mutable fields is a variable, and if we have pointers or
references or any way to have two different pathways to
that object/those variables, then we run in to the aliasing problem.

However if the mutable types are not first class, then there
is no way to have the aliasing. Thus, if we do not have pointers
or objects or identity but retain mutability, there is no aliasing
problem.


> Consequently, you cannot possibly get rid of aliasing issues without
> getting rid of (unrestricted) mutability. Mutability implies object
> identity implies aliasing problems.


Mutability by itself does not imply identity. I agree that mutability
plus
identity implies aliasing problems, however.


> On the other hand, pointers are totally a futile concept without
> mutability: if everything is immutable, it is useless to distinguish
> between an object and a pointer to it.


Agreed.


> In other words, pointers are essentially just an *aspect* of mutability
> in lower-level languages.


Again, I disagree: it is posible to have mutability without
pointers/identity/objects.


Marshall

 
Reply With Quote
 
Andreas Rossberg
Guest
Posts: n/a
 
      07-13-2006
Marshall wrote:
>
> However if the mutable types are not first class, then there
> is no way to have the aliasing. Thus, if we do not have pointers
> or objects or identity but retain mutability, there is no aliasing
> problem.


Yes, technically you are right. But this makes a pretty weak notion of
mutability. All stateful data structures had to stay within their
lexical scope, and could never be passed to a function. For example,
this essentially precludes object-oriented programming, because you
could not have objects with state (the alternative, second class
objects, would be even less "objective").

Generally, second-classness is an ad-hoc restriction that can work
around all kinds of problems, but rarely with satisfactory results. So I
would tend to say that this is not an overly interesting point in the
design space. But YMMV.

>>In other words, pointers are essentially just an *aspect* of mutability
>>in lower-level languages.

>
> Again, I disagree: it is posible to have mutability without
> pointers/identity/objects.


OK, if you prefer: it is an aspect of first-class mutability - which is
present in almost all imperative languages I know.

- Andreas

--
Andreas Rossberg, http://www.velocityreviews.com/forums/(E-Mail Removed)-sb.de
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
What is Expressiveness in a Computer Language Xah Lee Java 640 07-22-2006 03:50 PM
What is Expressiveness in a Computer Language Xah Lee Python 671 07-22-2006 03:50 PM
A language-agnostic language Ed Java 24 03-27-2006 08:19 PM
[perl-python] text pattern matching, and expressiveness Xah Lee Python 4 02-11-2005 09:11 PM
[perl-python] text pattern matching, and expressiveness Xah Lee Perl Misc 1 02-07-2005 08:18 PM



Advertisments