6 ms·

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

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, article says "particularly for programming pracitioners who didn’t learn it at school." -- Correct! I taught myself Basic, I taught myself a bit of x86 assembler, most importantly, I taught myself C. My working mental model of a computer is the C machine model. And even now, now that I know Ruby with its lambdas, I know that Ruby is written in C. And the Linux kernel. And Nginx (C++ maybe? Dunno). And on, and on. Show me the tutorial where I can build, _in C_ a bare bones working (tail recursion) implementation of the lambda calculus with type inference and dependent (algebraic?) types and I'll shake your hand and call you a champion. Closest I've seen is Make A Lisp - https://github.com/kanaka/mal https://github.com/kanaka/mal but I don't think it has the sweet types and tail recursion and other good stuff. PS: bonus points if Regexen are native type :) (Open to suggestions (I am))

mafribe 11y ago
Show me the tutorial where I can build, _in C_ a bare bones working (tail recursion) implementation of the lambda calculus with type inference and dependent (algebraic?) types Why would you want to do that? Type inference and dependent types don't go well together (already System F doesn't have type-inference), although it depends on the details of what you mean by dependent types. Tail recursion is a concept of compilation and does not show up in an interpreter. Note also that C has higher-order functions (via function pointers). The only relevant difference from lambda-calculus is that C functions must be named, cannot be nested and must exist at compile time. But conceptually these restrictions make little difference to the understanding of what lambda does: it creates a function. Finally writing something like that (to the extent that the requirements make sense) is gonna be really painful in C. If you understand the lambda-calculus well enough to know what dependent types are, the implementation language should not make much of a difference. I think the easiest way to learn the lambda-calculus program in a functional language. The second easiest way is to read the theory, after all the lambda-calculus as a calculus is incredibly simple, and you can hand-wave away the problems of bound-variable renaming. A slow-paced textbook like Hankin's "An Introduction to Lambda Calculi for Computer Scientists", and doing the exercises in the first few chapters should do the job.
- mkehrt 11y ago
  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 their containing scope. Variables mentioned in lambda bodies that are not parameters get their values from the definition scope, not the scope where they are used. In C function pointers, this issue doesn't even come up.
  - mafribe 11y ago
    I did point out the nesting and the requirement to name in C. The scoping follows immediately from beta-reduction (lambda x.M)N --> M[N/x] which I find very intuitive. I never had trouble understanding this, but maybe I'm overgeneralising from my own learning process. The real difficulty, or rather the real subtlety, is not nesting but name binding and the automatic renaming of bound variables where necessary. Having taught lambda-calculus to generations of students, that causes confusion with some students. And I think implementing a type-inferencer in C is going to be confusing because beauty of e.g. the W type-inference algorithm is drowned by orthogonal issues that C forces on you like memory management. Interpreters are best written in languages with pattern matching. So I prefer to bootstrap one's learning: get the basics of lambda-calculus, then implement a lambda-calculus interpreter and type-inferencer in a modern FP language. (As an aside, that's what SICP also does.)
    - Silhouette 11y ago
      The real difficulty, or rather the real subtlety, is not nesting but name binding and the automatic renaming of bound variables where necessary. If you're trying to understand what a closure does, perhaps that's true. If you're trying to understand how it does it, and you come from an imperative programming background where you know the ABIs for your languages like the back of your hand and are used to the kind of function set-up that always allocates space for local variables on the stack, there is a huge question of how all that lovely, neat theory is actually implemented in practice. Some of this discussion reminds me of the jokes about professors who prove that a solution to some elegantly expressed problem must exist, but then lead it to the grad students to actually find it...
agumonkey 11y ago
Here's a famous reddit comment about bootstrapping a language: http://www.reddit.com/r/programming/comments/9x15g/programming_thought_experiment_stuck_in_a_room/c0ewj2c http://www.reddit.com/r/programming/comments/9x15g/programmi... Also this was here not long ago https://news.ycombinator.com/item?id=9699065 https://news.ycombinator.com/item?id=9699065
- igravious 11y ago
  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...
  - agumonkey 11y ago
    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-9782866013554.html 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 :)
  - ufo 11y ago
    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.
