Re: A case for HTML as a programming language

From: Michael Mendelsohn (keine.Werbung.1300_at_msgid.michael.mendelsohn.de)
Date: 11/22/04 

Date: Mon, 22 Nov 2004 11:35:30 +0100

In my answer, I'm going to talk about the distinction between Finite
State Machines from Turing Machines and bring up the notion of a
language used to specify FSMs (rather than explicitly list them all, as
I'm forced to do with HTML).

"tinyurl.com/uh3t" schrieb:
> In fact C or VB can be used to write much more than trivial
> programs, whereas HTML cannot.

You are, of course, right in practice. In theory, there is no
distinction.
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.
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.

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.

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.
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.

It is obvious to me that HTML is an impractical FSM programming language
because it forces me to express the program as an explicit list of
states; to produce my simple demonstration program, which contains 326
files, I availed myself of a short awk program that generated them.
If one wanted to create a FSM programming language, it would certainly
be at a higher level of abstraction; it would contain the specification
for a FSM, and the language would generate those states that are needed
to complete the program on the fly.

Since this approach leads to an execution model similar to what you get
with a TM language such as C or VB, what are the advantages of such an
approach?
I don't know.
I think such a language would be more easily verifyable, and it would
more naturally disallow common TM programming errors at the syntactic
level.
Is VHDL such a language?

> (In today's world I'd define a
> "nontrivial" program as one that is capable, within that single
> program, of exploring more different machine states than the total
> number of files in all the Web servers in the world. For example, it's
> rather trivial to write a C or VB program that sorts any arbitrary list
> of one thousand 16-bit numbers, whereas it's impossible to do the same
> in HTML because there are more than one-thousand-factorial possible
> machine states at the start of the sorting process, just after taking
> input, before starting to sort, which is far larger than the number of
> files in the world.)

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".

> So C and VB are true programming languages,
> whereas HTML isn't.

That is not the usual distinction.
C and VB are Turing-complete, whereas HTML isn't.
 
> Note that with a static-linked-page system such as HTML, the cost goes
> up linearily with the total number of potential states, since you need
> to set up, in advance, one file for each different potential state. But
> with a real programming language, the cost goes up *much* more slowly.

Well, there's a space/time tradeoff; remember that a FSM program with
precomputed states always runs O(1). This is the reason why tables _are_
used in current programs when speed is an issue.

Cheers
Michael 

-- 
Still an attentive ear he lent        Her speech hath caused this pain
But could not fathom what she meant   Easier I count it to explain
She was not deep, nor eloquent.       The jargon of the howling main
                 -- from Lewis Carroll: The Three Usenet Trolls

Relevant Pages

  • Re: UML Question (Object <-> ObjectFinder?)
    ... An FSM is a description of an algorithm. ... system will likely be composed of many different state machines ... >> I'm not saying that abstracting the problem space is not a good idea, ... >> an OO language than you can in a procedural language. ...
    (comp.object)
  • Re: Injecting local variable to a function - Can it be done?
    ... in a different language but are quite non-idiomatic to JavaScript. ... For FSM, I first started with something similar ... but following two goals drove me to this state: ... integrating async op like below into FSM: ...
    (comp.lang.javascript)
  • Re: Steps beyond "Hello World" program
    ... >>If you want to prove a language is really a programming language you ... >>HTML is not a programming language because it is not Turing complete. ... Turing-complete language can. ...
    (comp.programming)
  • Re: A case for HTML as a programming language
    ... > language for adding meta information to an information stream. ... I agree with you that HTML is a markup language, ... Turing-complete languages. ... Turing-completeness is the defining aspect of a programming language, ...
    (comp.programming)
  • Re: implementation of finite state machine
    ... ??>> Could you please point me to some resource, describing sample ... ??>> implementation of FSM in C language, ... Due to my understandanding of FSM, ...
    (comp.programming)