EE Student, Edit, Proposal Masters, Help (concepts of functional programming, symbolic programming and MATLAB)

EE Student, Edit, Proposal Masters, Help (concepts of functional programming, symbolic programming and MATLAB)

Post by JohnCreigh » Tue, 08 Mar 2005 07:19:17


I am an EE student and in part of my thesis I use MAPLE to
symbolically derive the RIDF for a Kalman filter. This worked but as
part of my proposal I discuss symbolic math packages in the context of
functional programming. Since, I am not widely read in the area I
would appreciate it if someone could look over what I read to make
sure everything I say is at least somewhat true. I am currently
reading more references to strengthen this aspect of my proposal. All
help is appreciated.

1.1.3 A few comments on Symbolic and Functional Programming
Symbolic programming languages fall under two categories, functional
(e.g. lisp, Maple) and logical (e.g. PROLOG). In functional
programming languages each program is a function similar to a
mathematical function. A program is made up of a composition of
functions [9]. The arguments to the functions can include the data
types, lists, expressions, primitives and variables. All data types
are built up of elemental units called primitives. In Maple an
algebraic variables contains a pointer. The pointer will point to null
until a value is substituted for the variable. At that point the
variable points to the value subsisted, which could be another
variable, an entire expression or a primitive. If the value
substituted is a primitive, then a numeric value can be obtained by
evaluating the variable. A pointer abstracts the manipulation of data
in a manner similar to the way variables in mathematics abstract the
manipulation of numbers. That is the rules of algebra can be used to
manipulate the variables without having compete knowledge of the
underlying structure.

Expressions describe how data is evaluated mathematically in terms of
data (e.g. variables) and functions (e.g plus). Expressions can be
represented with strings but are usually represented as a list. The
MATAB equivalent of a list is a one dimensional cell array. In an
expression, the first element of the list is the function or
operation. The subsequent elements are the arguments. Arguments can be
any data structure including expressions. When the arguments of the
functions in an expression are expressions it becomes natural to
represent the expression as a tree. This representation is known as
the operation tree. Unlike the flow of procedural programming
languages, in functional programming language the outer function is
evaluated first and the inner function is only evaluated if called by
the outer function. This is referred to as lazy evaluation. Functional
programming languages are well suited to mathematic symbolic packages
such as Maple and Mathematica. The symbolic package for MATLAB
performs symbolic operations by storing symbolic expressions as
objects. MATLAB manipulating expressions by: passing the expression to
the Maple kernel and then storing the result as a symbolic object [7].

[7] The Help Files for MATLAB 6.0.0.88 (R12)
[9] John Hughes, Why Functional Programming Matters, John Hughes,
Institutionen fr Datavetenskap, Chalmers Tekniska Hgskola, 41296
Gteborg, SWEDEN. XXXX@XXXXX.COM ,
http://www.yqcomputer.com/ ~rjmh/Papers/whyfp.html aug 3.200
[37] Roger Kraft, Programming in Maple, Department of Mathematics,
Computer Science, and Statistics Purdue University Calmuet,
http://www.yqcomputer.com/



Also note I am currently reading
http://www.yqcomputer.com/
 
 
 

EE Student, Edit, Proposal Masters, Help (concepts of functional programming, symbolic programming and MATLAB)

Post by israe » Tue, 08 Mar 2005 10:39:52

n article < XXXX@XXXXX.COM >,
John Creighton < XXXX@XXXXX.COM > wrote:


Nearly everything has pointers. The low-level internal representation
of data is not ordinarily of interest to the user.


You don't substitute a value for the variable, you assign a value to the
variable.


I don't know what you mean by a "primitive". That word is not
part of the usual description of Maple. An object of type "numeric"
is an integer, a fraction or a float.


I don't know what you're getting at here.


No, expressions are not lists. A list is a particular type of expression.


Maple does not use lazy evaluation. When an expression is evaluated,
it is ordinarily evaluated from the inside out: by default, a function
evaluates its arguments first. There are some exceptions.

