macOS Recursively calling init method am I doing this right?

[ArtOfWarfare]

I'm writing a class called CalcyrNumber. Each instance contains a scaler value, an array of warnings (IE, if the user attempted dividing by zero or passed in a non-number), and a few other things that aren't important for the snippet of code I'm asking about.

The class can be initialized from a string. If the string contains any operations, it should perform those operations. These are done by splitting the string in half at the operator, recursively parsing each half with the same initWithString function, and then combining them.

Parsing is done with another class called CalcyrBase, which looks perfectly fine to me. It's able to handle user defined bases, which is why I'm using it rather than the number parses Apple provides.

What concerns me is how I'm recursively calling initWithString: … is this a proper thing to do in Obj-C, or is there a better solution that I'm missing? I've bolded the line that concerns me for emphasis.

- (CalcyrNumber *)initWithString:(NSString*)string {
    if (self = [super init]) {
        // detect and handle operations here.
        NSUInteger loc = [string rangeOfString:@"+"].location;
        if (loc != NSNotFound) {
            [b]self = [self initWithString:[string trimmedSubstringToIndex:loc]];[/b]
            [self assignmentAdd:[[CalcyrNumber alloc] initWithString:[string trimmedSubstringFromIndex:loc + 1]]];
            return self;
        }
        
        self.warnings = [[NSMutableArray alloc] init];
        self.scaler = [CalcyrBase parseNumber:string warnings:self.warnings];
    }
    
    return self;
}

 

[Sydde]

You have left out some code: -initWithString: never does anything with the string. Knowing that part might be useful for answering the question.

More importantly, I would avoid calling [super init] more than once on an object, just as a matter of form (I would guess this is a subclass of NSObject, but I have no idea what NSObject does in its -init method, probably not much). Bear in mind that you do not actually have to put the
if ( self = [super init] )
line at the very beginning of the -init… method, you could do your test before you get to that part and handle the string/substring appropriately within.

Also, make absolute sure you are not going to overrun the end of the string or you will crash.

 

[ArtOfWarfare]

You have left out some code: -initWithString: never does anything with the string. Knowing that part might be useful for answering the question.

Sure it does. First it splits the string into parts based on the operators, if any are present, and then it does this once none are present:

self.scaler = [CalcyrBase parseNumber:string warnings:self.warnings];

More importantly, I would avoid calling [super init] more than once on an object, just as a matter of form (I would guess this is a subclass of NSObject, but I have no idea what NSObject does in its -init method, probably not much). Bear in mind that you do not actually have to put the
if ( self = [super init] )
line at the very beginning of the -init… method, you could do your test before you get to that part and handle the string/substring appropriately within.

That's an interesting point I hadn't considered. It is a direct subclass of NSObject right now, but that's an implementation detail that could (I have absolutely no intentions to right now, but since it's so easy to fix, there's no reason not to fix it.)

Also, make absolute sure you are not going to overrun the end of the string or you will crash.

Those trimmedSubstring*: methods are in a category on NSString I made which takes care of that. If it's taking the start of a string and it finds the index is beyond the end, it uses the whole string instead.

If it's taking the end of a string and it finds the index is beyond the end, it just returns the empty string instead.

And if my parse method is handed the empty string, the current implementation returns 0. I'm thinking I might modify it to allow it to return 0 or 1 based on context (IE, in "/x", "x/", "x*", or "*x", I'd like the missing argument to be interpreted as 1, whereas in "+x", "x+", "-x", or "x-", I'd like the missing argument to be interpreted as 0.)

Edit:

I took a crack at making sure [super init] only gets called once:

- (CalcyrNumber *)initWithString:(NSString*)string {
    // detect and handle operations here.
    NSUInteger loc = [string rangeOfString:@"+" options:NSBackwardsSearch].location;
    if (loc != NSNotFound) {
        self = [self initWithString:[string trimmedSubstringToIndex:loc]];
        [self assignmentAdd:[[CalcyrNumber alloc] initWithString:[string trimmedSubstringFromIndex:loc + 1]]];
        return self;
    }

    if (self = [super init]) {
        self.warnings = [[NSMutableArray alloc] init];
        self.scaler = [CalcyrBase parseNumber:string warnings:self.warnings];
    }
    
    return self;
}

