Implementing Scheme in F# | Hacker News Reader

Implementing Scheme in F#

blogs.msdn.com

This is interesting; reminds me of lisp in Haskell http://www.defmacro.org/ramblings/lisp-in-haskell.html

Is there any practical use for these kind of projects? I imagine it might make make it easier to write multithreading programs when the lisp is implemented in a purely functional language. At least Haskell seems to have decent multithreading support, I don't know about F#. Are there any other reasons other than curiosity to do this?

IMHO embedding in F# or Haskell isn't particularly useful, but embedding in C is pretty neat. You can add scripting support to an application in a day or two. This was gimp's trick. Arguably it is emacs trick too. Nowadays, It's probably better to use something like guile or lua.

Beyond that, if you're on .Net it's trivial to add scripting to your application via IronPython or IronRuby (or any other .Net language, I suppose).

or Tcl... or Muddy Scheme http://wiki.tcl.tk/25512

are all languages implementable in every other language?

Nope. For example, you can't parse HTML or source code with a regular expression, because of limitations on how the language itself works (it doesn't have the ability to parse nested structures).

However, in practice, most common programming languages can be used to implement other programming languages...it's just a matter of how much/little code you're going to need to write to do it. Using this article as an example, it would be much easier to implement Scheme in F# than it would be in C#, due to some features of the F# language.

Not all languages, but many: http://en.wikipedia.org/wiki/Turing_completeness#Examples

From that wikipedia page: "The untyped lambda calculus is Turing-complete, but many typed lambda calculi, including System F, are not."

Anyone have any details about System F not being turing complete? Is it not straightfoward to implement an untyped lambda calculus in a typed one?

Reply on news.ycombinator.com