exDM69 11y ago
> 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 a language like C would be a lot of work, a lot of effort going into memory management which is not at all useful towards the goal of learning how to implement a language. To give a practical example: last time I was working on a toy compiler using Haskell, I needed to calculate the strongly connected components in a directed graph to perform dependency analysis (rearranging "letrecs") that is required to do type inference. Had I been writing the compiler in C, it would have required a week's worth of engineering to get done. With Haskell, I could grab Data.Graph.SCC and be done in a few hours. Arguably I could have picked up a graph library in C, but then I'd have to spend time understanding how memory management works in the library and so on. I understand the appeal in using C or just an imperative programming language but quite frankly, that would really hurt the pedagogic aspects of a project like that. edit: Here's the relevant code if you're interested: https://github.com/rikusalminen/funfun/blob/master/FunFun/DependencyAnalysis.hs https://github.com/rikusalminen/funfun/blob/master/FunFun/De...
- Silhouette 11y ago
  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 Web about practical, real world techniques for implementing that sort of programming language feature, despite its ubiquity in functional languages and the increasing presence of -- or emphasis on -- higher order functions and related tools in mainstream imperative languages. The same could be said of many other non-trivial language features, say laziness, or various concurrency models. I think this is regrettable, because it creates a real barrier for anyone who's interested in learning about these features and maybe writing their own languages one day, but who doesn't come from an academic background where this kind of material was taught. It also makes it unnecessarily difficult for someone from an imperative programming background -- which is probably still the overwhelming majority of programmers -- to understand the real costs and performance implications of using these kinds of features.
locokoko 11y ago
I'm not sure if it satisfies all your needs, but Scheme 9 from Empty Space is a full R4RS Scheme implementation written from scratch in pure C (and Scheme). It has a heavily commented source code and a book, which is supposed to be quite good. Here are some key points from the website which the book addresses: - How does tail call elimination work? - How is macro expansion implemented? - How is arbitrary precision arithmetics implemented? Enjoy! http://t3x.org/s9book/index.html http://t3x.org/s9book/index.html
- igravious 11y ago
  Thank you!
jrapdx3 11y ago
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/ http://www.call-cc.org/
- igravious 11y ago
  Another fine suggestion, thanks!
swah 11y ago
That's something I liked about jonesforth (https://raw.githubusercontent.com/AlexandreAbreu/jonesforth/master/jonesforth.S https://raw.githubusercontent.com/AlexandreAbreu/jonesforth/...) ! but its not a lambda calculus interpreter I guess.
- igravious 11y ago
  Not what I had in mind but intriguing nonetheless.
tel 11y ago
If LLVM is good enough for you... http://www.stephendiehl.com/llvm/ http://www.stephendiehl.com/llvm/ and http://dev.stephendiehl.com/fun/ http://dev.stephendiehl.com/fun/ (in progress)
- igravious 11y ago
  Thank you, indeed it is :)
sklogic 11y ago
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://combinatorylogic.wordpress.com/2015/01/14/bootstrapping-a-compiler/ https://combinatorylogic.wordpress.com/2015/01/14/bootstrapp...
- igravious 11y ago
  That's a bit defeatist, we don't know until we try!
  - sklogic 11y ago
    Ok, take a look at Hugs, it's mostly done on a C level.
