Dynamic Computer Language Engineering

​

Prof. Michael Carbin

6.1120

Administrivia

• Instructors
• Prof. Michael Carbin mcarbin@csail.mit.edu 32-G782
• Teaching Assistants
• Kosi Nwabueze kosinw@mit.edu
• Website
• https://6112-fa25.github.io

What is a “Dynamic” Language?

​

​

​

​

​

​

​

1: x = “foo”;

2: print(x);

3:

4: x = 5;

5: print(x);

1: if (y > 0) :

2: x = “foo”;

3: else :

4: x = 5;

5: print(x);

1: x = new object();

2: x.f = 5;

Change the type of a variable

Variable may have different types at the same program point.

Data types themselves are flexible

Dynamic Languages?

The MITScript Project: Python -> x86

​

​

​

​

​

​

• Infinite resources
• No performance specification

​

​

​

​

​

​

• Finite resources
• Extremely performance sensitive

fun(y) {

x = y - 2;

return x;

};

Language

Machine

Translation

fun(y) {

x = y - 2;

};

function {

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

load_const 1

sub

store_local 1

load_const 0

return

]

}

​

function __function_1 (y) : {

%x = alloca int64_t

%0 = %y

%1 = 2

%2 = sub %0 %1

store %x %2

%3 = 0

return %3

}

__function_1 :

sub 8 %rsp

mov %rsp %rbp

mov (%rbp, 2, 8) %rax

mov 2 %rcx

sub %rcx %rax

mov %rax (%rbp)

mov 0 %rax

ret

High-Level

VM

Low-Level

VM

Machine Code

Language

The MITScript Project: The Five Phases

1. Parser (Formal Grammars and Parsing Theory)
2. Interpreter (Program Semantics)
3. Garbage Collector (Memory Management)
4. Virtual Machine (Syntax-Directed Translation)
5. Code Generation and Optimization (Efficiency)

​

Last day of class: Project Derby!

Each Phase

• Phase Start
• Project Description and Specification
• Lectures
• 2 – 5 lectures
• Deliverables
• Implementation
• Design Document
• Extra Credit Project Checkpoints
• Presentation (for Phase 5)

Project Organization (Groups)

• 1^st and 2^nd phases are done individually
• At the end of Phase 2, each student should have a complete understanding of the MITScript language (syntax and semantics)
• Phases 3 to 5 are done in groups
• Each group consists of 3 students
• Grading
• For group segments, single graded submission, but also individual assessment of relative contribution.

​

More Information

• Blank slate project – you will receive very little starting code
• The project is challenging
• You are on your own (with our support)
• Collaboration policy
• Free to talk
• Write all the code yourself (or within your group)
• Allowed to use LLMs, see LLM Policy on website
• Accepted Language:
• C/C++ (see calendar for Intro C++ recitations)

6.1120: Coursework and Grading (Tentative)

• Project = 85%
• Phase 1 and Phase 2 = 25%
• Phase 3 = 20%
• Phase 4 = 15%
• Phase 5 = 35%
• Quiz = 10%
• Miniquizzes/class participation = 5%

Mini Quizzes

• One is already available
• Collaboration is OK
• If you submit any answer, even if incorrect, you get full credit
• Designed to help you gauge your own understanding of the material
• This is in lieu of time-consuming problem sets, gives you the opportunity to check fundamentals that will be assessed on the quiz

6.1120: Coursework and Grading (Tentative)

• Project = 85%
• Phase 1 and Phase 2 = 25%
• Phase 3 = 20%
• Phase 4 = 15%
• Phase 5 = 35%
• Quiz = 10%
• Miniquizzes/class participation = 5%

The MITScript Project: Python -> x86

​

​

​

​

​

​

• Infinite resources
• No performance specification

fun(y) {

x = y - 2;

return x;

};

Language

Machine

​

​

​

​

​

​

• Finite resources
• Extremely performance sensitive

What a Language Environment Does (Typically)

• Input: High-level programming language
• Output: Low-level assembly instructions

