Lambda the Ultimate - Comments

IIRC some old versions of

Alexandre Richer — Fri, 25 Jul 2008 01:06:06 -0400

IIRC some old versions of Lisp had a (comment "string") expression which meant the same as () ie nil but was a comment kept in the AST. Well, Emacs Lisp and Python have documentation strings, e.g.: From the GNU Emacs Lisp Reference Manual:

  (defun capitalize-backwards ()
            "Upcase the last letter of a word."
            (interactive)
            (backward-word 1)
            (forward-word 1)
            (backward-char 1)
            (capitalize-word 1))
               => capitalize-backwards

You can then access the documenation string at runtime by using (documentation 'function) in Emacs Lisp or print function.__doc__ in Python.

And arguably...

Matt Hellige — Thu, 24 Jul 2008 23:26:45 -0400

And arguably, static languages would be improved if they more commonly allowed the recognition that all of these nil values are in some sense the same. And this is exactly the kind of thing that generic programming is all about.

Apologies to Philippa if I'm off base here, but...

Matt M — Thu, 24 Jul 2008 23:06:04 -0400

I think the idea is that *? is a kind variable. Consider the kind of Set. It's not * -> *, but EQ -> *, where EQ is the subkind of types that implement equality. As a variable I think it might be better to give it a name, so I'll use *A (imagining *B, *C, etc):

class Functor (f :: *A -> *) where
	fmap :: ((a :: *A) -> (b :: *A)) -> f a -> f b

The kinds of types a and b in the signature of fmap should probably be inferred from the use of f, so the signature of fmap could be the usual one. This feels like a can of worms, but I think Philippa's suggestion to restrict the construction of Sets to the appropriate kind of type sounds like "the right way" to proceed.

Compiling bitC

Gregory Propf — Thu, 24 Jul 2008 23:03:16 -0400

I just got what I think is your latest release via rsync (I don't have Hg) It needed a couple dependencies I didn't have that the configure script didn't tell me about. They were the ici stuff (uchar.h) and the Boehm gc package. Also I had to symlink x86_64 to the i386 directory to get it to find mkclosure.c. Compiled alright after that. This is on an AMD64 of course.

yes, essential like 0

Thomas Lord — Thu, 24 Jul 2008 20:24:02 -0400

Nil-like values are essential like 0 because we like to define data structures inductively. "A list is the empty list or...", "A natural number is 0 or ...", etc. It's just handy to have around.

The question is, do you want just one? or many?

The statically typed languages generally say "many": you explicitly define a new one for each new type.

Dynamic languages, for some reason, mostly fixate on having "one true nil" so that a nil list is EQ? to a nil tree. (Scheme is a mild exception. It somehow settled on having "two true nils" ("()" and "#f") which divide among themselves the properties of a "one true nil".

The "win" of "one [or two] true nil[s]" in a dynamic language is that it allows easier abstraction of patterns of induction. For example, one could write a common-lisp function "MAP-SEQUENCE" that works on all sequence types using generic functions to access elements and build the result -- using "nil" to stand for the "end of sequence" in all cases.

The "lose" is that a limitation to only one or two true nils gets in the way of composing data types. For example, suppose that I have an associative data structure (say, a hash table). I wish to define that values stored in the table are either lists (possibly empty) or values (possibly nil) of a given record type. If I store a non-nil value in the hash table, the type (list or record) is preserved. If I store a nil value, the table doesn't know if I stored a nil record or a nil list.

Arguably, dynamic languages would be improved if they more commonly allowed the creation of (in scheme terms) multiple NIL? objects none of which are EQ? to any others. With the generic NIL? one could still abstract patterns of induction. With multiple, non-EQ? nils, I'd have an easier time composing data structures.

-t

how hard can it be, really?

Thomas Lord — Thu, 24 Jul 2008 19:53:04 -0400

CPP emits "#" directives to report filenames and line numbers properly. C compilers already deal with that and already decorate the AST with that information. They typically keep track of columns, as well.

To fully handle preserving comments and other pre-processor information, all that a typical parser needs to do is build an index that maps file/line/column positions to a number of datums: the extents of the previous, following, and enclosing comments (if any); the "include stack", and the "macro expansion stack". A "positition" as a compiler might emit it in an error message is then "file X, line Y, column Z, as expanded by the macro definition at file A, line B, column C, as expanded by [....], as included from [....]".

In other words, ASTs *already* contain (as node attributes) file / line / column information -- and that is completely sufficient to index a record of "what CPP did". It shouldn't "hair up" parsers or lexers, much at all.

A separate question is the idea of defining new languages in which comments are constrained as to their location and are explicitly attached to a specific AST node (e.g., a comment attached to a function definition or attached to the declaration of one of the parameters to that function).

-t

Too Strong

marshall — Thu, 24 Jul 2008 19:07:21 -0400

A side effecting procedure cannot be reordered without breaking the programmer's intent This is a bit too strong--it assumes that every order expressed in the syntax is the result of the programmer's intent. But linear syntax means the programmer has no choice but to state things in a particular order, whether that order is part of his intent or not. He ought to have a way to say that. In fact, I'd say the terminology reinforces your point of view: a "side" effect ought to be one that can be reordered or discarded without consequence. One that cannot ought to be called a "primary" effect. When printf() writes to stdout, that's a primary effect. When log() does, that's a side effect.

Mizar, Isar and proofless text

slawekk — Thu, 24 Jul 2008 18:58:07 -0400

It seems to me that proofless text is a language for expressing definitions and assertions and does not cover proofs. The "Practical Set Theory" article talks about definitions only. I would not say that it is a representation of mathematical reasoning that can be verified by a machine. Mizar and Isabelle's Isar (and I guess Ontic) are formal proof languages that allow to write and verify definitions and theorems, where a theorem is an assertion with the accompanying proof. The human readable rendering of PST is impressive and it would be interesting to see PST expanded to cover proofs as well.

Yup.

Douglas McClean — Thu, 24 Jul 2008 18:13:36 -0400

Yup.

No place to put context

Greg Buchholz — Thu, 24 Jul 2008 18:00:50 -0400

Ah, so you want something like this to work...

instance Functor Set where
  fmap :: (Ord a, Ord b) => (a -> b) -> (Set a) -> (Set b)
  fmap = S.map

Ah, indeed. So, under the

Brooks Moses — Thu, 24 Jul 2008 16:45:25 -0400

Ah, indeed. So, under the hood at machine level, you'd have a regular pointer (which the compiler guarantees will always point somewhere valid, insofar as it can, and doesn't provide the option of "nullifying"), and then the option type is the same representation but might also have a value that represents "there isn't a pointer-to-something stored here"? And, of course, one can query the latter so see if there's a pointer-to-something there or not. That makes a lot of sense to me.

(Possible) Differences from Haskell

Douglas McClean — Thu, 24 Jul 2008 16:35:13 -0400

My problem, in Haskell-speak, is that I would like to unify the definition of Prelude.fmap with that of Data.Set.map, and in so doing to make (Functor Data.Set) a valid instance.

*Main> Prelude.fmap (+) theSet

<interactive>:1:0:
    No instance for (Functor Set)
      arising from use of `fmap' at :1:0-22
    Possible fix: add an instance declaration for (Functor Set)
    In the expression: fmap (+) theSet
    In the definition of `it': it = fmap (+) theSet

Data.Set doesn't define this instance because (as I understand it) it isn't possible, because there isn't a way to carry the constraint that making a set requires equality (or in the case of Data.Set, ordering) along with the type of fmap.

Different from Haskell?

Greg Buchholz — Thu, 24 Jul 2008 16:23:11 -0400

I'm not sure I understand the question. Here's an example Haskell program:

import Data.Set as S

theSet = S.insert 1 (S.insert 2 (S.insert 3 S.empty))
 
foo = S.map (+) theSet

...that fails with the following compiler error message in GHC...

setfun.hs:5:6:
    No instance for (Ord (a -> a))
      arising from use of `map' at setfun.hs:5:6-21
    Possible fix: add an instance declaration for (Ord (a -> a))
    In the expression: map (+) theSet
    In the definition of `foo': foo = map (+) theSet
Failed, modules loaded: none.

...what differences from Haskell are you looking for?

FlapJax

rossjudson — Thu, 24 Jul 2008 14:52:12 -0400

You can do something like what you want with FlapJax, which gives you a functional reactive environment in JavaScript. Since it's wrapped up inside of a web page, you can easily do a kind of "literate spreadsheet programming". You'd do your programming with the FlapJax core, and use its DOM library to actually show the results of the computation.

Just when I thought I was getting somewhere

Douglas McClean — Thu, 24 Jul 2008 13:51:31 -0400

I'm fairly sure I am missing something. The proposed *? kind seems strange, since nothing has that kind. Or are you saying that it decorates the arrow, like * ->? * ? If I understand the definition properly, at the moment I only have rank-2 types, because the product type generator and the function arrow are the highest kinded things I've decided to care about yet. Under this idea, what would the type of the map function end up being?