Tag Archive for "macros" tag

Haskell-like function definitions in Scheme

June 26th, 2013 by Ivan Lakhturov | 0 Category: Programming | Tags: | |

Haskell allows to decompose arguments straight in a function signature. While pattern matching is implemented in some Scheme-s, it's not applied to the signature. Luckily, we have Scheme macros to alter that.

Let's say we started out with a new language, bootstrapping it with Scheme. And in the beginning we have no lexing / parsing, just redefinitions. First of all, we change the names for the pairs, as that's the cornerstone of Scheme and some other functional languages.

Why not to change those, indeed? Say, what is the meaning of 'cdr'? Perhaps, earlier "Contents of the Decrement part of Register number" meant something. But nowadays - nothing. The only advantage perhaps is that you can quickly write some 'cadadr'-like compositions.

So, we redefine pairs' functions:

  1. (define pair cons)
  2. (define former car)
  3. (define latter cdr)

Then, suppose we want to write a swap function, which interchanges the former and the latter parts of a pair:

  1. (define (swap p) (pair (latter p) (former p)))

Now compare this to the Haskell version:

  1. swap (a, b) = (b, a)

Haskell decomposes a pair into "a" and "b" straight in the function signature. One can argue that it looses "p" variable name for the whole pair. But for that it has a special syntax:

  1. swap pair@(a, b) = (b, a)

Notice, we could not use the "pair" identifier in Scheme version, as we would shadow the constructor.

The Haskell's variant is more declarative. Also, if the variable "p" would have a longer name, we'd suffer, as it's used twice. Let's make use of macros to implement Haskell-like function definitions in Scheme:

  1. (define-syntax
  2.   (syntax-rules ()
  3.     [(_ (function possibly-decomposed-argument) . body)
  4.      (define (function generated-argument-name)
  5.        (match generated-argument-name
  6.          [possibly-decomposed-argument . body]
  7.          [_ (error "input did not match the function definition")]
  8.          ))]
  9.     [(_ identifier expression)
  10.      (define identifier expression)]
  11.     ))

The second transformer is to allow identifier definitions like "(≝ x 10)". The "match" is defined in PLT/Racket and some other implementations. Now we can write our swap-function like this:

  1. ((swap (pair a b)) (pair b a))

or even like this:

  1. ((swap (pair a b)) . ≝ . (pair b a))

- if we remember about the dot-notation of the Scheme's lexer (reader).

However, that will not work. The reason is simple, the redefinitions that we wrote for the pair funcions are executed in the last phase (run-time), but the "match" macro needs it already during the macro-application phase (the expander phase). That "match" does not know about new pair's constructor.

And to mitigate that there is a clumsy "define-match-expander":

  1. (define-match-expander pair
  2.   (syntax-rules () [(_ a b) (cons a b)])
  3.   (syntax-rules () [(_ a b) (cons a b)]))

The first transformer is used in the "match" context, and the second is for everything else (i.e. it replaces our "cons" pair constructor). The transformers are identical, but I didn't manage to declare one separately and re-use. Quick search reveals that others also have some problems with that.

So, now we can imitate Haskell notation. For one parameter and one pattern only, but that could be extended. Haskell, however, also has a limit of one pattern, as to declare a different pattern one needs to repeat a function name on a different line. That's what I don't like in Haskell. It is really enough to write a function name once. Say, in Nemerle with indentation-based syntax one can write:

  1. def fibonacci(i)
  2.   | 0 => 0
  3.   | 1 => 1
  4.   | _ => fibonacci(i - 1) + fibonacci(i - 2)

There are case expressions in Haskell, but those oblige to declare additional identifiers for function's arguments (those could be replaced with _ in Nemerle). And hey! The "case" from Haskell resembles define/match, which is already implemented in PLT Scheme/Racket. And define/match is a good enough substitute for the default Haskell notation, I think. So, instead of "(define (swap p) (pair (latter p) (former p)))" we would write:

  1. (define/match (swap _)
  2.   [((pair a b)) (pair b a)])

A bit too many parentheses to support multiple patterns for one branch (different from normal "match"), but in other respects nice.

So, actually I would choose Haskell-like notation for functions with one pattern, and define/match for many-pattern functions, like Fibonacci one. I guess it's possible to combine these in one ≝-notation. For that we would need to enhance the ≝ macro. But that is already "a topic of the future research", as scientists say (when they don't want (or cannot) continue).