Robert Israel XXXX@XXXXX.COM
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

 
 
 

EE Student, Edit, Proposal Masters, Help (concepts of functional programming, symbolic programming and MATLAB)

Post by JohnCreigh » Wed, 09 Mar 2005 14:21:56

n article < XXXX@XXXXX.COM >,
John Creighton < XXXX@XXXXX.COM > wrote:
of

"Nearly everything has pointers. The low-level internal
representation
of data is not ordinarily of interest to the user."

Perhaps from an abstract mathematical perspective the low level
interpretation is not important except when the low level behavior has
a direct consequence on the abstract high level behavior. In the case
of MAPLE the pointers are not completely encapsulated. Consider the
example given in

Rofer Kraft, Programming In Maple
http://adept.maplesoft.com/powertools/programming/html/2.01and2.02.html
"Now make x a name for y , y a name for z , and give z a numeric
value, in that order.
x:=y
y:=z
z:=3
What does x evaluate to now?
3
Change the value of z .
X:=5
Check the value of x .

5
In this example, x points to y , y points to z , and at first z
pointed to 3, so x (and y ) evaluated to 3. Then z was pointed at
5, so x (and y ) evaluated to 5. This is full evaluation. Maple keeps
following the trail of assignments until it gets to a "dead end",
either a numeric value or an unassigned name. "



"You don't substitute a value for the variable, you assign a value to
the
variable."

Okay, I see my mistake here. Although you can substitute a value for a
variable in an expression usingm "subs" or "algsubs" the pointer
stored in the variable for which an expression or variable is being
substituted will no longer have anything to do with the resulting
expression. In contrast if you assign a variable a value which is in
the expression then the value the variable points to is linked to the
expression though the variable.




"I don't know what you mean by a "primitive". That word is not
part of the usual description of Maple. An object of type "numeric"
is an integer, a fraction or a float."

Come to think of it I agree. My statement is not quite right. In MAPLE
a numeric variable can contain an indeterminate number of bytes
resulting in numbers which use more bytes then a native machine type.
Thus in Maple a numeric variable is not a primitive data type.



"I don't know what you're getting at here."
I'll rethink this. Not to sound to obvious but the elements
manipulated are often a mapping to or an obstruction of the actual
object which are of primary concern in the computation. Some times
these mappings are given such names as homomorphism and isomorphism.


"No, expressions are not lists. A list is a particular type of
expression."

Do you have a reference for this? I wonder if the definition of a list
is agreed upon in the context of computer science. In MATLAB a list
separates function input arguments when calling a function and
function output arguments when the function returns its values. A list
has the property that each element is of indeterminate size. A cell
array in MATLAB is also a data structure which maps an n tuplet of
integers to elements of indeterminate size. The natural way to
represent such a data structure is with an array of pointers and when
the array is one dimensional it has the same properties of a list.
Perhaps it would be best to see how list is defined in the language
lisp given lisp was the second programming language and stands for
list processing.

By the very
 
 
 

EE Student, Edit, Proposal Masters, Help (concepts of functional programming, symbolic programming and MATLAB)

Post by Nasser Abb » Wed, 09 Mar 2005 16:48:39


...

But isn't this simply how the semantics of an assignment
is supposed to be?

You are asked for x to have the value assigned to y.
Then for y to have the value assigned to z.
Then for z to have the value 3.

This means that the value of x will have, by implication,
the value of 3.

x have the value of 3 not becuase internally pointers are used
as you imply, but it happened as a result of the semantics of
the chain of the assignment operations.

I think this is what the reply you are replying to is saying.
 
 
 

EE Student, Edit, Proposal Masters, Help (concepts of functional programming, symbolic programming and MATLAB)

Post by israe » Thu, 10 Mar 2005 07:27:56

n article < XXXX@XXXXX.COM >,
John Creighton < XXXX@XXXXX.COM > wrote:



Yes, but this should be thought of as a chain of assigned values rather
than a chain of pointers. A rather subtle difference, to be sure...




