Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2318 > unrolled thread

At what point is a language so abstract that it simply cannot be compiled?

Back to article view | Back to comp.compilers

Contents

  At what point is a language so abstract that it simply cannot be compiled? "Costello, Roger L." <costello@mitre.org> - 2019-05-13 14:38 +0000
    Re: At what point is a language so abstract that it simply cannot be compiled? "Derek M. Jones" <derek@_NOSPAM_knosof.co.uk> - 2019-05-13 20:15 +0100
      Re: At what point is a language so abstract that it simply cannot be compiled? Jan Ziak <0xe2.0x9a.0x9b@gmail.com> - 2019-05-14 08:52 -0700
    Re: At what point is a language so abstract that it simply cannot be compiled? Martin Ward <martin@gkc.org.uk> - 2019-05-14 12:52 +0100
    Re: At what point is a language so abstract that it simply cannot be compiled? gah4@u.washington.edu - 2020-02-27 18:27 -0800

#2318 — At what point is a language so abstract that it simply cannot be compiled?

Hello compiler experts!

Possibly a philosophical question ...

As I understand it, a computer can understand (process) only a small set of
simple instructions such as addition, subtraction, comparison, branching, and
so forth. Everything we do daily on our computers is ultimately compiled down
to a (huge) number of these simple machine instructions.

In the last few years I have used some quite abstract languages such as the
constraint satisfaction language Alloy and the XML processing language XSLT.
It amazes me that these languages can be broken apart and compiled into the
small, simple set of instructions required by the computer.

This makes me wonder: Is a theoretical limit to the level of abstraction that
can be turned into machine instructions? Are there languages (abstractions)
that are so high level, so abstract, that they simply cannot be mapped to the
required set of addition, subtraction, comparison, branching instructions? Or
is there no limit to the languages/abstractions that can be compiled?

/Roger
[In 1936 Alan Turing proved a surprising theorem that a very simple
hypothetical computer, now known as a Turing machine, could calculate
anything that any more complex computer could, given enough time and
storage.  Every computer built since the EDVAC in the 1940s has been
"Turing complete", able to compute what a Turing machine can, other
than that real computers have finite memories.  So we can be pretty
sure that the simplicity of an instruction set doesn't limit what
a computer can do.

There are plenty of problems that are known to be undecidable.  The
best known is the halting problem.  You cannot write a program that
can inspect any arbitrary program and always tell you whether the
program it's inspecting will eventually halt or it will run forever.

Wikipedia has a lot on this topic.  You can start here:

https://en.wikipedia.org/wiki/Turing_machine

-John]

[toc] | [next] | [standalone]

#2319

John,

> [...
> There are plenty of problems that are known to be undecidable.  The
> best known is the halting problem.  You cannot write a program that
> can inspect any arbitrary program and always tell you whether the
> program it's inspecting will eventually halt or it will run forever.
....
> -John]

This wording of the halting problem tends to lead to all kinds of
misunderstandings.

I prefer to phrase it as:
It has been provided that there exist programs for which it is not
possible to deduce whether it will eventually halt or not.


For many programs it is possible to deduce whether they will
halt, or not.

--
Derek M. Jones
blog:shape-of-code.coding-guidelines.com

[toc] | [prev] | [next] | [standalone]

#2321

On Monday, May 13, 2019 at 9:31:05 PM UTC+2, Derek M. Jones wrote:
> John,
>
> > [...
> > There are plenty of problems that are known to be undecidable.  The
> > best known is the halting problem.  You cannot write a program that
> > can inspect any arbitrary program and always tell you whether the
> > program it's inspecting will eventually halt or it will run forever.
> ....
> > -John]
>
> This wording of the halting problem tends to lead to all kinds of
> misunderstandings.
>
> I prefer to phrase it as:
> It has been provided that there exist programs for which it is not
> possible to deduce whether it will eventually halt or not.
>
>
> For many programs it is possible to deduce whether they will
> halt, or not.

Hello.

My preference is to phrase it like this:

For any program P that is able to decide in finite time whether a subset S of
its Turing-complete inputs will halt it is possible to construct an input X
not in S which will cause P to either loop forever or return the result
"unable to decide whether X halts".

From practical viewpoint (which does not allow infinite runtimes), P must
always terminate in finite time and return one of these three results:

