Live data from Hacker News

What was wrong with SML?

blog.plover.com

61–70 of 82 posts

Re: What was wrong with SML?

#61

Earlier quoted context omitted.

It's the opposite, no? Basically every lazy language has some way to force evaluation, but in most strict languages laziness is never fully supported. Closest I can think of is a Scheme with continuations, but even then it takes some extra work. I know in CL even primitive laziness takes a lot of work and a code-walker, and whatever it's other flaws Common Lisp is at least adaptable.

I could be totally wrong, happy to be corrected. And I'm less familiar with lazy languages. My very basic impression of implementing laziness is just that you wrap all of your data structures/algorithms in functions that must themselves be called. Like everything is an iterator. See also: https://en.wikipedia.org/wiki/Lazy_evaluation#Simulating_laz...

Wrapping in bare functions gives you “call by name”, where

  let y = f(x) in g(y, y)
will compute f(x) twice. In effect you just evaluate function applications (and lets) by substituting a copy(!) of the argument text for every occurence of the variable in the body. It’s pretty easy for this to get exponentially bad.

If you want conventional lazy evaluation, that is “call by need”, you need to memoize: wrap everything in stateful functions (“thunks” in Haskell-implementer-speak, “promises” in Scheme-speak, but not the same as E/JavaScript-style async promises) that compute the result and save it on the first invocation, but then return it immediately. Apart from efficiency considerations (it’s better to use a tagged union of function pointer and result value instead of calling the function all the time) and a single conceptual wrinkle[1], that’s it.

Call-by-name and call-by-need obviously yield very different complexity, but are in fact equivalent regarding termination, and optimal: if any evaluation strategy terminates on a given term, so do they. The lovely recent paper “Call-by-need is clairvoyant call-by-value”[2] shows that lazy evaluation in fact never does more steps than call-by-need and in fact does a subset of them: those and only those that influence the final result. (The problem, of course, is that none of this addresses memory usage.)

Emulating eager evaluation with lazy can be done if you have seq: (a `seq` b) means “when this is forced, force (the outermost layer of) a, then replace yourself with b (which will then be forced as much as necessary)”: replacing f(e) with (let x = e in x `seq` f(x)) everywhere is not quite enough IIRC, but gets you most of the way there. In a dynamically-typed language, you can implement seq using some of the built-in strictness, like

  a `seq` b = if null(a) then b else b,
because null (or any other type discriminator) needs to force the outer layer of its argument (though I’m not sure if you can make this work in bare lambda calculus with functions only, oops); in a statically typed language, a polymorphic seq is AFAIU an unimplementable primitive, but if you need to translate a complete program you should always be able to implement seqT for every type T that occurs in it and use that (and every lazy language has seq anyway).

[1] https://srfi.schemers.org/srfi-45/srfi-45.html

[2] https://www.cs.nott.ac.uk/~pszgmh/clairvoyant.pdf, https://youtu.be/S69UOGqda8w

Re: What was wrong with SML?

#62

Earlier quoted context omitted.

It would be nice to have a language that could treat both strict and lazy evaluation as equally first-class, as opposed to having one be the default (whether "strict" as in ML or "lazy" as in Haskell) and the other only being expressed by syntactical kludges. This may well be possible by relying on logically-inspired features like polarity and focusing, and endowing data types with strict or lazy "natural" polarities…

Haskell is such a language. You can enable strict evaluation on a per module basis, or for an entire package.

Is that a Haskell or GHC feature?

Re: What was wrong with SML?

#63
post #62

Earlier quoted context omitted.

Haskell is such a language. You can enable strict evaluation on a per module basis, or for an entire package.

Is that a Haskell or GHC feature?

GHC extensions, StrictData (strict data structures) or Strict (strict evaluation for everything).

Re: What was wrong with SML?

#64

Earlier quoted context omitted.

I could be totally wrong, happy to be corrected. And I'm less familiar with lazy languages. My very basic impression of implementing laziness is just that you wrap all of your data structures/algorithms in functions that must themselves be called. Like everything is an iterator. See also: https://en.wikipedia.org/wiki/Lazy_evaluation#Simulating_laz...

Wrapping in bare functions gives you “call by name ”, where let y = f(x) in g(y, y) will compute f(x) twice. In effect you just evaluate function applications (and lets) by substituting a copy(!) of the argument text for every occurence of the variable in the body. It’s pretty easy for this to get exponentially bad. If you want conventional lazy evaluation, that is “call by need ”, you need to memoize: wrap everythin…

Right I forgot that everything is memoized. Thanks for the correction!

Re: What was wrong with SML?

#65
post #62

Earlier quoted context omitted.

Haskell is such a language. You can enable strict evaluation on a per module basis, or for an entire package.

Is that a Haskell or GHC feature?

Without extensions you can do it per-case via `seq`, see https://wiki.haskell.org/Seq (although it might get tricky because you might have to do it repeatedly because it only performs one “level" of evaluation)

There is also another GHC extension called bang patterns to request strictness on pattern matches.

