Can Haskell programs be represented as Lisp S-expressions?

Question

This would be useful for genetic programming, which usually use a Lisp subset as representation for programs.

I've found something called Liskell (Lisp syntax, Haskell inside) on the web, but the links are broken and I can't find the paper on it...

Mcgarry

I would argue that this must be the case, however inelegant. But a simple "yes" isn't very existing. – Deport

Answer 1

Check out Lisk, which was designed to fix the author's gripes with Liskell.

In my spare time I’m working on a project called Lisk. Using the -pgmF option for GHC, you can provide GHC a program name that is called to preprocess the file before GHC compiles it. It also works in GHCi and imports. You use it like this:

{-# OPTIONS -F -pgmF lisk #-}
(module fibs
  (import system.environment)

  (:: main (io ()))
  (= main (>>= get-args (. print fib read head)))

  (:: test (-> :string (, :int :string)))
  (= test (, 1))

  (:: fib (-> :int :int))
  (= fib 0 0)
  (= fib 1 1)
  (= fib n (+ (fib (- n 1))
              (fib (- n 2)))))

The source is here.

Also, if you don't actually care about Haskell and just want some of its features, you might want to check out Qi (or its successor, Shen), which has s-expression syntax with many modern functional-programming features similar to Haskell.

Santoyo

Answer 2

You might be interested in a project I have been working on, husk scheme.

Basically it will let you call into Scheme code (S-expressions) from Haskell, and vice-versa. So you can intermingle that code within your program, and then process the s-expressions as native Haskell data types when you want to do something on the Haskell side.

Anyway, it may be useful to you, or not - have a look and decide for yourself.

Vocal

Answer 3

In most genetic programming software, programs are represented as abstract syntax trees (AST) which are evaluated directly in that form. The Lisp S-expression syntax is only apparent when the programs are output as source code. Have you considered just modifying the output module in your chosen software to produce Haskell source code from the ASTs instead?

Carbylamine

Answer 4

The obvious answer is "yes" -- unsurprising given that S-expressions were intended as a simple & uniform representation of parsed code. The thing is that languages like Haskell or ML tend to have some problems with that. I once did something similar to OCaml (abused CamlP4 and wrote some function that translates the P4 AST into some sexpr-like representation), and the fun begins when you run into similar kinds of AST nodes that have different types because they're not really the same... For example, there's function application, and there's a similar form that is used in patterns, and yet another form that is used in type expressions.

My guess is that trying to do genetic programming this way is likely to suffer from too much junk programs that don't have any meaning. But that's unsurprising too for any statically typed language -- a dynamically typed language will allow more junk in. Comparing the two worlds WRT to genetic programming might be interesting for reasons beyond the AI...

Nummary

Answer 5

The Liskell paper is at http://clemens.endorphin.org/ILC07-Liskell-draft.pdf and the liskell.org site seems to still be up in general.

Propraetor

Strange, I see a lottery ad there. Do I need to click on something? – Mcgarry

It says "Sorry, access forbidden, error 403." But I'm not using a proxy AFAIK. – Mcgarry