Software language comparasons, prime number example

[rcgldr]

This needed a separate thread.

prime number example

Here is an APL example where it's all done with no interation using N by N matrices in the intermediate propagation of data. Note, code flow in APL statements is right to left.

The []IO<-0 sets the "index origin" to zero so a list of numbers and indexing starts with 0 instead of 1, adding this to N has no effect, but it allows the classic 1 line approach so popular in APL programs.

It creates a list of N numbers, 2 -> N-1, (Z <- 2 + ι N). Then it creates a N by N matrix of remainders (Z ∘.| Z) for every number in the list divided by every number in the list. (Note in APL the remainder operator is residue(s) = divisor(s) | dividend(s)). It then compares 0 ≠ to that matrix of remainders to generate a matrix of boolean ones and zeros, with ones corresponding to non-zero remainders. It then creates another matrix boolean ones and zeros for every number in the list compared to every number in the list (Z ∘.= Z), which creates a zero matrix with a diagonal of 1's where the numbers are the same, which would correspond to the cases where the remainders from the first matirx would be zero, but only because the numbers were divided by themselves. Then the two boolean matrices are or'ed, resuting in a boolean matrix of ones and zeros where the ones correspond to remainders not equal to zero or numbers equal to themselves. The columns of this matrix are then and'ed vertically to produce a list of ones and zeros that correspond to primes and non-primes in the list of numbers (Z). Then this list of ones and zeroes is used to "reduce" Z so that only prime numbers are copied back into Z, which is the output from the prime function.

In C or Java, functions cannot take functions as argument

In C, pointers to functions can be passed as arguments. I often use pointer to functions to handle end actions from common code sequences, such as interrupt handlers in device drivers.

filter(list(2,n),prime?)

Something similar could be impemented in C by using

void *list(int, int, boolean (* function)(int));
void boolean prime(int);

...
list(2, n, prime);

where the list function calls the prime function as a qualifier and/or modifier for each number it finds. List would be returning a pointer to a list that would have to be freed later though. C++ templates, being code fragments implemented as macros instead of functions, might be able to do this beter.

Next on is 'declarative programming', this is even clearer but at a significant performance cost. In declarative programming we are mainly concerned with what we want to do, and not how to do it. Simply said:

def prime n : 2 or n > 1 and n % m > 0 : prime m
give all prime x : x < n.

This one I don't understand. Where are m, n, and x declared to be integers, where is it implied that x is to be incremented by 1, and where is the list of all the m's being kept? For the "n % m > 0" part, is m a list of numbers or is this an iterative or recursive test?

 

[D H]

This one I don't understand. Where are m, n, and x declared to be integers, where is it implied that x is to be incremented by 1, and where is the list of all the m's being kept? For the "n % m > 0" part, is m a list of numbers or is this an iterative or recursive test?

Not all languages require variables to be declared. They pop into being by using them. This is an *old* capability; it harkens back to the earliest versions of Fortran.

In this case, the variables m, n, and x are used in an integer context (comparison to 2, the use of the mod operator) so they are integers. This is duck typing. "If it looks like a duck and quacks like a duck, it is a duck."

The more interesting aspect of declarative programming is that the programmer does not tell the system how do it (whatever "it" is). You instead give the system hints as to how to construct the solution.

You probably have used a declarative language if you have done any significant programming on a Unix machine. The Unix make facility is essentially a declarative language. You specify production rules and dependencies but not necessarily specific commands or command sequences.

Addendum
Better stated, make is a hybrid of imperative and declarative programming. The command sequences follow the imperative paradigm while the production rules follow the imperative paradigm.

 

[rcgldr]

Not all languages require variables to be declared.

That wasn't an issue for me.

In this case, the variables m, n, and x are used in an integer context (comparison to 2, the use of the mod operator)

Perhaps comparason with 2, but modulo is defined for floating point numbers.

The more interesting aspect of declarative programming is that the programmer does not tell the system how do it (whatever "it" is).

