Computer Science Canada

Test your skills (2006)

Author:  wtd [ Mon Jan 02, 2006 3:48 am ]
Post subject:  Test your skills (2006)

Io TYS. Smile

code:
Io> foo(a, 42, a print)
42
==> 42
Io> foo(i, "foo", i with("!") print)
foo!
==> foo!


Write a method which makes the above possible.

code:
Io> foo := method(
       /* your code here */
    )

Author:  wtd [ Sun Jan 15, 2006 5:09 pm ]
Post subject: 

Write a function which appends lists.

code:
(defun list-append (...) ...)


A few samples:

code:
(list-append '(1 2 3) '(4 5 6))    ; (1 2 3 4 5 6)
(list-append '(1 2) '(3 4) '(5 6)) ; (1 2 3 4 5 6)


You may use the following functions or macros.


  • flet
  • cons
  • car
  • cdr
  • if
  • defun (but only the one, in the code I already demonstrated)
  • reduce


You may very explicitly not use the loop macro.

You may not have any code outside of the list-append function.

Author:  wtd [ Fri Feb 03, 2006 2:27 am ]
Post subject: 

C++ gurus: a TYS just for you.

Explain why this code will not compile.

code:
#include <list>
#include <vector>

int main()
{
   std::vector<std::list<int>> foo;

   return 0;
}

Author:  Martin [ Tue Feb 07, 2006 3:18 am ]
Post subject: 

C/C++ (or Java). Complete this function to determine if n is a power of 2.

c:

int isPowerOfTwo (int n)
{
    return <your code!>;
}

c++:
bool isPowerOfTwo (int n)
{
    return <your code!>;
}

Java:
boolean isPowerOfTwo (int n)
{
    return <your code!>;
}

Author:  Andy [ Tue Feb 07, 2006 9:37 am ]
Post subject: 

c++:

bool isPowerOfTwo (int n)
{
    return n % 2 ? n == 1 : isPowerOfTwo(n/2);
}


does that count as cheating? lol

Author:  Martin [ Tue Feb 07, 2006 7:23 pm ]
Post subject: 

There's a much better way.

Think bitwise.

Author:  Andy [ Tue Feb 07, 2006 10:27 pm ]
Post subject: 

haha yea, i was going to do it bitwise, but then i got lazy =P, if i have time, i'll do it at work tomorow

Author:  bugzpodder [ Wed Feb 08, 2006 12:53 pm ]
Post subject: 

c++:
bool isPowerOfTwo (int n)
{
    return n<0?0:(n^(n-1))==-1;
}

Author:  bugzpodder [ Wed Feb 08, 2006 12:56 pm ]
Post subject: 

code:
#include <list>
#include <vector>

int main()
{
   std::vector<std::list<int>> foo;

   return 0;
}


>> is an operator in C++. need a space in between.

Author:  wtd [ Wed Feb 08, 2006 12:58 pm ]
Post subject: 

bugzpodder wrote:
code:
#include <list>
#include <vector>

int main()
{
   std::vector<std::list<int>> foo;

   return 0;
}


>> is an operator in C++. need a space in between.


Yes, that is the solution. But why is it a problem? Smile

Author:  bugzpodder [ Wed Feb 08, 2006 1:07 pm ]
Post subject: 

? its a problem because >> is a predefined operator in C++. But i thought I've already said that.

Author:  wtd [ Wed Feb 08, 2006 1:08 pm ]
Post subject: 

But surely C++ compilers can tell the difference?

Author:  bugzpodder [ Wed Feb 08, 2006 2:33 pm ]
Post subject: 

clearly not? lol

Author:  Martin [ Wed Feb 08, 2006 6:26 pm ]
Post subject: 

bugzpodder wrote:
c++:
bool isPowerOfTwo (int n)
{
    return n<0?0:(n^(n-1))==-1;
}


Another one is.

c++:
bool isPowerOfTwo (int n)
{
    return n?(n &-n)==n:0;
}

Author:  wtd [ Wed Feb 08, 2006 6:30 pm ]
Post subject: 

bugzpodder wrote:
clearly not? lol


code:
some_value >> some_other_value


Could clearly never be a type. So... why does C++ get confused? Smile

Author:  Martin [ Wed Feb 08, 2006 7:59 pm ]
Post subject: 

Would this be a problem relating to operator overloading?

Author:  bugzpodder [ Wed Feb 08, 2006 8:02 pm ]
Post subject: 

bugzpodder wrote:
c++:
bool isPowerOfTwo (int n)
{
    return n<0?0:(n^(n-1))==-1;
}


actually this is wrong. it should be

c++:
bool isPowerOfTwo (int n)
{
    return n<0?0:(n^(n-1))==2*(n-1)+1;
}

Author:  wtd [ Wed Feb 08, 2006 8:57 pm ]
Post subject: 

Martin wrote:
Would this be a problem relating to operator overloading?


More fundamental.

Author:  Martin [ Wed Feb 08, 2006 9:44 pm ]
Post subject: 

I'm at a loss.

Can we have a hint?

Author:  wtd [ Wed Feb 08, 2006 9:51 pm ]
Post subject: 

C++ templates work with more than just types. They permit the use of values as template parameters as well.

code:
some_value >> some_other_value


That isn't a type, but it is a value. The compiler is stupid enough that it sees something like "foo>>" as potentially being a value that could be a template parameter.

The problem exists because the parser is not aware enough of the semantics of the language it's parsing.

One of the requirements of C++0x compliant compilers will be that they not exhibit this problem.

Author:  wtd [ Fri Feb 10, 2006 5:29 pm ]
Post subject: 

Another C++ question

In Objective-Caml it's relatively easy to define a function which can compose two other functions to create a new function.

code:
let compose f g x = g (f x)


Now I can write:

code:
let my_func = compose (fun x -> x * 3) (fun x -> x + 1)


And this is equivalent to:

code:
let my_func x = x * 3 + 1


Write a function or function object in C++ which replicates the functionality of the compose function demonstrated above.

Author:  wtd [ Wed Feb 15, 2006 11:08 pm ]
Post subject: 

Give myList.ml as follows:

code:
module type LIST_ITEM_TYPE =
  sig
    type t
  end
 
module MyList =
  functor (Elt : LIST_ITEM_TYPE) ->
    struct
      type element = Elt.t
     
      type t =
      | Empty
      | Node of element * t
     
      let empty = Empty
     
      let rec to_list =
        function
        | Empty -> []
        | Node (v, rest) -> v :: to_list rest
       
      let rec from_list =
        function
        | [] -> Empty
        | x::xs -> Node (x, from_list xs)
       
      let rec fold_left f i =
        function
        | Empty -> i
        | Node (v, rest) -> fold_left f (f i v) rest
       
      let rec map f =
        function
        | Empty -> Empty
        | Node (v, rest) -> Node (f v, map f rest)
       
      let iter f = fold_left (fun _ b -> f b) ()
     
      let length = fold_left (fun a _ -> a + 1) 0
     
      let rec append lst1 lst2 =
        match lst1, lst2 with
        | Empty, lst2 -> lst2
        | Node (v, rest), lst2 -> Node (v, append rest lst2)

      let reverse = fold_left (fun a b -> Node (b, a)) Empty
       
    end


Complete the following:

code:
let (* your code *) in
   M.append (M.from_list [1; 2; 3]) (M.Node (4, M.Node (5, M.empty)))

Author:  rizzix [ Thu Feb 16, 2006 7:20 pm ]
Post subject: 

Write the following expression in point-free form:
Haskell:
f n = g (x n) (y n)

Author:  wtd [ Wed Mar 01, 2006 9:53 pm ]
Post subject: 

Explain why:

code:
open Int64

let factorial n =
   let rec f n acc =
      if n = Int64.zero then
         acc
      else
         f (Int64.sub n Int64.one) (Int64.mul n acc)
   in
      f (Int64.of_int n) Int64.one


Does not cause a stack overflow when called with a value of ten million.

Author:  rizzix [ Sat Mar 18, 2006 1:11 am ]
Post subject: 

rizzix wrote:
Write the following expression in point-free form:
Haskell:
f n = g (x n) (y n)


500 bits to the first person who correctly answers this. Oh and you need to explain your solution. Smile

Author:  Martin [ Tue Mar 21, 2006 6:22 pm ]
Post subject: 

Rizzix - what is point free form?

Author:  rizzix [ Wed Mar 22, 2006 1:58 am ]
Post subject: 

eta reduce it to the point where there is no "n" (function parameter) visible in that code.

Author:  Martin [ Wed Mar 22, 2006 2:17 am ]
Post subject: 

Huh?

Is there a website on this, I'm not following...

Author:  rizzix [ Wed Mar 22, 2006 5:07 pm ]
Post subject: 

An example:
Haskell:
f m n = g m (x n)
Haskell:
f m n = ((g m) . x) n
Haskell:
f m = (g m) . x


Eta-reduced, yet it is still not point free. As you can see there is still one parameter visible: m.

Another example:
Haskell:
f m n = n + m
Haskell:
f m n = (+m) n
Haskell:
f m = (+) m
Haskell:
f = (+)


As you can see after completly eta-reducing it, there are no parameters visible. This final form is an example of point-free form.

Author:  tez_h [ Mon Apr 03, 2006 9:13 pm ]
Post subject: 

rizzix wrote:
Write the following expression in point-free form:
Haskell:
f n = g (x n) (y n)


First, some useful functions:
Definitions:
(f . g) x  = f (g x)
flip f x y =  f y x
twice f x  = f x x


Now, we can derive a point-free expression of your function:
Solution:
               f n = g (x n) (y n)
{defn of (.)}      = (g.x) n (y n)
{defn of flip}     = flip (g.x) (y n) n
{defn of (.)}      = (flip (g.x).y) n n
{defn of twice}    = twice (flip (g.x).y) n

                 f = twice (flip (g.x).y)


Is that the sort of answer you were looking for?

-Tez

Author:  rizzix [ Tue Apr 04, 2006 12:56 am ]
Post subject: 

Hey! Congrats and welcome to compsci!

BTW: There is no need for you to redefine any of the Prelude functions (flip, composition). I was hoping you could do it without defining any of your own functions, like twice.

The truth is, that is not the answer I was hoping for, but it is an answer I was expecting -- or one kind of answer anyway. You get 350 bits for that one Smile

Here's my solution that's synonymous to yours (i.e worth 350bits)

Helper function:
Haskell:
toPair n = (n, n)
Eta-reduction:
Haskell:
f n = g (x n) (y n)            --          let a = g (x n)
    = (g (x n)) (y n)          -- therefore, f n = (a . y) n
    = ((g (x n)) . y) n        --                = ((. y) a) n
    = ((. y) (g (x n))) n      -- therefore, f n = ((. y) (g (x n)))
    = ((. y) ((g . x) n)) n
    = ((. y) . g . x) n n
Therefore,
Haskell:
f = (uncurry $ (. y) . g . x) . toPair


Note that if we used your function twice, it was just a matter of:
Haskell:
f = twice $ (. y) . g . x
Eitherway, this is still not what I'm looking for, for that extra 150bits. Smile

Author:  tez_h [ Tue Apr 04, 2006 5:31 am ]
Post subject: 

rizzix wrote:
Hey! Congrats and welcome to compsci!

BTW: There is no need for you to redefine any of the Prelude functions (flip, composition). I was hoping you could do it without defining any of your own functions, like twice.


Hi, and thanks. Yeah, I thought I'd just write out the definitions for ease of reference.

rizzix wrote:
The truth is, that is not the answer I was hoping for, but it is an answer I was expecting -- or one kind of answer anyway. You get 350 bits for that one Smile
<snip>
Eitherway, this is still not what I'm looking for, for that extra 150bits. Smile

Well, I haven't quite worked out if you're expecting some ultra-clever combination of (.), ($), and flip, say, but here's one that only uses standard prelude functions, starting from near the end of my derivation:
Haskell:
f n = (flip (g.x).y) n n
    = foldr1 (flip (g.x).y) (replicate 2 n)
    = (foldr1 (flip (g.x).y) . replicate 2) n
  f = foldr1 (flip (g.x).y) . replicate 2

Not pretty, and certainly point-less Wink . Similarly, starting from near the end of your derivation:
Haskell:
f n = ((. y) . g . x) n n
    = foldr1 ((. y) . g . x) (replicate 2 n)
    = (foldr1 ((. y) . g . x) . replicate 2) n
  f = foldr1 ((. y) . g . x) . replicate 2

Is that more what you're looking for?

-Tez

Author:  rizzix [ Tue Apr 04, 2006 11:51 am ]
Post subject: 

No. Let me give you a hint: I'm looking for a simpler solution Wink
Another hint: (->a)

Author:  tez_h [ Wed Apr 05, 2006 4:27 am ]
Post subject:  (-> a) monad

rizzix wrote:
No. Let me give you a hint: I'm looking for a simpler solution Wink
Another hint: (->a)


Yes, well I did see somewhere that there is a "(-> a)" monad that lambdabot (on #haskell on freenode) uses to transform point-wise expressions into point-free form. But since I haven't really done much proper haskell programming for a good few years, and googling for ' "(-> a)" monad ' turned up very little, I'm afraid I'm going to have to admit defeat here.

I'd love it if you could provide a reference or something about the (-> a) monad, or even if it has a more googlable name. Or PM me a more obvious hint!

Thanks for your time and the challenge. Now I need something to get me to learn about arrows!

-Tez

Author:  rizzix [ Thu Apr 06, 2006 1:04 am ]
Post subject: 

Just lookup the Reader Monad. (->a) is just an instance of Control.Monad.Reader. Where (->) is the function type constructor.

http://www.nomaware.com/monads/html/readermonad.html

Author:  wtd [ Thu Apr 20, 2006 2:34 pm ]
Post subject: 

C++ today.

code:
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

char upcase(const char original);
string capitalize(const string& s);

int main(int argc, char **argv)
{
   string *args = new string[argc - 1];
   copy(argv + 1, argv + argc, args);
   transform(args, args + argc - 1, args, capitalize);

   for (int i = 0; i < argc - 1; i++)
   {
      cout << i << " " << args[i] << endl;
   }

   delete args;

   return 0;
}

char upcase(const char ch)
{
   return (ch >= 97 && ch <= 122) ? ch - 32 : ch;
}

string capitalize(const string& s)
{
   string dup = s;

   if (dup.length() > 0)
   {
      dup[0] = upcase(dup[0]);
   }

   return dup;
}



I have done something wrong here. Find and explain the mistake.

Author:  Aziz [ Wed Jul 12, 2006 7:48 pm ]
Post subject: 

I like these...get more going...I'd like to see some more java and possibly even turing?

Author:  Cervantes [ Thu Jul 13, 2006 3:25 pm ]
Post subject: 

We had one Turing TYS (of sorts) a while back: http://www.compsci.ca/v2/viewtopic.php?t=10450

Author:  Slaivis [ Thu Jul 13, 2006 5:15 pm ]
Post subject: 

Cervantes wrote:
We had one Turing TYS (of sorts) a while back: http://www.compsci.ca/v2/viewtopic.php?t=10450



That's pretty cool. Can we start it up again? I'd like to be a participant of that.

Author:  Cervantes [ Thu Jul 13, 2006 5:47 pm ]
Post subject: 

That one was already solved.

Feel free to dream up questions to ask. If there are no questions, there will be no TYS.

Author:  Aziz [ Thu Jul 13, 2006 7:14 pm ]
Post subject: 

I was going to say only the well-experienced could come up with good questions, but you know what, I'm thinkin' it's not that hard, just not so many uber-complex ones (that I never get anyways). Maybe I'll write some...

Author:  wtd [ Thu Jul 13, 2006 8:16 pm ]
Post subject: 

TYS isn't about "hard" questions. It isn't about questions that take a lot of "work" to solve.

Author:  Aziz [ Fri Jul 14, 2006 8:41 am ]
Post subject: 

Exactly. Here's an easy one:

Java:
public class hello_world {
        private static String say_this_to_console;
        private static final int no_of_times = 5;
       
        public static void main(String args[]) {
                say_this_to_console = "Hello you dudes";
                if (no_of_times <= 0) {
                        System.out.println(say_this_to_console);
                } else {
                        String new_string;
                        new_string = "";
                        for (int i = 1; i <= no_of_times; i = i +1) {
                                new_string = new_string + say_this_to_console + "\n";
                        }
                        System.out.println(new_string);
                }
        }
}


This code compiles fine.

1) Change it all to proper convention.
2) Make it effecient (ie. there are several things in there that are too much work, I'm not asking for extreme effeciency, but plain sense)

Author:  wtd [ Fri Jul 14, 2006 11:56 am ]
Post subject: 

Another C++ TYS.

code:
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
   string foo[] = {"Hello", "world"};

   print_all(foo);

   return 0;
}


