Slashdot Mirror

If you don't think coroutines aren't a form of goto, [...]

Lambda: The Ultimate Goto

There is no language / system on the planet that has such a feature. Except Java 9.

I'm pretty sure that whatever modularity feature you can come up, Scheme most likely already has it.

There is no language / system on the planet that has such a feature. Except Java 9.

I'm pretty sure that whatever modularity feature you can come up, Scheme most likely already has it.

Given his major influence on:

C
Java
Common Lisp
Scheme

And, as a throwaway on his Oracle bio page:

He designed the original EMACS command set and was the first person to port TeX.

I'd argue instead that the machine being imperative is the problem. It's 2011 and we still just have a gigantic array of words that we can move an instruction pointer through... See e.g. Lambda: The Ultimate Opcode for an alternative approach to system design.

Nothing really prevents us from building an expression reduction machine (with an imperative IO processor, naturally... it is nice to interact with the external environment) nowadays. I'm not sure where the rest of the project went, but there was a project involving Ivan Sutherland at Berkeley that built a purely parallel processor. In FLEET there is no notion of a linear program nor of linearly addressable memory--programs become dependency graphs that are reduced.

Basically, the machine being a really fancy Turing machine is an accident (in the formal sense), and not at all essential to computation. It happens to work pretty well and certainly will be dominant for a long time, but forever? Probably not, expression reduction machines can be clockless, massively parallel (as in executing thousands of operations simultaneously), &c -- which means smaller dies, lower power usage, ....

Another thing to think about is that this is for freshman. I'm suspecting that anyone who can get into CMU has a pretty good grasp on Algebra... and probably the differential/integral calculus. Functional programming is a natural extension of the mathematics the students have already learned whereas OO is an entirely different paradigm which presents a barrier to actually learning the essence of computing science.

That, and CMU is the Land of SML. The mantra there is that OO is a hack--an artificial conglomeration of several orthogonal concepts: modules, protocols, records, polymorphic functions, &c. Under that philosophy OO is just another obsolete intermediate step in the evolution of computer language.

Please show me the interpreted byte code langauge/runtime that has never had a buffer overflow exploit.

What about this one?

I really like what Guy Steele Jr. wrote about this in Lambda: The Ultimate Goto:

One can argue quite strongly that there are so large a number (possibly infinite) of distinct useful control constructs that no one language could embody them all, and that therefore no language designer should be so conceited as to think he has encompassed all desirable constructions in a given language. By this reasoning, the omission of CASE, or Dahl loops, or event constructions, or whatever else is not a matter of neglect, but of necessity: you just cannot foresee them all.

...

Until a much more advanced theory of programming is devised, designers of practical languages are well advised to leave in "ugly hooks" like GOTO, even if also discouraging their use except in emergencies. After all, using GOTO to simulate a peculiar control construct is probably preferable to a convoluted perversion of a more specialized construct.

.

I would recommend Scheme. Not because I recommend you program in it, but because it will change the way you think about programming and programming languages, especially if you also read Structure and Interpretation of Computer Programs (affectionately known as SICP).

Scheme is a small programming language, so you can learn it relatively quickly. This allows you time to read some of the literature about Scheme. And SICP. This will give you insight in the design of programming languages, and how features (like loops, class systems, etc.) can be implemented in terms of simpler constructs, given the right primitives and powerful enough abstractions.

And, in the end, it's the primitives and abstractions that matter. Given the right primitives and abstractions, you can mold your programming language to be anything you want. Scheme, and other languages in the larger Lisp family, are very good at this. That's probably why they are still around, despite tracing their roots back to the 1950s. Other languages are not so good at it, and you will end up writing lots of boilerplate and repetitive code if you program in them.

