Hacker News Reader

Comment by dr0wsy | Hacker News Reader

How do I express my models of programs on paper that doesn't easily translate into math? I understand that the part of programs there you have a formula on beforehand (e.g., convert between Celsius and Fahrenheit) is easily expressed in a mathematical formula before implementing it. However, how should I express I/O?

Often when I have a problem that isn't easily expressed in mathematical notation (albeit to my limited knowledge of math), I usually got a good idea of how I could express it in code.

When I write pseudo code it often feels like I already have the code in my mind before I describe in plain English. That feels like a waste of time. So pseudo code doesn't feel like a great tool to express models of my programs.

View on HN

Math isn't formulas. The part of math that is most useful for programming are algebraic structures. Many "patterns", conventions, frameworks, etc., are just bastardizations of mathematical patterns. What really matters is the composition of concepts, and what better way to think about that than mathematically?

So if you want your programming to reap the benefits of (others', mostly) mathematical reasoning--use a functional language that is all about expressing the ways in which things compose!

IO is modelled pretty well through monads. As are many other things, like nondeterministic processes, exceptions, state, etc.

> So if you want your programming to reap the benefits of (others', mostly) mathematical reasoning--use a functional language that is all about expressing the ways in which things compose!

I do prefer using functional language over imperative ones, but I don't understand that is connected to model software on paper?

> IO is modelled pretty well through monads. As are many other things, like nondeterministic processes, exceptions, state, etc.

Isn't there any easier way to describe I/O than with category theory? I understand that it's _possible_ to model IO with monads, but how would I communicate it with colleagues that doesn't have a background in category theory (or myself for that matter)?

Part of the benefits with modelling a program on paper should be to make communication easier. And to require people you communicate with to have knowledge in category theory to understand your design fells silly.

I probably misinterpret you, so could you please give a more detailed explanation or example?

> but I don't understand that is connected to model software on paper

I was talking more generally about techniques that allow for sneaking in mathematical thinking in various stages of development, not just modelling. Largely because of the very precise types which make a large part of your program verifiable (and force you to think about a lot of things you wouldn't have if you were using, say, JavaScript).

I was recently making a script engine for a game. It was really neat to realize that the "runScript" method was literally just a mapping between two monads. No special state inbetween, no complex logic, no file lookup or anything like that. These types of insight accumulate, and there's really a tonne of stuff to learn (this potential for learning the language itself feels much greater in functional programming for me).

> Isn't there any easier way to describe I/O than with category theory?

This isn't category theory! Do you really think every working Haskell programmer is some mathematician? No. Look at this random image I googled, you think Haskell programmers understand this? https://i.stack.imgur.com/4IzGk.png Most mathematicians don't!

The notion of a monad in functional programming might be inspired by category theory, but you're really better of not taking that connection too seriously. Functors, applicatives, and monads are all very simple notions that should be understood as programming constructs, not arcane math. If you want an area of math to research to most benefit your functional programming, that is undoubtedly mathematical logic and/or intro-level type theory, and not category theory. (This should take you in the direction of dependent types.)

Really, types are the key. The notion of a monad is best understood not through vague real-world analogies with sandwiches, but through the type and implementation of its >>= method. The reason for that is that the point of monads is in composition. And basic linear algebra is enough to understand the importance of composition, not category theory. Just look at the Maybe monad to immediately understand it: Nothing >>= f = Nothing, Just x >>= f = f x, where f : a -> Maybe b. Isn't this a really clear, intuitive way of composing operations which might fail?

Same goes for IO. The only thing you're doing is composing some values. When you compose an IO Int with some function of the type Int -> IO (), you get back a value of type IO () (which your runtime executes if you bind it to main). All of this is right in the type, and it's just as intuitive a way of composing IO values as Maybe ones, IMO.

You get the added benefit of execution becoming not a side-effect, but a first-class member. Evaluation of IO programs is not their execution, you could evaluate putStrLn "asdf" a million times without it being executed. You can literally store those programs (values) somewhere and execute them later.

You don't need to know category theory. You just need to understand a few things that came from it, like `Maybe`, which is the most obviously useful and trivially easy monad. Just forget about the fact that it's a monad and any general rules about monads and just learn how to use `Maybe`.

From there, input handling is just a state machine. Easy to draw on paper as a graph.

> Part of the benefits with modelling a program on paper should be to make communication easier. And to require people you communicate with to have knowledge in category theory to understand your design fells silly.

This is an odd complaint, because you can also say: requiring people you communicate with to have knowledge in (state machines | graphs | `if` statements | ...) to understand your design feel silly.

> because you can also say

I don't think you can actually:D

I mean for each category of programmer there is a pretty clear line separating common knowledge from things you can't expect people to know. And for pretty much every category of programmer, if statements and category theory are the opposite ends of that line.

I mean I feel like you agree with this based on your first paragraph, his complaint isn't odd because it's saying you can't expect people to know category theory, it's because he thinks that category theory is necessary here.

> You don't need to know category theory. You just need to understand a few things that came from it, like `Maybe`, which is the most obviously useful and trivially easy monad. Just forget about the fact that it's a monad and any general rules about monads and just learn how to use `Maybe`.

I didn't convey my question clearly. What I'm wondering is how I should express programs, or part of them, using mathematical notation when I don't see them being mathematical in nature to begin with?

An example:

  def hello(name):
      if (name == "Bob"):
          print("Hello, " + name)
      else:
          print("Hello, World!")

How could I express this easily using mathematical notation?

It just feels weird that to convey this simple program on paper both I and the person I try to communicate with needs to have a grounding in category theory.

Hope you're able to understand my question. :)

That was the second part of my answer: a graph on paper. Draw nodes of execution and represent the branch as two arrows coming from the node and heading to new nodes. Label the arrows with the predicates of the branch.

This is both definitely useful and definitely math.

> That was the second part of my answer: a graph on paper. Draw nodes of execution and represent the branch as two arrows coming from the node and heading to new nodes. Label the arrows with the predicates of the branch.

Thanks! You don't happen to have some learning resources for modelling programs as state machines? I can't find anything when I search.

This isn't about modelling rather a programming technique, but check out Idris for its dependent typing. It lets you encode state machines in types, which means your programs literally will not typecheck if you try for example to withdraw money from an unauthorized ATM, or candy from an empty store. You can make verified network protocols and drivers like this.

This is more of a practical writeup on state machines than a theoretical one: http://gameprogrammingpatterns.com/state.html

You might also know these as flowcharts when applied to program flow control.

I don't think I answered the original question well. I just wanted to point out that math is more than just equations. Others have done a much better job in this thread.

Author here.

I would say that modeling the computational process in math is not typically helpful (you already have a formal programming language) you should model the real-world (or at least computer world) problem you are trying to solve.

Carefully define operations and constraints, introduce abstractions for solving them, etc.

Do you have an example of an I/O problem you have thought about that you would like me to talk more about?

Thanks for the article and discussion that sprang up around it!

The question I'm trying to ask is how I should express (part of) programs on paper using math when I don't see how they are related to math.

Example: How could I easily express a function that takes a string as input and outputs the string capitalized using math notation?

I understand that the problem you solve in the post should probably be put on paper first before you began writing any code.

My problem is to express programs in math when "calculate" isn't part of the problem description, like it is in the example in the blog post.

Edit: Changed example question.

This is a great question. What I really tried to emphasize in the article is that math is not a formal language. Since its just you and coworkers, write out the parts you need as you need them, and ignore details. After all, its an exercise to help you think.

If I needed uppercase I would just say:

  `up(s)` is a function that maps a string s to its uppercase string

Writing that down, you and I already have a pretty good idea of how it works, or its included in our libraries, and we can figure out the details when writing the code.

This is of course assuming `uppercase` is a minor part of another algorithm. If it was the subject of discussion I might describe it like this:

  Let `u(c)` be a function that maps a characters to its uppercase character. In ASCII `u(c) = c + K` where K is some offset.

  To capitalize an entire string we need to apply that function to each character.

  Let `up(s)` = (u(c_1), u(c_2), ... u(c_n))
  where the string s = (c_1, c_2, ... c_n)

Perhaps that helps, but I don't think it addresses your question directly. I think you need some experience reading math to know how to describe problems, but I don't think you need to know fancy math. A knowledge of functions, sets, tuples, logic, summations, etc, will get most of what you need.

I highly recommend that book I linked in the article: "Introduction to Graph Theory" By: Trudeau

Thanks for the explanation! An example to check if I understood you correctly.

  `func1(r, s)` is a function that sends a request `r` to a given server `s`. It returns a status code from the server.

How does that sound? It feels more like a spec than "doing math".

> I highly recommend that book I linked in the article: "Introduction to Graph Theory" By: Trudeau

I'll check it out! Does the book cover all the relevant parts you mentioned before?

Btw, it seems you don't link the book in the article. At least I couldn't find it when looked now.

Sort of. That would absolutely be "allowed". Now whether that is useful to write out, depends on what problem you are trying to solve.

Here is another example

https://gist.github.com/justinmeiners/0aff3d98a66b4d5f109656...

> Does the book cover all the relevant parts

No, it isn't quite so comprehensive, but it will absolutely help you get started and help you decide if you want to learn more.

https://www.amazon.com/Introduction-Graph-Theory-Dover-Mathe...

> However, how should I express I/O?

First thing that comes to mind is category theory, especially monads. Haskell's I/O monad for example: https://en.wikipedia.org/wiki/Monad_(functional_programming)...

But why? Having to sweet talk the compiler into simply reading/writing data by building towers of super abstract mathematical concepts doesn't look like a win from here. If that's the cure, I'll take the disease.

The question was about expressing I/O as a mathematical concept (on paper), not about talking to compilers.

Haskell and others have pretty much proved it's possible in practice as well. But from my experience the cure is worse than the disease. Wishing that software was as formal as math is one thing. Pretending it is leads nowhere worth going.

I have most of my feet in the C++/Common Lisp camps these days. Where you accept that the world is a messy place with complex problems that don't fit neatly into labeled boxes, and use the most powerful tools you can think of to deal with it.

Reply on news.ycombinator.com