Navigating from Dr. Niklaus Wirth's wikipedia web page, I could find a very interesting interview conversation, Dr. Wirth had, on the following web site (ref, http://www.eptacom.net/pubblicazioni/pub_eng/wirth.html).
This interview is dated, in 1997. I found Dr. Wirth's views in this interview, quite good to read.
Something interesting to share, I thought!
Showing posts with label theory. Show all posts
Showing posts with label theory. Show all posts
Saturday, July 18, 2009
Sunday, July 12, 2009
Niklaus Wirth: On recursive algorithms
I have started reading the computer science, classic collection "ALGORITHMS + DATA STRUCTURES = PROGRAMS" by Niklaus Wirth. Dr. Wirth wrote this text in 1975. It's a great book.
Though "recursive algorithms" are widely known to computer science community since long time, I still could find some good advice in Dr. Wirth's book on usage of recursive algorithms.
Dr. Wirth mentions:
"An object is said to be recursive if it partially consists or is defined in terms of itself. Recursion is a particularly powerful means in mathematical definitions. The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions."
We all know, what recursive algorithms are. It's a widely known programming technique. But I found particularly the advice, "When not to use recursion" in Dr. Wirth's book very worth while to apply.
Dr. Wirth further mentions:
"Recursive algorithms are particularly appropriate when the underlying problem or the data to be treated are defined in recursive terms. This does not mean, however, that such recursive definitions guarantee that a recursive algorithm is the best way to solve the problem.
Programs in which the use of algorithmic recursion is to be avoided can be characterized by a schema which exhibits the pattern of their composition. Such schema's can described as following:
[1]
P => if B then (S; P)
or, equivalently
P => (S; if B then P)
"
Dr. Wirth illustrates this principle with a well known, recursive definition of the factorial computation (mentioned below):
F0 = 1
F(i+1) = (i + 1) * f(i)
Dr. Wirth maps the factorial problem with the recursive anti-pattern he defines ([1] above):
[2]
P => if I < n then (I := I + 1; F := I * F; P)
I := 0; F := 1; P
In the above definition [2], S (ref, [1]) refers to,
I := I + 1; F := I * F
Dr. Wirth in the book, illustrates a following, iterative definition of factorial computation:
Dr. Wirth says, "The lesson to draw is to avoid the use of recursion when there is an obvious solution by iteration.
This, however, should not lead to shying away from recursion at any price. The fact that implementations of recursive procedures on essentially non-recursive machines exists proves that for practical purposes every recursive program can be transformed into a purely iterative one. This, however, involves the explicit handling of a recursion stack, and these operations will often obscure the essence of a program to such an extent that it becomes most difficult to comprehend. The lesson is that algorithms which by their nature are recursive rather than iterative should be formulated as recursive procedures."
Just thought of sharing a bit of text, from this nice book and encouraging readers to read the book!
Though "recursive algorithms" are widely known to computer science community since long time, I still could find some good advice in Dr. Wirth's book on usage of recursive algorithms.
Dr. Wirth mentions:
"An object is said to be recursive if it partially consists or is defined in terms of itself. Recursion is a particularly powerful means in mathematical definitions. The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions."
We all know, what recursive algorithms are. It's a widely known programming technique. But I found particularly the advice, "When not to use recursion" in Dr. Wirth's book very worth while to apply.
Dr. Wirth further mentions:
"Recursive algorithms are particularly appropriate when the underlying problem or the data to be treated are defined in recursive terms. This does not mean, however, that such recursive definitions guarantee that a recursive algorithm is the best way to solve the problem.
Programs in which the use of algorithmic recursion is to be avoided can be characterized by a schema which exhibits the pattern of their composition. Such schema's can described as following:
[1]
P => if B then (S; P)
or, equivalently
P => (S; if B then P)
"
Dr. Wirth illustrates this principle with a well known, recursive definition of the factorial computation (mentioned below):
F0 = 1
F(i+1) = (i + 1) * f(i)
Dr. Wirth maps the factorial problem with the recursive anti-pattern he defines ([1] above):
[2]
P => if I < n then (I := I + 1; F := I * F; P)
I := 0; F := 1; P
In the above definition [2], S (ref, [1]) refers to,
I := I + 1; F := I * F
Dr. Wirth in the book, illustrates a following, iterative definition of factorial computation:
I := 0;
F := 1;
while I < n do
begin I := I + 1; F := I * F
end
Dr. Wirth says, "The lesson to draw is to avoid the use of recursion when there is an obvious solution by iteration.
This, however, should not lead to shying away from recursion at any price. The fact that implementations of recursive procedures on essentially non-recursive machines exists proves that for practical purposes every recursive program can be transformed into a purely iterative one. This, however, involves the explicit handling of a recursion stack, and these operations will often obscure the essence of a program to such an extent that it becomes most difficult to comprehend. The lesson is that algorithms which by their nature are recursive rather than iterative should be formulated as recursive procedures."
Just thought of sharing a bit of text, from this nice book and encouraging readers to read the book!
Sunday, June 21, 2009
Primitive long a subtype of float
The Java language specification defines, that primitive "long" is a subtype of primitive "float" (ref, http://java.sun.com/docs/books/jls/third_edition/html/typesValues.html#4.10.1).
But XML Schema Datatypes spec, shows no relationship between xs:float and xs:long (
ref: XML Schema 1.0 data types, XML Schema 1.1 data types).
I'm a little confused, that which concept is correct (Java's definition of this data-type inheritance, or XML Schema). I seem to be in favor of XML Schema definition. But perhaps, XML Schema type system is for XML oriented data, and Java type system is for a wider class of applications. But I'm not sure, if this is the reason for the differences of definitions in Java language spec and XML Schema.
But XML Schema Datatypes spec, shows no relationship between xs:float and xs:long (
ref: XML Schema 1.0 data types, XML Schema 1.1 data types).
I'm a little confused, that which concept is correct (Java's definition of this data-type inheritance, or XML Schema). I seem to be in favor of XML Schema definition. But perhaps, XML Schema type system is for XML oriented data, and Java type system is for a wider class of applications. But I'm not sure, if this is the reason for the differences of definitions in Java language spec and XML Schema.
Saturday, May 30, 2009
Function parameters vs global variables
I bumped upon this problem, and thought of sharing my experiences here.
There are occasions, where I have to write an XSLT function and simply use it. For e.g. (this is just an illustration. we could have more function parameters, and a different return type),
The evaluation of this function also depends on some data/information other than the parameters being passed. This external information on which the function depends, could be a global variable. Say for e.g.,
In my case, this is a fairly static data (the variable, $someList), and is needed for the evaluation of above function.
I could see two option, on how the function may use an external data ($someList in this case):
1) Have an external data as a global variable (as illustrated above)
2) Supply this data as additional function parameter
I was in a sort of dilemma recently, where I had to decide whether I should go for option 1) or 2).
In my case, I opted for option 1) i.e., the global variable.
I can think of few pros and cons of both of the above options:
1. Having a global variable: This is good, if the external information is fairly static and perhaps has big chunk of data. Having global variable could be also useful, if the data is shared between multiple functions.
2. Having a parameter for the data: This option looks good from the point of view of the principle of composability. Functional programming advocates like this idea. I think, in classical computer science theory, a function (a callable module) is an abstraction which takes some input and produces some output. I think, the notion of functions accessing data which exists outside it's body is a mechanism devised by specific programming languages, and not as such defined by computer science theory. So from the point of view of this idea, having parameter for data is a good option. In fact I would also support this option, as far as possible.
In my case, I was working with XSLT. But I guess, these concepts would apply to many of other programming languages as well.
This topic could turn into a discussion, about how we must write good computer programs.
Any ideas are welcome please.
There are occasions, where I have to write an XSLT function and simply use it. For e.g. (this is just an illustration. we could have more function parameters, and a different return type),
<xsl:function name="fn:somefunction" as="xs:boolean">
<xsl:param name="pName" as="xs:string" />
<!-- use $pName and the variable, $someList (defined below) -->
<xsl:sequence select="something.." />
</xsl:function>
The evaluation of this function also depends on some data/information other than the parameters being passed. This external information on which the function depends, could be a global variable. Say for e.g.,
<xsl:variable name="someList" as="element()+">
<x>a</x>
<x>b</x>
..
..
</xsl:variable>
In my case, this is a fairly static data (the variable, $someList), and is needed for the evaluation of above function.
I could see two option, on how the function may use an external data ($someList in this case):
1) Have an external data as a global variable (as illustrated above)
2) Supply this data as additional function parameter
I was in a sort of dilemma recently, where I had to decide whether I should go for option 1) or 2).
In my case, I opted for option 1) i.e., the global variable.
I can think of few pros and cons of both of the above options:
1. Having a global variable: This is good, if the external information is fairly static and perhaps has big chunk of data. Having global variable could be also useful, if the data is shared between multiple functions.
2. Having a parameter for the data: This option looks good from the point of view of the principle of composability. Functional programming advocates like this idea. I think, in classical computer science theory, a function (a callable module) is an abstraction which takes some input and produces some output. I think, the notion of functions accessing data which exists outside it's body is a mechanism devised by specific programming languages, and not as such defined by computer science theory. So from the point of view of this idea, having parameter for data is a good option. In fact I would also support this option, as far as possible.
In my case, I was working with XSLT. But I guess, these concepts would apply to many of other programming languages as well.
This topic could turn into a discussion, about how we must write good computer programs.
Any ideas are welcome please.
Saturday, February 28, 2009
Ptarithmetic: logic in computer science
A post on comp.theory newsgroup referred to this paper, by Giorgi Japaridze. I read a bit of this paper, and believe the thoughts presented here are quite promising (at least, I found the goal of this study quite ambitious). I guess, people with interest in computer logic might find this interesting.
This paper introduces ptarithmetic (short for "polynomial time arithmetic") - a formal number theory similar to the well known Peano arithmetic, but based on the recent, computability logic instead of classical logic.
The arithmetic primitives defined in this theory, compute in polynomial time (as against classical logic, operations in which can compute in exponential or combinatorial time).
This paper introduces ptarithmetic (short for "polynomial time arithmetic") - a formal number theory similar to the well known Peano arithmetic, but based on the recent, computability logic instead of classical logic.
The arithmetic primitives defined in this theory, compute in polynomial time (as against classical logic, operations in which can compute in exponential or combinatorial time).
An ideal compiler architecture
I found the compiler architecture description here, http://lambda.uta.edu/cse5317/notes/node5.html to be the most appealing from all the definitions I have read upto now.
Particularly I like the following idea:
"Suppose that you want to build compilers for n programming languages (eg, FORTRAN, C, C++, Java, BASIC, etc) and you want these compilers to run on m different architectures (eg, MIPS, SPARC, Intel, alpha, etc). If you do that naively, you need to write n*m compilers, one for each language-architecture combination.
The holly grail of portability in compilers is to do the same thing by writing n + m programs only. How? You use a universal Intermediate Representation (IR) and you make the compiler a two-phase compiler. An IR is typically a tree-like data structure that captures the basic features of most computer architectures. The first phase of this compilation scheme, called the front-end, maps the source code into IR, and the second phase, called the back-end, maps IR into machine code. That way, for each programming language you want to compile, you write one front-end only, and for each computer architecture, you write one back-end. So, totally you have n + m components."
Though the above idea of compiler construction is quite ideal, the author cautions with these statements:
"But the above ideal separation of compilation into two phases does not work very well for real programming languages and architectures. Ideally, you must encode all knowledge about the source programming language in the front end, you must handle all machine architecture features in the back end, and you must design your IRs in such a way that all language and machine features are captured properly."
I guess, this is something interesting to think about. How good it will be, if all major programming languages translate to the same intermediate representation.
Particularly I like the following idea:
"Suppose that you want to build compilers for n programming languages (eg, FORTRAN, C, C++, Java, BASIC, etc) and you want these compilers to run on m different architectures (eg, MIPS, SPARC, Intel, alpha, etc). If you do that naively, you need to write n*m compilers, one for each language-architecture combination.
The holly grail of portability in compilers is to do the same thing by writing n + m programs only. How? You use a universal Intermediate Representation (IR) and you make the compiler a two-phase compiler. An IR is typically a tree-like data structure that captures the basic features of most computer architectures. The first phase of this compilation scheme, called the front-end, maps the source code into IR, and the second phase, called the back-end, maps IR into machine code. That way, for each programming language you want to compile, you write one front-end only, and for each computer architecture, you write one back-end. So, totally you have n + m components."
Though the above idea of compiler construction is quite ideal, the author cautions with these statements:
"But the above ideal separation of compilation into two phases does not work very well for real programming languages and architectures. Ideally, you must encode all knowledge about the source programming language in the front end, you must handle all machine architecture features in the back end, and you must design your IRs in such a way that all language and machine features are captured properly."
I guess, this is something interesting to think about. How good it will be, if all major programming languages translate to the same intermediate representation.
Subscribe to:
Posts (Atom)