The original bang (`!`) which is Standard Haskell can make fields of data structures strict, see: https://wiki.haskell.org/Performance/Data_types#Strict_field...

In general both lazy and strict languages can be strict or lazy. But the way it shows in the data types is different. A strict language can defer evaluation by adding a level of abstraction (instead of type `X` you have `() -> X`). A lazy language can force evaluation (it will have to evaluate at some point anyway) but you might not see it in the type. I’m not sure which one is better to be honest. Being able to infer laziness/strictness from the type is nice, but it also hinders interoperability.

Re: What was wrong with SML?

#66

I mentioned to Mark when I saw this, and he noted it in the addendum at the end, that calling Standard ML dead is a bit too much. I've written recently [0] about how active it surprisingly is. I also disagree that its failure to "succeed" has anything to do with syntax or semantics and solely that it doesn't have a Jane Street or any company publicly behind it. [0] https://notes.eatonphil.com/standard-ml-in-2020.html

I do wonder if differences in language governance models impact uptake. Being completely biased (having worked on the SML/NJ compiler a long while ago), I very badly want to see more adoption. There is definitely continuing activity with new (IFL award winning) LLVM backend work [1] and Manticore.

[1] http://cs.uchicago.edu/news/smlnj-overhaul/

Re: What was wrong with SML?

#67
post #9

I mentioned to Mark when I saw this, and he noted it in the addendum at the end, that calling Standard ML dead is a bit too much. I've written recently [0] about how active it surprisingly is. I also disagree that its failure to "succeed" has anything to do with syntax or semantics and solely that it doesn't have a Jane Street or any company publicly behind it. [0] https://notes.eatonphil.com/standard-ml-in-2020.html

I don’t think it succeeded or failed. Languages don’t need to be wildly popular in industry to be valuable. I personally like that industry ignores SML. Even for Ocaml I don’t use the Jane street core: I just use the stock language since it’s small and stable. I like that Jane street helps improve the core compiler though.

Haskell's motto is "avoid success at all costs", after all.

Re: What was wrong with SML?

#68

Earlier quoted context omitted.

Wouldn’t that last example be incorrect mathematically? For example, if the Int8 was -10 and the UInt16 was 10, what would that casting do? Would a better promotion be Int32 for both? Just curious, Julia is a language I’ve been very interested in using for a long time, just haven’t had the opportunity to sit down and learn yet.

> Wouldn’t that last example be incorrect mathematically? For example, if the Int8 was -10 and the UInt16 was 10, what would that casting do? Well.... Signed integer arithmetic and unsigned integer arithmetic do not differ. At all. The difference between an Int16 and a UInt16 is not in the 16 defined bits. It's in the infinite number of implicit bits representing place values above 2^15. Those bits are always 0 for t…

It took me a couple of readings to make sure I understood what you were saying, thanks for the reply. I think my misunderstanding was from not knowing Julia and thinking about promotion of values as having a permanent effect on the variables used, which isn’t what’s happening. As well, it requires the user to understand what they’re doing when they’re using an operator that uses automatic promotion, and to think about what they want to happen. For example, if Int8 = -10 and UInt16 = 5, and I’m expecting an answer of -5, then I’ll need to be more explicit to get the number I’m looking for. If I’m expecting 65530, then the implicit promotion works fine. Of course, this is no different from any other programming language that allows addition of differing types.

Great point on the path dependence.

Re: What was wrong with SML?

#69

IMHO Haskell's lazy evaluation has some significant disadvantages compared to SML's strict evaluation. In particular, lazy evaluation makes it difficult to find the performance bottlenecks in a particular piece of code or to determine the time complexity of an algorithm just by reading it. Furthermore, subtle changes in how a function is written (for instance, making a multiplication function not evaluate the right o…

It would be nice to have a language that could treat both strict and lazy evaluation as equally first-class, as opposed to having one be the default (whether "strict" as in ML or "lazy" as in Haskell) and the other only being expressed by syntactical kludges. This may well be possible by relying on logically-inspired features like polarity and focusing, and endowing data types with strict or lazy "natural" polarities…

Lazy evaluation order can be turned into strict one with less effort than vice versa.

Also, your suggestion will result in identical code being copied for different contexts. Consider lazy structures in OCaml and C#.

Re: What was wrong with SML?

#70

Earlier quoted context omitted.

It would be nice to have a language that could treat both strict and lazy evaluation as equally first-class, as opposed to having one be the default (whether "strict" as in ML or "lazy" as in Haskell) and the other only being expressed by syntactical kludges. This may well be possible by relying on logically-inspired features like polarity and focusing, and endowing data types with strict or lazy "natural" polarities…

I'd like to see more use of things that are more powerful than evaluation. For instance, in mathematical functions you can differentiate them, or invert them, and both of those are obviously useful in mathematical "metaprogramming". The only PL example I can think of is unification, which logic programming has as well as evaluation.

https://en.wikipedia.org/wiki/Pure_(programming_language)

A programming language where you can write programs to rewrite programs.

It appears that author of Pure is prone to come up with PL names that are quite unsearchable.

Post reply on HN