Re: A case for HTML as a programming language

From: tinyurl.com/uh3t (rem642b_at_Yahoo.Com)
Date: 11/26/04 

Date: Thu, 25 Nov 2004 23:24:24 -0800

> From: Michael Mendelsohn <keine.Werbung.1300@msgid.michael.mendelsohn.de>
> A computer is a programmable finite-state machine (FSM), and a
> language that can express any finite state machine can express any
> program that runs on it.

A CPU is a finite-state machine that has access to an arbitrarily large
amount of external read/write memory, some fixed amount directly
addressible as "main memory" or "RAM" via a fixed-length address, and
the rest indirectly addressible via I/O devices including network
connections. (Most network-accessible memory is read-only because it
belongs to other people and the owner of the particular CPU doesn't
have write-permission, but there's a lot of network-accessible memory
that *is* potentially read-write, all the CPU owner needs do is apply
for a free account to get write-access to additional memory, such as
Yahoo Geocities, Tripod, etc.)

A full computer (CPU plus installed RAM) and using a particular
programming language is a much larger finite-state machine that has
access to an arbitrary large amount of additional memory via I/O
devices including network connections. (Same remark about read-only and
read-write network storage.)

The number of potential machine states goes up exponentially with the
size of the read/write memory available. This makes either of the above
Turing complete in the sense of being potentially able to use an
infinitely long tape without modifying the original device.

By contrast, a full computer with only HTML as its language, no real
programming language in addition, and links only to static WebPages (no
CGI or other way to submit form to external processor, and no daemon
watching to see which WebPages are accessed and using that as a code
for doing processing on behalf of the HTML engine), has *only*
read-only external memory, no read-write external memory whatsoever, so
the number of machine states increases only linearily, not
exponentially, with the quantity of external memory (WebPages it can
browse). This is a fundamental difference between "real" programming
languages and HTML, a theoretical difference (asymptotic number of
states) not just a practical difference (above or below some particular
threshold I stated such as number of bytes of memory worldwide).

> C and VB are claimed to be Turing-complete languages, and they would be,
> if run on memory-unlimited computers; but since those do not exist, all
> you can practically do with them is use them to run finite-state machine
> programs.

A Turing machine, or a C or VB language, are all the same, Turing
complete in the sense of being able to emulate each other if given
enough external memory. HTML does not have that capability, so it's not
a real programming language. You cite that there's no such thing as an
infinite tape. That's just a practical matter and doesn't affect the
theoretical point I'm making.

So I'm correct on both theoretical and practical points:
- Theoretical: Asymptotic behaviour, exponential as contrasted with
linear number of machine states as function of external memory
available. Able to emulate any particular size of each other if finite
memory big enough on machine doing the emulation. HTML can't emulate
any such at all, except by first running an all-paths emulation on a
"real" computer and the simply writing a complete dump of such an
emulation to an immense Web, which is basically cheating, having some
*other* program do the actual emulation and then HTML simply displays
the output from it.
- Practical: Any "real" programming langauge can sort a thousand
arbitrary 16-bit integers on a machine with only a few thousand bytes
of memory. HTML, with all the resources in the world, can't do that
simple task, even if it's allowed to cheat by having some "real"
programming language generate an all-paths Web that HTML can then
browse.

HTML is neither theoretically nor practically a "real" programming
language.

> The contradiction of runinng a TM program on a FSM leads to the problems
> with out-of-memory "errors"; a C program would have a bug if such a
> condition occurred and the program did not catch it, so a prudent C
> programmer accepts that his program will run on a FSM when writing his
> code.

Correct. But a simple solution to not enough memory is to get access to
more memory, either by buying it yourself, leasing it from your ISP, or
getting free network memory from Yahoo Geocities etc. No major change
to the program itself is needed to run it with more memory.

> If programming languages had been designed not with a TM, but rather a
> FSM in mind, these kinds of errors couldn't occur as easily, because the
> limits of the machine would have been designed right into the language.

If the exact amount of memory you have today is a fundamental limit of
your programming language, then you can't just buy or lease more memory
tomorrow, you have to switch to a different programming language to
deal with any problem that doesn't fit in the old one.

> As an added advantage, I believe the halting problem is solvable for
> FSMs, so you can know whether a given program will enter an endless
> loop.

That ability isn't worth the price. First the limitation of not being
able to just buy more memory to solve larger problems. Second, the need
to purchase the entire Universe many times over just have enough memory
to run the does-it-halt program. The only direct way to detect a loop
(repeated state) is to keep a complete list of all machine states
so-far and check each new state against the old ones to see whether it
has looped yet. If it's looped, then it'll loop forever, hence it won't
halt. If it never repeats a machine state, then it eventually runs out
of new states and hence must halt. But even a computer with one
megabyte of memory has more potential machine states than all the atoms
in the Universe, so the cost of keeping that list of all machine states
so-far is astronomically impossible.

