juan_gandhi | Entries tagged with programming

"From Mathematics to Generic Programming"

I had ordered this book a couple of years ago, but by my mistake it was delivered to my old Californian address. Just received it eventually, about a month ago.

The book has 14 chapters. I don't know who is Daniel Rose, but everybody (except GenZ) knows Stepanov, who is, I think, an actual founder of map/reduce (but who cares, right?). He has an education in "abstract algebra", as I understand (S.Lang's "Algebra" book is what I see throughout this book), and, since he spent his life programming every since, he didn't add any knowledge above, and the book mixes his "Mekhmat Algebra of year 1972" level with programming practices of 1990-s.

I remember I was doing a similar algebra, but in my case category theory was already looming somewhere above, and, many years later, I figured that all that cheap shit that I was doing in homological algebra can be expressed in about a couple of pages if we show that a couple of important functors are adjoint. Same here: "similarities", mentioned here and there throughout the book are just functors between some abelian categories. OTOH, model theory was almost mentioned.

Still, a good reading, really good, especially for kids.

Also, the book contains a lot of stories from the history: How Euclides got pissed off by his contemporary idiots, how Lobachevsky got pissed off by his contemporary idiots, how Galois pissed of some idiots like Cauchy and eventually he got pissed off and killed by some now forgotten asshole.

We start with finding GCD, and we spend the whole book returning to finding GCD, eventually wrapping up with the explanation of how RSA works. GCD everywhere. Since there are c++ code examples and exercises, a lot of time is dedicated to explaining how code works, and how it should be written. The general approach reminds me what they taught us in the 5th year: performance! efficiency! minimalistic code with no extra instruction! Ok, we need that efficiency for doing RSA, of course, especially finding a couple of good primes. And all these things are good exercises if you are learning, or just want to have fun.

So, I recommend this book as a casual weekend or vacation reading to programmers that for some reason skipped algebra - and also as a good algebraic programming tutorial to the kids who are curious to learn something mathematically deeper than Java OOP or Scala FP.

Defining pred function in Church-encoded numbers in lambda:

  const _0 = f => x => x                   // zero, Church-encoded
  const succ = n => f => x =>f(n(f)(x))    // successor operation
  const p1 = x => y => x                   // first projection
  const p2 = x =>y => y                    // second projection
  const pair = x => y => f => f(x)(y)      // 'pair' function
  const p_0_0 = pair(_0)(_0)               // (0, 0)

  const pred = n => n(p => f => f(p(p2))(succ(p(p2))))(p_0_0)(p1)

You can try it with


  const _1 = succ(_0)              // number 1
  const _2 = succ(succ(_0))        // number 2
  const _3 = succ(succ(succ(_0)))  // number 3

  function print(n) {                   // show number 'n'
    const dot = s => "\\u25CF" + s      // as dots in square brackets
    console.log("[" + n(dot)("") + "]")
  }

  print(_2)         // we will see two dots
  print(_3)         // we will see three dots
  print(pred(_0))   // we will see no dots
  print(pred(_3))   // we will see two dots

It will produce

[●●]
[●●●]
[]
[●●]

Вот какая задачка и какое решение.

Dana S. Scott, A Timeline for Logic, λ-Calculus, and Programming Language Theory

So, if you think you call a function in your code, and this function returns current time, or a random number... IT'S NOT A FUNCTION. Your code is function of "random number", or "time".

So, if your code is written as something that retrieves this kind of data, to test your code, you should provide that data. Not just today, but try the time, like 10 years from now. As to "random", You provide the randomness. If your code cannot be fixed to behave as a function of those inputs, make your "random stream" or "time stream" not hard-coded, but substitutable. Mockable. And mock it in your tests. MAKE SURE that you don't provide just happy-path data. Provide anything. A sequence of 100 numbers 4 for random. Time that is 10 years from now. Or even 30 yeas from now.

Make sure that your tests don't depend on anything. Because test Must Be Reproducible.

All these things, I know, are obvious to some, and not obvious to others.

If you still have questions, ask. But don't argue. Because what I say is math. Unless you have another math (some people do), or another logic (there's plenty of them), please don't argue.

I'd be glad to see how all this changes if logic is e.g. linear.

https://github.com/izhangzhihao/intellij-rainbow-brackets

> rustc -version
error: Unrecognized option: 'e'

Reminds me what we did in Forth, with Leo, present here:

      applyTo | "a" | "b"  | "c" | "d"  | "e" |
      at("a") | "a" | "ab" | ""  | ""   | ""  |
      at("b") | ""  | "b"  | ""  | ""   | ""  |
      at("c") | ""  | "cb" | "c" | "cd" | ""  |
      at("d") | ""  | ""   | ""  | "d"  | ""  |
      at("e") | ""  | ""   | ""  | "ed" | "e"

This is a test case. Rather, 25 test cases.
We scan through at("a") to at("e"), where at(x) is a representable diagram (presheaf, functor, whatever) for object x:

      val at = (obj: topos.site.Obj) => topos.representable(obj)

