Corbin @ Corbin @programming.dev

Posts

2

Comments

91

Joined

2 yr. ago

If it's on Stack Exchange, you can help us keep the community decent by assuming good faith and being patient with newcomers. Yes, it's frustrating. And yeah, sometimes, it's basically impossible to avoid sarcasm and scorn, just like how HN sometimes needs to be sneered at, but we can still strive for a maximum of civility.

If all else fails, just remember: you're not on Philosophy SE or any of the religious communities, it's just a computer question, and it can be answered without devolving into an opinion war. Pat yourself on the back for being a "schmott guy!" and write a polite answer that hopefully the newbies will grok. Be respectful of plural perspectives; it's a feature that a question may have multiple well-liked answers.

Yeah, this list of sites is making me think of asking for a book by loudly asking a library, a series of coffeeshops, a chud microbrewery, and an 11-year-old bully. Try quietly reading in the library first, I guess.

There are Python compilers which do AST analysis instead of bytecode analysis, particularly Nuitka and Shed Skin. They aren't very good, but it's not clear whether that's because working with the AST is somehow harder than working with the bytecode. RPython doesn't compile all bytecodes; most generator/coroutine functionality is missing, for example.

Think of type-checking as a syntactic analysis; this is how it avoids Rice's theorem. Like you say, we can annotate names with type information, and we can do it without evaluating the code. The main problem here is that Python's semantics don't require these annotations to enforce the types of values; you may be interested in E, a research language from the 90s which did enforce type annotations on otherwise-untyped names. In Python, this doesn't error:

        >>> x :int = "42"


  

But in E, this does error:

        ? def x :int := "42"
    # problem: <ClassCastException: String doesn't coerce to an int>


  

Sadly, E is long dead, and something of an archeological artifact rather than a usable system. But it may be inspiring to your future efforts, especially since it sounds like you're learning how to build compilers. (I helped write Monte, a language which blends E and Python; it is also dead, but was more enjoyable than E.)

I've only skimmed the paper, so let me know if I've missed something, ideally with a page number. Also, it's late and I'm tired, so I'm not hyperlinking anything; sorry.

I'm not sure what a "full semantic analysis" entails, but always keep Rice's theorem in mind: there aren't any interesting semantic analyses available for Turing-complete systems.

Python is a descendant of Smalltalk. Like several of its cousins, particularly the famous ECMAScript, Python doesn't have types or classes in the Smalltalk sense, but prototypes which form a class-like hierarchy. From the static-analysis point of view, whether a type is created or instantiated is a matter of Rice's theorem.

The ability to invoke type() at runtime is not lazy. Python is eager and strict; even generators are eager and strict, although they can cause stack frames to become "stale"; whether a stale stack frame is cleaned up is also a matter of Rice's theorem.

None of this prevents compilation of Python. The RPython toolchain first imports an application, evaluating all calls to type() and pre-building all classes; then, it statically analyzes all of the Python objects in memory and decompiles their bytecode to determine their behaviors. The resulting executable behaves as if it were started from a snapshot of the Python heap.

Yes, CPython sucks. Use PyPy instead; also, use cffi to wrap C libraries.

I use Nix. Or, rather, I use traditional tools like sed and awk and python, along with newer tools like jq so that I can store tables in JSON, and I call those tools from Nix builders. For example, this flake builds a book in several stages, starting by generating DOT from diagrams, then feeding some JSON tables via jq into Python scripts (replacing older awk scripts) to generate some Markdown tables and Metamath axioms, and finally calling mdbook and metamath to build the HTML for the book.

It's because most of the hard questions and theorems can be phrased over the Booleans. Lawvere's fixed-point theorem, which has Turing's theorem and Rice's theorem as special cases (see also Yanofsky 2003), applies to Boolean values just as well as to natural numbers.

That said, you're right to feel like there should be more explanation. Far too many parser papers are written with only recognition in mind, and the actual execution of parsing rules can be a serious engineering challenge. It would be nice if parser formalisms were described in terms of AST constructors and not mere verifiers.

It would be incorrect, but only because you've learned from vague teaching materials. You're on the right track; let's just be a bit more precise about terminology.