My only change was moving the operation handling above of self = [super init].

It seems to me the way that this will work is:

alloc/initWithString"3+5"
=> initWithString"3"
==> super init
==> return my first object containing 3
=> alloc/initWithString"5"
==> super init
==> return my second object containing 5
=> return my first object containing 8 (and I think ARC will autorelease the second object.)

So [super init] only gets called once per call to alloc.

 

[mrichmon]

The typical model in OO languages when you want to support a constructor with no arguments and constructor(s) with arguments is:

init() // constructor with no arguments 
{
    super.init();
    perform initialization on object
}

init_with_arg1(string arg) // constructor with one string argument
{
    self.init();
    perform initialization that depends on arg
}

init_with_arg2(string arg, init num) // another constructor
{
    self.init_with_arg1(arg);
    perform initialization that depends on num
}

This involves thinking about the parts of code that depend on the various arguments. But it has the benefit of having a single call point to self.init and to super.init.

Typically, an assignment to "self" should be avoided since that idiom can lead to memory leaks.

 

[ArtOfWarfare]

The typical model in OO languages when you want to support a constructor with no arguments and constructor(s) with arguments is:

init() // constructor with no arguments 
{
    super.init();
    perform initialization on object
}

init_with_arg1(string arg) // constructor with one string argument
{
    self.init();
    perform initialization that depends on arg
}

init_with_arg2(string arg, init num) // another constructor
{
    self.init_with_arg1(arg);
    perform initialization that depends on num
}

This involves thinking about the parts of code that depend on the various arguments. But it has the benefit of having a single call point to self.init and to super.init.

Typically, an assignment to "self" should be avoided since that idiom can lead to memory leaks.

The equivalent in Objective-C to super.init and self.init is [super init] and [self init]. I initially had just [self initWithString:[string substring…]] but the compiler complained that I should assign the results of a call to an init method to self.

Your example didn't seem relative at first glance, but as I thought about it, I realized that what my method is doing is it's consuming a small part of the string and then calling other init methods with the different parts of the string, and that though the syntax doesn't look the same, your example is consuming variables and passing other variables in the same way.

So… is my code correct? I'm getting the sense that, though it looks quite unusual, it's correct.

 

[iSee]

The equivalent in Objective-C to super.init and self.init is [super init] and [self init]. I initially had just [self initWithString:[string substring…]] but the compiler complained that I should assign the results of a call to an init method to self.

Your example didn't seem relative at first glance, but as I thought about it, I realized that what my method is doing is it's consuming a small part of the string and then calling other init methods with the different parts of the string, and that though the syntax doesn't look the same, your example is consuming variables and passing other variables in the same way.

So… is my code correct? I'm getting the sense that, though it looks quite unusual, it's correct.

I think it will work... I think. But since you asked for a code review , I'll add:

I recommend you change it because it's confusing and unnecessary. There are a set of conventions associated with initializers that you shouldn’t deviate from unless you’ve got a really good reason. Sticking with the conventions make it easy to avoid mistakes (e.g., like calling [super init] more than once). So, perhaps move the parsing into a utility method.

Personally, I wouldn’t use recursion there either because you’re just processing the string from one end to the other. A simple loop will do fine. But I guess that's mostly a style thing (unless your input string could be quite large I wouldn't worry about the overhead of recursion... premature optimization is evil and all that.)

 

[ArtOfWarfare]

Personally, I wouldn’t use recursion there either because you’re just processing the string from one end to the other. A simple loop will do fine. But I guess that's mostly a style thing (unless your input string could be quite large I wouldn't worry about the overhead of recursion... premature optimization is evil and all that.)