I think we have a terminology problem here. Maple has a specific data
type called a list, which is not the same as what computer science calls
a list. In Maple, a list (at the user level) is an ordered sequence of
expressions enclosed in square brackets.


Basically every Maple object is an expression, unless it's a sequence of
expressions.


You might start with the Maple 9.5 "Introductory Programming Guide".

Robert Israel XXXX@XXXXX.COM
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
 
 
 

EE Student, Edit, Proposal Masters, Help (concepts of functional programming, symbolic programming and MATLAB)

Post by William Lo » Thu, 10 Mar 2005 08:14:20

In article <rNcXd.13110$ XXXX@XXXXX.COM >, Nasser



Not in a language with lexical scope -- x would receive the value
*currently* assigned to y, y the value *currently* assigned to z, and
*then* z the value 3. Only if x, y, and z are pointers, or if dynamic
scope is in effect, would a statement like "y := z" bind y to whatever
future values z might take on.

cheers,
William
 
 
 

EE Student, Edit, Proposal Masters, Help (concepts of functional programming, symbolic programming and MATLAB)

Post by Richard Fa » Thu, 10 Mar 2005 10:20:51


...

Lisp presumably has precedence in computer science, in using the
word "list". In that context John Creighton is right.

In lisp there are atoms and lists. (I am somewhat simplifying this...)
A symbolic expression or s-exp is either nil, an atom, or
a pair (a CONS cell), e.g. (a . b)
The two components, here a, and b, can be any s-exp.

Lists are composed of cons cells. (a . nil) is also written (a)
(a . (b . (c . nil))) is written (a b c).

(a . ((r . nil) . (c . nil))) is written (a (r) c).

etc.

Maple's notion of list would be encoded in lisp something like this:

(<maple-special-number-for-list-thing> a b c d e )

Lisp's notion of list allows anything to be that first element.

There's lots of info on-line about lisp. There is relatively
little about Maple's debt to lisp, at least that I'm aware of.
 
 
 

EE Student, Edit, Proposal Masters, Help (concepts of functional programming, symbolic programming and MATLAB)

Post by Richard Fa » Thu, 10 Mar 2005 10:26:12


The question was about Maple, which doesn't work this way, and it
doesn't really have to do with lexical scope. It has to do with
symbolic values and evaluation.

For example,

a:=a+1

is illegal in Maple, because of its rules of evaluation.
 
 
 

EE Student, Edit, Proposal Masters, Help (concepts of functional programming, symbolic programming and MATLAB)

Post by israe » Thu, 10 Mar 2005 10:34:23

In article < XXXX@XXXXX.COM >,







Yes, if y and z are unassigned at the start of this sequence.

But:

y:= foo;
x:= y;
y:= z;
z:= 3;

will leave x evaluating to foo.

On the other hand:

y:= (t -> foo);
x:= y;
y:= z;
z:= 3;

again leaves x evaluating to 3.



In Maple, x := y assigns to x the value currently obtained by
evaluating y. If y is unassigned, or subject to last-name evaluation
(i.e. assigned a procedure, module or table) that value is y itself.
Then a future assignment to y will affect how x is evaluated.

Things are further complicated by the fact that local variables of
procedures are subject to only one level of evaluation. So for example,
guess what this procedure returns?

f:= proc()
local x,y,z;
y:= z;
z:= 1;
x:= y;
y:= 2;
z:= 3;
return x
end proc:

f();

Answer:
It returns z (which on further evaluation yields 3).

Robert Israel XXXX@XXXXX.COM
Department of Mathematics http://www.yqcomputer.com/ ~israel
University of British Columbia Vancouver, BC, Canada
 
 
 

EE Student, Edit, Proposal Masters, Help (concepts of functional programming, symbolic programming and MATLAB)

Post by William Lo » Thu, 10 Mar 2005 13:50:46


Fair enough. I was worried to see what appeared to be a blanket statement
about the "semantics of assignment", which is of course dependent upon the
language in question. I should have read back a bit further to see that it
was merely a statement about the semantics of assignment in Maple.

