Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Software language comparasons, prime number example

  1. Apr 26, 2010 #1

    rcgldr

    User Avatar
    Homework Helper

    This needed a separate thread.

    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.

    aplprime.jpg

    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, 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.

    Something similar could be impemented in C by using
    Code (Text):

    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.

    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?
     
    Last edited: Apr 26, 2010
  2. jcsd
  3. Apr 26, 2010 #2

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
    Last edited: Apr 26, 2010
  4. Apr 26, 2010 #3

    rcgldr

    User Avatar
    Homework Helper

    That wasn't an issue for me.
    Perhaps comparason with 2, but modulo is defined for floating point numbers.

    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.

    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.
     
    Last edited: Apr 26, 2010
  5. Apr 26, 2010 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  6. Apr 26, 2010 #5
    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:

    Code (Text):
    (define (square x) (* x x))
    is actually a shorthand for
    Code (Text):
    (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.

    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.

    BNF is not turing complete though.

    The trick is getting a turing complete declarative system. I wouldn't call BNF a 'programming language'
     
  7. Apr 26, 2010 #6

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    lex and yacc are programming languages, however.
     
  8. Apr 26, 2010 #7

    rcgldr

    User Avatar
    Homework Helper

    OK, I wasn't sure on this.
    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.
    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.

    I'm not familiar with this.

    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.
     
  9. Apr 26, 2010 #8

    rcgldr

    User Avatar
    Homework Helper

    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.

    Code (Text):

    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.
     
    Last edited: Apr 26, 2010
  10. Apr 26, 2010 #9
    They're turing complete? What?
     
  11. Apr 26, 2010 #10
    Re: How do I start to learn programming?

    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.
     
  12. Apr 26, 2010 #11

    rcgldr

    User Avatar
    Homework Helper

    Re: How do I start to learn programming?

    Just filler now, was a comment about moving to this thread.
     
    Last edited: Apr 26, 2010
  13. Apr 26, 2010 #12
  14. Apr 26, 2010 #13

    rcgldr

    User Avatar
    Homework Helper

    Re: How do I start to learn programming?

    Ok "to c or not to c" is locked again, continue here please.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook