dogfishbar

Retired CS prof here (from a below (ok way-below) top-4 program). There is no longer a job market for CS grads outside of top-4? Is this true? I had no idea, as I understood it, CS major numbers are still rising.

Sure, OCaml is great as are the other dialects of ML. I'm hoping that someone will weigh in with a compelling case for laziness everywhere or dynamic dispatch everywhere, other than pre-existing infrastructure, libraries, etc.

Thanks for letting us tag along. What I'd like to hear are your thoughts on the Groucho Marx cigar question: laziness is useful every now and then, but in lazy languages like Haskell you pay for it everywhere. The same is true for dynamic dispatch, it's needed when working with values of sum type. But like laziness, it isn't needed wall-to-wall but in dynamically-typed languages, you pay for it everywhere. Give me a call-by-value language with arrow and sum types and I can pay as I go. [edit: added "arrow and"]

Life goal: outlive dynamic type checking.

Lyn T. is one of a small handful of the best CS educators on the planet. Good job HN!

I spent a lot of time on this. See M-LISP: a representation-independent dialect of LISP with reduction semantics, TOPLAS, 1992, the relevant bit is in section 2.

It's true that J. McCarthy had only a passing familiarity with LC. M-expression LISP, as it was originally conceived, was all about first-order recursion schemes over S-expressions. But due to a very simple error in the base case of an inductive definition, LISP 1.0 "featured" or "supported" higher-order functions, ala LC.

Robert Heinlein's nephew Terrance Heinlein (Terry) is a brilliant architect. Bob Muller

M-LISP: a representation-independent dialect of LISP with reduction semantics

In this paper we introduce M-LISP, a dialect of LISP designed with an eye toward reconciling LISP's metalinguistic power with the structural style of operational semantics advocated by Plotkin [28]. We begin by reviewing the original definition of LISP [20] in an attempt to clarify the source of its metalinguistic power. We find that it arises from a problematic clause in this definition. We then define the abstract syntax and operational semantics of M-LISP, essentially a hybrid of M-expression LISP and Scheme. Next, we tie the operational semantics to the corresponding equational logic. As usual, provable equality in the logic implies operational equality. Having established this framework we then extend M-LISP with the metalinguistic eval and reify operators (the latter is a nonstrict operator that converts its argument to its metalanguage representation). These operators encapsulate the metalinguistic representation conversions that occur globally in S-expression LISP. We show that the naive versions of these operators render LISP's equational logic inconsistent. On the positive side, we show that a naturally restricted form of the eval operator is confluent and therefore a conservative extension of M-LISP. Unfortunately, we must weaken the logic considerably to obtain a consistent theory of reification.

I have been teaching OCaml in CS1 at Boston College for 4 years now. Of hundreds of students who went on to learn Java in our CS2 course (joining Python-trained students from other sections of CS1), nearly unanimous happy campers. When OCaml is their first programming language, they're good to go.

Nice article! But you have a typo.

(λx.x y)

does not return y, though

(\x.x) y

does.

I'm teaching a sophomore level web apps course in the spring semester. I'm torn between doing what I think will help them land an internship this summer or land a real job and on the other hand, teaching them something like Elm which makes much more sense to me. Anybody willing to weigh in on these? It would be greatly appreciated. 1. Would a course focussing on just the front end using HTML + CSS + JS + React be reasonable? 2. Is it reasonable to deal only with the front end? 3. If the answer to 2. is no, then what is most reasonable and likely to endure technology for the back end?

Akkartik: the paper of mine that you cited has a bunch of theorems following the program laid out by Gordon Plotkin in the single best paper I ever read: "Call-by-Name, Call-by-Value and the Lambda Calculus" - a truly profound piece of work that is still worth careful study. But my TOPLAS paper on the topic of LISP can safely be skipped --- the punch-line, as I said, is that the amazing genius John McCarthy messed up the base-case for the definition of his hat(.) function. Stuff happens. In the process, he invented (the very buggy) LISP which was the essential bridge between the true source of sensible computation --- (typed) lambda calculus --- and modern and future software.