and then, in each row, apply this representable to objects "a",..., "e", and check that the result is a set (hom(x, y)) consisting of the values in the cells of the table. The values in the table are split by comma and converted to sets - because we deal with Grothendieck toposes.

But toposes are not essential here. I just decided to be lazy, and write code as tables, as Leo suggested eons ago, probably in 1989. It's not even my idea.

Implementation:

      val at = (obj: topos.site.Obj) => topos.representable(obj)
      
      case class table(data: List[String] = Nil) {
        def |(x: String): table = table(x::data)
        def |(d: Diagrams.Diagram) = check(d, data, data)
      }

      case class check(d: Diagram, data: List[String], fullList: List[String]) {
        def |(x: String): check = {
            d(data.head) === x.split(",").toSet
            check(d, data.tail, fullList)
        }
        def |(d: Diagram): check = check(d, fullList, fullList)
      }

      val applyTo = new table

http://tinyurl.com/cleanercode

www.cs.cmu.edu/~rwh/pfpl/

A new book, I guess

I think I got it where all this bs about passing around numerical ids of entities instead of entity references (maybe lazy) come from. It's like 'error code'. It comes from the ancient c programming, where we just could not allocate a string for a readable piece of text, or for the data that may need some efforts to instantiate or allocate.

In short. It's stupid to pass around "ids" in a program.

Find the type error in the following Haskell expression:

if null xs then tail xs else xs

If your constructor has a boolean parameter, you actually have two different types.

http://www.programmingusingscala.net/home/chapters

I loved it.

http://michaelochurch.wordpress.com/2012/04/13/java-shop-politics/

http://qandwhat.apps.runkite.com/i-failed-a-twitter-interview/ (10x

polycode)

Take a look.

I ~~think~~ thought it is not fair to ask this kind of questions from programmers that do not have an education in geometry. It's not a programming problem, it's just geometry.

~~Get a convex hull, split into chunks by the top vertices; find largest area.~~ - BULLSHIT! does not work.

E.g. print $ solve [4,3,0,0,0,0,0,0,1]

But if a candidate is not familiar (or too familiar, like me) with all this crap, they'll go with a bunch of stupid "solutions", especially stressing "optimal" ones.

Makes ZERO sense to me. It is a bad interview question.

is not with algorithms; there's hardly any algorithm that is hard to implement, once it's clearly formulated.
And it is probably not even performance, since it is another algorithm issue.

It is our struggle with monads. With monads that don't commute.

That's what makes Haskell so good (and so hard): it makes us to mention monads explicitly.

  def bytes(is: InputStream) : Iterator[Byte] = new Iterator[Byte] {
    def hasNext = is.available > 0
    def next = is.read.toByte

  def isText(b: Byte) = b == 0x0a || b == 0x0d || b >= 32 && b < 0xff

  def chars(is: InputStream) = bytes(is) filter isText map (_.toChar)

So that I can use it like this:

  def main(args: Array[String]) {
    val is = new FileInputStream(args(0))
    for (c <- chars(is)) print(c)
  }

(that's monadic, kind of)

It's a known puzzle from the depths of object-oriented teaching: is Circle a subclass or Ellipse. From school we know it is; but as we read in books, for programmers, it is not. How come? Oh, "Liskov principle". They use Liskov principle to scare kids.

Actually we know that a circle is an ellipse with both axes being the same length.

But in programming, an ellipse is something different. It is at least stretchable. And it is also moveable. Somehow it is not rotatable, but we can skip it for simplicity.

An ellipse in programming is (almost) always horizontal; it can be moved (by changing coordinates of its center) and it can be stretched/compressed by changing its height and width. Sure a stretchable ellipse is neither an ellipse nor a circle, not even a stretchable circle. A stretchable circle stretches equally in all directions.

That's it, no? Questions? Objections?

here
slides only

Profile

Juan-Carlos Gandhi

patryshev.com

June 2025

S	M	T	W	T	F	S
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

Syndicate

Page Summary

Active Entries

Style Credit

Style: Neutral Good for Practicality by timeasmymeasure

Expand Cut Tags

No cut tags

Page generated Jun. 26th, 2025 07:05 am

Observations

Views from Souths

Entries tagged with programming

Stepanov, Rose

всякая примитивная лямбда

программисты, гляньте-ка

logic timeline

TWIMC: tests using random and current time

brackets plugin for intellij (etc) for probably all languages

secure programming

the kind of programming

slapped together some stuff regarding cleaner code

"Practical Foundations for Programming Languages"

long id

problems with ifs and with imperative programming and with typeless code

one-liner

videobook, "Introduction to the Art of Programming Using Scala"

amazingly good reading: Java Shop Politics

here's an interview problem

the biggest trouble in writing code...

the simple thing I missed in Scala

inheritance: is circle an ellipse?

Josh Bloch, Effective Api Design