kyouko-taiga / alpinelang Goto Github PK

The current implementation of pattern matching doesn't allow non-linear patterns, as documented in the sources.

It would be nice to be able to define non-linear patterns, but there are several options:

• All one let-binding to appear multiple times in a pattern
• Attach where-clauses to match cases

The first option is the simplest, but would only lets us match terms with multiple occurrences of the same subterm (e.g. (#a, #a) would match (let x, let x)), and would not support patterns with more elaborate conditions on one or several bindings.

A where-clause on the other end would fit both bills, and have a nice syntax:

match (#a, #a)
  with (let x, let y) where x = y :: x
  with (let x, let y) where any_other_predicate(x, y) :: x
  with let any :: #a

This is also a better way to handle custom semantics of the equality operator.

I have this error:

l.21:c.3: type error: type '( Int or $12 )' doesn't match 'Int':
  match list
  ^

My code:

type List :: #empty or #cons(_ element: Int, _ rest: List)

func size(_ list: List) -> Int ::
  match list
    with #empty :: 0
    with #cons(let x, let s) ::
      1 + size(s)

My input:

alpine --import list.alpine -e '"hello"'

I have the code below:

I have this error:
l.52:c.1: syntax error: consecutive statements should be separated by ';':

If I add a ; after the last contain before the declaration of function remove, it works.
It'll be better if it can work without it 👍 !

// Example
// #cons(#zero, #cons(#succ(#succ(#zero)), #empty))
// contain(#succ(#succ(#zero)), #cons(#zero, #cons(#succ(#succ(#zero)), #empty)))

type Nat :: #zero or #succ(Nat)
type Boolean :: #True or #False
type Set :: #empty or #cons(_ element: Nat, _ rest: Set)

//BOOLEAN FUNCTIONS

func not(_ bool: Boolean) -> Boolean ::
  match(bool)
    with #True ::
      #False
    with #False ::
      #True

// NAT FUNCTIONS

func eq(_ nat1: Nat, _ nat2: Nat) -> Boolean ::
  match (nat1, nat2)
    with (#zero, #zero) ::
      #True
    with (let x, #zero) ::
      #False
    with (#zero, let x) ::
      #False
    with (#succ(let x), #succ(let y)) ::
      eq(x, y)


// SET FUNCTIONS

func count(_ set: Set) -> Nat ::
    match set
      with #empty ::
        #zero
      with #cons(let x, let rest) ::
        #succ(count(rest))


func contain(_ nat: Nat, _ set: Set ) -> Boolean ::
  match set
    with #empty ::
      #False
    with #cons(let x, let rest) ::
      match eq(nat, x)
        with #True :: #True
        with #False ::
          contain(nat, rest)

func remove(_ nat: Nat, _ set: Set) -> Set ::
  match set
    with #empty ::
      #empty
    with #cons(let x, let rest) ::
      match eq(nat, x)
        with #True :: rest
        with #False :: #cons(nat, remove(nat, rest))

The semantic analysis currently doesn't guarantee match-cases to exhaustively cover the possible execution of a match statement, which could potentially lead to a runtime crash of the interpreter. Here's super minimal example:

match 1 with 0 :: 0

I've written a little example about a bank user and its account.

// Example: addMoney(#user(name: "coco", age: 10, account: #account(10, 100)), 50)

type User :: #nil or #user(name: String, age: Int, account: Account)
type Account :: #empty or #account(_ interest: Int, _ money: Int)

func addMoney(_ user: User, _ moneyAdd: Int) -> User ::
  match(user)
  with #nil ::
    #nil
  with #user(name: let nom , age: let age, account: let account) ::
    match(account)
    // with #empty ::
    //  #nil 
    with #account(let interest, let money) ::
      #user(name: nom, age: age, account: #account(interest, money + moneyAdd))

The code above works if I comment:

with #empty ::
  #nil 

Otherwise, I have this error:

l.29:c.5: type error: type '#empty' doesn't match '#account(_: $8, _: $9)':
    match(account) 

In Account, I've defined two cases, but the #empty case isn't recognize.
I've tested a case with only Account but everything works:

// foo(account: #account(10,10))

func foo(account: Account) -> User ::
  match(account)
  with #empty ::
    #nil
  with #account(let interest, let money) ::
    #nil

When I run the code below with the command: alpine --import list.alpine -e 'size(insert(3, list: insert(5, list:#empty)))', I have the error: l.13:c.3: type error: type '( $17 or Int )' doesn't match 'Int': match list

//insert(3, list: insert(5, list:#nil)

type List :: #empty or #cons(Int, List)

func insert(_ el: Int, list: List) -> List ::
  match list
    with #empty ::
      #cons(el, #empty)
    with #cons(let x, let l) ::
      #cons(el, list)

func size (_ list: List) -> Int ::
  match list
    with #empty ::
      0
    with #cons(let x, let l) ::
      1 + 2

There's not library product in Package.swift. Hence one cannot use Alpine as a library, as mentioned in the README.

Overloading a built-in operator (e.g. +) in a user module shadows the built-in definitions of the same operator, making it impossible to manipulate built-in values.

Here's a minimal example:

type Point :: #point(x: Int, y: Int)
func + (_ lhs: Point, _ rhs: Point) -> Point ::
  #point(x: lhs.x + rhs.x, y: lhs.y + rhs.y)

The above code will produce a type error complaining that #point(x: Int, y: Int) does not match type Int, suggesting that the operator + between integers is no longer considered by the type solver. Further evidences can be found by observing the type constraints generated by the above program, which do not feature any disjunction.

I am going to work on new implementation and improvement for:

• String
• Binary Tree

There's currently no way to match a function unless they are bound to a new variable, meaning they can't appear as the subject of a match value. Should we consider a sort of identity comparison for function values, in other words synthesizing = for functions?

This would allow us to write things like:

match (func () -> Int :: 1)
  with (func () -> Int :: 1) :: "the function matched!"
  //

If such synthesized equality operator was to be implemented, should function with the same signature be considered equal, or should equality also encompass function identifiers and/or body?

There's currently no way to match built-in strings with anything but identify. In other words, one can write the following:

match s
  with "one" :: 1
  with "two" :: 2

But one can't check for any pattern that would match only parts of the string (e.g. the character at specific position). Although less impactful, note that built-in integers expose a similar problem.

One solution could be to map the built-in strings to an algebraic type such as #cons(_: Char, _: String) or #empty, which would make them naturally expressible in the language. Hence, the syntax with double quotes would be merely a syntactic sugar for #cons("a", cons("b", ....

Another direction would be to provide a built-in function to extract a specific character (e.g. char(in:at:)) and use identity matching, e.g.:

match char(in: s, at: 0)
  with "a" :: "the string starts with 'a'"
  // ...

Note that both solutions would require a built-in Char type.

It is not possible to use reserved keywords in labels, as the parser always expects identifiers. This reduces a lot the options we have to create meaningful function signatures and is likely to break existing code as it'll grow and feature more constructions.

The parser could be modified to accept reserved keywords as identifiers whenever their use wouldn't make the grammar ambiguous.

It would be nice to illustrate how to manipulate a tree structure. A simple example would be to use a binary tree to maintain an ordered collection of some built-in type (e.g. Int).

It would be nice to add examples on the following subjects:

• List
• Stack

The interpreter will crash if it finds a let-binding appears anywhere outside of the pattern of a match case. For instance:

#node(value: let v, left: let left, right: let right)

This should never happen, and hence be detected statically after semantic analysis, at least as long as we don't allow let-bindings to have a role similar to letrec in scheme.