COMP[39]161 Concepts of Programming Languages
Semester 2, 2018

Code (Week 1)

Table of Contents

1 Basic Haskell Programming

factorial :: Int -> Int 
factorial 0 = 1
factorial n | n > 0 = n * factorial (n - 1)
            | otherwise = error "urgh!"

-- this is already defined in the standard prelude as
-- (.)
comp :: (b -> c) -> (a -> b) -> a -> c
comp f g x = f (g x)


type Point = (Int, Int)
type Length = Int 
type Angle = Int 
data Colour = Red | Blue | Fuchsia | Cyan | Turquoise 
data Shape  = 
      Square Length 
    | Triangle Angle Length Length 
    | Rect Length Length 
    deriving (Show) -- so that I can print it.

area :: Shape -> Int 
area (Square s) = s * s
area (Rect w h) = w * h
area (Triangle theta s1 s2) = error "High school maths?!"


-- Haskell's built-in lists are as follows:
--   List a is written [a]
--   Empty  is written []
--   NonEmpty is written as :
--   e.g NonEmpty 3 (NonEmpty 4 Empty) :: List Int
--   is equivalent to 3:4:[] :: [Int]
data List a = Empty | NonEmpty a (List a) deriving (Show)

-- Just like "length", but for our lists
length' :: List a -> Int 
length' Empty = 0
length' (NonEmpty x xs) = 1 + length' xs 

-- Just like (++), but for our lists
append :: List a -> List a -> List a 
append Empty ys = ys
append (NonEmpty x xs) ys = NonEmpty x (append xs ys)

-- Already defined in prelude as (++)
append' :: [a] -> [a] -> [a]
append' [] ys = ys 
append' (x:xs) ys = x:(append' xs ys)

-- Already defined in prelude as filter
filter' :: (a -> Bool) -> [a] -> [a]
filter' p [] = []
filter' p (x:xs) | p x = x : filter' p xs 
                 | otherwise = filter' p xs

2 Lexer

import Data.Char(isSpace, isDigit, isAlpha)
import Data.List(partition)

data Token 
   = Kwd Keyword 
   | Ident String 
   | Times | Minus | Equals | Gt | Lt 
   | LParen | RParen | LBrace | RBrace | Semi
   | Number Int 
   deriving (Show)
data Keyword = If | Else | Return | While 
             deriving (Show)

lexer :: String -> [Token]
lexer [] = []
lexer (' ':cs) = lexer cs 
lexer ('\n':cs) = lexer cs 
lexer (c:cs) | isSpace c = lexer cs 
lexer ('*':cs) = Times : lexer cs 
lexer ('-':c:cs) = Minus : lexer (c:cs)
lexer ('=':cs) = Equals : lexer cs
lexer ('>':cs) = Gt : lexer cs
lexer ('<':cs) = Lt : lexer cs
lexer ('(':cs) = LParen : lexer cs
lexer (')':cs) = RParen : lexer cs
lexer ('{':cs) = LBrace : lexer cs
lexer ('}':cs) = RBrace : lexer cs
lexer (';':cs) = Semi : lexer cs
lexer (c:cs) | isAlpha c = let 
      (word,rest) = span isAlpha (c:cs)
    in checkKeyword word : lexer rest
  where 
    checkKeyword :: String -> Token 
    checkKeyword "if" = Kwd If 
    checkKeyword "while" = Kwd While
    checkKeyword "else" = Kwd Else
    checkKeyword "return" = Kwd Return
    checkKeyword other = Ident other 

lexer ('/':'/':cs) = lexer (dropWhile (/= '\n') cs)
lexer (c:cs) | isDigit c = let 
       (numString, rest) = span isDigit (c:cs)
    in Number (read numString) : lexer rest
lexer _ = []

We used the following C program as input:

int factorial(int n) { // comment
    if (n < 0) {
        return -1;
    } else {
        int ret = 1;
        while (n > 0) { 
            ret = ret * n;
            n = n-1;
        }
        return ret;
    }
}

To run our lexer on this file, use the following GHCi commands:

> :l Lexer.hs
> file <- readFile "input.c"
> lexer file

3 Mole Problem (Extension)

module Mole where
import Data.List(nub)

data State = G1 | G2 | G3 | G4 | G5 | Found | Initial
           deriving (Show, Eq)

data Act = Start | D1 | D2 | D3 | D4 | D5 
           deriving (Show)

initialState = Initial 

finalState = Found

-- concatMap :: (a -> [b]) -> [a] -> [b]
deltaSubset :: Act -> [State] -> [State]
deltaSubset a ss = nub (concatMap (delta a) ss)

isSolution :: [Act] -> [State] -> Bool
isSolution []     ss = ss == [Found]
isSolution (a:as) ss = isSolution as (deltaSubset a ss)

allSequencesOfLength :: Int -> [[Act]]
allSequencesOfLength 0 = [[]]
allSequencesOfLength n = [ (a:as) | a <- [D1,D2,D3,D4,D5] 
                                  , as <- allSequencesOfLength (n-1) 
                                  ]

candidates = map (\l -> Start:l) 
            (allSequencesOfLength 0 ++ allSequencesOfLength 1
            ++ allSequencesOfLength 2 ++ allSequencesOfLength 3 
            ++ allSequencesOfLength 4 ++ allSequencesOfLength 5)

-- Returns false, indicating that no sequence of digs of length <= 5 is 
-- a solution.
check = any (\acts -> isSolution acts [Initial])  candidates

delta :: Act -> State -> [State]
delta Start Initial = [G1,G2,G3,G4,G5]
delta D1 G1 = [Found]
delta _  G1 = [G2] 
delta D2 G2 = [Found]
delta _  G2 = [G1,G3]
delta D3 G3 = [Found]
delta _  G3 = [G2,G4]
delta D4 G4 = [Found]
delta _  G4 = [G3,G5]
delta D5 G5 = [Found]
delta _  G5 = [G4]
delta _  g  = [g]

2018-11-16 Fri 19:37

Announcements RSS