Make this work, such that the output is:

code:
Hello
world


You may not use "sizeof" or hard-code the size of the array. In other words, it must still work if the size of the array changes.

It must also work if the type of the array is changed. For instance, if foo were an array of five integers.

Bonus points if the body of the print_all function is only one line long.

Author:  Aziz [ Fri Jul 14, 2006 2:25 pm ]
Post subject: 

can i try doing this in java? i think i know a way...

Author:  wtd [ Fri Jul 14, 2006 2:33 pm ]
Post subject: 

Arrays work somewhat differently in Java, so it really wouldn't be much of a challenge.

That said, if you want to try, then go for it.

Author:  Null [ Fri Jul 14, 2006 9:00 pm ]
Post subject: 

Quote:

Another C++ TYS.


code:

#include <iostream>
#include <string>
#include <iterator>
#include <algorithm>
#include <cstddef>

template<typename T>
void print_all(const T *foo, size_t size) {
    std::copy(foo, foo + size, typename std::ostream_iterator<T>(std::cout, "\n"));
}

int main() {
    std::string foo[] = { "Hello", "world" };

    print_all(foo, 2);
}


Partial answer. Everything is there (and in 1 line), except I don't know how you'd find the length of an array. It's just a pointer to memory. Confused

On a related note, I don't find these challenges test one's skill, but rather they test their familiarity with the intricacies of a single language.