​

• The translation:
• Read and understand the program
• Precisely determine what actions it requires
• Figure-out how to faithfully carry out those actions
• Instruct the computer to carry out those actions

Why Study Language Environments?

• Interpreters, virtual machines, and compilers enable programming at a high level language instead of machine instructions.
• Malleability, Portability, Modularity, Simplicity, Programmer Productivity
• Also Efficiency and Performance

​

• Indispensable programmer productivity tool

​

• One of most complex software systems to build

The MITScript Project: Python -> x86

​

​

​

​

​

​

• Infinite resources
• No performance specification

fun(y) {

x = y - 2;

return x;

};

Language

Machine

​

​

​

​

​

​

• Finite resources
• Extremely performance sensitive

The MITScript Project: The Five Phases

• Parser (Formal Grammars and Parsing Theory)

​

• Interpreter (Program Semantics)

​

• Garbage Collector (Memory Management)�
• Virtual Machine (Syntax-Directed Translation)

​

• Code Generation and Optimization (Efficiency)

MITScript Environment

• Language (“What”)
• Parser (Syntax)
• Interpreter (Semantics)
• Virtual Machine (“How”)
• Instruction Set (single operations)
• Execution Organization (code, stack, heap)
• Memory Management
• Machine Code (“the truth”)
• Instruction Set
• Execution Organization (Segments, Stack, Pages)

Virtual Machine

Language

High-Level

VM

Machine Code

Low-Level

VM

Interpreter (Semantics)

• Goal: Provide a specification of the behavior of a program

​

​

• Precise: detailed enough to produce an implementation

​

• Complete: covers all features of the language

​

• Unambiguous: reasonable interpretations lead to the same result

​

• Balanced: communicates design goals of the language (i.e., correctness) leaves implementers some choice in implementation (i.e., performance)

x = 1 + 2 * 3;

Example: Semantics

​

​

​

​

​

​

• Multiply is overloaded based on the type of its input:

multiply(string, int) -> string (and ruby coerces 2.2 to 2)

multiply(float, float) -> float (does what one expects)

test1.rb:

_____________________________

​

print ARGV[0] * 2.2

​

> ruby test1.rb 100

> 100100

test2.rb:

_____________________________

​

print 2.2 * ARGV[0]

​

> ruby test2.rb 100

> *': String can't be coerced into Float (TypeError)

MITScript Virtual Machine

f = fun(y) {

x = y - 2;

};

f(1);

Organization (Code, Stack, and Heaps)

• Code
• Instructions
• Functions
• Metadata

Organization (Code, Stack, and Heaps)

• Globals
• Stacks
• Locals
• Instruction pointer
• Operand Stack
• Heaps
• Associative Array

MITScript VM

Heap

Stack

Frame

MITScript VM

Heap

Stack

Frame

MITScript VM

Heap

Stack

Frame

MITScript VM

Heap

Stack

Frame

MITScript VM

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

MITScript VM

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

MITScript VM

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

MITScript VM

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

MITScript VM

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

MITScript VM

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

MITScript VM

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

MITScript VM

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

Stack

Frame

MITScript VM

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

Stack

Frame

MITScript VM

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

Stack

Frame

MITScript VM

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

Stack

Frame

MITScript VM

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

Stack

Frame

MITScript VM

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

Stack

Frame

MITScript VM

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

MITScript VM

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

MITScript VM

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

MITScript VM

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

Dynamic Languages are Slow

In C:

​

//assuming y is in r1 and t is in r3

//puts the result in r2.

​

mov $r2, 7

add $r2 $r1

add $r2 $r3

In a dynamic language:

​

Check what type of value y is.

Get the integer value from the value object of y�Get the integer value from the value object of 7

Allocate a new object value to store y + 7

Check that the new value is an integer

Check that t is an integer

Allocate a new object value to store (y+7)+t

Make x point to new object

x = (y + 7) + t

Dynamic Languages are Slow

// t is in $r1, v is in $r3

​

