good chemistry is complicated,and a little bit messy -LW PerlMonks

### Re^2: OT: Mathematics for programming (again)

by mpeg4codec (Pilgrim)
 on Sep 11, 2008 at 07:04 UTC ( #710544=note: print w/replies, xml ) Need Help??

I imagine w-ber is only considering Turing-complete programming languages in this discussion (of which SQL is not one). Since all Turing-complete languages can simulate one another, and since at least one Turing-complete language has loops (Perl, for instance), then all Turing-complete languages must have some equivalent to looping. It may have to be simulated, and that simulation may not be efficient, but it's there nonetheless from a mathematical standpoint.
• Comment on Re^2: OT: Mathematics for programming (again)

Replies are listed 'Best First'.
Re^3: OT: Mathematics for programming (again)
by Jenda (Abbot) on Sep 11, 2008 at 10:27 UTC

Equivalent to looping, I buy that. But equivalent_to_X ne X.

The fact that I can move and use legs for that doesn't mean that since a car can move as well it's got to have legs.

More specifically, any language that has goto, conditional jumps, or continuations can be used to implement loops if they don't have native loops. Any language which can build and walk a tree or list can be used to implement a loop, too. Any language in which one can attach arbitrary actions to an iterator has a basic looping construct. Any language that can both increment or decrement an integer value and evaluate data as code can be used to implement loops.

Things equivalent to loops in one situation or another include recursion, vector operators, iterators, and repetition operators. Tail recursion or mutual recursion between two subroutines can be converted into a looping construct. Vector operators are made up of loops unless they are using special explicitly parallel hardware. Iterators can both be the basis of a loop and can be implemented using a loop or some loop equivalent. Repetition operators are usually implemented as loops, but could be implemented using recursion, conditional jumps, lists, set manipulations, vector ops, or continuations. Any language in which you can construct, transform, and test arbitrary sets in arbitrary ways can be used as an equivalent to loops, too.

SQL is a declarative set specification and transformation language. Where the loops in SQL are is obvious if you look at the issue sideways: they are implicit. SELECT, UPDATE, and DELETE are vector operators and WHERE confines the members of the vector to some subset of the master set. INSERT is a vector operator which adds to the master set. Each SQL statement (barring special functions) is a subset specification, set growth or shrinkage operation, or transformation on (sub)set members. There generally is an iterative or recursive program in charge of getting you the proper results for your requested set. You're just not writing it. It's the product of translation and happens inside the database software's planning and execution engines. Still, since SQL can store, transform, and test arbitrary sets in arbitrary ways, it can be used equivalently to a language with explicit loops in regards to those sets.

That's a bit backwards: HOW it gets there is unimportant. That it can accomplish the task eventually is what really matters.

If the Car and the Person were both Touring [sic] complete, and it is known that the Person can Tour France (using feet) then the implication is that the Car can Tour France as well. How it accomplishes that (with wheels) and how long it takes is unimportant. It can simulate the Human's route and make the Tour because it is, by definition, Touring complete.

• Making a Tour = Loops
• Touring France = Looping over all elements in a list of cities
• Using Feet = "for" statement
• Using Wheels = "JMP" statement

You did not leave von Neumann there. Not "for" and "JMP", but rather "for" and "recursion". And recursion in a language that doesn't have mutable variables. And

• Making a Tour = implementing an algorithm
• Touring France = creating the program
• Using Feet = using loops
• Using Wheels = using recursion

The thing is not whether it's possible to implement the same algorithms, but whether reasoning about the individual building blocks of one kind of programming languages will be useful for other kinds.

With your "for" vs "JMP" you've stayed within the von Neumann architecture, there are languages that are built on , say, lambda calculus. And even though both are turing complete and may be used to implement the same algorithms and eventualy transform the same data to the same result, their building blocks are different.

Re^3: OT: Mathematics for programming (again)
by TGI (Parson) on Sep 13, 2008 at 02:54 UTC

Create A New User
Node Status?
node history
Node Type: note [id://710544]
help
Chatterbox?
 [shmem]: ctags is a program which (recursively) extracts the symbols from source and stores them in a one-file database. This allows you to query the locations where these symbols (e.g. a subroutine name) are used anywhere in the source code tree... [shmem]: ...from inside the editor. [shmem]: apt-get install exuberant-ctags [Lady_Aleena]: I think I heard vim has a big learning curve. [shmem]: then in the root of your source tree run: ctags -R [shmem]: you get a file named tags where all symbols and the places where they are used are listed [Lady_Aleena]: geany may not support that. [shmem]: I see that there is a plugin geany-plugin- codenav [shmem]: maybe that supports ctags, check the documentation

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (10)
As of 2017-04-27 12:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I'm a fool:

Results (506 votes). Check out past polls.