5 ms·

Mathematics and Computation

107 points by altro 7y ago

garganzol 7y ago
I would also mention that LISP is a highly enlightening instrument that connects math (lambda calculus) with programming (Turing). Once you get LISP you will never separate math and programming again. Two slightly different facets of the very same computational thing.
- TheRealPomax 7y ago
  If you never separate those two again, you will have lost the ability to reason about programming at the various levels of abstraction... which would be a net loss, not a net win.
  - garganzol 7y ago
    This can work as simultaneous win for both disciplines - one can apply math apparatus on programs, and design paradigms of programming on math. This is exactly what happens when one tries to create an iO obfuscator mentioned in the article by using FHE encryption. No way one can do that unless they understand how deeply information and data, computation and math are intervened together. Touching the LISP is enlightening experience that allows to find all those missing links between aforementioned disciplines. Especially by creating a simple LISP machine in your language of choice. You will touch the holy grail of computation and the world will never be the same again.
  - antonvs 7y ago
    All programs can be mapped to a more traditionally mathematical representation, no matter the level of abstraction. You gain reasoning ability, nothing is lost. Programming language research has also shown that there are many mathematical structures, e.g. in lambda calculus, category theory, graph theory etc. that map directly to useful computational structures. These tend to be more rigorously defined and more generic than the programming equivalents, which are often limited, ad-hoc, special case instantiations of more general structures. This argues for the opposite of your claim: if you want to reason about programming, you are seriously limiting yourself and your ability to reason about programming by ignoring the mathematical models that underlie the code you're working with.
  - chongli 7y ago
    Could you expand on this? I’m not quite sure what you mean. Are you suggesting that there are levels of abstraction in programming that can’t be modelled mathematically?
    - AnimalMuppet 7y ago
      Let's say I'm working on a user interface. Thinking of it in terms of lambda calculus instead of user interaction is... let's call it sub-optimal, even though the code can be thought of in terms of lambda calculus. Now, you can come up with some metrics to mathematically analyze certain aspects of the user interaction. I don't think that's what garganzol was talking about, though.
      - chongli 7y ago
        you can come up with some metrics to mathematically analyze certain aspects of the user interaction And we have done that! Fitts’ law [1] gives us a very good way of quantifying certain aspects of user interface design. I can’t tell you how many UIs I’ve used (lost count) that have ignored this very basic principle and as a result they’re extremely frustrating to use. In any case, it may not be what garganzol was talking about, but it did resemble a comment I’ve seen made many times. In the vast majority of cases I’ve seen, people who claim that math is inapplicable to some problem are completely unaware of a rich and storied field of mathematics dedicated to that topic. [1] https://en.wikipedia.org/wiki/Fitts%27s_law https://en.wikipedia.org/wiki/Fitts%27s_law
        AnimalMuppet 7y ago
        Sure. But like TheRealPomax said, that's a different level of abstraction. If you need to be thinking in terms of Fitts' Law, and you're thinking of your code in terms of lambda calculus-level math, you're going to have a rough time.
  - contravariant 7y ago
    That's a weird interpretation. Usually when you can consider things to be two sides of the same coin then it's a sign that you can reason about them at more levels of abstraction. Like most insights it's very hard to stop seeing the connection, but that's not usually a bad thing.
- Koshkin 7y ago
  Lisp is like some natural languages - you have to be born into it.
  - garganzol 7y ago
    Not born, but at least educated. Many people do not realize it, but JavaScript is a syntactically sugared dialect of LISP. The same goes to Logo, a simple language designed for kids, usually taught at schools.
    - aratakareigen 7y ago
      What makes JavaScript a Lisp? I associate Lisps with a small but immensely expressive core, powerful metaprogramming facilities, a very simple syntax, and an emphasis on linked lists as the building block of syntax and, at least historically, of everything else, too. JavaScript has maybe one of those.
      - garganzol 7y ago
        JavaScript is a LISP due to following properties: 1. Minimal core modeled on Scheme 2. Everything is a dictionary (globals, locals, objects, prototypes). This is a direct result of relying on LISP notion of an 'env' 3. Functions are first-class citizens 4. JavaScript is a dynamic language LISPs are fairly easy to spot. Their cores are minimal Scheme-like implementations with everything on top being a syntatic sugar over a few basic concepts. This approach makes the implementations surprisingly concise and powerful.
        lispm 7y ago
        JavaScript is not a LISP (aka LISt Processor) because of these properties: * Lisp is based on efficient procedures (usually with lexical scoping), not objects with properties (-> dictionaries) and complex scoping. * Lisp has a code representation based on lists of symbols (and other atoms) and an evaluator model for that. Identifiers in code are symbols. This is typically used both internally and externally (as textual source code). * Lisp is doing list processing at its core and applies it to itself. * Lisp provides forms of source transformations based on list processing: macros, ... JavaScript might be considered to be some non-symbolic non-list-processing Lisp/Scheme derived language, turned into an object-oriented language.
rory_isAdonk 7y ago
Loving reading this, thanks altro. Motivation gained to do a MSc in Statistics.
- altro 7y ago
  There are so many beautiful books, notes, blogs on theoretical computer science...Keep reading ;)
  - petulla 7y ago
    Share some!
    - dpflan 7y ago
      Check out altro’s other submissions, quite a few PDFs. > https://news.ycombinator.com/submitted?id=altro https://news.ycombinator.com/submitted?id=altro
    - altro 7y ago
      just as a starting point: https://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read https://cstheory.stackexchange.com/questions/3253/what-books... Many links point to Amazon, but there are some that point to free stuff.
zozbot234 7y ago
Tl;dr: an excellent book on computational complexity theory.
deyouz 7y ago
Thanks a lot!

