A case for HTML as a programming language
Michael Mendelsohn
I've been reading the September thread titled 'Steps beyond "Hello
World" program' and pondered HTML as a programming language.
You see, I consider adventure games to be programs - and it so happens
that some of them have been implemented in book form. It is trivially
easy to do this in HTML.
Why is this possible?
Because HTML has the possibility to branch based on user input.
In a recent thread titled "tree coloring data problem?", to curb
runtime, Peter Ammon suggested to expand the tree coloring program into
a giant state machine that would change state based on user input.
It is certainly conceivable - albeit impractical - to do this in HTML.
Produce a page for every state the system can have; have each page
display the state to the user somehow, and depending on what input the
user selects (i.e. clicks on), the browser executes a state transition.
If we are talking about Turing machines with finite memories, i.e.
finite tapes, certainly every state of the tape can be included in the
set of system states, and HTML would then in theory be no better and no
worse than general-purpose programming languages.
Programs would be quite sizeable ("huge" would still be an
understatement), but exceptionally speedy: every operation can be
executed with the speed the filesystem takes to look up the link.
For illustration, I've written a small (static) HTML program that sorts
5 numbers. You can see it at www.michael.mendelsohn.de/sort5/ .
Enjoy!
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
Casey Hawthorne
--
Regards,
Casey
Michael Mendelsohn
> Looping? Recursion?
"You're in maze of twisty passages, all alike."
Cheers
Michael Mendelsohn
> On Tue, 9 Nov 2004, Michael Mendelsohn wrote:
> Steven Rudich does exactly this in his "Great Theoretical Ideas" course
> at CMU. :) This is during the lecture in which he points out that it's
> impossible to tell "from the outside" how many states (pages) a finite
> state machine (website) has, if all the outsider can see is "accept" or
> "reject" (the page text) for the current state (page).
Ah, I've had that bookmarked already, for a time when I've got time.
> > If we are talking about Turing machines with finite memories, i.e.
> > finite tapes,
>
> Ah, but a Turing machine without an infinite tape is not a Turing
> machine! So you mean "If we are talking about finite state machines,"
> and you already said that. ;)
Well, we've discussed this here, and no computer ever made had an
infinite tape...
> > certainly every state of the tape can be included in the
> > set of system states, and HTML would then in theory be no better and no
> > worse than general-purpose programming languages.
>
> Worse, space-wise. :)
That's "in practice", not "in theory". ;)
Actually, come to think of it, it's worse in theory as well, because the
space taken up by the "program" is proportional to the complexity
(thinking "big-O") of the problem.
> > Programs would be quite sizeable ("huge" would still be an
> > understatement), but exceptionally speedy: every operation can be
> > executed with the speed the filesystem takes to look up the link.
>
> Since when are file systems "speedy"?
Since the time the flat directory has been superseded by a tree.
> > For illustration, I've written a small (static) HTML program that sorts
> > 5 numbers. You can see it at www.michael.mendelsohn.de/sort5/ .
>
> All right, now make one that prints its own source code! ;)
I think it could be doable with modern HTML; CSS provides for a
substitution mechanism. See http://www.w3.org/TR/CSS21/generate.html .
Cheers
gswork
> Dear Reader!
>
> I've been reading the September thread titled 'Steps beyond "Hello
> World" program' and pondered HTML as a programming language.
>
> You see, I consider adventure games to be programs - and it so happens
> that some of them have been implemented in book form. It is trivially
> easy to do this in HTML.
>
> Why is this possible?
> Because HTML has the possibility to branch based on user input.
>
> In a recent thread titled "tree coloring data problem?", to curb
> runtime, Peter Ammon suggested to expand the tree coloring program into
> a giant state machine that would change state based on user input.
> It is certainly conceivable - albeit impractical - to do this in HTML.
> Produce a page for every state the system can have; have each page
> display the state to the user somehow, and depending on what input the
> user selects (i.e. clicks on), the browser executes a state transition.
>
> If we are talking about Turing machines with finite memories, i.e.
> finite tapes, certainly every state of the tape can be included in the
> set of system states, and HTML would then in theory be no better and no
> worse than general-purpose programming languages.
>
> Programs would be quite sizeable ("huge" would still be an
> understatement), but exceptionally speedy: every operation can be
> executed with the speed the filesystem takes to look up the link.
>
> For illustration, I've written a small (static) HTML program that sorts
> 5 numbers. You can see it at www.michael.mendelsohn.de/sort5/ .
What i like about this is that it challenges what a program is, by
producing the html output for every possible output it looks like a
program, branching away.
Just imagine how a game of pacman, with it's user input, pixel by
pixel movement and limited mix of AI and random movement, scoring etc,
would look. a big zip file of html i'd guess! Slow too.
Bill Godfrey
> All right, now make one that prints its own source code! ;)
> I'd play with it some more. Googling "html quine" doesn't really help,
> of course. I wonder if "HTML programs" are on-topic in comp.text.sgml?)
Here's one, you'll find the file between the BEGIN and END markers.
BEGIN
END
Bill, did you miss it?
Thomas G. Marshall
> On Tue, 9 Nov 2004, Michael Mendelsohn wrote:
...[rip]...
>> If we are talking about Turing machines with finite memories, i.e.
>> finite tapes,
>
> Ah, but a Turing machine without an infinite tape is not a Turing
> machine! So you mean "If we are talking about finite state machines,"
> and you already said that. ;)
I've always viewed this as a silly detail (sorry). If we live no longer
than 150 years, then we merely need long enough tapes to last 150 years.
Who cares what states there are beyond that, or if they even exist?
{author ducks}
--
Forgetthesong,I'dratherhavethefrontallobotomy...
Michael Mendelsohn
Michael Mendelsohn
> Michael Mendelsohn <keine.Wer...@msgid.michael.mendelsohn.de> wrote in message news:<419036DB...@msgid.michael.mendelsohn.de>...
> > display the state to the user somehow, and depending on what input the
> > user selects (i.e. clicks on), the browser executes a state transition.
> > Programs would be quite sizeable ("huge" would still be an
> > understatement), but exceptionally speedy: every operation can be
> > executed with the speed the filesystem takes to look up the link.
> What i like about this is that it challenges what a program is, by
> producing the html output for every possible output it looks like a
input
> program, branching away.
>
> Just imagine how a game of pacman, with it's user input, pixel by
> pixel movement and limited mix of AI and random movement, scoring etc,
> would look. a big zip file of html i'd guess! Slow too.
Well, get a big computer, preload all images into a memory cache (or put
them on a ramdisk), and there won't be a problem.
I think you can actually place the maze in the background and use layers
to position the movable elements, so that you wouldn't have to reload
that many images.
The HTML looks a lot like a display list then.
You'd need to use an extremely short "Refresh" cycle, though.
Cheers
MIchael
Programmer Dude
> Because HTML has the possibility to branch based on user input.
No, it doesn't. Please show me the "branching" statement.
An HTML *system* including a server, browser and user may be able
to branch, but by this logic, pencil and paper is a programming
language.
Programmer Dude
>> Here's one, you'll find the file between the BEGIN and END markers.
>>
>> BEGIN
>> END
>
> The validator.w3.org does not consider the empty file valid HTML.
Rightfully so. TITLE is required. I think this should fix it....
BEGIN
<title>Bill's Program</title>
END
Michael Mendelsohn
> Arthur J. O'Dwyer coughed up:
> > machine! So you mean "If we are talking about finite state machines,"
> > and you already said that. ;)
>
> I've always viewed this as a silly detail (sorry). If we live no longer
> than 150 years, then we merely need long enough tapes to last 150 years.
> Who cares what states there are beyond that, or if they even exist?
You will be the sole culprit for the infamous Y2.15K problem!
Michael Mendelsohn
> > Michael Mendelsohn writes:
[In search of the elusive HTML quine]
> >> The validator.w3.org does not consider the empty file valid HTML.
> >
> > Rightfully so. TITLE is required. I think this should fix it....
> >
> > BEGIN
> > <title>Bill's Program</title>
> > END
>
> suspect that not only is <title> NOT required, it's actually invalid
> to put the <title> tag outside a <head> section, and it's invalid to
> put <head> outside an <html> section.
Declaring the <HEAD> and <HTML> sections is optional; you'd need a
doctype, though.
You don't need to declare the <BODY> either, but it's got to be
nonempty, says the validator. The shortest valid HTML 4.01 I can come up
with is
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<title></title>
<P>
Still a long way to go to make a quine.
Michael Mendelsohn
> Michael Mendelsohn writes:
> > Because HTML has the possibility to branch based on user input.
>
> No, it doesn't. Please show me the "branching" statement.
The branching statement is an implied
loop
case readuserclick() of
link1: goto target1
link2: goto target2
...
> An HTML *system* including a server, browser and user may be able
> to branch, but by this logic, pencil and paper is a programming
> language.
A server is not required.
The browser is the HTML interpreter; a program in an interpreted
language needs an interpreter to run, and a program in a compiled
language can't run at all, because it only runs after being translated
to machine language.
If you use the "Refresh" statement, user input is not required to change
state.
The pencil/paper/user system is limited to algorithms that merely append
the user input to the system state. ;)
Cheers
Thomas G. Marshall
> "Thomas G. Marshall" schrieb:
>> Arthur J. O'Dwyer coughed up:
>>> Ah, but a Turing machine without an infinite tape is not a Turing
>>> machine! So you mean "If we are talking about finite state
>>> machines," and you already said that. ;)
>>
>> I've always viewed this as a silly detail (sorry). If we live no
>> longer than 150 years, then we merely need long enough tapes to last
>> 150 years. Who cares what states there are beyond that, or if they
>> even exist?
>
> You will be the sole culprit for the infamous Y2.15K problem!
{chuckling...}
--
"Gentlemen, you can't fight in here! This is the War Room!"
Programmer Dude
>>> Because HTML has the possibility to branch based on user input.
>>
>> No, it doesn't. Please show me the "branching" statement.
>
> The branching statement is an implied
>
> loop
> case readuserclick() of
> link1: goto target1
> link2: goto target2
> ...
My point, exactly. The *language* has no branching statement.
A set of 3x5 index cards is just as much a "programming language"
as HTML, and works about the same. Instead of links, the cards
just contain the id numbers of other cards. The *USER* picks
a "link" on one card to go to another.
>> An HTML *system* including a server, browser and user may be able
>> to branch, but by this logic, pencil and paper is a programming
>> language.
>
> A server is not required.
In the case of browsing files, the browser itself "serves" the
files (in a much more restricted manner than real server).
> The browser is the HTML interpreter;...
I would say, rather, it's a *renderer*. It uses meta data in
the data stream to render and display that data. And then
it's done what that data stream, never to return. There's
no way for it to reach a certain point in the stream and
then loop back to an earlier point.
I think that alone would disqualify it as a programming language.
> If you use the "Refresh" statement, user input is not required
> to change state.
But you can only go to one next state that way. You're merely
extending the rendering of that single page to include a series
of pages. Is a movie projector running a language? Same thing.
Thomas G. Marshall
> Casey Hawthorne schrieb:
>> Looping? Recursion?
>
> "You're in maze of twisty passages, all alike."
Plugh or xyzzy, take your pick.
This is what I really liked and thought was inspired:
You are faced with a dragon
--> kill dragon
With what, your bare hands?
--> yes
You've killed the dragon, (amazing isn't it?)
Took me forever to stumble onto that one. Many people never did.
--
Whyowhydidn'tsunmakejavarequireanuppercaselettertostartclassnames....
Casey Hawthorne
recurse, etc. under program control -- contents of variables?
If it is only branching user control, isn't that just like shuffling a
bunch of index cards (as somebody else has pointed out)!
--
Regards,
Casey
Michael Mendelsohn
> Doesn't a programming language have to be able to branch, loop,
> recurse, etc. under program control -- contents of variables?
Why?
A program can be completely characterized by its input-output relation.
The program gets some input and provides some output. How it does that
is completely irrelevant. For reasons of economy, most programs use
branching and looping when going from input to output; HTML does that
directly.
> If it is only branching user control, isn't that just like shuffling a
> bunch of index cards (as somebody else has pointed out)!
No, it's not.
When shuffling index cards, the user performs the algorithm; with the
HTML "program", the user need only provide the input.
Have you tried my sorting program [1] mentioned upthread? All you need
to provide are the numbers 1 through 5, in any order, and the program
sorts them. You can even watch it sort them. It can sort any subset of
those 5 numbers, too!
It is easy to see that the program could be extended to sort 2^32
numbers ranging from 0 to 2^32-1, although the program would be
hopelessly, impossibly big; but conceptually, there's no problem with
that, and it is all most sorting routines implemented on today's
computers ever do.
Cheers
Michael
[1] http://www.michael.mendelsohn.de/sort5/
Randy Howard
tgm2tothe...@replacetextwithnumber.hotmail.com says...
> Michael Mendelsohn coughed up:
> > Casey Hawthorne schrieb:
> >> Looping? Recursion?
> >
> > "You're in maze of twisty passages, all alike."
>
> Plugh or xyzzy, take your pick.
That was in a different location, and I think it was "plgh"
not "plugh" was it not? (It was on the Heathkit H-89
implementation for HDOS anyway).
To get out of the maze, it was N,D,D,D.
--
Randy Howard (2reply remove FOOBAR)
Michael Mendelsohn
> Michael Mendelsohn writes:
> >>> Because HTML has the possibility to branch based on user input.
> >>
> >> No, it doesn't. Please show me the "branching" statement.
> >
> > The branching statement is an implied
> >
> > loop
> > case readuserclick() of
> > link1: goto target1
> > link2: goto target2
> > ...
>
> My point, exactly. The *language* has no branching statement.
> A set of 3x5 index cards is just as much a "programming language"
> as HTML, and works about the same. Instead of links, the cards
> just contain the id numbers of other cards. The *USER* picks
> a "link" on one card to go to another.
In the HTML case, the user just provides the input.
The program "knows" which card to branch to from that input;
the interpreter finds that card and displays it, asking for the next
input.
You can hardly fault the program for requiring the user to provide
input, can you? Some of the best programs ever written take user input.
;)
> >> An HTML *system* including a server, browser and user may be able
> >> to branch, but by this logic, pencil and paper is a programming
> >> language.
> >
> > A server is not required.
>
> In the case of browsing files, the browser itself "serves" the
> files (in a much more restricted manner than real server).
So my Desktop PC is also a file server, because when my program loads a
file, it could do so from a "real" file server, and when none is
present, my PC acts as one? You're using a definition of "server" that
is useless, because it can't distinguish anything useful.
Any anyway it doesn't matter where the program is stored and how it gets
to teh CPU that acts on it.
> > The browser is the HTML interpreter;...
>
> I would say, rather, it's a *renderer*. It uses meta data in
> the data stream to render and display that data.
It contains a renderer. And so do many other programs.
> And then
> it's done what that data stream, never to return. There's
> no way for it to reach a certain point in the stream and
> then loop back to an earlier point.
Not true at all.
Provided you have user input and programmed for that to happen. Go
through my little sort routine and click on "Restart", and you have
looped back to an earlier point.
> I think that alone would disqualify it as a programming language.
Not necessarily true.
In the thread I referenced, people were musing about programming a "Big
Trak" toy or a VCR. But then, the case for HTML is much stronger than
that.
> > If you use the "Refresh" statement, user input is not required
> > to change state.
>
> But you can only go to one next state that way. You're merely
> extending the rendering of that single page to include a series
> of pages. Is a movie projector running a language? Same thing.
What do you think a VBASIC program is doing that accepts no external
input? It is completely deterministic and can only go to one next state
from any state.
Thomas G. Marshall
>> tgm2tothe...@replacetextwithnumber.hotmail.com says...
>>> Michael Mendelsohn coughed up:
>>>> Casey Hawthorne schrieb:
>>>>> Looping? Recursion?
>>>>
>>>> "You're in maze of twisty passages, all alike."
>>>
>>> Plugh or xyzzy, take your pick.
>>
>> That was in a different location, and I think it was "plgh"
>> not "plugh" was it not? (It was on the Heathkit H-89
>> implementation for HDOS anyway).
>>
>> To get out of the maze, it was N,D,D,D.
>
> get the treasure chest. (Not in the H-89 version, maybe, but in the
> "extended" version. :) It was "plugh," but in a different location;
> and "xyzzy" was in a different location too. (So was "plover." ;)
> The only way to get out of this twisty maze was to go "back" from the
> entrance or slide down the column, IIRC.
>
> Back on topic, sort of, last summer I got about halfway through
> writing an adaptation of Colossal Cave in Perl CGI. It's one big
> CGI program, which generates an HTML page describing the current room
> in which various words are linked to other rooms' pages. Inventory
> and state information is tracked in the CGI parameter string. It
> got boring after a while, and I let the free-CGI-hosting account
> I was using to test it expire. The magic words are tricky to preserve
> in HTML. ;)
>
> -Arthur,
> noside samoht
!sttawagig 12.1
--
Framsticks. 3D Artificial Life evolution. You can see the creatures
that evolve and how they interact, hunt, swim, etc. (Unaffiliated with
me). http://www.frams.alife.pl/
Michael Mendelsohn
> > Casey Hawthorne schrieb:
> > A program can be completely characterized by its input-output relation.
> > The program gets some input and provides some output. How it does that
> > is completely irrelevant. For reasons of economy, most programs use
> > branching and looping when going from input to output; HTML does that
> > directly.
>
> algorithms --- some programs, some input-output relationships --- that
> simply require the use of loops. Some algorithms *cannot* be represented
> by a finite state machine, no matter how big. One example would be a
> program that reads input until it finds a "Q", and then prints out all
> the input it's seen before that point... in reverse order. No HTML
> finite state machine can duplicate that relationship; it requires a
> "push-down automaton" --- an FSM connected to a data stack. Your
> simplistic HTML model has no such "stack."
This is not a problem.
An actual PDA would have a finite stack, and then I can make it part of
the state space of my HTML FSM.
If you insist, I could rig a simple demo. It would print "out of stack
space" for certain inputs (almost all of them, I'm sad to say). However,
I doubt you can show me a working PDA that doesn't. 8)
> >> If it is only branching user control, isn't that just like shuffling a
> >> bunch of index cards (as somebody else has pointed out)!
> >
> > No, it's not.
> >
> > When shuffling index cards, the user performs the algorithm; with the
> > HTML "program", the user need only provide the input.
>
> A nonsensical distinction. Where do you draw the line between "using an
> input device" and "performing an algorithm"? If the user has to turn a
> crank in order to get results, is he "performing" an algorithm? Suppose
> he has to turn a crank simply in order to see a placard informing him
> which lever to pull in order to get results --- is he "performing" yet?
Ok, I grant you this: if an algorithm is affixed to note cards, and a
user faithfully executes it, never exercising his free will, the system
can be, under certain cirumstances, be considered a Turing machine (or.,
let's say, mainly due to the finiteness of the user, a FSM).
While this is as good a place as any to take up Searle's Chinese Room
argument, I suggest you change the topic if you intend to.
Douglas Adams was another author who popularized the notion of humans
executing a computer program... ;)
My point is that my program does nothing less than a C program does that
reads from stdin when stdin is connected to a keyboard.
"Press number 1 on keyboard and hit enter" simply becomes "click on
number 1 with mouse".
> > Have you tried my sorting program [1] mentioned upthread? All you need
> > to provide are the numbers 1 through 5, in any order, and the program
> > sorts them. You can even watch it sort them. It can sort any subset of
> > those 5 numbers, too!
>
> It's not sorting them --- the user is sorting them! After all, for
> your little demonstration to prove anything, I have to know it actually
> works... and to know that, I have to sort the numbers myself, don't I? ;-)
If you sort them yourself, you will find out that the machine has sorted
them correctly for you. You do not have to click on the numbers in sort
order!
However, to prove that my state machine correctly sorts your input in
any case, I'd have to show some proofs that employ certain invariants I
took care to observe when constructing the "program".
> Serious points: (1) Lose the "inputting/performing" semantic argument;
> it's a hopeless case. (2) And learn the fundamental differences between
> FSMs, PDAs, and Turing machines.
Thanks for the hint.
I never claimed Turing completeness; contrariwise, I claim that any
existing computer can't be more than a FSM - and that thus my HTML
machine can (in theory) be programmed to do everything a computer can be
programmed to do.
> (I'm not (yet) denying that standard HTML (4.0) might be
> Turing-complete, since I haven't gotten the time to investigate it yet,
> but certainly Michael's simple arguments aren't valid.)
I'll not be overly concerned if my arguments should turn out not to be
valid; but at thi spoint, I'm still trying to hold the fort a little
longer.
Cheers
Michael
Randy Howard
a...@nospam.andrew.cmu.edu says...
> >>> "You're in maze of twisty passages, all alike."
> >>
> >> Plugh or xyzzy, take your pick.
> >
> > That was in a different location, and I think it was "plgh"
> > not "plugh" was it not? (It was on the Heathkit H-89
> > implementation for HDOS anyway).
> >
> > To get out of the maze, it was N,D,D,D.
>
> get the treasure chest. (Not in the H-89 version, maybe, but in the
> "extended" version. :)
Perhaps so, that's why I posted the version.
> It was "plugh," but in a different location;
> and "xyzzy" was in a different location too.
I remember them being different, and in different locations. I could
swear that it was plgh in that version though. It has been at least
15 years, perhaps longer since I saw it running though, so...
> (So was "plover." ;)
Yes, I remember that one vaguely now that you mentioned it.
> The only way to get out of this twisty maze was to go "back" from the
> entrance or slide down the column, IIRC.
In the Heath version, no matter where you were in the maze, N,D,D,D would
drop you out of it.
> Back on topic, sort of, last summer I got about halfway through
> writing an adaptation of Colossal Cave in Perl CGI. It's one big
> CGI program, which generates an HTML page describing the current room
> in which various words are linked to other rooms' pages. Inventory
> and state information is tracked in the CGI parameter string. It
> got boring after a while, and I let the free-CGI-hosting account
> I was using to test it expire. The magic words are tricky to preserve
> in HTML. ;)
Strange, about the same time I decided to take a version of it in ancient
pre-ANSI C I found on a website and "port" it (bring up to date more-like)
to C-89 at least, and make it compile cleanly on Linux. Got it working
in a half-day or so, then promptly lost interest again.
It's just not what is was 20 years ago. Compare to something like FarCry
today. :-)
Craig Nicol
> "Arthur J. O'Dwyer" schrieb:
> > On Tue, 9 Nov 2004, Michael Mendelsohn wrote:
>
> > > For illustration, I've written a small (static) HTML program that sorts
> > > 5 numbers. You can see it at www.michael.mendelsohn.de/sort5/ .
> >
> > All right, now make one that prints its own source code! ;)
>
> I think it could be doable with modern HTML; CSS provides for a
> substitution mechanism. See http://www.w3.org/TR/CSS21/generate.html .
If anyone wants to take up the challenge, here's a start of at HTML
Quine, unfortunately all the major browsers (Mozilla, IE and Opera
I've tested) treat a </style> tag in the content text as the end of
the style section so that has to be escaped. Anyone got any ideas how
to fix that?
Oh, and you might need to remove all line feeds to make it work
properly.
Craig.
File follows:
<html>
<head>
<title>Quine</title>
<style type="text/css">
.c { display : inline }
.c:before { content : '\<html\>\<head\>\<title\>Quine</title>\<style
type="text/css"\>.c { display : inline } .c:before { content : ' }
.c:after { content : "\</style\></head><body><span class=c>\'<p
class=c>'} .c:after { content : \"</p>\" }</div></body></html>" }
</style>
</head>
<body>
<span class=c>'<p class=c>'} .c:after { content : "</p>"
}</div></body></html>
tinyurl.com/uh3t
> What do you think a VBASIC program is doing that accepts no external
> input? It is completely deterministic and can only go to one next
> state from any state.
You're making the same mistake that other fellow did in one of those
old threads, the fellow who claimed that because C can be used to write
a "hello world" program then C is no more a programming language than
HTML is. (That's the remark that got me started on the steps beyond
"hello world" thread.) Just because C or VB *can* be used to write a
trivial program, doesn't mean the language is *limited* to such trivial
programs. In fact C or VB can be used to write much more than trivial
programs, whereas HTML cannot. (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.) So C and VB are true programming languages,
whereas HTML isn't.
Now if you cheat by augmenting HTML with plugins such as JavaScript or
applets or CGI or that other thing you mentionned, then the augmented
HTML-plus-something may be a real programming language. But plain
vanilla HTML without any plugin is *not* a real programming langauge
per my definition above.
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.
This cost factor is the main reason why we nowadays use computers
(including pocket calculators) to generate answers on the fly whenever
possible, rather than use the ancient practice of printing all possible
answers in book form such as trigonometry tables and gunnery aiming
tables etc.
Michael Mendelsohn
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.
tinyurl.com/uh3t
> An actual PDA would have a finite stack, and then I can make it part
> of the state space of my HTML FSM.
That's not HTML being the programming language. That's HTML being used
as a user-interface for a stack machine. It's the stack machine which
has the many states, not the HTML pseudo-computer.
The topic was whether HTML by itself, not as a user-interface for CGI
or JSP or some other "real" programming system, was itself, all by
itself without help from anything more powerful, a true programming
language.
You need to look at my example of a shell script as a trampoline for
launching awk and other CGI applications, where awk etc., not the shell
script, gets credit for the "real" computing. Likewise the stack, not
HTML, gets credit for the large number of machine states possible in
your proposed device.
> My point is that my program does nothing less than a C program does
> that reads from stdin when stdin is connected to a keyboard. "Press
> number 1 on keyboard and hit enter" simply becomes "click on
> number 1 with mouse".
You're making that same mistake again. Just because you can write a C
program that is so stupid it doesn't do any nontrivial calculation,
doesn't mean that C isn't a real programming language, or that such
trivial programs are typical of what C can do. But HTML simply cannot
do any nontrivial calculation. All that HTML can do is (1) select from
a fixed set of pre-arranged choices, and (2) pass data (through a FORM)
to some other program which is written in a *real* programming language
unlike HTML. Any real programming language can be used to write a
trivial program. But a trivial language like HTML cannot be used to
write a non-trivial program. It's the same as any human can act stupid
like a chimpanzee, but no chimpanzee can act intelligent like a human
such as by writing a computer program from scratch to solve a new task,
or playing well a difficult game such as Chess or Go.
> > Have you tried my sorting program [1] mentioned upthread? All you need
> > to provide are the numbers 1 through 5, in any order, and the program
By the way, your program can't sort five numbers. It can only sort the
five numbers it already knows about. I bet you can't write a pure-HTML
"program" to sort five numbers where each number can be anything the
user chooses in the range of 0 to 29999. The user interface part is in
principle easy: have the user select the 10k digit of the first number,
which takes the user to another WebPage that has that already picked
and the user then picks the 1k digit of that same first number, which
takes the user to a third WebPage where the first two digits are
selected and the user clicks on the hundreds digit, likewise the tens
digit, likewise the ones digit, and then the user gets to pick the 10k
digit of the second number, etc. Just doing the input would require
more than 30000**5 separate WebPages, far more than you can fit on your
server, right?
e-Mergence Consultant
Sure that u're right, but aniway i think that we must reconsider the question.
Coming back soon
e-Mergence Consultant
www.emergence-consultant.com
Programmer Dude
>> 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.
That is *exactly* the usual distinction. C and VB are
programming languages. HTML is not.
The fact that you can string a series of user-driven
pages together does not make it a programming language.
It merely means you can use some things beyond their
functional use in some fashion with a little help.
I would consider the *defining* feature of a programming
language the ability of the language to branch ON ITS
OWN due to a perceived state.
All programming language can do this with ease.
HTML cannot.
dark...@gmail.com
program in 100% html with no javascript or php or dhtml or anything
that has a text box (such as the one I am typing in right now) and will
allow me to type a message and then display it back to me.
I can do the same thing in a real language with about 10 minutes of
coding... if that even.
Dave Vandervies
Let's see you do that in Prolog.
(Postscript would also be interesting. If it's powerful enough to
implement a ray tracer, it's got to be a real language, no?)
dave
(For that matter, how 'bout a turing machine? Untyped Lambda calculus?)
--
Dave Vandervies dj3v...@csclub.uwaterloo.ca
[I]s this what mathematicians do for a living? Whose pocket pays for them do
it? Why? Is it as much fun as it looks, when you're getting paid to do it?
--Chris Redmond in uw.general
tinyurl.com/uh3t
> 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.
gswork
that's the kind of thing that can be done in one little line in some
scripting langages, or another langauge raised in this thread; VB
MsgBox InputBox("input!") ' a full GUI implementation!! ;)
the question of HTML as a language is one of those interesting ones
whereby, if we disregarded practicalities such as servers with
billions of html pages, we could produce 'websites' that behaved like
simple branching programs. The problem is matching all possible
states with a page, it quickly unravels when doing something like
random number generation, I/O and more complex conditional branching.
It becomes clear that a webserver the size of Jupiter would quickly be
outdone by a progam written in QBasic!
Doesn't stop the idea from being interesting though!
Programmer Dude
> the question of HTML as a language is one of those interesting ones
Speak for yourself! I don't find it interesting in the least! (-:
One more time: HTML is a ***markup*** language. It is a "meta" language
for adding meta information to an information stream.
That you can use it to cobble together something that resembles a
running program doesn't change this.
Thomas G. Marshall
> has been dominated by people's confusion between FSMs and "real"
> Turing-complete languages. (Scare quotes intentional
Bingo, we have a winner. I've seen the TC words brought up in an effort to
spook the crowd more than once.
...[rip]...
--
"His name was Robert Paulson. His name was Robert Paulson. His name was
Robert Paulson..."
Edward G. Nilges
> "Arthur J. O'Dwyer" schrieb:
> > On Tue, 9 Nov 2004, Michael Mendelsohn wrote:
>
> > at CMU. :) This is during the lecture in which he points out that it's
> > impossible to tell "from the outside" how many states (pages) a finite
> > state machine (website) has, if all the outsider can see is "accept" or
> > "reject" (the page text) for the current state (page).
>
> Ah, I've had that bookmarked already, for a time when I've got time.
>
> > > If we are talking about Turing machines with finite memories, i.e.
> > > finite tapes,
> >
> > Ah, but a Turing machine without an infinite tape is not a Turing
> > machine! So you mean "If we are talking about finite state machines,"
> > and you already said that. ;)
>
> infinite tape...
Yeah, we have, and nobody yet understands mathematical intuitionism,
apparently.
The Turing tape doesn't have to be physically infinite and in fact
will work fine with a finite set of squares (Web pages!? Yikes. OK.)
The problem is that it must have the Intuitionist capability of ADDING
a tape square to the left or right of the working set at any time.
Turing was of course silent on how this operation would be
implemented, whether splicing the tape as in film school, or moseying
down to CDW for memory chips.
Thanks to Anglo-American philosophical hegemony as it infects computer
science, nearly all computer scientists are unconscious Platonists who
believe only in one type of infinity, a finished and perfected
infinity ("infinite in all directions"). This has produced the nasty
phenomenon of American "scientific fundamentalism" and its nealry
religious intolerance, not only of religion, but also of imagination.
To my knowledge pure HTML cannot do this but I will check out this
discussion at greater leisure to see if it can. Who knows what dark
secrets the script kiddies know? Hell, I'm a script kiddie according
to some clowns in this ng. I wrote a compiler in Visual Basic, which
was blasphemy in some circles. If someone can write a Turing Machine
simulator in pure HTML with no constant restriction on states, squares
or symbols, then I will admit that pure HTML is Turing complete.
Edward G. Nilges
> Arthur J. O'Dwyer coughed up:
> > On Tue, 9 Nov 2004, Michael Mendelsohn wrote:
>
>
> >> If we are talking about Turing machines with finite memories, i.e.
> >> finite tapes,
> >
> > Ah, but a Turing machine without an infinite tape is not a Turing
> > machine! So you mean "If we are talking about finite state machines,"
> > and you already said that. ;)
>
> than 150 years, then we merely need long enough tapes to last 150 years.
> Who cares what states there are beyond that, or if they even exist?
Ah, a mathematical Intuitionist. Good lad.
>
> {author ducks}
Programmer Dude
>>> the question of HTML as a language is one of those interesting ones
>>
>> Speak for yourself! I don't find it interesting in the least! (-:
>> One more time: HTML is a ***markup*** language. It is a "meta"
>> language for adding meta information to an information stream.
>
> I agree with you that HTML is a markup language, and that this thread
> has been dominated by people's confusion between FSMs and "real"
> Turing-complete languages. [snip]
>
> But I wouldn't be surprised if Turing-completeness had slipped into
> HTML somewhere along the way, the same way TC seems to slip into any
> sufficiently complex tool..
But I don't know if I'd call HTML a complex tool. And I would be
surprised to find out its TC (in the casual definition).
> So I find that question interesting. Not terribly /deep/, no---it's
> just a yes-or-no question ("Is HTML 4.0 Turing-complete?")---but
> I would like to know the answer sometime.
That is a different--and I agree slightly interesting--question.
Programmer Dude
>>> The branching statement is an implied
>>>
>>> loop
>>> case readuserclick() of
>>> link1: goto target1
>>> link2: goto target2
>>> ...
>>
>> My point, exactly. The *language* has no branching statement.
>> A set of 3x5 index cards is just as much a "programming language"
>> as HTML, and works about the same. Instead of links, the cards
>> just contain the id numbers of other cards. The *USER* picks
>> a "link" on one card to go to another.
>
> In the HTML case, the user just provides the input.
That's exactly what we keep trying to tell you. The *user* is
the computational mechanism here--not the HTML.
> The program "knows" which card to branch to from that input;
The program don't know squat. The *user* looking at the rendered
HTML "knows" which link to click.
> You can hardly fault the program for requiring the user to provide
> input, can you? Some of the best programs ever written take user
> input. ;)
Of course not, but that has nothing to do with anything. There is
a huge difference between a user providing *data* and a user playing
the role of the computational device.
Is an abacus a computational device or just a very slick way of
helping a human be a computational device?
>> In the case of browsing files, the browser itself "serves" the
>> files (in a much more restricted manner than real server).
>
> So my Desktop PC is also a file server, because when my program
> loads a file, it could do so from a "real" file server, and when
> none is present, my PC acts as one? You're using a definition of
> "server" that is useless, because it can't distinguish anything
> useful.
As opposed to a definition of "programming language" so useless that
a set of 3x5 index cards qualifies? (-:
Your PC--your operating system specifically--IS a file server. For
example, my desktop often serves files to my laptop.
>> And then it's done what that data stream, never to return. There's
>> no way for it to reach a certain point in the stream and then
>> loop back to an earlier point.
>
> Not true at all.
Totally true.
> Provided you have user input and programmed for that to happen. Go
> through my little sort routine and click on "Restart", and you have
> looped back to an earlier point.
No, you've just shuffled the cards to the first one.
I don't know if you're playing troll, or if you really don't get this,
but the point we've made over and over is that without user intervention,
your HTML "programming language" doesn't work *AT* *ALL*. It cannot
be given a dataset and sent off to process that data.
> In the thread I referenced, people were musing about programming a
> "Big Trak" toy or a VCR.
"Musing about "does not mean defining such as programming.
> But then, the case for HTML is much stronger than that.
Actually, I'd say it's worse. In those cases a stored program was
provided which was executed by the devices. Most importantly, there
are branch and control points followed by the devices. Once a web
browser starts rending an HTML page, that's it. One shot deal.
>> But you can only go to one next state that way. You're merely
>> extending the rendering of that single page to include a series
>> of pages. Is a movie projector running a language? Same thing.
>
> What do you think a VBASIC program is doing that accepts no external
> input? It is completely deterministic and can only go to one next
> state from any state.
Those state transitions are typically guided by branch or selection
statements in the language, so right away there's a significant
difference. Second--and more critically--just because we can use
a real programming language to do something trivial and stupid
doesn't have any meaning with regard to what HTML is.
dark...@gmail.com
with, its the simple stuff. How can you take input without links? You
can't!!! Textboxes and such require Javascript, PHP, SOMETHING to get
that data.
I think its safe to assume all real programming languages have
variables and can perform math functions. Do this with html for me
please.
C/C++
int x = 2;
int y = 5;
int z = x + y;
printf("%d", z);
Java
int x = 2;
int y = 5;
int z = x + y;
System.out.println(z);
PHP
$x = 2;
$y = 5;
$z = x + y;
echo $z;
Even if you only know one of the languages its pretty easy to see how
they work for all three. Even if you dont know ANY programming I am
sure you can get an educated guess as to what the program is going to
output. It will print out 7. Go ahead and make this program for me in
HTML. Don't just make a page that will display 7... because thats no
different than the following...
printf("7");
System.out.println("7");
echo "7";
Do you see the difference? Now I suppose you could make an html LIKE
syntax for a language. Please note this language doesnt exist but I
suppose it would be technically possible to do this.
<int><x>2</x></int>
<int><y>5</y></int>
<int><z> <plus> <x></x> <y></y> </plus> </int>
<print> <z></z> </print>
As far as I know... such a language does not exist. Maybe it does, I
dont know. But like I said before... its only html LIKE syntax. Not
actual html.
Dan Tex1
Anyone wanting to actually use it to write codes is probably a bit nuts. Even
if it were "theoretically" a language, I don't see any use that can come from
having this type of knowledge. To call it academic might even be a low blow to
academicians everywhere.
Dan :-)
Gerry Quinn
dark...@gmail.com says...
> Its more than just this advanced stuff that you guys are countering
> with, its the simple stuff. How can you take input without links? You
> can't!!! Textboxes and such require Javascript, PHP, SOMETHING to get
> that data.
>
> I think its safe to assume all real programming languages have
> variables and can perform math functions. Do this with html for me
> please.
>
> C/C++
>
> int x = 2;
> int y = 5;
> int z = x + y;
> printf("%d", z);
Just read off the unary value of 2 + 3:
<HTML>
<HEAD>
<TITLE>Addition Example</TITLE>
</HEAD>
<BODY>
<TABLE CELLSPACING=0 BORDER=0 CELLPADDING=0>
<TR>
<TD WIDTH=2 BGCOLOR="#ff0000"></TD>
<TD WIDTH=3 BGCOLOR="#ffff00"></TD>
</TR>
</TABLE>
</BODY>
</HTML>
- Gerry Quinn