Re: Dijkstra gets it wrong [was: Re: D gets it right]

From: Michael Mendelsohn (keine.Werbung.1300_at_michael.mendelsohn.de)
Date: 03/18/04 

Date: Thu, 18 Mar 2004 01:15:05 +0100

Cristiano Sadun schrieb:
> Michael Mendelsohn <keine.Werbung.1300@michael.mendelsohn.de> wrote in
> news:405824C3.EB7F38C4@michael.mendelsohn.de:

> > Well, I thought that if a programming language wasn't completely
> > defined, it could not be a formal language.
>
> "Formal language" in itself means even less: that there's a formal
> grammer that can be used to parse it. :)
>
> C is a formal language insofar you can create a compiler whose output is
> "syntactically correct" or "not syntactically correct".

Said compiler would usually be called a parser, yes.
Memory comes back now... a formal language spec is a set of rules; all
expressions that can be constructed using these rules are in the
language, those that can't are out. (Does Goedel say that for some
expressions, this can't be determined?)

> What we're talking here is (more or less formal) language semantics.
>
> > No, that's just it: since PEEK(A) reads the memory content at address
> > A, it should return b, but sometimes it doesn't.
>
> "Peek" is *another* operation. It hasnt anything to do with poke. For all
> poke's concerned, "peek" could not even exist.

The point I was making was a response to

>>> "Again, what's "undefined" in poke a,b? The memory content of the address a
>>> is going to be b. From a language point of view, that's all the definition
>>> that is needed."

>From a language point of view, this statment of yours defines the
semantics of "poke". But actually, what you should have told me is that
"after POKE expect a "(", then a numeric expression, then a ",", then
another numeric expression, then a closing ")"; the whole thing is a
program statement.
<statement> = POKE ( <numex> , <numex> ) | ...

[light switch example]
> Similarly, a programming language definition is never enough for using
> that language practically - you need to have a *system* definition also.
> But a language is not a system - and language semantics regards
> languages, not systems.

I don't concur: a language standard that defines an argument list and
standard input and output streams regards a system. A programming
language standards document doesn't specify syntax alone.

> > Maybe I'm off on a wrong track here: what would say is a formal
> > language? what is a programming language?
>
> A programming language is a formal language associated to a formal
> machine specification. That's the ultimate structure over which the
> notion of "computation" can be defined and studied clearly (Mr. Turing
> here is your guy).

Yes, that sounds right to me.
Although that's a self-defeating definition of programming language,
because that holds the point of contention as an axiom. I'd rather
define programming language as "language used to write programs in",
whether formally defined or tied to a formal machine or not.

EGN > All programming languages are formal languages although the
converse
EGN > is not true.
RH > Exercise: think of a counter-example.

So to provide Richard's counterexample I would have to find a
programming language and a program such that the syntactical correctness
of the program in regard to the language cannot be determined.

I still think Pseudocode is a good counterexample, because it can be
used to express algorithms clearly, yet it can't be formally specified.

I'd also get second thoughts about a program that contains the line
REM values swapped will unswapped on the fly to be the end
but I can understand how you would argue that this program is formally
syntactically correct. ;)

New example: C programs that use #define must rely on #define semantics
to be determined correct or false; if these semantics included undefined
behaviour, then the C language would not be a programming language
(although it could be well used for programming if that behaviour was
avoided).

-----
I feel adventurous today, so why not tackle the other side of EGNs
statement? The converse would be: "There are formal languages that are
not programming languages". However, for any such formal language one
cared to name, I need only tie it to a formal machine to make it a
programming language.

I hereby define my programming language REM+ that accepts any formal
language; all elements of the language will be considered comments, and
the VM will do nothing (useful) all the time (many would argue that
obviously there are already a lot of REM+ programs being sold today ;).

Michael 

-- 
Feel the stare of my burning hamster and stop smoking!

Relevant Pages

  • Re: Genetics as a Language System
    ... All of these codes are language systems, ... They are all language systems. ... sequences of dashes and dots. ... a formal language does not equal (and is not even ...
    (talk.origins)
  • Re: Name for a website about programming language design
    ... programming language design for any of us here to use. ... semantics semantics ... PiLuD has discussions and light wiki: ... Programming Language News seems to be operating in the future?? ...
    (comp.lang.misc)
  • Re: Torkel Franzen on truth
    ... with a deductive system and/or a model-theoretic semantics. ... The language ... The deductive system is to capture, codify, or simply record ... of 'formal language' so that a formal language has both a formal ...
    (sci.logic)
  • Re: Dijkstra gets it wrong [was: Re: D gets it right]
    ... it could not be a formal language. ... a programming language definition is never enough for using ... > But a language is not a system - and language semantics regards ...
    (comp.object)
  • Re: Godels incompleteness and formal language
    ... as well as a language there is a deducibility relation. ... First Order logic is an undecidable formal language ... >> No formal language is able to express all truthful statements. ...
    (sci.logic)