Author:  OneOffDriveByPoster [ Fri Jul 14, 2006 9:47 pm ]
Post subject: 

wtd wrote:
Another C++ TYS.

code:
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
   string foo[] = {"Hello", "world"};

   print_all(foo);

   return 0;
}


Make this work, such that the output is:

code:
Hello
world


You may not use "sizeof" or hard-code the size of the array. In other words, it must still work if the size of the array changes.

It must also work if the type of the array is changed. For instance, if foo were an array of five integers.

Bonus points if the body of the print_all function is only one line long.


My STL is not that good, but I think this is a full solution:

code:
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>

using namespace std;

template <typename T, size_t N>
void print_all(T (&t)[N]) {
    for (size_t i = 0; i < N; ++i) cout << t[i] << endl;
}

int main()
{
   string foo[] = {"Hello", "world"};

   print_all(foo);

   return 0;
}

Author:  [Gandalf] [ Fri Jul 14, 2006 10:07 pm ]
Post subject: 

Just about. Though that for loop should really be two lines.

Here's wtd's solution:
c++:
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
 
using namespace std;
 
template <typename T, size_t N>
void print_all(T (&arr)[N])
{
   copy(arr, arr + N, ostream_iterator<T>(cout, "\n"));
}
 
int main()
{
   string foo[] = {"Hello", "world"};
   print_all(foo);
   return 0;
}