allocate a block of sizeof(X) bytes of memory store address in $r1

$r2 = $r1 + offset(X, x)

mov addr($r2) 5

mov $r3, addr($r2)

Allocate a new map from strings to vals

Allocate a new value 5.

Check that t stores a map value

Perform an insert operation in map t with key “x” to store value 5.

Check that t stores a map value

Perform a lookup operation on map t with key “x”

Write value to v

​

struct X { int x; int y; }

​

t = new X();

t.x = 5;

v = t.x;

t = object { }

t.x = 5;

v = t.x

Code Generation and Optimization

• Analysis
• Statically (or dynamically) identify facts about the program

​

• Transformation
• Use facts to transform the code to a more efficient version

For Dynamic Language

__function_1 :

push %rdi

call assert_integer

pop %rax

shr $3 %rax

mov $2 %rcx

sub %rcx %rax

ret

void execute() {

Frame f = ...;

​

push(f.locals[0]);

push(f.constants[1]);

Value* op2 = pop(stack);

assert_integer(op2);

Value* op1 = pop(stack);

assert_integer(op2);

auto* result =

new Integer((Int *) op1->value – ((Int *)op2)->value);

push(result);

​

Value* op3 = pop(stack);

f.locals[1] = op3;

push(f.constants[0]);

Value* op4 = pop(stack);

return op4;

}

Instructions: > 1000s -> 7

Function Calls: 10s -> 1

Memory Accesses: 100s -> 2

Allocations: > 1 -> 0

fun(y) {

x = y - 2;

};

Optimization Example

int sumcalc(int a, int b, int N)

{

int i;

int x, y;

x = 0;

y = 0;

for(i = 0; i <= N; i++) {

x = x + (4*a/b)*i + (i+1)*(i+1);

x = x + b*y;

}

return x;

}

45

pushq %rbp

movq %rsp, %rbp

movl %edi, -4(%rbp)

movl %esi, -8(%rbp)

movl %edx, -12(%rbp)

movl $0, -20(%rbp)

movl $0, -24(%rbp)

movl $0, -16(%rbp)

.L2: movl -16(%rbp), %eax

cmpl -12(%rbp), %eax

jg .L3

movl -4(%rbp), %eax

leal 0(,%rax,4), %edx

leaq -8(%rbp), %rax

movq %rax, -40(%rbp)

movl %edx, %eax

movq -40(%rbp), %rcx

cltd

idivl (%rcx)

movl %eax, -28(%rbp)

movl -28(%rbp), %edx

imull -16(%rbp), %edx

movl -16(%rbp), %eax

incl %eax

imull %eax, %eax

addl %eax, %edx

leaq -20(%rbp), %rax

addl %edx, (%rax)

movl -8(%rbp), %eax

movl %eax, %edx

imull -24(%rbp), %edx

leaq -20(%rbp), %rax

addl %edx, (%rax)

leaq -16(%rbp), %rax

incl (%rax)

jmp .L2

.L3: movl -20(%rbp), %eax

leave

ret

Lets Optimize...

int sumcalc(int a, int b, int N)

{

int i, x, y;

x = 0;

y = 0;

for(i = 0; i <= N; i++) {

x = x + (4*a/b)*i + (i+1)*(i+1);

x = x + b*y;

}

return x;

}

Constant Propagation

int i, x, y;

x = 0;

y = 0;

for(i = 0; i <= N; i++) {

x = x + (4*a/b)*i + (i+1)*(i+1);

x = x + b*y;

}

return x;

​

​

Constant Propagation

​

int i, x, y;

x = 0;

y = 0;

for(i = 0; i <= N; i++) {

x = x + (4*a/b)*i + (i+1)*(i+1);

x = x + b*y;

}

return x;

​

​

Constant Propagation

​

int i, x, y;

x = 0;

y = 0;

for(i = 0; i <= N; i++) {

x = x + (4*a/b)*i + (i+1)*(i+1);

x = x + b*0;

}

return x;

​

​

Algebraic Simplification

​

int i, x, y;

