A Path to Enlightenment in Programming Language Theory • Hacker News Board

Re: A Path to Enlightenment in Programming Language Theory

#31

Post by agumonkey » Mon, Jun 22, 2015, 9:50 PM UTC

igravious wrote: post #22

agumonkey wrote: post #8

Earlier quoted context omitted.

Here's a famous reddit comment about bootstrapping a language: http://www.reddit.com/r/programming/comments/9x15g/programmi... Also this was here not long ago https://news.ycombinator.com/item?id=9699065

Ha, I remember that from not long ago. That's a _bit_ extreme though. Let's start with C, the portable assembly language. Having said that, now that WebAssembly is on the cards (boo, hiss), we'll have many more of these from-the-ground-up affairs. re: reddit thread: that Kragen, name is familiar...

I don't know how field-famous he is, but googling his name (he has a ML named after him) was full of fun crazy hacks idea. Like writing binaries under MS-DOS (just the few commands it provides like dir, copy etc) by using codepage keycodes `COPY CON > MY.COM`. And then expanding possibilities.

I agree it's a bit much to answer your question, but the spirit is there. And I agree, although learning lisp in lisp was very valuable on the intellectual level, the ignored primitives (cons, gc, interned symbols, IO) are worth knowing too. I found this book (warning: french) http://www.decitre.fr/livres/la-programmation-applicative-97... at a library, discussing a scheme system up until the io primitives. It was a great read. Sidenote: they called macros doubly-recursive functions :)

Re: A Path to Enlightenment in Programming Language Theory

#32

Post by jules » Mon, Jun 22, 2015, 9:52 PM UTC

Silhouette wrote: post #21

exDM69 wrote: post #17

Earlier quoted context omitted.

> knocking together a small lambda calculus + dependently typed interpreter in C. Not ML, Not Ocaml, not, Haskell, not any language that is _already_ got lambdas in it! This wouldn't be any more educational and just plain painful. "Research" programming languages tend to work very well for building compilers, that's why they are used in many toy programming language projects. Dealing with tree and graph structures in…

The flip side of this is that if you're writing something in C, you actually do have to understand how details like closures are implemented on real hardware. These are not trivial problems, yet many programming language design papers and articles effectively brush the whole issue of actually implementing these things under the carpet. Go ahead and search for that particular example. There is almost nothing on the We…

You can also implement an interpreter in Haskell/ML without using closures to implement closures. It would still be a lot less painful than C.

Re: A Path to Enlightenment in Programming Language Theory

#33

Post by jules » Mon, Jun 22, 2015, 9:57 PM UTC

igravious wrote: post #15

mkehrt wrote: post #10

Earlier quoted context omitted.

I don't think the grandparent wants all of these features at once necessarily in a single tutorial, but an introduction to them in a language that they already know. Also, the things you say that function pointers don't have are exactly the things that make lambdas interesting. Lambdas are anonymous and, crucially, can be nested. It's the very nesting that is what makes them difficult to get right, as they close over…

Grandparent here :) Indeed, you have put it more succinctly and cogently that I ever could. I would like an introduction to these advanced topics in the language that I already now. For instance, for a Haskell module I was studying we used a teeny tiny interpreter that had been created just for the task of learning the basics of Haskell. This interpreter was written in Lua. It was small, and I could follow the logic…

It's actually a lot easier to learn ML and then read/write the interpreter in ML than to read/write the interpreter in C. An interpreter written in C would be too convoluted.

Re: A Path to Enlightenment in Programming Language Theory

#34

Post by Silhouette » Mon, Jun 22, 2015, 10:04 PM UTC

exDM69 wrote: post #24

Silhouette wrote: post #21

Earlier quoted context omitted.

The flip side of this is that if you're writing something in C, you actually do have to understand how details like closures are implemented on real hardware. These are not trivial problems, yet many programming language design papers and articles effectively brush the whole issue of actually implementing these things under the carpet. Go ahead and search for that particular example. There is almost nothing on the We…

> The flip side of this is that if you're writing something in C, you actually do have to understand how details like closures are implemented on real hardware. If you're writing a compiler targeting real hardware and not a high level virtual machine, you'll need to learn how to implement closures regardless of the "host" language you write your compiler in. But you're correct, when implementing an interpreter, it's…