> to produce my simple demonstration program, which contains 326
> files, I availed myself of a short awk program that generated them.

So HTML didn't really do any sorting. AWK did the all-paths exploration
of the input to the sorting algorithm as applied to up to five numbers
specifically the numbers 1,2,3,4,5 only, and generated a report linking
all paths using HTML anchors, and HTML merely allows somebody to browse
that report.

> I can get around this limitation by storing a specification for the
> HTML files on the server, and generating the HTML for the necessary
> states on the fly. Call it "algorithmic compression".

In that case you'd be merely using HTML as a front-end (user interface)
for a program that actually runs in some other langauge. It's that
*other* language that is doing any real computation, not HTML. It
doesn't matter whether you have the *other* language run on demand,
such as CGI, or sit around constantly running as a daemon looking for
new tasks to do as determined by which pages HTML has been accessing
recently. The CGI server, or the daemon, are "real" programs written in
"real" programming languages, whereas HTML is just providing a
user-interface to those other programs.

> remember that a FSM program with precomputed states always runs O(1).

That statement is false except in some idealized world where access to
infinite memory is fixed-speed. In the real world, you can pack memory
only to the cube of radius (and that's ignoring how you'll get power in
and waste heat out), but access is limited by speed of light hence
slows linearly by radius, so at best you can get cuberoot of memory
size as access time, i.e. O(cuberoot(n)). That's slower than
logarithmic, but faster than linear. But n there is the total number of
WebPages you need to browse. Given that you need exponential number of
WebPages to handle an all-paths trace from an algorithm that uses a
particular number of bits of read-write memory, your HTML browser will
require O(cuberoot(exponential(N))) where N is the number of bits of
read-write memory used by the program that generated the all-paths Web.
So your HTML browser, looking at an all-paths report from sorting N
16-bit integers, will run almost exponentially slow, which is much
worse than even bubble sort would run, even if enough disk space for
all those Web pages were available. And that's just asymptotic
behaviour. The actual speed, even for small cases, is even worse: Sort
just five 16-bit integers restricted to range 0 to 30000 via Bubble
Sort, and it takes a micro-second or less on a cheap laptop computer.
Browse a giant Web full of more than 30000**5 WebPages, one for each
different combination of up to five 16-bit numbers in that range, don't
even count the time it took to buy all that memory and hook it
together, nor the time it took for your AWK program to build the
WebPages, just count the HTML browsing time, and it's a lot slower. Now
try the same for sorting one hundred 16-bit integers in the same range,
and Bubble Sort still takes a tiny fraction of a second, but your Web
won't be doable at all, and if somehow you magically had enough
resources to buy enough memory, it'd take years just for light to
traverse the Web.

No case has been made for HTML as a programming language. It's just a
browsing language without FORMs or other add-ons, and with FORMs or
JavaScript or applets etc. HTML is just a user interface to such other
programming capability. HTML is no more a programming language than
ASCII or VT100 or VGA, even if it does have more smarts about how to
present text etc. on-screen.

Relevant Pages

  • Re: OT: concrete and clay WAS: Re: I need a new compiler...
    ... which is the definition of the C language. ... indirection operators provide access to system memory. ... Michael can see abstraction and recognise it, ... But I would not argue that abstraction, encapsulation, de-coupling, and a few other methodologies are at the core of good design and even good programming. ...
    (comp.lang.cobol)
  • Re: Am I the only one who questions JSTL, Struts Tags, XSL Tags?
    ... it is a terrible affront to the Java language. ... a taglib is an extension to HTML. ... > attempts to make HTML a programming language - which it is not. ...
    (comp.lang.java.programmer)
  • Re: Dynamic Memory Allocation
    ... memory could be found by looking only at "pointer variables". ... In practical terms you need to use a language that has garbage ... an interpreter for a functional programming ...
    (comp.lang.c)
  • Re: E. W. Dijkstra VS. John McCarthy. A rebuttal to Paul Grahams web writings.
    ... > If you don't see html as a programming language you could run into ... > some definition problems of what a programming language should be. ... and the CGI script would examine the encoded-form-contents (via the GET ...
    (comp.lang.lisp)
  • Re: ASP.NET Internationalization bug?
    ... The Microsoft team has confirmed the bug. ... For every programming team that works like you do, ... My use of language and culture in ASP.Net is a bit different than most. ... I have already found, first-hand, that the better of the major search engines use the cc TLD *and* the HTML ...
    (microsoft.public.dotnet.framework.aspnet)