Implement map in C.

Go To Last Post
16 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I want to implement a generic mapping function in C, although it doesn't have to be all that generic to start with.

 

Like Haskells simple definition of map;

map _ [] = []

map f (x:xs) = f x : map f xs

 

where "map double [1, 2, 3, 4] = [2, 4, 6, 8]" or "map (\x -> x / 2) [10, 20, 30] = [5, 10, 15]" etc..

 

I've so far done a stupid proof of concept thing for my own amusement similar to;

add f x y = f x + f y

 

which looks like this in C:

int square(int n) {
	return n*n;
}

int add(int f(int), int x, int y) {
	return f(x) + f(y);
}

int main() {
        int n = add(*square, 12, 3); // just square without the asterisk also works (as does putting & before it)
        printf("%d\n", n);
}

Which prints the true value of 153.

 

Now, C and lists.. Never settled with me. I want to apply f to the head of the list and recursively call map with f and the tail of the list, till it's empty. How? How do I check that the list is empty, and how do I "cut off" an element from an existing list? Plus I need to concatenate the result from one iteration with the list that is going to constitute my result. Which way is the cleanest?

sol i sinne - brun inne

Last Edited: Wed. Apr 11, 2018 - 06:24 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0
        int n = add(*square, 12, 3);

You SURE about that '*' ?!?!

 

In C that * operator is a pointer dereference. So square() returns some int then you appear to be using that as an ADDRESS?!?!?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I had to try that. Well it seems to work! I have no idea what's going on here.  This main seems to work as well
 

int main() {
        int n = add(*******square, 12, 3);
        printf("%d\n", n);
}

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I don't think I've ever used a function pointer passed as an argument.  At least not on AVR8.

 

CodeVision did not swallow the syntax as shown.  An excerpt from the Help:

 

Pointers to functions always access the FLASH memory area. There is no need to use the flash or __flash memory attributes for these types of pointers.

Example:

 

/* Declare a function */

int sum(int a, int b) {

return a+b;

}

 

/* Declare and initialize a global pointer to the function sum */

int (*sum_ptr) (int a, int b)=sum;

 

void main(void) {

int i;

 

/* Call the function sum using the pointer */

i=(*sum_ptr) (1,2);

}

  

On to try different variations of syntax...CV blew up on my first try.  lol

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Functional programming guys :D

Function (or method rather) pointers work well on AVRs, I can't say I've over used them but the multithread kernel in my tutorial uses them with success.

 

So, how 'bout those arrays? (sorry for the late response)

sol i sinne - brun inne

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Making a map function work in C isn't playing to any of C strengths and isn't going to bring any of functional programing benifits. Making list and passing them is going to require an additional data structure and passing along manual this information for each call. It's putting a square peg in a round hole. 

 