The syntax is a bit confusing in this case. def prime n : 2 or n > 1 and n % m > 0 : prime m. One issue is the precedence is it (2) or (n >1) or could it be (2 or n) > 1? Another issue is that somehow n % m > 0 has an implicit "and" involved where all m that are prime must be tested. The last issue is that : prime m is used to imply all m's that are prime, without specifying m < n as a limit on the test. It appears to be a recursive definition with no limiting clause.

You probably have used a declarative language if you have done any significant programming on a Unix machine. The Unix make

Not unix, but MSDOS based builds using nmake (not sure why they changed the name). It's not quite the same thing. With make or nmake you clearly specify rules needed to create every type of object, then list dependencies between objects. There was an issue in creating a directory tree with nmake, so builds often started off by getting a single batch file from version control that would then do a bunch of "if not exist .\...\...\nul md .\...\..." to create the directory tree, then it switched to nmake (or some version control variation of nmake) to do the rest of the build.

 

[D H]

The syntax is a bit confusing in this case. def prime n : 2 or n > 1 and n % m > 0 : prime m.

You are reading Kajahtava's example a bit too literally. I don't think that Kajahtava was writing real code here. For one thing, his algorithm is quite inefficient. There is no reason to search beyond sqrt(n). For another, that all primes other than 2 are odd offers another speedup.

Regarding make, you could have simply written a script than explicitly compiles every file and then links the object files to create an executable. That is the imperative approach. With make you do not explicitly say how to proceed. You say what the ultimate result is and give rules for how to proceed from one result to another.

Another way to think of it is the difference between forward chaining and backward chaining in an AI system.

Yet another example of declarative programming is a Backus-Naur Form and lex/yacc systems based on a BNF.

 

[Kajahtava]

In C, pointers to functions can be passed as arguments. I often use pointer to functions to handle end actions from common code sequences, such as interrupt handlers in device drivers.

True but I wouldn't use that, as soon as you start to work that way the advantages of C go lost.

Also, the main deal with higher order languages is that functions are objects in their own right, just as integers. For instance, in Scheme:

(define (square x) (* x x))

is actually a shorthand for

