Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Path to Enlightenment in Programming Language Theory

steshaw.org

Post reply on HN
Print view View original

51–60 of 99 posts

Re: A Path to Enlightenment in Programming Language Theory

#51

Post by igravious »

jrapdx3 wrote: post #39
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/

Another fine suggestion, thanks!

Re: A Path to Enlightenment in Programming Language Theory

#52

Post by igravious »

swah wrote: post #42
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…

That's something I liked about jonesforth ( https://raw.githubusercontent.com/AlexandreAbreu/jonesforth/... ) ! but its not a lambda calculus interpreter I guess.

Not what I had in mind but intriguing nonetheless.

Re: A Path to Enlightenment in Programming Language Theory

#53

Post by ufo »

psibi wrote: post #2

How much does algebra contribute to learning Type theory ? I'm currently working on the How to prove it book. I thought, I would jump to TAPL after finishing that.

Type theory is closer to logic than it is to algebra. But for things like TAPL that don't get into really deep type theory you don't need lots of previous knowledge.

Knowing how to prove things and express your self rigorously is very helpful though, but its generally helpful for any part of computer science, not just programming languages.

Re: A Path to Enlightenment in Programming Language Theory

#54

Post by igravious »

sklogic wrote: post #48
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…

There is no point in doing such things in C, since C is just too low level. What is normally done is a very simple and stupid, but extensible language bootstrapped with C (or whatever else), and then grown up to a level when it's convenient to implement a functional language compiler (i.e., at least higher order functions and some pattern matching). I wrote about such a bootstrap some time ago: https://combinatorylog…

That's a bit defeatist, we don't know until we try!

Re: A Path to Enlightenment in Programming Language Theory

#55

Post by sklogic »

panic wrote: post #9

In practice, most programming languages are not purely or even mostly functional. So why is everything on this list about functional programming?

In practice, most programming languages are compiled via SSA or even Array SSA, i.e., via a pure functional intermediate representation. And understanding it thoroughly is a huge advantage.

Re: A Path to Enlightenment in Programming Language Theory

#56

Post by sklogic »

igravious wrote: post #54
sklogic wrote: post #48

Earlier quoted context omitted.

There is no point in doing such things in C, since C is just too low level. What is normally done is a very simple and stupid, but extensible language bootstrapped with C (or whatever else), and then grown up to a level when it's convenient to implement a functional language compiler (i.e., at least higher order functions and some pattern matching). I wrote about such a bootstrap some time ago: https://combinatorylog…

That's a bit defeatist, we don't know until we try!

Ok, take a look at Hugs, it's mostly done on a C level.

Re: A Path to Enlightenment in Programming Language Theory

#57

Post by ufo »

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...

That "C is portable assembly language" mantra bugs me a bit. There are lots of things that are dirt simple in real assembly language but impossible to do in (standard) C: tail call optimization, computed gotos, arithmetic overflow detection, SIMD, control over registers and local variable allocations, etc...

If you want to make things really low level, then make a compiler that targets assembly language and then bootstrap it. Coding the first version of the compiler in assembly or C instead of something more suitable for the task is just unnecessary pain.

Re: A Path to Enlightenment in Programming Language Theory

#58

Post by AnimalMuppet »

NotableAlamode wrote: post #49
seanmcdirmid wrote: post #46

Earlier quoted context omitted.

Not just that, but we still don't really know how to combine subtyping and generics very well. The soundness question when considering variance is still quite open, and it shows in the poor support for type inference in OO languages (in spite of heroic efforts made in languages like Scala). Much of this has to do with the root: most of our PL theory was basically designed for FP, and applying them to OOP has been pre…

soundness question when considering variance What is this question? Have you got a reference?

I'm not the one you were replying to, but maybe seanmcdirmid means this: https://en.wikipedia.org/wiki/Covariance_and_contravariance_...

But I thought that was pretty well understood, so I don't know what he thinks is open...

Re: A Path to Enlightenment in Programming Language Theory

#59

Post by jules »

Silhouette wrote: post #35
jules wrote: post #32

Earlier quoted context omitted.

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, whi…

In that case, why not write a compiler in Haskell to C ;-)

Re: A Path to Enlightenment in Programming Language Theory

#60

Post by ufo »

Silhouette wrote: post #34
exDM69 wrote: post #24

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. 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 de…

Thats because tutorial material is going to keep things simple. If you really want to implement a garbage collector on your own then you should go looking for an advanced compiler book instead of a tutorial.
Post reply on HN