Lambda the Ultimate

Hi all,

I am starting to work on my own pet language and I joined in to make it public here, as I like very much to follow the very informative discussions hosted at Lambda the Ultimate.

I hope to contribute more in the future. Though I have to confess that proofs and lambdas are not my forte, I did not really look into these since my student days. So what I can do at the moment is to answer the questions you may have on dodo as it gets better defined and evolves over time.

This is the URL of the dodo home page on Sourceforge.

Take a look here :)
Janek

The latest Cat version ( 0.9.7 at http://www.cat-language.com/download.html ) now has a linear recursion combinator "rec". The Cat type inference algorithm currently can't handle self-referential functions, but you implement recursive algorithms using the rec combinator.

Here is an example of the factorial program:

  >> define f { [dup 1 <=] [*] [pop 1] [dup --] rec }
  inferred type for program 'f' as ( int ) -> ( int )
  main stack: _empty_
  >> 5 f
  main stack: 120
  >> 6 f
  main stack: 120 720

The type of the rec combinator is interesting (at least I thought so):

(
  (A:any*)->(A A) // argument relation
  (A)->(B:any*)   // termination function
  (A B)->(B)      // result relation
  (A)->(bool A)   // termination condition
  A               // input 
)->(B)

I was wondering what people's thoughts were about the rec combinator? For example is it in fact interesting or novel to see the types explicitly stated for each component of linear recursion? Do you think there might be some educational value for students to have recursion explained in terms of arguments to a combinator?

Any feedback would be very helpful, thanks in advance!

Note: those familiar with Cat will notice that stack descriptions now read left to right, where the leftmost type corresponds to the top of the stack.

hye everyone..im a newbies of lisp. im trying to understand lisp better by using example. i got this program from a website and would like to see how it actually works. but i have difficulty in understanding and running it. can anyone help me to run it? it is a tic-tac-toe game. below is the coding. tq.

;;Function NULL-BOARD creates an empty tic-tac-toe board. The board is
;; stored as a list of nine elements. Elements are either 'x, 'o, or nil
;; (empty).

(defun null-board ()
(list nil nil nil nil nil nil nil nil nil))

;; Variable *START* is the starting board position.

(defvar *start* nil)
(setq *start* (null-board))

;; Function MAKE-MOVE takes a board position (pos), a player (player, which
;; is 'x or 'o), and a move (which is a number between 0 and 8). It returns
;; a new board position.

(defun make-move (pos player move)
(let ((b (copy-list pos)))
(setf (nth move b) player)
b))

;; Function MOVEGEN takes a position and a player and generates all legal
;; successor positions, i.e., all possible moves a player could make.

(defun movegen (pos player)
(mapcar
#'(lambda (m)
(if (null (nth m pos))
(list (make-move pos player m))
nil))
'(0 1 2 3 4 5 6 7 8)))

;; Function WON? returns t is pos is a winning position for player,
;; nil otherwise.

(defun won? (pos player)
(or (and (eq (first pos) player)
(eq (second pos) player)
(eq (third pos) player))
(and (eq (fourth pos) player)
(eq (fifth pos) player)
(eq (sixth pos) player))
(and (eq (seventh pos) player)
(eq (eighth pos) player)
(eq (ninth pos) player))
(and (eq (first pos) player)
(eq (fourth pos) player)
(eq (seventh pos) player))
(and (eq (second pos) player)
(eq (fifth pos) player)
(eq (eighth pos) player))
(and (eq (third pos) player)
(eq (sixth pos) player)
(eq (ninth pos) player))
(and (eq (first pos) player)
(eq (fifth pos) player)
(eq (ninth pos) player))
(and (eq (third pos) player)
(eq (fifth pos) player)
(eq (seventh pos) player))))

;; Function DRAWN? returns t if pos is a drawn position, i.e., if there are
;; no more moves to be made.

(defun drawn? (pos)
(not (member nil pos)))

;; Function OPPOSITE returns 'x when given 'o, and vice-versa.

(defun opposite (player)
(if (eq player 'x) 'o 'x))

;; Function STATIC evaluates a position from the point of view of a
;; particular player. It returns a number -- the higher the number, the
;; more desirable the position. The simplest static function would be:
;;
;; (defun static (pos player)
;; (cond ((won? pos player) 1)
;; ((won? pos (opposite player)) -1)
;; (t 0)))
;;
;; However, this heuristic suffers from the problem that minimax search
;; will not "go in for the kill" in a won position. The following static
;; function weighs quick wins more highly than slower ones; it also
;; ranks quick losses more negatively than slower ones, allowing the
;; program to "fight on" in a lost position.

(defun static (pos player)
(cond ((won? pos player)
(+ 1 (/ 1 (length (remove nil pos)))))
((won? pos (opposite player))
(- (+ 1 (/ 1 (length (remove nil pos))))))
(t 0)))

;; Function DEEP-ENOUGH takes a board position and a depth and returns
;; t if the search has proceeded deep enough. The implementation below
;; causes the search to proceed all the way to a finished position. Thus,
;; minimax search will examine the whole search space and never make a
;; wrong move. A depth-limited search might look like:
;;
;; (defun deep-enough (pos depth)
;; (declare (ignore pos))
;; (if (> depth 3) t nil))

(defun deep-enough (pos depth)
(declare (ignore depth))
(or (won? pos 'x)
(won? pos 'o)
(drawn? pos)))

;; Function PRINT-BOARD prints a two-dimensional representation of the board.

(defun print-board (b)
(format t "~% ~d ~d ~d~% ~d ~d ~d~% ~d ~d ~d~%~%"
(or (first b) ".") (or (second b) ".") (or (third b) ".")
(or (fourth b) ".") (or (fifth b) ".") (or (sixth b) ".")
(or (seventh b) ".") (or (eighth b) ".") (or (ninth b) ".")))

Orc is a language in the process calculi tradition that I really like. It's combination of simplicity and expressiveness is amazing. Unlike some other process calculi, Orc does not make unreasonable assumptions (like mobility) about what properties are implementable in a distributed system. Orc's semantics are compatible with transparent distribution, distributed object-capability security, and distributed garbage collection. Here's a draft implementation of Orc in E providing approximately these three properties, with the caveats that E currently does not collect distributed cyclic garbage, and E's distributed failure semantics are wrong for Orc.

It would be good to see some embeddings of Orc into other distributed languages, and to compare these.

I'm currently taking a computer engineering course that involves a gratuitous amount of assembly programming. Sadly, it's largely superfluous to the actual course work (implementing processor componentns), so I'd like to program in a high level language.

I've looked at several compilers (gcc, mit-scheme, and ocaml) so far and all of them seemed to require a fair amount of work to retarget. Moreover, the processor we are implementing doesn't use a totally conventional execution model due to time constraints on the class. It essentially omits registers and works directly in memory.

I'll also admit my knowledge on compilation is lacking; it's taking me time to get through the dragon book¹. I had no problem following along with Crenshaw's "Let's Build a Compiler!" on my architecture, and Ghuloum's "An Incremental Approach to Compiler Construction" also seemed doable, although I have not gone through it in any detail.

With that in mind, are there any compilers that would be easy (or at the very least, not excessively painful) to retarget to such an architecture? I'd assume that a lisp will probably occupy this niche, but I'm comfortable with any language.

¹ I've heard that Wirth's compiler book is more approchable; is this true?

Edit: Added links.

Hi,

Please be gentle with me, this is my first post :-)

I am currently writing my master thesis (CS) on the topic of adding type inference to the formal specification language VDM++.

VDM++ is an object-oriented, formal specification language, typically used to model mission-critical systems. The syntax is mathematically oriented, using a lot of abstract constructs such as sets, sequences, maps and unions as well as more widespread language constructs.

If anyone is interested in the language spec, it can be found here:
http://www.vdmbook.com/langmanpp_a4.pdf

Anyway, to my question...
I am looking for some pointers to literature on the use of union types, specifically the problems which union types may cause in connection with type inference. In VDM++, unions correspond to set-theoretic unions of two or more types which may be disjoint or non-disjoint.

There seems to be plenty written on intersection types, but union types and ways to statically handle these seem quite scarce.

Question from this seemingly eternal newbie: I don't grok things enough yet, but it seems like something in the world of Scrap your Boilerplate / GADTs / etc. type stuff might be able to obviate evil code generation in more static-than-dynamic languages? Or am I just hopelessly befuddling concepts?

Frédéric Peschanski and Samuel Hym, A stackless runtime environment for a Pi-calculus, 2nd ACM/Usenix International Conference on Virtual Execution Environments.

From the abstract:

...We present in this paper the CubeVM, an interpreter architecture for an applied variant of the Pi-calculus, focusing on its operational semantics. The main characteristic of the CubeVM comes from its stackless architecture. We show, in a formal way, that the resource management model inside the VM may be greatly simplified without the need for nested stack frames. This is particularly true for the garbage collection of processes and channels. The proposed GC, based on a reference counting scheme, is highly concurrent and, most interestingly, does automatically detect and reclaim cycles of disabled processes...

The slides that accompany the paper can be found here. A little more information on the CubeVM, including an early release of the source code, can be found on the project website.

This is the best introduction to "Monads" for newbies and imparative
mined that I'v ever read! For a long time I was searching for such an
excellent text on monads. Ofcourse there are many good text there. But
all of them are about mathematics and how clever the monads are. After
all most of them are useless for a practical approach. Take a look at
this http://sigfpe.blogspot.com/2006/08/you-could-have-invented-monads-and.html
!!