Programming thread

[Kosher Dill]

When you're dealing with recursive functions, do you imagine the whole tree of functions

No, I just say "What if I knew the answer to the next smaller case, or all smaller cases, what would I do right now?"
And of course make sure you do actually get to a base case eventually.

 

[Agent Sandoval]

This one is simple, but would you imagine or picture in your head the whole tree/paths?

https://en.wikipedia.org/wiki/Mathematical_induction ^ ever did this at school?

Count me as a +1 for induction. Identify your base case and the change unit; the nth case is simply the function as written. Though, sometimes it doesn't work out so cleanly, especially when writing a parser for example.

Dodgy stuff starts happening if you add persistent context to it (not f(n) but f(n, context)).

This can be made a hundred times easier by making any context object/function write-only and handle anything context sensitive using the context's add method. It's much easier that way to verify the recursive induction and context state machine independently.

 

[779777]

A question for the pros here, if you want to answer.

When you're dealing with recursive functions, do you imagine the whole tree of functions, or closely keep track on which step you are mentally? Or do you just summarize what is supposed to do and call it a day?

Like for:

def f(n):
  if n <= 1:
    return n
  return f(n - 1) + f(n - 2)

print(f(8))

This one is simple, but would you imagine or picture in your head the whole tree/paths?

I mainly try to think through it until I fail to grasp it (recursion is like exponential growth as far as the mental load for each recursive call), when that fails I step into the debugger just so I can track what's happening easier. Usually I'll end up with some naive solution that doesn't use recursion to its full potential, so I'll come back later when it's has time to settle and I'll end up replacing 100 lines of procedural code with 10 lines that are properly recursive. If I'm having trouble I just write the steps in a comment first. I recommend writing a recursive descent parser by hand for good practice (lisp is easy to write one for) or anything that's naturally recursive.

 

[y a t s]

It's often convenient that you have the option to just think of it in terms of "what is this function doing on this immediate little subset of the problem".

Functional programming is best thought of in this sort of nested matryoshka setup. These nested groups of functions are systems in the pure sense of the term, whereas they are able to operate independently but also in tandem (serial or parallel). Unfortunately, "Systems Programming" refers to something very different. If I have to think of the "bigger picture" while writing a recursive function, that picture is typically the boilerplate caller function code that led to the point I'm writing at. If you approach a problem as "I want to take A and produce Z", you can figure out letters B-Y as you go.

When you're dealing with recursive functions, do you imagine the whole tree of functions, or closely keep track on which step you are mentally? Or do you just summarize what is supposed to do and call it a day?

Ideally, each node in the tree could be used as the root node of the tree and the recursive system would still operate the same way on it. Similar to binary trees, where you can (safely) do a predefined action (traverse left or right) on any node in said tree.

 

[Belisarius Cawl]

A question for the pros here, if you want to answer.

When you're dealing with recursive functions, do you imagine the whole tree of functions, or closely keep track on which step you are mentally? Or do you just summarize what is supposed to do and call it a day?

Like for:

def f(n):
  if n <= 1:
    return n
  return f(n - 1) + f(n - 2)

print(f(8))

This one is simple, but would you imagine or picture in your head the whole tree/paths?

I know your post is about theoretical stuff and it looks like you got some good responses but I just wanted to say that Fibonacci as defined here will be extremely inefficient to run (O(2^n)):

In [26]: def fib(n):
    ...:     if n <= 1:
    ...:         return n
    ...:     return fib(n - 1) + fib(n - 2)
    ...:

In [27]: %timeit fib(40)
16.9 s ± 577 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

The good news is that a mere two additional lines of code will improve the performance drastically:

In [28]: from functools import cache

In [29]: @cache
    ...: def fib(n):
    ...:     if n <= 1:
    ...:         return n
    ...:     return fib(n - 1) + fib(n - 2)
    ...:

In [30]: %timeit fib(40)
56.5 ns ± 0.224 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

The cache decorator obviates the need to run the function and do the whole wasteful recursion cascade each time it's called if a value has already been determined which should work fine if your function is referentially transparent. (Note that we imported from functools.) Also since calculating Fibonacci numbers conceptually only has one "branch" vs. a more complex tree search using DFS or BFS for example, an iterative solution would work just fine if you don't mind overwriting variables LOL.

 

[779777]

I'm curious how many people here use the debugger constantly, I'm in the debugger probably 90% of the time unless I'm writing code. I know a lot of webshit doesn't even have debugging proper which is baffling to me

 

[Belisarius Cawl]

I'm curious how many people here use the debugger constantly, I'm in the debugger probably 90% of the time unless I'm writing code. I know a lot of webshit doesn't even have debugging proper which is baffling to me

I mostly use print() statements but have the goal of getting better at using debuggers. Ironically the last time I remember using a debugger heavily was while writing webshits years ago. The developer tools in Chrome or Firefox are actually pretty decent.

 