Some crazy code, I must say.

Author:  Aziz [ Fri Jul 14, 2006 11:30 pm ]
Post subject: 

wtd wrote:
Another C++ TYS.

code:
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
   string foo[] = {"Hello", "world"};

   print_all(foo);

   return 0;
}


Make this work, such that the output is:

code:
Hello
world


You may not use "sizeof" or hard-code the size of the array. In other words, it must still work if the size of the array changes.

It must also work if the type of the array is changed. For instance, if foo were an array of five integers.

Bonus points if the body of the print_all function is only one line long.


Java:
public class PrintAll
{
    public static void main(String[] args)
    {
        String foo[] = {"Hello", "world"};

        print_all(foo);
    }

    public static void print_all(Object[] o)
    {
        int i = 0;
       
        while (true)
        {
            try
            {
                System.out.println(o[i++]);
            }
            catch (ArrayIndexOutOfBoundsException e)
            {
                break;
            }
        }
    }
}


I don't think it's quite as difficult as in c++, though?

Author:  Andy [ Sat Jul 15, 2006 12:08 am ]
Post subject: 

not even close... it wouldnt be an error in c++.. it would just output garbage.

Author:  OneOffDriveByPoster [ Sat Jul 15, 2006 12:09 am ]
Post subject: 

wtd wrote:
C++ today.