Arrays in C are intentonally simple, just access to memory. Being simple is a strength when interfacing hardware, as it can exactly describe in software the same as expected in hardware (writing to hardware's buffer from software. Updating the 16 counters require an exact set of instructions that match what C does). As for adding to cutting elements from a C array, it just doesn't work. An array in C is exactly just a place in memory. Adding another element is asking for hardware to change and another number of places put after. Keeping track of memory or arrays or list or anything in C, it's using the hardware's numbers. Item "1" is an item at the first memory location "1" in ram at location "1", accessable when the wires on the chip read "1". Putting something after "1" while something is already in "2" doesn't work. 

 

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I'm still mystified. Just "square" or possibly "&square" which are both a function pointer to the code in the square() function would make sense. But *?!? * is a pointer dereference. What on earth do you get if you dereference a function pointer? Surely it'd be the first opcode of the function or something?

 

However I just tried this:

$ cat test.c
#include <stdio.h>

int square(int n) {
	return n*n;
}

int add(int f(int), int x, int y) {
	return f(x) + f(y);
}

int main() {
        int n = add(*square, 12, 3);
        printf("%d\n", n);
	printf("square=%08X, &square=%08X, *square=%08X\n", square, &square, *square);
}
$ ./test
153
square=00400564, &square=00400564, *square=00400564

Interesting (inexplicable?) result? So you get the function address whether you use "square", "&square" or "*square". Go figure!

 

Certainly for a seasoned C programmer "square" or "&square" feels a lot more comfortable than "*square".

 

If you forget function pointers and use something simpler:

$ cat test.c
#include <stdio.h>

int somevar = 12345;

int main() {
	printf("somevar=%08X, &somevar=%08X, *somevar=%08X\n", somevar, &somevar, *somevar);
}
$ gcc -Os test.c -o test
test.c: In function ‘main’:
test.c:6:76: error: invalid type argument of unary ‘*’ (have ‘int’)

You get told off by the C compiler just as you would expect. Here C is telling us that to use * the thing to the right must be the address of something.

Last Edited: Thu. Feb 26, 2015 - 10:30 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

That seems to work too yeah. Well, C's type checking is as strict as a pair of washed out lounge pants.. And pointers are to me a bit mystic, I can't understand why they didn't abstract away from them but, hey it's C! It works so why complain? :D

sol i sinne - brun inne

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Eh? Pointers are arguably C's most powerful tool. It's probably why the majority of the world have chosen to use C in preference to most other languages on offer.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Very well, but it's not safe in the least.

sol i sinne - brun inne

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

That is EXACTLY why programmers choose it! You can do some seriously dirty stuff using pointers. It lets high level programmers think like Asm programmers (because that's the way most C programmers started out). It's often said C is just a high level macro assembler language.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Tickstart wrote:
C's type checking is as strict as a pair of washed out lounge pants.

and never claimed to be anything else.

 

clawson wrote:
Pointers are arguably C's most powerful tool

I don't think there's much argument about that!

 

As with most Power Tools, also the most dangerous when mishandled...

 

Tickstart wrote:
I can't understand why they didn't abstract away from them

To what, exactly?

Top Tips:

  1. How to properly post source code - see: https://www.avrfreaks.net/comment... - also how to properly include images/pictures
  2. "Garbage" characters on a serial terminal are (almost?) invariably due to wrong baud rate - see: https://learn.sparkfun.com/tutorials/serial-communication
  3. Wrong baud rate is usually due to not running at the speed you thought; check by blinking a LED to see if you get the speed you expected
  4. Difference between a crystal, and a crystal oscillatorhttps://www.avrfreaks.net/comment...
  5. When your question is resolved, mark the solution: https://www.avrfreaks.net/comment...
  6. Beginner's "Getting Started" tips: https://www.avrfreaks.net/comment...
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

To what, exactly?

Arrays ;-)

 

(if you were forced to use arrays all the time and no pointer access you couldn't adjust the base address and wreak havoc (though you could still write off the end of the array for just a little bit of havoc)).

Last Edited: Thu. Feb 26, 2015 - 02:23 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:

Pointers are arguably C's most powerful tool

 

Now y'all are making me think.  I did some semi-formal language comparison in college but as that was 40 years ago...  A bit of thinking and reviewing the Wikipedia list of programming languages http://en.wikipedia.org/wiki/Lis... and...

 

-- C is classed as a procedural language.  Other than some very brief excursions, that's all I've dealt with.

-- The mentioned Haskell is classed as a pure functional language.

 

IMO trying to compare languages in different classes is fruitless.  Or is such mixing of apples and oranges fruit salad?

 

-- By definition of a procedural language, we have some level of subprogram (i.e. C functions).

-- Given that C is a procedural language, we have expressions, and they make up statements.  So, one can do the equivalent of A + B = C.

-- To some degree all the procedural languages will have more or less the same iteration constructs.

 

So, what does C give us in addition to the basics?

 

IMO it comes down to what is expressed in the rationale: 

Keep the spirit of C. The Committee kept as a major goal to preserve the traditional spirit of C.  There are many facets of the spirit of C, but the essence is a community sentiment of the underlying principles upon which the C language is based.  Some of the facets of the spirit of C can be summarized in phrases like

  • Trust the programmer.
  • Don't prevent the programmer from doing what needs to be done.
  • Keep the language small and simple.
  • Provide only one way to do an operation.
  • Make it fast, even if it is not guaranteed to be portable.

 

So by the very definition in the rationale with excerpts such as the above, purists can point their noses skyward and sniff.  So be it.

 

I think my thoughts are an extension of what I bolded above:  Let the programmer give the compiler a hint, to allow it to produce [pick a word]  fast/small/efficient/optimal code sequences.

 

What then, in C, is beyond the core of any procedural language?  I think the concept of casting is quite important and useful.  Pointers were mentioned, along with the compare/contrast with arrays.  IMO again, it gives the compiler a chance to use these valuable index registers that are in most processor architectures.

 

IMO the extent of standard library is immaterial.  Not part of the "language".  And can always be "re-implemented" using the language or other facilities.  [NB  All in all I have very light use of C libraries in my AVR8 apps.]

 

Take a look at e.g. the table of contents in the C standard.  It is really all syntax and the behaviour of applying that syntax.  The only "core" IMO is

 

 

6.8 Statements and blocks . . . . . . . . . . . . . . . . . . . . 131

6.8.1 Labeled statements . . . . . . . . . . . . . . . . . . 131

6.8.2 Compound statement . . . . . . . . . . . . . . . . . 132

6.8.3 Expression and null statements . . . . . . . . . . . . . 132

6.8.4 Selection statements . . . . . . . . . . . . . . . . . 133

6.8.5 Iteration statements . . . . . . . . . . . . . . . . . . 135

6.8.6 Jump statements . . . . . . . . . . . . . . . . . . . 136
 

...which are all pretty much in every procedural language.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

A map data structure works as an adjustable function.

The domain and range are adjustable at run time.

This is generally done with a hash table or a tree.

Note that a function is a *set* of ordered pairs.

A map does not necessarily allow efficiently going through its domain in a specific order.

Iluvatar is the better part of Valar.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Interesting (inexplicable?) result?

Neither '*' nor '&' really make any sense with function pointers, so I believe that gcc simply ignores them. I just tried it in Visual Studio (though admittedly in C++, not straight C). There 'func' and '&func' produced identical results, but '*func' produced a compile error.

Regards,
Steve A.

The Board helps those that help themselves.