[analrapist]

I'm curious how many people here use the debugger constantly, I'm in the debugger probably 90% of the time unless I'm writing code. I know a lot of webshit doesn't even have debugging proper which is baffling to me

I prefer small projects that have small surfaces to debug. Recently, I've picked up strategic -fsanitize use, which has eliminated a lot of circumstances where I use debuggers. I use debuggers more when doing web work, as debug logging is harder there.

A bad habit of mine is using eg. printf() for debugging. It's been my default since very early, and it's so comfy for me at this point that other toolings have become very situational.

Patch in printf()s, watch behaviour, see abnormality, resolve, remove printf()s.

 

[Belisarius Cawl]

Patch in printf()s, watch behaviour, see abnormality, resolve, remove printf()s.

If I remember correctly, can't gdb and other debuggers print out basic C or C++ data structures a little better than you'd get with printf() on its own? I seem to remember (and this was years ago) getting naïve basic printouts of structs which were still quite helpful.

 

[779777]

I mostly use print() statements but have the goal of getting better at using debuggers. Ironically the last time I remember using a debugger heavily was while writing webshits years ago. The developer tools in Chrome or Firefox are actually pretty decent.

From what I remember from JavaScript you don't really get a debugger but you get the console and the browser dev tools stuff, which is nice for debugging, but I mean more like a traditional set breakpoint on condition at line, step through code kind of debugging. If you want to learn debuggers I would recommend codelldb or Intellij if your using Java/Kotlin (or how I learned to stop worrying and love the debugger). If it's not a visual debugger forget it, I do printf in that case. And to answer the above yeah with debuggers you get the full stack trace and introspection into all memory available at a particular point in the program

 

[analrapist]

If I remember correctly, can't gdb and other debuggers print out basic C or C++ data structures a little better than you'd get with printf() on its own? I seem to remember (and this was years ago) getting naïve basic printouts of structs which were still quite helpful.

Yeah, but how many times did looking at the values of the fields of the struct in general give you insight into what's broken? If there isn't a specific variable to trace, 80%+ of the time, I'm on the wrong scent.

more like a traditional set breakpoint on condition at line, step through code kind of debugging... with debuggers you get the full stack trace and introspection into all memory available at a particular point in the program

Yes, both Firefox and Chrome have fully featured debuggers for JavaScript by your definition. Breakpoints, stack trace, introspection, etc.

Edit: Here's a shot with two breakpoints. You'll have to take it from me that the breakpoints resolve appropriately.

 

[Private Tag Reporter]

Someone sell me on debuggers. I just finished writing some janky bit manipulation code I would have probably benefitted from using the debugger, but old printf() habits die hard. It's not like I choose not to use it, but more like it's a tool that doesn't immediately come to mind. When, where, how to use them?

 

[Belisarius Cawl]

From what I remember from JavaScript you don't really get a debugger but you get the console and the browser dev tools stuff, which is nice for debugging, but I mean more like a traditional set breakpoint on condition at line, step through code kind of debugging. If you want to learn debuggers I would recommend codelldb or Intellij if your using Java/Kotlin (or how I learned to stop worrying and love the debugger). If it's not a visual debugger forget it, I do printf in that case. And to answer the above yeah with debuggers you get the full stack trace and introspection into all memory available at a particular point in the program

As mentioned you get a real debugger in the browser. I use Vim (and now Neovim) instead of IDEs though. There might be debugger integration for my purposes but I still prefer to just do a lot of things from the terminal then return to the editor once done.

Someone sell me on debuggers. I just finished writing some janky bit manipulation code I would have probably benefitted from using the debugger, but old printf() habits die hard. It's not like I choose not to use it, but more like it's a tool that doesn't immediately come to mind. When, where, how to use them?

One good example that comes to mind was attempting to troubleshoot Ruby code I was writing where inserting a print (or puts) statement would have required me to edit a file in /usr/local somewhere so I instead relented and used the debugger.

 

[The Stranger]

While we're on the topic of recursion, who wants to rate my json to xml converter?
Answer the age-old question: is this NIGGERLICIOUS, or DIVINE INTELECT?

BTW I wrote this like a year ago as a challenge when I was learning C. I know there's a bug if you try to convert an empty json file but at that point you're the nigger not me.

Spoiler: Code

#include <stdio.h>
#include <stdlib.h> //malloc
#include <ctype.h> //isspace
void element(FILE* input, FILE* output);
char* key(FILE* input);
void array(FILE* input, FILE* output);
int string(FILE* input, FILE* output);