(define square (lambda (x) (* x x))

, we create a function literal (if has to from dynamic parameters) and store it in a symbol. (Note that symbols are also datatypes themselves, a variable can hold a variable.)

Though, passing function pointers of course does have a great application in sorting algorithms.

Oh, P.S: I forgot, your list function on the inside probably does alter state and mutates data and changes variables. Though that's not really an issue for referential transparency.

Not all languages require variables to be declared. They pop into being by using them. This is an *old* capability; it harkens back to the earliest versions of Fortran.

In this case, the variables m, n, and x are used in an integer context (comparison to 2, the use of the mod operator) so they are integers. This is duck typing. "If it looks like a duck and quacks like a duck, it is a duck.

Nope, this is static typing. Duck typing is dynamic.

Languages of the ML-family use static typing without typing to be explicit, there's a difference between explicit typing and static typing. The use the Howard-Curry correspondence and the Milner inference to still have static types without explicit typing. (As in, type errors are reported at compile time)

The type system would infer in this case that n may be a float, but x has to be an integer larger than 1.

Yet another example of declarative programming is a Backus-Naur Form and lex/yacc systems based on a BNF.

BNF is not turing complete though.

The trick is getting a turing complete declarative system. I wouldn't call BNF a 'programming language'

 

[D H]

lex and yacc are programming languages, however.

 

[rcgldr]

You are reading Kajahtava's example a bit too literally.

OK, I wasn't sure on this.

For one thing, his algorithm is quite inefficient. There is no reason to search beyond sqrt(n). For another, that all primes other than 2 are odd offers another speedup.

It can't be as bad as my APL example where a N by N matrix of all possible combinations of numbers are modulo'ed including when the divisors are greater than the dividends.

Regarding make, you could have simply written a script than explicitly compiles every file and then links the object files to create an executable. That is the imperative approach. With make you do not explicitly say how to proceed. You say what the ultimate result is and give rules for how to proceed from one result to another.

For nmake you give it a set of explicit inference rules, .asm.obj: ml /c $<, .c.obj: cl /c $<, ... which desribe how to process a target file and produce a dependent file. Then you define a list of dependencies between dependents and targets. It can follow a complex and nested set of dependencies, even recurse, and a lot of the inference rules are pre-defined, but it ends up straight forward. I don't recall if make for unix was much different.

Another way to think of it is the difference between forward chaining and backward chaining in an AI system.

I'm not familiar with this.

Yet another example of declarative programming is a Backus-Naur Form and lex/yacc systems based on a BNF.

Perhaps this is a better example, but BNF is similar to a define or macro with nesting capability. A simple example would be an expression evaluator that allows parenthesis, where each element of an "expression" can be a "value" or yet another "expression". As you scan the tree, eventually you get to all the leafs (values).

Perhaps the point I'm getting at here is that eventually the computer is going to execute some instructions and generate a result based on the set of rules given to the high level language. By the time it gets to machine language your down to a fairly simple set of rules.

 

[rcgldr]

I often use pointer to functions to handle end actions from common code sequences, such as interrupt handlers in device drivers.

True but I wouldn't use that, as soon as you start to work that way the advantages of C go lost.

The alternative is some massive switch case statement at some common message or interrupt handler which gets messy, as opposed to this sequence where it very easy to insert another step in the series of interrupt driven events, and where various series of interrupt driven sequences can reside in different source modules without requiring any cross editting of those modules.

typedef void (*PFUN)(void);

static PFUN pfInterrupt;
static PFUN pfEndSequence;

static void StartSequence(void)
{
    pfEndSequence = EndSequence;
    pfInterrupt   = Interrupt1;
    InitiateStep1();
    // return to main thread to wait for task level messages
}

static void Interrupt1(void)
{
    pfInterrupt = Interrupt2;
    InitiateStep2();
}

static void Interrupt2(void)
{
    pfInterrupt = UnexpectedInterrupt;
    pfEndSequence();
}

static void EndSequence(void)
{
    // sequence completed, send msg to wake up task
}

static void UnexpectedInterrupt(void)
{
    // send UnexpectedInterrupt msg to diagnostic task
}

I also recall a menu oriented application where structures for the menus included a set of pointer to functions to handle the window message events. As the user traversed the menu tree, after performing any associated actions, the main change was the pointer to the current menu structure was updated to the next menu, with it's own set of message handling pointer to functions. The code always ended up as the same message dequeue point, while the pointer to menu structure followed the menu tree. In some cases the pointer to functions within the menu structures would be changed, representing a state change in a node of the menu tree.

 

[Kajahtava]

lex and yacc are programming languages, however.

They're turing complete? What?

 

[PaulS1950]

From WIKI:

Programming languages that support function pointers as function parameters can emulate higher-order functions. Such languages include the C and C++ family. An example is the following C code which computes an approximation of the integral of an arbitrary function:

// Compute the integral of f() within the interval [a,b]
double integral(double (*f)(double x), double a, double b)
{
double sum;
int i;

// Sum 100 values of f(x) for x in [a,b]
sum = 0.0;
for (i = 0; i <= 100; i++)
sum += (*f)(i/100.0 * (b - a) + a);
return sum;
}
Another example is the function qsort from C standard library.

Normally the programmer has the freedom to write any function needed in C/C++. In that way it can be taylored to his/her needs.

 

[rcgldr]

Just filler now, was a comment about moving to this thread.

 

[Kajahtava]

I attempted to direct the language capabilites discussion part of this thread into another thread:

https://www.physicsforums.com/showthread.php?t=398535

This IS that thread.

 

[rcgldr]

This IS that thread.

Ok "to c or not to c" is locked again, continue here please.