code:
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

char upcase(const char original);
string capitalize(const string& s);

int main(int argc, char **argv)
{
   string *args = new string[argc - 1];
   copy(argv + 1, argv + argc, args);
   transform(args, args + argc - 1, args, capitalize);

   for (int i = 0; i < argc - 1; i++)
   {
      cout << i << " " << args[i] << endl;
   }

   delete args;

   return 0;
}

char upcase(const char ch)
{
   return (ch >= 97 && ch <= 122) ? ch - 32 : ch;
}

string capitalize(const string& s)
{
   string dup = s;

   if (dup.length() > 0)
   {
      dup[0] = upcase(dup[0]);
   }

   return dup;
}



I have done something wrong here. Find and explain the mistake.


The obvious one is:
code:
delete args;

which should be
code:
delete[] args;
.

I am not so clear about the explanation though, so here is my try at it:
argc can be 1;
args can point to a zero-length array and be distinct from a pointer to any other object;
using "plain" delete on args in such a case causes undefined behaviour (afaik).

I suspect that
code:
args + argc - 1

is also a cause of undefined behaviour when argc is 1.

Author:  OneOffDriveByPoster [ Sat Jul 15, 2006 12:19 am ]
Post subject: 

[Gandalf] wrote:
Just about. Though that for loop should really be two lines.