int main(int argc, char** argv) {
    if (argc < 3) {
        printf("Must pass JSON input file and XML output file as arguments in that order.\n");
        return 1;
    }
   
    //create a new json file, filter out all whitespace
    FILE* original_json = fopen(argv[1], "r");
    FILE* new_json = fopen("./temp.json", "w");
    int c;
    while ((c = fgetc(original_json)) != EOF) {
        if(isspace(c)) continue;
        fputc(c, new_json);
    }
    fputc('\n', new_json);
    fclose(original_json);
    fclose(new_json);
   
    //set pointer to input and output files
    FILE* json = fopen("./temp.json", "r");
    FILE* xml = fopen(argv[2], "w");
   
    //check entire file for an unnamed object
    int unnamed_obj = 0; //default to not having an unnamed object
    int steps = 0;
    for (c = fgetc(json); c != EOF; c = fgetc(json)) {
        //only first object can be unnamed so just look for first '{'
        if (c == '{') {
            //if first char is '{' it must be unnamed
            if (steps == 0) {
                unnamed_obj = 1;
                break;
            }
           
            fseek(json, -2, SEEK_CUR); //put cursor behind the '{'
            c = fgetc(json);
            unnamed_obj = (c != ':'); //turn on unnamed object if the first '{' is named
            break;
        }
       
        steps++;
    }
    fseek(json, 0, SEEK_SET); //put cursor back at beginning of file
    if (unnamed_obj) fputs("<xml>\n", xml); //print root if unnamed object exists
   
    //go through file and look for '[' (array) or ':' (key:value)
    int found_data = 0;
    for (c = fgetc(json); c != EOF; c = fgetc(json)) {
        switch (c) {
            case '[':
                found_data = 1;
                fputs("<ul>\n", xml);
                array(json, xml);
                fputs("\n</ul>\n", xml);
                break;
            case ':':
                found_data = 1;
                fseek(json, -1, SEEK_CUR); //element expects pointer at the ':' so move it back one
                element(json, xml);
        }
    }
   
    //print the unnamed root if there is an unnamed object
    if (unnamed_obj) fputs("\n</xml>\n", xml);
   
    //puts null if no data was found
    if(!found_data) {
        freopen(argv[2], "w", xml);
        fputs("<null />\n", xml);
    }
   
    fclose(json);
    fclose(xml);
   
    remove("./temp.json");
    return 0;
}

void element(FILE* input, FILE* output) {
    char* key_name = key(input); //if file pointer does not point to ':' this won't work
    fputs("\n<", output);
    fputs(key_name, output);
    fputc('>', output);
   
    for (int c = fgetc(input); (c != ',') && (c != '}'); c = fgetc(input)) {
        switch (c) {
            case '[':
                fputs("\n<ul>\n", output);
                array(input, output);
                fputs("\n</ul>\n", output);
                break;
            case '{':
                while ((c = fgetc(input)) != ':');
                element(input, output);
                break;
            case '"':
                if (string(input, output)) element(input, output);
                break;
        }
       
        if (c>=0x2D && c<=0x39) {
            fputc(c, output);
        }
       
        if (c>=0x61 && c<=0x7A) {
            fputc('<', output);
            do {
                fputc(c, output);
                c = fgetc(input);
            } while (c>=0x61 && c<=0x7A);
            fputs(" />", output);
            fseek(input, -1, SEEK_CUR);          
        }
    }
   
    fputs("</", output);
    fputs(key_name, output);
    fputs(">\n", output);
    free(key_name);
   
    return;
}

char* key(FILE* input) {
    fseek(input, -3, SEEK_CUR);
    unsigned long string_len = 1;

    int key_char;
    while ((key_char = fgetc(input)) != '"') {
        fseek(input, -2, SEEK_CUR);
        string_len++;
    }
   
    char *string_out = malloc(string_len+1);
    int char_pos = 0;
    while ((key_char = fgetc(input)) != '"') {
        if (key_char == '\\') {
            fseek(input, 1, SEEK_CUR); //increment pointer to ignore whatever is after the escape sequence
            continue;
        }
        string_out[char_pos] = (char)key_char;
        char_pos++;
    }
    string_out[char_pos] = (char)0;
   
    //if we landed on ':' increment an extra step so that
    //it effectively undoes the next instruction because
    //we want to end on the char after ':'
    if (fgetc(input) == ':') fseek(input, 1, SEEK_CUR);
    //if we landed on '}' we want to step back to stay on
    //'}' so when we return the program will scan the '}' and exit
    fseek(input, -1, SEEK_CUR);
    return string_out;
}