chewie123 11y ago
The first language I learned was C. I don't claim to be an expert, but I'm comfortable enough with it that I can hack on an OS kernel with C. I have also learnt how to write compilers for simple languages (mostly from Appel's book). Through reading the book, I picked up ML. At first it was an uncomfortable transition from C, but I eventually loved writing ML code. Strong typing eliminates a lot of common errors, and the compiler really feels like a friend that's watching over you. Later on, I decided to pick up Haskell. Frankly it was a lot harder to get used to it (I still can't say I understand Haskell) because of how side effects in Haskell are made much more explicit than either C or ML. But after about a year and a half, I can now code comfortably in Haskell. And if someone let me choose a language that I can only code in for the rest of my life, it might actually just be Haskell. But ML and Haskell are not without their problems. C and functional languages like ML/Haskell have different problem domains. Haskell, being (almost) pure, is really good at modeling side-effect free computations. The compiling process is really a translation process (thus a computation), and it's easier to model it in Haskell. It is quite easy to mess things up in a language like C where side-effects show up everywhere, although if you're disciplined enough you could probably translate a Haskell program into C with some modifications. But Haskell/ML is definitely not for everything. I would not write a kernel in Haskell (although I do know people who have done it). With the runtime problem aside, it doesn't give me enough control over the bare metal it's running over (or it's probably I just don't know it well enough yet). I can't layout things exactly the way I want with Haskell, but with C, I can build structs, cast integers into pointers (might not be a good idea, but sometimes necessary when you're dealing with a kernel) and so on. With C it feels like you're the creator, taking care of everything, hence, you have much more responsibility on your shoulder. But with Haskell, the compiler takes care a lot of things for you if you're in the right problem domain, and it lets you focus on abstractions and the problem itself. Anyway, just a little thought. I love Haskell and C equally, and they're both absolutely wonderful languages. But try to keep yourself open and just try a little bit of new things at a time. Pretty soon you might find yourself designing compiler for your own language in Haskell (or C)!

mafribe 11y ago

Show me the tutorial where I can build, _in C_ a bare bones working (tail recursion) implementation of the lambda calculus with type inference and dependent (algebraic?) types Why would you want to do that? Type inference and dependent types don't go well together (already System F doesn't have type-inference), although it depends on the details of what you mean by dependent types. Tail recursion is a concept of compilation and does not show up in an interpreter. Note also that C has higher-order functions (via function pointers). The only relevant difference from lambda-calculus is that C functions must be named, cannot be nested and must exist at compile time. But conceptually these restrictions make little difference to the understanding of what lambda does: it creates a function. Finally writing something like that (to the extent that the requirements make sense) is gonna be really painful in C. If you understand the lambda-calculus well enough to know what dependent types are, the implementation language should not make much of a difference. I think the easiest way to learn the lambda-calculus program in a functional language. The second easiest way is to read the theory, after all the lambda-calculus as a calculus is incredibly simple, and you can hand-wave away the problems of bound-variable renaming. A slow-paced textbook like Hankin's "An Introduction to Lambda Calculi for Computer Scientists", and doing the exercises in the first few chapters should do the job.

mkehrt 11y ago
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 their containing scope. Variables mentioned in lambda bodies that are not parameters get their values from the definition scope, not the scope where they are used. In C function pointers, this issue doesn't even come up.
- mafribe 11y ago
  I did point out the nesting and the requirement to name in C. The scoping follows immediately from beta-reduction (lambda x.M)N --> M[N/x] which I find very intuitive. I never had trouble understanding this, but maybe I'm overgeneralising from my own learning process. The real difficulty, or rather the real subtlety, is not nesting but name binding and the automatic renaming of bound variables where necessary. Having taught lambda-calculus to generations of students, that causes confusion with some students. And I think implementing a type-inferencer in C is going to be confusing because beauty of e.g. the W type-inference algorithm is drowned by orthogonal issues that C forces on you like memory management. Interpreters are best written in languages with pattern matching. So I prefer to bootstrap one's learning: get the basics of lambda-calculus, then implement a lambda-calculus interpreter and type-inferencer in a modern FP language. (As an aside, that's what SICP also does.)
  - Silhouette 11y ago
    The real difficulty, or rather the real subtlety, is not nesting but name binding and the automatic renaming of bound variables where necessary. If you're trying to understand what a closure does, perhaps that's true. If you're trying to understand how it does it, and you come from an imperative programming background where you know the ABIs for your languages like the back of your hand and are used to the kind of function set-up that always allocates space for local variables on the stack, there is a huge question of how all that lovely, neat theory is actually implemented in practice. Some of this discussion reminds me of the jokes about professors who prove that a solution to some elegantly expressed problem must exist, but then lead it to the grad students to actually find it...

agumonkey 11y ago

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

igravious 11y ago
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...
- agumonkey 11y ago
  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-9782866013554.html 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 :)
- ufo 11y ago
  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.

exDM69 11y ago

> 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 a language like C would be a lot of work, a lot of effort going into memory management which is not at all useful towards the goal of learning how to implement a language. To give a practical example: last time I was working on a toy compiler using Haskell, I needed to calculate the strongly connected components in a directed graph to perform dependency analysis (rearranging "letrecs") that is required to do type inference. Had I been writing the compiler in C, it would have required a week's worth of engineering to get done. With Haskell, I could grab Data.Graph.SCC and be done in a few hours. Arguably I could have picked up a graph library in C, but then I'd have to spend time understanding how memory management works in the library and so on. I understand the appeal in using C or just an imperative programming language but quite frankly, that would really hurt the pedagogic aspects of a project like that. edit: Here's the relevant code if you're interested: https://github.com/rikusalminen/funfun/blob/master/FunFun/DependencyAnalysis.hs https://github.com/rikusalminen/funfun/blob/master/FunFun/De...

Silhouette 11y ago
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 Web about practical, real world techniques for implementing that sort of programming language feature, despite its ubiquity in functional languages and the increasing presence of -- or emphasis on -- higher order functions and related tools in mainstream imperative languages. The same could be said of many other non-trivial language features, say laziness, or various concurrency models. I think this is regrettable, because it creates a real barrier for anyone who's interested in learning about these features and maybe writing their own languages one day, but who doesn't come from an academic background where this kind of material was taught. It also makes it unnecessarily difficult for someone from an imperative programming background -- which is probably still the overwhelming majority of programmers -- to understand the real costs and performance implications of using these kinds of features.

locokoko 11y ago

I'm not sure if it satisfies all your needs, but Scheme 9 from Empty Space is a full R4RS Scheme implementation written from scratch in pure C (and Scheme). It has a heavily commented source code and a book, which is supposed to be quite good. Here are some key points from the website which the book addresses: - How does tail call elimination work? - How is macro expansion implemented? - How is arbitrary precision arithmetics implemented? Enjoy! http://t3x.org/s9book/index.html http://t3x.org/s9book/index.html

igravious 11y ago
Thank you!

jrapdx3 11y ago

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/ http://www.call-cc.org/

igravious 11y ago
Another fine suggestion, thanks!

swah 11y ago

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

igravious 11y ago
Not what I had in mind but intriguing nonetheless.

tel 11y ago

If LLVM is good enough for you... http://www.stephendiehl.com/llvm/ http://www.stephendiehl.com/llvm/ and http://dev.stephendiehl.com/fun/ http://dev.stephendiehl.com/fun/ (in progress)

igravious 11y ago
Thank you, indeed it is :)

sklogic 11y ago

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://combinatorylogic.wordpress.com/2015/01/14/bootstrapping-a-compiler/ https://combinatorylogic.wordpress.com/2015/01/14/bootstrapp...

igravious 11y ago
That's a bit defeatist, we don't know until we try!
- sklogic 11y ago
  Ok, take a look at Hugs, it's mostly done on a C level.

chewie123 11y ago

The first language I learned was C. I don't claim to be an expert, but I'm comfortable enough with it that I can hack on an OS kernel with C. I have also learnt how to write compilers for simple languages (mostly from Appel's book). Through reading the book, I picked up ML. At first it was an uncomfortable transition from C, but I eventually loved writing ML code. Strong typing eliminates a lot of common errors, and the compiler really feels like a friend that's watching over you. Later on, I decided to pick up Haskell. Frankly it was a lot harder to get used to it (I still can't say I understand Haskell) because of how side effects in Haskell are made much more explicit than either C or ML. But after about a year and a half, I can now code comfortably in Haskell. And if someone let me choose a language that I can only code in for the rest of my life, it might actually just be Haskell. But ML and Haskell are not without their problems. C and functional languages like ML/Haskell have different problem domains. Haskell, being (almost) pure, is really good at modeling side-effect free computations. The compiling process is really a translation process (thus a computation), and it's easier to model it in Haskell. It is quite easy to mess things up in a language like C where side-effects show up everywhere, although if you're disciplined enough you could probably translate a Haskell program into C with some modifications. But Haskell/ML is definitely not for everything. I would not write a kernel in Haskell (although I do know people who have done it). With the runtime problem aside, it doesn't give me enough control over the bare metal it's running over (or it's probably I just don't know it well enough yet). I can't layout things exactly the way I want with Haskell, but with C, I can build structs, cast integers into pointers (might not be a good idea, but sometimes necessary when you're dealing with a kernel) and so on. With C it feels like you're the creator, taking care of everything, hence, you have much more responsibility on your shoulder. But with Haskell, the compiler takes care a lot of things for you if you're in the right problem domain, and it lets you focus on abstractions and the problem itself. Anyway, just a little thought. I love Haskell and C equally, and they're both absolutely wonderful languages. But try to keep yourself open and just try a little bit of new things at a time. Pretty soon you might find yourself designing compiler for your own language in Haskell (or C)!