cheers,
William
 
 
 

EE Student, Edit, Proposal Masters, Help (concepts of functional programming, symbolic programming and MATLAB)

Post by JohnCreigh » Thu, 10 Mar 2005 13:51:09

XXXX@XXXXX.COM (Robert Israel) wrote in message news:<d0l8tc$6sh$ XXXX@XXXXX.COM >...



Okay, I'll take a look. I have been listening to the feedback and
trying to take others suggestions into account as best as possible.
Unfortunately, I might end up cutting it out of my proposal. I have
expanded the history of the Kalman filter section and have now
exceeded the 8 page limit by a page. I might be able to include it as
an appendix. I will definitely be able to include it in the body of my
final thesis. Currently my proposal has the following structure:

1 INTRODUCTION 3
2 LITERATURE REVIEW 4
2.1 THE HISTORY OF THE KALMAN FILTER 4
2.2 THE HISTORY OF DESCRIBING FUNCTIONS 4
2.3 A FEW COMMENTS ON SYMBOLIC AND FUNCTIONAL PROGRAMMING 5
3 OBJECTIVE 6
4 SIGNIFICANCE 7
5 THE KALMAN FILTERS IN THE CONTEXT OF ESTIMATION THEORY 7
5 PRELIMINARY RESULTS 9
6 CONCLUSIONS 10
REFERENCES 10

Bellow is the update to my update to section 2.3:

1.1.3 A few comments on Symbolic and Functional Programming

Symbolic programming languages fall under two categories, functional
(e.g. lisp, Maple) and logical (e.g. PROLOG). In functional
programming languages each program is a function similar to a
mathematical function. A program is made up of a composition of
functions [9]. The arguments to the functions can include the data
types, lists, expressions, primitives and variables. As in all
languages data types are built up of elemental units called
primitives. However, in some third generation languages (e.g. Maple)
the primitives are not part of the language. This is analogues to
assembler and machine code falling outside the scope of a second
generation language. Maple uses a numeric data type which can be of
arbitrary precision. The software must decide how to reduce the higher
level computation down to machine level operations on primitive data.

Unlike pure functional languages such as Haskell, Maple uses
assignment instead of monads. In Maple if a variable x is assigned a
variable y then x points to y. If y is then assigned the value z then
x points to y which points to z. Programmatically the value at the end
of the chain of assignment can be returned by evaluating a variable in
the chain. The assignment chain is not altered by evaluation. It is
only altered when one of the variables in the chain is reassigned. So
for instance the chain could be altered by assigning the first
variable in the chain the value at the end of the chain as follows:

x:=eval(x)

Variables can represent many kinds of data structures. A data
structure that can be evaluated is known as an expression. An
expression could be formed from a single variable, a single function
at a given domain or though the composition of several expressions.

Another data structure is a list. Linguistically a list is an ordered
collection of items. In computer science a list usually refers to a
data structure that is easy to add and remove stuff from but must be
accessed in a sequential fashion. In a purely functional language a
list can be defined by the composition of functions in a recursive
manner. For instance the list function could take two arguments where
one argument is the first element of the list and the next argument is
the rest of the list. Since, a list can be represented as a
composition of functions; functions can be evaluated and; expressions
are something that can be evaluated then: a list could be thought of
 
 
 

EE Student, Edit, Proposal Masters, Help (concepts of functional programming, symbolic programming and MATLAB)

Post by Jerzy Karc » Thu, 10 Mar 2005 16:05:16


Cum grano salis.
This doesn't work when a is unassigned.
a:=7;
a:=a+1;

works perfectly well. Then, a:='a'+1; fails again.

Maple as a *programming language* is an abomination because of its
scoping rules which aren't. It has a notion of "evaluation to name"
which is confusing. There was a project in France to introduce
programming in high schools using Maple.
I have seen a few youngsters which passed by such a training. They
lost completely the distiction between a 'symbol' and a 'variable'.

