Hi all, Coq is a "proof assistant" that allows you to write both code and proofs in the same language (thanks to the Curry–Howard correspondence). Its uses range from pure math (e.g., the Feit–Thompson theorem was proven in Coq!) to reasoning about programming languages (e.g., proving the soundness of a type system) to writing verified code (e.g., this verified C compiler!). You can "extract" your code (without the proofs) to OCaml/Haskell/Scheme for running it in production. Coq is awesome, but it's known for having a steep learning curve (it's based on type theory, which is a foundational system of mathematics). It took me several years to
stepstep
u/stepstep
Hi folks, this might be of interest to anyone who is designing a language with dependent types. I stumbled upon this question from a couple years ago about Girard's paradox. If you haven't heard of Girard's paradox, it's the reason you don't want Type : Type if you want your language to be consistent for writing proofs. Note that Type : Type doesn't break soundness (i.e., type safety), which means it's fine if you don't care about proofs. It just means you can construct a non-normalizing term (i.e., an infinite loop), which most languages will happily let you do anyway regardless of
This is just a small PSA for an inconsequential issue. I often see people here saying "the semantics are..." when they mean "the semantics is...". I used to make this mistake back in grad school until my PI corrected me. An example of correct usage might be: "The semantics of the language is given by the small-step rules in Figure 1." As an umbrella term for the academic discipline, "semantics" is also usually singular (like "physics").
Occasionally, you may actually need the plural form, which is also "semantics". In that case, "semantics are" is correct. Example: "The denotational semantics of non-strict languages are typically based on domain theory." But note that the plural form is onl
I'm curious what everyone thinks about this. Programming languages generally have a way to import code from another file/module. Some languages have some kind of abstract namespacing scheme that maps to a location in the file system (e.g., Java), whereas other languages allow you to provide a literal path to the file/module (e.g., JavaScript), though sometimes the file extension is omitted. Languages in the former category typically require fully qualified namespaces, whereas languages in the latter category typically allow for relative paths. And of course some languages deviate from this and/or implement some kind of hybrid system.
Another consideration is that some languages don't have a
I don't want to sound unappreciative, but I believe this sub is a disappointment for computer science enthusiasts and researchers. There's a lot of spam about cloud computing, devops, various libraries and frameworks, etc. by users like u/Techbiason, u/itbloggy, and others. Can we ban them? There is also a high volume of posts about programming or software engineering topics that are largely irrelevant to computer science. What's up with the low signal-to-noise in this sub? Are the mods stretched too thin?
Obviously people can have differing opinions on what constitutes "computer science", but I wouldn't include things like "[Review[ing] client's brand standards](https://www.reddit.com/r/
Program Logics for Certified Compilers (this textbook is now free)
cs.princeton.edu/~appel/papers/plcc.pdfI somewhat fall into the stereotypical Haskell/Coq/Agda/Idris-loving, category theory embracing, type theory enthusiast, functional programmer camp that many programmers love to make fun of (if they even know of our existence). I view programming as a craft, and I'm always eager to lean more about (and teach!) how to build better software. But I also write Java code at a big tech company because, unfortunately, it seems to pay the bills better than more mathematically-inspired programming methodology. Given the opening sentence of this post, it may come as no surprise that I care about different aspects of programming languages than most programmers, for example:
- Parametricity
- Soundness
I need to learn enough Haskell to implement Yoneda's lemma in a couple days
reddit.com/r/haskell/comments/g6y7vg/decent_c...Upcoming virtual meetup: Ghost Hunting the Perfect API (with departed proofs)
meetup.com/Bay-Area-Haskell-Users-Group/event...Who here has experience with de Bruijn indices? I'm using them in my compiler project, but they're a huge pain:
- They're hard to read (when debugging)
- They're hard to get right (it's easy to have off-by-one errors, out-of-bounds errors, etc.)
- Most of the compilers and PLT literature uses explicit names
On the positive side:
- They make alpha equivalence trivial (useful for languages with type-level abstractions), and there is no need to invent fresh variables to avoid variable capture problems during substitution
- When they are implemented incorrectly, they tend to fail catastrophically (as opposed to explicit names, which tend to fail in more subtle and hard-to-detect ways)
- They
Hi folks, I'm working on a small dependently-typed programming language with Type : Type. Of course this system is inconsistent as a logic, but it's sound as a type system for programming, and the goal of this language is not theorem proving.
As a stress test of the type checker, I am trying to type check Girard's paradox. I'm using the version of the paradox given in section 3 of the paper A Simplification of Girard's Paradox. The goal is to construct a well-typed program that loops forever without any fixpoint operators or recursive types (e.g., no Y combinator). This is my attempt at translating that rather insidious term into code (
Hey folks, this might be a little niche, but in case it's helpful: I wrote a small program called Docuum (like "Docker" + "Vacuum") that cleans up old Docker images to prevent your hard disk from filling up. I run it on any machine that builds Docker images, such as continuous integration (CI) workers or my laptop. You tell it the maximum amount of space you want to use for storing Docker images (e.g., 10 GB), and it it deletes images as needed to fit in that space.
You might wonder what the point of Docuum is, since Docker has a built-in command for cleaning up old images: docker image prune --filter until=…. The key difference is in how they deci