Here's wtd's solution:
c++:
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
 
using namespace std;
 
template <typename T, size_t N>
void print_all(T (&arr)[N])
{
   copy(arr, arr + N, ostream_iterator<T>(cout, "\n"));
}
 
int main()
{
   string foo[] = {"Hello", "world"};
   print_all(foo);
   return 0;
}


Some crazy code, I must say.


For loop is one line now (unless if I messed the code up):
code:
template <typename T, size_t N>
void print_all(T (&t)[N]) {
    for (size_t i = 0; i < N; cout << t[i++] << endl);
}

Author:  [Gandalf] [ Sat Jul 15, 2006 1:09 am ]
Post subject: 

Andy wrote:
dump the contents of the array into the vector, and use iterators to access them?

That was my original guess as well, but how would you "dump the contents of the array into a vector" under these circumstances?

Aziz, why do that when arrays already keep track of their size in Java? Just use o.length.

Author:  Aziz [ Sat Jul 15, 2006 8:19 am ]
Post subject: 

[Gandalf] wrote:
Andy wrote:
dump the contents of the array into the vector, and use iterators to access them?

That was my original guess as well, but how would you "dump the contents of the array into a vector" under these circumstances?

Aziz, why do that when arrays already keep track of their size in Java? Just use o.length.


Trying to follow to question as much as possible...

Quote:
You may not use "sizeof" or hard-code the size of the array. In other words, it must still work if the size of the array changes.

Author:  wtd [ Sat Jul 15, 2006 8:37 am ]
Post subject: 

OneOffDriveByPoster wrote:
The obvious one is:
code:
delete args;

which should be
code:
delete[] args;
.


Yes.

OneOffDriveByPoster wrote:
I am not so clear about the explanation though, so here is my try at it:
argc can be 1;
args can point to a zero-length array and be distinct from a pointer to any other object;
using "plain" delete on args in such a case causes undefined behaviour (afaik).

I suspect that
code:
args + argc - 1

is also a cause of undefined behaviour when argc is 1.