I could go on and on and list all the insights Scheme has provided me with, but I'd say you go see for yourself. SICP is a good place to start, because it starts at the basics (so you don't need to know Scheme before you start), but gets up to speed really quickly (so you won't get bored). You could also try my Scheme tutorial.

Note that all this is about the 5th revision of Scheme (known as R5RS). R5RS lacks many primitives that would make it useful for Real World applications (just to name one thing, there is nothing about networking). Many implementations of Scheme (and there are many) provide various such primitives - but that's not the point here. The point is about the fundamentals of programming.

As a final remark, if you are used to Java's "everything is part of a class" curfew, Scheme will provide a refreshing change of perspective. R5RS doesn't even have classes. Instead, the focus is on procedures. So you will be decomposing your system in terms of what it does, more than in terms of what real, imaginary, or "forced on you by the programming language" objects it acts on. In my experience, this leads to many small functions, each doing a simple thing, which can then be composed to build your system - or perhaps a very different system that happens to re-use part of the functionality. Unlike Java's classes, each containing a bunch of method, each of which contains gobs of repetitive code...try to adapt _that_ to do something similar, but slightly different. Again, it's all about primitives and abstractions.

The the construction you are describing is a closure; indeed they rock and show up in several functional languages. The power of the abstraction (more than just iterators) was well explored in the "Lambda the ultimate..." papers in Scheme in the 1970s. They may well included in Java 1.7 and a prototype is even available (examples here and here). .

Scheme is a language that every programming language enthusiast should know. Being both simple and flexible, it's suitable for communicating and explaining all kinds of concepts. A lot of books and papers are about Scheme or use Scheme for examples or teaching (see Readscheme.org). Scheme also pioneered some of the concepts in modern programming languages (such as lexical scoping), as well as several uncommon features (such as hygienic macros and first-class continuations). There are many Scheme implementations, some tiny, some slow, some fast, some with extensive libraries, some which interface to other programming languages, etc. etc.

Here's a neat project that addresses the points you've mentioned: how do you know your programming language implmentation is correct.

That project featured a verified compiler for a high-level language that created assembly code.

No C in there at all!

Since when can you write a domain specific language/interpreter in just about a day or two???

This book teaches functional programming as a way of thinking and problem solving, using Haskell, the most popular purely functional language. Rather than using the conventional mathematical examples commonly found in other programming language textbooks, the author draws examples from multimedia applications, including graphics, animation, and computer music, thus rewarding the reader with working programs for inherently more interesting applications. Aimed at both beginning and advanced programmers, this tutorial begins with a gentle introduction to functional programming and moves rapidly on to more advanced topics. An underlying theme is the design and implementation of domain specific languages, using three examples: FAL (a Functional Animation Language), IRL (an Imperative Robot Language), and MDL (a Music Description Language)...

Check out Lava at Xilinx, Lava at Chalmers, Hawk, the Hardware Design and Synthesis section of Haskell Application Papers on readscheme.org.
The links above lead to programs that are used by companies like Xilinx and Intel to help designers build better chips with existing technology. There are more interesting hardware approaches being investigated with Haskell. Two that come to mind immediately are quantum computing and dataflow-based simulations more related to the Lustre and Lucid languages. Though I do know of some unfinished research in the dataflow/hardware design area, I can't find any published papers at the moment.

One day I'll get around to buying a PCI card with a FPGA and use Haskell to turn it into a reprogrammable coprocessor. So many cool things to learn, so little time...

"The Web has been polluted by the ever increasing crop of "web applications." HTTP is not designed for session-based, interactive applications."

Or one could start using functional languages as part of the solution (Of which 'Curl' is one).

One of the original designers of Scheme?
Primary author of Common Lisp the Language?
Co-author of C: A Reference Manual, which was the bible on writing portable C?
Co-author of The Java Language Specification?

If contributing to the design of four major programming languages doesn't get you into the top twenty, how about designing the original EMACS command set? There may be people who are better known for contributions to one language or one toolset, but it's hard to beat him for sheer breadth.

It would be great, if instead, I could hook into the compiler and tell it exactly how it should handle vectors.

Well of course that's what templates are. Yes, their syntax is horrendous but that's what comes of trying to wedge the concept into the existing crannies of C syntax (or when, as Stroustrup remarked to me once, "the ecological niche was already polluted").

If you hanker for a language in which metasyntactic extension is natural, you need Lisp macros (or here and here for a more complex example), Scheme "hygenic" macros or the CLOS MOP.

But if you really want to consider "hooking into the compiler" as you say then you should look at the reflective programming work, the ground work for which was laid down almost 25 years ago by Brian Cantwell Smith and was even implemented, by me and others, back then. Although a lot of work continued in this area that vein pretty much got mined: unless you can think up a completely new control structure there's not a huge amount more you can do with such a system than you could with a normal metasyntactic extension mechanism.

HTH
-d

There is also the paper "The Art of the Interpreter" by the same author (one of the Sussmans) - other papers by Sussman available from http://library.readscheme.org/page1.html. The Art of the Interpreter is all about implementing mini-languages in interpreters. Using Lisp. Making an interpreter in Lisp is easy, since the whole language runtime gives you an interpreter, so you just define your parser and your evaluator...

I know what you mean, since I've picked up a lot of theory in similar ways over the years. Along those lines, Lambda the Ultimate is a good place to get pointers to a variety of current research. It's worth getting at least some of the theory closer to its source. Have you read SICP, for example? That was one of the books that got me back into theory after many years out of CS at university (the CS I did was pretty lame - mainly learnt Pascal, very little real CS theory).

If you're into that sort of thing, though, SICP is just a gateway drug. Lambda calculus, type inferencing, type theory in general, and much, much more follows, and pretty soon all the mainstream languages are looking pretty pale... It all does give some good criteria by which to compare languages, though, and helps avoid being limited in one's thinking by the language one happens to be using.

BTW, I agree about not teaching closures in Perl to newbies. Perl and Python both have enough hardcoded ways to do things that you don't need to rely on closures, except to be perverse. The more important concept for useful programming is higher-order functions, since they provide a capability that's directly useful in Perl (or any language), and closures can be introduced in that context.

You've probably come across this before, but here's a nice piece about ML's type system from a partly Perl perspective.

Are there any VMs currently, for Java, Python or some other language, that can execute each thread one VM instruction at a time?

if you have a language that optimizes tail-calls, you could have the front-end of the language convert the separate threads of execution into continuation-passing style, and then execute the code one continuation at a time, simulating threading on a VM level. if i remember correctly, the scheme48 VM could do that kind of threading, though on a coarse level.

in CPS a function decomposes into a sequence of more primitive functions, each returning a continuation, ie. a handler for computation yet to come. for a simplified example, the evaluation of (+ (* 2 3) (* 4 5)) would evaluate (* 2 3) into 6 and return a continuation that evaluates (+ 6 (* 4 5)), which in turn would evaluate (* 4 5) into 20 and return a continuation that evaluates (+ 6 20), and that would finally evaluate to 26.

but the point here is that one could explicitly halt the evaluation after receiving the first continuation, store it on the queue, and go off and compute something else. after a while you can come back, pop the continuation off the queue, and pick up the computation where you left off.

the problem with such a setup is that it makes optimization difficult. i'd suggest looking at the CPS for more details...

You couldn't be further from the truth. Someone's already mentioned CiteSeer. I've read and downloaded hundreds of papers from there. Google is great for tracking down papers, too.

Another nice resource is library.readscheme.org. It's Scheme-specific, but Scheme is the root of much research about programming languages and the underlying concepts - it pretty much spawned the field of functional programming.

The biggest barrier to entry for this sort of stuff is your own existing knowledge. There's no pill you can take to pick it all up overnight. You have to work hard at it. This is the real reason to go to a real universities - not to learn how to program in the language du jour, but to learn about what some very smart people have already figured out over decades, centuries, millenia, and to learn how to think like those people.

There aren't many shortcuts here. It doesn't help to be told that there's a simple solution to the problem you're working on, if it involves a network of deep concepts you've never heard of and are totally unfamiliar with. To take some examples from functional programming: closures, continuations, continuation passing style, fold operators, polymorphic type inference... If you don't know what all those things mean, and can't use them in your code, you're unnecessarily limiting yourself and denying yourself leverage that can help get big, complicated things done more quickly, with less fuss.

One way to start out is to learn some advanced languages. Scheme is a good starting point because there's so much tutorial literature for it. You can pick up the computer science concepts as you go along. Read Structure and Interpretation of Computer Programs (SICP) and How to Design Programs (HTDP). Join the ACM. There's so much stuff out there, go look for it, and apply yourself!