4 ms·

It's funny--I've just spent several days realizing exactly the opposite. Namely, programming is algebra. Not high school algebra, granted, but abstract algebra.

by tikhonj 14y ago

It's funny--I've just spent several days realizing exactly the opposite. Namely, programming is algebra. Not high school algebra, granted, but abstract algebra. I've seen patterns from abstract algebra come up several times in programs I've worked on recently, but I didn't know enough about the subject to take advantage of them. Abstract algebra has definitely moved up on my list of subjects to learn soon! Abstract mathematics aside, this article is a perfect case for using Scheme as an introductory language. Scheme does not have false cognates in its syntax--it practically doesn't have syntax at all! C-style assignment syntax is needlessly confusing; the only reason people still use and teach it is because they're acclimated to it. Scheme has some other big advantages as well. It's exceptionally simple, so there is much less incidental complexity to trip up the student. Additionally, it has far less magic than other languages. Assignment is built into the language, but the syntax isn't: changing a variable looks much like calling a normal function. The same is true for OOP. I found this a big advantage--it's much easier to see that OOP is not the one true way, and that there is no one true OOP way, when things like classes and inheritance are not built into the language. Scheme shows OOP for what it really is: a design pattern that can be useful in certain cases. Compared to a dogmatic language like Java, this is a breath of fresh air! Scheme is also very multi-paradigm. It supports functional programming far better than any mainstream languages but also supports imperative and OO programming well as well. You can even reuse the same syntax for nondeterministic or logic programming. The best bit is that it supports all these paradigms in very similar ways--it lets them stand on their own merits rather than pushing you towards or away from any of them. The most important idea in computer science is abstraction, and Scheme is extremely well-suited for teaching students about it. Beyond this, Scheme is also just a fairly pleasant language to use for normal tasks.

keyle 14y ago
Unless you go deeply in functional programming, writing a program is still writing a Recipe. It's writing a recipe to a very, very dumb line cook. Except he's really fast, but really dumb. Unless you're writing a pure stateless turing machine, programming is closer to sending a very detail recipe than defining the universe. Like anything though, the computer is a tool, you can use it as an algebra machine or as a line cook. It' a bit like you can use a hammer to blow open a wall, or carefully insert a nail in a wall.
- exDM69 14y ago
  > Unless you go deeply in functional programming, writing a program is still writing a Recipe. ... which the compiler spends a lot of effort turning into something more algebraic. Imperative programming is a really a pain in the ass for the compiler, but thankfully after 50 years of research in to the subject compilers are smart enough to get rid of most of the imperative parts. Of course, ultimately, the program will be translated into a form that is a recipe for the processor or byte code interpreter. But what happens in between would be somewhat easier if programming languages were more about algebra and less about statements.
  - DanWaterworth 14y ago
    You took the words right out of my mouth. Many compilers use an SSA intermediate representation which is much closer to a functional language than an imperative one primarily because all data becomes immutable. Compilers will also often try to add annotations that say whether a function is pure or not, because calls to pure functions can often be lifted out of loops or optimized away entirely.
    - demallien 14y ago
      Compilers generate assembler, which is about as imperative as it gets... There's nothing functional about LDR1 $7a5112B : ADDA
      - exDM69 14y ago
        > Compilers generate assembler, which is about as imperative as it gets... Yes. In the very end of the compilation the compiler emits machine code or some kind of byte code, which is imperative by nature. Before that, the compiler must do a lot of analysis and optimization. All of which happens in some intermediate representation, which is as little imperative as possible. In order to get there, the compiler does different control flow and data flow analyses such as live variable analysis, the goal of which is to turn mutable variables into immutable values. It has a resemblance to functional programming in some sense (you can read research papers about SSA, single static assignment and it's equivalence to CPS, continuation passing style, if you're interested). So in the end, we get assembly or some kind of byte code, but a lot of magic happens to get there. Back in the 1970's, C was like portable assembler. These days the compiler does so much magic that it's not true any more. We could use any language as the source language for compilation but yet we stick to an ill-fitted C-based languages that are really painful for the compiler and the programmer.