I don't know that this is possible without recursion. The code sample I shared only uses addition, but I've since expanded it to have +, -, *, /, %, and (), all evaluating in the correct order. Next, I'll probably add power, root, log, some trig functions, bitwise functions, and maybe some more. Then there's other things that it needs to handle besides just operators.

 

[mrichmon]

I don't know that this is possible without recursion. The code sample I shared only uses addition, but I've since expanded it to have +, -, *, /, %, and (), all evaluating in the correct order. Next, I'll probably add power, root, log, some trig functions, bitwise functions, and maybe some more. Then there's other things that it needs to handle besides just operators.

Every recursive program can be restructured into an iterative solution.

For calculator systems a common implementation strategy is to:

• use reverse polish notation in the calculation string, or
• use a pushdown stack to evaluate sub-expressions and hold partial results

 

[ArtOfWarfare]

Every recursive program can be restructured into an iterative solution.

For calculator systems a common implementation strategy is to:

• use reverse polish notation in the calculation string, or
• use a pushdown stack to evaluate sub-expressions and hold partial results

I'm expecting this program will be useful for people like my fiancé, who has enough difficulty with infix notation - I don't think I'll try teaching her RPN.

As for using a stack, that seems silly. C/Obj-C already use a stack with implicit pushes and pops when functions call and return. I don't see a reason to implement my own stack to work alongside the stack that's already present, when the existing stack was conceived basically for exactly what I'm doing.

 

[mrichmon]

I'm expecting this program will be useful for people like my fiancé, who has enough difficulty with infix notation - I don't think I'll try teaching her RPN.

As for using a stack, that seems silly. C/Obj-C already use a stack with implicit pushes and pops when functions call and return. I don't see a reason to implement my own stack to work alongside the stack that's already present, when the existing stack was conceived basically for exactly what I'm doing.

Your code so implement it how you like. But the task of implementing a calculator is a common problem in which particular implementation strategies can make the code easier to write and debug. The advice you are receiving in this thread has been advising you directly toward these strategies.

Two things:

1. Converting infix notation to postfix notation while parsing the calculation is a trivial programming exercise.
2. You are conflating the execution stack with a stack data-structure. The difference is that a stack data-structure is used to shape the implementation strategy to simplify the problem.

Good luck.

 

[ArtOfWarfare]

1. Converting infix notation to postfix notation while parsing the calculation is a trivial programming exercise.

1. 
   
   Were I requiring complete parenthezation (is this an actual word? Not sure...) then I can see how that would be trivial, but as I'm letting the user enter it as they please, it seems it would be just as complicated as the parsing I'm doing now. Why would I bother converting it to a string that looks different?

 

[Sydde]

I don't know that this is possible without recursion. The code sample I shared only uses addition, but I've since expanded it to have +, -, *, /, %, and (), all evaluating in the correct order. Next, I'll probably add power, root, log, some trig functions, bitwise functions, and maybe some more. Then there's other things that it needs to handle besides just operators.

By "correct order" I assume you mean correct priority as well? As in "2 * 3 + 4" == "4 + 2 * 3"? Getting that right in a recursive scheme seems like it would be more of a challenge than with straight scanning. Elegance can be nice when it makes your work easier and your code more readable and more flexible, but it can be the more difficult approach – in which case, you would have to ask yourself if it is worth the trouble.

 

[ArtOfWarfare]

By "correct order" I assume you mean correct priority as well? As in "2 * 3 + 4" == "4 + 2 * 3"? Getting that right in a recursive scheme seems like it would be more of a challenge than with straight scanning. Elegance can be nice when it makes your work easier and your code more readable and more flexible, but it can be the more difficult approach – in which case, you would have to ask yourself if it is worth the trouble.

Yes, that is what I mean. I found the code that worked with getting the priority to work a bit of a surprise... it was quite counterintuitive. Things which I want evaluated first, need to be broken into subexpressions last.

 

[iSee]

I don't know that this is possible without recursion. The code sample I shared only uses addition, but I've since expanded it to have +, -, *, /, %, and (), all evaluating in the correct order. Next, I'll probably add power, root, log, some trig functions, bitwise functions, and maybe some more. Then there's other things that it needs to handle besides just operators.

