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

From	"Costello, Roger L." <costello@mitre.org>
Newsgroups	comp.compilers
Subject	At what point is a language so abstract that it simply cannot be compiled?
Date	2019-05-13 14:38 +0000
Organization	Compilers Central
Message-ID	<19-05-083@comp.compilers> (permalink)

Show all headers | View raw

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]

Back to comp.compilers | Previous | Next — Next in thread | Find similar

Thread

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

csiph-web