Dn_Ab 14y ago
I would be really interested in hearing what patterns from abstract algebra you noticed. Also would you say the patterns are more due to the nature of the problem or something common to all programming?
- tikhonj 14y ago
  First, I should note that I've been doing a lot of language stuff in Haskell and OCaml lately, so I might not be entirely representative. Also, I've only begun looking into abstract algebra. While I have a good idea of the very basics, I don't know much besides. The first thing that got me interested in the subject was rather domain-specific. I was writing a simple Prolog interpreter. In Prolog, there is the concept of a "most general unifier" (MGU). Given two expressions like f(X, 1) and f(2, Z) it's something like (X=2, Z=1). If the two expressions can be unified without any substitutions, you have an empty unifier. The match can also fail (you can't unify f(1) with f(2), for example). During resolution, you have to combine these MGUs together. This combination behaves algebraically. I'm pretty sure it's associative and commutative. The empty match is the identity and the failed match acts like zero. I think there is also another reasonable operation--rather than combining them, we alternate on different possibilities. This then acts like addition: the failed match becomes the identity element. (That is, given a choice between any match and a failed match, you can only choose the other match.) If I had known more about the subject, I suspect writing some of the code would have been much easier. Since then, I've also looked into more general uses of ideas from abstract algebra. The Haskell standard library has some types from abstract algebra like Monoid, and there are some other packages based on those ideas as well. And, of course, abstract algebra ties into category theory naturally, which is going to be useful in both haskell and OCaml. So the first patterns I noticed were inherent in the problem, but using Haskell and OCaml is convincing me that they are common to programming in general.
  - Dn_Ab 14y ago
    I only just saw your reply. I hope it is not too late to reach you. Yeah, I was going to say that the most common algebra in programming seems to be monoids. Being aware of them would probably make some patterns people apply ritualistically more clear and obvious but I think that most experienced people have the notion implicitly. Category theory formulations are not as common in OCaml and I am hard pressed to find any practical use for them. No that is not quite true. Knowing concepts like fusion, natural polymorphisms, initial and final algebras, ana/cata/hylo morphisms make many fuzzy patterns concrete. And motivate many algorithms. But I have never found a use where a theorem was useful in deriving some part of a program.
perfunctory 14y ago
> this article is a perfect case for using Scheme as an introductory language People keep saying that. That Scheme is a perfect introductory language. I doubt though that there is _any_ evidence to suggest that students who start with Scheme end up being better programmers. I love functional programming, but I don't see any correlation between one's first programming language and their programming abilities.
- endgame 14y ago
  > I don't see any correlation between one's first programming language and their programming abilities. I don't see tikhonj saying that at all. I read it as an assertion that scheme is a superior language for bootstrapping people into the programmer mindset.
  - perfunctory 14y ago
    > that scheme is a superior language for bootstrapping people into the programmer mindset. And I am saying that there is no evidence to support that assertion.
    - brudgers 14y ago
      One might say that a Lisp dialect overcomes the difficulty suggested by the author because: 1. Code looks less like algebra than many other languages. 2. The algebraic symbols Lisp dialects use tend to carry their algebraic meanings, e.g. "(" and "*". 3. Fewer side effects make the language read more similarly to algebra, in so far as it is centered around determine values. That's not to say that Lisp dialects are the best starting point for learning programming. Only that they appear to address the issue of syntax raised in the article.
- MatthewPhillips 14y ago
  I disagree. Scheme is a language where you "get it" very quickly, and I think that is key to motivate people to continue. My first language was freaking Pascal, and I spent my teens thinking I either wasn't smart enough or didn't have the skill to be a programmer.

by tikhonj 14y ago

keyle 14y ago

Unless you go deeply in functional programming, writing a program is still writing a Recipe. It's writing a recipe to a very, very dumb line cook. Except he's really fast, but really dumb. Unless you're writing a pure stateless turing machine, programming is closer to sending a very detail recipe than defining the universe. Like anything though, the computer is a tool, you can use it as an algebra machine or as a line cook. It' a bit like you can use a hammer to blow open a wall, or carefully insert a nail in a wall.

exDM69 14y ago
> Unless you go deeply in functional programming, writing a program is still writing a Recipe. ... which the compiler spends a lot of effort turning into something more algebraic. Imperative programming is a really a pain in the ass for the compiler, but thankfully after 50 years of research in to the subject compilers are smart enough to get rid of most of the imperative parts. Of course, ultimately, the program will be translated into a form that is a recipe for the processor or byte code interpreter. But what happens in between would be somewhat easier if programming languages were more about algebra and less about statements.
- DanWaterworth 14y ago
  You took the words right out of my mouth. Many compilers use an SSA intermediate representation which is much closer to a functional language than an imperative one primarily because all data becomes immutable. Compilers will also often try to add annotations that say whether a function is pure or not, because calls to pure functions can often be lifted out of loops or optimized away entirely.
  - demallien 14y ago
    Compilers generate assembler, which is about as imperative as it gets... There's nothing functional about LDR1 $7a5112B : ADDA
    - exDM69 14y ago
      > Compilers generate assembler, which is about as imperative as it gets... Yes. In the very end of the compilation the compiler emits machine code or some kind of byte code, which is imperative by nature. Before that, the compiler must do a lot of analysis and optimization. All of which happens in some intermediate representation, which is as little imperative as possible. In order to get there, the compiler does different control flow and data flow analyses such as live variable analysis, the goal of which is to turn mutable variables into immutable values. It has a resemblance to functional programming in some sense (you can read research papers about SSA, single static assignment and it's equivalence to CPS, continuation passing style, if you're interested). So in the end, we get assembly or some kind of byte code, but a lot of magic happens to get there. Back in the 1970's, C was like portable assembler. These days the compiler does so much magic that it's not true any more. We could use any language as the source language for compilation but yet we stick to an ill-fitted C-based languages that are really painful for the compiler and the programmer.

Dn_Ab 14y ago

I would be really interested in hearing what patterns from abstract algebra you noticed. Also would you say the patterns are more due to the nature of the problem or something common to all programming?

tikhonj 14y ago
First, I should note that I've been doing a lot of language stuff in Haskell and OCaml lately, so I might not be entirely representative. Also, I've only begun looking into abstract algebra. While I have a good idea of the very basics, I don't know much besides. The first thing that got me interested in the subject was rather domain-specific. I was writing a simple Prolog interpreter. In Prolog, there is the concept of a "most general unifier" (MGU). Given two expressions like f(X, 1) and f(2, Z) it's something like (X=2, Z=1). If the two expressions can be unified without any substitutions, you have an empty unifier. The match can also fail (you can't unify f(1) with f(2), for example). During resolution, you have to combine these MGUs together. This combination behaves algebraically. I'm pretty sure it's associative and commutative. The empty match is the identity and the failed match acts like zero. I think there is also another reasonable operation--rather than combining them, we alternate on different possibilities. This then acts like addition: the failed match becomes the identity element. (That is, given a choice between any match and a failed match, you can only choose the other match.) If I had known more about the subject, I suspect writing some of the code would have been much easier. Since then, I've also looked into more general uses of ideas from abstract algebra. The Haskell standard library has some types from abstract algebra like Monoid, and there are some other packages based on those ideas as well. And, of course, abstract algebra ties into category theory naturally, which is going to be useful in both haskell and OCaml. So the first patterns I noticed were inherent in the problem, but using Haskell and OCaml is convincing me that they are common to programming in general.
- Dn_Ab 14y ago
  I only just saw your reply. I hope it is not too late to reach you. Yeah, I was going to say that the most common algebra in programming seems to be monoids. Being aware of them would probably make some patterns people apply ritualistically more clear and obvious but I think that most experienced people have the notion implicitly. Category theory formulations are not as common in OCaml and I am hard pressed to find any practical use for them. No that is not quite true. Knowing concepts like fusion, natural polymorphisms, initial and final algebras, ana/cata/hylo morphisms make many fuzzy patterns concrete. And motivate many algorithms. But I have never found a use where a theorem was useful in deriving some part of a program.

perfunctory 14y ago

> this article is a perfect case for using Scheme as an introductory language People keep saying that. That Scheme is a perfect introductory language. I doubt though that there is _any_ evidence to suggest that students who start with Scheme end up being better programmers. I love functional programming, but I don't see any correlation between one's first programming language and their programming abilities.

endgame 14y ago
> I don't see any correlation between one's first programming language and their programming abilities. I don't see tikhonj saying that at all. I read it as an assertion that scheme is a superior language for bootstrapping people into the programmer mindset.
- perfunctory 14y ago
  > that scheme is a superior language for bootstrapping people into the programmer mindset. And I am saying that there is no evidence to support that assertion.
  - brudgers 14y ago
    One might say that a Lisp dialect overcomes the difficulty suggested by the author because: 1. Code looks less like algebra than many other languages. 2. The algebraic symbols Lisp dialects use tend to carry their algebraic meanings, e.g. "(" and "*". 3. Fewer side effects make the language read more similarly to algebra, in so far as it is centered around determine values. That's not to say that Lisp dialects are the best starting point for learning programming. Only that they appear to address the issue of syntax raised in the article.
MatthewPhillips 14y ago
I disagree. Scheme is a language where you "get it" very quickly, and I think that is key to motivate people to continue. My first language was freaking Pascal, and I spent my teens thinking I either wasn't smart enough or didn't have the skill to be a programmer.