Components of a Language & Function Polymorphism in Haskell - Programming Languages - Sep 10th, 2019

Syntax

Syntax consists of:
- Identifier
- Operators, Punctuation
- Keywords, reserved words
- Whitespace
- Literals, Constants
  - int, float, string, char

Parse Tree

A parse tree is generated by a compiler or interpreter when you compile or run code

Statements
Expressions
- Multi Expressions
- Atoms

Abstract Syntax Tree

An AST is generated from a Parse Tree

Punctuation, whitespace are removed

Semantics

A Symbol has:
- representation (how it looks)
- denotation (what it means)
  - type
  - memory location
  - value
  - modifiers
    - ex: const, volatile
  - scope

Name resolution (“Binding”)

The process of mapping representation to denotation in Symbol Table

Some languages do name resolution at compile time (C++) and other languages do it at runtime (Python)

In Python, the symbol table entry for a variables does not store the type of the variable because it has dynamic typing.

ex: “foo” -> {value: “3”}

In C++, the symbol table entry for variable stores type and the memory address of the variable ,but not the actual value.

ex: “foo” -> {type: int, addr: 0x0000001}

Notice how similar the code for the below functions stringLength and intListLength are:

stringLength :: String -> Int
stringLength "" = 0
stringLength (h:t) =
	let tailLength = stringLength t
	 in 1 + tailLength

intListLength :: [Int] -> Int
intListLength [] = 0
intListLength (h:t) =
	let tailLength = intListLength t
	 in 1 + tailLength

Instead of making two different functions, you can create one generic or polymorphic function that works with any list type

ListLength :: [a] -> Int
ListLength [] = 0
ListLength (h:t) =
	let tailLength = ListLength t
	 in 1 + tailLength

Lets write a function that can reverse a list in haskell Note: every item in a list in Haskell has to be the same type

myreverse :: [a] -> [a]
myreverse [] = []
myreverse (h:t) = myreverse t ++ [h]

#proglang-f19