Re: a language is a language
- From: rem642b@xxxxxxxxx (Robert Maas, see http://tinyurl.com/uh3t)
- Date: Wed, 13 Dec 2006 09:49:27 -0800
From: "Ed Prochak" <edproc...@xxxxxxxxx>
What constitutes a programming language?
Examples to consider
C
Assembler
...
HTML
...
What do you consider a programming language and why?
C and assembler (for most any CPU) are programming languages.
HTML is not.
The "standard" reasoning is that C or assembler can emulate a
Turing machine whereas HTML cannot. But IMO that doesn't get to the
heart of the matter, why anybody would *want* to write something
using a programming language. After all, Turing machines are famous
for being very very slow at solving typical D/P (data-processing)
problems by emulating in a very painful cranky way typical D/P
algorithms by very roundabout ways, so nobody in their right mind
would use a Turing machine to solve typical D/P problems, so why
would ability to emulate a Turing machine be the key qualification
for a language??
Just over two years ago, in the course of working on my
"Hello-World Plus" project to show how various programming
languages can go beyond just the "Hello World" program while HTML
basically can't, I think I came to the correct realization what
makes the key difference: In a simple data storage and presentation
system such as HTML with a Web browser but no help on serverside
such as CGI or JSP and no help on clientside such as JavaScript,
the total number of possible machine states is linear with the
amount of memory accessible. But with a true programming language
such as C or assembler, the total number of possile machine states
is *exponential* with the amount of memory accessible.
<http://groups.google.com/group/comp.programming/msg/da223976a8b59abb>
= Message-ID: <REM-2004nov25-004@xxxxxxxxx>
Below is a clarification of concepts that were first expressed back then.
First an explanation of how I count "memory available" and how it's
used in practice to establish different machine states that are
apparent to the user, then I'll get back to finishing my
explanation.
When using HTML with Web browser, there are Web pages located on
various servers around the InterNet. A physical Web page is the
entire file that is downloaded from the server to the client
(browser) at a single time in response to a single URL address. But
a physical Web page can be broken into more than different
accessible locations, what I call logical Web pages, by means of
anchors of type "name". The URL#name then downloads the entire
physical Web page, then directs the browser to move the window to
the #name anchor within that page and show *that* logical page to
the user. Now consider the following trick that pretends to use
HTML to sort five numbers:
<http://www.michael.mendelsohn.de/sort5/>
It's just a tree of Web pages, one page for the starting state,
five additional pages for the states possible after the first
number has been selected, twenty additional pages for the states
possible after two numbers have been selected, sixty additional
pages for the states possible after three numbers have been
selected, 120 additional pages for the states possible after four
numbers have been selected, and 120 additional pages for the states
possible after all five numbers have been selected. This particular
hack uses a separate physical Web page for each logical Web page,
but the principle would be the same if all the logical Web pages
were contained within one huge physical Web page with "name"
anchors to jump around within that one huge file. Regardless of
which method is used, or a combination with several "name" anchors
within each of several different physical pages, still the total
number of accessible machine states equals the total number of
logical Web pages, which is at best proportional to the total
amount of data storage available. In that example,
1+5+10+20+60+120+120=336 states were needed, so 336 different
logical Web pages were needed.
Now compare that to a "real" programming language. It would need a
single integer with only 9 bits to encode 512 different possible
states, and with a suitably complicated coding system could
represent all 336 states of the five-number-sorting demo within
that single 9-bit word. (Then a transformation of that state-number
would be required to present the data to the user in the format
given by that demo, and reverse transformation from the possible
next states back to that 9-bit-coding system would be required to
express the alternatives for the next states which are reachable.)
Alternately a more "natural" state-coding system could be used,
such as using 3 bits to represent each of the five numbers, with a
spare pattern used to represent end-of-numbers, with a array of
five such 3-bit numbers, a total of 15 bits, still far fewer than
336 logical Web pages.
Now push that up to a more reasonable number of states for a
practical algorithm, say a hundred million different states. That
would require a hundred million different logical Web pages to make
all the states available as separate logical Web pages, but a real
programming language would require only a single 27-bit number to
represent them all. Now push it up again to a very very small
practical computer with only one kilobyte of RAM. How many states
can that represent? Well, that's 2**(8*1024) states, which is
approximately 10**2466, which is more than a googol to the 24th
power. There's no way the different possible machine states of even
such a tiny computer system can be emulated via HTML pages
occupying the entire Universe.
See also my discussion of the topic here:
<http://www.rawbw.com/~rem/HelloPlus/hellos.html#realprog>
In summary, a "real" programming language, unlike HTML, has a total
number of machine states that grows exponentially, instead of
linearly, with the amount of memory available.
So is a Turing machine a "real" programming language per my
criterion? Yes. With a fixed alphabet of at least two different
characters allowed on the "tape", but with varying lengths of tape
available before it "runs off the end and dies", the number of
different possible patterns on the tape grows exponentially with
the length of the tape, just like the number of possible bit
patterns (or numbers represented) in RAM of varying size.
.
- References:
- a language is a language
- From: Ed Prochak
- a language is a language
- Prev by Date: Re: Which is the Best cross platform language?
- Next by Date: Re: a language is a language
- Previous by thread: Re: a language is a language
- Next by thread: Which is the Best cross platform language?
- Index(es):
Relevant Pages
|