If you're writing a compiler targeting real hardware and not a high level virtual machine, you'll need to learn how to implement closures regardless of the "host" language you write your compiler in.

Right, but a lot of the tutorial material in this area doesn't really consider that issue, even though it's rather fundamental to practical applications. Instead the explanation often settles for some sort of indirect dependency on the implementation language's existing version of a similar feature. I think this is unfortunate, not least because it reduces us to a model where most people implementing these ideas depend on some sort of magic run-time environment instead of learning how to actually write that run-time.

Re: A Path to Enlightenment in Programming Language Theory

#35

Post by Silhouette » Mon, Jun 22, 2015, 10:07 PM UTC

jules wrote: post #32

Silhouette wrote: post #21

Earlier quoted context omitted.

The flip side of this is that if you're writing something in C, you actually do have to understand how details like closures are implemented on real hardware. These are not trivial problems, yet many programming language design papers and articles effectively brush the whole issue of actually implementing these things under the carpet. Go ahead and search for that particular example. There is almost nothing on the We…

You can also implement an interpreter in Haskell/ML without using closures to implement closures. It would still be a lot less painful than C.

Of course. But it's still reasonable to ask how you'd write a compiler that implements such features in a free-standing way, without depending on either the built-in tools of the language you're writing an interpreter in or a black box run-time environment/VM that does all the tricky stuff for you by magic. With a relatively low-level language like C, you don't have any choice but to confront such issues head-on, while many tutorials manage to side-step them using higher-level languages. Of course it's easier to write almost anything in a suitable higher-level language, but for educational purposes that isn't really the point IMHO.

Re: A Path to Enlightenment in Programming Language Theory

#36

Post by NotableAlamode » Mon, Jun 22, 2015, 10:07 PM UTC

igravious wrote: post #28

mafribe wrote: post #16

Earlier quoted context omitted.

When I open Pierce TaPL and see immediately ML my heart sinks. I strongly recommend that you ignore this feeling and learn a modicum of ML coding. If you want to learn TAPL, just learn a bit of Ocaml. You don't need much. If you already speak C, a bit of Haskell and Ruby, you should be able to pick up enough Ocaml in a few hours/days. Programming in Ocaml is way easier than in Haskell or C. The only two things that a…

Really? I feel like C fits my brain, know what I mean? I don't even think that it was because I learnt it early on. It's a simple language, I feel. Why is programming way easier in Ocaml than in C? Setting aside that for me programming is way easier in C than in Ocaml because I know C and don't know Ocaml, what is it about Ocaml that is way easier than C? Anyway, my original point is that it is _cheating_ to explain…

    Why is programming way easier in Ocaml than in C?

I've written vast amounts of Ocaml and C/C++, certainly over 100K LoCs in each. Programming in ML dialects is so much easier than C/C++, it's not funny. I'd estimate it takes me about 10 times longer to implement the same functionality in C/C++ than in an ML dialect. The three key features enabling this difference are the following.

* Garbage collection, removes all memory bugs, avoids tons of ugly and distracting (de)allocation commands and keeps your head free to think about more important stuff.

* Pattern matching, enables you to code up complex decision making code (and most functinality needs this) in a readable and maintainable way.

* higher-order functions allow you to parameterise code with behaviour in a neat way.

(There is one caveat, which is code for extremely high performance, I'd probably write that in C/C++, but this is not an issue concerning a learner.)

As to useless car analogies, I think implementing lambda in C is like saying: Today I'm going to learn how to build a car. First, let's do this while riding a uni-cycle ... oh... um...

Re: A Path to Enlightenment in Programming Language Theory

#37

Post by NotableAlamode » Mon, Jun 22, 2015, 10:11 PM UTC

habitue wrote: post #20

igravious wrote: post #15

Earlier quoted context omitted.

Grandparent here :) Indeed, you have put it more succinctly and cogently that I ever could. I would like an introduction to these advanced topics in the language that I already now. For instance, for a Haskell module I was studying we used a teeny tiny interpreter that had been created just for the task of learning the basics of Haskell. This interpreter was written in Lua. It was small, and I could follow the logic…

I agree with you it'd be useful to see how you might implement lambdas in a language like C. But after that first example, implementing other more complicated language constructs in C, instead of learning ML/haskell is going to be more time fighting C, and less time learning anything new. The lack of side-effects and equational reasoning in functional languages let you get a lot of details out of your way. That being…

     The lack of side-effects and equational reasoning in functional languages let you get a lot of details out of your way.

