matt’s�~ languages of the week ~
all mistakes are his; sources are cited when possible
quick table of contents
javascript gone wrong*
�(and how to infer language behaviour by example)
doing things a lil’ differently…
aside: matt has given variations of this talk a couple of times!
Haskell
We just learned about OCaml and functional programming (FP)!
Haskell is functional programming to the extreme.
We cover Haskell in Carey’s CS 131!
The Haskell logo. �Haskell website.
Why Haskell?
Compared to OCaml, Haskell is a different approach to functional programming!
Haskell’s characteristics:
And … large performance differences!
And, it has influenced:
Haskell code (and lazy eval)
-- Generate first 5 #s divisible by 29
-- between 1000 and infinity
div_by_29 = take 5 [x | x <- [1000..], (mod x 29) == 0]
-- Generate all numbers divisible by 29�-- between 1000 and infinity
div_by_29 = [x | x <- [1000..], (mod x 29) == 0]
ML & OCaml
We just learned about Haskell (and functional programming)!
ML is the influential functional programming language!
OCaml is one popular dialect of ML
Why ML & OCaml?
History and influence:
OCaml is widely used in PL tooling (compilers, interpreters), formal methods, analysis.
Major projects: Coq, various Facebook-related type retrofitters (Hack, Flow, pyre), Haxe.
We used to cover OCaml in 131!
Compared to Haskell, ML/OCaml are different approaches to functional programming!
Compared to Haskell:
And … large performance implications!
Quicksort in OCaml – similar to Haskell :)
let rec qsort = function
| [] -> []
| pivot :: rest ->
let is_less x = x < pivot in
let left, right = List.partition is_less rest in
qsort left @ [pivot] @ qsort right
JavaScript
“Technically it’s actually ECMAScript” smh
A little about JS:
Matt’s most-used language (~200k sloc).
Why is JS interesting?
JavaScript
“Technically it’s actually ECMAScript” smh
A little about JS:
Matt’s most-used language (~200k sloc).
Why is JS interesting?
FP in JavaScript (and React)
const listItems = products.map(product =>
<li key={product.id}>
{product.title}
</li>
);
FP in JavaScript (and React) – Map & Lambdas!
const listItems = products.map(product =>
<li key={product.id}>
{product.title}
</li>
);
FP in JavaScript
const dates = [
'2019/06/01', '2018/06/01', '2019/09/01', '2018/09/01'
].map(v => new Date(v));
const maxDate = dates.reduce(
(max, d) => d > max ? d : max, // ternary operator
dates[0]
);
FP in JavaScript – Map, Lambda, & Reduce
const dates = [
'2019/06/01', '2018/06/01', '2019/09/01', '2018/09/01'
].map(v => new Date(v));
const maxDate = dates.reduce(
(max, d) => d > max ? d : max, // ternary operator
dates[0]
);
Lua
Lua is a small, lightweight language designed to be embedded in other applications!
On one hand:
On the other hand:
chunk ::= {stat [`;´]} [laststat[`;´]]
block ::= chunk
stat ::= varlist1 `=´ explist1 |
functioncall |
do block end |
while exp do block end |
repeat block until exp |
if exp then block {elseif exp then block} [else block] end |
for Name `=´ exp `,´ exp [`,´ exp] do block end |
for namelist in explist1 do block end |
function funcname funcbody |
local function Name funcbody |
local namelist [`=´ explist1]
laststat ::= return [explist1] | break
funcname ::= Name {`.´ Name} [`:´ Name]
varlist1 ::= var {`,´ var}
var ::= Name | prefixexp `[´ exp `]´ | prefixexp `.´ Name
namelist ::= Name {`,´ Name}
explist1 ::= {exp `,´} exp
exp ::= nil | false | true | Number | String | `...´ | function | � prefixexp | tableconstructor | exp binop exp | unop exp
prefixexp ::= var | functioncall | `(´ exp `)´
functioncall ::= prefixexp args | � prefixexp `:´ Name args
args ::= `(´ [explist1] `)´ | tableconstructor |
String
function ::= function funcbody
funcbody ::= `(´ [parlist1] `)´ block end
parlist1 ::= namelist [`,´ `...´] | `...´
tableconstructor ::= `{´ [fieldlist] `}´
fieldlist ::= field {fieldsep field} [fieldsep]
field ::= `[´ exp `]´ `=´ exp | Name `=´ exp | exp
fieldsep ::= `,´ | `;´
binop ::= `+´ | `-´ | `*´ | `/´ | `^´ | `%´ | `..´ |
`<´ | `<=´ | `>´ | `>=´ | `==´ | `~=´ |
and | or
unop ::= `-´ | not | `#´
the entire Lua syntax! (in modified BNF)
compared to…
Similar in length to the CSS Grammar!
local default_fcompval = function( value ) return value end
local fcompf = function( a,b ) return a < b end
local fcompr = function( a,b ) return a > b end
function table.binsearch( tbl,value,fcompval,reversed )
local fcompval = fcompval or default_fcompval
local fcomp = reversed and fcompr or fcompf
local iStart,iEnd,iMid = 1,#tbl,0
while iStart <= iEnd do
iMid = math.floor( (iStart+iEnd)/2 )
local value2 = fcompval( tbl[iMid] )
if value == value2 then
local tfound,num = { iMid,iMid },iMid - 1
while value == fcompval( tbl[num] ) do
tfound[1],num = num,num - 1
end
num = iMid + 1
while value == fcompval( tbl[num] ) do
tfound[2],num = num,num + 1
end
return tfound
elseif fcomp( value,value2 ) then
iEnd = iMid - 1
else
iStart = iMid + 1
end
end
end
array binary search in Lua
Small exercise: yes, you know nothing about Lua, but can you guess…
who uses Lua?
Lua is now* primarily used:
Question for you: why do you think these are the prevalent uses?
*for some time, it was also used in AI & operating systems work, but imo those died out
so, why Lua?
Takeaway: spectrum on how lightweight language should be; no “right” answer!
Other dimensions:
Go
“We hated C++ so much, we made a new language…”
Why Go?
go’s defer keyword
// Contents returns the file's contents as a string.
func Contents(filename string) (string, error) {
f, err := os.Open(filename)
if err != nil {
return "", err
}
defer f.Close() // f.Close will run when we're finished.
var result []byte
buf := make([]byte, 100)
for {
n, err := f.Read(buf[0:])
result = append(result, buf[0:n]...) // append is discussed later.
if err != nil {
if err == io.EOF { break }
return "", err // f will be closed if we return here.
}
}
return string(result), nil // f will be closed if we return here.
}
goroutines with go (go by example)
$ go run goroutines.go
direct : 0
direct : 1
direct : 2
goroutine : 0
going
goroutine : 1
goroutine : 2
done
func f(from string) {
for i := 0; i < 3; i++ {
fmt.Println(from, ":", i)
}
}
func main() {
f("direct")
go f("goroutine")
go func(msg string) {
fmt.Println(msg)
}("going")
time.Sleep(time.Second)
fmt.Println("done")
}
Go is designed to avoid “footguns”.
It stops you from doing things like…
Having undeclared variables!
$ go run prog.go
./prog.go:6:2: a declared and not used
Go build failed.
func main() { a := "hi" } |
opinionated languages
Go is part of a larger trend of opinionated / “restrictive” languages:
Many languages restrict you from doing things that you can do in C and C++.
Core argument: what we’ve learned in class from C & C++’s weak typing, and similar arguments to memory safety, threads, and more!
Rust
A better C++ (for systems programming)?
Some neat things about Rust:
Also has a super vibrant community, and is well-loved: Rust is the most-loved language 7 years running in the SO Dev Survey!
Rust & Memory Safety
Rust does not allow (and catches at compile time):
What’s the secret sauce?
First: let’s review our memory model. What’s probably going on?
let s1 = String::from("hello");
let s2 = s1;
// ... some stuff happens
println!("{}, world!", s1);
In Rust (and most langs): a shared reference!
let s1 = String::from("hello");
let s2 = s1;
// ... some stuff happens
println!("{}, world!", s1);
Okay, so … what could go wrong?
let s1 = String::from("hello");
let s2 = s1;
// ... some stuff happens
println!("{}, world!", s1);
Yikes!!
let s1 = String::from("hello");
let s2 = s1;
delete(s2);
println!("{}, world!", s1);
This is really bad! We’re inadvertently also affecting s1!
Then, this becomes a use-after-free!
Rust & Memory Safety
Rust does not allow (and catches at compile time):
What’s the secret sauce? Lifetimes, bindings, and references!
Rust’s solution!
let s1 = String::from("hello");
let s2 = s1;
// ... some stuff happens
println!("{}, world!", s1);
Here, s1’s lifetime ends.
Then, this becomes a compile-time error in Rust.
$ cargo run
Compiling ownership v0.1.0 (file:///projects/ownership)
error[E0382]: borrow of moved value: `s1`
--> src/main.rs:5:28
|
2 | let s1 = String::from("hello");
| -- move occurs because `s1` has type `String`, which does not implement the `Copy` trait
3 | let s2 = s1;
| -- value moved here
4 |
5 | println!("{}, world!", s1);
| ^^ value borrowed here after move
|
= note: this error originates in the macro `$crate::format_args_nl` (in Nightly builds, run with -Z macro-backtrace for more info)
For more information about this error, try `rustc --explain E0382`.
error: could not compile `ownership` due to previous error
“but matt”, you say,
“that seems really inconvenient…”
and you’d be right!
there are, of course, still ways to work with strings in Rust.
bigger picture: like with functional programming, Rust adds restrictions to your code. The tradeoff?
Memory Safety!
(and it turns out, this tradeoff is often worth it!)
Lisp & Scheme & Racket
Lisp is the second oldest high-level PL!
Used to be heavily used for AI research & NLP.
Huge influences in:
Lisp & Scheme & Racket
A Lisp dialect made by Guy Steele* and Gerald Sussman in the “Lambda papers”.
Defining features:
Bringing that all together: metaprogramming is easy!
no logo???
Lisp & Scheme & Racket
A Lisp dialect that’s also a Scheme “descendant”
Racket has some defining features:
Often used: creating & teaching PLs!
Python variants
(okay, it’s not one language)
Jython
Python on JVM
PyPy
JIT Python
CircuitPython
For microcontrollers!
Cython
Compiled Python!
Why talk about variants?
Common misconceptions:
Case study, PyPy:
And, the failure of certain separations!
here are alternative runtimes for other languages!
Ruby
A general-purpose, dynamic, and “fun” lang!
Shares many similarities with Python:
But, it has some differences:
Powers: Stripe, Shopify, GitHub, AirBnB, Coinbase, …
Ruby (and Sorbet!)
Sorbet is a static + runtime type system for Ruby.
Sorbet guesses types for 100k+ LoC libraries with only code examples, without manual intervention!
(disclaimer: matt did some OSS Sorbet work at CZI :’)))))
sig {params(name: String).returns(Integer)}
def main(name)
puts "Hello, #{name}!"
name.length
end
main("Sorbet") # ok!
main() # error: Not enough arguments provided
man("") # error: Method `man` does not exist
Sorbet catches type errors statically - in your editor!
Developers write this annotation
Cirq & Qiskit
A new frontier of programming languages*!
Both OSS Python SDKs/DSLs built by companies:
Core problem: representing quantum objects (qubits, gates, circuits) in a non-quantum PL!
If you’re interested, take Palsberg’s class!
*matt’s opinion: quantum programming is far too limited by (physical) engineering problems. “we still can’t factor 21”. but, it’s neat!
import cirq
# Pick a qubit.
qubit = cirq.GridQubit(0, 0)
# Create a circuit
circuit = cirq.Circuit(
cirq.X(qubit)**0.5, # Square root of NOT.
cirq.measure(qubit, key='m') # Measurement.
)
print("Circuit:")
print(circuit)
# Simulate the circuit several times.
simulator = cirq.Simulator()
result = simulator.run(circuit, repetitions=20)
print("Results:")
print(result)
import qiskit
# create circuit with Qiskit quantum circuit libraries
quantum_circuit = qiskit.circuit.library.QuantumVolume(5)
quantum_circuit.measure_all()
quantum_circuit.draw()
# select simulator backend
from qiskit import BasicAer
backend = BasicAer.get_backend('qasm_simulator')
# prepare your circuit to run on the simulator
optimized_circuit = qiskit.transpile(quantum_circuit, backend)
optimized_circuit.draw()
# run on simulator
job = backend.run(optimized_circuit)
result = job.result()
print(result.get_counts())
type-level programming (LiquidHaskell & Idris)
Two main languages in this field:
Why “type-level programming”?
... but what is dependent typing?
Let’s start with refinement types, like what’s in LiquidHaskell:
Q: What does it looks like this does?
A: 🤔
addPos : { a : Int | a > 0 } -> { b : Int | b > 0 } -> { n : Int | n > a & n > b }
addPos a b = a + b
... but what is dependent typing?
Let’s start with refinement types, like what’s in LiquidHaskell:
Q: What does it looks like this does?
A: this encodes three “refinements”:
And, the compiler will check these for you!
addPos : { a : Int | a > 0 } -> { b : Int | b > 0 } -> { n : Int | n > a & n > b }
addPos a b = a + b
... but what is dependent typing?
Why do we care?
Think about functions that are only defined on parts of their type’s domain:
Instead of magic values (like -1), we can embed this in the type system!
... but what is dependent typing?
Dependent typing is a true application of type-level programming; types can depend on values (and be used like any other value)!
Here’s the classic Idris example: lists where the length is part of the type!
data Vect : Nat -> Type -> Type where
Nil : Vect 0 a
(::) : (x : a) -> (xs : Vect n a) -> Vect (n + 1) a
... but what is dependent typing?
Here’s the classic Idris example: lists where the length is part of the type!
Q: why would we want this?
A: ?
data Vect : Nat -> Type -> Type where
Nil : Vect 0 a
(::) : (x : a) -> (xs : Vect n a) -> Vect (n + 1) a
... but what is dependent typing?
Here’s the classic Idris example: lists where the length is part of the type!
Q: why would we want this?
A: (among many other things) we can implement true math vectors!
data Vect : Nat -> Type -> Type where
Nil : Vect 0 a
(::) : (x : a) -> (xs : Vect n a) -> Vect (n + 1) a
total
pairAdd : Num a => Vect n a -> Vect n a -> Vect n a
pairAdd Nil Nil = Nil
pairAdd (x :: xs) (y :: ys) = x + y :: pairAdd xs ys
if you found that idea interesting,�good dependent typing is a “holy grail” of PL�– and an active research area :)