I see. Hmm. This is a well-understood problem with a well-documented solution. Ah, here's a link to get you started: http://en.wikipedia.org/wiki/Shunting-yard_algorithm

As suggested in another post, it's a two step process: a first pass over the expression to convert the expression from the conventional notation -- taking into account the precedence of operations, parenthesis that may appear or whatever else you want to support -- to an RPN sequence (well, there are other options too, but RPN seems like a good fit to me). Then a second pass over the RPN to evaluate the expression.

(To suggest that that's trivial is absurd, however. It certainly is not. We wouldn't have needed Dijkstra to invent it if it was trivial! It's not complicated at all but it's far from obvious unless you are already familiar with the algorithm.)

 

[subsonix]

You certainly can use a recursive parser for this. I have used recursive descent for this my self. While it may take some thinking initially to get it right, the beauty of it is when the parser is done you can just give it symbols as they appear in the input string and they will all be encoded with the right priority in the ast. The consequence of this is that you can then do an in order traversal of the tree and the entire expression will be evaluated in correct order, again because that's the way the tree is built.

 

[ArtOfWarfare]

I see. Hmm. This is a well-understood problem with a well-documented solution. Ah, here's a link to get you started: http://en.wikipedia.org/wiki/Shunting-yard_algorithm

Very interesting - thank you.

 

[Mac_Max]

If you're doing simple arithmetic perhaps NSPredicate is better?

http://funwithobjc.tumblr.com/post/1553469975/abusing-nspredicate

Also googling around turned up this: https://github.com/unixpickle/ANExpressionParser

Might be a good source for inspiration.

 

[gnasher729]

What concerns me is how I'm recursively calling initWithString: … is this a proper thing to do in Obj-C, or is there a better solution that I'm missing? I've bolded the line that concerns me for emphasis.

You need to know what is actually happening.

The alloc class method returns an object of the class, setup to be a proper object of that class, with all members initialised to 0 / nil / NULL as appropriate. At that point, initWithString: is just an ordinary method like any others, except that it expects a completely uninitialised object. It is expected to either initialise and return the object, or to return nil if there is some kind of failure, or to initialise and return a different object.

First thing you call self = [super init]. At that point, "self" is not an uninitialised object anymore. Therefore you shouldn't call [self initWithString: ], because initWithString expects an uninitialised object. You could write

self = [[CalcyrNumber alloc] initWithString:...]

 

[ArtOfWarfare]

You need to know what is actually happening.

The alloc class method returns an object of the class, setup to be a proper object of that class, with all members initialised to 0 / nil / NULL as appropriate. At that point, initWithString: is just an ordinary method like any others, except that it expects a completely uninitialised object. It is expected to either initialise and return the object, or to return nil if there is some kind of failure, or to initialise and return a different object.

First thing you call self = [super init]. At that point, "self" is not an uninitialised object anymore. Therefore you shouldn't call [self initWithString: ], because initWithString expects an uninitialised object. You could write

self = [[CalcyrNumber alloc] initWithString:...]

Right, in the third post in this thread I posted a revised version where it calls [super init] only if it doesn't need to call [self initWithString:…]

 

[Senor Cuete]

Not Reentrant?

Some functions are not reentrant. For example they might declare a static or external variable, or they might malloc memory for a *. This was an issue with the Mac Toolbox - many of the functions weren't reentrant and this is probably true for the successor, Carbon. Cocoa encapsulates Carbon toolbox calls. Objects in a framework are a black box - you don't know how they are implemented, what data is in them and how they allocate memory. For this reason you should not assume that you can call an object method recursively. It will cause you to to violate the law of unintended consequences. Yes, passing the pointer to the object with the init method and the message init is probably safe but probably is a big word when it comes to programming your computer. For example the init message might (probably will) overwrite the initialization done to the object's data by an earlier call in the chain of recursion.

So FWIW IMHO what you're doing is very foolish - don't do it.