107 points by altro 7y ago

I would also mention that LISP is a highly enlightening instrument that connects math (lambda calculus) with programming (Turing). Once you get LISP you will never separate math and programming again. Two slightly different facets of the very same computational thing.

TheRealPomax 7y ago
If you never separate those two again, you will have lost the ability to reason about programming at the various levels of abstraction... which would be a net loss, not a net win.
- garganzol 7y ago
  This can work as simultaneous win for both disciplines - one can apply math apparatus on programs, and design paradigms of programming on math. This is exactly what happens when one tries to create an iO obfuscator mentioned in the article by using FHE encryption. No way one can do that unless they understand how deeply information and data, computation and math are intervened together. Touching the LISP is enlightening experience that allows to find all those missing links between aforementioned disciplines. Especially by creating a simple LISP machine in your language of choice. You will touch the holy grail of computation and the world will never be the same again.
- antonvs 7y ago
  All programs can be mapped to a more traditionally mathematical representation, no matter the level of abstraction. You gain reasoning ability, nothing is lost. Programming language research has also shown that there are many mathematical structures, e.g. in lambda calculus, category theory, graph theory etc. that map directly to useful computational structures. These tend to be more rigorously defined and more generic than the programming equivalents, which are often limited, ad-hoc, special case instantiations of more general structures. This argues for the opposite of your claim: if you want to reason about programming, you are seriously limiting yourself and your ability to reason about programming by ignoring the mathematical models that underlie the code you're working with.
- chongli 7y ago
  Could you expand on this? I’m not quite sure what you mean. Are you suggesting that there are levels of abstraction in programming that can’t be modelled mathematically?
  - AnimalMuppet 7y ago
    Let's say I'm working on a user interface. Thinking of it in terms of lambda calculus instead of user interaction is... let's call it sub-optimal, even though the code can be thought of in terms of lambda calculus. Now, you can come up with some metrics to mathematically analyze certain aspects of the user interaction. I don't think that's what garganzol was talking about, though.
    - chongli 7y ago
      you can come up with some metrics to mathematically analyze certain aspects of the user interaction And we have done that! Fitts’ law [1] gives us a very good way of quantifying certain aspects of user interface design. I can’t tell you how many UIs I’ve used (lost count) that have ignored this very basic principle and as a result they’re extremely frustrating to use. In any case, it may not be what garganzol was talking about, but it did resemble a comment I’ve seen made many times. In the vast majority of cases I’ve seen, people who claim that math is inapplicable to some problem are completely unaware of a rich and storied field of mathematics dedicated to that topic. [1] https://en.wikipedia.org/wiki/Fitts%27s_law https://en.wikipedia.org/wiki/Fitts%27s_law
      - AnimalMuppet 7y ago
        Sure. But like TheRealPomax said, that's a different level of abstraction. If you need to be thinking in terms of Fitts' Law, and you're thinking of your code in terms of lambda calculus-level math, you're going to have a rough time.
- contravariant 7y ago
  That's a weird interpretation. Usually when you can consider things to be two sides of the same coin then it's a sign that you can reason about them at more levels of abstraction. Like most insights it's very hard to stop seeing the connection, but that's not usually a bad thing.
Koshkin 7y ago
Lisp is like some natural languages - you have to be born into it.
- garganzol 7y ago
  Not born, but at least educated. Many people do not realize it, but JavaScript is a syntactically sugared dialect of LISP. The same goes to Logo, a simple language designed for kids, usually taught at schools.
  - aratakareigen 7y ago
    What makes JavaScript a Lisp? I associate Lisps with a small but immensely expressive core, powerful metaprogramming facilities, a very simple syntax, and an emphasis on linked lists as the building block of syntax and, at least historically, of everything else, too. JavaScript has maybe one of those.
    - garganzol 7y ago
      JavaScript is a LISP due to following properties: 1. Minimal core modeled on Scheme 2. Everything is a dictionary (globals, locals, objects, prototypes). This is a direct result of relying on LISP notion of an 'env' 3. Functions are first-class citizens 4. JavaScript is a dynamic language LISPs are fairly easy to spot. Their cores are minimal Scheme-like implementations with everything on top being a syntatic sugar over a few basic concepts. This approach makes the implementations surprisingly concise and powerful.
      - lispm 7y ago
        JavaScript is not a LISP (aka LISt Processor) because of these properties: * Lisp is based on efficient procedures (usually with lexical scoping), not objects with properties (-> dictionaries) and complex scoping. * Lisp has a code representation based on lists of symbols (and other atoms) and an evaluator model for that. Identifiers in code are symbols. This is typically used both internally and externally (as textual source code). * Lisp is doing list processing at its core and applies it to itself. * Lisp provides forms of source transformations based on list processing: macros, ... JavaScript might be considered to be some non-symbolic non-list-processing Lisp/Scheme derived language, turned into an object-oriented language.

rory_isAdonk 7y ago

Loving reading this, thanks altro. Motivation gained to do a MSc in Statistics.

altro 7y ago
There are so many beautiful books, notes, blogs on theoretical computer science...Keep reading ;)
- petulla 7y ago
  Share some!
  - dpflan 7y ago
    Check out altro’s other submissions, quite a few PDFs. > https://news.ycombinator.com/submitted?id=altro https://news.ycombinator.com/submitted?id=altro
  - altro 7y ago
    just as a starting point: https://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read https://cstheory.stackexchange.com/questions/3253/what-books... Many links point to Amazon, but there are some that point to free stuff.

zozbot234 7y ago

Tl;dr: an excellent book on computational complexity theory.

deyouz 7y ago

Thanks a lot!