x = 0;

y = 0;

for(i = 0; i <= N; i++) {

x = x + (4*a/b)*i + (i+1)*(i+1);

x = x + b*0;

}

return x;

​

​

Algebraic Simplification

​

int i, x, y;

x = 0;

y = 0;

for(i = 0; i <= N; i++) {

x = x + (4*a/b)*i + (i+1)*(i+1);

x = x + b*0;

}

return x;

​

​

Algebraic Simplification

int i, x, y;

x = 0;

y = 0;

for(i = 0; i <= N; i++) {

x = x + (4*a/b)*i + (i+1)*(i+1);

x = x;

}

return x;

​

​

Copy Propagation

​

int i, x, y;

x = 0;

y = 0;

for(i = 0; i <= N; i++) {

x = x + (4*a/b)*i + (i+1)*(i+1);

x = x;

}

return x;

​

​

​

Copy Propagation

​

int i, x, y;

x = 0;

y = 0;

for(i = 0; i <= N; i++) {

x = x + (4*a/b)*i + (i+1)*(i+1);

x = x;

}

return x;

​

​

​

Copy Propagation

int i, x, y;

x = 0;

y = 0;

for(i = 0; i <= N; i++) {

x = x + (4*a/b)*i + (i+1)*(i+1);

}

return x;

​

​

​

Common Subexpression Elimination

​

int i, x, y;

x = 0;

y = 0;

for(i = 0; i <= N; i++) {

x = x + (4*a/b)*i + (i+1)*(i+1);

}

return x;

​

​

​

​

Common Subexpression Elimination

​

int i, x, y;

x = 0;

y = 0;

for(i = 0; i <= N; i++) {

x = x + (4*a/b)*i + (i+1)*(i+1);

}

return x;

​

​

​

​

Common Subexpression Elimination

​

int i, x, y, t;

x = 0;

y = 0;

for(i = 0; i <= N; i++) {

t = i+1;

x = x + (4*a/b)*i + t*t;

}

return x;

​

​

​

​

Dead Code Elimination

​

int i, x, y, t;

x = 0;

y = 0;

for(i = 0; i <= N; i++) {

t = i+1;

x = x + (4*a/b)*i + t*t;

}

return x;

​

Dead Code Elimination

​

int i, x, y, t;

x = 0;

y = 0;

for(i = 0; i <= N; i++) {

t = i+1;

x = x + (4*a/b)*i + t*t;

}

return x;

​

Dead Code Elimination

​

int i, x, t;

x = 0;

​

for(i = 0; i <= N; i++) {

t = i+1;

x = x + (4*a/b)*i + t*t;

}

return x;

​

Loop Invariant Removal

​

int i, x, t;

x = 0;

​

for(i = 0; i <= N; i++) {

t = i+1;

x = x + (4*a/b)*i + t*t;

}

return x;

Loop Invariant Removal

​

int i, x, t;

x = 0;

​

for(i = 0; i <= N; i++) {

t = i+1;

x = x + (4*a/b)*i + t*t;

}

return x;

Loop Invariant Removal

​

int i, x, t, u;

x = 0;

u = (4*a/b);

for(i = 0; i <= N; i++) {

t = i+1;

x = x + u*i + t*t;

}

return x;

​

Strength Reduction

​

int i, x, t, u;

x = 0;

u = (4*a/b);

​

for(i = 0; i <= N; i++) {

t = i+1;

x = x + u*i + t*t;

​

}

return x;

Strength Reduction

​

int i, x, t, u;

x = 0;

u = (4*a/b);

​

for(i = 0; i <= N; i++) {

t = i+1;

x = x + u*i + t*t;

​

}

return x;

Strength Reduction

​

int i, x, t, u, v;

x = 0;

u = ((a<<2)/b);

v = 0;

for(i = 0; i <= N; i++) {

t = i+1;

x = x + v + t*t;

v = v + u;

}

return x;

​

​

Optimized Example

int sumcalc(int a, int b, int N)