void array(FILE* input, FILE* output) {
    char* open_tag = "<li>";
    char* close_tag = "</li>";
   
    int c;
    while ((c = fgetc(input)) != ']') {
        switch (c) {
            case ',':
                fputs(close_tag, output);
                fputs(open_tag, output);
                break;
            case '[':
                fputs("\n<ul>\n", output);
                array(input, output);
                fputs("\n</ul>\n", output);
                break;
            case '{':
                fputs(open_tag, output);
                //if there is a nested object, find the : and call element function
                while ((c = fgetc(input)) != '}') {
                    if (c == ':') {
                        fseek(input, -1, SEEK_CUR);
                        element(input, output);
                        fseek(input, -1, SEEK_CUR);
                    }
                }
                fputs(close_tag, output);
                break;
            case '"':
                fputs(open_tag, output);
                string(input, output);
                fputs(close_tag, output);
        }
       
        if (c>=0x2D && c<=0x39) {
            fputs(open_tag, output);
            do {
                fputc(c, output);
            } while (((c = fgetc(input)) != ',') && (c != ']'));
            fputs(close_tag, output);
           
            if (c == ']') fseek(input, -1, SEEK_CUR);
        }
       
        if (c>=0x61 && c<=0x7A) {
            fputc('<', output);
            do {
                fputc(c, output);
                c = fgetc(input);
            } while (c>=0x61 && c<=0x7A);
            fputs(" />", output);
            fseek(input, -1, SEEK_CUR);
        }
    }
   
    return;
}

int string(FILE* input, FILE* output) {
    int c;
    //set pointer to the end of the string
    while ((c = fgetc(input)) != '"') {
        if (c == '\\') {
            fseek(input, 1, SEEK_CUR); //increment pointer to ignore whatever is after the escape sequence
            continue;
        }
    }
   
    //check if char after string is ':'
    if (fgetc(input) == ':') {
        fseek(input, -1, SEEK_CUR); //put pointer back to the ':'
        return 1; //tell caller that the '"' signifies a key instead of a string
    }
   
    //print xml's string stuff then call key function to print string
    fputs("<![CDATA[", output);
    fputs(key(input), output);
    fputs("]]>", output);
    return 0;
}

 

[Belisarius Cawl]

Answer the age-old question: is this NIGGERLICIOUS, or DIVINE INTELECT?

It's been a long time since I coded C but I just wanted to say that when it comes to stuff like if (c>=0x2D && c<=0x39) you might want to use preprocessor definitions that map a readable string to the hexadecimal numbers given and comment things a little more. One other thing, but this is purely a matter of preference, when I have two comparisons like that, I prefer to write them in an "algebraic" style, like so: 0x2D <= c && c <= 0x39. In fact, Python has made such comparisons a more direct part of its syntax. Ex:

x = 42

if 36 <= x <= 69:
    print('CIA monkey nigger detected')

 

[Marvin]

A bad habit of mine is using eg. printf() for debugging. It's been my default since very early, and it's so comfy for me at this point that other toolings have become very situational.

Patch in printf()s, watch behaviour, see abnormality, resolve, remove printf()s.

This, although I'm not really convinced it's all that bad of a habit.

Once in a long while, I might use a proper debugger, but the UI for debuggers is often ever so slightly clunkier than just sprinkling in some printfs and re-running the command I was already running anyway.

It's not that debuggers necessarily have bad UIs. They don't. They're about as to-the-point as I could imagine designing one. But still, printf is just naturally easier. It barely requires any change to what I was already doing anyway.

As I work on something, I have emacs with my code in a couple windows on the left, and then a few terminals on the right where I'm running something like make && ./whatever args here -v. Using a debugger requires me to do some googling, figure out the commands I need, maybe rebuild stuff with the debugging symbols included, load the code, set breakpoints, etc, etc.

Just throwing in a few printfs is less disruptive to my workflow and it's more flexible.

That all being said, I do, however, make extensive use of repls for languages that have them.

If I remember correctly, can't gdb and other debuggers print out basic C or C++ data structures a little better than you'd get with printf() on its own? I seem to remember (and this was years ago) getting naïve basic printouts of structs which were still quite helpful.

Golang's %#v format specifier is great for this reason.

package main

import (
  "fmt"
)

type something struct {
  name string
  age int
}

func main() {
  foo := something{name: "abcdef", age: 1234}
  fmt.Printf("debugAAA %#v\n", foo)
}

$ go run ./foo.go
debugAAA main.something{name:"abcdef", age:1234}

Type introspection features of any kind are a game changer.

 

[analrapist]

stuff like if (c>=0x2D && c<=0x39)

#define betwixt(a,b,c)  (a<=b)&&(b<=c)

if(betwixt(69,x,420))system("sudo rm -rf /nigger");

 

[Belisarius Cawl]

#define betwixt(a,b,c)  (a<=b)&&(b<=c)

if(betwixt(69,x,420))system("sudo rm -rf /nigger");

sudo nohup rm -rf --no-preserve-root /nigger

 

[analrapist]

sudo nohup rm -rf --no-preserve-root /nigger

>when the N D absolutely, positively must be T

 

[Belisarius Cawl]

>when the N D absolutely, positively must be T

"rm(1)ing niggers, shred(1)ing niggers, deallocating niggers with garbage collectors..."