(And for what it's worth (ha!) the architect for my present residence was the amazing Terry Heinlein, nephew of Robert Heinlein (of "grok" fame.))

Thank you for reminding me, McCarthy also invented COND which eventually led to the great modern pattern matching forms.

An ironic side-story of this that may or may not be of interest:

Because QUOTE was mis-defined, McCarthy had to hack his definition of APPLY/EVAL to get it to work. One consequence of this hacking was that the S-expression LISP "defined" by his version of APPLY/EVAL was a higher-order language while the M-expression LISP that he was attempting to model was strictly first-order. So in his S-expression LISP he could write the MAP function (called "mapcar" back in the day) but the syntax of M-expressions leaves no way to express MAP.

I find it so ironic that it took this little representation error to lead to LISP having the essential property of lambda calculus. (Guy Steele fixed most of the trouble with the grammar and introduced proper lexical scoping in Scheme but he didn't catch the quote bug.) It's also fair to say that M-expression LISP wouldn't have changed the world as S-expression LISP did.

I don't know if Paul Graham reads HN but Paul once wrote a book on macros in LISP. As far as I know, he doesn't know this story about QUOTE. It doesn't seem to have slowed him down.

Fair enough, I felt I was droning on but it's true that I didn't show the key mistake. Here it is.

If you want to represent an arbitrary M-expression as an M-expression, it's most natural to use S-expressions for the representation language, these are the -values- in M-expression LISP. (In lambda calculus we have more choices, normal-forms or weak-head normal-forms). McCarthy defined hat(.), naturally enough, by induction on the structure of M-expressions. For each M-expression, we need an S-expression representation. (Note that we use uppercase symbols for the symbolic constants and lowercase symbols for identifiers.) Here goes:

hat(S) == (QUOTE S)

hat(x) == X

hat(if[M1; M2; M3]) == (IF hat(M1) hat(M2) hat(M3))

etc..

But HOLD ON! The S-expressions have inductive structure(!). The definition of hat(S) should have been:

hat(A) == (SYM A)

hat(()) == (NIL)

hat((S1 . S2)) == (PAIR hat(S1) hat(S2))

There are sensible mathematical properties that this latter representation has that the former doesn't. It's a bit of a long story. But the bottom line is that QUOTE, was defined erroneously. (And John McCarthy burst out laughing when I explained it to him.)

RM

apologies, more typos.

I published a paper on this in the ACM Transactions on Programming Languages and Systems (TOPLAS) back in 1992. The title was "M-LISP: A Representation-independent Dialect of LISP with Reduction Semantics". No need to read it, the punch-line is above.

Fixed yet another typo.

OK, you asked! LISP was originally developed as a language for writing recursive functions of symbolic expressions (S-expressions). It was roughly based on lambda calculus, the language developed by Alonzo Church. But roughly is the key word. S-expressions are given by the context-free grammar:

S ::= A | [] | (S . S)

One can write data structures this way and lists by using the abbreviation:

(S1 . (S2 . ( ... ( SK . ()) ...))) == (S1 S2 ... SK)

The terms that manipulated these S-expressions were called M-expressions. They were first-order terms. McCarthy's key idea was to use a conditional in conjunction with a label form to define recursive functions (in the service of various AI applications). The M-expressions were defined roughly as follows:

M ::= S | x | if[M; M; M] | f[M; ...; M]

f ::= lambda[[x1; ...; xn]; M] | label[g; M]

(I'm not 100% confident that I remember the exact details on this syntax but the idea is correct!)

McCarthy wanted to show that his new language was Turing-complete. So he wanted to exhibit a universal function APPLY (derivable from f above) such that for any function f and arguments M1; ...; Mk such that f[M1; ...; Mk] evaluates to S-expression S, well, given a representation of f[M1;...;Mk], lets call it, hat(f[M1;...;Mk]), well

APPLY[hat(f); hat(M1);...;hat(Mk)] would evaluate to hat(S). This is pretty much a standard formulation of the recursion-theoretic argument. In order to close the sale, McCarthy had to exhibit such an APPLY and also the hat(.) function. Sadly for all of us LISP lovers (!) he botched the definition of hat(.)! It left people utterly confused for 30+ years. Such a shame.

Fixed a couple of typos. Sorry! Fixed one other typo! It's been a while...

The definition of quote is broken. I personally explained it to John McCarthy. He agreed.

Ha! LISP macros and read both work because of a very simple bug in the original definition of LISP. Don't even bother with it or Scheme or Racket --- they're all utterly broken and needlessly confusing!