{

int i, x, t, u, v;

x = 0;

u = ((a<<2)/b);

v = 0;

for(i = 0; i <= N; i++) {

t = i+1;

x = x + v + t*t;

v = v + u;

}

return x;

}

xorl %r8d, %r8d

xorl %ecx, %ecx

movl %edx, %r9d

cmpl %edx, %r8d

jg .L7

sall $2, %edi

.L5: movl %edi, %eax

cltd

idivl %esi

leal 1(%rcx), %edx

movl %eax, %r10d

imull %ecx, %r10d

movl %edx, %ecx

imull %edx, %ecx

leal (%r10,%rcx), %eax

movl %edx, %ecx

addl %eax, %r8d

cmpl %r9d, %edx

jle .L5

.L7: movl %r8d, %eax

ret

​

pushq %rbp

movq %rsp, %rbp

movl %edi, -4(%rbp)

movl %esi, -8(%rbp)

movl %edx, -12(%rbp)

movl $0, -20(%rbp)

movl $0, -24(%rbp)

movl $0, -16(%rbp)

.L2: movl -16(%rbp), %eax

cmpl -12(%rbp), %eax

jg .L3

movl -4(%rbp), %eax

leal 0(,%rax,4), %edx

leaq -8(%rbp), %rax

movq %rax, -40(%rbp)

movl %edx, %eax

movq -40(%rbp), %rcx

cltd

idivl (%rcx)

movl %eax, -28(%rbp)

movl -28(%rbp), %edx

imull -16(%rbp), %edx

movl -16(%rbp), %eax

incl %eax

imull %eax, %eax

addl %eax, %edx

leaq -20(%rbp), %rax

addl %edx, (%rax)

movl -8(%rbp), %eax

movl %eax, %edx

imull -24(%rbp), %edx

leaq -20(%rbp), %rax

addl %edx, (%rax)

leaq -16(%rbp), %rax

incl (%rax)

jmp .L2

.L3: movl -20(%rbp), %eax

leave

ret

​

Unoptimized Code

Optimized Code

For Dynamic Language

__function_1 :

push %rdi

call assert_integer

pop %rax

shr $3 %rax

mov $2 %rcx

sub %rcx %rax

ret

void execute() {

Frame f = ...;

​

push(f.locals[0]);

push(f.constants[1]);

Value* op2 = pop(stack);

assert_integer(op2);

Value* op1 = pop(stack);

assert_integer(op2);

auto* result =

new Integer((Int *) op1->value – ((Int *)op2)->value);

push(result);

​

Value* op3 = pop(stack);

f.locals[1] = op3;

push(f.constants[0]);

Value* op4 = pop(stack);

return op4;

}

Instructions: > 1000s -> 7

Function Calls: 10s -> 1

Memory Accesses: 100s -> 2

Allocations: > 1 -> 0

fun(y) {

x = y - 2;

};

Optimize Programs for…

• Performance/Speed
• Code Size
• Energy Consumption
• Fast/Efficient Compilation
• Security/Reliability (Spectre and Meltdown)
• Debugging

The MITScript Project: The Five Phases

• Parser (Formal Grammars and Parsing Theory)

​

• Interpreter (Program Semantics)

​

• Virtual Machine (Syntax-Directed Translation)

​

• Garbage Collector (Memory Management)

​

• Code Generation and Optimization (Efficiency)

Language Environment Construction touches �many topics in Computer Science

• Theory
• Finite State Automata, Grammars and Parsing, data-flow
• Algorithms
• Graph manipulation, dynamic programming
• Data structures
• Symbol tables, abstract syntax trees
• Systems
• Allocation and naming, multi-pass systems, compiler construction
• Computer Architecture
• Memory hierarchy, instruction selection, interlocks and latencies, parallelism
• Security
• Detection of and Protection against vulnerabilities
• Software Engineering
• Software development environments, debugging
• Artificial Intelligence
• Heuristic based search for best optimizations
• Principles that inform translating natural language to code (vibecoding with copilot, cursor, etc)