Michael Weber: Random Bits and Pieces

A #lisp conversation sparked the cunning idea to write a diff-like algorithm for s-expressions.

It was mainly an exercise to see how hard it would be, since Xophe asserted it might not be trivial.

Example session:

DIFF-SEXP> (diff-sexp  
	  	'(DEFUN F (X) (+ (* X 2) 1)) 
	  	'(DEFUN F (X) (- (* X 2) 3 1)))
((DEFUN F (X) (|#-new| + |#+new| - (* X 2) |#+new| 3 1)))

The algorithm is based on Levenshtein-like edit distance calculations. It tries to minimize the number of atoms in the result tree (also counting the edit conditionals |#-new|, |#+new|). This can be observed in the example below: instead of blindly adding more edit conditionals, the algorithm backs up and replaces the whole subexpression.

DIFF-SEXP> (diff-sexp  
	  	'(DEFUN F (X) (+ (* X 2) 4 1)) 
	  	'(DEFUN F (X) (- (* X 2) 5 3 1)))
((DEFUN F (X) (|#-new| + |#+new| - (* X 2) |#-new| 4 |#+new| 5 |#+new| 3 1)))

DIFF-SEXP> (diff-sexp  
	  	'(DEFUN F (X) (+ (* X 2) 4 4 1)) 
	  	'(DEFUN F (X) (- (* X 2) 5 5 3 1)))
((DEFUN F (X) |#-new| (+ (* X 2) 4 4 1) |#+new| (- (* X 2) 5 5 3 1)))

The library is called diff-sexp (caveat emptor: should be regarded as prototype). Currently it handles updates, deletions and insertions, but does not take advantage of moved subtrees. However, for production use, e.g. inside Climacs, it needs to handle more details.

Update: Thanks to Lemonodor for the URL to the original discussion.

via Planet Smalltalk:

A Java developer answers the question Smalltalk v. Java: Which is More Productive?:

Java is kind of like kindergarten. There are lots of rules you have to remember. If you don't follow them, the compiler makes you sit in the corner until you do. There are 59+ reserved words. Everything is not an object. [...] You have to remember to tell the compiler things several times so it knows what you're talking about (Date date = new Date()).

via LtU:

Just for me to remember, I reiterate some type theory terminology.

statically checked
statically typed

Each term of a language can be classified as being of at least one (possibly more) sort (syntactic type). Statically checked programs are safe in the sense that operations are (statically) guaranteed to work only on sorts they are intended for.

Examples: Alice, Haskell, O'Caml, Standard ML


Special case of a typed language with only a single sort, the universal sort, which is assigned to each term. One implication is that not many interesting assertions about unityped programs can be made statically.

Examples: Common-Lisp, Erlang, Mozart/Oz, Scheme, Smalltalk, Assembler

XXX This is not entirely true for some implementations of those languages. They define subsorts (subtypes) of the universal sort and function types which allows type inference to some extent.
XXX Also, how do function types (cue word simply typed) fit in there?

dynamically checked

All values are tagged. Operations at run-time are constrained (by tags) to only work on values they are intended for. A program of a tagged language is safe in the sense that violations of these constraints at run-time will not go undetected.

Examples: Common-Lisp, Erlang, Mozart/Oz, Scheme, Smalltalk
(Note how these overlap with unityped languages!)


Languages which admit programs for which undefined behavior goes undetected, for example, operations being applied to values they are not defined for without raising an error.

Examples: C, Assembler

Other commonly heard terminology:

strongly typed
Term better avoided, denoting a sound type system (as opposed to unsound or none at all) and is applied to statically checked or sometimes even dynamically checked languages.
weakly typed
Bad term for language with unsound type system.
dynamically typed
latently typed
Terms better avoided because they don't really mean types in the narrow mathematical sense. Both terms are used to mean the same as dynamically checked.

If anyone spots a mistake or can suggest better wording, do not hesitate to contact me!

Overview over Proof-carrying Code research. A bit dated by now, but otherwise might prove (hah!) helpful one day.

via lemonodor:

Gene Michael Stover wrote a date parsing library some time ago, which, it seems, is not widely known.

Page 24/29: « 20 21 22 23 24 25 26 27 28 »