Coding: Fleeting Thoughts

[Flumble]

Can a string like "6/2+9/3" not occur or have you not thought about expressions that can't be expressed as a list of operator+operand? (also see Shunting-yard if you have't already)

[The Great Hippo]

I think my initial goal (to create list of strings that could be parsed as simple-to-execute statements) was deeply flawed; I'm reading the shunting-yard algorithm now (I ninja-edited my post to mention it >.>), and starting to understand that yeah, my initial idea doesn't really work for complex cases at all.

[ahammel]

I'm trying to create a function that takes strings with nested parenthesis and operators (ex: "4 + ((10 - 1) / 2)") and breaks the string down into a list of strings that can be interpreted as the correct order of operations (ex: ["10", "- 1", " / 2", " + 4"]).

This is turning out to be way trickier than I thought (but at least I'm learning about the shunting yard algorithm, plus prefix vs postfix vs infix notation).

If there's a decent parser generator available in your programming environment, I recommend using that to get the abstract syntax tree and do any post-processing you need on that. God help you if you need it to be left-binding.

[The Great Hippo]

If there's a decent parser generator available in your programming environment, I recommend using that to get the abstract syntax tree and do any post-processing you need on that. God help you if you need it to be left-binding.

I'm probably going to end up doing it this way, but since I'm at work (and can't access libraries aside from what's core to Python 3.x), I'm still going to mess with it a little bit.

When you say 'left-binding', are you referring to operators which operate on operands that are to their left? IE, how "9 + 4 / 2" requires you to perform "4 / 2" before adding 9?

[ahammel]

If there's a decent parser generator available in your programming environment, I recommend using that to get the abstract syntax tree and do any post-processing you need on that. God help you if you need it to be left-binding.

I'm probably going to end up doing it this way, but since I'm at work (and can't access libraries aside from what's core to Python 3.x), I'm still going to mess with it a little bit.

I seem to recall that I was unable to find a satisfactory parser generator for Python the last time I tried, but that was several years ago now.

When you say 'left-binding', are you referring to operators which operate on operands that are to their left? IE, how "9 + 4 / 2" requires you to perform "4 / 2" before adding 9?

Not quite. The problem comes when you have operators that have the same precedence and you have to make a decision about which comes first. For instance, if you have a string like "a <> b <> c" (where <> is some arbitrary infix operator) you can parse that into a binary tree in one of two ways. Right-binding gives you (2 <> (3 <> 4)), while left-binding gives you ((2 <> 3) <> 4). For most parser generators, it's natural to define right-binding like so:

Code: Select all

Statement = Variable (Operator Statement)?

(i.e., a Statement is Variable, optionally followed by an operator and another statement). The left-binding version would be this:

Code: Select all

Statement = (Statement Operator)? Statement

but the parser generators I've used will either not compile that, or will infinite loop.

I had this problem just today at work, actually. The solution was to unroll the left recursion using the '*' operator:

Code: Select all

Statement = (Statement Operator)* Statement

You need to do some post-processing to make it spit out a binary tree, though.

Here's a full pegjs example if you want to play with it a bit:

Code: Select all

RightBindStatement
  = v:Var Op s:RightBindStatement
  { return { left: v, right:s } }
  / Var
 
LeftBindStatement
  = ls:(Var Op)* r:Var
  { return leftAssociative(ls, r);

    function leftAssociative(ls, r) {
        if (!ls.length) return r;
        var last = ls.pop();
        return {left:leftAssociative(ls, last[0]), right:r};
    }
  }

Op = _* "<>" _*
Var = [a-z]
_ = [ \t\n]


[The Great Hippo]

Thank you! That explanation actually managed to make me realize why my attempt wasn't working. I think I've managed too get a shunting-yard algorithim working (the code is clumsy because I just hacked this together real fast, but -- so far -- it's producing expected outputs):

Spoiler:

Code: Select all

import re

# Precedence Dictionary
OPER = {"-" : 2,
      "+" : 2,
      "/" : 3,
      "*" : 3,
      "^": 4}

# Right/Left Binding
RIGHT = {"^"}
LEFT = {"/", "*", "-", "+"}


input_text = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
correct = [3, 4, 2, "*", 1, 5, "-", 2, 3, "^", "^", "/", "+"]

#input_text = "5 + ((1 + 2) * 4) - 3"
#correct = [5, 1, 2, "+", 4, "*", "+", 3, "-"]

def simplify(text):
   raw = re.split("([+-/()*^ ])", text)
   formatted = [e for e in raw if e != " " and e != ""]
   return parse(formatted)


def parse(tokens):
   output = []
   stack = []
   for t in tokens:
      try:
         output.append(int(t))
         continue
      except ValueError:
         pass
      if t in OPER:
         output += _pop_operators(t, stack)
         stack += t
      elif t == "(":
         stack += t
      elif t == ")":
         output += _pop_parenthesis(t, stack)
   for t in reversed(stack):
      if t == ")":
         raise Exception("Mismatched parenthesis")
      output.append(stack.pop())
   return output


def _pop_operators(token, stack, output=None):
   if output is None:
      output = []
   if len(stack) == 0 or stack[-1] not in OPER:
      return output
   o = stack[-1]
   if o in OPER:
      if ((token in LEFT and OPER[token] <= OPER[o]) or
            (token in RIGHT and OPER[token] < OPER[o])):
         output.append(stack.pop())
         return _pop_operators(token, stack, output)
   return output

def _pop_parenthesis(token, stack, output=None):
   if output is None:
      output = []
   if len(stack) == 0:
      raise Exception("Mismatched ()")
   o = stack[-1]
   if o == "(":
      stack.pop()
      return output
   output.append(stack.pop())
   return _pop_parenthesis(token, stack, output)
   


print("input: " + input_text)
print("output: " + str(simplify(input_text)))
print("correct: " + str(correct))


I've tested it for two cases ("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" and "5 + ((1 + 2) * 4) − 3") and it's producing the correct RPN; I'm trying to find more examples of correct RPN outputs so I can test it a little more.

[ahammel]

I'm not sure I follow your code, but I don't think you have a left vs. right binding problem. All of the operators you're working with are associative, so you can bind to the right or the left at your choice after you've accounted for BEDMAS precedence. The only exception is exponentiation, which is right-associative ( 2^3^4 == 2^(3^4) != (2^3)^2 ), so it's natural for the whole parser to be right-binding.

If you parse your expression to a binary tree first (easier said than done, obviously!) converting to rpn becomes really nice:

Code: Select all

BTree = namedtuple('BTree', ['opr', 'left', 'right'])

def rpn(expression):
    if not(hasattr(expression, 'opr')  and
           hasattr(expression, 'left') and
           hasattr(expression, 'right')):
        # i.e., if expression is base value, not a tree
        return [expression]

    return rpn(expression.left) + rpn(expression.right) + [expression.opr]
   
example = BTree("+", BTree("*", 1, 2), BTree("/", 3, 4))
print(rpn(example))

[Xenomortis]

Subtraction and Division are not associative: "20 o (10 o 2) != (20 o 10) o 2" for both o = - and o = /.
Further, if pressed, I'd be inclined to make them left-associative, mirroring how naive calculators work, leaving exponentiation as right-associative.

Edit:
Use the correct symbol for subtraction.

[ahammel]

Subtraction and Division are not associative: "20 o (10 o 2) != (20 o 10) o 2" for both o=* and o=/.

...well that explains why I could never do better than a B in math.

[Xenomortis]

This problem would be so much easier if I could just allocate 200GB of memory.
But no, I have to be clever and work out element repetitions and tiling patterns for these arrays that act as axes for some n-dimensional dataset, and filter out points that aren't inside some prism like region.
And I thought I'd solved it, but then it turns out sometimes these axes can run backwards and now I have to work *that* out.

Nobody told me programming would be hard!

[ThemePark]

This problem would be so much easier if I could just allocate 200GB of memory.
But no, I have to be clever and work out element repetitions and tiling patterns for these arrays that act as axes for some n-dimensional dataset, and filter out points that aren't inside some prism like region.
And I thought I'd solved it, but then it turns out sometimes these axes can run backwards and now I have to work *that* out.

Nobody told me programming would be hard!

Outsource work, problem solved!

[Flumble]

This problem would be so much easier if I could just allocate 200GB of memory.

If your hadoop cluster doesn't have at least 1TB RAM there's not enough money going to IT!

[raudorn]

Today I learned that a zero is not always a zero:

Code:

Code: Select all

printf("%f (%f)", foo(bar), 0);

Expected output:

Code: Select all

0.000000 (0.000000)

Actual ouput:

Code: Select all

0.000000 (0.015625)

Turns out when printf expects a float, you should give a float, otherwise expect unexpected output.

Corrected code:

Code: Select all

printf("%f (%f)", foo(bar), 0.0);

[Thesh]

%f expects a double, which is 8 bytes, and you provided an integer which is probably 4 bytes. Because it expects 8 bytes, it is also reading whatever is in the next 4 bytes after the integer - this is a buffer overflow error which could lead to a security flaw as it can leak information.

[raudorn]

Ah, the wonders of C. It's a good thing I long ago swore to never to do anything security related unless I'm damn sure what I'm doing and I only ever broke that promise, like, seven times at most.

[Tub]

These are the oldest compilers I could find, and they both warn by default.

gcc 4.8.4

Code: Select all

 /tmp> gcc printf.cpp
printf.cpp: In function ‘int main()’:
printf.cpp:9:31: warning: format ‘%f’ expects argument of type ‘double’, but argument 3 has type ‘int’ [-Wformat=]
  printf("%f (%f)", foo(bar), 0);

clang 3.5

Code: Select all

 /tmp> clang++-3.5 printf.cpp
printf.cpp:9:30: warning: format specifies type 'double' but the argument has type 'int' [-Wformat]
        printf("%f (%f)", foo(bar), 0);
                    ~~              ^
                    %d

[jeanrenaud]

Hi folks,

Here is the only proof by code that 1=0 ! Runs on Excel VBA.

Copy-paste this into a module, then press "play" with the cursor inside the procedure:

Code: Select all

Sub t()
    x = 2
    If x * ½ = 0 Then MsgBox "It is proven that 1=0 !"
End Sub


[chridd]

Code: Select all

½

Let me guess... it's treating all non-ASCII characters as usable in identifiers, and so this is a variable name... and undefined variables default to 0 (or some value that converts to zero when used as a number)... so the "½" is actually not one half, but 0.

(Edit: Or maybe it's just some non-ASCII characters, but ½ isn't recognized and is printable so defaults to being an identifier character.)

[jeanrenaud]

Yes, you are right. Excel has a very loosy "allowed characters" in variable names

I'm just not sure why my post got here. I made a separate post for it...

[jeanrenaud]

So you can get very weird looking code by using chr(255) as a variable character (which looks like a space, but is a valid identifier) :

Code: Select all

Private Type       
      As Boolean
End Type

Sub t()
      =   
    MsgBox      ( ,  )
        =   +   
 :
    For      =   To   
   
    Next
End Sub

Function      (  As Variant,    As Variant) As Boolean
          = False
End Function
 

And excel will accept all the stuff !

[phlip]

↶
I'm just not sure why my post got here. I made a separate post for it...

Yeah, I merged it in... I thought it made a better fit in here (and would probably get more traction)

[jeanrenaud]

Or you can find a guy who is coding VBA, and if you dislike this guy, you open his code and add random "chr(255)" characters in his code (like at the beginning or the end of some variables), so everything will break up, and he will possibly have a hard time finding why his code is broken.

Mwa ha ha ha ha !

[phlip]

Code: Select all

' Some assertions to verify maths is still working
¼ = 0.25
½ = 0.5
¾ = 0.75
' OK, everything seems good

Sub t()
    x = 2
    If x * ½ = 1 Then MsgBox "Multiplication still works as expected"
End Sub

[The Great Hippo]

Okay, so I have a pretty straightforward parser class that can transform strings written in infix notation into single values ("(3-2) * 5" into 5). You can load custom operators and functions (unary or otherwise), and also provide 'internal' values as keywords that can be referenced by the expressions (so, like, "(myvalue - 10)" is valid if you instanced the parser with a myvalue keyword assignment; it'll also traverse attributes on those assignments. So "(myvalue.my_attribute - 10)" is also valid, presuming the thing you assigned to myvalue has an attribute named "my_attribute").

The next step is to pick a method of storing, editing, and loading data; tables, maybe? I have some experience with xml, but I've been told xml is not really your friend when it comes to data.

This is for D&D-esque stuff, most likely? So the data is going to be stuff like -- stats for a monster, or a sword; possibly tables and charts for experience, spell-level, etc.

[Thesh]

Depends on what kind of data and what you need to be able to do with it. SQLite is great, but it might be overkill. XML works fine, but it can be bulky and hard to skim if you want to be able to read it. JSON is a nice lightweight solution, or YAML if you want a bit more human readability. Or you can play around with writing your own simple binary format, depending on your needs.

[The Great Hippo]

Hm; thanks! At a glance, both YAML and JSON look like good solutions. I'm a little tempted by the idea of doing something myself -- just for the sake of easily-readable tables -- but if I did, I'd probably follow YAML's example pretty closely anyway.

[ahammel]

Or you can find a guy who is coding VBA, and if you dislike this guy, you open his code and add random "chr(255)" characters in his code (like at the beginning or the end of some variables), so everything will break up, and he will possibly have a hard time finding why his code is broken.

Mwa ha ha ha ha !

Can't find it now, but I saw a script on GitHub to replace, eg, semicolons with very similar looking Unicode characters. Run it on your cowoekers' code and watch them tear out their hair looking for the compiler bug! Or restrict it to running on string literals for more insidious evil.

[chridd]

So you can get very weird looking code by using chr(255) as a variable character (which looks like a space, but is a valid identifier)

Shouldn't chr(255) be ÿ? Does it really use DOS encoding?

Or you can find a guy who is coding VBA, and if you dislike this guy, you open his code and add random "chr(255)" characters in his code (like at the beginning or the end of some variables), so everything will break up, and he will possibly have a hard time finding why his code is broken.

Mwa ha ha ha ha !

Can't find it now, but I saw a script on GitHub to replace, eg, semicolons with very similar looking Unicode characters. Run it on your cowoekers' code and watch them tear out their hair looking for the compiler bug! Or restrict it to running on string literals for more insidious evil.

There's also Acme::Bleach for Perl.

[ThemePark]

Shouldn't chr(255) be ÿ? Does it really use DOS encoding?

If by DOS encoding you mean code pages, then yes.

http://stackoverflow.com/questions/2256 ... r-encoding

Code page 437 to be exact, in where character 255 is a non breaking space. Mystery solved.

https://en.wikipedia.org/wiki/Code_page_437

[Wildcard]

Code: Select all

>>> import networkx
>>> g = networkx.Graph()
>>> my_dict = {"x": 0, "y": 0}
>>> g.add_node("node", my_dict, y=1)
>>> print(my_dict)
{'y': 1, 'x': 0}
>>> my_dict["x"] = 1
>>> print(g.node["node"])
{'y': 1, 'x': 1}
>>> my_other_dict = {"x": 5}
>>> g.add_node("node", my_other_dict)
>>> print(my_dict)
{'y': 1, 'x': 5}
>>> g.add_node("other node", my_dict)
>>> my_dict["x"] = 10
>>> print(g.node["node"])
{'y': 1, 'x': 10}
>>> print(g.node["other node"])
{'y': 1, 'x': 10}

It's funny, I don't consider myself a Python programmer by any stretch, but I still spotted the error there and thought, "Hey, someone thinks Python variables are boxes into which you can dump values, but they're not; they're labels which you can attach to objects." Nice job finding and fixing that, Hippo.

Complex systems have bugs. Complex systems coupled to systems with bugs rely on those bugs to operate.

This is a rather profound statement. I like it.

Hmmm. It doesn't, however, mean that you shouldn't fix bugs. It just means that you will need to fix the bugs in the related systems (that are under your supervision), or that you will need to put pressure on the external systems to fix their bugs, and warn that you aren't backward compatible with those bugs anymore after version x.y.z.

Also, after another moment's thought, I think you have cause and effect mixed up. The proper statement is:

Systems into which bugs are introduced become complex.

Systems into which bugs are not introduced remain simple. Regardless of how many "moving parts" they have.

The real question becomes, what IS a "bug" and how can we precisely define it?

(Also: nice answer. *waves*)

This is also why, the *moment* I start getting confused, I print something to verify that execution is actually running thru the code I'm writing. This instinct has saved me hours of debugging time. I often do it even before I start getting confused, just to make sure I'm looking at the right code in the first place.

This is a brilliant instinct; I like it. I have a similar one for tech support problems: I never believe any description of a bug that I haven't seen. When I am asked to help someone with a computer problem (whether transposing a column in Excel or fixing a CFEngine policy so it correctly detects and repairs a corrupt RPM database), I want to see what is described. I don't take it for granted that it has been correctly observed.

[Tub]

Have you ever had the need to change the network configuration on a headless machine? Do you remember double-checking everything before accepting the new network configuration and rebooting? Do you remember cursing, when you finally realized that the machine has not come back up and will not come back up?

Yesterday, I did one better.

The problem was simple: I wanted to set up a software access point, so I needed a bridge connecting eth0 and wlan0. What I didn't realize at the time was that DHCP requests would henceforth be sent from the bridge's made-up MAC address instead of eth0's MAC, so I should have reconfigured the DHCP server. Machine didn't come up, I attached keyboard and monitor and started to diagnose the problem. Should have been easy enough from there.

After an hour of debugging and trial-and-error reconfiguration, I noticed a second problem: while attaching keyboard and monitor, I had managed to misalign the ethernet plug.

[Moo]

EEEEEeeeeee I am not a good test taker!!!!!!!!!!!11

Just did an online programming assessment (looking for a job) using HackerRank. Nice platform, decent and interesting questions. But damn if my mind doesn't go blank the minute the timer starts running.

Eh, I guess we'll see how it goes. Realised as soon as I finished that the reason one of my functions didn't work is because I thought I was being clever by showing I know not to compare floating points like this "if (x == y)" but "if ((x - y) > int.MinValue)", but didn't take the absolute value of x - y. DAMMIT.

[Flumble]

Also int.MinValue looks like a constant for the lower bound of signed integers, rather than the constant for the smallest positive float value, let alone a dynamic value based on the magnitude of both numbers.

Anyway, there's not real life scenario in which you test floats for equality, right?

[Thesh]

Yeah, I usually do if abs(a-b) < 0.01 (or whatever precision I just need) if I am forced to compare floats for equality.

[raudorn]

1.0 bottles of beer, 1.0 bottles of beer on the wall.
Take 0.9 down, pass it around, 0.1000000000000001 bottles of beer on the wall.

double.MaxVal bottles of beer, double.MaxVal bottles of beer on the wall.
Take int.MaxVal down, pass them around, double.MaxVal bottles of beer on the wall.

[Link]

↶
EEEEEeeeeee I am not a good test taker!!!!!!!!!!!11

Just did an online programming assessment (looking for a job) using HackerRank. Nice platform, decent and interesting questions. But damn if my mind doesn't go blank the minute the timer starts running.

Eh, I guess we'll see how it goes. Realised as soon as I finished that the reason one of my functions didn't work is because I thought I was being clever by showing I know not to compare floating points like this "if (x == y)" but "if ((x - y) > int.MinValue)", but didn't take the absolute value of x - y. DAMMIT.

I did something similar in Python recently. I had some functions that are sensitive to small perturbations, so I filtered the inputs using "0 if x < delta else x". I got extremely confusing results, until I eventually realised I was setting my (large!) negative inputs to 0; what I had meant to write was "0 if abs(x) < delta else x".

[Moo]

That makes me feel better

Although, I couldn't have done too badly, got invited for an interview on Monday.

I'm pretty sure half the time the novelty of a female dev is enough to get me in the door so they can see what this mythical creature looks like

[AngrySquirrel]

So uhm, here's the thing, I feel like I'm an imposter.

I'm not a programmer. I've never claimed to be a programmer nor do I ever intend to. I do however program. I write small programs, I update big ones, I maintain pages upon pages of spaghetti code, and I help develop new programs. I also regularly take courses in web development and programming languages I've not already studied. But I'm not a programmer.

If I start applying for jobs again, I'll most likely get most the most interesting offers from companies who want me to do at least partial development/programming/translation between programmers and others. I can list at least 5 languages which I actively use every day and I can pick up a new language pretty goddamned quick. But I'm not a programmer.

I feel if I am to call myself a programmer I need to be better. I need to be able to see errors without running the programs first. I feel I should be able to write things without googling to check up on syntax. I feel every single person who calls themselves a programmer, or otherwise works in IT is better than me at everything. That everyone understands everything better than me. That there's some big secret I just don't get.

And I don't know if this is truth. Or just a result of my low self-confidence. Or just imposter-syndrome. Or just shit. I don't know. And I don't know how to figure it out.

[Yakk]

At upteen-odd¹ years of programming, in my language of specialization, I can sometimes write a small program without checking documentation, having syntax errors, or bugs, or the like. I am pleasantly surprised when it happens.

Almost always those small programs are made out of pieces that I have written more than once before. Doing something novel or interesting has a much lower success rate.

Imposter syndrome is normal and pretty universal. The people who claim not to be "imposter"s are usually bluffing. Everyone tends to put their best, most competent face forward; so if you compare yourself (top to bottom) to the public face you see in others, you feel incompetent.

At the same time, Dunning-Krugar means that if you think you are competent, that isn't useful evidence.

---

In related news, this is why I'm afraid of web dev:

http://www.funnyjunk.com/Using+the+righ ... s/5491981/

---

¹ Exact value obscured to protect the guity.

[raudorn]

I feel if I am to call myself a programmer I need to be better. I need to be able to see errors without running the programs first. I feel I should be able to write things without googling to check up on syntax.

Personally, I don't expect employed/professional/experienced programmers to be able to do that either. Googling syntax is fine, you will remember it with repetition. Or not, then it wasn't important.

Identifying errors without running the program is also a higher skill that's useful, but not required in order to be a successfull programmer. Although, to be fair, there's a class of errors that can only by identified by examining the program closely, line by line. Those errors boil down to "what I wrote isn't what I meant, but it's valid syntax". For all else there's testing. Half of "error diagnosis" is the editor's syntax highlighting and compiler errors/warnings. The fast feedback cycle with modern systems has reduced the amount of line-by-line checking a lot by giving you hints where to look and often the mistake is then obvious. There's nothing wrong with relying on these tools for errors as simple as "spelled wihle wrong".

The other thing, the "big secret", is 50% general SD experience, 15% theory of computer science and 35% tribal knowledge. All of which can be acquired with time and each can substitute for the others, at least to a certain degree.

Lastly, "programmer" is just a label. The two definitions I've encountered most often are 1.) "A programmer is someone who can write useful and non-trivial programs" and 2.) "A programmer is someone who spends most of their (paid or unpaid) work-time with programming or other software development aspects".