Actually ... You (kind-of/sort-of) need side effects when implementing a language with higher-order functions. You at least need it for generating fresh variables to avoid free name capture. Yes, I know you can do this with a monad, but this is not going to help a beginner. It's much easier to maintain a global counter that you increment every time you want a fresh variable name.

Re: A Path to Enlightenment in Programming Language Theory

#38

Post by NotableAlamode » Mon, Jun 22, 2015, 10:12 PM UTC

Silhouette wrote: post #21

exDM69 wrote: post #17

Earlier quoted context omitted.

> knocking together a small lambda calculus + dependently typed interpreter in C. Not ML, Not Ocaml, not, Haskell, not any language that is _already_ got lambdas in it! This wouldn't be any more educational and just plain painful. "Research" programming languages tend to work very well for building compilers, that's why they are used in many toy programming language projects. Dealing with tree and graph structures in…

The flip side of this is that if you're writing something in C, you actually do have to understand how details like closures are implemented on real hardware. These are not trivial problems, yet many programming language design papers and articles effectively brush the whole issue of actually implementing these things under the carpet. Go ahead and search for that particular example. There is almost nothing on the We…

This is not quite true. There is SPJ's famous "The implementation of functional programming languages" [1]. Then there is lots of material on various abstract machines, like the SECD machine, the CAM, the many variants of the Krivine machine, the G-machine and plenty of others whose name I forget.

All that said, I kind-of agree with you. It would be nice to have some easy to grasp explanations of how to compile higher-order functions to actual machines, x86, ARM, MIPS ... This material can be found e.g. in Appel's book [2], but I don't think it's available freely (and legally) on the web. I think this is in parts because the compilation process is not so easy: you need to understand the compilation of normal languages, in particular stack layout, and then add more pointers. You also need to think about how to do memory management if a closure lives longer than its creating context. This is quite rich material, and not even usually covered in undergraduate compilers courses.

The situation with concurrency is much worse, but that only reflects the fact that this is far from a solved problem on many levels. To cite a recent paper [3]: "Despite decades of research, we do not have [in 2015] a satisfactory concurrency semantics for any general-purpose programming language that aims to support concurrent systems code [...] Disturbingly, 40+ years after the first relaxed-memory hardware was introduced (the IBM 370/158MP), the field still does not have a credible proposal for the concurrency semantics of any general-purpose high-level language that includes high-performance shared-memory concurrency primitives. This is a major open problem for programming language semantics."

And memory models are but one issue to deal with in concurrency.

[1] http://research.microsoft.com/en-us/um/people/simonpj/papers...

[2] A. Appel, Modern Compiler Implementation in ...

[3] M. Batty et al, The Problem of Programming Language Concurrency Semantics.

Re: A Path to Enlightenment in Programming Language Theory

#39

Post by jrapdx3 » Mon, Jun 22, 2015, 10:27 PM UTC

igravious wrote: post #6

What is always missing for me in these lists is a tutorial for knocking together a small lambda calculus + dependently typed interpreter in C. Not ML, Not Ocaml, not, Haskell, not any language that has _already_ got lambdas in it! Always when I read these I see, "get your Haskell compiler and..." and I'm like, if I knew Haskell well enough to do that I wouldn't be doing this tutorial in the first place. Case in point…

And a great many fine suggestions have been made. To add one more, you might take a look at CHICKEN Scheme. It's written in C, and compiles to C.

The CHICKEN website and user manual contain a wealth of info re: theory and implementation of the compiler. The development team has always been friendly and willing to answer questions.

See http://www.call-cc.org/

Re: A Path to Enlightenment in Programming Language Theory

#40

Post by NotableAlamode » Mon, Jun 22, 2015, 10:28 PM UTC

seanmcdirmid wrote: post #12

innguest wrote: post #11

Earlier quoted context omitted.

Because 20 years ago everything on every list was about object-oriented programming and I didn't complain (too much).

PL theory has never been dominated by OOP, except for those theories specifically related to it. Just take a look at a POPL '95 proceedings. FP starts from math, for OO math had to be shoe horned into successful existing work that didn't care about it that much.

The semantics of OO languages is really messy and complicated and probably has the least well understood theory of all sequential forms of computing.