code:
args + argc - 1


This is simply pointer arithmetic. If argc is one, then one minus one is zero, and we get the same args pointer back.

The reason we use:

code:
delete [] args


Is that using just delete would treat the start of the dynamic array as a pointer to a single string object. It would free the memory for that one object, but not for the remainder of the array. The correct form of delete in this case frees all of the memory used by the array.

Yes, the run-time does track information about how long the array is, so that it can do this.

Author:  OneOffDriveByPoster [ Sat Jul 15, 2006 10:58 am ]
Post subject: 

wtd wrote:
OneOffDriveByPoster wrote:
I suspect that
code:
args + argc - 1

is also a cause of undefined behaviour when argc is 1.


code:
args + argc - 1


This is simply pointer arithmetic. If argc is one, then one minus one is zero, and we get the same args pointer back.

I was not thinking straight--argc does not have to be 1 for the code to be wrong.

code:
args + argc - 1
adds argc to args before subtracting one.

The result of
code:
args + argc

is undefined, afaik.

To get what you want, you need
code:
args + (argc - 1)

Author:  wtd [ Sat Jul 15, 2006 11:07 am ]
Post subject: 

OneOffDriveByPoster wrote:
The result of
code:
args + argc

is undefined, afaik.

To get what you want, you need
code:
args + (argc - 1)


It is not undefined.

args is a pointer. argc is an integer, as is "argc - 1". Adding a pointer and an integer is not undefined. It is in fact the way array access works.

code:
args[n]


Is equivalent to:

code:
*(args + n)

Author:  OneOffDriveByPoster [ Sat Jul 15, 2006 11:19 am ]
Post subject: 

wtd wrote:
OneOffDriveByPoster wrote:
The result of
code:
args + argc

is undefined, afaik.

To get what you want, you need
code:
args + (argc - 1)


It is not undefined.

args is a pointer. argc is an integer, as is "argc - 1". Adding a pointer and an integer is not undefined. It is in fact the way array access works.

code:
args[n]


Is equivalent to:

code:
*(args + n)


Seriously:
code:
args + argc
causes undefined behaviour since argc is greater than the length of args[].

I guess I was wrong to say that it is "undefined", as the operation is defined (I guess).

Author:  wtd [ Sat Jul 15, 2006 11:23 am ]
Post subject: 

It only produces undefined behavior if you dereference it. My code never does that. Smile

Author:  OneOffDriveByPoster [ Sat Jul 15, 2006 11:27 am ]
Post subject: 

wtd wrote:
It only produces undefined behavior if you dereference it. My code never does that. :)


That was fast...

There is a limitation to pointer arithmetic: for any object, you can only go "one past the end" of it and still have it work the way you expect it to.

Of course, dereferencing the "one past the end" produces undefined behaviour. :)

Author:  wtd [ Sat Jul 15, 2006 11:31 am ]
Post subject: 

Indeed. I'm headed out in a bit, but until then I'm hanging out on the forums and in IRC.

And all I need to do is go one past the end of the array, so that I have a known sentinel value.

Author:  OneOffDriveByPoster [ Sat Jul 15, 2006 11:35 am ]
Post subject: 

wtd wrote:
And all I need to do is go one past the end of the array, so that I have a known sentinel value.


Thus
code:
args + (argc - 1)

so that you don't go past "one-past".

Author:  wtd [ Sat Jul 15, 2006 11:38 am ]
Post subject: 

Ok... I think you're missing something here.

Pointers are just numbers. Within the range of that integer type, I can assign any value I want to a pointer. As long as I don't dereference it, there's no problem.

Author:  OneOffDriveByPoster [ Sat Jul 15, 2006 11:40 am ]
Post subject: 

wtd wrote:
Ok... I think you're missing something here.

Pointers are just numbers. Within the range of that integer type, I can assign any value I want to a pointer. As long as I don't dereference it, there's no problem.


Everything on a computer are just numbers :)
Just do a Google search on "C++ pointer-arithmetic one-past-the-end".

Author:  Aziz [ Sat Jul 15, 2006 11:43 am ]
Post subject: 