Making, say, x an array permits its indexing. But you type just
x, and you don't get this array, but the symbol x, since it has
been "evaluated to name". It takes a lot of time to master those
conventions... In brief, I like Maple, I use it, but as a programming
language this is a real calamity...

Jerzy Karczmarczuk
 
 
 

EE Student, Edit, Proposal Masters, Help (concepts of functional programming, symbolic programming and MATLAB)

Post by G. A. Edga » Thu, 10 Mar 2005 22:15:15

In article < XXXX@XXXXX.COM >, William





OK, here it is:

17
99

--
G. A. Edgar http://www.yqcomputer.com/ ~edgar/
 
 
 

EE Student, Edit, Proposal Masters, Help (concepts of functional programming, symbolic programming and MATLAB)

Post by Joachim Du » Thu, 10 Mar 2005 22:29:37

ohn Creighton wrote:

It is, though in some contexts it's used in a more specific way than in
others.

In general, a list is a container of elements of some common type that
can be iterated linearly and that has an unspecified number of elements.
(Arrays are the same but have a specific number of elements.) Also,
accessing the N'th element of a list is an O(N) operation.

> In MATLAB a list

This is a specialty of Matlab lists. Or, rather, of dynamically-typed
languages.

> A cell

Agreed, but that's not specific to lists but a property of data
structures with elements of varying size. I.e. this is done not only in
lists and arrays but in records as well.


Lisp uses a definition that explicitly relies on implementation details,
so it's a bit misleading.

And, no, Lisp isn't the last word on what's a list and what isn't, even
if it's the oldest modern language.


You have been misled. A list is simply a data structure.

Interpreters often use lists to store expressions that are awaiting
evaluation, but that's just an implementation detail. In practice, it's
usually an "association list", a mapping from names to expressions,
which is often implemented as a list in Lisp but as some tree structure
in any other language (Lisp as defined in the '50ies isn't particularly
efficient at working with datastructures other than lists, mostly
because everything is forced into double-pointer list cells even if it
doesn't make sense. Modern Lisp dialects tend to have data structures
beyond lists and can do reasonably well, though they still tend to call
the thing an "association list" even if it isn't a list. It's a
traditional name *g*)


That's what lazy evaluation does, at least in theory, but making this
even reasonably efficient requires a good deal of coding.

Most tree evaluation algorithms work recursively, along the lines of
eval (tree-node) is
case tree-node.operation of
add:
eval (tree-node.child [1]) + eval (tree-node.child [2])
negate:
- eval (tree-node.child [1])
if-then-else:
if eval (tree-node.child [1]) then
eval (tree-node.child [2])
else
eval (tree-node.child [3])
end
... other operations go here
end
end

This is easy to code and reasonably efficient, and that's why most
language use strict evaluation.

Note that only one of the "then" and "else" part of an if-then-else
expression is evaluated. If both parts were evaluated, it would be
impossible to write a recursive function that terminates.

> Perhaps expressions are by default

I don't know how Matlab does this, but usually expressions are evaluated
whenever they are used. It's the responsibility of the programmer/user
to assign results to intermediate variables to prevent multiple
evaluation of the same expression.

Many compilers do "common subexpression elimination", but this
optimization is usually limited to the scope of a single function. And
it's not motivated to make programmer-written code faster (programmers
tend to factor out common expressions anyway), it's to make
compiler-generated code faster, particularly code that accesses arrays.

> I am interested to here more on this do you

It's usually a list, because during parsing a function's parameter list,
the parser doesn't know how many additional subexpressions there will
b
 
 
 

EE Student, Edit, Proposal Masters, Help (concepts of functional programming, symbolic programming and MATLAB)

Post by Martin Eis » Fri, 11 Mar 2005 00:38:06


Isn't it the case that that's just what happens in Maple, and the
twist is in the evaluator rather than the assignment? A fresh Maple
variable holds its own name, so that gets assigned. Evaluating one
level shows that it simply stays put:

y
3
y

You might of course respond that holding a name makes x a pointer of
sorts, but I don't know how useful that is.


--
Quidquid latine dictum sit, altum viditur.