An algorithm is a sequence of numbered steps, where some steps make decisions and some steps point towards other steps. Equivalently (thanks to the structured-programming theorem) an algorithm is a flowchart with decision nodes. Machines typically evaluate algorithms directly; the numbered steps can be mapped to sequences of machine instructions. Machine states arise from considering how a particular algorithm behaves on a given machine.

A specification is a pair of claims, often called the precondition and postcondition, which logically connect the inputs and outputs of a machine. The idea is that, if we fulfill the precondition prior to running the machine, then the outputs of the machine will fulfill the postcondition. The study of specifications is often called "formal methods", a terrible name for a great idea.

The connection is hopefully straightforward to see: an algorithm might happen to fulfill a specification. In general, there are often multiple algorithms for a given specification; for example, there's usually an infinite number of ways to add a do-nothing instruction to an algorithm without changing any of its behaviors. A classic example is sorting; there are many sorting algorithms, all of which fulfill the postcondition that the output list is sorted, usually with the precondition that the input list contains sortable/orderable elements.

Define your terms before relying on platitudes. Mutability isn't cleaner if we want composition, particularly in the face of concurrency. Being idiomatic isn't good or bad, but patterned; not all patterns are universally desirable. The only one which stands up to scrutiny is efficiency, which leads to the cult of performance-at-all-costs if one is not thoughtful.

You are very close to a deep truth of language design: all large popular languages slowly die from committees overloading them with cruft and redundant features, and at the end of their healthspans, they become painful for all involved. In your list, this includes both PHP and ECMAScript; Perl 5 avoided this fate, but Raku certainly suffers from it.

You are correct. For the example of regular languages, we have Kleene algebras, which are special cases of *-semirings. Similar algebras exist for the rest of the Chomsky hierarchy.

Before going up the hierarchy, I would recommend checking out what we can do with semirings alone. Two great papers on the topic are "Fun with Semirings", Dolan 2013 and "A Very General Method of Computing Shortest Paths", O'Connor 2011. Don't be fooled by the titles; they both involve surprise guest appearances from regular expressions.

Thanks for offering your perspective! It's important that we keep in mind that not everybody who studies computer science becomes a professional programmer, and you've offered us good food for thought.

For what it's worth, pointers are fundamental for Von Neumann machines, which are very common in the computing world; your current machine and the machine serving this page are both Von Neumann. In such machines, memory doesn't just store data, but also instructions; the machine has an instruction pointer, which is a pointer referencing the currently-executing instruction in memory. So, if one wants to understand how a computer jumps from one instruction to another, then one must somewhat understand pointers.

Yeah, some folks have trouble with pointers, and computer-engineering curricula are designed to discourage folks from taking third-year courses if pointers don't make sense. It's a stereotype for a reason. I'd love to know if there's an underlying psychological explanation, or if pointers are just...hard.

Learn finance and bookkeeping; work for a bank. Software development is not lucrative; the high-paying jobs are fundamentally tough and cause burnout. Median employment at big software companies is maybe 2-3yrs and it will ruin your ability to relate to other humans.

It sounds like you understand what's wrong with your opinion and yet can't bring yourself to improve as a person.

But you do sometimes get asked to do "unethical" things, and you're "proud of what [you] do" even though "sometimes … [you] just have to do as [you're] told." Why? It sounds like you've chosen a compromised position "to get money."

I directly tell my managers that what they are asking for is illegal, and then I refuse to do it. So far, I've yet to be forced to "do as I'm told," and I doubt that this will ever be a problem for me as I don't intend to sign up for the military or any other organization that can actually force people to follow orders.

Lucky 10000: It's a pun. A quaver is a duration of a musical note in the UK, equivalent to a USA eighth note; a semidemihemiquaver is a sixtyfourth note, used to notate e.g. certain kinds of trumpet trills.

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

Free Software is literally communist.

Nailed it. I think about this a lot: a sysadmin is basically a manager of dozens, hundreds, or even thousands of computers. But management is a poor way of orchestrating human labor; small teams usually operate better without management. So, is there a better way to administer computer systems as well?