This noobie knows something Razz doesn't it feel good?

Author:  wtd [ Sat Jul 15, 2006 12:34 pm ]
Post subject: 

As far I can tell, the standard specifies only that any of this becomes an issue when dereferencing is brought into question. Comparing the value of two pointers does not entail any dereferencing operation(s).

If you know of a section of the standard that specifies otherwise, please enlighten me.

Author:  [Gandalf] [ Sat Jul 15, 2006 12:37 pm ]
Post subject: 

Aziz wrote:
Trying to follow to question as much as possible...

Quote:
You may not use "sizeof" or hard-code the size of the array. In other words, it must still work if the size of the array changes.

You're not using any Java equivalent of "sizeof" (which wouldn't really help you anyway) by using myArray.length, nor does it cause problems when the size of the array changes. It's still only checking for the length of the array that was passed, which does not change.
Smile

Author:  Aziz [ Sat Jul 15, 2006 12:47 pm ]
Post subject: 

I guess I should learn C++ then eh Razz

Author:  OneOffDriveByPoster [ Sat Jul 15, 2006 12:49 pm ]
Post subject: 

wtd wrote:
As far I can tell, the standard specifies only that any of this becomes an issue when dereferencing is brought into question. Comparing the value of two pointers does not entail any dereferencing operation(s).

If you know of a section of the standard that specifies otherwise, please enlighten me.


5.7 [expr.add] paragraph 5; hope this helps.

Also: I'm sorry for not pm'ing the stuff to you instead of posting--I did not read the 2005 TYS thread until now.

Author:  wtd [ Sat Jul 15, 2006 1:48 pm ]
Post subject: 

If "enum" is being used in reference to all integral types, then pointer arithmetic is smply outright undefined behavior in all forms.

Author:  OneOffDriveByPoster [ Sat Jul 15, 2006 2:07 pm ]
Post subject: 

wtd wrote:
If "enum" is being used in reference to all integral types, then pointer arithmetic is smply outright undefined behavior in all forms.

? are we looking at the same thing?

Author:  wtd [ Sat Jul 15, 2006 2:15 pm ]
Post subject: 

Can you provide an exact quotation for what you're looking at?

Author:  OneOffDriveByPoster [ Sat Jul 15, 2006 2:36 pm ]
Post subject: 

wtd wrote:
Can you provide an exact quotation for what you're looking at?

Here it is:
ISO C++98 5.7.5 wrote:
When an expression that has integral type is added to or subtracted
from a pointer, the result has the type of the pointer operand. If
the pointer operand points to an element of an array object, and the
array is large enough, the result points to an element offset from the
original element such that the difference of the subscripts of the
resulting and original array elements equals the integral expression.
In other words, if the expression P points to the i-th element of an
array object, the expressions (P)+N (equivalently, N+(P)) and (P)-N
(where N has the value n) point to, respectively, the i+n-th and i-n-
th elements of the array object, provided they exist. Moreover, if
the expression P points to the last element of an array object, the
expression (P)+1 points one past the last element of the array object,
and if the expression Q points one past the last element of an array
object, the expression (Q)-1 points to the last element of the array
object. If both the pointer operand and the result point to elements
of the same array object, or one past the last element of the array
object, the evaluation shall not produce an overflow; otherwise, the
behavior is undefined.

Author:  wtd [ Sat Jul 15, 2006 2:49 pm ]
Post subject: 

Gracias.

Interesting. Of course, having the ability to go one past the end suffices for pretty much any foreseeable scenario.

Author:  OneOffDriveByPoster [ Sat Jul 15, 2006 4:59 pm ]
Post subject: 

wtd wrote:
Gracias.

Interesting. Of course, having the ability to go one past the end suffices for pretty much any foreseeable scenario.


You're welcome. Your TYS question was interesting too. :)

Author:  wtd [ Sat Jul 15, 2006 5:17 pm ]
Post subject: 

You should try some of the non-C++ questions so your frightening knowledge of ISO standards won't come into play.

Though admittedly there are a fair number of C++ TYS questions. I chalk it up to the number of odd quirks in C++ syntax and semantics.


: