8 ms·

Whiteboard problems in pure Lambda Calculus (2017)

87 points by jesperht 8y ago

calebm 8y ago
Could anyone describe practical benefits to studying lambda calculus (other than, perhaps, to better understand the underlying concepts in LISP)? It seems kind of interesting because it is a way to describe what programs do with a very small number of building blocks. But why is it useful? What insights does it bring?
- nisa 8y ago
  not a good student, can't give you a good overview but this kind of blew me away: https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon... - you also can explain the y-combinator from first principles. Not sure how practical that is :)
juliangamble 8y ago
My team at Vivint, the Space Monkey group, stopped doing whiteboard interviews a while ago. We certainly used to do them, but we’ve transitioned to homework problems or actually just hiring a candidate as a short term contractor for a day or two to solve real work problems and see how that goes. Whiteboard interviews are kind of like Festivus but in a bad way: you get the feats of strength and then the airing of grievances. Unfortunately, modern programming is nothing like writing code in front of a roomful of strangers with only a whiteboard and a marker, so it’s probably not best to optimize for that.
- snaky 8y ago
  The logical way forward is then to actually just hiring a candidate as a short term contractor for a week or two to solve real work problems on site, in a team with other employees and see how that goes.
  - bumholio 8y ago
    The problem with that approach is that the company must commit. You can't embed 100 candidates into your team but you can easily send 100 identical homeworks and then only bother to analyze those that make it to the face to face interview. As a bonus, it optimizes for subservience, a perennial business resource.
    - ptero 8y ago
      An even bigger problem is that most good candidates have their current job and could be open to better opportunities, but would not consider going into this hung up state. Do you expect me to quit my job before doing the tryout? Even if not and, say, you like me, when do you expect me to quit my current job? I need at least a couple of months to cleanly exit without burning bridges and I am not going to even start this process until I have a firm offer from the new company.
  - Tharkun 8y ago
    Yeah. Because a programmer in a new team is likely to be productive after a week or two. /s
    - naasking 8y ago
      In my experience, good and bad candidates differentiate themselves pretty quickly. Being productive is not the expectation, it's about gathering more empirical data on the candidate's actual skills with real development.
      - Tharkun 8y ago
        Which is a really awful way of hiring. Forcing someone to go through the hassle of being a contractor for a couple of weeks, only so you can decide whether you want to hire them afterwards. I suggest you don't try this in Belgium, where employee protection is a thing and this sort of nonsense doesn't fly. Unless, of course, you're looking for a long term contractor and not an employee.
GGfpc 8y ago
Every day I feel amazed at how much smarter other people are.
- medh2000 8y ago
  Yes this sound unrealistic in most cases. Taking a leave from your current job to try out another one is very risky.
- akullpp 8y ago
  Lambda calculus is simple and easy to understand. I learnt it in university from scratch and I think that everybody can do it. Set theory has a quite similar, manageable, learning curve.
  - _emacsomancer_ 8y ago
    And set theory and lambda calculus have nice 'interoperability' (e.g. λx[Dog(x)] is a characteristic lambda function for the set {x | x is a dog}.)
ptero 8y ago
IMO Lambda calculus should be taught wider in CS programs. It brings useful models, builds (if one likes theory) good background to functional programming paradigms, etc. However, to me, this post was hard to read. Wikipedia https://en.wikipedia.org/wiki/Lambda_calculus https://en.wikipedia.org/wiki/Lambda_calculus provides a much better introduction: from informal motivation to formal descriptions. My 2c.
- fhood 8y ago
  I learned it in school, so I don't think it is that uncommon. Barely remember it though. Doesn't come up a ton.
- PopeDotNinja 8y ago
  I want to budget cognitive learning cycles to learning lambda calculus, but I've tried superficially a couple of times and couldn't find a practical reason to do so. Prioritizing picking up a more nuts & bolts skill has always seemed more engaging and lucrative. If I already know some Lisp-ish stuff from languages I already know, is there some benefit to picking up Lambda Calculus that isn't super obvious?
  - ptero 8y ago
    Just my 2c -- maybe not, this is just a way of thinking about problems that might come handy in some usually unexpected way. Also, it could be cool to mumble to your geek friends on use cases of alpha conversion and beta reduction. Seriously though, I do not know Lisp, but if you know OCaml you probably have a good feel for lambda calculus just from practical application of the language. My 2c.
    - PopeDotNinja 8y ago
      Learning OCaml is something I've wanted to do. I'll add this to the list of reasons to learn it :) Thanks!
- lomnakkus 8y ago
  > IMO Lambda calculus should be taught wider in CS programs. It brings useful models, builds (if one likes theory) good background to functional programming paradigms, etc. I'm surprised than anyone thinks this. Unless you're in a very specialized area, it's about as useful as getting practice with writing algorithms using Turing Machines. (Yes, it offers a very different perspective to the usual Von Neumann machine, but learning graph reduction as evalation is just as valuable, if not more.)
dang 8y ago
Previously at https://news.ycombinator.com/item?id=13914004 https://news.ycombinator.com/item?id=13914004.
gexla 8y ago
I stopped reading after... (λU.(λY.(λvoid.(λ0.(λsucc.(λ+.(λ*.(λ1.(λ2.(λ3.(λ4.(λ5.(λ6.(λ7.(λ8.(λ9.(λ10.(λnum.(λtrue.(λfalse.(λif.(λnot.(λand.(λor.(λmake-pair.(λpair-first.(λpair-second.(λzero?.(λpred.(λ-.(λeq?.(λ/.(λ%.(λnil.(λnil?.(λcons.(λcar.(λcdr.(λdo2.(λdo3.(λdo4.(λfor.(λprint-byte.(λprint-list.(λprint-newline.(λzero-byte.(λitoa.(λfizzmsg.(λbuzzmsg.(λfizzbuzzmsg.(λfizzbuzz.(fizzbuzz (((num 1) 0) 1)) λn.((for n) λi.((do2 (((if (zero? ((% i) 3))) λ_.(((if (zero? ((% i) 5))) λ_.(print-list fizzbuzzmsg)) λ_.(print-list fizzmsg))) λ_.(((if (zero? ((% i) 5))) λ_.(print-list buzzmsg)) λ_.(print-list (itoa i))))) (print-newline nil)))) ((cons (((num 0) 7) 0)) ((cons (((num 1) 0) 5)) ((cons (((num 1) 2) 2)) ((cons (((num 1) 2) 2)) ((cons (((num 0) 9) 8)) ((cons (((num 1) 1) 7)) ((cons (((num 1) 2) 2)) ((cons (((num 1) 2) 2)) nil))))))))) ((cons (((num 0) 6) 6)) ((cons (((num 1) 1) 7)) ((cons (((num 1) 2) 2)) ((cons (((num 1) 2) 2)) nil))))) ((cons (((num 0) 7) 0)) ((cons (((num 1) 0) 5)) ((cons (((num 1) 2) 2)) ((cons (((num 1) 2) 2)) nil)))))
lisper 8y ago
Factorials in pure lambda calculus, compiled to native code and running in non-geological time: http://www.flownet.com/ron/lambda-calculus.html http://www.flownet.com/ron/lambda-calculus.html
lapinot 8y ago
Extra weirdness with this turing-complete combinatory logic with only a single combinator [1,2]. Combinatory logic being like lambda-calculus but where are only allowed to use some predefined functions and function application (you can't create your own functions). Bonus: since iota/jot/zot only have 1 symbol + application, programs are binary trees (with the combinator in the leaves) which we can write in prefix order as "1" for leaf and "0<program><program>" for node. And now (modulo some io details) we have a cool language where any bitstring is a valid program. [1] http://www.nyu.edu/projects/barker/Iota/zot.html http://www.nyu.edu/projects/barker/Iota/zot.html [2] https://en.wikipedia.org/wiki/Iota_and_Jot https://en.wikipedia.org/wiki/Iota_and_Jot

87 points by jesperht 8y ago

Could anyone describe practical benefits to studying lambda calculus (other than, perhaps, to better understand the underlying concepts in LISP)? It seems kind of interesting because it is a way to describe what programs do with a very small number of building blocks. But why is it useful? What insights does it bring?

nisa 8y ago
not a good student, can't give you a good overview but this kind of blew me away: https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon... - you also can explain the y-combinator from first principles. Not sure how practical that is :)

juliangamble 8y ago

My team at Vivint, the Space Monkey group, stopped doing whiteboard interviews a while ago. We certainly used to do them, but we’ve transitioned to homework problems or actually just hiring a candidate as a short term contractor for a day or two to solve real work problems and see how that goes. Whiteboard interviews are kind of like Festivus but in a bad way: you get the feats of strength and then the airing of grievances. Unfortunately, modern programming is nothing like writing code in front of a roomful of strangers with only a whiteboard and a marker, so it’s probably not best to optimize for that.

snaky 8y ago
The logical way forward is then to actually just hiring a candidate as a short term contractor for a week or two to solve real work problems on site, in a team with other employees and see how that goes.
- bumholio 8y ago
  The problem with that approach is that the company must commit. You can't embed 100 candidates into your team but you can easily send 100 identical homeworks and then only bother to analyze those that make it to the face to face interview. As a bonus, it optimizes for subservience, a perennial business resource.
  - ptero 8y ago
    An even bigger problem is that most good candidates have their current job and could be open to better opportunities, but would not consider going into this hung up state. Do you expect me to quit my job before doing the tryout? Even if not and, say, you like me, when do you expect me to quit my current job? I need at least a couple of months to cleanly exit without burning bridges and I am not going to even start this process until I have a firm offer from the new company.
- Tharkun 8y ago
  Yeah. Because a programmer in a new team is likely to be productive after a week or two. /s
  - naasking 8y ago
    In my experience, good and bad candidates differentiate themselves pretty quickly. Being productive is not the expectation, it's about gathering more empirical data on the candidate's actual skills with real development.
    - Tharkun 8y ago
      Which is a really awful way of hiring. Forcing someone to go through the hassle of being a contractor for a couple of weeks, only so you can decide whether you want to hire them afterwards. I suggest you don't try this in Belgium, where employee protection is a thing and this sort of nonsense doesn't fly. Unless, of course, you're looking for a long term contractor and not an employee.

GGfpc 8y ago

Every day I feel amazed at how much smarter other people are.

medh2000 8y ago
Yes this sound unrealistic in most cases. Taking a leave from your current job to try out another one is very risky.
akullpp 8y ago
Lambda calculus is simple and easy to understand. I learnt it in university from scratch and I think that everybody can do it. Set theory has a quite similar, manageable, learning curve.
- _emacsomancer_ 8y ago
  And set theory and lambda calculus have nice 'interoperability' (e.g. λx[Dog(x)] is a characteristic lambda function for the set {x | x is a dog}.)

ptero 8y ago

IMO Lambda calculus should be taught wider in CS programs. It brings useful models, builds (if one likes theory) good background to functional programming paradigms, etc. However, to me, this post was hard to read. Wikipedia https://en.wikipedia.org/wiki/Lambda_calculus https://en.wikipedia.org/wiki/Lambda_calculus provides a much better introduction: from informal motivation to formal descriptions. My 2c.

fhood 8y ago
I learned it in school, so I don't think it is that uncommon. Barely remember it though. Doesn't come up a ton.
PopeDotNinja 8y ago
I want to budget cognitive learning cycles to learning lambda calculus, but I've tried superficially a couple of times and couldn't find a practical reason to do so. Prioritizing picking up a more nuts & bolts skill has always seemed more engaging and lucrative. If I already know some Lisp-ish stuff from languages I already know, is there some benefit to picking up Lambda Calculus that isn't super obvious?
- ptero 8y ago
  Just my 2c -- maybe not, this is just a way of thinking about problems that might come handy in some usually unexpected way. Also, it could be cool to mumble to your geek friends on use cases of alpha conversion and beta reduction. Seriously though, I do not know Lisp, but if you know OCaml you probably have a good feel for lambda calculus just from practical application of the language. My 2c.
  - PopeDotNinja 8y ago
    Learning OCaml is something I've wanted to do. I'll add this to the list of reasons to learn it :) Thanks!
lomnakkus 8y ago
> IMO Lambda calculus should be taught wider in CS programs. It brings useful models, builds (if one likes theory) good background to functional programming paradigms, etc. I'm surprised than anyone thinks this. Unless you're in a very specialized area, it's about as useful as getting practice with writing algorithms using Turing Machines. (Yes, it offers a very different perspective to the usual Von Neumann machine, but learning graph reduction as evalation is just as valuable, if not more.)

dang 8y ago

Previously at https://news.ycombinator.com/item?id=13914004 https://news.ycombinator.com/item?id=13914004.

gexla 8y ago

I stopped reading after... (λU.(λY.(λvoid.(λ0.(λsucc.(λ+.(λ*.(λ1.(λ2.(λ3.(λ4.(λ5.(λ6.(λ7.(λ8.(λ9.(λ10.(λnum.(λtrue.(λfalse.(λif.(λnot.(λand.(λor.(λmake-pair.(λpair-first.(λpair-second.(λzero?.(λpred.(λ-.(λeq?.(λ/.(λ%.(λnil.(λnil?.(λcons.(λcar.(λcdr.(λdo2.(λdo3.(λdo4.(λfor.(λprint-byte.(λprint-list.(λprint-newline.(λzero-byte.(λitoa.(λfizzmsg.(λbuzzmsg.(λfizzbuzzmsg.(λfizzbuzz.(fizzbuzz (((num 1) 0) 1)) λn.((for n) λi.((do2 (((if (zero? ((% i) 3))) λ_.(((if (zero? ((% i) 5))) λ_.(print-list fizzbuzzmsg)) λ_.(print-list fizzmsg))) λ_.(((if (zero? ((% i) 5))) λ_.(print-list buzzmsg)) λ_.(print-list (itoa i))))) (print-newline nil)))) ((cons (((num 0) 7) 0)) ((cons (((num 1) 0) 5)) ((cons (((num 1) 2) 2)) ((cons (((num 1) 2) 2)) ((cons (((num 0) 9) 8)) ((cons (((num 1) 1) 7)) ((cons (((num 1) 2) 2)) ((cons (((num 1) 2) 2)) nil))))))))) ((cons (((num 0) 6) 6)) ((cons (((num 1) 1) 7)) ((cons (((num 1) 2) 2)) ((cons (((num 1) 2) 2)) nil))))) ((cons (((num 0) 7) 0)) ((cons (((num 1) 0) 5)) ((cons (((num 1) 2) 2)) ((cons (((num 1) 2) 2)) nil)))))

lisper 8y ago

Factorials in pure lambda calculus, compiled to native code and running in non-geological time: http://www.flownet.com/ron/lambda-calculus.html http://www.flownet.com/ron/lambda-calculus.html

lapinot 8y ago

Extra weirdness with this turing-complete combinatory logic with only a single combinator [1,2]. Combinatory logic being like lambda-calculus but where are only allowed to use some predefined functions and function application (you can't create your own functions). Bonus: since iota/jot/zot only have 1 symbol + application, programs are binary trees (with the combinator in the leaves) which we can write in prefix order as "1" for leaf and "0<program><program>" for node. And now (modulo some io details) we have a cool language where any bitstring is a valid program. [1] http://www.nyu.edu/projects/barker/Iota/zot.html http://www.nyu.edu/projects/barker/Iota/zot.html [2] https://en.wikipedia.org/wiki/Iota_and_Jot https://en.wikipedia.org/wiki/Iota_and_Jot