1: X halts
2: X loops forever
3: unable to decide whether X halts or loops forever

(3) can be further extended in precision by allowing conditional expressions
in the result, such as:

3.A: If <condition> then [X halts] else [X loops forever]
3.B: If <condition> then [X halts] else [unable to decide whether X halts or
loops forever]

Precision of (3) is maximized when <condition> has the form of a universal
expression which evaluates to true or false in finite time.

Sincerely
Jan
[This thread has gotten far afield from compilers.  Please note followup-to. -John]

[toc] | [prev] | [next] | [standalone]

#2320

My WSL language is a "wide spectrum language" which includes
abstract specifications and low-level programming constructs in
the same language. At the specification level you can write
a specification statement of the form:

x := x'.Q

where x is a list of variable, x' is the corresponding list
of "primed variables" and Q is any formula of infinitary
first-order logic. If there is a set of values which can be assigned
to x' such that Q becomes true, then these values are assigned to x
and the statement terminates. (If there is more than one such
set of values, then one is selected nondeterminstically).
Otherwise, the statement aborts (does not terminate). For example:

<x> := <x'>.(x' = x + 1)

increments the value in x.

Since Q is a formula of infinitary first order logic,
the specification statement can be infinitely long.
There are formulae for which the solution cannot be computed:
for example, the Halting Problem for a Turing machine
can be implemented as a specification statement in WSL.

The language is used as the basis for my research into
program transformations. By using a wide-spectrum language
the refinement of a specification into exectuable code
is an example of a program transformation, as is the process
of reverse-engineering an abstract specification from
executable code.

A subset of WSL (not including the specification statement)
is implemented in the FermaT program transformation system:

http://www.gkc.org.uk/fermat.html

The FermaT program transformation system is used commercially
to migrate assembler code to structured and maintainable
functionally equivalent high-level language code.

This paper includes an introduction to WSL and transformation theory:

"Pigs from Sausages? Reengineering from Assembler to C via
FermaT Transformations", M.Ward, Science of Computer Programming,
Special Issue on Program Transformation,
Vol 52/1-3, pp 213-255, 2004. ISSN 0167-6423
doi:dx.doi.org/10.1016/j.scico.2004.03.007

This paper discusses how the theory can be used to derive
algorithms from specifications to give a provably correct
implementation:

"Provably Correct Derivation of Algorithms Using FermaT"
Martin Ward and Hussein Zedan
Formal Aspects of Computing, Volume 26, Issue 5, Pages 993–1031,
September 2014, ISSN 0934-5043
doi:10.1007/s00165-013-0287-2

Copies of these papers and others are available on my web site:

http://www.gkc.org.uk/martin/papers/index.html

--
			Martin

Dr Martin Ward | Email: martin@gkc.org.uk | http://www.gkc.org.uk
G.K.Chesterton site: http://www.gkc.org.uk/gkc | Erdos number: 4

[toc] | [prev] | [next] | [standalone]

#2464

On Monday, May 13, 2019 at 8:17:54 AM UTC-7, Costello, Roger L. wrote:

(snip)

> This makes me wonder: Is a theoretical limit to the level of abstraction that
> can be turned into machine instructions? Are there languages (abstractions)
> that are so high level, so abstract, that they simply cannot be mapped to the
> required set of addition, subtraction, comparison, branching instructions? Or
> is there no limit to the languages/abstractions that can be compiled?

For most languages, there is some back and forth between language
design and compiler design, to be sure that the language is parsable.

Though there is the complication that when new features are added
to an existing language, for a new release of the standard, to be sure
that existing programs are still valid and have the same meaning.

It is possible, for example, to (mis)design a language such that
the parsing is ambiguous. Having two different mappings to the
underlying hardware is just about as bad as zero.

Of the languages that I know about, PL/I is one of the few where pretty
much the whole language was designed and specified before compiler(s)
were written.  Some parts might have turned out harder to compile than
might have been expected.

But note that if a compiler can't figure it out, likely it is even
harder for a human to understand. Some of the early languages might
have been designed to be easy to compile, but for many years now,
compilability is second to the ability of humans to understand and
reliably write programs in a language.  Then some legal language
constructs are recommended against, as they can confuse readers later,
though likely not compilers.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web